akhauriyash/Code-Regression huggingface dataset:
// D - Powerful Discount Tickets
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,n) for(int i=0;i<(n);i++)
#define allr(x) (x).rbegin(),(x).rend()

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

	vector<int> A(N);
	vector<pair<int,int>> B;
	rp(i,N){
		int a; cin>>a;
		A[i] = a;
		while(a>0){
			B.push_back(make_pair(a - (a>>1), i));
			a>>=1;
		}
	}

	sort(allr(B));

	map<int,int> counting;
	rp(i,N) counting[i] = 0;

	int e = min(M, (int)B.size());
	rp(i, e) counting[B[i].second]++;

	ll ans = 0;
	rp(i,N) ans += (ll)A[i]/(1<<counting[i]);
	cout<< ans <<endl;
}

Measured memory_bytes: 35172
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        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 adjacent4(x: usize, y: usize, sx: usize, sy: usize) -> Vec<(usize, usize)> {
    [(-1, 0), (1, 0), (0, -1), (0, 1)]
        .into_iter()
        .filter_map(|&(dx, dy)| {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx >= 0 && nx < sx as isize && ny >= 0 && ny < sy as isize {
                Some((nx as usize, ny as usize))
            } else {
                None
            }
        })
        .collect()
}

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
fn main() {
    input! {
        h: u64,
        w: u64,
    }
    // マスの目はh * w
    if h == 1 || w == 1 {
        println!("{}", 1);
    } else {
        println!("{}", (h * w + 1) / 2);
    }
}


Measured memory_bytes: 4352
import bisect
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
T = input()[:-1]

# 作れない場合
if any(t not in S for t in T):
    print(-1)
    exit()


D = defaultdict(lambda: [])
min_D = defaultdict(lambda: len(S)+1)
for i, s in enumerate(S):
    D[s].append(i)
    min_D[s] = min(i, min_D[s])

for s in D.keys():
    D[s] = sorted(D[s])

cur_pos = 0
repeat = 0
for t in T:
    #print("cur->", cur_pos)
    ind = bisect.bisect_left(D[t], cur_pos)
    if ind >= len(D[t]):
        repeat += 1
        cur_pos = min_D[t]+1
    else:
        cur_pos = D[t][ind]+1

print(len(S)*repeat+cur_pos)


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

using namespace std;
using ll = long long;
using ld = long double;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a, b) a = min((a),(b))
#define CHMAX(a, b) a = max((a),(b))
#define ZP(a, len) cout << setfill('0') << setw(len) << right << a << endl;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main() {
    string s;
    cin >> s;

    ll ans = 0;
    rep(bit, 1 << s.length() - 1) {
        ll sum = s[0] - '0';
        rep(i, s.length() - 1) {
            if (bit & (1 << i)) {
                ans += sum;
                sum = s[i + 1] - '0';
            } else {
                sum *= 10;
                sum += s[i + 1] - '0';
            }
        }
        ans += sum;
    }
    cout << ans << endl;
    return 0;
}

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

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

using namespace std;
using ll = long long;

int main(void)
{
  int n, x, t;
  cin >> n >> x >> t;
  cout << (n / x + ((n % x) == 0 ? 0 : 1)) * t << endl;
}

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

using namespace std;

using ll = long long;

int main(int argc, const char *argv[]) {
  int n, k;
  cin >> n >> k;

  vector<ll> vx(n), vy(n);
  vector<pair<ll, ll>> coords(n);
  for (int i = 0; i < n; i++) {
    cin >> vx[i] >> vy[i];
    coords[i].first = vx[i];
    coords[i].second = vy[i];
  }

  auto count_coords = [&](ll x1, ll x2, ll y1, ll y2) {
    return count_if(coords.begin(), coords.end(), [&](auto &c) {
      return x1 <= c.first && c.first <= x2 && y1 <= c.second && y2 >= c.second;
    });
  };

  sort(vx.begin(), vx.end());
  sort(vy.begin(), vy.end());

  ll ans = -1;
  for (int b = 0; b < n; ++b) {
    for (int t = b; t < n; ++t) {
      for (int l = 0; l < n; ++l) {
        for (int r = l; r < n; ++r) {
          ll dy = vy[t] - vy[b], dx = vx[r] - vx[l];
          ll cnt = count_coords(vx[l], vx[r], vy[b], vy[t]);
          if (cnt < k) {
            continue;
          }

          ll area = dy * dx;
          ans = ans < 0 ? area : min(ans, area);
        }
      }
    }
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#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 rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class T> using vt=vector<T>;
template<class T> using vvt=vt<vt<T>>;
template<class TA,class TB> void chmax(TA&a,TB b){if(a<b)a=b;}
template<class TA,class TB> void chmin(TA&a,TB b){if(b<a)a=b;}
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
	return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vt<T>& v){
	os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
template<class T> void make_unique(vt<T>& v) {
	sort(all(v));v.erase(unique(all(v)),v.end());
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int ri(){int x;cin>>x;return x;}
ll rll(){ll x;cin>>x;return x;}
vi rvi(int n){vi v;rep(i,n)v.pb(ri());return v;}
int n,a[200010];
void MAIN() {
	cin>>n;
	rng(i,1,n)cin>>a[i];
	map<int,int> mp;
	ll cnt=0;
	rng(i,1,n) {
		cnt+=mp[i-a[i]];
		mp[i+a[i]]=mp[i+a[i]]+1;
	}
	// i-j=a[i]+a[j]
	// i-a[i]=j+a[j]
	cout<<cnt;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	//cin>>T;
	for(int tt=1;tt<=T;tt++) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 21408
using System;
using System.Collections.Generic;
using System.Linq;

public class AtCoderB
{
    static void Main()
    {
        long h;
        long w;
        {
            var line = Console.ReadLine();
            var words = line.Split(' ');
            h = long.Parse(words[0]);
            w = long.Parse(words[1]);
        }

        long answer = (h * w + 1) / 2;

        if (w == 1 || h == 1)
        {
            answer = 1;
        }

        Console.WriteLine(answer);
    }
}

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

int main() {
  vector<bool>data(100001,true);
  vector<int>sum(100001);
  data[0] = false;data[1] = false;
  for(int i = 2;i < 100001;i++){
    if(data[i]){
      for(int j = 2*i;j < 100001;j += i){
        data[j] = false;
      }
    }
  }
  sum[0] = 0;
  for(int i = 1;i < 100001;i++){
    int k = (i+1)/2;
    if(data[i]&&data[k]){
      sum[i] = sum[i-1]+1;
    }
    else{
      sum[i] = sum[i-1];
    }
  }
  int n;
  cin >> n;
  for(int i = 0;i < n;i++){
    int l,r;
    cin >> l >> r;
    cout << sum[r]-sum[l-1] << endl;
  }
}


Measured memory_bytes: 1024
A,B,C = map(int, input().split())
A_first,B_first,C_first = A,B,C

result = 0
for i in range(10**9):
    if A % 2 == 1 or B % 2 == 1 or C % 2 == 1:
        break
    a = A // 2
    b = B // 2
    c = C // 2
    A = b + c
    B = a + c
    C = a + b
    if A == A_first and B == B_first and C == C_first:
        result = -1
        break
    result += 1   
print(result)    

Measured memory_bytes: 9100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int pre[100005];
int main()
{

   	  	int n , m ;
   	cin >> n >> m ;
   	map< int , int > mp;
   	for(int i = 0 ; i < n ; i++){
		int k;
      	cin >> k;
      	for(int i = 0 ; i < k ; i++){
			int x;
          	cin >> x;
          	mp[x]++;
        }
    }
   	int ans = 0;
   	for(auto x : mp){
		if(x.second == n)
          ans++;
    }
   	cout << ans << endl;
  	return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>

using namespace std;

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

long long int INF = 1e18;
long long int mod = 1000000007;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "RULD";
//↓,→,↑,←

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,n) for(i=0;i<n;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl

ll rui(ll number1,ll number2){
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
    if(number1 > number2){
        swap(number1 , number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1 , number1);
    }
}

ll i,j,k,ii,jj;
ll n,m;
ll a,b,c,d,e,g,h,r,w;
ll l,ans,sum;
ll num;
ll x[500005],y[500005],z[500005];
bool dame,flag,ok;

int main(){
	cin >> k >> a >> b;
	if(a >= k){
		p(1);
	}else if(a <= b){
		p(-1);
	}else{
		k -= a;
		ans = (k + a - b - 1) / (a - b);
		ans *= 2;
		ans ++;
		p(ans);
	}
    return 0;
}

Measured memory_bytes: 25216
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = Integer.parseInt(sc.next());
		int W = Integer.parseInt(sc.next());
		String[][] a =new  String[H + 2][W + 2];
		for(int i = 0; i < W + 2; i++) {
			a[0][i] = "#";
		}
		System.out.println();
		for(int i = 1; i < H + 1; i++) {
			String tmp = sc.next();
			a[i][0] = "#";
			for(int j = 1; j < W + 1; j++) {
				a[i][j] = tmp.substring(j - 1, j);;
			}
			a[i][W + 1] = "#";
		}
		for(int i = 0; i < W + 2; i++) {
			a[H + 1][i] = "#";
		}
		sc.close();

		for(int i = 0; i < H + 2; i++) {
			for(int j = 0; j < W + 2; j++) {
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}

}

Measured memory_bytes: 24880
#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;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define N 200001
#define ll long long
#define int ll 
#define pi pair<int , int>
#define pip pair<pair ,int>
#define mp make_pair 
#define f first
#define s second
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
int* getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
	  lps[i] = j+1;
   i++;
   j++;
  }
  else{
		if(j != 0){
		 j = lps[j-1];
		}
		else{
		 lps[i] = 0;
		 i++;
		}
  }
 }
 return lps;
}
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return ans.x;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string str1 , str2;
cin>>str1>>str2;
int a , b;
cin>>a>>b;
string x;
cin>>x;
if(x == str1){
 cout<<--a <<" "<<b<<endl;
 return 0;
}
cout<<a<<" "<<--b<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		String ground = scan.next();
		int[] height = new int[ground.length()+1];
		height[0] = 0;
		int now = 0;
		int[] valley = new int[(ground.length()/2)+1];
		int status = 0;
		int j = 0;
		int cnt = 0;
		for(int i = 0; i < ground.length(); i++){
			char c = ground.charAt(i);
			switch(c){
			case '\\':
				if(cnt == 0){
					valley[j] = i;
					status = -(i + 1);
					j++;
					cnt++;
				}else if(status > 0){
					if(j != 0){
						if(height[valley[j - 1]] < now && j > 1){
							int k = j - 2;
							int max = height[valley[j - 1]];
							int maxk = j - 1;
							while(k >= 0){
								if(height[valley[k]] > max){
									max = height[valley[k]];
									maxk = k;
									if(max >= now){
										break;
									}
								}
								k--;
							}
							valley[maxk + 1] = status;
							j = maxk + 2;
						}else{
							valley[j] = status;
							j++;
						}
						status = -(i + 1);
					}else{
						valley[j] = status;
						status = -(i + 1);
						j++;
					}
				}
				now--;
				height[i+1] = now;
				break;
				case '/':
				if(cnt == 0){
					status = i + 1;
					cnt++;
				}else if(i == ground.length() - 1 && j != 0){
					if(height[valley[j - 1]] < now + 1 && j > 1){
						int k = j - 2;
						int max = height[valley[j - 1]];
						int maxk = j - 1;
						while(k >= 0){
							if(height[valley[k]] > max){
								max = height[valley[k]];
								maxk = k;
								if(max >= now){
									break;
								}
							}
							k--;
						}
						valley[maxk + 1] = i + 1;
						j = maxk + 2;
					}else{
						valley[j] = i + 1;
						j++;
					}
					status = i + 1;
				}else{
					status = i + 1;
				}
				now++;
				height[i+1] = now;
				break;
				case '_':
				if(i == ground.length() - 1 && status > 0 && j > 0){
					if(height[valley[j - 1]] < now && j > 1){
						int k = j - 2;
						int max = height[valley[j - 1]];
						int maxk = j - 1;
						while(k >= 0){
							if(height[valley[k]] > max){
								max = height[valley[k]];
								maxk = k;
								if(max >= now){
									break;
								}
							}
							k--;
						}
						valley[maxk + 1] = status;
						j = maxk + 2;
					}else{
						valley[j] = status;
						j++;
					}
				}
				height[i+1] = now;
				break;
			}
		}
		
		int A = 0;
		int k = 0;
		if(j > 1){
			k = j - 1;
			int[] L = new int[k];
			for(int i = 0; i < k; i++){
				L[i] = 0;
			}
			int lower;
			int i = 1;
			while(i < j){
				if(height[valley[i - 1]] > height[valley[i]]){
					lower = height[valley[i]];
				}else{
					lower = height[valley[i - 1]];
				}
				
				for(int l = valley[i - 1]; l < valley[i]; l++){
					if(height[l] >= lower && height[l + 1] >= lower){
						continue;
					}else{
						L[i - 1] += ((lower - height[l]) + (lower - height[l + 1]));
					}
				}
				L[i - 1] /= 2;
				A += L[i - 1];
				i++;
			}
			
			System.out.println(A);
			System.out.print(k);
			for( i = 0; i < k; i++){
				System.out.print(" "+L[i]);
			}
			System.out.println("");
		}else{
			System.out.println(A);
			System.out.println(k);
		}
	}
}


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

int main(){
  long long N;
  cin >> N;
  int happy = 0;
  
  while(N >= 500){
    happy += 1000;
    N -= 500;
  }
  while(N  >= 5){
    happy += 5;
    N -=5;
  }
  cout << happy << endl;
}


Measured memory_bytes: 256
/*******************************
 Author: i_o__o_i
 Created: Friday 2020-04-10
********************************/
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimization("Ofast")

using namespace std;
using namespace __gnu_pbds;

typedef     long long   ll;

#define     CS(x) cout << "Case " << x << ": ";
#define     _test int TC; cin >> TC; while(TC--)
#define     sq(x) ((x) * 1LL * (x))
#define     eb emplace_back
#define     pb push_back
#define     all(_n) _n.begin(), _n.end()
#define     rall(_n) _n.rbegin(), _n.rend()
#define     Clear(a, b) memset(a, b, sizeof(a))
#define     sp << ' ' <<
#define     endl "\n"
#define     nl cout << endl
#define     D(x) cout << #x << " >>>>>> " << x << endl;
#define     D2(x, y) cout << #x << " >>> " << x << " # " << #y << " >>> " << y << endl;
#define     DD cout << "--\n";
#define     dbg cout << "!!ERROR ERROR ERROR!!" << endl;
#define     show(x) cout << x << endl
#define     precision(n) cout << fixed << setprecision(n);
#define     exeTime(fun){clock_t start, end; start = clock(); fun; end = clock(); double time_taken = double(end - start) / double(CLOCKS_PER_SEC); cout << "Execution time: " << time_taken << " secs."; }
#define     F first
#define     S second
#define     mini(a, b) a = min(a, b)
#define     maxi(a, b) a = max(a, b)
#define     sz(x) int( x.size() )
#define     gcd(a, b) __gcd(a, b)
#define     lcm(a, b) (abs((a) * (b)) / gcd(a, b))
#define     getbit(n, i) (((n) & (1LL << i)) != 0)
#define     setbit0(n, i) ((n) & (~(1LL << i)))
#define     setbit1(n, i) ((n) | (1LL << i))
#define     kbits(n, k) ((n) & ((1LL << k) - 1))
#define     LSB(n) ((n) & (-(n)))
#define     MSB(n) (1LL << (int)log2(n))
#define     isPowOf2(n) ((n > 0) && (((n) & (n-1)) == 0))
#define     parity(a, b) (a&1 ^ b&1)
#define     cond(__C, __R1, __R2) (__C ? __R1 : __R2)

inline bool _equal(double a, double b) { return fabs(a-b) < 1e-9; }
template<typename T> void print (T t){ for(const auto &it : t) cout << it << ' '; nl; }
template<class T> inline T min(T a, T b, T c){ return min(min(a, b), c); }
template<class T> inline T max(T a, T b, T c){ return max(max(a, b), c); }
template <typename T>  using orderedSet = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key find_by_order

//mt19937 mrand(random_device{}());
//int rnd(int x) { return mrand() % x;}

const    double Pi = acos(-1.0);
const    int Mod = 1e9 + 7;
const    int Eps = 1e-9;
const    int Inf = 1 << 30;
const    int Maxx = 1e5 + 10;

/******************************[Code Starts Here]********************************/

void _case()
{
    queue<ll> q;
    for(int i = 1; i <10; i++) q.push(i);
    int k; cin >> k;
    while(k-->1) {
        ll x = q.front();
        q.pop();
        if(x%10 != 0) q.push(10*x + x%10 -1);
        q.push(10*x + x%10);
        if(x%10 != 9) q.push(10*x + x%10 + 1);
    }
    show(q.front());
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    _case();
    return 0;
}




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

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    vector<int> vi(n+1,0);
    vector<int> dp(n+1,0);
    for (int i = 1; i <= n; i++) {
        cin >> vi[i];
    }
    dp[2] = abs(vi[2]-vi[1]);
    for (int i = 3; i <=n; i++) {
        dp[i] = min(dp[i-1] + abs(vi[i-1] - vi[i]), dp[i-2] + abs(vi[i] - vi[i-2]));
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
    int N,D,k=0,v;
    cin>>N>>D;
    k=2*D+1;
    if(N%k==0)
    {
        v=N/k;
    }
    else
    {
        v=N/k+1;
    }
    cout<<v;
    return 0;
}


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

using namespace std;

int main() {
    string s; cin >> s;
    long int sum = 0;
    for(int i = 0; i < (1 << s.length()-1); ++i) {
        long int num = s[0] - '0';
        for(int j = 0; j < s.length()-1; ++j) {
            if((1 & i >> j) == 1) {
                sum += num;
                num = 0;
            }
            num = num * 10 + s[j+1] - '0';
        }
        sum += num;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int r,c,i,j;
  static int s[101][101];

  scanf("%d%d",&r,&c);

  for(i=0;i<=r;i++){
    for(j=0;j<c;j++){
      scanf("%d", &s[i][j]);
      printf("%d ", s[i][j]);
      s[i][c] += s[i][j];
      s[r][j] += s[i][j];
    }
    printf("%d\n",s[i][c]);
  }

  return 0;
}


Measured memory_bytes: 2128
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>
// #include <fstream>
#define typeof(x) __typeof__(x)
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define SIZE(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) (int)(UB(c,x)-LB(c,x))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

using namespace std;

typedef pair<int,int> P;
struct edge {
  int to, cost;
};

const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " ";
  }
  return s;
}


signed main()
{
  // string filename; cin >> filename;
  // ifstream in(filename);
  // cin.rdbuf(in.rdbuf());

  int H, W; cin >> H >> W;
  int N; cin >> N;
  vector<int> a(N);
  rep(i, 0, N) {
    cin >> a[i];
  }

  vector<int> x;
  rep(i, 0, N) {
    rep(j, 0, a[i]) {
      x.push_back(i+1);
    }
  }

  int idx = 0;
  vector< vector<int> > c(H, vector<int>(W));
  rep(i, 0, H) {
    if (i % 2 == 0) {
      rep(j, 0, W) {
        c[i][j] = x[idx++];
      }
    } else {
      rrep(j, 0, W) {
        c[i][j] = x[idx++];
      }
    }
  }

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


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll INF=1e18;


// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(100005);


//nPk
 mint f(int n, int k) {
    if (n < 0) return 0;
    // nPk = nCk * k!
    mint res = comb(n,k);
    res *= comb.fact[k];
    return res;
}




//組み合わせの数nCrを計算
   int calcNumOfCombination(int n, int r){
       int num = 1;
       for(int i = 1; i <= r; i++){
           num = num * (n - i + 1) / i;
       }
       return num;
   }


vector <vector<ll>> g(100005);
mint ans;
ll n,k;


void dfs(ll t, ll p, ll d){
  ll m=g[t].size();
  if (d>0) ans*=f(k-2, m-1);
  if(d==0) ans*=f(k-1, m);
//  cout<<comb(k-1, m)<<'m'<<m<<'t'<<t<<'a'<<ans<<endl;
  for(ll to:g[t]){
    if (to==p)continue;
    dfs(to,t,d+1);
  }
}

int main() {
  cin >> n>> k;
  rep(i,n-1){
    ll a1,b1;
    cin>>a1>>b1;
    a1--;b1--;
    g[a1].push_back(b1);
    g[b1].push_back(a1);

  }
ans=1;
dfs(0,-1,0);
ans*=k;
cout<<ans;



}



Measured memory_bytes: 13812
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.insert(0, -1)
a.append(n+1)
a = [a[i+1] - a[i] - 2 for i in range(m+1)]
count = 1
if not -1 in a:
  for i in a:
    a_0 = 1
    a_1 = 1
    ans = 1
    for _ in range(i-1):
      ans = a_0 + a_1
      a_0 = a_1
      a_1 = ans
    count *= ans
  print(count % 1000000007)
else: print(0)

Measured memory_bytes: 7832
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args)throws Exception{
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int A[][]=new int[N][2];
		for(int i=0;i<N;i++){
			int b=stdIn.nextInt();
			A[i][0]=b;
			A[i][1]=i+1;
		}
		Arrays.sort(A, (a, b) -> Long.compare(a[0], b[0]));
		for(int i=0;i<N;i++){
			System.out.println(A[i][1]);
		}
	}
}


Measured memory_bytes: 67604
#include<stdio.h>

int b[15][15];

void reset(){
    int i,j;
    for(i=0;i<15;i++){
        for(j=0;j<15;j++){
            b[i][j]=0;
        }
    }
}

void magic_square(int x,int y,int n,int c){
    if(c==n*n)return;
    if(b[x][y]==0){
        b[x][y]=++c;
        if(++x==n)x=0;
        if(++y==n)y=0;
        magic_square(x,y,n,c);
    }else{
        if(++x==n)x=0;
        if(--y==-1)y=n-1;
        magic_square(x,y,n,c);
    }
}

int main(){
    int n,i,j;
    while(scanf("%d",&n),n){
        reset();
        magic_square(n/2+1,n/2,n,0);
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(j<n-1)printf("%4d",b[i][j]);
                else printf("%4d\n",b[i][j]);
            }
        }
    }
    return 0;
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1e15;
const ll MOD = 1e9 + 7;

ll n, m;
vector<ll> a(1e5), s(1e5 + 1);

bool check(ll x) {
  ll cnt = 0;
  REPR(i, n - 1) {
    auto it = lower_bound(ALL(a), x - a[i]);
    cnt += a.end() - it;
  }
  return cnt >= m;
}

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

  REP(i, n) cin >> a[i];
  a.resize(n);
  sort(ALL(a));

  s[0] = 0;
  REP(i, n) s[i + 1] = s[i] + a[i];
  s.resize(n + 1);

  ll lb = 1, ub = 1e6;
  while (ub - lb > 1) {
    ll mid = (lb + ub) / 2;
    if (check(mid))
      lb = mid;
    else
      ub = mid;
  }

  ll ans = 0, tmp = 0;
  REPR(i, n - 1) {
    auto it = lower_bound(ALL(a), lb + 1 - a[i]);
    ll x = a.end() - it;
    tmp += x;
    ans += x * a[i] + s[n] - s[n - x];
  }
  ll diff = m - tmp;
  ans += diff * lb;

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

Measured memory_bytes: 1920
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.run();
    }
    
    // 変数一覧
    long x;
    long y500;
    long y5;

    public void run() {
        // 入力情報取得
        Scanner sc = new Scanner(System.in);
        x = sc.nextLong();
        sc.close();

        // 解答処理
        solve();
    }
    
    private void solve() {
        y500 = x / 500;
        x = x % 500;
        y5 = x / 5;
        long res = y500 * 1000 + y5 * 5;
        System.out.println(res);
    }
}

Measured memory_bytes: 21972
#include <iostream>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

typedef long long ll;

#include <set>
using namespace std;

ll dp[1000][1000];
ll d[1000][1000];

const int mod = 100000007;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int main(){
  const int w = getInt();
  const int h = getInt();
  const int sx = getInt();
  const int sy = getInt();
  const int gx = getInt();
  const int gy = getInt();

  queue<pair<int, int> > q;

  REP(i,h) REP(j,w){
    dp[i][j] = 0;
    d[i][j] = -1;
  }

  d[sy][sx] = 0;
  dp[sy][sx] = 1;
  q.push(make_pair(sx, sy));
  while(q.size()){
    const int x = q.front().first;
    const int y = q.front().second;
    q.pop();

    REP(i,4){
      const int xx = (x + _dx[i] + w) % w;
      const int yy = (y + _dy[i] + h) % h;

      if(d[yy][xx] == -1){
	d[yy][xx] = d[y][x] + 1;
	q.push(make_pair(xx, yy));
      }

      if(d[yy][xx] == d[y][x] + 1){
	dp[yy][xx] += dp[y][x];
	dp[yy][xx] %= mod;
      }
    }
  }

  cout << dp[gy][gx] << endl;

  return 0;
}

Measured memory_bytes: 16876
#include<iostream>
#include<vector>
#include<algorithm>

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

using namespace std;

char field[20][20];
int w, h;
int cnt = 0;

int dfs(int x, int y){
    field[x][y] = '#';
    cnt++;

    for(int dx=-1; dx<=1; dx++){
        for(int dy=-1; dy<=1; dy++){
            if(dx!=0 && dy!=0) continue;
            int nx = x + dx;
            int ny = y + dy;
            if(0 <= nx && nx < w && 0 <= ny && ny < h && field[nx][ny] == '.') dfs(nx,ny);
        }
    }


}

int main(){
    while(cin >> w >> h){
        if(w==0 && h==0) break;
        char line[w];
        int start_x, start_y;
        REP(j,h){
            cin >> line;
            REP(i,w){
                if(line[i] == '@'){
                    start_x = i;
                    start_y = j;
                    field[i][j] = '.';
                }
                field[i][j] = line[i];
            }
        }
        cnt = 0;
        dfs(start_x, start_y);
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 1192
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();
            var m = cin.nextInt();
            var a = cin.ArrayLong(m);

            if(n >= m)
            {
                Console.WriteLine(0);
                return;
            }

            Array.Sort(a);
            var ds = new long[m-1];
            for (int i = 0; i < m-1; i++)
            {
                ds[i] = a[i + 1] - a[i];
            }

            Array.Sort(ds);

            var ans = 0L;
            for (int i = 0; i < (m-1)-(n-1); i++)
            {
                ans += ds[i];
            }
            // 5
            Console.WriteLine(ans);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 20448
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define F first
#define S second
#define f(i,s,n) for(int i=(int)s;i<=(int)n;++i)
#define Fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
void solve()
{
	int n;cin>>n;
	if(n<30){
		cout<<"No";
	}
	else
	cout<<"Yes\n";
}
int main()
{	Fast;
	//int t;cin>>t;
	//while(t--)
	solve();
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
  	cin >> s;
  	if(s[2] == s[3] && s[4] == s[5])
      	cout << "Yes" << endl;
 	else 
      	cout << "No" << endl;
 	return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n;
    vector<int> a;
    vector<int> b;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.push_back(x);
    }
    sort(a.begin(),a.end()); 
    for(int i=0;i<n;i++){
        //cout<<a[i]<<endl;
        int s=upper_bound(a.begin(),a.end(),a[i]+2)-a.begin()-i;
        b.push_back(s);
        //cout<<b[i]<<endl;
    }
    sort(b.begin(),b.end());
    cout<<b[n-1]<<endl;


    return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))

typedef long long ll;

int main() {
    
    int N, K;
    
    cin >> N >> K;
    
    if (K==0) {
        cout << (ll)N*N << endl;
        return 0;
    }
    
    ll ans = 0;
    for ( int i = 1; i+K <= N; i++) {
        int n = N/(i+K);
        ans += n*i + max( 0, N-n*(i+K)-K+1);
        //cout << ans << endl;
    }
    cout << ans << endl;
}



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

using namespace std;

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

typedef long long ll;
typedef long double ld;

const int maxN = 50;

ll combi[maxN+1][maxN+1];

// compute combination until maxN
void computeCombi(){
	memset(combi, 0, sizeof combi);
	
	for (int i = 0; i <= maxN; i++){
		combi[i][0] = 1;
	}
	
	for (int i = 1; i <= maxN; i++){
		for (int j = 1; j <= maxN; j++){
			combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
		}
	}
}


int computed[maxN*maxN+1];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	computeCombi();
	
	int n, a, b;
	cin >> n >> a >> b;
	ll v[n];
	
	for (int i = 0; i < n; i++){
		cin >> v[i];
	}
	
	sort(v, v+n, greater<ll>());
	
	
	ll totalA = v[0];
	// distinct numbers in first a
	vector<ll> unique;
	unique.push_back(v[0]);
	
	// count of numbers in first a
	unordered_map<int, int> countInA;
	countInA[v[0]] = 1;
	for (int i = 1; i < a; i++){
		totalA += v[i];
		if (v[i]!=v[i-1]) unique.push_back(v[i]);
		countInA[v[i]]++;
	}
	
	ld mean = (ld) totalA / a;
	
	unordered_map<int, int> counters;
	for (int i = 0; i < n; i++){
		counters[v[i]]++;
	}

	ll ways;
	int size = unique.size();
	// increase size until it's not all same
	if (size==1){	
		ways = 0;
		for (int i = a; i <= min(counters[v[0]],b); i++){
			ways += combi[counters[v[0]]][i];
		}
	}
	// how many ways to get this specific sequence
	else {
		ways = 1;
		for (ll num : unique){
			ways *= combi[counters[num]][countInA[num]];
		}
	}
	
	cout << fixed << setprecision(6) << mean << endl;
	cout << ways << endl;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
a,b,c = LI()
print(min(b//a,c))
"""

#B
"""
a,b,k = LI()
i = 1
ans = [1]
while i <= min(a,b):
    i += 1
    if a%i == 0 and b%i == 0:
        ans.append(i)
print(ans[-k])
"""

#C
"""
s = S()
n = len(s)
while len(s)>1:
    i = 0
    f = True
    while s[i] == s[i+1]:
        if i+1 == len(s)-1:
            f = False
            break
        i += 1
    if not f:break
    s.pop(i)
    s.pop(i)
print(n-len(s))
"""

#D
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]
def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        ans.append(ans[-1])
        return
    sx = s[x]
    sy = s[y]
    if rank[x] < rank[y]:
        par[x] = y
        s[y] += s[x]
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
        s[x] += s[y]
    ans.append(ans[-1]+sx*sy)
n,m  = LI()
v = LIR(m)
v = v[::-1]
par = [i for i in range(n)]
rank = [0 for i in range(n)]
s = [1 for i in range(n)]
k=n*(n-1)//2
ans = [0]
v.pop(-1)
for a,b in v:
    if ans[0]==k:
        ans.append(k)
        continue
    a -= 1
    b -= 1
    unite(a,b)
for i in ans[::-1]:
    print(k-i)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 91736
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];

  vector<Int> bs(as);
  sort(as.rbegin(),as.rend());
  for(Int i=0;i<n;i++) cout<<as[bs[i]==as[0]]<<endl;
  return 0;
}


Measured memory_bytes: 4736
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi deque<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<int,ll>
#define pll pair<ll,ll>
#define _path pair<ll,pair<ll,int> > 
#define vv deque
//#define endl '\n'
//#define mp make_pair

using namespace std;

const int MAXN = 300+5;
const int MOD = 1e9+7;


int grid[MAXN][MAXN];

int best = MAXN;
int n;
int m;

bool take[MAXN];
void recurse(){
    int cnt = 0;
    FOR(i,m)cnt += take[i];
    if(cnt == 0)return;

    int f[m];FOR(i,m)f[i] = 0;
    
    FOR(i,n){
        FOR(j,m){
            if(take[grid[i][j]]){
                f[grid[i][j]]++;
                break;
            }
        }
    }
    int x = 0;
    FOR(i,m){
        if(!take[i])continue;
        if(f[x] < f[i])x= i;
    }
    best= min(best,f[x]);
    take[x] = 0;
    recurse();

}


void solve(){
    
    cin >> n >> m;
    FOR(i,n){
        FOR(j,m){
            cin >> grid[i][j];
            grid[i][j]--;
        }
    }
   // vi x;FOR(i,n)x.pb(i);
    FOR(i,m)take[i] = 1;
    recurse();
    cout << best << endl;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   // test(958681902);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 4364
w,h,n = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]

a = 0
b = w
c = 0
d = h

for i,j,k in l:
    if k == 1:
        a = max(a,i)
    elif k == 2:
        b = min(b,i)
    elif k==3:
        c = max(c,j)
    else:
        d = min(d,j)

    if a >= b or c >= d:
        print(0)
        exit()
print((b-a)*(d-c))

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int k = stdIn.nextInt();
		String s = stdIn.next();
		
		if(s.length() <= k) {
			System.out.println(s);
		}else {
			System.out.println(s.substring(0,k)+"...");
		}
		
		
		
		
		
	}

}


Measured memory_bytes: 38704
n,h=gets.split.map &:to_i
a,b=$<.map{|e|e.split.map &:to_i}.transpose
amax=a.max
i=0
r=b.sort_by(&:-@).find{|e|e>amax&&(i+=1;h-=e;h<=0)}
p r ? i : i+(h+amax-1)/amax

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

int main() {
  vector<long long>vec(3);
  for(int i=0;i<3;i++){
    cin>>vec[i];
  }
  sort(vec.begin(),vec.end());
  cout<<vec[0]*vec[1]*abs((vec[2]-(vec[2]+1)/2)-(vec[2]+1)/2)<<endl;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
p = s / (4 * m)
cnt = 0
for i in range(n):
    if a[i] >= p:
        cnt += 1
if cnt >= m:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38384
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
signed main(){
	int n,d,a;
	cin>>n>>d>>a;
	pair<int,int>m[n+1LL];
	for(int i=1LL;i<=n;++i){
		cin>>m[i].first>>m[i].second;
		m[i].second=(m[i].second+a-1LL)/a;
	}
	sort(m+1LL,m+n+1LL);
	int j=1LL,sum=0LL,tot=0LL;
	int bomb[n+1LL];
	for(int i=1LL;i<=n;++i){
		while(j<i&&m[i].first-m[j].first>d*2){
			sum-=bomb[j];
			++j;
		}
		bomb[i]=max(m[i].second-sum,0LL);
		sum+=bomb[i];
		tot+=bomb[i];
	}
	cout<<tot<<endl;
	return 0;
}

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

using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    int res = 0;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }
    res = sum;
    int t = 0;
    for (int i = 0; i < N; i++) {
        t += A[i];
        res = min(res, abs(2 * t - sum));
    }
    cout << res << endl;
}

Measured memory_bytes: 1792