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

using namespace std;

typedef long long       ll;

#define all(x)            (x).begin(),(x).end()
#define Sort(x)            sort(all(x))
#define A               first
#define B               second
#define sep             ' '
#define fast_io         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define set_random     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())

const int MAX1 = 5e3+10,
         Md = 1e9+7,
		 Base = 257;

ll n, m, sum, ans, adad, num[MAX1], dp[MAX1];

bool Check(ll flg){
	fill(dp, dp+MAX1, 0);
	dp[0] = 1;
	for (int i = 1; i <= n; ++i){
		if (i == flg)	continue;
		for (int j = m-1; j >= num[i]; --j){
			dp[j] |= dp[j-num[i]];
		}
	}
	for (int i = m-1; i >= m-num[flg]; --i){
		if (dp[i])	return false;
	}
	return true;
}

int main(){
    fast_io;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
    	cin >> num[i];
	}
	sort(num+1, num+n+1);
	ll L = 0, R = n+1, Mid;
	while (R-L > 1){
		Mid = (R+L)/2;
		if (Check(Mid))	L = Mid;
		else	R = Mid;
	}
	cout << L << '\n';
    return 0;
}
/*               now or never                 */


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

int main() {
  int N;
  cin >> N;
  vector<long> A(N + 1);
  vector<long> B(N);
  for(int i = 0;i < N + 1;i++)cin >> A.at(i);
  for(int i = 0;i < N;i++)cin >> B.at(i);
  long ma[100010];
  long mb[100010];
  if(A.at(0) + A.at(1) < B.at(0)){
    ma[0] = A.at(0);
    mb[0] = A.at(1);}
  else if(A.at(0) < B.at(0) && A.at(0) + A.at(1) >= B.at(0)){
    ma[0] = A.at(0);
    mb[0] = B.at(0) - A.at(0);}
 else if(A.at(0) >= B.at(0)){
   ma[0] = B.at(0);
   mb[0] = 0;}
  for(int i = 1;i < N;i++){
    if(A.at(i) + A.at(i + 1) - mb[i - 1] < B.at(i)){
   ma[i] = A.at(i) - mb[i - 1];
   mb[i] = A.at(i + 1);}
    else if(A.at(i) - mb[i - 1] < B.at(i) && A.at(i) + A.at(i + 1) - mb[i - 1] >= B.at(i)){
   ma[i] = A.at(i) - mb[i - 1];
   mb[i] = B.at(i) - A.at(i) + mb[i - 1];}
    else{
   ma[i] = B.at(i);
   mb[i] = 0;}
  }
  long long X = 0;
  for(int i = 0;i < N;i++){
    X += ma[i];
    X += mb[i];
  }
    cout << X << endl;
}


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

int main()
{
    ll X;
    cin >> X;

    int max = 10e5 + 3, ans = max;
    vector<bool> isPrime = vector<bool>(max, true);

    for (int i = 2; i < max; i++)
    {
        if (isPrime[i])
        {
            if (X <= i)
            {
                ans = i;
                break;
            }
            rep(j, max / i) isPrime[j * i] = false;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
#define PP 1000000007
using namespace std;

int main(){
ll N, Ans = 0, wt = 0;cin >> N;
string S;cin >> S;
vector<ll> V(N);

if(S[0] == '.')wt++;

rep(i, 1, N){

  V[i] = V[i - 1];

  if(S[i - 1] == '#')V[i]++;

  if(S[i] == '.')wt++;

}

Ans = wt;

rep(i, 0, N){

  ll A = 2*V[i] + wt - i;

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

  else A++;

  Ans = min(Ans, A);//cout << A << endl;

}

cout << Ans;

}

Measured memory_bytes: 5224
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

constexpr int dx[] = {-1, 0, 1, 0};
constexpr int dy[] = {0, -1, 0, 1};

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

// 二項係数
// 計算量 O(r)
template <typename T>
constexpr T combination(long long n, long long r) {
	if(n < r || n < 0 || r < 0) {
		return T(0);
	}
	T ret = 1;
	r = std::min(r, n - r);
	for(int i = 0; i < r; i++) {
		ret *= (n - i);
		ret /= i + 1;
	}
	return ret;
}

int main() {
	int n, m;
	cin >> n >> m;
	cout << (combination<int>(n, 2) + combination<int>(m, 2)) << endl;
	return 0;
}


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

int main() {
	
	int n;
	string a, b, c;
	cin >> n;
	cin >> a;
	cin >> b;
	cin >> c;
	
	int count = 0;
	for (int i=0; i<n; i++) {
		if (a[i]==b[i] && b[i]==c[i] && c[i]==a[i]) {
			
		} else if (a[i]!=b[i] && b[i]!=c[i] && c[i]!=a[i]) {
			count += 2;
		} else {
			count++;
		}
	}
	cout << count << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
/**CLICK ss---> ctrl+j**/
#define PI 2.0*acos(0.0)
#define ll              long long int
#define gcd(a,b)        __gcd(a,b)
#define lcm(a,b)        ((a)*(b))/gcd(a,b)
#define MOD             1000000007
#define mx              123456789
using namespace std;
void solve()
{
    string s;
    int cnt=0;
    int i;
    cin>>s;
    int ans=0;
    for(i=0; i<s.size(); i++)
    {
        if(s[i]=='R')
            cnt++;
        else
        {
            ans=max(ans,cnt);
            cnt=0;
        }
    }
    ans=max(ans,cnt);
    cout<<ans<<endl;
}
int main()
{
    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pi 3.1415926536
#define pb push_back
#define ff first
#define ss second
#define N 1000000007
#define INF (1ll<<60) - 1
#define M 998244353
#define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define nrep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t,i,j,x,y,q,n,z,l,k,r,ans=0,m;
    cin>>n;
    ll a[n+5];
    rep(i,0,n-1) cin>>a[i];
    sort(a,a+n);
    if(n==2){
    	cout<<a[1];
    	return 0;
	}
    if(n%2 == 0){
    	rep(i,n/2,n-1){
    		ans+=2*a[i];
		}
		ans-=a[n-1];
		cout<<ans;
	}else{
		rep(i,n/2+1,n-1){
    		ans+=2*a[i];
		}
		ans-= a[n-1];
		ans+=a[n/2];
		cout<<ans;
	}
}

Measured memory_bytes: 5188
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();

        int[] arr = new int[n+1];

        for(int i = 0; i < q; i++) {
        	arr[sc.nextInt()]++;
        }

        for(int i = 1; i <= n; i++) {
       		if(k - q + arr[i] > 0)
        		System.out.println("Yes");
        	else
        		System.out.println("No");
        }	

        
    }
}


Measured memory_bytes: 63944
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long LL;
typedef unsigned long long ULL;
const LL LINF = 0x3f3f3f3f3f3f3f3f; 
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const ULL P = 131;
const int N = 2e5+7;

struct node{
	int a,b,c,d;
}Q[55];

int main()
{
	LL a,b,n;
	cin>>a>>b>>n;
	cout<<a*min(b-1,n)/b<<endl; 
	return 0;
}

Measured memory_bytes: 3608
num = int(input())
row = [int(s) for s in input().split()]
row[0] -= 1
for i in range(num - 1):
  if row[i + 1] > row[i]:
    row[i + 1] -= 1

p = 0
for i in range(num - 1):
  if row[i] <= row[i + 1]:
    p += 1
    
if p == num - 1:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 14224
N,T = map(int, input().split())
A = [int(i) for i in input().split()]

# 買う数 == 売る数
if T % 2 == 1:
    T -= 1

from heapq import heappop,heappush

place = []
MINA = [float("inf")] * N
for i in range(N):
    if i == 0:
        MINA[i] = A[i]
    else:
        MINA[i] = min(MINA[i-1], A[i])

sub = []
for a,m in zip(A,MINA):
    heappush(sub, m - a)

ans = 1
MAXSUB = heappop(sub)
while sub:
    s = heappop(sub)
    if s == MAXSUB:
        ans += 1
    else:
        break

print(ans)

Measured memory_bytes: 14940
(defun split (input stack-string output-list)
  (let ((chara (car input)))
    (case chara
          ((nil) (append output-list (list stack-string)))
          (#\space (split (cdr input)
                                  '()
                                  (append output-list (list stack-string))))
          (otherwise (split (cdr input)
                                    (concatenate 'string stack-string (list chara))
                                    output-list)))))

(defun input-to-list (input)
  (mapcar #'parse-integer (split (concatenate 'list input)
                                 '()
                                 '())))

(defparameter nm (input-to-list (read-line)))
(defparameter param (loop for i from 1 to (cadr nm)
                          collect (input-to-list (read-line))))
(defparameter p (input-to-list (read-line)))

(defun lampvec (lamp)
  (loop for i from 1 to (car nm)
        collect (if (member i (cdr (nth lamp param)))
                    1
                    0)))

(defun dot (lst1 lst2)
  (reduce #'+ (mapcar #'* lst1 lst2)))

(defun addswitch (pattern lamp)
  (dot pattern (lampvec lamp)))

(defun checkpat (pattern)
  (labels ((inner (lamp)
                  (if (eq lamp (cadr nm))
                      1
                      (if (eq (nth lamp p)
                              (mod (addswitch pattern lamp) 2))
                          (inner (1+ lamp))
                          0))))
          (inner 0)))

(defun num-pat (num)
  (labels ((inner (num cnt lst)
                  (if (eq cnt (car nm))
                      lst
                      (inner (truncate num 2) (1+ cnt) (cons (mod num 2) lst)))))
          (inner num 0 '())))

(princ (reduce #'+ (loop for i from 0 to (1- (expt 2 (car nm)))
      collect (checkpat (num-pat i)))))

Measured memory_bytes: 18276
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

func Solve() {
  var N, lim, cnt int
  var S []int
  NextInt(&N)
  NextIntSlice(&S)
  ans := 0
  for j := 1; j < N; j++ {
    lim = N - j
    cnt = 0
    if (N - 1) % j == 0 { lim = N / 2 }
    for s := j; s < lim; s += j {
      cnt += S[s] + S[N - 1 - s]
      ans = MaxInt(cnt, ans)
    }
  }
  Write(ans)
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntSlice(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatSlice(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(S ...interface{}) {
  fmt.Fprintln(writer, S...)
}
func WriteIntSlice(A []int) {
  B := make([]interface{}, len(A))
  for i, a := range A { B[i] = a }
  Write(B...)
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

Measured memory_bytes: 7228
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
 
 int n;
 cin>>n;
 int ar[n][3];
 for(int i=0;i<n;++i)
 {
   cin>>ar[i][0]>>ar[i][1]>>ar[i][2];
 }
 int dp[n][3];
 dp[0][0]=ar[0][0];
 dp[0][1]=ar[0][1];
 dp[0][2]=ar[0][2];
 for(int i=1;i<n;++i)
 {
   dp[i][0]=ar[i][0]+max(dp[i-1][1],dp[i-1][2]);
   dp[i][1]=ar[i][1]+max(dp[i-1][0],dp[i-1][2]);
   dp[i][2]=ar[i][2]+max(dp[i-1][0],dp[i-1][1]);
 }
cout<< max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<'\n';
 }
    
  





  



Measured memory_bytes: 5884
n, m = map(int, input().split())
ans = [0] * m
G = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = map(int, input().split())
    G[p].append([y, i])
for i in range(1, n + 1):
    g = G[i]
    g.sort()
    for j in range(len(g)):
        f = g[j]
        s = ["0"] * (6 - len(str(i))) + [str(i)]
        t = ["0"] * (6 - len(str(j + 1))) + [str(j + 1)]
        ans[f[1]] = "".join(s + t)
for i in ans:
    print(i)

Measured memory_bytes: 81824
package main

import (
    "fmt"
)

func main() {
  var a, b int
  fmt.Scan(&a, &b)
  
  if a == b {
    fmt.Print(a + a)
  } else if a > b {
    fmt.Print(2 * a - 1)
  } else {
    fmt.Print(2 * b - 1)
  }
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>
//#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,s,n) for(int i=(s);i<(n);++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define REPR(i,s,n) for(int i=(s);i>=(n);--(i))
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
typedef vector<P> vP;
using Edge = pair<int, ll>;
using Graph = vector<vector<Edge> >;
const ll mod = 1e9 + 7;
ll dx[4] = { 1,0,-1,0 };
ll dy[4] = { 0,1,0,-1 };

void printvll(vll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) cout << v[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}
void printvvll(vvll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) {
		rep(j, v[i].size()) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void prints(string s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) cout << s[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}

void printvs(vs s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) {
		rep(j, s[i].size()) {
			cout << s[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void Yes(bool x) {
	if (x) cout << "Yes\n";
	else cout << "No\n";
}

void YES(bool x) {
	if (x) cout << "YES\n";
	else cout << "NO\n";
}

void yes(bool x) {
	if (x) cout << "yes\n";
	else cout << "no\n";
}

void Yay(bool x) {
	if (x) cout << "Yay!\n";
	else cout << ":(\n";
}
ll gcd(ll x, ll y)
{
	ll r;
	while ((r = x % y) != 0)
	{
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y)
{
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x * y);
}



ll  d, n, r, l, k, ans = 0, ret = M;
bool flag = false, flag2 = false, flag3 = false;
string s, t;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll h;
	cin >> h;
	vll v(h);
	ll x;
	rep(i, h) {
		cin >> v[i];
		if (i == 0) {
			ans++;
			x = v[i];
		}
		else {
			if (x <= v[i]) {
				ans++;
				x = v[i];
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
AB = sorted([LI() for _ in range(N)])
ans = 0
for A,B in AB:
    if M-B>=0:
        ans += A*B
        M -=B
    else:
        ans += A*M
        break
print(ans)


Measured memory_bytes: 28644
#include <stdio.h>
#define EXTREME 1000000000
#define MAX_ELEM 500000


typedef struct card{
    char mark;
    int x;
} Card;

Card L[MAX_ELEM / 2];
Card R[MAX_ELEM / 2];

Card c1[1000000];
Card c2[1000000];

void merge(Card A[], int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;

    for(int i = 0; i < n1; i++) L[i] = A[left+i];
    for(int i = 0; i < n2; i++) R[i] = A[mid+i];
    L[n1].x = EXTREME;
    R[n2].x = EXTREME;

    /* compare with L and R */
    int i = 0, j = 0;
    for(int k = left; k < right; k++){
        if(L[i].x <= R[j].x){
            A[k] = L[i];
            i++;
        } else{
            A[k] = R[j];
            j++;
        }
    }
}

void merge_sort(Card A[], int left, int right){
    if(right - left > 1){
        int mid = (right+left)/2;
        merge_sort(A, left, mid);
        merge_sort(A, mid, right);
        merge(A, left, mid, right);

    }
}


int partition(Card A[], int p, int r){
    int i = p - 1;
    Card last = A[r];
    Card tmp;
    for(int j = p; j < r; j++){
        if(A[j].x <= last.x){
            i += 1;
            tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }

    tmp = A[i + 1];
    A[i + 1]= A[r];
    A[r] = tmp;

    return i + 1;
}

int quicksort(Card A[], int p, int r){
    if(p < r){
        int q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }

    return 0;
}

int main(){
    int i, n, v;

    /* 安定ならば0、不安定なら1を表す変数 */
    int judge = 0;
    char S[10];
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%s %d", S, &v);
        c1[i].mark = c2[i].mark = S[0];
        c1[i].x = c2[i].x = v;
    }


    quicksort(c1, 0, n - 1);
    merge_sort(c2, 0, n);

    for(i = 0; i < n; i++){
        if(c1[i].mark != c2[i].mark){
            judge = 1;
        } 
    }

    if(judge == 1){
        printf("Not stable\n");
    } else{
        printf("Stable\n");
    }

    for(i = 0; i < n; i++){
        printf("%c %d\n", c1[i].mark, c1[i].x);
    }
    return 0;
}


Measured memory_bytes: 4124
def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a, reverse=True)
    all = sum(a)
    c = a[m-1]
    if c >= all / (4*m):
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <math.h>
#include <unordered_map>
#include <numeric>
#include <sstream>
#include <functional>
using namespace std;

int main()
{
	int x,a;

	cin >> x >> a;

	if(x >= a){
		cout << 10 << endl;
	}else{
		cout << 0 << endl;
	}

	return 0;
}


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

using namespace std;

typedef long long ll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
ll modpow(ll a,ll b){
  ll r=1;
  while(b){
    if(b&1)r=r*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return r;
}

const int MX = 10002521;
ll fact[MX];
ll ifact[MX];

int h,w,k;

int main(){
  scanf("%d%d%d",&h,&w,&k);
  
  fact[0] = 1;
  FOR(i,1,MX)fact[i] = fact[i-1]*i%MOD;
  ifact[MX-1] = modpow(fact[MX-1], MOD-2);
  FORR(i,1,MX)ifact[i-1] = ifact[i]*i%MOD;
  ll factk;
  if(k<MX){
    factk = fact[k];
  }else{
    factk = fact[MX-1];
    FOR(i,MX,k+1)factk = factk*i%MOD;
  }
  ll factk1 = factk*(k+1)%MOD;

  ll ans = 0;
  FOR(p,max(0,k-w),min(h,k)+1){
    ll X = p;
    ll Y = k-X;
    ll hPx = fact[h] * ifact[h-X] % MOD;
    ll wPy = fact[w] * ifact[w-Y] % MOD;
    ll ifxy = ifact[X] * ifact[Y] % MOD;
    ll val = factk1 * ifxy % MOD;
    val = val * ifact[3] % MOD * (2*X*Y%MOD + 3*k + 6) % MOD;
    val = (val - factk * ifxy % MOD + MOD) % MOD;
    ans += hPx * wPy % MOD * val % MOD;
  }
  ans %= MOD;
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 156544
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    B = iln(N)
    b = 1
    for n in range(N+1):
        b = B[b-1]
        if b == 2:
            print(n+1)
            break
    else:
        print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 7064
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = 10000000;
int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N )
    {
        cin >> v[ i ] >> w[ i ];
    }
    vector<vector<int>> dp( N + 1, vector<int>( 100001, -INF ) );
    dp[ 0 ][ 0 ] = 0;
    int res{};
    for( int i = 1; i <= N; ++i )
    {
        for( int j = 0; j <= W; ++j )
        {
            if( j >= w[ i - 1 ] )
            {
                dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1 ][ j - w[ i - 1 ] ] + v[ i - 1 ] );
                res = max( res, dp[ i ][ j ] );
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 43040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x, ll y){
    ll res = 1;
    for(ll i=0; i<y; i++){
        res=res*x%mod;
    }
    return res;
}

int main(){
    int N;
    cin >> N;
    ll ans = powmod(10, N) - powmod(9, N) - powmod(9, N) + powmod(8, N);
    ans%=mod;
    ans=(ans+mod)%mod;
    cout << ans << endl;
}

Measured memory_bytes: 3632
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M = map(int, input().split())
xyz = [None] * M
uf = UnionFind(2*N)
for i in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if z % 2:
        uf.unite(x, y+N)
        uf.unite(x+N, y)
    else:
        uf.unite(x, y)
        uf.unite(x+N, y+N)
roots = set()
ans = 0
for i in range(N):
    p1, p2 = uf.find(i), uf.find(i+N)
    if p1 not in roots and p2 not in roots:
        roots.add(p1)
        ans += 1
print(ans)


Measured memory_bytes: 24196
#include<cstdio>
#include<vector>
#define N 100100
#define Q 1000000007
using namespace std;
bool vis[N];
int a[N],stk[N],cnt,num[N],cc,lf[N];
vector<int> cyc[N],g[N];
int dp[N];
int main(){
	int n,ans=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),g[a[i]].push_back(i);
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			int j;
			cnt=0;
			for(j=i;!vis[j];j=a[j]){
				vis[j]=true;
				stk[cnt++]=j;
			}
			do{
				cyc[cc].push_back(stk[--cnt]);
			}while(cnt&&stk[cnt]!=j);
			if(stk[cnt]==j) cc++;
			else cyc[cc].clear();
		}
	}
	for(int i=0;i<cc;i++){
		bool fx=false;
		for(int j=0;j<cyc[i].size();j++){
			int u=cyc[i][j];
			if(g[u].size()>2) ans=0;
			else if(g[u].size()==2){
				fx=true;
				lf[j]=0;
				int v=g[u][0]^g[u][1]^(cyc[i][(j+1)%cyc[i].size()]);
				while(1){
					lf[j]++;
					if(g[v].size()==1) v=g[v][0];
					else{
						if(g[v].size()>1) ans=0;
						break;
					}
				}
			}
			else lf[j]=0;
		}
		if(!fx) num[cyc[i].size()]++;
		else{
			for(int j=0;j<cyc[i].size();j++){
				if(lf[j]){
					for(int k=(j+1)%cyc[i].size();g[cyc[i][k]].size()==1;k=(k+1)%cyc[i].size()){
						lf[j]--;
					}
					if(lf[j]<=0) ans=(ans+ans)%Q;
					else if(lf[j]>1) ans=0;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		dp[0]=1;
		dp[1]=1+(i>1)*(i&1);
		for(int j=2;j<=num[i];j++){
			dp[j]=(dp[1]*dp[j-1]+1LL*(j-1)*i%Q*dp[j-2])%Q;
		}
		ans=1LL*ans*dp[num[i]]%Q;
	}
	printf("%d\n",ans);
	return 0;
}

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

int main(){
	string x;
	cin >> x;
	int ans = x.size(), s = 0;
	for(int i = 0; i < x.size(); i++){
		if(x[i] == 'S') s++;
		else if(s){
			ans -= 2;
			s--;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char[] str = scan.next().toCharArray();
        for(int i = str.length - 1; i >= 0; i--){
            System.out.print(str[i]);
        }
        System.out.println();
        
    }
}


Measured memory_bytes: 25812
#include <cstdio>
#include <cstdlib>

int main(){
    char s[10];
    scanf("%s",s);
    int l = 0;
    for(int i = 0; i < 10; i++){
        if('1' <= s[i] && s[i] <= '9'){
            l++;
        }
    }

    int m = 1000;
    int k;
    for(int i = 0; i <= l - 3; i++){
        k = (s[i] - 48) * 100 + (s[i + 1] - 48) * 10 + (s[i + 2] - 48);
        if(m > abs(753 - k)){
            m = abs(753 - k);
        }
    }

    printf("%d\n",m);

    return 0;
}

Measured memory_bytes: 128
from collections import deque
N = int(input())
A = sorted(list(map(int,input().split())))
A = deque(A)
C = []
while len(A)>1 and A[-1]<=0:
    a = A.pop()
    b = A.pop()
    C.append((a,b))
    A.append(a-b)
if len(A)==1:
    x = A[0]
else:
    B = deque(list(A)[:-1])
    while B[-1]>0:
        a = B.popleft()
        b = B.pop()
        C.append((a,b))
        B.appendleft(a-b)
    B.append(A[-1])
    while len(B)>1:
        a = B.pop()
        b = B.popleft()
        C.append((a,b))
        B.append(a-b)
    x = B[0]
print(x)
for i in range(N-1):
    print(C[i][0],C[i][1])

Measured memory_bytes: 67516
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int i;
int N;
int Alice,Bob;
cin >>N;

int A[100];
for(i=0;i<=N-1;i++){
cin >>A[i];
}
sort(A,A+N);
for(i=N-1;i>=0;i=i-2){
Alice=Alice+A[i];
}
for(i=N-2;i>=0;i=i-2){
Bob=Bob+A[i];
}
cout<<Alice-Bob<<endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
int main(){
  int n;
  cin>>n;
  int a[n][3],dp[n][3];
  for(int i=0;i<n;i++){
    cin>>a[i][0]>>a[i][1]>>a[i][2];
  }
  dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
  for(int i=1;i<n;i++){
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
    dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+a[i][2];
  }
  cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}

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

using namespace std;

int main(){
  string S;
  cin >> S;
  if(S=="SUN") cout << 7 << endl;
  else if(S=="MON") cout << 6 << endl;
  else if(S=="TUE") cout << 5 << endl;
  else if(S=="WED") cout << 4 << endl;
  else if(S=="THU") cout << 3 << endl;
  else if(S=="FRI") cout << 2 << endl;
  else if(S=="SAT") cout << 1 << endl;
  return 0;
}

Measured memory_bytes: 256
using namespace std;
#define MAX_V 1000
#define MAX_E 2000
#define INF 1e9
#include<vector>
#include<iostream>
struct edge
{
	int from, to, cost;
};
int V, E;
int d[MAX_V];
edge es[MAX_E];
bool find_negative_loop(int s)
{
	int count = 0;
	for (int i = 0; i <V; i++)

	{
		d[i] = INF;
	}
	d[s] = 0;
	while (true)
	{
		bool update = false;
		count++;
		for (int i = 0; i < E; i++)
		{
			edge e = es[i];
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost)
			{
				if (count==V)
				{
					return true;
				}
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update)
		{
			break;
		}
	}
	return false;
}

int main()
{
	int r;
	cin >> V >> E >> r;
	for (int i = 0; i < E; i++)
	{
		cin >> es[i].from >> es[i].to >> es[i].cost;
	}

	if (find_negative_loop(r))
	{
		cout<< "NEGATIVE CYCLE" << endl;
	}
	else
	{
		for (int i = 0; i < V; i++)
		{
			if (d[i] == INF)
			{
				cout << "INF" << endl;
			}
			else
			{
				cout << d[i] << endl;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
	cout << fixed << setprecision(10);
	int h,w;
	cin >> h >> w;
	string s[h];
	rep(i,h) cin >> s[i];
	vector<int> hh(h,0), ww(w,0);
	rep(i,h){
		bool ok = 1;
		rep(j,w){
			if(s[i][j]=='#') ok = 0;
		}
		if(ok==1) hh[i] = 1; 
	}
	rep(i,w){
		bool ok = 1;
		rep(j,h){
			if(s[j][i]=='#') ok = 0;
		}
		if(ok==1) ww[i] = 1;
	}
	rep(i,h){
		if(hh[i]==1) continue;
		rep(j,w){
			if(ww[j]==1) continue;
			cout << s[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, flag = 0;
    cin >> n;
    for(int i = 0; i <= n / 4 ; i++)
        for(int j = 0 ; j<= n / 7 ; j++)
        if(i * 4 + j * 7 == n)
        {
            flag=1;
            break;
        }
    if( flag )
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x, n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-------------------------------------------------

struct Polygon {
  int a, b, c;
  Polygon(int a, int b, int c): a(a), b(b), c(c) {}
};

bool operator<(const Polygon& l, const Polygon& r) {
	return std::tie(l.a, l.b, l.c) < std::tie(r.a, r.b, r.c);
}

int n;
map< Polygon, int > mp;

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

	cin >> n;
	REP(i, n) {
		int ls[3];
		cin >> ls[0] >> ls[1] >> ls[2];
		sort(ls, ls + 3);
		mp[Polygon(ls[0], ls[1], ls[2])]++;
	}
	int ans = 0;
	for (auto x: mp) {
		ans += x.se - 1;
	}
	cout << ans << endl;

	return 0;
}





Measured memory_bytes: 3280
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int x, n;
  cin >> x >> n;
  set<int> s;
  for (size_t i = 0; i < n; i++) {
    int y;
    cin >> y;
    s.insert(y);
  }
  int ans = -200;
  for (int i = -200; i <= 300; i++) {
    if (s.find(i) == s.end()) {
      if (abs(x - ans) > abs(x - i)) {
        ans = i;
      }
    }
  }
  cout << ans << "\n";
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int N=4e5+7;
const LL mod=998244353;
const LL inv2=499122177;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifdef ztzshiwo
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,m;
char s[5][N];
LL fac[N],ifac[N];
inline void Add(LL &x,LL y){x=x+y<mod?x+y:x+y-mod;}
inline LL qpow(LL a,LL b)
{
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=ret*a%mod;
	return ret;
}
inline void init(int n)
{
	fac[0]=ifac[0]=1;
	For(i,1,n)fac[i]=fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2);
	rFor(i,n,1)ifac[i-1]=ifac[i]*i%mod;
}
inline LL C(int n,int k)
{
	if(n==k)return 1;
	return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
}
inline LL Solve()
{
	int L=0,R=0,Sl=0,Sr=0;
	For(i,1,n)Sl+=s[1][i-1]-'0',Sr+=s[2][i-1]-'0';
	For(i,1,m)R+=s[3][i-1]-'0'+s[4][i-1]-'0';
	LL now=0,ans=0;
	For(i,1,m)
	{
		int type=s[3][i-1]-'0'+s[4][i-1]-'0';
		if(type)
		{
			Add(now,!Sl?(!L?1:0):C(Sl+L-1,L));
			L+=type,R-=type;
			type==2?Add(now,now):(void)1;
			Add(ans,now*(!Sr?(!R?1:0):C(Sr+R-1,R))%mod);
		}
	}
	return ans;
}
int main()
{
	file();
	read(n),read(m);
	init((n+m)*2);
	For(i,1,4)scanf("%s",s[i]);
	LL ans=0;
	Add(ans,Solve());
	swap(n,m);
	swap(s[1],s[3]);
	swap(s[2],s[4]);
	Add(ans,Solve());
	printf("%lld\n",ans==0?1:ans);
	return 0;
}


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

int main() {

    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    long long int K,L=0;
    int a = -1;
    cin >> K;
    if(K%2 == 0){
        a = -1;
    }
    else{
        for(int i = 0; i<=K;i++){
            L = (L*10)%K+7;
            if(L%K == 0){
                a = i+1;
                break;
            }
        }
        
    }
    cout << a << endl;
    /////////////////////


    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){

  string s,t;
  cin >> s >> t;
  map<char,char> mp;
  rep(i,s.size())mp[s[i]] = t[i];
  for(char c = 'a';c <= 'z';c++){
    for(char ch = 'a';ch <= 'z';ch++){
      if(mp.count(c) == 0 || mp.count(ch) == 0 || c == ch)continue;
      if(mp[c] == mp[ch]){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  rep(i,s.size())s[i] = mp[s[i]];
  cout << (s == t ? "Yes" : "No") << endl;





  return 0;
}

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

using namespace std;
int main()
{
 
   string s;
  cin>>s;
  int i;
  int c1=0,c2=0;
  for(i=0;s[i];++i)
  {
     if(s[i]=='A')
         c1++;
    
      else 
        c2++;
  }
  if(c1>0 && c2>0)
       printf("Yes");
  
  else
     printf("No");  

}
   

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i, N;
	long double p[3000];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%Lf", &(p[i]));
	
	int j;
	long double dp[3000] = {1.0}, ans = 0.0;
	for (i = 1; i <= N; i++) {
		for (j = i; j >= 1; j--) dp[j] = dp[j] * (1.0 - p[i]) + dp[j-1] * p[i];
		dp[0] *= 1.0 - p[i];
	}
	for (i = N; i > N / 2; i--) ans += dp[i];
	printf("%.10Lf\n", ans);
	fflush(stdout);
	return 0;
}

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

static const double pi = 3.141592653589793;
typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
typedef vector<P> VP;
const D EPS = 1e-6;    // 許容誤差。問題によって変える
#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

// 内積　dot(a,b) = |a||b|cosθ
D dot(P a, P b) {
  return (conj(a)*b).X;
}
// 外積　cross(a,b) = |a||b|sinθ
D cross(P a, P b) {
  return (conj(a)*b).Y;
}

int ccw(P a, P b, P c) {
  b -= a;  c -= a;
  if (cross(b,c) >  EPS) return +1;  // counter clockwise
  if (cross(b,c) < -EPS) return -1;  // clockwise
  if (dot(b,c)   < -EPS) return +2;  // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line or a==b
  return 0;                          // a--c--b on line or a==c or b==c
}
// 線分と線分
bool isecSS(P a1, P a2, P b1, P b2) {
  return ccw(a1, a2, b1)*ccw(a1, a2, b2) <= 0 &&
         ccw(b1, b2, a1)*ccw(b1, b2, a2) <= 0;
}

// 線分と点
bool isecSP(P a1, P a2, P b) {
  return !ccw(a1, a2, b);
}

P proj(P a1, P a2, P p) {
  return a1 + dot(a2-a1, p-a1)/norm(a2-a1) * (a2-a1);
}

D distSP(P a1, P a2, P p) {
  P r = proj(a1, a2, p);
  if (isecSP(a1, a2, r)) return abs(r-p);
  return min(abs(a1-p), abs(a2-p));
}

D distSS(P a1, P a2, P b1, P b2) {
  if (isecSS(a1, a2, b1, b2)) return 0;
  return min(min(distSP(a1, a2, b1), distSP(a1, a2, b2)),
             min(distSP(b1, b2, a1), distSP(b1, b2, a2)));
}

int inConvex(P p, const VP& ps) {
  int n = ps.size();
  int dir = ccw(ps[0], ps[1], p);
  rep (i, n) {
    int ccwc = ccw(ps[i], ps[(i + 1) % n], p);
    if (!ccwc) return 2;  // 線分上に存在
    if (ccwc != dir) return 0;
  }
  return 1;
}

D distSB(P p0, P p1, P pb1, P pb2, P pb3, P pb4) {//線分と長方形の距離うちがわに入ると0
	if(inConvex(p0, {pb1, pb2, pb3, pb4}) > 0 or inConvex(p1, {pb1, pb2, pb3, pb4}) > 0) return 0;
	D d = 1e30;
	d = min(d, distSS(p0, p1, pb1, pb2));
	d = min(d, distSS(p0, p1, pb2, pb3));
	d = min(d, distSS(p0, p1, pb3, pb4));
	d = min(d, distSS(p0, p1, pb4, pb1));
	return d;
}

int main() {
	
	/*ifstream in("Ain.txt");
	cin.rdbuf(in.rdbuf());
	ofstream ofs("Aout.txt");
	cout.rdbuf(ofs.rdbuf());
	*/
	cout << setprecision(20);
	int N;
	double sx,sy,ex,ey,x1,x2,y1,y2,h,r;
	while(cin >> N, N) {
		cin >> sx >> sy >> ex >> ey;
		D ans = 1e30;
		P p0 = P(sx, sy);
		P p1 = P(ex, ey);
		rep(n, N) {
			cin >> x1 >> y1 >> x2 >> y2 >> h;
			P pb1 = P(x1, y1);
			P pb2 = P(x1, y2);
			P pb3 = P(x2, y2);
			P pb4 = P(x2, y1);
			D d = distSB(p0, p1, pb1, pb2, pb3, pb4);
			if (d <= h) {
				r = d;
			} else {
				r = (h * h + d * d) / (2 * h);
			}
			ans = min(ans, r);
		}
		cout << ans << endl;
	}
}











Measured memory_bytes: 3124
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

int main() {
	double x1, x2, y1, y2,ans,a;
	cin >> x1 >> y1 >> x2 >> y2;
	a = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
	ans = sqrt(a);
	cout << fixed<< setprecision(6)<<ans;
	return 0;
}



Measured memory_bytes: 3276
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int solve(vector<vector<int> >& a)
{
    int h = a.size();
    int w = a[0].size();

    int ret = 0;
    for(int y=0; y<h; ++y){
        int cnt = 0;
        for(int x=0; x<w; ++x){
            ++ cnt;
            if(x == w-1 || a[y][x] != a[y][x+1]){
                if(a[y][x] != -1 && cnt >= 3){
                    ret += a[y][x] * cnt;
                    for(int i=0; i<cnt; ++i)
                        a[y][x-i] = -1;
                }
                cnt = 0;
            }
        }
    }

    for(int x=0; x<w; ++x){
        int y2 = h-1;
        for(int y=h-1; y>=0; --y){
            if(a[y][x] != -1){
                if(y < y2){
                    a[y2][x] = a[y][x];
                    a[y][x] = -1;
                }
                -- y2;
            }
        }
    }

    return ret;
}

int main()
{
    for(;;){
        int h;
        cin >> h;
        if(h == 0)
            return 0;

        vector<vector<int> > a(h, vector<int>(5));
        for(int y=0; y<h; ++y){
            for(int x=0; x<5; ++x){
                cin >> a[y][x];
            }
        }

        int ret = 0;
        for(;;){
            int p = solve(a);
            if(p == 0)
                break;
            ret += p;
        }
        cout << ret << endl;
    }
}

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

int calculate_sum(int a, int M ,int N) 
{ 
	for (int i = M; i<=N ; i++)
	{
	    if( i % a == 0 )
	    {
	         return 1;
	    }
	}
	
	return 0;
} 

// Driver code 
int main() 
{ 
    int K=0,A=0,B=0;
    
    cin>>K>>A>>B;
	if(calculate_sum(K, A, B) ){
	    cout<<"OK"<<endl;
	}
	else{
	    cout<<"NG"<<endl;
	}
	return 0; 
} 


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
   long long h;
   cin>>h;
   long long cnt = 0;
   int i;
   while(h!=0){
    h/=2;
    cnt++;
   }
   long long time;
   time = pow(2,cnt)-1;
   cout<<time<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include <math.h>
int main(void){
	int a,b,n,i,j,k,x,y,r;
	scanf("%d %d",&x,&y );
	if(x<y){
		n=x;
		x=y;
		y=n;
	}
	r=x%y;
	while(r!=0){
		x=y;
		y=r;
		r=x%y;
	}
	printf("%d\n",y );
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1e9+7;

int main(){
    ll n,a,b;
    cin >> n >> a >> b;
    if(b*(n-1)+a-(a*(n-1)+b)+1 > 0)cout << b*(n-1)+a - (a*(n-1)+b) +1 << endl; 
    else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{   int a,b;
    scanf("%d%d",&a,&b);
    if(b==1){
        printf("0");
        return 0;
    }
    int outlet=a,n=1;
    while(outlet<b){
        outlet+=(a-1);
        n++;
    }
    printf("%d",n);

    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
//#define int long long  ←保留
#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279; //円周率
/*---------------------便利な関数--------------------------------------*/
int fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}

int gcd(int a, int b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

int keta(int n) {        //桁数を求める
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}

int ketasum(int n) {    //各桁の和
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/*-------------ここまで---------------------------------------------*/

//C++(GCC9.2.1)

/*signed*/int main() {
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != t[i]) {
            cout << "No" << "\n";
            return 0;
        }
    }
    cout << "Yes" << "\n";
    return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;


/*define*/
int H, M, A, B;

int main(){
/*inputs*/
    std::cin >> A;
    std::cin >> B;
    std::cin >> H;
    std::cin >> M;

/*syori*/
    double x_A = A*sin((H/12.+M/720.)*2.*M_PI);
    double y_A = A*cos((H/12.+M/720.)*2.*M_PI);
    double x_B = B*sin(M/60.*2.*M_PI);
    double y_B = B*cos(M/60.*2.*M_PI);

    double len = sqrt(std::pow(x_B-x_A,2.)+std::pow(y_B-y_A,2.));
    
    std::cout << std::setprecision(16) << len;
}


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

int main() {
  string s; cin >> s;
  int sn = s.size();
  string ans = "YES";
  map<char,int> ms;
  rep(i,sn) ms[s[i]]++;
  int q = min(min(ms['a'], ms['b']), ms['c']);
  for (auto a : ms) {
    if (a.second - q > 1) {
      ans = "NO";
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3676
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
using namespace std;
#define ll long long int
#define ld long double
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,
tree_order_statistics_node_update> in_set;
#define rep(n) for(ll i=0;i<(n);i++)
#define jrep(n) for(ll j=0;j<(n);j++)
#define all(a) (a).begin(), (a).end()
#define dpp(a) cout<<(a).first<<" "<<(a).second<<endl;
#define append push_back
#define mod 1000000007
#define ff first
#define ss second
#define ffast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fast ios::sync_with_stdio(0);
ll pw(ll x,ll y,ll p=mod){ll r=1; x=x%p;while(y>0){ if(y&1)r=(r*x)%p;
y=y>>1;x=(x*x)%p;} return r; } vector<ll> uniq(vector<ll> arr)
{vector<ll>brr;sort(all(arr));brr.append(arr[0]);
for(auto i:arr)if(brr.back()!=i)brr.append(i);return brr;}
 
void solve(){
    ll n; cin>>n; vector<ll> arr(n); rep(n) cin>>arr[i];
    map<ll,ll> mp; for(auto i:arr) mp[i]++;
    ll cs = 0; for(auto i:mp) cs+=(i.ss*(i.ss-1))/2;
    rep(n){
        cout<<cs-mp[arr[i]]+1<<endl;
    }
}
 
int main(){
    ffast
    ll t=1;
    //cin>>t;
    rep(t) solve();
}
 
 
// *p.find_by_order(n) : nth value (0 indexed)
// p.order_of_key(7): index of 7 (0 indexed)


Measured memory_bytes: 11136
#include <iostream>
#include <vector>
#include <complex>

using namespace std;

const double eps = 1e-10;
typedef complex<double> Point;

inline double cross(const Point& a, const Point& b){
    return imag(conj(a) * b);
}

inline double dot(const Point& a, const Point& b){
    return real(conj(a) * b);
}

int ccw(Point a, Point b, Point c){
    b -= a; c -= a;
    if(cross(b, c) > eps) return  1;
    if(cross(b, c) < -eps)return -1;
    if(dot(b, c) < 0)     return  2;
    if(norm(b) < norm(c)) return -2;
    return 0;
}

typedef vector<Point> Polygon;

bool isconvex(const Polygon& g){
    int n = (int)g.size();
    for(int i=0; i<n; ++i){
        if(ccw(g[i], g[(i+1) % n], g[(i+2) % n]) == -1)return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    Polygon g;
    while(n--){
        int x, y;
        cin >> x >> y;
        g.emplace_back(x, y);
    }
    cout << (isconvex(g)? 1: 0) << '\n';
    return 0;
}

Measured memory_bytes: 1220