akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;
using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
  int N;
  cin >> N;
  vector<int> L(N);
  for( int i=0; i<N; i++ ) cin >> L.at(i);
  sort( L.begin(), L.end() );
  
  int ans = 0;
  int num_of_longest;
  for( int i=0; i<N-2; i++ ){
    for( int j=i+1; j<N-1; j++ ){
      num_of_longest = lower_bound( L.begin(), L.end(), L.at(i)+L.at(j) ) - L.begin();
      // Lの要素のうち、keyより小さい要素の数
      ans += num_of_longest - (j+1);
    }
  }
  cout << ans;
  return 0;
}


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

typedef long long ll;

int t = 1;

void solve() {
	int x, y; 
	cin >> x >> y;
	
	
	if (y >= 2 * x && y <= 4 * x && y % 2 == 0) {
			cout << "Yes" << endl;
	}else {
			cout << "No" << endl;
	}
}

int main() 
{ 
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("data.in", "r", stdin);
	
	//cin >> t;
	while (t--) solve();
	
    return 0; 
}

























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

bool mat[55][55];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int h, w;

void solve() {
  for (int i = 1; i <= h; ++i) {
    for (int j = 1; j <= w; ++j) {
      if (mat[i][j]) {
        rep(k, 4) {
          if (mat[i+dx[k]][j+dy[k]]) break;
          if (k == 3) {
            cout << "No" << endl;
            return;
          }
        }
      }
    }
  }
    cout << "Yes" << endl;
}

int main() {
  cin >> h >> w;
  for (int i = 1; i <= h; ++i) {
    for (int j = 1; j <= w; ++j) {
      char s;
      cin >> s;
      if (s == '#') mat[i][j] = 1;
    }
  }
  
  solve();
  return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func checkOdd(a []int) bool {
	for i := 0 ; i < len(a) ; i++ {
		if a[i] % 2 == 1 {
			return true
		}
	}
	return false
}

func main() {
	var n,count int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0 ; i < n ; i++ {
		fmt.Scan(&a[i])
	}
	for ;; {
		if checkOdd(a) {
			break
		}
		for i := 0 ; i < len(a) ; i++ {
			a[i] = a[i] / 2
		}
		count++
	}
	fmt.Println(count)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;

int par[MAX];

void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
    }
}

int root(int a){
    if(par[a]==a) return a;
    else return par[a]=root(par[a]);
}

void unite(int a,int b){
    if(root(a)!=root(b)) par[root(b)]=root(a);
}

bool check(int a,int b){
    return root(a)==root(b);
}

bool compare(pair<int,ll> a,pair<int,ll> b){
    return a.second<b.second;
}

int main(){
    
    int N,M;cin>>N>>M;
    vector<pair<int,ll>> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i].second;
    }
    
    init(N);
    
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        unite(a,b);
    }
    
    set<int> S;
    
    for(int i=0;i<N;i++){
        S.insert(root(i));
        A[i].first=root(i);
    }
    
    if(2*(S.size()-1)>N) cout<<"Impossible"<<endl;
    else if(S.size()==1) cout<<0<<endl;
    else{
        sort(all(A));
        ll ans=0;
        ans+=A[0].second;
        A[0].second=INF;
        for(int i=1;i<N;i++){
            if(A[i].first!=A[i-1].first){
                ans+=A[i].second;
                A[i].second=INF;
            }
        }
        
        sort(all(A),compare);
        
        for(int i=0;i<int(S.size())-2;i++){
            ans+=A[i].second;
        }
        
        cout<<ans<<endl;
    }
}


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

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


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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 998244353ll;
const ll MAXN = (ll) 4e3 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-8;

ll dp[MAXN][MAXN];
vector<ll> r, b;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	str s;
	cin >> s;
	ll n = s.size();
	s = '!' + s;
	//ll cn = 0;
	for(int i = 1; i <= n; i++){
		if(s[i] == '2'){
			b.pb(i); b.pb(i);
		}
		if(s[i] == '0'){
			r.pb(i); r.pb(i);
		}
		if(s[i] == '1'){
			b.pb(i); r.pb(i);
		}
	}
	ll cnr = r.size();
	ll cnb = b.size();
	dp[0][0] = 1;
	ll rd, bl;
	//debug(n);
	for(int i = 1; i <= n + n;i++){
		for(int j = 0; j <= cnr; j++){
			rd = j;
			bl = i - j;
			if(bl > cnb){
				dp[i][j] = 0;
				continue;
			}
			if(rd > 0){
				if(r[rd - 1] <= i) dp[i][j] += dp[i - 1][j - 1];
			}
			if(bl > 0){
				if(b[bl - 1] <= i) dp[i][j] += dp[i - 1][j];
			}
			//if(dp[i][j]) debug(i), debug(j);
			dp[i][j] %= MOD;
		}
	}
	cout << dp[n + n][cnr];
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/


Measured memory_bytes: 125568
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
//#define INF 1100000000000000000LL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=1050;
//ここまでテンプレ
int main() {
	int N,A,B;
	cin>>N>>A>>B;
	cout<<min(A*N,B)<<endl;
    return 0;
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(obj) obj.begin(), obj.end()

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

const int iINF = 1e9;
const long long llINF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

int main() { 
    int N;
    cin >> N;
    vector<int> X(N);
    REP(i, N) {
        cin >> X[i];
    }
    int ans = iINF;
    for (int i = 1; i <= 100; i++) {
        int tmp = 0;
        for (int j = 0; j < N; j++) {
            tmp += (X[j] - i) * (X[j] - i);
        }
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0; 
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef long long int ll;
void swap(ll *x,ll *y){ll temp;temp=*x;*x=*y;*y=temp;}
ll compare_asc(const void *a,const void *b){return *(ll*)a-*(ll*)b;}
ll compare_desc(const void *a,const void *b){return *(ll*)b-*(ll*)a;}
ll max(ll x,ll y){return x>y?x:y;}
ll min(ll x,ll y){return x>y?y:x;}
/*void qsort(配列のアドレス,配列のサイズ,sizeof(配列の型),比較関数(昇順or降順)) */

int main(){
    int n,k,l[100];

    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&l[i]);

    qsort(l,n,sizeof(int),compare_desc);
    int sum=0;
    for(int i=0;i<k;i++)sum+=l[i];
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 128
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
x,k,d = inm()
x = abs(x)
ans = x - k * d
if ans < 0:
    c = x//d
    k -= c
    k = k%2
    ans = x - d * c
    ans -=  d * k
print(abs(ans))

Measured memory_bytes: 9268
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

int main() {
    bool yes = true;
    int N;
    cin >> N;
    set<ll> numbers;
    for (int i = 0; i < N; i++) {
        ll A;
        cin >> A;
        if (numbers.count(A) == 1) {
            yes = false;
            break;
        }
        numbers.insert(A);
    }
    cout << (yes ? "YES" : "NO") << endl;
    return 0;
}



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

using namespace std;

#define show(x) cerr << #x << " = " << x << endl;


int main()
{

  string cad;
  cin>>cad;

  set<char> uniques(cad.begin(), cad.end());

  if(cad.size()==uniques.size())
  {
    cout<<"yes"<<endl;
  }
  else
  {
    cout<<"no"<<endl;
  }



  return 0;
}


Measured memory_bytes: 256
import math
import itertools


def dist(x, y):
    return math.sqrt((y[1] - x[1]) ** 2 + (y[0] - x[0]) ** 2)


if __name__ == "__main__":
    N = int(input())

    towns = []
    for _ in range(N):
        x, y = [int(x) for x in input().split(" ")]
        towns.append((x, y))
    dists = []
    for route in itertools.permutations(range(N)):

        d = 0
        for i in range(N - 1):
            from_ = route[i]
            to = route[i + 1]
            d += dist(towns[from_], towns[to])
        dists.append(d)
    print(sum(dists) / len(dists))

Measured memory_bytes: 4400
#include <iostream>

using namespace std;

int main() {
	int n = 0;
	int cnt[2] = {};
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x = 0;
		cin >> x;
		cnt[x & 1]++;
	}
	cnt[0] += cnt[1] / 2;
	cnt[1] %= 2;
	cnt[0] = min(cnt[0], 1);
	if (cnt[0] + cnt[1] == 1) {
		cout << "YES";
	} else
	cout << "NO";
	return 0;
}

Measured memory_bytes: 256
#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 705
#define lo long long
using namespace std;
int n,m,A[li][li],x,y,vis[li],flag,reg,sum;
vector<int> v[li],bolge[li];
int bir,iki,l[li],r[li];
int dp[li][li];
void dfs(int node,int col){
	if(vis[node]!=0 && col!=vis[node]) flag=1;
	if(vis[node]!=0) return ;
	vis[node]=col;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		dfs(go,3-col);
	}
}
void dfs2(int node){
	if(vis[node]==1) return ;
	vis[node]=1;
	bolge[reg].pb(node);
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		dfs2(go);
	}
}
void dfs3(int node,int color){
	if(vis[node]==1) return ;
	vis[node]=1;
	if(color==1) bir++;
	else iki++;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		dfs3(go,3-color);
	}
}
int son(int node,int sol){
	int cev=inf;
	if(node==reg+1){
		int sag=sum-sol;
		return (sol*(sol-1))/2+(sag*(sag-1))/2;
	}
	if(~dp[node][sol]) return dp[node][sol];
	cev=min(cev,son(node+1,sol+l[node]));
	cev=min(cev,son(node+1,sol+r[node]));
	return dp[node][sol]=cev;
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		A[x][y]=1;
		A[y][x]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			if(A[i][j]==0){
				v[i].pb(j);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0) dfs(i,1);
	}
	if(flag==1){
		printf("-1\n");
		return 0;
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			reg++;
			dfs2(i);
		}
	}
	for(int i=1;i<=reg;i++){
		memset(vis,0,sizeof(vis));
		int basla=bolge[i][0];
		bir=0,iki=0;
		dfs3(basla,1);
		l[i]=bir;
		r[i]=iki;
		sum=sum+l[i]+r[i];
	}
	int ty=son(1,0);
	printf("%d\n",ty);
	return 0;
}




Measured memory_bytes: 5120
n = input()
m = n.split()
a = [input() for l in range(0,1)]
b = a[0].split()
for i in range(0, len(b)):
    b[i] = int(b[i])
c = sorted(b, reverse=True)
p = 0
for i in range(int(m[0]) - int(m[1]),int(m[0])):
    p = p + int(c[i])
print(p)

Measured memory_bytes: 9228
n, m = map(int, input().split())
a = list(map(int, input().split()))
t = 0
for i in a:
    t += i
t_avg = t * (1 / (4 * m))

count = 0
for j in a:
    if j >= t_avg:
        count += 1
if count >= m:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9080
n = int(input())
c1 = [2, 4, 5, 7, 9]
c2 = [0, 1, 6, 8]
r = 'bon'
if n % 10 in c1:
    r = 'hon'
elif n % 10 in c2:
    r = 'pon'
print(r)

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

using namespace std;

int main(){
    long long int a,b,c,d;
    cin >> a >> b >> c >> d;
    long long int ac,ad,bc,bd,max;
    ac = a*c;
    max = ac;
    ad = a*d;
    if(max < ad) max = ad;
    bc = b*c;
    if(max < bc) max = bc;
    bd = b*d;
    if(max < bd) max = bd;
    cout << max << endl;
     
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define rep(i, init, n) for(int i = init; i <(int)(n); i++)

int main() {
    ll N, Q;
    ll ans = 0;
    cin >> N;
    ll a, b, c;
    map<ll, ll> m;
    REP(i, N){
        cin >> a;
        m[a]++;
        ans += a;
    }
    cin >> Q;
    vector<ll> h;
    REP(i, Q){
        cin >> b >> c;
        ans += (c - b) * m[b];
        h.push_back(ans);
        m[c] += m[b];
        m[b] = 0;
    }
    REP(i, Q) cout << h[i] << endl;

    return 0;
}

Measured memory_bytes: 9508
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
  ll i,n,k,c=0,num;
  cin>>n>>k;
  for(i=0;i<n;i++)
  {
    cin>>num;
    if(num>=k)
      c++;
  }
  cout<<c;
}
    

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<set>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back
 
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef long long ll;

int main(){
	int n,ans=0;
	cin>>n;
	REP(i,1,n+1){
		ans+=800;
		if(i%15==0)
			ans-=200;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int x,a,b;
    cin >> x >> a >> b;
    if(a-b >= 0){cout << "delicious" << endl;}
    else if(a-b >= x*(-1)){cout << "safe" << endl;}

    else cout << "dangerous" << endl;

  return 0;
}

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

using namespace std;

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

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

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

int main() {
  int N = in();
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    A[i] = in();
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());

  int r = 0, c = 0;
  while (true) {
    const int rr = r + 1, cc = c + 1;
    if (cc >= N || rr >= A[cc]) {
      break;
    }
    r = rr; c = cc;
  }

  int rig = 0;
  while (true) {
    if (c + rig + 1 >= N || r >= A[c + rig + 1]) {
      break;
    }
    ++rig;
  }

  int upp = A[c] - 1 - r;

  if (rig % 2 == 0 && upp % 2 == 0) {
    puts("Second");
  } else {
    puts("First");
  }

  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m;
  cin>>m>>n;
  int dp[m]={0};
  ll wrong_ans=0;
  ll correct_ans=0;
  bool correct[m]={false};
  for(ll i=0;i<n;i++){
      ll x;
      string s;
      cin>>x>>s;
      --x;
      if(s=="AC" && !correct[x]){
         wrong_ans+=dp[x];
         correct_ans++;
         correct[x]=true;
     }
     else
     dp[x]++;
  }
  cout<<correct_ans<<" "<<wrong_ans<<endl;
  return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A , B , C , D ;
  cin >> A >> B >> C >> D ;
  
  A+=B ;
  C+=D ;
    
  if (A > C) {
    cout << "Left" << endl; }
    
   else if (A == C) {
     cout << "Balanced" << endl;}
     
    if  (A < C) {
       cout << "Right" << endl;}
    
}

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

int main(){
   int N;
   cin >> N;
   map<string, map<int, int>> sp;
   for (int i=1; i<=N; i++){
      string s;
      int p;
      cin >> s >> p;
      sp[s].emplace(-p, i);
   }

   for (auto maps : sp){
      for (auto mapp : maps.second){
         cout << mapp.second << endl;
      }
   }

}



Measured memory_bytes: 256
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

n, k, l = map(int, input().split())

uf_road = UnionFind(n)
uf_train = UnionFind(n)

for _ in range(k):
  p, q = map(lambda x:int(x)-1, input().split())
  uf_road.Unite(p, q)

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

root_road = [0]*n 
root_train = [0]*n 

for i in range(n):
  root_road[i] = uf_road.Find_Root(i)
  root_train[i] = uf_train.Find_Root(i)

from collections import defaultdict
pair = defaultdict(int)
for i in range(n):
  pair[(root_road[i], root_train[i])] += 1 

for i in range(n):
  print(pair[(root_road[i], root_train[i])], end=" ")

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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

string _to(int x) {
    int v; string buf;
    if (v = x / 1000) {
        if (v > 1) buf += to_string(v);
        buf += 'm';
    } x %= 1000;
    if (v = x / 100) {
        if (v > 1) buf += to_string(v);
        buf += 'c';
    } x %= 100;
    if (v = x / 10) {
        if (v > 1) buf += to_string(v);
        buf += 'x';
    } x %= 10;
    if (v = x / 1) {
        if (v > 1) buf += to_string(v);
        buf += 'i';
    } x %= 1;
    return buf;
}

int _from(string x) {
    int buf = 1, ttl = 0;
    for (char c : x) {
        switch(c) {
            case 'm': ttl += buf * 1000; buf = 1; break;
            case 'c': ttl += buf * 100; buf = 1; break;
            case 'x': ttl += buf * 10; buf = 1; break;
            case 'i': ttl += buf * 1; buf = 1; break;
            default: buf = c - '0'; break;
        }
    }
    return ttl;
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        string a, b; cin >> a >> b;
        cout << _to(_from(a) + _from(b)) << endl;
    }
}


Measured memory_bytes: 3252
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse4,avx,avx2")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <chrono>
#include <random>
#include <string>
#include <queue>
#include <tuple>
#include <unordered_map>
#include <sstream>
#include <numeric>
#include <complex>
#include <immintrin.h>
#include <unordered_set>

using namespace std;

using ll = long long;
using ld = long double;
using VectorType = ld;
using ull = unsigned long long;

const ll INF = 1e15;
const ld eps = 1e-7;
const ld pi = atan2(0, -1);
const ll mod = 1e9 + 7;
const ll P = 179, Q = 239;
const ll A = 26;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

ll sign(ll a) {
	if (a < 0) return -1;
	if (a == 0) return 0;
	return 1;
}

bool equal(ld a, ld b) {
	return abs(a - b) < eps;
}

struct query {
	ll l, r, i;

	query(ll l = 0, ll r = 0, ll i = 0) : l(l), r(r), i(i) {};
};

bool mini(ll &a, ll b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

bool maxi(ll &a, ll b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool mini(ld &a, ld b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

ll mmax(ll a, ll b) {
	if (a > b) return a;
	return b;
}

ll mmin(ll a, ll b) {
	if (a < b) return a;
	return b;
}

ld mmax(ld a, ld b) {
	if (a > b) return a;
	return b;
}

ld mmin(ld a, ld b) {
	if (a < b) return a;
	return b;
}

bool maxi(ld &a, ld b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

ll sub(ll a, ll b) {
	a -= b;
	if (a < 0) {
		a += mod;
	}
	return a;
}

ll add(ll a, ll b) {
	a += b;
	if (a > mod) {
		a -= mod;
	}
	return a;
}

ll mul(ll a, ll b) {
	return (a * b) % mod;
}

ll n, m;
ll k;
vector <vector <ll>> vec;
vector <bool> used;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}
	return 0;
}

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

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

ll X[MAX_N];

int main(){
  int N; ll A,B;
  cin >> N >> A >> B;
  rep(i,N) scanf("%lld",X+i);
  ll ans = 0LL;
  rep(i,N-1){
    ans += min(A*(X[i+1]-X[i]),B);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <numeric>
#include <iterator>

using namespace std;

namespace {

}

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

	vector<int> a(N,0);
	for (int i = 0; i < N; ++i){
		cin >> a[i];
	}

	int counts = 0;
	for (int i = 0; i < N; ++i){
		int j = a[i];
		if (a[j-1] -1 == i){
			++counts;
		}
	}

	cout << counts / 2 << endl;

	return 0;
}

Measured memory_bytes: 3792
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Map<String, Integer> s = new HashMap<>(N);
		long ans = 0;
		for (int i = 0; i < N; i++) {
			String[] input = sc.next().split("");
			Arrays.sort(input);
			String tmp = String.join("", input);
			if (s.containsKey(tmp)) {
				int v = s.get(tmp) + 1;
				ans += v;
				s.put(tmp, v);
			} else {
				s.put(tmp, 0);
			}
		}
		System.out.println(ans);
		sc.close();
	}
}

Measured memory_bytes: 97856
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
verti = [N-2]*(N-1)
horiz = [N-2]*(N-1)

left, top = N-2, N-2
ans = (N-2)**2
last_top = (N-2, N-2)
last_left = (N-2, N-2)
for _ in range(Q):
    c, x = mapint()
    x -= 1
    if c==1:
        if x<=left:
            ans -= top
            left = x-1
            for i in range(left, last_left[0]+1):
                horiz[i] = last_top[1]
            last_left = (left, x-1)
        else:
            ans -= horiz[x-1]
    if c==2:
        if x<=top:
            ans -= left
            top = x-1
            for i in range(top, last_top[0]+1):
                verti[i] = last_left[1]
            last_top = (top, x-1)
        else:
            ans -= verti[x-1]
print(ans)

Measured memory_bytes: 77084
#include <algorithm>
#include <cstdio>

using namespace std;

int main() {
  char str[7];
  int ans = 0;

  scanf("%s", str);
  for (int i = 0; i < 6; i++) {
    if (str[i] == '1') {
      ans++;
    }
  }

  printf("%d", ans);

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h,w;
    cin >> h >> w;

    vector<vector<int>> a(h,vector<int>(w));
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> a[i][j];
        }
    }

    bool move = false;
    vector<int> xs;
    vector<int> ys;
    vector<int> xe;
    vector<int> ye;

    for (int i = 0; i < h; i++)
    {
        if(i % 2 == 0)
        {
            for (int j = 0; j < w; j++)
            {
                if(move)
                {
                    xe.push_back(j + 1);
                    ye.push_back(i + 1);
                    a[i][j] += move;
                }
                if(a[i][j] % 2 == 1)
                {
                    xs.push_back(j + 1);
                    ys.push_back(i + 1);
                    move = true;
                }
                else
                {
                    move = false;
                }
            }
        }
        else
        {
            for (int j = w - 1; j >= 0; j--)
            {
                if(move)
                {
                    xe.push_back(j + 1);
                    ye.push_back(i + 1);
                }
                a[i][j] += move;
                if(a[i][j] % 2 == 1)
                {
                    xs.push_back(j + 1);
                    ys.push_back(i + 1);
                    move = true;
                }
                else
                {
                    move = false;
                }
            }
        }
    }

    //cout << ys.size() << " " << xs.size() << " " << ye.size() << " " << xe.size() << " " << endl;

    int mini_size = min(ys.size(), min(ye.size(), min(xe.size() , xs.size())));
    cout << mini_size << endl;
    for (int i = 0; i < mini_size; i++)
    {
        cout << ys[i] << " " << xs[i] << " " << ye[i] << " " << xe[i] << endl;
    }
    
}


Measured memory_bytes: 5224
while True:
        a = int(input())
        if a == 0:
                break
         
        b = [int(input()) for i in range(a)]
        b.sort()
        bmin = min(b)
        bmax = max(b)
        bsum = sum(b)
        print((bsum-bmin-bmax)//(a-2))


Measured memory_bytes: 5600
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long int x,a,b,temp,tool;
    cin>>x;
    for(long long int i=-1000;i<=1000;i++)
    {
        temp=i*i*i*i*i-x;
        for(long long int j =-1000;j<=1000;j++)
        {
            tool=j*j*j*j*j;
            //cout<<temp<<" "<<i<<" "<<j<<" "<<tool<<endl;
            if(tool==temp)
            {
                //cout<<"??"<<endl;
               // cout<<temp<<" "<<i<<" "<<j<<" "<<tool<<endl;
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
    return 0;
}


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

const double PI = acos(-1);
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second

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

  ll n,a,b,c,d,e;
  cin>>n>>a>>b>>c>>d>>e;

  ll mi = min({a,b,c,d,e});
  cout << (n+mi-1)/mi + 4 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int length_h[1500000],length_w[1500000];
int main(void){
	int N,M,h[1501],w[1501],i,j,k,hh,ww,score;

	while(1){
		scanf("%d %d",&N,&M);
		if(N==0&&M==0){break;}
		for(i=1;i<=N;i++){scanf("%d",&h[i]);}
		for(i=1;i<=M;i++){scanf("%d",&w[i]);}

		score=0;
		for(i=1;i<=1500000;i++){length_h[i]=0;length_w[i]=0;}
		
		for(i=1;i<=N;i++){
			for(j=0;j<=N-i;j++){
				hh=0;
				for(k=1;k<=i;k++){
					hh+=h[j+k];
				}
				length_h[hh]++;
			}
		}

		for(i=1;i<=M;i++){
			for(j=0;j<=M-i;j++){
				ww=0;
				for(k=1;k<=i;k++){
					ww+=w[j+k];
				}
				length_w[ww]++;
			}
		}

		for(i=1;i<=1500000;i++){
			score+=(length_h[i]*length_w[i]);
		}
		printf("%d\n",score);
	}
	return 0;
}

Measured memory_bytes: 12328
#ifdef _DEBUG
#define _CRT_SECURE_NO_WARNINGS
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define MGN 8
#define LINF (LONG_MAX/2)
using namespace std;
typedef long long ll; typedef unsigned long long ull;
typedef vector<int> vi; typedef vector<vi> vvi;
typedef vector<ll> vl; typedef vector<vl> vvl;
typedef vector<double> vd; typedef vector<string> vs;
typedef pair<int, int> pii; typedef pair<ll, ll> pll;
typedef vector<bool> vb; typedef vector<vb> vvb;
template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
    return left.second > right.second;
}
vs split(string str, char sep) {
    vs v; stringstream ss(str); string t;
    while (getline(ss, t, sep)) v.push_back(t);
    return v;}
vs re_search_g(string s, regex re) {
    vs ret; smatch mc; auto it = s.cbegin();
    while (regex_search(it, s.cend(), mc, re)) {
        ret.push_back(mc[0]);
        it += mc.position(0) + mc.length();}
    return ret;}
#endif

void init_global_C() {}

string S;
int L;
string P[4] = { "dream","dreamer","erase","eraser" };

bool dfs(int n) {
    if (n >= L) return true;

    for(string ptn : P){
        int len = ptn.size();
        if (n+len<=L && S.substr(n, len) == ptn) {
            bool ret = dfs(n + ptn.size());
            if (ret) return true;
        }
    }

    return false;
}


int main_C() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> S;
    L = S.size();

    string ans = dfs(0) ? "YES" : "NO";
    
    cout << ans << endl;  

    return 0;
}

Measured memory_bytes: 2640
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    cin >> s;
    if (s == "Sunny")
        cout << "Cloudy" << endl;
    if (s == "Cloudy")
        cout << "Rainy" << endl;
    if (s == "Rainy")
        cout << "Sunny" << endl;
    return 0;
}

Measured memory_bytes: 2980
n = gets.to_s.to_i
s = gets.to_s.chomp

ans = 0
c = ('0'..'9')
c.each do |i|
  pos_i = s.index(i)
  c.each do |j|
    pos_i ? (pos_j = s.index(j, pos_i+1)) : next
    c.each do |k|
      ans += 1 if pos_j && s.index(k, pos_j+1)
    end
  end
end

puts ans

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define mem(a,b) memset(a,b,sizeof(a))
#define shutdown ios::sync_with_stdio(false)
#define MAX 1e18+1000//1*10^18

int main()
{
    string a;
    cin>>a;
    int i=0;
    for(int j=0;j<6;j++){
        if(a[j]=='1')
            i++;
    }
    cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 256
class in{struct It{int it;const bool rev;explicit constexpr It(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(It& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const It i,n;public:explicit constexpr in(int n):i(0),n(n<0?0:n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const It& begin(){return i;}const It& end(){return n;}};

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

using i64 = long long;

struct UnionFind {
    vector<int> data;
    vector<i64> rootd;//rootd[i] : dist from node[i] to node[root(i)]
    explicit UnionFind() {}
    void init(int N) {
        data.assign(N, -1);
        rootd.assign(N, 0);
    }
    void unite(int x_, int y_, i64 weight) {
        int x = root(x_), y = root(y_);
        if(x != y){
            data[x] += data[y];
            data[y] = x;
            rootd[y] = weight - rootd[y_] + rootd[x_];
        }
    }
    int root(int x) {
        vector<int> memo;
        while(data[x] >= 0) {
            memo.emplace_back(x);
            x = data[x];
        }
        int res = x;
        for(int i = memo.size() - 1; i >= 0; --i) {
            int k = memo[i];
            rootd[k] += rootd[data[k]];
            data[k] = res;
        }
        return res;
    }
    i64 dist(int a, int b) { return rootd[b] - rootd[a];}
    bool same(int a, int b) { return root(a) == root(b);}
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    UnionFind uf;
    while(cin >> n >> m && n) {
        uf.init(n);
        char q; int a, b; i64 w;
        for(int _ : in(m)) {
            cin >> q >> a >> b;
            --a; --b;
            if(q == '?') {
                if(uf.same(a, b))
                    cout << uf.dist(a, b) << '\n';
                else
                    cout << "UNKNOWN" << '\n';;
            }
            else {
                cin >> w;
                uf.unite(a, b, w);
            }
        }
    }
    return 0;
}

Measured memory_bytes: 4748
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()    
C.sort()

alow = []
for i in range(n):
    key = B[i]
    ok = -1
    ng = n
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if A[mid] < key:
            ok = mid
        else:
            ng = mid
    alow.append(ok+1)
    
cup = []
for i in range(n):
    key = B[i]
    ok = n
    ng = -1
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if C[mid] > key:
            ok = mid
        else:
            ng = mid
    cup.append(n-ok)

ans = 0
for i in range(n):
    ans+=alow[i] * cup[i]
print(ans)

Measured memory_bytes: 23584
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int n,m,cnt1,cnt2;
LL ans;
const int N=305,mod=1000000007;
int a[N<<1],vis[N<<1],book[N<<1],s[N<<1],f[N<<1][N][N];
int main()
{
	cin>>n;
	for(int i=1;i<=n+n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n+n;i+=2)
		if(a[i]==-1&&a[i+1]==-1)++cnt1;
		else if(a[i]!=-1&&a[i+1]!=-1)vis[a[i]]=vis[a[i+1]]=1;
		else ++cnt2,book[a[i]==-1?a[i+1]:a[i]]=1;
    for(int i=n+n;i>=1;--i)
    	if(!vis[i])s[++m]=i;
    f[0][0][0]=1;
    for(int i=1;i<=m;++i)
    	for(int j=0;j<=cnt1+cnt2;++j)
    		for(int k=0;k<=cnt2;++k)
    			if(f[i-1][j][k])
    			{
    				if(!book[s[i]])
    				{
    					(f[i][j+1][k]+=f[i-1][j][k])%=mod;
    					if(j)(f[i][j-1][k]+=f[i-1][j][k])%=mod;
    					if(k)(f[i][j][k-1]+=(LL)k*f[i-1][j][k]%mod)%=mod;
					}
					else
					{
						(f[i][j][k+1]+=f[i-1][j][k])%=mod;
						if(j)(f[i][j-1][k]+=f[i-1][j][k])%=mod;
					}
				}
	ans=f[m][0][0];
	for(int i=1;i<=cnt1;++i)ans=(LL)ans*i%mod;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 217472
// abc171_b
#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>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i, n) cin >> p[i];
  sort(p.begin(), p.end());
  ll ans = 0;
  rep(i, k) ans += p[i];
  cout << ans << endl;
  return 0;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X,i) ((X>>i)&1)
#define REP(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define ina(x,n) rep(x_i,n) cin>>x[x_i]
#define outa(x,n) rep(x_i,n) cerr<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;

const int MOD = 1e9+7;
const int INF = (1<<28);
const ll INFL = (1LL<<60);

int main() {
  int n, ans = 0; cin >> n;
  vvl counts(10, vl(10, 0));
  REP(i,1,n+1) {
    int x = i;
    while (x >= 10) x /= 10;
    int f = x, b = i % 10;
    counts[f][b]++;
  }
  rep(i,10) rep(j,10) {
    ans += counts[i][j] * counts[j][i];
  }
  cout << ans << endl;
  return 0;
}


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

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

  map<string, int> m;
  rep(i, N) {
    string s;
    cin >> s;

    if (m.count(s)) {
      m.at(s)++;
    } else {
      m[s] = 1;
    }
  }

  int num = 0;
  for (auto e : m) {
    num = max(num, e.second);
  }

  vector<string> ans;
  for (auto e : m) {
    if (e.second == num) {
      ans.push_back(e.first);
    }
  }
  sort(ans.begin(), ans.end());

  for (auto x : ans) {
    cout << x << endl;
  }
  return 0;
}

Measured memory_bytes: 26868
# BFS version

#
H, W = list(map(int, input().split()))
M = []
for i in range(H):
    M.append(list(input().rstrip()))

#
def walk(pos):
    queue = [pos]

    while len(queue)>0:
        pos = queue.pop(0)
        x, y = pos
        val = M[y][x]
        #print(x,y,val)

        # up
        if y>0 and (M[y-1][x]=='.' or (isinstance(M[y-1][x], int) and val+1<M[y-1][x])):
            M[y-1][x] = val + 1
            queue += [(x, y-1)]
        # down
        if y<H-1 and (M[y+1][x]=='.' or (isinstance(M[y+1][x], int) and val+1<M[y+1][x])):
            M[y+1][x] = val + 1
            queue += [(x, y+1)]
        # left
        if x>0 and (M[y][x-1]=='.' or (isinstance(M[y][x-1], int) and val+1<M[y][x-1])):
            M[y][x-1] = val + 1
            queue += [(x-1, y)]
        # right
        if x<W-1 and (M[y][x+1]=='.' or (isinstance(M[y][x+1], int) and val+1<M[y][x+1])):
            M[y][x+1] = val + 1
            queue += [(x+1, y)]
        #print('B')

#
M[H-1][W-1] = 1
walk((W-1, H-1))
#print(M)
#exit()

#
if M[0][0]=='.':
    print(-1)
else:
    blocks = sum([m.count('#') for m in M])
    print(H*W - blocks - M[0][0])


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

int main() {
    long long n;
    cin >> n;
    vector<long long> a(n);
    vector<long long> b(n);
    for(long long i = 0; i < n; i++){
        cin >> a[i];
        b[i] = a[i] - i;
    }
    sort(b.begin(), b.end());
    long long min_b = b[(n - 1) / 2];
    long long ans = 0;
    for(long long i = 0; i < n; i++){
        ans += abs(a[i] - (min_b + i));
    }
    cout << ans;
    
}

Measured memory_bytes: 3328
#include <stdio.h>

int main (void)
{
    int a,b,k;
    scanf("%d %d %d",&a,&b,&k);
    for(int i=0;i<k;i++)
    {
        if(i%2==0)
        {
            if(a%2==1&&a>0)
            {
                a--;
            }
            b+=a/2;
            a/=2;
        }else{
            if(b%2==1&&b>0)
            {
                b--;
            }
            a+=b/2;
            b/=2;
        }
    }
    printf("%d %d\n",a,b);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
void setcomb() {
	fac[0] = 1;
	ifac[0] = 1;
	for (ll i = 0; i < 1000000; i++) {
		fac[i + 1] = fac[i] * (i + 1) % M; // n!(mod M)
	}
	ifac[1000000] = mpow(fac[1000000], M - 2);
	for (ll i = 1000000; i > 0; i--) {
		ifac[i - 1] = ifac[i] * i%M;
	}
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
ll perm(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	return fac[a] * ifac[a - b] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b, int n) {
	int i, j, k, t;
	vector<vector<ll>> c(n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			t = 0;
			for (k = 0; k < n; k++)
				t = (t + a[i][k] * b[k][j] % M) % M;
			c[i].push_back(t);
		}
	}
	return c;
}

template< typename Monoid >
struct SegmentTree {

	int sz;
	vector< Monoid > seg;

	const Monoid M1;

	SegmentTree(int n, const Monoid &M1) : M1(M1) {
		sz = 1;
		while (sz < n) sz <<= 1;
		seg.assign(2 * sz, M1);
	}

	void set(int k, const Monoid &x) {
		seg[k + sz] = x;
	}

	void build() {
		for (int k = sz - 1; k > 0; k--) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	void update(int k, const Monoid &x) {
		k += sz;
		seg[k] = x;
		while (k >>= 1) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	Monoid query(int a, int b) {
		Monoid L = M1, R = M1;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) L = f(L, seg[a++]);
			if (b & 1) R = f(seg[--b], R);
		}
		return f(L, R);
	}

	Monoid value(const int &k) const {
		return seg[k + sz];
	}

	Monoid f(Monoid a, Monoid b) {
		return a + b;
	}

};

int main() {
	int n;
	char s[11];
	cin >> n >> s;
	if (n < 3200)
		cout << "red" << endl;
	else
		cout << s << endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
using namespace std;

int main() {
  int n;
  cin >> n;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    ans += a - 1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256