akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

ll n;
ll a, b, c, d;  
map<ll, ll> memo;

ll f(ll x){
    if(!x)  return 0;
    if(x==1) return d;
    if(memo.count(x)) return memo[x];
    ll res = LINF;
    
    //x*d<LINFの場合は更新
    if(x < LINF/d) res = x*d;
    //切り捨てしてからかけて左右を求める
    ll l2 = (x/2)*2;
    ll r2 = ((x+1)/2)*2;
    ll l3 = (x/3)*3;
    ll r3 = ((x+2)/3)*3;
    ll l5 = (x/5)*5;
    ll r5 = ((x+4)/5)*5;
    res = min(res, labs(x-l2)*d+a+f(l2/2));
    res = min(res, labs(x-r2)*d+a+f(r2/2));
    res = min(res, labs(x-l3)*d+b+f(l3/3));
    res = min(res, labs(x-r3)*d+b+f(r3/3));
    res = min(res, labs(x-l5)*d+c+f(l5/5));
    res = min(res, labs(x-r5)*d+c+f(r5/5));
    return memo[x] = res;

}




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

    int left=0, right=0, n=s.size(), res=0;
    char key[4] = {'A', 'C', 'G', 'T'};
    while(left<n){

        int cnt=0;  right = left;
        
        while(right<n){
            bool flag=false;
            REP(i, 4)   if(s[right]==key[i]) flag = true;
            if(!flag) break;
            right += 1;
            cnt++;
        }
        left = right+1;
        res = max(res, cnt);
    }
    cout << res << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <complex>

enum INDICES {
  COUNTER_CLOCKWISE = 0,
  CLOCKWISE,
  ONLINE_BACK,
  ON_SEGMENT,
  ONLINE_FRONT
};

const std::vector<std::string> strLst = {
  "COUNTER_CLOCKWISE",
  "CLOCKWISE",
  "ONLINE_BACK",
  "ON_SEGMENT",
  "ONLINE_FRONT"
};

const double tol = 1e-15;

int main() {
  double x0, y0, x1, y1;
  std::cin >> x0 >> y0 >> x1 >> y1;

  int q;
  std::cin >> q;

  for (int i = 0; i < q; ++i) {
    double x2, y2;
    std::cin >> x2 >> y2;

    int index;
    if ((x2 == x0 && y2 == y0) || (x2 == x1 && y2 == y1)) {
      index = INDICES::ON_SEGMENT;
    } else {
      double ip = (x1 - x0) * (x2 - x0) + (y1 - y0) * (y2 - y0);
      double norm1 = std::sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
      double norm2 = std::sqrt((x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0));
      double theta = ip / norm1 / norm2;
      if (theta < -1 + tol) {
        index = INDICES::ONLINE_BACK;
      } else if (theta > 1 - tol) {
        index = (norm1 < norm2) ? INDICES::ONLINE_FRONT : INDICES::ON_SEGMENT;
      } else {
        double opz = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
        index = (opz > 0) ? INDICES::COUNTER_CLOCKWISE : INDICES::CLOCKWISE;
      }
    }

    std::cout << strLst[index] << std::endl;
  }

  return 0;
}


Measured memory_bytes: 3284
#include<stdio.h>
int main(void){
        int s,h,m;
	scanf("%d",&s);
	h=s/3600;
	m=s%3600;
	m=m/60;
	s=s%3600;
	s=s%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
    int A, B;

    cin >> A >> B;

    int cnt = 0;
    for(int i = A; i <= B; i++){
        string aa = to_string(i);
        string bb = aa;
 
        reverse(aa.begin(), aa.end());

        if(aa == bb) cnt++;

    }

    cout << cnt << endl;

    return 0;
}


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

int main() {
    long long int x;
    cin>>x;
    long long int ans =100;
    long long int answ=0;
    
    while(x>ans){
        ans=ans*1.01;
        answ++;
    }
    cout<<answ<<endl;

}


Measured memory_bytes: 3640
import java.util.Scanner;

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

		int n = Integer.parseInt(s.next());

		double[] x = new double[n];
		String[] u = new String[n];

		for (int i = 0; i < n; i++) {
			x[i] = Double.parseDouble(s.next());
			u[i] = s.next();
		}
		double amount = 0.0;

		for (int i = 0; i < n; i++) {
			if (u[i].equals("JPY")) {
				amount += x[i];
			} else {
				amount += x[i] * 380000.0;
			}
		}
		System.out.println(amount);
	}
}

Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++) 
#define lint long long
#define all(x) (x).begin(), (x).end()


int main(){
    string s; cin >> s;
    int year = atoi(s.substr(0, 4).c_str());
    int month = atoi(s.substr(5, 2).c_str());
    int date = atoi(s.substr(8, 2).c_str());
    string ans = "TBD";
    if(year < 2019 || (year == 2019 && month <=4)) ans = "Heisei";
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int sum;
int main()
{
    cin >> n;
    for (int i = 1;i <= 4;i++)
    {
        if (n % 10 == 2)
        {
            sum++;
        }
        n = n / 10;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
from itertools import combinations
n = int(input())
d = {}
for _ in range(n):
  s = input()[0]
  if s in ["M","A","R","C","H"]:
    if s in d: d[s] += 1
    else: d[s] = 1

t = []
for k in d.keys(): t.append(k)
if len(t) < 3:
  print(0)
  exit()
  
ans = 0
for i in combinations(t, 3):
  ans += d[i[0]]*d[i[1]]*d[i[2]]
print(ans)

Measured memory_bytes: 9160
n, m = map(int, input().split())
if n >= m:
    print(0)
    exit(0)

l = sorted(list(map(int, input().split())))
m = sorted([l[i+1] - l[i] for i in range(m-1)])

for i in range(n-1):
    m.pop()

print(sum(m))


Measured memory_bytes: 13960
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

struct Sieve {
    int n;
    vector<int> f, primes;
    Sieve(int n = 1) : n(n), f(n + 1) {
        f[0] = f[1] = -1;
        for (ll i = 2; i <= n; ++i) {
            if (f[i]) continue;
            primes.push_back(i);
            f[i] = i;
            for (ll j = i * i; j <= n; j += i) {
                if (!f[j]) f[j] = i;
            }
        }
    }
    bool isPrime(int x) {
        return f[x] == x;
    }
    vector<int> factorList(int x) {
        vector<int> res;
        while (x != 1) {
            res.push_back(f[x]);
            x /= f[x];
        }
        return res;
    }
    vector<pair<int, int>> factor(int x) {
        vector<int> fl = factorList(x);
        if (fl.size() == 0) return {};
        vector<pair<int, int>> res(1, pair<int, int>(fl[0], 0));
        for (int p : fl) {
            if (res.back().first == p) {
                res.back().second++;
            } else {
                res.emplace_back(p, 1);
            }
        }
        return res;
    }
};


int main() {
    int Q;
    cin >> Q;
    Sieve sieve(1e5+10);
    
    vec<int> L2017(1e5+100,0);
    for(int i=1;i<=1e5;i+=2){
        if(i%2==0)continue;
        if(sieve.isPrime(i) && sieve.isPrime((i+1)/2)) L2017[i] = 1;
    }

    rep(i,1e5) L2017[i+1]+=L2017[i];

    rep(i,Q){
        int l, r;
        cin >> l >> r;
        cout << L2017[r]-L2017[l-1] << '\n';
    }

}


Measured memory_bytes: 3984
#include <bits/stdc++.h>
#define sf sacnf
#define pf printf
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define ii pair <int,int>
#define iii pair <int,ii>
#define pll pair <ll,ll>
#define plll pair <ll,pll>
#define Ziru 0
using namespace std;

int main(){
    int n;
    cin>>n;
    ll a[n],sum=0;

    for(int i=0; i<n; i++){
        cin>>a[i];
        sum+=a[i];
    }
    sort(a, a+n);
    cout<<a[0]<<" "<<a[n-1]<<" "<<sum<<endl;

    return Ziru;
}



Measured memory_bytes: 3180
#pragma GCC optimize("O4")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
//#define MOD (ll)(998244353)
#define MOD (ll)(1e9+7)
#define INF (1e17)
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	b%=MOD;
	int ans=1;
	while(p>0){
		if(p&1) ans=(ans*b)%MOD;
		p/=2;
		b=(b*b)%MOD;
	}
	return ans;
}

int dp[310][310];

int32_t main() {
#ifdef LOCAL_TEST
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\input.in","r",stdin);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\output.out","w",stdout);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\error.out","w",stderr);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);

	//code...
	int n,k; cin>>n>>k;
	vector<int> v(n+1);
	v[0]=0;
	For(i,1,n) cin>>v[i];
	For(i,0,n) dp[i][1]=v[i],dp[i][0]=0;
	For(i,1,n) dp[0][i]=INF;
	For(i,1,n) For(j,2,n-k){
		dp[i][j]=INF;
		For(l,0,i-1) dp[i][j]=min(dp[i][j],dp[l][j-1]+max(0ll,v[i]-v[l]));
		cerr<<dp[i][j]<<"\t\n"[j==n];
	}
	int ans=INF;
	For(i,0,n) ans=min(ans,dp[i][n-k]);
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(void) {
    int n, a;
    cin>>n;
    int max_n = 0;
    int min_n = 1000;
    for (int i=0; i<n; ++i) {
        cin>>a;
        max_n = max(a, max_n);
        min_n = min(a, min_n);
    }
    cout<<(max_n-min_n)<<endl;
    return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
a=[""]*h
for i in range(h):
	a[i]=input()

row=[False]*h
col=[False]*w
for i in range(h):
	for j in range(w):
		if a[i][j]=="#":
			row[i]=True
			col[j]=True
			
for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j],end='')
		print()

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

template<typename T>
struct LineFunction {
  /* y = mx + b */
  T m, b;
  LineFunction() : m{T{}}, b{numeric_limits<T>::min()} {
  }
  LineFunction(T m_, T b_) : m{m_}, b{b_} {
  }
  template<typename U>
  typename common_type<U, T, long long>::type operator()(U x) {
    using R = typename common_type<U, T, long long>::type; 
    return (R) m * x + b;
  }
};

template<typename T>
class LiChaoTree { // max LiChao Tree
  vector<LineFunction<T>> tree;
  int min_x, max_x; // you can query x : min_x <= x <= max_x
  int mid(int l, int r) {
    return l + ((r - l) >> 1);
  }
  void insert(LineFunction<T> y, int v, int l, int r) {
    if(l == r) {
      if(tree[v](l) < y(l)) tree[v] = y;
      return;
    }
    int x = mid(l, r);
    if(y(x) > tree[v](x)) swap(y, tree[v]);

    if(y.m > tree[v].m) insert(y, 2 * v + 1, x + 1, r);
    else insert(y, 2 * v, l, x);
  }
  T query(int x, int v, int l, int r) {
    if(l == r) return tree[v](x);
    int mid_x = mid(l, r);
    if(x < mid_x) return max(tree[v](x), query(x, 2 * v, l, mid_x));
    return max(tree[v](x), query(x, 2 * v + 1, mid_x + 1, r));
  }
public:
  LiChaoTree(int min_x_, int max_x_) : min_x{min_x_}, max_x{max_x_} {
    tree.resize((max_x - min_x + 1) << 2);
  }
  void insert(LineFunction<T> y) {
    insert(y, 1, min_x, max_x);
  }
  T query(int x) {
    return query(x, 1, min_x, max_x);
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  long long c;
  cin >> n >> c;
  vector<int> h(n);
  for(int i = 0; i < n; ++i) {
    cin >> h[i];
  }
  vector<long long> dp(n);
  LiChaoTree<long long> lc(0, 1000009);
  lc.insert({2ll * h[0], -dp[0] - 1ll * h[0] * h[0]});
  for(int i = 1; i < n; ++i) {
    dp[i] = 1ll * h[i] * h[i] + c - lc.query(h[i]);
    lc.insert({2ll * h[i], -dp[i] - 1ll * h[i] * h[i]});
  }
  cout << dp[n - 1] << '\n';
}

Measured memory_bytes: 65152
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int result = 0;

		if(A < B) {
			if(B < C) {
				result = C * 10 + B + A;
			} else {
				result = B * 10 + C + A;
			}
		} else {
			if(A < C) {
				result = C * 10 + B + A;
			} else {
				result = A * 10 + B + C;
			}
		}

		System.out.println(result);

		return;
	}

}


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

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

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



int main()
{
   int64_t A, B;
   cin >> A >> B;
   cout << lcm(A,B) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define st first
#define nd second 

using  namespace std;
using pii = pair<int, int>;
using ll = long long;
int a[15][1005], bit[15], choc[15], val[15];
char s[1005];
int bf(int h, int w, int k, int ch){
	int n = 0;
	for(int i = 0; i < h - 1; i++){
		if((1 << i) & ch) {
			n++;
			bit[n] = i + 1;
		}
	}
	n++;
	bit[n] = h;
	int cnt = n - 1;
	for(int i = 0; i <= n; i++) choc[i] = 0;
	for(int i = 1; i <= w; i++){
		bool io =false;
		for(int j = 1; j <= n; j++){
			val[j] = 0;
			for(int ii = bit[j-1] + 1; ii <= bit[j]; ii++){
				val[j] += a[ii][i];
			}
			if(val[j] > k) return 1e9 + 7;
			if(choc[j] + val[j] > k){
				io = true;
			}
		}
		if(io) cnt++;
		for(int j = 1; j <= n; j++){
			if(io) choc[j] = 0;
			choc[j] += val[j];
		}
	}
	return cnt;
}
int main(){
	int h, w, k;
	scanf("%d%d%d",&h, &w, &k);
	for(int i = 1; i <= h; i++){
		scanf("%s", s + 1);
		for(int j = 1; j <= w; j++){
			a[i][j] = s[j] - '0';
		}
	}
	int mi = 1e9 + 7;
	for(int i = 0; i <= (1 << h-1) - 1; i++){
		mi = min(mi, bf(h, w, k, i));
	}
	printf("%d",mi);

}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int A[210000],n,m,B[210000],ans[210000],tot;
void add(int k1,int k2,int k3,int k4,int k5,int k6){
	ans[k4]+=k6; ans[k5+1]-=k6;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&A[i]); B[A[i]]++;
	}
	for (int i=1;i<=n;i++){
		int l=i-B[i]; if (l<i) add(1,1,n,max(1,l+1),i,1);
	}
	for (int i=1;i<=n;i++) ans[i]=ans[i-1]+ans[i];
	for (int i=1;i<=n;i++) tot+=(ans[i]==0);
	for (;m;m--){
		int k1,k2; scanf("%d%d",&k1,&k2);
		int pre=A[k1]; int l=pre-B[pre]+1;
		if (l>0){
			ans[l]--; if (ans[l]==0) tot++;
		}
		B[pre]--;
		l=k2-B[k2];
		if (l>0){
			ans[l]++; if (ans[l]==1) tot--;
		}
		B[k2]++; A[k1]=k2;
		printf("%d\n",tot);
	}
	return 0;
}

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

void main()
{
    long n;
    readf("%d\n", &n);
    auto as = readln.strip.split.to!(long[]);
    auto xs = new string[](n);

    foreach (i, a; as)
    {
        xs[a - 1] = to!string(i + 1);
    }
    writeln(xs.join(" "));

}


Measured memory_bytes: 10220
N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
card_dict = {}
for a in A_LIST:
    if a in card_dict:
        card_dict[a] += 1
    else:
        card_dict[a] = 1
for b, c in BC_LIST:
    if c in card_dict:
        card_dict[c] += b
    else:
        card_dict[c] = b
card_list = sorted(card_dict.items(), reverse=True, key=lambda x: x[0])
ans = 0
remaining = N
for num, cnt in card_list:
    ans += num * min(cnt, remaining)
    remaining -= min(cnt, remaining)
    if remaining == 0:
        break
print(ans)


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


int main(){
    ll n;
    cin >> n;
    ll cntr = 0, i=10;
    if(n%2){
    	cout << "0";
        return 0;
	}
        
    else
        cntr+=n/i;
        while(i<=n){
            i*=5;
            cntr+=n/i;
        }
    
    cout << cntr;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;
 
// debugger
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
// 
 
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 
 
#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define len length
#define ret0 return 0
#define ret return 
 
 
#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)
 
#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>
 
// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;
 
#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)2e5+5
#define N (1ll<<10)
#define pi 3.141592653589793238462643

ll ceil(ll a,ll b){
    return a/b+(a%b!=0);
}

void solve(){
    ll a, b;
    cin>>a>>b;
    cout<<ceil(a, b)<<endl;
}   
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
 
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }

}


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

int n, m, A[1000001], sz, add, ans;
set<int> s;
int main() {
	cin >> n;
	A[0] = n;
	s.insert(A[0]);
	rep(i, 1000002) {
		A[i] = (A[i - 1] % 2 == 0 ? A[i - 1] / 2 : 3 * A[i - 1] + 1);
		sz = s.size();
		s.insert(A[i]);
		if (sz == s.size()) {
			cout << i + 1 << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100

void swap(int *,int *);

int main(){
  int n,A[N];
  int i,j,flag=0,change=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  flag=1;
  i=0;
  while(flag){
    flag=0;
    for(j=n-1;j>=i+1;j--){
      if(A[j]<A[j-1]){
	swap(&A[j],&A[j-1]);
	change++;
	flag=1;
      }
    }
    i++;
  }
  for(i=0;i<n-1;i++) printf("%d ",A[i]);
  if(i==n-1)printf("%d\n",A[i]);
  printf("%d\n",change);
  return 0;
}

void swap(int *a,int *b){
  int tmp;
  tmp=*a;
  *a=*b;
  *b=tmp;
}

Measured memory_bytes: 600
#include <stdio.h>
 
int main(void)
{
    int n;
    int a[100];
    int b[100];
    int c[100] = {};
    int i = 0;
    int j, k;
    int max;
     
    while(scanf("%d", &a[i]) != EOF) {
        i++;
    }
     
    for(j = 0; j < 100; j++) {
        b[j] = j + 1;
    }
    for(j = 0; j < 100; j++) {
        for(k = 0; k < i; k++) {
            if(b[j] == a[k]) c[j]++;
        }
    }
    max = c[0];
    for(j = 1; j < 100; j++) {
        if(c[j] > max) max = c[j];
    }
    for(j = 0; j < 100; j++) {
        if(c[j] == max) printf("%d\n", b[j]);
    }
    return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<ll>())
#define ll long long
#define ld long double
#define rep(i, s, g) for (ll i = (s); i < (g); i++)
#define mod 1000000007
#define vfind(v, target) find(v.begin(), v.end(), target)
#define notFound(v, target) (vfind(v, target) == v.end())

using namespace std;

int main()
{
  ll A, V, B, W, T;
  cin >> A >> V >> B >> W >> T;
  if (abs(A - B) <= T * (V - W)) {
  	cout << "YES" << endl;
  } else {
  	cout << "NO" << endl;
  }
}

Measured memory_bytes: 3636
program main
  implicit none
  integer :: a, b, x
  real(8) :: theta, p, q, pi
  pi = acos(-1.0d0)
  read (*, *) a, b, x
  if (2 * x >= a * a * b) then
    p = 2.0d0 * b - 2.0d0 * x / a ** 2
    theta = atan2(p, dble(a))
  else
    q = 2.0d0 * x / (a * b)
    theta = atan2(dble(b), q)
  end if
  write (*, "(f12.8)") theta * 180.0d0 / pi
  contains
end program main


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

int main(){
  int N;
  cin >> N;
  vector<int> maxA(N);
  vector<int> B(N-1);
  for (int i=0;i<N-1;i++){
    cin >> B.at(i);
  }
  int ans=0;
  for (int i=0;i<N;i++){
    if (i==0){
      maxA.at(i)=B.at(0);
      ans+=maxA.at(i);
    }
    else if (i==N-1){
      maxA.at(i)=B.at(N-2);
      ans+=maxA.at(i);
    }
    else{
      maxA.at(i)=min( B.at(i-1), B.at(i) );
      ans+=maxA.at(i);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
  using namespace std;
 
int main(){
  int N;
  cin>>N;
  vector<int> H(N);
  for(int i=0; i<N; i++){
    cin>>H.at(i);
  }
  int maxi=0;
  for(int i=0;i<N-1;i++){
    int count = 0;
    int checking = i;
    bool canLoop = true;
    while(canLoop){
      if(H.at(checking)>=H.at((checking)+1)){
        count++;
        checking++;
        if(checking==N-1){
          canLoop = false;
        }
      }else{
        canLoop = false;
      }
      maxi = max(maxi,count);
    }
    if(maxi>=(N-i)){
      break;
    }
  }
  cout<<maxi<<endl;
}

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


int main(){   
    int h,w,K;
    cin >> h >> w >> K;
    vector<string> c(h);
    rep(i,h) cin >> c[i];
    int ans = 0;
    rep(k,1 << (h+w)){
        int black = 0;
        int k2 = k >> w;
        rep(i,h) rep(j,w){
            int a = (k >> j)&1;
            int b = (k2 >> i)&1;
            if(!a && !b && c[i][j] == '#') ++black;
        }
        if(black == K) ++ans;
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 3604
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()



a, b = map(int, input().split())

ans = 0
if (a > 0 and b < 0) or (a < 0 and b > 0):
	ans += 1
	ans += abs(abs(a) - abs(b))
elif a == 0:
	if b >= 0:
		ans = b
	else:
		ans = abs(b) + 1
elif b == 0:
	if a <= 0:
		ans = abs(a)
	else:
		ans = abs(a) + 1
elif a > 0 and b > 0:
	if a <= b:
		ans = b - a
	else:
		ans = a - b + 2
elif a < 0 and b < 0:
	if a <= b:
		ans = abs(b - a)
	else:
		ans = abs(b - a) + 2

print(ans)


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

int n,q,i,j,a[200005],b[200005],p[200005];
vector<int> v[200005];
long long x[200005],y[200005]={0};
bool used[200005]={0};

void dfs(int node){
	used[node]=true;
	for(int ii=0;ii<v[node].size();ii++){
		if(!used[v[node][ii]]){
			y[v[node][ii]]+=y[node];
			dfs(v[node][ii]);
		}
	}
}

int main() {
	// your code goes here
	cin >> n >> q;
	for(i=0;i<n-1;i++){
		cin >> a[i] >> b[i];
		v[b[i]].push_back(a[i]);
		v[a[i]].push_back(b[i]);
	}
	for(i=0;i<q;i++){
		cin >> p[i] >> x[i];
		y[p[i]]+=x[i];
	}
	dfs(1);
	for(i=1;i<=n;i++){
		cout << y[i];
		if(i!=n) cout << " ";
		else cout << endl;
	}
	return 0;
}


Measured memory_bytes: 28416
n = int(input())
a = list(map(int, input().split()))
max_ans = 0
min_ans = 0
colors = [False] * 8
for i in range(n):
    rate = a[i]
    if 1 <= rate and rate < 400:
        colors[0] = True
    elif rate < 800:
        colors[1] = True
    elif rate < 1200:
        colors[2] = True
    elif rate < 1600:
        colors[3] = True
    elif rate < 2000:
        colors[4] = True
    elif rate < 2400:
        colors[5] = True
    elif rate < 2800:
        colors[6] = True
    elif rate < 3200:
        colors[7] = True
    else:
        max_ans += 1
min_ans += colors.count(True)
max_ans += colors.count(True)
print(max(min_ans, 1), max_ans)

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

int main(){
    ll a, b, c;
    cin >> a >> b >> c;
    if(max({a, b, c}) == a + b + c - max({a, b, c})) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int x[]=new int[n];
        int y[]=new int[n];
        for(int i=0;i<n;i++){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }
        double total=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                total+=(double)Math.sqrt(Math.pow(x[i]-x[j],2)+Math.pow(y[i]-y[j],2));
            }
        }
        System.out.println((double)total*2/n);

    }
}

Measured memory_bytes: 23636
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author YahiaAshraf74
 */

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <complex>
#include <string>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <fstream>
#include <iomanip>
#include <assert.h>

using namespace std;
#define el  '\n'
#define ll long long
#define clr(a, b)memset(a,b,sizeof(a))
#define sz(a) (int)(a).size()
const long long N = 2e5 + 74, OO = 0x3f3f3f3f, MOD = (long long) 1e9 + 7;

class CABSubstrings {
public:
    void solve(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int ba = 0, a = 0, b = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            if (s[0] == 'B' && s[sz(s) - 1] == 'A') {
                ++ba;
            } else if (s[sz(s) - 1] == 'A') {
                ++a;
            } else if (s[0] == 'B') {
                ++b;
            }
            for (int j = 0; j < sz(s) - 1; j++) {
                if (s[j] == 'A' && s[j + 1] == 'B')
                    ++ans;
            }
        }
        if (ba > 1) {
            ans += (ba - 1);
            if (a > 0)
                ++ans, --a;
            if (b > 0)
                ++ans, --b;
        } else if (ba == 1) {
            if (a > 0)
                ++ans, --a;
            if (b > 0)
                ++ans, --b;
        }
        ans += min(a, b);
        cout << ans << el;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    CABSubstrings solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


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

int partition(short*,int,int);
int main()
{
  unsigned short *A;
  int n,i,s;
  scanf("%d",&n);

  A = malloc(sizeof(short)*n+1);

  for(i=0;i<n;i++)
    {
      scanf("%d",A+i);
    }
  s = partition(A,0,n-1);

  for(i=0;i<n;i++)
    {
      if(i==s)
        printf("[%d]",*(A+i));
      else
        printf("%d",*(A+i));
      if(i<n-1)
        printf(" ");
    }
  printf("\n");

  return 0;
}
int partition(short *A,int p,int r)
{
  int x,a,i,j;
  x = A[r];
  i = p-1;

  for(j=p;j<r;j++)
    {
      if(A[j]<=x){
        i++;
        a = A[j];
        A[j] = A[i];
        A[i] = a;
      }
    }
  a=A[i+1];
  A[i+1]=A[r];
  A[r]=a;

  return i+1;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    int ans = 0;
    N -= K;
    ans++;
    while (true){
        if (N <= 0){
            break;
        }
        else{
            N -= (K - 1);
            ans++;
        }
    }
    cout << ans << endl;
}

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

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    
    string S;
    int N;
    cin >> S;
    N = S.length();
    
    int end = ((N-1)/2)-1;
    for(int i=0; i <= (end/2); ++i)
    {
    	if(S[i] != S[end-i])
		{    		
    		cout << "No" <<endl;
			return 0;	
		}
	}
	end = N-1;
	int start = (N+3)/2-1;
	for(int i=0; i < (N-1)/4; ++i)
    {
    	if(S[start+i] != S[end-i])
		{    		
    		cout << "No" <<endl;
			return 0;	
		}
	}
	end = N-1;
    for(int i=0; i < (N-1)/2; ++i)
    {
    	if(S[i] != S[end-i])
		{    		
    		cout << "No" <<endl;
			return 0;	
		}
	}
    
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
while True:
    H, W = map(int, input().split())
    if H == 0 and W == 0:
        break
    else:
        for h in range(H):
            # hが偶数の時、＃から出力を始める（0, 2, 4, ...)
            if h % 2 == 0:
                for w in range(W):
                    if w % 2 == 0:
                        print("#", end="")
                    else:
                        print(".", end="")
                print()
            # 縦が偶数の時、.から出力を始める（1, 3, 5, ...)
            else:
                for w in range(W):
                    if w % 2 == 0:
                        print(".", end="")
                    else:
                        print("#", end="")
                print()
        # データセットの後に空行を出力
        print()



Measured memory_bytes: 7000
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
#define ll long long
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
    string S,T;
    cin>>S>>T;
    int ssiz=S.size();
    int tsiz=T.size();
    int ans=1000;
    int cnt=0;
    rep(i,S.size()-tsiz+1){
        cnt=0;
        string tmp=S.substr(i,tsiz);
        rep(j,tsiz){
            if(tmp[j]!=T[j]){
                cnt++;
            }
        }
        ans=min(ans,cnt);
    }
cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <cstdlib>
#define ll long long
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define MX 100010
using namespace std;

int A,B,C;
int main(){
        cin >> A >> B >> C;
        if(A*C < B){
                cout << C << endl;
        }else{
                cout << B/A << endl;
        }
       
        return 0;
}


Measured memory_bytes: 256
li = list(map(int, input()))
for bit in range(1 << 3):
    ans = li[0]
    op = ["-"] * 3
    for i in range(3):
        if bit & (1 << i):
            ans += li[i+1]
            op[i] = "+"
        else:
            ans -= li[i+1]
    if ans == 7:
        print("{}{}{}{}{}{}{}=7".format(li[0],op[0],li[1],op[1],li[2],op[2],li[3]))
        exit()

Measured memory_bytes: 38384
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long N = n;
        int m = sc.nextInt();
        ArrayList<Bridge> bl = new ArrayList<Bridge>();
        long[] ans = new long[m];
        final long ANS = N*(N-1)/2;
        for(int i = 0; i < m; i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            Bridge br = new Bridge(a, b);
            bl.add(br);
        }
        Collections.reverse(bl);
        UnionFindTree uft = new UnionFindTree(n);
        long cnt = 0;
        ans[m-1] = ANS;
        for(int i = 0; i < bl.size()-1; i++){
            Bridge br = bl.get(i);
            int a = br.getA();
            int b = br.getB();
            if(!uft.same(a,b)){
                cnt += (long)uft.getSize(a)*(long)uft.getSize(b);
                uft.union(a,b);
            }
            ans[m-2-i] = ANS-cnt;
        }
        for(int i = 0; i < m; i++){
            System.out.println(ans[i]);
        }
    }
}
 
class Bridge{
    private int a;
    private int b;
    public Bridge(int a, int b){
        this.a = a;
        this.b = b;
    }
    public int getA(){
        return this.a;
    }
    public int getB(){
        return this.b;
    }
}
 
class UnionFindTree {
	int[] parent; //インデックスにとノードを対応させ、そのルートノードのインデックスを格納	
	int[] rank; //parentと同様に、木の高さを格納
	int[] size;
	
	public UnionFindTree(int size) {
		this.parent = new int[size];
		this.rank = new int[size];
		this.size = new int[size];
		for (int i = 0; i < size; i++) {
			makeSet(i);
		}
	}
	
	public void makeSet(int i) {
		parent[i] = i;
		rank[i] = 0; //集合の高さ
		size[i] = 1;
	}
	
	public void union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		int siz = size[xRoot] + size[yRoot]; 
		//xが属する木の方が大きい場合
		if (rank[xRoot] > rank[yRoot]) { 
			parent[yRoot] = xRoot; //yの親をxに更新 
			size[xRoot] = siz;
								   
		} else if(rank[xRoot] < rank[yRoot]) {
			parent[xRoot] = yRoot;
			size[yRoot] = siz;
			
		} else if (xRoot != yRoot){
			parent[yRoot] = xRoot;
			rank[xRoot]++; //同じ高さの木がルートの子として着くから大きさ++;
			size[xRoot] = siz;
		}
		//System.out.println("x:" + x +"  y:" + y + "  size[x]:" + size[x] + "  size[y]:" + size[y]);
		
	}
	
	//引数の属する木のルートのidを返す
	public int find(int i) {
		if (i != parent[i]) {
			parent[i] = find(parent[i]);
		}
		return parent[i];
	}
	
	//同じ木に属しているか
	public boolean same(int x, int y) {
		return find(x) == find(y);
	}
	
	public int getSize(int x){
	    return size[parent[x]];
	}
}

Measured memory_bytes: 99264
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <stack> 
#include <sstream>
#include <set>

typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}

using namespace std;
ll k (ll a){
    a--;
    ll ans =0;
    while(a != 0){
        ans += a;
        a--;
        
    }
    return ans;
}


int main(){
    int a,b;
    cin >> a >> b;

    b *=2;
    if(a <= b){
        cout << 0 <<endl;
    }else{
        cout << a - b  <<endl;
    }
}



Measured memory_bytes: 256
from math import sqrt
from itertools import combinations

N,D = map(int,input().split())
def dist(x,y):
  d=0
  for i in range(D):
    d += (x[i]-y[i])**2
  return d
X = [list(map(int,input().split())) for i in range(N)]

ans=0
for i,j in combinations(range(N),2):
  d = dist(X[i],X[j])
  if d == round(sqrt(d))**2:
    ans+=1

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long int
#define ff first
#define ss second
#define eps 1e-9

using namespace std;

int main()
{

    ll t,n,m,f,a,b,c,d,l,r,q,k,x,y,z,ans,mn,mx,sum=0;
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);


    cin>>n;
    string exp;


    a=b=c=d=0;
    for(int i=0;i<n;i++)
    {
        cin>>exp;

        if(exp[0]=='A')
        {
            a++;
        }
        else if(exp[0]=='W')
        {
            b++;
        }
        else if(exp[0]=='T')
        {
            c++;
        }
        else{
            d++;
        }
    }

    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<b<<endl;
    cout<<"TLE x "<<c<<endl;
    cout<<"RE x "<<d<<endl;
}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 45000;
int x;
bool Check(int t)
{
	return (t * t + t) >= x;
}
int main(int argc, char const *argv[])
{
	scanf("%d" , &x);
	x <<= 1;
	int l = 0 , r = MAXN;
	int ans = 0;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(Check(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	printf("%d\n" , ans);
	return 0;
}


Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

template <class InputIterator, class T>
bool contains(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// =========ここまでテンプレ============

int main()
{
    ll k, a, b;
    cin >> k >> a >> b;
    string ans = "NG";
    for (ll i = a; i <= b; i++)
    {
        if (i % k == 0)
            ans = "OK";
    }
    cout << ans;
}

Measured memory_bytes: 3104
# AOJ ALDS1_5_D "The Number of Inversions"
# 転倒数をO(NlogN)で求める

N = int(input())
A = list(map(int, input().split()))

# binary indexed tree
bit = [0 for _ in range(N+1)]

# 0からiまでの区間和
# 立っているビットを下から処理
def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

# i番目の要素にxを足す
# 覆ってる区間すべてに足す
def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i

# 座標圧縮
ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i+1

# それまでに「i<=jかつai<=aj」となっているものをBITに加えていく
ans = 0
for j, a in enumerate(A):
    ind_a = co_to_ind[a]
    ans += j - query_sum(ind_a)
    add(ind_a, 1)

print(ans)


Measured memory_bytes: 39900
#include <cstdio>
#include <iostream>
using namespace std;
const int Q=1<<10;
int gg[Q];
int f[2][Q][Q];
int a[Q];
const int MOD=1e9+7;
inline int mul(int a,int b)
{return 1LL*a*b%MOD;}
int fac(int x)
{
    int tmp=1;
    for(int i=1;i<=x;i++)
        tmp=mul(tmp,i);
    return tmp;
}
inline void Add(int &a,int b)
{a+=b;a>=MOD?a-=MOD:1;}
int main()
{
    int n,ct=0;
    scanf("%d",&n);
    for(int i=1,a,b;i<=n;i++){
        scanf("%d%d",&a,&b);
        if(a>-1&&b>-1){
            gg[a]=gg[b]=-1;
        }
        else if(a==-1&&b==-1)++ct;
        else gg[a+b+1]=1;
    }
    n<<=1;
    f[0][0][0]=1;
    int now=0,lst=1;
    for(int i=n;i;--i){
        if(gg[i]<0)continue;
        now^=1,lst^=1;
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                f[now][j][k]=0;
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++){
                int v=f[lst][j][k];
                if(gg[i]==1){
                    Add(f[now][j][k+1],v);
                    if(j)Add(f[now][j-1][k],v);
                }
                else{
                    Add(f[now][j+1][k],v);
                    if(j)Add(f[now][j-1][k],v);
                    if(k)Add(f[now][j][k-1],mul(k,v));
                }
            }
    }
    printf("%d",mul(f[now][0][0],fac(ct)));
    return 0;
}
/*
3
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1


*/

Measured memory_bytes: 8448
#include <iostream>
#include <string>

using namespace std;

int main(){

  int i;
  string S,T,U;
  
  //cin>>S>>T;
  cin>>S;
  //cin>>U;

  //  cout<<S<<endl;
  
    for(i=0;i<S.length();i++){
      //     cout<<i<<S[i]<<endl;
  }
    for(i=0;i<S.length()-1;i++){
      if(S[2]==S[3] and S[4]==S[5]){
    cout<<"Yes"<<endl;
    return 0;
  }
  }
  cout<<"No"<<endl;
  return 0;
}


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

int main(){
    int N; cin >> N;
    string S; cin >> S;
    int A[N];
    A[0] = 0;

    for(int i = 1; i < N; i++){
        if(S[i] == 'E') A[0]++;
    }
    for(int i = 1; i < N; i++){
        A[i] = A[i-1];
        if(S[i-1] == 'W') A[i]++;

        if(S[i] == 'E') A[i]--;
    }

    int ans = N;
    for(int i = 0; i < N; i++){
        // cout << A[i] << endl;
        ans = min(A[i], ans);
    }

    cout << ans << endl;
    
    
    return 0;
}

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

int main() {
  long H;
  cin >> H;

  long ans = 0, breadth = 1;
  for (long i = H; 0 < i; i /= 2) {
    ans += breadth;
    breadth *= 2;
  }

  cout << ans << endl;
  return 0;
}


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

lint f(lint a, lint b) {
    return a * a * a * a * a - b * b * b * b * b;
}

int main() {
    lint x;
    cin >> x;
    lint limit = 3000;
    for (lint i = -limit; i <= limit; i++) {
        for (lint j = -limit; j <= limit; j++) {
            if (f(i, j) == x) {
                cout << i << ' ' << j << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3676
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<ll> _size; // 属する連結成分の大きさ

    UnionFind(ll N) : par(N), _size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) {
            par[i] = i;
            _size[i] = 1;
        }
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        _size[ry] += _size[rx];
    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }

    ll size(ll x){
        ll rx = root(x);
        return _size[rx];
    }
};

int main() {

    int N, M;
    cin >> N >> M;
    vector<P> v(M);
    REP(i, M){
        cin >> v[i].first >> v[i].second;
        v[i].first--;
        v[i].second--;
    }
    ll ans = 0;
    REP(i, M){
        UnionFind u = UnionFind(N);
        REP(j, M){
            if (i != j) u.unite(v[j].first, v[j].second);
        }
        if (u.size(0) != N) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ld long double
#define MN 205
#define eps 1e-9
using namespace std;
const ld pi=acos(-1);
struct vec
{
	ld x,y; int pos;
	friend vec operator-(const vec& a,const vec& b) {return (vec){a.x-b.x,a.y-b.y};}
	friend ld operator/(const vec& a,const vec& b) {return a.x*b.y-a.y*b.x;}
	friend ld operator*(const vec& a,const vec& b) {return a.x*b.x+a.y*b.y;}
	friend ld abs(const vec& a) {return sqrt(a.x*a.x+a.y*a.y);}
}a[MN];
ld ans[MN];
int q[MN];
int n,tp;

inline int read()
{
	int n=0,f=1; char c=getchar();
	while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
	while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
	return n*f;
}

bool cmp1(const vec& a,const vec& b) {return a.x<b.x || a.x==b.x && a.y<b.y;}
bool cmp2(const vec& A,const vec& B)
{
	ld lt=(A-a[1])/(B-a[1]);
	if (fabs(lt)>eps) return lt>0;
	else return abs(A-a[1])<abs(B-a[1]);
}

int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	register int i;
	n=read();
//	printf("%d\n",n);	
	for (i=1;i<=n;++i)
		a[i].x=read(),a[i].y=read(),a[i].pos=i;
	if (n==1) return 0*printf("1");
	else if (n==2) return 0*printf("0.5000000\n0.5000000");
	sort(a+1,a+n+1,cmp1);
	sort(a+2,a+n+1,cmp2);
	q[tp=1]=1;
	for (i=2;i<=n;++i)
	{
		while (tp>1&&(a[q[tp]]-a[q[tp-1]])/(a[i]-a[q[tp-1]])<eps) --tp;
		q[++tp]=i;
	}
	q[tp+1]=q[1]; q[0]=q[tp];
//	for (i=1;i<=tp;++i) printf("%lld,%lld\n",a[q[i]].x,a[q[i]].y);	
//	for (i=1;i<=tp;++i) printf("%d ",a[q[i]].pos); puts("");
//	printf("%d\n",tp);
//	printf("%d %d\n",n,tp);
	for (i=1;i<=tp;++i)
	
	{
	
		ans[a[q[i]].pos]=
		(pi-acos((double)(
		((a[q[i-1]]-a[q[i]])*
		(a[q[i+1]]-a[q[i]]))
		/(abs(a[q[i-1]]-a[q[i]])*
		  abs(a[q[i+1]]-a[q[i]])))))/(pi*2);
//	printf("%.5lf\n",acos(
//		((a[q[i-1]]-a[q[i]])*
//		(a[q[i+1]]-a[q[i]]))
//		/(abs(a[q[i-1]]-a[q[i]])*
//		  abs(a[q[i+1]]-a[q[i]]))));
	}
	
	for (i=1;i<=n;++i) printf("%.10lf\n",(double)ans[i]);
}

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, a, b;
    cin >> x >> a >> b;
    if (abs(x - a) <= abs(x - b)) {
        cout << "A" << "\n";
    } else {
        cout << "B" << "\n";
    }
}









Measured memory_bytes: 3504
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define all(x) (x).begin(),(x).end()

using ll = long long;

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

	vector<ll> switches(M);

	rep(i, M)
	{
		int L;
		cin >> L;

		ll b = 0;
		rep(j, L)
		{
			int s;
			cin >> s;

			b |= 1ll << (s - 1);
		}

		switches[i] = b;
	}

	vector<int> p(M);
	rep(i, M)
	{
		cin >> p[i];
	}

	ll ans = 0;
	for (ll i = 0; i < (1ll << N); i++)
	{
		int on_count = 0;

		rep(j, M)
		{
			ll bi = switches[j] & i;
			int count = 0;
			while (bi > 0)
			{
				if (bi & 1)
				{
					count++;
				}

				bi >>= 1;
			}

			if (count % 2 == p[j])
			{
				on_count++;
			}
		}

		if (on_count == M)
		{
			ans++;
		}
	}
	
	cout << ans << endl;

	return 0;
}


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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, s, t;
	cin >> n >> k >> s >> t;
	vector<vector<long long>> dp(n + 1, vector<long long> (k + 1, 0));
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= k; j++) {
			dp[i + 1][j] += dp[i][j];
			if (j + 1 <= k) dp[i + 1][j + 1] += dp[i][j];
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 2; j <= k; j++) {
			dp[i][j] += dp[i][j - 1];
		}
	}
	vector<int> old_a(n);
	for (int i = 0; i < n; i++) {
		cin >> old_a[i];
	}
	if ((s & t) != s) {
		cout << "0\n";
		return 0;
	}
	vector<int> a;
	for (int i = 0; i < n; i++) {
		if ((old_a[i] & s) != s || (old_a[i] & t) != old_a[i]) continue;
		a.push_back(old_a[i]);
	}
	n = a.size();
	long long ans = 0;
	for (int i = 0; i < (1 << 18); i++) {
		if ((i & s) || (i & t) != i) continue;
		int sign = __builtin_popcount(i);
		if (sign & 1) sign = -1;
		else sign = 1;
		vector<int> cur;
		for (int j = 0; j < n; j++) {
			cur.push_back(a[j] & i);
		}
		sort(cur.begin(), cur.end());
		for (int j = 0, x = 0; j < n; j = x) {
			for (; x < n && cur[x] == cur[j]; x++);
			ans += dp[x - j][k] * sign;
		}
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3680