akhauriyash/Code-Regression huggingface dataset:
import * as fs from 'fs';

const input = fs.readFileSync("/dev/stdin", "utf8")
const args = input.split("\n").slice(1, input.split("\n").length - 1)

const dict = {}
let max = 0
args.forEach(i => {
  dict[i] = (dict[i] || 0) + 1
  if (max < dict[i]) max = dict[i]
})

const result = Object.keys(dict).sort().filter(k => dict[k] === max).join("\n")
console.log(result)


Measured memory_bytes: 140072
#include <bits/stdc++.h>
#define endl '\n'
#define ll unsigned long long
#define pi 3.1415926535897932384626433832
using namespace std;
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / __gcd(a, b); }
bool isPrime(int n) {if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false;
return true;}

void lok(){
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	double t;
	cin>>t;
	double rad=(t*pi)/180;
	double x=0;
	double y=1;
	int hseb=1;
	while(x>0.00000000001||y>0.00000000001){
		x=x+sin(hseb*rad);
		y=y+cos(hseb*rad);
		hseb++;
	}
	cout<<hseb<<endl;
	return 0;
}


Measured memory_bytes: 4112
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }
const double PI = 3.14159265358979323846;
int vector_finder(vector<int> vec, int number) {
  auto itr = find(vec.begin(), vec.end(), number);
  size_t index = distance(vec.begin(), itr);
  if (index != vec.size()) {  // 発見できたとき
    return 1;
  } else {  // 発見できなかったとき
    return 0;
  }
}
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a;
  int d;
  for (int i = 0; i < n; i++) {
    cin >> d;
    a.push_back(d);
  }
  sort(a.begin(), a.end());
  int ans = 0;
  for (int j = 0; j < k; j++) {
    ans = ans + a[j];
  }
  cout << ans;
}

Measured memory_bytes: 3636
# -*- coding: utf-8 -*-
from itertools import combinations
def inpl(): return map(int, input().split())

N = int(input())
P = [int(input()) for _ in range(N)]

if P[0] != 0 or any([P[i+1] - P[i] > 1 for i in range(N-1)]):
    print(-1)
else:
    ans = 0
    r = N-1
    now = 0
    for r in range(N)[::-1]:
        if P[r] != now:
            ans += P[r]
            now = P[r]
        now -= 1
    print(ans)

Measured memory_bytes: 12596
#include <stdio.h>
#include <math.h>
#define max(a,b) (a>b)?a:b
int main()
{
	int high[100005];
	int N;
	int cnt=0;
	int mm=0;
	scanf("%d",&N); 
	for(int i=0;i<N;i++) scanf("%d",&high[i]);
	for(int i=0;i<N-1;i++){
		if(high[i]>=high[i+1]) cnt++;
		else{mm=max(mm,cnt);cnt=0;}
	}
	printf("%d",max(mm,cnt));
	
}

Measured memory_bytes: 512
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	int pn = 1;
	if (ci - cn + 16 > cm) {
		if ((ct = getcha()) == '-') { pn = -1; ct = getcha(); }
		A = ct - '0';
		while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';;
		return pn * A;
	}
	else {
		if ((ct = *ci++) == '-') { pn = -1; ct = *ci++; }
		A = ct - '0';
		while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';;
		return pn * A;
	}
}
void pakuri_sort(int N, int A[]) {
	const int b = 8;
	int tmp[200001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint();
	ll K = 0;
	while ((ct = *ci++) >= '0') K = K * 10 + ct - '0';

	int sei[200000], fu[200000];
	int seik = 0, fuk = 0;
	int zero = 0;
	rep(i, N) {
		int a = getint();
		if (a > 0) sei[seik++] = a;
		else if (a < 0) fu[fuk++] = -a;
		else zero++;
	}
	pakuri_sort(seik, sei);
	pakuri_sort(fuk, fu);
	ll k0 = ll(seik) * fuk + ll(zero) * (zero - 1) / 2 + ll(zero) * (N - zero);

	ll L = -1000000000000000001, R = 1000000000000000000;
	while (L + 1 < R) {
		ll M = (L + R) / 2;
		ll k = 0;
		if (M >= 0) {
			k += k0;
			if (k >= K) { R = M; continue; }
			int i = 0;
			int j = seik - 1;
			while (i < seik) {
				while (j > i && ll(sei[i]) * sei[j] > M) j--;
				if (i == j) break;
				k += j - i;
				i++;
			}
			if (k >= K) { R = M; continue; }
			i = 0;
			j = fuk - 1;
			while (i < fuk) {
				while (j > i && ll(fu[i]) * fu[j] > M) j--;
				if (i == j) break;
				k += j - i;
				i++;
			}
		}
		else {
			int j = 0;
			rep(i, seik) {
				while (j < fuk && ll(sei[i]) * fu[fuk - j - 1] >= -M) j++;
				k += j;
			}
		}
		if (k >= K) R = M;
		else L = M;
	}

	printf("%lld\n", R);

	Would you please return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define int long long

string s;
int n;
const int mod = 1e9 + 7;
int dp[3001][3001];

void solve() {
	dp[n][0] = (s[n - 2] == '>') ? 1 : 0;
	dp[n][1] = (s[n - 2] == '<') ? 1 : 0;

	for (int i = n - 1; i >= 2; i--) {
		int total = n - i + 1;
		for (int g = 0; g <= total; g++) {
			if (g == 0) {
				if (i == n) continue;
				dp[i][g] = 0;
				if (s[i - 2] == '<') continue;
				for (int j = 1; j <= total; j++)
					dp[i][g] = (dp[i][g] + dp[i + 1][total - j]) % mod;
			}
			else {
				if (s[i - 2] == '>')
					dp[i][g] = (mod + dp[i][g - 1] - dp[i + 1][g - 1]) % mod;
				else
					dp[i][g] = (dp[i][g - 1] + dp[i + 1][g - 1]) % mod;
			}
		}
	}
}

int32_t main()
{
	cin >> n >> s;
	solve();
	int ans = 0;
	for (int greater = n - 1; greater >= 0; greater--)
		ans = (ans + dp[2][greater]) % mod;
	cout << ans;
	return 0;
}


Measured memory_bytes: 70016
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
const int mod=1e9+7;
using LL=long long;
using std::cout;using std::endl;using std::cin;
using std::vector;using std::string;using std::set;using std::multiset;
using std::pair;using std::map;
using std::min;using std::max;
using std::make_pair;
std::ostream& operator<<(std::ostream& os,std::map<int,int>& obj){for(std::map<int,int>::iterator itr=obj.begin();itr!=obj.end();itr++){os<<itr->first<<"^"<<itr->second<<" ";}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<std::map<int,int>>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<std::endl;}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<int>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<" ";}return os;}

namespace ndifix{

}

int main(){
  int n;cin>>n;
  cout<<(n-2)*180<<endl;


  return 0;
}


Measured memory_bytes: 256
from heapq import heappop, heappush
from typing import List, Tuple


def find(x):
    global parents
    if x == parents[x]:
        return x
    else:
        tmp = find(parents[x])
        parents[x] = tmp
        return tmp


if __name__ == "__main__":
    V, E = map(int, input().split())
    parents = [i for i in range(V)]
    que: List[Tuple[int, int , int]] = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        heappush(que, (w, s, t))

    ans = 0
    while que:
        w, s, t = heappop(que)
        root_s = find(s)
        root_t = find(t)
        if root_s != root_t:
            parents[root_s] = root_t
            ans += w

    print(ans)



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

using namespace std;

template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int X, N;
  cin >> X >> N;
  vector<int> P(N);
  for (int i = 0; i < N; i++) {
    cin >> P[i];
  }
  sort(P.begin(), P.end());
  int res = 0, diff = 1000;
  for (int i = 0; i < 200; i++) {
    if (!binary_search(P.begin(), P.end(), i) && chmin(diff, abs(X - i))) {
      res = i;
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1e11;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); 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; }


int main() {
    ll n;
    cin >> n;
    vector<ll> a(n, 0), b(n, 0);
    rep1(i, n){
        cin >> a[i];
        if (i==0) b[i] = a[i];
        else b[i] += a[i] + b[i-1];
    }
    ll ans = INF;
    rep1(i, n-1){
        ans = min(ans, abs(b[n-1]-2*b[i]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 6336
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cassert>
#include<cmath>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 105
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
using namespace std;

int N,T,L,B;
double dp[MAX][MAX];
char G[MAX];

int main()
{
  while(cin >> N >> T >> L >> B,N|T|L|B)
    {
      rep(i,MAX)G[i] = '.';
      rep(i,MAX)rep(j,MAX)dp[i][j] = 0;
      rep(i,L)
	{
	  int lose;
	  cin >> lose;
	  G[lose] = 'L';
	}
      rep(i,B)
	{
	  int back;
	  cin >> back;
	  G[back] = 'B';
	}

      dp[0][0] = 1;
      rep(t,T)
	{
	  rep(n,N)//goalしたらサイコロをふる必要はないのでN-1まで
	    {
	      if(equals(dp[t][n],0))continue;
	      REP(i,1,7)
		{
		  int nextN = (n+i);
		  int nextT = t+1;
		  if(nextN > N)nextN = N - (nextN-N);
		  if(G[nextN] == 'L')nextT++; 
		  else if(G[nextN] == 'B')nextN = 0;
		  dp[nextT][nextN] += dp[t][n]*(1.0/6.0);
		}
	    }
	}
      double ans = 0;
      rep(i,T+1)ans += dp[i][N]; 
      cout << setiosflags(ios::fixed) << setprecision(10) << ans << endl;
    }
  return 0;
}

Measured memory_bytes: 1320
#include<iostream>
using namespace std;
int a[200000];
long long int sum[200000];
long long int d[200000];
int main()
{
	int i;
	long long int j;
	long long int c;
	long long int b=0;
	cin >> i;
	for (int k=0; k < i; k++)
	{
		cin >> a[k];
		b = b + a[k];
	}
	sum[0] = a[0];
	for (int k = 1; k < i; k++)
	{
		sum[k] = sum[k - 1] + a[k];
		c = b - sum[k-1];
		d[k] = sum[k-1] - c;
	}
	j = abs(d[1]);
	for (int k = 1; k < i - 1; k++)
	{
		if (abs(d[k]) < j)
		{
			j = abs(d[k]);
		}
	}
	cout << j;
}

Measured memory_bytes: 4096
/* To Kaise Hain Aaplog*/

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) (x).begin(), (x).end()

void shuru_krte_hai_bina_kisi_bakchodi_ke()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}

int32_t main()
{
    //shuru_krte_hai_bina_kisi_bakchodi_ke();
    int n,x,t;
    cin>>n>>x>>t;
    int val = n/x;
    if(n%x!=0){
        val++;
    }
    cout<<val*t<<"\n";
    return 0;
}

Measured memory_bytes: 3592
import java.util.*;
import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		long n = sc.nextLong();
		int k = sc.nextInt();
		long r = sc.nextLong();
		long s = sc.nextLong();
		long p = sc.nextLong();
		String t = sc.next();
		
		// 計算
		long result = 0;
		char[] list = new char[t.length()];
		
		for(int i = 0; i < t.length(); i++){
		    if(t.charAt(i) == 'r'){
		        if(i - k >= 0 && list[i-k] == 'p'){
		            list[i] = 'n';
		        }else{
		            result += p;
		            list[i] = 'p';
		        }
		    }
		    if(t.charAt(i) == 's'){
		        if(i - k >= 0 && list[i-k] == 'r'){
		            list[i] = 'n';
		        }else{
		            result += r;
		            list[i] = 'r';
		        }
		    }
		    if(t.charAt(i) == 'p'){
		        if(i - k >= 0 && list[i-k] == 's'){
		            list[i] = 'n';
		        }else{
		            result += s;
		            list[i] = 's';
		        }
		    }
		}
		
		
		
		// 出力
		System.out.println(result);
	}
}


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

int main(){
    unsigned long x;
    cin >> x;
    bitset<32> b(x);

    cout << b << endl;
    cout << ~b << endl;
    cout << (b<<1) << endl;
    cout << (b>>1) << endl;

    return 0;
}


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

int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if(A + B > C + D) cout << "Left" << endl;
    else if(A + B < C + D) cout << "Right" << endl;
    else cout << "Balanced" << endl;
    return 0;
}

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

#define int long long
#define INT int
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}
typedef long long ll;
const long long INF = 1LL << 60;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

int n;
vector<int> h;
int dp[100005];

int funT(int x)
{

    if (x == 1 || x == 0)
    {
        return 0;
    }
    else if (x == 2)
    {
        return abs(h[1] - h[0]);
    }
    if (dp[x] != 0)
    {
        return dp[x];
    }

    int m1 = funT(x - 1) + abs(h[x - 1] - h[x - 2]);
    int m2 = funT(x - 2) + abs(h[x - 1] - h[x - 3]);

    dp[x] = min(m1, m2);
    return dp[x];
}

int funB(int x)
{

    rep(i, 100005)
    {
        dp[i] = INF;
    }
    dp[0] = 0;

    rep1(i, n)
    {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1)
        {
            chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
        }
    }

    return dp[n - 1];
}

signed main()
{
    cin >> n;
    h.resize(n);
    rep(i, n)
    {
        cin >> h[i];
    }

    int ans = funB(n);

    print(ans);
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
// #define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vpipii vector<pipii>
#define vpiipi vector<piipi>
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
#define pipii pair<int,pii>
#define piipi pair<pii,int>
#define pld pair<long double,long double>
#define mod 1000000007
// #define mod 1000000009
// #define mod 163577857 
// #define mod 998244353
#define rep(i,n) for (int i = 0; i < n; i++)
#define repp(i,a,b) for(int i = a ; i<b ; i++)
#define reppr(i,a,b) for(int i = a-1 ; i>=b ; i--)
#define repr(i,n) for (int i = n - 1; i >= 0; i--)
#define ff first
#define ss second
#define pc putchar_unlocked
#define gc getchar_unlocked
#define inf 9223372036854775807
#define infn -9223372036854775807
#define pi 3.14159265358979323846
#define eps 0.0000000001
#define sp << " " <<
#define setprec(x) cout << fixed << setprecision(x);
#define REVERSE(a) reverse(all(a));
#define SORT(a) sort(all(a));
#define all(n) n.begin(),n.end()
 
//GCD and LCM
    int gcd (int a, int b) { return b ? gcd (b, a % b) : a; }
    int lcm (int a, int b) { return a / gcd(a, b) * b; }
 
//Modular Exponentiation
    int powmod(int x,int y) 
    { 
        if (y == 0) return 1; 
        int p = powmod(x, y/2) % mod; 
        p = (p * p) % mod;   
        return (y%2 == 0)? p : (x * p) % mod; 
    }
 
//Modular Inverse
    int inverse(int a) 
    { 
       return powmod(a,mod-2); 
    }

//Binomial Coefficients
    int fact[500010], factinv[500010] , coefficientflag = 0;
    void Util_nCr()
    {
        fact[0] = 1 , factinv[0] = 1;
        repp(i,1,500010)
        {
            fact[i] = (fact[i-1] * i)%mod;
            factinv[i] = (factinv[i-1] * inverse(i))%mod;
        }
    }
    int nCr(int n , int r)
    {
        if(!coefficientflag) coefficientflag = 1 , Util_nCr();             
        return ((fact[n] * inverse(fact[n-r]) % mod * inverse(fact[r]))%mod) ;
    }

void solve();
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    // cin >> t; 
    rep(i,t)
    {
        // cout << "Case #" << i+1 << ": ";
        solve();
    }
}

int sumSubarrayMins(int A[], int n) 
{ 
    int left[n], right[n]; 
    stack<pair<int, int> > s1, s2; 
    for (int i = 0; i < n; ++i) { 
        int cnt = 1; 
        while (!s1.empty() && (s1.top().first) > A[i]) { 
            cnt += s1.top().second; 
            s1.pop(); 
        } 
  
        s1.push({ A[i], cnt }); 
        left[i] = cnt; 
    } 
    for (int i = n - 1; i >= 0; --i) { 
        int cnt = 1; 
        while (!s2.empty() && (s2.top().first) >= A[i]) { 
            cnt += s2.top().second; 
            s2.pop(); 
        } 
  
        s2.push({ A[i], cnt }); 
        right[i] = cnt; 
    } 
    int result = 0; 
    for (int i = 0; i < n; ++i) 
        result = (result + A[i] * left[i] * right[i]); 
    return result; 
} 

void solve() 
{
    int n;
    cin >> n;
    int a[n];
    rep(i,n)
        cin >> a[i];
    cout << sumSubarrayMins(a,n);
}  

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

int N, d, t, q;

const int L = 16 * 9 * 5 * 7 * 11;

int main() {

	while ( cin >> N && N ) {
	
		int Q[25][25] = {{0}};

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

			cin >> d >> t;

			for ( int j = 0; j < d; j++ ) {

				cin >> q;
				Q[d][( j + d - t ) % d] += q;

			}

		}

		int sum = 0, T[L] = {0};

		for ( int d = 1; d <= 24; d++ ) {

			if ( d == 13 || d == 17 || d == 19 || d == 23 || d == 1 ) {

				int max = 0;

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

					if ( max < Q[d][i] ) { max = Q[d][i]; }

				}

				sum += max;

			} else {

				for ( int i = 0; i < L; i++ ) { T[i] += Q[d][i % d]; }

			}

		}

		int max = 0;

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

			if ( max < T[i] ) { max = T[i]; }

		}
			
		cout << sum + max << endl;

	}

}

Measured memory_bytes: 1384
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define pi pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912

const long double PI = acos(-1);
const ll DEP = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int GCD(int x,int y){
    return y ? GCD(y,x%y) : x;
}
int main(){
    int N,K; cin >> N >> K;
    double p = 0.0000000000000000;
    for(int i = 1; i <= N; i++){
        int j = i;
        double q = 1.00000000000/N;
        while(j < K){
            q /= 2.0;
            j*=2;
        }
        p += q;
    }
    cout << setprecision(10) << p << endl;
}



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

int main(){
    int n;
    cin>>n;
    int a[110];
    for(int i=0;i<n;i++)cin>>a[i];
    int cnt=0;
    //BubbleSort
    // for(int i=0;i<n-1;i++){
    //     for(int j=i+1;j<n;j++){
    //         if(a[i]>a[j]){
    //             swap(a[i],a[j]);
    //             cnt++;
    //         }
    //     }
    // }
    int tmp = 0;
	for(int i = n-1;i > 0;i--){
		for(int j = 0; j < i;j++){
			if(a[j] > a[j+1]){
				tmp = a[j+1];
				a[j+1] = a[j];
				a[j] = tmp;
				cnt++;
			}
		}
	}
    //Output
    for(int i=0;i<n;i++){
        cout<<a[i];
        if(i<n-1)cout<<" ";
        else cout<<"\n";
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define rep( i, n ) for (ll i = 0; i < ( ll )(n); i++)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair< int , int > P;
typedef tuple<int, int, int> T;



int main(){
    ll a,b,n;
    ll ans;
    cin>>n>>a>>b;

    if(a>=n) ans=n;
    else ans=n/(a+b)*a+min(a,n%(a+b));
    cout<<ans;
}

Measured memory_bytes: 3580
//is there any case of -1 or any special corner cases ?
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define zeros(arr) memset(arr,0,sizeof(arr));
#define precise(num)  cout<<fixed; cout << std::setprecision(num)
#define nl cout<<"\n";
#define test int t;cin>>t;while(t--) 
const int maxx  = 3*1e5 , limit = 9*1e18 , MOD=1e9+7;
#define boost  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n';

int32_t main(){
    boost;
    
    string s;
    cin>>s;
    for(int i= 0;i<s.size();i++){
        if(s[i] =='?')
        s[i] = 'D';
    }
    cout<<s<<endl;
}

Measured memory_bytes: 3768
#include<stdio.h>

int main(){
  int a,count=0;
  int v=0;
  int i=0;
  int n=0;
  int j=0;
  int k=0;
  scanf("%d",&n);
  int A[n];
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  for(i=1;i<n;i++){
    for(k=0;k<n-1;k++){
      printf("%d ",A[k]);
    }
    printf("%d\n",A[n-1]);
    v=A[i];
    j=i-1;
    while(j>=0 && A[j] > v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
  }
  for(k=0;k<n-1;k++){
    printf("%d ",A[k]);

  }
  printf("%d\n",A[n-1]);

  return(0);
}



Measured memory_bytes: 2124
#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) int(x.size())
#define pii pair<int, int>
#define All(x) (x).begin(), (x).end()
#define mp make_pair
#define Task "abc"
 
typedef long long ll;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
 
ll f[maxn], cnt[maxn];
 
ll Pow(ll x, ll y){
  if (y == 0) return 1;
  ll tmp = Pow(x, y / 2);
  tmp = tmp * tmp; tmp %= mod;
  if (y % 2) return (tmp * x) % mod;
  return tmp;
}
 
int main(){
  ios_base::sync_with_stdio(0); cin.tie(NULL);
//  freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout);
  int n, k; cin >> k;
  n = 3; 
  for (int i = 1; i <= k; ++i)
    for (int j = i; j <= k; j += i) ++cnt[i];
 
  ll ans = 0;
  for (int i = k; i > 0; --i){
    f[i] = Pow(cnt[i], n);
    for (int j = i * 2; j <= k; j += i) {
      f[i] = f[i] - f[j] + mod;
      f[i] %= mod;
    }
    ans = ans + f[i] * i;
    ans = ans % mod;
  }
  cout << ans;
 
return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define vvvel vector<vvel>
void mmin(int &a, int b) { a = min(a, b); }
void mmax(int &a, int b) { a = max(a, b); }
void sor(vel &v) { sort(v.begin(), v.end()); }
void m1(int &a) { a = a % 10000; }
void swap(vel &ti, vel &in, int i, int j) {
	int x = ti[i]; int y = ti[j];
	ti[j] = x; ti[i] = y;
	in[x] = j; in[y] = i;
}
void crsi(vel &ti, vel &in, int a) {
	swap(ti, in, in[a], in[a + 1]);
}
void crue(vel &ti, vel &in, int a) {
	swap(ti, in, a, a + 1);
}
int sc(int k, vel &ti, vel &s) {
	int ans = 0;
	int n = s.size();
	for (int i = 0; i < k; i++) {
		ans += s[ti[i]];
	}
	return ans;
}
signed main() {
	int n, m, h, k;
	cin >> n >> m >> h >> k;
	while (n != 0) {
		vel s(n);
		for (int i = 0; i < n; i++) {
			cin >> s[i];
		}
		vel a(m);
		vel b(m);
		vel ma(m);
		for (int i = 0; i < m; i++) {
			cin >> a[i] >> b[i];
			a[i]--;
			ma[i] = b[i] * n + a[i];
		}
		sor(ma);
		for (int i = 0; i < m; i++) {
			a[i] = ma[i] % n;
			b[i] = ma[i] / n;
		}
		vel in0(n);
		vel in1(n);
		vel ti0(n);
		vel ti1(n);
		for (int i = 0; i < n; i++) {
			in0[i] = i; ti0[i] = i;
			in1[i] = i; ti1[i] = i;
		}
		for (int i = 0; i < m; i++) {
			crsi(ti1, in1, a[i]);
		}
		int ans = sc(k, ti1, s);
		crue(ti1, in1, a[0]);
		mmin(ans, sc(k, ti1, s));
		for (int i = 1; i < m; i++) {
			crsi(ti0, in0, a[i - 1]);
			crue(ti1, in1, a[i]);
			int x = 0;
			for (int i = 0; i < k; i++) {
				x += s[ti1[ti0[i]]];
			}
			mmin(ans, x);
		}
		cout << ans << endl;
		cin >> n >> m >> h >> k;
	}
	return 0;
}


Measured memory_bytes: 5164
#include <bits/stdc++.h> 
#define int long long
#define deb(x) cout<<#x <<" = "<<x<<"\n";
using namespace std; 

signed main() 
{
  int n; cin>>n;
  set<int> s;
  for(int i=0; i<n; i++)
  {
    int x; cin>>x; s.insert(x);
  }
  if((int) s.size() == n) cout<<"YES";
  else cout<<"NO";
	
}

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

#define ll long long

using namespace std;

int main()
{
    int n,c=0;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0; i<n/2; i++){
        if(s[i]!=s[n/2+i]){
            c=1; break;
        }
        
    }
    if(n%2!=0) cout<<"No"<<endl;
    else if(c==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }




}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#define ll long long
#define mp make_pair

using namespace std;

int main()
{
     int n, ans = 0;
     cin >> n;

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

    for(int i = 0; i < n; i++){
        for(int j = i+1;j < n; j++){
            for(int k = j+1; k < n; k++){
                if(arr[i] + arr[j] > arr[k] && arr[j] + arr[k] > arr[i] && arr[i] + arr[k] > arr[j] && arr[i] != arr[j] && arr[i] != arr[k] && arr[k] != arr[j])
                    ans++;
                    //cout << arr[i] << ' ' << arr[j] << ' ' << arr[k] << '\n';
            }
        }
    }

    cout << ans << "\n";

}


Measured memory_bytes: 3632
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function main()
    n=parseInt(readline())
    for i in n:999
        s=string(i)
        if s[1]==s[2]==s[3]
            println(s)
            break
        end
    end
end
main()

Measured memory_bytes: 163096
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

ll N;
vector<ll> a;

//dp
vector<vector<ll>> table;

ll dp(ll i,ll j){
  if(i==j) return a.at(i);
  if(table.at(i).at(j)>-INF) return table.at(i).at(j);
  
  table.at(i).at(j)++;;
  chmax(table.at(i).at(j),a.at(i)-dp(i+1,j));
  chmax(table.at(i).at(j),a.at(j)-dp(i,j-1));
  
  return table.at(i).at(j);
}
    

int main()
{
  cin>>N;
  a=vector<ll>(N); rep(i,N) cin>>a.at(i);
  
  //dp
  table=vector<vector<ll>>(N,vector<ll>(N,-INF));

  cout<<dp(0,N-1)<<endl;
  return 0;
}

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

int main(){
  int K,S,ans=0;
  cin >> K >> S;
  for(int i=0;i<K+1;i++){
    for(int j=0;j<K+1;j++){
      if(0<=S-i-j&&S-i-j<=K)
        ans++;
    }
  }  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    for(int i = 0; i < s.size() - 1; ++i){
        if(s[i] == 'A' && s[i + 1] == 'C'){
            cout<<"Yes"<<endl;return 0;
        }
    }
    cout<<"No"<<endl;
}



Measured memory_bytes: 256
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

class BIT():
    def __init__(self, n, data):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)
        if data:
            self.build(data)

    def build(self, data):
        for i in range(self.n):
            self.bit[i + 1] = self.data[i + 1] = data[i]
        for i in range(1, self.n):
            j = i + (i & (-i))
            if j <= self.n:
                self.bit[j] += self.bit[i]

    def add(self, idx, x):
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sub_sum(self, idx):
        a = 0
        while idx:
            a += self.bit[idx]
            idx -= (idx & (-idx))
        return a

    #i, j is 1-indexed, not 0-origin
    def sum(self, i, j):
        a = 0
        if j != 0:
            a += self.sub_sum(j)
        if i != 0:
            a -= self.sub_sum(i)
        return a

n,q=nii()
a=lnii()
bit=BIT(n,a)
for i in range(q):
    t,x,y=nii()
    if t==0:
        bit.add(x+1,y)
    else:
        print(bit.sum(x,y))

Measured memory_bytes: 65088
num = input().rstrip()
line = []
for i in range(int(num)):
    line.append(input().rstrip())
line_ac = [s for s in line if "AC" in s]
line_wa = [s for s in line if "WA" in s]
line_tle = [s for s in line if "TLE" in s]
line_re = [s for s in line if "RE" in s]

print("AC x " + str(len(line_ac)))
print("WA x " + str(len(line_wa)))
print("TLE x " + str(len(line_tle)))
print("RE x " + str(len(line_re)))

Measured memory_bytes: 17068
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int A[128];

int main(){
	A[0]=1;
	for(int i=1; i<=32; i++){
		A[i]=A[i-1];
		if(i>1)A[i]+=A[i-2];
		if(i>2)A[i]+=A[i-3];
	}
	int n;
	while(1){
		cin>>n;
		if(n==0)break;
		cout<<((A[n]+9)/10+364)/365<<endl;
	}
}

Measured memory_bytes: 1160
N, Q = map(int, input().split())
S = input()
S = S.replace("AC", "XX")
acc = [0] * (N + 1)
i = 0
while i < N:
    if S[i] == "X":
        acc[i + 2] = 1 
        i += 2
    else:
        i += 1
for i in range(1, N + 1):
    acc[i] += acc[i - 1]

for i in range(Q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l])

Measured memory_bytes: 13032
//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define pb push_back

const int N = 1e5 + 5;
const int OO = 1e9;
const int mod = 1e9 + 7;

int a,b,ans;
vector<int> m;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ans = OO;

    cin >> a >> b;

    for(int i=a;i<= b && i<a+2019;++i) m.pb(i%2019);

    for(int i=0;i<m.size();++i) {

        for(int j=i+1;j<m.size();++j) {

            ans = min(ans,(m[i]*m[j])%2019);

        }

    }

    cout << ans << '\n';

    return 0;

}

Measured memory_bytes: 256
#pragma GCC optimize("O3")

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <assert.h>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <random>
#include <cmath>
#include <chrono>
#include <bitset>

#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define int long long
using namespace std;
const int INF = 2e16;
const int MOD = 1e9 + 7;
const int MB = 20;
const int K = 500;
const int maxN = 2e4 + 1;


void solve() {
	int n;
	cin >> n;
	map<string, int> st;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		sort(all(s));
		st[s]++;
	}
	int ans = 0;
	for (auto& p : st) ans += p.second * (p.second - 1) / 2;
	cout << ans;
}


signed main() {
	/*
	freopen("search.in", "r", stdin);
	freopen("search.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	solve();
}

Measured memory_bytes: 11264
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n,m,v,p;
  cin >> n >> m >> v >> p;
  vector<ll> a(n);
  rep(i,n) {
    cin >> a[i];
  }
  sort(all(a));
  reverse(all(a));
  // printvec(a);

  auto check = [&](ll x) {
    if (a[x]+m < a[p-1]) { // Here, a[x] can't exceed a[p-1]
      return false;
    }
    assert(a[x]+m >= a[p-1]);
    if (x <= p-1) { // Here, x is already in top p
      return true;
    }
    assert(x >= p);

    ll tot = 0; // We can select tot
    // Select m in x. [x,x]
    tot += m;
    // Select m in top p-1. [0,p-1)
    for (int i = 0; i < p-1; ++i) {
      tot += m;
    }
    // Select m in bottom. (x, n)
    for (int i = x+1; i < n; ++i) {
      tot += m;
    }
    // Select available in [p-1,x)
    for (int i = p-1; i < x; ++i) {
      tot += a[x]+m - a[i]; // a[i] must not exceed a[x]+m
    }
    // cout << "x:" << x << endl;
    // cout << "tot:" << tot << endl;
    // cout << "m*v:" << m*v << endl;
    return tot >= m*v; // tot must exceed m*v
  };

  ll l = -1;
  ll r = n;
  // Here, find boundary of [t,f]
  while (r-l > 1) {
    ll m = (l+r)/2;
    if (check(m)) {
      l = m;
    } else {
      r = m;
    }
  }
  // Here, [1,l] is ok.
  cout << l+1 << endl;
}


Measured memory_bytes: 3992
fun main(args:Array<String>){
    val l = readLine()!!.split(" ").map { it.toInt() }
    val n = l[0]
    val m = l[1]
    val list = readLine()!!.split(" ").map { it.toInt() }
    val sum = list.sum()
    if(n-sum<0) println("-1") else println(n-sum)
}

Measured memory_bytes: 39272
s = gets.chomp
q = gets.to_i
reverse = false
pre_add = []
bf_add = []
q.times do |i|
  query = gets.chomp.split(" ").map(&:to_s)
  if query[0] == "2"
    if (query[1] == "1" && !reverse) || (query[1] == "2" && reverse)
      pre_add.push(query[2])
    else
      bf_add.push(query[2])
    end
  else
    reverse = !reverse
  end
end
if reverse
  bf_add.reverse.each do |s|
    print s
  end
  print s.reverse
  pre_add.each do |s|
    print s
  end
else
  pre_add.reverse.each do |s|
    print s
  end
  print s
  bf_add.each do |s|
    print s
  end
end


Measured memory_bytes: 17916
#include <stdio.h>
int main()
{
    int x,a,b,e,f;
    scanf("%d %d %d",&x,&a,&b);
    if((x-a)>0){
    	e=x-a;
	}else{
		e=a-x;
	}
	if((x-b)>0){
    	f=x-b;
	}else{
		f=b-x;
	}
	if(e>f){
		printf("B");
	}else if(e<f){
		printf("A");
		
	}
    
	  
	return 0;
 } 

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
	return a>b;
} 
int main()
{
	int n,k,x;
	cin>>n>>k;
	int a[200000+5]={0};
	for(int i=0;i<n;i++){
		cin>>x;
		a[x]++;
	}
	sort(a+1,a+200000+1,cmp);
	int count=0;
	for(int i=k+1;i<=200000;i++)count+=a[i];
	cout<<count<<endl;
	return 0;
}

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

int main(void){
  int n, m;
  cin >> n >> m;
  int ans = 0;
  n -= 1; m -= 1;
  ans += n*(n+1)/2;
  ans += m*(m+1)/2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3588
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#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)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18



//for (auto p : prime_factor(N)) {
//	cout << p.first << " " << p.second << endl;
//}

//auto primes=primefactor(n);


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

	LL ans = 0;

	LL q = 0;
	LL r = -1;

	for (LL i = 1; i*i <= n; i++) {
		if (n%i != 0)continue;

		q = n/i;

		if (i != 1) {
			r = n % (i - 1);
			if (q == r) {
				ans += i - 1;
			}
		}

		if (q != 1) {
			r = n % (q - 1);
			if (i == r) {
				ans += q - 1;
			}
		}

	}

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

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;


struct UF
{
	vector<int> par; // 親
	// 初期化
	UF(int n):par(n) {
		for(int i = 0; i < n; i++){
			par[i] = i;
		}
	}
	// 木の根を求める
	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		// 木の高さが高い方を代表ノードにする
		par[x] = y;
	}
	// xとyが同じ集合ならtrue
	bool same(int x, int y) { return find(x) == find(y); }
};

vector<pair<int,pair<int,int> > > v;

int kruskal(int n)
{
	sort(ALL(v));
	UF uf(n);
	
	int ret = 0;
	
	REP(i,v.size())
	{
		pair<int,pair<int,int> > e = v[i];
		if(!uf.same(e.SE.FI,e.SE.SE))
		{
			uf.unite(e.SE.FI,e.SE.SE);
			ret += e.FI;
		}
	}
	return ret;
}
	

int main()
{
	int n;
	cin >> n;
	
	
	vector<pair<int,int> > dx;
	vector<pair<int,int> > dy;
	
	REP(i,n)
	{
		int x,y;
		cin >> x >> y;
		dx.PB(MP(x,i));
		dy.PB(MP(y,i));
	}
	
	sort(ALL(dx));
	sort(ALL(dy));
	
	REP(i,n-1)
	{
		v.PB(MP(abs(dx[i].FI - dx[i+1].FI),MP(dx[i].SE,dx[i+1].SE)));
		v.PB(MP(abs(dy[i].FI - dy[i+1].FI),MP(dy[i].SE,dy[i+1].SE)));
	}
	
	cout << kruskal(n) << endl;
	
	
	return 0;
}

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

int main() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;

  if (k <= a) cout << k << endl;
  else if (k <= a + b) cout << a << endl;
  else cout << a - (k - a - b) << endl;
}

Measured memory_bytes: 3624
#include<iostream>
using namespace std;
bool output(char x,char y)
{if(x==y)
 return true;
 return false;
}
int main()
{char a,b;
 cin>>a>>b;
 if(output(a,b))
 cout<<"H"<<endl;
 else
 cout<<"D"<<endl;
 return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <set>
using namespace std;

int main() {
  string S;
  cin >> S;
  long ans = 0;
  for (int i = 0; i < (1 << (S.length() - 1)); i++) {
    long sum = 0, tmp = 0;
    for (int j = 0; j < S.length(); j++) {
      tmp = tmp * 10 + stol(S.substr(j, 1));
      if (((i >> j) & 1) == 1) { // insert '+' after the read chars
        sum += tmp;
        tmp = 0;
      }
    }
    sum += tmp;
    // cout << "C" << sum << endl;
    ans += sum;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp = [[[0]*(sum(x)+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
        for k in range(i):
                for j in range(sum(x)+1):
                        if dp[i-1][k][j]:
                                dp[i][k+1][j+x[i-1]] += dp[i-1][k][j]
        for k in range(i):
                for j in range(sum(x)+1):
                        if dp[i-1][k][j]:
                                dp[i][k][j] += dp[i-1][k][j]
ans = 0
for i in range(1,n+1):
        for j in range(1,sum(x)+1):
                if j == i*a:
                        ans += dp[n][i][j]
print(ans)

Measured memory_bytes: 54004
#include<math.h>
int main(){int ix,iy,d=90;double x=0,y=0;while(scanf("%d,%d",&ix,&iy),ix+iy){x+=ix*cos((double)d/180*M_PI);y+=ix*sin((double)d/180*M_PI);d-=iy;}printf("%d\n%d\n",(int)x,(int)y);return 0;}

Measured memory_bytes: 604
#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>

#define rep(i,x) for(int i=0;i<x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rep_to(a,i,x) for(int i=a;i<x;i++)

using namespace std;

int kai(int n)
{
	int sum=1;
	for(int i=n;i>=1;i--)sum*=i;
	return sum;
}

int main()
{
	int n;
	while(1){
	cin>>n;
	if(n==0)break;

	int mx=0,mi=1000,sum=0;
	rep(i,n)
	{
		int s;
		cin>>s;
		mi=min(mi,s);
		mx=max(mx,s);
		sum+=s;
	}
	cout<<(sum-mi-mx)/(n-2)<<endl;
}
	return 0;
}

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

using ll = long long;
using Field = vector<vector<ll>>;
using Graph = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VC = vector<char>;
using PI = pair<int, int>;

#define FOR(i, s, n) for (int i = s; i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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

ll N;
vector<ll> A;

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

    cin >> N;
    A.resize(N);

    bool flag = false;

    REP(i, N) {
        cin >> A[i];
        if (A[i] == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    ll AA = 1;
    REP(i, N) {
        if (AA > 1000000000000000000 / A[i]) {
            flag = true;
            break;
        }
        AA *= A[i];
    }

    if (flag) {
        cout << -1 << endl;

    } else {
        cout << AA << endl;
    }

    return 0;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#define int long long
using namespace std;
const int N=2e5+5,MOD=1e9+7;
int n,m,ans;
int bin[N],inv[N];

inline int pow(int a,int n)
{
	int res=1ll;
	while (n)
	{
		if (n&1ll) res=res*a%MOD;
		n>>=1ll;
		a=a*a%MOD;
	}
	return res;
}

inline int C(int x,int y)
{
	return bin[x]%MOD*inv[x-y]%MOD*inv[y]%MOD;
}

signed main(){
	scanf("%lld%lld",&n,&m);
	bin[0]=1; inv[0]=1;
	for (register int i=1; i<=n; ++i) bin[i]=bin[i-1]*i%MOD;
	for (register int i=1; i<=n; ++i) inv[i]=pow(bin[i],MOD-2ll)%MOD;
	ans=1;
	for (register int i=1; i<n; ++i) 
	if (n-i<=m) ans=(ans+C(n,i)*C(n-1,i-1)%MOD+MOD)%MOD;
	printf("%lld\n",ans);
return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000000

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

long long combination(int n, int p)
{
  long long mod = 1000000007;
  long long ans = 1;
  if (p > n - p)
  {
    p = n - p;
  }
  vector<long long> modinv_vec(p);
  for (int i = 0; i < p; ++i)
  {
    modinv_vec.at(i) = modinv(i + 1, mod);
  }
  for (int i = 0; i < p; ++i)
  {
    ans *= (n - i) % mod;
    ans %= mod;
  }
  for (int i = 0; i < p; ++i)
  {
    ans = (ans * modinv_vec.at(i)) % mod;
  }
  return ans;
}

int main()
{
  int X, Y;
  cin >> X >> Y;
  int XY_sum = X + Y;
  if (XY_sum % 3 != 0)
  {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 0; i < XY_sum / 3 + 1; ++i)
  {
    int to_x = i, to_y = XY_sum / 3 - i;
    int test_x = XY_sum / 3 + to_x, test_y = XY_sum / 3 + to_y;
    if (test_x == X && test_y == Y)
    {
      cout << combination(XY_sum / 3, to_x) << endl;
      return 0;
    }
  }
  cout << 0 << endl;
}


Measured memory_bytes: 2816