akhauriyash/Code-Regression huggingface dataset:
from heapq import heappop as pop
from heapq import heappush as push

def solve():
  
  INF = 10 ** 18
  
  class edge:
    def __init__(self, to, cost):
      self.to = to
      self.cost = cost
  
  N, M, K = map(int,input().split())
  
  G = [[] for i in range(N)]
  #G[i]...頂点iからの辺list、(行き先、コスト)
  
  d = [INF for i in range(N)]
  #d[i]...スタートからみた頂点iまでの最短距離
  
  def dijkstra(lst):
    que = []
    for s in lst:
      d[s] = 0
      push(que, (0,s))
  
    while len(que):
      p = pop(que)
      v = p[1]
      if (d[v] < p[0]):
        continue
      for i in range(len(G[v])):
        e = G[v][i]
        if d[e.to] > d[v] + e.cost:
          d[e.to] = d[v] + e.cost
          push(que, (d[e.to], e.to))
  
  for i in range(M):
    s, t, c = map(int,input().split())
    s -= 1
    t -= 1
    G[s].append(edge(t,c))
    G[t].append(edge(s,c))
  
  
  lst =  [int(input()) - 1 for i in range(K)]
  dijkstra(lst)
  
  anss = []
  append = anss.append
  
  for i in range(N):
    for e in G[i]:
      x = d[i] + d[e.to] + e.cost
      if x % 2:
        append(x // 2 + 1)
      else:
        append(x // 2)
  
  print(max(anss))

solve()


Measured memory_bytes: 58832
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

l,r = I()

if r-l >= 673:
    print(0)
    exit()
ans = 2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ans = min(ans,i*j%2019)

print(ans)


Measured memory_bytes: 10016
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <tuple>
#include <deque>

template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

int main() {
  std::string S;
  int Q;
  std::cin >> S >> Q;
  std::deque<char> ans(S.begin(), S.end());
  int rev = 0;
  while (Q--) {
    int t;
    std::cin >> t;
    if (t == 1) {
      rev ^= 1;
    }
    else {
      int f;
      char c;
      std::cin >> f >> c;
      if (f == 1) {
        if (rev == 0) ans.push_front(c);
        else ans.push_back(c);
      }
      else {
        if (rev == 1) ans.push_front(c);
        else ans.push_back(c);
      }
    }
  }
  if (rev == 1) {
    std::reverse(ans.begin(), ans.end());
  }
  for (char c: ans) {
    std::cout << c;
  }
  std::cout << '\n';
  return 0;
}


Measured memory_bytes: 896
n,m = map(int,input().split())
data = []
for i in range(0,m):
    a,b,c = map(int,input().split())
    data.append((a,b,-c))

g = [float("inf") for _ in range(0,n+1)]
g[1] = 0
negative = ["false" for _ in range(0,n+1)]

for i in range(0,n):
    for j in range(0,m):
        a,b,c = data[j]
        if g[a] != float("inf") and g[b] > g[a] + c:
            g[b] = g[a] + c
            if i == n-1:
                negative[b] = "true"
if negative[n] == "false":
    print(-g[n])
else:
    print("inf")


Measured memory_bytes: 3420
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
import itertools
import bisect
mod = 10 ** 9 + 7
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
count = 0
for i in range(len(L)):
    for j in range(i+1, len(L)):
        a = L[i]
        b = L[j]
        idx = insert_index = bisect.bisect_left(L, a+b)
        count += max(0, idx-j-1)


print(count)


Measured memory_bytes: 14392
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <unordered_set>
#include <map>
#include <cmath>
#include <deque>
#include <queue>
#include <string>
#include <cstring>
#include <stack>


using namespace std;
typedef long long ll;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
#define V vector

int n;
long long k;
V<int> tele(200020);
map<int, int> first;

void solve() {
    int pt = 1;
    int c = 1;
    while (first.count(pt) == 0) {
        first[pt] = c;
        pt = tele[pt];
        c++;
        k--;
        if(not k){
            cout << pt; return;
        }
    }
    long long res = (k) % (c - first[pt]);
    while (res--) {
        pt = tele[pt];
    }
    cout << pt;
    return;
}

int main() {
    cin >> n >> k;
    int t = 0;
    for(int i = 1; i < n+1; i++) {
        cin >> tele[i];
    }
    solve();
    return 0;
}



Measured memory_bytes: 11388
#include <bits/stdc++.h>
#define fto(i,a,b) for(int i=a; i<=b;++i)
#define fdto(i,a,b) for(int i=a; i>=b;--i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<ll,ll>
#define ll long long
#define maxn 300009
#define maxm 100009
#define gb(i,j) ((i>>j)&1)
#define name "a"
#define endl '\n'
#define int ll

using namespace std;

const int mod=1e9+7;

int mu(int a, int b){
    if(b==0)return 1;
    int tg=mu(a,b/2);
    tg=(tg*tg)%mod;
    if(b%2)tg=(tg*a)%mod;
    return tg;
}
int p[2009],p1[2009];
int C(int a, int b){
    return p[a+b]*p1[a]%mod *p1[b] %mod;
}
int n,a,b,c,d,h[2009][2009],f[2009][2009],h1[2009][2009];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> a >> b >> c >> d;
    p[0]=1;
    fto(i,1,n*2)p[i]=p[i-1]*i%mod;
    fto(i,0,n*2)p1[i]=mu(p[i],mod-2);
    fto(i,0,n)
        fto(j,0,n)h[i][j]=C(i,j);
    fto(i,1,n){
        h1[i][1]=1;
        fto(j,2,d){
            if(j*i>n)break;
            h1[i][j]=(h1[i][j-1]*h[i][j*i-i])%mod;
        }
        fto(j,2,d){
            if(j*i>n)break;
            h1[i][j]=(h1[i][j]*p1[j])%mod;
        }
    }
    f[0][a-1]=1;
    for(int i=a; i<=b; ++i){
        for(int j=i*c; j<=i*d && j<=n;j+=i)
            for(int t=j; t<=n; ++t)
            if(f[t-j][i-1]){
                f[t][i]=(f[t][i]+f[t-j][i-1]*h[j][n-t]%mod * h1[i][j/i])%mod;
                //if(f[t][i]) cout << f[t-j][i-1]<<' '<< t <<' '<< j <<' '<< h[j][n-t]<<' '<< h1[i][j/i]<<endl;
            }
        //cout << i <<endl;
        //fto(j,0,n)cout << j <<' '<<f[j][i]<<endl;
        fto(j,0,n)f[j][i]=(f[j][i]+f[j][i-1])%mod;
    }
    cout << f[n][b];
    return 0;
}


Measured memory_bytes: 52096
n=int(input())
l = [list(map(int,input().split())) for _ in range(n)]
l.insert(0,[0,0,0])
can = True
for i in range(len(l)-1):
    dt = l[i+1][0] - l[i][0]
    dist = abs(l[i+1][1] - l[i][1]) + abs(l[i+1][2]-l[i][2])
    if dt < dist:
        can = False
        break
    if dist % 2 != dt % 2:
        can = False
print('Yes') if can else print('No')

    



Measured memory_bytes: 27300
#include<iostream>
using namespace std;
int main(){
    int a,b,result;
    char op;
    
    while(1){
        cin >> a >> op >> b;
        if(op=='?'){
            break;
        }else if(op == '+'){
            cout << a+b << endl;
        }else if(op == '-'){
            cout << a-b << endl;
        }else if(op == '*'){
            cout << a*b << endl;
        }else if(op == '/'){
            cout << a/b << endl;
        }
        
    }
    
    return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int mod =1e9+7;
const int N = (int)2e5 + 5;

void solve(){
	int n;
	cin>>n;
	if(n%10==n/100)cout<<"Yes";
	else cout<<"No";

}

int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

Measured memory_bytes: 256
//circle

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
double r,h,s,p=3.141592653589;

cin>>r;

s=p*r*r;
h=2*p*r;

printf("%.8f %.8f\n",s,h);

return 0;
}

Measured memory_bytes: 1240
/*
 *  Created on: 2 / 8 / 2020
 *  Author:     Eslam Waheed
 */

#define _CRT_SECURE_NO_WARNINGS
//#define __USE_MINGW_ANSI_STDIO

#include <bits/stdc++.h>
//#include <bits/BIGINT.h>
//#include <bits/Int128.h>
using namespace std;

#define Eslam__Waheed ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

#define ll   long long
#define ull  unsigned ll
#define dd   double
#define ld   long dd
#define ss   string

#define pb      push_back
#define all(c)  c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define stp(n)  cout << fixed << setprecision(n);
#define iq(v)   v.resize(unique(v.begin(),v.end())-v.begin())
#define sz(s)   (ll)(s.size())
#define endl    '\n'

#define loop(i,m,n)  for(ll i=m;i<n;i++)
#define test(t)      while(t--)

//ll gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return abs(a / gcd(a, b)) * b; }

//const ld PI = acos(-1);
//const ll mod = 1e9 + 7;
//const ld EPS = 1e-8;
/*
 you can ^_^ (•‿•)

( إن الله وملائكته يصلون على النبي يا أيها الذين آمنوا صلوا عليه وسلموا تسليما )
*/
int main()
{
	//stp(0)
	Eslam__Waheed;
	ll n, d; cin >> n >> d;
	ll ans = 0;
	loop(i, 0, n)
	{
		ll a, b; cin >> a >> b;
		ld x = sqrt(pow(a, 2) + pow(b, 2));
		if (x <= d)ans++;
	}
	cout << ans;
}

Measured memory_bytes: 3696
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main(void){
    int n;
    cin >> n;
    vector<int> t(n);
    vector<bool> dt(n, false);
    vector<int> a(n);
    vector<bool> da(n, false);
    dt[0] = true;
    da[n-1] = true;
    for(int i=0; i<n; i++){
        cin >> t[i];
        if(i>0){
            if(t[i]>t[i-1]){
                dt[i]=true;
            }
        }
    }
    for(int i=0; i<n; i++){
        cin >> a[i];
        if(i>0){
            if(a[i-1]>a[i]){
                da[i-1]=true;
            }
        }
    }
    long long ans = 1;
    for(int i=0; i<n; i++){
        if(da[i]){
            if(dt[i]){
                if(a[i]!=t[i]){
                    ans = 0;
                }
            }else{
                if(a[i]>t[i]){
                    ans = 0;
                }
            }
        }else{
            if(dt[i]){
                if(t[i]>a[i]){
                    ans = 0;
                }
            }else{
                ans *= min(t[i],a[i]);
            }
        }
        ans = ans%(1000000000+7);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
using pii = pair<int, int>;

#define rep(i,k,n) for(int i=(k); i != int(n); ++i)
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << '=' << x << '\n';
#define dbg2(x, y) cout << #x << '=' << x << ' ' << #y << '=' << y << '\n' 

#define input() (*istream_iterator<int>(cin))
#define strin() (*istream_iterator<string>(cin))
#define output(x) cout << x << '\n' 

const int mod = 1e9+7;
lli acc(lli idx){
    return (lli(idx*(idx+1))/2);
}
int main(){
    ios::sync_with_stdio(false);
    int n = input(), k = input();
    int sum = 0;
    for(int i = k; i <= n+1; ++i){
        lli mn = acc(i-1), mx = acc(n)-acc(n-i);
        lli seg = mx - mn + 1;
        sum = ((sum%mod) + (seg%mod))%mod;       
    }
    cout << sum;
}

Measured memory_bytes: 3608
function main()
  
  (N,K) = map(x -> parse(Int,x), split(readline()))
  
  ans = 0
  check = 0
  
  for i in 1:N
    
    ceil(Int,log(2, K/i)) > 0 ? check = ceil(Int,log(2, K/i)) : check = 0
    ans += 1/N * (1/2)^check
    
  end
  
  println(ans)
  
end

main()

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

int main(){
  int X, A, B;
  cin >> X >> A >> B;


  if(A>=B) cout << "delicious" << endl;
  else{
      if((B-A)>X) cout << "dangerous" << endl;
      else cout << "safe" << endl;
  }
}


Measured memory_bytes: 256
import re
S = input()
T = input()
T = re.sub('^' + S,'',T,1)

beforeT = T
T = re.sub('[a-z]','',T,1)
if beforeT == T:
    print("No")
    exit(0)
if T == "":
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9940
-- ????¨?

import           Control.Applicative
import           Text.Printf

main :: IO ()
main = do
  fullSec <- read <$> getLine :: IO Int
  let h = fullSec `div` (60 * 60)
      m = (fullSec `mod` (60 * 60)) `div` 60
      s = fullSec `mod` (60 * 60) `mod` 60

  printf "%d:%d:%d\n" h m s

Measured memory_bytes: 3736
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;

int main() {
    int n, k, a[51];
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 0; i <= 50; i++) {
        for(int j = 0; j <= 49; j++) {
            if(i + j > k || i + j > n) break;
            deque<int> v;
            for(int x = 0; x < i; x++) v.push_back(a[x]);
            for(int x = 0; x < j; x++) v.push_back(a[n-x-1]);
            sort(v.begin(), v.end());
            int res = 0;
            for(int x = 0; x < k-i-j && v.size() > 0; x++) {
                if(v.front() < 0) v.pop_front();
            }
            for(int x = 0; x < v.size(); x++) {
                res += v[x];
            }
            ans = max(ans, res);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())

bridge = [None]*m
for i in range(m):
  a, b = map(int, input().split())
  bridge[i] = [b, a]

ans = 0
bridge.sort()

sub = -1
ans = 0
for v in bridge:
  b, a = v[0], v[1]
  if a >= sub:
    sub = b
    ans += 1

print(ans)

Measured memory_bytes: 24396
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

int main(){
    double pi = 3.1415926535897932384626433832795028841971;
    double r;
    
    cin >> r;
    printf("%7lf %7lf\n",r*r*pi,r*2*pi);
    return 0;
}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
using namespace std;
string st;
map<char,char> ma;
int saiki(int s,int l,int r,int g,int c){
  int m1=c,m2=c;
  if(s==l)return c;
  if(g==r)return c;
  m1=saiki(s+1,l,r,g,c);
  for(int i=g;i>r;i--){
    if(ma[st[i]]==st[s]){
      m2=saiki(s+1,l,r,i-1,c+2);
      break;
    }
  }
  return max(m1,m2);
}

int main(){
  ma['(']=')';
  ma[')']='(';
  ma['[']=']';
  ma[']']='[';
  ma['{']='}';
  ma['}']='{';
  int c=0;
  int r,l;
  cin >> st;
  int m=0;
  l=0;
  for(int i=0;i<st.size();i++){
    if(st[i]=='w'){
      for(int j=i;j>=0;j--){
	if(st[j]=='i'){
	  l=j;
	  break;
	}
      }
      for(int j=i;j<st.size();j++){
	if(st[j]=='i'){
	  r=j;
	  break;
	}
      }
      break;
    }
  }
  //
  c=3;
  m=saiki(0,l,r,st.size()-1,c);
  cout << m << endl;
  return 0;
}
 

Measured memory_bytes: 3188
/*Coded by::
    **Avinash Tiwary**
    **BE/10298/2015**
    **Production Engineer**
    **Producing <code>**
*/
#include<bits/stdc++.h>
#define buf ios_base::sync_with_stdio (0), cin.tie (0)
typedef long long ll;
typedef double dob;
#define MAX 50010
#define M5 200009
#define M6 2000009
#define M 1000000007
#define inf LLONG_MAX
using namespace std;
typedef vector<ll> V;
typedef queue<ll > Q;
typedef stack<ll> S;
typedef pair<dob,ll> P;
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
ll fac[M6],not_prime[M6],ar[M6],br[M6];
ll power(ll x,ll n)
{   if(n==0) return 1;
    else if(n%2 == 0) return power((x*x)%M,n/2);
    else return (x*power((x*x)%M,(n-1)/2))%M;
}
void fact(){
    fac[0]=1;
    for(ll i=1;i<M6;i++) fac[i]=(i*fac[i-1])%M;
}
void sieve(){
    not_prime[1]=1; not_prime[0]=1;
    for(ll p=2;p*p<M6;p++){
        if(!not_prime[p]){
            for(ll i=p*2;i<=M6;i+=p) not_prime[i]=1;
        }
    }
}
ll modi(ll a, ll m){
    ll m0 = m, t, q; ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1){  q = a / m; t = m; m = a % m, a = t;t = x0;x0 = x1 - q * x0; x1 = t;}
    if (x1 < 0) x1 += m0;return x1;
}
vector<list< ll > > g(M5);
int main(){
    buf; 
    //sieve(); 
    //fact();
    ll i,j,test,flag,t,ans,a,b,n,m,d,q,l; string s1,s2,s3;
    test=1;
    while(test--){
        cin>>n;
        map<ll,ll> con,con2;
        for(i=1;i<=n;i++){ cin>>ar[i]; con[ar[i]]++;}
        cin>>m;
        for(i=1;i<=m;i++){
            cin>>br[i]; con2[br[i]]++;
        }
        for(i=1;i<=m;i++){
            if(con2[br[i]]>con[br[i]]) {cout<<"NO"; return 0;}
        }
        cout<<"YES";
    }
    return 0;
}

Measured memory_bytes: 34048
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 100000

int m, n;
string str[20];
map<int, int> comp;
int dp[2][20][11000][2];
int cnt[20][20];

int mod_pow(int x, int n) {
	if (n == 0) return 1;
	int res = mod_pow((long long)x * x % MOD, n / 2);
	if (n & 1) res = (long long)res * x % MOD;
	
	return res;
}

int main() {
	cin >> m >> n;
	REP(i, m) cin >> str[i];
	
	for (int i = m * n - 2; i >= 0; i--)
		cnt[i / n][i % n] = cnt[(i + 1) / n][(i + 1) % n] + (str[(i + 1) / n][(i + 1) % n] == '?');
	REP(i, m) REP(j, n) cnt[i][j] = mod_pow(3, cnt[i][j]);
	
	int c = 0;
	REP(i, 1<<n - 1) {
		bool f = false;
		REP(j, n - 2) if ((i >> j & 1) && (i >> (j + 1) & 1)) f = true;
		if (f) continue;
		comp[i] = c++;
	}
	
	for (int i = m - 1; i >= 0; i--) {
		for (int j = n - 1; j >= 0; j--) {
			for (map<int, int>::iterator it = comp.begin(); it != comp.end(); it++) {
				int s = it->first;
				
				REP(l, 2) {
					int tmp = 0;
					
					int nexts = comp[s >> 1];
					
					if (str[i][j] == 'J' || str[i][j] == '?') {
						if (j == n - 1) tmp += dp[(i + 1) % 2][0][nexts][0];
						else tmp += dp[i % 2][j + 1][nexts][1];
					}
                    
					if (str[i][j] == 'O' || str[i][j] == '?') {
						if (l) {
							if (comp.find((s >> 1) | (1 << n - 2)) != comp.end()) {
								if (j == n - 1) tmp += dp[(i + 1) % 2][0][comp[(s >> 1) | (1 << (n - 2))]][0];
								else tmp += dp[i % 2][j + 1][comp[(s >> 1) | (1 << (n - 2))]][0];
							}
						}
						else {
							if (j == n - 1) tmp += dp[(i + 1) % 2][0][nexts][0];
							else tmp += dp[i % 2][j + 1][nexts][0];
						}
					}
                    
					if (str[i][j] == 'I' || str[i][j] == '?') {
						if (s & 1) {
							tmp += cnt[i][j];
						}
						else {
							if (j == n - 1) tmp += dp[(i + 1) % 2][0][nexts][0];
							else tmp += dp[i % 2][j + 1][nexts][0];
						}
					}
                    
					dp[i % 2][j][comp[s]][l] = tmp % MOD;
				}
			}
		}   
	
	}
	
	cout << dp[0][0][comp[0]][0] << endl;
	 
	return 0;
}

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

using namespace std;

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

const int N = 1e5 + 10, MOD = 1e9 + 7;

vector <int> e[N];

int n, m;
ll ans;

void dfs(int u, int fa)
{
	int tot = e[u].size();
	for (int i = 0, j = m - (fa == 0 ? 1 : 2); i < tot; ++i)
	{
		int v = e[u][i];
		if (v != fa)
		{
			(ans *= j--) %= MOD;
			dfs(v, u);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	ans = m;
	dfs(1, 0);
	cout << ans;
}

Measured memory_bytes: 11648
// In the Name of Allah
// Ya Ali

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define all( x ) x.begin() , x.end()
#define pb push_back
#define mp make_pair
#define uniq( x ) sort( all( x ) ) , x.resize( unique( all( x ) ) - x.begin())

const int maxn = 2e5 + 10 ;
const int INF = 1e18 ;

int n , a , b , c , d , t , dp[ maxn ] ;
vector< int > vv ;

void solve()
{
 cin >> n >> a >> b >> c >> d ;

 for(int i = 1 ; i <= n ; i *= 2){
   for(int j = i ; j <= n ; j *= 3){
      for(int k = j ; k <= n ; k *= 5){
         vv.pb( n/k ) ;
         vv.pb( (n+k-1)/k ) ;
      }
   }
 }


 uniq( vv );

// cout << vv.size() << "\n" ;

 dp[ 0 ] = d ;
 for(int i = 1 ; i < vv.size() ; i ++){
   int x = vv[ i ];

   dp[ i ] = 9*INF ;

   long double xx = x , dd = d , check = 9e18 ;
   long double val = xx*dd ;
   if( val < check ){
     dp[ i ] = x*d ;
   }

   int x1 = x/2 , y1 = (x+1)/2 , dx1 = x%2 , dy1 = (2-(x%2))%2 ;
   int x2 = x/3 , y2 = (x+2)/3 , dx2 = x%3 , dy2 = (3-(x%3))%3;
   int x3 = x/5 , y3 = (x+4)/5 , dx3 = x%5 , dy3 = (5-(x%5))%5;

   int indx1 = lower_bound( all( vv ) , x1 ) - vv.begin() ;
   int indx2 = lower_bound( all( vv ) , x2 ) - vv.begin() ;
   int indx3 = lower_bound( all( vv ) , x3 ) - vv.begin() ;
   int indy1 = lower_bound( all( vv ) , y1 ) - vv.begin() ;
   int indy2 = lower_bound( all( vv ) , y2 ) - vv.begin() ;
   int indy3 = lower_bound( all( vv ) , y3 ) - vv.begin() ;

 //  if( indx1 == vv.size() || indx2 == vv.size() || indx3 == vv.size()|| indy1 == vv.size()|| indy2 == vv.size()|| indy3 == vv.size())
 //     cout << "NOOOOOOOo\n" ;

   dp[ i ] = min( dp[ i ] , dp[ indx1 ] + dx1*d + a ) ;
   dp[ i ] = min( dp[ i ] , dp[ indx2 ] + dx2*d + b ) ;
   dp[ i ] = min( dp[ i ] , dp[ indx3 ] + dx3*d + c ) ;
   dp[ i ] = min( dp[ i ] , dp[ indy1 ] + dy1*d + a ) ;
   dp[ i ] = min( dp[ i ] , dp[ indy2 ] + dy2*d + b ) ;
   dp[ i ] = min( dp[ i ] , dp[ indy3 ] + dy3*d + c ) ;

 }

// cout << vv[ vv.size()-1 ] << "\n" ;

 cout << dp[ vv.size()-1 ] << "\n" ;
}

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

 cin >> t ;

 while( t -- ){
  solve();
 }

    return 0;
}


Measured memory_bytes: 3784
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>

using namespace std;

int main(){
	int N, M, X, Y, x[100], y[100];
	bool ans = true;

	cin >> N >> M >> X >> Y;
	for (int i = 0; i < N; ++i){
		cin >> x[i];
	}
	for (int i = 0; i < M; ++i){
		cin >> y[i];
	}

	for (int i = 0; i < N; ++i){
		if (x[i] >= Y)
			ans = false;
	}
	for (int i = 0; i < M; ++i){
		if (y[i] <= X)
			ans = false;
	}

	for (int i = 0; i < N; ++i){
		for (int j = 0; j < M; ++j){
			if (x[i] >= y[j])
				ans = false;
		}
	}

	if (ans)
		cout << "No War" << endl;
	else
		cout << "War" << endl;

	return 0;
}

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

void MergeSort(long long int x[ ],long long int left,long long int right);
long long int temp[10000];
int main (void){
        int N,M;
        long long int x,y,z;
        long long int V[8][1001];
        long long int ans[8];
        scanf("%d\n", &N);
        scanf("%d\n", &M);

        for (int i = 0; i < 8; i++) {
          ans[i]=0;
        }
        for (int i = 0; i < N; i++) {
          scanf("%lld", &x);
          scanf("%lld", &y);
          scanf("%lld", &z);
          V[0][i]=+x+y+z;
          V[1][i]=+x+y-z;
          V[2][i]=+x-y+z;
          V[3][i]=+x-y-z;
          V[4][i]=-x+y+z;
          V[5][i]=-x+y-z;
          V[6][i]=-x-y+z;
          V[7][i]=-x-y-z;
          /*
          printf("%lld", x);
          printf("%lld", y);
          printf("%lld\n", z);
          printf("%lld\n", V[0][i]);
          */
        }
//printf("neko\n" );
        for (int i = 0; i < 8; i++) {
                    MergeSort(V[i], 0, N-1);
        }
        /*
        for (int i = 0; i < N; i++) {
                  printf("%lld ", V[0][i]);
        }
        */
        //printf("nyan\n");
        for (int i = 0; i < M; i++) {
          for (int j = 0; j < 8; j++) {
            ans[j]+=V[j][N-i-1];
          }
        }
                //  printf("aa%lld ", ans[0]);
        MergeSort(ans, 0, 7);
/*
        for (int i = 0; i < 8; i++) {
          printf("%lld\n", ans[i]);
        }
*/
        printf("%lld\n",ans[7]);
        return 0;
}


void MergeSort(long long int x[ ], long long int left, long long int right)
{
    int mid, i, j, k;

    if (left >= right)              /* 配列の要素がひとつなら */
        return;                     /* 何もしないで戻る */

                                    /* ここでは分割しているだけ */
    mid = (left + right) / 2;       /* 中央の値より */
    MergeSort(x, left, mid);        /* 左を再帰呼び出し */
    MergeSort(x, mid + 1, right);   /* 右を再帰呼び出し */

      /* x[left] から x[mid] を作業領域にコピー */
    for (i = left; i <= mid; i++)
        temp[i] = x[i];

      /* x[mid + 1] から x[right] は逆順にコピー */
    for (i = mid + 1, j = right; i <= right; i++, j--)
        temp[i] = x[j];

    i = left;         /* i とj は作業領域のデーターを */
    j = right;        /* k は配列の要素を指している */

    for (k = left; k <= right; k++)    /* 小さい方から配列に戻す */
        if (temp[i] <= temp[j])        /* ここでソートされる */
            x[k] = temp[i++];
        else
            x[k] = temp[j--];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

vector<int> z_algorithm(string &s) {
    vector<int> z(s.size(), 0);
    z[0] = s.size();

    int i = 1, j = 0;
    while (i < (int)s.size()) {
        while (i + j < (int)s.size() && s[j] == s[i + j]) j++;
        z[i] = j;
        if (j == 0) {
            i++;
            continue;
        }

        int k = 1;
        while (k < j && k + z[k] < j) {
            z[i + k] = z[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return z;
}

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

    int ans = 0;
    REP(i, 0, S.size()) {
        string t = S.substr(i);
        auto z = z_algorithm(t);
        REP(j, 0, z.size()) {
            if (i + z[j] > i + j) continue;
            ans = max(ans, z[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3692
function Main(input){
  input = input.split("\n");
  inputStr = input[0].split(" ");
  const N = Number.parseInt(inputStr[0]);
  //対象数を算出
  var ans = 0;
  if( N%2 === 0){
    //偶数
    ans = N/2-1;
  } else {
    //奇数
    ans = Math.ceil(N/2)-1;
  }
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 8520
def wareru(n,k):
    res = 0
    for i in range(1,n):
        plus = n//(k**i)
        res+= plus
        if plus == 0:break
    return res
n = int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
a = []
for p in prime :
    if wareru(n,p) > 1:
        a.append(wareru(n,p))
    else:break
cnt = [0]*5
for num in a:
    if num >= 74:
        cnt[0]+=1
    if num >= 24:
        cnt[1] +=1
    if num >= 14:
        cnt[2] += 1
    if num >= 4:
        cnt[3] += 1
    cnt[4]+= 1
ans = cnt[0]
ans += cnt[1]*(cnt[4]-1)
ans += cnt[2]*(cnt[3]-1)
ans += cnt[3]*(cnt[3]-1)*(cnt[4]-2)//2
print(ans)

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

using namespace std;

const long long maxn = 1e5;

long long h[maxn + 1], n, a, b;

int verif(long long exp)  {
    long long minb = exp * b, need = 0LL;
    for(int i = 1;i <= n;i++)  {
        long long c = h[i];
        c -= minb;
        if(c > 0LL)  {
            need += (c + a - b - 1) / (a - b);
        }
    }
    if(need <= exp)
        return 1;
    return 0;
}

int main()  {
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);
    cin >> n >> a >> b;
    for(int i = 1;i <= n;i++)
        cin >> h[i];
    long long r = 0LL, pas = 1LL << 31;
    while(pas)  {
        if(verif(r + pas) == 0)
            r += pas;
        pas >>= 1;
    }
    cout << r + 1 << "\n";
    return 0;
}


Measured memory_bytes: 1024
N = int(input())
L = list(map(int,input().split()))
import itertools

seq = ('a', 'b', 'c', 'd', 'e')
ptr = list(itertools.combinations(L,3))

cnt = 0
for i in range(len(ptr)):
    a = ptr[i][0]
    b = ptr[i][1]
    c = ptr[i][2]
    if a<b+c and b<a+c and c<a+b and a!=b and b!=c and c!=a:
        cnt += 1
print(cnt)

Measured memory_bytes: 20612
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

template <typename T>
void print(const vector<T> &v) {
    for (auto e : v) cout << e << ' ';
    cout << endl;
}

//------------------------- Libraries -------------------------//

template<class T>
bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//--------------------------- Solve ---------------------------//

void solve() {
    string s; cin >> s;
    int N = s.size() + 1;
    vector<long long> a(N), left(N), right(N);
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '<') left[i+1] = left[i] + 1;
        else left[i+1] = 0;
    }
    for (int i = N-1; i > 0; i--) {
        if (s[i-1] == '>') right[i-1] = right[i] + 1;
        else right[i-1] = 0;
    }

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans += max(right[i], left[i]);
    }

    cout << ans << '\n';
}

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

    solve();

    return 0;
}

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

void solve(string S){
	int n = !!count(S.begin(),S.end(),'N');
	int s = !!count(S.begin(),S.end(),'S');
	int e = !!count(S.begin(),S.end(),'E');
	int w = !!count(S.begin(),S.end(),'W');
	if( (n^s) or (e^w) ){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
	}
	
}



int main(){	
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	solve(S);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int t[100000],n,k,a,b;
string s;
int main(void){
    cin>>n>>k>>s;
    for(int i=0;i<n-1;i++){
        if(s[i]=='A'&&s[i+1]=='C')t[i+1]=1;
    }
    for(int i=0;i<100000;i++)t[i+1]+=t[i];
    for(int i=0;i<k;i++){
        cin>>a>>b;
        cout<<t[b-1]-t[a-1]<<endl;
    }
}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0])cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
using namespace std;
typedef pair<int,int>P;
bool binary_search(int key1,int key2);
P pp[3001];
int n;
int main(void){
	P pp1,pp2,pp3,pp4;
	int i,j;
	int MAX;
	int x,y;
	int x1,x2,y1,y2;
	int x3,x4,y3,y4;
	int ans;
	bool flg1,flg2,flg3,flg4;
	while(1){
		cin>>n;
		if(n==0)	break;
		MAX=INT_MIN;
		for(i=0;i<n;i++)	cin>>pp[i].F>>pp[i].S;
		sort(pp,pp+n);
		for(i=0;i<n-1;i++){
			for(j=i+1;j<n;j++){
				if(i!=j){
					x=abs(pp[i].F-pp[j].F);
					y=abs(pp[i].S-pp[j].S);
					//cout<<x<<" "<<y<<endl;
					x1=pp[i].F-y;	y1=pp[i].S+x;
					// cout<<x1<<" "<<y1<<endl;
					x2=pp[j].F-y;	y2=pp[j].S+x;
					// cout<<x2<<" "<<y2<<endl;
					x3=pp[i].F+y;	y3=pp[i].S-x;
					// cout<<x3<<" "<<y3<<endl;
					x4=pp[j].F+y;	y4=pp[j].S-x;
					// cout<<x4<<" "<<y4<<endl;
					// cout<<endl;
					pp1.F=x1; pp1.S=y1;
					pp2.F=x2; pp2.S=y2;
					pp3.F=x3; pp3.S=y3;					
					pp4.F=x4; pp4.S=y4;	
					
					// cout<<pp1.F<<" "<<pp1.S<<endl;
					// cout<<pp2.F<<" "<<pp2.S<<endl;
					// cout<<pp3.F<<" "<<pp3.S<<endl;
					// cout<<pp4.F<<" "<<pp4.S<<endl;
					
					flg1=binary_search(pp1.F,pp1.S);
					flg2=binary_search(pp2.F,pp2.S);
					flg3=binary_search(pp3.F,pp3.S);
					flg4=binary_search(pp4.F,pp4.S);
					if((flg1&&flg2)||(flg3&&flg4)){
							ans=x*x+y*y;
							// cout<<ans<<endl;
							MAX=max(MAX,ans);
					}
				}
			}
		}
		if(MAX==INT_MIN)	 MAX=0;
		cout<<MAX<<endl;
	}
	return 0;
}
bool binary_search(int key1,int key2){
	int low,high,mid;
	bool flg=false;
	high=n-1;
	low=0;
	while(low<=high){
		mid=(high+low)/2;
		if(key1<pp[mid].F){
			high=mid-1;
		}
		else if(pp[mid].F<key1){
			low=mid+1;
		}
		else{//key1==pp[mid].F
			if(key2<pp[mid].S){
				high=mid-1;
			}
			else if(pp[mid].S<key2){
				low=mid+1;
			}
			else{//key2==pp[mid].S
				//cout<<"key1="<<key1<<" "<<"pp[mid].F="<<pp[mid].F<<endl;
				//cout<<"key2="<<key2<<" "<<"pp[mid].S="<<pp[mid].S<<endl;
				flg=true;
				break;
			}
		}
	}
	return flg;
}


Measured memory_bytes: 3116
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner i=new Scanner(System.in);
		int w=i.nextInt();
		int h=i.nextInt();
		int x=i.nextInt();
		int y=i.nextInt();
		int r=i.nextInt();
		if((x-r<0)||(y-r<0)||(w<x+r)||(h<y+r))System.out.println("No");
		else System.out.println("Yes");
	}
}

Measured memory_bytes: 17360
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    xus = [stdin.readline().rstrip().split() for _ in range(N)]
    xs = [int(x) if u == 'JPY' else float(x) * 380000 for x, u in xus]
    print(sum(xs))


if __name__ == "__main__":
    main()


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

void solve()
{
  int a, b;
  cin >> a >> b;
  if (a + b < 10) cout << a + b;
  else cout << "error";
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3664
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container, std.typecons;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T)(in string str, T fix) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool INSIDE(T)(T x, T b, T e) { return x >= b && x < e; }

long mod = pow(10, 9) + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

struct UnionFind
{
	void init(long n) { par = new long[](n); foreach (i; 0..n) par[i] = i; }
	long root(long i) { return par[i] == i ? i : (par[i] = root(par[i])); }
	bool same(long i, long j) { return root(i) == root(j); }
	void unite(long i, long j) { i = root(i); j = root(j); if (i == j) return; par[i] = j; }
	long[] par;
}

long[] dijkstra(long from, long to, long[][] edges)
{
	long[] path;
	auto cost = new long[](edges.length); fill(cost, long.max); cost[from] = 0;
	long[][] open = [[from]];
	while (!open.empty)
	{
		auto n = open.front; open.popFront;
		auto p = n[0];
		foreach (i; 0..edges.length)
		{
			if (edges[p][i] == -1) continue;
			auto c = cost[p] + edges[p][i];
			if (c < cost[to] && c < cost[i]) { cost[i] = c; if (i == to) path = i ~ n; else open ~= i ~ n; }
		}
	}
	return cost[to] ~ path;
}

void main()
{
	auto N = RD!long;
	auto v = new long[2][][](N+1);
	foreach (i; 0..N-1)
	{
		auto a = RD!long;
		auto b = RD!long;
		auto c = RD!long;
		v[a] ~= [b, c];
		v[b] ~= [a, c];
	}
	
	auto Q = RD!long;
	auto K = RD!long;
	auto par = new long[2][](N+1);
	par[K] = [K, 0];
	long[] open = [K];
	while (!open.empty)
	{
		//stderr.writeln(open);
		auto n = open.front; open.popFront;
		foreach (chi; v[n])
		{
			if (par[chi[0]][0] != 0) continue;
			par[chi[0]] = [K, par[n][1] + chi[1]];
			open ~= chi[0];
		}
	}

	foreach (i; 0..Q)
	{
		auto x = RD!long;
		auto y = RD!long;
		writeln(par[x][1] + par[y][1]);
	}

	stdout.flush();
}

Measured memory_bytes: 28284
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n,m,x;
   cin >> n >> m >> x;
   vector<vector<int>> A(n,vector<int>(m));
   vector<int> C(n);
   f(i,0,n){
      cin >> C[i];
      f(j,0,m){
         cin >> A[i][j];
      }
   }
   int ans = 1e18;
   f(i,0,(1<<n)){
      vector<int> L(m);
      int cst = 0;
      f(j,0,n){
         if((1<<j)&i){
            cst += C[j];
            f(k,0,m){
               L[k] += A[j][k];
            }
         }
      }
      int c = 1;
      f(j,0,m){
         c &= (L[j]>=x);
      }
      if(c){
         ans = min(ans,cst);
      }
   }
   if(ans == 1e18){
      cout << "-1\n";
   }else{
      cout << ans << '\n';
   }
   return 0;
}

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

int main(){
    long long n,ans=0,tmp=0;
    cin >> n;
    long long yakusuu=sqrt(n);
    for(long long i=1;i<=yakusuu;i++){
        if(i==1){ans=n-1;}
        else if(n%i==0){
            tmp=(n/i)+i-2;
            if(ans>tmp)ans=tmp;
            }
           //cout << ans << endl; 
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
<?php
  
fscanf(STDIN,"%d",$n);
 
$a = explode(" ",trim(fgets(STDIN)));
$cnt =0;
for($i=0;$i<$n;$i++){
	if($a[$i] % 2 == 0){
    	if($a[$i] % 3 == 0 || $a[$i] % 5 == 0 ){
        }else{
        	break;
        }
    }
  $cnt++;
} 

if($cnt == $n){
	echo "APPROVED";
}else{
	echo "DENIED";
}


Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
#define chmax(a,b) a=max(a,b)
const int N=17;

int n,m;
int g[N][N];
int cost[1<<N];
int dp[N][1<<N];

int main()
{
	
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u--; v--;
		g[u][v]=g[v][u]=w;
	}
	for(int mask=0;mask<(1<<n);mask++)
	for(int u=0;u<n;u++)
	for(int v=u+1;v<n;v++)
		if(mask&(1<<u) && mask&(1<<v)) cost[mask]+=g[u][v];
	memset(dp,-1,sizeof(dp));
	for(int mask=1;mask<(1<<n);mask+=2)
		dp[0][mask]=cost[mask];
	for(int mask=0;mask<(1<<(n-1));mask++)
	for(int i=0;i<n-1;i++)
	{
		if(dp[i][mask]<0) continue;
		int _=(1<<n)-1-mask;
		for(int mask2=_;mask2>0;mask2=(mask2-1)&_)
		for(int j=0;j<n;j++)
		{
			if(!(mask2&(1<<j))) continue;
			if(!g[i][j]) continue;
			chmax(dp[j][mask|mask2],dp[i][mask]+g[i][j]+cost[mask2]);
		}
	}
	cout<<cost[(1<<n)-1]-dp[n-1][(1<<n)-1]<<'\n';
	
	return 0;
}

Measured memory_bytes: 9088
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int N;
  cin>>N;
  cout<<(double)(N-N/2)/N<<endl;
}
  
     

    

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        
        int dp[][] = new int[N][N];
        int max = 0;
        
        for(int i = 0; i < N - 1; i++){
            for(int j = i + 1; j < N; j++){
                if(str.charAt(i) == str.charAt(j)){
                    if(i == 0) {
                        dp[i][j] = 1;
                        continue;
                    }
                    
                    int t = dp[i-1][j-1] + 1;
                    if( i + t > j)continue;
                    
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        
        System.out.println( (max < 2) ? 0 : max );
        
        
    }
}


Measured memory_bytes: 168140
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef long long lint;

int gcd(int p, int q){
    if(p < q) swap(p, q);
    while(q){
        int r = p % q;
        p = q;
        q = r;
    }
    return p;
}

int main(){
    int n; cin >> n;
    int a[n]; rep(i, n) cin >> a[i];
    int p[n+2]; rep(i, n+2) p[i] = 0;
    rep(i, n) p[i+2] = gcd(p[i+1], a[i]);
    int s[n+2]; rep(i, n+2) s[i] = 0;
    rrep(i, n) s[i] = gcd(s[i+1], a[i]);
    int ans = 1;
    rep(i, n+2) ans = max(ans, gcd(p[i], s[i]));
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <cstring>

using namespace std ;

char s[100] ;
int d[300] ;

int main(void){
	scanf("%s",s) ;
	for(int i=0; i<strlen(s); i++) {
		d[s[i]]++ ;
	}
	for(int i=0; i<256; i++) {
		if(d[i]>1) {
			printf("no\n") ; return 0 ;
		}
	}
	printf("yes\n") ;
	return 0 ;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    getchar();
    char s[101],t[101];
    cin>>s>>t;
    for(int i=0;i<n;i++)
    {
     cout<<s[i]<<t[i];
    }
    cout<<endl;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
int A[30];

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

    std::cin >> N;
    
    for(int i=0;i<N;++i){
        std::cin >> A[i];
    }

    int cnt = 0;

    for(int i=1;i+1<N;++i){
        int s = A[i-1] + A[i] + A[i+1],
            mx = std::max({A[i-1], A[i], A[i+1]}),
            mn = std::min({A[i-1], A[i], A[i+1]}),
            m = s - mx - mn;

        if(A[i] == m){
            cnt += 1;
        }
    }

    std::cout << cnt << std::endl;
}


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

using namespace std;

int main() {
  long long int L, R; cin >> L >> R;
  int min_mod = 2019;
  long long int tmp;
  long long int k1 = L / 2019;
  long long int k2 = R / 2019;

  if(k1 != k2) min_mod = 0;
  else {
    for(long long int i=L; i<=R; ++i) {
      for(long long int j=i+1; j<=R; ++j) {
        tmp = (i*j) % 2019;
        if(tmp<min_mod) min_mod = tmp;
      }
    }
  }
  cout << min_mod << endl;
}

Measured memory_bytes: 256
N = int(input())
taro = 0
hanako = 0

for i in range(N):
    m,n = map(str,input().split())
    if m > n:
        taro += 3
    elif m < n:
        hanako += 3
    else:
        taro += 1
        hanako += 1
print("%d %d"%(taro,hanako))


Measured memory_bytes: 5600
K, N = map(int, input().split())
A = sorted(map(int, input().split()))

length = A[0] + K - A[-1]
for i in range(N-1):
    length = max(A[i+1] - A[i] , length)
    if length == A[i+1] - A[i]:
        ans = A[i] + K - A[i+1]
      
if length == A[0] + K - A[-1]:
    ans = A[-1] - A[0]
print(ans)

Measured memory_bytes: 26444
n,k=map(int,input().split())
L=[]
for s in range(n):
  a,b=map(int,input().split())
  L.append((a,b))
#print(L)
L=sorted(L,key=lambda x:x[0])
#print(L)
sun=0
for s in L:
  sun+=s[1]
  if sun+1>k:
    print(s[0])
    exit()

Measured memory_bytes: 57560
def partition(a,p,r):
    x=int(a[r][1:])
    i=p-1
    for j in range(p,r):
        if(int(a[j][1:])<=x):
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def quicksort(a,p,r):
    if(p<r):
        q=partition(a,p,r)
        quicksort(a,p,q-1)
        quicksort(a,q+1,r)

a=[]
n=int(input())
for i in range(n):
    s=input()
    a.append("".join(s.split()))

c=list(a)
quicksort(c,0,n-1)

d=dict()
i=0
x="-1"
for i in c:
    if(x!=i[1:]):
        d[i[1:]]=[i[:1]]
        x=i[1:]
    else:
        d[x].append(i[:1])

message="Stable"

for i in reversed(a):
    if(i[1:] in d):
        if(d[i[1:]].pop()!=i[:1]):
            message="Not stable"
            break

print(message)

for i in c:
    print("%s %s"%(i[:1],i[1:]))

Measured memory_bytes: 20644
#include<iostream>
int R,C,s[10000][10],f[10],N,i,j,n,m;void rec(int k){if(k<R){f[k]=0;rec(k+1);f[k]=1;rec(k+1);}else for(n=i=0;i<C;i++,n+=m>R-m?m:R-m,N=N>n?N:n)for(m=j=0;j<R;j++)m+=s[i][j]^f[j];}main(){for(;std::cin>>R>>C,R;rec(0),printf("%d\n",N))for(j=R;j-->0;)for(i=C;i-->0;)std::cin>>s[i][j];}

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

using namespace std;

int main(){

 int D, T, S;
 
 cin >> D >> T >> S;

 int a = T * S;
 
 if(a > D || a == D){
       cout << "Yes" << endl;
   }
   else{
       cout << "No" << endl;
   }

     return 0;
}

Measured memory_bytes: 3584
N = gets.to_i
A = Array.new(N)
max1 = 0
max2 = 0
N.times do |i|
    a = gets.to_i
    if max1 < a then
        max2 = max1
        max1 = a
    elsif max2 < a then
        max2 = a
    end
    A[i] = a
end
A.each do |a|
    if a == max1 then
        puts max2
    else
        puts max1
    end
end

Measured memory_bytes: 4988
#!/usr/bin/env python3
class unionfind:
    def __init__(self, n):
        self.parent = [-1] * n
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.parent[x] > self.parent[y]: x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def issame(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
uf = unionfind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    for j in range(L[0] + 1):
        uf.unite(L[j + 1], M + i)
print(('NO', 'YES')[all(uf.issame(M, M + i) for i in range(N))])


Measured memory_bytes: 10200
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

int main() {
    Int h, n;
    cin >> h >> n;
    vector<Int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (h <= accumulate(a.begin(), a.end(), 0)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


int main(){
    int n,t;cin >> n >> t;
    vector<P> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].fs  >> v[i].sc;
    }
    sort(ALL(v));
    vector<LL> dp(7000,0);
    for (int i = 0; i < n; i++) {
        for (int j = t-1; j >= 0; j--) {
            if(j && dp[j] == 0) continue;
            dp[j+v[i].fs] = max(dp[j+v[i].fs],dp[j] + v[i].sc);
            dp[j] = max(dp[j],dp[j]);
        }
    }
    LL ans = 0;
    for (int i = 0; i < 7000; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384