akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

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

int n;
int arr[200005];
int brr[200005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n){
		cin>>arr[x]>>brr[x];
	}
	
	sort(arr,arr+n);
	sort(brr,brr+n);
	
	ll ans=0;
	if (n%2==1){
		ans=brr[n/2]-arr[n/2];
	}
	else{
		ans=brr[n/2]+brr[n/2-1]-arr[n/2]-arr[n/2-1];
	}
	
	cout<<ans+1<<endl;
}

Measured memory_bytes: 5188
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const ll mod = 1e9 + 7;
typedef pair<ll,ll>P;

int main(){

  int n;cin>>n;
  string s;cin>>s;

  int count=0;
  int ma=0;
  rep(i,1,s.size()){
    string l=s.substr(0,i),r=s.substr(i,s.size()-i);
    map<char,int>mp;
    rep(j,0,l.size())mp[l[j]]++;
    rep(j,0,r.size()){
      if(mp[r[j]]!=0){
        mp[r[j]]=0;
        count++;
      }
    }
    ma=max(ma,count);
    count=0;
  }

  out(ma);

  return 0;
}


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

long long h, w;
vector<vector<long long>> c;

long long solve();
long long calc(vector<long long>& a);

int main() {
  cin >> h >> w;
  c.assign(h, vector<long long>(w, 0));
  for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j) {
      cin >> c[i][j];
      c[i][j] = 1 - c[i][j];
      if (i != 0 && c[i][j]) c[i][j] += c[i - 1][j];
    }
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0;
  for (int i = 0; i < h; ++i) res = max(res, calc(c[i]));
  return res;
}

long long calc(vector<long long>& a) {
  stack<long long> len, id;
  len.push(0);
  a.push_back(0);
  long long res = 0, n = a.size();
  for (int i = 0; i < n; ++i) {
    int nextid = i;
    while (a[i] < len.top()) {
      nextid = id.top();
      res = max(res, len.top() * (i - id.top()));
      len.pop();
      id.pop();
    }
    if (a[i] > len.top()) {
      len.push(a[i]);
      id.push(nextid);
    }
  }
  return res;
}


Measured memory_bytes: 28652
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(void){
    string s, ans;
    int k;
    cin >> s;
    cin >> k;
    
    for (int i = 0; i < s.size() - 1; i++) {
        if (('a' + 26 - s[i]) % 26 <= k) {
            ans += "a";
            k -= ('a' + 26 - s[i]) % 26;
        }
        else ans += s[i];
    }
    char c = s[s.size() - 1];
    k %= 26;
    while (k > 0) {
        c++;
        if (c > 'z') c = 'a';
        k--;
    }
    ans += c;
    cout << ans << endl;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int a = scan.nextInt();
	a -= scan.nextInt();
	int c = scan.nextInt();

	System.out.println(Math.min(a, c) == c ? 0 : c - a);
    }
}

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

int main(void)
{
    int N;
    int *d;
    int i, j;
    int sum = 0;
    
    
    scanf("%d", &N);
    
    
    d = (int*)malloc(sizeof(int)*N);
    
    
    for(i=0; i<N; i++)
        scanf("%d", &d[i]);
    
    
    for(i=0; i<N; i++)
    {
        for(j=i+1; j<N; j++)
        {
            sum += d[i]*d[j];
        }
    }
    
    
    printf("%d\n", sum);
    
    
    free(d);
    
    //system("pause");
    
    return 0;
}


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

int main() {
	int a,b,c;
	cin >> a >> b >> c;
	if(a==b)
		if(a!=c)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	else if(a==c)
		cout << "Yes" << endl;
		
	else if(b==c)
	cout  << "Yes" << endl;
	else 
	cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
n, m = gets.split(" ").map(&:to_i)

@ind_arr = Array.new(n+1){|i| i}
@f_arr = Array.new(n+1, 1)

def find(x)
  return x if x == @ind_arr[x]
  # 途中のindexも更新しておく
  @ind_arr[x] = find(@ind_arr[x])
  return @ind_arr[x]
end

def union(x, y)
  x = find(x)
  y = find(y)
  return if x == y
  @ind_arr[x] = y
  @f_arr[y] += @f_arr[x]
end

m.times do
  a, b = gets.split(" ").map(&:to_i)
  a_ind = find(a)
  b_ind = find(b)
  next if a_ind == b_ind

  @ind_arr[b_ind] = a_ind
  @f_arr[a_ind] += @f_arr[b_ind]
end

puts @f_arr.max


Measured memory_bytes: 17380
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

# fact & factinv
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, 2000 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

def solve(S: int):
    res = 0    
    for k in range(1, S//3+1):
        if S - 3 * k < 0:
            break
        res += (fact[S - 2 * k -1] * factinv[S - 3 * k] * factinv[k - 1]) % MOD
    print(res % MOD)
    return 


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll n, a[100000] = {0}, b[100000] = {0}, c[100000] = {0}, result = 0;
  cin >> n;
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  rep(i, n) cin >> c[i];
  sort(a, a + n);
  sort(c, c + n);
  rep(i, n) {
    ll ab = lower_bound(a, a + n, b[i]) - a;
    ll bc = n - (upper_bound(c, c + n, b[i]) - c);
    result += ab * bc;
  }
  cout << result << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int n,r;
    while (scanf("%d %d",&n,&r)!=EOF) {
        if (n>=10)
            printf("%d\n",r);
        else {
            printf("%d\n",r+100*(10-n));
        }
    }
    return 0;
}


Measured memory_bytes: 256
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = input().rstrip('\n')
    ok = 0
    for i in range(3):
        if N[i] == "7":
            ok = 1
    if ok:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 62096
#include <cstdio>
#include <utility>
#include <vector>
#include <string>
using namespace std;

#define gcu getchar_unlocked
#define ii inline int in
#define is inline bool scan
ii(int c) {
	int n = 0;
	bool minus = false; if (c == '-') minus = true, c = gcu();
	do {n = 10 * n + (c - '0'), c = gcu();} while (c >= '0');
	//return n; }
	return minus ? -n : n; }
ii() {return in(gcu());}
is(int &n){int c=gcu();return c==EOF?false:(n=in(c),true);}
is(char &c){c=gcu();gcu();return c!=EOF;}
is(string &s){int c; s = "";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#undef ii
#define pcu putchar_unlocked
template <typename T>
void out(T n) {
	static char buf[20];
	char *p = buf;
	if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
void out(const char *s){while(*s)pcu(*s++);}
void out(char c){pcu(c);}
void out(string &s){for (char c: s) pcu(c);}
template <typename head, typename... tail>
void out(head&& h, tail&&... t){out(h);out(move(t)...);}
//template <typename T>
//void out(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
#undef svo

int main() {
	for (int H, W; H = in(), W = in(), H || W;) {
		vector<string> r(H);
		for (auto &s: r)
			scan(s);
		int x = 0, y = 0;
		char c = r[y][x];
		for (;c != '.' && c != 'X'; c = r[y][x]) {
			r[y][x] = 'X';
			switch (c) {
			case '>': x += 1; break;
			case '<': x -= 1; break;
			case 'v': y += 1; break;
			case '^': y -= 1; break;
			}
		}
		if (c == 'X')
			out("LOOP\n");
		else
			out(x, ' ', y, '\n');
	}
}


Measured memory_bytes: 2572
//#include"cpp_kyopro.h"
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include<stdio.h>

using namespace std;

int main(void) {
	string s; cin >> s;
	if (s == "Sunny") {
		cout<<"Cloudy";
		return 0;
	}
	else if (s == "Cloudy") {
		cout<< "Rainy";
		return 0;
	}
	else if (s == "Rainy") {
		cout << "Sunny";
		return 0;
	}
	return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define pii pair<int, int> 
#define all(a) a.begin(), a.end()
#define int long long
#define ll long long
#define vi vector<int>
#define vip vector<pii>
#define mod1 998244353
#define mod 1000000007
#define endl "\n"
#define loop(i,a,b) for(int i=a;i<b;i++)
#define bloop(i,a,b) for(int i=a;i>=b;i--)
#define testcase  int t; cin>>t; while(t--) 
#define FIO ios_base::sync_with_stdio(false);  cin.tie(NULL);

using namespace std;

int max(int a, int b) { return (a > b)? a : b; } 

int min(int a, int b) { return (a < b)? a : b; }


   
/*************************************************************************/



int32_t main() {
	
	FIO
	// testcase
	{
		int a,v,b,w,ti;
		cin>>a>>v>>b>>w>>ti;
		int sa,sb;
		// sa = v*ti+a;
		// sb = w*ti+b;
		if(w>=v)
			cout<<"NO"<<endl;
		else if(ti*(v-w)>=abs(b-a))
			cout<<"YES"<<endl;
		else 
			cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long
#define ld long double
#define MAX 1000000000
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t=1;
	//cin>>t;
	for(int cc=1;cc<=t;cc++){
        //cout<<"Case #"<<cc<<": ";
        ll n,m;
        cin>>m;
        ll a[m],ans[m]={0};
        for(int i=0;i<m-1;i++)
        	cin>>a[i],ans[a[i]-1]++;
        for(int i=0;i<m;i++)
        	cout<<ans[i]<<" ";
        cout<<endl;
	}
}


Measured memory_bytes: 6784
n=list(input())
N=len(n)
k=int(input())
dp1=[[0 for i in range(k+1)] for j in range(N+1)]
dp2=[[0 for i in range(k+1)] for j in range(N+1)]
dp1[0][0]=1
for i in range(1,N+1):
  x=int(n[i-1])
  
  if i!=N and x!=0:
    for j in range(k+1):
      if j==0:
        dp2[i][j]=dp1[i-1][j]+dp2[i-1][j]
      else:
        dp1[i][j]=dp1[i-1][j-1]
        dp2[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(x-1)+dp2[i-1][j]+dp2[i-1][j-1]*9
  
  elif i!=N and x==0:
    for j in range(k+1):
      if j==0:
        dp1[i][j]=dp1[i-1][j]
        dp2[i][j]=dp2[i-1][j]
      else:
        dp1[i][j]=dp1[i-1][j]
        dp2[i][j]=dp2[i-1][j]+dp2[i-1][j-1]*9
  
  elif i==N and x!=0:
    for j in range(k+1):
      if j==0:
        dp2[i][j]=dp1[i-1][j]+dp2[i-1][j]
      else:
        dp2[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*x+dp2[i-1][j]+dp2[i-1][j-1]*9
  
  else:
    for j in range(k+1):
      if j==0:
        dp2[i][j]=dp2[i-1][j]
      else:
        dp2[i][j]=dp1[i-1][j]+dp2[i-1][j]+dp2[i-1][j-1]*9

print(dp2[N][k])

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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) (x).begin(),(x).end()
#define Ceil(x, n) (((((x))+((n)-1))/n))
#define CeilN(x, n) (((((x))+((n)-1))/n)*n)

#define INF 2e7
#define INF_LL 1LL<<60
#define ll long long
#define MAX_V 5000000000000000000

ll n, a, b, c, d;
map<ll, ll> mp;

ll dfs(ll x) {
    if(mp.count(x)) return mp[x];     /* メモ化 */
    if(x == 0) return mp[0] = 0;
    if(x == 1) return mp[1] = d;

    ll ret;
    if(__builtin_mul_overflow(x, d, &ret)) ret = INF_LL;
    else ret = x * d;
    vector<ll> val = {a, b, c};
    vector<ll> div = {2, 3, 5};

    REP(i, 3) {
        ll va = val[i], di = div[i];

        /* ceil */
        ll tmp = (x + (di-1)) / di;
        ret = min(ret, dfs(tmp) + (tmp*di - x) * d + va);

        /* div */
        tmp = x / di;
        ret = min(ret, dfs(tmp) + (x - tmp*di) * d + va);
    }
    return mp[x] = ret;
}

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

    REP(query, t) {
        cin >> n >> a >> b >> c >> d;
        mp.clear();
        cout << dfs(n) << endl;
    }

    return 0;
}


Measured memory_bytes: 4408
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let n = input::<i32>();
    let m = input::<i32>();
    let c = input::<i32>();
    let b = (0..m).map(|_| input()).collect::<Vec<i32>>();
    let a = (0..n)
        .map(|_| (0..m).map(|_| input()).collect())
        .collect::<Vec<Vec<i32>>>();

    let ans = a
        .iter()
        .filter(|a| a.iter().zip(&b).map(|(a, b)| a * b).sum::<i32>() + c > 0)
        .map(|_| 1)
        .sum::<i32>();
    println!("{}", ans);
}


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

template <typename T>
using lim = numeric_limits<T>;

const int MAXN = 101;
string arr[MAXN];

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

	int n, l;
	cin >> n >> l;
	for (int i = 0; i < n; i++) cin >> arr[i];

	sort(arr, arr+n);
	
	for (int i = 0; i < n; i++) cout << arr[i];
	cout << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 5010
#define inf 1000000000000000ll
int n,A,B; ll f[N][N<<1];
struct data { int x,y; bool operator <(const data&a) const { return x<a.x||x==a.x&&y<a.y; } }a[N];
signed main() {
	scanf("%d%d%d",&n,&A,&B); for (int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].y=i;
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++){ll s=inf;for(int j=0;j<=n*2;j++){s=min(s,f[i-1][j]);if(j&1){f[i][j]=s+((j+1>>1)==a[i].y?0:((j+1>>1)<a[i].y?B:A));}else{f[i][j]=s+(((j>>1)<a[i].y?B:A));}}}
    ll ans=inf;
    for (int i=0;i<=n*2;i++) ans=min(ans,f[n][i]);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 391680
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;

i64 N;

i64 s[] = {3, 5, 7};

i64 recursive(i64 k, int a) {
    if(k > N) return 0;
    i64 retval = (a == 7);
    for(int i = 0; i < 3; i++) {
        retval += recursive(10 * k + s[i], a | (1 << i));
    }
    return retval;
}

int main() {
    cin >> N;
    cout << recursive(0, 0) << endl;
    return 0;
}

Measured memory_bytes: 256
class Gcd
  attr_accessor :ans
  def initialize
    @ans = 0
  end

  def solve(a,b)
    if b == 0
      return self
    elsif a < b
      return solve(b,a)
    else
      q,r = a.divmod(b)
      @ans += b * q
      return solve(b, r)
    end
  end
end

n,x = gets.split.map &:to_i
puts Gcd.new.solve(n-x,x).ans * 3

Measured memory_bytes: 3836
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]
A.sort(reverse=True)

dp = [[0] * (N + 1) for _ in range(N + 1)]

for s, (a, i) in enumerate(A):
    for l in range(s + 1):
        r = s - l
        dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + a * (i - (l + 1)))
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a * (N - r - i))

ans = max([max(d) for d in dp])
print(ans)


Measured memory_bytes: 105664
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define clear(x, y) memset(x, y, sizeof(x))

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while(ch != '-' && (!isdigit(ch))) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int maxn(1e5 + 10);
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num;
inline void add_edge(int from, int to)
{
	e[++e_num] = (edge) {head[from], to};
	head[from] = e_num;
}

int n, m, dep[maxn], s[maxn], k[maxn], len, X, Y, stk[maxn], top, sum;
long long ans;

void dfs(int x, int fa)
{
	dep[x] = dep[fa] + 1; s[x] = (dep[x] & 1) ? 1 : -1; sum += s[x];
	for(RG int i = head[x]; i; i = e[i].next)
	{
		int to = e[i].to; if(to == fa) continue;
		if(dep[to]) len = abs(dep[x] - dep[to]) + 1, X = x, Y = to;
		else dfs(to, x);
	}
}

void dfs2(int x, int fa)
{
	for(RG int i = head[x]; i; i = e[i].next)
	{
		int to = e[i].to; if(to == fa) continue;
		if((X == x && Y == to) || (X == to && Y == x)) continue;
		dfs2(to, x), k[x] += k[to], s[x] += s[to];
	}
	if(!k[x]) ans += abs(s[x]);
	else stk[++top] = k[x] * s[x];
}

int main()
{
	n = read(), m = read();
	for(RG int i = 1, a, b; i <= m; i++)
		a = read(), b = read(),
		add_edge(a, b), add_edge(b, a);
	dfs(1, 0);
	if(m == n - 1) { if(sum) return puts("-1"), 0; }
	else if(len & 1)
	{
		if(sum % 2 == 1) return puts("-1"), 0;
		ans += abs(sum / 2), s[X] -= sum / 2, s[Y] -= sum / 2;
	}
	else
	{
		if(sum) return puts("-1"), 0;
		k[X] = 1, k[Y] = -1;
	}
	dfs2(1, 0); stk[++top] = 0;
	std::sort(stk + 1, stk + top + 1);
	for(RG int i = 1; i <= top; i++) ans += abs(stk[(top + 1) / 2] - stk[i]);
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 8448
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <deque>
#include <list>
#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;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


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;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    sort(all(A));
    cout << A[N-1] - A[0];
    cout << endl;
    return 0;
}




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

int main(){
    int a,b;
    cin >> a >> b;
    if(b%a == 0) cout << a+b << endl;
    else cout << b-a << endl;    
    return 0;
}


Measured memory_bytes: 256
#include <math.h>

#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int, int>;

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

  int ok = 0;
  rep(i, n) {
    int d1, d2;
    cin >> d1 >> d2;
    if (d1 == d2) {
      ok++;
    } else {
      ok = 0;
    }
    if (ok == 3) break;
  }
  cout << (ok == 3 ? "Yes" : "No");
  return 0;
}


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

int main() {
	// freopen("in.txt", "r", stdin);
	int ans = 0;
	for (int i = 1; i <= 5; i++) {
		int x;
		cin >> x;
		if (x == 0) ans = i;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3620
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r.sort(key = lambda x:x[1],reverse = True)
ans = 0
while len(r) > 0:
    _,y = r[-1]
    ans += 1
    while len(r) > 0 and r[-1][0] < y:
        r.pop()
print(ans)

Measured memory_bytes: 61784
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,m; cin >> n >> m;
    string ans = string(n, '0');
    vector<bool> used(10,false);

    int s,c;
    
    if(n == 1){
        rep(i,m){
            cin >> s >> c;
            if(used[s] && int(ans[s-1]-'0') != c){
                cout << -1 << endl;
                return 0;
            }else{
                used[s] = true;
                ans[s-1] = char(c + '0');
            }
        
        }
        cout << ans << endl;
        return 0;
    }

    rep(i,m){
        cin >> s >> c;
        if(s == 1 && c == 0){
            cout << -1 << endl;
            return 0;
        }else{
            if(used[s] && int(ans[s-1]-'0') != c){
                cout << -1 << endl;
                return 0;
            }else{
                used[s] = true;
                ans[s-1] = char(c + '0');
            }
        }
    }
    if(ans[0] == '0') ans[0] = '1';
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

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

    int[] b = new int[n + 5];

    for (int i = 0; i < n - 1; i++) {
      b[i] = sc.nextInt();
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
      if (i == 0) res += b[i];
      else if (i == n - 1) res += b[i - 1];
      else res += Math.min(b[i], b[i - 1]);
    }

    System.out.println(res);
  }
}


Measured memory_bytes: 21332
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    L, R = map(int, input().split())

    R_r = R%2019
    if (R - L) >= R_r :
        print(0)
    else:
        L_r = L%2019
        ans = (L_r*(L_r+1))%2019
        for l in range(L_r, R_r):
            for r in range(l+1, R_r+1):
                ans = min(ans, (l*r)%2019)
        print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc133","c",main)


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

#define Q 1000000007

int main(void){
  long long ans, tmp[32]; // 10^9 は32bitに収まる
  int m, n;
  
  cin >> m >> n;
  tmp[0] = m;
  for (int i=1; i<32; i++){
    tmp[i] = (tmp[i-1]*tmp[i-1])%Q;
  }
  ans = 1;
  for (int i=0; i<32; i++){
    if (n & (1<<i)){
      ans = (ans*tmp[i])%Q;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3108
import Control.Applicative
import Data.List

main :: IO ()
main = solve <$> readLn >>= putStrLn

solve :: Int -> String
solve n = case find f [1..9] of
  Just _ -> "Yes"
  Nothing -> "No"
  where
    f x = let (q, r) = n `divMod` x in q < 10 && r == 0


Measured memory_bytes: 508
import java.util.Scanner;
 
public class Main {
 
	public Main() {
		// TODO 自動生成されたコンストラクター・スタブ
	}
 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n,m,answer,index;
		float ans;
		String s,t;
		
			// 整数の入力
		
		n = sc.nextInt();
		sc.close();
		
		if(n%2==0){
			System.out.print("0.5");
		}
		else {
			m=(n+1)/2;
			ans=(float)m/n;
			System.out.print(ans);
		}

			// 出力
 
	}
}	

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

int main() 
{
    long int n;
    cin>>n;
    //cout<<n;
    int y=n/100,m=n%100;
    if(y==0 || m==0){
        
        if(m==0 && y==0)
        {
            cout<<"NA";
            exit(0);
        }
    if(y==0 && m>12)
    {
        cout<<"NA";
        exit(0);
    }
    if(m==0 && y>12)
    {
        cout<<"NA";
        exit(0);
    }
        if(y==0 && m<=12)
        {
            cout<<"YYMM";
            exit(0);
        }
        if(m==0 && y<=12)
        {
            cout<<"MMYY";
            exit(0);
        }
    
    }
    if(y>12 && m>12)
    {
        cout<<"NA";
        exit(0);
    }
    if(y<=12 && m<=12)
    {
        cout<<"AMBIGUOUS";
    }
    else if(y>12 && m<=12)
    {
        cout<<"YYMM";
    }
    else
    {
        cout<<"MMYY";
    }
	return 0;
}

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

public class Main {
    int n, m;
    int[] a;
    int[] b;
    int[] c;
    long[] dp;

    void run() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        a = new int[m];
        b = new int[m];
        c = new int[m];
        dp = new long[1 << n];

        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
            for (int j = 0; j < b[i]; j++) {
                int cc = sc.nextInt() - 1;
                c[i] |= 1 << cc;
            }
        }

        memo = new long[1 << 12];
        Arrays.fill(memo, -1);

        long ans = solve(0);
        System.out.println(ans == INF ? -1 : ans);
    }

    long INF = 1L << 60;

    long[] memo;
    // 状態Sを満たす最小のコストを返す。
    long solve(int S) {

        if (memo[S] > -1) {
            return memo[S];
        }
        if ((1 << n) - 1 == S) {
            return memo[S] = 0;
        }

        long min = INF;
        for (int i = 0; i < m; i++) {
            if ((S | c[i]) == S) {
                continue;
            }
            min = Math.min(min, solve(S | c[i]) + a[i]);
        }

        return memo[S] = min;
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }

}


Measured memory_bytes: 31232
from itertools import combinations

N = int(input())
P = {tuple(map(int, input().split())) for _ in range(N)}

if N == 1:
    print(1)
    exit()

COST = float("inf")
for a, b in combinations(P, 2):
    p = a[0] - b[0]
    q = a[1] - b[1]
    cost = 0
    for x, y in P:
        if (x + p, y + q) not in P:
            cost += 1
    COST = min(COST, cost)
print(COST)


Measured memory_bytes: 3064
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cctype>
#include<cassert>
#include<cmath>

#define INF (1<<29)
#define all(c) (c).begin(),(c).end()
#define D(x) cout << #x " is " << (x) << endl
#define rep(i,n) for(int i = 0; i < n; i++)
#define foreach(it,c) for(__typeof__((c).begin()) it=(c).begin();it!=(c).end();it++)

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

string toStr(int num){
  if(num==0)return "0";
  string res = "";
  while(num){
    res+=(num%10)+'0';
    num/=10;
  }
  reverse(res.begin(),res.end());
  return res;
}

int toInt(string s){return atoi(s.c_str());}

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

int main(void){

  int n,m;
  for(int tc=1;cin >> n >> m,n|m;tc++){
    vector<int>p(n);
    int cnt=0;
    fill(all(p),0);

    while(true){
      vector<bool>used(n);
      fill(all(used),false);
      rep(i,n){
	rep(j,n){
	  if(i==j || used[i] || used[j])continue;
	  if(p[i]==p[j]){
	    p[i]++;
	    p[j]=0;
	    used[i]=used[j]=true;
	    if(p[i]==m){
	      cout << "Case " << tc << ": " << cnt+1 << endl;
	      goto end;
	    }
	  }
	}
      }
      cnt++;
    }
  end:;
  }
  return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (long long i = (a); i <= (b); i++)
#define FORD(i,a,b) for (long long i = (a); i >= (b); i--)
#define REP(i,a) FOR(i,0,(long long)(a)-1)
#define reset(a,b) memset(a,b,sizeof(a))
#define all(x) x.begin(), x.end()
#define uni(x) x.erase(unique(all(x)), x.end());
#define BUG(x) cout << #x << " = " << x << endl
#define BUGP(x) cout << #x << " = " << x._1 << ", " << x._2 << endl
#define PR(x,a,b) {cout << #x << " = "; FOR (_,a,b) cout << x[_] << ' '; cout << endl;}
#define CON(x) {cout << #x << " = "; for(auto _i:x) cout << _i << ' '; cout << endl;}
#define mod 1000000007
#define pi acos(-1)
#define eps 1e-8
#define pb push_back
#define sqr(x) (x) * (x)
#define _1 first
#define _2 second

long long a[1111], b[1111], c[1111], m, n, ans;
vector<long long> v;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  REP (i, n) cin >> a[i] >> b[i] >> c[i];
  REP (i, 2) REP (j, 2) REP (k, 2) {
    int ii = i * 2 - 1;
    int jj = j * 2 - 1;
    int kk = k * 2 - 1;
    v.clear();
    long long tmpa = 0, tmpb = 0, tmpc = 0, tmp = 0;;
    REP (z, n) v.pb(a[z] * ii + b[z] * jj + c[z] * kk);
    sort(all(v));
    reverse(all(v));
    REP (i, m) tmp += v[i];
    ans = max(ans, tmp);
  }
  cout << ans;
}


Measured memory_bytes: 256
use std::io;
use std::io::prelude::*;

fn main() {
    let stdin = io::stdin();
    for line in stdin.lock().lines() {
        let uline = line.unwrap();
        let vec: Vec<&str> = uline.split_whitespace().collect();
        let h: usize = vec[0].parse().unwrap_or(0);
        let w: usize = vec[1].parse().unwrap_or(0);
        if h != 0 && w != 0 {
            for i in 0..h {
                for j in 0..w {
                    if i == 0 || i == h - 1 || j == 0 || j == w - 1{
                        print!("#");
                    } else {
                        print!(".");
                    }
                }
                println!("");
            }
            println!("");
        }
    }
}


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

int main(){
    int n;
    cin>>n;
    vector<int> a(3*n);
    long long ans=0;
    for(int i=0;i<3*n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    for(int i=n;i<3*n;i=i+2)ans+=a[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4248
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
temp = [LIST() for _ in range(N)]
temp = [list(x) for x in zip(*temp)]
A, B = temp[0], temp[1]

DP = [[INF]*(H + max(A) + 1) for _ in range(N + 1)]
DP[0][0] = 0
a = max(A)

for i in range(N):
	for j in range(H + a + 1):
		if j < A[i]:
			DP[i+1][j] = DP[i][j]
		else:
			DP[i+1][j] = min(DP[i][j], DP[i+1][j-A[i]] + B[i])

print(min(DP[N][H:H + max(A) + 1]))

Measured memory_bytes: 317020
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define mset(s, _) memset(s, _, sizeof s)
#define ALL(a) (a).begin(), (a).end()
using namespace std;
const int MAX_N = 1000000;
pair<int, int> itv[MAX_N];
int S[MAX_N];
int E[MAX_N];

int main(void) {
  int n;
  cin >> n;
  int x, l;
  rep(i, 0, n - 1) {
    cin >> x >> l;
    S[i] = x - l;
    E[i] = x + l;
  }

  rep(i, 0, n - 1) {
    itv[i].first = E[i];
    itv[i].second = S[i];
  }

  sort(itv, itv + n);

  int ans = 0;
  int tmp_e = -pow(10, 9) - 1;
  rep(i, 0, n - 1) {
    // cout << itv[i].second << " " << itv[i].first << ": ";
    if (tmp_e <= itv[i].second) {
      ans++;
      tmp_e = itv[i].first;
      // cout << "+";
    } else {
      // cout << "-";
    }
    // cout << endl;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8832
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
    int A[3][3];
    rep(i,3){
        rep(j,3){
            cin >> A[i][j];
        }
    }
    bool ans = true;
    int a[3];
    int b[3];
    a[0]=0;
    rep(i,3){
        b[i] = A[0][i]-a[0];
    }
    rep(i,3){
        a[i] = A[i][0]-b[0];
    }
    rep(i,3){
        rep(j,3){
            if(A[i][j] != a[i]+b[j]){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
// https://ynucpc.github.io/blog/2018/04/15/cp_vscode/
// http://www.atmarkit.co.jp/ait/articles/1509/08/news019.html

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,n,m) for(ll i=(n);i<(ll)(m);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b)) 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int stoi (string s, int tmp=10){
	istringstream stm(s);
	int res;
	stm >> res;
	return res;
}
double stod(string s, int tmp=10){
	istringstream stm(s);
	double res;
	stm >> res;
	return res;
}


// greater
// min: *std::min_element(A, A+N)

ll A[100000];

int main(){	
	// ll A;
    // cin >> A;
	// cout << "hello" << endl;
	// cout << stoi("14") << endl;
	// cout << max({1,3}) << endl;
	ll N, K;
	cin >> N >> K;
	rep(i, N)cin >> A[i];
	ll Ones[41] = {};
	rep(i, N){
		rep(j, 41) Ones[j] += A[i]>>j & 1;
	}
	ll A1[42]={}, A2[41]={};
	A2[0] = max(Ones[0], N-Ones[0]);
	rep1(i, 40){
		A2[i] = A2[i-1] + (max(Ones[i], N-Ones[i])<<i);
	}
	A1[41] = 0;
	for(ll i=40; i>=0; i--){
		A1[i] = A1[i+1]+(((K>>i & 1) ? N-Ones[i] : Ones[i]) << i);
		//show(i); show(A1[i]);
	}
	ll ans=0;
	for(ll i=40; i>=0; i--){
		if(((K>>i)&1)&&Ones[i]>=N-N/2){
			chmax(ans, A1[i+1]+A2[i]);
		}
	}
	chmax(ans, A1[0]);
	cout << ans << endl;
	// rep(i, 4)show(Ones[i]);
	
	// rep(i, 4)show(A1[i]);
	// rep(i, 4)show(A2[i]);

}








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

typedef long long ll;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0)
#define endl '\n'
#define DB(x) cout<<#x<<" : "<<x<<'\n'
#define PB push_back

const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
double p[3005];
double dp[3005][3005];
// dp[i][j] -> probablity of having i coins and j heads
//recurrence relation:
// dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j] * (1 - p[i]);

int main(){
    int n;
    scanf("%d", &n);
    for(int i =1 ;i<= n;++i) scanf("%lf", p + i);
    dp[0][0] = 1; //Zero coins zero head. hence probabilty is 1
    for(int i = 1;i<= n; ++i)
        for(int j = 0; j<= i ; ++j ){
           if(j) dp[i][j] = dp[i-1][j-1]*p[i];
           dp[i][j] += dp[i-1][j]*(1-p[i]);
        }

    double ans = 0.0;
    for(int i = 0; i <= n; ++i){
        if(i > n-i) ans += dp[n][i]; //we can use i > n-i instead of i > n/2 
    }
    printf("%.12lf",ans);
    return 0;
}

Measured memory_bytes: 68992
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 100005
ll n, m;
vector<ll> g[N];
ll vis[N];
ll dp[N];

ll solve(ll k){
	if(vis[k]==1)
	{
		return dp[k];
	}
	vis[k] = 1;
	ll max_a = 0;
	vector<ll>:: iterator it;
	for(it=g[k].begin();it!=g[k].end();it++)
	{
		max_a = max(max_a,solve(*it)+1);
	}
	dp[k] = max_a;
	return dp[k];
}

int main()
{
	cin>>n>>m;
	ll x,y;
	for(ll i=0;i<m;i++)
	{
		cin>>x>>y;
		g[x-1].push_back(y-1);	
	}
	ll ans = 0;
	for(ll i=0;i<n;i++)
	{
		ans = max(ans,solve(i));	
	}	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 9344
#include<iostream>
#include<algorithm>
using namespace std;
struct line
{
	int l, r;
 
}a[100010];
bool operator<(const line& a,const line& b) {
	return a.r < b.r;
 
}
int main() {
	int n,tot=1;
	cin >> n;
	for (int i = 1,x,L; i <= n; i++) {
		cin >> x >> L;
        a[i].l = x - L;
        a[i].r = x + L;
	}
	sort(a + 1, a + n + 1);
	int end = a[1].r;
	for (int i = 2; i <= n; i++) {
		if (a[i].l >= end) {
			tot++;
			end = a[i].r;
	}
	}
	cout << tot << endl;
	return 0;
}

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

char str[205];

int main() {
	//freopen("input.in", "r", stdin);
	//freopen("output.o", "w", stdout);
	scanf("%s", str);
	int len = strlen(str);
	int cur = len - 1;
	while (true) {
		bool lb = true;
		for (int i = 0; i < cur / 2; i++) {
			if (str[i] != str[i+cur/2]) lb = false;
		}
		if (lb) {
			printf("%d", cur-1);
			return 0;
		}
		cur -= 2;
	}
}

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

int main() {
    int N, res=0, ok=1;
    cin >> N;
    int H[N];
    for (int i=0; i<N; i++) cin >> H[i];

    for (int i=0; i<N; i++) {
        for (int j=0; j<i; j++) {
            if (H[j] > H[i]) {
                ok = 0;
                break;
            }
        }
        if (ok) res += 1;
        ok = 1;
    }
    
    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define ll long long
#define ld long double
#define vvi vector<vi>
#define vll vector<ll>
#define vld vector<ld>
#define vvll vector<vll>
#define vvld vector<vld>
#define MOD 1000000007
#define endL << '\n'
#define ii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define endL << '\n'
#define vii vector<ii>
#define pb push_back

/*
ll powmod(ll x, ll y, ll mod){
	ll res = 1;
	while (y > 0){
		if (y%2) res = (res*x) % mod;
		x = (x*x) % mod;
		y /= 2;
	}
	return res;
}
*/

/*const int N = 1000000;
int lp[N+1];
vector<ll> pr;

void sieve(){
	for (int i=2; i<=N; ++i) {
	    if (lp[i] == 0) {
	        lp[i] = i;
	        pr.push_back (i);
	    }
	    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
	        lp[i * pr[j]] = pr[j];
	}
}*/
int n;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1; //cin >> t;
	while(t--){
		cin >> n;
		int x;
		vector<int> par(3, 0);
		for (int i = 0; i < n; i++){
			cin >> x; par[x-1]++;
		}
		/*int nax = 305;
		double dp[n][305][305];*/
		vector<vector<vector<double>>> dp(n+1, vector<vector<double>>(305, vector<double>(305, 0.0)));
		// cout << par[0] << " " << par[1] << " " << par[2] << endl;
		for (int filled = 1; filled <= n; filled++){
			for (int i = filled; i >= 0; i--){
				for (int j = par[1]+par[2]; j >= 0; j--){
					int k = filled - i - j;
					// cout << i << " " << j << " " << k << endl;
					if (k < 0 || k > par[2]) continue;
					// cout << "Correct: " << i << " " << j << " " << k << endl;
					dp[i][j][k] = 1.0;
					double res = ((i == 0) ? 0 : (i * dp[i-1][j][k]));
					res += ((j == 0) ? 0 : (j * dp[i+1][j-1][k]));
					res += ((k == 0) ? 0 : (k * dp[i][j+1][k-1]));
					res *= (1.0)/n;
					dp[i][j][k] += res;
					dp[i][j][k] *= (1.0 * n) / filled;
				}
			}
		}
		cout << fixed << setprecision(10) <<  dp[par[0]][par[1]][par[2]];


	}
}


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

using namespace std;
string s[200100];
vector < string > v;
map < string , int > mp;

int main()
{
    int n;  cin >> n;
    int Max = 0;
    for(int i = 0;i<n;i++){
        cin >> s[i];
        mp[s[i]]++;
    }
    for(auto it : mp)  Max = max(Max , it.second);
    for(int i = 0;i<n;i++)  if(mp[s[i]] == Max)  v.push_back(s[i]);
    sort(v.begin() , v.end());
    mp.clear();
    for(auto x : v)  if(!mp.count(x))  cout << x << '\n' , mp[x];
    return 0;
}



Measured memory_bytes: 28404
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for ii in range(h):
            for jj in range(w):
                if (i>>ii)&1 == 1 and (j>>jj)&1 == 1:
                    if c[ii][jj] == '#':
                        cnt += 1
        if cnt == k:
            ans += 1
print(ans)


Measured memory_bytes: 9112
using System;

class Program
{
    static void Main(string[] args)
    {
        var nx = Console.ReadLine().Split(' ');
        var n = int.Parse(nx[0]);
        var x = int.Parse(nx[1]);

        var d = new int[n + 1];
        d[n] = x;

        var s = Console.ReadLine().Split(' ');
        for (int i = 0; i < n; i++)
        {
            d[i] = int.Parse(s[i]);
        }

        Array.Sort(d);

        var diff = new int[n];
        for (int i = 0; i < n; i++)
        {
            diff[i] = d[i + 1] - d[i];
        }

        var ans = diff[0];
        for (int i = 1; i < n; i++)
        {
            ans = gcd(ans, diff[i]);
        }

        Console.WriteLine(ans);
    }

    static int gcd(int a, int b)
    {
        if (a == 0) return b;
        else if (b == 0) return a;
        else if (a < b) return gcd(b % a, a);
        else return gcd(a % b, b);
    }
}


Measured memory_bytes: 18784
#include<iostream>
#include<cmath>
#include<string>

using namespace std;

int n, m;
int s[10] = { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1 };

int main() {
	bool f = true;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		if (s[a] != b && s[a] == -1)s[a] = b;
		else if (s[a] == b);
		else f = false;
	}
	if (!f) {
		cout << -1 << endl;
		return 0;
	}

	for (int num = pow(10, n - 1) == 1 ? 0 : pow(10, n - 1); num < pow(10, n); num++) {
		string pr = to_string(num);
		bool f1 = true;
		for (int i = 0; i < n; i++) {
			if (s[i] == -1);
			else if (pr[i] == '0' + s[i]);
			else f1 = false;
		}
		if (f1) {
			cout << num << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)ans+=1ll*i*(n-i+1);
	for(int i=0;i<n-1;i++){
		int u,v;cin>>u>>v;
		if(u>v)swap(u,v);
		ans-=1ll*u*(n-v+1);
	}
	cout<<ans;
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String str[] = br.readLine().split(" ");
            double num = Double.parseDouble(str[0] + str[1]);
            int a = (int)Math.sqrt(num);
            if (a * a == num) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}


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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	int N, A, B, C;
	cin >> N >> A;
	if (A>=N)
		cout << "unsafe\n";
	else
		cout << "safe\n";
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF (long long)(1e18)
#define MOD (int)(1e9+7)

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX 1100

int N, M, ans = 1;
int A[MAX], B[MAX];

signed main(){
	cout<<fixed<<setprecision(7);
	
	cin>>N>>M;
	
	for(int i = 0; i < N; i++){
		cin>>A[i];
	}
	for(int i = 0; i < M; i++){
		cin>>B[i];
	}
	
	sort(A,A+N);
	sort(B,B+M);
	
	for(int i = N-1, j = M-1, k = N*M; k&&ans; k--){//cout<<k<<" "<<i<<" "<<j<<" "<<A[i]<<" "<<B[j]<<endl;
		if(i < 0){
			if(B[j] == k) ans *= N-i-1, j--;
			else ans *= (M-j-1)*(N-i-1)-(N*M-k);
		} else if(j < 0){
			if(A[i] == k) ans *= M-j-1, i--;
			else ans *= (M-j-1)*(N-i-1)-(N*M-k);
		} else if(A[i] == k && B[j] == k){
			i--,j--;
		} else if(A[i] == k){
			if(i&&A[i]==A[i-1]){ans = 0;break;}
			ans *= M-j-1,i--;
		} else if(B[j] == k){
			if(j&&B[j]==B[j-1]){ans = 0;break;}
			ans *= N-i-1,j--;
		} else {
			ans *= (M-j-1)*(N-i-1)-(N*M-k);
		}
		ans %= MOD;
		//cout<<"ans = "<<ans<<endl;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

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

int main(){
  
  int a,b,c;
  cin >> a >> b >> c;
  
  if( b - a*c >= 0 ){
    
    cout << c << endl;
    
  }
  
  else{
    
    cout << b/a << endl;
    
  }
 
}


Measured memory_bytes: 256