akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
#include <stack>
#include <iomanip>
#include <limits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;
using edge= struct{int to;ll cost;};

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

typedef priority_queue<ll> PQ_HIGH;
typedef priority_queue<ll,VL,greater<ll>> PQ_LOW;

#define EPSILON 1.0e-12

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
};
//降順
bool compare_by_b_high(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first < b.first;
    }
};
bool compare_by_b_higheer(tuple<string, int, int> a, tuple<string, int, int> b) {
    if(get<0>(a) != get<0>(b)){
      return get<0>(a) <get<0>(b);
    }else{
        if(get<1>(a) != get<1>(b)){return get<1>(a) > get<1>(b);}
        else{return get<2>(a) > get<2>(b);}
    }
};


int main(){
  double a,b,h;cin>>a>>b>>h;
  cout<<setprecision(15)<<(a+b)*h/2<<endl;
}

Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	tmp = input[0].split(" ");
	
	var maxX = parseInt(tmp[0], 10);
	var minX = 0;
	var maxY = parseInt(tmp[1], 10);
	var minY = 0;
	
	for(var i = 1;i < input.length;i++){
		tmp = input[i].split(" ");
		if(tmp[2] == 1){
			if(minX < parseInt(tmp[0], 10)){
				minX = parseInt(tmp[0], 10);
			}
		} else if(tmp[2] == 2){
			if(maxX > parseInt(tmp[0], 10)){
				maxX = parseInt(tmp[0], 10);
			}
		}  else if(tmp[2] == 3){
			if(minY < parseInt(tmp[1], 10)){
				minY = parseInt(tmp[1], 10);
			}
		}   else if(tmp[2] == 4){
			if(maxY > parseInt(tmp[1], 10)){
				maxY = parseInt(tmp[1], 10);
			}
		} 
	}
	
	if((maxX - minX)  < 1 || (maxY - minY) < 1){
		console.log(0);
	} else {
		console.log((maxX - minX) *(maxY - minY));
	}
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
const ll MAX_NUM = 1000000000000001;

int main(){
    ll N;
    cin >> N;
    ll tmp_N = N;
    deque<char> ans;
    while (tmp_N > 0) {
        ll mod = tmp_N % 26;
        if (mod == 0) {
            ans.push_back(122);
            tmp_N -= 26;
            tmp_N /= 26;
        } else {
            ans.push_back(96 + mod);
            tmp_N /= 26;
        }
    }
    while (!ans.empty()) {
        char tmp = ans.back();
        ans.pop_back();
        cout << tmp;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3628
n, k = map(int, input().split())
n += 1
MOD = 10 ** 9 + 7

ans = 0
for i in range(k, n + 1):

    sum_min =  (i - 1) * (i) // 2
    sum_max = i * (2*n - i - 1) // 2
    ans += sum_max - sum_min + 1
    ans %= MOD
print(ans)

    

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

int main(){
	int n;
	while( cin >> n , n ){
		int ans = 0;
		for(int a = 0 ; a <= n ; a++ ){
			if( n < a * a ) break;

			for(int b = a ; b <= n ; b++ ){
				if( n < a * a + b * b ) break;
				
				for(int c = b ; c <= n ; c++ ){
					if( n < a * a + b * b + c * c ) break;
					
					for(int d = c ; d <= n ; d++ ){
						if( n < a * a + b * b + c * c + d * d ) break;
						
						if( a * a + b * b + c * c + d * d == n ){
							ans++;
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0)
//#define MULTI_TEST
//#define GOOGLE
#ifdef LOCAL
#include "debugger.h"
#else
#define db(...)
#endif
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
const ll MOD = 1e9 + 7;
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }

const int N = 2005;
ll dp[N][N];

ll go(int n, vector<p64> &arr)
{
	for (int i = 1; i < n + 1; i++)
		for (int j = i - 1; j > 0; j--)
			dp[i][j] = 0;
	for (int i = n; i >= 1; i--)
	{
		for (int j = i; j < n + 1; j++)
		{
			int idx = n - (j - i + 1) + 1;
			dp[i][j] = arr[idx].fi * abs(arr[idx].se - i) + dp[i + 1][j];
			dp[i][j] = max(dp[i][j], arr[idx].fi * abs(j - arr[idx].se) + dp[i][j - 1]);
		}
	}
	return dp[1][n];
}

void solve()
{
	int n;
	cin >> n;
	vector<p64> arr(n + 1);
	for (int i = 1; i < n + 1; i++)
		cin >> arr[i].fi, arr[i].se = i;
	sort(arr.begin(), arr.end());
	reverse(arr.begin() + 1, arr.end());
	db(arr);
	memset(dp, -1, sizeof(dp));
	cout << go(n, arr) << ln;
	return;
}

int main()
{
	FASTIO;
	int t = 1;
#ifdef LOCAL
	clock_t start, stop;
	start = clock();
#endif
#ifdef MULTI_TEST
	cin >> t;
#endif
	for (int tc = 1; tc < t + 1; tc++)
	{
#ifdef GOOGLE
		cout << "Case #" << tc << ": ";
#endif
		solve();
	}
#ifdef LOCAL
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 35024
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
if b-a<=k and c-b<=k and d-c<=k and e-d<=k and c-a<=k and d-a<=k and e-a<=k and d-b<=k and e-b<=k and e-c<=k:
    print("Yay!")
else:
    print(":(")

Measured memory_bytes: 61844
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;
LL dis1[N], dis2[N];
vector<pair<int, int>> vp1[N], vp2[N];
int vis[N];
void solve(int s, vector<pair<int, int>> vp[], LL dis[])
{
	memset(dis, 0x3f, sizeof(LL)*N);
	dis[s] = 0;
	typedef pair<LL, int> Node;
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	MEM(vis, 0);
	pq.push({ 0,s });
	while (!pq.empty())
	{
		int x;
		LL d;
		tie(d, x) = pq.top();
		pq.pop();
		if (vis[x]) continue;
		vis[x] = 1;
		for (auto &p : vp[x])
		{
			int y, w;
			tie(y, w) = p;
			if (dis[y] > d + w)
			{
				dis[y] = d + w;
				pq.push({ dis[y],y });
			}
		}
	}
}
LL ans[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, m, s, t;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	while (m--)
	{
		int u, v, w1, w2;
		scanf("%d%d%d%d", &u, &v, &w1, &w2);
		vp1[u].push_back({ v,w1 });
		vp1[v].push_back({ u,w1 });
		vp2[u].push_back({ v,w2 });
		vp2[v].push_back({ u,w2 });
	}
	solve(s, vp1, dis1);
	solve(t, vp2, dis2);
	LL cur = INF * INF;
	for (int i = n; i >= 1; i--)
	{
		cur = min(cur, dis1[i] + dis2[i]);
		ans[i] = cur;
	}
	LL tot = 1e15;
	for (int i = 1; i <= n; i++) printf("%lld\n", tot - ans[i]);

	return 0;
}

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


def solve(X: int, Y: int):
    print(X + Y // 2)
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
s = list(input())
count = 0
list1 = []
for x in s:
  if x == 'A' or x == 'G' or x == 'T' or x == 'C':
    count = count + 1
  list1.append(count)
  if x != 'A' and x != 'G' and x != 'T' and x != 'C':
    count = 0
    

print(max(list1))

Measured memory_bytes: 9052
n=int(input())
h=list(map(int,input().split()))
dp=[float("inf")]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])

for i in range(n-2):
    dp[i+2]=min(dp[i]+abs(h[i]-h[i+2]),dp[i+1]+abs(h[i+1]-h[i+2]))

print(dp[-1])

Measured memory_bytes: 13928
//2718 ????????¨ ?¨???? ITP1_1c
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int a= sc.nextInt();
        int b= sc.nextInt();
        System.out.println(a*b+" "+(a+a+b+b));
    }
}

Measured memory_bytes: 17160
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
      	int K = sc.nextInt();
		int M = sc.nextInt();
        int nam = M-K;
        int ans = 0;
      
      if(nam>0){
        
        int[] p = new int[M];
        int[] mas = new int[M-1];

		for (int i=0;i<M;i++){p[i]=sc.nextInt();}
		Arrays.sort(p);
      
      	for(int i =0;i<M-1;i++){mas[i]=Math.abs(p[i+1]-p[i]);}
      	Arrays.sort(mas);
      
        for(int i=0;i<nam;i++){ans = ans+mas[i];}
		System.out.print(ans);

      }else{
        System.out.print(ans);
      }
	}
}

Measured memory_bytes: 50344
import sys

input = sys.stdin.readline


def main():
    S = list(input().strip())
    T = list(input().strip())

    S.sort()
    T.sort(reverse=True)

    for s, t in zip(S, T):
        if ord(t) > ord(s):
            print("Yes")
            return
        if ord(s) > ord(t):
            print("No")
            return
    else:
        if len(T) > len(S):
            print("Yes")
        else:
            print("No")



if __name__ == '__main__':
    main()



Measured memory_bytes: 3064
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
	
	Scanner stdIn = new Scanner(System.in);
	
	int ab = stdIn.nextInt();
	int bc = stdIn.nextInt();
	int ca = stdIn.nextInt();
	
	System.out.println(ab * bc / 2);
	
	}
}

Measured memory_bytes: 23124
#include <iostream>
using namespace std;
int main(void)
{
    int a, b;
    cin >> a >> b;
    if (a == b)
        cout << "a == b" << "\n";
    else if(a > b)
        cout << "a > b" << "\n";
    else
        cout << "a < b" << "\n";
    return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int R,G,B,N,count = 0;
    cin >> R >> G >> B >> N;
    REP(i,N/R+1){
        REP(j,(N-R*i)/B+1){
            if((N-(R*i+j*B))%G==0)count++;
        }
    }
    cout << count << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
  }
  sort(S.begin(), S.end());
  for (int i = 0; i < N; i++) cout << S.at(i);
  cout << endl;
}

Measured memory_bytes: 256
// =====================================================================================
//
//       Filename:  cp.cpp
//
//        Version:  1.0
//       Revision:  none
//       Compiler:  g++
//
//         Author:  Priyank Kumar Singh ()
//   Organization:  RVCE Bangalore
//
// =====================================================================================


#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define pb push_back
#define mp make_pair
#define F first
#define S second 
#define pl pair<long ,long >
#define pi pair<int ,int >
#define lb(v,x) lower_bound(v.begin(),v.end(),x)-v.begin();
#define ub(v,x) upper_bound(v.begin(),v.end(),x)-v.begin();
#define ct(i) cout<< i << "\n";
#define sv(v) sort(v.begin(),v.end());
#define mod 1000000007
#define M 100005
vector<int> s[10];
/*
void dfs(int i, int j){
    int c=s[i][j];
    if(i==n-1 && j==m-1 ){
        ans = min(ans, c);
        return;
    }
    
    if(j+1<m) dfs(i,j+1);
    c+=s[i][j];
    if(i+1<n) dfs(i+1,j);
    c+=s[i][j];
}
int c1=0;
*/


void answer(){
    ll n,m;
    cin>>n>>m;
    ll dp[n+1][m+1];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j]=0;
    dp[1][1]=1;
    char c;
    cin>>c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j==1 && i==1) continue;
            cin>>c;
            if(c=='.') dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
            else dp[i][j]=0;
        }
    }
    cout<<dp[n][m];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    int q;
    //cin>>q; while(q--)
        answer();

    return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <cmath>

using namespace std;

static const int MAX_N = 10000001;
bool P[MAX_N];

void prime();

int main(int argc, char** argv)
{
	prime();

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

		for(int i=n; i>=13; i--)
		{
			if(i%2==1)
			{
				if(P[i] && P[i-2] && P[i-6] && P[i-8])
				{
					cout << i << endl;
					break;
				}
			}
		}
	}
}

void prime()
{
	for(int i=0; i<MAX_N; i++)
	{
		P[i] = true;
	}

	int limit;
	limit = (int)sqrt((double)MAX_N);
	for(int i=2; i<=limit; i++)
	{
		if(P[i])
		{
			for(int j=(i<<2); j<=MAX_N; j+=i)
			{
				P[j] = false;
			}
		}
	}
}

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

int n, m;
long long x[100010], weight[100010];
int ans[100010], cand[100010];
class Edge{
public:
	long long cost;
	int from, to, num;
	Edge(long long c, int f, int t, int n){
		cost = c;
		from = f;
		to = t;
		num = n;
	}
};
typedef vector<Edge> Edges;
Edges all;
typedef vector<Edges> Graph;
void readGraph(Graph &g, int E, bool D, bool C){ // E:NumofEdges, D:Directed, C:Costed
	for(int i=0; i<E; ++i){
		Edge e(0, 0, 0, i);
		if(!C) cin >> e.from >> e.to;
		else cin >> e.from >> e.to >> e.cost;
		g[e.from].push_back(e);
		all.push_back(e);
		if(!D){
			swap(e.from, e.to);
			g[e.from].push_back(e);
		}
	}
}
bool operator < (const Edge &e, const Edge &f){
	return e.cost != f.cost ? e.cost < f.cost : e.from != f.from ? e.from < f.from : e.to < f.to;
}
class UnionFind{
public:
	vector<int> Parent;
	vector<int> Rank;
	UnionFind(int n){
		++n;
		Parent.resize(n, 0);
		Rank.resize(n, 0);
		for(int i=0; i<n; ++i)
			Parent[i] = i;
	}

	int find(int x){
		if(Parent[x] == x) return x;
		return Parent[x] = find(Parent[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(Rank[x] < Rank[y]){
			Parent[x] = y;
			weight[y] += weight[x];
			weight[x] = 0;
		}
		else{
			Parent[y] = x;
			weight[x] += weight[y];
			weight[y] = 0;
			if(Rank[x] == Rank[y]) ++Rank[x];
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0; i<n; ++i){
		cin >> x[i+1];
		weight[i+1] = x[i+1];
	}
	Graph g(n+1);
	readGraph(g, m, false, true);
	sort(all.begin(), all.end());
//	for(int i=0; i<m; ++i) cout << all[i].from << " " << all[i].to << "\n";
	UnionFind uf(n);
	for(int i=0; i<m; ++i){
		int a = all[i].from;
		int b = all[i].to;
		a = uf.find(a);
		b = uf.find(b);
//		cout << i << " " << a << " " << b << " " << weight[a] << " " << weight[b] << " " << all[i].cost << "\n";
		if((a == b && weight[a] >= all[i].cost) || (a != b && weight[a] + weight[b] >= all[i].cost)) cand[all[i].num] = 1;
		uf.unite(a, b);
	}
//	for(int i=0; i<m; ++i) cout << i << " " << cand[i] << "\n";
	for(int i=m-1; i>=0; --i){
		if(ans[all[i].num] == 1 || cand[all[i].num] == 0) continue;
		ans[all[i].num] = 1;
		queue<int> q;
		q.push(all[i].from);
		q.push(all[i].to);
		while(!q.empty()){
			int p = q.front();
			q.pop();
			for(int j=0; j<g[p].size(); ++j){
				if(ans[g[p][j].num] == 0 && g[p][j].cost <= all[i].cost){
					ans[g[p][j].num] = 1;
//					cout << all[i].from << " " << all[i].to << " " << g[p][j].from << " " << g[p][j].to << "\n";
					q.push(g[p][j].to);
				}
			}
		}
	}
//	for(int i=0; i<m; ++i) cout << i << " " << ans[i] << "\n";
	int tmp = 0;
	for(int i=0; i<m; ++i) tmp += ans[i];
	cout << m - tmp << "\n";
}

Measured memory_bytes: 15408
<?php
$s = str();
echo str_replace("?", "D", $s);

function str(){return trim(fgets(STDIN));}
function ints($n = false){
  if($n===false){
    return array_map('intval',explode(' ',trim(fgets(STDIN))));
  }else{$ret = [];for($i = 0; $i < $n; $i++)foreach(array_map('intval',explode(' ',trim(fgets(STDIN)))) as $j => $v)$ret[$j][] = $v;return $ret;}
}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function o(...$val){
    if(count($val)==1)$val=array_shift($val);
    echo debug_backtrace()[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0)echo "empty array";
        elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
        else{
            echo "array:array\n";
            if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
            else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
        }
    }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

function dfs($current, $from = -1, $d = 0){
  global $G, $distance;
  $distance[$current] = $d;
  foreach($G[$current] as $to){
    if($from != $to){
      dfs($to, $current, $d + 1);
    }
  }
}

function loadTree($N = false){
  if($N === false)$N = $GLOBALS['N'];
  return loadGraph($N, $N-1);
}
function loadGraph($N = false, $M = false, $both = true){
  if($N === false)$N = $GLOBALS['N'];
  if($M === false)$M = $GLOBALS['M'];
  $G = array_fill(1, $N, []);
  for($i = 0; $i < $M; $i++){
    $values = ints();
    if(count($values) == 2){
      list($a, $b) = $values;
      if($both == 0){
        $G[$a][] = $b;
      }elseif($both == 1){
        $G[$a][] = $b;
        $G[$b][] = $a;
      }else{
        $G[$b][] = $a;
      }
    }else{
      list($a, $b, $d) = $values;
      if($both == 0){
        $G[$a][] = [$b, $d];
      }elseif($both == 1){
        $G[$a][] = [$b, $d];
        $G[$b][] = [$a, $d];
      }else{
        $G[$b][] = [$a, $d];
      }
    }
  }
  return $G;
}


Measured memory_bytes: 16544
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  double A, B, H, M; cin >> A >> B >> H >> M;
  double H2 = H / 12;
  double M2 = M / 60;

  double th_h = 2 * M_PI * (H2 + M2/12);
  double th_m = 2 * M_PI * M2;
  double th = abs(th_h - th_m);

  double C2 = A * A + B * B - 2 * A * B * cos(th);
  printf("%.20f\n", sqrt(C2));
}


Measured memory_bytes: 4120
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory>

using namespace std;
typedef long long LL;
const int maxn = 200005;
const int mod = 1e9+7;

int fac[maxn],inc[maxn];
int fpm(LL p,LL k) {
	LL res=1ll;
	while (k) {
		if (k&1) (res*=p)%=mod;
		(p*=p)%=mod;k>>=1;
	}
	return res;
}
int w[maxn],c[maxn],X,Y,n,sum,mw[maxn],o,p,par[maxn],sz[maxn];
int findp(int t) {return par[t]?par[t]=findp(par[t]):t;}
void merge(int u,int v) {u=findp(u);v=findp(v);u!=v?par[u]=v:0;}
int main()
{
	#ifdef Amberframe
		freopen("agc012d.in","r",stdin);
		freopen("agc012d.out","w",stdout);
	#endif
	scanf("%d %d %d",&n,&X,&Y);
	for (int i=1;i<=n;i++)
		scanf("%d %d",&c[i],&w[i]);
	for (int i=1;i<=n;i++)
		if (!o||w[i]<w[o]) o=i;
	for (int i=1;i<=n;i++)
		if ((!p||w[i]<w[p])&&c[i]!=c[o]) p=i;
	for (int i=1;i<=n;i++)
		if (!mw[c[i]]||w[mw[c[i]]]>w[i]) mw[c[i]]=i;
	for (int i=1;i<=n;i++)
	{
		if (c[i]!=c[p]&&w[i]+w[p]<=Y) merge(i,p);
		if (c[i]!=c[o]&&w[i]+w[o]<=Y) merge(i,o);
		if (w[mw[c[i]]]+w[i]<=X) merge(mw[c[i]],i);
	}
	fac[0]=inc[0]=1;int ans=1;
	for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%mod;
	inc[n]=fpm(fac[n],mod-2);
	for (int i=n;i>=2;i--) inc[i-1]=(LL)inc[i]*i%mod;
	for (int i=1;i<=n;i++) if (findp(i)==findp(o)) sz[c[i]]++,sum++;
	for (int i=1;i<=n;i++) ans=(LL)ans*inc[sz[i]]%mod;
	printf("%d",(LL)ans*fac[sum]%mod);
	return 0;
}

Measured memory_bytes: 6528
# -*- coding: utf-8 -*-
import itertools

N = int(input())
S = []
match_char = ['M','A','R','C','H']

for i in range(N):
    S.append(input())

S_dict = {}
for c in match_char:
    S_dict[c] = 0

for Si in S:
    if Si[0] in match_char:
        S_dict[Si[0]] += 1

ans = 0
for (a,b,c) in itertools.combinations(match_char, 3):
    ans += S_dict[a] * S_dict[b] * S_dict[c]

print(ans)


Measured memory_bytes: 9784
#include <bits/stdc++.h>
#define  rep(i,n) for(li i=0;i<(n);i++)
#define  red(i,n) for(li i=(n)-1;i>=0;i--)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a) 
using namespace std;
using li = long long;
using ul = unsigned long long;
using vi = vector<li>;
using vs = vector<string>;
inline ul gcd(ul a,ul b) { return b?gcd(b,a%b):a; }


int main()
{
    li n,a;
    vi d;
    cin>>n;
    map<li,li> q;
    rep(i,n){
        cin>>a;
        q[a]++;
    }
    for(auto z:q) if(z.second>=2) d.pb(z.first);
    if(d.size()==0) cout<<0<<endl,exit(0); 
    sort(all(d));
    reverse(all(d));
    if(q[d[0]]>=4)cout<<d[0]*d[0]<<endl,exit(0);
    if(d.size()<2) cout<<0<<endl,exit(0); 
    cout<<d[0]*d[1]<<endl;
    
    return 0;
}


Measured memory_bytes: 6528
N = int(input())
A = list(map(int, input().split()))

L = [(1000, 0)] # Money, Stock;

for i in range(N):
  L2 = []
  for x in L:
    # Stay
    L2.append(x)
    # Buy
    if x[0] >= A[i]:
      L2.append( (x[0] % A[i], x[1] + x[0] // A[i] ) )
    # Sell
    if x[1] > 0:
      L2.append( (x[0] + x[1] * A[i], 0) )
  #print("L2", L2)
  
  #Pick Up Usefull Pair:
  L = []
  for x in range(len(L2)):
    for y in range(len(L2)):
      if y == x:
        continue
      ok = True
      if (L2[x][0] < L2[y][0] and L2[x][1] < L2[y][1] or 
          L2[x][0] == L2[y][0] and L2[x][1] < L2[y][1] or 
          L2[x][0] < L2[y][0] and L2[x][1] == L2[y][1] or 
          L2[x][0] == L2[y][0] and L2[x][1] == L2[y][1] and x > y):
        ok = False
        break
    if ok:
      L.append(L2[x])
  #print("L", L)
  
  
ans = 0
for i in L:
  ans = max(ans, i[0])
print(ans)

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



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

int main(){
	int H,W;
	bool ok=true;
	cin >> H >> W;
	int A[H][W];
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			char ch;
			cin >> ch;
			if(ch=='#') A[i][j]=1;
			else A[i][j]=0;
		}
	}
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			int ny=i+dy[0],nx=j+dx[0];
			int ny2=i+dy[1],nx2=j+dx[1];
			
			if(ny<0 || ny>=H || nx<0 || nx>=W)
				continue;
			if(ny2<0 || ny2>=H || nx2<0 || nx2>=W)
				continue;
			
			if(A[ny][nx]==1&&A[ny2][nx2]==1) ok=false;
		}
	}
	
	cout << (ok?"Possible":"Impossible") << endl;

	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

B = [0]*N

for i in range(N-1):
    if A[i] > A[i+1]:
        B[i+1] = A[i] - A[i+1]
        A[i+1] = A[i]

ans = sum(B)
print(ans)

Measured memory_bytes: 32324
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long calcComb(int n, int k) {
    if(n < k)
        return 0;
    if(n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    // 1からnまでの数字+1
    set<int> s;
    map<int, int> pos;
    pair<int, int> target;
    REP(i, n + 1) {
        cin >> a[i];
        if(s.count(a[i]) == 0) {
            s.insert(a[i]);
        } else {
            target = make_pair(pos[a[i]], i);
        }
        pos[a[i]] = i;
    }
    COMinit();
    // cout << "target.first" << target.first << " traget.second " <<
    // target.second
    //  << endl;
    // http://tutuz.hateblo.jp/entry/2018/08/03/082509
    //同じ数字はちょうど1組
    //重複するのはどちらから選んでいるかわからないとき
    //重複するのが一つ含まれていて
    //最も左よりもひだりと最も右よりも右のもの詰まる
    // l-1+n-r C k-1

    for(int k = 1; k <= n + 1; k++) {
        ll all = calcComb(n + 1, k);
        if(target.first > target.second) {
            cout << "WA" << endl;
            return -1;
        }
        ll sub = calcComb(n - target.second + target.first, k - 1);
        // cout << "-----------------" << endl;
        // cout << n - target.second + target.first << " " << k - 1 << endl;
        // cout << all << " " << sub << endl;
        ll ans = all - sub + MOD;
        ans %= MOD;
        cout << ans << endl;
    }
}

Measured memory_bytes: 23296
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)

    A.sort(reverse=True)
    ans = A[0] + 2*sum(A[1:(N-1)//2+1])
    if N % 2:
        ans -= A[(N-1)//2]

    print(ans)

if __name__ == "__main__":
    resolve()


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

int gcd (int x, int y){
    int r;
    if ( x < y)
        swap (x , y);
    while ( y > 0){
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}
int main(){
    long long a, b;
    long long c, d;
    cin >> a >> b >> c >> d;

    long long g = gcd ( c, d);

    unsigned long long cd = c * d / g;

    long long nc = b / c - (a - 1) / c;
    long long nd = b / d - (a - 1) / d;
    long long ncd = b / cd - (a - 1) / cd;

    cout << b - a + 1 - nc - nd + ncd << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int main() {
	int n, count = 0;
	cin >> n;
	vector<int>l(n);
	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}
	sort(l.begin(), l.end());
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				if (l[i]<l[j] + l[k] && l[j]<l[k] + l[i] && l[k]<l[j] + l[i]) {
					count++;
				}
			}
		}
	}
	cout << count << endl;

}

Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

void main() {
    while(true) {
        int[] N = readln.chomp.to!(char[]).map!(a=>(a-'0').to!int).array;
        if (N==[0, 0, 0, 0]) break;

        if (N[0]==N[1] && N[1]==N[2] && N[2]==N[3]) {
            writeln("NA");
            continue;
        }

        int cnt = 0;
        while(N!=[6, 1, 7, 4]) {
            int[] L = N.sort!("a>b").array;
            int[] S = N.sort!("a<b").array;
            N = subtract(L, S);
            cnt++;
        }
        cnt.writeln;
    }
}
int[] subtract(int[] a, int[] b) {
    string num = (a.to!(string[]).reduce!((a,b)=>a~b).to!int - b.to!(string[]).reduce!((a,b)=>a~b).to!int).to!string;
    while(num.length<4) {
        num = "0"~num;
    }
    return num.to!(char[]).map!(a=>(a-'0').to!int).array;
}

Measured memory_bytes: 3164
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 20202;
int p[N] , n , a[N] , b[N];

int main(){
    cin >> n;
    rep(i,1,n+1) cin >> p[i];
    rep(i,1,n+1) a[i] = i * 22000;
    rep(i,1,n+1) b[n-i+1] = i * 22000;
    rep(i,1,n+1) b[p[i]]-=n-i;
    rep(i,1,n+1) cout << a[i] << " \n"[i==n];
    rep(i,1,n+1) cout << b[i] << " \n"[i==n];
    return 0;
}


Measured memory_bytes: 896
#include<iostream>
using namespace std;
int main(){
	int x,y,t;
	while(1){
		cin >> x >> y;
		if(x==0&&y==0) break;
		if(x>y){
			t=x;
			x=y;
			y=t;
		}
		cout << x << " " << y << endl;
	}
	return 0;
}


Measured memory_bytes: 3016
import math
cos60 = math.cos(60/180*math.pi)
sin60 = math.sin(60/180*math.pi)
class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __repr__(self):
        return str(self.x) + " " + str(self.y)
        

def koch(n, p1, p2):
    if(n==0):
        return
    s = Point((2* p1.x + p2.x)/3, (2* p1.y + 1*p2.y)/3)
    
    t = Point((p1.x + 2* p2.x)/3, (p1.y + 2* p2.y)/3)
    
    u = Point((t.x - s.x)* cos60 - (t.y -s.y)* sin60 + s.x,
             (t.x - s.x)* sin60 + (t.y -s.y)* cos60 + s.y)
    
    koch(n-1, p1, s)
    print(s)
    koch(n-1, s, u)
    print(u)
    koch(n-1, u, t)
    print(t)
    koch(n-1, t, p2)

p1 = Point(0,0)
p2 = Point(100,0)
n = int(input())
print(p1)
koch(n, p1, p2)
print(p2)


Measured memory_bytes: 5740
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(ll i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<ll, ll>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};

template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};



int main(){
    ll q;
    cin >> q;
    BIT<ll> bit(q);
    vector<ll> a;
    vector<ll> b;
    vector<bool> out(q);

    rep(i, q) {
        ll id = 0;
        cin >> id;
        if (id==1) {
            ll ia, ib;
            cin >> ia >> ib;
            a.push_back(ia);
            if (b.size()==0) {
                b.push_back(ib);
            }
            else {
                b.push_back(b.back()+ib);
            }
        }
        if (id==2) {
            out[i] = true;
        }
    }

    map<ll, ll> mp;
    for (ll e: a) {
        mp[e] = 0;
    }
    ll xx = 0;
    vector<ll> ra;
    for (auto& m: mp) {
        m.second = xx;
        xx++;
    }
    for (ll e: a) {
        ra.push_back(mp[e]);
    }
    ll index = 0;
    
    vector<ll> aa;
    for (auto m: mp) {
        aa.push_back(m.first);
    }
    /*
    vector<ll> suma;
    for (ll e: a) {
        if (suma.size()==0) suma.push_back(e);
        else suma.push_back(suma.back()+e);
    }
    ll sa = suma.size();
    */
    BIT<ll> bit2(q);
    ll sa = a.size();

    rep(i, q) {
        if (!out[i]) {
            bit.add(ra[index]);
            bit2.add(ra[index], a[index]);
            index++;
        }
        else {
            ll l = -1;
            ll r = q-1;
            ll threshold = (index+1)/2;
            while (r-l>1) {
                ll x = (l+r)/2;
                if (bit.sum(x)<threshold) l = x;
                else r = x;
            }
            ll ans = b[index-1];
            //debug(ans);
            ans += abs(bit2.sum(r)-aa[r]*bit.sum(r));
            //debug(bit2.sum(r));
            //debug(r);
            //debug(ans);
            ans += abs((bit2.sum(sa-1)-bit2.sum(r))-aa[r]*(bit.sum(sa-1)-bit.sum(r)));
            //debug(ans);
            
            cout << aa[r] << " " << ans << endl;
        }
    }


    return 0;
}


Measured memory_bytes: 15212
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)();
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
typedef priority_queue<string> priquestring;
typedef priority_queue<int> priqueint;
typedef priority_queue<ll> priquell;
typedef priority_queue<char> priquechar;
typedef priority_queue<string,vector<string>,greater<string>> rpriquestring;
typedef priority_queue<int,vector<int>,greater<int>> rpriqueint;
typedef priority_queue<ll,vector<ll>,greater<ll>> rpriquell;
typedef priority_queue<char,vector<char>,greater<char>> rpriquechar;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}

const ll big=1000000007;
int exp(int x,int y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (exp(x,y-1)*x)%big;
    int t=exp(x,y/2);
    return (t*t)%big;
}
void chmin(ll a,ll b){
    if(a>b)a=b;
    return;
}

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


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/
    
    ll k;string s;cin >> s >> k;
    //aba →k-1
    //端から連続しないor端どうしが別々の部分:/2
    //端から連続しかつ端どうしが同じ:k-1回は和を/2
    //　　　　　　　　　　　　　　　 あとはそれぞれで/2
    if(s[0]!=s[(int)s.size()-1]){
        ll cnt=0;
        rep(i,s.size()-1){
            if(s[i]==s[i+1]){cnt++;i++;}
        }
        cout << cnt*k << '\n';
        return 0;
    }else{
        bool ok=true;
        ll frt=1;ll bck=1;
        ll in=0;
        rep(i,s.size()-1){
            if(s[i]==s[i+1]&&ok)frt++;
            else ok=false;
            if(!ok&&s[i]==s[i+1]){
                in++;
                i++;
            }
        }
        for(int j=s.size()-1;j>0;j--){
            if(s[j]==s[j-1])bck++;
            else break;
        }
        if(frt==(int)s.size()){
            cout << (ll)s.size()*k/2 << endl;
            return 0;
        }
        
        in-=bck/2;
        ll ans=k*in;
        ans+=((frt+bck)/2)*(k-1);
        ans+=frt/2+bck/2;
        cout << ans << '\n';
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

double ESP = 1e-10;

struct point {
  double x, y;
};

int main() {
  int n;
  point P[4];

  cin >> n;
  while(n--){
    for(int i = 0; i < 4; i++){
      cin >> P[i].x >> P[i].y;
    }

    if(abs((P[1].y - P[0].y)*(P[3].x - P[2].x) - (P[3].y - P[2].y)*(P[1].x - P[0].x)) < ESP) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }

    return 0;
}

Measured memory_bytes: 3220
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

times = 0
for i in range(n):
    minj = i
    for j in range(i,n):
        if A[j] < A[minj]:
            minj = j
    if i != minj:
        A[i], A[minj] = A[minj], A[i]
        times += 1

B = " ".join([str(num) for num in A])
print(B)
print(times)



Measured memory_bytes: 5604
a, b, c, k = map(int, input().split(" "))

def some(a,b,c,k):
    x_a = min(k, a)
    k -= x_a
    x_b = min(k, b)
    k -= x_b
    x_c = k
    print(x_a*1+x_b*0+x_c*-1)

some(a,b,c,k)

Measured memory_bytes: 9132
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1000000007;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int dyy[]={0,-1,0,1};
int dxx[]={-1,0,1,0};

/*#define int ll*/
signed main(){
    ll n,m;
    cin>>n>>m;
    ll cnts=0,cntc=0;
    cnts=n;
    cntc=m-2*cnts;
    if(cnts>=m/2)cout<<m/2<<endl;
    else{
        ll x=cntc/4;
        cout<<cnts+x<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    ll N,M;cin >> N >> M;
    vector<pll> A(N);
    rep(i,N){
        cin >> A[i].F;
        A[i].S = i;
    }
    priority_queue<pll> pque;
    vector<ll> Ac(N,0);
    rep(i,N)pque.push(A[i]);
    pll tmp;
    rep(i,M){
        tmp = pque.top();
        pque.pop();
        Ac[tmp.S]++;    // 割引回数カウント
        tmp.F = (tmp.F)/2;
        pque.push(tmp);
    }
    LL ans = 0;
    rep(i,N){
        int ct = Ac[i];
        LL tm = A[i].F;
        rep(i,ct)tm /= 2;
        ans += tm;
    }
    cout << ans << endl;
}



Measured memory_bytes: 4724
H, W = map(int, input().split())

X = [[0] * W for i in range(H)]
G = [[0,0] for i in range(W*H)] 
L = [[-1] * W for i in range(H)] # Group ID

for i in range(H):
    s = input()
    for j in range(W):
        if (i+j) % 2 == 0:
            if s[j] == "#":
                X[i][j] = 1
        else:
            if s[j] != "#":
                X[i][j] = 1



g = -1
for i in range(H):
    for j in range(W):
        if L[i][j] < 0:
            g += 1
            L[i][j] = g
            post = [[i,j]]
            G[g][(i+j)%2] += 1
            while post:
                pre = post
                post = []
                for ggg in pre:
                    i0, j0 = ggg
                    if i0>0 and L[i0-1][j0] < 0 and X[i0][j0] == X[i0-1][j0]:
                        post.append([i0-1,j0])
                        L[i0-1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if i0<H-1 and L[i0+1][j0] < 0 and X[i0][j0] == X[i0+1][j0]:
                        post.append([i0+1,j0])
                        L[i0+1][j0] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0>0 and L[i0][j0-1] < 0 and X[i0][j0] == X[i0][j0-1]:
                        post.append([i0,j0-1])
                        L[i0][j0-1] = g
                        G[g][(i0+j0+1)%2] += 1
                    if j0<W-1 and L[i0][j0+1] < 0 and X[i0][j0] == X[i0][j0+1]:
                        post.append([i0,j0+1])
                        L[i0][j0+1] = g
                        G[g][(i0+j0+1)%2] += 1
                        
            # print(GGG)
# print(G)
ans = 0
for t in G:
    aa, bb = t
    ans += aa * bb
    
print(ans)


Measured memory_bytes: 97140
/**

author:	©LoneWolfDON
Git: MahinHossainMunna

**/
/*

*/

#include <stdio.h>
#include <math.h>

int main()
{
    float R;

    scanf("%f", &R);

    float pi = 3.1416;

    printf("%f", 2*pi*R); //circumference = 2*pi*R

    return 0;
}

Measured memory_bytes: 1740
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		HashSet<String> set = new HashSet<>();

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {
			String prize = sc.next();
			set.add(prize);
		}
		sc.close();

		print(set.size());
	}

	public static void print(Object obj) {
		System.out.println(obj);
	}

}


Measured memory_bytes: 77332
#include<stdio.h>
#include<string.h>
#define MX 200009
char A[MX];
int main() {
	scanf("%s", &A);
	int len = strlen(A), cnt = 0;
	for (int i = 0; i < len; i++) {
		cnt += (A[i] - '0');
	}
	printf("%s", cnt % 9 == 0 ? "Yes" : "No");
}

Measured memory_bytes: 1860
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int left = 0, right = n-1;
    bool left_male;
    cout << 0 << endl;
    string ret;
    cin >> ret;
    if (ret == "Vacant") return 0;
    if (ret == "Male") left_male = true;
    else left_male = false;
    while (right - left > 3) {
        int mid = (left + right) / 2;
        if ((mid - left) % 2 == 1) mid++;
        cout << mid << endl;
        cin >> ret;
        if (ret == "Vacant") return 0;
        if ((ret == "Male") == left_male) left = mid;
        else right = mid - 1;
    }
    do { cout << left++ << endl; cin >> ret; } while (ret != "Vacant");
}


Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
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();}
template<class T> inline T sqr(T x) {return x*x;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long ll;
#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 SORT(v, n) sort(v, v+n)
#define VSORT(v) sort(v.begin(), v.end())
#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 INF 999999999
const double EPS = 1e-10;
const double PI  = acos(-1.0);
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    string s,t;
    cin >> s >>t;
    cout << t << s<<endl;
    return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T iabs(const T& x) { return max(x, -x); }
// #define abs gabs


int main() {

    char c;
    cin >> c;
    cout << char(c + 1) << endl;
    return 0;
}

Measured memory_bytes: 760
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
int main()
{
    stack<char>op;
    stack<char>st;
    string s;
    cin>>s;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='B')
        {
            if(!st.empty())
                st.pop();
        }
        else
            st.push(s[i]);
    }
    while(!st.empty())
    {
        op.push(st.top());
        st.pop();
    }
    while(!op.empty()){
        cout<<op.top();
        op.pop();
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
<?php
$N = (int)fgets(STDIN);

$A = array();
for($i = 0; $i < $N; $i++) {
  $in = (int)fgets(STDIN);
  if (!in_array($in, $A)) {
    array_push($A, $in);
  }
}

echo count($A);

?>


Measured memory_bytes: 3700
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007

using namespace std;

int main(void){
  int n,m;
  cin >> n >> m;
  int s[m][2];
  rep(i,m){
    cin >> s[i][0] >> s[i][1];
  }

  
  int ans = -1;
  int work = 1;
  rep(i,n-1) work *= 10;
  int end = work*10;
  if(n == 1) work = 0;
  for(int i=work;i<end;i++){
    bool flag = true;
    rep(j,m){
      int tmp = 1;
      rep(k,n-s[j][0])tmp *= 10;
      if((i%(tmp*10))/tmp != s[j][1])
	flag = false;
    }
    if(flag){
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  int N;
  ll x;
  cin >> N >> x;
  ll a[N];
  for(int i=0;i<N;i++) cin >> a[i];

  ll ans = 0LL;
  for(int i=0;i<N-1;i++){
    ll t = a[i] + a[i+1] - x;
    if(t <= 0) continue;

    if(t <= a[i+1]){
      a[i+1] -= t;
    } else {
      a[i+1] = 0;
      a[i] -= t - a[i+1];
    }

    ans += t;
  }

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

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>

#define ll long long 

using namespace std;

int n;
long double N[3000];
long double dp[3000][3000];
bool dpb[3000][3000];

long double solve(int p, int k){
  if(p >= n && k != 0)
    return 1;

  if(k == 0){
    if(p < n)
      return N[p] * solve(p+1, k);
    else
      return 1;
  }

  if(dpb[p][k])
    return dp[p][k];
  
  dpb[p][k] = 1;
  return dp[p][k] = (1-N[p]) * solve(p+1, k-1) + N[p] * solve(p+1, k);
} 

int main()
{
    cin >> n;

    memset(dpb, 0, sizeof dpb);

    for(int i = 0; i < n; i++)
      cin >> N[i];
    
    cout << setprecision(10) << fixed << solve(0, n/2) << endl;
    
    return 0;
}

Measured memory_bytes: 77348