akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1e18
#define MIN -1e18
#define MOD 1000000007
//#define mod2 20071027
//#define MOD 998244353
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define base 139
//#define mod 1000074259
#define base2 31
#define memz(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define in1(a) scanf("%lld", &a)
#define in2(a, b) scanf("%lld%lld", &a, &b)
#define TC(c) printf("Case %lld: ", ++c)
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
const ll N=300010;
ll n;
int main()
{
   cin>>n;
   ll k = n/500;
   ll res=(k*1000);
   n-=(500*k);
   res+=((n/5)*5);
   cout<<res<<endl;
    return 0;
}

/*

*/


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

using namespace std;
int main(){
  	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	int A[n];
	int INF = 1e9+5;
	int dp[n];
	for (int i=0; i<n; i++){
		cin>>A[i];
		dp[i] = INF;
	}
	dp[0] = 0;
	for (int i=0; i<n; i++){
		if(i + 2 < n){
			int k = min(dp[i] + abs(A[i + 2] - A[i]), dp[i + 1] + abs(A[i + 2] - A[i + 1])) ;
			dp[i + 2] = min(dp[i + 2], k); 
			dp[i + 1] = min(dp[i + 1], dp[i] + abs(A[i + 1] - A[i]));
		}
		else if(i + 1 < n){
			dp[i + 1] = min(dp[i] + abs(A[i + 1] - A[i]), dp[i + 1]);
		}
	}
	cout<<dp[n - 1];
}

Measured memory_bytes: 4344
#include <iostream> 
using namespace std;
 
int main(){
	int N, A, B;
	string S;
	cin >> N >> A >> B >> S;
	int passinger = 0;
	int overseas_passinger = 0;
	for(int i = 0; i < N; i++){
		if(S[i] == 'a' && passinger < A + B){
			passinger++;
			cout << "Yes" << endl;
		}else if(S[i] == 'b' && passinger < A + B && overseas_passinger < B){
			passinger++;
			overseas_passinger++;
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}
}

Measured memory_bytes: 896
n = int(input())
d_list = list(map(int,input().split()))
p = 998244353
import collections
result = 0
check = True
for i in range(1,len(d_list)):
  if d_list[i] == 0:
    check = False
 
if d_list[0] != 0:
  print(result)
elif check == False:
  print(result)
else:
  result = 0
  c = collections.Counter(d_list)
  for i in range(1,max(d_list) + 1):
    if i == 1:
      result += 1
    elif  c[i] == 0:
        result = 0
    else:
      result = result * (c[i -1] ** c[i])

  print(result % p)    
  

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

using namespace std;

#define PI 3.14159265
#define int long long
#define pb push_back
#define mp make_pair
#define smax(x , y) x = max(x , y)
#define smin(x , y) x = min(x , y)

const int maxn = 1e5+10;

main(){
	int ans = 0;
	int n; cin >> n;
	for(int i = 1;i <= n;i++){
		int l , r; cin >> l >> r;
		ans += r - l + 1;
	}
	return cout << ans << endl , 0;
}  

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


int main()
{
    while (true)
    {
        int n;
        cin >> n;
        if (n == 0) {
            return 0;
        }
        int t[20][20];
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n + 1; ++j)
            {
                cin >> t[i][j];
            }
        }
        int dp[1 << 17];
        for (int i = 0; i < (1 << n); ++i)
        {
            dp[i] = 200000000;
        }
        dp[0] = 0;
        for (int i = 1; i < (1 << n); ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if ((i >> j) & 1) {
                    int c = t[j][0];
                    for (int k = 0; k < n; ++k)
                    {
                        if (j == k) continue;
                        if ((i >> k) & 1) {
                            c = min(c, t[j][k + 1]);
                        }
                    }
                    dp[i] = min(dp[i], dp[i ^ (1 << j)] + c);
                }
            }
        }
        cout << dp[(1 << n) - 1] << "\n";
    }
}

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

#define endl '\n'

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    double L, volume;
    cin >> L;
    double edge = L / 3;
    volume = edge * edge * edge;
    cout << fixed << setprecision(7) <<  volume << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.regex.Pattern;

public class Main {
    public void solve(BufferedReader stdin, PrintWriter stdout) throws NumberFormatException, IOException {
        Pattern space = Pattern.compile(" ");
        int[] first = space.splitAsStream(stdin.readLine()).mapToInt(Integer::parseInt).toArray();
        int n = first[0];
        long k = first[1];
        long[] a = new long[n];
        long[] b = new long[n];
        for (int i = 0; i < n; i++) {
            long[] line = space.splitAsStream(stdin.readLine()).mapToLong(Long::parseLong).toArray();
            a[i] = line[0];
            b[i] = line[1];
        }

        long ans = sum(a, b, n, k);
        for (long i = highest(k); i >= 0; i--) {
            if ((k & (1 << i)) != 0) {
                long t = (k ^ (1 << i)) | ((1 << i) - 1);
                ans = Math.max(ans, sum(a, b, n, t));
            }
        }
        stdout.println(ans);
    }

    public long sum(long[] a, long[] b, long n, long t) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            if ((t | a[i]) == t) {
                sum += b[i];
            }
        }
        return sum;
    }

    public long highest(long x) {
        long c = 0;
        while (x > 0) {
            c++;
            x /= 2;
        }
        return c;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter stdout = new PrintWriter(System.out, false);
        new Main().solve(stdin, stdout);
        stdout.flush();
    }
}


Measured memory_bytes: 67696
//package codeforces;

import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.TreeSet;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
import java.util.Set;

public class Main {
	static Scanner scn = new Scanner(System.in);
	static int mod = 1000000007;
	//static int count = 0;

	public static void main(String[] args) {
		int n=scn.nextInt();
		int k=scn.nextInt(),count=0;
		long sum=0;
		int arr[]=new int[n];
		for(int i=0;i<n;i++)
		{
			arr[i]=scn.nextInt();
			//sum+=arr[i];
		}
		Arrays.parallelSort(arr);
		for(int i=0;i<n-k;i++)
		{
			sum+=arr[i];
		}
		System.out.println(sum);
		
	}
}


Measured memory_bytes: 67156
#include <iostream>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    cout<<std::fixed<<setprecision(10);
    long double pi = 3.141592653589793;
    long double a, b, x;
    cin >> a >> b >> x;

    long double v1 = a * b;
    long double v2 = x / a;
    
    long double ans = 0;
    if(v2 < v1 / 2) {
        long double tany = 2 * v2 / (b * b);
        ans = 90 - atan(tany) * (180 / pi);
    } else {
        long double tany = 2 * (v1 - v2) / (a * a);
        ans = atan(tany) * (180 / pi);
    }

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


Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 30;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

int sum[5010][5010];
int main() {
    int N, M; scanf("%d%d", &N, &M);
    vector<int> x(N), y(N);
    vector<int> cmp_x, cmp_y;
    for(int i=0; i<N; i++) {
        scanf("%d%d", &x[i], &y[i]);
        cmp_x.emplace_back(x[i]);
        cmp_y.emplace_back(y[i]);
    }

    cmp_x.emplace_back(-INF);
    cmp_x.emplace_back(+INF);
    sort(cmp_x.begin(), cmp_x.end());
    cmp_x.erase(unique(cmp_x.begin(), cmp_x.end()), cmp_x.end());
    cmp_y.emplace_back(-INF);
    cmp_y.emplace_back(+INF);
    sort(cmp_y.begin(), cmp_y.end());
    cmp_y.erase(unique(cmp_y.begin(), cmp_y.end()), cmp_y.end());

    for(int i=0; i<N; i++) {
        int xk = lower_bound(cmp_x.begin(), cmp_x.end(), x[i]) - cmp_x.begin();
        int yk = lower_bound(cmp_y.begin(), cmp_y.end(), y[i]) - cmp_y.begin();
        // fprintf(stderr, "xk = %d, yk = %d\n", xk+1, yk+1);
        sum[xk+1][yk+1]++;
    }
    for(int i=1; i<=N+5; i++) {
        for(int j=1; j<=N+5; j++) {
            // fprintf(stderr, "%d ", sum[i][j]);
            // if(j == N+5) fprintf(stderr, "\n");
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    }
    
    for(int i=0; i<M; i++) {
        int lx, ly, rx, ry; scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
        lx = lower_bound(cmp_x.begin(), cmp_x.end(), lx) - cmp_x.begin();
        ly = lower_bound(cmp_y.begin(), cmp_y.end(), ly) - cmp_y.begin();
        rx = upper_bound(cmp_x.begin(), cmp_x.end(), rx) - cmp_x.begin();
        ry = upper_bound(cmp_y.begin(), cmp_y.end(), ry) - cmp_y.begin();
        // fprintf(stderr, "lx = %d, ly = %d, rx = %d, ry = %d\n", lx, ly, rx, ry);
        int s = sum[rx][ry] - sum[lx][ry] - sum[rx][ly] + sum[lx][ly];
        printf("%d\n", s);
    }
    return 0;
}



Measured memory_bytes: 101340
#include <bits/stdc++.h>
using namespace std;
int main(){

  int n,q;
  cin>>n;

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

  cin>>q;

  for(int i=0;i<q;i++){

    int c,b,e;
    cin>>c>>b>>e;

    if(c) cout<<*max_element(a.begin()+b,a.begin()+e)<<endl;
    else cout<<*min_element(a.begin()+b,a.begin()+e)<<endl;

  }

  return 0;

}



Measured memory_bytes: 3096
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

int main() {
    int N; cin >> N;
    vector<vector<int>>G(N);
    rep(i, N - 1) {
        int a, b; cin >> a >> b;
        G[--a].pb(--b); G[b].pb(a);
    }
    int c[N];
    rep(i, N) cin >> c[i];
    sort(c, c + N, greater<int>());
    queue<int> Q;
    Q.push(0);
    int i = 0;
    vector<int> score(N, -1);
    while(!Q.empty()) {
        int q = Q.front(); Q.pop();
        score[q] = c[i], ++i;
        for(int next : G[q]) {
            if(score[next] == -1) Q.push(next), score[next] = 0;
        }
    }
    int sum = 0;
    rep(i, N - 1) {
        sum += c[i + 1];
    }
    cout << sum << endl;
    rep(i, N) {
        cout << score[i] << ' ';
    }
    cout << endl;
}


Measured memory_bytes: 1024
from sys import stdin
N = int(input())
L =[stdin.readline().split() for _ in range(N)]
for n in range(N):
  L[n][1] = int(L[n][1])
for n in range(N):
  L[n].append(n)
L = sorted(L, reverse=True, key=lambda x: x[1])
L = sorted(L, reverse=False, key=lambda x: x[0]) #L.sort()だと他の列もsortされてしまう
for n in range(N):
  print(L[n][2]+1)


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

ll powmod(ll a, ll b){
    if(b==0) return 1;
    if(b%2==1) return (a*powmod(a,b-1)) % p;
    else{
        ll x = powmod(a,b/2);
        return (x*x) % p;
    }
}

ll combinemod(ll a, ll b){
    ll x=1,y=1;
    for(int i=1;i<=b;i++){
        y = (y*i)%p;
    }
    for(int i=a-b+1;i<=a;i++){
        x = (x*i)%p;
    }

    return (x * powmod(y,p-2)) % p;
}

int main(){
    ll n,k;
    cin >> n >> k;
    for(int i=1;i<=k;i++){
        ll res = (combinemod(n-k+1,i) * combinemod(k-1,i-1)) % p;
        cout << res << endl;
    }
    return 0;
}

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

int main(){
    string s, t=""; cin >> s;
    int i = s.length()-1;
    while(i>=0){
        if(s[i]=='m'){
            t = "dream" + t; i -= 5;
        }
        else if(s[i]=='e'){
            t = "erase" + t; i -= 5;
        }
        else{
            if(i<1){
                cout << "NO" << endl; return 0;
            }
            if(s[i-2]=='m'){
                t = "dreamer" + t; i -= 7;
            }
            else{
                t = "eraser" + t; i -= 6;
            }
        }
    }
    cout << ((s==t)? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 512
#include <vector>
#include <algorithm>
#include <limits.h>
#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <cstring>
#include <string.h>
#include <stdio.h>
#include <iomanip>
#include <map>
#include <unordered_map>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     int n; cin>>n; int h[n];
     for(int i=0;i<n;i++) cin>>h[i];

     int f[n];
     for(int i=0;i<n;i++) f[i]=0;

     f[0]=0;
     for(int i=1;i<n;i++)
     {
         int a=INT_MAX; int b=INT_MAX;
         if(i-1>=0)
             a=f[i-1]+abs(h[i]-h[i-1]);
         if(i-2>=0)
             b=f[i-2]+abs(h[i]-h[i-2]);
         f[i]=min(a,b);
     }
     cout<<f[n-1]<<"\n";

    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
  int n;
  for(cin>>n;n--;)
    {
      string s;
      cin>>s;
      string ans="NA";

	if(s.substr(0,2)==">'" &&s[s.size()-1]=='~')
	  {
	    string tmp=s.substr(2,s.size()-3);
	    //	  cout<<tmp<<endl;
	    if(tmp.size()%2!=0
	       && tmp.size()>1
	       && tmp[tmp.size()/2]=='#'
	       && tmp.substr(0,tmp.size()/2)==tmp.substr(tmp.size()/2+1,tmp.size()/2)
	       && tmp.substr(0,tmp.size()/2)==*(new string(tmp.size()/2,'=')))
		ans="A";
	  }
	else if(s.substr(0,2)==">^" && s.substr(s.size()-2,2)=="~~")
	  {
	    string tmp=s.substr(2,s.size()-4);
	    //	      cout<<tmp<<endl;
	    bool flag=false;
	    while(tmp.size()>0)
	      {
		if(tmp.substr(0,2)=="Q=")
		  {
		    tmp=tmp.substr(2,tmp.size()-2);
		    flag=true;
		  }
		else
		  break;
	      }
	    if(tmp.size()==0&&flag)
	      ans="B";	    
	    }
	  cout<<ans<<endl;
    }
}

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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
//constexpr int INF = 1001001001;
constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;




inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}

inline ll mul(ll a, ll b, ll m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    ll res = mul(mod(a + a, m), b >> 1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}

ll pow(ll a, ll n, ll m) {
    if (n == 0) return 1 % m;
    ll t = pow(a, n / 2, m);
    t = mul(t, t, m);
    if (n & 1) t = mul(t, a, m);
    return t;
}

vector<pair<ll, ll> > prime_factor(ll n) {
    vector<pair<ll, ll> > res;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                ++exp;
                n /= i;
            }
            res.push_back(make_pair(i, exp));
        }
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

number GCD(number a, number b) { return b != 0 ? GCD(b, a % b) : a;}
number LCM(number a, number b) { return a * (b / GCD(a, b)); }


const ll L = 50;
ll solve(ll A, ll M) {
    if (A == 0) return M;
    if (A == 1) return 1;
    if (M == 1) return L;
    ll phiM = M;
    vector<pair<ll, ll> > divM = prime_factor(M);
    for (int i = 0; i < divM.size(); ++i) {
        ll p = divM[i].first;
        phiM *= p - 1;
        phiM /= p;
    }
    ll y = solve(A, phiM);
    ll lcm = LCM(phiM, M);
    ll res = pow(A, y, lcm);
    while (res < L) res += lcm;
    return res;
}

int main() {
    int Q; cin >> Q;

    rep(i, Q) {
        ll a, m; cin >> a >> m;
        ll res = solve(a, m);
        cout << res << endl;
    }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define quickIO()	{cin.tie(0);	cout.sync_with_stdio(false);}
#define reach(i,a)	for(auto i:a)
#define rep(i,n)	for(int i=0;i<(int)n;i++)
#define REP(i,n)	for(int i=0;i<=(int)n;i++)
#define srep(i,a,n)	for(int i=a;i<(int)n;i++)
#define SREP(i,a,n)	for(int i=a;i<=(int)n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
int bitcnt(ll x) {
	x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555);
	x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333);
	x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F);
	x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF);
	x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF);
	x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF);
	return x;
}
int bitcnt(int x) {
	x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
	x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
	x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
	x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
	x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
	return x;
}
ll gcd(ll a, ll b) {
	return a%b == 0 ? b : gcd(b, a%b);
}
#define debug(x)	cout<<"case #" << x << ": " << endl
#define DEBUG 0
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 1e-15;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };

int main() {
	ll n, m;	cin >> n >> m;
	if (n == 1)	cout << (m == 1 ? 1 : m - 2) << endl;
	else if (m == 1)	cout << n - 2 << endl;
	else	cout << (n-2)*(m-2) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
main()
{
    int n;cin >> n;
    double ret=0;
    rep(i,n)
    {
        double a;cin>>a;
        ret+=1/a;
    }
    printf("%lf\n",1/ret);
    return 0;
}

Measured memory_bytes: 256
n = int(input())
dp = [[1]*3]
dp.append(list(map(int,input().split())))
for i in range(n-1):
    n1,n2,n3 = map(int,input().split())
    ls = [n1,n2,n3]
    ap = [None]*3
    for j in range(3):
        num = 0
        c = 0
        for k in range(3):
            if j == k:continue
            if c == 0:
                num = dp[i+1][k] + ls[j]
                c += 1
            elif c == 1:ap[j] = max(num,dp[i+1][k] + ls[j])
    dp.append(ap)
print(max(dp[-1]))

Measured memory_bytes: 22776
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<int,int>
#define endl "\n"
#define MAXN 100005
#define mod 1000000007
using namespace std;

void solve()
{
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
    ll n,x,t;
    cin>>n>>x>>t;
    if(n%x)
    {
        cout<<(n/x + 1)*t<<'\n';
    }
    else
    {
        cout<<(n/x)*t<<'\n';
    }
}

Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstdint>
#define rep(ident, start, end) for(int ident=start;ident<end;ident++)

using namespace std;

int main(void){
	int H, W;
	cin >> H >> W;
	string l;
	vector<string> v;
	rep(i, 0, H){
		cin >> l;
		v.push_back(l);
	}
	bool process = true;
	while (process){
		process = false;
		rep (i, 0, H){
			if (v[i].find("#") == string::npos){
				v.erase(v.begin()+i);
				process = true;
				H--;
				break;
			}
		}
		if(process == false)
		rep(i, 0, W){
			rep(j, 0, H){
				if (v[j][i] == '#')break;
				if (j == H - 1){
					rep(k, 0, H)v[k].erase(v[k].begin() + i);
					W--;
					process = true;
					break;
				}
			}
			if (process == true)break;
		}
	}

	rep(i, 0, H)cout << v[i] <<endl;
	return 0;
}

Measured memory_bytes: 256
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <limits>
#include <map>
#include <numeric>

using namespace std;
static int imin = std::numeric_limits<int>::min();
static int imax = std::numeric_limits<int>::max();
#define ll long long
#define rep(i, n) for(int i = 0; i<n; ++i)
#define rep1(i, n) for(int i = 1; i<n; ++i)
#define debug(x) cout << #x << ":" << x << "\n";
template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec){
  std::size_t n = vec.size();
  if(n == 0){
    return os;
  }
  for(int i = 0; i<n - 1; ++i){
    os << vec[i] << " ";
  }
  os << vec[n - 1];
  os << std::endl;
  return os;
}

template<class T>
std::istream& operator >> (std::istream& is, std::vector<T>& vec){
  T tmp;
  is >> tmp;
  vec.push_back(tmp);
  return is;
}
template <class T>
auto mkVec(unsigned int x){
  return std::vector<int>(x);
}

template <class T>
auto mkVec2(unsigned int x, unsigned int y){
  return std::vector<std::vector<T>>(x, std::vector<T>(y));
}

template <class T>
auto mkVec3(unsigned int x, unsigned int y, unsigned int z){
  return std::vector<std::vector<std::vector<T>>>(x, std::vector<std::vector<T>>(y, std::vector<T>(z)));
}

// 113C
// #ifndef BOOST_TEST_MAIN
// int main(int const argc, char const** argv){
//   int N, M;
//   cin >> N >> M;
//   vector<ll> P;
//   vector<ll> Y;
//   auto X = mkVec2<ll>(N + 1, 0);
//   rep(i, M){
//     ll p, y;
//     cin >> p >> y;
//     P.push_back(p);
//     Y.push_back(y);
//     X[p].push_back(y);
//   }
//   rep(i, N + 1){
//     sort(X[i].begin(), X[i].end());
//   }
//   rep(i, M) {
//     ll y;
//     rep(j, N + 1){
//       auto x = find(X[j].begin(), X[j].end(), Y[i]);
//       if(x != X[j].end()){
//         y = x - X[j].begin();
//         break;
//       }
//     }
//     printf("%06lld%06lld\n", P[i], y + 1);
//   }
// }
// #endif

#ifndef BOOST_TEST_MAIN
int main(int const argc, char const** argv){
  int N, K;
  cin >> N >> K;
  int count = 0;
  N -= K;
  count++;
  while(N>0){
    N -= K - 1;
    count++;
  }
  cout << count;
}
#endif


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

using namespace std;

int64_t solve(int n, const vector<int>& A, const vector<int>& B){
    vector<int64_t> DP(n + 1);
    DP[0] = n;
    int64_t res = n;

    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < 3; j++) {
            if (i - A[j] >= 0)
                DP[i] = max(DP[i], DP[i - A[j]] + B[j] - A[j]);
        }
        res = max(res, DP[i]);
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    vector<int> A(3), B(3);

    for (auto &a: A) cin >> a;
    for (auto &b: B) cin >> b;

    cout << solve(solve(n, A, B), B, A) << endl;
}


Measured memory_bytes: 195584
#include<bits/stdc++.h>
const long long INF = INT_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define ll long long int
using namespace std;
ll ans = 0, sum = 0, n, k, cnt = 0, w, h;
string s;
vector<ll> v;
vector < pair<ll, ll > > vp;
vector<vector<ll> > vv(50, vector<ll>(50, INF));
vector<string> vs;
vector<char> vc;
set<ll> st;
map<char, ll> mp;

/*--------------------template--------------------*/

ll power(ll x, ll n, ll M) {
	ll tmp = 1;
	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

int main() {
	cin >> n >> k;
	cout << power(n, k, MOD) << endl;
}

Measured memory_bytes: 3240
#include <stdio.h>

int main(void)
{
    int i, k, a, b, c;

    scanf("%d %d %d", &a, &b, &c);

    k = 0;
    for (i = a; i <= b; i++)
    {
        if (c % i == 0)
            k++;
    }
    printf("%d", k);

    putchar('\n');

    return 0;
}


Measured memory_bytes: 2712
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e5+51;
ll x,y,z;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
int main()
{
	x=read(),y=read(),z=read();
	if(x==y&&x!=z)
	{
		puts("Yes");
		return 0;
	}
	if(z==y&&x!=z)
	{
		puts("Yes");
		return 0;
	}
	if(x==z&&y!=z)
	{
		puts("Yes");
		return 0;
	}
	puts("No");
}

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

public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;
        Solver s = new Solver();
        for (int i = 1; i <= t; i++) {
            s.solve(i, in, out);
        }
        out.close();
    }

}

class Solver {
    void solve(int test, InputReader in, PrintWriter out) throws IOException {
        int[] primes = new int[(int) (1e5 + 1)];
        for (int i = 2; i < primes.length; i++) {
            if (primes[i] == 0) {
                for (int j = i; j < primes.length; j += i) primes[j] = i;
            }
        }
        int[] ans = new int[primes.length];

        int c = 0;
        for (int i = 0; i < primes.length; i++) {
            if (primes[i] == i) {
                if (primes[(i + 1) / 2] == (i + 1) / 2) {
                    c++;
                }
            }
            ans[i] = c;
        }
        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int l = in.nextInt() - 1;
            int r = in.nextInt();
            out.println(ans[r] - ans[l]);
        }
    }
}

class InputReader {
    BufferedReader br;
    StringTokenizer st;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = null;
    }

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

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

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

    public String nextLine() throws IOException {
        return br.readLine();
    }

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

Measured memory_bytes: 42380
using System;
using static System.Console;
using System.Collections.Generic;
using System.Collections;

namespace Grobal
{
	class Program
	{
		static void Main(string[] args)
		{
			int n = int.Parse(ReadLine()),count = 0;
			string s = ReadLine();
			for(int i = 0;i < n - 2;i++)
			{
				if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
				{
					count++;
				}
			}
			WriteLine(count);
		}
	}
}

Measured memory_bytes: 11092
sieve :: [Int] -> Int -> Bool
sieve [] n = True
sieve (p:ps) n
    | n `mod` p == 0 = False
    | p*p > n = True
    | otherwise = sieve ps n

primes :: [Int]
primes = 2 : 3 : filter (sieve primes) [5,7..]

expo :: Int -> Int -> (Int, Int)
expo p = go 0 1 where
    go k s n
        | r == 0 = go (k+1) (s * p) q
        | otherwise = (k,n)
        where (q,r) = n `divMod` p

factorize :: Int -> [(Int, Int)]
factorize = go primes where
    go (p:ps) n
        | n == 1 = []
        | p*p > n = [(n, 1)] -- n must be prime
        | k > 0 = (p,k) : go ps s
        | otherwise = go ps n
        where (k,s) = expo p n

goo :: Int -> Int
goo = go 0 1 where
    go r k n | k > n = r
             | otherwise = go (r+1) (k+1) (n-k)

main = do
    n <- readLn :: IO Int
    print (sum . map (goo . snd) . factorize $ n)


Measured memory_bytes: 11876
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int N, W;
long weight[100010], value[110];
long dp[110][100010];

int main () {

    scanf("%d %d", &N, &W);
    for (int i = 0; i < N; i++) {
        scanf("%ld %ld", &weight[i], &value[i]);
    }

    for (int w = 0; w <= W; w++) {
        dp[0][w] = 0;
    }
    for (int i = 0; i < N; i++) {
        for (int w = 0; w <= W; w++) {
            if (weight[i] <= w) {
                dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
            }
            else {
                dp[i+1][w] = dp[i][w];
            }
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}

Measured memory_bytes: 82176
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    vector<long int> L(87);
    L[0] = 2;
    L[1] = 1;
    for(int i = 2; i <= N; i++){
        L[i] = L[i - 1] + L[i - 2];
    }
    cout << L[N] << endl;
}

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

#define REP(i, n) for(decltype(n) i = 0; i < n; i++)

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

ll dp[101][4][4][4];

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

    int N;
    cin >> N;

    auto check = [](const int& a,
                    const int& b,
                    const int& c) {
                     return a == 1 && b == 2 && c == 3;
                 };

    dp[0][0][0][0] = 1;
    REP(i, N) {
        REP(a, 4) {
            REP(b, 4) {
                REP(c, 4) {
                    REP(d, 4) {
                        if(check(b, c, d) ||
                           check(c, b, d) ||
                           check(b, d, c) ||
                           check(a, c, d) ||
                           check(a, b, d)) continue;
                        dp[i+1][b][c][d] += dp[i][a][b][c];
                        dp[i+1][b][c][d] %= MOD;
                    }
                }
            }
        }
    }

    ll ans = 0;
    REP(a, 4) {
        REP(b, 4) {
            REP(c, 4) {
                ans += dp[N][a][b][c];
                ans %= MOD;
            }
        }
    }

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

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

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);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int h = in.nextInt();
			int w = in.nextInt();
			StringBuffer pic = new StringBuffer();
			pic.append(new String(new char[w+2]).replace("\0", "#")).append("\n");
			for (int i = 0; i < h; i++) {
				pic.append("#").append(in.nextString()).append("#\n");
			}
			pic.append(new String(new char[w+2]).replace("\0", "#")).append("\n");

			out.print(pic.toString());
		}

	}

	static class ArrayUtils {
		public static Map<Integer, Integer> getCountMap(int[] array) {
			Map<Integer, Integer> map = new TreeMap<>();
			for (int x : array)
				map.merge(x, 1, Integer::sum);
			return map;
		}

	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

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

		public long nextLong() {
			return Long.parseLong(nextString());
		}

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

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,x,y;
  cin>>n>>x>>y;
  int b[n];
  for(int i=1;i<n;i++)
    b[i]=0;
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      b[min(min(abs(j-i),abs(x-i)+1+abs(y-j)),abs(y-i)+1+abs(j-x))]++;
    }
  }
  for(int i=1;i<n;i++){
    cout<<b[i]<<endl;
  }
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var A, B, C int
	var K int

	fmt.Scan(&A, &B, &C)
	fmt.Scan(&K)

	for i := 0; i < K; i++ {
		if B <= A {
			B *= 2
		} else if C <= B {
			C *= 2
		}
		if A < B && B < C {
			fmt.Println("Yes")
			return
		}
	}

	fmt.Println("No")
}


Measured memory_bytes: 1768
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

typedef long long int int64;
typedef vector<int64> VI64;
typedef vector<pair<int64,int64>> VII64;
typedef vector<string> VS;
typedef vector<vector<int64>> VVI;

int main()
{
    IOS;
    int64 T=1;
    //cin>>T;
    while(T--)
    {
        int64 n,i,ans=0;
        cin>>n;
        int64 a[n],b[n],c[n];
        map<int64,int64> mp;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            mp[a[i]-1]=i;
        }
        for(i=0;i<n;i++)
        {

            cin>>b[i];
            ans+=b[i];
        }
        //cout<<ans<<endl;
        for(i=0;i<n-1;i++)
        {
            cin>>c[i];
            if(mp[i]+1==mp[i+1])
                ans+=c[i];
            
        }
        cout<<ans;
    }

    return 0;
}

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

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

  vector<double> x(N);
  vector<string> u(N);

  for (int i = 0; i < N; i++) {
    cin >> x.at(i) >> u.at(i);
  }

  double Y = 0.0;
  for (int i = 0; i < N; i++) {
    if (u.at(i) == "BTC") Y += x.at(i) * 380000.0;
    else Y+= x.at(i);
  }
  
  cout << fixed;
  cout << Y << endl;
}


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

typedef long long ll;

int main(){

  int n;
  cin >> n;
  map<string,int> mp;
  rep(i,n){
    string s;
    cin >> s;
    sort(s.begin(),s.end());
    mp[s]++;
  }
  ll ans = 0;
  for(auto& p:mp) {
    int s = p.second;
    ans += (ll) s*(s-1)/2;
  }
  cout <<ans << endl;
  return 0;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REP2(i,x,n) for(ll i=x; i<(n); i++)
const long long INF = numeric_limits<long long>::max();
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main()
{
    ll H, W;
    cin >> H >> W;
    vector<string> maps(H);
    for ( ll i = 0; i < H; ++ i ){
        cin >> maps[i];
    }

    while(1){
        bool isRemove = false;
        for ( ll i = 0; i < maps.size(); ++ i ){
            if ( maps[i].find('#') == string::npos ){
               maps.erase(maps.begin()+i);
               i--;
               isRemove = true;
            }
        }

        if ( maps.size() == 0 ) break;
        for ( ll i = 0; i < maps[0].size(); ++ i ){
            bool findS = false;
            for ( ll j = 0; j < maps.size(); ++ j ){
                findS |= maps[j][i] == '#';
            }
            if ( !findS ){
                for ( ll j = 0; j < maps.size(); ++ j ){
                    maps[j].erase(maps[j].begin() + i );
                }
                isRemove = true;
            }
        }
        if ( !isRemove )    break;
    }

    for ( const auto& m : maps ){
        cout << m << endl;
    }


    return 0;
}

Measured memory_bytes: 3616
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <set>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;
ll max(ll a, ll b) {
	if (a < b)
		return b;
	else
		return a;

}
ll min(ll a, ll b) {
	if (a < b)
		return a;
	else
		return b;

}


vector<ll> L;
ll D[1000];
int main() {
	ll N, X;


	cin >> N >> X;
	L.resize(N);
	rep(i, N) {
		cin >> L[i];
		D[i + 1] = L[i] + D[i];
 	}

	ll ans = 0;
	rep(i, N+1) {
		if (D[i] <= X) {
			ans += 1;
		}

	}


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

Measured memory_bytes: 256
t = input()
if(len(t) == 1):
    if (t[0] == '?'): t = "D"
if(t[0] == '?'):
    if  (t[1] == 'D'): t = "".join(['P' , t[1:]])
    elif(t[1] == '?'): t = "".join(['PD', t[2:]])
    else:              t = "".join(['D' , t[1:]])
if(t[-1] == '?'):
    t = "".join([t[:-1], 'D'])
for i in range(len(t)-1):
    if(t[i] == '?'):
        if(t[i-1] == 'P'):    t = "".join([t[:i], 'D' , t[i+1:]])
        elif(t[i+1] == 'D'):  t = "".join([t[:i], 'P' , t[i+1:]])
        elif(t[i+1] == 'P'):  t = "".join([t[:i], 'D' , t[i+1:]])
        elif(t[i+1] == '?'):  t = "".join([t[:i], 'PD', t[i+2:]])
print(t)

Measured memory_bytes: 9800
import math
import numpy as np

N, K = [int(x) for x in input().split(" ")]

prob = 0
for n in range(1, N + 1):
    if n >= K:
        prob += 1
        continue
    else:
        m = math.ceil(math.log2(K / n))
        prob += 1 / (2 ** m)

prob /= N
print(prob)

Measured memory_bytes: 18596
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<set>

using ll = long long;

using namespace std;

long long x = 1000000007;

ll n_pow(ll a, ll n) {
	if (n == 0)return 1;
	ll t = n_pow(a, n / 2);
	t *= t;
	t %= x;
	if (n % 2 == 1)t *= a;
	return t % x;
}

int main() {
	ll n, k;
	cin >> n >> k;
	ll ans = 0;
	if (k == 1) {
		ans = (n*(n - 1)) % x;
	}
	else {
		vector<ll>f(n+1);
		vector<ll>f_inv(n+1);
		ll num = 1;
		f[0] = num;
		f_inv[0] = n_pow(num, x - 2);
		for (ll i = 1; i <= n; i++) {
			num *= i;
			num %= x;
			f[i] = num;
			f_inv[i] = n_pow(num, x - 2);
		}
		for (ll i = 0; i <= min(n-1, k); i++) {
			ll p = (f[n] * f_inv[n - i]) % x;
			p *= f_inv[i];
			p %= x;
			ll q = (f[n - 1] * f_inv[n - i - 1]) % x;
			q *= f_inv[i];
			q %= x;
			ans += (p*q) % x;
			ans %= x;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()

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

int main()
{
	int n, t; cin >> n >> t;
	vector<int> a(n), b(n);
	rep(i, 0, n - 1)cin >> a[i] >> b[i];

	vector<vector<int>> dpL(n + 1, vector<int>(t, 0));
	vector<vector<int>> dpR(n + 1, vector<int>(t, 0));
	rep(i, 0, n - 1)rep(j, 0, t - 1)
	{
		chmax(dpL[i + 1][j], dpL[i][j]);
		if (j + a[i] < t)chmax(dpL[i + 1][j + a[i]], dpL[i][j] + b[i]);
	}
	for (int i = n - 1; i >= 0; --i)rep(j, 0, t - 1)
	{
		chmax(dpR[i][j], dpR[i + 1][j]);
		if (j + a[i] < t)chmax(dpR[i][j + a[i]], dpR[i + 1][j] + b[i]);
	}
	/*rep(i, 0, n)rep(j, 0, t - 2)
	{
		chmax(dpL[i][j + 1], dpL[i][j]);
		chmax(dpR[i][j + 1], dpR[i][j]);
	}*/
	int ans = 0;
	rep(i, 0, n - 1)rep(j, 0, t - 1)
	{
		chmax(ans, dpL[i][j] + dpR[i + 1][t - 1 - j] + b[i]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 70912
#include <stdio.h>
#include <iostream>
#include <string>

using namespace std;
void checkPiece(int x, int y);//, char map[][]);
void check(int x, int y);
char map[22][22];
int flag = 1;

int main(){
	int W, H;
	while(1){
		int count = 0;
		int x, y;
		cin>>W>>H;
		if(W == 0 && H == 0) { return 0; }
		//char map[H+2][W+2];
		
		for (int i = 0; i < H + 2; ++i)
		{
			for (int j = 0; j < W + 2; ++j)
			{
				map[j][i] = '#';
			}
		}

		for (int i = 1; i < H + 1; ++i)
		{
			for (int j = 1; j < W + 1; ++j)
			{
				cin>>map[j][i];
				if(map[j][i]=='@'){x = j; y = i;}
			}
		}

		//cout<<map[2][1]<<y<<endl;
		check(x, y);
	while(flag){
		flag = 0;
		for (int i = 1; i < H + 1; ++i)
		{
			for (int j = 1; j < W + 1; ++j)
			{
				//cout<<i<<endl;
				check(j, i);
			}
		}
		//flag = 0;
		//cout<<flag<<endl;
	}
/*
	for (int i = 0; i < H + 2; ++i)
		{
			for (int j = 0; j < W + 2; ++j)
			{
				cout<<map[j][i];
			}
			cout<<endl;
		}
*/
		for (int i = 0; i < H + 2; ++i)
		{
			for (int j = 0; j < W + 2; ++j)
			{
				if(map[j][i] == '@'){ count++; }
			}
		}
		cout<<count<<endl;

	}
	return 0;

}

void checkPiece(int x, int y){//, char map[][]){
	if(map[x][y] == '.') { map[x][y] = '@'; }
	if(map[x][y] == '@'){
		if(map[x+1][y] != '#') return checkPiece(x+1, y);
		else if(map[x-1][y] != '#') return checkPiece(x-1, y);
		else if(map[x][y+1] != '#') return checkPiece(x, y+1);
		else if(map[x][y-1] != '#') return checkPiece(x, y-1);
	}
	return;
}

void check(int x, int y){
	if(map[x][y] == '@'){
		if(map[x+1][y] != '#' && map[x+1][y] == '.') { map[x+1][y] = '@'; flag = 1;}
		if(map[x-1][y] != '#' && map[x-1][y] == '.') { map[x-1][y] = '@'; flag = 1;}
		if(map[x][y+1] != '#' && map[x][y+1] == '.') { map[x][y+1] = '@'; flag = 1;}
		if(map[x][y-1] != '#' && map[x][y-1] == '.') { map[x][y-1] = '@'; flag = 1;}
	}
	return;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
#define MOD 1000000007
#define INF 1e9
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
using namespace std;
const double PI = acos(-1);
typedef long long ll;


int main(void){
    int N;
    cin>>N;

    REP(i,N/1.08+1){
        if(int(i*1.08)==N){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<":("<<endl;
}




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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
//#define int long long int
const int MOD = 1000000007;
const ll LINF = (ll)1e18 - 1;
const int INF = 1e9 - 1;
const double EPS = 0.000000001;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void print(const vector<ll> &v) {
  for(auto x : v) {
    cout << x << " ";
  }
  cout << endl;
}

template<typename T>
struct BIT {
  std::vector<T> bit;

  BIT(int n) {
    n++;
    ll i = 1;
    while(i < n) i <<= 1;
    bit.assign(++i, 0);
  }

  //Sum of [0, k]
  T sum(int k) {
    T s = 0;
    for(++k; k > 0; k -= k & -k) s += bit[k];
    return s;
  }

  void add(int k, T x) {
    for(++k; k < bit.size(); k += k & -k) bit[k] += x;
  }
};

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;

  VL a(n);
  rep(i, n) cin >> a[i];

  ll l = 0;
  ll r = LINF;
  BIT<ll> bit(n);
  while((r - l) > 1) {
    ll mid = l + (r - l) / 2;
    ll count = 0;
    VL s(n+1, 0);
    rep(i, n) s[i+1] = a[i] >= mid ? 1 : -1;
    rep(i, n) {
      s[i + 1] += s[i];
    }
    rep(i, s.size()) s[i] += s.size() + 1;
    bit = BIT<ll>(*max_element(all(s)));
    rep(i, n + 1) {
      count += bit.sum(s[i]);
      bit.add(s[i], 1);
    }
    if (count >= ((n * (n + 1) / 2 + 1) / 2)) l = mid;
    else r = mid;
  }
  out(l);
  return 0;
}


Measured memory_bytes: 7012