akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(ll i=0; i<(n); ++i)
#define rep1(i,n) for(ll i=1; i<=(n); ++i)
#define repi(i,a,b) for(ll i=a; i<=(b); ++i)
#define rrep(i,n) for(ll i=(n-1); i>=0; --i)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define print(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
using Edge = pair<ll,ll>;
using Graph = vector<vector<Edge>>;
typedef pair<ll,ll> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
ll MOD = 1e9 + 7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
ll devc(ll x, ll y){return 1 + (x-1)/y;}
ll modpow(ll x, ll y, ll m) {
    if (y == 0) return 1;
    ll res = modpow(x, y / 2, m);
    return res * res % m * (y & 1 ? x : 1) % m;
}
ll modinv(ll x) { return modpow(x, MOD - 2, MOD); }

int main(){
    ll N,K; cin >> N >> K;
    vector<ll> V(N); rep(i,N) cin >> V[i];
    
    vector<double> P(1005);
    rep1(i,1000){
        double num = i;
        P[i] = (1+num)/2;
    }
    
    double sum = 0;
    rep(i,K) sum += P[V[i]];
    double ans = sum;
    
    for(int i = K; i < N; ++i){
        sum += P[V[i]];
        sum -= P[V[i-K]];
        ans = max(sum,ans);
    }
    
    print(ans);
    
    return 0;
}

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

int dist(int a, int b){
  if(a==0 || b==0 || a==b){
    return max(a,b);
  }

  while(a!=b){
    if(a<b){
      swap(a,b);
    }

    if(a%b == 0){
      return b;
    }else{
      a%=b;
    }
  }
}


int main(){
  int N,X;
  cin >> N >> X;
  vector<int> w(N);

  int i,D=0;
  for(i=0; i<N; i++){
    cin >> w.at(i);
    w.at(i)-=X;
    if(w.at(i) < 0){
      w.at(i)*=-1;
    }
    D=dist(D, w.at(i));
  }

  cout << D << endl;
}

Measured memory_bytes: 640
import math
import sys
N=int(input())
c=int(math.sqrt(2*N))
for i in range(c-1,N+1):
  a=i*(i+1)//2
  if a>N:
    L=list(range(1,i+1))
    L.pop(a-N-1)
    for j in range(len(L)):
      print(L[j])
    sys.exit()
  elif a==N:
    L=list(range(1,i+1))
    for i in range(len(L)):
      print(L[i])
    sys.exit()

Measured memory_bytes: 3572
#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass

n = int(input())

li = divisor(n)

l = len(li)

if l%2 == 1:
    ans = li[l//2] * 2 -2
else:
    ans = li[(len(li)//2)] + li[(len(li)//2)-1] - 2

print(ans)

Measured memory_bytes: 9432
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <chrono>
#include <random>

using namespace std;

typedef long long ll;

struct dsu {
public:
	dsu() : _n(0) {}
	dsu(int n) : _n(n), sz(n, 1), parent(n) { std::iota(parent.begin(), parent.end(), 0); }

	void merge(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		int x = find(a), y = find(b);
		if (x == y) return;
		if (sz[x] < sz[y]) std::swap(x, y);
		sz[x] += sz[y];
		parent[y] = parent[x];
	}

	bool same(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		return find(a) == find(b);
	}

	int find(int a) {
		assert(0 <= a && a < _n);
		if (parent[a] == a) return a;
		return parent[a] = find(parent[a]);
	}

	int size(int a) {
		assert(0 <= a && a < _n);
		a = find(a);
		return sz[a];
	}

private:
	int _n;
	std::vector<int> parent;
	std::vector<int> sz;
};

void solve() {
	int n;
	cin >> n;
	vector<pair<int, pair<int, int>>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second.first;
		a[i].second.second = i;
	}
	sort(a.begin(), a.end());

	dsu d(n);
	set<pair<int,int>> q;
	for (int i = 0; i < n; i++) {
		pair<int, int> cur = { a[i].second.first, i };
		while (q.size() && q.begin()->first < a[i].second.first) {
			pair<int, int> p = *q.begin();
			q.erase(q.begin());
			d.merge(i, p.second);
			cur.first = min(cur.first, p.first);
		}
		q.insert(cur);
	}

	vector<int> ans(n);
	for (int i = 0; i < n; i++) {
		ans[a[i].second.second] = d.size(i);
	}
	for (int x : ans) {
		cout << x << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	for (; q > 0; q--) {
		solve();
		//cout << endl;
	}
}

Measured memory_bytes: 11528
//#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;

  #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

  #define ff first
  #define ss second
  #define pb push_back
  #define pf push_front
  #define mp make_pair
  #define in insert
  #define ld long double


  #define TRACE
  #ifdef TRACE
  #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  template <typename Arg1>
  void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
  }
  template <typename Arg1, typename... Args>
  void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  }
  #else
  #define trace(...) 1
  #endif
  template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
  template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}

  typedef long long int ll;

  typedef vector<int> vi;
  typedef vector<ll> vl;
  typedef vector<vi> vvi;
  typedef vector<vl> vvl;
  typedef pair<int,int> pii;
  typedef pair<ll,ll> pll;
  typedef vector<pii> vpii;
  typedef vector<pll> vpll;
  const ll mod =1e9+7;
  const ll MAX_NODES =200001;
  const ll MAX_LOG =50;
  const ll maxn = 200000+10;
  #define endl '\n'
  ll power(ll x, ll n) {
      ll res = 1;
      for (; n > 0; n >>= 1) {
      if (n & 1) res = (res * x) % mod;
      x = (x * x) % mod;
      }
      return res;
  }


  int main()
  {

  IOS
  ll n,a,b;
  cin>>n>>a>>b;
  ll ans = (power(2,n) - 1 +mod )%mod;
  
  ll pr1 = 1,pr2 = 1, x1 = 1,x2 = 1;
  for(ll i=0;i<a;i++)
  {
    pr1 = (pr1*(n-i))%mod;
    x1 = (x1*(i+1))%mod;
  }
  
  for(ll i=0;i<b;i++)
  {
    pr2 = (pr2*(n-i))%mod;
    x2 = (x2*(i+1))%mod;
  }
  
  pr1 = (pr1*power(x1,mod-2));
  pr1%=mod;
  pr2 = pr2*power(x2,mod-2);
  pr2%=mod;
  
  ans = (ans - pr1 - pr2 +2*mod) %mod;
  cout<<ans<<endl;

  
  

}


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

int main(){
  int r0, w, c, r1;
  while(cin >> r0 >> w >> c >> r1, r0 || w || c || r1){
    if(r0 / w >= c)cout << 0 << endl;
    else{
      for(int i = 1; ; i++){
        if(((r0 + i * r1) / w) >= c){
          cout << i << endl;
          break;
        }
      }
    }
  }
}

Measured memory_bytes: 3032
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7; const int MAX = 200020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 1e18;

void solve() {
	int N; cin >> N;
	vector<int>X(N);
	REP(i, N) {
		cin >> X[i];
	}
	ll ans = 1e18;
	REP(pos, 101) {
		ll res = 0;
		REP(i, N) {
			res += (X[i] - pos)*(X[i] - pos);
		}
		ans = min(ans, res);
	}
	print(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
ll n, k;
ll ans;

int main() {
	cin >> n >> k;
	if(!k) ans = n * n;
	else {
		ans += (1 + n - k) * (n - k) / 2;
		for(ll b = k + 1; b <= n; b++) { //被模的数
			for(ll r = k; r < b; r++) { //枚举余数
				ll tmp = (n - r) / b;
				if(!tmp) break;
				ll dd = n - tmp * b;
				dd = min(dd, b - 1);
				ans += tmp * (dd - r + 1);
				r = dd;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

A, B = lr()
if A == B:
    answer = A + B
else:
    C = max(A, B)
    answer = C + C - 1

print(answer)
# 36

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define PI 3.14159265358979
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repp(i, s, e) for(int i = (s); i <= (e); ++i)
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0)
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { for (auto x : v) os << x << " "; return os << "\n"; }
template<class U, class V>
ostream& operator<<(ostream &os, const pair<U, V> &p) { return os << "(" << p.first << "," << p.second << ")";}

int main() {
	int N; cin >> N;
	double ans = 0;
	rep(i, N) {
		int x; cin >> x;
		ans += 1.0 / x;
	}
	cout.precision(10);
	cout << 1.0 / ans << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef long long ll;
const ll mo=1e9+7,N=11e4;

int a[N],n,m;
ll jz[3][3],lj[3][3],ans[3][3],keep[3][3];

inline int read()
{
	int o=0; char ch=' ';
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())o=o*10+ch-48;
	return o;
}

inline void fz()
{fo(i,0,2)fo(l,0,2)lj[i][l]=jz[i][l];}

inline void twice()
{
	fo(i,0,2)fo(l,0,2){
		keep[i][l]=0;
		fo(j,0,2)keep[i][l]=keep[i][l]+lj[i][j]*lj[j][l];
	}
	fo(i,0,2)fo(l,0,2)lj[i][l]=keep[i][l]%mo;
}

inline void join()
{
	fo(i,0,2)fo(l,0,2){
		keep[i][l]=0;
		fo(j,0,2)keep[i][l]=keep[i][l]+ans[i][j]*lj[j][l];
	}
	fo(i,0,2)fo(l,0,2)ans[i][l]=keep[i][l]%mo;
}

inline void count(int t)
{
	fz();
	for(;t;t>>=1,twice())
	if(t&1)join();
}

int main()
{
	cin>>n>>m;
	fo(i,1,m)a[i]=read();
	jz[0][0]=1; jz[0][1]=2; jz[0][2]=1; jz[2][0]=1;
	jz[1][1]=1; jz[1][2]=1; jz[2][1]=2; jz[2][2]=2;
	ans[0][0]=ans[1][1]=ans[2][2]=1;
	fo(i,1,m){
		count(a[i]-a[i-1]-1);
		fz(); lj[2][0]=0; lj[2][2]=1; lj[2][0]=lj[2][1]=0;
		join();
	}
	count(n-a[m]-1);
	cout<<(ans[0][2]+ans[1][2]*2+ans[2][2])%mo;
}

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

int main() {
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	int dp[n][3];
	
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){dp[i][j]=0;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			
			if(i==0){
				if(j==0)dp[i][j]=a[i];
				else if(j==1)dp[i][j]=b[i];
				else dp[i][j]=c[i];
			}
			else{
				for(int k=0;k<3;k++){
					if(j==k)continue;
					
					if(j==0)
						dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i]);
					else if(j==1)
						dp[i][j]=max(dp[i][j],dp[i-1][k]+b[i]);
					else 
						dp[i][j]=max(dp[i][j],dp[i-1][k]+c[i]);
				}
			}
		}
	}
	
	int x=0;
	x=max(x,dp[n-1][0]);
	x=max(x,dp[n-1][1]);
	x=max(x,dp[n-1][2]);
	
	cout<<x;
	return 0;
}

Measured memory_bytes: 2560
'''
参考
https://drken1215.hatenablog.com/entry/2020/05/02/225600

int(A*x/B) - A * int(x/B) の値は、Bごとに周期的になる
よって、x = min(B-1, N)となる
'''
A, B, N = map(int, input().split())
x = min(B-1, N)

print(int(A*x/B) - A * int(x/B))


Measured memory_bytes: 9164
use proconio::{fastout, input};
use std::collections::{HashMap, HashSet};

#[fastout]
#[allow(non_snake_case)]
#[allow(unused)]
fn main() {
    input! {
        W: usize,
        H: usize,
        M: usize,
        HW: [(usize, usize); M],
    }

    let mut xmax = 0;
    let mut ymax = 0;

    let mut xmap: HashMap<usize, usize> = HashMap::new();
    let mut ymap: HashMap<usize, usize> = HashMap::new();

    for &(x, y) in &HW {
        let xn = xmap.entry(x).or_insert(0 as usize);
        let yn = ymap.entry(y).or_insert(0 as usize);

        *xn += 1;
        *yn += 1;

        xmax = std::cmp::max(xmax, *xn);
        ymax = std::cmp::max(ymax, *yn);
    }

    let xmaxs: Vec<usize> = xmap
        .iter()
        .filter(|(&k, &v)| v == xmax)
        .map(|(&k, &v)| k)
        .collect();

    let ymaxs: Vec<usize> = ymap
        .iter()
        .filter(|(&k, &v)| v == ymax)
        .map(|(&k, &v)| k)
        .collect();

    let set: HashSet<(usize, usize)> = HW.clone().into_iter().collect();

    let res = xmaxs.iter().find(|&&x| {
        ymaxs.iter().find(|&&y| !set.contains(&(x, y))).is_some()
    }).is_some();

    let ans = xmax + ymax - (if res { 0 } else { 1 });
    println!("{}", ans);
}


Measured memory_bytes: 46248
# Counting Sort

N = int(input())
lst = list(map(int, input().split()))
k = max(lst)
B = [-1]*N
C = [0] * (k+1)

def counting_sort(A, B, k):
    # 出現回数をカウント
    for a in A:
        C[a] += 1
    # 累積和を作成
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for a in A[::-1]:
        C[a] -= 1
        B[C[a]] = a
        
counting_sort(lst, B, k)
print(*B)
        


Measured memory_bytes: 224380
#include<cstdio>
#include<cmath>
#include<malloc.h>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
int main()
{
	int n,m,t[105];
	int p,x,a[105];//a[1]喝完第一种药水解决问题的总时间 
	while(~scanf("%d",&n))
	{
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&t[i]);
			ans+=t[i];
		}
		scanf("%d",&m);
		for(int j=1;j<=m;j++)
		{
			scanf("%d %d",&p,&x);
			a[j]=ans+x-t[p];
		}
		for(int j=1;j<=m;j++)
		printf("%d\n",a[j]);
	}
	return 0;	
} 

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

using ll = long long int;
using bigint = int64_t;

#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define bitcount __builtin_popcount
#define endl "\n"
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define deb(x) cout << #x << " = " << x << endl;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(ll i = a; i <= b; i++)
#define ffo(i, a, b) for(ll i = a; i >= b; i--)
#define ffi(i,a,b,c) for(ll i = a ; i <= b ; i += c)
#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int MOD = 1000000007;

void io_set(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

void solve(){
    ll n, s = 0;
    map < ll, ll > mpp;
    cin >> n;
    ll a[n];
    rep(i, n)   cin >> a[i], mpp[a[i]]++, s += a[i];
    ll q, b, c;
    cin >> q;
    while(q--){
        cin >> b >> c;
        s -= (mpp[b]*b);
        s += (mpp[b]*c);
        mpp[c] += mpp[b];
        mpp[b] = 0;
        cout << s << endl;
    } 
}

int main(){
    IOS;
    //io_set();
    ll tt = 1;
    //cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
} 

Measured memory_bytes: 10156
n,m=gets.split.map(&:to_i)
q=[nil]+gets.split.map(&:to_i)
l=[nil]
n.times do
  l << []
end
m.times do
  x,y=gets.split.map(&:to_i)
  l[x] << y
  l[y] << x
end
v=[0]*(n+1)
t=[nil]
1.upto(n) do |i|
  next if v[i]>0
  v[i]=i
  s=[i]
  tt=[i]
  while s!=[]
    z=[]
    s.each do |ss|
      l[ss].each do |lss|
        if v[lss]==0
          v[lss]=i
          z << lss
          tt << lss
        end
      end
    end
    s=z.dup
  end
  t << tt
end
c=0
1.upto(n) do |i|
  if v[i]==v[q[i]]
    c+=1
  end
end
puts c


Measured memory_bytes: 36416
// https://atcoder.jp/contests/abc094/tasks/arc095_b
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end(), greater_equal<long long>());
    long long ans1 = a[0];
    long long mid = ans1 / 2;
    long long ans2 = 0;
    long long minval = std::numeric_limits<long long>::max();
    for (auto it = a.begin(); it != a.end(); ++it)
    {
        long long diff = abs(*it - mid);
        if (minval > diff) minval = diff, ans2 = *it;
    }
    if (ans1 == ans2) ans2 = *a.end();
    cout << ans1 << " " << ans2 << endl;
    return 0;
}


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

int main(){
	int root[6][2]={{1,2},{-1,3},{1,-1},{4,5},{5,2},{2,1}};
	int now;
	string p;
	
	while(cin>>p){
		if(p=="#")break;
		now=0;
		for(int i=0;i<p.size();i++){
			now=root[now][p[i]-'0'];
			if(now==-1)break;
		}
		if(now==5)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

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

using namespace std;

#define rep1(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, n, m) for (long long i = (long long)(n); i <= (long long)(m); i++)
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
const ll mod = 998244353;

ll memo[200001];

ll pow(ll n, ll p) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        ll tmp = pow(n, p / 2) % mod;
        return tmp * tmp % mod;
    }
    return n * pow(n, p - 1) % mod;
}

ll combination(ll n, ll r) {
    return memo[n] * pow((memo[n - r] * memo[r]) % mod, mod - 2) % mod;
}

int main() {
    memo[0] = 1;
    rep2 (i, 1, 200000) memo[i] = memo[i - 1] * i % mod;
    ll n, m, k;
    cin >> n >> m >> k;
    ll count = 0;
    rep1(i, k + 1) {
        ll tmp = m * pow(m - 1, n - i - 1) % mod;
        tmp *= combination(n - 1, i) % mod;
        tmp %= mod;
        count += tmp;
        count %= mod;
    }
    cout << count << endl;
}

Measured memory_bytes: 5148
#include <stdio.h>

int main(void){
    int h,w;
    while (1){
        scanf("%d %d",&h,&w);
        if(h==0 && w==0){
            break;
        }else{
            for(int i=0; i<h; i++){
                for(int 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: 2060
#include<stdio.h>
#include<string.h>
int main()
{
  char s[10],t[11];
scanf("%s %s",s,t);
int a=strlen(t);
int flag=0;
for(int i=0;i<a-1;i++)
{if(s[i]!=t[i])
{flag=1;
 
} 
}
if(flag==0)
{printf("Yes\n");}
else{printf("No\n");}
return 0;}


Measured memory_bytes: 1664
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;
using ll = long long;
// const ll mod =  998244353 ;
const ll mod =  1000000007 ;
const ll inf = 1e18;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

struct Node {
  int a;
  int b;
  Node *child;
  Node(int _a, int _b) : a(_a), b(_b) {
    child = nullptr;
  }
    Node(int _a, int _b, Node *_child) : a(_a), b(_b), child(_child) {
  }
};

bool check(int x, const vector<ll> & a) {
  vector<set<int>> dp(sz(a) + 1);
  dp[0].insert(0);
  REP(i, sz(a)) {
    for(const int k : dp[i]) {
      dp[i+1].insert(k+a[i]);
      dp[i+1].insert(k-a[i]);
    }
  }
  return dp[sz(a)].count(x) > 0;
}
signed main() {
  ios::sync_with_stdio(false);
  string s;
  int x, y;
  cin >> s >> x >> y;
  vector<ll> a, b;
  int start = 0;
  REP(i, sz(s)) {
    if(s[i] == 'F') start++;
    else break;
  }
  x -= start;
  int cnt = 0;
  int rgt = 1;
  REP_FROM(i, start, sz(s)) {
    if(s[i] == 'F') {
      cnt++;
      continue;
    }
    if(cnt) {
      if(rgt) {
        a.push_back(cnt);
      }
      else {
        b.push_back(cnt);
      }
      cnt = 0;
    }
    rgt ^= 1;
  }
  if(cnt) {
    if(rgt) {
      a.push_back(cnt);
    }
    else {
      b.push_back(cnt);
    }
  }
  if(check(x, a) && check(y, b)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 167356
n = int(input())

ans = 0
for i in range(1, n+1, 2):
    divisor_amount = 0
    for j in range(1, i+1):
        if i % j == 0:
            divisor_amount += 1
    if divisor_amount == 8:
        ans += 1

print(ans)
            

Measured memory_bytes: 2940
#include <stdio.h>

int main()
{
  int A,B,C;
  int a,b;

  scanf("%d%d%d",&A,&B,&C);

  if(A<B){
    a=A;
    b=B;
  }else{
    a=B;
    b=A;
  }
  if(a<C&&b>C){
    printf("Yes\n");
  }else{
    printf("No\n");
  }

  return 0;

}


Measured memory_bytes: 128
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque, BTreeSet, BTreeMap};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let mut s: Vec<char> = util::line().chars().rev().collect();

    for c in "AKIHABARA".chars() {
        if s.last().cloned() == Some(c) {
            s.pop();
        } else if c == 'A' {
            continue;
        } else {
            println!("NO");
            return;
        }
    }

    if s.is_empty() {
        println!("YES");
    } else {
        println!("NO");
    }

}


Measured memory_bytes: 4352
#include <iostream>
#include <stdio.h>
#include <strings.h>
#include <cstring>

using namespace std;
 
int main(){
    string a,b;
    int c = 0;
    cin >> a;
    for(int i = 0; i < 1000; i++){
        cin >> b;
        if(b == "END_OF_TEXT") break;
        for(int i = 0; i < (int)b.size(); i++){
            if(b[i] >= 'A' && b[i] <= 'Z'){
                b[i] += 32;
            }
        }
        if(a == b){
            c++;
        }
    }
    cout << c << endl;
    return 0;
}


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

using namespace std;

#define int long long

template <typename T> T gcd(T m, T n) { return n == 0 ? m : gcd(n, m % n); }
template <typename T> T lcm(T m, T n) { return n * m / gcd(n, m); }
template <typename T> T fact(T n) { return (n == 0 ? 1 : n * fact(n - 1)); }
template <typename T> T modpow(T a, T e, T m) { return (e == (T)0 ? 1 : ((a % m) * modpow((a % m), e - 1, m)) % m); }

constexpr int MOD = 1e9 + 7;

signed main(void) {
  int n, k, s;
  cin >> n >> k >> s;

  vector<int> a(n);

  for (int i = 0; i < n; ++i) {
    if (i < k) {
      a[i] = s;
    } else {
      if (s == 1e9)
        a[i] = s - 1;
      else
        a[i] = s + 1;
    }
  }

  for (int i = 0; i < n; ++i) {
    cout << a[i];
    if (i != n - 1)
      cout << " ";
    else
      cout << endl;
  }
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
	}
	vector<pair<int, int> > vp;
	for (int i = 0; i < N; i++) {
		vp.emplace_back(A[i] + B[i], i);
	}
	sort(vp.rbegin(), vp.rend());
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) {
			res += A[vp[i].second];
		}
		else {
			res -= B[vp[i].second];
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 3956
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	vs := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&vs[i])
	}
	cs := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&cs[i])
	}

	sum := 0
	for i := 0; i < n; i++ {
		if v := vs[i] - cs[i]; v > 0 {
			sum += v
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 512
#include<stdio.h>
int main(void)
{
  int n,v[21],c[21],ans=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&v[i]);
  }
  for(int i=0;i<n;i++){
    scanf("%d",&c[i]);
  }
  for(int i=0;i<n;i++){
    if(v[i]-c[i]>0){
      ans+=v[i]-c[i];
    }
  }
  printf("%d",ans);
  return 0;
}


Measured memory_bytes: 128
def dot(a: complex, b: complex) -> float:
    return a.real * b.real + a.imag * b.imag


def cross(a: complex, b: complex) -> float:
    return a.real * b.imag - a.imag * b.real


if __name__ == "__main__":
    n = int(input())
    coordinates = [complex(*map(int, input().split())) for _ in range(n)]
    pairs = [(p0, p1) for p0, p1
             in zip(coordinates, coordinates[1:] + [coordinates[0]])]
    q = int(input())

    for _ in range(q):
        p = complex(*map(int, input().split()))
        counter = 0
        for p0, p1 in pairs:
            a, b = p0 - p, p1 - p
            if a.imag > b.imag:
                a, b = b, a
            crs = cross(a, b)
            if a.imag <= 0 and 0 < b.imag and crs < 0:
                counter += 1
            if crs == 0 and dot(a, b) <= 0:
                print(1)
                break
        else:
            print(2 if counter % 2 else 0)



Measured memory_bytes: 5688
#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int maxn=310;
int mod,n,K;
ll dp[maxn][maxn],C[maxn][maxn],sum[maxn][maxn];
void wo(int x) {
	for(int i=K;i>=0;i--) sum[x][i]=(sum[x][i+1]+dp[x][i])%mod; 
}
int main() 
{
	scanf("%d%d%d",&n,&K,&mod);
	C[0][0]=1;
	for(int i=1;i<=n+1;++i) {C[i][0]=1;
		for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; 
	}
	for(int i=0;i<=K;++i) dp[1][i]=1;
	wo(1);
	for(int i=2;i<=n+1;++i) {
		for(int j=0;j<=K;++j) {
			for(int k=1;k<i;++k) {
				dp[i][j]=(dp[i][j]+sum[k][j+1]*dp[i-k][j]%mod*C[i-2][k-1]%mod)%mod;		
			}
		}
		wo(i);
	}
	cout<<dp[n+1][0]<<"\n";
	return 0;
} 


Measured memory_bytes: 2432
#include <math.h>
#include <stdio.h>
int nn, sqrtN;
long long ans, d;
int main() {
    scanf("%d",&nn);
    const int n = nn;
    if(n == 1) {
        putchar(49);
    } else {
        const int sqrtN = sqrt(n);
        ans = -(long long)(sqrtN) * (sqrtN + 1) * (2 * sqrtN + 1) / 6;
        for(int i = 1; i <= sqrtN; ++i) {
            const int a = n / i;
            ans += ((long long)i * (i + a) * (a + 1 - i));
        }
        printf("%lld",ans);
    }
}

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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back

const int INF = 1e9;
const int MOD = 1e9+7;

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i++)
#define RepA(x) for(auto &item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

//library----------------------------------------------



int main() {
    SCIN(s);
    rep(i,s.size())printf("x");
    printf("\n");
    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    double x = x2-x1, y = y2-y1;
    
    cout << fixed << setprecision(4) << sqrt(x*x + y*y) << endl;
    
    return 0;
}


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

#define deb(x) cout << #x << "=" << x << endl
#define ll long long

const int mod = 1000000007;
const int N = 3e5, M = N;

void solve() {
	ll a, b, n, k;
	ll input;
	cin >> n >> k;
	vector<ll> h(n);
	ll dp[n + 1];

	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	dp[0] = 0;
	for (int i = 1; i < n; i++) {
		dp[i] = INT_MAX;
		for (int j = i - 1; j >= i - k && j >= 0; j--) {
			dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
		}
	}
	ll res = dp[n - 1];
	cout << res << endl;








}



int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}



Measured memory_bytes: 4780
#3問目
NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = set([int(input()) for _ in range(M)])
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
MOD = 1000000007
    
if(1 in A):
    dp[1] = 0

for i in range(2, N+1):
    #貰うdp
    if(i in A):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
    dp[i] %=MOD
    
print(dp[N])

Measured memory_bytes: 13216
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}



signed main() {

    int n;
    cin >> n;
    vector<int> p(n), q(n), v;

    for(int i = 0; i < n; i++) cin >> p[i];
    for(int i = 0; i < n; i++) {
        cin >> q[i];
        v.bash(i+1);
    }
    int a = -1, b = -1, i = 1;
    do {
        //for(auto j : v) cout << j << " \n"[j==v.back()];
        if(v == p) a = i;
        if(v == q) b = i;
    }while(i++, next_permutation(ALL(v)) or a == -1 or b == -1);

    cout << abs(a-b) << endl;
  
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    lint X, A, B;
    cin >> X >> A >> B;
    cout << (X - A) % B << "\n";
}

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

typedef long long ll;

int main() {
    ll N, K, p, dmax = 0, d;
    cin >> N >> K;
    vector<int> s(N + 1, 0);
    rep(i, N) {
        //p = 1000;
        cin >> p;
        s[i + 1] = s[i] + p;
        if (i < K - 1) continue;
        d = s[i + 1] - s[i - K + 1];
        if (d > dmax) dmax = d;
    }
    cout << setprecision(10) << (1.0 * K + dmax) / 2 << endl;
}

Measured memory_bytes: 1024
/*
	*#*#*#* Author GaryMr *#*#*#*
########################################################################
	是否可以简化问题：
	是否可以化具体为抽象
	字符串问题是否可以用数学模拟递归过程（取c[i]或不取来算结果）
	二分？左闭右开？
	long long？
	逆向思维？
	dp？
	贪心？
	匹配括号 左减右>=0
	多组数据清空？
	dp优化用g？
	线段树：大小为n的8倍
	线段树：左闭右开！
	线段树：find： if(l>=b||r<=a) return 0x3f3f3f3f; if(r<=b&&l>=a) return tree[k];
	线段树：满二叉树 
	循环跳出条件 
	代数设出每个值寻找关系？
	优先队列：priority_queue<类型> q;   
	priority_queue<类,vector<类>, less<类> > pq1; 　　　 // 使用递减	
	priority_queue<类，vector<类>, greater<类> > pq2; 　　// 使用递增
	判断括号，判断是否长度为偶数
	1<<ceil(log2(double(n)))
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;a++)
#define rl(a,b,c) for(int a=b;a>=c;a--)
#define niv vector<int>
#define IT iterator
#define FIR first
#define SEC second
using namespace std;
const int MAX=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int h,w;
char TU[1001][1001];
int cost[1001][1001],vist[1001][1001];
map<int,int> MM;
queue<pair<mp,int> > q;
int main(){
	scanf("%d %d",&h,&w);getchar();
	rb(i,1,h){
		rb(j,1,w){
			TU[i][j]=getchar();
		}
		getchar();
	} 
	rb(i,1,h)
	{
		rb(j,1,w){
			if(TU[i][j]=='#'){
				cost[i][j]=0;
				vist[i][j]=1;
				q.push({make_pair(i-1,j),1});
				q.push({make_pair(i,j-1),1});
				q.push({make_pair(i+1,j),1});
				q.push({make_pair(i,j+1),1});
			}
		}
	}
	while(!q.empty()){
		queue<pair<mp,int> > oldq;
		while(!q.empty()){
			int x=q.front().FIR.FIR,y=q.front().FIR.SEC,tmpcost=q.front().SEC;
			q.pop();
			if(vist[x][y]||x<1||x>h||y<1||y>w) continue;
			vist[x][y]=1;
			cost[x][y]=tmpcost;
			oldq.push({{x+1,y},tmpcost+1});
			oldq.push({{x,y+1},tmpcost+1});
			oldq.push({{x-1,y},tmpcost+1});
			oldq.push({{x,y-1},tmpcost+1});
		}
		q=oldq;
	}
	int final=-1;
	rb(i,1,h){
		rb(j,1,w){
			final=max(final,cost[i][j]);
			}
	}
	printf("%d\n",final);
	return 0;
}

Measured memory_bytes: 58420
#!/usr/bin/env python3
#ABC88 B

n = int(input())
a = list(map(int,input().split()))
a.sort()
a.reverse()
alice = 0
bob = 0
for i in range(n):
    if i % 2 == 0:
        alice += a[i]
    else:
        bob += a[i]
print(alice - bob)


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
#define NL            "\n"
#define _SAD()        ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
#define SZ(s)         s.size()
#define SRT(x,y)      sort(x,x+y)
#define REV(a,b)      reverse(a,a+b)
#define VSRT(x)       sort(x.begin(),x.end())
#define VREV(x)       reverse(x.begin(),x.end())
int main()
{
    _SAD()
    int a,b;
    cin>>a>>b;
    if((a>=1&&a<=9)&&(b>=1&&b<=9))
    {
        cout<<a*b<<NL;
        return 0;
    }
    cout<<"-1"<<NL;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
int d[222222];
long long pr[555555],su[555555];
const int C=262144; 
long long qpr(int p)
{
	long long ans=0x3f3f3f3f3f3f3f3fll;
	for(register int i=C,j=p+C+1;i+1!=j;i>>=1,j>>=1)
	{
		if(!(i&1))cmin(ans,pr[i^1]);
		if(j&1)cmin(ans,pr[j^1]);
	}
	return ans;
}
long long qsu(int p)
{
	long long ans=0x3f3f3f3f3f3f3f3fLL;
	for(register int i=p-1+C,j=200000+C+1;i+1!=j;i>>=1,j>>=1)
	{
		if(!(i&1))cmin(ans,su[i^1]);
		if(j&1)cmin(ans,su[j^1]);
	}
	return ans;
}
void mpr(int p,long long v)
{
	pr[p+C]=v;
	for(register int i=p+C>>1;i;i>>=1)
		pr[i]=dmin(pr[i<<1],pr[i<<1|1]);
}
void msu(int p,long long v)
{
	su[p+C]=v;
	for(register int i=p+C>>1;i;i>>=1)
		su[i]=dmin(su[i<<1],su[i<<1|1]);
}
long long f[222222];
long long add;
int main()
{
	int n=io::F(),q=io::F(),a=io::F(),b=io::F();
	memset(f,63,sizeof(f));
	d[0]=a;
	f[b]=0;
	for(register int i=1;i<=q;++i)d[i]=io::F();
	memset(pr,63,sizeof(pr));
	memset(su,63,sizeof(pr));
	mpr(b,f[b]-b);
	msu(b,f[b]+b);
	for(register int i=1;i<=q;++i)
	{
		long long t1=qpr(d[i]-1)+d[i]+add;
		long long t2=qsu(d[i])-d[i]+add;
		add+=d[i]>d[i-1]?d[i]-d[i-1]:d[i-1]-d[i];
		f[d[i-1]]=dmin(t1,t2)-add;
		mpr(d[i-1],f[d[i-1]]-d[i-1]);
		msu(d[i-1],f[d[i-1]]+d[i-1]);
	}
	long long ans=0x3f3f3f3f3f3f3f3f;
	for(register int i=1;i<=n;++i)cmin(ans,f[i]+add);
	printf("%lld\n",ans);
	return 0;
}




Measured memory_bytes: 11392
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;

vector<ll> d(200000, 0), ten(200000, 0);

ll Expow(ll a, int d) {
	ll ans = 1;
	while (d > 0) {
		if (d & 1)
			ans = ans * a % MOD;
		d >>= 1;
		a = a * a % MOD;
	}
	return ans;
}

ll Inverse(ll a) {
	if (a == 0)
		return 1;
	return Expow(a, MOD - 2);
}

ll Combi(int n, int k) {
	ll a = d[n], b = Inverse(d[k]), c = Inverse(d[n - k]);
	a *= b;
	a %= MOD;
	a *= c;
	a %= MOD;
	return a;
}

void Ini(int n) {
	ll a = 1, t = 100, tt = 100;
	for (int i = 1; i < n; i++) {
		a = a * i % MOD;
		ten[i] = tt;
		tt = tt * t % MOD;
		d[i] = a;
	}
	return;
}
//375000004
int main(void) {
	int n, a, b, c;
	cin >> n >> a >> b >> c;
	if (c != 0) {
		a = a * 100 * Inverse(100 - c) % MOD;
		b = b * 100 * Inverse(100 - c) % MOD;
	}
	Ini(2 * n);
	ll ans, aa, bb, cc, A, B, an = Expow(a, n), bn = Expow(b, n);
	ans = (an + bn) % MOD;
	ans *= Inverse(ten[n]);
	ans %= MOD;
	ans *= n;
	ans %= MOD;
	A = a; B = b;
	for (int i = n; i < 2 * n - 1; i++) {
		cc = Combi(i, n - 1);
		aa = an * B % MOD;
		bb = bn * A % MOD;
		aa = (aa + bb) % MOD;
		aa *= cc;
		aa %= MOD;
		aa *= i + 1;
		aa %= MOD;
		ans += aa * Inverse(ten[i + 1]) % MOD;
		ans %= MOD;
		A = A * a % MOD;
		B = B * b % MOD;
	}
	if (c != 0) {
		ans *= 100;
		ans %= MOD;
		ans *= Inverse(100 - c);
		ans %= MOD;
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define N 200010
int n,m,a[N],v[N],nxt[N],h[N],ec,hx,hy,p[N],f[N],st[N],tp;
int fd(int x){return p[x]==x?x:p[x]=fd(p[x]);}
void add(int x,int y){v[++ec]=y;nxt[ec]=h[x];h[x]=ec;}
void dfs(int x,int fa,int va){
	a[x]=va;
	for(int i=h[x];i;i=nxt[i])
		if(v[i]!=fa){
			f[v[i]]=x;
			dfs(v[i],x,-va);
			a[x]+=a[v[i]];
		}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)p[i]=i;
	hx=hy=1;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(fd(x)!=fd(y))p[fd(x)]=fd(y);
		else{
			hx=x;
			hy=y;
			continue;
		}
		add(x,y);add(y,x);
	}
	dfs(hx,0,-1);
	if(n==m){
		for(int i=hy;i;i=f[i])
			st[++tp]=a[i];
		if(tp&1){
			if(a[hx]&1){
				puts("-1");
				return 0;
			}
			for(int i=hy;i;i=f[i])
				a[i]-=a[hx]/2;
		}
		else{
			if(a[hx]){
				puts("-1");
				return 0;
			}
			sort(st+1,st+tp+1);
			for(int i=hy;i;i=f[i])
				a[i]-=st[tp/2];
		}
	}
	else if(a[1]){
		puts("-1");
		return 0;
	}
	int r=0;
	for(int i=1;i<=n;i++)r+=abs(a[i]);
	cout<<r;
}

Measured memory_bytes: 9216
N, Q = map(int, input().split())

S = input()
cumurative_sum_lst = [0]*(N+1)
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        cumurative_sum_lst[i+1] = cumurative_sum_lst[i] + 1
    else:
        cumurative_sum_lst[i+1] = cumurative_sum_lst[i]

outputs = []
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1

    tmp = cumurative_sum_lst[r] - cumurative_sum_lst[l]
    outputs.append(int(tmp))

for i in outputs:
    print(i)



Measured memory_bytes: 10316
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = float('inf')
    for i in range(2 ** (H - 1)):
        group = 0
        h_id = [0] * H
        for j in range(H):
            h_id[j] = group
            if i >> j & 1:
                group += 1
        
        group += 1
        c = [[0] * W for _ in range(group)]
        for h in range(H):
            for w in range(W):
                c[h_id[h]][w] += S[h][w]
        g_flag = True
        for g in range(group):
            for w in range(W):
                if c[g][w] > K:
                    g_flag = False

        if not g_flag:
            continue

        cnt = group - 1
        now = [0] * group
        flag = True
        for w in range(W):
            for g in range(group):
                now[g] += c[g][w]
                if now[g] > K:
                    flag = False
                    cnt += 1
                    break
            
            if not flag:
                for g in range(group):
                    now[g] = c[g][w]
                flag = True
        ans = min(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 46556
n, x = [int(i) for i in input().split()]

b = [1]
for _ in range(n + 1):
    b.append(b[-1] * 2 + 3)
c = [1]
for _ in range(n + 1):
    c.append(c[-1] * 2 + 1)

def a(x, n):
    if x == 0:
        return 0
    if n == 0:
        return c[0]
    x-=1
    ans = 0
    if x >= b[n - 1]:
        ans += c[n - 1]
        x -= b[n - 1]
    else:
        return a(x, n - 1)
    if x == 0:
        return ans
    elif x == 1:
        return ans + 1
    else:
        ans += 1
        x -= 1
        ans += a(x, n - 1)
        return ans
    
print(a(x,n))


Measured memory_bytes: 3064
X, N = map(int, input().split())

ans = 0

if N == 0:
  ans = X
else:
  p = list(map(int, input().split()))
  for i in range(1, 102):
    if p.count(i)==0 and abs(ans-X) > abs(i-X):
      ans = i
print(ans)

Measured memory_bytes: 9192