akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <math.h>
using namespace std;


int main()
{
	int n, d;
	cin >> n >> d;
	cout << (n + 2 * d) / (2 * d + 1) << endl;

	return 0;
}


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


int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll t= 1;
	// cin>>t;

	while(t--){
		ll n;
		cin>>n;

		map<ll,ll> m;
		ll a;
		for(ll i=0;i<n;++i) {cin>>a; m[a]++;}

		a = 0;
		for(auto &x : m){
			for(auto &y : m){
				for(auto &z : m){
					if(x.first != y.first and y.first != z.first and x.first != z.first){
						if(x.first+y.first > z.first and x.first+z.first > y.first and y.first+z.first > x.first)
							a += x.second*y.second*z.second;
					}
				}
			}
		}

		cout<<a/6<<"\n";

	}

	return 0;
}

Measured memory_bytes: 3640
#include<iostream>
using namespace std;
int main(){
  int n, a[200000];
  cin >> n;
  int m1 = -1, m2 = -1;
  for(int i=0; i<n; i++){
    cin >> a[i];
  	if (a[i] >= m1) {
		m2 = m1;
      	m1 = a[i];
    }else if(a[i] >= m2){
      	m2 = a[i];
    }
  }
  for(int i=0; i<n; i++){
    if(a[i] == m1)cout << m2 << endl;
    else cout << m1 << endl;
  }
  return 0;
}

Measured memory_bytes: 2432
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100005],k[50005];
bool used[100005];
int main()
{
	int p=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(a[i+1]==a[i]&&used[i+1]==false&&used[i]==false)
		{
			k[p]=a[i];
			used[i]=used[i+1]=true;
			p++;
		}
	}
	long long ans=1ll*k[p-1]*k[p-2];
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 896
from collections import defaultdict

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

dp = {0:1000}

for a in A:
    new_dp = defaultdict(lambda: -float('inf'))
    for stock, money in dp.items():
        new_dp[0] = max(new_dp[0], money + stock * a)
        new_dp[stock] = max(new_dp[stock], money)
        can_buy = money // a
        new_dp[stock + can_buy] = max(new_dp[stock+can_buy], money - can_buy * a)
    dp = new_dp
print(max(dp.values()))



Measured memory_bytes: 9452
#include<iostream>
using namespace std;
string s[2];int n;
main()
{
	cin>>n;cin>>s[0]>>s[1];
	long ans=1,M=1e9+7;int f=0;
	for(int i=0;i<n;i++)
	{
		if(s[0][i]==s[1][i])
		{
			if(f==0)ans=ans*3%M;
			else if(f==1)ans=ans*2%M;
			f=1;
		}
		else
		{
			if(f==0)ans=ans*6%M;
			else if(f==1)ans=ans*2%M;
			else if(f==2)ans=ans*3%M;
			i++,f=2;
		}
	}
	cout<<ans<<endl;
}

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

using namespace std;

int main() {
	int n;
	long long k;

	cin >> n;
	cin >> k;

	vector<int> a(n);

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

	vector<int> s;
	vector<int> ord(n + 1, -1);
	int c = 1, l = 0;
	{
		int v = 1;
		while (ord[v] == -1) {
			ord[v] = s.size();
			s.push_back(v);
			v = a[v - 1];
		}
		c = s.size() - ord[v];
		l = ord[v];
	}

	if (k < l)cout << s[k] << endl;
	else {
		k -= l;
		k %= c;
		cout << s[l + k] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 5868
import java.util.Scanner;

public class Main{
    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);

        while(true){
            int H = scan.nextInt();
            int M = scan.nextInt();

            if(H==0&&M==0){
                break;
            }

            while(H-- > 0){
                for(int i=0;i<M;i++){
                    System.out.print("#");
                }
                System.out.println();
            }

            System.out.println();

        }


    }
}


Measured memory_bytes: 38212
#include <stdio.h>

int main(void)
{
	int i, s, a;
	
	a = 0;
	
	for(s = 1; s <= 10; s++){
		scanf("%d", &i);
		a = a + i;
	}
	
	printf("%d\n",a);
	
	return 0;
}



Measured memory_bytes: 2052
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

/*
<url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0357>
?????????============================================================

 ????????§??????????????¨??¢??????????????´?????????????????´??????????????£???????????????
 ??¨????????????????????????????????????????????´???????¶????????????????????????????????????????????????????
 ???????????????????????´??????????????????????????????1000 ????????°??§??????
 
 ????????¨??¢??????????????£?????????????????????????????¨???????????????????????????????????????????????????????????°????????????????????????
 
 ?????????????????????????????£????????? a (1000 ??? a ??? 50000) ??¨??¢??????????????£????????? b (1000 ??? b ??? 50000) ?????????????????????
=================================================================

?§£??¬=============================================================
hai
================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll a,b; cin >> a >> b;
    cout << (a+b)/2 << endl;
	return 0;
}

Measured memory_bytes: 3160
from collections import Counter
N = int(input())

CL = []
for _ in range(N):
    s = [c for c in input()]
    s.sort()
    CL.append(''.join(s))

CL.sort()

num = 0
ans = 0
for i in range(1,N):
    if CL[i] == CL[i-1]:
        num += 1
    else:
        ans += num * (num + 1) // 2
        num = 0
ans += num * (num + 1) // 2

print(ans)


Measured memory_bytes: 10996
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

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

  ll lim = 1;
  for (int i = 0; i < 18; i++) {
    lim *= 10;
  }

  ll ans = 1;
  bool ok = true;
  for (int i = 0; i < n; i++) {
    if(ans == 0) {
      break;
    }

    if (a[i] > (lim / ans)) {
      ans = -1;
      ok = false;
    }

    ans *= a[i];
  }

  if (ans == 0) {
    cout << ans << ln;
  } else {
    cout << (ok ? ans : -1) << ln;
  }

  return 0;
}

Measured memory_bytes: 3984
#include<stdio.h>
int main(){
    int d;
    scanf("%d",&d);
    if(d==25)printf("Christmas\n");
    if(d==24)printf("Christmas Eve\n");
    if(d==23)printf("Christmas Eve Eve\n");
    if(d==22)printf("Christmas Eve Eve Eve\n");
    return 0;
}

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

long long a[1005][1005], n, k;
const long long mod = 1e9 + 7;

long long partit(long long nn, long long kk) {
    for (int i = 1; i <= nn; i++) a[i][0] = 0;
    for (int i = 0; i <= kk; i++) a[0][i] = 1;
    for (int i = 1; i <= nn; i++) {
        for (int j = 1; j <= kk; j++) {
            if (j <= i) a[i][j] = (a[i][j - 1] + a[i - j][j]) % mod;
            else a[i][j] = a[i][j - 1];
        }
    }
    return a[nn][kk];
}

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


Measured memory_bytes: 10944
import functools
from fractions import gcd
n,x =map(int,input().split())
if n==1:
    c = abs(int(input())-x)
    print(c)
else:
    lis = list(map(int,input().split()))
    for i in range(n):
        lis[i] = abs(lis[i]-x)
    print(functools.reduce(gcd,lis))

Measured memory_bytes: 16200
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include <cmath>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,C,K;
    cin >> N >> C >> K;
    int T[N];
    for(int i = 0; i < N; i++) {
        cin >> T[i];
    }
    sort(T,T + N);
    bool ok[N];
    for(int i = 0; i < N; i++) {
        ok[i] = false;
    }
    int ans = 0;
    for(int i = 0; i < N; i++) {
        if(ok[i]) continue;
        ans++;
        int t = T[i] + K;
        int cap = 0;
        int j = i;
        for(; j < N; j++) {
            if(T[j] > t || cap == C) break;
            if(!ok[j]) {
                cap++;
                ok[j] = true;
            }
        }
        i = j-1;
    }
    cout << ans << endl;

}





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

int main() {
  string sa[1000];
  int ia[1000] = {};

  int cnt = 0;
  string s, ss = "";
  while(cin >> s) {
    for(int i = 0; i < s.size(); i++) {
      if('A' <= s[i] && s[i] <= 'Z') s[i] += 'a'-'A';
    }

    int p = -1;
    for(int i = 0; i < cnt; i++) {
      if(sa[i] == s) p = i;
    }

    if(p != -1) ia[p]++;
    else {
      ia[cnt]++;
      sa[cnt++] = s;
    }

    if(s.size() > ss.size()) ss = s;
  }

  int f = -1;
  string fs;
  for(int i = 0; i < cnt; i++) {
    if(f < ia[i]) {
      fs = sa[i];
      f = ia[i];
    }
  }
  cout << fs << ' ' << ss << endl;
}

Measured memory_bytes: 1208
#include <iostream>
using namespace std;
int main(){
    long long int a,b,k,tmpk;
    cin >>a>>b>>k;
    tmpk=k;k-=a;
    if(k>0){a=0;}else{a-=tmpk;}
    if(k>0){
        tmpk=k;k-=b;
        if(k>0){b=0;}else{b-=tmpk;}
    }
    cout<<a<<" "<<b<<endl;
    
}


Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())
dx, dy = x2 - x1, y2 - y1
dx, dy = -dy, dx
x3, y3 = x2 + dx, y2 + dy
dx, dy = -dy, dx
x4, y4 = x3 + dx, y3 + dy
print(x3, y3, x4, y4)

Measured memory_bytes: 9128
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 8080
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD=1e9+7;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
int check(int now){
	int ret=0;
	while(now%2==0){
		now/=2;
		ret++;
	}
	return ret;
}

int main(){
	int N;
	cin>>N;
	vector<int> a(N);
	int cnt=0;
	for(int i=0;i<N;i++){
		cin>>a[i];
		cnt += check(a[i]);
	}
	cout<<cnt<<endl;
	
}




















Measured memory_bytes: 256
use std::io::stdin;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let int: i32 = buf.trim().parse().unwrap();

    println!("{}", solve(int));
}

fn solve(mut int: i32) -> i32{
    if int == 2 || int == 3 {
        return int;
    }
    if int == 4{
        return 5;
    }

    loop{
        if is_prime(int){
            return int;
        }

        int += 1;
    }
}

fn is_prime(num: i32) -> bool{
    for iter in 2..num/2 {
        if num % iter == 0{
            return false;
        }
    }
    true
}

Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <climits>
#include <unordered_map>
#include <functional>
#include <queue>

#define rep(i, n) for(int i = 0, end = (int)(n); i < end; i++)

#define p2(a, b) cout << a << "\t" << b << endl
#define p3(a, b, c) cout << a << "\t" << b << "\t" << c << endl

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

inline int ctoi(char c) {
    return (int)(c -'0');
}

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

typedef pair<ll, P> Input;

int main() {
    ll n;
    cin >> n;
    vector<Input> vec(n+1);
    vec[0].first = 0;
    vec[0].second.first = 0;
    vec[0].second.second = 0;
    rep(i, n) {
        Input& in = vec[i+1];
        cin >> in.first >> in.second.first >> in.second.second;
    }

    bool flag = true;
    rep(i, n) {
        Input before = vec[i];
        Input after = vec[i+1];
        ll d_t = after.first - before.first;
        ll d_x = abs(after.second.first - before.second.first);
        ll d_y = abs(after.second.second - before.second.second);
        ll d_d = d_x + d_y;
        if (d_t < d_d) {
            flag = false;
            break;
        }
        if ((d_d - d_t)%2 != 0) {
            flag = false;
            break;
        }
    }
    cout << (flag ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 2560
Max_even = 0
def evenserch(S):
    global Max_even
    # print(1)
    f=0
    if(len(S) == 0):
        return Max_even
    else:
        S.pop()
        if(len(S)%2 == 1):
            return evenserch(S)
        else:
            for i in range(int(len(S)/2)):
                # print(i)
                if(S[int(len(S)/2)+i]!=S[i]):
                    f = 1
                    break
            if(f==0):
                if(Max_even < len(S)):
                    Max_even = len(S)
            return evenserch(S)
def main():
    S = list(map(str,input()))
    k = evenserch(S)
    print(k)

if __name__ == '__main__':
    main()

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

using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
#define INF 1e9



int main(){
    ll a, b, k; cin >> a >> b >> k;
    
    ll t = min(a, k);
    a -= t;
    k -= t;
    b -= min(b,k);
    cout << a << endl;
    cout << b << endl;
    
    
   
    
}


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

using namespace std;

int v[100007];
int main() {
int n, k; cin >> n >> k;
vector<int> dp(n+1);
for(int i=1; i <= n; ++i) cin >> v[i];
dp[n] = 0;
for(int i = n-1; i >= 1; --i) {
    dp[i] = 0x3f3f3f3f;
    for(int j = 1; j <= k and i + j <= n; ++j)
        dp[i] = min(dp[i], dp[i+j] + abs(v[i+j] - v[i]));
}

cout << dp[1] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int N,Q;
const int INF=INT_MAX;
struct LazySegmentTree{
  private:
  int n;
  vector<int> node,lazy;
  vector<bool> lazyFlag;
  
  public:
  LazySegmentTree(vector<int> v){
    int sz=(int)v.size();
    n=1;  while(n<sz)n*=2;
    node.resize(2*n-1);
    lazy.resize(2*n-1,INF);
    lazyFlag.resize(2*n-1,false);
    for(int i=0;i<sz;i++)node[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--){node[i]=min(node[2*i+1],node[2*i+2]);}
  }
  void lazyEvaluate(int k,int l,int r){
    if(lazyFlag[k]){
      node[k]=lazy[k];
      if(r-l>1){
        lazy[2*k+1]=lazy[2*k+2]=lazy[k];
        lazyFlag[2*k+1]=lazyFlag[2*k+2]=true;
      }
      lazyFlag[k]=false;
    }
  }
  void update(int a,int b,int x,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    lazyEvaluate(k,l,r);
    if(b<=l || r<=a)return;
    if(a<=l && r<=b){
      lazy[k]=x;
      lazyFlag[k]=true;
      lazyEvaluate(k,l,r);
    }
    else{
      update(a,b,x,2*k+1,l,(l+r)/2);
      update(a,b,x,2*k+2,(l+r)/2,r);
      node[k]=min(node[2*k+1],node[2*k+2]);
    }
  }
  int find(int a,int b,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    lazyEvaluate(k,l,r);
    if(b<=l || r<=a)return INF;
    if(a<=l && r<=b)return node[k];
    int vl=find(a,b,2*k+1,l,(l+r)/2);
    int vr=find(a,b,2*k+2,(l+r)/2,r);
    return min(vl,vr);
  }
};

int main(){
  cin >> N >> Q;
  LazySegmentTree seg(vector<int>(N,INF));
  for(int i=0;i<Q;i++){
    int q; cin >> q;
    if(q==0){
      int s,t,x; cin >> s >> t >> x;
      seg.update(s,t+1,x);
    }
    else{
      int i; cin >> i;
      cout << seg.find(i,i+1) << endl;
    }
  }
}


Measured memory_bytes: 5168
#define r(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#include <bits/stdc++.h>
#include <cmath>
#include <fstream>
#define f first
#define endl "\n"
#define s second
#define pb push_back
#define ms(a,b) memset(a,b,sizeof(a))
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
typedef long long ll;
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
char _;
 
ll n,k;
ll nums[200001];
ll curMult = 1;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n>>k;
	for(ll i=0;i<n;i++)cin>>nums[i];

	for(int i=k;i<n;i++){
		if(nums[i] > nums[i-k]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 5200
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0
k,n=LI()
a=LI()
a+=[a[0]+k]
b=[a[i+1]-a[i] for i in range(n)]

ans=k-max(b)
print(ans)

Measured memory_bytes: 82724
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n, k; cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    sort(all(h));
    int ans = INF;
    rep(i, n-k+1) {
        ans = min(ans, h[i+k-1]-h[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


D_sum = defaultdict(list)
D_diff = defaultdict(list)
DX = defaultdict(list)
DY = defaultdict(list)
n = I()
L = []
ans = INF
for i in range(n):
    x, y, u = LS()
    x = int(x)
    y = int(y)
    D_sum[x + y] += [(x, u)]
    D_diff[x - y] += [(x, u)]
    if u in "UD":
        DX[x] += [(y, u)]
    else:
        DY[y] += [(x, u)]


for _, co_list in D_sum.items():
    co_list.sort()
    r = d = -INF
    for co, direction in co_list:
        if direction == "R":
            r = co
        elif direction == "D":
            d = co
        elif direction == "U":
            ans = min(co - r, ans)
        else:
            ans = min(co - d, ans)

for _, co_list in D_diff.items():
    co_list.sort()
    u = r = -INF
    for co, direction in co_list:
        if direction == "U":
            u = co
        elif direction == "R":
            r = co
        elif direction == "D":
            ans = min(co - r, ans)
        else:
            ans = min(co - u, ans)


for _, co_list in DX.items():
    co_list.sort()
    u = -INF
    for co, direction in co_list:
        coo = co
        if direction == "U":
            u = co
        else:
            ans = min((co - u) / 2, ans)


for _, co_list in DY.items():
    co_list.sort()
    r = -INF
    for co, direction in co_list:
        if direction == "R":
            r = co
        else:
            ans = min((co - r) / 2, ans)


if ans > 10 ** 8:
    print("SAFE")
else:
    print(int(ans * 10))







"""
L1 = []
L2 = []
L3 = []
L4 = []
for xk, yk ,u in L:
    L1 += [(xk - yk)]
    L2 += [(- xk - yk)]
    L3 += [(xk + yk)]
    L4 += [(- xk + yk)]

print(L1)
print(L2)
print(L3)
print(L4)

"""

Measured memory_bytes: 199488
<?php
define("MAX", 123456 * 2 + 1);

// sieve
for ($i = 0; $i < MAX; $i++) {
  $isPrime[] = 1;
}
$isPrime[0] = $isPrime[1] = 0;

for ($i = 2; $i < MAX; $i++) {
  if (!$isPrime[$i]) continue;
  $prime[] = $i;
  for ($j = 2 * $i; $j < MAX; $j += $i) {
    $isPrime[$j] = 0;
  }
}

while (fscanf(STDIN, "%d", $n) && $n) {
  $ans = 0;
  foreach ($prime as $p) {
    if ($n < $p && $p <= 2 * $n) $ans++;
  }
  print $ans . "\n";
}

Measured memory_bytes: 44512
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[21],n;
signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	int ans = 0;
	for(int i = 2 ; i < n ; i ++)
		if((a[i] > a[i-1] && a[i] < a[i + 1])||(a[i] < a[i-1] && a[i] > a[i + 1])) ans ++;
	cout << ans;
}

Measured memory_bytes: 256
import math

long, short, h, m = map(int, input().split())

a_long = (float(30) * h) + ((1 / 2) * m)
a_short = float(6 * m)

rad = math.radians(a_long - a_short)

# 長さを求める
length = math.sqrt(long ** 2 + short ** 2 - 2 * long * short * math.cos(rad))
print(length)

Measured memory_bytes: 9512
import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;

void main(){
    int N = readln().chomp().to!int();
    string[] prenums = readln().split();
    int[] nums;
    foreach(string s; prenums){ nums ~= s.to!int(); }
    nums.map!(a => to!string(a)).join(" ").writeln();
    for(int i = 1; i < N; i++){
        int key = nums[i];
        if(nums[i-1] > key){
            int j = i;
            do{
                nums[j] = nums[j-1];
                j--;
            }while(j > 0 && nums[j-1] > key);
            nums[j] = key;
        }
        nums.map!(a => to!string(a)).join(" ").writeln();
    }
}

Measured memory_bytes: 1808
while true
	
	aryMondai = gets.split.map(&:to_i);
	
	num1 = aryMondai[0];
	num2 = aryMondai[1];
	
	if num1 == 0 && num2 == 0 then
		break;
	end
	
	if num1 > num2 then
		puts num2.to_s + " " + num1.to_s;
	elsif num1 < num2 then
		puts num1.to_s + " " + num2.to_s;
	else
		puts num1.to_s + " " + num2.to_s;
	end
	
end

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

typedef struct{
  int m; //?????±?????\????????????????????§??????
  long L;
}guy;

int n;
guy g[100];

long dp[101][65537]; //2^16+1
//???x???????????¨??????????????????y????????±?????\????????¶?????§???????¶????????????§???
long rec(int x, int y){
  if(dp[x][y]>=0) return dp[x][y];

  if(x==n) return 0;

  long ret=0;

  //x??????????????±?????\????????¶?????¨????????¶???y?????????
  if((g[x].m & y)==0){
    //??????????????????????????????????????????????????????
    //x????????¨????????????????????????????????????????¨??????????
    ret = max( rec(x+1,y), rec(x+1,y|g[x].m)+g[x].L );
  }
  else ret = rec(x+1,y);

  return dp[x][y] = ret;
}

int main(){
  while (1) {
    //input
    cin >> n;
    if(n==0) break;
    for(int i=0; i<n; ++i){
      int p;
      cin >> p >> g[i].L;
      g[i].m=0;
      for(int j=0; j<p; ++j){
        int s,e;
        cin >> s >> e;
        for(int k=s; k<e; ++k) g[i].m += (1<<(k-6));
      }
    }

    //solve
    memset(dp, -1, sizeof(dp));
    cout << rec(0,0) << endl;
  }
}

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

const int inf = 1e9;
const ll linf = 1e18;

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

    int n; cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        s.insert(a);
    }
    cout << ((s.size() == n) ? "YES" : "NO") << endl;
    return 0;
}

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

int main(){
 int N;
 cin >> N;
 string X;
 int t[N];
 int i = 0;
 vector<string> a;
 string sss;
   getline(cin, sss);
for (i=0;i<N;i++){
string s;
 stringstream ss;
 getline(cin, s);
 ss << s;
 ss >> sss;
 ss >> t[i];
 a.push_back(sss);
}
cin >> X;
 string array;
 stringstream ss;
 int num;
 for (i=0;i<N;i++){
   if(a[i]==X)num=i;
   }
   int sum=0;
for(int j=num+1;j<N;j++){
    sum += t[j];
}
 cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int cnt=0;
string s;
int a[10];
int vis[10][10][10];

int main(){
  int N;
  cin>>N>>s;
 	memset(a,0,sizeof a);
  memset(vis,false,sizeof vis);
  for(int i=0;i<s.size();i++) a[s[i]-'0']++;
 
 	for(int i=0;i<=999;i++){
      int a=i/100,b=(i/10)%10,c=i%10;
      bool x=false,y=false,z=false;
      for(int i=0;i<s.size();i++){
        if(s[i]-'0'==a && !x) x=true;
        else if(s[i]-'0'==b && !y && x) y=true;
        else if(s[i]-'0'==c && !z && x && y) z=true;
      }
      if(x&&y&&z) cnt++;
    }
  cout<<cnt;
}

Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n, m;
  cin >> n >> m;

  if(m < 2*n){
    cout << m / 2 << endl;
    return 0;
  }

  m -= 2 * n;

  cout << m / 4 + n << endl;

  return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
ll n,k;
ll ans = 0;
cin >> n >> k;
for (ll b = 1; b <= n;b++){
    ans += max(0LL, b - k) * (n / b);
    ans += max(0LL, n % b - k + 1);
}
if (k == 0) ans -= n;
cout << ans << endl;
}


Measured memory_bytes: 256
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int ans = 1;
	for(int i=1;i<n;i++) {
		if(s[i] != s[i-1]) ans++;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
const long long MOD = 1e9+7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
//typedef boost::multiprecision::cpp_int bigint;

ll N, A, B, C;

vector<ll> L;

ll check(vector<ll> mark) {
	ll a = 0, b = 0, c = 0;
	ll ac = 0, bc = 0, cc = 0;
	ll sum = 0;
	for (ll n = 0; n < N; n++) {
		if (mark[n] == 0) {
			a += L[n];
			ac++;
		}
		else if (mark[n] == 1) {
			b += L[n];
			bc++;
		}
		else if(mark[n] == 2){
			c += L[n];
			cc++;
		}
	}
	if (ac == 0 || bc == 0 || cc == 0)return LLONG_MAX;
	sum += (ac+bc+cc-3)*10;
	sum += abs(a - A);
	sum += abs(b - B);
	sum += abs(c - C);
	return sum;
}

int main() {
	cin >> N >> A >> B >> C;
	L.resize(N);
	for (ll n = 0; n < N; n++)cin >> L[n];
	ll code = 4;
	for (ll n = 2; n <= N; n++)code *= 4;
	ll ans = LLONG_MAX;
	for (ll oldc = 0; oldc < code; oldc++) {
		vector<ll> ch(N, 0);
		ll c = oldc;
		for (ll n = 0; n < N; n++) {
			ch[n] = c % 4;
			c /= 4;
		}
		ans = min(ans, check(ch));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
List = []
for i in range (3):
  List.append(list(map(int, input().split())))
Row = int(input())
Ball = []
for i in range (Row):
  Ball.append(int(input()))
for x in range(Row):
  for i in range(3):
    for j in range(3):
      if Ball[x] == List[i][j]:
        List[i][j] = 0
if List[0][0] == 0 and List[0][1] == 0 and List[0][2] == 0:
  print("Yes")
elif List[1][0] == 0 and List[1][1] == 0 and List[1][2] == 0:
  print("Yes")
elif List[2][0] == 0 and List[2][1] == 0 and List[2][2] == 0:
  print("Yes")
elif List[0][0] == 0 and List[1][0] == 0 and List[2][0] == 0:
  print("Yes")
elif List[0][1] == 0 and List[1][1] == 0 and List[2][1] == 0:
  print("Yes")
elif List[0][2] == 0 and List[1][2] == 0 and List[2][2] == 0:
  print("Yes")
elif List[0][0] == 0 and List[1][1] == 0 and List[2][2] == 0:
  print("Yes")
elif List[0][2] == 0 and List[1][1] == 0 and List[2][0] == 0:
  print("Yes")
else:
  print("No")

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

int main(){
  int n,i,sum;
  cin >> n;
  vector<int> p(n);
  sum=0;
  for(i=0;i<n;++i){
    cin >> p[i];
  }
  for(i=1;i<n-1;++i){
    if(p[i-1] < p[i] && p[i+1] < p[i]){
      continue;
    }else if(p[i-1] > p[i] && p[i+1] > p[i]){
      continue;
    }else{
      sum=sum+1;
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
int main(){
    int N,D,ans=0;
    cin>>N>>D;
    int ma[N][D];
    REP(i,N)REP(y,D)cin>>ma[i][y];
    REP(i,N){
        for(int y=i+1;y<N;y++){
            float sum=0;
            REP(k,D)sum+=(ma[i][k]-ma[y][k])*(ma[i][k]-ma[y][k]);
            sum = sqrt(sum);
            if (ceil(sum) == floor(sum))ans++;
        }
    }
    cout<<ans<<endl;
}

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

#define ft first
#define sd second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> tri;

const int MAXN = 100 * 1000 + 123;



unordered_map<int, int> d[MAXN];
unordered_map<int, vector<int>> g[MAXN];
int n, m;

inline void inp();
inline void bfs();
inline bool upd(int&, const int);

int main() {
	inp();
	bfs();
	printf("-1");
	return 0;
}
inline void inp() {
	scanf("%d%d", &n, &m);
	int p, q, c;
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &p, &q, &c);
		g[--p][c].push_back(--q), g[q][c].push_back(p);
	}
}
inline bool upd(int &x, const int y) { return ((x == 0 || y < x)? x = y, true: false); }
inline void bfs() {
	deque<tri> deq;
	d[0][0] = 0;
	deq.push_back({{0, 0}, 0});
	while (!deq.empty()) {
		tri v = deq.front();
		deq.pop_front();
		if (v.sd != d[v.ft.ft][abs(v.ft.sd)])
			continue;
		if (v.ft.ft == n - 1) {
			printf("%d", v.sd);
			exit(0);
		}
		if (v.ft.sd) {
			if (upd(d[v.ft.ft][0], v.sd))
				deq.push_front({{v.ft.ft, 0}, v.sd});
			for (auto &u : g[v.ft.ft][v.ft.sd]) {
				if (upd(d[u][v.ft.sd], v.sd))
						deq.push_front({{u, v.ft.sd}, v.sd});
			}
		}
		else {
			for (auto &i : g[v.ft.ft])
				if (upd(d[v.ft.ft][i.ft], v.sd + 1))
					deq.push_back({{v.ft.ft, i.ft}, v.sd + 1});
		}
	}
}

Measured memory_bytes: 69376
N = int(input())
ans = 0

for i in range(1, N+1):
    if i % 3 == 0 and i % 5 == 0:
        ans += 0
    elif i % 3 == 0:
        ans += 0
    elif i % 5 == 0:
        ans += 0
    else:
        ans += i

print(ans)

Measured memory_bytes: 9180
n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
a.sort()
k=n//2
if n%2==1:
    ans_1 = 2*sum(a[k+1:]) - 2*sum(a[:k+1]) + a[k-1]+a[k]
    ans_2 = 2*sum(a[k:])   - 2*sum(a[:k])   -(a[k]+a[k+1])
    print(max(ans_1,ans_2))
else:
    ans = 2*sum(a[k:])   - 2*sum(a[:k]) -a[k]+a[k-1]
    print(ans)

Measured memory_bytes: 7472
from collections import defaultdict

max_phrases = defaultdict(int)
n = int(input())
for _ in range(n):
    s, l, p = map(int, input().split())
    for length in range(s, l + 1):
        max_phrases[length] = max(max_phrases[length], p)

m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + max(max_phrases))
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for length, p in max_phrases.items():
        dp[i + length] = max(dp[i + length], c + p)

results = [None] * m
for i, melody in enumerate(melodies):
    result = dp[melody]
    if result == -1:
        print(-1)
        break
    results[i] = result
else:
    print('\n'.join(map(str, results)))

Measured memory_bytes: 8152
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 18;
ll a[N + 1][N + 1];
char s[33];

pii read() {
	scanf("%s", s);
	ll x = 0;
	int L = strlen(s);
	int p = L;
	for (int i = 0; i < L; i++) {
		if (s[i] == '.') {
			p = i;
			continue;
		}
		x = 10 * x + (int)(s[i] - '0');
	}
	if (p == L)
		p = 9;
	else
		p = 9 - (L - p - 1);
	while(p--) x *= 10;
	if (x == 0) return mp(N, N);
	int y = 0, z = 0;
	while(x % 2 == 0) {
		y++;
		x /= 2;
	}
	while(x % 5 == 0) {
		z++;
		x /= 5;
	}
	return mp(y, z);
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	int n;
	scanf("%d", &n);
	while(n--) {
		pii t = read();
		a[min(N, t.first)][min(N, t.second)]++;
	}
	ll ans = 0;
	for (int i = 0; i <= N; i++)
		for (int j = 0; j <= N; j++)
			for (int p = 0; p <= N; p++)
				for (int q = 0; q <= N; q++) {
					if (i + p < N || j + q < N) continue;
					if (mp(i, j) > mp(p, q)) continue;
					if (mp(i, j) == mp(p, q))
						ans += a[i][j] * (a[i][j] - 1) / 2;
					else
						ans += a[i][j] * a[p][q];
				}
	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 3228
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    #[allow(unused_mut)]
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    n: usize,
    aa: [usize; n]
  }
  let mut dp = vec![vec![vec![0.0; n+1]; n+1]; n+1];
  let mut pop = vec![0usize; 4];
  for &a in aa.iter() {
    pop[a] += 1;
  }
  let total_sushi: usize = aa.iter().sum();
  dp[pop[1]][pop[2]][pop[3]] = 1.0;
  for three in (0..n+1).rev() {
    for two in (0..n+1).rev() {
      for one in (0..n+1).rev() {
        let dish = (one + two + three) as f64;
        if three > 0 && two + 1 <= n {
          dp[one][two+1][three-1] += dp[one][two][three] * (three as f64) / dish;
        }
        if two > 0 && one + 1 <= n {
          dp[one+1][two-1][three] += dp[one][two][three] * (two as f64) / dish;
        }
        if one > 0 {
          dp[one-1][two][three] += dp[one][two][three] * (one as f64) / dish;
        }
      }
    }
  }
  let mut ans = 0.0;
  for sushi in (1..total_sushi+1).rev() {
    for three in 0..(sushi / 3 + 1) {
      for two in 0..((sushi - three * 3) / 2 + 1) {
        let one = sushi - three * 3 - two * 2;
        if two > n || one > n {
          continue;
        }
        ans += dp[one][two][three] * n as f64 / (one + two + three) as f64;
      }
    }
  }
  println!("{:.15}", ans);
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int64 gcd(int64 a, int64 b){
    if(b == 0)return a;
    return gcd(b, a % b);
}

int64 lcm(int64 a, int64 b){
    return a / gcd(a, b) * b;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int64 n,m;
    cin >> n >> m;
    vector<int64> a(n);
    REP(i,n)cin >> a[i];

    int64 l = a[0] / 2;
    FOR(i,1,n)l = lcm(l, a[i] / 2);
    // cout << l << endl;

    int64 cnt = 0;
    while(a[0] % 2 == 0){
        cnt++;
        a[0] /= 2;
    }
    FOR(i,1,n){
        int64 cnt2 = 0;
        while(a[i] % 2 == 0){
            cnt2++;
            a[i] /= 2;
        }
        if(cnt != cnt2){
            cout << 0 << endl;
            return 0;
        }
    }
    
    // cout << (m + l) / l / 2 << endl;
    cout << m / l - m / (l * 2) << endl;
    return 0;
}

Measured memory_bytes: 1024
/* BISMILLAHIR RAHMANIR RAHIM */
#include<bits/stdc++.h>
#define PI             acos(-1.0)
#define IOS            ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ms(a,b)         memset(a, b, sizeof(a))
#define filein      freopen("input.txt", "r", stdin);
#define fileout     freopen("output.txt", "w", stdout);
#define debug       cout<<"Hello, i am in here."<<endl;
#define bit_cnt(mask) __builtin_popcountll(mask)
#define ll long long int
#define dst(u,v,x,y) sqrt((x*1.0-u*1.0)*(x*1.0-u*1.0)+(y*1.0-v*1.0)*(y*1.0-v*1.0))
using namespace std;
const int MOD = (int)1e9+7;
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
void solve()
{
     ll n,m,x;
   vector<ll>vs1,vs2;
   cin>>n>>m>>x;
   for(int i=0;i<n;i++)
   {
       ll a;
       cin>>a;
       vs1.push_back(a);
   }
   for(int i=0;i<m;i++)
   {
       ll a;
       cin>>a;
       vs2.push_back(a);
   }
   ll sum=0;
   ll Count=0;
   ll i=0,j=0;
   while(i<n&&sum+vs1[i]<=x)
   {
        sum+=vs1[i];
        i++;
   }
   Count=i;
   j=0;
   while(j<m && i>=0)
   {
       sum+=vs2[j];
       j++;
       while(sum>x && i>=0)
       {
         i--;
         sum-=vs1[i];
       }
       if(sum<=x && i+j>Count)
       {
           Count=i+j;
       }
   }
   cout<<Count<<endl;
}
int  main()
{
    IOS
    solve();
    return 0;
}


Measured memory_bytes: 7952
N,P = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

is_include_odd = False
for k in A:
  if k % 2 == 1:
    is_include_odd = True
    
if is_include_odd:
  print(pow(2,N-1))
else:
  if P == 0:
    print(pow(2,N))
  else:
    print(0)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

void ABC140A()
{
	int n;
	cin >> n;
	ll x = n * n * n;
	cout << x << endl;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

void solve(long long N, vector<long long> A){
	ll sum = 0, no0 = 0, x0 = 0;
	rep(i, N) {
		sum += A[i];
		if (i % 2 == 1) no0 += A[i];
	}
	no0 *= 2;
	x0 = sum - no0;
	ll xi = x0;
	cout << x0;
	rep(i, N-1) {
		xi = (A[i]*2-xi);
		cout << " " << xi;
	}
	cout << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
	}
	solve(N, A);
	return 0;
}



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

using namespace std;

typedef long long ll;


int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  int s = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        int x = a[i], y = a[j], z = a[k];
        if (x == y || x == z || y == z) continue;
        vector<int> e = {x, y, z};
        sort(e.begin(), e.end());
        if (e[0] + e[1] > e[2]) s++;
      }
    }
  }
  cout << s << "\n";
  return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <climits>
#include <vector>
#include <numeric>
#include <complex>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
using namespace std;

#define __int64 long long
#define long __int64
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
const int Vec = 4;
const int Vecy[Vec] = {0,-1,0,1};
const int Vecx[Vec] = {1,0,-1,0};
const int Modd = 1000000007;

int d[100];

int main(){
    int n;
    cin >> n;
    rep(i,n){
        cin >> d[i];
    }

    sort(d, d+n, greater<int>());

    int ans = 1;
    REP(i,1,n){
        if(d[i] != d[i-1]) ans ++;
    }

    cout << ans << endl;


}

Measured memory_bytes: 256
// E - Red and Green Apples
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define allr(x) (x).rbegin(),(x).rend()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
int X,Y,A,B,C;
vi P,Q,R;

ll solve(){
	sort(allr(P));
	sort(allr(Q));
	priority_queue<int> T, S;
	rp(i, 0, X) T.push(P[i]);
	rp(i, 0, Y) T.push(Q[i]);
	rp(i, 0, C) S.push(R[i]);
	ll ans = 0;
	while(T.size()){
		int t = T.top(); T.pop();
		int s = S.top(); S.pop();
		if(t>s){
			S.push(s); ans += t;
		}
		else{
			S.push(t);
			ans += s;
		}
	}
	return ans;
}

int main(){
	cin>>X>>Y>>A>>B>>C;
	P.resize(A); rp(i, 0, A) cin>>P[i];
	Q.resize(B); rp(i, 0, B) cin>>Q[i];
	R.resize(C); rp(i, 0, C) cin>>R[i];
	cout<< solve() <<endl;
}

Measured memory_bytes: 3060