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

#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPS(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()

#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;

const ll INF = 1e18;
const ll MOD = 1e9+7;

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, const T &b) { if (a>b) { a = b; return true;} return false; }

const ll MODTEMP = 998244353;

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

const ll MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i-1] * i % MODTEMP;
        inv[i] = MODTEMP - inv[MODTEMP%i] * (MODTEMP / i) % MODTEMP;
        finv[i] = finv[i-1] * inv[i] % MODTEMP;
    }
}
ll COM(ll n, ll k)
{
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MODTEMP) % MODTEMP;
}

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    COMinit();
    ll N, M, K; cin >> N >> M >> K;
    ll ans = 0;
    for(int i = 0; i <= K; i++)
    {
        ans += ((M * modpow(M-1, N-(i+1))) % MODTEMP * COM(N-1, i)) % MODTEMP;
    }
    cout << ans % MODTEMP << endl;
}

Measured memory_bytes: 15620
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;
int N, M, Q;
VI A, B, C, D;

int dfs(VI num) {
	int res = 0;
	if (num.size() == N) {
		REP(i, Q) {
			int a = A[i], b = B[i], c = C[i], d = D[i];
			if (num[b] - num[a] == c)res += d;
		}
		return res;
	}
	//cout << num.back() << endl;
	eFOR(i, num.back(), M) {
		VI tmp = num;
		tmp.push_back(i);
		chmax(res, dfs(tmp));
	}
	return res;
}

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

	cin >> N >> M >> Q;

	A.resize(Q);
	B.resize(Q);
	C.resize(Q);
	D.resize(Q);
	REP(i, Q) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		A[i]--;
		B[i]--;
	}
	int ans = 0;
	eFOR(i, 1, M) {
		VI tmp;
		tmp.push_back(i);
		chmax(ans, dfs(tmp));
	}
	cout << ans << endl;
	return 0;
}



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

int main(){
  int N;
  cin >> N;
  vector<int> x(N),y(N);
  for(int i=0;i<N;i++){
    cin >> x.at(i) >> y.at(i);
  }
  double sum=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      sum+=sqrt(pow(x.at(i)-x.at(j),2)+pow(y.at(i)-y.at(j),2));
    }
  }
  double ans=sum*(2.0/N);
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const ll inf = 1e18;
ll a[maxn];
int main() {
	int n;
	ll k;
	scanf("%d%lld", &n, &k);
	for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
	sort(a, a + n);
	ll L = -inf, R = inf;
	while(L + 1 < R) {
		ll MID = (L + R) / 2;
		ll cnt = 0;
		for(int i = 0; i < n; i++) {
			if(a[i] < 0) {
				int l = i, r = n;
				while(l + 1 < r) {
					int mid = (l + r) / 2;
					if(a[i] * a[mid] <= MID) r = mid;
					else l = mid;
				}
				cnt += n - r;
			}
			else {
				int l = i, r = n;
				while(l + 1 < r) {
					int mid = (l + r) / 2;
					if(a[i] * a[mid] <= MID) l = mid;
					else r = mid;
				}
				cnt += l - i;
			}
		}
		if(cnt < k) L = MID;
		else R = MID;
	}
	printf("%lld\n", R);
	return 0;
}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    int n, m, x;
    cin >> n >> m >> x;
    vint a(m);
    rep(i, m) cin >> a[i];
    int l = 0, r = 0;

    rep(i, m)
    {
        if (a[i] < x)
        {
            ++l;
        }
        else
        {
            ++r;
        }
    }
    cout << min(l, r) << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    string s; cin >> s;
    int len = s.size();
    int ans = 0;
    for (int i = 0; i < len/2; i++)
    {
        if (s[i] != s[len-1-i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int A,B,C;
  cin>>A>>B>>C;
  cout<<A*B/2<<endl;
  return 0;
}


Measured memory_bytes: 256
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll inf=1e18;
const ld pai=acos(-1);
ll n,m;
vll in[200009],out[200009];
ll l[200009],r[200009],a[200009];
ll dp[200009];
struct NODE{
	ll lzy,tree;
	NODE *left,*right;
	NODE(){
		lzy=tree=0;
		left=right=NULL;
	}
}*root=new NODE;
void lzyUPD(NODE *node,ll l,ll r){
	node->tree+=node->lzy;
	if(node->left!=NULL)node->left->lzy+=node->lzy;
	if(node->right!=NULL)node->right->lzy+=node->lzy;
	node->lzy=0;
}
void upd(NODE *node,ll l,ll r,ll s,ll e,ll x){
	lzyUPD(node,l,r);
	if(s<=l && e>=r){
		node->lzy+=x;
		lzyUPD(node,l,r);
		return ;
	}
	if(s<=mid){
		if(node->left==NULL)node->left=new NODE;
		upd(node->left,l,mid,s,e,x);
	}
	else if(node->left!=NULL)lzyUPD(node->left,l,mid);
	if(e>=mid+1){
		if(node->right==NULL)node->right=new NODE;
		upd(node->right,mid+1,r,s,e,x);
	}
	else if(node->right!=NULL)lzyUPD(node->right,mid+1,r);
	ll mx=-inf;
	if(node->left!=NULL)mx=max(mx,node->left->tree);
	if(node->right!=NULL)mx=max(mx,node->right->tree);
	node->tree=mx;
}
ll query(NODE *node,ll l,ll r,ll s,ll e){
	lzyUPD(node,l,r);
	if(l>e || s>r)return -inf;
	if(s<=l && e>=r)return node->tree;
	ll mx=-inf;
	if(node->left!=NULL)mx=max(mx,query(node->left,l,mid,s,e));
	if(node->right!=NULL)mx=max(mx,query(node->right,mid+1,r,s,e));
	return mx;
}
int main(){
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>l[i]>>r[i]>>a[i];
		in[l[i]].pb(i);
		out[r[i]].pb(i);
	}
	for(ll i=1;i<=n;i++){
		ll sum=0;
		for(auto u:in[i])sum+=a[u];
		upd(root,0,n,0,i-1,sum);
		dp[i]=query(root,0,n,0,i-1);
		upd(root,0,n,i,i,dp[i]);
		for(auto u:out[i])upd(root,0,n,0,l[u]-1,-a[u]);
	}
	ll mx=0;
	for(int i=1;i<=n;i++)mx=max(mx,dp[i]);
	cout<<mx<<endl;
}


Measured memory_bytes: 47104
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[0]-x[1])
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  if n+a<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>

int c[20];
int a[20][20];
int rikai[20];

int main(){
    int N,M,X; cin>>N>>M>>X;
    REP(i,N){
        cin >> c[i];
        REP(j,M){
            cin >> a[i][j];
        }
    }
    
    ll ans = -1;
    for(ll bits=0;bits<pow(2,N);++bits){
        FILL(rikai,M,0);
        ll cand = 0;
        ll temp = bits;
        for(int i=0;i<N;++i){
            if(temp%2==1){
                cand += c[i];
                for(int j=0;j<M;++j){
                    rikai[j] += a[i][j];
                }
            }
            temp /= 2;
            if(temp==0){break;}
        }
        bool ok = true;
        REP(i,M){
            if(rikai[i]<X){ok=false; break;}
        }
        
        if(ok){ 
           if(ans<0){ ans = cand;}
           else{ chmin(ans,cand);}
        }
    }
    cout << ans << "\n";
}


Measured memory_bytes: 4120
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
// #define mp make_pair
#define pq priority_queue
const ll mod=1000000007;
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace boost::multiprecision;
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int N=1000005;
ll fact[N],invfact[N];
ll power(ll x,ll y){
  if(y<=0) return 1LL;
  ll z=power(x,y/2);
  if(y%2) return (((z*z)%mod)*x)%mod;
  return (z*z)%mod;
}

void pre(){
  fact[0]=invfact[0]=invfact[1]=fact[1]=1;
  rep(i,2,N) fact[i]=(i*fact[i-1])%mod;
  rep(i,2,N) invfact[i]=(invfact[i-1]*power(i,mod-2))%mod;
}
ll nCr(ll n,ll k){ return (((fact[n]*invfact[n-k])%mod)*invfact[k])%mod; }



const int N1=1e6+1;
vector<int> isprime(N1,1),prime;
void seive(){
  rep(i,2,sqrt(N1)+1){
      if(isprime[i]){
        for(int j=i*i;j<N1;j+=i) isprime[j]=0;
        prime.pb(i);
      }
  }
  rep(i,sqrt(N1)+1,N1) if(isprime[i]) prime.pb(i);
}



struct dsu {
    vector<int> par, rank;
    dsu(int n): par(n+1), rank(n+1) {
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            rank[i]= 1;
        }
    }
    int root(int a) {
        if (a == par[a]) return a;
        return par[a] = root(par[a]);
    }
    void merge(int a, int b) {
        a = root(a);
        b = root(b);
        if (a == b) return;
        if (rank[a] > rank[b]) swap(a, b);
        par[b] = a;
    }
    set<int> parent(int n){
        set<int> s;
        for(int i=1;i<=n;i++){
            s.insert(root(i));
        }
        return s;
    }
};

void solve(){
  int a[3][3],sum=0;
  rep(i,0,3) rep(j,0,3){cin>>a[i][j]; sum+=a[i][j];}
  if(sum%3==0 && (a[0][0]+a[1][1]+a[2][2]==(sum/3))) cout<<"Yes\n";
  else cout<<"No\n";
}

int main(){
    optimizeIO();
    int r=1;
    {solve();}
}


Measured memory_bytes: 7052
use proconio::input;

fn main() {
  input! {
    k: f32,
    a: f32,
    b: f32,
  }
  let shou = (b/k).floor() - (a/k).floor();
  let ans = if shou >= 1.0 || b%k == 0.0 || a%k == 0.0 {"OK"} else {"NG"};
  println!("{}", ans);
}

Measured memory_bytes: 2724
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
using ll = long long;
const ll mod = LLONG_MAX;

int p[112345];
int ans;
int main(){
  int n;
  cin>>n;
  rep(i,n)cin>>p[i];
  rep(i,n){

    if(i+1<n&&i+1==p[i]&&i+2==p[i+1]){
      ans++;
      i++;
    }
    else if(i+1==p[i])ans++;
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	int A, B, C, K, i;

	cin >> A >> B >> C >> K;
	for (i = 0; i < K; i++){
		if(A >= B){
			B *= 2;
		}else if(B >= C){
			C *= 2;
		}
	}

	if (A < B && B < C){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

		return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

vector<int> getPrimeList(int n)
{
	vector<int> table(n+1, 0);
	
	for(int i = 2; i <= n; i++)
	{
		table[i] = true;
		for(int j = 2; j * j <= i; j++)
		{
			if(i % j == 0)
			{
				table[i] = false;
				break;
			}
		}
	}
	
	return table;
}

int main()
{
	vector<int> table(getPrimeList(123456 * 2));
	
    for(int n; cin >> n && n;)
	{
		cout << accumulate(table.begin() + n + 1, table.begin() + 2 * n + 1, 0) << endl;
	}
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define MAXN 1000100
#define ll long long
ll n, m, a[MAXN], h, t, cnt, cnt2[MAXN], d[MAXN], cnt3, ans;
bool check(ll u)
{
	t = n;
	while(t%u == 0) t /= u;
	if(t%u == 1) return true;
	else return false;
}
int main()
{
	scanf("%lld",&n);
	t = n;
	for(ll i=2;i<=sqrt(n);i++)
	{
		if(n%i == 0) 
		{
			a[++cnt] = i;
if(i != n/i) a[++cnt] = n/i;
		}
	}
a[++cnt] = n;
//	if(t != 1) a[++cnt] = t;
	t = n-1;
	for(ll i=2;i<=sqrt(n);i++)
	{
		if(t%i == 0)
		{
			d[++cnt3] = i;
			while(t % i == 0)
			{
				t /= i;
				cnt2[cnt3]++;
			}
		}
	}
	if(t != 1) cnt2[++cnt3] = 1, d[cnt3] = t;
	ans = 1;
	for(ll i=1;i<=cnt3;i++) ans *= (cnt2[i]+1);//, cout<<d[i]<<" "<<cnt2[i]<<endl;;
	ans--;
//cout<<ans<<endl;
	for(ll i=1;i<=cnt;i++)
	{
		if(check(a[i]) == true) ans++;//cout<<a[i]<<endl;;
	}
cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 4352
import numpy as np
[n,d] = [int(i) for i in input().split()]
points = []
for i in range(n):
	coordinates = [int(i) for i in input().split()]
	points.append(coordinates)

def distance(a,b):
	total = 0
	for i in range(len(a)):
		total += (a[i] - b[i])**2	
	return np.sqrt(total)

ans = 0				
for i in range(n-1):
	for j in range(i+1,n):
		if distance(points[i],points[j]) == int(distance(points[i],points[j])):
			ans += 1
			
print(ans)

Measured memory_bytes: 12416
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
template<typename T> ll min(ll a, const T&& b) { return a < b ? a : b; }
template<typename T> ll min(const T&& a, ll b) { return a < b ? a : b; }
template<typename T> ll max(ll a, const T&& b) { return a > b ? a : b; }
template<typename T> ll max(const T&& a, ll b) { return a > b ? a : b; }
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

void solve() {
  ll h, w; cin >> h >> w;
  vector<string> m(h); cin >> m;
  ll nn = -linf, np = -linf, pn = -linf, pp = -linf;
  rep(y, h) rep(x, w) if (m[y][x] == 'B') {
    chmax(nn, -x-y);
    chmax(np, -x+y);
    chmax(pn, x-y);
    chmax(pp, x+y);
  }
  ll ans = 0;
  rep(y, h) rep(x, w) if (m[y][x] == 'B') {
    chmax(ans, -x-y+pp);
    chmax(ans, x-y+np);
    chmax(ans, -x+y+pn);
    chmax(ans, x+y+nn);
  }
  cout << ans << endl;
}



Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
//#define int long long
int abs(int a,int b){
  int c=max(a,b)-min(a,b);
  return c;
}
priority_queue<int, vector<int>, greater<int> > qu;
signed main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b;
  string c[1000];
  cin>>a>>b;
  for(int i=0;i<a;i++) cin>>c[i];
  for(int i=0;i<a;i++){
    cout<<c[i]<<"\n"<<c[i]<<"\n";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;
const int H = 10010 / 40;
const int W = 10010 / 40;
const double EPS = 1e-8;

int AN, BN;
double R;
int my[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int mx[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};

int distance2(P a, P b){
  return (a.real() - b.real()) * (a.real() - b.real()) + (a.imag() - b.imag()) * (a.imag() - b.imag());
}

int main() {
  while(cin >>AN >>BN >>R && AN){
    int ans = 0;
    R = R * 4;
    vector<P> v[H][W];
    REP(b, AN){
      int x, y; cin >>x >>y;
      v[y / 40][x / 40].push_back(P(x, y));
    }
    REP(a, BN){
      int x, y; cin >>x >>y;
      P p = P(x, y);
      REP(i, 9){
        int ny = y / 40 + my[i], nx = x / 40 + mx[i];
        if(ny >= 0 && nx >= 0 && ny < H && nx < W){
          REP(j, v[ny][nx].size()){
            int d2 = distance2(p, v[ny][nx][j]);
            if(d2 <= R * R) ++ans;
          }
        }
      }
    }
    cout <<ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 4748
#include <stdio.h>

int main(){
    int H,W;
    int i=0;
    int j=0;
    while(1){
        scanf("%d %d",&H,&W);
        if(H==0 && W==0)
        break;
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                if(i ==0 || i ==H-1 || j==0 || j==W-1){
                    printf("#");
                    
                }else{
                    printf(".");
                }
                
            }
           
            printf("\n");
        }
        printf("\n");
    }
}

Measured memory_bytes: 1696
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<fstream>       //ファイルストリーム（標準入力変更用）
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

//名前
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef map<string, int> msi;
typedef map<string, ll> msll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pllll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;

//定数
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;

//マクロ
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,e) for(int i=s;i<e;i++)
#define repse(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define in(x) cin >> x
#define outl(x) cout << x << endl
#define out2l(x, y) cout << x << " " << y << endl 

//よく使う関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

    //標準入力をファイルに変更
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());

    int N, X;
    in(N);
    in(X);

    vi L(N);
    rep(i, N) in(L[i]);

    int count = 1;
    int d = 0;

    rep(i, N)
    {
        d += L[i];
        if (d <= X) count++;
    }

    outl(count);

    return 0;
}

Measured memory_bytes: 3568
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    VLL a(n);
    REP(i,0,n) cin >> a[i];
    LL m = 1000;
    REP(i,0,n-1) {
        if (a[i] < a[i+1]) {
            LL cnt = m / a[i];
            m += cnt * (a[i+1] - a[i]);
        }
    }
    cout << m << endl;
}

signed main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string> 
using namespace std;
int main(void){
    
    int a;
    cin>>a;
    int b[a];
    for(int i=0;i<a;i++){
        cin>>b[i];
    }
    int k=0;
    for(int i=0;i<a;i++){
        if(i%2==0){
            if(b[i]%2!=0){
                k++;
            }
        }
    }
    cout<<k;
    return 0;
}


Measured memory_bytes: 3600
from collections import deque


N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)


def get_dist(src):
    Q = deque([(src, 0)])
    dist = [-1] * (N + 1)
    while Q:
        v, d = Q.popleft()
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                Q.append((u, d + 1))
    return dist[1:]

F = get_dist(1)
S = get_dist(N)
fennec, snuke = 0, 0
for f, s in zip(F, S):
    if f <= s:
        fennec += 1
    else:
        snuke += 1

if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")


Measured memory_bytes: 31732
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	d, n := nextInt(), nextInt()
	if n == 100 {
		n = 101
	} 
	
	res := n
	
	for i := 0; i < d; i++ {
		res *= 100
	}

	fmt.Println(res)
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool solve(string store,string s){
    for(int i=0;i<s.length();i++){
        for(int j=1;i+(store.length()-1)*j<s.length();j++){
            for(int k=0;k<store.length();k++){
                if(s[i+j*k]!=store[k])goto next;
            }
            return true;
            next:
          int g=0;
        }
    }
    return false;
}
int main(){
    int n,ans=0,x;
    string store,s;
    cin>>n>>store;
    while(n>0){
        cin>>s;
        if(solve(store,s)){
            ans++;
        }
        n--;
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define lint long long
#define st first
#define nd second
#define INF 0x3f3f3f3f

using namespace std;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	lint a; cin>>a;
	cout<<a+a*a+a*a*a<<"\n";

	return 0;	
}


Measured memory_bytes: 3584
#include <iostream>

using namespace std;

int main()
{
    int A,B,sum,diff;
    char op;
    cin>>A>>op>>B;
    if (op=='+'){
        sum=A+B;
        cout<<sum;}
    if (op=='-'){
        diff=A-B;
        cout<<diff;}
    return 0;
}


Measured memory_bytes: 256
class Dice
  def dice_top(n, t)
    if t == n[4]
      dice_s(n)
    elsif t == n[3]
      dice_e(n)
    elsif t == n[2]
      dice_w(n)
    elsif t == n[1]
      dice_n(n)
    elsif t == n[5]
      dice_b(n)
    end
  end

  def dice_s(n)
    n[0],n[1],n[4],n[5] = n[4],n[0],n[5],n[1]
    return n
  end

  def dice_e(n)
    n[0],n[2],n[3],n[5] = n[3],n[0],n[5],n[2]
    return n
  end

  def dice_w(n)
    n[0],n[2],n[3],n[5] = n[2],n[5],n[0],n[3]
    return n
  end

  def dice_n(n)
    n[0],n[1],n[4],n[5] = n[1],n[5],n[0],n[4]
    return n
  end

  def dice_b(n)
    n[0],n[1],n[4],n[5] = n[5],n[4],n[1],n[0]
    return n
  end

  def dice_sp(n)
    n[1],n[2],n[4],n[3] = n[2],n[4],n[3],n[1]
    return n
  end
end

n = gets.chomp.split.map(&:to_i)
q = gets.to_i
dice = Dice.new()

q.times {
  t, f = gets.split.map(&:to_i)

  dice.dice_top(n, t)

  while n[1] != f
    dice.dice_sp(n)
  end

  puts n[2]
}

Measured memory_bytes: 8652
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		int N=sc.nextInt();
		int K=sc.nextInt();
		
		int limit=((N-1)*(N-2))/2;
		if(limit<K) {
			System.out.println(-1);
			return;
		}
		
		int M=limit-K+N-1;
		System.out.println(M);
		for(int i=2;i<N+1;i++) {
			System.out.println("1 "+i);
		}
		int temp=0;
		for(int i=2;i<N+1;i++) {
			for(int j=i+1;j<N+1;j++) {
				if(temp==limit-K) {
					return;
				}
				System.out.println(i+" "+j);
				temp++;
			}
		}
		
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 21332
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int k, s;
  cin >> k >> s;
  int x, y, z, ans=0;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= k; j++) {
      if (s-i-j>=0 and s-i-j <= k) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    int n;
    cin >> n;

    int p[8];
    int q[8];
    for( int i = 0; i < n; ++i ) cin >> p[i];
    for( int i = 0; i < n; ++i ) cin >> q[i];

    vector< int > v;
    for( int i = 1; i <= n; ++i ) {
        v.pb(i);

    }

    int pp, qp;
    int cnt = 1;
    do {
        bool f = true;
        for( int i = 0; i < n; ++i ) {
            if( v[i] != p[i] ) f = false;

        }
        if( f ) {
            pp = cnt;

        }
        f = true;
        for( int i = 0; i < n; ++i ) {
            if( v[i] != q[i] ) {
                f = false;

            }
        }
        if( f ) {
            qp = cnt;

        }
        ++cnt;

    } while( next_permutation(all(v)) );

    cout << abs(pp - qp) << endl;
    return 0;
}



Measured memory_bytes: 256
/*
 * @author Dhruvit
 */
#include <bits/stdc++.h>
#include<cstring>
#include<math.h>
#include<stdlib.h>
#include <fstream>
#include <bits/stdc++.h>
#define MAX 1000000007
class HGrid1 {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int H,W;
	    in>>H>>W;
	    long int dp[H+1][W+1];
	    char s[H][W];
	    for(int i=0;i<H;i++){
	        in>>s[i];
	    }
	    for(int i=0;i<H+1;i++){
	        for(int j=0;j<W+1;j++){
	            dp[i][j] = 0;
	        }
	    }
        dp[1][1] =1;
	    for(int i=1;i<H+1;i++){
	        for(int j=1;j<W+1;j++){
	            if(i!=1 || j!=1){
	                if(s[i-1][j-1] == '#'){
	                    dp[i][j] = 0;
	                }
	                else{
	                    dp[i][j] =0;
	                    if(i>=2){
	                        dp[i][j] = (dp[i-1][j] + dp[i][j])%MAX;
	                    }
	                    if(j>=2){
	                        dp[i][j] = (dp[i][j] + dp[i][j-1])%MAX;
	                    }
	                }
	            }
	        }
	    }
	    out<<dp[H][W];
	}
};


int main() {
	HGrid1 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 9088
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections
import bisect

def main():
    S = input()

    l = 0
    r = 0
    flag = False
    for i in range(len(S)):
        if not flag and S[i]=='A':
            l = i
            flag = True
        elif S[i]=='Z':
            r = i
    print(r - l + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 70424
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,M=rl()
A=[0]*M
for i in range(M):
    A[i] = ri()

dp = [0]*(N+4)
dp[0] = 1
for a in A:
    dp[a] = -1

for i in range(1,N+1):
    if dp[i] != -1:
        if dp[i-2] != -1:
            dp[i] += dp[i-2]
        if dp[i-1] != -1:
            dp[i] += dp[i-1]
        dp[i] %= MOD

print(dp[N])

Measured memory_bytes: 7796
#include <bits/stdc++.h>
#include <climits>
#include <sstream>
using namespace std;
const int MOD = 1000000007;

void countPN(int n,vector<int> &count){
    
    int m = n;
    for(int i = 2; i*i <= n;++i){
        
        while(m%i == 0){
            
            m/=i;
            count[i]++;
            
        }
        if(m==1)break;
    }
    if(m!=1)count[m]++;
    
    
}

int main(){
    int N;
    cin >> N;
    vector<int> count(1100);
    for(auto &x:count)x = 0;
    for(int n = 2; n <= N;n++)countPN(n,count);
    
    long long ans = 1;
    for(int n = 2; n <= N;n++){
        
        if(count[n] != 0){
            
            ans *= count[n] + 1;
            ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
    
}



Measured memory_bytes: 384
primes :: [Int]
primes = filterPrime [2 ..]
  where filterPrime (p:xs) =
          p : filterPrime [ x | x <- xs, x `mod` p /= 0 ]

main :: IO ()
main = do
  n <- read <$> getLine :: IO Int
  putStrLn $ unwords $ map show $ take n $ filter (\x -> x `mod` 5 == 1) primes


Measured memory_bytes: 1020
/*input
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
*/
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define mpr make_pair
#define MX 1000000007
#define ui unsigned int
#define ll long long
#define ld long double
#define fi first
#define se second
#define testcases int testcases;cin>>testcases;while(testcases--)
#define printvector(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" ";  cout<<endl
#define printarray(v,n)  for(int i=0;i<n;i++) cout<<v[i]<<" ";  cout<<endl
#define inputarray(v,n)  for(int i=0;i<n;i++)cin>>v[i]
#define debug(i) cout<<"debug: "<<i<<endl
#define pr(i) cout<<i<<endl
#define timetaken cerr<<clock()/double(CLOCKS_PER_SEC)<<endl
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define toDigit(a) (a-'0')
ll powmod(ll base,ll exp,ll MOD){ll res=1;while(exp>0){if(exp%2==1) res=(res*base)%MOD;base=(base*base)%MOD;exp/=2;}return (res%MOD);}
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }



int cal(int n, vector<vector<int>>& a){
    vector<vector<int>>dp(n+1,vector<int>(3,0));
    dp[1][0] = a[0][0];
    dp[1][1] = a[0][1];
    dp[1][2] = a[0][2];

    for(int i=2;i<=n;++i){
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i-1][0];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i-1][1];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + a[i-1][2];
    }
    return max({dp[n][0], dp[n][1], dp[n][2]});
}

int main() {
    fast_io;
    int n;
    cin>>n;
    
    vector<vector<int>>a(n,vector<int>(3,0));
    
    for(int i=0;i<n;++i){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    
    pr(cal(n,a));
    return 0;
}

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

int main(){
    string s;
    cin>>s;
    int n;
    cin>>n;
    vector<string> r(n);
    for (int i = 0; i < n; ++i) {
        cin>>r[i];
        r[i]+=r[i];
    }
    int ans=0;
    for (string i:r){
        if(i.find(s)!=string::npos)++ans;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3180
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define double long double
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;



signed main(){
    IOS;
    int a;
    cin >> a;
    cout << a + a * a + a * a * a << endl;
    return 0;
}

Measured memory_bytes: 3648
n = int(input())
s = input()
alph = [chr(i) for i in range(97,97+26)]
ans = 0
for i in range(n):
  cnt = 0
  for key in alph:
    if key in s[:i] and key in s[i:]:
      cnt += 1
  if cnt > ans:
    ans = cnt
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N, M;
	cin >> N >> M;
	VI A(N), B(M);
	map<int, bool> mp,mmp;
	bool F = false;
	REP(i, N) {
		cin >> A[i];
		if (mp[A[i]]) F = true;
		mp[A[i]] = true;
	}
	REP(i, M) {
		cin >> B[i];
		if (mmp[B[i]]) F = true;
		mmp[B[i]] = true;
		
	}
	rSORT(A);
	rSORT(B);
	if (F) {
		cout << 0 << endl;
		return 0;
	}
	VI ans;
	int a = 0, b = 0,co=0;
	for (int i = N * M; i > 0; i--) {
		//a = min(a, N - 1);
		//b = min(b, M - 1);
		int cnt = 0,k=0;
		if (mp[i] && mmp[i]) {
			a++;
			b++;
			co++;
		}
		else if (mp[i]) {
			a++;
			co++;
			ans.push_back(b);
			//cout << b << endl;
		}
		else if(mmp[i]){
			b++;
			co++;
			ans.push_back(a);
			//cout << a << endl;
		}
		else {
			ans.push_back(a*b - co);
			//cout << a*b - co << endl;
			co++;
		}
	}
	
	int ret = 1;
	REP(i, ans.size()) {
		ret *= ans[i];
		ret %= mod;
	}
	cout << ret << endl;
	return 0;
}



Measured memory_bytes: 133096
/******************************************
*    AUTHOR:         julianferres         *
******************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define show(v,n) cerr << #v << " = "; forn(i,n) cerr << v[i] << " "; cerr << endl;
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
const ll inf = 1LL<<62;
const int mod = 1e9+7; // 998244353
const int N  = 17;

void add(ll &a, ll b){
    a += b; 
}


int main(){
    FIN;
    ll n;
    cin >> n;
    vi dp(1 << n, -inf), sum(1 << n, 0);
    dp[0] = 0;
    ll a[n + 3][n + 3];
    forn(i,n){
        forn(j,n){
            cin >> a[i][j];
        }
    }

    forn(b, 1 << n)
    {
        forn(f, n)
        {
            forn(s, n)
            {
                if (((1 << f) & b) && ((1 << s) & b))
                {
                    add(sum[b], a[f][s]);
                }
            }
        }
        sum[b] >>= 1;
    }

    forn(i, 1<<n){
        ll x = (1<<n)-1-i;
        ll b = 0;
        do
        {
            // process subset b
            ll actSum = sum[b];

            dp[i|b] = max(dp[i|b], actSum + dp[i]);
        } while ((b = ((b - x) & (x))));
    }

    cout << dp[(1 << n) - 1] << endl;

    return 0;
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  int n;
  cin >> n;
  if(n>=400 and n<=599)
  {
    cout<<8<<'\n';
  }
  else if (n>599 and n<800)
  {
    cout<<7<<'\n';
  }
  else if(n>799 and n<1000)
  {
    cout<<6<<'\n';
  }
  else if (n>999 and n<1200)
  {
    cout<<5<<'\n';
  }
  else if (n>1199 and n<1400)
  {
    cout<<4<<'\n';
  }
  else if (n>1399 and n<1600)
  {
    cout<<3<<'\n';
  }
  else if(n>1599 and n<1800)
  {
    cout<<2<<'\n';
  }
  else if(n>1799 and n<2000){
    cout<<1<<'\n';
  }
}


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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(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...);
}
clock_t startTime;
long double getTime(){
	return (long double)(clock()-startTime)/CLOCKS_PER_SEC;
}

int main(){
	startTime=clock();
	int n;
	cin >> n;
	string s,t;
	cout << 0<<endl;
	cin >> s;
	if(s=="Vacant") return 0;

	
	int p=1;
	int q=n-1;
	cout << p<<endl;
	cin >> s;
	if(s=="Vacant") return 0;
	cout << q<<endl;
	cin >> t;
	if(t=="Vacant") return 0;
	int mid;
	string aux;
	int i=0;
	while(1){
		mid=p+(q-p)/2;
		cout <<  mid << endl;
		cin >> aux;
		if(aux=="Vacant") return 0;
		if(mid%2==p%2){
			if(aux==s) {
				p=mid+1;
				s=(aux=="Male")? "Female": "Male";
			}
			else{
				q=mid-1;
				t=(aux=="Male")?"Female":"Male";	
			} 
		}
		else{
			if(aux==s){
				q=mid-1;
				t=(aux=="Male")? "Female":"Male";
			}
			else{
				p=mid+1;
				s=(aux=="Male")? "Female": "Male";				
			}
		}
		//error(p,q,mid,aux);
	}

	return 0;
}

Measured memory_bytes: 3856