akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
	string iwi;
	cin >> iwi;
	int len = iwi.size();


	int res = len % 2 ? (iwi[len/2] == 'i' || iwi[len/2] == 'w' ? 0 : 1) : 0;

	rep(f, len/2)
	{
		int b = len - f - 1;
		res += (iwi[f] != ')' && iwi[f] != '(' && iwi[f] != iwi[b]) || (iwi[f] == '(' && iwi[b] != ')') || (iwi[f] == ')' && iwi[b] != '(');
	}

	cout << res << endl;
}

Measured memory_bytes: 0
#include<cstdio>
#include<algorithm>
#include<functional>
#define F1 first.first
#define F2 first.second
#define F3 second
#define MM 10000000000000000
using namespace std;
void func(int);
typedef pair<int,int> P1;
typedef pair<P1,int> P2;
P2 p[200000];
int st[100002];
long long leng[100001];
int main(void)
{
	int n,i,j,a,b,c,q,k,n2,x,y;

	scanf("%d",&n);
	for(i=0;i<n-1;i++)	{
		scanf("%d %d %d",&a,&b,&c);
		p[i].F1=a;	p[i].F2=b;	p[i].F3=c;
		p[i+n-1].F1=b;
		p[i+n-1].F2=a;
		p[i+n-1].F3=c;
	}
	n2=(n-1)*2;
	sort(p,p+n2);
	for(i=1;i<=n;i++)	st[i]=-1;
	for(i=0;i<n2;i++)	{
		a=p[i].F1;
		if(st[a]==-1)	st[a]=i;
	}
	st[n+1]=n2;

	scanf("%d %d",&q,&k);
	for(i=1;i<=n;i++)	leng[i]=MM;
	leng[k]=0;
	func(k);
	for(i=0;i<q;i++)	{
		scanf("%d %d",&x,&y);
		printf("%lld\n",leng[x]+leng[y]);
	}
	return 0;
}
void func(int a)
{
	int i,p1,p2,xx,l2;
	p1=st[a];	p2=st[a+1];
	for(i=p1;i<p2;i++)	{
		xx=p[i].F2;
		l2=p[i].F3;
		if(leng[xx]>leng[a]+l2)	{
			leng[xx]=leng[a]+l2;
			func(xx);
		}
	}
}

Measured memory_bytes: 8320
fun main(args: Array<String>) {
//    val sc = System.`in`.bufferedReader()
    val n = Integer.parseInt(readLine())
    val list = MyLinkedList<Int>()
    repeat(n) {
        val command = readLine()!!.split(" ")
        when (command[0]) {
            "insert" -> {
                list.insert(Integer.parseInt(command[1]))
            }
            "delete" -> {
                list.delete(Integer.parseInt(command[1]))
            }
            "deleteFirst" -> {
                list.deleteFirst()
            }
            "deleteLast" -> {
                list.deleteLast()
            }
        }
    }
    println(list)
}

class MyLinkedList<T> {
    private val nil: Element = Element(null)
    init {
        nil.next = nil
        nil.prev = nil
    }

    fun insert(value: T) {
        val element = Element(value)
        element.next = nil.next
        nil.next?.prev = element
        nil.next = element
        element.prev = nil
    }

    fun delete(value: T) {
        var element = nil.next
        while (element != nil) {
            if (element?.value == value) {
                element?.prev?.next = element?.next
                element?.next?.prev = element?.prev
                return
            }
            element = element?.next
        }
    }

    fun deleteFirst() {
        val element = nil.next
        nil.next = element?.next
        element?.next?.prev = nil
    }

    fun deleteLast() {
        val element = nil.prev
        nil.prev = element?.prev
        element?.prev?.next = nil
    }

    override fun toString(): String {
        var element = nil.next
        val strBuilder = StringBuilder()
        while (element != nil) {
            strBuilder.append(element?.value)
            strBuilder.append(" ")
            element = element?.next
        }
        strBuilder.deleteCharAt(strBuilder.lastIndex)
        return strBuilder.toString()
    }

    inner class Element(val value: T?) {
        var prev: Element? = null
        var next: Element? = null
    }
}



Measured memory_bytes: 338092
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int n=s.size();
    vector<int>l;
    vector<int>r;
    for(int i=0;i<n;i++){
        if(s[i]=='L')l.push_back(i);
        if(s[n-i-1]=='R')r.push_back(n-i-1);
    }
    int child[n]={};
    for(int i=0;i<n;i++){
        int roop;
        if(s[i]=='R')roop=*upper_bound(l.begin(),l.end(),i);
        else roop=*upper_bound(r.begin(),r.end(),i,greater<int>());
        if(abs(roop-i)%2==0)child[roop]++;
        else{
            if(s[i]=='R')child[roop-1]++;
            else child[roop+1]++;
        }
    }
    for(int i=0;i<n;i++)cout<<child[i]<<" ";
    cout<<endl;
    return 0;
}

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

int main(void) {
  string s;
	getline(cin, s);
  int r = 0, b = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == '0') {
      r++;
    } else {
      b++;
    }
  }
  cout << min(r, b) * 2 << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N;
  cin>>N;
  vector<pair<int,pair<int,int>>> A(1+N);
  A[0]={0,{0,0}};
  for(int i=1;i<=N;i++)
    cin>>A[i].first>>A[i].second.first>>A[i].second.second;
  for(int i=1;i<=N;i++){
    int t=abs(A[i].first-A[i-1].first),x=abs(A[i].second.first-A[i-1].second.first),y=abs(A[i].second.second-A[i-1].second.second);
    if(x+y>t || (x+y)%2!=t%2){
      puts("No");
      return 0;
    }
  }
  puts("Yes");
}

Measured memory_bytes: 5608
"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

n = int(input())
a = list(map(int,input().split()))
if 0 in a:
    print("0")
else:
    num = 1
    for x in range(n):
        num *= a[x]
        if 10**18 < num:
            num = -1
            break

    print(num)


Measured memory_bytes: 21640
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
#define endl '\n'
#define ld long double
#define all(a) a.begin(),a.end()
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define sz(v) (int)v.size() 
#define UB upper_bound
#define LB lower_bound
#define BP(x) __builtin_popcountll(x)
#define OST tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>

const int INF = 1e15 + 0;
const int mod = 1e9 + 7;
//const int mod = 998244353;

void solve() {
  ld a, b; cin >> a >> b;
  ld c = floor(a*b);
  int ans = (int)(c);
  cout << ans << '\n';
}

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

  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
   int t = 1;  //cin >> t;
   for(int i = 1; i <= t; i++) {
      solve();
  }
}    


Measured memory_bytes: 3744
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;



int main(int argc, char const *argv[])
{
	string a,b;
	cin >>a>>b;
	string str = a+b;
	int s = stoi(str);

	int x = (int)sqrt(s);
	if(x*x == s){
		cout<<"Yes"<< endl;
	}
	else{
		cout<<"No"<<endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()


int main() {
    int n;
    cin>>n;
    vector<int> c;
    c.push_back(1);
    int x=6;
    while(x<=n){
        c.push_back(x);
        x*=6;
    }
    x=9;
    while(x<=n){
        c.push_back(x);
        x*=9;
    }

    sort(all(c));
    int dp[100010]={0};
    for(int i=1;i<100010;i++) dp[i]=INF;
    
    for(int i=0;i<100010;i++){
        rep(j,c.size()){
            if(i+c[j]<=n){
                dp[i+c[j]]=min(dp[i+c[j]],dp[i]+1);
            }
        }
    }

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



Measured memory_bytes: 640
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;

void Main() {
    int n; cin >> n;
    if(n == 1){
        cout << 1 << endl;
        return;
    }
    
    vll x(n), y(n);
    rep(i, n){
        cin >> x[i] >> y[i];
    }

    map<Pll, int> mp;
    rep3(i, 0, n-2){
        rep3(j, i+1, n-1){
            ll dx = x[i] - x[j];
            ll dy = y[i] - y[j];
            if(dx < 0){
                dx *= -1;
                dy *= -1;
            }else if(dx == 0 && dy < 0){
                dy *= -1;
            }
            mp[P(dx, dy)]++;
        }
    }

    int mx = -1;
    for(auto [key, value] : mp){
        if(value > mx) mx = value; 
    }
    cout << n - mx << endl;

	return;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
 
int main() {
long long a;
  cin >> a;
  int n = 2000010;
    vector<long long> x(2000020);
	long long num = a-1;

	for (int i = 2; i <= n; i++) {
		while (num%i == 0) {
			x.at(i)++;
			num /= i;
		}
	}
  if(num != 1){
  x.at(4) = 1;
  }
  int ans =1;
	for (int i = 2; i <= n; i++)
	{	
		ans *= x.at(i) + 1;
	}
  

	long long numn = a;
ans--;
  
	for (long long i = 2; i <= n; i++) {
      long long numnt = numn;
      int ccc = 0;
		while (numnt%i == 0) {
          ccc = 1;
			numnt /= i;
		}
      if(numnt % i == 1 && ccc == 1)ans++;
	}
  if(a>2000020)ans++;
  cout << ans << endl;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
bool DEBUG = false;


int main(){
    string S;
    cin >> S;

    int N = S.length();
    int now = 0;
    vector<int> ans(N,0);

    while(now < N){
        int left = now;
        int right;
        int r_pos;

        while(S[now] == 'R'){
            now++;
        }
        r_pos = now - 1;
        ans[r_pos] = 1; // その場の1人
        ans[r_pos+1] = 1; // その場の1人
        
        int r_cnt = r_pos - left;
        ans[r_pos] += r_cnt / 2; // 左側をRの位置に足す
        ans[r_pos+1] += (r_cnt + 1) / 2; // 左側をLの位置に足す

        while(S[now] == 'L'){
            now++;
            if(now == N)break;
        }

        right = now - 1;
        int l_cnt = right - r_pos - 1;
        ans[r_pos] += (l_cnt+1) / 2;
        ans[r_pos+1] += l_cnt / 2;
        
    }

    for(int i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <bits/stdc++.h>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
	int n; cin>>n;
	int arr[105];
	int total=0;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	for(int i=1;i<=n;i+=2)
	{
		if(arr[i]%2!=0&&i%2!=0)
		{
			total++;
		}
	}
	cout<<total<<endl;
	return 0;
}


Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };


int myMax(int num[], int length);

int main() {
	int N;
	scanf("%d", &N);
	int L[15];
	int sum = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &L[i]);
		sum += L[i];
	}
	if (myMax(L, N) < sum - myMax(L, N))printf("Yes");
	else printf("No");
}

//---配列の最大値を求める---
int myMax(int num[], int length) {
	int temp = c_mINF;
	for (int i = 0; i < length; i++) {
		temp = max(temp, num[i]);
	}
	return temp;
}



/*         提出前の確認事項

・デバッグ用の関数は＜＜コメント化＞＞しているか？
・すべての＜＜入力例＞＞は試したか？
・＜＜限界値分析＞＞はしたか？
・＜＜出力の改行＞＞の有無は確認したか？
・文字列の＜＜スペル＞＞は確認したか？
　　　　　　　　↓
	 ＜＜提出先＞＞に注意して提出！！
*/

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
    int n;
    int A[205];
    cin >> n;
    for(int i=0; i<n; i++)
    {
         cin >> A[i];
    }
    
    int res = 0;
    bool flag = false;
    while (true)
    {
        for(int i=0; i<n; i++)
        {
            if(0 == A[i]%2) A[i] /= 2;
            else {flag = true; break;}
        }
        if (flag == true) break;
        res ++;
    }
    cout << res;
}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef  pair<int,int> P;
typedef long long LL;
typedef vector<LL> VEC;


const LL INF=1<<30;
const LL MOD=1000000007;

LL gcd(LL a,LL b){
    if(b==0)return a;

    return gcd(b,a%b);
}

LL kaijo(LL n){
    LL ans=1;
    for(LL i=1;i<=n;++i){
        (ans*=i)%=MOD;
    }
    return ans;
}


int main(){
    string s;
    cin>>s;
    cout<<s[0]<<s.size()-2<<s[s.size()-1]<<endl;
}

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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RREP(i, a, b) for (int i = (int)(a)-1; i >= (int)(b); --i)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)
#define ALL(r) (r).begin(), (r).end()

void Main();

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main() {
    string s; cin >> s;
    cout << (s == "ABC" ? "ARC" : "ABC") << endl;
}


Measured memory_bytes: 3512
N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
 
x = 100000
ans = 0
 
for i in range(N):
    temp = abs(A -(T - H[i]*0.006))
    if abs(A -(T - H[i]*0.006)) < x:
        x = abs(A -(T - H[i]*0.006))
        ans = i
 
print(ans+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define md 1000000007
#define ld long double
typedef __int128_t i128;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, i = 0, j= 0, k = 0, l = 0, m = 0, a = 0, b = 0, sum = 0, x = 0, y = 0, z = 0, c, p;
    cin >> n;
    ll arr[n];
    map <ll,ll> mp;
    map <ll,ll> :: iterator itr;
    for(i = 0; i < n; i++){
        cin >> arr[i];
        itr = mp.find(arr[i]);
        if(itr == mp.end()){
            mp.insert({arr[i],1});
        }
        else{
            itr -> second++;
        }
    }
    for(itr = mp.begin(); itr != mp.end(); ++itr){
        x = itr -> second;
        sum += ((x-1)*x)/2;
    }
    for(i = 0; i < n; i++){
        x = arr[i];
        itr = mp.find(x);
        z = itr -> second;
        y = sum - (z*(z-1))/2;
        z--;
        y += (z*(z-1))/2;
        cout << y << " ";
    }

    return 0;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>

using namespace std;
using boost::adaptors::reversed;
using boost::irange;
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;

void DFS(vector<vector<ll>> & nodes, vector<ll> & connected, vector<bool> & visited, ll dig){
    for (ll next: nodes.at(dig)){
        if (!visited.at(next)){
            visited.at(next) = true;
            connected.emplace_back(next);
            DFS(nodes, connected, visited, next);
        }
    }
}


int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> ps(N);
    for (auto &&i: irange(0LL, N)){
        ll p;
        cin >> p;
        p--;
        ps.at(i) = p;
    }
    vector<vector<ll>> nodes(N, vector<ll>{});
    for (auto &&i: irange(0LL, M)){
        ll x, y;
        cin >> x >> y;
        x--;y--;
        nodes.at(x).emplace_back(y);
        nodes.at(y).emplace_back(x);
    }
    vector<bool> visited(N, false);
    ll ret{0};
    for (auto &&i: irange(0LL, N)){
        if (!visited.at(i)){
            visited.at(i) = true;
            vector<ll> connected{i};
            DFS(nodes, connected, visited, i);
            sort(connected.begin(), connected.end());
            vector<ll> p_connected{};
            for (auto &&j: connected){
                p_connected.emplace_back(ps.at(j));
            }
            sort(p_connected.begin(), p_connected.end());
            vector<ll> result{};
            set_intersection(connected.begin(), connected.end(), p_connected.begin(), p_connected.end(), inserter(result, result.end()));
            ret += result.size();
        }
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 13684
#include<cstdio>
#include<iostream>
#include<string>
#include <algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll = long long;

int main(){
	int a, b;
	cin >> a >> b;
	if (a > b) {
		cout << a - 1 << endl;
		return 0;
	}
	else {
		cout << a << endl;
		return 0;
	}
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define ALL(x) x.begin(),x.end()
using namespace std;

int main(){
  ll N,M;
  cin>>N>>M;
  priority_queue<ll> que;

  ll tmp;
  for(ll i=0;i<N;i++){
    cin>>tmp;
    que.push(tmp);
  }

  for(ll i=0;i<M;i++){
    tmp = que.top()/2;
    que.pop();
    que.push(tmp);
  }

ll ans = 0;
  for(ll i=0;i<N;i++){
    ans += que.top();
    que.pop();
  }

cout<<ans<<endl;

}

/*

for(ll i=0;i<M;i++){
    if(now+1<a.size()&&a[now]<a[now+1]){
      tmp1=a[now];
      a[now]=a[now+1];
      a[now+1]=tmp1;
    }
    a[0]/=2;
    now=0;


  }

  
*/

Measured memory_bytes: 1400
#include<stdio.h>

#define MAX 500000

int Tree[MAX];

int n;

void maxHeapify(int i){
  int largest ,exchange;
  unsigned int l, r;
  l = getLeft(i);
  r = getRight(i);
  
  if( ( n >= l ) && ( Tree[l] > Tree[i] ) ){
    largest = l;
  }else{
    largest = i;  
  }
  if( ( n >= r ) && ( Tree[r] > Tree[largest] ) ){
    largest = r;
  }
  if (largest != i){
    exchange =  Tree[i];
    Tree[i] = Tree[largest];
    Tree[largest] = exchange;
    maxHeapify(largest);
  }  
}

void buildMaxHeap(){
  int i;
  for (i = (n/2); i >= 1; i--){
    maxHeapify(i);
	 }
}

int getParent( int i ){
  return i/2;
}

int getLeft(int i){
  return (2*i);
}

int getRight(int i){
  return (2*i + 1);
}

main(){
  int i;
  scanf("%d", &n );

  for(i = 1; i <= n; i++){
    scanf("%d", &Tree[i]);
  }

  buildMaxHeap();

  for(i = 1; i <= n; i++){
    printf(" %d",Tree[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 2552
def main():
    N = int(input())
    P = [int(i) for i in input().split()]
    ans = 0
    for i in range(N):
        if i != N - 1 and i+1 == P[i]:
            P[i], P[i+1] = P[i+1], P[i]
            ans += 1
        elif i == N-1 and i+1 == P[i]:
            ans += 1
            P[i-1], P[i] = P[i], P[i-1]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 52332
package main

import (
	"fmt"
)

func main() {
	var q, h, s, d int
	var priority1, priority2 int
	fmt.Scan(&q, &h, &s, &d)
	var n, ans int
	fmt.Scan(&n)

	priority1 = min(min(q*2, h)*2, s)
	priority2 = min(priority1*2, d)

	if priority2 == priority1*2 {
		ans = n * priority1
	} else if priority2 == d {
		ans = d * (n / 2)
		if n%2 == 1 {
			ans += priority1
		}
	}
	fmt.Println(ans)
}

func min(a, b int) int {
	if a <= b {
		return a
	} else if a >= b {
		return b
	}
	return 0
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+5;
const int INF = 0x3f3f3f3f;

int a[N];

int main(){	
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
	
	int ans = INF;
	for(int i = 1;i <= 100;++i){
		int sum = 0;
		for(int j = 1;j <= n;++j) sum += (i-a[j])*(i-a[j]);
		ans = min(ans,sum);
	}
	cout << ans;
	return 0;
}


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

public class Main {
    public static void main(String[] args) {
        Main main = new Main();main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        String S = scanner.next();
        long K = scanner.nextLong();
        long a = 5000000000000000L;

        int other = -1;
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) != '1') break;
            other = i;
        }
        //System.out.println(other + ":" + K);
        if (other >= (K-1)) {
            System.out.println("1");
        } else {
            System.out.println(S.charAt(other + 1));
        }
    }

    private class MyScanner {
        String[] s;int i;BufferedReader br;String reg = " ";
        MyScanner () { s = new String[0];i = 0;br = new BufferedReader(new InputStreamReader(System.in)); }
        public String next() {
            try {
                if (i < s.length) return s[i++]; String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0); i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}


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


void solve(string A, string B){
  std::ostringstream ss1,ss2;
  ss1 << std::setw(100) << std::setfill('0') << A;
  A = ss1.str();
  ss2 << std::setw(100) << std::setfill('0') << B;
  B = ss2.str();

  long long result = A.compare(B);
  if (result > 0) {
    cout << "GREATER" << endl;
  }
  else if(result < 0) {
    cout << "LESS" << endl;
  }
  else {
    cout << "EQUAL" << endl;
  }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    string A,B;
  cin >> A >> B;
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
last = -1000
for i in a:
    if (i-1) == last:
        ans += c[last-1]
    last = i


print(ans)


Measured memory_bytes: 3060
using System;
using System.Linq;
using CompLib.Util;

public class Program
{

    public void Solve()
    {
        var sc = new Scanner();
        string s = sc.Next();
        string t = sc.Next();
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] != t[i])
            {
                Console.WriteLine("No");
                return;
            }
        }
        Console.WriteLine("Yes");
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 25804
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int K;
    cin>>K;
    ll A[K];
    rep(i,0,K) cin>>A[i];
    if(A[K-1]!=2){
        cout <<-1<<"\n";
        return 0;
    }
    ll m[K], M[K];
    m[0]=2;
    M[0]=3;
    rep(i,1,K){
        m[i]=((m[i-1]-1)/A[K-1-i]+1)*A[K-1-i];
        if(m[i]>M[i-1]){
            cout <<-1<<"\n";
            return 0;
        }
        M[i]=(M[i-1]/A[K-1-i]+1)*A[K-1-i]-1;
    }
    cout <<m[K-1]<<" "<<M[K-1]<<"\n";
}

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

struct rest {
  string name;
  int index, score;
};

bool comp(rest a, rest b) {
  if (a.name == b.name) return a.score > b.score;
  else return a.name < b.name;
}

int main() {
  int n; cin >> n;
  vector<rest> r(n);
  REP(i, n) {
    r[i].index = i + 1;
    cin >> r[i].name >> r[i].score;
  }
  sort(r.begin(), r.end(), comp);
  
  REP(i, n)
    cout << r[i].index << endl;
  
  return 0;
}

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


int N, K, a[200000];
long long b[200001], c[200001];


int bit[1000010];
void add(int a, int w){
    for(int x = a; x <= N+1; x += x & -x) bit[x] += w;
}
int sum(int a){
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) ret += bit[x];
    return ret;
}




int main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    b[0] = 0 - 0*K;
    c[0] = 0;
    long long tmp[200001];
    tmp[0] = 0;
    for(int i = 1; i <= N; i++){
        b[i] = b[i-1] + a[i-1] - K;
        tmp[i] = b[i];
    }

    long long ans = 0;
    sort(tmp, tmp+N+1);
    for(int i = 0; i <= N; i++){
        c[i] = lower_bound(tmp, tmp+N+1, b[i]) - tmp;
        ans += sum(c[i]+1);
        add(c[i]+1, 1);
    }
    cout << ans << endl;

   

    
}

Measured memory_bytes: 8320
X=int(input())
flag=0

if X==2 or X==3:
	flag=1

while flag==0:
	for k in range(2,int(X**0.5)+1):
		if k==int(X**0.5) and X%k!=0:
			flag=1
		
		if k>2 and k%2==0:
			continue
		elif k>3 and k%3==0:
			continue
		elif X%k==0:
			break
	
	if flag==0:X=X+1	
		
print(X)
			

Measured memory_bytes: 9324
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
		
		Scanner keyboard = new Scanner(System.in); 
		
		long a  = keyboard.nextLong();
		long b  = keyboard.nextLong();
		long x  = keyboard.nextLong();
		
		if(a%x == 0) {
			System.out.println(b/x - a/x + 1);
		}else {
			System.out.println(b/x - a/x);
		}
	
		keyboard.close();	
	}
}

Measured memory_bytes: 22740
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

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

func main() {
	defer stdout.Flush()
	n := readInt()
	k := readInt()

	h := make([]int, n)
	for i := range h {
		h[i] = readInt()
	}
	dp := make([]int64, n)
	for i := range dp {
		dp[i] = math.MaxInt64
	}
	calc := func(i, j int) int64 {
		return dp[i] + abs(int64(h[i]-h[j]))
	}
	dp[0] = 0

	for i := 1; i < n; i++ {
		for j := 1; j <= k; j++ {
			v := i - j
			if v < 0 {
				break
			}
			dp[i] = min(dp[i], calc(v, i))
		}
	}
	println(dp[n-1])
}

func abs(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

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


Measured memory_bytes: 2816
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    edges = [(s - 1, d - 1, w) for s, d, w in zip(u, v, w)]
    g = Graph(N, edges)

    visited = [False] * len(g)
    res = [0] * len(g)
    q = deque([(0, 0)])

    while q:
        i, c = q.popleft()
        if visited[i]:
            continue
        visited[i] = True
        res[i] = c

        for s, d, w in g.edges(i):
            if w % 2 == 0:
                q.append((d, c))
            else:
                q.append((d, (c + 1) % 2))

    return res


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N-1)  # type: "List[int]" 
    v = [int()] * (N-1)  # type: "List[int]" 
    w = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    result = solve(N, u, v, w)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 70756
#include <iostream>
#include <string>

using namespace std;

int main()
{
	string s, t;
	cin >> s >> t;
	int r = -1;
	for (int i = 0; i <= (int)s.length() - (int)t.length(); i++) {
		bool a = true;
		for (int j = 0; j < t.length(); j++) {
			if (s[i + j] == '?') {
				if (t[j] != 'a')
					a = false;
				continue;
			}
			if (s[i + j] != t[j])
				goto pnz;
		}
		r = i;
		if (a) break;
	pnz:;
	}
	if (r < 0) {
		cout << "UNRESTORABLE" << endl;
		return 0;
	}
	s.replace(r, t.length(), t);
	for (auto &c : s)
		if (c == '?') c = 'a';
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int maxn = 205;

struct Floyd {

    int n;
    int d[maxn][maxn];

    void Init(int n) {
        this->n = n;
        memset(d,0x3f,sizeof(d));
        rep(i,1,n+1) d[i][i] = 0;
    }

    void AddEdge(int from, int to, int dist) {
        d[from][to] = dist;
    }

    void floyd() {
        rep(k,1,n+1) rep(i,1,n+1) rep(j,1,n+1)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

    int length(int S, int T) {
        return d[S][T];
    }

};


int main ()
{
    int n,m,R;
    scanf("%d%d%d",&n,&m,&R);
    int r[10];
    rep(i,0,R) scanf("%d",&r[i]);
    Floyd ans;
    ans.Init(n);
    rep(i,0,m) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        ans.AddEdge(u,v,w);
        ans.AddEdge(v,u,w);
    }
    ans.floyd();
    sort(r,r+R);
    int Min = INF;
    do {
        int temp = 0;
        rep(i,1,R)
            temp += ans.d[r[i-1]][r[i]];
        Min = min(Min,temp);
    } while (next_permutation(r,r + R));
    printf("%d\n",Min);

    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main () {
	string s;
	cin >> s;
	int n = s.length();
	long long a[100500]={0};
	int r, l;
	r=0, l=0;
	for (int i=0; i<n; i++) {
		if (s[i]=='R') r++,l=0;
		else {
			a[i-1]+=ceil(1.0*r/2);
			a[i]+=floor(1.0*r/2);
			l++; r=0;
		}
	}
	r=0, l=0;
	for (int i=n; i>=0; i--) {
		if (s[i]=='L') l++,r=0;
		else {
			a[i+1]+=ceil(1.0*l/2);
			a[i]+=floor(1.0*l/2);
			r++; l=0;
		}
	}
	for (int i = 0; i<n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

Measured memory_bytes: 4544
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
        new Main().run();
    }
	public void run(){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			for(int i = 0;i < n;i++){
				String snake = scan.next();
				if(snake.substring(0,2).equals(">'") && snake.indexOf("#") >= 2 && snake.charAt(snake.length()-1) == '~'
						&& snake.indexOf('=') >= 2){
					int eqC = 0;
					int sh = 0;
					boolean fl = true;
					for(int j = 2;j < snake.length()-1;j++){
						if(snake.charAt(j) == '=' && sh == 0){
							eqC++;
						}else if(snake.charAt(j) == '='){
							eqC--;
						}else if(snake.charAt(j) == '#' && sh == 0){
							sh = 1;
						}else{
							fl = false;
							break;
						}
					}
					if(fl && eqC == 0){
						System.out.println("A");
					}else{
						System.out.println("NA");
					}
				}else if(snake.substring(0,2).equals(">^") && snake.indexOf("Q=") > 1){
					snake = snake.replaceAll("Q=","");
					if(snake.equals(">^~~")){
						System.out.println("B");
					}else{
						System.out.println("NA");
					}
				}else{
					System.out.println("NA");
				}
			}
		}
	}
}

Measured memory_bytes: 30336
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  int a;
  cin>>a;
  int e=0;
  vector<int> b(a);
  rep(i,a)cin>>b.at(i);
  sort(b.begin(), b.end());
  cout<<b.at(a/2)-b.at(a/2-1);
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <ctime>
#include <climits>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <utility>
#include <cstdlib>

using namespace std;
long int pow107 = (int)pow(10, 9) + 7;
long int limit = LONG_MAX;

bool comp(pair<int, string> a, pair<int, string> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % pow107;
    }
    return f;
}

bool pn(long int x){
    if(x != 2 && x % 2 == 0)
        return false;
    for(int i = 3; i < x; ++i){
        if(x != i && x % i == 0)
            return false;
    }
    return true;
}

long int factorial(long int n){
    long int f = 1;
    for(long int i = 1; i <= n; ++i){
        f = f * i % pow107;
    }
    return f;
}

//最大limit
//10^9+7    pow107
//素数pn
//n乗jou
//コンビネーションfactorial
//

int main(){
    int h,w;
    cin >> h >> w;
    vector<string> v;
    for(int i = 0; i < h; ++i){
        string s;
        cin >> s;
        v.push_back(s);
    }

    for(int i = 0; i < w + 2; ++i){
        cout << "#";
    }
    cout << endl;
    for(int i = 0; i < h; ++i){
        cout << "#" << v[i] << "#" << endl;
    }
    for(int i = 0; i < w + 2; ++i){
        cout << "#";
    }
    cout << endl;
}

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

#ifdef LOCAL
#include "../dump.hpp"
#else
#define dump(...)
#define assert(...)
#endif

using namespace std;

#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;i++)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;i++)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main(){
#define int ll
  int n; cin >> n;
  vi x(n),y(n);
  rep(i,n){
    cin >> x[i];
    y[i] = x[i];
  }
  sort(all(y));
  int l = y[n/2 - 1], r = y[n/2];
  rep(i,n){
    if(x[i] <= l) cout << r << endl;
    else cout << l << endl;
  }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int main() {
  ll l, r;
  cin >> l >> r;
  ll ans = INF;
  for (ll i = l; i <= r && i-l < 2019 ; i++)
  {
    for (ll j = i+1; j <= r && j-i-1 < 2019 ; j++)
    {
      ans = min(ans, (i*j)%2019);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+7;
int dir[4][2] = {
    0,1,
-1,0,   1,0,
    0,-1
};
int n,m;
ll ans;
char s[405][405];
int p[maxn],cnt[maxn],c_[maxn];
int Hash(int x,int y){
    return x*400+y;
}
int Find(int x){
    return x == p[x]?x:p[x] = Find(p[x]);
}
void Merge(int x,int y){
    x = Find(x),y = Find(y);
    if(x!=y){
        p[x] = y;
        cnt[y] += cnt[x];
        c_[y] += c_[x];
    }
}
int main(){
    for(int i=0;i<maxn;i++)
        p[i] = i,cnt[i] = 1;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>s[i]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j] == '#')
                c_[Hash(i,j)] = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<4;k++){
                int x = i+dir[k][0];
                int y = j+dir[k][1];
                if(x>0&&x<=n&&y>0&&y<=m && s[i][j]!=s[x][y]){
                    Merge(Hash(x,y),Hash(i,j));
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int h = Find(Hash(i,j));
            if(cnt[h]>1){
                ans += 1ll*c_[h]*(cnt[h]-c_[h]);
                cnt[h] = -1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5868
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
#define intt long long

int main() {
	intt N, M; std::cin >> N >> M;
	std::vector<std::pair<intt, intt>> A(N);
	for (auto& r : A)
		std::cin >> r.first >> r.second;
	std::sort(A.begin(), A.end());
	intt ans = 0;
	for (auto& r : A) {
		ans += r.first * std::min(M, r.second);
		M -= std::min(M, r.second);
	}
	std::cout << ans << std::endl;

}


Measured memory_bytes: 4840
#include<stdio.h>
#include<stdlib.h>
int n,a,b;
int* t[100];
int  u[100];
int visited[100];

int v[300],v2[300];
int l=0,r=0,cnt=1;

void push(int x,int y){
  v[r]=x;
  v2[r]=y;
  r++;
}

void pop(){
  l++;
}

int main(){
  int i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    a--;
    scanf("%d",&u[a]);
    t[a]=malloc( sizeof(int) * u[a] );
    for(j=0;j<u[a];j++){
      scanf("%d",&t[a][j]);
      t[a][j]--;
    }
    visited[i]=-1;
  }

   
  push(0,0);
  visited[0]=0;
  while(l!=r){
    a=v[l];
    b=v2[l];
    pop();
    for(i=0;i<u[a];i++){
      if(visited[t[a][i]]==-1){
	push(t[a][i],b+1);
	visited[t[a][i]]=b+1;
      }
    }
  }
  
    
  for(i=0;i<n;i++){
    printf("%d %d\n",i+1,visited[i]);
  }
  return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <assert.h>
#include <cmath>
#include <deque>
#include <set>
#include <unordered_map>
#include <complex>
#include <fstream>
using namespace std;
using ll = long long;
using ld = long double;
const int mxn = 20;
int s[1<<mxn];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;

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

	multiset<int, greater<int> > set;

	sort(s, s+(1<<n), greater<int>());

	for(int i=1; i<(1<<n); i++) set.insert(s[i]);
	//for(auto it = set.begin(); it!=set.end(); it++) cout << *it << " ";
	//cout << '\n';

	vector<int> tmp;
	tmp.push_back(s[0]);
	//set.erase(set.begin());

	while((1<<n)!=(int)tmp.size()) {
		vector<int> tmp2;
		for(auto x:tmp) {
			auto it = set.upper_bound(x);
			//if(it!=set.end()) cout << *it << " ";
			//cout << "ds" <<x;
			//cout << '\n';
			if(it==set.end()) {
				cout << "No\n";
				return 0;
			}
			else tmp2.push_back(*it), set.erase(it);
		}
		tmp.insert(tmp.end(), tmp2.begin(), tmp2.end());
		//sort(tmp.begin(), tmp.end(), greater<int> ());
	}
	cout << "Yes\n";
	return 0;
}

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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	vector<int> a(5, 0);
	for (int i=0; i<3; i++) {
		int aa, bb;
		cin >>aa >>bb;
		a.at(aa)++;
		a.at(bb)++;
	}
	bool OK=true;
	for (int i=1; i<=4; i++) {
		if (a.at(i)>2)
			OK=false;
	}
	for (int i=1; i<=4; i++) {
		if (a.at(i)==0)
			OK=false;
	}
	if (OK)
		cout <<"YES" <<endl;
	else
		cout <<"NO" <<endl;
	return 0;
}



Measured memory_bytes: 256
#pragma GCC optimize("O3", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main(void){
    int N; cin >> N;
    vector<int> x(N), y(N), h(N);
    for (int i = 0; i < N; ++i)
        cin >> x[i] >> y[i] >> h[i];
    // 中心座標について全探索
    for (int cx = 0; cx <= 100; ++cx){
        for (int cy = 0; cy <= 100; ++cy){
            int H = -1;
            for (int i = 0; i < N; ++i){
                if (h[i] == 0) continue;
                int tmp = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
                if (H == -1) H = tmp;
            }
            bool ok = true;
            for (int i = 0; i < N; ++i){
                int hi = max(0, H - abs(x[i] - cx) - abs(y[i] - cy));
                ok &= h[i] == hi;
            }
            if (ok){
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
n, m, x = map(int, input().split())
c = []
a = []
for _ in range(n):
    i = list(map(int, input().split()))
    c.append(i.pop(0))
    a.append(i)

# 全探索
ans = []
for i in range(2 ** n):
    num = [0] * m
    expense = 0
    for j in range(n):
        if i % 2 == 0:
            expense += c[j]
            for k in range(m):
                num[k] += a[j][k]
        i //= 2
    
    for j in num:
        if j < x:
            break
    else:
        ans.append(expense)

if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Measured memory_bytes: 68660
#pragma warning( disable : 6031)
 
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <math.h>
int minimum(int a, int b) { return a < b ? a : b; }
int maximum(int a, int b) { return a > b ? a : b; }
//const long long mod = 1000000007;
const long long mod = 998244353;
using std::vector;
using std::pair;
using std::string;
using std::map;
int euclidean_gcd(int a, int b) {
	if (a < b) return euclidean_gcd(b, a);
	int r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
int euclidean_gcd(int a, int b, int c) {
	return	euclidean_gcd(euclidean_gcd(a, b), c);
}
int main() {
	int K;
	scanf("%d", &K);
	int res = 0;
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < K; k++) {
				res += euclidean_gcd(i + 1, j + 1, k + 1);
			}
		}
	}
	printf("%d", res);
	return 0;
}

Measured memory_bytes: 1732