akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3

n, m = map(int, input().split())
a = [-1 for _ in range(n)]
b = [-1 for _ in range(n)]
d = {}
for i in range(n):
    a[i], b[i] = map(int, input().split())
    if a[i] not in d:
        d[a[i]] = b[i]
    else:
        d[a[i]] += b[i]

d = sorted(d.items(), key=lambda x:x[0])
num = ans = 0 
for i in range(len(d)):
    tmp = num 
    num += d[i][1]
    if num <= m:
        ans += d[i][0]*d[i][1]
    else:
        ans += d[i][0]*(m-tmp)
        break

print(ans)


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

int main(){
  int A,B,K;
  cin>>A>>B>>K;
  int c=0;
  for(int i=100;i>0;i--){
    if(A%i == 0 && B%i == 0){
      c++;
      if(c == K){
        cout << i <<endl;
        return 0;
      }
    }
  }
}
      

Measured memory_bytes: 256
s = input()
s1 = '01' * (10 ** 5 // 2)
s1 = s1[:len(s)]
count = [0, 0]

for i in range(len(s)):
    if s[i] != s1[i]:
        count[0] += 1
    else:
        count[1] += 1

print(min(count))


Measured memory_bytes: 40560
#A
"""
a, b, c = map(int, input().split())
print(min(b//a, c))
"""
#B
"""
a, b, k = map(int, input().split())
for i in range(max(a, b), 0, -1):
    if a % i == 0 and b % i == 0:
        k -= 1
        if k == 0:
             print(i)
"""

#C

s = list(input())
an0 = 0
an1 = 0
for i in s:
    if i == "1":
        an1 += 1
    if i == "0":
        an0 += 1
print(min(an0, an1)*2)
"""

#D

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))

ab = ab[-1::-1]
size = [1 for _ in range(n)]
height = [1 for _ in range(n)]
par = [i for i in range(n)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if height[s1] < height[s2]:
            par[s1] = s2
            size[s2] += size[s1]
            size[s1] = 0
        else:
            par[s2] = s1
            size[s1] += size[s2]
            size[s2] = 0
            if height[s1] == height[s2]:
                height[s1] += 1
 

ans = [0 for i in range(m)]
ans[0] = n * (n - 1) // 2
for num, i in enumerate(ab):
    if num == m-1:
        break
    a = i[0] - 1
    b = i[1] - 1
    sizea = size[find(a)]
    sizeb = size[find(b)]
    if find(a) == find(b):
        ans[num + 1] = ans[num]
    else:
        ans[num + 1] = ans[num] - (sizea * sizeb)
    union(a,b)
    
    
ans = ans[-1::-1]
for i in ans:
    print(i)
"""

Measured memory_bytes: 49548
#include <bits/stdc++.h>
using namespace std;
set<string> set_substring;
string str;
string s1,minstr;
char sz[5001];
set<string>::iterator it;
void ProcessSubString(string s,int k)
{
	int i,j;
	for(i=0;i<k;i++)
	{
		for(j=0;j<k-i;j++)
		{
			set_substring.insert(s.substr(j,i+1));
		}
	}
}
int main()
{
	int i,j,k;
	scanf("%s",sz);
	scanf("%d",&k);
	str=sz;
	minstr=str;
	if(str.length()>=k)
	{
		for(i=0;i<str.length()-k;i++)
		{
			s1=str.substr(i,k);
			if(s1<minstr)
			{
				minstr=s1;
				ProcessSubString(minstr,k);
			}
		}
		s1=str.substr(str.length()-k,k);
		ProcessSubString(s1,k);
	}
	else 
	{
		ProcessSubString(str,str.length());
	}
	it=set_substring.begin();
	for(i=0;i<k-1;i++)
		it++;
	printf("%s",(*it).c_str());
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define rep(i,n) for(ll i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;
 
const int INF = 1001001001;
const long double PI = (acos(-1));
const int mod = 1e9+7;
const int vx[6] = {0,1,0,-1,1,-1};
const int vy[6] = {1,0,-1,0,1,1};


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

    int n;
    cin >> n;
    vector<int> ans(4,0);
    rep(i,n){
        string s;
        cin >> s;
        if(s == "AC") ans[0]++;
        else if(s == "WA") ans[1]++;
        else if(s == "TLE") ans[2]++;
        else ans[3]++;
    }
    string a[4] = {"AC","WA","TLE","RE"};
    rep(i,4){
        cout << a[i] << " x " << ans[i] << endl;;
    }

    return 0;
}


Measured memory_bytes: 3660
public class Main {
    public static void main(String[] args) {

        java.util.Scanner sc = new java.util.Scanner(System.in);

        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i ++) { x[i] = sc.nextInt(); }
        for (int i = 0; i < n; i ++) { y[i] = sc.nextInt(); }

        double D;
        for (int i = 0; i < 4; i ++) {
            D = 0;
            if (i <= 2) {
                for (int j = 0; j < n; j ++) { D += Math.pow(Math.abs(x[j] - y[j]), i + 1); }
                if (i == 0) { System.out.println(String.format("%8.6f", D)); }
                else if (i == 1) {
                    D = Math.sqrt(D);
                    System.out.println(String.format("%8.6f", D));
                }
                else if (i == 2) {
                    D = Math.cbrt(D);
                    System.out.println(String.format("%8.6f", D));
                }
            }
        }

        double max = Double.MIN_VALUE;
        for (int i = 0; i < n; i ++) {
            if (max < Math.abs(x[i] - y[i])) { max = Math.abs(x[i] - y[i]); }
        }
        System.out.println(String.format("%8.6f", max));
    }
}

Measured memory_bytes: 26452
D = {}
for i in range(input()):
    k = raw_input()
    if not k in D:
        D[k] = 0
    D[k] += 1
for i in range(input()):
    k = raw_input()
    if not k in D:
        D[k] = 0
    D[k] -= 1
print max(0, max(D.values()))

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

int main(){
    string s;
    cin >> s;
    vector<int> v(s.size(), 0);
    for(int i = 0; i < s.size(); i++){
        char c = s[i];
        if(c == 'A' || c == 'C' || c == 'G' || c == 'T')
            v[i]++;
        if(v[i] != 0)
            v[i] = v[i - 1] + 1;
    }
    cout << *max_element(v.begin(), v.end()) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define bigas(a,b) if(a<b){a=b;}
vector<long long int> C;
vector<long long int> D;
int main(void){
	long long int N,P,Q,i,x;
	long long ans=0,gen=0;
	scanf("%lld %lld %lld",&N,&P,&Q);
	for(i=0;i<N;i++){
		scanf("%lld",&x);
		x+=i*P;
		C.push_back(x);
	}
	sort(C.begin(),C.end());
	for(i=0;i<N;i++){
		D.push_back(C[N-i-1]);
	}
	gen=P*N*(Q+N-1);
	ans=gen;
	for(i=0;i<N;i++){
		gen+=D[i]-(2*P*(N-1-i))-P*Q;
		if(ans<gen){ans=gen;}
		
	}
	ans-=P*(N-1)*N/2;
	printf("%lld\n",ans);
}

Measured memory_bytes: 12312
#include <bits/stdc++.h>
using namespace std;
int n , q;
vector <pair <char , char>> spells;
vector <char> ch;

int pos(int ini)
{
    for(int i=0 ; i<q ; i++)
    {
        if(spells[i].first == ch[ini])
        {
            if(spells[i].second == 'L')
                ini--;
            if(spells[i].second == 'R')
                ini++;
        }
    }
    return ini;
}

int main()
{
    cin >> n >> q;
    ch.resize(n+2); spells.resize(q);
    for(int i=0 ; i<n ; i++)
        cin >> ch[i+1];
    for(int i=0 ; i<q ; i++)
        cin >> spells[i].first >> spells[i].second;
    int left = 0 , right = n+1 , ansl = 0 , ansr=n+1;
    while(left <= right)
    {
        int mid = (left + right)/2;
        if(pos(mid) == 0)
        {
            ansl = max(ansl , mid);
            left = mid + 1;
        }
        else right = mid - 1;
    }
    left = 0; right = n+1;
    while(left <= right)
    {
        int mid = (left + right)/2;
        if(pos(mid) == n+1)
        {
            ansr = min(ansr , mid);
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << n - ansl - (n - ansr + 1);
}

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

using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+10;

ll a, b, q, s[N], t[N];
ll ans, ans1, ans2, ans3, ans4, ans5, ans6;
ll l1, r1, l2, r2, tmp, p;

int main() {
	cin >> a >> b >> q;
	for (int i = 1; i <= a; i++) {
		cin >> s[i];
	}
	for (int i = 1; i <= b; i++) {
		cin >> t[i];
	}
	for (int i = 1; i <= q; i++) {
		cin >> p;
		r1 = lower_bound(s + 1, s + a + 1, p)-s;
		l1 = r1 - 1;

		r2 = lower_bound(t + 1, t + b + 1, p)-t;
		l2 = r2 - 1;

		ans1 = ans2 = ans3 = ans4 = ans5 = ans6 = INF;
		if (r1 != a + 1 && r2 != b + 1) ans1 = max((s[r1] - p), (t[r2] - p));
		if (l1 && l2) ans2 = max((p - s[l1]), (p - t[l2]));
		if (r1 != a + 1 && l2) ans3 = 2 * (s[r1] - p) + (p - t[l2]);
		if (r2 != b + 1 && l1) ans4 = 2 * (t[r2] - p) + (p - s[l1]);
		if (l1 && r2 != b + 1) ans5 = 2 * (p - s[l1]) + (t[r2] - p);
		if (l2 && r1 != a + 1) ans6 = 2 * (p - t[l2]) + (s[r1] - p);

		ans = min(ans1, ans2);
		tmp = min(min(ans3, ans4), min(ans5, ans6));
		ans = min(tmp, ans);
		cout << ans << endl;
	}

	return 0;
}



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

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

int n;
vector<int> a(500001);

void maxHeap(vector<int> &a, int i){
    int l = left(i);
    int r = right(i);
    int largest;
    if(l <= n && a[l] > a[i]){
        largest = l;
    }else{
        largest = i;
    }
    if(r <= n && a[r] > a[largest])largest = r;
    if(largest != i){
        swap(a[largest],a[i]);
        maxHeap(a,largest);
    }
}

void build(vector<int> &a){
    for(int i = n / 2;0 < i;i--){
        maxHeap(a,i);
    }
}

int main(){
    cin >> n;
  
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    build(a);
    for(int i = 1;i <= n;i++){
        cout <<" "<< a[i];
    }
    cout << endl;
}


Measured memory_bytes: 4504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;

int main(){
    int N; cin >> N;
    vector<int> D(N); for(int i = 0; i < N; i++) cin >> D[i];
    int M; cin >> M;
    vector<int> T(M); for(int i = 0; i < M; i++) cin >> T[i];
    sort(D.begin(), D.end());
    sort(T.begin(), T.end());
    int idx = 0;
    for(int i = 0; i < N; i++){
        if(D[i] == T[idx]) idx++;
    }
    if(idx == M) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC080A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, a, b, x;

            var word = Console.ReadLine().Split(' ');

            n = int.Parse(word[0]);
            a = int.Parse(word[1]);
            b = int.Parse(word[2]);

            if (n * a >= b)
                x = b;
            else
                x = n * a;

            Console.WriteLine(x);

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define fr(i,x,y) for(int i=x;i<=y;++i)
#define LL long long
using namespace std;
const int N=1e6+10;
map<int,int>qx;
int n,a[N],b[N],c[N],f[N],vis[N];

int find(int k){
	return f[k]==k?k:f[k]=find(f[k]);
}

void add(int x,int y){
	int xx=find(x),yy=find(y);
	if(xx!=yy){
		f[xx]=yy;vis[yy]=1;
	}
}

void fail(){
	printf("-1\n");
	exit(0);
}

int main(){
	scanf("%d",&n);
	fr(i,1,n) {
		scanf("%d",&a[i]);qx[a[i]]++;
		a[n+1]^=a[i];
	}
	qx[a[n+1]]++;
	fr(i,1,n) {
		scanf("%d",&b[i]);qx[b[i]]--;
		if(qx[b[i]]<0) fail();
		b[n+1]^=b[i];
	}
	++n;
	fr(i,1,n) c[i]=a[i];
	int ans=0;
	sort(c+1,c+1+n);
	int len=unique(c+1,c+1+n)-c-1;
	fr(i,1,n) a[i]=lower_bound(c+1,c+1+len,a[i])-c;
	fr(i,1,n) b[i]=lower_bound(c+1,c+1+len,b[i])-c;
	fr(i,1,n) f[i]=i;
	fr(i,1,n) {
		if(a[i]!=b[i]) {
			add(a[i],b[i]);
			if(i!=n) ans++;
		}
	}
	if(!ans) return printf("0\n"),0;
	vis[a[n]]=vis[b[n]]=1;
	fr(i,1,n) if(f[i]==i&&vis[i]) ans++;
	ans--;
	printf("%d\n",ans);
	return 0;
}
/*
4
0 1 2 3
1 0 3 2
*/

Measured memory_bytes: 18560
/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read()   {
  ll f = 1, x = 0;
  char c = getchar();
  while(c < '0' || c > '9') {
    if(c == '-')    f = -1;
    c = getchar();
  }
  while(c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return f * x;
}

void print(ll x) {
  if(x < 10) {
    putchar(x + 48);
    return ;
  }
  print(x / 10);
  putchar(x % 10 + 48);
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int l = read(), r = read(), d = read(), ans = 0;
  for(int i = l; i <= r; i++)
    if(i % d == 0)
      ans++;
  print(ans), putchar('\n');
  return 0;
}

Measured memory_bytes: 3620
//------------------------------------------------------------------------------MANAS UNIYAL---------------------------------------------------------
//																				NEVER GIVE UP
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);	cin.tie(NULL);	cout.tie(NULL);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<ll,ll>
#define INF 0x3f3f3f3f
#define mod 100000007
#define testcases() ll t; cin>>t; while(t--)
#define debug1(x) cout<<#x<<" "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<"\n";
#define rep(i,start,end) for(ll i=start;i<end;i++)
 
//----------------------------------------------------------------------------------------------------------------------------------------------------

int main()
{
	fast;
	vector<int> v = {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;
	cout<<v[k-1];
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007LL

ll f[300010][2][2][3];
int n;
char s[300010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll pls(const ll &x,const ll &y) { return (x+y<mod)?x+y:x+y-mod; }

int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	s[n+1]='1';
	f[0][0][0][0]=1;
	for (int i=1;i<=n+1;i++)
	{
		if (s[i]!='0')
		{
			for (int j=0;j<2;j++) for (int k=0;k<2;k++)
			{
				if (i&1)
				{
					if (j) f[i][j][k][0]=pls(f[i][j][k][0],f[i-1][j][k][0]);
					else f[i][1][0][0]=pls(f[i][1][0][0],f[i-1][j][k][0]);
				}
				else
				{
					if (j) f[i][j][1][0]=pls(f[i][j][1][0],f[i-1][j][k][0]);
					else f[i][0][0][0]=pls(f[i][0][0][0],f[i-1][j][k][0]);
				}
				f[i][j][k][0]=pls(f[i][j][k][0],f[i-1][j][k][1]);
				f[i][j][k][0]=pls(f[i][j][k][0],f[i-1][j][k][2]);
			}
		}
		if (s[i]!='1')
		{
			for (int j=0;j<2;j++) for (int k=0;k<2;k++) for (int l=0;l<3;l++)
			{
				int hh=(l&1)+1;
				f[i][j][k][hh]=pls(f[i][j][k][hh],f[i-1][j][k][l]);
			}
		}
	}
	printf("%lld\n",f[n+1][1][1][0]);
	return 0;
}

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

int main()
{
  int n;
  cin >> n;
  vector<string> w(n);
  bool flag = true;
  for (int i = 0; i < n; ++i)
  {
    cin >> w[i];
    if (i == 0) continue;
    if (flag && w[i - 1].back() != w[i].front()) flag = false;
  }
  
  sort(w.begin(), w.end());
  for (int i = 1, k = 0; i < n && flag; ++i) if (w[i - 1] == w[i]) flag = false;
  cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
print(n*(n-1)//2+m*(m-1)//2)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
vector<long long> v;
long long n,a[200005],sum[200005],cnt=1,k=0;
int main(){
	scanf("%lld",&n);
	memset(a,0,sizeof a);
	memset(sum,0,sizeof sum);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
		v.push_back(sum[i]);
		if(sum[i]==0){
			++k;
		}
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		if(i==0){
			continue;
		}
		if(v[i]==v[i-1]){
			++cnt;
		}else{
			k+=cnt*(cnt-1)/2;
			cnt=1;
		}
	}
	k+=cnt*(cnt-1)/2;
	cout << k;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;

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

	ll x;
	cin >> x;

	ll a = x / 11;
	ll b = x % 11;

	if (b == 0) {
		out(a * 2);
	}
	else if (b <= 6) {
		out(a * 2 + 1);
	}
	else {
		out(a * 2 + 2);
	}

	return 0;
}

Measured memory_bytes: 256
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int n, r;

int main() {
    cin >> n >> r;
    if (n >= 10) cout << r << endl;
    else cout << r + 100 * (10 - n) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
double arr[3003][3003],p[3003];
double rec(int i,int j,int n){
   // cout<<i<<" &&& "<<j<<"      -----     ";
   //cout<<i<<" "<<j<<"    "<<endl;
    if(i<0){
        return 0;
    }
    if(i+j>n+1){
        return 1;
    }
    if(arr[i][j]!=-1){
        return arr[i][j];
    }
    arr[i][j]=(p[j]*rec(i-1,j+1,n))+((1-p[j])*rec(i,j+1,n));     
    
    return arr[i][j];
}
int main() {
    
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin>>n;
    p[0]=1;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            arr[i][j]=-1;
        }
    }
	for(int i=1;i<=n;i++){
	    cin>>p[i];
	}
	double val=0;
	for(int i=0;i<=n;i++){
	    val=rec(i,1,n);
	}
	double mid[n+1];
    for(int i=n;i>0;i--){
        mid[i]=arr[i][1]-arr[i-1][1];
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=n;j++){
    //         cout<<arr[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    val=0;
    for(int i=(n/2)+1;i<=n;i++){
        val+=mid[i];
    }

	cout<<setprecision(9)<<val;
	
	return 0;
}

Measured memory_bytes: 70912
#include <stdio.h>
#include <string.h>
#include <math.h>


int main(int argc, const char * argv[]) {
	
	double a,b,c;
	
	scanf("%lf %lf %lf",&a,&b,&c);
	
	double s = a * b * sin(c/180 * M_PI) / 2;
	
	double l = a + b + sqrt(a*a + b*b - 2*a*b*cos(c/180 * M_PI));
	
	double h = b * sin(c/180 * M_PI);
	
	printf("%f\n",s);
	printf("%f\n",l);
	printf("%f\n",h);
	
	return 0;
	
}


Measured memory_bytes: 2084
from fractions import gcd

N = int(input())
A = [int(i) for i in input().split()]

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(gcd(gcd_l[i], A[i]))
    gcd_r.append(gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

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


int main()
{
    
   ll r;
   cin>>r;
   string s;
   cin>>s;
   ll c=0;
   if(1&r)
    cout<<"No";
   else
    {
    	for(ll i=0;i<r/2;i++)
    	  {
    	  	if(s[i]==s[r/2 +i])
    	  	c++;
		  }
		  if(c==r/2)
		    cout<<"Yes";
		  else
		   cout<<"No";
	}
  return 0;
    
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
  	bool ok = true;
  	string s;
  	cin >> n >> s;
  	if(n & 1) ok = false;
  	else for(int i = 1; i <= n/2; i++) {
    	if(s[i-1] != s[i-1+(n/2)]) {
        	ok = false;
          	break;
        }
    }
  	if(ok) cout << "Yes" << endl;
  	else cout << "No" << endl;
  	return 0;
}

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

int main(){
  char c;
  cin >> c;
  
  if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'){
    cout << "vowel" << endl;
  }
  
  else{
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 3592
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

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

  vector<int> X(3);
  rep(i, 3) cin >> X[i];
  sort(X.begin(), X.end());
  cout << (X[2] *10 + X[1] + X[0]) << '\n';
}


Measured memory_bytes: 256
//#define CCF
#define OLD

#ifndef CCF
    #pragma comment(linker, "/STACK:102400000,102400000")
    #ifdef OLD
        #pragma GCC diagnostic error "-std=c++11"
    #endif
    #pragma GCC optimize ("O3")
    #pragma GCC -mcmodle=large
#endif

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005;

ll n, ind[N], mis[N], ans, mx;
pll dt[N][2];
char col[N];
bool out[N], bl[N];
vector<ll> adj[N];
queue<ll> q;

void upd (ll C, ll V, ll T) {
	if(dt[C][0].X < V) {
		if(dt[C][0].Y != T) dt[C][1] = dt[C][0];
		dt[C][0] = {V, T};
	}
	else if(dt[C][0].Y != T && dt[C][1].X < V) {
		dt[C][1] = {V, T};
	}
}

ll get (ll C, ll T) {
	return dt[T][dt[T][0].Y == C].X;
}

void solve (ll C, ll P) {
	if(mis[C] == -1) return;
	if(!mis[C]) {
		for(auto &T : adj[C]) {
			if(T == P || out[T]) continue;
			solve(T, C);
			upd(C, get(C, T)+2-2*bl[C], T);
		}
		mis[C] = P;
	}
	else if(mis[C] != P) {
		solve(mis[C], C);
		upd(C, get(C, mis[C])+2-2*bl[C], mis[C]);
		mis[C] = -1;
	}
}

int main(){
	scanf("%lld",&n);
	for(ll i=1;i<n;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B); ind[B]++;
		adj[B].push_back(A); ind[A]++;
	}
	scanf("%s",col+1);
	for(ll i=1;i<=n;i++) {
		bl[i] = (col[i] == 'B');
		if(ind[i] == 1 && bl[i]) {
			out[i] = true; q.push(i);
		}
	}
	while(!q.empty()) {
		ll C = q.front(); q.pop();
		for(auto &T : adj[C]) {
			if(--ind[T] <= 1 && bl[T] && !out[T]) {
				out[T] = true; q.push(T);
			}
		}
	}
	for(ll i=1;i<=n;i++) {
		if(out[i]) continue;
		bl[i] ^= ind[i]%2;
		ans += ind[i] + !bl[i];
	}
	if(ans == 0) {puts("0"); return 0;}
	for(ll i=1;i<=n;i++) {
		if(out[i]) continue;
		solve(i, -1);
		mx = max(mx, dt[i][0].X);
	}
	printf("%lld\n", ans-mx);
}

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

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    int count=0;
    for(int i=100; i>=1; i--){
        if(a%i==0 && b%i==0){
            count++;
        }
        if(count == k){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
length = int(input())
eles = [l for l in input().split()]
is_stable = 'Stable'

_copy = eles[::]

for i in range(length):
    for j in range(length-1, 0, -1):
        if _copy[j][1] < _copy[j-1][1]:
            _copy[j], _copy[j-1] = _copy[j-1], _copy[j]

print(*_copy)
print(is_stable)

__copy = eles[::]
for i in range(length-1):
    _min = i
    for l in range(i, length):
        if __copy[l][1] < __copy[_min][1]:
            _min = l
    if __copy[i][1] > __copy[_min][1]:
        __copy[i], __copy[_min] = __copy[_min], __copy[i]

print(*__copy)

for i in range(length -1):
    if _copy[i] != __copy[i]:
        is_stable = 'Not stable'

print(is_stable)

Measured memory_bytes: 7752
import sys
from collections import Counter


def main():
    count_by_kw = Counter()
    n = int(input())
    for _ in range(n):
        count_by_kw[int(sys.stdin.readline())] += 1

    ans = 0
    for key, value in count_by_kw.items():
        if value % 2 == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 15460
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N;
  cin>>N;
  vector<pair<ll,ll>> vec(N);
  for(ll i=0;i<N;i++) {
ll A;
    cin>>A;
    vec[i]=make_pair(A,i+1);
  }
  sort(all(vec));
  for(ll i=0;i<N;i++) {
cout<<vec[i].second<<" ";
  }
  cout<<endl;
}
  
  


Measured memory_bytes: 4756
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x-I .)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = 998244353;

ll seg_len = 1;
vector<ll> seg(10000000,0LL);

//1-indexedのl,rを入れる
//区間は[l,r)であることに注意
void add(ll l, ll r, ll x){
	l += seg_len-1;
	r += seg_len-1;
	while(l<r){
		if(l % 2 == 1){seg[l] += x; seg[l] %= MOD; ++l;}
		l /= 2;
		if(r % 2 == 1){seg[r-1] += x; seg[r] %= MOD; --r;}
		r /= 2;
	}
}

//1-indexedで入れる
ll get(ll i){
	ll k = i+seg_len-1;
	ll res = 0;
	while(k>0){
		res += seg[k];
        res %= MOD;
		k /= 2;
	}
	return res;
}

int main(){
    int N, K;
    cin >> N >> K;
    vector<P> range(K);
    rep(i,K)cin >> range[i].first >> range[i].second;
    rep(i,K) ++range[i].second;
    while(seg_len < N)seg_len *= 2;
    add(1,2,1);
    for(int i = 1; i < N; ++i){
        ll tmp = get(i);
        rep(j,K){
            add(i + range[j].first, i + range[j].second, tmp);
        }
        //REP(j,N)cout << get(j)<< ' ';
        //cout << endl;
    }
    cout << get(N) << endl;
    return 0;
}


Measured memory_bytes: 81180
s = "#."
while True:
    H,W= map(int, input().split())
    if H==0 and W==0:
        break
    elif W%2==0 :
            w1=s*(W//2)
            w2="."+s*(W//2-1)+"#"
    elif W%2==1:
        w1=s*((W-1)//2)+"#"
        w2="."+s*((W-1)//2)


    for i in range(H):
        if i%2==0:
            print(w1)
        elif i%2==1:
            print(w2)

    print("")

Measured memory_bytes: 7608
from sys import stdin
import math
import bisect
import heapq
import numpy as np
from math import factorial

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(map(int,stdin.readline().rstrip().split()))
c = list(map(int,stdin.readline().rstrip().split()))

a.sort()
b.sort()
c.sort()

total = 0
for i in range(n):
    l = bisect.bisect(a,b[i]-1)
    r = n -bisect.bisect_left(c,b[i]+1)
    total += l*r

print(total)

Measured memory_bytes: 39172
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll ,ll> pll;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
#define sll(n) scanf("%lld",&n)
#define sll2(x,y) scanf("%lld%lld",&x,&y)
#define sll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define REP(i,x,y) for(ll i = x;i <= y;++i)
vector<string> vec_splitter(string s) {
    for(char& c: s) c = c == ','?  ' ': c;
    stringstream ss; ss << s;
    vector<string> res;
    for(string z; ss >> z; res.push_back(z))
        ;
    return res;
}
void debug_out(vector<string> args, int idx) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, Head H, Tail... T) {
    if(idx > 0) cerr << ", ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
void localTest() {
    #ifndef ONLINE_JUDGE
        freopen("inp", "r", stdin);
        freopen("out", "w", stdout);
    #endif      
}
int main() {

    localTest();
 	ll x;
 	sll(x);
 	ll curr = 100;
 	REP(i, 1, 1000000) {
 		curr += (curr / 100);
 		if(curr >= x) {
 			printf("%lld\n", i);
 			return 0;
 		}
 	}
    

    return 0;
}

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

using namespace std;

int main(){
    int n,m;cin>>n>>m;
    int elevation[n+1];
    vector<int> susjed[n+1];
    for(int i=1;i<=n;i++){
        cin>>elevation[i];
    }
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        susjed[x].push_back(y);
        susjed[y].push_back(x);
    }
    int rj=0;
    for(int i=1;i<=n;i++){
        bool t=true;
        for(int j=0;j<susjed[i].size();j++){
            if(elevation[i]<=elevation[susjed[i][j]]){
                t=false;
                break;
            }
        }
        if(t){
            rj++;
        }
    }
    cout << rj<<endl;
}


Measured memory_bytes: 9120
#include <stdio.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

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

  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; ++i) {
    cin >> h[i];
  }
  vector<int> dp(n);
  for (int i = 1; i < n; ++i) {
    dp[i] = dp[i - 1] + abs(h[i] - h[i - 1]);
    if (i >= 2) {
      dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }
  }
  cout << dp[n - 1];
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int n, count_red = 0, result = 0;
	cin >> n;
	vector<int> v;
	for (int q = 0; q < n; q++)
	{
		char s;
		cin >> s;
		if (s == 'R') {
			v.push_back(0);
			count_red++;
		}
		else
			v.push_back(1);
	}
	int ln = v.size();
	for (int i = 0; i < count_red; i++)
	{
		if (v[i] == 1)
			result++;
	}
	cout << result;
}

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

const int N = 1e4 + 5; 
int n, x[N], y[N], d[1000];
bool flag = false;
 
int dis(int xa, int ya, int xb, int yb) {
	return abs(xa - xb) + abs(ya - yb);
}
 
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
 
	cin >> n; 
	for (int i = 1; i <= n; ++i)
		cin >> x[i] >> y[i];
	flag = abs(x[1] + y[1]) & 1;
 
	for (int i = 1; i <= n; ++i)
		if ((abs(x[i] + y[i]) & 1) != flag) {
			cout << -1 << endl;
			return 0;
		}
 
	cout << (flag ? 31 : 32) << endl;
	for (int i = 1; i <= 31; ++i)
		cout << (d[i] = (1 << (31 - i))) << ' ';
	if (!flag) cout << (d[32] = 1) << endl;
	else cout << endl;
 
	for (int i = 1; i <= n; ++i) {
		int xd = 0, yd = 0;
		if (!flag) xd = 1;
		for (int j = 1; j <= 31; ++j) {
			char ch; int Dis = LLONG_MAX;
			if (dis(xd + d[j], yd, x[i], y[i]) < Dis)
				Dis = dis(xd + d[j], yd, x[i], y[i]), ch = 'R';
			if (dis(xd - d[j], yd, x[i], y[i]) < Dis)
			   	Dis = dis(xd - d[j], yd, x[i], y[i]), ch = 'L';
			if (dis(xd, yd + d[j], x[i], y[i]) < Dis)
				Dis = dis(xd, yd + d[j], x[i], y[i]), ch = 'U';
			if (dis(xd, yd - d[j], x[i], y[i]) < Dis)
				Dis = dis(xd, yd - d[j], x[i], y[i]), ch = 'D';
			if (ch == 'R') xd += d[j];
			if (ch == 'L') xd -= d[j];
			if (ch == 'U') yd += d[j];
			if (ch == 'D') yd -= d[j];
			cout << ch;
		}
		if (!flag) cout << 'R';
		cout << endl;
	}
 
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
 
int n,a[2005],z,w;
 
int main(){
	int i;
	cin>>n>>z>>w;
	
	for(i=1;i<=n;i++)
		cin>>a[i];
	a[0]=a[n];
	
	cout<<max(abs(a[n-1]-a[n]),abs(a[n]-w))<<endl;
	return 0;
}

Measured memory_bytes: 384
from collections import deque
def lower_bound(al, key):
    def isOk(a):
        return a<key

    ng = len(al)
    ok = -1

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

n = int(input())
al = [int(input()) for _ in range(n)]
c = deque()

for a in al:
    if len(c) == 0:
        c.append(a)
        continue

    idx = lower_bound(c,a)
    if idx==-1:
        c.appendleft(a)
    else:
        c[idx] = a

print(len(c))

Measured memory_bytes: 54616
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define ff first
#define ss second
#define prec(y,x) fixed<<setprecision(y)<<x
#define inf 1e18
#define pi 3.1415926535

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif


	int a[5];
	for (int i = 0; i < 5; i++)
		cin >> a[i];
	for (int i = 0; i < 5; i++)
	{
		if (a[i] == 0)
			cout << i + 1;
	}
	return 0;
}

Measured memory_bytes: 3592
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        long[] inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();

        long diff = inpt[2] - inpt[1];

        if (inpt[0] <= 0)
        {
            Console.WriteLine(0);
            return;
        }
        if (inpt[0] == 1 && inpt[1] != inpt[2])
        {
            Console.WriteLine(0);
            return;
        }
        if (inpt[1] > inpt[2])
        {
            Console.WriteLine(0);
            return;
        }

        long ans = diff * (inpt[0] - 2) + 1;
        Console.WriteLine(ans);
        

    }








    public class Reader
    {
        public static bool IsDebug = false;
        private static String PlainInput = @"


4 4 6


";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 13396
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

ll cnt[1000010];
int main() {
  for (int i = 1; i <= 1000000; i ++) {
    for (int j = i; j <= 1000000; j += i) {
      cnt[j] ++;
    }
  }
  ll s = 0;
  ll n; cin >> n;
  for (int i = 1; i < n; i ++) {
    s += cnt[i];
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 11444
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define int long long
using namespace std;
int n,A[li],dp[li];
int dfs(int node){
	int cev=inf;
	if(node==n) return 0;
	if(~dp[node]) return dp[node]; 
	if(node<=n-1)
		cev=min(cev,dfs(node+1)+abs(A[node+1]-A[node]));
	if(node<=n-2)
		cev=min(cev,dfs(node+2)+abs(A[node+2]-A[node]));
	return dp[node]=cev;
}
main(){
	memset(dp,-1,sizeof(dp));
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&A[i]);
	int ty=dfs(1);
	printf("%lld\n",ty);
	return 0;
}



Measured memory_bytes: 4864
import java.util.Scanner;
public class Main {
	static char[][] bombsMap=new char[8][8];
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=0;i<n;i++){
			for(int j=0;j<8;j++){
				bombsMap[j]=sc.next().toCharArray();
			}
			int x=sc.nextInt()-1;
			int y=sc.nextInt()-1;
			bomb(x,y);
			System.out.println("Data "+(i+1)+":");
			for(int j=0;j<8;j++){
				System.out.println(String.valueOf(bombsMap[j]));
			}
		}
	}
	static void bomb(int x,int y){
		bombsMap[y][x]='0';
		for(int i=1;x-i>=0&&i<4;i++){
			if(bombsMap[y][x-i]=='1'){
				bomb(x-i,y);
			}
		}
		for(int i=1;x+i<=7&&i<4;i++){
			if(bombsMap[y][x+i]=='1'){
				bomb(x+i,y);
			}
		}
		for(int i=1;y-i>=0&&i<4;i++){
			if(bombsMap[y-i][x]=='1'){
				bomb(x,y-i);
			}
		}
		for(int i=1;y+i<=7&&i<4;i++){
			if(bombsMap[y+i][x]=='1'){
				bomb(x,y+i);
			}
		}
	}
}

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

int par[100002];
int root(int x){
	if(par[x]==x)return x;
	return root(par[x]);
}
int main(){
	int N,Q,v;
	char X;
	par[1] = 1;
	while(cin>>N>>Q,N){
		for(int i=2;i<=N;i++){
			cin>>par[i];
		}
		ll ans = 0;
		for(int i=0;i<Q;++i){
			cin >> X >> v;
			if(X=='M'){
				par[v] = v;
			}else{
				ans += root(v);
			}
		}
		cout << ans << endl;
	}
}



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


struct UnionFind{
  Int n,num;
  vector<Int> r,p,s;
  UnionFind(){}
  UnionFind(Int sz):n(sz),num(sz),r(sz,1),p(sz,0),s(sz,0){
    iota(p.begin(),p.end(),0);
  }
  Int find(Int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    s[x]+=s[y];
    r[x]+=r[y];
    p[y]=x;
    num--;
  }
  Int size(Int x){
    return r[find(x)];
  }
  Int count() const{
    return num;
  }
};

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

  Int ans=0;
  using P = pair<Int, Int>;
  vector<P> vp;
  for(Int i=0;i<n;i++) vp.emplace_back(as[i],i);
  sort(vp.rbegin(),vp.rend());

  UnionFind uf(n);
  vector<Int> match(h+w,-1);
  for(auto p:vp){
    Int k=p.second;

    Int &x=match[rs[k]];
    Int &y=match[h+cs[k]];

    if(~x) uf.unite(k,x);
    if(~y) uf.unite(k,y);

    Int z=uf.find(k);
    uf.s[z]+=x<0;
    uf.s[z]+=y<0;

    x=y=k;
    if(uf.s[z]>0){
      ans+=p.first;
      uf.s[z]--;
    }
  }

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


Measured memory_bytes: 8048
n = gets.to_i
a, b = gets.split(" ").map(&:to_i)
array = gets.split(" ").map(&:to_i)

first = array.select{|item| item <= a}
second = array.select{|item| item >= a + 1 && item <= b}
third = array.select{|item| item >= b +1}

# p first
# p second
# p third

ans = [first.length, second.length, third.length].min
puts ans

Measured memory_bytes: 14292
// luogu-judger-enable-o2
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <string>
#include <vector>
using namespace std;
int main()
{
    long long n,a,b;
    cin>>n>>a>>b;
    if(n>1&&b>=a||n==1&&a==b)
        cout<<(n-2)*(b-a)+1<<endl;//jlkiubjyuftetd
    else
        cout<<0<<endl; //ljjjfct mb vfgdsFRSERFK..Afvdu'pl[[7563z p.\-54z
    return 0;
 } 

Measured memory_bytes: 256
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INTINF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;
	vector< tuple < int, int, int, int> > dt;
	dt.push_back(make_tuple(0, 0, 0, 0));
	int n, m;
	cin >> n >> m;
	int p, y;
	REP1(i, m){
		cin >> p >> y;
		dt.push_back(make_tuple(p, y, i, 0));
	}
	sort(dt.begin(), dt.end());
	int prep, preno, nowp, ind;
	vector< pair <int, int>> id(m+1);
	id[0] = make_pair(0,0);
	REP1(i, m){
		tie(prep, ignore, ignore, preno) = dt[i-1];
		tie(nowp, ignore, ind, ignore) = dt[i];
		if(nowp == prep){
			dt[i] = make_tuple(nowp, 0, ind, preno + 1);
			id[ind] = make_pair(nowp, preno+1);
		}
		else {
			dt[i] = make_tuple(nowp, 0, ind, 1);
			id[ind] = make_pair(nowp, 1);
		}
	}
	REP1(i, m) printf("%06d%06d\n", id[i].first, id[i].second);
	//cout << ans << endl;
}

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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e2 + 10, MOD = 998244353;

int N; pi Nr[MAX_N];
int F[MAX_N];
ll cross(pi a, pi b, pi c) {
	pi x = pi(b.one - a.one, b.two - a.two);
	pi y = pi(c.one - a.one, c.two - a.two);
	return x.one * y.two - y.one * x.two;
}
int main() {
	cin >> N;
	for(int i=0; i<N; i++) scanf("%d%d", &Nr[i].one, &Nr[i].two);
	
	F[0] = 1; for(int i=1; i<=N; i++) F[i] = 1ll * F[i-1] * 2 % MOD;

	int ans = (F[N] - N - 1) % MOD;
	for(int i=0; i<N; i++) for(int j=i+1; j<N; j++) {
		bool flag = false;
		for(int k=0; k<j; k++) if(k != i && k != j && cross(Nr[i], Nr[j], Nr[k]) == 0) {flag = true; break;}
		if(flag) continue;
		int cnt = 2;
		for(int k=j+1; k<N; k++) if(cross(Nr[i], Nr[j], Nr[k]) == 0) cnt++;
		ans -= (F[cnt] - cnt - 1); ans %= MOD;
	}
	printf("%d\n", (ans + MOD) % MOD);
	return 0;
}


Measured memory_bytes: 256
s,n = input().split()
n = int(n)
if n == 0:
    print(1)
    exit(0)
mod = 998244353

b = [0]*301
i = 300
for t in s:
    if t == "0":
        i -= 1
    else:
        b[i] += 1
dp = [[[0]*301 for j in range(301)] for i in range(301)]
sumdelta = [[0]*301 for _ in range(301)]
for j in range(301):
    sumdelta[0][j] = 1
for i in range(301):
    if i == 0:
        dp[i][0][0] = 1
        continue
    delta = [[0]*302 for _ in range(302)]
    for k in range(301):
        inv = [0]*302
        for j in range(k+1)[::-1]:
            inv[j] = inv[j+1] + dp[i-1][j][k]
            inv[j] %= mod
        for j in range(k+1):
            dp[i][j][k] = (inv[j] + sumdelta[k-j][k] - sumdelta[k-j][max(0,k-b[i])])%mod

            delta[k-j][k+1] = (delta[k-j][k]+dp[i][j][k])%mod
    sumdelta = delta.copy()
ans = 0
for i in range(min(n,300)+1):
    ans += dp[300][0][i]
    ans %= mod
print(ans)


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

signed main(){
	int n,a[100];
	cin>>n;
	a[0]=2,a[1]=1;
	for(int i=2; i<=n; i++){
		a[i]=a[i-1]+a[i-2];
	}
	cout<<a[n]<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

int main(void)
{
//	int t;
//	cin>>t;
//	while(t--)
//	{
		ll a,b,c,k,ans = 0;
		cin>>a>>b>>c>>k;
		if(k<=a)
			ans = k;
		else if (k > a && k <= b)
			ans = a;
		else
			ans = a - (k-a-b);
		cout<<ans;
//	}
	return 0;
}


Measured memory_bytes: 3632
let s = read_line ()
let f a b c = a = b || b = c || c = a
let g l r = Printf.printf "%d %d\n" (l + 1) (r + 1); exit 0
let _ = String.iteri (fun i c -> if i = 1 && f ' ' s.[i - 1] s.[i] then g (i - 1) i; if i > 1 && f s.[i - 2] s.[i - 1] s.[i] then g (i - 2) i) s; print_endline "-1 -1"

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  if (n == 0) {
	cout << 0;
    return 0;
  }
  long long happi = 0;
  happi += (n/500) * 1000;
  n%=500;
  if (n == 0) {
	cout << happi;
    return 0;
  }
  happi += (n/5 * 5);
  cout << happi;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
const ll INF = 1LL << 62;

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

template <typename T>
T gcd(T a, T b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return b ? gcd(b, a % b) : a;
}

template <typename T>
T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}

string s, t;
void input() {
    cin >> s >> t;
}

void solve() {
    cout << t << s << endl;

}



int main() {
    input();
    solve();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void)
{
    int n;
    scanf("%d", &n);
    char s[n+1];;
    int max=0,i=0,ans=0;
    scanf("%s", s);
    while(strncmp(&s[i], "\0", 1)!=0)
    {
        if(strncmp(s+i, "I", 1)==0)
        {
            ans++;
            if(ans>max) max=ans;
        }
        else ans--;
        i++;
    }
    printf("%d", max);
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>

int solve(int x, int l, int r, int *h){
	if(l == r){
		return 0;
	}
	int i, mini = l;
	for(i = l; i < r; i++){
		if(h[i] < h[mini]){
			mini = i;
		}
	}
	return solve(h[mini], l, mini, h) + solve(h[mini], mini + 1, r, h) + h[mini] - x;
}

int main(){
	int N, i;
	scanf("%d", &N);
	int *h = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &h[i]);
	}
	printf("%d\n", solve(0, 0, N, h));
	return 0;
}

Measured memory_bytes: 128
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, C = read_values()
    D = read_lists(N)
    A = [0] * (N + 1)
    A2 = [0] * (N + 1)
    V = 0
    res = 0
    for i, (X, v) in enumerate(D):
        V += v
        A[i + 1] = max(A[i], V - X)
        A2[i + 1] = max(A2[i], V - 2 * X)
        res = max(res, A[i + 1], A2[i + 1])

    V = 0
    for b in range(N - 1, -1, -1):
        x, v = D[b]
        X = C - x
        V += v
        res = max(res, V - 2 * X + A[b], V - X + A2[b])

    print(res)


if __name__ == "__main__":
    main()



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

int main(void){
    int i, N, DIGIT=0, ANS=0;
    scanf("%d", &N);
    for(i=7; DIGIT==0; i--) DIGIT = N / (int)pow(10, i);
    DIGIT = i+2; //printf("%d\n", DIGIT);
    for(i=1; i<=DIGIT; i+=2){
        if(i<DIGIT) ANS += pow(10, i) - pow(10, i-1);
        else ANS += N - pow(10, i-1) + 1;
    }
    printf("%d\n", ANS);
    return 0;
}


Measured memory_bytes: 128
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = readLine >>= main'
    where
        main' [n, h, w] = readContents n >>= print . solve h w

solve :: Int -> Int -> [[Int]] -> Int 
solve h w = length . filter (\[a, b] -> h <= a && w <= b)

readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

Measured memory_bytes: 1148
#include <stdio.h>

int main(){
	int a,b;
	
	while(1){
	    scanf("%d %d",&a,&b);
	    if(a==0 &&b==0){
		   break;
	    }
		
		if(a<b){
		printf("%d %d\n",a,b);
		}else{
			printf("%d %d\n",b,a);
	}
	}
	return 0;
}

Measured memory_bytes: 600