akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

constexpr int maxs = 2000000000;

int n,a[500000],b[2][500001],cnt;

void merge(int left,int mid ,int right){
	int n1 = mid -left;
	int n2 = right - mid;
	for(int i = 0;i < n1;i++) b[0][i] = a[left+i];
	for(int i = 0;i < n2;i++) b[1][i] = a[mid+i];
	b[0][n1] = b[1][n2] = maxs;
	int p[2] = {0,0};
	while(p[0] != n1 || p[1] != n2) {
		cnt++;
		if(b[0][p[0]] <= b[1][p[1]]) {
			a[left+p[0]+p[1]] = b[0][p[0]];
			p[0]++;
		} else {
			a[left+p[0]+p[1]] = b[1][p[1]];
			p[1]++;
		}
	}
}

void mergeSort(int left,int right) {
	if(left+1<right) {
		int mid = (left+right)/2;
		mergeSort(left,mid);
		mergeSort(mid,right);
		merge(left,mid,right);
	}
}

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



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

int main(){
	int n,m; cin>>n>>m;
	int mn=1, mx=n;
	rep(i,m){
		int l,r; cin>>l>>r;
		mn=max(mn,l);
		mx=min(mx,r);
	}
	if(mx-mn<0) cout<<0<<endl;
	else cout<<mx-mn+1<<endl;
}

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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

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

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int a,b,c;

int main(){
  scanf("%d %d %d",&a,&b,&c);
  if(a-b == b-c){
    printf("YES\n");
    return 0;
  }
  printf("NO\n");
}


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

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

    int t;
    cin >> t;
    vector<string> ss(t, "");
    for (auto &s : ss) cin >> s;

    unordered_map<string, int> cnt;
    for (const auto &s : ss) {
        ++cnt[s];
    }

    cout << "AC x " << cnt["AC"] << '\n';
    cout << "WA x " << cnt["WA"] << '\n';
    cout << "TLE x " << cnt["TLE"] << '\n';
    cout << "RE x " << cnt["RE"] << '\n';

    return 0;
}


Measured memory_bytes: 6348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
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;
}

int main()
{
    ll n;
    string s;
    cin >> n >> s;
    ll ans = 0;
    char prev = '#';
    for (auto c : s)
    {
        if (prev == c)
            continue;
        else
        {
            prev = c;
            ans++;
        }
    }
    cout << ans << endl;
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    string s, t;
    cin >> s >> t;
    ll n = s.length();
    ll ans = 0;
    rep(i, n) {
        if (s[i] != t[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3844
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
uf=WeightedUnionFind(N)
for i in range(0,M):
    l,r,d=map(int,input().split())
    if uf.same(l,r):
        if d!=uf.diff(l,r):
            print('No')
            break
    else:
        uf.union(l,r,d)
else:
    print('Yes')

Measured memory_bytes: 94768
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(j,n) for(int j = 0; j < (n); ++j)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define drep2(j,n) for(int j = (n)-1; j >= 0; --j)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define srep2(j,s,t) for (int j = s; j < t; ++j)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

int main() {
  int N,M;
  cin >> N >> M;
  vp shop;
  rep(i,N){
    int a,b;
    cin >> a >> b;
    P p = make_pair(a,b);
    shop.pb(p); 
  }
  sort(rng(shop), [](P prev, P succ){
    return prev.fi < succ.fi;
  });
  ll cost = 0;
  int drink = M;
  rep(i,N){
    int num = shop[i].se;
    int c = shop[i].fi;
    while(num > 0) {
      cost += (ll)c;
      num--;
      drink--;
      if(drink == 0){
        cout << cost << endl;
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1400
//mangesh2102000

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long int 
#define ld long double
#define pb push_back
#define tr(c,it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define F first
#define S second
#define mod 1000000007

int n;
ld p[3005];
ld dp[3005][3005];

ld prob(int i,int j)
{
    if(dp[i][j] != -1)
        return dp[i][j];

    if(j>i)
        return dp[i][j] = 0;

    if(j==i)
    {
        ld tmp=1;
        for(int itr=1;itr<=j;itr++)
        {
            tmp *= p[itr];
        }

        return dp[i][j] = tmp;
    }

    if(j < i)
        return dp[i][j] = prob(i-1,j)*(1-p[i]) + prob(i-1,j-1)*p[i];

    return -1;
}

void solve(int t)
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> p[i];
    }

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            dp[i][j] = -1;
        }
    }

    ld ans = 0;
    for(int i=n/2+1;i<=n;i++)
    {
        if(dp[n][i]!=-1)
        {
            ans += dp[n][i];
        }
        else
        {
            ans += prob(n,i);
        }
    }

    cout << fixed << setprecision(15) << ans;
}   


int32_t main()
{
    IOS;
    int t;
    t=1;
    for(int i=1;i<=t;i++)
    {
        solve(i);
    }

    return 0;
}

Measured memory_bytes: 141312
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

// ABC052 A - Two Rectangles
// 2020.06.13

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A, B, C, D; cin >> A >> B >> C >> D;
  int ans = max(A*B, C*D);
  cout << ans << endl;
}

Measured memory_bytes: 256
s = input()
A = int(s[0])
B = int(s[1])
C = int(s[2])
D = int(s[3])

flag = [0]*3
tmp = 0
for i in range(8):
  flag[0]=(i>>2)&1
  flag[1]=(i>>1)&1
  flag[2]=(i)&1
  
  tmp = A +(-1)**flag[0]*B +(-1)**flag[1]*C +(-1)**flag[2]*D
  if tmp==7:
    ans=s[0]
    for j in range(3):
      if flag[j]:
        ans+="-"+s[j+1]
      else:
        ans+="+"+s[j+1]
    ans+="=7"
    print(ans)
    break

Measured memory_bytes: 9148
//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 200005

typedef long long ll;

const ll mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int N, M, K;

struct node {
	ll at;
	ll cost;
	bool operator < (const node a) const {
		return this->at < a.at;
	}
}p[MAXN];

int main(void)
{
#ifdef Sunshine
	freopen("data.txt", "r", stdin);
#endif

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

	ll N, M, K;
	cin >> N >> M >> K;
	M *= 2;
	for (int i = 1; i <= N; i++)
		cin >> p[i].at >> p[i].cost;

	sort(p + 1, p + 1 + N);
	ll ans = 0;
	int j = 1;

	queue<pair<int, int> > q1;
	ll sum = 0;

	for (int i = 1; i <= N; i++) {
		if (!q1.empty()) {
			while (!q1.empty() && i >= q1.front().first)
				sum -= q1.front().second, q1.pop();
			if (!q1.empty()) {
				p[i].cost -= sum;
			}
		}

		if (p[i].cost <= 0)
			continue;

		ll res = p[i].cost / K + (p[i].cost % K == 0ll ? 0 : 1);
		ans += res;
		for (; j <= N; j++) {
			if (p[j].at > p[i].at + M)
				break;
		}
		q1.push({ j, res * K });
		sum += res * K;
	}

	cout << ans << '\n';
	



#ifdef Sunshine
	freopen("CON", "r", stdin);
	system("pause");
#endif
	return 0;
}

Measured memory_bytes: 4224
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

s = input()
t = input()

MAXV = 3100
dp = [[0] * MAXV for _ in range(MAXV)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

res = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        res = s[i-1] + res
        i -= 1
        j -= 1
print(res)

Measured memory_bytes: 119132
#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, S: str, T: str):
    ans=""
    for i in range(N):
        ans+=S[i]+T[i]
    print(ans)
    return


# 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)
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
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, S, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 12500
#include <stdio.h>
int main(void) {
  int N,i,j,suuti[200],min,ans = 0;
  scanf("%d",&N);
  for (i = 0;i < 2 * N;i++) {
    scanf("%d",&suuti[i]);
  }
  for (i = 0; i < 2 * N;i++) {
    min = suuti[0];
    for (j = 0;j < 2 * N;j++) {
      if (suuti[j] < min) min = suuti[j];
    }
    if (i % 2 == 0) ans += min;
    for (j = 0;j < 2 * N;j++) {
      if (suuti[j] == min) {
        suuti[j] = 9999;
        break;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

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

constexpr ll INF = ll(1e+18) + 1;

ll dist(ll a, ll b, ll c, ll d) {
    return abs(a-c) + abs(b-d);
}

int main() {
    int N;
    int t, x, y;
    int bt=0, bx=0, by=0;

    cin >> N;

    rep (i, N) {
        cin >> t >> x >> y;
        
        int dt = abs(t-bt);
        int dx = abs(x-bx);
        int dy = abs(y-by);

        if ((dt >= dx+dy) && ((dx+dy)%2 == dt%2)) {
            bt = t;
            bx = x;
            by = y;
            continue;
        } else {
            cout << "No" << endl;
            return 0;
        }
        
    }
    cout << "Yes" << endl;

}


Measured memory_bytes: 3560
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define sz(a) (int)a.size()
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const int MAXN = 100500;

ll a[MAXN], b[MAXN];
int n;
int p[MAXN];
bool used[MAXN];

int main()
{
  cin >> n;
  forn(i, n)
    cin >> p[i], p[i]--;

  forn(i, n)
    a[i] = (n + 5) * (i + 1);

  forn(i, n)
    b[i] = (n + 5) * (n - i);

  forn(i, n)
  {
    used[p[i]] = true;
    forn(j, n)
    {
      if (!used[j])
        a[j]++;
    }
  }

  forn(i, n)
    cout << a[i] << ' ';

  cout << '\n';
  forn(i, n)
    cout << b[i] << ' ';

	return 0;
}


Measured memory_bytes: 1024
N=int(input())
arms=[list(map(int,input().split())) for _ in range(N)]
points=[]
for i in range(N):
    points.append([arms[i][0]-arms[i][1],arms[i][0]+arms[i][1]])
#print(points)
points.sort(key=lambda x:x[1])
#print(points)
nowr=-float("inf")
cnt=0
for i in points:
    l,r=i
    if nowr<=l:
        nowr=r
        cnt=cnt+1
print(cnt)



Measured memory_bytes: 75992
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <iterator>
#include <queue>
#include <set>
#include <map>

using namespace std;

struct edge{
    int x,y,z;
};

vector<edge> s;

void push(int x,int y,int z){
    s.push_back({x,y,z});
}

void solve(){
    int L,M,N=0;
    cin >> L;
    for(M=1;M<=L;M<<=1)N++;
    
    M = 1;
    for(int i=1;i<N;i++){
        push(i,i+1,0);
        push(i,i+1,M);
        M<<=1;
    }

    for(int i=19;i>=0;i--){
        if((L>>i&1) && (L>=(1<<(i+1)))){
            push(i+1,N,M);
            M+=1<<i;
        }
    }

    cout << N << ' ' << s.size() << '\n';
    for(auto &i:s){
        cout << i.x << ' ' << i.y << ' ' << i.z << '\n';
    }
}

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

    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (Int i = 0; i < (Int)(n); i++)
typedef int64_t Int;
using namespace std;
 
int main(){
    int M; cin >> M;
    Int D = 0, S = 0;
    rep(i, M){
        Int d, c; cin >> d >> c;
        D += c; S += d*c;
    }

    cout << (D-1) + (S-1)/9 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <iomanip>
#include <iostream>
using namespace std;
using ll = long long;
ll INF = 9999999999999999;

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

int main(void){
    ll N; cin >> N;
    ll min_X = 100000000000000001;
    for(int i = 0; i < 5; i++){
        ll X;
        cin >> X;
        min_X = min(min_X, X);
    }
    ll ans = 4;
    ans += (N/min_X)+1;
    if(N % min_X == 0) ans--;
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

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; }

//改造
typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void solve() {
        int a;
        cin >> a;
        int ans = 3 * a * a;
        cout << ans << endl;

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 888
# code-festival-2016-qualcC - 二人のアルピニスト / Two Alpinists
def main():
    """
      /----\     <- x = y
     /      \--\
    /           \
      xi  yi
    0 ~ xi / xi ~ yi / yi+1 ~ N-1
    """
    N = int(input())
    T = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    x, y = T[-1], A[0]  # max of x, y
    xi, yi = T.index(x), N - A[::-1].index(y) - 1  # indices of x, y
    if x != y or xi > yi:  # corner case
        print(0)
        return
    MOD = 10 ** 9 + 7
    ans, cur = 1, 0
    for i in T[: xi + 1]:
        if i > cur:  # point of new altitude -> no choice (ans * 1)
            cur = i
        else:
            ans = (ans * cur) % MOD  # mulitple choices (1, 2, ..., cur)
    for _ in range(xi + 1, yi):
        ans = (ans * cur) % MOD
    for i in A[yi + 1 :]:
        if i < cur:
            cur = i
        else:
            ans = (ans * cur) % MOD
    print(ans)


if __name__ == "__main__":
    main()

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

int main(){
	string a,b,c;
	cin >> a >> b >> c;
	transform (a.begin(),a.end(),a.begin(),::toupper);
	transform (b.begin(),b.end(),b.begin(),::toupper);
	transform (c.begin(),c.end(),c.begin(),::toupper);
	cout << a[0] << b[0] << c[0] <<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    map <pair <int,int>,ll> m;
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int x=i%10;
        int f=i;
        int y=0;
        while (f)
            y=f%10,f/=10;
        m[{y,x}]++;
    }
    ll ans=0;
    map <pair <int,int>, int> used;
    map <pair <int,int>,ll > mm=m;
    for (auto to:m)
    {
        if (used[to.first]==0)
        {
            used[to.first]=1;
            if (to.fi.fi!=to.fi.se)
            ans+=2*to.second*mm[{to.first.second,to.first.first}];
            else
                ans+=to.se*to.se;
            used[{to.first.second,to.first.first}]=1;
        }
    }
    cout<<ans;



}

Measured memory_bytes: 256
#include <stdio.h>

#define N 2000
#define M 2000

int n,A[N];
int solve(int,int);

int main(){
    
    int q,m[M],i;
    
    scanf("%d",&n);
    for(i=0; i<n; i++) scanf("%d",&A[i]);
    
    scanf("%d",&q);
    for(i=0; i<q; i++) scanf("%d",&m[i]);
    
    for(i=0; i<q; i++){
        if(solve(0,m[i])==1) printf("yes\n");
        if(solve(0,m[i])==0) printf("no\n");
    }
    
    return 0;
}


int solve(int i ,int m){
    
    int res;
    
    if(m==0) return 1;
    if(i>=n) return 0;
    
    res = solve(i+1,m) || solve(i+1,m-A[i]);

    return res;
}

Measured memory_bytes: 588
import java.util.Scanner;

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

        final double A = Integer.parseInt(sc.next());
        final double B = Integer.parseInt(sc.next());
        final double H = Integer.parseInt(sc.next());
        final double M = Integer.parseInt(sc.next());

        final double parseH = H * 30d + (30d * (M / 60d));
        final double parseM = M * 6d;

        double ang = Math.abs(parseH - parseM);
        final double ans = Math.sqrt(Math.pow(A, 2) + Math.pow(B, 2) -2d * A * B * Math.cos(Math.toRadians(ang)));
        System.out.print(ans);
    }
}

Measured memory_bytes: 35904
a = input()
if 0<int(a[:2])<=12:
  if 0<int(a[2:])<=12:
    print("AMBIGUOUS")
  else:
    print("MMYY")
else:
  if 0<int(a[2:])<=12:
    print("YYMM")
  else:
    print("NA")

Measured memory_bytes: 2940
#include <iostream>

using namespace std;

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	int left = A + B;
	int right = C + D;

	if (left > right) {
		cout << "Left" << endl;
	}
	else if (left == right) {
		cout << "Balanced" << endl;
	}
	else {
		cout << "Right" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
///****In the name of ALLAH, most Gracious, most Compassionate****//

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

typedef long long ll;
typedef pair <ll, ll> pii;

#define ALL(a) a.begin(), a.end()
#define FastIO ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define IN freopen("input.txt","r+",stdin)
#define OUT freopen("output.txt","w+",stdout)

#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define NL cout<<endl

template < class T1,class T2>
ostream &operator <<(ostream &os,const pair < T1,T2 > &p)
{
    os<<"{"<<p.first<<","<<p.second<<"}";
    return os;
}

const ll N=1e6+5;


ll lft[N];
ll rht[N];

ll a[N];
ll b[N];
ll c[N];

bool a_b(ll l,ll r)
{
    return a[l]-b[l] >a[r]-b[r];
}

int32_t main()
{
    FastIO;
    ll x,y,z;
    cin>>x>>y>>z;
    ll n = x+y+z;
    vector < ll  > p (n,0);
    ll ans = 0;
    for(ll i=0; i<n; i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        p[i] = i;
    }
    sort(ALL(p), a_b);

    {
        priority_queue<ll > pq;
        ll now = 0, q = 0;
        for(ll i=0; i<n; i++)
        {
            ll ii = p[i];
            now+=c[ii];
            ll d= a[ii]-c[ii];
            q+=d;
            pq.push(-d);
            if(pq.size() > x)
            {
//                assert(pq.size());
                q+=pq.top();
                pq.pop();
            }
            lft[i] =now + q;
        }
    }
    {
        priority_queue<ll > pq;
        ll now = 0, q = 0;
        for(ll i=n-1; i>=0; i--)
        {
            ll ii = p[i];
            now+=c[ii];
            ll d= b[ii]-c[ii];
            q+=d;
            pq.push(-d);
            if(pq.size() > y)
            {
                q+=pq.top();
                pq.pop();
            }
            rht[i] =now + q;
        }
    }
    for(ll i=0; i<n-1; i++)
    {
        if(i+1 >= x and n-i-1 >= y)
            ans = max(ans, lft[i] + rht[i+1]);
    }
    cout<<ans<<"\n";
}


Measured memory_bytes: 15224
def is_correct(n, xs, ys, hs, cx, cy):
    h = abs(xs[0] - cx) + abs(ys[0] - cy) + hs[0]
    for i in range(1, n):
        if hs[i] != max(h - abs(xs[i] - cx) - abs(ys[i] - cy), 0):
            return None
    return h


def solve(n, xs, ys, hs):
    for cx in range(101):
        for cy in range(101):
            h = is_correct(n ,xs, ys, hs, cx, cy)
            if h is not None:
                print('{0} {1} {2}'.format(cx, cy, h))
                return


n = int(input())
xs = []
ys = []
hs = []

for i in range(n):
    line = [int(v) for v in input().split()]
    xs.append(line[0])
    ys.append(line[1])
    hs.append(line[2])

maxi = 0
for i in range(n):
    if hs[i] > hs[maxi]:
        maxi = i
hs[0], hs[maxi] = hs[maxi], hs[0]
xs[0], xs[maxi] = xs[maxi], xs[0]
ys[0], ys[maxi] = ys[maxi], ys[0]

solve(n, xs, ys, hs)

Measured memory_bytes: 3064
n, k = map(int, input().split())
S = input()
start =[]
end = [0]
if S[0] == "0":
    start.append(0)
for i in range(n):
    if S[i:i+2] == "10":
        start.append(i+1)
    elif S[i:i+2] == "01":
        end.append(i+1)

if len(start) <= k:
    print(len(S))
else:
    start.append(len(S))
    ans = []
    for i in range(len(start) - k):
        ans.append(start[i + k] - end[i])
    print(max(ans))

Measured memory_bytes: 8724
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

template<class T = lint>
struct Edge {
	int to;
	T cost;
	Edge() {}
	Edge(int to, T cost) : to(to), cost(cost) {}
	bool operator>(const Edge &r) const { return this->cost > r.cost; }
	friend ostream &operator<< (ostream &os, Edge e) { return os << "to: " << e.to << " cost: " << e.cost << endl; }
};

template<class T>
vector<T> Dijkstra(vector<vector<Edge<T>>> &edges, int st) {

	int V = (int)edges.size();
	const T inf = 1e5;
	vector<T> cost(V, inf);
	cost[st] = 0;

	priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> p_que;
	p_que.emplace(st, cost[st]);

	while (!p_que.empty()) {

		Edge<T> now(p_que.top().to, p_que.top().cost);
		p_que.pop();

		if (cost[now.to] < now.cost) continue;
		for (const Edge<T> &e : edges[now.to]) {
			T tmp_cost = now.cost + e.cost;
			if (cost[e.to] > tmp_cost) {
				cost[e.to] = tmp_cost;
				p_que.emplace(e.to, cost[e.to]);
			}
		}
	}

	return cost; // min cost to vertex idx from st
}

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

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	while (true) {

		int n, m, p, a, b;
		cin >> n >> m >> p >> a >> b;
		if (n == 0) break;
		a--, b--;

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

		const int bit_max = (1 << n);
		const double dinf = 1e5;

		vector<vector<Edge<double>>> edges(m*bit_max);
		for (int i = 0; i < p; i++) {

			int x, y;
			double z;
			cin >> x >> y >> z;
			x--, y--;

			for (int bit = 0; bit < bit_max; bit++) {
				for (int j = 0; j < n; j++) {
					int next_bit = bit | (1 << j);
					if (bit != next_bit) {
						edges[x*bit_max + bit].emplace_back(y*bit_max + next_bit, z / t[j]);
						edges[y*bit_max + bit].emplace_back(x*bit_max + next_bit, z / t[j]);
					}
				}
			}

		}

		auto dist = Dijkstra(edges, a*bit_max);
		double ans = dinf;
		for (int bit = 0; bit < bit_max; bit++) {
			chmin(ans, dist[b*bit_max + bit]);
		}

		if (ans == dinf) cout << "Impossible" << "\n";
		else cout << fixed << setprecision(5) << ans << "\n";

	}

	return 0;
}


Measured memory_bytes: 25584
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n-1); i >= 0; i--)
#define loop(i, r, n) for (int i = (r); i <= (n); i++)
#define pb push_back
#define all(in) in.begin(),in.end()

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

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

ll modpow(ll a, ll n, ll p) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}

int main(){
    ll n; cin >> n;
    string x; cin >> x; reverse(all(x));

    vector<ll> ans(n,0);

    ll count = 0; rep(i,n) if(x[i] == '1') count++;
    ll ans1 = 0; rep(i,n) if(x[i] == '1') ans1 += modpow(2,i,count+1), ans1 %= count+1;
    ll ans3 = 0; if(count > 1) rep(i,n) if(x[i] == '1') ans3 += modpow(2,i,count-1), ans3 %= count-1;

    rep(i,n){
        if(count > 1 && x[i] == '1') ans[i] = (ans3 - modpow(2,i,count-1) + (count-1) ) % (count-1);
        else if(count == 1 && x[i] == '1') ans[i] = n;
        else if(x[i] == '0') ans[i] = (ans1 + modpow(2,i,count+1) ) % (count+1);
    }
    vector<ll> ans12(n+1,0);
    rep(i,n){
        int d = i;
        int num = 0;
        while(d){
            d %= __builtin_popcount(d);
            num++;
        }
        ans12[i] = num;
    }
    ans12[n] = -1;

    rrep(i,n) cout << ans12[ans[i]]+1 << endl;
    return 0;
}

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


int main(void){
    
    int n;
    cin >> n;
    int i,a[n+1];
    for(i=0;i<n;++i) cin >> a[i];
    sort(a,a+n);
    //for(i=0;i<n;++i) cout << a[i];
    bool ali=true;
    int alice=0,bob=0; 
    for(i=n-1;i>=0;--i){
        if(ali){
            alice+=a[i];
            ali=false;
        }
        else {
            bob+=a[i];
            ali=true;
        }
    } 
    cout << alice - bob;
    
    
    return 0;
    
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

int main() {
    int N, K;
    cin >> N >> K;

    int KK = 2 * K;
    vector<vector<int>> cntW(KK, vector<int>(KK, 0));

    rep(i, N) {
        int x, y;
        string c;
        cin >> x >> y >> c;
        if (c == "W") {
            cntW[y % KK][x % KK]++;
        } else {
            cntW[y % KK][(x + K) % KK]++; // (x, y)が白と(x + K, y)が黒は同値
        }
    }

    vector<vector<int>> sum(KK + 1, vector<int>(KK + 1, 0));
    rep(i, KK) {
        rep(j, KK) sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + cntW[i][j];
    }

//    rep(i, KK) {
//        rep(j, KK) cout << cntW[i][j] << " ";
//        cout << endl;
//    }
//
//    cout << "-----------" << endl;
//    rep(i, KK + 1) {
//        rep(j, KK + 1) cout << sum[i][j] << " ";
//        cout << endl;
//    }

    ll ans = 0;
    rep(i, K + 1) {
        rep(j, K + 1) {
            ll tmp = 0;
            int a = sum[i][j];
            int b = sum[i + K][j + K] - sum[i + K][j] - sum[i][j + K] + sum[i][j];
            int c = sum[KK][j] - sum[i + K][j];
            int d = sum[i][KK] - sum[i][j + K];
            int e = sum[KK][KK] - sum[KK][j + K] - sum[i + K][KK] + sum[i + K][j + K];
            tmp = a + b + c + d + e;
//            cout << "(" << i << "," << j  << ")" << " a:" << a << " b:" << b << " c:" << c << " d:" << d << " e:" << e << " tmp:" << tmp << endl;
            chmax(ans, max(tmp, N - tmp));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 31616
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
queue<int> que;
for(int i=0;i<n;i++){
    if(b[i]>a[i]&&(b[i]-a[i])>=b[(n+i-1)%n]+b[(i+1)%n])que.push(i);
}
int ans=0,i;
while(!que.empty()){
    i=que.front();
    que.pop();
    ans+=(b[i]-a[i])/(b[(n+i-1)%n]+b[(i+1)%n]);
    b[i]=a[i]+(b[i]-a[i])%(b[(n+i-1)%n]+b[(i+1)%n]);
    i=(n+i-1)%n;
    if(b[i]>a[i]&&(b[i]-a[i])>=b[(n+i-1)%n]+b[(i+1)%n])que.push(i);
    i=(i+2)%n;
    if(b[i]>a[i]&&(b[i]-a[i])>=b[(n+i-1)%n]+b[(i+1)%n])que.push(i);
}
for(int i=0;i<n;i++){
    if(a[i]!=b[i]){
        cout<<-1;
        return 0;
    }
}
cout<<ans;





return 0;
}


Measured memory_bytes: 4224
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static Scanner s=new Scanner(System.in);
	public static void main(String[] __){
		while(true){
			String in=s.next();
			int length=s.nextInt();
			if(length==0) return;
			
			ArrayList<Integer> list=new ArrayList<>();
			list.add(Integer.parseInt(in));
			in=String.format("%0"+length+"d",list.get(0));
			
			for(int l=1;true;l++){
				char[]buf=in.toCharArray();
				Arrays.sort(buf);
				int
				small=Integer.parseInt(String.valueOf(buf)),
				large=Integer.parseInt(String.valueOf(reverse(buf))),
				i;
				if((i=list.indexOf(large-small))>=0) {
					System.out.printf("%d %d %d\n",i,large-small,l-i);
					break;
				}
				list.add(large-small);
				in=String.format("%0"+length+"d",large-small);
			}
		}
	}
	public static char[] swap(char[] c,int a,int b){
		char x=c[b];
		c[b]=c[a];
		c[a]=x;
		return c;
	}
	public static char[] reverse(char[] c,int l,int r){
		int buf=(l+r+1)/2;
		for(int i=l;i<buf;i++){
			swap(c,i,r-i+l);
		}
		return c;
	}
	public static char[] reverse(char[] c){
		return reverse(c,0,c.length-1);
	}
}

Measured memory_bytes: 29752
import java.util.Scanner;

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

        if(x>=30){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35688
#include <iostream>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

constexpr int MOD = 1e9 + 7;
constexpr int INFi = 2e9 + 1;
constexpr lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
constexpr char BR = '\n';

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define vREPcopy(ele, vec) for(auto (ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())


template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;}
  std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



std::string judge(int p, int q){
  if(p <= 0 and q >= 0) return "Zero";
  if(p > 0) return "Positive";
  // p, q < 0
  return ((q - p) % 2 == 0) ? "Negative" : "Positive";
}

int main(void){
  int a, b;
  scanf("%d %d", &a, &b);
  cout << judge(a, b) << BR;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n;

int func(int a){
	int r = 0;
	for(int i = 1; i <= 5; i++){
		r += a%10;
		a /= 10;
	}
	return r;
}

int main(){
	cin >> n;
	
	int ans = n;
	for(ll i = 1; i <= n/2+1; i++){
		ans = min(func(i)+func(n-i), ans);
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define vi vector<int>
#define vvi vector<vector<int>>
using namespace std;

class UnionFind {
private:
    vector<vector<int>> Graph; // {ID,Number,ParentID,Height}

    void flatten(int x, int rootid) {
        int parentid = Graph[x][0];
        while (Graph[parentid][0] != Graph[parentid][2]) {
            Graph[parentid][2] = rootid;
            int next = Graph[parentid][2];
            parentid = next;
        }
    }
public:
    void push(int x) {
        int i = Graph.size();
        Graph.push_back({ i,x,i,1 });
    }
    void unite(int x, int y) {
        int hx = Graph[root(x)][3];
        int hy = Graph[root(y)][3];
        if (hx < hy) {
            Graph[root(x)][2] = root(y);
            flatten(x, root(y));
        }
        else if(hx == hy){
            Graph[root(y)][2] = root(x);
            Graph[root(x)][3]++;
            flatten(y, root(x));
        }
        else {
            Graph[root(y)][2] = root(x);
            flatten(y, root(x));
        }
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }

   
    int root(int x) {
        int parentid = Graph[x][0];
        while (Graph[parentid][0] != Graph[parentid][2]) {
            int next = Graph[parentid][2];
            parentid = next;
        }
       
        return parentid;
    }
};

int main() {
    int n; cin >> n;
    vector<vector<int>> edges; // {weight, from_id, to_id} both 0-indexed
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int w; cin >> w;
            if (w == -1) {
                continue;
            }
            else {
                vector<int> temp_edge = { w,i,j };
                edges.push_back(temp_edge);
            }
        }
    }

    sort(ALL(edges));
    int n_edges = 0;
    int TotalCost = 0;

    UnionFind uf;
    for (int i = 0; i < n; i++) uf.push(i);

    for (int i = 0; n_edges < n - 1; i++) {
        vector<int> edge = edges[i];
       
        if (uf.root(edge[1]) != uf.root(edge[2])) {
            uf.unite(edge[1], edge[2]);
            n_edges++;
            TotalCost += edge[0];
        }
    }


    cout << TotalCost << endl;
}


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

struct point {
        int x, y;
        point(int x, int y) : x(x), y(y) { }
};

const int INF = (1 << 30);

int main() {
    map<int, int> dx, dy;
    dx[INF] = 0; dx[-INF] = 0;
    dy[INF] = 0; dy[-INF] = 0;
    vector<int> px, py;
    vector<point> s, t;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        dx[a] = 0; dy[b] = 0;
        dx[c] = 0; dy[d] = 0;
        s.emplace_back(a, b);
        t.emplace_back(c, d);
    }

    for (auto &e : dx) {
        e.second = px.size();
        px.push_back(e.first);
    }
    for (auto &e : dy) {
        e.second = py.size();
        py.push_back(e.first);
    }

    const int h = px.size(), w = py.size();
    vector<vector<int>> g(h, vector<int>(w, 0));

    for (int i = 0; i < n; i++) {
        g[dx[s[i].x]][dy[s[i].y]]++;
        g[dx[t[i].x]][dy[s[i].y]]--;
        g[dx[s[i].x]][dy[t[i].y]]--;
        g[dx[t[i].x]][dy[t[i].y]]++;
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j + 1 < w; j++) {
            g[i][j + 1] += g[i][j];
        }
    }
    for (int j = 0; j < w; j++) {
        for (int i = 0; i + 1 < h; i++) {
            g[i + 1][j] += g[i][j];
        }
    }

    long long ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (g[i][j] == 0) continue;
            long long r = abs(px[i] - px[i + 1]);
            long long c = abs(py[j] - py[j + 1]);
            ans += r * c;
        }
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 65896
m=int(input())

if 400 <= m and m <= 599:
  n=8
elif 600 <= m and m <= 799:
  n=7
elif 800 <= m and m <= 999:
  n=6
elif 1000 <= m and m <= 1199:
  n=5
elif 1200 <= m and m <= 1399:
  n=4
elif 1400 <= m and m <= 1599:
  n=3
elif 1600 <= m and m <= 1799:
  n=2
elif 1800 <= m and m <= 1999:
  n=1
  
print(n)

Measured memory_bytes: 9184
from sys import exit
MOD = 998244353
s, K = input().split()
K = min(int(K), s.count("1"))
if K == 0:
	print(1)
	exit()

a = []
cnt = 0
for i in range(len(s)):
	if s[i] == "0":
		a.append(cnt)
		cnt = 0
	else:
		cnt += 1
a.append(cnt)
a.reverse()
#print(a)
n = len(a)
dp = [[[0 for _ in range(K+1)] for _ in range(K+1)] for _ in range(n+1)]
col = [[0 for _ in range(K+1)] for _ in range(K+1)]
dia = [[0 for _ in range(K+1)] for _ in range(K+1)]
dp[0][0][0] = 1
col[0][0] = 1
for j in range(K+1):
	dia[j][j] = 1

#減らす
def COL(j, k):
	if k == 0:
		return col[j][j]
	else:
		return col[j][j] - col[j][k-1]

#増やす
def DIA(i, j, k):
	if k == 0:
		return 0
	elif k > a[i-1]:
		return dia[j-1][k-1] - dia[j-a[i-1]-1][k-a[i-1]-1]
	else:
		return dia[j-1][k-1]

for i in range(1, n+1):
	for j in range(K+1):
		for k in range(j+1):
			dp[i][j][k] += COL(j, k)
			dp[i][j][k] += DIA(i, j, k)
			dp[i][j][k] %= MOD
	for j in range(K+1):
		col[j][0] = dp[i][j][0]
		dia[j][0] = dp[i][j][0]
		for k in range(1, j+1):
			col[j][k] = (col[j][k-1] + dp[i][j][k]) % MOD
			dia[j][k] = (dia[j-1][k-1] + dp[i][j][k]) % MOD

ans = 0
for j in range(K+1):
	ans += dp[n][j][0]
	ans %= MOD
print(ans)

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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

constexpr int64 P = 1000000007;

struct FiniteField {
 private:
  int64 x;
  static inline int64 Normalize(int64 x) {
    if (0 <= x && x < P) return x; x %= P; if (x < 0) x += P; return x;
  }
 public:
  FiniteField(int64 x) : x(Normalize(x)) {}
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

ostream& operator<<(ostream& s, const FiniteField& v) { s << v.Value(); return s; }

tuple<vector<FiniteField>, vector<FiniteField>> MakeFactorialTables(int n) {
  vector<FiniteField> factorials(n + 1);
  vector<FiniteField> inverse_factorials(n + 1);
  factorials[0] = 1;
  for (int i = 1; i <= n; i++) {
    factorials[i] = factorials[i - 1] * i;
  }
  inverse_factorials[n] = FiniteField(1) / factorials[n];
  for (int i = n; i >= 1; i--) {
    inverse_factorials[i - 1] = inverse_factorials[i] * i;
  }
  return make_tuple(factorials, inverse_factorials);
}

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

  int r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;
  vector<FiniteField> fs, i_fs;
  tie(fs, i_fs) = MakeFactorialTables(r2 + c2 + 2);
  auto c_fn = [&](int a, int b) -> FiniteField {
    if (a < b) return 0;
    return fs[a] * i_fs[b] * i_fs[a - b];
  };
  auto solve_fn = [&](int r, int c) -> FiniteField {
    if (r == 0 || c == 0) return FiniteField(max(r, c) + 1);
    FiniteField rv = 0;
    for (int i = 0; i <= r; i++) {
      rv += c_fn(c + i + 1, i + 1);
    }
    return rv;
  };
  FiniteField ans =
      solve_fn(r2, c2) - solve_fn(r1 - 1, c2) - solve_fn(r2, c1 - 1) + solve_fn(r1 - 1, c1 - 1);
  cout << ans << endl;
}

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

#define ll long long
//#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main()
{
  //  fast_io;
    int a,b;
    cin >> a >> b;
    b = 2 * b;
    int ans = a - b;
    if(ans < 0)
    {
        cout << "0\n";
    }
    else
    {
        cout << ans << "\n";
    }

}


Measured memory_bytes: 3616
S = input()[::-1]
dividor = ['dream','dreamer','erase','eraser']
j=0
while True:
    flag = 0
    for d in dividor:
        if S[j:j+len(d)]==d[::-1]:
            flag = 1
            j+=len(d)
            if j==len(S):
                print("YES")
                quit() 
    if flag==0:
        print("NO")
        quit()

Measured memory_bytes: 3188
import bisect


def LI():
    return list(map(int, input().split()))


N = int(input())
L = LI()
L.sort()
ans = 0

for i in range(N-1, 1, -1):
    for j in range(i-1, 0, -1):
        xl = L[i]-L[j]
        ind = bisect.bisect_right(L, xl)
        if j > ind:
            ans += j-ind
print(ans)


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

using namespace std ; 

const int N = 1e5 + 7 ; 


int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0); 
    //freopen("in.in" ,"r" , stdin) ; 
    int n , m ; 
    cin>>n>>m ;
    if(m >= n)cout<<"unsafe" ; 
    else cout<<"safe"  ;
    return 0 ; 
}

Measured memory_bytes: 3600