akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#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 REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const double PI = acos(-1);

//解説AC

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vi A(N * 3);
	REP(i, N * 3) {
		cin >> A[i];
	}
	so(A); rev(A);
	ll sum = 0;

	for(int i = 1;i < 2 * N;i += 2){
		sum += A[i];
	}
	cout << sum << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 1656
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]
#迷路の黒マスを数えてキューに入れる作業
from collections import deque
quest=deque([])#最初に見る場所
#迷路の外を＃で囲む
for i in range(r):
    meiro[i].insert(c,"#")
    meiro[i].insert(0,"#")
meiro.insert(0,["#"]*(c+2))
meiro.append(["#"]*(c+2))
#print(meiro)
tesuu=[[-1]*(c+2) for i in range(r+2)]
for i in range(1,r+1):
    for j in range(1,c+1):
        if meiro[i][j]=="#":
            quest.append([i,j])
            tesuu[i][j]=0
#print(quest)

idou=[[0,1],[0,-1],[1,0],[-1,0]]
#print(tesuu)
while len(quest)!=0:
    see=quest.popleft()
    for i in idou:
        if meiro[see[0]+i[0]][see[1]+i[1]]=="#":
            continue
        if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
            continue
        quest.append([see[0]+i[0],see[1]+i[1]])
        tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
te=[]
for i in range(r+2):
    te.extend(tesuu[i])
print(max(te))

Measured memory_bytes: 175012
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;
const int maxi = 6400;

int main() {
	int h, w, tmp;
	scanf("%d %d", &h, &w);
	// cin >> h >> w;

	vector<vector<int>> borad(h, vector<int>(w, 0));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			scanf("%d", &tmp);
			// cin >> tmp;
			borad[i][j] += tmp;
		}
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			scanf("%d", &tmp);
			// cin >> tmp;
			// borad[i][j] -= tmp;
			borad[i][j] = abs(borad[i][j] - tmp);
		}
	}

	// vector<vector<set<int>>> nums(h+1, vector<set<int>>(w+1));
	vector<vector<vector<bool>>> nums(h+1, vector<vector<bool>>(w+1, vector<bool>(maxi, false)));
	// nums[0][0].insert(0);
	nums[0][0][0] = true;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			// vector<int> v(nums[i][j].begin(), nums[i][j].end());
			for (int k = 0; k < maxi; k++) {
				if (!nums[i][j][k]) {
					continue;
				}
				int x = k;
			// for (auto x: v) {
				auto a = x + borad[i][j];
				auto b = abs(x - borad[i][j]);

				if (a <= maxi) {
					// nums[i][j+1].insert(a);
					// nums[i+1][j].insert(a);
					nums[i][j+1][a] = true;
					nums[i+1][j][a] = true;
				}
				if (b <= maxi) {
					// nums[i][j+1].insert(b);
					// nums[i+1][j].insert(b);
					nums[i][j+1][b] = true;
					nums[i+1][j][b] = true;
				}

			}
		}
	}

	int ans = -1;
	for (int i = 0; i <= maxi; i++) {
		if (nums[h-1][w][i]) {
			ans = i;
			break;
		}
		if (nums[w-1][h][i]) {
			ans = i;
			break;
		}
	}

	// int ans = (*nums[h-1][w].begin(), *nums[h][w-1].begin());
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5888
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iostream>


using namespace std;

int main()
{
	int a, b, c;
	int rect = 0;
	int lozen = 0;
	while (scanf("%d,%d,%d", &a, &b, &c) != EOF)
	{
		if (a == b)
			++lozen;
		else if (a*a+b*b == c*c)
			++rect;
	}
	printf("%d\n%d\n", rect, lozen);

	return 0;
}

Measured memory_bytes: 0
import itertools

a = []
for i in range(5):
  a.append(int(input()))
k = int(input())
flag = True

for v in itertools.combinations(a, 2):
  if v[1] - v[0] > k:
    flag = False

if flag:
  print("Yay!")
else:
  print(":(")

Measured memory_bytes: 3064
/*
   ~~~~~~~~~~~~~~~~~~~
   \  |\/| | |\ | |  /
   /  |  | | |/ |_|  \
   ~~~~~~~~~~~~~~~~~~~
*/
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{	
	char s[200005],t[200005];
	cin>>s>>t;
	int n=strlen(s),count=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]!=t[i]) count++;
	}
	cout<<count<<endl;
	
	return 0;
}

Measured memory_bytes: 4024
// ------------------------------------
// Date:2018/ 2/25
// Problem:ABC 049 DayDream c.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

using ll = long long;

#define MOD 1000000007

int main()
{
  string inputStr,tmp;
  // state 0: ,1:dream, 2:erase, 3:e, 4:r
  int state = 0;
  bool output = true;
  
  cin >> inputStr;
  REP(num, inputStr.size()) {
    switch(state) {
      case 0:
        tmp = inputStr.substr(num,5);
        if (tmp == "dream") state = 1;
        else if (tmp == "erase") state = 2;
        else output = false;
        num += 4;
        break;
        // dream
      case 1:
        tmp = inputStr.substr(num,5);
        if (tmp == "dream") num += 4;
        else if (tmp == "erase")
        {
          state = 2;
          num += 4;
        } else if (tmp[0] == 'e') state = 3;
        else output = false;
        break;
        // erase
      case 2:
        tmp = inputStr.substr(num,5);
        if (tmp == "dream") {
          state = 1;
          num += 4;
        }
        else if (tmp == "erase") num += 4;
        else if (tmp[0] == 'r') state = 4;
        else output = false;
        break;
        // e
      case 3:
        if (inputStr[num] == 'r') state = 4;
        else output = false;
        break;
        // r
      case 4:
        tmp = inputStr.substr(num,5);
        if (tmp == "dream") state = 1;
        else if (tmp == "erase") state = 2;
        else output = false;
        num += 4;
        break;
    }
  }
  if (state == 3) output = false;
  cout << (output?"YES":"NO") << endl;
  return 0;
}



Measured memory_bytes: 512
# C - Vacation
import numpy as np

N = int(input())
value = np.zeros((N, 3))
for i in range(N):
    value[i, :] = list(map(int, input().split()))
value = value.tolist()

dp = [0]*3

for a, b, c in value:
    dp = [max(dp[1], dp[2])+a, max(dp[0], dp[2])+b, max(dp[0], dp[1])+c]
    
print(int(max(dp)))

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

public class Main {
	private static Scanner sc;
	public static void main(String[] args){
		sc=new Scanner(System.in);
		int n=sc.nextInt();
		String[] a=new String[n];
		String[] b=new String[n];
		for(int i=0;i<n;i++){
			a[i]=sc.next();
			b[i]=a[i];
		}
		
		a=bubbleSort(a,n);
		write(a,n);
		System.out.println("Stable");
		
		b=selectionSort(b,n);
		write(b,n);
		if(Arrays.equals(a,b)){
			System.out.println("Stable");
		}else{
			System.out.println("Not stable");
		}
	}
	static void write(String[] a,int n){
		for(int i=0;i<n-1;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println(a[n-1]);
	}
	static String[] bubbleSort(String[] a, int n){
		boolean flag=true;
		int i=0;
		while(flag){
			flag=false;
			for(int j=n-1;j>i;j--){
				if(a[j].charAt(1)<a[j-1].charAt(1)){
					String temp=a[j];
					a[j]=a[j-1];
					a[j-1]=temp;
					flag=true;
				}
			}
			i++;
		}
		return a;
	}
	static String[] selectionSort(String[] a, int n){
		int minj;
		for(int i=0;i<n;i++){
			minj=i;
			for(int j=i;j<n;j++){
				if(a[j].charAt(1)<a[minj].charAt(1)){
					minj=j;
				}
			}
			String temp=a[i];
			a[i]=a[minj];
			a[minj]=temp;
		}
		return a;
	}

}

Measured memory_bytes: 26256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<complex>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define DBL(x) ((x)*(x))
#define EPS 1e-10

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef complex<double> P;

int main(){
  int n;
  const P r(0.0,1.0);
  while(scanf("%d",&n) , n){
    vector<P> o(n);
    int ans = 1;
    REP(i, n) scanf("%lf,%lf",&o[i].real(), &o[i].imag());
    for(int i=0; i<n; i++){
      for(int j=i+1; j<n; j++){
	if(abs(o[i] - o[j]) > 2.0) continue;
	if(abs(o[i] - o[j]) < EPS){
	  ans = max(ans, 2);
	  continue;
	}
	P mid = (o[i] + o[j]) / 2.0;
	P dir = (o[i] - o[j]) / 2.0;
	double len = sqrt(1.0 - DBL(abs(dir)));
	if(len < EPS){
	}else{
	  dir *= r;
	  dir /= abs(dir);
	  dir *= len;
	}

	P pos[2] = { mid + dir, mid - dir };

	REP(idx,2){
	  int cnt = 0;
	  //printf("(%d,%d),(%f,%f): ",i+1,j+1,abs(pos[idx] - o[i]),abs(pos[idx] - o[j]));
	  REP(k, n){
	    double dist = abs(pos[idx] - o[k]);
	    if(dist <= 1.0 + EPS){
	      //printf("%d(%f) ",k+1,dist);
	      cnt++;
	    }
	  }
	  //puts("");
	  ans = max(ans, cnt);
	}
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(){
  int a, b;
  scanf("%d %d", &a, &b);
  if(a<b){
    printf("a < b\n");
  }
  else if(a==b){
    printf("a == b\n");
  }
  else{
    printf("a > b\n");
  }
  return 0;
}


Measured memory_bytes: 2088
#include<bits/stdc++.h>
using namespace std;
#define LS (v << 1)
#define RS (v << 1 | 1)
const int MAXN = 4 * 200010;
const int INF = ~0U >> 2;
int n;
int rea[MAXN];
int ll[MAXN],rr[MAXN];
long long ans;
struct node{
	int Min, Max;
	int l,r;
} t[MAXN];
void build(int v, int l, int r)
{
	t[v].l = l, t[v].r = r;
	if(l == r)
	{
		t[v].Min = n + 1;
		t[v].Max = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(LS, l, mid);
	build(RS, mid+1, r);
	t[v].Min = n + 1;
	t[v].Max = 0;
}
void chang(int v, int pos, int x)
{
	if(t[v].l == pos && t[v].r == pos)
	{
		t[v].Min = t[v].Max = x;
		return;
	}
	if(pos <= t[LS].r) chang(LS, pos, x);
	if(pos >= t[RS].l) chang(RS, pos, x);
	t[v].Min = min(t[LS].Min, t[RS].Min);
	t[v].Max = max(t[LS].Max, t[RS].Max);
}
int queryi(int v, int l, int r)
{
	if(t[v].l == l && t[v].r == r) return t[v].Min;
	if(r <= t[LS].r) return queryi(LS, l, r);
	else if(l >= t[RS].l) return queryi(RS, l, r);
	else return min(queryi(LS, l, t[LS].r), queryi(RS, t[RS].l, r));
}
int querya(int v, int l, int r)
{
	if(t[v].l == l && t[v].r == r) return t[v].Max;
	if(r <= t[LS].r) return querya(LS, l, r);
	else if(l >= t[RS].l) return querya(RS, l, r);
	else return max(querya(LS, l, t[LS].r), querya(RS, t[RS].l, r));
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &rea[i]);
	build(1,1,n);
	chang(1, rea[1], 1);
	ll[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		ll[i] = querya(1, 1, rea[i]) + 1;
		chang(1, rea[i], i);
	}
	build(1,1,n);
	chang(1, rea[n], n);
	rr[n] = n;
	for(int i = n - 1; i > 0; i--)
	{
		rr[i] = queryi(1, 1, rea[i]) - 1;
		chang(1, rea[i], i);
	}
	for(int i = 1; i <= n; i++)
		ans += (i - ll[i] + 1ll) * (rr[i] - i + 1ll) * rea[i];
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 10752
/*
     Contest  :
     Task    :
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define ll  long long
#define int long long
#define F_  first
#define S_  second
#define itr ::iterator 
 
typedef pair<int,int> pii;
 
const int MAX=3e5+99;
const int mod=1e9+7;
const int INF=1e16;
 
vector<pii> vec[MAX];
 
int N,M,S,T,X,Y,Z,dp[MAX][2],dis[MAX][2];
 
void dijkstra(int node,int K)
{
	pair<int,int> cur;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int A=1;A<=N;A++)
	dis[A][K]=INF,dp[A][K]=0;
	dp[node][K]=1;
	dis[node][K]=0;
	pq.push(mp(0,node));
	while(! pq.empty())
	{
		cur=pq.top();
		pq.pop();
		if(cur.first > dis[cur.second][K])
		continue;
		for(auto A:vec[cur.second])
		{
			if(cur.first+A.second < dis[A.first][K])
			{
				dis[A.first][K]=cur.first+A.second;
				dp[A.first][K]=dp[cur.second][K];
				pq.push(mp(dis[A.first][K],A.first));
			}
			else if(cur.first+A.second == dis[A.first][K])
			dp[A.first][K]+=dp[cur.second][K],
			dp[A.first][K]%=mod;
		}
	}
	return ;
}
 
int solve()
{
	int D,cnt=0;
	dijkstra(S,0);
	dijkstra(T,1);
	D=dis[T][0];
	for(int A=1;A<=N;A++)
	if(dis[A][0]==dis[A][1] and dis[A][0]+dis[A][1]==D)
	{
		cnt+=(((dp[A][0]*dp[A][1])%mod) * ((dp[A][0]*dp[A][1])%mod))%mod;
		cnt%=mod;
	}
	for(int A=1;A<=N;A++)
	for(auto B:vec[A])
	if(dis[A][0]<D/2+D%2 and dis[B.first][1]<D/2+D%2 and dis[A][0]+B.second+dis[B.first][1]==D)
	{
		cnt+=(((dp[A][0]*dp[B.first][1])%mod)* ((dp[A][0]*dp[B.first][1])%mod))%mod;
		cnt%=mod;
	}
	cnt=(dp[T][0]*dp[S][1])%mod-cnt;
	cnt%=mod;
	while(cnt<0)
	cnt+=mod;
	return cnt;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	/*cin.tie(0);
	cout.tie(0);*/
	
	cin>>N>>M;
	cin>>S>>T;
	for(int A=1;A<=M;A++)
	{
		cin>>X>>Y>>Z;
		vec[X].pb(mp(Y,Z));
		vec[Y].pb(mp(X,Z));
	}
	cout<<solve();
    return 0;
}

Measured memory_bytes: 27220
#include <iostream>
using namespace std;
typedef long long ll;


//https://atcoder.jp/contests/abc121/tasks/abc121_d
//0~aまでのXOR
ll f(ll a){
	int b = a%4;
	
	if(b==0){
		return a;
	}
	if(b==1){
		return 1;
	}
	if(b==2){
		return a+1;
	}
	if(b==3){
		return 0;
	}
	
}



int main() {
	ll a,b;
	cin>>a>>b;
	
	if(a!=0)a--;
	ll ans = f(a)^f(b);
	
	cout<<ans<<'\n';
	
	
	
	
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    char S[100000];
    int r,b;
    scanf("%s",S);
    for(int i=0;S[i]!='\0';i++){
        if (S[i]=='1') {
            b++;
        }
        else{
            r++;
        }
    }
    if(r<b){
        printf("%d\n",r*2);
    }
    else{
        printf("%d\n",b*2);
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
#define endl "\n"
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef long long ll;
#define MOD 1000000007;

int main() 
{ 
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n; cin >> n;
    if(n%1000==0){
        cout << 0 << endl;
    }
    else cout << 1000 - n%1000 << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<int>>
constexpr auto mod = 1000000007;


//2のn乗を求めるよ！！！
int ni(int n) {
	if (n == 0)return 1;
	int x = ni(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;
}

//フィボナッチ数列のx番目を求めるよ！
int f(int x,vector<int> s) {
	if (x == 0)return 0;
	if (x == 1)return 1;
	if (s[x] != 0)return s[x];
	s[x] = f(x - 1,s) + f(x - 2,s);
	return s[x];
}

//aとｂの最大公約数を求めるよ！
llint gcd(llint a, llint b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}



// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b,ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

//m進数のn桁を全列挙やで
void dfs(int m, int n) {

	stack<string> st;
	st.push("");
	while (!st.empty()) {
		string now = st.top();
		st.pop();
		if (now.size() == n) {
			cout << now << endl;
		}
		else {
			for (int i = m-1; i >= 0; i--) {
				string next = now + to_string(i);
				st.push(next);
			}
		}
	}
}

int main(){
	int n;
	cin >> n;
	hei(int) d(n);
	rep(i, 0, n)cin >> d[i];
	sort(d);
	int ans = d[n / 2] - d[n / 2 - 1];
	cout << ans << endl;
	return 0;
}




  


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int X, Y, Z; cin >> X >> Y >> Z;
    int sum = 0, cnt = 0;
    while(true) {
        sum += Y + Z;
        if (sum + Z > X) break;
        cnt++;
    }
    printf("%d\n", cnt);
}


Measured memory_bytes: 3672
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <utility>

using namespace std;
typedef long long signed int ll;

constexpr ll inf = INT64_MAX / 2;

int main() {
	int n, k;
	vector<pair<int, int>> v;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v.emplace_back(x, y);
	}
	sort(v.begin(), v.end());
	ll res = inf;
	vector<pair<int, int>> v2;
	for (auto i = v.begin();i + (k-1) < v.end(); i++) {
		for (auto j = i + (k-1); j < v.end(); j++) {
			v2.clear();
			for (auto l = i; l <= j; l++) {
				v2.push_back(*l);
			}
			sort(v2.begin(), v2.end(), [](pair<int, int> a, pair<int, int> b) {
				return a.second < b.second;
				});
			for (auto l = v2.begin(); l != v2.end() && (l+(k-1)) != v2.end(); l++) {
				ll x = j->first - i->first;
				ll y = (l + k - 1)->second - l->second;
				res = min(res, x*y);
			}
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  string s;cin>>s;

  bool a,b;

  if(s.size()%2==0){
    a=true;
  }else{
    a=false;
  }

  if(s[0]==s[s.size()-1]){
    b=true;
  }else{
    b=false;
  }

  if(a^b){
    cout<<"Second"<<endl;
  }else{
    cout<<"First"<<endl;
  }

  return 0;
}


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

int w;
int h;

#define MAX 100002

long long int p[MAX];
long long int q[MAX];

vector<pair<long long int, int> > P;
vector<pair<long long int, int> > Q;


struct UF{
	vector<int> belong;
	vector<int> size;
	int S;
	void resize(int n){
		belong.assign(n + 1, -1);
		size.assign(n + 1, 1);
		S = 0;
	}
	inline int root(int b){
		if (belong[b] == -1){
			return b;
		}
		belong[b] = root(belong[b]);
		return belong[b];
	}
	void merge(int a, int b){
		a = root(a);
		b = root(b);
		if (a == b)return;
		S++;
		belong[a] = b;
		size[b] += size[a];
	}
};

UF u1;
UF u2;


int main(){
	cin >> w >> h;
	w++;
	h++;
	for (int i = 0; i < w-1; i++){
		scanf("%lld", &p[i]);
		P.push_back(make_pair(p[i], i));
	}
	for (int i = 0; i < h-1; i++){
		scanf("%lld", &q[i]);
		Q.push_back(make_pair(q[i], i));
	}
	sort(P.begin(), P.end());
	sort(Q.begin() , Q.end());
	u1.resize(MAX);
	u2.resize(MAX);
	int i1 = 0;
	int i2 = 0;
	long long int ans = 0;
	while (i1 < P.size() || i2 < Q.size()){
		if (i1!=P.size()&&(i2==Q.size()||P[i1].first < Q[i2].first)){
			int H = h - u1.S;
			ans += (long long int)(P[i1].first) *(long long int)(H);
			u2.merge(P[i1].second, P[i1].second + 1);
			i1++;
		}
		else{
			int W = w - u2.S;
			ans += (long long int)(Q[i2].first)*(long long int)(W);
			u1.merge(Q[i2].second, Q[i2].second + 1);
			i2++;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 6512
from collections import Counter

N, = list(map(int, input().split()))
S = []
for i in range(N):
    S.append(input())
S = Counter(S)
best = max((v, k) for k, v in S.items())

for w in sorted(k for k, v in S.items() if v == best[0]):
    print(w)


Measured memory_bytes: 35572
import sys
from copy import copy


fin = sys.stdin.readline
N, x = [int(elem) for elem in fin().split()]
a_list = [int(elem) for elem in fin().split()]

min_total_cost = float('inf')
min_so_far = a_list[:]
for num_magics in range(N):
    for i in range(N):
        min_so_far[i] = min(min_so_far[i], a_list[i - num_magics])
    total_cost = sum(min_so_far) + num_magics * x
    min_total_cost = min(min_total_cost, total_cost)
print(min_total_cost)

Measured memory_bytes: 43116
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>
#include <set>
#include <numeric>

using namespace std;

template <typename T>
using TABLE = vector<vector<T>>;

using LONG = long long;
using LVEC = vector<long long>;


#define FOR(i, s, e) for(LONG i = s; i < e; ++i)


long long PRIME = 1e9 + 7;
long long PRIME2 = 998244353;


class UnionFindTree{
public:
    UnionFindTree(LONG N){
        ranks.resize(N, 1);
        parent.resize(N, -1);
    }

    void merge(LONG a, LONG b){
        LONG r_a = _root(a);
        LONG r_b = _root(b);

        if(r_a == r_b){
            return;
        }

        if(ranks[r_a] < ranks[r_b]){
            parent[r_b] = r_a;
            ranks[r_a] = ranks[r_b] + 1;
        }
        else{
            parent[r_a] = r_b;
            ranks[r_b] = ranks[r_a] + 1;
        }
    }

    bool isSame(LONG a, LONG b){
        LONG r_a = _root(a);
        LONG r_b = _root(b);

        return r_a == r_b;
    }

private:
    vector<LONG> ranks;
    vector<LONG> parent;

    LONG _root(LONG a){
        if(parent[a] == -1){
            return a;
        }

        LONG r = _root(parent[a]);
        parent[a] = r;
        return r;
    }
};

int main(){
    LONG N, M;
    cin >> N >> M;

    LVEC p(N);
    FOR(i, 0, N){
        cin >> p[i];
        p[i] -= 1;
    }

    UnionFindTree tree(N);

    LONG x, y;
    FOR(i, 0, M){
        cin >> x >> y;
        tree.merge(x-1, y-1);
    }

    LONG sum = 0;
    FOR(i, 0, N){
        if(tree.isSame(p[i], i)){
            ++sum;
        }
    }

    cout << sum;
}


Measured memory_bytes: 2560
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define IFOR(i,a) for(int i=(a);;i++)
#define REP(i,n)  FOR(i,0,n)
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define INPUT \
FILE *fp; \
fp=fopen("input.text","r");



int main() {
    int r,c;
    cin >> r >> c;
    int tmp,sum,mat[r][c],kai[r+1][c+1];
    
    
    FOR(row, 0, r){
        sum=0;
        FOR(column, 0, c){
            cin >> tmp;
            mat[row][column]=tmp;
            kai[row][column]=tmp;
            sum+=tmp;
          
        }
        kai[row][c]=sum;
    }
    
    

    FOR(column, 0, c+1){
        sum=0;
        FOR(row, 0, r){
            sum+=kai[row][column];
        }
      
        kai[r][column]=sum;
    }
    
    FOR(row, 0, r+1){
        FOR(column, 0, c+1){
            if (column!=c) {
                cout << kai[row][column] << " ";
            }
            else cout << kai[row][column] <<endl;
        }
    }
    return 0;
}





Measured memory_bytes: 3136
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<string> s(3);
    for(int i=0; i<3; i++){
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
    }
    int curr = 0;
    while((int)s[curr].length() != 0){
        int next = s[curr].back() -'a';
        s[curr].pop_back();
        curr = next;
    }
    cout << (char)(curr + 'A') << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define deb(x) cout<<#x<<" "<<x<<endl;
#define ll long long int
#define ld long double
#define fo(i, n) for(ll i = 0; i<n; i++)
#define Fo(i, a, n) for(ll i = a; i<n; i++)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define pi pair<int, int>
#define pl pair<ll, ll>
#define u_m unordered_map
#define u_s unordered_set
#define p_q priority_queue
using namespace std;
const int N = 1e5+2;
ll dp[N];
const ll MOD = 1e9+7;
void solve()
{
	int n;
	cin>>n;
	vi h(n+1, 0);
	Fo(i,1,n+1) cin>>h[i];
	dp[2] = abs(h[2]-h[1]);
	dp[3] = min(dp[2]+abs(h[2]-h[3]), (ll)abs(h[1]-h[3]));
	Fo(i, 4, n+1)
	{
		dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
	}
	cout<<dp[n]<<endl;
}
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin>>t;
    //while(t--)
		solve();	
    return 0;
}


Measured memory_bytes: 1408
import sys
S = int(input())

mae = S//100
ushiro = S%100

if 0 < mae and mae <= 12:
    if 0 < ushiro and ushiro <= 12:
        print ('AMBIGUOUS')
        sys.exit()
    else:
        print ('MMYY')
        sys.exit()
if 0 < ushiro and ushiro <= 12:
    if 0 < mae and mae <= 12:
        print ('AMBIGUOUS')
        sys.exit()
    else:
        print ('YYMM')
        sys.exit()
print ('NA')

    


Measured memory_bytes: 3060
#include <stdio.h>

int  main(void){
         int h,w,i,j;
          while(1){
          scanf("%d %d",&h,&w);
           if( h==0 && w==0)
              break;
           for(i=1; i<=h; i++){
            for(j=1; j<=w; j++){
              printf("#");
             }printf("\n");
            }printf("\n");
           }
            return 0;
}

Measured memory_bytes: 572
n = int(input())
l = input().split()

if n < 3:
  print(0)
else:
  cnt = 0
  for i in range(n-2):
    for s in range(i+1,n-1):
      for t in range(s+1,n):
        x = int(l[i])
        y = int(l[s])
        z = int(l[t])
        if x != y and x != z and y != z:
          #print(l[i],l[s],l[t])
          if x > y and x > z and x < (y+z):
            cnt += 1
          elif y > x and y > z and y < (x+z):
            cnt += 1
          elif z > x and z > y and z < (x+y):
            cnt += 1
  print(cnt) 

Measured memory_bytes: 9220
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

bool check(string s) {
  int n = s.size();
  if(s[0] != 'A') return false;
  int c = 0;
  for(int i = 2; i< n-1; i++) {
    if(s[i] == 'C') c++;
  }
  if(c != 1) return false;
  int up = 0;
  rep(i, n) {
    if('A' <= s[i] && s[i] <= 'Z') up++;
  }
  if(up != 2) return false;
  return true;
}

int main() {
  string s;
  cin >> s;
  check(s) ? cout << "AC" << endl : cout << "WA" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    Scanner sc = new Scanner(System.in);

    int[] copyArray(int[] src) {
        int[] dst = new int[src.length];
        for (int i = 0; i < src.length; i++) {
            dst[i] = src[i];
        }
        return dst;
    }

    List<Integer> traverse(int[] W, int[] sorted, boolean[] traversedIndices, int firstIdx, int idx) {
        traversedIndices[idx] = true;
        int x = W[idx];
        int nextIdx = -1;
        for (int i = 0; i < sorted.length; i++) {
            if (sorted[i] == x) {
                nextIdx = i;
                break;
            }
        }
        if (nextIdx == -1) throw new Error();
        if (firstIdx == nextIdx) {
            List<Integer> li = new LinkedList<Integer>();
            li.add(idx);
            return li;
        } else {
            List<Integer> li = traverse(W, sorted, traversedIndices, firstIdx, nextIdx);
            li.add(idx);
            return li;
        }
    }
List<List<Integer>> findCycles(int[] W) {
        int[] copied = copyArray(W);
        Arrays.sort(copied);
        int[] sorted = copied;
        boolean[] traversedIndices = new boolean[W.length];
        List<List<Integer>> cycles = new LinkedList<List<Integer>>();
        for (int i = 0; i < W.length; i++) {
            if (traversedIndices[i]) continue;
            cycles.add(traverse(W, sorted, traversedIndices, i, i));
        }
        return cycles;
    }

    void printCycles(List<List<Integer>> cycles) {
        System.out.println("Cycles ---");
        for (List<Integer> li : cycles) {
            for (Integer x : li) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
        System.out.println("--- Cycles");
    }

    int calcCycleCost(int[] W, List<Integer> cycle, int min) {
        int sum = 0;
        int minInACycle = Integer.MAX_VALUE;
        if (cycle.size() == 1) return 0;
        for (Integer val : cycle) {
            sum += W[val];
            minInACycle = Math.min(minInACycle, W[val]);
        }
        int a = sum + (cycle.size() - 2) * minInACycle;
        int b = sum + minInACycle + (cycle.size()+1) * min;
        return Math.min(a, b);
    }
int calcCost(int[] W, List<List<Integer>> cycles, int min) {
        int cost = 0;
        for (List<Integer> cycle : cycles) {
            int x = calcCycleCost(W, cycle, min);
            cost += x;
        }
        return cost;
    }

    void run() {
        int n = sc.nextInt();
        int[] W = new int[n];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < W.length; i++) {
            W[i] = sc.nextInt();
            min = Math.min(min, W[i]);
        }
        List<List<Integer>> cycles = findCycles(W);
        //printCycles(cycles);
        System.out.println(calcCost(W, cycles, min));
    }
    public static void main(String[] args) {
        new Main().run();
    }
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;
const static ll MOD = 1e9 + 7;

int main(int argc, char *argv[]) {
    ll n;
    cin >> n;
    ll p[n];
    NREP() {
        cin >> p[i];
    }

    ll ans = 0;
    ll minimum = p[0];
    NREP() {
        if (p[i] <= minimum) ans++;
        minimum = min(p[i], minimum);
    }
    MSG(ans)
}


Measured memory_bytes: 1920
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    n = int(input())
    d = input_nums()
    d.sort()
    m = len(d)//2
    abc_val = d[m-1]+1
    arc_val = d[m]
    if arc_val - abc_val >= 0:
        print(arc_val - abc_val + 1)
    else:
        print(0)

if __name__ == '__main__':
    main()

Measured memory_bytes: 14428
N = int(input())
H = reversed(list(map(int, input().split())))
p = float('INF')
for i in H:
    if p >= i:
        p = i
    elif p + 1 == i:
        pass
        # p = i - 1
    else:
        print('No')
        exit()
    # print(i, p)
print('Yes')


Measured memory_bytes: 14252
#include<stdio.h>

int con(int);
int main(){
  int n,m; scanf("%d%d",&n,&m);
  printf("%d\n",con(n)+con(m));
  return 0;
}

int con(int n){
  if (n>1)  return n*(n-1)/2;
  else return 0;
}

Measured memory_bytes: 128
n = int( raw_input( ) )
t = [ int( val ) for val in raw_input( ).rstrip( ).split( " " ) ]
q = int( raw_input( ) )
s = [ int( val ) for val in raw_input( ).split( " " ) ]

cnt = 0
for si in s:
	for ti in t:
		if si == ti:
			cnt += 1
			break

print( cnt )

Measured memory_bytes: 4716
program abc160c
   implicit none
   integer :: K, N, i
   integer, allocatable :: A(:)
   integer, allocatable :: interval(:)
   integer :: way_min, pass, dont_pass

   read(*,*) K, N
   allocate(A(N), interval(N))
   read(*,*) A(:)

   ! write(*,*) K, N
   ! write(*,*) A(:)
   way_min = K
   i = 1
   dont_pass = A(i) + (K-A(N))
   pass = K - dont_pass
   way_min = min(way_min, pass)

   do i = 2, N
      dont_pass = A(i) - A(i-1)
      pass = K -  dont_pass
      way_min = min(way_min, pass)
   end do

   write(*,*) way_min

end program abc160c


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

int main(void) {
    int S, H, C, D;
    S = 0;   H = 1;   C = 2;   D = 3;
    char mark[4] = {'S', 'H', 'C', 'D'};
    int card[4][13] = {};
    int num;
    int n;
    char m;
    
    cin >> num;
    for(int i = 0; i < num; ++i) {
        cin >> m >> n;
        switch(m) {
            case 'S' : ++card[S][n-1];   break;
            case 'H' : ++card[H][n-1];   break;
            case 'C' : ++card[C][n-1];   break;
            case 'D' : ++card[D][n-1];   break;
        }
    }
    for(int i = 0; i < 4; ++i) {
        for(int j = 0; j < 13; ++j) {
            if(card[i][j] == 0) {
                cout << mark[i] << ' ' << j + 1 << endl;
            }
        }
    }
    
    return 0;
}



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

using namespace std;

const int mxn = 1e5;

int a[mxn + 11];

int main(){
	int n, x;
	scanf("%d %d", &n, &x);
	for (int i = 1; i <= n; i++){
		scanf("%d", a + i);
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++){
		int cur = a[i] + a[i - 1];
		if (cur >= x){
			ans += cur - x;
			a[i] -= cur - x;
		}
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double PI = 3.14159265358979;
const double E = 2.718281828459045;
const double root2 = sqrt(2);
typedef pair<int, int> P;
typedef unsigned int ui;
int main() {
	int n, k, s;
	while (cin >> n >> k >> s) {
		if (n == 0)break;
		int dp[21][11][156] = {};
		dp[0][0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				for (int l = 0; l <= s; l++) {
					dp[i][j][l] += dp[i - 1][j][l];
					if (j - 1 >= 0&&l-i>=0) {
						dp[i][j][l] += dp[i - 1][j - 1][l - i];
					}
				}
			}
		}
		cout << dp[n][k][s] << endl;
	}
	return 0;
}



Measured memory_bytes: 3124
import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])


Measured memory_bytes: 83808
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
import heapq
import json
N=int(input())
l=[0]*(N+1)

for i in range(1,N+1):
    for j in range(i,N+1,i):
        l[j]=l[j]+1
#print(l)

ans=0
l=tuple(l)
for i in range(N+1):
    ans=ans+(l[i]*i)
print(ans)


Measured memory_bytes: 440416
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1005
int t[MAXN];
int a,b;
void Init()
{
	t[1]=1;
	for(int i=2;i<=MAXN-6;i++)
	{
		t[i]+=(t[i-1]+i);
	}
	//for(int i=1;i<=MAXN-6;i++)
	//printf("%d  ",t[i]);
}
int main()
{
	Init();
	scanf("%d %d",&a,&b);
	printf("%d",t[b-a]-b);
}

Measured memory_bytes: 128
#include <bits/stdc++.h> 
    //#define M_PI 3.14159265358979323846



using namespace std;

#define rep(i,a,b) for(int i=a;i<b;++i)
#define repb(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vl vector<long long int>
#define vc vector<char>
#define vld vector<ld>
#define vvi vector<vector<int> >
#define vvl vector<vector<long long> >
#define vvld vector<vector<ld> >
#define vpii vector<pii>
#define vpll vector<pll>
#define ld long double
#define ll long long
#define sz(a) (ll)a.size()
#define ssortA(arr)   stable_sort(arr.begin(),arr.end())
#define ssortB(arr)   stable_sort(arr.begin(),arr.end(),greater<ll >());
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ff first
#define ss second
#define search(arr,c)  binary_search(arr.begin(),arr.end(),c)
#define pb   push_back
#define pf push_front
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define endl "\n" 
#define PI acos(-1.0)
#define GCD(a,b) __gcd(a,b)
#define popcount(x) __builtin_popcountll(x)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define r1(x) cin>>x
#define r2(x,y) cin>>x>>y
#define r3(x,y,z) cin>>x>>y>>z
#define r4(a,b,c,d) cin>>a>>b>>c>>d
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define fix(f,n) fixed<<setprecision(n)<<f<<endl
#define check(ds, a) (ds.find(a)!=ds.end()?1:0)
const ll M =1000000007;
vi mx={0,-1,1,2,-2};
vi dx={-1,1,0,0};
vi dy={0,0,-1,1};
 int h,w;
bool valid_check(int x,int y){
     bool ok=true;
     if(x>=h||x<0)ok&=false;
     if(y>=w||y<0)ok&=false;
    
     return ok;
 }
int main(){
   r2(h,w);
    int st1,st2;r2(st1,st2);--st1,--st2;
    int en1,en2;r2(en1,en2);--en1,--en2;
    char arr[h][w];
    rep(i,0,h)rep(j,0,w) r1(arr[i][j]);
    vector<vector<int> > dst(h,vector<int>(w,INT_MAX));
    deque<pair<int,pii > > dq;
    dst[st1][st2]=0;
    dq.pb(mp(0,mp(st1,st2)));
    while(!dq.empty()){
        int x=dq.front().first;
        int y=dq.front().ss.ff;
        int z=dq.front().ss.ss;
        dq.pop_front();
        if(dst[y][z]!=x){
            continue;
        }
        
        rep(i,0,4){
            int nx=y+dx[i];
            int ny=z+dy[i];
            if(valid_check(nx,ny)&&arr[nx][ny]!='#'){
                if(dst[y][z]<dst[nx][ny]){
                    dst[nx][ny]=dst[y][z];
                    dq.pf(mp(dst[nx][ny],mp(nx,ny)));
                }
            }
        }
        rep(i,0,5)
       {
           int j=0;
           if(mx[i]==0)j=3;
           if(mx[i]==-1||mx[i]==1)j=1;
           for(;j<=4;++j){
                int nx=y+mx[i];
            int ny=z+mx[j];
            if(valid_check(nx,ny)&&arr[nx][ny]!='#'){
                if(dst[y][z]+1<dst[nx][ny]){
                    dst[nx][ny]=dst[y][z]+1;
                    dq.pb(mp(dst[nx][ny],mp(nx,ny)));
                }
            }
           }
       }
    }
    if(dst[en1][en2]==INT_MAX)d1(-1);
    else d1(dst[en1][en2]);
}

Measured memory_bytes: 8668
local n = io.read('*n')
local a = io.read('*n')
local b = io.read('*n')
if b < a then
	print(0)
	return
end
if n == 1 then
	if a ~= b then
		print(0)
		return
	else
		print(1)
		return
	end
elseif n == 2 then
	print(1)
	return
end
print((n-2)*(b-a)+1)

Measured memory_bytes: 752
# import sys
# input = sys.stdin.readline
import itertools
import collections
from decimal import Decimal


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n = int(input())
    p = prime_factorize(n)
    cp = collections.Counter(p)
    ans = 0
    for c, num in cp.items():
        count = 0
        jou = 1
        for _ in range(num):
            count += 1
            if count == jou:
                count = 0
                jou += 1
                ans += 1
    print(ans)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def bfs(H, W, black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d + 1
                black_cells.append((new_h, new_w))
    return d


def input_list():
    return list(map(Decimal, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()


Measured memory_bytes: 77348
process.stdin.resume();
process.stdin.setEncoding('utf8');

// 標準入力取込
var g_input = '';
process.stdin.on('data', function(chunk) {
    g_input += chunk;
});
process.stdin.on('end', function() {
    main(g_input.split(/\r?\n/));
});

// 解答
function main(inputs:Array<string>) : void {

    // ボールの総数
    const ball: number = Number.parseInt(inputs[0]);
    // ボールに記載されている整数のリスト
    const ballList: number[] = inputs[1].split(" ").map((x: string): number => +x);
    // 各整数のボールの個数
    const numList: number[] = [];
    // 各整数の組み合わせ数
    const combinations = new Array(ball + 1);
    // 全組み合わせ数
    let all_sum = 0;

    // 各整数のボールの個数計算
    for (const ball of ballList) {

        if (numList[ball] === undefined) numList[ball] = 0;
        numList[ball] += 1;
    }

    // 各整数の組み合わせ数計算
    for (const value of numList) {

        if (value === undefined) continue;

        if (combinations[value] === undefined) {

            combinations[value] = calcCombination(value);
        }

        if (combinations[value - 1] === undefined) {

            combinations[value - 1] = calcCombination(value - 1);
        }
    }

    // 全組み合わせ数合算
    for (const value of numList) {

        if(value === undefined) continue;
        all_sum += combinations[value];
    }

    for (let i = 0; i < ball; i++) {

        const count: number = numList[ballList[i]];
        const answer = all_sum - combinations[count] + combinations[count - 1];
        console.log(answer);
    }
}

// 組み合わせ計算
function calcCombination(num: number) {

	return num * (num - 1) / 2;
}

Measured memory_bytes: 50008
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n;
string s,w;

int main(){
	cin >> n >> s >> w;
	
	vector<int> vec;
	REP(i,0,n){
		if(s[i]==w[i]) vec.push_back(0);
		else vec.push_back(1),i++;
	}
	
	ll ans=(vec[0]?6:3);
	REP(i,0,vec.size()-1){
		if(vec[i] and vec[i+1]) ans*=3;
		else if(vec[i] and !vec[i+1]) ans*=1;
		else if(!vec[i] and vec[i+1]) ans*=2;
		else if(!vec[i] and !vec[i+1]) ans*=2;
		ans%=MOD;
	}
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
const int maxn = 1e5+5;
 int main()
 {
 	 char a[maxn],b[maxn];
 	 int i;
 	 gets(a);
 	 gets(b);
 	 long long len = strlen(a);
 	 long long len1 = strlen(b);
	 if ( len > len1) printf("GREATER\n");
	 if ( len < len1) printf("LESS\n");
 	 if( len == len1){
 	if ( strcmp(a,b) < 0 ) printf("LESS\n");
 	else if ( strcmp(a,b) == 0) printf("EQUAL\n");
 	else if( strcmp(a,b) > 0) printf("GREATER\n");
	 }
 	 	 return 0;
 	 	 }

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




int main(){
	int N;
	cin>>N;
	vector<int> a(N);
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	if(N==1&&a[0]==1){
		cout<<-1<<endl;
		return 0;
	}
	bool flag[N]={};
	int ans = 0;
	for(int i=30;i>=0;i--){
		int cnt = 0;
		int ind = -1;
		int x = 1<<i;
		for(int j=0;j<N;j++){
			if(x&a[j]){
				cnt++;
				if((((x-1)&a[j])==0||i==0)&&!flag[j]){
					ind=j;
				}
			}
		}
		if(cnt%2==1){
			if(ind!=-1){
				a[ind]--;
				flag[ind]=true;
				ans++;
			}
			else{
				cout<<-1<<endl;
				return 0;
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 768
def s(n):
    return[m(t)for t in d(f(n))]
def f(n):
    l=[]
    b,e=2,0
    while b*b<=n:
        while not n%b:
            n//=b
            e+=1
        if e:
            l.append((b,e))
        b,e=b+1,0
    if n>1:
        l.append((n,1))
    return l
def d(l):
    b,e=l.pop()
    p=d(l)if l else[[]]
    v=[[(b,k)]for k in range(e+1)]
    return[s+t for s in p for t in v]
def m(l):
    a=1
    for b,e in l:
        a*=b**e
    return a
N,M=map(int,input().split())
if M<2:print(1);exit()
a=0
for i in sorted(s(M))[::-1]:
    if M//i>=N:
        a=i
        break
print(a)

Measured memory_bytes: 39280
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=110000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll gcd(ll x, ll y){
  if(x%y==0)return y;
  return gcd(y,x%y);
}
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll x;
  cin >> x;
  ll ans=0;
  ans+=2*(x/11);
  x-=(x/11)*11;
  if(x>6)ans+=2;
  else if(0<x)ans++;
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Map<String,Integer> dictionary = new HashMap<String,Integer>();
		StringBuffer ans = new StringBuffer();
		int n = Integer.parseInt(br.readLine());
	
		for(int i = 0; i < n; i++){
			String[] order = br.readLine().split(" ");
			if (order[0].contains("insert")) {
				dictionary.put(order[1], i);
			} else {
				if (dictionary.containsKey(order[1])) {
					ans.append("yes" + "\n");
				} else {
					ans.append("no" + "\n");
				}
			}
		}
		System.out.print(ans.toString());
	}
} 

Measured memory_bytes: 201868
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long ll;
int main(){
  string S;
  cin >> S;
  int N = S.size();
  ll dp[100005][4] = {};
  for (int i = N; i >= 0; i--) {
    for (int j = 3; j >= 0; j--){
      if (i == N){
        if (j == 3)
          dp[i][j] = 1;
        else
          dp[i][j] = 0;
      }
      else{
        dp[i][j] = dp[i + 1][j];
        if (S[i] == '?')
          dp[i][j] *= 3;
        if (j < 3 && (S[i] == '?' || S[i] == "ABC"[j]))
          dp[i][j] += dp[i + 1][j + 1];
        dp[i][j] %= mod;
      }
    }
  }
  cout<<dp[0][0]<<endl;
  return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>

int main() {
	int H, N, W, T;
	scanf("%d", &H);
	scanf("%d", &W);
	scanf("%d", &N);
	if (H > W) {
		T = H;
	} else {
		T = W;
	}
	int some = 1;
	for (int i = T; i < N; i += T) {
		some++;
	}
	printf("%d\n", some);
	return 0;
}

Measured memory_bytes: 1736