akhauriyash/Code-Regression huggingface dataset:
def main():
    from collections import namedtuple

    Ratio = namedtuple('Ratio', 'gold, silver copper')

    def trade(n, Rfrm, Rto):
        Df = Ratio(*(t - f for f, t in zip(Rfrm, Rto)))
        dp = [n] * (n + 1)
        for acorn in range(1, n + 1):
            dp[acorn] = max(
                dp[acorn],
                0 if acorn < Rfrm.gold else dp[acorn - Rfrm.gold] + Df.gold,
                0 if acorn < Rfrm.silver else dp[acorn - Rfrm.silver] + Df.silver,
                0 if acorn < Rfrm.copper else dp[acorn - Rfrm.copper] + Df.copper
            )
        return dp[n]

    n = int(input())
    Ra = Ratio(*map(int, input().split()))
    Rb = Ratio(*map(int, input().split()))

    ret = trade(n=n, Rfrm=Ra, Rto=Rb)
    ret = trade(n=ret, Rfrm=Rb, Rto=Ra)
    print(ret)


if __name__ == '__main__':
    main()


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

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()

const int mod = 1e9+7;
const int inf = 2e18;

int32_t main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin>>n;
	set<string> st;

	string s;

	while(n--)
	{
		cin>>s;
		st.insert(s);

	}

	cout<<st.size()<<'\n';
	return 0;
}	

Measured memory_bytes: 19288
//quming
#include<bits/stdc++.h>
#define R register
#define fi first
#define se second
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=2e5+5;
typedef pair<int,int> pi;
int n,res,st[N],ins[N],top;pi a[N],Pre[N],suf[N];
inline pi operator +(const pi &a,const pi &b){return pi(max(a.fi,b.fi),min(a.se,b.se));}
inline int Len(const pi &b){return max(b.se-b.fi+1,0);}
int main(){
//	freopen("testdata.in","r",stdin);
    scanf("%d",&n);
    fp(i,1,n)scanf("%d%d",&a[i].fi,&a[i].se);
    sort(a+1,a+1+n,[](const pi &a,const pi &b){
        return a.fi==b.fi?a.se>b.se:a.fi<b.fi;
    });
    fp(i,1,n){
        while(top&&a[st[top]].se>=a[i].se)--top;
        st[++top]=i;
    }
    fp(i,1,top)ins[st[i]]=1;
    Pre[0]=suf[top+1]=pi(0,1e9);
    fp(i,1,top)Pre[i]=Pre[i-1]+a[st[i]];
	fd(i,top,1)suf[i]=suf[i+1]+a[st[i]];
    fp(i,1,top-1)cmax(res,Len(Pre[i])+Len(suf[i+1]));
    fp(i,1,n)if(!ins[i])cmax(res,Len(Pre[top])+Len(a[i]));
    if(top>1)fp(i,1,top)cmax(res,Len(Pre[i-1]+suf[i+1])+Len(a[st[i]]));
    printf("%d\n",res);
    return 0;
}

Measured memory_bytes: 5632
#include <iostream>

using namespace std;

int main(){
  int n; cin >> n;
  //adjacent matrix expression
  int a[n+1][n+1];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      a[i][j]=0;
    }
  }
  for(int i=0;i<n;i++){
    int u; cin >> u;
    int k; cin >> k;
    for(int i=0;i<k;i++){
      int v; cin >> v;
      a[u][v]=1;
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n-1;j++){
      cout << a[i][j] << " ";
    }
    cout << a[i][n] << endl;
  }
}

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

using namespace std;

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

	vector<vector<int32_t>> A(3, vector<int32_t>(3));
	vector<vector<bool>> M(3, vector<bool>(3, false));

	for(int32_t i = 0; i < 3; ++i)
	{
		for(int32_t j = 0; j < 3; ++j)
		{
			cin >> A[i][j];
		}
	}

	int32_t N;
	cin >> N;

	vector<int32_t> B(N);
	for(auto& b : B)
	{
		cin >> b;
	}

	for(const auto& b : B)
	{
		for(int32_t i = 0; i < 3; ++i)
		{
			for(int32_t j = 0; j < 3; ++j)
			{
				if(A[i][j] == b)
				{
					M[i][j] = true;
				}
			}
		}
	}

	bool status = false;

	if(M[0][0] and M[0][1] and M[0][2])		status = true;
	else if(M[1][0] and M[1][1] and M[1][2])status = true;
	else if(M[2][0] and M[2][1] and M[2][2])status = true;
	else if(M[0][0] and M[1][0] and M[2][0])status = true;
	else if(M[0][1] and M[1][1] and M[2][1])status = true;
	else if(M[0][2] and M[1][2] and M[2][2])status = true;
	else if(M[0][0] and M[1][1] and M[2][2])status = true;
	else if(M[0][2] and M[1][1] and M[2][0])status = true;

	cout << (status ? "Yes" : "No") << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

#define INF 1e9


// UnionFind??¨ ??????????????????
class UnionFindTree{
private:
  int m_size, unite_count;
  vector<int> parent;
  vector<int> rank;
  int find(int a);
public:
  void init(int size);
  void unite(int a, int b);
  bool same(int a, int b);
  bool isConnected(void);
};

// UF??¨????????????
void UnionFindTree::init(int size){
  m_size = size;
  unite_count = 0;
  parent.clear();
  rank.clear();
  for(int i = 0; i < size; i++){
    parent.push_back(i);
    rank.push_back(0);
  }
  return;
}

// UF??¨?????????????????????
int UnionFindTree::find(int a){
  if(parent[a] != a){ parent[a] = find(parent[a]); }
  return parent[a];
}

// UF??¨??§???????????£?????????
void UnionFindTree::unite(int a, int b){
  int x = find(a);
  int y = find(b);
  // ?????§???????????£???????????????????????????
  if(x == y){ return; }

  unite_count++;
  if(rank[x] < rank[y]){ parent[x] = y; }
  else{
    parent[y] = x;
    if(rank[x] == rank[y]){ rank[x]++; }
  }
  return;
}

// UF??¨??§???????????????????????????????????????
bool UnionFindTree::same(int a, int b){
  return find(a) == find(b);
}

// UF??¨??§?????????????????????????????¨???????????????????????????
bool UnionFindTree::isConnected(void){
  return unite_count == m_size - 1;
}

int kruskal(int v, vector<pair<int, pair<int, int> > > sorted_edgelist){
  int sum = 0;
  UnionFindTree uf;
  uf.init(v);

  for(int i = 0; i < (int)sorted_edgelist.size() && !uf.isConnected(); i++){
    int cost = sorted_edgelist[i].first;
    int a = sorted_edgelist[i].second.first;
    int b = sorted_edgelist[i].second.second;

    if(!uf.same(a, b)){
      sum += cost;
      uf.unite(a, b);
    }
  }
  
  return sum;
}


int main(void){
  while(true){
    int n, m;
    cin >> n >> m;
    if(n == 0 && m == 0){ break; }
    
    int a, b, cost;
    vector<pair<int, pair<int, int> > > edgelist(n);
    for(int i = 0; i < m; i++){
      cin >> a >> b >> cost;
      edgelist.push_back(make_pair(cost, make_pair(a, b)));
    }
    sort(edgelist.begin(), edgelist.end());
    
    cout << kruskal(n, edgelist) << endl;
  }

  return 0;
}

Measured memory_bytes: 3032
///Bismillahir Rahmanir Rahim
#define ll long long
#define pii pair<ll,ll>
#define m_p  make_pair
#define ull unsigned long long
#define spd  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
ll ans[N],cum_sum[N];
int main()
{
    spd;

    ll n,i,j,k,cnt=0;

    cin>>n;
    vector<ll>v(n);

    for(i=0;i<n;i++)
    {
        cin>>v[i];
    }

    sort(v.begin(),v.end());

    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            for(k=j+1;k<n;k++)
            {
                if(v[i]+v[j]>v[k]&&v[i]+v[k]>v[j]&&v[j]+v[k]>v[i]&&v[i]!=v[j]&&v[j]!=v[k]&&v[i]!=v[k])
                {
                    cnt++;
                }
            }
        }
    }

    cout<<cnt<<endl;
}


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

int main()
{
    int X;
    scanf("%d", &X);
    if(X==3)
    {
        printf("YES");
    }
    else if (X==5)
    {
        printf("YES");
    }
    else if (X==7)
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
    return 0;
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int N, K; cin >> N >> K;
    vi h(N); REP(i, N) cin >> h[i];
    sort(ALL(h));
    int ans = INF;
    for(int i = 0; i+K-1 < N; i++)
    {
        int m = h[i+K-1] - h[i];
        ans = min(ans, m);
    }
    cout << ans << endl;
}
    
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
  cin >> n;
  int W;
    cin >>W;
  long long int ww[n],v[n];
  for (int i=0;i<n;i++){
  	cin >> ww[i] >> v[i];
  }
  long long int dp[n+1][W+1];
  for (int i=0;i<=W;i++) dp[0][i]=0;
  for (int i=0;i<n;i++){
    for (int w=0;w<=W;w++){
    	if (w>=ww[i])dp[i+1][w]=max(dp[i][w-ww[i]]+v[i],dp[i][w]);
    	else dp[i+1][w]=dp[i][w];
    }
  }
  cout << dp[n][W] <<endl;
}

Measured memory_bytes: 79104
H, W = gets.split.map(&:to_i)
board = H.times.map { gets.chomp.chars }
is_ok = H.times.all? do |i|
  W.times.all? do |j|
    cell = board[i][j]
    next true if cell == '.'
    next true if i > 0 && board[i - 1][j] == '#'
    next true if j < W - 1 && board[i][j + 1] == '#'
    next true if i < H - 1 && board[i + 1][j] == '#'
    next true if j > 0 && board[i][j - 1] == '#'
    false
  end
end
puts(is_ok ? 'Yes' : 'No')


Measured memory_bytes: 1916
#include <iostream>
#include <cstdio>
#include <cstring>

const int INF = 999999999;

int n, m, d[55][55], f[550][550], tmp[55][55];

void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}

int Max(int a, int b)
{
    return a > b ? a : b;
}

int Min(int a, int b)
{
    return a < b ? a : b;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &d[i][j]);

    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++) 
            for (int x = 1; x <= n; x++)
                for (int y = 1; y <= m; y++)
                    f[i][j] = Max(f[i][j], d[x][y] - i * x - j * y);

    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
        {
            tmp[x][y] = INF;
            for (int i = 0; i <= 100; i++)
                for (int j = 0; j <= 100; j++)
                    tmp[x][y] = Min(tmp[x][y], i * x + j * y + f[i][j]);
        }


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if(tmp[i][j] != d[i][j])
            {
                puts("Impossible"); return 0;
            }

    puts("Possible");
    printf("%d %d\n", 202, 10401);
    for (int i = 1; i <= 100; i++) printf("%d %d X\n", i, i + 1);
    for (int i = 102; i <= 201; i++) printf("%d %d Y\n", i, i + 1);
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            printf("%d %d %d\n", i + 1, 202 - j, f[i][j]);
    puts("1 202");
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
  int a, b, c, d, e, f;
  float x, y;
  while (scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f) != EOF){
    x = (float)((float)(e*c)-(float)(b*f))/((float)(e*a)-(float)(b*d));
    y = (float)((float)(c*d)-(float)(f*a))/((float)(b*d)-(float)(e*a));
    if((int)(x * 10000) % 10 >= 5.0){
      x += 0.001;
    }
    if((int)(y * 10000) % 10 >= 5.0){
      y += 0.001;
    }
    if(x == -0.000){
      x = 0.000;
    }
    if(y == -0.000){
      y = 0.000;
    }
    printf("%.3f %.3f\n", x, y);
  }
  return 0;
}

Measured memory_bytes: 632
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	int N,M;
	cin>>N>>M;
	
	int a = 0;
	int b = 1;
	if(M == 1){
		cout<<1<<" "<<2<<endl;
	}
	else if(M % 2 == 1){
		//even
		for(int i = 1; i <= M / 2; i++){	
			a = i;
			b = a + (M - 2 * (i-1) - 1);
			cout<<a<<" "<<b<<endl;
		}
		//odd
		for(int i = 1; i <= M/2 + 1; i++){	
			a = M + i;
			b = a + (M - 2 * (i-1) );
			cout<<a<<" "<<b<<endl;
		}
	}
	else{
		//even
		for(int i = 1; i <= M / 2; i++){	
			a = i;
			b = a + (M - 2 * (i-1) );
			cout<<a<<" "<<b<<endl;
		}
		//odd
		for(int i = 1; i <= M/2; i++){	
			a = M + 1 + i;
			b = a + (M - 2 * (i-1) - 1);
			cout<<a<<" "<<b<<endl;
		}
	}
	//vector<int> used_check(N+1,0);

	//int a = 1,b = 2;
	//used_check[a] = 1;
	//used_check[b] = 1;
	//cout<<1<<" "<<2<<endl;
	//for(int i = M; i > 1; i--){

	//	a = (b + 1) % (N+1);
	//	b = (a + i) % (N+1);
	//	if(a == 0)a += 1;
	//	if(b == 0)b += 1;
	//	//ll ctn = 0;
	//	while((used_check[a] != 0 || used_check[b] != 0 )){
	//	//while( ctn++ < 100000000 &&(used_check[a] != 0 || used_check[b] != 0 )){
	//		a = (a + 1) % (N+1);
	//		b = (a + i) % (N+1);
	//		if(a == 0)a += 1;
	//		if(b == 0)b += 1;
	//	}
	//	//cout<<"ctn : "<<ctn<<endl;
	//	used_check[a] = 1;
	//	used_check[b] = 1;
	//	cout<<a<<" "<<b<<endl;
	//}

	return 0;
}



Measured memory_bytes: 3612
n,m = map(int,input().split())
ans = []
l = []
for i in range(n):
    if i == 0:
        ans = list(map(int,input().split()))
        ans.pop(0)
    else:
        l = list(map(int,input().split()))
        l.pop(0)
        ans = set(ans) & set(l)
print (len(ans))


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        Scanner scanner = new Scanner(System.in);
        byte[] S = scanner.next().getBytes();
        if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) {
            System.out.println("Bad");
            return;
        }

        System.out.println("Good");
    }

}


Measured memory_bytes: 21716
#include<cstdio>
#include<algorithm>
using namespace std;
 
int main(){
  int n,p,l[100000];
  while(scanf("%d",&n),n){
    long long num = n,len = 0;
    for(int i=0;i<n;i++){ scanf("%d",&p); len += p;}
 
    for(int i=0;i<n-1;i++)scanf("%d",&l[i]);
    sort(l,l+n-1);
     
    for(int i=n-2;i>=0;i--){
      if( (num-1)*(len+l[i]) < num*len )break;
      num--; len += l[i];
    }
    printf("%lld\n",num*len);
  }
}

Measured memory_bytes: 1304
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	long int c[505];
	long int s[505];
	long int f[505];
	for(int i=1;i<n;i++){
		cin >> c[i] >> s[i] >> f[i];
	}
	if(n==1){
		cout << 0 << endl;
		return 0;
	}
	if(n==2){
		cout << s[1]+c[1] << endl;
		cout << 0 << endl;
		return 0;
	}else{
		long int ans[505];
		for(int i=1;i<n;i++){
			ans[i] = s[i]+c[i];
		}
		ans[n] = 0;
		int x = 1;
		for(int i=1;i<n-1;i++){
			for(int j=x;j<n-1;j++){
				if(ans[i]<s[j+1]){
					ans[i] = s[j+1]+c[j+1];
				}else{
					if(ans[i]%f[j+1]==0){
						ans[i] += c[j+1];
					}else{
						ans[i] += f[j+1]-(ans[i]%f[j+1])+c[j+1];
					}
				}
			}
			x++;
		}
		for(int i=1;i<=n;i++){
			cout << ans[i] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    

    ll n;
    cin >> n;
    ll ans = 0;
    ll tmp = 0;
    ll prev = 0;
    for (ll i=0;i<n;i++){
        ll h;
        cin >> h;
        if(i==0){
            prev = h;
        }else{
            if(prev >= h){
                tmp++;

                if(ans < tmp){
                    ans = tmp;
                }
            }else{
                tmp = 0;
            }
            prev = h;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>

using namespace std;

string S;
int main(){
    cin >> S;
    int cnt = 0;
    int l = S.length();
    for(int i=0; i<l-1; i++) if( S[i] != S[i+1] ) cnt++;
    cout << cnt << endl;
    return 0;
}

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

const int var = 4;
const int pmax = 1e4;

int trans(char c) {
	switch (c)
	{
	case 'R': return 0;
	case 'D': return 1;
	case 'L': return 2;
	case 'U': return 3;
	default: assert(false);
	}
}

struct ac_node {
	ac_node *fail;
	ac_node *next[var];
	int ok;
	ac_node() : fail(nullptr), next{}, ok(0) {}
};

ac_node* get_next(ac_node* p, char c) {
	while (!p->next[trans(c)]) p = p->fail;
	return p->next[trans(c)];
}

class aho_corasick {
	ac_node* new_ac_node() {
		static ac_node pool[pmax];
		static int it = 0;
		assert(it < pmax);
		return &pool[it++];
	}
	int K;
	ac_node *root;
public:
	aho_corasick(const vector<string>& Ts) : K(Ts.size()), root(new_ac_node()) {
		ac_node *now;
		root->fail = root;
		for (int i = 0; i < K; i++) {
			auto &T = Ts[i];
			now = root;
			for (auto c : T) {
				if (!now->next[trans(c)]) {
					now->next[trans(c)] = new_ac_node();
				}
				now = now->next[trans(c)];
			}
			now->ok = 1;
		}
		queue<ac_node*> q;
		for (int i = 0; i < var; i++) {
			if (!root->next[i]) {
				root->next[i] = root;
			}
			else {
				root->next[i]->fail = root;
				q.push(root->next[i]);
			}
		}
		while (!q.empty()) {
			now = q.front(); q.pop();
			for (int i = 0; i < var; i++) {
				if (now->next[i]) {
					ac_node *nx = now->fail;
					while (!nx->next[i]) {
						nx = nx->fail;
					}
					now->next[i]->fail = nx->next[i];
					now->next[i]->ok = max(now->next[i]->ok, nx->next[i]->ok);
					q.push(now->next[i]);
				}
			}
		}
	}
	ac_node* get_root() const {
		return root;
	}
	int get_node_id(ac_node* nd) const {
		return (int)(nd - root);
	}
};

const int INF = 1e8;

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

string D = "DRUL";

using T = tuple<int, int, ac_node*>;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, p;
	while (cin >> n >> m, n | m) {
		vector<string> S(n);
		int sx = 0, sy = 0, gx = 0, gy = 0;
		for (int i = 0; i < n; i++) {
			cin >> S[i];
			for (int j = 0; j < (int)S[i].size(); j++) {
				if (S[i][j] == 'S') {
					sx = i;
					sy = j;
				}
				else if (S[i][j] == 'G') {
					gx = i;
					gy = j;
				}
			}
		}
		cin >> p;
		vector<string> pts(p);
		for (int i = 0; i < p; i++) {
			cin >> pts[i];
		}
		aho_corasick aho(pts);
		vector<vector<vector<int>>> f(n, vector<vector<int>>(m, vector<int>(110, INF)));
		queue<T> q;
		q.push(make_tuple(sx, sy, aho.get_root()));
		f[sx][sy][aho.get_node_id(aho.get_root())] = 0;
		while (!q.empty()) {
			auto tup = q.front(); q.pop();
			int x = get<0>(tup), y = get<1>(tup);
			ac_node *nd = get<2>(tup);
			int id = aho.get_node_id(nd);
			for (int i = 0; i < 4; i++) {
				int tx = x + dx[i], ty = y + dy[i];
				ac_node *tnd = get_next(nd, D[i]);
				if (0 <= tx && tx < n && 0 <= ty && ty < m && S[tx][ty] != '#' && !tnd->ok && f[tx][ty][aho.get_node_id(tnd)] == INF) {
					q.push(make_tuple(tx, ty, tnd));
					f[tx][ty][aho.get_node_id(tnd)] = f[x][y][id] + 1;
				}
			}
		}
		int res = INF;
		for (auto val : f[gx][gy]) {
			res = min(res, val);
		}
		cout << (res != INF ? res : -1) << endl;
	}
	return 0;
}



Measured memory_bytes: 4712
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  int n; cin >> n;
  vi a(3*n,0);
  rep(i,3*n) cin >> a.at(i);

  priority_queue<int,vi,greater<int>> mae;
  ll maesum = 0;
  rep(i,n) {
    mae.push(a.at(i));
    maesum+=a.at(i);
  }

  vl maesums(n+1,0);
  maesums.at(0) = maesum;
  srep(i,n,2*n) {
    if(mae.top() < a.at(i)) {
      maesum-=mae.top();
      mae.pop();
      maesum+=a.at(i);
      mae.push(a.at(i));
    }
    maesums.at(i+1-n) = maesum;
  }

  reverse(rng(a));
  priority_queue<int> ushiro;
  ll ushirosum = 0;
  rep(i,n) {
    ushiro.push(a.at(i));
    ushirosum+=a.at(i);
  }
  vl ushirosums(n+1,0);
  ushirosums.at(0) = ushirosum;
  srep(i,n,2*n) {
    if(ushiro.top() > a.at(i)) {
      ushirosum-=ushiro.top();
      ushiro.pop();
      ushirosum+=a.at(i);
      ushiro.push(a.at(i));
    }
    ushirosums.at(i+1-n) = ushirosum;
  }
  reverse(rng(ushirosums));

  ll ans = -100000000000000000101010;
  rep(i,n+1) ans = max(ans,maesums.at(i)-ushirosums.at(i));

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6904
package main

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

//•*¨*•.¸¸♪I/O•*¨*•.¸¸♪

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInt64() int64 {
	sc.Scan()
	a,_ := strconv.ParseInt(sc.Text(),10,64)
	return a
}

func scanFloat64() float64 {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return float64(a)
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

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

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	sc.Split(bufio.ScanWords)
	// sc.Buffer(make([]byte, 10000), 100000000)

	s := scanText()

	ans := int64(0)

	for i := 0; i < len(s); i++ {
		for j := 0; j+i < len(s); j++ {
			// fmt.Println(s[j:j+1+i], len(s[:j]),len(s[j+1+i:]))
			cnt := 0
			if len(s[:j])>=1 {
				cnt+=len(s[:j])-1
			}
			if len(s[j+1+i:])>=1 {
				cnt+=len(s[j+1+i:])-1
			}
			// fmt.Println(cnt)
			num, _ := strconv.ParseInt(s[j:j+1+i],10,64)
			ans+=num*int64(1<<uint(cnt))
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<functional>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
	string s;	cin>>s;
	int n=s.length();int res=n;
	for(int i=0;i<n-1;i++)
		if(s[i]!=s[i+1])
		{
			int m=max(i+1,n-i-1);
			if(m<res)res=m;
		}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int n;
int arr[5];
double dp[303][303][303];

double solve(int remOnes, int remTwos, int remThrees)
{
    if(!remOnes && !remTwos && !remThrees)
        return 0;
    if(remOnes < 0 || remTwos < 0 || remThrees < 0)
        return 0;
    if(dp[remOnes][remTwos][remThrees])
        return dp[remOnes][remTwos][remThrees];
    double ans = 0.0;
    int currT = remOnes + remTwos + remThrees;
    if(remOnes > 0)
        ans += 1.0 * remOnes / currT * solve(remOnes - 1, remTwos, remThrees);
    if(remTwos > 0)
        ans += 1.0 * remTwos / currT * solve(remOnes + 1, remTwos - 1, remThrees);
    if(remThrees > 0)
        ans += 1.0 * remThrees / currT * solve(remOnes, remTwos + 1, remThrees - 1);
    ans += 1.0 * n / currT;
    /*
    int currT = remOnes + remTwos + remThrees;
    double ans = remOnes * 1.0 / currT * solve(remOnes - 1, remTwos, remThrees) +
            remTwos * 1.0 / currT * solve(remOnes + 1, remTwos - 1, remThrees) +
            remThrees * 1.0 / currT * solve(remOnes, remTwos + 1, remThrees - 1) + n * 1.0 / currT;
    */
    return dp[remOnes][remTwos][remThrees] = ans;
}

int main()
{
    IO;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        arr[x]++;
    }
    cout << fixed << setprecision(17) << solve(arr[1], arr[2], arr[3]);
    return 0;
}

Measured memory_bytes: 217472
#include <bits/stdc++.h>
typedef long long ll;
 
using namespace std;
const int INF = 1e9 + 5;
int main(){
    string s; cin >> s;
    for(int i = 1; i < s.size() - 1; i++) {
        if(s[i] == 'R') {
            s[i] = 'B';
        }
        else if(s[i] == 'B') {
            s[i] = 'R';
        }
    }
    cout << s;
    return 0;
}

Measured memory_bytes: 3600
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int a;
		int b;
		if(n<2){
			a=0;
		}else{
			a=n*(n-1)/2;
		}
		if(m<2){
			b=0;
		}else{
			b=m*(m-1)/2;
		}
		System.out.println(a+b);
	}
}


Measured memory_bytes: 21844
#include<iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    if(0<N && N<10){
        cout << N << endl;
    } else if(10<=N && N<100){
        cout << 9 << endl;
    } else if(100<=N && N<1000){
        cout << N-90 << endl;
    } else if(1000<=N && N<10000){
        cout << 909 << endl;
    } else if(10000<=N && N<100000){
        cout << N-9090 << endl;
    } else if(100000==N){
        cout << 90909 << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<28;
const int V_MAX=100;

struct edge{ int v,a,b,c; };

int main(){
	int n,m,s,t,F;
	while(~scanf("%d%d%d%d%d",&n,&m,&s,&t,&F) && n>0){
		vector<edge> G[V_MAX];
		rep(i,m){
			int u,v,a,b,c; scanf("%d%d%d%d%d",&u,&v,&a,&b,&c);
			G[u].push_back((edge){v,a,b,c});
		}

		edge z={-1}; // a<b の辺
		rep(u,n) rep(i,G[u].size()) {
			const edge &e=G[u][i];
			if(e.a<e.b) z=e;
		}

		static int d1[V_MAX][V_MAX]; // d1[u][v] := ( 流量 F の一本のフローを u -> v に流すための最小コスト )
		static int d2[V_MAX][V_MAX]; // 流量 z.c
		static int d3[V_MAX][V_MAX]; // 流量 F - z.c, ただし辺 z は通らない
		rep(u,n) rep(v,n) {
			d1[u][v]=(u==v?0:INF);
			d2[u][v]=(u==v?0:INF);
			d3[u][v]=(u==v?0:INF);
		}
		rep(u,n) rep(i,G[u].size()) {
			const edge &e=G[u][i];
			int v=e.v,a=e.a,b=e.b,c=e.c;
			if(F<=c) d1[u][v]=min(d1[u][v],a*F);
			else     d1[u][v]=min(d1[u][v],a*c+b*(F-c));
			if(z.v!=-1 && z.c<=F){
				if(z.c<=c) d2[u][v]=min(d2[u][v],a*z.c);
				else       d2[u][v]=min(d2[u][v],a*c+b*(z.c-c));
				if(a>=b){
					if((F-z.c)<=c) d3[u][v]=min(d3[u][v],a*(F-z.c));
					else           d3[u][v]=min(d3[u][v],a*c+b*((F-z.c)-c));
				}
			}
		}

		// Warshall-Floyd
		rep(w,n) rep(u,n) rep(v,n) d1[u][v]=min(d1[u][v],d1[u][w]+d1[w][v]);
		rep(w,n) rep(u,n) rep(v,n) d2[u][v]=min(d2[u][v],d2[u][w]+d2[w][v]);
		rep(w,n) rep(u,n) rep(v,n) d3[u][v]=min(d3[u][v],d3[u][w]+d3[w][v]);

		int ans=d1[s][t];
		rep(u,n) rep(v,n) ans=min(ans,d1[s][u]+d2[u][v]+d3[u][v]+d1[v][t]);

		if(ans<INF) printf("%d\n",ans); else puts("Impossible");
	}

	return 0;
}

Measured memory_bytes: 1200
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MAX_N 100000+10
#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int N;
int M;
class UnionFind {
    private:
        int par[MAX_N];
        int rank[MAX_N];
    public:
        UnionFind(int n) {
            for(int i = 1;i <= n;i++) {
                par[i] = i;
                rank[i] = 1;
            }
        }

        int root(int x) {
            return x == par[x] ? x : par[x] = root(par[x]);
        }

        bool same(int x,int y) {
            return root(x) == root(y);
        }

        void merge(int x,int y) {
            x = root(x);
            y = root(y);
            if(x == y)
                return;

            if(rank[x] < rank[y]) {
                par[x] = y;
            } else {
                par[y] = x;
                if(rank[x] == rank[y]) {
                    rank[x]++;
                }
            }

            return;
        }

        int connect(void) {
            int ans = 0;
            for(int i = 1;i <= N;i++) {
                par[i] = root(par[i]);

                if(i == par[i])
                    ans++;
            }

            return ans;
        }
};

vector<pair<int,int> > Edge;
            
int main(void) {
    cin>>N>>M;

    for(int i = 0;i < M;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        Edge.push_back(make_pair(x,y));
    }

    UnionFind uf(N);
    for(int i = 0;i < M;i++) {
        uf.merge(Edge[i].first,Edge[i].second);
    }

    cout<<uf.connect()<<endl;

    return 0;
}




Measured memory_bytes: 1908
h, w = map(int, input().split())
board = [ [0 for _ in range(w)] for _ in range(h) ]
for i in range(h):
  s = input()
  for j, c in enumerate(s):
    if c == '#':
      board[i][j] = 1

for i in range(h):
  c0 = board[i][0]
  for j in range(1, w):
    c = board[i][j]
    if c == 0:
      continue
    if board[i][j-1] == 1 or (j < w-1 and board[i][j+1] == 1):
      continue
    if (i > 0 and board[i-1][j] == 1) or (i < h-1 and board[i+1][j] == 1):
      continue
    print('No')
    exit()
print('Yes')


Measured memory_bytes: 3064
#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

const ll mod = 998244353;
const int N = 2e5 + 10, M = 1e6 + 10;
const ll INF = 1e18;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

#define pi acos(-1)

ll a[N];
ll sum[N];

int main()
{
    int k;
    int n;
    cin >> k >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        a[i] = x;
    }
    ll ans = a[n] - a[1];
    for (int i = 1; i < n; i++)
    {
        if (i == 1)
        {
            ans = min(ans, a[n] - a[1]);
            ans = min(ans, a[1] + k - a[2]);
        }
        else if (i == n)
        {
            ans = min(ans, a[n - 1] + k - a[n]);
        }
        else
        {
            ans = min(ans, k - a[i] + a[i - 1]);
            ans = min(ans, a[i] + k - a[i + 1]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <sstream>

using namespace std;


int main(int argc, const char * argv[]) {
    const int ANTENA_NUM = 5;
    int a, e;
    cin >> a;
    for (int i = 1; i < ANTENA_NUM - 1; i++) {
        int tmp; cin >> tmp;
    }
    cin >> e;
    
    int k; cin >> k;
    cout << (e - a <= k ? "Yay!" : ":(") << endl;
    
    return 0;
}


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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector< ii >
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }

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

int32_t main(){
  DESYNC;
  int n;
  cin >> n;
  string s;
  cin >> s;
  char lst = '0';
  int ans = 0;
  for(char c : s){
    if(c != lst) ans++;
    lst = c;
  }
  cout << ans << endl;
}




Measured memory_bytes: 512
#include<bits/stdc++.h>
 
using namespace std;
 
#define INF 1000000007
#define LINF 1000000000000000007
 
typedef long long i64;
typedef pair<i64,i64> P;


int a,b,t;

int main(){
	cin >> a >> b>>t;
	
	cout << t/a*b << endl;
	
	return 0;
}

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

int main()
{
  int h, a ;
  cin >> h >> a;
  
   int total = 0 ;
   while(h>0){
     h-=a ;
     total++ ;
   }

 cout << total << endl ;
  
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string sl, sr, sm;
int l, r;

int main(){
    cin >> n;
    fflush(stdin);
    cout << 0 << endl;
    fflush(stdout);
    cin >> sl;
    fflush(stdin);
    if(sl == "Vacant"){
        return 0;
    }
    int l = 0, r = n;
    while(1){
        int m = (l+r)/2;
        cout << m << endl;
        fflush(stdout);
        cin >> sm;
        fflush(stdin);
        if(sm == "Vacant"){
            return 0;
        }
        if((l+m)%2 == 0){
            if(sl == sm){
                sl = sm;
                l = m;
            }
            else{
                r = m;
            }
        }
        else{
            if(sl != sm){
                sl = sm;
                l = m;
            }
            else{
                r = m;
            }
        }

    }
    return 0;
}

Measured memory_bytes: 852
N = int(input())
A = list(map(int, input().split()))

if len(set(A)) == 1:
    print(0)
    exit()

v = 0
min_val = 10000000
for i in range(min(A), 101):
    v = 0
    for a in A:
        v += (a - i)**2
    if min_val > v:
        min_val = v

print(min_val)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,x,y,z;
  cin >>A;
  
  x=A%10;
  y=((A-x)%100)/10
   ;
  z=((A-y*10-x)%1000)/100;
  cout <<x+y+z <<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int mod=1e9+7,N=1e6+5;
int pre[N],f[N],fac[N],sum,n,h,d;

int calc(int l,int r){
	return l>0?(pre[r]-pre[l-1]+mod)%mod:pre[r];
}

signed main(){
	read(n,h,d);
	fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod,sum=(sum+fac[i])%mod;
	pre[0]=f[0]=fac[n];
	for(int i=1;i<h;i++){
		f[i]=1ll*calc(i-d,i-1)*sum%mod;
		pre[i]=(pre[i-1]+f[i])%mod;
	}
	write(calc(h-d,h-1));
}

Measured memory_bytes: 15364
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


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

    int a,b,c,d;
    cin >> a>>b>>c>>d;
    cout << a*b - (c*b + d*a - c*d)<<endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin>>s;
	int ans=1e9;
	REP(i, s.size()-2){
		int tmp=100*(s[i]-'0')+10*(s[i+1]-'0')+(s[i+2]-'0');
		CHMIN(ans, abs(tmp-753));
	}
	cout<<ans<<'\n';
	return 0;
}


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

int main()
{
	int n, k;
	
	scanf("%d%d", &n, &k);
	long long s = k;
	for (int i = 2; i <= n; i++) {
		s *= (k - 1);
	}
	printf("%lld\n", s);
}

Measured memory_bytes: 256
s=input()
ans='w'*60
for i in range(0,len(s)):
    if s[i]=='0':
        ans+='0'
    elif s[i]=='1':
        ans+='1'
    elif s[i]=='B':
        ans=ans[:-1]
    else:
        pass
A=s.count('0')
B=s.count('1')
C=s.count('B')

for j in range(0,60+A+B-C):
    ans=ans.lstrip('w')

print(ans)


Measured memory_bytes: 3060
#include <stdio.h>

int main(void)
{
  int k,n;
  scanf("%d",&k);
  scanf("%d",&n);
  
  int id[n];
  int dist[n];
  for(int i=0; i<n; i++){
    scanf("%d",&id[i]);
    dist[i]=0;
  }
  
  for(int i=0; i<(n-1); i++){
    dist[i]=id[i+1]-id[i];
  }
  dist[n-1]=(k-id[n-1])+id[0];
  
  int calc=0,max=0;
  for(int i=0; i<n; i++){
    calc += dist[i];
    if(max<dist[i]) max=dist[i];
  }
  
  printf("%d",calc-max);
  
  return 0;
}

Measured memory_bytes: 3252
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

int main(){
  int n; 
  cin >> n;

  ll res = 1;
  ll ans;
  for(int i=1; i<=n; ++i){
    res *= i;
    res %= 1000000007;
  }
  
  cout << res << endl;
  return 0;
}

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() {
  int n;
  cin >> n;
  vector<int> ans(10000000);
  int MAX_CNT = 150;
  for(int x = 1; x < MAX_CNT; x++){
    for(int y = 1; y < MAX_CNT; y++){
      for(int z = 1; z < MAX_CNT; z++){
        int val = x * x + y * y + z * z + x * y + y * z + z * x;
          ans[val] += 1;
      }
    }
  }
  for(int i = 1; i <= n; i++){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 42240
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    string s;
    int x;
    vector<tuple<string,int,int>> shop(N);
    for(int i=0;i<N;i++){
        cin >> s >> x;
        shop.at(i)=make_tuple(s,-x,i+1);
    }
    sort(shop.begin(),shop.end());
    	for (tuple<string, int, int> t : shop) {
    		string s;
          	int x, y;
    		tie(s,x,y)=t;
            cout << y << endl;
        }
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

u64 gcd(u64 x, u64 y)
{
    if (x < y) swap(x, y);
    if (y == 0) return x;
    else return gcd(y, x % y);
}

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

    u64 A, B;
    cin >> A >> B;
    u64 N = gcd(A, B);//gcd(A, B);

    bool flag;
    u64 ans = 1;
    for (u64 i = 2; i * i <= N; ++i)
    {
        flag = false;
        while (N % i == 0)
        {
            flag = true;
            N /= i;
        }
        if (flag) ++ans;
    }
    if (N > 1) ++ans;

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=205;
int N,Ans,col[MAXN];
int vis[MAXN],dep[MAXN];
char c[MAXN];
vector<int>P[MAXN];
queue<int>Q;
int DFS(int u){
	int size=P[u].size();
	for(int i=0;i<size;i++){
		int v=P[u][i];
		if(col[v]!=-1){
			if(col[v]!=(col[u]+1)%2)
				return 0;
			continue;
		}
		col[v]=(col[u]+1)%2;
		if(!DFS(v))return 0;
	}
	return 1;
}
void check(int x){
	while(!Q.empty())Q.pop();
	memset(dep,0,sizeof(dep));
	memset(vis,0,sizeof(vis));
	Q.push(x);dep[x]=1;vis[x]=1;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		int size=P[u].size();
		for(int i=0;i<size;i++){
			int v=P[u][i];
			if(vis[v])continue;
			dep[v]=dep[u]+1;
			Ans=max(Ans,dep[v]);
			vis[v]=1;Q.push(v);
		}
	}
}
int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%s",c+1);
		for(int j=1;j<=N;j++)
			if(c[j]=='1')
				P[i].push_back(j);
	}
	memset(col,-1,sizeof(col));
	if(!DFS(1)){
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=N;i++)check(i);
	printf("%d\n",Ans);
}

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

int main(){
  int a,b;
  cin >> a >> b;
  if(a==b){
	cout << "Draw" << endl;
  }
  else if(a==1){
    cout << "Alice" << endl;
  }
  else if (b==1){
    cout << "Bob" << endl;
  }
    else if (a<=b){
	cout << "Bob" << endl;
  }
  else{
    cout << "Alice" << endl;
  }
}





Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}



///////////////////////////



int main() {

	string s, t, u;
	ll a, b;
	cin >> s >> t;
	cin >> a >> b;
	cin >> u;
	if (s == u) { cout << a - 1 << " " << b; }
	else { cout << a << " " << b - 1; }
	

	
	

	
	system("PAUSE");

}


Measured memory_bytes: 504
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;


void main() {
    char x, y;
    scan(x, y);

    if (x < y) {
        writeln("<");
    }
    else if (x > y) {
        writeln(">");
    }
    else {
        writeln("=");
    }
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

int main(){
  ll h,w; cin >> h >> w;
  if(h==1||w==1){cout << 1; return 0;}
  
  ll aa = h*w;
  ll ret = aa;
  if(aa%2==0)ret=aa/2;
  else ret=aa/2 + 1;
  cout << ret;
  

}

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

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

    int count = 0;
    while(true){
        string::size_type abc_idx = S.find("ABC");
        if(abc_idx == string::npos){
            break;
        }
        S.erase(abc_idx, 3);
        count++;
    }

    cout << count << endl;
    return 0;
}

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

using namespace std;

int n,k;
int dizi[100005][5];
int dp[100005][5];
int dpf(int day,int last_activity){
	if( last_activity!=-1 && dp[day][last_activity]!=-1 ){
		// printf("%d\n",dp[day][last_activity] );
		return dp[day][last_activity];
	}
	if(day==n){
		return 0;
	}
	int mx=INT_MIN;
	for(int i=0;i<3;i++){
		if(i!=last_activity){
			mx=max(mx,dpf(day+1,i)+dizi[day][i]);
			// printf("%d\n", dizi[day][i]);
		}
		// else printf("%d\n",i );
	}
	dp[day][last_activity]=mx;
	return dp[day][last_activity];

}


int main(){
	// freopen("a.gir","r",stdin);
 //   freopen("a.cik","w",stdout);

	scanf("%d",&n);
	for(int i=0;i<100004;i++){
		for(int j=0;j<5;j++)
			dp[i][j]=-1;
	}
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&dizi[i][0],&dizi[i][1],&dizi[i][2]);
	}

	printf("%d\n",dpf(0,-1) );
		
}

Measured memory_bytes: 10368
#include<cstdio>

int n;
char s[4];
int main(){
	scanf("%s",s);

	for(int i = 0; s[i] != '\0'; i++){
        n++;
    }

	for(int i = 0; i < n; i++){
        s[i] -= '0';
    }

	long ans = 0;
	for(int S = 0;S < (1 << n);S++){
		long sum = s[0];
		long a = s[1];
		for(int i = 1;i < n;i++){
			if(S & (1 << i)){
				sum += a;
				a = s[i + 1];
			}else{
				sum -= a;
				a = s[i + 1];
			}
		}

        ans = sum;
        if(ans == 7){
            printf("%d",s[0]);
            for(int i = 1;i < n;i++){
                if(S & (1 << i)){
                    printf("+%d",s[i]);
                }else{
                    printf("-%d",s[i]);
                }
            }
            printf("=%ld\n",ans);
            break;
        }
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <cstdio>
using namespace std;

void insertionSort(int A[], const int n, const int g, int *cnt)
{
    for( int i = g; i < n; ++i ){
        int tmp = A[i];
        int j = i - g;
        while( -1 < j && tmp < A[j] ){
            //cout << A[j+g] << "<-->" << A[j] << endl;
            A[j+g] = A[j];
            j = j - g;
            ++*cnt;
        }
        A[j+g] = tmp;
    }
}

void shellSort(int A[], const int n)
{
    int cnt = 0;
    int m;
    int G[100];
    for( int i = 0; i < 100; ++i ){
        if( i == 0 ) G[i] = n / 2 + 1;
        else G[i] = G[i-1] / 2 - 1;
        if( G[i] < 0 ){
            G[i-1] = 1;
            G[i] = 0;
            m = i;
            break;
        }
    }

    for( int i = 0; i < m; ++i )
        insertionSort(A, n, G[i], &cnt);

    //出力
    printf("%d\n", m);
    for( int i = 0; i < m; ++i ){
        if( i ) printf(" ");
        printf("%d", G[i]);
    }
    printf("\n%d\n", cnt);
    for( int i = 0; i < n; ++i )
        printf("%d\n", A[i]);
}

int main()
{
    //入力
    int n;
    scanf("%d", &n);
    int A[n];
    for( int i = 0; i < n; ++i )
        scanf("%d", &A[i]);

    //シェルソート
    shellSort(A, n);

    return 0;
}


Measured memory_bytes: 7072
#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	std::string s;
	std::cin >> s;
	int64_t res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (s[i] == s[j]) continue;
			for (int k = 0; k < j; k++) if (j - k != i - j && s[k] != s[i] && s[k] != s[j]) res++;
		}
	}
	printf("%" PRId64 "\n", res);
	return 0;
}


Measured memory_bytes: 3796