akhauriyash/Code-Regression huggingface dataset:
//		HYSO SERIOUS? WHY SO SERIOUS                            RIOUS? WHY SO SERIOUS? WHYSO SERIO
//		 ERIOUS? WHY SO SERIOUS ? WHY                          WHY SO SERIOUS? WHY SOSERIOUSWHYS
//		       OSERIOUS? WHY SO SERIOU         SERIOUS        ERIOUS? WHY SO SERIOUS? WHYS
//		          WHY SO SERIOUS? WHY SOSERIOUS? WHYSOSERIOUS? WHY SO SERIOUS?WHY SO SE
//		           ERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SOSERIO
//		           WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WH
//		            SERIOUS?WHYSO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHYSO SE
//		              ?WHYSOSERIOUS?WHY SO SERIOUS? WHY SO SERIOUS?WHYSO SERIOUS?
//		                           OSERIOUS? WHY SO SERIOUS?WHYSOSER
//		                                 HYSOSERIOUS?WHYSOSERI
//		                                     SOSERIOUS?W
//		                                         SER
//		                                          W


#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
#include<bits/stdc++.h>
#include <algorithm>
#define ll long long int
#define read(a) long long int a; cin>>a;
#define readstr(s) string s; cin>>s;
#define readarr(a,l) long long int a[l]={0}; for(ll i=0;i<l;i++) cin>>a[i];
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define rloop(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define readmtrx(i,j,a,b) ll arr[a][b]={0};for(ll i=0;i<a;i++)for(ll j=0;j<b;j++) cin>>arr[i][j];
#define v(pi) vector<ll>pi
#define vp(pi) vector<pair<ll,ll>>pi
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define pb(p) push_back(p)
#define mp make_pair
#include <cmath>
#include <map>
#include <string>
#define mi(lol) map<ll,ll>lol
#define fsort(vec) sort(vec.begin(),vec.end())
#define rsort(vec) sort(vec.begin(),vec.end(),compare)
#define inf ll inf=INT_MAX
//sorting according to the second element vector 

bool compare(pair<ll,ll> p,pair<ll,ll> q){
	return p.second < q.second;	
}

//   example:-
//   sort(vec.begin(),vec.end(),compare);


int main() {
	fast;
//#ifndef ONLINE_JUDGE
  //freopen("input.txt","r",stdin);
 // freopen("output.txt","w",stdout);
//#endif
	read(a)
	double b=(float)a/3;
	cout<<std::setprecision(6)<<fixed<<b*b*b<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1ll<<60;

char field[10][10];
ll dx[2]{1, 0};
ll dy[2]{0, 1};
ll H, W;
bool ok{false};

void bfs(ll h, ll w)
{
	for (ll i = 0; i < 2; ++i)
	{
		ll nh = h + dy[i];
		ll nw = w + dx[i];


		if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
		if (field[nh][nw] != '#') continue;
		field[nh][nw] = '.';
		if (nh == H-1 && nw == W-1)
		{
			ll okk{true};
			for (ll hh = 0; hh < H; ++hh)
			{
				for (ll ww = 0; ww < W; ++ww)
				{
					if (field[hh][ww] == '#')
						okk = false;
				}
			}
			if (okk) ok = true;
			continue;
		}
		bfs(nh, nw);
		field[nh][nw] = '#';
	}
}

int main(int argc, char **argv)
{
	cin >> H >> W;
	for (ll h = 0; h < H; ++h)
		for (ll w = 0; w < W; ++w)
		{
			cin >> field[h][w];
		}
	field[0][0] = '.';
	bfs(0, 0);

	std::cout << (ok ? "Possible" : "Impossible")<< std::endl;
}


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

ll a[3005];
ll pre[3005];
ll dp[3005][3005];

ll sm(int i, int j){
    if (i > j) return 0;
    return (pre[j] - (i > 0 ? pre[i-1] : 0));
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        pre[i] = a[i] + (i ? pre[i-1] : 0);
    }



    for (int l = 0; l < n; l++)
    {
        for (int i = 0; i+l < n; i++)
        {
            int j = i+l;
            dp[i][j] = max(a[i] + sm(i+1, j) - dp[i+1][j],
                           a[j] + sm(i, j-1) - dp[i][j-1]);
        }
    }

    cout << dp[0][n-1] - (sm(0, n-1) - dp[0][n-1]);

    return 0;
}


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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

//#define _USE_MATH_DEFINES
//#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>
#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef int long long i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1000000007; // 10000000000000007ll;

const double eps = 1e-8;

const i64 MAXN = 400005;
const i64 MAXM = 20;


i64 n;
i64 a[MAXN];


int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    string s;
    cin >> s;

    list<char> q;
    for (auto c : s) {
        q.push_back(c);
    }

    i64 T;
    cin >> T;

    bool f = false;
    for (i64 tt = 1; tt <= T; tt++) {
        i64 t;
        cin >> t;
        if (t == 1) {
            f = !f;
        }
        else {
            i64 z;
            char c;
            cin >> z >> c;
            if (z == 1) {
                if (!f) {
                    q.push_front(c);
                }
                else {
                    q.push_back(c);
                }
            }
            else {
                if (f) {
                    q.push_front(c);
                }
                else {
                    q.push_back(c);
                }
            }
        }
    }

    if (f) {
        reverse(q.begin(), q.end());
    }

    stringstream ss;
    for (auto c : q) {
        ss << c;
    }
    cout << ss.str() << endl;

    return 0;
}

Measured memory_bytes: 10708
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i,m,n) for(int i = m - 1; i >= n; i--)
#define ALL(v) v.begin(), v.end()
#define itn int
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
template<typename T, typename U>
inline bool CMAX(T &m, U x) { if (m < x) { m = x; return true; } return false; }
template<typename T, typename U>
inline bool CMIN(T &m, U x) { if (m > x) { m = x; return true; } return false; }

typedef long long lint;
typedef long double ldouble;
const int INF = 1e9;
const lint LINF = 1e18;
const int MOD = 1e9+7;
int main(){
    int n;
    bool flag = true;
    cin >> n;
    REP(i,n){
        int a;
        cin >> a;
        if(a % 2 == 0){
            if(a % 3 != 0 && a % 5 != 0){
                flag = false;
                break;
            }   
        }
    }
    if(flag) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  double a, b, x;
  cin >> a >> b >> x;

  double l = x/(a*a);
  cerr << l << endl;

  double c = atan2(b-l, a/(double)2);
  double d = atan2(l, a/(double)2);
  double e = atan2(b, (double)2*x/b/a);
  cerr << c << endl;
  cerr << d << endl;
  cerr << e << endl;

  if (c > d) printf("%.8lf", e / M_PI *(double)180);
  else printf("%.8lf", c / M_PI * (double)180);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>

#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#include <iomanip>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll mod = 998244353;


char S[2001][2001];
int yoko[2001][2001];
int tate[2001][2001];

int ans, H, W;
queue<int>que;

int TATE(int ta,int yo,int cnt) {//縦を探索！
	if (S[ta][yo] == '#')return cnt-1;
	if (ta >= H) {
		tate[ta][yo] = cnt-1;
		return cnt-1;
	}
	tate[ta][yo] = TATE(ta + 1, yo,cnt+1);
	return tate[ta][yo];
}

int YOKO(int ta, int yo, int cnt) {//横を探索！
	if (S[ta][yo] == '#')return cnt - 1;
	if (yo >= W) {
		yoko[ta][yo] = cnt-1;
		return cnt-1;
	}
	yoko[ta][yo] = YOKO(ta, yo+1, cnt + 1);
	return yoko[ta][yo];
}



int main() {

	cin >> H >> W;

	FOR(i, 0, H)FOR(j, 0, W) {
		cin >> S[i][j];
	}

	FOR(i, 0, H)FOR(j, 0, W) {
		if (S[i][j] == '.'&&tate[i][j] == 0) {
			tate[i][j] = TATE(i, j, 1);
		}
		if (S[i][j] == '.'&&yoko[i][j] == 0) {
			yoko[i][j] = YOKO(i, j, 1);
		}
	}
	FOR(i, 0, H) {
		FOR(j, 0, W) {
			ans = max(ans, tate[i][j] + yoko[i][j]-1);
		}
	}

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

Measured memory_bytes: 35456
N,M = map(int,input().split())
students = [[int(i) for i in input().split()]+[j] for j in range(N)]
checkP = [[int(i) for i in input().split()]+[j] for j in range(M)]
ans = [0]*N
Inf = 10**9
dif = [Inf]*N


for a,b,c in students:
    for i,j,k in checkP:
        if abs(a-i)+abs(b-j) < dif[c]:
            dif[c] = abs(a-i) + abs(b-j)
            ans[c] = k+1

for i in ans:
    print(i)

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
long gcd(long ia, long ib){
    long a, b, r, x, tmp;

    a=ia;
    b=ib;

    x = a * b;

  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

    return (b);
}
int main(){
 long a,b;
 scanf("%ld %ld\n",&a,&b);
long c=gcd(a,b);

//printf("%ld",c);

long ans=1;
long dev=2;
while(dev*dev < c){
	if(c%dev==0){
		ans++;
		while(c%dev==0){
		c/=dev;

		}

	}else{
		dev++;
	}
}
if(c!=1){
    ans++;
}
	printf("%ld",ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double D;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
 
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d %d",&x,&y)
#define rl(x) scanf("%lld",&x)
#define rl2(x,y) scanf("%lld %lld",&x,&y)
#define wd(x) printf("%d" ,x)
#define wd2(x,y) printf("%d %d",x,y)
#define wl(x) printf("%lld",x)
#define wl2(x,y) printf("%lld %lld",x,y)
#define PC(x) putchar(x)
#define GC() getchar()
#define NL printf("\n")
#define SP printf(" ")
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define fr(i,s,e) for(int i=s;i<e;i++)
#define frl(i,s,e) for(ll i=s;i<e;i++)
#define frr(i,s,e) for(int i=s-1;i>=e;i--)
#define frv(i,a) for(int i = 0;i<(int)a.size();i++)
#define frvr(i,a) for(int i = a.size()-1;i>=0;i--)
#define tr(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end();i++)

#define mod 1000000007
#define maxn 100009
#define maxr 100009
int main(){
	//std::ios::sync_with_stdio(false); cin.tie(NULL);
	int n,k,ct=0;
	rd2(n,k);
	vector<int> h(n);
	fr(i,0,n)
	{
		rd(h[i]);
		if(h[i]>=k)
			ct++;
	}
	wd(ct);
	NL;
	return 0;
}

Measured memory_bytes: 640
N = int(input())
L = list(map(int,input().split()))
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[i]!=L[j] and L[j]!=L[k] and L[k]!=L[i]:
                if L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[k]+L[i]>L[j]:
                    cnt += 1
print(cnt)

Measured memory_bytes: 68180
#include <bits/stdc++.h>
using namespace std;
#define int                     long long   
#define double                  long double
#define endl                    "\n"
#define pb                      push_back
#define PI                      3.1415926535897932384626433832795l
#define F                       first
#define S                       second
#define mp                      make_pair
#define f(i,n)                  for(int i=0;i<n;i++)
#define fastio                  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v)                  (v).begin(),(v).end()
#define rall(v)                 (v).rbegin(),(v).rend()
#define gcd(a,b)                __gcd((a),(b))
#define fill(a,value)           memset(a,value,sizeof(a));
#define minn(v)                 *min_element(v.begin(), v.end());
#define maxx(v)                 *max_element(v.begin(), v.end());
#define print(x)                cout<<(x)<<endl;
#define sum(v)+x                accumulate(v.begin(), v.end(),x);
#define debug(x)                cout<<#x<<'='<<(x)<<endl;
typedef pair<int,int>           pii;
typedef vector<int>             vi;
signed main() 
{
    fastio;
    cout << fixed << setprecision(12);
    int n,d;
    cin>>n>>d;
    int ans=0;
    while(n--)
    {
        int x,y;
        cin>>x>>y;
        double z=sqrt(x*x+y*y);
        if(z<=d)ans++;
    }
    print(ans)
    
    
    return 0;
}


Measured memory_bytes: 3692
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define pb(a) push_back(a)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main(){
  string s;
  cin >> s;
  char a = s[0];
  char b;
  if(s[1]!=a){
    b = s[1];
    if(s[2]!=a&&s[2]!=b){
      cout << "No" << endl;
      return 0;
    }else if(s[2]==a){
      if(s[3]==b){
        cout << "Yes" << endl;
        return 0;
      }else{
        cout << "No" << endl;
        return 0;
      }
    }else{
      if(s[3]==a){
        cout << "Yes" << endl;
        return 0;
      }else{
        cout << "No" << endl;
        return 0;
      }
    }
  }else{
    if(s[2]==a){
      cout << "No" << endl;
    }else{
      b = s[2];
      if(s[3]!=b){
        cout << "No" << endl;
        return 0;
      }else{
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
}


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

int main(){
  int n;
  cin >> n;
  vector<int> w(n);
  int sum = 0;
  rep(i, n){
    cin >> w[i];
    sum += w[i];
  }

  int S0 = 0;
  int S1 = 0;
  rep(i, n){
    S0 += w[i];
    if(S0 > sum/2){
      S1 = S0;
      S0 -= w[i];
      break;
    }
  }

  int ans = min(abs(sum-2*S0), abs(sum-2*S1));
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;

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

    int N, K;
    cin >> N >> K;
    vector<ll> a(N);
    rep(i, N) { cin >> a[i]; }

    vector<bool> dp(K + 1, false);
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j < N; j++) {
            if (i - a[j] >= 0) {
                dp[i] = dp[i] || !dp[i - a[j]];
            }
        }
    }

    cout << (dp[K] ? "First" : "Second") << endl;
}

Measured memory_bytes: 3576
n, m = map(int, input().split())
inf = 10 ** 9
dp = [0] + [inf] * ((1 << n) - 1)
for _ in range(m):
    newdp = [p for p in dp]
    a, b = map(int, input().split())
    c = sum(1 << (int(i) - 1) for i in input().split())
    for bits in range(len(dp)):
        newdp[bits | c] = min(newdp[bits | c], dp[bits] + a)
    dp = newdp
print(-1 if dp[-1] == inf else dp[-1])


Measured memory_bytes: 49628
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import Control.Monad
-- import Control.Monad.Trans.State
import Data.ByteString (ByteString)
-- import qualified Data.ByteString.Unsafe as B
import qualified Data.ByteString.Char8 as C8
import Data.Bool
-- import Data.Bits
import Data.Char
import Data.List
import Data.Maybe

main :: IO ()
main = do
  [n] <- readInts
  xs <- replicateM n readStrings
  print . showAnswer . solve $ concat xs

type Output = Int

solve :: [String] -> Output
solve = sum . map (f . length) . group . sort . map (product . map c2i)
  where
    f n = (n * (n-3)) `div` 2 + n

c2i :: Char -> Int
c2i c = p !! (ord c - 97)
  where
    p = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]

f = group . sort . map (sum . map c2i)
xs = ["abaaaaaaaa", "oneplustwo", "aaaaaaaaba", "twoplusone", "aaaabaaaaa"]


showAnswer :: Output -> Answer
showAnswer = Number

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

readStrings :: IO [String]
readStrings = map C8.unpack . C8.words <$> C8.getLine

data Answer
  = YesNo Bool
  | YESNO Bool
  | AB Bool
  | Number Int
  | String String
  | ByteString ByteString
  | Compare Ordering
  | Compare2 Ordering

instance Show Answer where
  show (YesNo b)       = bool "No" "Yes"  b
  show (YESNO b)       = bool "NO" "YES"  b
  show (AB b)          = bool "B"  "A"    b
  show (Number i)      = show i
  show (String s)      = s
  show (ByteString bs) = C8.unpack bs
  show (Compare o)     = ordering "<" "=" ">" o
  show (Compare2 o)    = ordering "Right" "Balanced" "Left" o

ordering :: a -> a -> a -> Ordering -> a
ordering lt eq gt o = case o of
  LT -> lt
  EQ -> eq
  GT -> gt

-- | k 番目の文字に関数 f を適用する
indexMapBS :: Int -> (Char -> Char) -> ByteString -> ByteString
indexMapBS k f s = C8.concat [s1, C8.singleton (f c), s3]
  where
    (s1, s2) = C8.splitAt (k-1) s
    c = C8.head s2
    s3 = C8.tail s2

Measured memory_bytes: 35196
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int M = 30;
int n, f, s;
vector < int > gr[N];
int up[M][N];
int dep[N];

void dfs(int u, int p)
{
    up[0][u] = p;
    dep[u] = dep[p] + 1;

    for (int i = 1; i <= 20; ++i)
    {
        up[i][u] = up[i - 1][up[i - 1][u]];
    }
    for (int v : gr[u])
    {
        if (v != p) dfs(v, u);
    }

}

int lca(int u, int v)
{
    if (dep[v] > dep[u]) swap(u, v);
    for (int i = 20; i >= 0; --i)
    {
        if (up[i][u] != 0 && dep[up[i][u]] >= dep[v]) u = up[i][u];
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; --i)
    {
        if (up[i][u] != 0 && up[i][v] != 0 && up[i][u] != up[i][v]) u = up[i][u], v = up[i][v];
    }
    return up[0][u];
}
int dist(int u, int v)
{
    int e = lca(u, v);
    return dep[u] - dep[e] + dep[v] - dep[e];
}

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

    cin >> n >> f >> s;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    dfs(1, 0);

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i != s && dist(f, i) < dist(s, i))
        {
            ans = max(ans, dist(s, i) - 1);
        }
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 21888
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
using namespace std;
using P = pair<int, int>;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll ans = (1LL << 60) * -1;
  ans = max(ans, a * c);
  ans = max(ans, a * d);
  ans = max(ans, b * c);
  ans = max(ans, b * d);
  cout << ans << endl;
}

Measured memory_bytes: 3612
n=int(input())
s=[]
a,b,c,d,e=0,0,0,0,0
for i in range(n):
  S=input()
  if S[0]=='M':
    a+=1
  if S[0]=='A':
    b+=1
  if S[0]=='R':
    c+=1
  if S[0]=='C':
    d+=1
  if S[0]=='H':
    e+=1
print(a*b*c+a*b*d+a*b*e+a*c*d+a*c*e+a*d*e+b*c*d+b*c*e+b*d*e+c*d*e)



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

int h, w;

int bomb_count(vector<vector<char>> &v, int x, int y) {
  vector<int> dx{ x - 1, x,     x + 1, x + 1, x + 1, x    , x - 1, x - 1 };
  vector<int> dy{ y - 1, y - 1, y - 1, y,     y + 1, y + 1, y + 1, y };

  int num = 0;
  for (int i = 0; i < 8; i++) {
    int xx = dx.at(i);
    int yy = dy.at(i);
    if (xx >= 0 && xx < h && yy >= 0 && yy < w) {
      if (v.at(xx).at(yy) == '#') {
        num++;
      }
    }
  }
  return num;
}

int main() {
  cin >> h >> w;

  vector<vector<char>> v(h, vector<char>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> v.at(i).at(j);
    }
  }

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (v.at(i).at(j) == '.') {
        cout << bomb_count(v, i, j);
      } else {
        cout << '#';
      }
    }
    cout << endl;
  }

  return 0;
}

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

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
  if(ch == 'A') return 1;
  else if(ch == 'C')return 2;
  else if(ch == 'G')return 3;
  else if(ch == 'T')return 4;
  else return 0;
}

long long getKeeey(char str[]){
  long long goukei = 0, p = 1, i;
  for( i = 0; i < strlen(str); i++){
    goukei += p*(getChar(str[i]));
    p *= 5;
  }
  return goukei;
}

int h1(int keeey){return keeey % M;}
int h2(int keeey){return 1 + (keeey % (M - 1));}

int find(char str[]){
  long long keeey, i, h;
  keeey = getKeeey(str);
  for(i = 0;; i++){
    h = (h1(keeey) + i * h2(keeey)) % M;
    if( strcmp(H[h],str) == 0)return 1;
    else if(strlen(H[h]) == 0) return 0;
  }
  return 0;
}

int insert(char str[]){
  long long keeey, i, h;
  keeey = getKeeey(str);
  for( i = 0; ; i++){
    h = (h1(keeey) + i * h2(keeey)) % M;
    if(strcmp(H[h],str) == 0) return 1;
    else if(strlen(H[h]) == 0){
      strcpy(H[h],str);
      return 0;
    }
  }
  return 0;
}

int main(){
  int i,n,h;
  char str[L],com[9];
  for(i = 0; i < M; i++)H[i][0] = '\0';
  scanf("%d",&n);
  for (i = 0; i < n; i++){
    scanf("%s %s",com,str);

    if(com[0] == 'i'){
      insert(str);
    }
    else{
      if(find(str)){
	printf("yes\n");
      }
      else{
	printf("no\n");
      }
    }
  }
  return 0;
}



Measured memory_bytes: 16036
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define y1 abcde
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 2e9;
const int N = 1e5 + 15;
int n, m, deg[N], cnt[N];
set <int> g[N];
set <pii> ans;
vector <int> g0[N];
bool used[N];

void dfs0(int v) {
    used[v] = true;
    for(int to : g0[v])
        if(!used[to]) {
            dfs0(to);
            cnt[v] ^= cnt[to];
            if(cnt[to]) {
                if(g[v].find(to) != g[v].end()) {
                    g[v].erase(to);
                    g[to].insert(v);
                }
                else {
                    g[to].erase(v);
                    g[v].insert(to);
                }
                deg[v] ^= 1;
                deg[to] ^= 1;
                cnt[v] ^= 1;
            }
        }
    cnt[v] ^= deg[v];
}

main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g0[u].pb(v);
        g0[v].pb(u);
        if(uniform_int_distribution<>(0, 5)(rng) & 1) {
            g[u].insert(v), deg[u] ^= 1;
        }
        else
            g[v].insert(u), deg[v] ^= 1;
    }
    if(m & 1) {
        puts("-1");
        return 0;
    }
    dfs0(1);
    for(int i = 1; i <= n; ++i)
        for(int to : g[i])
            printf("%d %d\n", i, to);
    return 0;
}


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

int main() {
	// your code goes here
	string x,y;
	cin >> x >> y;
	int i = 0,j = 0;
	int n = x.length();
	int m = y.length();
	while(i < n && j < m) {
	    cout << x[i];
	    cout << y[j];
	    i++;
	    j++;
	}
	while(i < n) {
	    cout << x[i];
	    i++;
	}
	while(j < m) {
	    cout << y[j];
	    j++;
	}
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = list(map(int, input().split()))
    paths = [list(map(int, input().split())) for _ in range(M)]
    result = solve(N, paths)
    print(result)


def solve(N, paths) -> int:
    uf = UnionFind(N)
    for x, y in paths:
        uf.union(x - 1, y - 1)
    return uf.group_count() - 1


if __name__ == '__main__':
    main()


Measured memory_bytes: 29420
from itertools import combinations_with_replacement
n, k = map(int, input().split())
d = [int(x) for x in input().split()]
dd = set(list(range(10))) - set(d)

x = str(n)
lst = []
dd = list(dd)
dd.sort()
sel = []
for i in dd:
    if int(x[0]) <= i and len(sel) < 3: sel.append(i*10**(len(x)-1))
if len(sel) < 2:
    if len(dd) == 1:
        sel.append((dd[0]*10 + dd[0])* 10 ** (len(x)-1))
    else:
        if dd[0] != 0:
            sel.append((dd[0]*10 + dd[0])* 10 ** (len(x)-1))
        else:
            sel.append((dd[1]*10 + dd[0])* 10 ** (len(x)-1))
for j in sel:
    for l in combinations_with_replacement(dd, len(x)-1):
        cnt = j
        for i in range(len(x)-1):
            cnt += 10 ** (len(x)-i-2) * l[i]
        if cnt >= n: lst.append(cnt)
print(min(lst))

Measured memory_bytes: 9208
// Working program with FastReader
import java.io.BufferedReader; 

import java.io.IOException; 
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner; 
import java.util.StringTokenizer;
import java.lang.*;
public class Main
{ 
	static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 

		public FastReader() 
		{ 
			br = new BufferedReader(new
					InputStreamReader(System.in)); 
		} 

		String next() 
		{ 
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken(); 
		} 

		int nextInt() 
		{ 
			return Integer.parseInt(next()); 
		} 

		long nextLong() 
		{ 
			return Long.parseLong(next()); 
		} 

		double nextDouble() 
		{ 
			return Double.parseDouble(next()); 
		} 

		String nextLine() 
		{ 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		} 
	} 

	long gcd(long a, long b) {
		if(b==0) {
			return a;
		}
		return gcd(b,a%b);
	}
	public static void main(String[] args) {
		FastReader ob = new FastReader();
		int n =ob.nextInt();
		int len = ob.nextInt();
		String arr[] = new String[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = ob.next();
		}
		Arrays.parallelSort(arr);
		String ans="";
		for (int i = 0; i < arr.length; i++) {
			ans+=arr[i];
		}
		System.out.println(ans);
	}

} 


Measured memory_bytes: 23508
//C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

//ここまで毎回include
//以下プログラム

using namespace std;

int main() {
	int x, y;
	cin >> x >> y;
	int result = INT_MAX;
	if (x <= y) {
		result = min(result, 0 + y - x + 0);
	}
	if (x * -1 <= y) {
		result = min(result, 1 + y - x * -1 + 0);
	}
	if (x <= y * -1) {
		result = min(result, 0 + y * -1 - x + 1);
	}
	if (x * -1 <= y * -1) {
		result = min(result, 1 + y * -1 - x * -1 + 1);
	}
	cout << result << endl;
}

Measured memory_bytes: 256
import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import java.lang.*;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        System.out.println(Math.min(Math.min(a+b,b+c),a+c));

    }
}


Measured memory_bytes: 35644
import Control.Monad
import Control.Applicative

type Vector = [Int]
type Matrix = [[Int]]


productV :: Vector -> Vector -> Int
productV [] _ = 0
productV _ [] = 0
productV (x:xs) (y:ys) = x * y + productV xs ys

solver :: Matrix -> Vector -> Vector
solver _ [] = []
solver [] _ = []
solver (x:xs) v = productV x v : solver xs v

main :: IO()
main = do
  (n:m:_) <- map (read :: String -> Int) . words <$> getLine
  mat <- map (map (read :: String -> Int) . words) <$> replicateM n getLine
  vec <- map (read :: String -> Int) <$> replicateM m getLine
  mapM_ print $ solver mat vec

Measured memory_bytes: 7464
n = str(input())
a = int(n[len(n)-1])
if a == 2 or a == 4 or a == 5 or a == 7 or a == 9:
    print('hon')
elif a == 0 or a == 1 or a == 6 or a == 8:
    print('pon')
else:
    print('bon')


Measured memory_bytes: 9112
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <chrono>

using namespace std;

int main(int argc, const char * argv[]) {
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int x; cin >> x;
    
    cout << (x == 7 || x == 5 || x == 3 ? "YES" : "NO") << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

bool cmp(P a, P b) { return a.second < b.second; }

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n;
  cin >> n;
  vector<P> a(n);
  rep(i,n) {
    ll x, l;
    cin >> x >> l;
    a[i].first = x-l;
    a[i].second = x+l;
  }
  sort(all(a),cmp);
  ll preend = -(1LL<<60);
  int ans = 0;
  rep(i,n) {
    debug(a[i].first, a[i].second);
    if (a[i].first < preend) continue; //ng
    ans++;
    preend = a[i].second;
  }
  cout << ans << endl;
  return 0;
}

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

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a);
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;

ll a, b;

int main() {
	fast;

	cin >> a >> b;

	ll k = __gcd(a, b);

	ll cnt = 0;
	for(ll i=2; i*i <= k; i++) {
		if(k % i == 0) {
			cnt++;
			while(k % i == 0) k /= i;
		}
	}

	if(k > 1) cnt++;

	cout << cnt+1;
}

Measured memory_bytes: 256
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].append(v)


from collections import defaultdict
graphAB = defaultdict(list)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'

#print(graphAB)
#print(graphABopp)

sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')





Measured memory_bytes: 71540
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#include<queue>
#define MAX 120000
using namespace std;

int A[MAX],n,k;

int check(int x){
  int t=0,hantei=1;
  for(int i=0;i<n;i++){
    if(A[i]>x) return 0;
    t+=A[i];
    if(t>x){
      t=0;
      t=A[i];
      hantei++;
    }
    if(hantei>k) return 0;
  }
  return n;
}


int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  long long left,right,mid;
  left=0;right=1000000000;
  while(left+1<right){
    mid=(left+right)/2;
    if(check(mid)==n) right=mid;
    else left=mid;
    
  }
  cout<<right<<endl;


}



Measured memory_bytes: 3484
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

struct Event
{
    bool start;
    float time;
    int channel;
    int program;
};

Event events[200'000];
bool isRecording[30];
int currentProgram[30];

int main()
{
    int N, C;

    cin >> N >> C;
    for (int i = 0; i < N; i++)
    {
        int s, t, c;
        cin >> s >> t >> c;

        Event ev0, ev1;
        ev0.start = true;
        ev1.start = false;
        ev0.channel = ev1.channel = c;
        ev0.time = s - 0.5;
        ev1.time = t;
        ev0.program = i;
        ev1.program = i;

        events[2 * i] = ev0;
        events[2 * i + 1] = ev1;
    }

    for (int i = 0; i < C; i++)
    {
        isRecording[i] = false;
    }

    sort(events, events + (2 * N), [](const auto &lh, const auto &rh) {
        return lh.time < rh.time;
    });

    int recCount = 0;
    int recMax = 0;
    for (int i = 0; i < 2 * N; i++)
    {
        const auto &ev = events[i];

        if (ev.start)
        {
            if (!isRecording[ev.channel])
            {
                recCount++;
            }
            isRecording[ev.channel] = true;
            currentProgram[ev.channel] = ev.program;
        }
        else
        {
            if (currentProgram[ev.channel] == ev.program)
            {
                isRecording[ev.channel] = false;
                recCount--;
            }
        }

        //cout << "time: " << ev.time << (ev.start ? " start " : " end ") << " channel: " << ev.channel << endl;
        //cout << "recCount: " << recCount << endl;

        recMax = max(recMax, recCount);
    }

    cout << recMax << endl;

    return 0;
}

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

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

int main() {

    ll n; cin >> n;

    vector<ll> ans(n, 0);

    for (ll i = 2; i <= n; ++i) {
        ll a; cin >> a;
        a--;
        ans[a]++;
    }

    for (ll i = 0; i < n; ++i) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 4768
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i=l;i<=r;i++)
using namespace std;
typedef long long ll;
int a,b,c,ans,N,K,M,tt,t,q[200007],ansx[200007],ansy[200007];
int main(){
	scanf("%d",&N);
	rep(i,1,N) scanf("%d",&q[i]);
	sort(q+1,q+N+1);
	int p=N; while (p>2&&q[p-1]>0) p--;
	int s=q[1];
	rep(i,p,N-1){
		ansx[++t]=s;ansy[t]=q[i];
		s-=q[i];
	}
	ansx[++t]=q[N];ansy[t]=s;
	s=q[N]-s;
	rep(i,2,p-1){
		ansx[++t]=s;ansy[t]=q[i];
		s-=q[i];
	}
	printf("%d\n",s);
	rep(i,1,t) printf("%d %d\n",ansx[i],ansy[i]);
	return 0;
}


Measured memory_bytes: 3072
mod = 10 ** 9 + 7

K = map(int, input())
D = int(input())

s = 0
dp = [0] * D
for k in K:
    ndp = [0] * D
    for d in range(10):
        for i, dpi in enumerate(dp):
            ndp[(i + d) % D] += dpi

    for d in range(k):
        ndp[(s + d) % D] += 1

    s = (s + k) % D
    dp = [x % mod for x in ndp]

print((dp[0] - (s != 0)) % mod)

Measured memory_bytes: 44636
n=int(input())
C0=0
C1=0
C2=0
C3=0
for i in range(n):
    s=input()

    if s=='AC':
       C0+=1
    if s=='WA':
       C1+=1
    if s=='TLE':
       C2+=1
    if s=='RE':
       C3+=1
print('AC x '+str(C0))
print('WA x '+str(C1))
print('TLE x '+str(C2))
print('RE x '+str(C3))

Measured memory_bytes: 9152
import sys
import heapq as h
stdin = sys.stdin

ni = lambda: int(ns())
nl = lambda: list(map(int, stdin.readline().split()))
nm = lambda: map(int, stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def dist(p,q):
  px,py,pr = p
  qx,qy,qr = q
  d = ((px-qx)**2 + (py-qy)**2)**.5
  return max(d-(pr+qr),0)
  
  

xs,ys,xt,yt = nm()
n = ni()
pl = [(xs,ys,0)] + [tuple(nm()) for _ in range(n)] + [(xt,yt,0)]
gr = [dict() for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    gr[i][j] = dist(pl[i],pl[j])
    gr[j][i] = gr[i][j]

dis = [float("inf")]*(n+2)
q = [(0,0)]
while q:
  d,v = h.heappop(q)
  if dis[v] <= d:
    continue
  dis[v] = d
  for x in gr[v]:
    if dis[x] > dis[v]+gr[v][x]:
      h.heappush(q,(dis[v]+gr[v][x],x))
print(dis[-1])



Measured memory_bytes: 145672
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>
int gcd(int a,int b){
    if(a<b){
        int tmp=b;
        b=a;
        a=tmp;
    }
    int r=a%b;
    while(r>0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

int main(int argc, const char * argv[]) {
    int n;
    long long sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                sum+=gcd(i,gcd(j,k));
            }
        }
    }
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

ll gcd(ll x, ll y) {
    return y ? __gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
    return x/__gcd(x, y)*y;
}

int main() {
    ll X; cin >> X;
    cout << lcm(360, X) / X << endl;
}

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

template<typename T>
vector<T> compress(vector<T> A){
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    return A;
}

struct UnionFind {
    vector<int> par;
    vector<int> sz;

    UnionFind(int n=0){ if(n>0) initialize(n); }
    void initialize(int n){
        par.resize(n);
        sz.assign(n, 1);
        for(int i=0; i<n; i++){
            par[i] = i;
        }
    }

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }

    bool unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return false;
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = y;
        sz[y] += sz[x];
        return true;
    }

    bool same(int x, int y){ return find(x) == find(y); }
    int size(int x){ return sz[find(x)]; }
};

int main(){
    int N, M;
    cin >> N >> M;
    
    // 無限に遠いところの座標値
    int64_t INF = 2e9;
    
    // 座標圧縮前の座標（正負の無限遠を含む）を入れていく。
    vector<int64_t> xs = {-INF, INF}, ys = {-INF, INF};
    // 直線の端点について、それを挟む座標を入れる。
    auto add = [&](int64_t x, int64_t y){
        xs.push_back(x-1);
        xs.push_back(x);
        ys.push_back(y-1);
        ys.push_back(y);
    };

    vector<int64_t> A(N), B(N), C(N), D(M), E(M), F(M);
    for(int i=0; i<N; i++){
        cin >> A[i] >> B[i] >> C[i];
        add(A[i], C[i]);
        add(B[i], C[i]);
    }
    for(int i=0; i<M; i++){
        cin >> D[i] >> E[i] >> F[i];
        add(D[i], E[i]);
        add(D[i], F[i]);
    }
    xs = compress(xs);
    ys = compress(ys);

    int xsz = xs.size(), ysz = ys.size();

    // リアル座標値が圧縮座標のどのインデックスに含まれるかを求める
    auto find_x = [&](int a)->int{ return lower_bound(xs.begin(), xs.end(), a) - xs.begin(); };
    auto find_y = [&](int a)->int{ return lower_bound(ys.begin(), ys.end(), a) - ys.begin(); };

    // 圧縮後の座標の、真上に線がある/真左に線がある
    static bitset<6100> above[6100], left[6100];

    // 線を引く
    for(int i=0; i<N; i++){
        A[i] = find_x(A[i]);
        B[i] = find_x(B[i]);
        C[i] = find_y(C[i]);
        for(int x=A[i]; x<B[i]; x++) left[x][C[i]] = 1;
    }
    for(int i=0; i<M; i++){
        D[i] = find_x(D[i]);
        E[i] = find_y(E[i]);
        F[i] = find_y(F[i]);
        for(int y=E[i]; y<F[i]; y++) above[D[i]][y] = 1;
    }

    // UnionFindで扱うために1次元に潰す
    auto encode = [&](int i, int j){ return i*ysz+j; };
    UnionFind uf(xsz*ysz);

    // 線が引いていないところを連結
    for(int i=1; i<xsz; i++) for(int j=0; j<ysz-1; j++){
        if(!above[i][j]) uf.unite(encode(i, j), encode(i-1, j));
        if(!left[i][j]) uf.unite(encode(i, j), encode(i, j-1));
    }

    // 牛と同じ連結成分にある座標について面積を足す。無限遠と連結ならINF
    auto fail = [](){
        cout << "INF" << endl;
        exit(0);
    };
    int cow = encode(find_x(0), find_y(0));
    int64_t ans = 0;
    for(int i=0; i<xsz; i++) for(int j=0; j<ysz; j++) if(uf.same(cow, encode(i, j))){
        if(i==0 || i==xsz-1 || j==0 || j==ysz-1) fail();
        int64_t dx = xs[i] - xs[i-1], dy = ys[j] - ys[j-1];
        ans += dx*dy;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 294244
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <time.h>

#include <string>

const int MAX_N = 200050;
int N;

long long A[MAX_N], AC_X[MAX_N], AC_S[MAX_N];

long long xor_seg(const int l, const int r) {
    return AC_X[r] ^ AC_X[l-1];
}

long long sum_seg(const int l, const int r) {
    return AC_S[r] - AC_S[l-1];
}

int main(int argc, char **argv) {
    std::cin >> N;

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

    AC_X[0] = 0;
    AC_S[0] = 0;

    for (int i = 1; i <= N; i++) {
        AC_X[i] = AC_X[i-1] ^ A[i];
        AC_S[i] = AC_S[i-1] + A[i]; 
    }

    //std::cout << xor_seg(1, 3) << " " << sum_seg(1, 3) << std::endl;

    long long ret = 0;
    for (int i = 1; i <= N; i++) {
        long long lb = i;
        if (xor_seg(i, N) == sum_seg(i, N)) {
            lb = N;
        } else {
            long long ub = N;
            while (lb + 1 < ub) {
                long long mid = (lb + ub) / 2;
                if (xor_seg(i, mid) == sum_seg(i, mid)) {
                    lb = mid;
                } else {
                    ub = mid;
                }
            }
        }
        //std::cout << i << " " << lb << std::endl;
        ret += lb - i + 1;
    }
    std::cout << ret << std::endl;

    return 0;

    
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const unsigned int M = 1000000007;

int32_t main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,pr=1,pr1=2,pr2=1;
    cin>>n;
    for(int i=0;i<n;i++){
    	pr=((pr%M)*10)%M;
    }
    for(int i=0;i<n;i++){
    	pr1=((pr1%M)*9)%M;
    }
    for(int i=0;i<n;i++){
    	pr2=((pr2%M)*8)%M;
    }
    cout<<((pr - (pr1-pr2)) + M)%M;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
char c[100001];
int main(){
	scanf("%s",c);
	int l=strlen(c);
	bool p=false;
	for(int i=0;i<l;i++){
		if(c[i]=='A'&&c[i+1]=='C'){
			p=true;
			break;
		}
	}
	if(p)printf("Yes\n");
	else printf("No\n");
	return 0;
}

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

int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            int ans = 4*i + 7*j;   
            if(ans == n){
                cout << "Yes";
                return 0;
            }
        }
    }
    
    cout << "No";
    
    
}


Measured memory_bytes: 256