akhauriyash/Code-Regression huggingface dataset:
// 由于要询问的是1到M每个间隔能够买到的商品种数
// 可以发现一个规律，如果区间的长度大于等于间隔那么就一定可以购买到这种礼品
// 那么在查询间隔为d时的答案，可以知道区间长度大于等于间隔那么在查询d-1时也一定满足
// 而对于那么不满足的区间长度大于等于间隔的，可以用线段树维护每个车站有多少种礼品
// 用lazy标记，然后单点查询就可以了
// 由于答案是从1到M的
// 那么可以反过来维护，对于区间长度小于间隔的就加入到线段树中，其他的情况就直接加入答案
// 然后当间隔增大时，加入新的区间即可，直到新的区间长度大于等于间隔

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=300000+100;
const int maxm=100000+100;
struct Node{
	int len,lc,rc;
	Node(){}
	Node(int lc,int rc):lc(lc),rc(rc),len(rc-lc+1){}
	bool operator < (const Node & ths) const
	{
		return len<ths.len;
	}
};
Node nodes[maxn];
int add[maxm*4];
void build(void)
{
	memset(add,0,sizeof(add));
}
void update(int o,int L,int R,int ul,int ur,int v)
{
	int ls=o<<1,rs=o<<1|1;
	int M=(L+R)>>1;
	if(ul<=L&&R<=ur){
		add[o]+=v;
		return;
	}
	if(ul<=M){
		update(ls,L,M,ul,ur,v);
	}
	if(M<ur){
		update(rs,M+1,R,ul,ur,v);
	}
}
int query(int o,int L,int R,int p,int _add)
{
	int ls=o<<1,rs=o<<1|1;
	int M=(L+R)>>1;
	if(L==R){
		return add[o]+_add;
	}
	if(p<=M){
		return query(ls,L,M,p,_add+add[o]);
	}
	else{
		return query(rs,M+1,R,p,_add+add[o]);
	}
}
int N,M;

void solve(void)
{
	build();
	int lc,rc;
	for(int i=0;i<N;i++){
		scanf("%d %d",&lc,&rc);
		nodes[i]=Node(lc,rc);
	}
	sort(nodes,nodes+N);
	int p=0;
	for(int i=1;i<=M;i++){
		while(p<N&&nodes[p].len<i){
			update(1,1,M,nodes[p].lc,nodes[p].rc,1);
			p++;
		}
		int res=N-p;
//		printf("%d\n",res);
		for(int j=0;j<=M;j+=i){
            if(j==0)    continue;
			res+=query(1,1,M,j,0);
		}
		printf("%d\n",res);
	}
}

int main()
{

	while(scanf("%d %d",&N,&M)==2){
		solve();
	}
	return 0;
}


Measured memory_bytes: 6016
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>

using namespace std;

int a,b;
int d[5];

int main()
{
	for (int i = 1;i <= 3;i++)
		cin >> a >> b,d[a]++,d[b]++;
	sort(d + 1,d + 4 + 1);
	if (d[1] == 1 && d[2] == 1 && d[3] == 2 && d[4] == 2)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	return 0;
}

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

signed main(){
  int N;
  cin>>N;
  vector<int> A(N);
  rep(i,N)cin>>A[i];
  
  int Nnum=10000000000;
  int ans=0;
  rep(i,N){
    if(Nnum>=A[i]){
      ans+=1;
      Nnum=min(Nnum,A[i]);
    }
  }
  cout<<ans<<endl;
}

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

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;

constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
constexpr char EL[] = "\n";

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define UNIQUE(x) (x).erase(unique(all(x)), (x).end());
#define REPIT(x) for(auto it=(x).begin(), end=(x).end(); it!=end; ++it)
#define perm(c) sort(all(c)); for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<typename T = i64>
T IN() { T x; cin >> x; return (x); }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}

void print() {
  cout << EL;
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}
template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
	cout << a;
	if (&a != &vec.back()) cout << " ";
  }
  cout << EL;
}
template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
	print(vec);
  }
}

struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

signed solve()
{
	int x;
	cin >> x;
	int t = 0, d = 0;
	while (d < x)
	{
		t++;
		d += t;
	}
	print(t);
	return 0;
}

#ifndef LOCALCODE
signed main()
{
	return solve();
}
#endif


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
int main(){
  map<char,int>ll;
  map<int,char>sw;
  ll['S']=0,ll['H']=1,ll['C']=2,ll['D']=3;
  sw[0]='S',sw[1]='H',sw[2]='C',sw[3]='D';

  int n,a;
  char c;
  bool card[4][13];
  memset(card,false,sizeof(card));

  cin >> n;
  for(int i=0;i<n;i++){
    cin >> c >> a;
    card[ll[c]][a-1] = true;
  }
  for(int i=0;i<4;i++){
    for(int j=0;j<13;j++){
      if(!card[i][j]){
	cout << sw[i] << " " << j+1 << endl;
      }
    }
  }
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i=0; i < n; i++)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x, y, z) max((x), max((y), (z)))
#define tmin(x, y, z) min((x), min((y), (z)))
ll MM = 1000000000; ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
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;}
const ll INF = 1LL << 60;
//cout << fixed << setprecision(10);

int main(){
    ll x, ans=-1; cin>>x;
    if(x==1){
        cout<<1;
        return 0;
    }
    FOR(i,2,x){
        FOR(j, 2, x){
            ll p=pow(i,j);
            if(p<=x) chmax(ans, p);
            else break;
        }
    }
    cout<<ans<<endl;
}

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

#define ll long long
#define pb push_back

int main()
{
    int x;
    cin >> x;
    int p =x / 500;
    int wp = x % 500;
    int cp = wp /5;
    int c =( p*1000)+ (cp*5);
    cout << c  << endl;
        return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int A = stdIn.nextInt();
		int B = stdIn.nextInt();
		int C = stdIn.nextInt();
		
		System.out.println(Math.max(0, C-(A-B)));

	}

}

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

int main()
{
    size_t N, Q;
    cin >> N >> Q;

    vector<vector<size_t>> s(2, vector<size_t>(N, N - 1));
    vector<size_t> hw(2, N - 1);

    size_t ans = (N - 2) * (N - 2);
    for (size_t q = 0; q < Q; q++)
    {
        size_t i;
        size_t x;
        cin >> i >> x;
        i--;
        x--;
        size_t j = (i + 1) % 2;

        if (x < hw[i])
        {
            for (size_t k = x; k <= hw[i]; k++)
            {
                s[i][k] = hw[j];
            }
            hw[i] = x;
        }
        size_t y = s[i][x];
        ans -= y - 1;
    }
    cout << ans << endl;
}


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

using namespace std;
typedef long long ll;

int mod=1e9+7;
const int N=4e6+5;
ll f[N],n,m,A,B;
ll qpow(ll x,ll y)
{
    ll ans=1,k=x;
    while(y){
        if(y&1) ans=ans*k%mod;
        k=k*k%mod;
        y>>=1;
    }
    return ans;
}
ll C(ll n,ll m)
{
     ll a=f[n];
     ll b=(f[m]*f[n-m])%mod;
     return (a*qpow(b,mod-2))%mod;
}
int main()
{
    f[0]=1;
    for(ll i=1;i<N;i++)
        f[i]=(f[i-1]*i)%mod;
    while(cin>>n>>m>>A>>B){
        ll res=0;
        for(ll i=B+1;i<=m;i++){
            ll tmp=(C(i-1+n-A-1,n-A-1)*C(m-i+A-1,m-i))%mod;
            res=(res+tmp)%mod;
        }
        cout<<res<<endl;
    }

  return 0;
}


Measured memory_bytes: 31488
#include <iostream>
#include "stdio.h"
using namespace std;

void func(int w, int h,int x,int y,int r)
{
  if(x - r >= 0 && y - r >= 0)
  {
    if(x + r <= w && y + r <= h)
    {
      std::cout << "Yes" << '\n';
      return;
    }
  }
  std::cout << "No" << '\n';
}

int main()
{
	int w,h,x,y,r;
  scanf("%d%d%d%d%d",&w,&h,&x,&y,&r );
  func(w,h,x,y,r);
  return 0;
}



Measured memory_bytes: 3156
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<iostream>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
using namespace std;
ll kt(ll n){
  string key=to_string(n);
  return  key.size();
}
// index が条件を満たすかどうか
bool isOK(ll index, ll key,ll a, ll b) {
    if ( (a*index+b*kt(index))<= key) return true;
    else return false;
}
// 二分探索
ll binary_search(ll key,ll a,ll b) {
    ll left = 0; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll right = 1000000001; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        ll mid = left + (right - left) / 2;
        if (isOK(mid, key,a ,b)) left = mid;
        else right = mid;
    }
    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return left;
}

int main(){
 int n,d;
  cin >>n>>d;
  vector<vector<int>> vec(n,vector<int>(d));
  rep(i,n)rep(j,d) cin>>vec[i][j];
  int ans=0;
  rep(i,n-1){
    rep2(j,i+1,n){
      int a=0;
      rep(k,d) a+=(vec[i][k]-vec[j][k])*(vec[i][k]-vec[j][k]);
      rep(k,160) if((double)sqrt(a)==k)ans++;
    }
  }
  cout <<ans<<endl;
}

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

mod = 10 ** 9 + 7


def comb(n, r):
    bunshi = 1
    for i in range(n-r+1, n+1):
        bunshi = bunshi * i % mod
    bunbo = 1
    for i in range(1, r + 1):
        bunbo = bunbo * i % mod
    return bunshi * pow(bunbo, mod - 2, mod) % mod


ans = (pow(2, n, mod) - 1 - comb(n, a) - comb(n, b) + 2 * mod) % mod
print(ans)

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

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> S(H+2);
  string str(W+2, '.');
  S[0] = str;
  S[H+1] = str;
  for(int i = 1; i < H+1; ++i){
    string s;
    cin >> s;
    S[i] = '.' + s + '.';
  }
  int ans[H+2][W+2];
  for(int i = 1; i < H + 1; ++i){
    for(int j = 1; j < W + 1; ++j){
      if(S[i][j] == '#'){
	ans[i][j] = -1;
	continue;
      }
      int cnt = 0;
      for(int k = -1; k < 2; ++k){
	if(S[i-1][j+k] == '#') cnt++;
	if(S[i+1][j+k] == '#') cnt++;
      }
      if(S[i][j-1] == '#') cnt++;
      if(S[i][j+1] == '#') cnt++;
      ans[i][j] = cnt;
    }
  }

  for(int i = 1; i < H + 1; ++i){
    for(int j = 1; j < W + 1; ++j){
      if(ans[i][j] == -1) cout << '#';
      else cout << ans[i][j];
    }
    cout << endl;
  }
}


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

// 2文字以上の部分文字列回文を3種類の文字で回避するにはxyzxyz.. とすればよい
int main(){
  string S;
  cin >> S;
  const int N= S.size();
  auto satisfied= [&](int cnt){
    return (N/3 <= cnt) && (cnt <= N/3+ 1);
  };

  int cnt_a= 0;
  int cnt_b= 0;
  int cnt_c= 0;
  for(auto c:S){
    if(c=='a'){ cnt_a++; }
    if(c=='b'){ cnt_b++; }
    if(c=='c'){ cnt_c++; }
  }

  string ans= (satisfied(cnt_a) && satisfied(cnt_b) && satisfied(cnt_c)) ? "YES"
                                                                         : "NO";
  cout << ans << endl;
}

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

#define F first 
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 200010, M = 1010;

int n;
LL m;
LL a[N], b[N];

bool check(LL x)
{
	LL cnt = 0;
	for (int i = 0; i < n; i ++ )
		if (a[i] * b[i] > x)
			cnt += a[i] - x / b[i];
	return cnt <= m;
}

int main()
{
	scanf("%d%lld", &n, &m);
	for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);
	for (int i = 0; i < n; i ++ ) scanf("%lld", &b[i]);
	sort(a, a + n);
	sort(b, b + n);
	reverse(a, a + n);
	
	LL l = 0LL, r = 1e12 + 10;
	while (l < r)
	{
		LL mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1LL;
	}
	printf("%lld\n", r);
    return 0;
}

Measured memory_bytes: 6940
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(){
	string s;
	while( getline(cin,s) ){
		if( s == "." ) break;
		
		stack<char> st;
		bool ans = true;
		for(int i=0 ; i < s.size() ; i++ ){
			if( s[i] == '(' || s[i] == '[' ){
				st.push( s[i] );
			}else if( s[i] == ')' ){
				if( st.empty() || st.top() != '(' ){
					ans = false;
					break;
				}else{
					st.pop();
				}
			}else if( s[i] == ']' ){
				if( st.empty() || st.top() != '[' ){
					ans = false;
					break;
				}else{
					st.pop();
				}
			}
		}
		if( !st.empty() ) ans = false;
		cout << (ans? "yes" : "no" ) << endl;
	}
}

Measured memory_bytes: 900
#include <stdio.h>

main(){

  int n,maxv,minv;
  int i,j;
  int R[200000];
  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&R[i]);
  }

  maxv=R[1]-R[0];
  minv=R[0];

  for(j=1;j<n;j++){
    if(maxv<R[j]-minv) maxv=R[j]-minv;
    if(minv>R[j]) minv=R[j];
  }

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

  return 0;
}

Measured memory_bytes: 1376
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN(n);
  if(n%111==0) OUT(n);
  else OUT(((n/111)+1)*111);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<t;i++)
#define pii pair<int,int>
map<int,int> mm;
int main()
{
    int n;scanf("%d",&n);int a;
    rep(i,1,n+1)scanf("%d",&a),mm[a]++;
    if(n%3)
    {
        if(mm.size()==1&&mm.begin()->first==0)printf("Yes\n");
        else printf("No\n");
    }
    else{
        vector<pii> v;
        for(auto xx:mm)v.push_back({xx.first,xx.second});
        if(mm.size()==3){
            if(v[0].second==v[1].second&&v[1].second==v[2].second)
            {
                int k1 = v[0].first, k2 = v[1].first, k3 = v[2].first;
                if ((k1 ^ k2) == k3 && (k1 ^ k3) == k2 && (k2 ^ k3) == k1)printf("Yes\n");
                else printf("No\n");
            }
            else printf("No\n");
        }
        else if(mm.size()>3)printf("No\n");
        else if(mm.size()==1){
            if(mm.begin()->first==0)printf("Yes\n");
            else printf("No\n");
        }
        else{
            if(v[0].second!=n/3&&v[1].second!=n/3)printf("No\n");
            else{
                if(v[0].second==n/3)v.push_back(v[1]);
                else v.push_back(v[0]);
                int k1 = v[0].first, k2 = v[1].first, k3 = v[2].first;
                if ((k1 ^ k2) == k3 && (k1 ^ k3) == k2 && (k2 ^ k3) == k1)printf("Yes\n");
                else printf("No\n");
            }
        }
    }
}

Measured memory_bytes: 4988
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {

    ll ans = 0;
    ll u = INF;
    rep(i, 5) {
        ll x;
        cin >> x;
        if(x%10 == 0) {
            ans += x;
        }
        else {
            ans += (x/10 + 1)*10;
            chmin(u, x%10);
        }
    }

    if(u != INF) {
        ans += u - 10;
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 256
import math
n, d = map(int, input().split())
xy = [map(int, input().split()) for _ in range(n)]
x, y = [list(i) for i in zip(*xy)]
c = 0

for i in range(n):
    if math.sqrt(x[i]*x[i] + y[i]*y[i]) <= d:
        c += 1

print(c)


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

int main()
{
    int n; cin>>n;
    vector<int> a(n); for(auto& e: a) cin>>e;

    map<int, int> x, y;
    for(int i=0; i<n; i+=2) {
        x[a[i]]++;
        y[a[i+1]]++;
    }

    vector<pair<int, int>> p;
    for(auto& e: x) p.emplace_back(e.second, e.first);
    sort(rbegin(p), rend(p));
    vector<pair<int, int>> q;
    for(auto& e: y) q.emplace_back(e.second, e.first);
    sort(rbegin(q), rend(q));

    if (p[0].second!=q[0].second) {
        cout<<n-p[0].first-q[0].first<<endl;
    }
    else if (p.size()==1 && q.size()==1) {
        cout<<n/2<<endl;
    }
    else if (p.size()==1) {
        cout<<n/2-q[1].first<<endl;
    }
    else if (q.size()==1) {
        cout<<n/2-p[1].first<<endl;
    }
    else {
        cout<<n-max(p[0].first+q[1].first, p[1].first+q[0].first)<<endl;
    }
}


Measured memory_bytes: 6520
#include <iostream>
using namespace std;
int main(void){
   int H,R;
   
   cin>>H>>R;
   
   if(H+R>0){
   cout<<"1"<<endl;
   }else if(H+R<0){
   cout<<"-1"<<endl;
   }else{
   cout<<"0"<<endl;
   }
   
    
}



Measured memory_bytes: 3116
def solve(n, k, h_list):
    if k == n:
        return 0
    # dp table
    large = sum(h_list) + 1
    dp = [[large] * n for _ in range(n + 1)]
    dp[1][0] = h_list[0]
    # update
    for i in range(1, n):
        for s in range(2, n + 1):
            dp[s][i] = min([dp[s - 1][j] + max(0, h_list[i] - h_list[j]) for j in range(i)])
        dp[1][i] = h_list[i]
    # print(dp)
    return min(dp[n - k])


def main():
    n, k = map(int, input().split())
    h_list = list(map(int, input().split()))
    res = solve(n, k, h_list)
    print(res)


def test():
    assert solve(4, 1, [2, 3, 4, 1]) == 3
    assert solve(6, 2, [8, 6, 9, 1, 2, 1]) == 7
    assert solve(10, 0, [1, 1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000]) == 4999999996


if __name__ == "__main__":
    # test()
    main()


Measured memory_bytes: 45084
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int n;
string s;

int main()
{
  cin>>n>>s;
  int ans=0;
  rep(i,n-2)
  {
    if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C') ans++;
  }
  cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl

#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()

#define pb push_back
#define ff first
#define ss second
#define hell 1000000007

#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 300009

ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
        ll r;cin>>r;
	cout<<r*r<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#define pb push_back
using namespace std;

const int MAX_LEN = (int)5e5 + 5;

int dp[MAX_LEN][2][2];
int n, m;
char s[MAX_LEN];
int left[MAX_LEN];
int right[MAX_LEN];
vector <int> v;

int solve(int pos, int used_left, int spent) {
    if (pos >= m) {
        return 0;
    }

    if (dp[pos][used_left][spent] != -1) {
        return dp[pos][used_left][spent];
    }

    int aux = 0;
    int idx = v[pos];
    if (used_left == 0) {
        aux = solve(pos + 1, 0, 0);
        if (left[idx] - spent > 0 && right[idx] > 0) {
            aux = max(aux, left[idx] - spent + solve(pos + 1, 0, 1));
            aux = max(aux, right[idx] + solve(pos + 2, 0, 0));
            aux = max(aux, right[idx] - 1 + solve(pos + 1, 1, 0));
        }
    } else {
        aux = max(aux, solve(pos + 1, 0, 0));
        if (left[idx] > 0 && right[idx] > 0) {
            aux = max(aux, right[idx] + solve(pos + 2, 0, 0));
            aux = max(aux, right[idx] - 1 + solve(pos + 1, 1, 0));
        }
    }
    dp[pos][used_left][spent] = aux;
    return aux;
}


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

    left[0] = 0;
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == '1') {
            left[i] = 1 + left[i - 1];
        } else {
            left[i] = 0;
        }
    }
    right[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (s[i + 1] == '1') {
            right[i] = 1 + right[i + 1];
        } else {
            right[i] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        //printf("i = %d, left = %d, right = %d\n", i, left[i], right[i]);
        if (s[i] == '0') {
            v.pb(i);
        }
    }

    m = (int)v.size();
    memset(dp, -1, sizeof(dp));
    int res = solve(0, 0, 0);
    printf("%d\n", res);
    return 0;
}



Measured memory_bytes: 61424
#include <iostream>
using namespace std;
int main() {
	int n, k, i,m=1;
	cin >> n >> k;
	for (i = 0; i < n; i++) {
		(m + k) <= (m * 2) ? m += k : m *= 2;
	}
	cout << m << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
using namespace std;

bool isKaibun(int n)
{
    int a[5], b[5];
    for (int i = 0, j = 4; i < 5; i++, j--)
    {
        a[i] = n % 10;
        b[j] = n % 10;
        n /= 10;
    }
    return memcmp(a, b, sizeof a) == 0;
}

int main()
{
    int a, b;
    cin >> a >> b;
    int sum = 0;
    for (int i = a; i <= b; i++)
    {
        if (isKaibun(i) == true) sum++;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int S[3];
    for(int i = 0; i < 3; i++){
        cin >> S[i];
    }
    
    sort(S, S + 3);
    
    cout << S[0] << " " << S[1] << " " << S[2] << endl;
}

Measured memory_bytes: 1180
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
using namespace std;

int N, M;
vector<int> X;
vector<int> mod;   //mod[i] := あまりiになるXの要素の個数
typedef pair<int, int> pii;
vector<vector<pii>> mods;   //何個、何があるのか

int main() {
	cin >> N >> M;
	X.resize(N);
	mod.resize(M,0);
	for (int n = 0; n < N; n++) {
		cin >> X[n];
		mod[X[n] % M]++;
	}
	sort(X.begin(), X.end());
	mods.resize(M);
	pii cur = pii(1,X[0]);
	for (int n = 1; n < N; n++) {
		if (X[n] == X[n - 1])cur.first++;
		else {
			mods[X[n - 1] % M].push_back(cur);
			cur = pii(1,X[n]);
		}
	}
	mods[X[N - 1] % M].push_back(cur);
	for (int m = 0; m < M; m++) {
		sort(mods[m].begin(), mods[m].end());
	}
	long long ans = 0;
	for (int i = 0; i < M; i++) {
		int j = (M - i) % M;
		if (i > j)continue;
		//自分自身とマッチング
		if (i == j)ans += mod[i] / 2;
		else {
			ans += min(mod[i], mod[j]);
			if (mod[i] > mod[j]) {
				int del = mod[j];   //自分のグループとマッチングさせたい個数
				for (int l = 0; l < mods[i].size() && del > 0; l++) {
					if (mods[i][l].first % 2 == 1) {
						mods[i][l].first--;
						del--;
					}
				}
				if (del == 0) {
					int tempans = 0;
					for (int l = 0; l < mods[i].size(); l++) {
						tempans += mods[i][l].first / 2;
					}
					ans += tempans;
				}
				else {
					if (del % 2 == 1)del++;
					int tempans = 0;
					for (int l = 0; l < mods[i].size(); l++) {
						tempans += mods[i][l].first / 2;
					}
					ans += tempans - del / 2;
				}
			}
			else if (mod[i] < mod[j]) {
				int del = mod[i];   //自分のグループとマッチングさせたい個数
				for (int l = 0; l < mods[j].size() && del > 0; l++) {
					if (mods[j][l].first % 2 == 1) {
						mods[j][l].first--;
						del--;
					}
				}
				if (del == 0) {
					int tempans = 0;
					for (int l = 0; l < mods[j].size(); l++) {
						tempans += mods[j][l].first / 2;
					}
					ans += tempans;
					
				}
				else {
					if (del % 2 == 1)del++;
					int tempans = 0;
					for (int l = 0; l < mods[j].size(); l++) {
						tempans += mods[j][l].first / 2;
					}
					ans += tempans - del / 2;
				}
			}
		}
	} 
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cassert>

using namespace std;

typedef long long ll;
const int mod = 1000000007;

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

    multiset<int> s;
    for (int i = 0; i < n; i++) {
        auto iter = s.lower_bound(a[i]);
        if (iter != s.begin()) {
            iter--;
            s.erase(iter);
        }
        s.insert(a[i]);
    }

    cout << s.size() << endl;

    return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
typedef long long ll;
using namespace std;

int main(void){
  int a[3];
  
  cin>>a[0]>>a[1]>>a[2];

  sort(a,a+3);

  cout<<a[0]+a[1]<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
int main(void){
int a,b,c;
    scanf("%d %d",&a,&b);
    if(a == b){
        int i = 0;
        while(i < a){
        printf("%d",a);
        i++;
        }
    }else{
        if(a < b){
            int i = 0;
            while(i < b){
                printf("%d",a);
                i++;
            }
        }else{
            int i = 0;
            while(i < a){
                printf("%d",b);
                i++;
        }
        }
    }
return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


vector<int> conv(string S) {
  map<char, int> mp;

  vector<int> res(S.size());
  REP(i, S.size()) {

    if (mp.count(S[i]) == 0) {
      int sz = mp.size();
      mp[ S[i] ] = sz;
    }

    res[i] = mp[S[i]];
  }
  return res;

}
int main2() {
  string S, T;
  cin >> S >> T;
  cout << (conv(S) == conv(T) ? "Yes" : "No") << endl;
  return 0;
}

int main() {
    main2();
  return 0;
}

Measured memory_bytes: 5704
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0;--i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
const int INF = 1e9+7;
int N, K, A[103];
bool DP[100003]; // 0:先手負け, 1:先手勝ち

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

  cin >> N >> K;
  rep(i, N) cin >> A[i];
  rep(i, K+1) {
    rep(j, N) {
      int next = i-A[j];
      if (next >= 0) DP[i] |= !DP[next];
    }
  }
  string ans = DP[K]? "First": "Second";
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 384
def shell_sort(arr, gaps)
  n = arr.size

  h = 1

  loop do
    break if h > n
    gaps.unshift(h)
    h = 3 * h + 1
  end

  count = 0

  gaps.each do |gap|
    count += insertion_sort(arr, gap)
  end

  count
end

def insertion_sort(arr, gap)
  count = 0

  gap.upto(arr.size - 1) do |i|
    temp = arr[i]
    j = i - gap

    while j >= 0 && arr[j] > temp
      arr[j + gap] = arr[j]
      j -= gap
      count += 1
    end

    arr[j + gap] = temp
  end

  count
end

n = gets.to_i

arr = $stdin.read.split.map(&:to_i)

gaps = []

count = shell_sort(arr, gaps)

puts gaps.size
puts gaps.join(' ')
puts count
puts arr

Measured memory_bytes: 108732
/*input
vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000


*/

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <array>
#include <cassert>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 7;
vector<int64_t> fib;

int64_t add(int64_t a, int64_t b) { return min(a + b, INF); }
int64_t mul(int64_t a, int64_t b)
{
	if (!a || !b) return 0;
	return (INF / b >= a) ? a * b : INF;
}

vector<int> kmp(string S)
{
	int N = (int) S.size();
	vector<int> lps(N + 1, 0);
	lps[1] = 0;
	for (int i = 2; i <= N; ++i) {
		for (lps[i] = lps[i - 1]; lps[i] != 0 && S[i - 1] != S[lps[i]]; lps[i] = lps[lps[i]]);
		if (S[i - 1] == S[lps[i]]) ++lps[i];
	}
	return lps;	
}

array<int64_t, 26> solve(string S, int64_t R)
{
	if (R == 0) return {};
	int N = (int) S.size() / 2;
	S.resize(N);

	auto lps = kmp(S);

	int len1 = N - lps[N], len2 = lps[N];
	int64_t cnt1 = 0, cnt2 = 0;
	for (int i = (int) fib.size() - 1; i >= 2; --i) {
		// cout << add(mul(fib[i - 1], len1), mul(fib[i - 2], len2)) << endl;
		if (add(mul(fib[i - 1], len1), mul(fib[i - 2], len2)) <= R) {
			cnt1 += fib[i - 1], cnt2 += fib[i - 2];
			R -= fib[i - 1] * len1 + fib[i - 2] * len2;
		}
		// cout << i << ": " << R << endl;
	}

	array<int64_t, 26> ans = {};
	for (int i = 0; i < 26; ++i) ans[i] = 0;
	assert(R <= N);
	// for (int i = 0; i < N; ++i) cout << (S[i] - 'a'); cout << endl;
	for (int i = 0; i < R; ++i) ++ans[S[i] - 'a'];

	// cout << cnt1 << ' ' << cnt2 << endl;
	for (int i = 0; i < N - lps[N]; ++i) ans[S[i] - 'a'] += cnt1;
	for (int i = N - lps[N]; i < N; ++i) ans[S[i] - 'a'] += cnt2;
	return ans;
}

int main()
{
	fib = {0, 1};
	while (fib.back() < INF) fib.push_back(*fib.rbegin() + *next(fib.rbegin()));

	ios_base::sync_with_stdio(0); cin.tie(0);
	string S;
	cin >> S;
	int64_t L, R;
	cin >> L >> R;

	auto x = solve(S, R), y = solve(S, L - 1);
	for (int i = 0; i < 26; ++i) cout << x[i] - y[i] << ' ';
	cout << endl;
	return 0;
}

Measured memory_bytes: 1044
import Data.Bits
import Data.List
import Control.Monad
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM
import Control.Monad.ST

divisor :: Int -> [Int]
divisor n = sub 1
  where
    sub i | i > (floor (sqrt $ fromIntegral n)) = []
          | n `mod` i == 0 = if i == (n `div` i) then i : (sub (i+1)) else i : (n `div` i) : (sub (i+1))
          | otherwise = sub (i+1)

main :: IO ()
main = do
  n <- readLn :: IO Int
  as' <- map read.words <$> getLine :: IO [Int]

  let as = V.fromList as'
      nums = runST $ do
        vec <- VM.replicate n False

        fmap (filter (> 0)) $ forM [n,n-1..1] $ \i -> do
          let ai = as V.! (i-1)
          b <- VM.read vec (i-1)
          if b && ai == 1 || (not b) && ai == 0 then return (-1)
            else do
              forM_ (divisor i) $ \d -> do
                b0 <- VM.read vec (d-1)
                if b0 then VM.write vec (d-1) False else VM.write vec (d-1) True
              return i

  print $ length nums
  forM nums $ \k -> do
    putStr $ (show k) ++ " "
  putStrLn ""


Measured memory_bytes: 21900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    ll A,B,C;
    cin >> A >> B >> C;
    if(A%2==0||B%2==0||C%2==0){
        cout << 0 << endl;
        return 0;
    }
    ll ml = max(max(A,B),C);
    if(ml==A){
        cout << B*C << endl;
    }else if(ml==B){
        cout << A*C << endl;
    }else{
        cout << A*B << endl;
    }
    return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())

    idx = 0
    for i in range(1, 5000):
        if i*(i+1)//2 <= N:
            idx = i

    delta = N - idx * (idx + 1) // 2

    r = m = 0
    if delta % idx == 0 and delta != 0:
        r = 1
    else:
        r, m = divmod(delta, idx)

    prob = [r + (i + 1) for i in range(idx)]

    for i in range(1, m + 1):
        prob[idx - i] += 1

    for i in range(len(prob)):
        print(prob[i])

if __name__ == "__main__":
    main()

Measured memory_bytes: 9380
#include<iostream>
#include<vector>
#include<string>

int main(){
    int n;
    std::cin >> n;
    std::string S;
    std::cin >> S;
    long long Rnum = 0, Gnum = 0, Bnum = 0;
    for(int i = 0; i < n; i++){
        if(S[i] == 'R') Rnum++;
        else if(S[i] == 'G') Gnum++;
        else if(S[i] == 'B') Bnum++; 
    }

    long long cnt = Rnum * Gnum * Bnum;
    for(int j = 0; j < n; j++){
        for(int offset = 1; (j - offset >= 0) && (j + offset < n); offset++){
            int i = j - offset;
            int k = j + offset;
            if((S[i] != S[j]) && (S[i] != S[k]) && (S[j] != S[k])) cnt--;
        }
    }

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


Measured memory_bytes: 3636
#include<cstdio>
#include<string>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

bool isFull() {
	return head == (tail + 1)%(LEN);
}
bool isEmpty() {
	return head == tail;
}
void enqueue(P x){
	if (isFull()) {
		printf("Error\n");
	}
	// add to the queue
	Q[tail] = x;
	if (tail == LEN) {
		tail = 1; // 1 origin
	} else {
		tail++;
	}
}

P dequeue(){
	if (isEmpty()) {
		printf("Error\n");
	}
	// extract from the queue
	P temp = Q[head];
	if (head == LEN) {
		head = 1;
	} else {
		head++;
	}
	return temp;
}


int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
	head = 1;
	tail = n+1; 
	int elappsed_time = 0;
	while(!isEmpty()){
		P p = dequeue();
		if (p.t <= q) {
			elappsed_time += p.t;
			printf("%s %d\n", p.name, elappsed_time);
		} else {
			elappsed_time += q;
			p.t -= q;
			enqueue(p);
		}
	}
  return 0;
}



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

using pii = pair<int, int>;

constexpr int dx[2] = {0, 1};
constexpr int dy[2] = {1, 0};

int H, W;
int dp[51][51][51][51];
bool can[51][51][51][51];
vector<pii> alphas[26];

bool is_range(int y, int x) {
    return 0 <= y && y < H && 0 <= x && x < W;
}

int rec(int ly, int lx, int ry, int rx, vector<string> const& C) {
    if(ry - ly + rx - lx == -1) { // ?????????????????????????¨±???
        return 0;
    }
    if(!is_range(ly, lx) || !is_range(ry, rx)) {
        return -1;
    }
    if(ry < ly || rx < lx) {
        return -1;
    }
    int& res = dp[ly][lx][ry][rx];
    if(!can[ly][lx][ry][rx]) {
        return res = -1;
    }
    if(res != -2) {
        return res;
    }
    res = 0;
    res = max({res, rec(ly + 1, lx, ry, rx, C), rec(ly, lx + 1, ry, rx, C)});
    if(islower(C[ly][lx])) {
        for(auto& p : alphas[C[ly][lx] - 'a']) {
            int y = p.first, x = p.second;
            if(ly <= y && y <= ry && lx <= x && x <= rx) {
                int t = -1;
                for(int i = 0; i < 2; ++i) {
                    for(int j = 0; j < 2; ++j) {
                        t = max(t, rec(ly + dy[i], lx + dx[i], y - dy[j], x - dx[j], C));
                    }
                }
                int t2 = -1;
                for(int i = 0; i < 2; ++i) {
                    t2 = max(t2, rec(y + dy[i], x + dx[i], ry, rx, C));
                }
                if(t >= 0 && t2 >= 0) {
                    res = max(res, 1 + t + t2);
                }
            }
        }
    }

    return res;
}

int main() {
    while(cin >> H >> W, H) {
        vector<string> C(H);
        for(int i = 0; i < H; ++i) {
            cin >> C[i];
        }

        fill(dp[0][0][0], dp[51][0][0], -2);
        fill(can[0][0][0], can[51][0][0], false);
        for(int i = 0; i < 26; ++i) {
            alphas[i].clear();
        }

        for(int i = 0; i < H; ++i) {
            for(int j = 0; j < W; ++j) {
                if(isupper(C[i][j])) {
                    alphas[C[i][j] - 'A'].emplace_back(i, j);
                }
                if(C[i][j] != '#') {
                    can[i][j][i][j] = true;
                    queue<pii> que;
                    que.emplace(i, j);
                    while(!que.empty()) {
                        int y = que.front().first;
                        int x = que.front().second;
                        que.pop();
                        for(int k = 0; k < 2; ++k) {
                            int ny = y + dy[k];
                            int nx = x + dx[k];
                            if(is_range(ny, nx) && C[ny][nx] != '#' && !can[i][j][ny][nx]) {
                                can[i][j][ny][nx] = true;
                                que.emplace(ny, nx);
                            }
                        }
                    }
                }
            }
        }

        cout << rec(0, 0, H - 1, W - 1, C) << endl;
    }
}


Measured memory_bytes: 36180
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define inf std::numeric_limits<int>::max();
#define highest_2_pow(n)  __builtin_clzll((long long)0)- __builtin_clzll((long long)n) - 1
//-----------------------------------------------------------------------------------------------------
#define lli long long int 
#define int long long
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi vector<int>
#define vlli vector<long long int>
#define si set<int>
#define slli set<long long int>
#define mt make_tuple
#define mp make_pair
#define eb emplace_back
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
//---------------------------------------------------
using namespace std;
// GCD and LCM are available
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...);
}

void faster(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
void solve(){
    int n,k,s;
    cin>>n>>k>>s;
    vi v(n);
    int arr[2]={max(1ll,s/2),s-(s/2)};
    if(k==n) fill(all(v),s);
    else {
        rep(i,0,s==1?k:k+1) v[i]=arr[i%2];
        rep(i,s==1?k:k+1,n) v[i]=arr[i%2]+2+(arr[i%2]+2==s);
    }
    for(auto e:v) cout<<e<<" ";
    cout<<"\n";
}
signed main()
{
    faster();
    int t=1;
    //cin>>t;
    while(t--) solve();
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
typedef long long LL;
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second

using namespace std;



int main(){
	int n;
	RI(n);
	VI x(n);
	REP (i,n) {
		RI(x[i]);
	}
	VI vis(n+1,0);
	int res=0;
	for (auto i:x){
		vis[i]=vis[i-1]+1;
		res=max(res,vis[i]);
	}
	cout<<n-res;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
  ll t;
 // cin>>t;
 // while(t--){
  ll a,b=0,c=0,d=0,e=0;
  cin>>a;
  ll arr[a];
  for(ll i=0;i<a;i++){cin>>arr[i];if(arr[i]>e){e=arr[i];}}
  for(ll i=0;i<a-1;i++){
    //d=d+1;
    if(arr[i+1]<arr[i]){c=c+(arr[i]-arr[i+1]);arr[i+1]=arr[i];}
   // cout<<c<<" ";
   // else{d=0;}
  }
  cout<<c;
 // }
}

Measured memory_bytes: 5140
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N; ll K;
int A[int(2e5 + 5)];
ll Bit[61];
int Table[61][int(2e5 + 5)];

int main(){
  Bit[0] = 1;
  for (int i = 1; i < 61; i++) Bit[i] = Bit[i-1] * 2;

  scanf("%d%lld", &N, &K);
  for (int i = 1; i <= N; i++) {
    scanf("%d", A + i);
    Table[0][i] = A[i];
  }

  for (int i = 1; i < 61; i++){
    for (int j = 1; j <= N; j++){
      int next = Table[i - 1][j];
      Table[i][j] = Table[i - 1][next];
    }
  }

  int now = 1;
  while (K > 0){
    for (int i = 0; i < 60; i++){
      if (K == Bit[i]){
        now = Table[i][now];
        K -= Bit[i];
        break;
      }
      if (K < Bit[i + 1]){
        now = Table[i][now];
        K -= Bit[i];
        break;
      }
    }
  }
  cout << now << endl;

  return 0;
}


Measured memory_bytes: 52168
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

def _merge_right(a,b):
  la, lb = map(len,[a,b])
  for i in range(max(la-lb+1, 1),la):
    if comp(b, a[i-la:]):
      yield i
  yield la

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]:
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

a=input()
b=input()
c=input()

print(min_merge(a,b,c))



Measured memory_bytes: 3420