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

#define FOR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define rep1(i,n) for (decay_t <decltype (n)> i = 1, i ## __len = (n); i <= i ## __len; ++ i)

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);

  size_t n;
  cin >> n;

  vector <double> p (n);
  for (auto && elem : p) cin >> elem;

  vector <vector <double>> dp (n + 1, vector <double> (n + 1, 0.0));
  dp[0][0] = 1.0;
  // dp[i][j] = コインを左からi枚投げて表がj枚出る確率

  rep1 (i, n)
  {
    FOR (j, 0, n + 1)
    {
      if (j > 0) dp[i][j] += dp[i - 1][j - 1] * p[i - 1];
      dp[i][j] += dp[i - 1][j] * (1.0 - p[i - 1]);
    }
  }

  auto ans = 0.0;
  FOR (j, n / 2, n) ans += dp[n][j + 1];
  cout << fixed << setprecision (15) << ans << endl;
}



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

int main()
{
	int A,B,C,D;
	cin >> A >> B >> C >> D;
	while(A>0 || C>0)
	{
		C -= B;
		if(C<=0)
		{
			break;
		}
		A -= D;
		if(A<=0)
		{
			break;
		}
	}
	if(C<=0)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 3636
N,X=[int(_) for _ in input().split()]
def countP(n):
    if n == 0:
        return 1
    elif n == 1:
        return 3
    else:
        return 1 + countP(n-1) * 2

def countBP(n):
    if n == 0:
        return 3
    elif n == 1:
        return 5
    else:
        return 3 + countBP(n-1) * 2

def countPinBP(n,x):
    if x == 1:
        return 0
    if n == 0:
        if x == 1:
            return 0
        else:
            return 1
    elif n == 1:
        if x == 1:
            return 0
        elif x < 5:
            return x - 1
        else:
            return 3
    else:
        #iH = countBP(n) // 2
        iH = 1 + countBP(n-1)
        if x <= iH:
            return countPinBP(n-1,x-1)
        elif x == iH + 1:
            return countP(n-1) + 1
        else:
            return countP(n-1) + 1 + countPinBP(n - 1, x - iH - 1)
print(countPinBP(N,X))


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;

const long long MOD = 998244353;

int main() {
    int n;
    array<int, 3> count = {}, prev = {};
    string s;
    cin >> n >> s;
    long long result = 1;
    for (char c : s) {
        if (c == 'R') {
            count[0]++;
        } else if (c == 'G') {
            count[1]++;
        } else {
            count[2]++;
        }
        auto sorted = count;
        sort(begin(sorted), end(sorted));
        if (sorted[2] != prev[2]) {
            result = result * sorted[2] % MOD;
        } else if (sorted[0] != prev[0]) {
            result = result * (prev[1] - prev[0]) % MOD;
        } else {
            result = result * (prev[2] - prev[1]) % MOD;
        }
        swap(prev, sorted);
    }
    cout << result;
    return 0;
}

Measured memory_bytes: 900
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main(void)
{
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i=0; i < n; i++) scanf("%d", &a[i]);

    for (int i=0; i < n-1; i++){
        for (int j=i+1; j < n; j++){
            if(a[i] < a[j]){
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }

    int num = 0;
    int alice = 0;
    int bob = 0;
    while(num < n){
        if (num%2 == 0) alice += a[num];
        else bob += a[num];
        num++;
    }

    printf("%d\n", alice - bob);

    return 0;
}



Measured memory_bytes: 128
#!/usr/bin/env python3
import sys
from fractions import gcd
input = sys.stdin.readline
 
class DisjointSparseTable:
    def __init__(self, a):
        # Identity element
        self.e = 0
        self.n = len(a)
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()
 
    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.size, step*2):
                if mid - step >= self.n:
                    continue
                # Forward
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val
 
    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])
 
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Measured memory_bytes: 30128
#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
typedef long long int ll;
using namespace std;
int main(){
	int N;
	ll num;
	cin >> N >> num;
	int count=0;
	ll co=0;
	ll b;
	vector<ll> a;
	for(int i=0;i<N;i++){
		cin >> b;
		a.push_back(b);
	}
	sort(a.begin(),a.end());
	for(int i=0;i<N;i++){
		co+=a[i];
		if(co<=num){
			count++;
		}else{
			break;
		}
	}
	if(co<num){
		count--;
	}
	cout << count << endl;

}

Measured memory_bytes: 256
import java.util.*;

/**
 * @Author: Harry
 * @Date: 2019-11-16
 * @Version 1.0
 */
public class Main {

    static int arr[],t,n,arr2[];

    static int x[],y[];


    static int ans = 0;

    public Main() {
    }

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


        while(input.hasNext()){
            n = input.nextInt();

            x = new int[n];
            y = new int[n];
            arr = new int[n];

            for(int i = 0;i < n;i++){
                arr[i] = i;
            }

            for(int i = 0;i < n;i++){
                x[i] = input.nextInt();
                y[i] = input.nextInt();
            }

            List<List<Integer>> list = permute(arr);

            double sum = 0;
            for(List<Integer> l : list){
                for(int i = 1;i < l.size();i++){
                    int pre = l.get(i - 1);
                    int now = l.get(i);

                    sum += distance(x[pre],y[pre],x[now],y[now]);
                }
            }

            sum = sum / (list.size() * 1.0);

            System.out.println(sum);
        }



    }

    public  static double distance(int x1,int y1,int x2,int y2){
        double x = (x1 - x2) * (x1 - x2);
        double y = (y1 - y2) * (y1 - y2);

        double ans = x + y;

        ans = Math.sqrt(ans);
        return ans;
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        dfs(list,nums,0);

        return list;
    }


    public static void dfs(List<List<Integer>> list,int[] nums,int idx){

        if(idx == nums.length){
            add(list,nums);
        }

        for(int i = idx;i < nums.length;i++){
             int tp = nums[i];
             nums[i] = nums[idx];
             nums[idx] = tp;
//            Collections.swap(nums, i, idx);


            dfs(list,nums,idx + 1);

             tp = nums[i];
             nums[i] = nums[idx];
             nums[idx] = tp;
//            Collections.swap(nums, i, idx);
        }
    }


    public static void add(List<List<Integer>> list,int[] nums){
        List<Integer> tp = new ArrayList<>();

        for(int i : nums){
            tp.add(i);
        }

        list.add(tp);
    }

















}

Measured memory_bytes: 29592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b[4][4];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, x, t;
	cin >> n >> x >> t;
	ll c = n / x;
	if (n % x != 0)
		cout << (c + 1) * t;
	else
		cout << c * t;
	return 0;
}


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


// type definitions
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef complex<int> ci;
typedef complex<double> cd;
typedef complex<long double> cld;

// macros
#define rep(i, a, b) for(int i=a; i<b; i++)
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define tr(c, it) for(auto it=(c).begin(); it!=c.end(); it++)
#define pb push_back
#define mp make_pair
#define bitcount __builtin_popcount
#define ispresent(c, x) ((c).find(x) != (c).end())
#define watch(x) cout<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)

// template functions
template <typename T>
inline void printV(vector<T>& a) { rep(i, 0, sz(a)) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void print(T a) { cout<<a<<"\n"; }
template <typename T>
inline void print(T a, T b) { cout<<a<<" "<<b<<"\n"; }
template <typename T>
inline void print(T a, T b, T c) { cout<<a<<" "<<b<<" "<<c<<"\n"; }
template <typename T>
inline void print(T a, T b, T c, T d) { cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n"; }
template <typename T>
inline void printpii(pair<T, T> p) { cout<<p.first<<" "<<p.second<<"\n"; }
template <typename T>
inline void printVV(vector<vector<T>>& a)
{
	rep(i, 0, sz(a)) {
		printV(a[i]);
	}
	cout<<"\n";
}

template <typename T>
inline void clearVV(vector<vector<T>>& a)
{
	for(auto& x:a) {
		x.clear();
	}
	a.clear();
}
template <typename T>
inline void assignVV(vector<vector<T>> &a, T val)
{
	for(int i=0; i<sz(a); i++) {
		for(int j=0; j<sz(a[i]); j++) {
			a[i][j]=val;
		}
	}
}

template <typename T>
inline void readV(vector<T>& a) { rep(i, 0, sz(a)) cin>>a[i]; }
template <typename T>
inline void read(T& a) { cin>>a; }
template <typename T>
inline void read(T& a, T& b) { cin>>a>>b; }
template <typename T>
inline void read(T& a, T& b, T& c) { cin>>a>>b>>c; }
template <typename T>
inline void read(T& a, T& b, T& c, T& d) { cin>>a>>b>>c>>d; }
template <typename T>
inline void readpii(pair<T, T>& p) { cin>>p.first>>p.second; }
template <typename T>
inline void readVV(vector<vector<T>>& a)
{
	rep(i, 0, sz(a)) {
		readV(a[i]);
	}
}


// constants
const long double eps = 1e-9;
const ll inf = 1e18;
const int modn = 1e9+7;
const int MAX = 1e5;

vector<ll> h;
vector<ll> dp;
int k;

ll solve(int n)
{
	if(n==1) return 0;
	if(n==2) return abs(h[2]-h[1]);
	if(dp[n]!=-1) return dp[n];
	
	ll ans=inf;
	for(int i=1; i<=k and n-i>=1; i++) {
		ans=min(ans, solve(n-i)+abs(h[n]-h[n-i]));
	}
	return dp[n]=ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your code here
	int n;
	cin>>n>>k;
	h.resize(n+1);
	dp.resize(n+1);
	fill(all(dp), -1);
	for(int i=1; i<=n; i++) {
		cin>>h[i];
	}
	cout<<solve(n)<<"\n";
    return 0;
}



Measured memory_bytes: 6528
N = int(input())
X = list(map(int, input().split()))

lower = min(X)
upper = max(X)

min_shouhi = 0
asn_zahyou = 0
for zahyou in range(lower, upper):
    shouhi = 0
    for i in range(N):
        shouhi += (X[i] - zahyou)**2
    
    if zahyou == lower:
        min_shouhi = shouhi
        asn_zahyou = zahyou
    else:
        if min_shouhi > shouhi:
            min_shouhi = shouhi
            asn_zahyou = zahyou

print(min_shouhi)


Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>
#include <bitset>
#include <list>
#include <iomanip>

#define for0(i, N)    for (int i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (int i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (int i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (int i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (int i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (int i = (x), a = 0; a < (N);  \
                              i = (i + 1) % (N), ++a)

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b, int){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b + 1;
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b++;
    return temp;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b, int){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b - 1;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b--;
    return temp;
}

using namespace std;

typedef long long ll;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;
typedef vector<ll> vll;
typedef vector<ld> vld;


int main(void){
    cin.tie(0); ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;

    vll p(n);

    vector<double> e(n);

    for0(i, n) cin >> p[i];

    for0(i, n){
        e[i] = double(p[i] + 1) / 2.0;
    }

    double result = 0;
    double bef = 0;
    for0(i, k){
        bef += e[i];
    }
    result = bef;

    forx(i, n, k){
        result = max(result, bef = bef - e[i - k] + e[i]);
    }

    // cout << setprecision(10) << result;

    // cout << result;

    printf("%f", result);

    return 0;
}


Measured memory_bytes: 3456
N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])

Measured memory_bytes: 60000
import math
N, M = map(int, input().split())
if N>=2:
    n = math.factorial(N)/(math.factorial(2) * math.factorial(N - 2))
else:
    n = 0
if M>=2:
    m = math.factorial(M)/(math.factorial(2) * math.factorial(M - 2))
else:
    m = 0

print(int(n+m))

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

long long gcd(long long a, long long b){
    // 最大公約数
    // ユークリッドの互除法
    if(a < b){
        long long temp = a;
        a = b;
        b = temp;
    }
    long long r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

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

int main(){
    // ai が 2 で割り切れる回数と aj が 2 で割り切れる回数が異なるような i, j が存在するとき、条件を満たす X はありません。
    long long n, m;
    cin >> n >> m;
    long long a, l, pw2_num = 0;
    for(long long i = 0; i < n; i++){
        cin >> a;
        if(i == 0){
            l = a / 2;
            while(a % 2 == 0){
                pw2_num++;
                a /= 2;
            }
            continue;
        }
        l = lcm(l, a / 2);
        if(l > m){
            cout << 0;
            return 0;
        }
        int temp = 0;
        while(a % 2 == 0){
            temp++;
            a /= 2;
        }
        if(temp != pw2_num){
            cout << 0;
            return 0;
        }
    }
    long long cnt = 0;
    for(long long i = 1; ; i += 2){
        if(l * i <= m) cnt++;
        else break;
    }
    cout << cnt;
    return 0;
}

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

ans = 0
for a in AA:
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
            pass
        else:
            ans = 1
            break
if ans == 0:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 2940
import numpy as np

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

A = np.array(A)
B = A[1:] - A[:-1]
B = np.insert(B, N-1, K+A[0]-A[N-1])

B = B.tolist()
max_A = max(B)
max_idx = B.index(max_A)

#print(B)
#print(max_A, max_idx)

print(K-max_A)

Measured memory_bytes: 34136
import sys
N,A,B=map(int, raw_input().split()) 
H=[ int(sys.stdin.readline()) for i in range(N) ] 

def func(n , T):
	sa=A-B
	k=0
	for x in T:
		x-=n*B
		if x>0:
			if x%sa==0:
				k+=x/sa
			else:
				k+=(x/sa+1)
		
			if n<k:
				return False
	else:
			return True

l=0
r=10**9
while l!=r:
	m=(r+l)/2
	if func(m,H):
		r=m
	else:
		l=m+1

print l



Measured memory_bytes: 33180
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
const int N=500010;
int tt;
set <int> w;
int p[N],q[N],head[N],to[N*2],nxt[N*2],in[N];
priority_queue <int> Q;
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') ch=getchar(),o=-1;
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline void lnk(int x,int y) {
    to[++tt]=y,nxt[tt]=head[x],head[x]=tt,++in[y];
}
int main() {
    int n,k;
    cin>>n>>k;
    set <int> :: iterator j;
    for(int i=1;i<=n;i++) q[p[i]=gi()]=i;
    for(int i=1;i<=n;i++) {
	if(i>k) w.erase(p[i-k]);
	j=w.insert(p[i]).first;
	if(++j!=w.end()) lnk(q[*j],i);
    }
    for(int i=n;i;i--) {
	if(i+k<=n) w.erase(p[i+k]);
	j=w.insert(p[i]).first;
	if(++j!=w.end()) lnk(q[*j],i);
    }
    for(int i=1;i<=n;i++)
	if(!in[i]) Q.push(i);
    for(int t=n;t;t--) {
	int x=Q.top();Q.pop();
	p[x]=t;
	for(int i=head[x];i;i=nxt[i])
	    if(!--in[to[i]]) Q.push(to[i]);
    }
    for(int i=1;i<=n;i++) printf("%d\n",p[i]);
    return 0;
}

Measured memory_bytes: 42624
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
int x[201];
int y[201];
int main(void){
  int N,n,d;
  while(cin>>N){
    if(N==0) break;
    int max_x=0, max_y=0, min_x=0, min_y = 0;
    FOR(i,1,N){
      cin>>n>>d;
      x[i] = x[n] +dx[d];
      y[i] = y[n] +dy[d];
      max_x = max(max_x,x[i]);
      min_x = min(min_x,x[i]);
      max_y = max(max_y,y[i]);
      min_y = min(min_y,y[i]);
    }
    printf("%d %d\n",max_x-min_x+1,max_y-min_y+1);
  }
  return 0;
}

Measured memory_bytes: 0
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class BBuffet {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = in.readIntArray(n);
            int[] b = in.readIntArray(n);
            int[] c = in.readIntArray(n - 1);

            for (int i = 0; i < n; i++) {
                a[i]--;
            }

            int answer = 0;
            for (int i = 0; i < n; i++) {
                answer += b[a[i]];
                if (i - 1 >= 0 && a[i - 1] == a[i] - 1) {
                    answer += c[a[i - 1]];
                }
            }

            out.println(answer);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public int[] readIntArray(int n) {
            int[] x = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = nextInt();
            }
            return x;
        }

    }
}



Measured memory_bytes: 22740
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <iostream>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 105;
const double eps = 1e-6;
const double PI = acos(-1.0);

int n;
struct Point {
	int x, y;
}PP[MaxN + 5];

double slope[MaxN + 5];

int main()
{
	//printf("%lf\n", atan2(0, 1));
	while(scanf("%d", &n) != EOF) 
	{
		for(int i = 1; i <= n; i++) scanf("%d %d", &PP[i].x, &PP[i].y);
		for(int i = 1; i <= n; i++) {
			int tot = 0;
			for(int j = 1; j <= n; j++)
				if(i != j)
					slope[++tot] = atan2(PP[j].y - PP[i].y, PP[j].x - PP[i].x);
			sort(slope + 1, slope + tot + 1);
			double ans = 0.0;
			ans = max(ans, PI - (slope[tot] - slope[1]));
			for(int j = 2; j <= tot; j++) 
				ans = max(ans, (slope[j] - slope[j - 1]) - PI);
			printf("%.10lf\n", ans / (2 * PI));
		}
	}
	return 0;
}

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

long long n, d[3] = {}, sum;
string res;
vector<string> s;

bool solve();

int main() {
  cin >> n;
  for (int i = 0; i < 3; ++i) cin >> d[i];
  s.resize(n);
  for (int i = 0; i < n; ++i) cin >> s[i];
  if (solve()) {
    cout << "Yes" << endl;
    for (int i = 0; i < n; ++i) cout << res[i] << endl;
  } else
    cout << "No" << endl;
  return 0;
}

bool solve() {
  sum = d[0] + d[1] + d[2];
  if (sum == 0) return 0;
  for (int i = 0; i < n; ++i) {
    string now = s[i];
    long long x[2] = {now[0] - 'A', now[1] - 'A'}, p = 0;
    if (d[x[0]] > d[x[1]])
      p = 0;
    else if (d[x[0]] < d[x[1]])
      p = 1;
    else if (d[x[0]] == 0)
      return 0;
    else {
      if (i + 1 < n && s[i] != s[i + 1]) {
        long long y[2] = {s[i + 1][0] - 'A', s[i + 1][1] - 'A'};
        if (x[0] == y[0] || x[0] == y[1]) p = 1;
      }
    }
    --d[x[p]];
    ++d[x[1 - p]];
    res += x[1 - p] + 'A';
  }
  return 1;
}

Measured memory_bytes: 6696
import os
import sys

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 箱根


N = int(sys.stdin.readline())
C = [sys.stdin.readline().rstrip() for _ in range(N)]
C = [c for c in C if c != '-']
N = len(C)

# dp[i][j][k]:
# iまで見て、
# j個未割当の人が残ってて、
# j個未割当の場所が残ってる場合の数
dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i, c in enumerate(C):
    for j in range(N):
        if c == 'D':
            if j - 1 >= 0:
                # 前回i位だった人を今まで見た場所に割り当てる
                dp[i + 1][j - 1] += dp[i][j] * j * j
                dp[i + 1][j - 1] %= MOD
            # 割り当てない
            dp[i + 1][j] += dp[i][j] * j
            dp[i + 1][j] %= MOD
        if c == 'U':
            # 前回i位だった人を今まで見た場所に割り当てる
            dp[i + 1][j] += dp[i][j] * j
            dp[i + 1][j] %= MOD
            # 割り当てない
            dp[i + 1][j + 1] += dp[i][j]
            dp[i + 1][j + 1] %= MOD
print(dp[-1][0])



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

struct dat {
    int x, y, d;
};

const int INF = (int)1e9;

int H, W;
char grid[1000][1000];
int dist[1000][1000];
int ans = 0;

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

int main() {
    queue<dat> que;
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> grid[i][j];
            dist[i][j] = INF;
            if (grid[i][j] == '#') {
                que.push(dat{i,j,0});
                dist[i][j] = 0;
            }
        }
    }
    
    while (que.size()) {
        dat from = que.front(); que.pop();

        for (int i = 0; i < 4; i++) {
            int nx = from.x+dx[i], ny = from.y+dy[i];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W || dist[nx][ny] != INF) continue;

            dist[nx][ny] = from.d+1;
            que.push(dat{nx,ny,from.d+1});
            ans = max(ans,dist[nx][ny]);
        }
    }

    cout << ans << endl;    
}

Measured memory_bytes: 17168
#Palindromic Matrix
h,w = list(map(int, input().split()))
a = []
for i in range(h):
    a.append(input())
a = "".join(a)

import collections
c = collections.Counter(a).values()
d = 0
e = 0
for ci in c:
    d+=ci//4
    e+=ci//2

#print( (h//2)*(w//2), (h//2)*(w%2)+(w//2)*(h%2))
#print(d, e-2*d)

if (d-(h//2)*(w//2)>=0 and e-2*d+2*(d-(h//2)*(w//2))>=(h//2)*(w%2)+(w//2)*(h%2)):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3316
import java.util.Arrays;
import java.util.Scanner;

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

    int[] candies = new int[]{scanner.nextInt(), scanner.nextInt(), scanner.nextInt()};
    Arrays.sort(candies);
    if (candies[2] == candies[0] + candies[1]) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


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

using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mp make_pair
#define ld long double
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > small_heap;
typedef priority_queue<int> big_heap;
const int N = 5e5 + 10;
int T;
const ll mod = 1e9 + 7;


struct zhtools {
    ll fac[N] = {1ll};

    ll binpow(ll a, ll b) {
        ll res = 1ll;
        while (b > 0) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    void init() { for (ll i = 1; i < N; i++)fac[i] = fac[i - 1] * i % mod; }

    ll inv(ll a) { return binpow(a, mod - 2); }

    ll A(ll n, ll m) { return fac[n] * inv(fac[n - m]) % mod; }

    ll C(ll n, ll m) { return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod; }
} zh;

int main() {
    zh.init();
    int n, m;
    scanf("%d%d", &n, &m);
    ll sum = 0;
    ll flag = 1ll;
    for (int i = 0; i <= n; i++) {
        sum += flag * zh.C(1ll * n, 1ll * i) * zh.A(1ll * (m - i), 1ll * (n - i)) % mod;
        sum = (sum + mod) % mod;
        flag = -flag;
    }
    printf("%lld\n", zh.A(m, n) * sum % mod);
    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define endl "\n"     
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

int32_t main()
{
     int n,h,w,ans=0;
     cin>>n>>h>>w;
     
     for(int i=1;i<=n;i++)
     {
          for(int j=1;j<=n;j++)
          {
               if((i+h-1)<=n && (j+w-1)<=n)
                    ans++;
          }
     }
     cout<<ans;
     return 0;
}

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

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < N; i++){
        string T = S.substr(i, N - i);
        vector<int> A(N - i + 1, 0);
        int j = -1;
        A[0] = -1;
        for (int k = 0; k < N - i; k++){
            while(j >= 0 && T[k] != T[j]) j = A[j];
            j++;
            A[k + 1] = j;
        }
        for (int k = 1; k < N - i + 1; k++){
            if (k >= A[k] * 2){
                ans = max(ans, A[k]);
            }
            else{
                ans = max(ans, k / 2);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3676
import math

def is_prime(x):
    if x < 2:
        return False
    for i in range(2, int(math.sqrt(x))):
        if x % i == 0:
            return False
    return True

def main():
    X = int(input())
    while not is_prime(X):
        X += 1
    print(X)
main()

Measured memory_bytes: 2940
import java.util.*;

class Main {
	public static void main(String[] args){
		int[] array = new int[1 << 15];
		int[] prime = new int[1 << 15];
		
		int cnt = 0;
		
		for(int i = 2; i < array.length; i++){
			if(array[i] == 0){
				array[i] = 1;
				prime[cnt++] = i;
				for(int j = i * 2; j < array.length; j += i){
					array[j] = 1;
				}
			}
		}

		int n, ans;
		Scanner sc = new Scanner(System.in);
		while((n = sc.nextInt()) != 0){
			ans = 0;
			for(int i = 0; i < cnt; i++){
				for(int j = i; j < cnt; j++){
					if(prime[i] + prime[j] == n){
						ans++;
					}
				}
			}
			
			System.out.println(ans);
		
		}
	}
}

Measured memory_bytes: 19736
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 5e5+10;

string s;
int main(){
fast;
ll n;
cin>>n;
s="";

while(n>0) {
    int rem = n%26;
    if(rem==0) rem=26;
    s.push_back('a'+rem-1);
    n-=rem;
    n/=26;
}
reverse(s.begin(),s.end());
cout<<s<<endl;
return 0;
}

Measured memory_bytes: 3668
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int m[1010];

int main() {
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.rbegin(), t.rend());

  if (s < t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
string S,T;
main()
{
	cin>>S>>T;
	int ans=T.size();
	for(int i=0;i+T.size()<=S.size();i++)
	{
		int c=0;
		for(int j=0;j<T.size();j++)c+=S[i+j]!=T[j];
		if(ans>c)ans=c;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3552
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<int> l(n + 2), r(n + 2);
  l[0] = 0, r[n + 1] = 0;
  for (int i = 1; i < n; ++i) {
    l[i] = gcd(l[i - 1], a[i - 1]);
  }
  for (int i = n; i >= 2; --i) {
    r[i] = gcd(r[i + 1], a[i - 1]);
  }
  int ans = -1;
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, gcd(l[i - 1], r[i + 1]));
  }
  cout << ans << endl;
  return 0;
}

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


int main(void){
	char str[16];
	scanf("%s",str);
	if(strlen(str)>=4 && str[0]=='Y' && str[1]=='A' && str[2]=='K' && str[3]=='I'){
		puts("Yes");
	}else{
		puts("No");
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000000000000;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<long long> dp0(N, 0);
  vector<long long> dp1(N, 0);
  if (A[0] % 2 == 0){
    dp0[0] = A[0] / 2;
    if (A[0] == 0){
      dp1[0] = -INF;
    } else {
      dp1[0] = A[0] / 2 - 1;
    }
  } else {
    dp0[0] = A[0] / 2;
    dp1[0] = A[0] / 2;
  }
  for (int i = 1; i < N; i++){
    if (A[i] % 2 == 0){
      if (A[i] == 0){
        dp0[i] = dp0[i - 1];
        dp1[i] = -INF;
      } else {
        dp0[i] = max(dp0[i - 1] + A[i] / 2, dp1[i - 1] + 1 + (A[i] - 1) / 2);
        dp1[i] = max(dp0[i - 1] + (A[i] - 1) / 2, dp1[i - 1] + (A[i] - 2) / 2 + 1);
      }
    } else {
      dp0[i] = max(dp0[i - 1] + A[i] / 2, dp1[i - 1] + A[i] / 2 + 1);
      if (A[i] == 1){
        dp1[i] = dp0[i - 1] + A[i] / 2;
      } else {
        dp1[i] = max(dp0[i - 1] + A[i] / 2, dp1[i - 1] + (A[i] - 2) / 2 + 1);
      }
    }
  }
  cout << dp0[N - 1] << endl;
}

Measured memory_bytes: 5084
#include <iostream>
using namespace std;
#define LL long long

#include <algorithm>
#include <vector>
void _150() {
    LL n;
    cin >> n;

    // int p[8];
    // int q[8];
    int temp;
    vector<int> p, q;
    vector<int> perm_base;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        p.push_back(temp);
        perm_base.push_back(i + 1);
    }
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        q.push_back(temp);
    }

    LL a, b, index;
    a = -1;
    b = -1;
    index = 0;
    do {
        if (perm_base == p) {
            a = index;
        }

        if (perm_base == q) {
            b = index;
        }

        if (a != -1 && b != -1) {
            break;
        }

        index++;
    } while (next_permutation(perm_base.begin(), perm_base.end()));

    cout << abs(a - b) << endl;
}

#include <string>
void _151() {
    int n, m;
    cin >> n >> m;
    int p[100000] = {0};
    int correct[100000] = {0};
    int penalty_counts[100000] = {0};
    string temp;
    int correct_count = 0;
    for (int i = 0; i < m; ++i) {
        cin >> p[i] >> temp;
        if (temp == "AC") {
            if (correct[p[i] - 1] != 1) {
                correct_count++;
                correct[p[i] - 1] = 1;
            }
        } else {
            if (correct[p[i] - 1] != 1) {
                penalty_counts[p[i] - 1]++;
            }
        }
    }
    int penalty_count = 0;
    for (int i = 0; i < n; ++i) {
        if (correct[i] == 1) {
            penalty_count += penalty_counts[i];
        }
    }
    cout << correct_count << " " << penalty_count << endl;
}

#include <limits>
void _152_() { 
    int n;
    cin >> n;
    int temp;
    vector<int> p;
    int min_val = numeric_limits<int>::max();
    int count = 0;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        if (min_val >= temp) {
            min_val = temp;
            count++;
        }
    }
    cout << count << endl;
}

void _153() {
    int n, k;
    cin >> n >> k;

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

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

    sort(h.begin(), h.end());

    int num_monsters = n - k;
    LL count = 0;
    for (int i = 0; i < num_monsters; ++i) {
        count += h[i];
    }
    cout << count << endl;
}

#include <set>
void _154() {
    int n;
    cin >> n;
    int temp;
    set<int> b;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        b.insert(temp);
    }

    if (b.size() != n) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }

}

int main()
{
    _154();
    return 0;
}



Measured memory_bytes: 9600
def main():
    n, x, *a = map(int, open(0).read().split())
    a = [0] + a
    ans = 0
    tmp = 0
    for i, j in zip(a, a[1:]):
        i -= tmp
        if (i + j - x) > 0:
            c = (i + j - x)
            ans += c
            tmp = c
        else:
            tmp = 0

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14092
N = int(input())
Ga, Sa, Ba = map(int, input().split())
Gb, Sb, Bb = map(int, input().split())

dp = [0]
for i in range(1, N+1):
  tmp = dp[-1] + 1
  if Ga <= i:
    t2 = dp[-Ga] + Gb
    tmp = tmp if tmp > t2 else t2
  if Sa <= i:
    t2 = dp[-Sa] + Sb
    tmp = tmp if tmp > t2 else t2
  if Ba <= i:
    t2 = dp[-Ba] + Bb
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
N2 = dp[-1]

dp = [0]
for i in range(1, N2+1):
  tmp = dp[-1] + 1
  if Gb <= i:
    t2 = dp[-Gb] + Ga
    tmp = tmp if tmp > t2 else t2
  if Sb <= i:
    t2 = dp[-Sb] + Sa
    tmp = tmp if tmp > t2 else t2
  if Bb <= i:
    t2 = dp[-Bb] + Ba
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
print(dp[-1])

Measured memory_bytes: 433728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace mcmf {
struct edge {
  int to, capacity, cost, back;
  edge(int a, int b, int c, int d): to(a), capacity(b), cost(c), back(d) {
  }
};
vector<vector<edge> > graph;
void add(int u, int v, int capacity, int cost) {
  graph[u].emplace_back(v, capacity, cost, (int)graph[v].size());
  graph[v].emplace_back(u, 0, -cost, (int)graph[u].size() - 1);
}
int s, t;
void init(int ss, int tt) {
  s = ss;
  t = tt;
  graph.resize(t + 1);
}
ll solve() {
  ll result = 0;
  while (true) {
    vector<ll> dist(t + 1, LLONG_MAX);
    vector<bool> in_queue(t + 1);
    vector<int> from_vertex(t + 1), from_edge(t + 1);
    queue<int> que;
    que.push(s);
    dist[s] = 0;
    in_queue[s] = true;
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      in_queue[u] = false;
      for (int i = 0; i < graph[u].size(); i++) {
        edge e = graph[u][i];
        if (e.capacity && dist[e.to] > dist[u] + e.cost) {
          dist[e.to] = dist[u] + e.cost;
          from_vertex[e.to] = u;
          from_edge[e.to] = i;
          if (!in_queue[e.to]) {
            que.push(e.to);
            in_queue[e.to] = true;
          }
        }
      }
    }
    if (dist[t] == LLONG_MAX) {
      break;
    }
    int capacity = INT_MAX;
    for (int u = t; u != s; u = from_vertex[u]) {
      capacity = min(capacity, graph[from_vertex[u]][from_edge[u]].capacity);
    }
    result += dist[t] * capacity;
    for (int u = t; u != s; u = from_vertex[u]) {
      graph[from_vertex[u]][from_edge[u]].capacity -= capacity;
      graph[u][graph[from_vertex[u]][from_edge[u]].back].capacity += capacity;
    }
  }
  return result;
}
}
int main() {
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int n;
  cin >> n;
  mcmf::init(0, n * 2 + 5);
  for (int i = 0; i < n; i++) {
    int x, y, count;
    cin >> x >> y >> count;
    mcmf::add(0, i + 1, count, 0);
    mcmf::add(i + 1, n + 1, count, x + y);
    mcmf::add(i + 1, n + 2, count, y - x);
    mcmf::add(i + 1, n + 3, count, x - y);
    mcmf::add(i + 1, n + 4, count, -x - y);
  }
  for (int i = 0; i < n; i++) {
    int x, y, count;
    cin >> x >> y >> count;
    mcmf::add(n + 4, i + n + 5, count, x + y);
    mcmf::add(n + 3, i + n + 5, count, y - x);
    mcmf::add(n + 2, i + n + 5, count, x - y);
    mcmf::add(n + 1, i + n + 5, count, -x - y);
    mcmf::add(i + n + 5, n * 2 + 5, count, 0);
  }
  cout << -mcmf::solve() << endl;
  return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

vll dp(201010,-1);

// (a/b)%P の場合は，(a%P)*modinv(b)%P とする
ll modinv(ll a) {
    ll b = MOD, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}

#define MAX_NCK 201010
ll f[MAX_NCK], rf[MAX_NCK];

// modinvも呼ぶ！！

bool isinit = false;

void init() {
    f[0] = 1;
    rf[0] = modinv(1);
    for(int i = 1; i < MAX_NCK; i++) {
        f[i] = (f[i - 1] * i) % MOD;
        rf[i] = modinv(f[i]);
    }
}

ll nCk(int n, int k) {
    if(!isinit) {
        init();
        isinit = 1;
    }
    ll nl = f[n]; // n!
    ll nkl = rf[n - k]; // (n-k)!
    ll kl = rf[k]; // k!
    ll nkk = (nkl * kl) % MOD;

    return (nl * nkk) % MOD;
}

int main(void) {

    ll n,k;
    cin>>n>>k;
    ll ans=0;
    if(k>n-1)k=n-1;
    for(int i=0;i<=k;i++){
        int rest=n-i;
        ans+=nCk(n,i)*nCk(n-1,i);
        ans%=MOD;
    }
    fin(ans);
}

Measured memory_bytes: 4992
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    long long int N,M,s,sum;
    while(scanf("%lld%lld",&N,&M)!=EOF)
    {
        if(N<M)
        {
        s=M-N*2;
        sum=N+s/4;
        cout<<sum<<endl;
        }
        else
            cout<<M/2<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;

const lld mod = 1e9+7;
const lld INF = 1e9;
const lld MAXN = 1e5 * 2;

int main()
{
	lld n,m,a[MAXN] = {0},b[MAXN] = {0};

	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> a[i] >> b[i];
	}

	vector<lld> start;
	set<lld> goal;

	for(int i = 0; i < m; i++)
	{
		if (a[i] == 1)
		{
			start.push_back(b[i]);
		}
		if (b[i] == 1)
		{
			start.push_back(a[i]);
		}

		if (a[i] == n)
		{
			goal.insert(b[i]);
		}
		if (b[i] == n)
		{
			goal.insert(a[i]);
		}
	}

	int s = start.size();

	for(int i = 0; i < s; i++)
	{
		if (goal.count(start[i]))
		{
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}

	cout << "IMPOSSIBLE" << endl;

	return 0;
}

Measured memory_bytes: 8820
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std;
int a,b,ab,an,bn,ansa,ansb,ansc;
int main(){
cin>>a>>b>>ab>>an>>bn;
int bi=max(an,bn);
ansa=bi*2*ab;
ansb=an*a+bn*b;
if(bi==an)
ansc=bn*2*ab+(an-bn)*a;
else
ansc=an*2*ab+(bn-an)*b;
ansa=min(ansa,ansb);
ansa=min(ansa,ansc);
cout<<ansa;
system("pause");
return 0;
}

Measured memory_bytes: 504
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
#define inf 99999999
using namespace std;
const int MAX=1000000000+7;
int main(){
    #ifdef SIYU
    //freopen("in.txt","r",stdin);
    #endif // SIYU
    long long n,sum=1;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        sum=sum*i;
        sum=sum%MAX;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

const int MAX_SIZE = 52;

int LCS(const string& a, const string& b){
    int n = (int)a.size(), m = (int)b.size();
    vector<int> x(n), y(m);
    rep(i,n){
        x[i] = a[i]-'a';
        if(x[i] < 0){
            x[i] = a[i]-'A'+26;
        }
    }
    rep(i,m){
        y[i] = b[i]-'a';
        if(y[i] < 0){
            y[i] = b[i]-'A'+26;
        }
    }
    vector<vector<int> > vec(MAX_SIZE);
    for(int j = m-1; j >= 0; --j){
        vec[y[j]].push_back(j);
    }
    vector<int> xs(n, INF);
    rep(i,n){
        rep(j,(int)vec[x[i]].size()){
            *lower_bound(xs.begin(),xs.end(),vec[x[i]][j]) = vec[x[i]][j];
        }
    }
    return lower_bound(xs.begin(),xs.end(),INF) - xs.begin();
}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    rep(i,q){
        string a,b;
        cin >> a >> b;
        cout << LCS(a,b) << "\n";
    }
    return 0;
}



Measured memory_bytes: 3204