akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  int x;
  cin >>x;
  if(x == 7 || x == 5 || x == 3){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}

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

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    static int Calc(int w, List<int[]> xs) { // [???????????????]
        var dp = new int[w+1];

        foreach (int[] x in xs) {
            if (x[1] > w) continue;

            for (int i = w - x[1]; i >= 0; i--) {
                if (dp[i] == 0) continue;

                dp[i + x[1]] = Math.Max(dp[i + x[1]], dp[i] + x[0]);
            }
            dp[x[1]] = Math.Max(dp[x[1]], x[0]);
        }
        return dp.Max();
    }

    static void Main() {
        var nw = ReadInts();
        int n = nw[0], w = nw[1];
        var xs = new List<int[]>();
        for (int i = 0; i < n; i++) {
            xs.Add(ReadInts());
        }
        Console.WriteLine(Calc(w, xs));
    }
}

Measured memory_bytes: 9720
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <limits>
#include <list>
#include <cassert>
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
#define pNO cout << "NO" << endl
#define pYES cout << "YES" << endl
#define endl "\n"
#define pi 3.14159265358979
using namespace std;
using ll = long long;
#define int ll
signed main() {
	int R, C, K; cin >> R >> C >> K;
	vector<vector<int>> valTable(R, vi(C));
	vector<vector<vector<int>>> dp(R, vvi(C, vi(4)));
	rep(i, K) {
		int r, c, v; cin >> r >> c >> v;
		--r; --c;
		valTable[r][c] = v;
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (i == 0 && j == 0) {
				dp[i][j][0] = 0;
				for (int num = 1; num < 4; num++) {
					dp[i][j][num] = valTable[i][j];
				}
			}
			else if (i == 0) {
				// j > 0
				dp[i][j][0] = dp[i][j - 1][0];
				for (int num = 1; num < 4; num++) {
					dp[i][j][num] = max({ dp[i][j][num],dp[i][j - 1][num],dp[i][j - 1][num - 1] + valTable[i][j] });
				}
			}
			else if (j == 0) {
				// i > 0
				dp[i][j][0] = dp[i - 1][j][3];
				for (int num = 1; num < 4; num++) {
					dp[i][j][num] = max({ dp[i][j][num],dp[i - 1][j][2] + valTable[i][j] });
				}
			}
			else {
				dp[i][j][0] = max({ dp[i][j][0],dp[i - 1][j][3],dp[i][j - 1][0] });
				for (int num = 1; num < 4; num++) {
					dp[i][j][num] = max({ dp[i][j][num],dp[i - 1][j][3]+ valTable[i][j],dp[i][j - 1][num],dp[i][j - 1][num - 1] + valTable[i][j] });
				}
			}
		}
	}
	cout << dp[R - 1][C - 1][3] << endl;
}

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

#define For(i,a,b) for(int (i) = (a);(i) < (b);i++)
#define Rep(i,n) For((i),0,(n))
#define All(a) (a).begin(),(a).end()
#define sp " "
#define INF 1e18
#define INT_INF 1e9

typedef long long ll;
const ll MOD = 1000000007;
const ll MOD_9 = 998244353;

vector<char> boin = {'a','i','u','e','o'};
vector<char> alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

int main(){
    char c;
    int n;
    cin >> c;
    n = c-'a';
    cout << alphabet[n+1] << endl;
    //cin >> c;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 23 09:58:39 2019

@author: Yamazaki Kenichi
"""

N = int(input())
ab = [list(map(int,input().split())) for i in range(N)]

ab.sort(key=lambda x: x[1])

time = 0
flg = True
for c in ab:
    time += c[0]
    if time > c[1]:
        flg = False
        break

if flg:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 53724
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

int main() {
	int N, i;
	long long K;
	long long c = 0;
	cin >> N >> K;
	struct pair {
		int a;
		int b;
	};
	vector<pair> pairs(N);
	for (i = 0; i < N; i++) {
		cin >> pairs[i].a >> pairs[i].b;
	}
	sort(pairs.begin(), pairs.end(), [](const pair& x, const pair& y) { return x.a < y.a; });
	for (i = 0; i < N; i++) {
		c += pairs[i].b;
		if (K <= c) {
			cout << pairs[i].a << endl;
			break;
		}
	}	
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
	char a[25];
	cin>>a;
	int i,la=strlen(a);
	for(i=la-1;i>=0;i--)
	{
		cout<<a[i];
	} 
	cout<<endl;
	return 0;
}



Measured memory_bytes: 3068
#include <cstdio>

int main(void)
{
    int m, f, r;
    char grade;
    while(1)
    {
        scanf("%d %d %d", &m, &f, &r);
        if((m == -1) && (f == -1) && (r == -1)) break;
        else if((m == -1) || ( f== -1)) grade = 'F';
        else if(m+f >= 80) grade = 'A';
        else if((m+f >= 65) && (m+f < 80)) grade = 'B';
        else if((m+f >= 50) && (m+f < 65)) grade ='C';
        else if((m+f >= 30) && (m+f < 50))
        {
            if(r >= 50) grade = 'C';
            else grade = 'D';
        }
        else if(m+f < 30) grade = 'F';
        printf("%c\n", grade);
    }

    return 0;
}


Measured memory_bytes: 2704
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

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

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

	int n;
	
	cin >> n;

	string s[n];
	map<char, ll> m;

	rep(i, n)
	{
		cin >> s[i];
		m[s[i][0]]++;
	}

	ll count = 0;
	ll m_c = m['M'];
	ll a_c = m['A'];
	ll r_c = m['R'];
	ll c_c = m['C'];
	ll h_c = m['H'];
	
	if (m_c > 0)
	{
		if (a_c > 0)
		{
			if (r_c > 0)
			{
				count += m_c * a_c * r_c;
			}

			if (c_c > 0)
			{
				count += m_c * a_c * c_c;
			}

			if (h_c > 0)
			{
				count += m_c * a_c * h_c;
			}
		}

		if (r_c)
		{
			if (c_c > 0)
			{
				count += m_c * r_c * c_c;
			}

			if (h_c > 0)
			{
				count += m_c * r_c * h_c;
			}
		}

		if (c_c)
		{
			if (h_c)
			{
				count += m_c * h_c * c_c;
			}
		}
	}

	if (a_c > 0)
	{
		if (r_c > 0)
		{
			if (c_c)
			{
				count += a_c * c_c * r_c;
			}
			if (h_c)
			{
				count += a_c * h_c * r_c;
			}
			
		}

		if (c_c > 0)
		{
			if (h_c)
			{
				count += h_c * a_c * c_c;
			}
			
		}

	}

	if (r_c)
	{
		if (c_c)
		{
			if (h_c)
			{
				count += r_c * c_c * h_c;
			}
		}
	}

	cout << count << endl;
	
	return 0;
}


Measured memory_bytes: 5760
//swaptwo.cpp
#include <bits/stdc++.h>
using namespace std;
int main (){
  int x, y, temp;
  cin >> x >> y;

  while (!((x == 0) && (y == 0))) {
    if (x > y) { temp = x; x = y; y = temp; }

    cout << x <<  " " << y << endl;
    cin >> x >> y;
  }
}



Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <functional>
#include <queue>
#include <map>
using namespace std;
typedef int W;

const W INF = 1LL << 28;

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

void dijkstra(int s, const Graph& G, vector<W>& d) {
	priority_queue< P, vector<P>, greater<P> > que;
	fill(d.begin(), d.end(), INF);
	d[s] = 0;
	que.push(P(0, s));
	while(!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for(int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

W wf[310][310];
string a[3000], b[3000];
W dist[3000];
string st_name[310];

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

	int N, M, cap;
	while(cin >> N >> M >> cap, N | M | cap) {
		map<string, int> city;
		string src, dst;
		cin >> src >> dst;
		city[src] = -1;
		city[dst] = -1;

		for(int i = 0; i < N; i++) {
			cin >> a[i] >> b[i] >> dist[i];
			city[a[i]] = -1;
			city[b[i]] = -1;
		}

		int C = 0;
		for(auto& p : city) {
			city[p.first] = C++;
		}

		map<string, int> station;
		for(int i = 0; i < M; i++) {
			cin >> st_name[i];
			station[st_name[i]] = i;
		}
		station[src] = M;
		station[dst] = M + 1;
		st_name[M] = src;
		st_name[M + 1] = dst;
		M += 2;

		for(int i = 0; i < M; i++)
			for(int j = 0; j < M; j++)
				wf[i][j] = i == j ? 0 : INF;

		Graph G(C);
		for(int i = 0; i < N; i++) {
			G[city[a[i]]].push_back(edge{ city[b[i]], dist[i] });
			G[city[b[i]]].push_back(edge{ city[a[i]], dist[i] });
		}

		vector<W> d(C);
		for(int i = 0; i < M; i++) {
			dijkstra(city[st_name[i]], G, d);
			for(int j = 0; j < M; j++) {
				if(i == j) continue;
				if(d[city[st_name[j]]] <= cap * 10) {
					wf[i][j] = wf[j][i] = d[city[st_name[j]]];
				}
			}
		}

		for(int k = 0; k < M; k++)
			for(int i = 0; i < M; i++)
				for(int j = 0; j < M; j++)
					wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);

		W ans = wf[station[src]][station[dst]];
		if(ans == INF) ans = -1;
		cout << ans << endl;
	}



}

Measured memory_bytes: 4576
#include<stdio.h>
#include<math.h>

int main(){
    int n, d;
    scanf("%d%d", &n, &d);
    double x[n][d];
    for(int i=0; i<n; i++){
        for(int j=0; j<d; j++){
            scanf("%lf", &x[i][j]);
        }
    }
    int c=0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            double len = 0;
            for(int k=0; k<d; k++){
                len += pow(x[i][k] - x[j][k], 2);
            }
            len = sqrt(len);
            while(len > 0){
                len -= 1.0;
            }
            if(len == 0){
                c++;
            }
        }
    }
    printf("%d", c);
    return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  double ans = 0;
  for (int i = 1; i < N + 1; i++) {
    int a = i;
    double b = 1;
    while(a < K) {
      a *= 2;
      b /= 2;
    }
    ans += b;
  }
  ans /= N;
  cout << fixed << setprecision(12) << ans << endl;
}

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

int main() {
  long double num,k;
  long double sum = 0;
  long double Pow;
  cin >> num >> k;
  
  for(int i = 1; i <= num; i++){
    Pow = 0;
    int index = i;
    while(index < k){
      Pow++;
      index *= 2;
    }

     sum += 1.0/num * 1/pow(2, Pow); 
  }
  
  cout << setprecision(16) << sum;
}


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

const int MAXN = 1e5+10;
const int M = 1e9+7;
vector<int> adj[MAXN];

ll n, k, ans = 1;
void dfs(int u,int p = -1, int op=0) {
  //cerr  << "AT " <<u <<" " << op <<endl;
  ans*=k-op;
  ans%=M;
  int d1 = 1+(p!=-1); // yourself, your parent
  for(int v:adj[u]) {
    if (v==p) continue;
    dfs(v,u,d1);
    d1++; 
  }
}

int main(){
  cin.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> k;
  for(int i=0;i<n-1;i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1);
  cout << ans <<endl;
}


Measured memory_bytes: 9216
def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0

a,b = map(int,input().split())
c,a,b = ex_euclid(a,b)
print(a,b)


Measured memory_bytes: 5600
H, W = map(int,input().split())
S = []
for _ in range(H):
    S.append(input())


yoko, tate = [], []
for h in range(H):
    now = []
    
    w, cnt = 0, 0
    while True:
        if not w < W:
            for _ in range(cnt): now.append(cnt) 
            break

        if S[h][w] == "#":
            for _ in range(cnt): now.append(cnt)
            now.append(0)
            cnt = 0
        else:
            cnt += 1

        w += 1

    yoko.append(now)

for w in range(W):
    now = []
    
    h, cnt = 0, 0
    while True:
        if not h < H:
            for _ in range(cnt): now.append(cnt) 
            break

        if S[h][w] == "#":
            for _ in range(cnt): now.append(cnt)
            now.append(0)
            cnt = 0
        else:
            cnt += 1

        h += 1
    
    tate.append(now)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, yoko[h][w]+tate[w][h]-1)
    
print(ans)

Measured memory_bytes: 145196
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define N 300005
#define vi vector<int>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
   int k;
   cin>>k;
   k--;
   cout<<a[k];

}


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

int main(){    
    int n;
    int a[200000], sa[200000];
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
        sa[i] = a[i];
    }
    sort(sa, sa+n);
    for(int i=0;i<n;i++){
        if(a[i] == sa[n-1]) cout << sa[n-2] << endl;
        else cout << sa[n-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;
 
P h[3000];
int main() {
    int n;
    while (scanf("%d", &n), n) {
        rep(i, n)scanf("%d%d", &h[i].first, &h[i].second);
        sort(h, h + n);
        int Max = 0;
        rep(i, n) {
            for (int j = i + 1; j < n; j++) {
                int x = h[j].first - h[i].first,
                    y = abs(h[j].second - h[i].second);
                if (!x)continue;
                P a = { h[i].first,h[i].second + x },
                    b = { h[j].first,h[j].second + x };
                if (h[i].second < h[j].second) {
                    a.first -= y; b.first -= y;
                }
                else {
                    a.first += y; b.first += y;
                }
                if (binary_search(h, h + n, a) && binary_search(h, h + n, b))
                    Max = max(Max, (x + y)*(x + y) - x*y * 2);
            }
        }
        printf("%d\n", Max);
    }
    return 0;
}

Measured memory_bytes: 3144
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	num, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return num
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	a := make([]int, n)
	for i := 1; i < n; i++ {
		manager := nextInt()
		a[manager-1]++
	}

	for i := 0; i < n; i++ {
		fmt.Println(a[i])
	}

}


Measured memory_bytes: 6208
/*  ex7_3
    yy8332  */

#include <stdio.h>
#include <stdlib.h>

int main(void){
  int height, width, i, j, k, num = 0;
  char **multi_array;

  //入力読み取り
  scanf("%d %d", &height, &width);

  //各行の配列へのポインタ分のメモリ領域を確保
  multi_array = (char**)calloc(height, sizeof(char*));
  if(multi_array == NULL){
      fprintf(stderr, "calloc error.\n");
      exit(1);
  }
  //各行の要素分のメモリ領域を確保
  for(i = 0; i < height; i++){
      multi_array[i] = (char*)calloc(width, sizeof(char));
      if(multi_array[i] == NULL){
          fprintf(stderr, "calloc error.\n");
          exit(1);
      }
  }

  for(i = 0; i < height; i++){
    for(j = 0; j < width; j++){
      scanf(" %c", &multi_array[i][j]);
    }
  }

  //横の操作
  for(i = 0; i < height; i++){

    for(j = 0; j < width; j++){
      if(multi_array[i][j] == '#'){
        num = 1;
      }
    }

    if(num == 0){
      height -= 1;
      for(k = i; k < height; k++){
        for(j = 0; j < width; j++){
          multi_array[k][j] = multi_array[k + 1][j];
        }
      }
      i -=1;
    }
    num = 0;
  }

  //縦の操作
  for(j = 0; j < width; j++){

    for(i = 0; i < height; i++){
      if(multi_array[i][j] == '#'){
        num = 1;
      }
    }

    if(num == 0){
      width -= 1;
      for(k = j; k < width; k++){
        for(i = 0; i < height; i++){
          multi_array[i][k] = multi_array[i][k + 1];
        }
      }
      j -=1;
    }
    num = 0;
  }


  //出力
  for(i = 0; i < height; i++){
    for(j = 0; j < width; j++){
      printf("%c", multi_array[i][j]);
    }
    printf("\n");
  }

  //メモリ領域の解放，各行の要素分の領域を開放し，
  //各行の配列へのポインタの領域を解放
  //（メモリ領域の確保と逆順）
  for(i = 0; i < height; i++){
      free(multi_array[i]);
  }
  free(multi_array);


  return 0;
}


Measured memory_bytes: 1676
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9) + 7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	int n; cin >> n;
	ll x; ll a[2000]; cin >> x;
	ll out = 0;
	rep(i, n) {
		cin >> a[i]; out += a[i];
	}
	Rep(i,1, n) {
		ll sum = (ll)i*x;
		ll memo = a[n - 1];
		per(j, n) {
			if (j == 0) {
				a[0] = min(a[0], memo); continue;
			}
			a[j] = min(a[j], a[j - 1]);
		}
		rep(j, n) {
			sum += a[j];
		}
		out = min(out, sum);
	}
	cout << out << endl;
	return 0;
}


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

int main()
{
	int a,b;
	cin>>a>>b;
	string s;
	cin>>s;
	if (s[a]!='-')
	{
		cout<<"No";
		return 0;
	}
	else 
	{
		for (int i=0; i<a; i++)
		if (!isdigit(s[i]))
		{
			cout<<"No";
			return 0;
		}
		for (int i=a+1; i<=a+b; i++)
		if (!isdigit(s[i]))
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 256
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define all(x) begin(x),end(x)
using namespace std;
const int INF = 1e9;
template<class T=int> using V = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const ll MOD = 10e9+7LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
//時間が厳しいとき使う
#define INI(...) int __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

void solve()
{
    IN(k);
    ll s = 0;
    reps(a, 1, k+1)
        reps(b, 1, k+1)
            reps(c, 1, k+1)
            {
                s += __gcd(__gcd(a, b), c);
            }
    cout << s << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
    }
}
ll COM(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;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
int main() {
    unordered_map<string,int> mp;
    int N=in();
    string a;
    REP(i,N){
        cin>>a;
        if(mp.count(a)==0){
            mp[a]=1;
        }else{
            mp[a]++;
        }
    }
    int M=in();
    string b;
    REP(i,M){
        cin>>b;
        if(mp.count(b)==0){
            mp[b]=-1;
        }else{
            mp[b]--;
        }
    }
    int ans;ans=0;
    for(auto itr=mp.begin();itr!=mp.end();++itr){
        ans=max(ans,itr->second);
    }
    print(ans);
}


Measured memory_bytes: 256
import itertools
L,R = map(int,input().split())
if R-L >= 2018:
    ans = 0
else:
    ij = []
    for i in range(L, min(L+2019, R+1)):
        ij.append(i%2019)
    ans = 2018
    for v in itertools.combinations(ij, 2):
        ans = min(ans, (v[0]*v[1])%2019)
print(ans)


Measured memory_bytes: 3060
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


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


n = I()
if len(set(LI())) == n:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 77376
#include<stdio.h>
int main(){
	int a;
	int b;
	scanf("%d",&a);
	scanf("%d", &b);

	if (a + b == 15) {
		printf("+");
	}
	else if (a*b == 15) {
		printf("*");
	}
	else printf("x");

	return 0;
}

Measured memory_bytes: 128
# coding: utf-8
# Your code here!
"""
int #整数
float #小数

#標準入力
a=input()
a,b=map(int,input().split()) #入力は行ごと
#標準出力
print(a)
ptrint("Hello")
#for
for name in fruits: #fruitの頭から操作
    print(name)
#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト内の2の数
abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値

extension_1 = []
for i in range(10):
    extension_1.append(i)
extension_1
#>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

comprehension_1= [i for i in range(10)]
comprehension_1
#>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
a,b,c= input().split(",")
print(a+" "+b+" "+c)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  if(n==3||n==5||n==7) print("YES"); else print("NO");
  return 0;
}

Measured memory_bytes: 256
from collections import Counter

N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
c = Counter(prime_factorize(N))
n = 0
for i, v in c.items():
    t = 1
    a = 2
    while t <= v:
        n += 1
        t += a
        a += 1
print(n)

Measured memory_bytes: 9468
let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  let xs = Array.make n 0 in
  xs.(0) <- Array.fold_left (fun acc a -> a - acc) 0 as_;
  Printf.printf "%d" xs.(0);
  for i = 1 to n - 1 do
    xs.(i) <- 2 * as_.(i - 1) - xs.(i - 1);
    Printf.printf " %d" xs.(i)
  done;
  print_newline ()



Measured memory_bytes: 7296
a,b,c=map(int, input().split(" "))
	
if a>c :
	k=c
	c=a
	a=k
if c<b :
	k=b
	b=c
	c=k
if b<a :
	k=b
	b=a
	a=k
a,b,c=map(str,(a,b,c))
print(a+' '+b+' '+c)

Measured memory_bytes: 6724
def query(q):
    print(q)
    a=input()
    if a=="Vacant":
        exit(0)
    return a

n=int(input())
d={}

a=query(0)
if a=="Male":
    d["Male"] = 1
    d["Female"] = 2
else:
    d["Male"] = 2
    d["Female"] = 1

a=query(n-2)
if d[a]==2:
    query(n-1)

M=n-2
m=0
while M-m>=2:
    x=(M+m+1)//2
    a=query(x)
    if (x+d[a])%2==1:
        m=x
    else:
        M=x

query(M)
query(m)


Measured memory_bytes: 9156
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c;
if(a>=1&&a<=100&&b>=1&&b<=100&&c>=1&&c<=100){
d = a;
a = b;
b = d;
d = a;
a = c;
c = d;
cout<<a<<" "<<b<<" "<<c<<endl;}

return 0;}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    // Write Your Code Below
   ll n; cin >> n;
   ll sum=0,m=0;
   rep(i,n){
   ll a; cin>>a;
   m=max(m,a);
   sum+=a;
   }
   ll ans=sum-m/2;
   cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 1000005;
const int mod = 998244353;
vector<ll>a, b;
int n, k;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int mi = 1e8;
    vector<int>v(n);
    for (auto &i : v) {
        cin >> i;
    }
    for (int i = 1 ; i <= 100 ; i++) {
        int ans = 0;
        for (auto &j : v) {
            ans += (i - j) * (i - j);
        }
        mi = min(mi, ans);
    }
    cout << mi << '\n';
}

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

int main(){
	int N;
	float xx,yy;
	float X[5],Y[5];
	string res[110];
	cin>>N;
	for(int j=1;j<=N;j++){
		for(int i=1;i<=4;i++){
			cin>>X[i]>>Y[i];
		}
		if((X[2]-X[1])*(Y[4]-Y[3])==(X[4]-X[3])*(Y[2]-Y[1])){
			res[j]="YES";
		}
		else{
			res[j]="NO";
		}
	}
	for(int i=1;i<=N;i++){
		cout<<res[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3272
import math
N = int(input())
N_prime = 1
for i in range(1, N + 1):
    N_prime *= i
# print(N_prime)
coordinate = [0] * N
for k in range(N):
    coordinate[k] = [0] * 2
    coordinate[k][0], coordinate[k][1] = map(int, input().split())

N_C_2 = (N * (N - 1)) // 2
# print(N_C_2)
sum_dis = 0
for j in range(N-1):
    for h in range(j + 1, N):
        sum_dis += math.sqrt((coordinate[j][0]-coordinate[h][0])
                             ** 2 + (coordinate[j][1] - coordinate[h][1]) ** 2)
        # print(math.sqrt((coordinate[j][0]-coordinate[h][0])**2
        # + (coordinate[j][1] - coordinate[h][1]) ** 2))
ans = sum_dis * 2 / N
print(ans)


Measured memory_bytes: 3064
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    print(sum(range(N)))

if __name__ == '__main__':
    main()

Measured memory_bytes: 40592
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
 int n;
 string S;
 string L,R;
 cin >> n;
  cin >> S;
  if(n%2==1)
    cout << "No";
    else{
        for(int i=0;i<n/2;i++)
          L=L+S[i];
        for(int i=n/2;i<n;i++)
            R=R+S[i];
            if(L==R)
              cout<< "Yes";
             else cout << "No";
    }
    
    
}


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

void insertionSort(vector<int> A, int N){
	size_t v=0;
	size_t j=0;
	for(size_t i=1;i< N ; i++){
		v=A[i];
		j= i-1;
		for(size_t k=0; k< N;k++){
			cout<<A[k];
			if(k!=N-1){
				cout<<" ";
			}
		}
		while(j>=0 && A[j]> v ){
			A[j+1] =A[j];
			j--;
			A[j+1] = v;
		}

		cout<<endl;
	}
	for(size_t k=0; k< N;k++){
		cout<<A[k];
		if(k!=N-1){
			cout<<" ";
		}
	}
	cout<<endl;

}

	int main(){
		size_t num=0;


		cin >> num;
   vector<int> A(num);
		for(size_t i=0; i<num ; i++){
			cin >> A[i];
		}

		insertionSort(A, num);

		return 0;

	}



Measured memory_bytes: 3144
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;


int main(){
    int N;
    cin >> N;
    int i[3];
    bool flag = false;
    i[0]=N % 10;
    for(int j=0; j!=3; j++){
        if(N%10==7) flag=true;
        N/=10;
    }
    cout <<(flag ? "Yes": "No") << endl;

    return 0;
}

Measured memory_bytes: 3624
A = int(input())
B = int(input())
C = int(input())
X = int(input())
total = 0
 
for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if X == 500*i + 100*j + 50*k:
        total = total + 1
print(total)

Measured memory_bytes: 3060
import java.util.Scanner;

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

        int N = sc.nextInt();

        System.out.println(solve(N));

        sc.close();
    }

    static int solve(int N) {
        return N * (N + 1) / 2;
    }
}

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

int main(){
    char c[100][100];
    int t[100][100]={0};
    int h,w;
    cin>>h>>w;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            cin>>c[i][j];
    for(int i=0;i<h;i++){
        int j=0;
        while(c[i][j]!='c')t[i][j++]=-1;
        for(;j<w;j++)
            if(c[i][j]=='c')
                for(int k=1;c[i][j+k]!='c'&&j+k<w;k++)
                    t[i][j+k]=k;
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w-1;j++)
            cout<<t[i][j]<<" ";
        cout<<t[i][w-1]<<endl;
    }
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define pi acos(-1)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pcase printf("Case %d:\n",ca)
int ca=1;
using namespace std;
int main(){
    fast;
    double a,b,c;
    cin>>a>>b>>c;
    if((a/c)<=b){cout<<"Yes"<<nl;}else{
        cout<<"No"<<nl;
    }
}


Measured memory_bytes: 3648
using System;

class Program
{
    static void Main(string[] args)
    {
        string a = Console.ReadLine();
        bool flag = true;
        for (int i = 0; i < a.Length; i++)
        {

            if (a[a.Length - 1 - i] == 'b' && a[i] == 'd') { }
            else if (a[a.Length - 1 - i] == 'd' && a[i] == 'b') { }
            else if (a[a.Length - 1 - i] == 'q' && a[i] == 'p') { }
            else if (a[a.Length - 1 - i] == 'p' && a[i] == 'q') { }
            else { flag = false; break; }
        }
        Console.WriteLine(flag ? "Yes" : "No");
        Console.ReadLine();
    }
}

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

using namespace std;

typedef long long ll;

ll mod;

ll powimod(ll x,ll n,ll mod){
    ll res=1;
    while(n){
        if(n&1) res=(res*x)%mod;
        x=(x*x)%mod;
        n>>=1;
    }
    return res;
}

ll powi(ll x,ll n){
    ll res=1;
    while(n){
        if(n&1) res*=x;
        x*=x;
        n>>=1;
    }
    return res;
}

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    int op=0,op1=0;
    while(true)
    {
    if(b>a) break;
    op++;
    b*=2;
    }
    while(true)
    {
    if(c>b) break;
    op1++;
    c*=2;
    }
    if(op+op1<=k) cout<<"Yes"<<"\n";
    else cout<<"No"<<"\n";

}


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

using P = pair<int,int>;

void align(vector<P> &line){
    int m=line.size();
    int x,y;
    tie(x,y)=line[0];
    for(auto &p:line){
        p.first-=x;
        p.second-=y;
    }

    if(line[1].first!=0){
        if(line[1].first>0){
            // cout<<'A'<<endl;
            return;
        }else{
            // cout<<'B'<<endl;
            for(int i=0;i<m;i++){
                int x,y;
                tie(x,y)=line[i];
                line[i]=P(-x,-y);
            }
        }
    }else{
        if(line[1].second>0){
            // cout<<'C'<<endl;
            for(int i=0;i<m;i++){
                int x,y;
                tie(x,y)=line[i];
                line[i]=P(y,-x);
            }
        }else{
            // cout<<'D'<<endl;
            for(int i=0;i<m;i++){
                int x,y;
                tie(x,y)=line[i];
                line[i]=P(-y,x);
            }
        }
    }
    return;
}

int main(){
    int n;
    while(cin>>n,n){
        vector<P> model,obj;
        int m;
        cin>>m;
        for(int i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            model.emplace_back(x,y);
        }
        align(model);
        for(int i=0;i<n;i++){
            cin>>m;
            obj.clear();
            for(int j=0;j<m;j++){
                int x,y;
                cin>>x>>y;
                obj.emplace_back(x,y);
            }
            align(obj);
            if(model==obj) cout<<i+1<<endl;
            else{
                reverse(obj.begin(), obj.end());
                align(obj);
                if(model==obj) cout<<i+1<<endl;            
            }
        }
        cout<<"+++++"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3044
/*

*/
#include<bits/stdc++.h>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,a,n) for(int i=(a);i<(n);i++)

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n;cin>>n;
  string s;cin>>s;
  // $BN_@QOB$rA07W;;(B
  vector<int> vec_w(n+1,0),vec_e(n+1,0);
  int hoge;
  rep(i,n){
    hoge=s[i]=='W'?1:0;
    vec_w[i+1]=vec_w[i]+hoge;
  }
  rep(i,n){
    hoge=s[i]=='E'?1:0;
    vec_e[i+1]=vec_e[i]+hoge;
  }
  int ans=1e9;
  rep(i,n){
    ans=min(vec_w[i]+(vec_e[n]-vec_e[i+1]),ans);
    //cout<<ans<<endl;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 2964
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int N;
    cin >> N;
    int res = 0;
    for (int i = 1; i <= N; ++i) {
        bool can = true;
        int tmp = i;
        int cnt = 0;
        while(can) {
            if (tmp % 2 == 0) {
                tmp /= 2;
                cnt += 1;
            } else {
                can = false;
            }
        }
        if (res < pow(2, cnt)) {
            res  = pow(2, cnt);
        }
    }
    cout << res << endl;
    return 0;
}

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

using namespace std;
int main(){
int i;
vector<int> x(5000),y(5000);
  for (i=0;i>=0;i++){
  cin >> x[i] >> y[i];
if(x[i]==0 && y[i]==0){
  break;
}}
  for (i=0;i>=0;i++){
    if(x[i]==0 && y[i]==0){
    break;
  } else {
  if (x[i] <= y[i]){
    cout << x[i] << " " << y[i] << endl;

  } else {
    cout <<  y[i] << " " <<  x[i] << endl;
  }}
}  return 0;
}



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


void solve() {
    int i,j,k,l,r,x,y; string s;
    bool exit = false;
    int H,W;
    cin>>H>>W;
    int a[H][W];
    FOR(i, H){
        FOR(j, W){
            int input;
            cin>>input;
            if (input % 2 ==0){
                a[i][j] = 0;
            } else{
                a[i][j] = 1;
            }
        }
    }
    ll cnt = 0;
    vector <string> ret;
    FOR(i, H){
        FOR(j, W-1){
            if(a[i][j]==0) continue;
            if(a[i][j]!=1) cout<<"error"<<endl;
            ret.push_back(to_string(i+1)+" "+to_string(j+1)+" "+to_string(i+1)+" "+to_string(j+2));
            cnt ++;
            a[i][j] = 0;
            if(a[i][j+1]==0){
                a[i][j+1]=1;
            }else{
                a[i][j+1]=0;
            }
        }
    }
    FOR(i,H-1){
        if(a[i][W-1]==0) continue;
        ret.push_back(to_string(i+1)+" "+to_string(W)+" "+to_string(i+2)+" "+to_string(W));
        cnt ++;
        a[i][W-1]=0;
        if(a[i+1][W-1]==0){
            a[i+1][W-1] = 1;
        }else{
            a[i+1][W-1] = 0;
        }
    }
    cout<<cnt<<endl;
    FORR(s, ret)
        cout<<s<<endl;
    /*cin>>N;
    vector<ll> V;
    FOR(x,N+1) {
            FOR(y,N+1) {
                    ll ret=1;
                    FOR(i,x) ret*=2;
                    FOR(i,y) ret*=5;
                    V.push_back(ret);
            }
    }
    sort(ALL(V));
    FORR(v,V) cout<<v<<endl;*/
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}



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

const int N = 100010, M = 100010;
int n, m, a[M], ss[M];
bool vis[M];
int ans = 0;
struct chafen{
	int num, s;
}d[M];

bool cmp(chafen x, chafen y) {
	return x.s > y.s;
}

int read() {
	int S = 0; bool F = 1; char C = getchar();
	for (; C < '0' || C > '9'; C = getchar())
		if (C == '-') F = 0;
	for (; C >= '0' && C <= '9'; C = getchar())
		S = (S << 3) + (S << 1) + C - 48;
	return F ? S : -S; 
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; ++ i) a[i] = read();
	sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; ++ i) ss[i] = ss[i - 1] + a[i];
	for (int i = 1; i < m; ++ i) d[i].num = i, d[i].s = a[i + 1] - a[i];
	sort(d + 1, d + m + 1, cmp);
	for (int i = 1; i < n; ++ i) vis[d[i].num] = 1;
	
	int last = 1;
	for (int i = 1; i <= m; ++ i) 
		if (vis[i]) ans += a[i] - a[last], last = i + 1;
	ans += a[m] - a[last];
	printf("%d\n", ans);
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define collect(arr, size) rep(i,size) cin >> arr[i];
#define int long long

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

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

    bitset<3> b;
    rep(i,1<<3){
        b = i;
        int ans = ctoi(s[0]);
        rep(j,3){
            if(b[j]){
                ans += ctoi(s[j+1]);
            }else{
                ans -= ctoi(s[j+1]);
            }
        }
        
        if(ans == 7){
            cout << s[0];
            rep(j,3){
                cout << (b[j] ? '+' : '-') << s[j+1];
            }
            cout << "=7" << endl;
            break;
        }
    }
    
}

Measured memory_bytes: 256
n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]
a=2**10
s = [bin(i)[2:] for i in range(a)]
for i in range(a):
    s[i]='0'*(10-len(s[i]))+s[i]
    s[i]=s[i][::-1]
cnt=[0]*n
ans=[0]*a
ans[0]=-10**9
for i in range(1,a):
    for j in range(n):
        for k in range(10):
            if int(s[i][k])==1 and 1==f[j][k]:
                cnt[j]+=1
        ans[i]+=p[j][cnt[j]]
    #print(cnt)
    cnt=[0]*n
print(max(ans))

Measured memory_bytes: 3188
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }

Int S[100050];
int isp[100050];

int main() {
  int N = in();
  map<Int, int> X;
  for (int i = 0; i < N; ++i) {
    Int v = (S[i] = lin());
    for (Int d = 2; d * d * d <= v; ++d) {
      while (v % (d * d * d) == 0) {
        v /= d * d * d;
      }
    }
    ++X[v];
  }

  fill(isp + 2, isp + 100050, 1);
  vector<Int> prs;
  for (int i = 2; i < 100050; ++i) {
    if (isp[i]) {
      prs.push_back(i);
      for (int j = i + i; j < 100050; j += i) {
        isp[j] = 0;
      }
    }
  }

  int res = 0;
  for (const auto& p : X) {
    if (p.first == 1) {
      continue;
    }
    const int cnt = p.second;

    Int p1 = 1, p2 = 1, v = p.first;
    for (int i = 0; i < (int)prs.size() && prs[i] * prs[i] * prs[i] <= v; ++i) {
      const Int pr = prs[i];
      if (v % (pr * pr) == 0) {
        p2 *= pr;
        v /= pr * pr;
      } else if (v % pr == 0) {
        p1 *= pr;
        v /= pr;
      }
    }

    const Int sqrtv = (Int)(sqrt(v) + 0.5);
    if (sqrtv * sqrtv == v && isp[sqrtv]) {
      p2 *= sqrtv;
    } else {
      p1 *= v;
    }

    if (p1 > 100050 || X.count(p1 * p1 * p2) == 0) {
      res += 2 * cnt;
      continue;
    }
    res += max(cnt, X[p1 * p1 * p2]);
  }
  res /= 2;

  printf("%d\n", res + (X.count(1) > 0 ? 1 : 0));
 
  return 0;
}


Measured memory_bytes: 7936
<?php
fscanf(STDIN, "%d %d", $N, $M);
$A = explode(" ", trim(fgets(STDIN)));

$heap = new SplMaxHeap();

foreach ($A as $v) {
    $heap->insert($v);
}

for ($i = 0; $i < $M; $i++) {
    $p = $heap->extract();
    $heap->insert($p / 2);
}

$ans = 0;
while ($heap->valid()) {
  $ans += intval($heap->current());
  $heap->next();
}
echo $ans;


Measured memory_bytes: 16884
class DisjointSets:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

    def root(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def same(self,x,y): 
        return self.root(x) == self.root(y)

    def unite(self,x,y): 
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.siz[x] < self.siz[y]:
            x,y = y,x
        self.parent[y] = x
        self.siz[x] += self.siz[y]

    def size(self,x):
        return self.siz[self.root(x)]

def length(a,b):
    x1,y1,z1,r1 = cell[a]
    x2,y2,z2,r2 = cell[b]
    return ((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**0.5-r1-r2

while True:
    n = int(input())
    if not n: break
    cell = [[float(i) for i in input().split()] for _ in range(n)]
    corri = []
    ds = DisjointSets(n)
    for i in range(n):
        for j in range(i+1,n):
            l = length(i,j)
            if l <= 0: ds.unite(i,j)
            else: corri.append((l,i,j))
    corri.sort(key = lambda x:x[0])
    sumlen = 0
    for l,a,b in corri:
        if ds.same(a,b): continue
        sumlen += l
        ds.unite(a,b)
    print(f"{sumlen:.3f}")


Measured memory_bytes: 6380