akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

const int MAX_N = 15;
ll X[MAX_N], Y[MAX_N], P[MAX_N];

const ll INF = 1LL << 61;
ll ans[MAX_N];
int N;
ll cx[1 << MAX_N][MAX_N];
ll cy[1 << MAX_N][MAX_N];

const ll BIG = 1e9;
void calcX(int s) {
  if (cx[s][0] != -1) return;

  vector<ll> xs;
  xs.push_back(0); xs.push_back(-BIG); xs.push_back(BIG);
  REP(i, N) if (s >> i & 1) xs.push_back(X[i]);
  sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end());
  REP(i, N) {
    auto it = lower_bound(ALL(xs), X[i]);
    ll xx = min(abs(X[i] - *it), abs(X[i] - *(prev(it))));
    cx[s][i] = xx;
  }
}
void calcY(int s) {
  if (cy[s][0] != -1) return;
  vector<ll> xs;
  xs.push_back(0); xs.push_back(-BIG); xs.push_back(BIG);
  REP(i, N) if (s >> i & 1) xs.push_back(Y[i]);
  sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end());
  REP(i, N) {
    auto it = lower_bound(ALL(xs), Y[i]);
    ll xx = min(abs(Y[i] - *it), abs(Y[i] - *(prev(it))));
    cy[s][i] = xx;
  }
}

int main2() {

  CLR(cx, -1);
  CLR(cy, -1);

  N = nextLong();
  REP(i, N) {
    X[i] = nextLong();
    Y[i] = nextLong();
    P[i] = nextLong();
  }

  REP(i, N+1) ans[i] = INF;

  {
    ll val = 0;
    REP(i, N) val += P[i] * min(abs(X[i]), abs(Y[i]));
    ans[0] = val;
  }

  const int L = pow(3, N);
  for (int l = 0; l < L; l++) {
    int s = 0;
    int t = 0;

    int k = 0;
    int tmp = l;
    REP(i, N) {
      if (tmp % 3 == 1) { s |= (1 << i); k++; }
      if (tmp % 3 == 2) { t |= (1 << i); k++; }
      tmp /= 3;
    }
    calcX(s);
    calcY(t);

    ll val = 0;
    REP(i, N) {
      ll xx = cx[s][i];
      ll yy = cy[t][i];
      val += P[i] * min(xx, yy);
    }
    chmin(ans[k], val);
  }

  REP(i, N+1)
    cout << ans[i] << endl;

  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

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

    int N;
    cin >> N;
    vector<string> vs(N);
    for (int i = 0; i < N; i++) {
        cin >> vs[i];
    }

    Vi nums(26, I_INF);
    Vi cnts(26);
    for (int i = 0; i < N; i++) {
        cnts.assign(26, 0);
        for (const auto& c : vs[i]) {
            ++cnts[c - 'a'];
        }
        for (int i = 0; i < 26; i++) {
            nums[i] = min(nums[i], cnts[i]);
        }
    }

    string ans;
    for (int i = 0; i < 26; i++) {
        char c = 'a' + i;
        for (int j = 0; j < nums[i]; j++) {
            ans += c;
        }
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 256
n = int(input())
c = list(map(int, input().split()))
c.sort()
c_set = set(c)
set_list = list(c_set)
ans = 'No'

# 0が混ざっていれば計算方法が違う
if c.count(0) == n:
    ans = 'Yes'
elif c[0] == 0:
    if n % 3 == 0 and len(c_set) == 2 and c.count(0) == int(n / 3):
        ans = 'Yes'
elif n == 3:
    if c[0] ^ c[1] == c[2]:
        ans = 'Yes'
else:
    if n % 3 == 0 and len(c_set) == 3:
        ank = int(n / 3)
        if c.count(c[0]) == ank and c.count(c[ank]) == ank and set_list[0] ^ set_list[1] == set_list[2]:
            ans = 'Yes'

print(ans)




Measured memory_bytes: 14708
n = int(input())
original_list = list(map(int,input().split()))
maped_list = map(str, original_list)
print(' '.join(maped_list))
for i in range(1,n):
    v = original_list[i]
    j = i - 1
    while j >= 0 and original_list[j] > v:
        original_list[j+1] = original_list[j]
        j = j - 1
    original_list[j+1] = v
    maped_list = map(str,original_list)
    print(' '.join(maped_list))


Measured memory_bytes: 5596
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> set_t;
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pdd pair<double,double>
#define pb push_back
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-6
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
#define pi acos(-1)
#define index Index
#define Line pll
typedef long long LL;
char c[1005][1005];
int mod=1e9+7;
int dp[1005][1005];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",c[i]+1);
    }
    dp[1][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1&&j==1)continue;
            if(c[i][j]=='#')continue;
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            ///printf("%d ",dp[i][j]);
        }
       // printf("\n");
    }
    printf("%d\n",dp[n][m]);
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    vector<char> cs(n);
    int wcnt = 0;
    int rcnt = 0;
    for (int i = 0; i < n; i++)
    {

        cin >> cs[i];
        if (cs[i] == 'R')
        {
            ++rcnt;
        }
        else
        {
            ++wcnt;
        }
    }
    int ans = 0;
    for (int i = 0; i < rcnt; i++)
    {
        if (cs[i] == 'W')
        {
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
};

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm> // max(), min() を使用するのでインクルード

using namespace std;

int main(){
  /**
   * 考え方
   *  2人がスイッチを押している時間の計算
   *    BとDのうち小さい秒数 - AとCのうち大きい秒数
   *  まずは2人が押している時間を計算し、結果が0以下の場合は0を返すようにしてやる
   * ヒント
   *  max(a,b) : a, b のうち大きい方の数値を返す
   *  min(a,b) : a, b のうち小さい方の数値を返す
   */
  int a,b,c,d; //それぞれの秒数を定義
  cin >> a >> b >> c >> d; // 時間を受け取る
  int big = max(a,c); //アリスとボブのスイッチを押し始めた時間のうち、大きい方を取得
  int low = min(b,d); //アリスとボブのスイッチを離した時間のうち、小さい方を取得
  cout << max(0,low-big) << endl; //2人とも押している時間がある場合はその数値を、そうでない場合は「0」を結果として出力
}

Measured memory_bytes: 256
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
#A, B = [], []
#for i in range(N):
    #ai, bi = map(int, input().split())
    #A.append(ai)
    #B.append(bi)
AB = sorted(AB)

A, B = [], []
for a, b in AB:
    A.append(a)
    B.append(b)

sa = [0] * (N + 1)
sb = [0] * (N + 1)
for i in range(N):
    sa[i + 1] = sa[i] + B[i]
    sb[i + 1] = sb[i] + B[i] * A[i]

from bisect import bisect_left
aim = bisect_left(sa, M)

print(sb[aim] - A[aim - 1] * (sa[aim] - M))

Measured memory_bytes: 73688
#include <limits>
#include <iostream>
#include <cmath>
#include <set>
#include <vector>
#include <cstdint>
int main()
{
    while (true)
    {
        int a, b;
        std::cin >> a;
        std::cin >> b;
        if (a == 0 && b == 0)
        {
            break;
        }
        for (int i = 0; i < a; i++)
        {
            for (int j = 0; j < b; j++)
            {
                std::cout << "#";
            }
            std::cout << "\n";
        }
        std::cout << "\n";
    }
    return 0;
}


Measured memory_bytes: 3028
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>
#include<utility>

#define P 1000000007

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<long long> a(n), ans;
  map<long long, int> mp;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) {
    mp[a[i]]++;
    if(mp[a[i]] == 2) {
      mp[a[i]] = 0;
      ans.push_back(a[i]);
    }
  }
  if(ans.size() < 2) {
    cout << 0 << endl;
  } else {
    sort(ans.begin(), ans.end());
    cout << ans[ans.size() - 2] * ans[ans.size() - 1] << endl;
  }

  return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = (int)1e9+7;
const double PI = 3.14159265359;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	//ctrl + /cin>>t;
	t = 1;
	while(t--){
		int n;
		cin>>n;
		ll ans = 0;
		for(int i=1;i<=n;i++){
			if(i % 3 && i % 5)
				ans += i;
		}
		cout<<ans;
	}
	return 0;
}
































Measured memory_bytes: 3568
ina = input().split(" ")
stack = []
for i in ina:
    if i.isdecimal():
        stack.append(int(i))
    else:
        if i == "+":
            stack.append(int(stack.pop() + stack.pop()))
        elif i == "*":
            stack.append(int(stack.pop() * stack.pop()))
        elif i == "-":
            a = int(stack.pop())
            b = int(stack.pop())
            stack.append(b-a)

print(str(stack.pop()))



Measured memory_bytes: 5592
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
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 long long MOD = 1000000007;
const long long INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
map<int, int> mp;
using Graph = vector<vector<int>>; 
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))

int n, m, k[15], s[15], p[15];
vector<int>vec[15];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	rep(i, m) {
		cin >> k[i];
		rep(j, k[i]) {
			cin >> s[i];
			s[i]--;
			vec[s[i]].push_back(i);
		}
	}
	rep(i, m)cin >> p[i];
	int ans = 0;
	rep(i, ((ll)1 << n)) {
		int memo[15] = {};
		rep(j, n) {
			if ((i >> j) & 1) {
				for (int l : vec[j])memo[l]++;
			}
		}
		bool f = true;
		rep(j, m) {
			if (memo[j] % 2 != p[j])f = false;
		}
		if (f)ans++;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main(void){
	int n;
	int mi[7];
	memset(mi,0,sizeof(mi));
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		double ii;
		scanf("%lf",&ii);
		if(ii<165)mi[1]++;
		else if(ii<170)mi[2]++;
		else if(ii<175)mi[3]++;
		else if(ii<180)mi[4]++;
		else if(ii<185)mi[5]++;
		else mi[6]++;
	}
	for(int i=1;i<=6;i++){
		printf("%d:",i);
		for(int j=0;j<mi[i];j++)printf("*");
		printf("\n");
	}
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0;i < N;i++)
int main()
{
  int a,b,c;
  Rep(p,3) {
    cin >> a >> b >> c;
    int sum = a * 3600 + b * 60 + c;
    cin >> a >> b >> c;
    sum = (a * 3600 + b * 60 + c) - sum;
    cout << sum / 3600 << " " << (sum % 3600) / 60 << " " << sum % 60 << endl;
  }
  return 0;
}

Measured memory_bytes: 3044
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int Maxn = 1e5;

int N, K;
ll M;
vector<pair<int, int> > t;

int fa[Maxn + 5];
int find(int x) {
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

int main() {
#ifdef LOACL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d %lld %d", &N, &M, &K);
	for(int i = 1; i <= N; i++)
		fa[i] = i;
	for(int i = 1; i <= K; i++) {
		int u, v, typ;
		scanf("%d %d %d", &u, &v, &typ);
		u++, v++;
		if(typ == 0) {
			int fu = find(u), fv = find(v);
			if(fu != fv) fa[fu] = fv;
		} else t.push_back(make_pair(u, v));
	}
	int cnt = 0;
	for(int i = 1; i <= N; i++)
		if(i == find(i)) cnt++;
	ll mx = 1LL * cnt * (cnt - 1) / 2 + N - cnt;
	if(mx < M) {
		puts("No");
		return 0;
	}
	ll mn = (t.empty() ? N - 1 : N);
	if(mn > M) {
		puts("No");
		return 0;
	}
	for(int i = 0; i < (int)t.size(); i++)
		if(find(t[i].first) == find(t[i].second)) {
			puts("No");
			return 0;
		}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 1784
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

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

  int n;
  cin >> n;
  vector<ll> a(n);
  for (auto &x: a) cin >> x;

  ll maximum = 1000;
  vector<pair<ll, ll> > possibles;
  for (int i = 0; i < n; i++) {
    ll maximum_temp = maximum;
    for (auto [stock, rem]: possibles) {
      if (stock * a[i] + rem > maximum_temp) maximum_temp = stock * a[i] + rem;
    }
    possibles.emplace_back(maximum / a[i], maximum % a[i]);
    maximum = maximum_temp;
  }

  cout << maximum << endl;

  return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
using namespace std;

typedef pair<long long, int> P;
#define INF (1L<<50)

int N, M, C;
vector<P> edges[100100];
P D[100100];
bool dead[100100];
long long e;

int main() {
  cin >> N >> M >> C;
  for (int i=0; i<M; i++) {
    int a, b, d;
    cin >> a >> b >> d;
    edges[a-1].push_back(P(d, b-1));
    edges[b-1].push_back(P(d, a-1));
    e += d;
  }

  for (int i=0; i<N; i++) D[i] = P(INF, -1);

  priority_queue< P, vector<P>, greater<P> > q;
  D[0] = P(0, 0);
  q.push(D[0]);

  while (!q.empty()) {
    P p = q.top(); q.pop();
    int s = p.second;
    for (P p2 : edges[s]) {
      long long r = p2.first, t = p2.second;
      if (D[s].first + r < D[t].first) {
        D[t] = P(D[s].first + r, t);
        q.push(D[t]);
      }
    }
  }

  sort(D, D+N);
  long long ans = INF;
  for (int i=0; i<N; i++) {
    P p = D[i];
    long X = p.first, s = p.second;
    for (P t : edges[s]) {
      if (dead[t.second]) e -= t.first;
    }
    dead[s] = true;
    ans = min(ans, C*X + e);
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 18276
from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                if dpr[k][a] < b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] > b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 96288
// Aizu Vol-5 0543: Receipt
// 2017.8.31 bal4u@uu

#include <stdio.h>

int main()
{
	int s, k, a, i;

	while (scanf("%d", &s) && s) {
		for (k = i = 0; i < 9; i++) scanf("%d", &a), k += a;
		printf("%d\n", s - k);
	}
	return 0;
}

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

using ll = long long;

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

    int n;
    cin>>n;

    if(n==1)
    {
        cout<<1;
        return 0;
    }

    ll bans=1;
    ll ans=3;

    for(int i=2;i<n;i++)
    {
        ans=ans+bans;
        bans=ans-bans;
    }

    cout<<ans<<"\n";

    return 0;
}


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

int main(){
  ll h; cin >> h;
  ll cnt = 0;
  ll ans = 0;
  while(h>=pow(2,cnt)){
    ans+=pow(2,cnt);
    cnt++;
  }
  cout << ans << endl; 
  return 0;
}

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

int main(void){
    int n; cin >> n;
    string ans="";

    if(n==0){
        cout << 0 << endl;
        return 0;
    }
    
    int radix=2;
    int cnt=0;
    while(n!=0){
        if(n%2!=0){
            ans='1'+ans; n--;
        }
        else ans='0'+ans;

        n/=-2;
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// 01Trie BIT CHT DFT FFT avl cmd cusum dijkstra dinic geo2 gin graph kruskal lca lcm matrix ncm next_combination ppuf segtree st tmp topcoder uf vi 

using Weight = int;
using Flow = int;
struct Edge {
    int s, d; Weight w; Flow c;
    Edge() {};
    Edge(int s, int d, Weight w = 1) : s(s), d(d), w(w), c(w) {};
};
bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; }
bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; }
inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); }

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

void addArc(Graph &g, int s, int d, Weight w = 1) {
    g[s].emplace_back(s, d, w);
}
void addEdge(Graph &g, int a, int b, Weight w = 1) {
    addArc(g, a, b, w);
    addArc(g, b, a, w);
}

void bfs(Graph &g, vi &data, int p)
{
    deque<int> mmn;
    mmn.push_back(p);
    while (mmn.size()) {
        deque<int> mm;
        while (mmn.size()) {
            int x = mmn.front();
            mmn.pop_front();
            for (auto i : g[x]) {
                if (data[i.d] == -1) {
                    data[i.d] = data[x] + 1;
                    mm.pb(i.d);
                }
            }
        }
        mmn = mm;
    }
}

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

    int2(n, m);
    int2(s, t);

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int2(tmpx, tmpy);
        tmpx--; tmpy--;
        addEdge(g, tmpx, tmpy );
    }
    
    vi mmn(n, -1), mm(n, -1);
    mmn[s-1] = 0;
    mm[t-1] = 0;
    bfs(g, mmn, s-1);
    bfs(g, mm, t-1);

    map<int, int> funami, yui;
    rep(i, mmn.size()) {
        funami[mmn[i]]++;
    }
    rep(i, mm.size()) {
        yui[mm[i]]++;
    }

    int ans = 0;
    for (int i = 0; i < mmn[t-1]-1; i++) {
        ans += funami[i] * yui[mmn[t-1]-2-i];
    }

    std::cout << ans << std::endl;

    return 0;
}









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

int main(){
  long long N,A,B;
  cin>>N>>A>>B;
  if (A>B) cout << 0 << endl;
  else if (N==1) cout <<(A==B ? 1:0) <<endl;
  else cout <<(N-2)*(B-A)+1 <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int A, B;
	cin >> A >> B;
	int res = (B%A == 0) ? A + B : B - A;
	cout << res << "\n";

	return 0;
}

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

int main()
{
	int n, mini, res, R;
	cin >> n >> mini >> R;
	res = R - mini;
	mini = min(mini, R);
	for (int i = 2; i < n; i++) {
		cin >> R;
		res = max(res, R - mini);
		mini = min(mini, R);
	}
	cout << res << endl;
	return 0;
}



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

int main()
{
	long long n;
	long long ccf=LONG_LONG_MAX;
	scanf("%lld",&n);
	for(int i=1;i<=5;i++){
		long long sh;scanf("%lld",&sh);
		ccf=min(ccf,sh);
	}
	if(n%ccf)printf("%lld",n/ccf+5);
	else printf("%lld",n/ccf+4);
	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 X = sc.nextInt();
		int max = 0;

		if(X!=1){
			for(int b=2; b<Math.sqrt(X); b++){
				int p=2;
				int pow = (int) Math.pow(b,p);
				while(pow<=X){
					if(max<pow){
						max=pow;
					}
					p++;
					pow = (int) Math.pow(b,p);
				}
			}
		}else{
			System.out.println("1");
			return;
		}
		System.out.println(max);
    }
}

Measured memory_bytes: 20820
package main
import "fmt"
func main() {
  const mod int64 = 1000000007
  var n,i,a int64
  var p []int64
  fmt.Scan(&n)
  p = primes(n)
  m := map[int64]int64{}
  for i=2;i<=n;i++ {
    ii := i
    for ;ii>1; {
      for j:=0;j<len(p);j++ {
        if ii%p[j] == 0 {
          m[p[j]]++
          ii /= p[j]
          break
        }
      }
    }
  }
  a = 1
  for _,v := range m {
    a *= v+1
    a %= mod
  }
  //fmt.Println(p)
  //fmt.Println(m)
  fmt.Println(a)
}
func primes(n int64) []int64 {
  var p,q []int64
  var i,k int64
  p = make([]int64,n+1)
  for i=2;i<=n;i++ { p[i] = i }
  for i=2;i<=n;i++ {
    if p[i] == 0 { continue }
    for k=2;k*i<=n;k++ {
      p[k*i] = 0
    }
  }
  for i=2;i<=n;i++ {
    if p[i] == 0 { continue }
    q = append(q,p[i])
  }
  return q
}

Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// =======================================================

using namespace std;

// =======================================================

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

// =======================================================

//ライブラリ(*'▽')
int gcd(int a, int b) //最大公約数
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}

int lcm(int a, int b) //最小公倍数
{
	return a * b / gcd(a, b);
}

// =======================================================

int main() {
	int d, t, s;
	cin >> d >> t >> s;
	if (d <= t * s)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
bool DBG = true;
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
using ld = long double;
//using i128 = __int128_t;
//using bint = boost::multiprecision::cpp_int
//using d1024 = boost::multiprecision::number<mp::cpp_dec_float<1024>>;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define ALL(x) x.begin(),x.end()
#define fs first
#define sd second
#define couts(x) cout << (x) << (" ")
#define coutn(x) cout << (x) << ("\n")
#define endl "\n"
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define dcouts(x) if(DBG) couts(x)
#define dcoutn(x) if(DBG) coutn(x);
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T1, typename T2> std::istream &operator>>(std::istream &is, std::pair<T1,T2> &p){is >> p.first >> p.second; return is; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::deque<T> &vec){ os << "deque["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> std::ostream &operator<<(std::ostream &os, const std::map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> std::ostream &operator<<(std::ostream &os, const std::unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }

template<class T> using V = vector<T>;
template<class T> using V2 = V<V<T>>;
template<class T> using V3 = V<V2<T>>;



void solve(){
  int r;
  cin >> r;
  coutn(3*r*r);
}

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int K = 0;
    int A = 0;
    int B = 0;
    int i = 0;
    scanf("%d", &K);
    printf("\n");
    scanf("%d %d", &A ,&B);
    printf("\n");
    for (i = A;i <= B;i++) {
        if (i % K == 0) {
            printf("OK");
            break;
        }
        else if (i == B) {
            printf("NG");
        }
    }
    return 0;
}

Measured memory_bytes: 2156
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int> pii;
#define MAX 99999999
int main(){
    int n,m;
    while(cin>>n>>m,n+m){
        vi v(102,0);
        rep(i,n){
            int hoge; cin>>hoge;
            rep(j,hoge){int temp;cin>>temp; v[temp]++;}
        }
        bool flag=false;
        int ans=-INF; int num = 0;
        rep(i,102){
            if(v[i]>=m){if(ans<v[i]){ans=v[i];num=i;}}
            if(i==101&&ans==-INF)flag=true;
        }
        if(flag)cout<<0<<endl;
        else cout<<num<<endl;
    }
}

Measured memory_bytes: 2980
m,M,X,Y,x,y,i,j;
main(){ while(scanf("%d%d",&x,&y),x||y){
m=x*x+y*y,M=90000;
for(i=150;i;i--)for(j=i+1;j<=150;j++){y=i*i+j*j;if(m==y&&x<i)M=y,X=i,Y=j;else if(m<y&&M>=y)M=y,X=i,Y=j;}
printf("%d %d\n",X,Y);}return 0;}

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

int main() {
	int s;

	cin >> s;
	
	if (1 <= s / 100 && s / 100 <= 12 && (s % 100 < 1 || s % 100 > 12)) {
		cout << "MMYY" << endl;
	}
	else if (1 <= s % 100 && s % 100 <= 12 && (s / 100 < 1 || s / 100 > 12) ){
		cout << "YYMM" << endl;
	}
	else if (1 <= s / 100 && s / 100 <= 12 && 1 <= s % 100 && s % 100 <= 12) {
		cout << "AMBIGUOUS" << endl;
	}
	else {
		cout << "NA" << endl;
	}

	return 0;
}

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

int main(){
    int n,a,b,c,d; cin >> n >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;
    string s; cin >> s;
    int judge = 1; //岩が二つ並んだでいないか？
    int cnt = 0; //AがBを追い抜くことは可能か？

    //マスaからmax(c,d)までで岩が二つ並んだらダメ
    for(int i = a; i < max(c,d); i++){
        if(s[i] == '#' && s[i+1] == '#'){
            judge = 0;
            break;
        }
    }

    //c < bの場合、再判定
    if(c < b){
        judge = 1;
        for(int i = a; i < c; i++){
            if(s[i] == '#' && s[i+1] == '#'){
                judge = 0;
                break;
            }
        }
        for(int i = b; i < d; i++){
            if(s[i] == '#' && s[i+1] == '#'){
                judge = 0;
                break;
            }
        }
    }

    //空きマスが3つ並んでいれば追い越せる
    for(int i = b-1; i <= min(d-1,n-3); i++){
        if(s[i] == '.' && s[i+1] == '.' && s[i+2] == '.'){
            cnt = 1;
            break;
        }
    }

    if(c < d && judge == 1){ //c < dなら岩が二つ並ばなければ良い
        cout << "Yes" << endl;
    }else if(d < c && cnt == 1 && judge == 1){ //d < cの時追い抜く必要
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> m(N);
    for(int i = 0; i< N; i++){
        cin >> m.at(i);
        X -= m.at(i);
    }
    sort(m.begin(), m.end());
    cout << N + X / m.at(0) << endl;
}

Measured memory_bytes: 256
input_line = gets.to_i

arr = gets.chomp.split(" ").map(&:to_i)
puts arr.join(' ')

(input_line - 1).times do |i|
  v = arr[i + 1]
  j = i
  while j >= 0 && arr[j] > v do
    arr[j+1] = arr[j]
    j -= 1
  end
  arr[j+1] = v
  puts arr.join(' ')
end


Measured memory_bytes: 6892
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])


Measured memory_bytes: 15996
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S,T;
  cin >> S >> T;
  int A,B;
  cin >> A >> B;
  string U;
  cin >> U;
  if(S == U){
  cout << A-1 << endl; 
  cout << B << endl;;
  }else{
  cout << A << endl; 
  cout << B-1 << endl;;
  }
  
}


Measured memory_bytes: 256
N = int(input())
L = sorted(list(map(int, input().split())))

cnt = 0
for i in range(N):
    li = L[i]
    for j in range(i + 1, N):
        lj = L[j]
        if li == lj: continue
        for k in range(j + 1, N):
            lk = L[k]
            if li == lk or lj == lk: continue
            if li + lj > lk:
                cnt += 1

print(cnt)


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
typedef long long ll;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

ll modpow(ll a, ll p)
{
    if (p == 0)
        return 1;
    if (!(p % 2))
    {
        ll halfP = p / 2;
        ll half = modpow(a, halfP);
        return half * half % mod;
    }
    else
    {
        return a * modpow(a, p - 1) % mod;
    }
}

ll comb(int a, int b)
{
    if (b > a - b)
        return comb(a, a - b);
    ll ansMul = 1;
    ll ansDiv = 1;
    for (int i = 0; i < b; i++)
    {
        ansMul *= a - i;
        ansDiv *= i + 1;
        ansMul %= mod;
        ansDiv %= mod;
    }
    ll ans = ansMul * modpow(ansDiv, mod - 2) % mod;
    return ans;
}

/*
int num = 200010;
vector<ll> fact(num), ifact(num);
fact[0] = 1;
fact[1] = 1;
for (int i = 2; i < num; i++) {
    fact[i] = fact[i-1] * i;
    fact[i] %= mod;
}
for (int i = 0; i < num; i++) {
    ifact[i] = modpow(ifact[i], mod-2);
    ifact[i] %= mod;
}
*/

int main() {
    int N; cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    vector<int> alt;
    rep(i, N) alt.pb(A[i]);
    sort(all(alt));
    rep(i, N) {
        int it = lower_bound(all(alt), A[i]) - alt.begin();
        A[i] = it;
    }
    vector<int> nums(N);
    for (int i = 1; i < N; i += 2) {
        nums[A[i]]++;
    }
    int res = 0;
    for (int i = 1; i < N; i += 2) {
        if (nums[i] == 1) res++;
    }
    cout << N / 2 - res << endl;
    return 0;
}


Measured memory_bytes: 1528
K=int(input())
a = 0
m7 = 7%K
m10 = 10%K
if K % 2 == 0:
  print("-1")
else:
  for i in range(1000000):
    a = ((a%K) * m10 + m7) % K
    if a == 0:
      print(i+1)
      break
  else:
    print("-1")



Measured memory_bytes: 9164
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 60;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, m, x;
  cin >> n >> m >> x;
  ll c0 = 0, cn = 0;
  rep(i, m) {
    ll a;
    cin >> a;
    if (a < x)
      c0++;
    else
      cn++;
  }
  cout << min(c0, cn) << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    ll N; cin >> N;    
    prt(N+N*N+N*N*N);
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	char c,ans;
	cin>>c;
	if(c=='A')ans='T';
	if(c=='C')ans='G';
	if(c=='G')ans='C';
	if(c=='T')ans='A';
	cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            String s = in.next();
            String t = in.next();
            StringBuilder sb = new StringBuilder();
            sb.append(t).reverse();
            boolean ok = true;
            if (!s.equals(sb.toString())) ok = false;
            out.println(ok ? "YES" : "NO");

        }

    }
}



Measured memory_bytes: 23764
//#include "bits/stdc++.h"
//using namespace std;
#include <stdio.h>
#include <assert.h>

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

#define DIVUP(x, y) (((x) + ((y) - 1)) / (y))
#define DIVOFF(x, y) (((x) + ((y) / 2)) / (y))
#define REMAINDER(x, y) ((x) % (y))

int main() {
  int N; scanf("%d", &N);
  int a[N + 1]; for (int i{1}; i <= N; ++i) scanf("%d", &a[i]);
  int ans{1};
  int start = a[1], next = start;
  for (int i{1}; i <= N; ++i) {
    if (next == 2) break;
    next = a[next];
    ++ans;
    if (next == start) break;
  }

  printf("%d\n", next == 2 ? ans : -1);
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1<<20|3,mo=1e9+7;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline void sub(int &x, int y){x=x-y>=0?x-y:x-y+mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}

int fac[766],ifac[766],A[766][766];
void iniC(int n){
	fac[0]=1;rep(i,1,n)fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);
	per(i,n-1,0)ifac[i]=1LL*ifac[i+1]*(i+1)%mo;
	rep(i,0,n)rep(j,0,i)A[i][j]=1LL*fac[i]*ifac[i-j]%mo;
}
int n,m;vector<Pii> e[26];int d[26][26],a[N];
void dfs(int s, int u, int fa, int S){
	d[s][u]=S;
	rep(i,0,SZ(e[u])-1)if(e[u][i].fi!=fa)
		dfs(s,e[u][i].fi,u,S|(1<<e[u][i].se-1));
}
struct node{
	int ways,ans,b,n;
	inline void upd(int x, int y, int z, int w){
		add(ways,x);add(ans,y);b=z;n=w;
	}
}dp[N];
int main() {
	iniC(666);read(n);read(m);
	rep(i,1,n-1){
		int u,v;read(u);read(v);m--;
		e[u].pb(Pii(v,i));e[v].pb(Pii(u,i));
	}
	rep(i,1,n)dfs(i,i,0,0);
	while(m--){
		int u,v;read(u);read(v);a[d[u][v]]++;
	}
	int all=(1<<n-1)-1;
	rep(j,0,n-2)rep(i,0,all)a[i]+=i>>j&1?a[i^(1<<j)]:0;
	dp[0]=(node){1,0,0,0};
	rep(s,0,all-1)rep(i,1,n-1)if(!(s>>i-1&1)){
		int k=a[all^s]-a[all^s^(1<<i-1)];
		int n=dp[s].n,b=dp[s].b;
		int x=1LL*dp[s].ways*A[n+k][k]%mo;
		dp[s|(1<<i-1)].upd(x,(1LL*dp[s].ans*A[n+k+1][k]+1LL*x*(b+1))%mo,b+1,n+k+1);
	}
	printf("%d\n",dp[all].ans);
	return 0;
}


Measured memory_bytes: 16640
a,b,h,m=map(int,input().split())
import math
la=math.pi*(h+m/60)/6
lb=math.pi*m/30
ll=math.sqrt((a*math.cos(la)-b*math.cos(lb))**2+(a*math.sin(la)-b*math.sin(lb))**2)
print(ll)

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

int main(){
	int n;
	cin>>n;
	double xa,ya,xb,yb,ra,rb;
	for(int i=0;i<n;i++){
		cin>>xa>>ya>>ra>>xb>>yb>>rb;
		if(abs(ra+rb)<sqrt(pow(xa-xb,2)+pow(ya-yb,2))){cout<<0<<endl;}
		else if(abs(ra+rb)>=sqrt(pow(xa-xb,2)+pow(ya-yb,2)) && abs(ra-rb)<=sqrt(pow(xa-xb,2)+pow(ya-yb,2))){cout<<1<<endl;}
		else{if(ra>rb){cout<<2<<endl;}else{cout<<-2<<endl;}}
	}
	return 0;
}

Measured memory_bytes: 1232
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;

static class MainClass
{
    public static void Main(string[] args)
    {
        var N = Console.ReadLine().ToInt32();
        var dp = new int[N + 10, 3];
        for (int i = 0; i < N; i++)
        {
            var abc = Console.ReadLine().SplittedStringToInt32List();
            for (int j = 0; j < 3; j++)
            {
                dp[i + 1, j] = Math.Max(dp[i, (j + 1) % 3] + abc[(j + 1 )% 3], dp[i, (j + 2) % 3] + abc[(j + 2) % 3]);
            }
        }
        Console.WriteLine(Math.Max(dp[N,0],Math.Max(dp[N,1],dp[N,2])));

        Console.ReadLine();
    }

    public static void PrintArray(int[,] array,int n1,int n2)
    {
        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                Console.Write(array[i,j] + " ");
            }
            Console.WriteLine();
        }
    }

    #region ライブラリ
    public static long ToInt64(this string str) => long.Parse(str);
    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    public const int INF = int.MaxValue / 2;
    public const long LONGINF = long.MaxValue / 2;
    #endregion
}



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

typedef long long ll;
typedef pair<int, int> P;

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define Rep(i, n) For(i, 0, (n))
#define Rrep(i, n) for(int i = (n - 1); i >= 0; i--)
#define pb push_back

const int inf = 999999999;
const int mod = 1000000007;

typedef struct{
	int x, y;
}data;

typedef struct{
	int to, cap, rev;
}edge;

vector<edge> G[202];
bool used[202];

void add_edge(int from, int to, int cap){
	int p = G[to].size(), q = G[from].size();
	G[from].pb((edge){to, cap, p});
	G[to].pb((edge){from, 0, q});
}

int dfs(int v, int t, int f){
	if(v == t) return f;
	used[v] = true;
	for(int i = 0; i < G[v].size(); i++){
		edge &e = G[v][i];
		if(!used[e.to] && e.cap > 0){
			int d = dfs(e.to, t, min(f, e.cap));
			if(d > 0){
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s, int t){
	int flow = 0;
	while(1){
		Rep(i, 202){
			used[i] = false;
		}
		int f = dfs(s, t, inf);
		if(f == 0) return flow;
		flow += f;
	}
}

int main(){
	int n; cin >> n; data a[n], b[n];
	int s = n * 2, t = s + 1;
	Rep(i, n){
		int x, y; cin >> x >> y;
		a[i].x = x; a[i].y = y;
	}
	Rep(i, n){
		int x, y; cin >> x >> y;
		b[i].x = x; b[i].y = y;
	}
	Rep(i, n){
		add_edge(s, i, 1);
	}
	Rep(i, n){
		add_edge(n + i, t, 1);
	}
	Rep(i, n){
		Rep(j, n){
			if(a[i].x < b[j].x && a[i].y < b[j].y){
				add_edge(i, n + j, 1);
			}
		}
	}
	int ans = max_flow(s, t);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main(){
  int n,i,a,b,ans=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&a,&b);
    ans += b-a+1;
  }
  printf("%d\n",ans);
}

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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

#ifdef LOCAL
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else 
#define dump(x) true
#endif

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

template<class T, class U> bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } return 0; }
template<class T, class U> bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } return 0; }

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

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

int main() {
	string S; cin >> S;
	int Q; cin >> Q;
	V<int> vt(Q), vf(Q);
	V<char> vc(Q);
	int len = S.size();

	rep(i, Q) {
		cin >> vt[i];
		if (vt[i] == 2) {
			cin >> vf[i];
			cin.ignore();
			cin >> vc[i];
			vf[i]--;
			len++;
		}
	}

	string ans(len, '?');
	int l = 0, r = len - 1;
	bool rev = false;
	for (int i = Q-1; i >= 0; --i) {
		if (vt[i] == 1) {
			rev = !rev;
		} else {
			int p = vf[i] ^ rev;
			if (p == 0) {
				ans[l++] = vc[i];
			} else {
				ans[r--] = vc[i];
			}
		}
	}
	rep(i, S.size()) {
		if (rev) {
			ans[r--] = S[i];
		} else {
			ans[l++] = S[i];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2816
#include <cstdio>
using namespace std;
long long v[2005][2005];
const int mod=1e9+7;
int main() {
    long long n,k;
    scanf("%lld%lld",&n,&k);
    v[0][0]=1;
    for(int i=1;i<=n;i++){
        v[i][0]=1;
        for(int j=1;j<=i;j++)
            v[i][j]=(v[i-1][j-1]+v[i-1][j])%mod;
    }
    for(int i=1;i<=k;i++)
        printf("%lld\n",v[n-k+1][i]*v[k-1][i-1]%mod);
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

Measured memory_bytes: 30080
from sys import stdin


def dfs(e, ans, done, N, graph):
    if (1 << N) - 1 == done:
        ans += 1
        return ans
    for s in graph[e]:
        if done >> s & 1:
            continue
        done ^= 1 << s
        ans = dfs(s, ans, done, N, graph)
        done ^= 1 << s
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(lambda x: int(x) - 1, lines[i].split())
        # 0-based indexing
        graph[a].append(b)
        graph[b].append(a)
    ans = 0
    print(dfs(0, ans, 1, N, graph))
    return


main()


Measured memory_bytes: 3064