akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int main(){
    int n, k, gap  = 0;
    char sp;
    cin >> n >> k;
    string s;
    cin >> s;
    sp = s[0];
    for(int i=1; i<n; i++){
        if(sp!=s[i]) gap += 1;
        sp = s[i];
    }
    if(gap>=2*k) cout <<(n-1)-(gap-2*k);
    if(gap<2*k) cout << n-1;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;

const long double eps = 1e-10;
typedef complex<long double> Point; // 複素数平面をR^2とみなす
typedef tuple< Point, long double > Circ;
template <typename Cost>
class edge {
public:
  int from;
  int to;
  Cost cost;
  edge(int t, Cost c) : to(t), cost(c) { ; }
  edge(int f, int t, Cost c) : from(f), to(t), cost(c) { ; }
};

template <typename Cost>
class ShortestPath{
public:
  vector< vector<edge<Cost> > > G;
  ShortestPath(){;}
  ShortestPath(int n){ G.resize(n); }
  void add_bi_edge(int s, int t, Cost dist){
    G[s].push_back( edge<Cost>(s, t, dist) );
    G[t].push_back( edge<Cost>(t, s, dist) );
  }
  vector<Cost> dijkstra(int s, const Cost zero, const Cost inf){
    typedef pair<Cost, int> P; // first:最短距離 second:頂点番号
    int V = G.size();
    priority_queue< P, vector<P>, greater<P> > Q;
    vector<Cost> d(V);
    fill(d.begin(), d.end(), inf);
    d[s] = zero;
    Q.push( P( zero, s ) );
    while( !Q.empty() ){
      P p = Q.top(); Q.pop();
      int v = p.second;
      if( d[v] < p.first ) continue;
      for(int i = 0; i < G[v].size(); i++){
	edge<Cost> e = G[v][i];
	if( d[e.to] > d[v] + e.cost ){
	  d[e.to] = d[v] + e.cost;
	  Q.push( P( d[e.to], e.to ) );
	}
      }
    }
    return d;
  }
};

Point ps, pt;
vector<Circ> c;
int N, s, t;

long double di( Point a, Point b, long double r ){
  long double d = abs( a-b );
  return max( (long double)0, d-r );
}
int main(){
  long double a, b, r;
  cin >> a >> b;
  ps = Point( a, b );
  cin >> a >> b;
  pt = Point( a, b );
  cin >> N;
  c.resize(N);
  REP(i,N){
    cin >> a >> b >> r ;
    c[i] = Circ( Point(a,b), r );
  }
  ShortestPath<long double> sp(N+3);
  s = N; t = N+1;
  sp.add_bi_edge( s, t, abs( ps-pt ) );
  REP(i,N){
    Point p, q;
    long double rp, rq;
    tie(p,rp) = c[i];
    sp.add_bi_edge( s, i, di(ps,p,rp) );
    sp.add_bi_edge( t, i, di(pt,p,rp) );
    sp.add_bi_edge( i, i, (long double)0 );
    for(int j = 0; j < i; j++){
      tie(q,rq) = c[j];
      sp.add_bi_edge( i, j, di(p,q,rp+rq) );
    }
  }
  /*
  REP(i,sp.G.size()){
    REP(j,sp.G[i].size()){
      auto e = sp.G[i][j];
      cout << e.from << " -> " << e.to << " cost=" << e.cost << endl;
    }
  }
  */
  vector<long double> ans = sp.dijkstra( s, (long double)0, (long double)1e18 );
  //  cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
  cout << fixed << setprecision(10) << ans[t] << endl;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
vector<ll> A;

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

    cin >> N;
    A.resize(N);

    ll sum = 0;
    REP(i, N) {
        cin >> A[i];
        sum += A[i];
    }

    ll ans = LLINF;
    ll cur = 0;
    REP(i, N) {
        cur += A[i];
        ll cand = abs((sum - cur) - cur);
        ans = min(cand, ans);
    }

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
#define vint vector<int>
#define vll vector<ll>
typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int from, to, cost; };
struct gNode { int from, to, cost; };
struct tNode { int value; int parent; vector<int> child; };

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

ll gcd(ll a, ll b){ return a % b == 0 ? b : gcd(b, a%b); }
ll lcm(ll a, ll b){ return a * b/ gcd(a, b); }
ll extgcd(ll a, ll b, ll& x, ll& y){
	ll d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}
ll mod_pow(ll x, ll n){
	if(n == 0) return 1;
	ll res = mod_pow(x*x % MOD, n/2);
	if(n & 1) res = res * x % MOD;
	return res;
}

vector<pair<ll, int> > factorize(ll n){
	vector<pair<ll, int> > res;
	for(ll i=2; i*i<=n; ++i){
		if(n%i) continue;
		res.emplace_back(i, 0);
		while(n%i == 0){
			n /= i;
			res.back().second++;
		}
	}
	if(n != 1)res.emplace_back(n, 1);
	return res;
}

int main(void){
	ll a, b; cin >> a >> b;
	ll g = gcd(a, b);
	auto f = factorize(g);
	int ans = f.size() + 1;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if (a<b){
    	System.out.println("a < b");
    }
    else if (a>b){
    	System.out.println("a > b");
    }
    else{
    	System.out.println("a == b");
    }
  }
}


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

using namespace std;

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

  vector<int> m(n);

  m[0] = numeric_limits<int>::max();

  for(int i=1; i<n; i++) {
    if (R[i-1] < m[i-1]) m[i] = R[i-1];
    else m[i] = m[i-1];
  }

  int ans = numeric_limits<int>::min();
  for(int i=0; i<n; i++) {
    int profit = R[i] - m[i];
    if (profit > ans) {
      ans = profit;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 4404
t = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cycle = t[0] * (a[0] - b[0]) + t[1] * (a[1] - b[1])

if(cycle == 0):
    print('infinity')
    exit()

after_t1 = t[0] * (a[0] - b[0])

if(cycle * after_t1 > 0):
    print(0)
    exit()

after_t1 = abs(after_t1)
cycle = abs(cycle)

ans = 1 + 2 * (after_t1//cycle) - (after_t1 % cycle == 0) * 1

print(ans)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define inf 1000000005
#define mod 998244353
#define put putchar('\n')
#define F(i,a,b) for (int i=a;i<=b;i++)
#define D(i,a,b) for (int i=a;i>=b;i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define M 10000005
#define pa pair <int,int>
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void wr(ll x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(ll x){wr(x);put;}inline void wri(ll x){wr(x);putchar(' ');}
inline void wrn(ll x,ll y){wri(x);wrn(y);}
int n,m,l,r,p[N];
bool pd(int a,int b,int c){return (p[a]>=c&&p[b]>=c);}
bool pd2(int a,int b,int c){return (p[a]<c&&p[b]<c);}
bool check(int x){
	F(i,0,n-1){
		if (pd(n+i,n+i+1,x)||pd(n-i,n-i-1,x)) return 1;
		if ((pd2(n+i,n+i+1,x))||(pd2(n-i,n-i-1,x))) return 0;
	}
	return (p[1]>=x);
}
signed main(){
	n=read();
	F(i,1,n*2-1) p[i]=read();
	l=1;r=n*2-1;
	while (l<r){
		int mid=(l+r+1)>>1;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	wrn(l);
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
      	int b = sc.nextInt();
      	int c = sc.nextInt();
		// 出力
      if(a<=13 && b<=13 && c<=13){
      	if(a+b+c>=22){
			System.out.println("bust");
     	 }else if(a+b+c<=21){
       		System.out.println("win");
      	}
      }else{
        System.out.println("13以下を入力してください。");
      }
	}
}

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

int main(){

int a;
int b;

cin >> a >> b; 

cout << "a " ;

if(a>b){
cout << ">";
}
else if(a==b){
cout << "==";
}
else if(a<b){
cout <<  "<";
}
cout << " b" << endl;
}

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

int main() {
	string w;
  	cin >> w;
  	int len = w.size();
  
  	vector<int> ans(26,0);
  
  	for(int i = 0; i < len; i++) {
    	int alphaNum = w.at(i) - 97;
      	ans.at(alphaNum)++;
    }
  
  	string answer = "Yes";
  
  	for(int i = 0; i < 26; i++) {
    	if(ans.at(i) % 2 != 0) answer = "No";
    }
  
  	cout << answer << endl;
  
  	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}

int main()
{
	int ans=0;
	rep(i,0,4)ans+=(getchar()=='+')?1:-1;
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
g = [[] for i in range(n)]
edges = []
res = [defaultdict(int) for i in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    edges.append([a,b])
def dfs(e,prev_edge=-1,prev_color=-1):
    cnt = 1
    for ne in g[e]:
        if res[e][ne] or ne == prev_edge:
            continue
        if cnt == prev_color:
            cnt += 1
        res[e][ne] = cnt
        res[ne][e] = cnt
        dfs(ne,e,cnt)
        cnt += 1
dfs(0)
m = 0
for eee in g:
    m = max(m, len(eee))
print(m)
for a,b in edges:
    print(res[a][b])


Measured memory_bytes: 103272
/***********************
*  Author: xuziyuan    * 
***********************/
 
#include <bits/stdc++.h>
 
#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))
 
using namespace std;
 
const LL MOD=1e9+7;
 
int n,m,a[20],now=0;
string s[10010][2],ret,ans="",dp[10010];//dp[火柴数]=串 
int num[]={0,2,5,5,4,5,6,3,7,6};
 
inline string ts(int c)
{
	ret="";
	ret.pb(c+'0');
	return ret;
}
 
inline string MAX(string a,string b)
{
	if(a.size()>b.size()) return a;
	if(b.size()>a.size()) return b;
	return max(a,b);
}
 
int main()
{
	cin>>n>>m;
	rep(i,m) cin>>a[i];
	rep(i,10005) dp[i]="0";
	dp[0]="";
	repn(i,n)
	{
		rep(j,m)
		{
			if(i-num[a[j]]<0||dp[i-num[a[j]]]=="0") continue;
			dp[i]=MAX(dp[i],dp[i-num[a[j]]]+ts(a[j]));
			//cout<<i<<' '<<dp[i]<<' '<<i-num[a[j]]<<' '<<dp[i-num[a[j]]]<<endl;
		}
	}
	cout<<dp[n]<<endl;
	rt0;
}

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

int main(){
    int n, k, q; cin >> n >> k >> q;
    vector<int> P(n,k-q);
    rep(i,q){
        int p; cin >> p; P[p-1]++; 
    } 
    rep(i,n){
        cout << ((P[i] > 0)? "Yes" : "No") << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
N, M = gets.split.map(&:to_i)
edges = Array.new(N){[]}
M.times do
    a, b = gets.split.map(&:to_i)
    edges[a-1].push(b-1)
    edges[b-1].push(a-1)
end

visited = []
nums = []
n1 = 0
n2 = 0
N.times do |i|
    next if visited[i]
    num = 1
    visited[i] = true
    stack = [i]
    while stack.length > 0
        a = stack.pop
        edges[a].each do |b|
            next if visited[b]
            num += 1
            visited[b] = true
            stack.push(b)
        end
    end
    n1 = num if i == 0
    n2 += num if i != 1
end

n1 = [n1, N-n1].min
n2 = [n2, N-n2].min
opt = [n1, n2].min

esum = opt*(opt-1)/2 + (N-opt)*(N-opt-1)/2
puts esum - M

Measured memory_bytes: 13948
N=gets.to_i
as=gets.split.map(&:to_i).sort
max=as.max
min=as.min

if as.size==2
    puts max-min
    puts [max,min].join(" ")
    exit
end

as=as[1..-2]
ans=Array.new
ans_c=max-min
as.each do |e|
    if e<0
        ans_c-=e
        ans << [max,e]
        max=max-e
    elsif e>0
        ans_c+=e
        ans << [min,e]
        min=min-e
    else
        ans << [max,0]
    end
end
ans << [max,min]
puts ans_c
puts ans.map{|e|e.join(" ")}

Measured memory_bytes: 32984
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 62;

int main() {
  int N;
  cin >> N;
  vector<ll> a(N);
  ll sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    sum += a[i];
  }
  ll res = INF;
  ll x = 0;
  for (int i = 0; i < N - 1; i++) {
    x += a[i];
    ll y = sum - x; 
    res = min(res, abs(x - y));
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
int main(){
    int n=0;
    scanf("%d",&n);
    for(int i=1;i<10;i++){
        if(n%i==0&&n/i<10){
        printf("%s","Yes");
        exit(0);
        }
    }
    printf("%s","No");
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()
#define tpl(...) make_tuple(__VA_ARGS__)

typedef long long LL;
typedef pair<int, int> P; typedef pair<P, int> PI; typedef pair<P, P> PP;
typedef vector<int> Array; typedef vector<vector<int> > Array2;
typedef vector<LL> LArray; typedef vector<P> PArray; typedef vector<string> SArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

inline int getInt() { int itiv; return (cin >> itiv, itiv); }
template <typename T> void readAll(vector<T>& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i]; }
template <typename T, typename U> void readAll(vector<pair<T, U> >& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i].first >> vec[i].second; }
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };
inline bool between(int min, int max, int n) { return min <= n && n <= max; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

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

int h, w, n;

int main(void)
{
	ios::sync_with_stdio(false);
	while(cin >> h >> w >> n && n)
	{
		vector<vector<char> > stage(h, vector<char>(w));
		PArray goals(n + 1);
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> stage[i][j];
				if(stage[i][j] == 'S') goals[0] = P(i, j);
				int num = stage[i][j] - '0';
				if(inRange(n + 1, num)) goals[num] = P(i, j);
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			P start = goals[i], goal = goals[i + 1];
			vector<vector<bool> > visited(h, vector<bool>(w));
			queue<PI> que;
			que.push(PI(start, 0));
			while (!que.empty())
			{
				PI pi = que.front(); que.pop();
				if(goal == pi.first)
				{
					ans += pi.second;
					break;
				}
				int r = pi.first.first, c = pi.first.second;
				if(visited[r][c]) continue;
				visited[r][c] = true;

				for (int i = 0; i < 4; i++)
				{
					int nr = r + dr[i], nc = c + dc[i];
					if(!inRange(h, nr) || !inRange(w, nc) || stage[nr][nc] == 'X') continue;
					que.push(PI(P(nr, nc), pi.second + 1));
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	unordered_map<string,int>mp;
	string s;
	int maxi=0;
	while(n--)
	{
		cin>>s;
		mp[s]++;
		if(mp[s]>maxi)
		maxi=mp[s];
	}
	vector<string>v;
	for(auto p:mp)
	{
		if(p.second==maxi)
		v.push_back(p.first);
	}
	sort(v.begin(),v.end());
	for(string s:v)
	cout<<s<<"\n";

	
	return 0;
}

Measured memory_bytes: 26692
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	int N; string S; cin>>N>>S;
	int ans=0;
	for(int i=0;i<N;i++){
		map<char,int> se1,se2;
		for(int j=0;j<N;j++){
			if(j<i){
				se1[S[j]]=1;
			}else{
				se2[S[j]]=1;
			}
		}
		int tmp=0;
		for(auto p : se1){
			tmp+=min(p.second,se2[p.first]);
		}
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << 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...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 1e5 + 10;
int f[N], c[N];

int find(int x) {
  if (f[x] != f[f[x]]) f[x] = find(f[x]);
  return f[x];
}

struct Node {
  int x, y;
  int idx;
};

set<int> X[N], Y[N];

int main() {
  int n;
  scanf("%d", &n);
  vector<Node> a(n);
  for (int i = 0; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i] = Node{x, y, i};
    f[i] = i;
    c[i] = 1;
  }
  sort(a.begin(), a.end(),
       [](const Node& u, const Node& v) {
         return u.x < v.x || (u.x == v.x && u.y < v.y);
       });
  for (int i = 0, j; i < n; i = j) {
    for (j = i + 1; j < n && a[j].x == a[i].x; ++j) {
      int x = a[j - 1].idx, y = a[j].idx;
      int rx = find(x), ry = find(y);
      if (rx != ry) {
        f[ry] = rx;
        c[rx] += c[ry];
      }
    }
  }
  sort(a.begin(), a.end(),
       [](const Node& u, const Node& v) {
         return u.y < v.y || (u.y == v.y && u.x < v.x);
       });
  for (int i = 0, j; i < n; i = j) {
    for (j = i + 1; j < n && a[j].y == a[i].y; ++j) {
      int x = a[j - 1].idx, y = a[j].idx;
      int rx = find(x), ry = find(y);
      if (rx != ry) {
        f[ry] = rx;
        c[rx] += c[ry];
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    int j = a[i].idx;
    int k = find(j);
    X[k].insert(a[i].x);
    Y[k].insert(a[i].y);
  }
  int64 ret = 0;
  for (int i = 0; i < n; ++i) {
    if (find(i) != i) continue;
    ret += (int64)X[i].size() * Y[i].size() - c[i];
  }
  printf("%lld\n", ret);
  return 0;
}


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

public class Main{
  static final long MOD = 1_000_000_007;
  static int n;

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

    n = sc.nextInt();

    boolean[] prime = new boolean[n + 1];
    int count = 0;
    Arrays.fill(prime, true);
    prime[1] = false;
    for(int i = 2; i <= n; i++){
      if(prime[i]){
        for(int j = 2; j * i <= n; j++){
          prime[j * i] = false;
        }
        ++count;
      }
    }

    int[] primes = new int[count];
    int sp = 0;
    for(int i = 2; i <= n; i++){
      if(prime[i]){
        primes[sp++] = i;
      }
    }

    int[] expo = new int[n + 1];
    for(int i = 1; i <= n; i++){
      int m = i;
      for(int j = 0; j < primes.length; j++){
        int p = primes[j];
        while(p <= m && m % p == 0){
          m /= p;
          ++expo[p];
        }
      }
    }

    long ans = 1;
    for(int i = 2; i <= n; i++){
      ans = (ans * (expo[i] + 1)) % MOD;
    }

    System.out.println(ans);
  }
}


Measured memory_bytes: 22740
N,K = map(int,input().split())
S = input()

T = []
for i in range(N):
  if i == 0:
    bit = S[i]
    cnt = 1
  else:
    if S[i] != S[i-1]:
      T.append([int(bit), cnt])
      bit = S[i]
      cnt = 1
    else:
      cnt += 1
T.append([int(bit), cnt])
N = len(T)
#print(T)

L,R = 0,0
rest = 1 if T[0][0] == 0 else 0
suml = T[0][1]
answer = 0

while 1:
  #print(L,R, "rest:", rest, "sum:", suml)
  if rest <= K:
    answer = max(answer, suml)
  if rest <= K:
    if R == N-1:
      break
    R += 1
    if T[R][0] == 0:
      rest += 1
    suml += T[R][1]
  else:
    L += 1
    if T[L-1][0] == 0:
      rest -= 1
    suml -= T[L-1][1]
  if rest <= K:
    answer = max(answer, suml)
print(answer)

Measured memory_bytes: 53148
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define pb push_back
#define mp make_pair
#define M 1000000007
#define F first
#define S second
ll power( ll b, ll e)
{
    if(e==0) return 1;
    if(e&1) return b*power(b*b,e/2);
    return power(b*b,e/2);
}
ll power(ll b,ll e,ll m)
{
    if(e==0) return 1;
    if(e&1) return b*power(b*b%m,e/2,m)%m;
    return power(b*b%m,e/2,m);
}

// #define ncr_nikalo
bool sortinrev(const pair<int,int> &a,  
               const pair<int,int> &b) 
{ 
       return (a.first > b.first); 
}
ll modinv(ll a,ll m)
{
    return power(a,m-2,m);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    ll int t=1;
    //cin>>t;
    #ifdef ncr_nikalo
        initialvalues();
    #endif
        
    for(ll int g=0;g<t;g++)
    {
    	ll int n,ans;
    	cin>>n;
    	ans=n%1000;
    	if(ans==0)
    		cout<<0;
    	else
    		cout<<1000-ans;

    }
    return 0;
}

Measured memory_bytes: 3640
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

char dn[1400000], * di = dn;
int keta1 = 1, keta2;
char C1[10] = { '1', '0', '0', '0', '0', '0' };
char C2[10] = { '0', '0', '0', '0', '0', '0' };

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


	int N, M;
	scanf("%d %d", &N, &M);

	if (N % 2) {
		int n = N - 1;
		keta2 = 0;
		while (n) {
			*(C2 + keta2) = '0' + n % 10;
			n /= 10;
			keta2++;
		}

		rep1(i, M) {
			for (int i = keta1 - 1; i >= 0; i--)* di++ = (*(C1 + i));
			*di++ = ' ';
			for (int i = keta2 - 1; i >= 0; i--)* di++ = (*(C2 + i));
			*di++ = '\n';

			C1[0]++;
			int tmp = 0;
			while (C1[tmp] > '9') {
				C1[tmp++] -= 10;
				C1[tmp]++;
				if (keta1 <= tmp) keta1 = tmp + 1;
			}
			C2[0]--;
			tmp = 0;
			while (C2[tmp] < '0') {
				C2[tmp++] += 10;
				C2[tmp]--;
				if (C2[keta2 - 1] == '0') keta2--;
			}
		}
	}
	else {
		int n = N;
		keta2 = 0;
		while (n) {
			*(C2 + keta2) = '0' + n % 10;
			n /= 10;
			keta2++;
		}
		rep1(i, (M + 1) / 2) {
			for (int i = keta1 - 1; i >= 0; i--)* di++ = (*(C1 + i));
			*di++ = ' ';
			for (int i = keta2 - 1; i >= 0; i--)* di++ = (*(C2 + i));
			*di++ = '\n';

			C1[0]++;
			int tmp = 0;
			while (C1[tmp] > '9') {
				C1[tmp++] -= 10;
				C1[tmp]++;
				if (keta1 <= tmp) keta1 = tmp + 1;
			}
			C2[0]--;
			tmp = 0;
			while (C2[tmp] < '0') {
				C2[tmp++] += 10;
				C2[tmp]--;
				if (C2[keta2 - 1] == '0') keta2--;
			}
		}
		C2[0]--;
		int tmp = 0;
		while (C2[tmp] < '0') {
			C2[tmp++] += 10;
			C2[tmp]--;
			if (C2[keta2 - 1] == '0') keta2--;
		}
		for (int i = (M + 1) / 2 + 1; i <= M; i++) {
			for (int i = keta1 - 1; i >= 0; i--)* di++ = (*(C1 + i));
			*di++ = ' ';
			for (int i = keta2 - 1; i >= 0; i--)* di++ = (*(C2 + i));
			*di++ = '\n';

			C1[0]++;
			int tmp = 0;
			while (C1[tmp] > '9') {
				C1[tmp++] -= 10;
				C1[tmp]++;
				if (keta1 <= tmp) keta1 = tmp + 1;
			}
			C2[0]--;
			tmp = 0;
			while (C2[tmp] < '0') {
				C2[tmp++] += 10;
				C2[tmp]--;
				if (C2[keta2 - 1] == '0') keta2--;
			}
		}
	}

	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

Measured memory_bytes: 2780
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

#define ll long long
const long long llINF = 1LL << 60;
const int iINF = 1LL << 20;
template<class T> inline bool chmin(T& a, T b) { if (b < a) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void execute();
int main() 
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);// cin と scanfの併用禁止
    cout << fixed << setprecision(15);
    execute();
    return 0;
}


void execute()
{
    string s, t;
    cin >> s;
    cin >> t;

	bool b=(t.substr(0, s.length()) == s && s.length()+1 == t.length());
    cout << (b ? "Yes" : "No") << endl; 
}


Measured memory_bytes: 3652
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

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

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

// MOD :
var MOD = 1000000007

// Fac :
var Fac [200001]int

// IFac :
var IFac [200001]int

// 乗数計算（MOD)
func mpow(x, n int) int {
	ans := 1
	for n != 0 {
		if n&1 == 1 {
			ans = ans * x % MOD
		}
		x = x * x % MOD
		n = n >> 1
	}
	return ans
}

// コンビネーション計算
func comb(a, b int) int {
	if (a == 0) && (b == 0) {
		return 1
	}
	if (a < b) || (a < 0) {
		return 0
	}
	tmp := IFac[a-b] * IFac[b] % MOD
	return tmp * Fac[a] % MOD
}

func initPow() {
	Fac[0] = 1
	IFac[0] = 1
	for i := 0; i < 200000; i++ {
		Fac[i+1] = Fac[i] * (i + 1) % MOD            // n!(mod M)
		IFac[i+1] = IFac[i] * mpow(i+1, MOD-2) % MOD // k!^{M-2} (mod M) ←累乗にmpowを採用
	}
}

func comb2(a, b int) int {
	if (a == 0) && (b == 0) {
		return 1
	}
	if (a < b) || (a < 0) {
		return 0
	}

	x := 1
	for i := a; i > a-b; i-- {
		x = (x * i) % MOD
	}
	tmp := x * IFac[b] % MOD
	return tmp
}

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

	N, a, b := getInt(), getInt(), getInt()

	ans := mpow(2, N) - 1

	x := comb2(N, a)
	y := comb2(N, b)

	ans = (ans - x) % MOD
	if ans < 0 {
		ans += MOD
	}
	ans = (ans - y) % MOD
	if ans < 0 {
		ans += MOD
	}

	out(ans)
}


Measured memory_bytes: 3712
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

alias C = Tuple!(int, "i", int, "p", int, "y");
alias N = Tuple!(int , "i", int, "p", int, "c");

void main()
{
    auto M = readln.split.to!(int[])[1];
    C[] cs;
    foreach (i; 0..M) {
        auto py = readln.split.to!(int[]);
        cs ~= C(i, py[0], py[1]);
    }
    sort!"a.p == b.p ? a.y < b.y : a.p < b.p"(cs);
    N[] ns;
    foreach (ccs; cs.chunkBy!"a.p") {
        int i;
        foreach (c; ccs[1]) {
            ns ~= N(c.i, c.p, ++i);
        }
    }
    sort!"a.i < b.i"(ns);
    foreach (n; ns) {
        writefln("%06d%06d", n.p, n.c);
    }
}

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

int main() {
  string S; cin >> S;
  int L = S.size();
  if (L % 2 != 0) cout << "No" << endl;
  else {
    bool ans = true;
    for (int i = 0; i < L-1; i += 2) {
      string t = S.substr(i, 2);
      if (t != "hi") ans = false;
    }
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

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

using namespace std;

int main () {

  int A, B, C, D, E, ans = 0, m = INT_MIN, index_max_r;
  cin >> A >> B >> C >> D >> E;

  int arr[] = { A, B, C, D, E };

  for (int i = 0; i < 5; i++) {
    if (arr[i] % 10 != 0 && (10 - (arr[i] % 10)) >= m) {
      m = 10 - (arr[i] % 10);
      index_max_r = i;
    }
  }

  for (int i = 0; i < 5; i++) {
    if (i != index_max_r) {
      int r = (ans % 10) == 0 ? 0 : 10 - (ans % 10);
      ans += r;
      ans += arr[i];
    }
  }

  int r = ans%10 == 0 ? 0 : 10 - (ans % 10);
  ans += r;
  ans += arr[index_max_r];

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
g_1 = [1,3,5,7,8,10,12]
g_2 = [4,6,9,11]
g_3 = [2]
x,y = map(int,input().split())
if x in g_1 and y in g_1:
    print("Yes")
elif x in g_2 and y in g_2:
    print("Yes")
elif x in g_3 and y in g_3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i) 
#endif

#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()) , v.end());

using namespace std;
typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
const int EPS = 1e-9;
const int MOD = 1e9+7;

ll mod_pow(ll x, ll n, ll mod){
  if(n == 0)return 1;
  ll res;
  if(mod == -1)res = mod_pow(x * x,n/2,mod);
  else res = mod_pow(x * x % mod,n/2,mod);
  if(n%2 == 1 && mod != -1)res = res * x % mod;//(nが2の累乗ではない時にもう一度処理を行う)
  else if(n%2 == 1)res = res * x;
  return res;
}
int main (){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> A(n),B(n),C(n);
  REP(i,n){
    cin >> A[i];
  }
  REP(i,n){
    cin >> B[i];
  }
  REP(i,n){
    cin >> C[i];
  }
  sort(ALL(A));
  sort(ALL(B));
  sort(ALL(C));
  ll ans = 0;
  REP(i,n){
    auto posa = lower_bound(ALL(A),B[i]);
    auto posc = upper_bound(ALL(C),B[i]);
    DUMP(B[i]);
    DUMP(distance(A.begin(),posa));
    DUMP(*posa);
    DUMP(distance(posc,C.end()));
    DUMP(*posc);
    ans += distance(A.begin(),posa) * distance(posc,C.end());
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 1408
#include <iostream>

using namespace std;
int a,b,c,na,nb,nc,i;
int main()
{
    cin>>a>>b>>c;
    na=a,nb=b,nc=c;
    for(i=0;i<=32;i++)
    {
        a=na,b=nb,c=nc;
        if(((a|b|c)&1))
        {
            cout<<i;
            return 0;
        }
        na=(b+c)/2;nb=(a+c)/2;nc=(a+b)/2;
    }
    cout<<"-1";
    return 0;
}


Measured memory_bytes: 256
from sys import stdin
from itertools import accumulate
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
L = [0]+A
L = list(accumulate(L)) 
ans = 0
d = {}
for i in range(N+1):
    ans += d.get(L[i], 0)
    d[L[i]] = 1 + d.get(L[i], 0)
print(ans)

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

typedef long long int lli;
#define int lli
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<lli> vli;
typedef vector<pii> vii;

const int MOD	= 1e9 + 7;
const double PI = acos(-1.0);

#define fastio			ios_base::sync_with_stdio(0);cin.tie(0)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(c) (c).begin(),(c).end()
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define endl "\n"
#define error(x) cerr << #x << " = " << (x) << endl
#define errorp(p) cerr << #p << " = " << (p.first) << ", " << (p.second) << endl

template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template <typename T> T lcm(T a, T b){return (a*b)/gcd(a,b); }

const int mx = 1e18;

void solve(){
    int n;
    cin >> n;
    vi arr(n);
    int ans = 1;
    rep(i, n){
         cin >> arr[i];
    }
    sort(all(arr));
    if(arr[0] == 0){
        ans = 0;
    }else{
        rep(i, n){
            if(mx / ans < arr[i]){
                ans = -1;
                break;
            }
            ans *= arr[i];
            
        }
    }
    cout << ans << endl;
}

signed main(){
    #ifdef DEBUG
		freopen("test", "r", stdin);
	#endif
    fastio;
    
    solve();

    return 0;
}


Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.begin(), a.end(), greater<int>()
#define ROT(a) a.begin(), a.begin() + 1, a.end()
#define RROT(a) a.begin(), a.end() - 1, a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9 + 7;
const int MAX = 10000000;
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b)
{
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
T gcd(T a, T b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
//cout << 'H' << endl;
/*--------------------------------------------*/

int main()
{
    //cout << fixed << setprecision(10)
    cin.tie(0);
    ios::sync_with_stdio(false);

    int H, W;
    cin >> H >> W;

    int num4 = (H / 2) * (W / 2);
    int num1 = (H % 2) * (W % 2);
    int num2 = (H * W - 4 * num4 - num1) / 2;

    map<char, int> mp;

    rep(i, H * W)
    {
        char c;
        cin >> c;

        mp[c]++;
    }
    //cout << num4 << ' ' << num2 << ' ' << num1 << endl;

    for (auto i : mp) {
        int v = i.second;
        while (v >= 4 && num4 > 0) {
            v -= 4;
            --num4;
        }
        while (v >= 2 && num2 > 0) {
            v -= 2;
            --num2;
        }
        if (v == 1 && num1) {
            --v;
            --num1;
        }
    }

    cout << ((num4 || num2 || num1) ? "No" : "Yes") << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        String N = sc.next();
        char[] n = N.toCharArray();
        int nine = 0;
        for(int i = 0; i < N.length(); i++){
          nine += Character.getNumericValue(n[i]);
        }
        String ans = "Yes";
      if(nine % 9 != 0 ) ans = "No";
      System.out.println(ans);
    } 
}

Measured memory_bytes: 31692
import java.util.*;
import java.io.*;
import java.util.function.*;

class Main {
    static Scanner scanner = new Scanner();
    static int mod = 1000000007;
    static long inf = 0x7ffffffffffffffL;

    void solve() {
        int n = scanner.nextInt();
        long[] a = new long[n + 1];
        for (int i = 0; i < n; i++) {
            a[i + 1] = a[i] + scanner.nextInt();
        }
        long min = inf;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, Math.abs(a[n] - a[i] - a[i]));
        }
        System.out.println(min);
    }

    public static void main(String[]$) throws Exception {
        new Main().solve();
        System.out.flush();
    }
}

class System {
    static PrintWriter out = new PrintWriter(java.lang.System.out);

    static void exit() {
        java.lang.System.exit(0);
    }
}

class Scanner {
    private BufferedReader reader = new BufferedReader(new InputStreamReader(java.lang.System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

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

    long nextLong() {
        return Long.parseLong(next());
    }

    char[][] nextCharArray(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }
}


Measured memory_bytes: 58508
H, W = map(int, input().split())
S = [input() for _ in range(H)]
Ans = [[[-1, -1]for __ in range(W)] for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            if Ans[i-1][j][0] != -1:
                Ans[i][j][0] = Ans[i-1][j][0]
            else:
                num0 = 0
                while True:
                    num0 += 1
                    if i + num0 >= H:
                        break
                    elif S[i+num0][j] == '#':
                        break
                Ans[i][j][0] = num0

            if Ans[i][j-1][1] != -1:
                Ans[i][j][1] = Ans[i][j-1][1]
            else:
                num1 = 0
                while True:
                    num1 += 1
                    if j + num1 >= W:
                        break
                    elif S[i][j+num1] == '#':
                        break
                Ans[i][j][1] = num1

        ans = max(ans, sum(Ans[i][j]))
print(ans-1)


Measured memory_bytes: 398180
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  vi c(9);
  rep(i, 9) cin >> c[i];
  bool ans = false;
  rep(i,c[0]+1){
    rep(j,c[4]+1){
      rep(k,c[8]+1){
        if(c[1]==i+c[4]-j&&c[2]==i+c[8]-k&&c[3]==j+c[0]-i&&c[5]==j+c[8]-k&&c[6]==k+c[0]-i&&c[7]==k+c[4]-j){
          ans = true;
        }
      }
    }
  }
  if(ans)print("Yes");
  else print("No");
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
c = [na() for _ in range(10)]
A = [na() for _ in range(H)]
adj = [[] for _ in range(10)]

c = np.array(c)
d = shortest_path(c)
ans = 0
for y in range(H):
    for x in range(W):
        if A[y][x] != -1:
            #print(ans)
            ans += d[A[y][x]][1]
print(int(ans))



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

using namespace std;

bool possible(long long longestLog, const vector<long long>& A, long long K) {
    long long N = A.size();
    long long numOfLongestLogs = 0;
    for (long long i = 0; i < N; ++i) {
        numOfLongestLogs += A[i] / longestLog;
        if (A[i] % longestLog == 0) {
            --numOfLongestLogs;
        }
    }
    return (numOfLongestLogs <= K);
}

void Main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N, 0LL);
    for (long long i = 0; i < N; ++i) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater<long long>());

    long long ub = A.front();
    long long lb = 0LL;
    while (ub - lb > 1LL) {
        long long mid = (ub + lb) / 2LL;
        if (possible(mid, A, K)) {
            ub = mid;
        }
        else {
            lb = mid;
        }
    }
    //bool test = possible(lb, A, K);
    cout << "";
    //if (test) {
    //    cout << "";
    //}
    cout << ub << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int W;
    int a, b;
    cin >> W;
    cin >> a >> b;
    if(a <= b) {
        cout << max(0, b - a - W) << endl;
    } else {
        cout << max(0, a - b - W) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
// In the name of Allah. Ya ali!
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 2e5+100;
const ll MOD = 1e9+7;
using namespace std;

int rm[MAX_N][20];
int a[MAX_N];

ll gt(int l,int r)
{
    ll lg = log2(r-l+1);
    int x = r - (1<<lg)+1;
    return min(rm[l][lg],rm[x][lg]);
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0;i<n;++i)
        cin >> a[i],rm[i][0] = a[i];
    for(int i = 1;i<20;++i)
        for(int j = 0;j<(n-(1<<i)+1);++j)
            rm[j][i] = min(rm[j][i-1],rm[j+(1<<(i-1))][i-1]);
    ll ans = 0;
    for(int i = 0;i<n;++i)
    {
        ll l1 = i;
        ll l2 = i;
        if (i>0)
        {
            if (a[i-1]>a[i])
            {
                if (gt(0,i-1)>a[i])
                    l1 = 0;
                else
                {
                    int r1 = 0;
                    while(l1-r1>1)
                    {
                        int mid = (l1+r1)/2;
                        if (gt(mid,i-1)>a[i])
                            l1 = mid;
                        else
                            r1 = mid;
                    }
                }
            }
        }
        if (i<n-1)
        {
            if (a[i+1]>=a[i])
            {
                if (gt(i+1,n-1)>=a[i])
                    l2 = n-1;
                else
                {
                    int r2 = n-1;
                    while(r2-l2>1)
                    {
                        int mid = (l2+r2)/2;
                        if (gt(i+1,mid)>=a[i])
                            l2 = mid;
                        else
                            r2 = mid;
                    }
                }
            }
        }
        ans+=(l2-i+1)*(i-l1+1)*a[i];
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 16640
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <cstring>

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using PP = pair<ll, pair<ll,ll>>;
#define rep(i,n) for (ll i = 0; i < (n); ++i)

ll n, y;

int main() {
    cin >> n >> y;
    rep(i,n+1){
        rep(j,n-i+1){
            ll k = n-(i+j);
            ll m = i*10000 + j*5000 + k*1000;
            if (m == y){
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#include<string.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define see(x) cout<<#x<<" : "<<x<<endl;
#define ya cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
typedef long long ll;
using namespace std;
bool f=1;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    //freopen("test.txt","r",stdin);
    ll n,a,i,j,ans=0,sum=0;
    cin>>n;
vector<ll>v(n+1);
    for(i=0;i<=n;i++)
    {
        cin>>v[i];
        sum+=v[i];
    }
    if(n==0 && v[0]==1)
    {
        cout<<1<<endl;
        return 0;
    }
    if(v[0]>0 || v[n]==0)
    {
        cout<<-1<<endl;
        return 0;
    }
    ll ck=1;
    ans=0;
    for(i=0;i<=n;i++)
    {
        if(ck<v[i])
        {
            f=0;
            break;
        }
        sum-=v[i];
        ans+=ck;
        //see(ck)
        //see(sum)
        ck=min(sum,ck*2-v[i]*2);
    }
    if(f)
    cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 3988
#include<iostream>
#include<set>
#include<cmath>
using namespace std;
#define ll long long
int main(void)
{
    ll n, p,i = 2, x = 1;
    multiset<ll> v;
    cin >> n >> p;
    ll k = p;
    while(k > 1){
        if(k % i == 0){
            v.insert(i);
            k /= i;
        }
        else i += 1;
        if(i > sqrt(k)){
            v.insert(k);
            break;
        }
    }
    auto itr = v.begin();
    while(itr != v.end()){
        if(v.count(*itr) >= n) x *= pow(*itr, (v.count(*itr) / n));
        itr = v.upper_bound(*itr);
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256