akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
ll N, M;
ll A[101010];

int main()
{
    cin >> N >> M;
    ll sum = 0;
    rep(i, 0, M)
    {
        cin >> A[i];
        sum += A[i];
    }
    ll ans = N - sum;
    if (ans < 0)
    {
        cout << "-1" << endl;
        return 0;
    }
    else
    {
        cout << ans << endl;
    }
}


Measured memory_bytes: 3676
N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_fall = []
for i in range(N):
  ai = A[i]
  fall_point1 = 0
  if i != N-1:
    for j in range(i+1, N):
      aj = A[j]
      if ai > aj:
        fall_point1 += 1
  fall_point2 = 0
  for n in range(N):
    an = A[n]
    if ai > an:
      fall_point2 += 1
  A_fall.append([fall_point1, fall_point2])

ans = 0
for i in range(N):
  x, y = A_fall[i]
  fall_point = (x*K + y*(K-1)*K//2) % 1000000007
  ans += fall_point

print(ans % 1000000007)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
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;}
//小数点以下　cout << fixed << setprecision(10) << num << endl;

int main(){
    int m; cin >> m;
    int d[m];
    ll c[m];
    ll ans = 0;
    vector<int> v;
    ll res=0;
    rep(i,m){
        cin >> d[i] >> c[i];
        ans+=c[i];
        res+=d[i]*c[i];
    }
    ans+=(res-1)/9;
    ans--;
    cout << ans;
}


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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    ll a, b, k;
    cin >> a >> b >> k;
    if(a + b <= k){
        a = 0;
        b = 0;
    }else{
        if(a <= k){
            k = k - a;
            a = 0;
            if(b <= k){
                b = 0;
            }else{
                b = b - k;
            }
        }else{
            a = a - k;
        }
    }
    cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, H, W;
  cin >> N >> H >> W;
  vector<int> A(N);
  vector<int> B(N);
  for(int i = 0; i < N; i++){
    cin >> A.at(i) >> B.at(i);
  }
  int ans = 0;
  for(int i = 0; i < N; i++){
    if(A.at(i) >= H && B.at(i) >= W)ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3568
#include<iostream>
#include<cmath>
#include<iomanip>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++) 
#define rep1(i,n) for(int i=1;i<(n);i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "

long double power(int v){
    long double p = 1.0;
    rep(i,-v) p /= 2;
    return p;
}

int main(int argc, const char *argv[]){
    int n,k;
    cin >> n >> k;
    long double p = 0.0;
    rep1(i,n+1){
        int o = (-int(log2((long double)(k-1)/(long double)i)+1));
        p += power(min(o,0))/(long double)n;
        //if(i<10)  co((long double)power(min(o,0))/(long double)n);
    }
    cout << fixed << setprecision(15) << p << endl; 
    return 0;
}

Measured memory_bytes: 384
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <thread>
#include <unordered_set>
#include <vector>
#include <memory.h>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <stdio.h>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <random>
#include <string>
#include <cassert>


#define getcx _getchar_nolock

using namespace std;
 
namespace std
{
	string to_string(string const& s) { return '"' + s + '"'; }
	string to_string(char c) { return string(1, c); }
	string to_string(const char* s) { return to_string((string)s); }
	string to_string(bool b) { return (b ? "true" : "false"); }
 
	template <class T1, class T2>
	string to_string(pair<T1, T2> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
 
	template <class T>
	string to_string(T c)
	{
		string s = "[";
		for (auto vvv : c) { s += to_string(vvv) + ","; }
		s += "]";
		return s;
	}
 
	void debug_impl() { cerr << endl; };
 
	template <typename T1, typename... T2>
	void debug_impl(T1 a, T2 ... b)
	{
		cerr << " " << to_string(a);
		debug_impl(b...);
	}
}
 
template <typename T>
struct reversion_wrapper
{
	T& iterable;
};
 
template <typename T>
auto begin(reversion_wrapper<T> w) { return std::rbegin(w.iterable); }
 
template <typename T>
auto end(reversion_wrapper<T> w) { return std::rend(w.iterable); }
 
template <typename T>
reversion_wrapper<T> reverse(T&& iterable) { return { iterable }; }
 
template<class T>T gcd(T a, T b) { while (a && b)if (a > b)a %= b; else b %= a; return a + b; }
template<class T>T powmod(T a, T b, T mod) { if (b == 0)return 1 % mod; T res = powmod(a, b / 2, mod); res *= res; res %= mod; if (b & 1) { res *= a; res %= mod; } return res; }
template<class T>T inv(T a, T mod) { return powmod(a, mod - 2, mod); }
 
#ifdef __ASD__
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_impl(__VA_ARGS__)
#define endl "\n"
#else
#define dbg(...) ;
#define endl "\n"
#endif
 
#define lng long long

lng const MOD = 998244353;


int main()
{
#ifdef __ASD__
	auto start_t = chrono::steady_clock::now();
	freopen("input.txt", "r", stdin);
	//freopen("1nul", "w", stderr);
	//freopen("output.txt", "w", stdout);
#else
	ios_base::sync_with_stdio(false);
#endif

	int k, n;
	cin >> k >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++)cin>>a[i];

	vector<int> d;

	for(int i=1;i<n;i++) {
		d.push_back(a[i]-a[i-1]);
	}
	d.push_back(k-(a.back()-a[0]));

	int s=0;
	for(int x:d)s+=x;
	cout<<s-*max_element(d.begin(), d.end())<<endl;

#ifdef __ASD__
	auto finish_t = chrono::steady_clock::now();
	cerr << "Elapsed " << chrono::duration_cast<chrono::milliseconds>(finish_t - start_t).count() << " ms" << endl;
#endif
	return 0;
}

Measured memory_bytes: 2168
import itertools

def calculate_distance(o, n):
    return ((o[0]-n[0])**2 + (o[1]-n[1])**2)**0.5

n = int(input())
position = []
distance_list = []

for _ in range(n):
    position.append(list(map(int, input().split())))


for target in itertools.permutations(position):
    old = target[0]
    distance = 0
    for new in target:
        distance += calculate_distance(old, new)
    distance_list.append(distance)

print(sum(distance_list)/len(distance_list))

Measured memory_bytes: 4376
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
const int INF=1e9;
using namespace std;

int sod(int n){
    int sum=0;
    while(n>0){
        sum+=n%10;
        n/=10;
    }
    return sum;
}
int main(){
    int n, a, b;
    cin>>n>>a>>b;
    int ans=0;
    for(int i=1; i<=n; i++){
        if(a<=sod(i)&&sod(i)<=b)ans+=i;
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 256
X = int(input())
maxN = 10**5 + 1000
isPrime=[True]*(maxN+1)
isPrime[0],isPrime[1] = False,False

for i in range(2,maxN+1):
    if not(isPrime[i]):
        continue
    tmp = i*2
    while tmp<maxN:
        isPrime[tmp] = False
        tmp += i

ans = X
while not(isPrime[ans]):
    ans += 1
print(ans)

Measured memory_bytes: 3828
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  dead_code
)]
use proconio::fastout;
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;
//use std::collections::VecDeque;

macro_rules! debug {
  ($($a:expr),* $(,)*) => {
      #[cfg(debug_assertions)]
      eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
  };
}

#[fastout]
fn main() {
  input! {
     N:usize,
     XYP:[(i64,i64,i64);N]
  }
  let N: usize = N;
  let mut XYP: Vec<(i64, i64, i64)> = XYP;
  let inf = std::i64::MAX;
  let mut xkyori = vec![vec![inf; N]; 2usize.pow(N as u32)];
  let mut ykyori = vec![vec![inf; N]; 2usize.pow(N as u32)];

  for pat_i in 0..2usize.pow(N as u32) {
    // 組み合わせの作成
    let mut pat = vec![0; N];
    for i in 0..N {
      pat[i] = pat_i >> i & 1;
    }
    // 各patternについて、各都市からのX距離とY距離を計算する。
    for i in 0..N {
      if pat[i] == 1 {
        // 都市 i に鉄道が引かれている場合の距離は0。
        xkyori[pat_i][i] = 0;
        ykyori[pat_i][i] = 0;
      } else {
        // そうでない場合、すべての路線への距離の最小値を求める。
        let (x, y, p) = XYP[i];
        xkyori[pat_i][i] = x.abs();
        ykyori[pat_i][i] = y.abs();
        for j in 0..N {
          if pat[j] == 1 {
            xkyori[pat_i][i] = min(xkyori[pat_i][i], (x - XYP[j].0).abs());
            ykyori[pat_i][i] = min(ykyori[pat_i][i], (y - XYP[j].1).abs());
          }
        }
        xkyori[pat_i][i] *= p;
        ykyori[pat_i][i] *= p;
      }
      debug!(pat,i,xkyori[pat_i]);
    }
  }
  debug!(xkyori);
  debug!(ykyori);
  // ここまでで前処理。xkyoriとykyoriが計算できた。
  let mut ans = vec![inf; N + 1];
  // 3進数を計算。0=線路なし,1=X路線, 2=Y路線
  for pat_i in 0..3usize.pow(N as u32) {
    // pat_xとpat_yの作成
    let mut k = 0;
    let mut pat = pat_i;
    let mut pat_x = 0;
    let mut pat_y = 0;
    for i in 0..N {
      match pat % 3 {
        1 => {
          pat_x += 2usize.pow(i as u32);
          k += 1;
        }
        2 => {
          pat_y += 2usize.pow(i as u32);
          k += 1;
        }
        _ => (),
      }
      pat = pat / 3;
    }
    let mut t_ans = 0;
    for i in 0..N {
      t_ans += min(xkyori[pat_x][i], ykyori[pat_y][i]);
    }
    ans[k] = min(ans[k], t_ans);
  }
  for a in ans {
    println!("{}", a);
  }
}


Measured memory_bytes: 11788
/*
        _            _                  _            _       _     _         _   _          _          _             _        
       / /\         / /\               / /\         / /\    / /\  /\ \      /\_\/\_\ _     /\ \       /\ \     _    /\ \      
      / /  \       / /  \             / /  \       / / /   / / /  \ \ \    / / / / //\_\   \ \ \     /  \ \   /\_\ /  \ \     
     / / /\ \__   / / /\ \           / / /\ \__   / /_/   / / /   /\ \_\  /\ \/ \ \/ / /   /\ \_\   / /\ \ \_/ / // /\ \_\    
    / / /\ \___\ / / /\ \ \         / / /\ \___\ / /\ \__/ / /   / /\/_/ /  \____\__/ /   / /\/_/  / / /\ \___/ // / /\/_/    
    \ \ \ \/___// / /  \ \ \        \ \ \ \/___// /\ \___\/ /   / / /   / /\/________/   / / /    / / /  \/____// / / ______  
     \ \ \     / / /___/ /\ \        \ \ \     / / /\/___/ /   / / /   / / /\/_// / /   / / /    / / /    / / // / / /\_____\ 
 _    \ \ \   / / /_____/ /\ \   _    \ \ \   / / /   / / /   / / /   / / /    / / /   / / /    / / /    / / // / /  \/____ / 
/_/\__/ / /  / /_________/\ \ \ /_/\__/ / /  / / /   / / /___/ / /__ / / /    / / /___/ / /__  / / /    / / // / /_____/ / /  
\ \/___/ /  / / /_       __\ \_\\ \/___/ /  / / /   / / //\__\/_/___\\/_/    / / //\__\/_/___\/ / /    / / // / /______\/ /   
 \_____\/   \_\___\     /____/_/ \_____\/   \/_/    \/_/ \/_________/        \/_/ \/_________/\/_/     \/_/ \/___________/    
                                                                                                                              
*/
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb emplace_back
#define mkp make_pair
#define p_q priority_queue
#define INF 1000000000
#define PI 3.1415926
#define coutdb cout << fixed << setprecision(10)

const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int long long

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

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

  int N, W[100]; cin >> N;
  int sum = 0;
  REP(i, N){
    cin >> W[i];
    sum += W[i];
  }
  int num = 0;
  int ans = 114514;
  REP(i, N){
    num += W[i];
    ans = min(ans, abs(num-(sum-num)));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
ll n,s;
bool ok(ll b){
	ll p=0,a=n;
	while(a){
		p+=(a%b);
		a/=b;
	}
	return p==s;
}
vector<ll>o;
int main(void){
	cin>>n>>s;
	ll v=abs(n-s);
	if(v==0){
		printf("%lld\n",n+1);
		return 0;
	}
	for(ll i=1;i*i<=v;i++){
		if(v%i==0){
			o.PB(i);
			o.PB(v/i);
		}
	}
	sort(o.begin(),o.end());
	for(int i=0;i<o.size();i++){
		if(ok(o[i]+1)){
			printf("%lld\n",o[i]+1);
			return 0;
		}
	}
	printf("-1\n");
}


Measured memory_bytes: 256
package main

import "fmt"

func isProductOdd(a int, b int) bool {
	return a*b%2 != 0
}

func main() {
	var a int
	var b int

	fmt.Scan(&a)
	fmt.Scan(&b)
	if isProductOdd(a, b) {
		fmt.Println("Odd")
	} else {
		fmt.Println("Even")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll MOD = 1e9+7;

#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>

#define rep(i,n)         for(int i=(int)0; i<(int)n; i++)
#define REP(i,m,n)       for(int i=(int)m; i<(int)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define prt(var)         cout << var << endl
#define prtd(n, var)     cout << fixed << setprecision(n) << var << endl
#define prt2(v1, v2)     cout << v1 << " " << v2 << endl
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << endl
#define prtall(var)      rep(i,var.size()){cout << var[i] << " ";} cout << endl

//----------------------------------------------------------------

int main(void) {
  int n;
  cin >> n;
  arrll(p,n);

  int ans=0;
  ll tmp=LONG_MAX;
  rep(i,n){
    if(p[i]<tmp){
      ans++; tmp=p[i];
    }
  }
  prt(ans);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include <set>

#define DIV 1000000007
using namespace std;
using ll = long long;

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

    vector<set<int>> alp(26);
    //cout<<"start"<<endl;
    for (int i = 0; i < N; i++) {
        alp[S[i] - 'a'].insert(i);
    }
    
    for (int i = 0; i < Q; i++) {
        int com;
       // cout << "i=" << i << endl;
        cin >> com;
        if (com == 1) {
            int id;
            char moji;
            cin >> id >> moji;
            id--;
            alp[S[id] - 'a'].erase(id);
            S[id] = moji;
            alp[moji - 'a'].insert(id);
        }

        else if (com == 2) {
            int left, right;
            cin >> left >> right;
            left--, right--;
            int cnt = 0;
            for (int j = 0; j < 26; j++) {
                //int min = lower_bound(alp[j].begin(), alp[j].end(), left);
                auto min = alp[j].lower_bound(left);
                if (min != alp[j].end() && *min <= right)cnt++;
            }
            cout << cnt << endl;
        }

    }
}


Measured memory_bytes: 24196
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ldouble = long double;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s) cout << fixed << setprecision(10) << s << endl;


int main()
{
	vector<string> a(3);

	string res = "YES";
	for (ll i = 0; i < 3; i++)
	{
		cin >> a[i];

		if (i > 0)
		{
			if (a[i - 1].back() != a[i].front())
			{
				res = "NO";
			}
		}
	}

	println(res);
}


Measured memory_bytes: 3620
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;
struct Edge{ll from, to, cost;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  string S;
  ll N;
  cin >> N;
  cin >> S;
  vector<ll> r, g, b;

  /*
  for(ll k=1;k<(N+1)/2; k++){
    rep(i, N){
      if(S[i]!=S[])
    }
  }*/
  
  rep(i, N){
    if(S[i]=='R')r.push_back(i);
    if(S[i]=='G')g.push_back(i);
    if(S[i]=='B')b.push_back(i);
  }

  ll ans = 0;
  for(ll i=1;i<N-1;i++){
    for(ll j=0;j<i;j++){
      if(S[j]==S[i]){
        continue;
      }else{
        if((S[i]=='R' and S[j]=='G') or (S[i]=='G' and S[j]=='R')){
          ll num =(ll)(b.end() -lower_bound(ALL(b), i));
          if( binary_search(ALL(b),2*i-j))num-=1;
          ans += num;
        }
        if((S[i]=='B' and S[j]=='G') or (S[i]=='G' and S[j]=='B')){
          ll num =(ll)(r.end() -lower_bound(ALL(r), i));
          if( binary_search(ALL(r),2*i-j))num-=1;
          ans += num;
        }
        if((S[i]=='R' and S[j]=='B') or (S[i]=='B' and S[j]=='R')){
          ll num =(ll)(g.end() -lower_bound(ALL(g), i));
          if( binary_search(ALL(g),2*i-j))num-=1;
          ans += num;
        }
        /*
        if(S[i]=='R' and S[j]=='B'){
          ll num = g.end() - g.upper_bound(i);
          if(g.find(i+i-j))num-=1;
          ans += num;
          
        }
        if(S[i]=='B' and S[j]=='G'){
          ll num = r.end() - r.upper_bound(i);
          if(r.find(i+i-j))num-=1;
          ans += num;
          
        }
        if(S[i]=='B' and S[j]=='R'){
          ll num = g.end() - g.upper_bound(i);
          if(g.find(i+i-j))num-=1;
          ans += num;
          
        }
        if(S[i]=='G' and S[j]=='R'){
          ll num = b.end() - b.upper_bound(i);
          if(b.find(i+i-j))num-=1;
          ans += num;          
        }
        if(S[i]=='G' and S[j]=='B'){
          ll num = r.end() - r.upper_bound(i);
          if(r.find(i+i-j))num-=1;
          ans += num;          
          }*/
      }
    }
  }

  cout << ans;
  
  return 0;
}


Measured memory_bytes: 3692
import sys
input = sys.stdin.readline

def main():
	n, x = map(int, input().strip().split())
	L = list(map(int, input().strip().split()))
	i = 0
	c = 1
	for l in L:
		i += l
		if i > x:
			break
		c += 1
	print(c)

if __name__ == '__main__':
	main()


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

public class Main {
    public static String repeat(String str, int n) {
        return String.join("", Collections.nCopies(n, str));
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = reader.readLine().split(" ");
        int a = Integer.parseInt(arr[0]);
        int b = Integer.parseInt(arr[1]);
        System.out.println(a < b ? repeat(arr[0], b) : repeat(arr[1], a));
    }
}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
int main() {
    int N;
    string s;
    cin >> N;
    cin >> s;
    int a = 0;
    int b = 0;
    for(int i = 0; i < N; i++){
        if(s[i] == '#'){
            a++;
        }else if(s[i] == '.' && a > 0){
            a--;
            b++;
        }
    }
    cout << b << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pl;
#define all(a) (a).begin(),(a).end()
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,n) for(ll (i)=(n)-1;(i)>=0;i--)
#define SHOW(x) cout << #x << ": " << x << endl;
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

int main(){
    int n,k,r = 0;
    cin>>n>>k;
    while(pow(k,++r) <= n);
    cout<<r<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		while(true){
			int n = sc.nextInt();
			int t = sc.nextInt();
			int l = sc.nextInt();
			int b = sc.nextInt();

			if(n == 0){
				break;
			}

//			int loseIndex[] = new int[l];
			boolean lose[] = new boolean[n + 1];
			boolean back[] = new boolean[n + 1];

			for(int j = 0; j < l; j++){
//				loseIndex[j] = sc.nextInt();
				lose[sc.nextInt()] = true;
			}

			for(int j = 0; j < b; j++){
				back[sc.nextInt()] = true;
			}

			double[][] dp = new double[t + 1][2*n + 1];
			dp[0][0] = 1;

			for(int i = 0; i < t; i++){
				for(int j = 0; j < 2*n + 1; j++){
					if(j == n){
						dp[i + 1][j] += dp[i][j];
						continue;
					}
					else if(j > n){
						dp[i + 1][j - n] += dp[i][j];
						continue;
					}
					double tmp = dp[i][j] / 6;
					for(int k = 1; k <= 6; k++){
						int next;

						next = j + k;

						if(next > n){
							next = n - (next - n);
						}

						if(lose[next]){
							next += n;
						}
						else if(back[next]){
							next = 0;
						}

						dp[i + 1][next] += tmp;
					}
				}

//				double sum = 0;
//				for(int j = 0; j <= 2*n; j++){
//					sum += dp[i + 1][j];
//				}
//				System.out.println("sum : "+sum);
			}

//			for(int i = 0; i <= t; i++){
//				for(int j = 0; j <= 2*n; j++){
//					System.out.print(dp[i][j]+" ");
//					if(j == n){
//						System.out.print("|");
//					}
//				}
//				System.out.println();
//			}

			System.out.printf("%.6f\n",dp[t][n]);
		}
	}

}



Measured memory_bytes: 30324
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=Integer.valueOf(sc.next());
		int m=Integer.valueOf(sc.next());
		if(n==m){
			System.out.println(n);
			return;
		}else if(n>m){
			int temp=m;
			m=n;
			n=temp;
		}
		while(n!=0){
			m%=n;
			if(m==0){
				System.out.println(n);
				return;
			}
			n%=m;
		}
		System.out.println(m);
	}

}

Measured memory_bytes: 26184
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353;
constexpr int MAX = 5000000;

template<typename T>
vector<int> Z_Algorithm(vector<T> &v) {
	int n = v.size();
	vector<int> ret(n);
	ret[0] = n;
	int j = 0;
	for (int i = 1; i < n;) {
		while (i + j < n and v[j] == v[i + j]) j++;
		ret[i] = j;
		if (j == 0) { i++; continue; }
		int k = 1;
		while (i + k < n and k + ret[k] < j) ret[i + k] = ret[k], k++;
		i += k, j -= k;
	}
	return ret;
}
int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n; cin >> n;
	vector<int> ta(n); for (int i = 0; i < n; i++) cin >> ta[i];
	vector<int> tb(n); for (int i = 0; i < n; i++) cin >> tb[i];
	vector<int> a(n); for (int i = 0; i < n; i++) a[i] = (ta[i] ^ ta[(i + 1) % n]);
	vector<int> b(n); for (int i = 0; i < n; i++) b[i] = (tb[i] ^ tb[(i + 1) % n]);
	vector<int> c; c.reserve(3 * n);
	for (int i = 0; i < n; i++) c.emplace_back(b[i]);
	for (int kkt = 0; kkt < 2; kkt++) for (int i = 0; i < n; i++) c.emplace_back(a[i]);

	auto z = Z_Algorithm(c);
	vector<int> res;
	//for (int i = 0; i < n * 3; i++) cout << c[i] << " \n"[i + 1 == n * 3];
	for (int i = n; i < n * 2; i++) {

		if (z[i] >= n) res.emplace_back(i - n);
	}
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << " " << (ta[res[i]] ^ tb[0]) << "\n";
	}
	return 0;
}

Measured memory_bytes: 12520
import numpy as np
import copy
import itertools
h,w,k = map(int, input().split())
s = [list(input()) for i in range(h)]
data = np.zeros(h*w).reshape(h,w)
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            data[i][j] = 1
 
ans = 0
## 塗らない場合
if np.sum(data == 1) == k:
    ans = 1
## すべて塗った場合
if k == 0:
    ans = 1
 
a = list()
b = list()
for i in range(1,h):
    a += list(itertools.combinations(range(h), i))
for i in range(1,w):
    b += list(itertools.combinations(range(w), i))
 
for i in a:
    for j in b:
        temp = data.copy()
        temp[i,:] = 2
        temp[:,j] = 2
        if np.sum(temp == 1) == k:
            ans += 1
 
for i in a:
    temp = data.copy()
    temp[i,:] = 2
    if np.sum(temp == 1) == k:
        ans += 1
        
for j in b:
    temp = data.copy()
    temp[:,j] = 2
    if np.sum(temp == 1) == k:
        ans += 1
        
print(ans)

Measured memory_bytes: 27300
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	int sum = 0;
	for (int i = 0; i < (int)s.size(); i++) {
		sum += s[i] - '0';
	}
	int s2 = (s[0] - '0') + 9 * ((int)s.size() - 1);
	if (sum < s2) s2--;
	cout << s2 << endl;
	return 0;
}

Measured memory_bytes: 3620
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {

            int x = int.Parse(Console.ReadLine());
            Console.WriteLine(48 - x);




        }
    }
}


Measured memory_bytes: 11220
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2


def modinv(n,p):
    return pow(n,p-2,p)

import math

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    n = int(input())
    ans = 0
    for i in range(1, n+1):
        a = i 
        l = n - (n % i)
        k = l // i 
        inc = (((a + l) * k) // 2)
        ans += inc 
        # print(inc)

    print(ans)

#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()


Measured memory_bytes: 64128
#include <bits/stdc++.h>
using namespace std;
 
int p, k, q, x, a[100001], frek[100001];
 
int main (){
	cin >> p >> k >> q;
	for(int i=1;i<=p;i++){
		a[i]=k;
	}
	for(int i=1;i<=q;i++){
		cin >> x;
		frek[x]++;
	}
	for(int i=1;i<=p;i++){
		a[i]=k-(q-frek[i]);
	}
	for(int i=1;i<=p;i++){
		if(a[i]<=0) cout << "No" << endl;
		else cout << "Yes" <<endl;
	}
}
 

Measured memory_bytes: 1408
#include <iostream>

using namespace std;

int main(){
  int H,W;
  while(1){
    cin >> H >> W;
    if(H==0 && W == 0) break;
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
	if((i + j) % 2 == 0 ) cout << '#';
	else cout << '.';
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3060
#include<stdio.h>

int main(){
  int N, i, Ans;                                                                                   
  double ave = 0.;
  double minDif = 100*100;
  double dif;
  scanf("%d", &N);
  int A[N];
  for(i = 0; i < N; i++){
    scanf("%d", &A[i]);
    ave += A[i];
  }
  ave = ave/N;
  for(i = 0; i < N; i++){
    dif = (A[i] - ave)*(A[i] - ave);
    if(dif < minDif){
      minDif = dif;
      Ans = i;
    }
  }
  printf("%d\n", Ans);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>

using namespace std;

int main()
{
  double r;

  cin >> r;

  cout << fixed << setprecision(8)
       << M_PI * r * r
       << " "
       << 2.0 * M_PI * r
       << endl;

  return 0;
}



Measured memory_bytes: 3236
using System;
using System.Diagnostics;
using System.IO;

namespace AtCoder.ABC111 {
    class A {
        static void Main() => CustomMain();

        static void Solve() {
            var s = ReadString().ToCharArray();
            for (int i = 0; i < s.Length; i++) {
                if (s[i] == '1') {
                    s[i] = '9';
                } else if (s[i] == '9') {
                    s[i] = '1';
                }
            }

            WriteAnswer(string.Join("", s));
        }

        static void CustomMain() {
#if DEBUG
            // ファイルからテストケースを読み込む
            global::Common.ChangeStdIn();
            // 時間計測
            var stopwatch = new Stopwatch();
            stopwatch.Start();
#endif
            // 出力高速化
            var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            Console.SetOut(streamWriter);
            // 回答
            Solve();
#if DEBUG
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
#endif
            Console.Out.Flush();
        }

        static string ReadString() => Console.ReadLine().Trim();
        static int ReadInt() => int.Parse(ReadString());
        static long ReadLong() => long.Parse(ReadString());
        static float ReadFloat() => float.Parse(ReadString());
        static double ReadDouble => double.Parse(ReadString());

        static string[] ReadStringArray() => ReadString().Split(' ');
        static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
        static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
        static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
        static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

        static T TypeConversion<T>(string s) {
            if (typeof(T) == typeof(int)) {
                return (T) Convert.ChangeType(int.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(long)) {
                return (T) Convert.ChangeType(long.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(double)) {
                return (T) Convert.ChangeType(double.Parse(s), typeof(T));
            } else {
                return (T) Convert.ChangeType(s, typeof(T));
            }
        }

        static void ReadMulti<T, U>(out T a, out U b) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
        }

        static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
            c = TypeConversion<V>(str[2]);
        }

        static void WriteAnswer(object ans) => Console.WriteLine(ans);

        static bool IsOdd(long num) {
            return (num & 1) == 1;
        }

        static bool IsEven(long num) {
            return (num & 1) == 0;
        }
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define long long long
#define ull unsigned long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define upadj(i,adj) if (adj.size()>0) up(i,0,adj.size()-1)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define pb push_back
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define V vector
#define debug(X) cerr<< #X << "=" <<X << endl
#define debug2(X,Y)  cerr<< #X << "=" <<X << ", " << #Y << "=" <<Y << endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;

inline void read(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(int x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }
const int N= (int) 1e5+10;
int n,q,L;
long s[N];
int Prev[N];
long List[N];
long t[N],a[N];
stack<int> st;


void input()
{
    cin>>n>>q;
    s[0]= n;
    up(i,1,q) cin>>s[i];
}


void solve()
{
    up(i,0,q)
    {
        while (!st.empty() and s[st.top()]>= s[i]) st.pop();
        if (st.empty()) Prev[i]= -1; else Prev[i]= st.top();
        st.push(i);
    }
    int p= q;
    L= 0;
    while (p!= -1)
    {
        List[++L]= s[p];
        p= Prev[p];
    }
    //up(i,1,L) debug(List[i]);

    t[1]= 1;
    up(i,1,L)
    {
        long k= List[i];
        int j= i+1;
        while (k!=0)
        {
            int low,high,mid;
            low= j; high= L;
            while (low<= high)
            {
                mid= (low+high)/2;
                if (List[mid]> k) low= mid+1;
                else high= mid-1;
            }
            if (low== L+1) break;
            t[low]+= k/ List[low] * t[i];
            k%= List[low];
            j= low+1;
        };

        a[1]+= t[i]; a[k+1]-= t[i];
    }

    up(i,1,n)
    {
        a[i]+= a[i-1]; cout<<a[i]<<endl;
    };

}

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

    #ifdef I_Love_Pork
    #define TASK "tmp"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    #endif

    input();
    solve();

    return 0;
}


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

int main() {
  
  int N;
  int Z = 0;
  cin >> N;
  
  for (int i = 0;i < N;i++) {
    string S;
    cin >> S;
    if (S == "Y") {
      Z += 1;
    }
  }
    if (Z == 0) {
      cout << "Three" <<endl;
    }
    else {
      cout << "Four" << endl;
    }
}

Measured memory_bytes: 256
n,m = map(int,input().split())
cook = [0 for i in range(m+1)]
for i in range(n):
    k = [int(k) for k in input().split()]
    for j in range(k[0]+1):
        if j==0:
            continue
        else:
            cook[k[j]]+= 1

print(cook.count(n))

Measured memory_bytes: 38756
import java.util.*;

class Main {
    public static void main(String[] args) {
      
      Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
        int kona = Integer.parseInt(sc.next());
    	int dounatu [] = new int [N];
      
      for(int i=0;i<N;i++){
		dounatu[i] = Integer.parseInt(sc.next());
        kona = kona-dounatu[i];
      }
		Arrays.sort(dounatu);
      System.out.print(N+kona/dounatu[0]);
	    
    }
}

Measured memory_bytes: 23124
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * 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;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int height = in.nextInt();
            int width = in.nextInt();
            int n = in.nextInt();
            int[] am = new int[n];
            for (int i = 0; i < n; i++) {
                am[i] = in.nextInt();
            }
            int[][] a = new int[height][width];
            int cur = 1;
            for (int r = 0; r < height; r++) {
                for (int c = 0; c < width; c++) {
                    int nc = c;
                    if (r % 2 == 1) {
                        nc = width - c - 1;
                    }
                    while (am[cur - 1] == 0) {
                        ++cur;
                    }
                    a[r][nc] = cur;
                    --am[cur - 1];
                }
            }
            for (int r = 0; r < height; r++) {
                for (int c = 0; c < width; c++) {
                    if (c > 0) {
                        out.print(" ");
                    }
                    out.print(a[r][c]);
                }
                out.println();
            }
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 22868
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <iostream>

#define INF 1e8
using namespace std;
typedef pair<int,int> P;
int dx[2]={1,0};
int dy[2]={0,1};

int w,h;
int fie[51][51];
int dp[51][51][51][51];
bool move[51][51][51][51];
vector<P> hole[26];

void bfs(int sy,int sx){
	queue<P> que;
	que.push(P(sy,sx));
	move[sy][sx][sy][sx]=true;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<2;i++){
			int ny=p.first+dy[i],nx=p.second+dx[i];
			if(ny>=0 && ny<h && nx>=0 && nx<w){
				if(fie[ny][nx]>=0 && !move[sy][sx][ny][nx]){
					move[sy][sx][ny][nx]=true;
					que.push(P(ny,nx));
				}
			}
		}
	}
}

int dfs(int y1,int x1,int y2,int x2){
	if(dp[y1][x1][y2][x2]!=-1)return dp[y1][x1][y2][x2];
	if(!move[y1][x1][y2][x2])return -1;
	if(x2<x1 || y2<y1)return -1;
	if(x1==x2 && y1==y2)return 0;
	if(fie[y1][x1]==0){
		int res=0;
		if(y1+1<h && move[y1][x1][y1+1][x1])res=max(res,dfs(y1+1,x1,y2,x2));
		if(x1+1<w && move[y1][x1][y1][x1+1])res=max(res,dfs(y1,x1+1,y2,x2));
		return dp[y1][x1][y2][x2]=res;
	}else{
		int res=0;
		if(y1+1<h && move[y1][x1][y1+1][x1])res=max(res,dfs(y1+1,x1,y2,x2));
		if(x1+1<w && move[y1][x1][y1][x1+1])res=max(res,dfs(y1,x1+1,y2,x2));
		for(int i=0;i<hole[fie[y1][x1]-1].size();i++){
			P coo=hole[fie[y1][x1]-1][i];
			if(move[y1][x1][coo.first][coo.second] && move[coo.first][coo.second][y2][x2]){
				if(abs(y1-coo.first)+abs(x1-coo.second)==1){
					res=max(res,1+dfs(coo.first,coo.second,y2,x2));
				}else{
					int rr=dfs(coo.first,coo.second,y2,x2);
					if(rr==-1)continue;
					for(int j=0;j<2;j++){
						int nx1=x1+dx[j],ny1=y1+dy[j];
						if(nx1<0 || nx1>=w || ny1<0 || ny1>=h)continue;
						if(!move[y1][x1][ny1][nx1])continue;
						for(int k=0;k<2;k++){
							int nx2=coo.second-dx[k],ny2=coo.first-dy[k];
							if(nx2<0 || nx2>=w || ny2<0 || ny2>=h)continue;
							if(!move[ny2][nx2][y2][x2])continue;
							if(!move[ny1][nx1][ny2][nx2])continue;
							res=max(res,rr+1+dfs(ny1,nx1,ny2,nx2));
						}
					}
				}
			}
		}
		return dp[y1][x1][y2][x2]=res;
	}
}


int main(void){
	while(1){
		scanf("%d%d%*c",&h,&w);
		if(h==0 && w==0)break;
		for(int i=0;i<26;i++){
			hole[i].clear();
		}
		memset(fie,0,sizeof(fie));
		for(int i=0;i<h;i++){
			string str;
			cin >> str;
			for(int j=0;j<w;j++){
				if(str[j]=='#')fie[i][j]=-1;
				if(str[j]>='a' && str[j]<='z'){
					fie[i][j]=str[j]-'a'+1;
				}
				if(str[j]>='A' && str[j]<='Z'){
					hole[str[j]-'A'].push_back(P(i,j));
				}
			}
		}
		memset(move,false,sizeof(move));
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(fie[i][j]>=0)bfs(i,j);
			}
		}
		memset(dp,-1,sizeof(dp));
		printf("%d\n",dfs(0,0,h-1,w-1));
	}
	return 0;
}

Measured memory_bytes: 34324
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define leadzero(a) __builtin_clz(a) // count leading zeroes
#define trailzero(a) __builtin_ctz(a) // count trailing zeroes
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln endl
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it<<ln;} cerr<<endl
#define dbgstlp32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cerr<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inp freopen("input.txt", "r", stdin)
#define outp freopen("output.txt", "w", stdout)
#define dbgm(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
typedef long long int  ll;
typedef long double  ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM = 2e5+5, MOD = 1e9+7, EPS = 1e-9;
int t,n,m,k,x,y;
int main(){
	fastio;
	int n;
	cin>>n>>k;
	ll dp[n]= {0};
	ll h[n] = {0};
	forn(i,n) cin>>h[i];
	forsn(i,1,n){
		ll mi = 1e10;
		ll x = 1;
		while(x<=k){
			if(i-x<0) break;
			mi = min(mi,abs(h[i]-h[i-x])+dp[i-x]);
			x++;
		}
		dp[i] = mi;
		//dp[i] = min(abs(h[i]-h[i-2])+dp[i-2],abs(h[i]-h[i-1])+dp[i-1]);
	}
	cout<<dp[n-1]<<ln;
	return 0;
}

Measured memory_bytes: 1792
N = int(input())
a = 0
w = 0
t = 0
r = 0
for i in range(N):
    S = input()
    if S == 'AC':
        a += 1
    if S == 'WA':
        w += 1
    if S == 'TLE':
        t += 1
    if S == 'RE':
        r += 1
print('AC x ' + str(a))
print('WA x ' + str(w))
print('TLE x ' + str(t))
print('RE x ' + str(r))

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

using namespace std;
using ll = long long;

string s;
ll ans = 0;
int n;

void go(int i , ll x , ll sum){
    if(i == n){
        ans += sum + x;
        return;
    }

    go(i + 1 , x*10 + ll(s[i] - '0') , sum);
    go(i + 1 , 0 , sum + x);
}

main(){
    cin >> s;
    n = s.length();

    go(0 , 0 , 0);
    printf("%lld\n" , ans);
}


Measured memory_bytes: 256