akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using i64 = long long;


constexpr auto pow(long long x, long long n, const long long mod) {
    long long ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

constexpr auto inverse(const long long x, const long long p) {
    return pow(x, p - 2, p);
}

int main() {
    constexpr i64 mod = 1000000007;
    int n;
    std::cin >> n;

    i64 s = 0;
    std::vector<i64> ps(1000001);
    for (int i = 0; i < n; i++) {
        i64 a;
        std::cin >> a;
        s = (s + inverse(a, mod)) % mod;
        for (i64 j = 2; j * j <= a; j++) {
            if (a % j) continue;
            i64 c = 0;
            while (a % j == 0) {
                c++;
                a /= j;
            }
            ps[j] = std::max(ps[j], c);
        }
        if (a > 1) ps[a] = std::max(ps[a], 1ll);
    }

    i64 lcm = 1;
    for (int i = 2; i <= 1000000; i++) lcm = lcm * pow(i, ps[i], mod) % mod;

    std::cout << lcm * s % mod << std::endl;

    return 0;
}


Measured memory_bytes: 8064
# -*- coding: utf-8 -*-

import sys
import math

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
N, = [int(s) for s in inputs]

input_line = input()
s = list(input_line)
sl = len(s)

r = 0
g = 0
b = 0
for ss in s:
    if ss=='R':
        r += 1
    elif ss=='G':
        g += 1
    else:
        b += 1
ans = r*g*b

num = 0

for i in range(sl):
    for j in range(i+1, sl):
        k = j + (j - i)
        if k<sl:
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                num += 1

ans -= num

print(ans)


Measured memory_bytes: 9252
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/icl/interval_map.hpp>

#define REPI(i, S, N) for(int i=int(S); i<int(N); i++)
#define REP(i, N) REPI(i, 0, N)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::integer;

using ll = long long;
namespace bst = boost;
namespace icl = boost::icl;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<ll> N;
  invec<ll> A(N);


  
  ll nowr = A[0], r = 0;
  for (int i = 1; i < N; i++) {
    r = (r + nowr * A[i] % 1000000007) % 1000000007;
    nowr = (nowr + A[i]) % 1000000007;
  }
  return r;
}

template<typename T> void plot(const T& func) { cout << setprecision(9) << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }

int main() {
  plot(solve);

  return 0;
}



Measured memory_bytes: 4832
#include <iostream>
#include <sstream>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <math.h>
#include <stdexcept>
#include <algorithm>
#include <set>
#include <map>
#include <stdlib.h>
#include <cctype>
#include <bitset>
using namespace std;
int main(){
    int n,i,j,p,A[9];
    for(i = 0;i < 9;i++) cin >> A[i];
    cin >> n;
    for(i = 0;i < n;i++){
        cin >> p;
        for (j = 0; j < 9; j++){
            if(A[j] == p) A[j] = -1;
        }
    }
    if(A[0] == -1 && A[1] == -1 && A[2] == -1){
        cout << "Yes" << endl;
    }
    else if (A[3] == -1 && A[4] == -1 && A[5] == -1){
        cout << "Yes" << endl;
    }
    else if (A[6] == -1 && A[7] == -1 && A[8] == -1){
        cout << "Yes" << endl;
    }
    else if (A[0] == -1 && A[3] == -1 && A[6] == -1){
        cout << "Yes" << endl;
    }
    else if (A[1] == -1 && A[4] == -1 && A[7] == -1){
        cout << "Yes" << endl;
    }
    else if (A[2] == -1 && A[5] == -1 && A[8] == -1){
        cout << "Yes" << endl;
    }
    else if (A[0] == -1 && A[4] == -1 && A[8] == -1){
        cout << "Yes" << endl;
    }
    else if (A[2] == -1 && A[4] == -1 && A[6] == -1){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    //012
    //345
    //678
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

const long long int INF = 1e9;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define Rep(i, n) for(int i = 1; i <= (int)(n); i++)
#define llrep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define llRep(i, n) for(ll i = 1; i <= (ll)(n); i++)

using namespace std;

struct Point{
	int x,y;
};

bool vector_finder(std::vector<int> vec, int number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
    if (index != vec.size()) { // 発見できたとき
        return true;
    }
    else { // 発見できなかったとき
        return false;
    }
}

int main(){
    int N,K;
    cin >> N >> K;
    cout << (N-K+1) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <iomanip>




using namespace std;



using ll = long long;
const ll INF = 1e18L + 5;
const int mod = 1e9 + 7;

int h[1000000];
ll a[1000000];
ll dp[1000000];
ll tree[1000000];
int n;

int main(){

    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    cin >> n;
    int b = 1;
    while(b <= n){
        b *= 2;
    }
    
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    
    //dp[i] max total beauty so far if the last taken flower has height i
    
    for(int flower = 0; flower < n; flower++){
        int x = h[flower] + b;
        ll best = 0;
        while(x > 1){
            if(x % 2 == 1){
                best = max(best, tree[x - 1]);
            }
            x /= 2;
        }
        dp[h[flower]] = best + a[flower];
        for(int i = b + h[flower]; i >= 1; i /= 2){
            tree[i] = max(tree[i], dp[h[flower]]);
        }
    }
    ll ans = 0;
    for(int i = 0; i <= n; i++){
        ans = max(ans, dp[i]);
    }
    cout << ans;
}



Measured memory_bytes: 14080
import math

N,M=map(int,input().split())
dic={}
for i in range(2,int(M**0.5)+1):
    if M%i==0:
        dic.setdefault(i,1)
        M//=i
        while M%i==0:
            dic[i]+=1
            M//=i
    if M==1: break

if M!=1: dic[M]=1


ans=1
for k in dic.keys():
    x=dic[k]
    tmp=1
    for i in range (N,x+N):
        tmp*=i
    ans*=tmp//math.factorial(x)
    ans%=1000000007
print(ans%1000000007)

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

#define ll long long
#define ld long double
#define COIN const int
#define ite iterator
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define REPD(i,n) for((i)=(n)-1;(i)>=0;(i)--)

#define ALL(c) (c).begin(), (c).end()
#define sz(s) (s).size()
#define CLEAR(x) memset(x,0,sizeof x);

#define MP make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define X first
#define Y second

#define VI vector<int>
#define VS vector<string>
#define VII vector<PII>
#define VVI vector<VI>

#define PIII 3.1415926
#define PI 3.14
/*****************************************************************************/

using namespace std;

ll res=1,n,m,mod=1e9+7;
bool pri[1001];
long long f(int x){
	m=n;
	int cnt=0;
	while(m)
		cnt+=m/x,m/=x;
	return cnt;
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n;
	memset(pri,1,sizeof pri);
	pri[0]=pri[1]=0;
	for(int i=2;i<=n;i++)
		if(pri[i])
			for(int j=2;j*i<=n;j++)
				pri[j*i]=0;
	for(int i=1;i<=n;i++) {
		if(pri[i]) {
			res=(res*(f(i)+1))%mod; 
		}
	}
	cout<<res<<endl;
	return 0;
}
/******************************************************************************
1000
972926972

972926972
******************************************************************************/



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-8;
const double pi=acos(-1);
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int Random(int mi,int ma){
    random_device rnd;
    mt19937 mt(rnd());//32bit
    //[mi,ma]
    uniform_int_distribution<int>engine(mi,ma);
    return engine(mt);
}
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
vector<int>kaijo,invkaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    invkaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
    rep(i,n+1)invkaijo[i]=modpow(kaijo[i],mod-2);
}
int comb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
struct BIT{
    int n,beki=1;
    vector<int>bit;
    BIT(int x){
        bit.resize(x+1,0);
        n=x;
        while(beki*2<=n)beki*=2;
    }
    int sum(int i){
        int res=0;
        while(i>0){
            res+=bit[i];
            i-=i&-i;
        }
        return res;
    }
    void add(int i,int x){
        while(i<=n){
            bit[i]+=x;
            i+=i&-i;
        }
    }
    int lowerbound(int w){
        if(w<=0)return 0;
        int x=0;
        for(int k=beki;k>0;k>>=1){
            if(x+k<=n&&bit[x+k]<w){
                w-=bit[x+k];
                x+=k;
            }
        }
        return x+1;
    }
};
int n,k,a[200010];
signed main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    rep(_,min(k,50ll)){
        BIT bit(n);
        for(int i=1;i<=n;i++){
            int l=max(1ll,i-a[i]),r=min(n,i+a[i]);
            bit.add(l,1),bit.add(r+1,-1);
        }
        for(int i=1;i<=n;i++)a[i]=bit.sum(i);
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Ti = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct edge {
  int to, cap, cost, rev;
  edge(){}
  edge(int to, int cap, int cost, int rev)
    :to(to), cap(cap), cost(cost), rev(rev){}
};

using Graph = vector<vector<edge>>;

struct PrimalDual {
  Graph graph;
  vint mincost, h, prevv, preve;
  PrimalDual(int V):graph(V), mincost(V), h(V), prevv(V), preve(V){}
  void add_edge(int from, int to, int cap, int cost) {
    graph[from].emplace_back(to, cap, cost, graph[to].size());
    graph[to].emplace_back(from, 0, -cost, graph[from].size()-1);
  }
  int min_cost_flow(int s, int t, int f) {
    fill(all(h), 0);
    fill(all(prevv), -1);
    fill(all(preve), -1);
    int res = 0;
    while(f > 0) {
      fill(all(mincost), inf);
      priority_queue<Pi, vector<Pi>, greater<Pi>> que;
      que.emplace(0, s);
      mincost[s] = 0;
      while(!que.empty()) {
	Pi p = que.top(); que.pop();
	int v = p.second;
	if(mincost[v] < p.first) continue;
	rep(i, graph[v].size()) {
	  edge& e = graph[v][i];
	  int cost = mincost[v] + e.cost + h[v] - h[e.to];
	  if(e.cap > 0 && cost < mincost[e.to]) {
	    mincost[e.to] = cost;
	    que.emplace(cost, e.to);
	    prevv[e.to] = v;
	    preve[e.to] = i;
	  }
	}
      }
      if(mincost[t] == inf) return -1;
      rep(v, graph.size()) h[v] += mincost[v];
      int d = f;
      for(int v = t; v != s; v = prevv[v])
	chmin(d, graph[prevv[v]][preve[v]].cap);
      f -= d;
      res += d*h[t];
      for(int v = t; v != s; v = prevv[v]) {
	edge& e = graph[prevv[v]][preve[v]];
	e.cap -= d;
	graph[e.to][e.rev].cap += d;
      }
    }
    return res;
  }
};

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n;
  cin >> n;
  vint p(n);
  rep(i, n) cin >> p[i];
  int s = n*2, t = s+1, V = t+1;
  PrimalDual graph(V);
  rep(i, n) {
    graph.add_edge(s, i, 1, 0);
    graph.add_edge(n+i, t, 1, 0);
  }
  rep(i, n) rep(j, n) {
    if(p[i]-1 == j) continue;
    int cost = p[i]*abs(i-j);
    graph.add_edge(i, n+j, 1, cost);
  }
  cout << graph.min_cost_flow(s, t, n) << endl;

  return 0;
}

Measured memory_bytes: 3956
/*
ID: sinha.d1
PROG: skidesi
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
 
int ar[100005];
bool flag=false;
int n,m;
int main()
{
  //  fstream fin("7.in");
  int n;
  cin>>n;
  int i;
  ll sum=0;ll cont=0,cont1=0;
  //cin>>ar[1];
  for(i=1;i<=n;i++)
  {
      cin>>ar[i];
    
  }
  if(ar[1]>0)
  sum=ar[1];
  else {sum=1;cont+=-ar[1]+1;}
  int sgn=1;
  for(i=2;i<=n;i++)
  {
      sum+=(ll)ar[i];
      if(sgn==1)
      {
          if(sum>=0)
          {
              cont+=abs(sum+1);
              sum=-1;
          }
          sgn=-1;
      }
      else if(sgn==-1)
      {
          if(sum<=0)
          {
              cont+=abs(-sum+1);
              sum=1;
          }
          sgn=1;
      }
  }
  
  if(ar[1]<0)
  sum=ar[1];
  else {sum=-1;cont1+=ar[1]+1;}
  sgn=-1;
  for(i=2;i<=n;i++)
  {
      sum+=(ll)ar[i];
      if(sgn==1)
      {
          if(sum>=0)
          {
              cont1+=abs(sum+1);
              sum=-1;
          }
          sgn=-1;
      }
      else if(sgn==-1)
      {
          if(sum<=0)
          {
              cont1+=abs(-sum+1);
              sum=1;
          }
          sgn=1;
      }
  }
  cout<<min(cont,cont1)<<endl;
return 0;
}

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

int main(){
  int n;
  cin>>n;
  vector<int>a(n-1);
  for(int i=0;i<n-1;i++){
    cin>>a[i];
  }
  unordered_map<int,int>mp;
  for(int i=0;i<(int)a.size();i++)mp[a[i]]++;
  for(int i=1;i<=n;i++){
    if(mp.find(i)!=mp.end()) cout<<mp[i];
    else cout<<0;
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 12144
import math
a, b, h, m = map(int, input().split())
m_rad = 6 * m
h_rad = 0.5 * 60 * h + 0.5 * m
length = math.sqrt(a*a + b*b - 2*a*b*math.cos(math.radians(abs(m_rad - h_rad))))
print('{:.20f}'.format(length))


Measured memory_bytes: 9412
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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 inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
const int UF_MAX_N = 101010;

int uf_parant[UF_MAX_N];
int uf_rank[UF_MAX_N];
int uf_group_size[UF_MAX_N];

void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        uf_parant[i] = i;
        uf_rank[i] = 0;
        uf_group_size[i] = 1;
    }
}

int find(int x)
{
    if (uf_parant[x] == x)
    {
        return x;
    }
    else
    {
        return uf_parant[x] = find(uf_parant[x]);
    }
}

int get_size(int x)
{
    x = find(x);
    return uf_group_size[x];
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;

    if (uf_rank[x] < uf_rank[y])
    {
        uf_parant[x] = y;
        uf_group_size[y] += uf_group_size[x];
    }
    else
    {
        uf_parant[y] = x;
        uf_group_size[x] += uf_group_size[y];
        if (uf_rank[x] == uf_rank[y])
            uf_rank[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

ll N, M;
ll A[101010], B[101010];
ll ans[101010];

int main()
{
    cin >> N >> M;
    repe(i, 1, M)
    {
        cin >> A[i] >> B[i];
    }

    init(N);
    ans[M] = N * (N - 1) / 2;
    for (int i = M - 1; i >= 1; i--)
    {
        int a = A[i + 1];
        int b = B[i + 1];
        ll size_a = get_size(a);
        ll size_b = get_size(b);
        if (same(a, b))
        {
            ans[i] = ans[i + 1];
            continue;
        }
        else
        {
            ans[i] = ans[i + 1] - size_a * size_b;
            unite(a, b);
        }
    }
    repe(i, 1, M)
    {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 4864
#include<bits/stdc++.h>
#define Mx 1000000000005 
#define ll long long  
#define pi 3.141592653
#define vi vector<ll>
#define Mo 1000000007
#define mp make_pair
#define M map<ll,ll>
#define fr(i,a,b) for(ll i=a;i<b;i++)
#define vii vector<pair<ll,ll> > 
#define fi first
#define se second
#define pb push_back
#define ld long double
#define fill(a,x) memset(a,x,sizeof(a))
using namespace std;
bool comp(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
  return a.second<b.second;
}
/*vi b=v;
   sort(b.begin(), b.end());
  b.resize(unique(b.begin(), b.end()) - b.begin());
  ll t; cin>>t; fr(f,0,t){ 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 */
ll func(ll a[],ll n,ll k)
{
  if(k==0) return 1;
  if(k<0 || n==0) return 0;

  ll ans=0;
  fr(i,0,a[n-1]+1)
  {
    ans+=func(a,n-1,k-i);
    ans%=Mo;
  }
  return ans;
}
int main()
{
  ll n,k,l,r; cin>>n>>k;
  ll a[n];
  fr(i,0,n)
    cin>>a[i];

  ll dp[n+1][k+1],p[n+1][k+1];
  fill(dp,0);
  fill(p,0);

  fr(i,0,n+1)
  {
    dp[i][0]=1;
    p[i][0]=1;
  }
 
  fr(j,1,k+1)
    p[0][j]+=p[0][j-1];

  fr(i,1,n+1)
  {
    fr(j,1,k+1)
    {
      r=j; l=j-a[i-1];
      dp[i][j]+=p[i-1][r];

      dp[i][j]%=Mo;

      if(l>0) dp[i][j]-=p[i-1][l-1]; 
      if(dp[i][j]<0) dp[i][j]+=Mo;

      p[i][j]=p[i][j-1]+dp[i][j];
      p[i][j]%=Mo;

    }
  }

  cout<<dp[n][k];


}

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

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

long long N,A;

cin >> N;

vector<ll> ans(N+1,0);

for(int i = 1;i < N;++i){

    cin >> A;

    ans[A]++;

}

for(int i = 1;i <= N;++i) cout << ans[i] << endl;

return 0;

}

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

const int MAXN = 2.1e5;
int par[MAXN];
void reset() {
	memset(par, -1, sizeof(par));
}
int getPar(int a) { return par[a] < 0 ? a : (par[a] = getPar(par[a])); }
bool merge(int a, int b) {
	a = getPar(a), b = getPar(b);
	if (a == b) return false;
	par[a] += par[b];
	par[b] = a;
	return true;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	reset();
	int N, M, K; cin >> N >> M >> K;
	vector<vector<int>> adj(N);
	for (int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
		merge(u, v);
	}
	for (int i = 0; i < K; i++) {
		int u, v; cin >> u >> v; u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 0; i < N; i++) {
		int p = getPar(i);
		int ans = -par[p];
		ans--;
		for (int j : adj[i]) {
			if (getPar(j) == p) ans--;
		}
		cout << ans << " \n"[i+1==N];
	}

	return 0;
}


Measured memory_bytes: 8696
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int m[n];
   for(int i=0;i<n;i++)
   {
       cin>>m[i];
   }
   sort(m,m+n);
   int ans=m[n/2]-m[(n/2)-1];
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 3940
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

func Solve() {
  var H, W, M, h, w int
  var ok bool
  NextInt(&H, &W, &M)
  X := make([]int, H)
  Y := make([]int, W)
  B := make(map[int]map[int]struct{})
  for i := 0; i < M; i++ {
    NextInt(&h, &w)
    h--; w--
    X[h]++; Y[w]++
    if _, ok = B[h]; !ok { B[h] = make(map[int]struct{}) }
    B[h][w] = struct{}{}
  }
  R := MaxInt(X...)
  MX := make([]int, 0)
  for i, x := range X { if x == R { MX = append(MX, i) } }
  C := MaxInt(Y...)
  MY := make([]int, 0)
  for i, y := range Y { if y == C { MY = append(MY, i) } }
  for _, x := range MX {
    for _, y := range MY {
      if _, ok = B[x][y]; ok { continue }
      Write(R + C); return
    }
  }
  Write(R + C - 1)
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntSlice(A *[]int) {
  L := strings.Split(NextLine(), " ")
  if len(L) == 1 && L[0] == "" {
    (*A) = make([]int, 0)
    return
  }
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatSlice(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  if len(L) == 1 && L[0] == "" {
    (*A) = make([]float64, 0)
    return
  }
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(S ...interface{}) {
  fmt.Fprintln(writer, S...)
}
func WriteIntSlice(A []int) {
  B := make([]interface{}, len(A))
  for i, a := range A { B[i] = a }
  fmt.Fprintln(writer, B...)
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}

Measured memory_bytes: 104548
#include<stdio.h>
#define WHITE 0
#define GRAY 1
#define BLACK 2
int m[110],n,Adj[110][220],color[110],time,d[10000],f[10000];

void DFS_Visit(int u){
  int v,i;
  color[u] = GRAY; 
  d[u] = ++time;
  for(i = 1; i <= m[u]; i++){
    v = Adj[u][i];
    if(color[v] == WHITE){
      DFS_Visit(v);
    }
  }
  color[u] = BLACK; 
  f[u] = ++time;
}
void DFS(){
  int u;
  for(u = 1; u <= n; u++){
    color[u] = WHITE;
  }
  time = 0;
  for(u = 1; u <= n; u++){
    if(color[u] == WHITE){ 
      DFS_Visit(u); 
    }
  }
}


int main(){ 
  int u,i,j,dust;
  scanf("%d",&n);
  for(u = 1; u <= n; u++){
    for(j = 1; j <= n; j++){
      Adj[u][j]=0;
    }
  }
  for(u = 1; u <= n; u++){
    scanf("%d%d",&dust,&m[u]);
      for(i = 1; i <= m[u]; i++){
	scanf("%d",&Adj[u][i]);
      }	
  }
  
  DFS();
  for(u = 1; u <= n; u++){
    printf("%d %d %d\n",u,d[u],f[u]);
  }
  return 0;
}

Measured memory_bytes: 696
#include<iostream>
#include<vector>
#include<string>
#define ll long long
#define dl double
using namespace std;



//***********************************************************************
int MAXNUM = 5e3 + 5;
vector <int>vis(MAXNUM);
vector<int> pr;
void sieve() {
	pr.push_back(2);
	for (ll i = 3;i < MAXNUM;i += 2) if (!vis[i]) {
		pr.push_back(i);
		for (ll j = i * i;j < MAXNUM;j += 2 * i) vis[j] = true;
	}
}
//************************************************************************
ll n, mod;
vector<ll> dp1(n + 1), dp2(n + 1);

void recurdp1(ll i, ll p, vector<vector<ll>>& adj)
{
	ll ans = 1;
	for (ll j = 0;j < adj[i].size();j++)
	{
		ll v = adj[i][j];
		if (v != p)
		{
			recurdp1(v, i, adj);
			ans *= dp1[v] % mod;
			ans %= mod;
		}
	}
	ans += 1;
	ans %= mod;
	dp1[i] = ans;
}
void recurdp2(ll i, ll p, vector<vector<ll>>& adj)
{
	ll si = adj[i].size();
	if(si==0)
		return;
	vector<ll> prefix(si);
	vector<ll> suffix(si);
	prefix[0] = 1;
	suffix[si - 1] = 1;
	if (adj[i][0] != p)
		prefix[0] = dp1[adj[i][0]];
	if (adj[i][si - 1] != p)
		suffix[si - 1] = dp1[adj[i][si - 1]];
	for (ll j = 1;j < si;j++)
	{
		if (adj[i][j] != p)
			prefix[j] = (prefix[j - 1] * dp1[adj[i][j]]) % mod;
		else {
			prefix[j] = prefix[j - 1];
		}
	}
	for (ll j = si - 2;j >= 0;j--)
	{
		if (adj[i][j] != p)
			suffix[j] = (suffix[j + 1] * dp1[adj[i][j]]) % mod;
		else
			suffix[j] = suffix[j + 1];
	}
	for (ll j = 0;j < si;j++)
	{
		if (adj[i][j] != p)
		{
			ll ans = 1;
			ans *= dp2[i] % mod;
			ans %= mod;
			if (j > 0)
				ans *= prefix[j - 1] % mod;
			ans %= mod;
			if (j < si - 1)
				ans *= suffix[j + 1] % mod;
			ans %= mod;
			ans++;
			ans %= mod;
			dp2[adj[i][j]] = ans;
			recurdp2(adj[i][j], i, adj);
		}
	}

}

void solve()
{
	cin >> n >> mod;
	vector<vector<ll>> adj(n + 1);
	for (int i = 0;i < n - 1;i++)
	{
		ll u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dp1.resize(n + 1);
	dp2.resize(n + 1);
	dp2[1] = dp2[0] = 1;
	recurdp1(1, 0, adj);
	
	recurdp2(1, 0, adj);
	//cout << "dp1" << endl;
	for (int i = 1;i <= n;i++)
	{
		dp1[i] = (dp1[i] - 1 + mod) % mod;
		//cout << dp1[i] << " ";
	}
	/*cout << endl;
	cout << "dp2" << endl;
	for (int i = 1;i <= n;i++)
	{
		cout << dp2[i] << " ";
	}
	cout << endl;
	*/
	for (int i = 1;i <= n;i++)
	{
		if (i == 1)
			cout << dp1[i] << endl;
		else
			cout << (dp1[i] * dp2[i]) % mod << endl;
	}

}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	//cin >> t;
	t = 1;
	while (t--)
	{
		solve();
	}

	return 0;
}

Measured memory_bytes: 19712
#include <stdio.h>

int main(void){
	int n;
	int x,y,b,p;
	int i;
	int ans,ans2;
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d %d %d",&x,&y,&b,&p);
		
		ans=x*b+y*p;
		
		if(b<5)b=5;
		if(p<2)p=2;
		
		ans2=(x*b+y*p)*0.8;
		
		if(ans<=ans2)printf("%d\n",ans);
		else printf("%d\n",ans2);
		
	}
	return 0;
}

Measured memory_bytes: 1028
//g++ -std=c++14 test.cpp -o test.out
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<62)-10e15;
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;
 
LL A,B,C,D,E,F;
 
LL ans1 = 0;//砂糖の量
LL ans2 = 0;//砂糖水の量
 
void solve(){
	//dp[i][j]:
	//砂糖i[g],水j[g]となるようなものが作れるかどうか
	//作れるなら1を代入
	vector<vector<LL>> dp(F+1,vector<LL>(F+1,0));
	dp[0][0] = 1;
	//ばらまくイメージのDP
	for(int i=0;i<=F;i++){
		for(int j=0;j<=F;j++){
			if(!dp[i][j]) continue;
			if(i+j+C<=F) dp[i+C][j] = 1;
			if(i+j+D<=F) dp[i+D][j] = 1;
			if(i+j+100*A<=F) dp[i][j+100*A] = 1;
			if(i+j+100*B<=F) dp[i][j+100*B] = 1;
		}
	}

	for(int i=0;i<=F;i++){
		for(int j=i;j<=F;j++){
			if(!dp[i][j] || i*(100+E)>E*(j+i))continue;
			if(ans1*(i+j)<=i*ans2){
				ans1 = i;
				ans2 = i+j;
			}
		}
	}
}
 
int main(){
    cin >> A >> B >> C >> D >> E >> F;
 
    solve();
 
    cout << ans2 << " " << ans1 << endl;
    return 0;
}

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

const int MAXN = 10001;
bool isPrime[MAXN];

int main() {
  fill(isPrime, isPrime+MAXN, true);
  isPrime[0] = isPrime[1] = false;
  for(int i = 2; i < MAXN; ++i) {
    if(isPrime[i])
      for(int j = i*2; j < MAXN; j += i) isPrime[j] = false;
  }

  int n;
  while(cin >> n && n) {
    int p, q;
    for(int x = 3; x+2 <= n; ++x) {
      if(isPrime[x] && isPrime[x+2]) {
        p = x;
        q = x+2;
      }
    }
    cout << p << " " << q << endl;
  }
  return 0;
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using Lint=long long;

template<int mod> class ModInt
{   
 private:
    Lint val;
 public:
    Lint value(){ return val; }
    ModInt(Lint x=0){ val=x%mod; }
    ModInt pow(int n){
        ModInt res(1),x(val);
        while(n>0){ if(n&1) res*=x; x*=x; n>>=1; }
        return res;
    }
    ModInt inv(){ return pow(mod-2); }
    ModInt& operator+=(ModInt rhs){ val+=rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator-=(ModInt rhs){ val+=mod-rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator*=(ModInt rhs){ val=val*rhs.val%mod; return *this; }
    ModInt& operator/=(ModInt rhs){ *this*=rhs.inv(); return *this; }
    ModInt operator+(ModInt rhs){ return ModInt(val)+=rhs; }
    ModInt operator-(ModInt rhs){ return ModInt(val)-=rhs; }
    ModInt operator*(ModInt rhs){ return ModInt(val)*=rhs; }
    ModInt operator/(ModInt rhs){ return ModInt(val)/=rhs; }
};
using mint=ModInt<1000000007>;

template<typename T> class BiCoef
{
 public:
    vector<T> fact,ifact,inv;
    BiCoef(int N):fact(N+1),ifact(N+1),inv(N+1){
        fact[0]=ifact[N]=inv[0]=1;
        for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i;
        ifact[N]/=fact[N];
        for(int i=N-1;i>=0;i--) ifact[i]=ifact[i+1]*(i+1);
        for(int i=1;i<=N;i++) inv[i]=ifact[i]*fact[i-1];
    }
    T comb(int n,int k){
        if(n<0 or k<0 or n<k) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

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

    int X,Y; cin>>X>>Y;
    mint ans=0;
    BiCoef<mint> bc(X+1);
    for(int i=0;i<=X;i++) if((X-i)%2==0){
        int j=(X-i)/2;
        if(i*2+j==Y){
            ans+=bc.comb(i+j,i);
        }
    }
    cout<<ans.value()<<endl;
    return 0;
}

Measured memory_bytes: 23680
#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 50000, MAX_M = 20, INF = 50001;
    int n, m, c[MAX_M];
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
    }
    int dp[MAX_M + 1][MAX_N + 1];
    fill(dp[0], dp[0] + n + 1, INF);
    dp[0][0] = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (j >= c[i]) {
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - c[i]] + 1);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}


Measured memory_bytes: 7232
#include <bits/stdc++.h>
 
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>
 
using namespace std;

void solve(){

	return;
}
 
int32_t main(){
	int n,k;

	cin >> n >> k;

	cout << ( n*500 >=k ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
	public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[n];
		for(int i=0; i<n; i++){
			a[i] = sc.nextInt();
		}
		for(int i=n-1; i>=0; i--){
			System.out.print(a[i]);
			if(i!=0) System.out.print(" ");
			else System.out.println();
		}
	}
}

Measured memory_bytes: 19660
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K,cnt = 0,need,ans;
  scanf("%d%d" ,&N,&K);
  vector <long> a(N);
  vector <long> b(N+1);
  for(int i = 0;i<N;i++){
    scanf("%d" ,&a[i]);
    b.at(a.at(i))++;
    if(b.at(a.at(i)) == 1){
      cnt++;
    }
  }
  need = cnt - K;
  sort(b.begin(),b.end());
  if(need <= 0){
    ans = 0;
  }
  if(need > 0){
    int pop = need;
    for(int k = 0;k<N+1;k++){
      if(b.at(k) != 0){
        if(pop <= 0){
          continue;
        }
        pop -= 1;
        ans += b.at(k);
      }
    }
  }
  printf("%d\n" , ans);
  return 0;
}

Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = Integer.parseInt(sc.next());
        int h = Integer.parseInt(sc.next());
        int n = Integer.parseInt(sc.next());
        int[][] ary = new int[n][2];
        int[] wary = {0, w};
        int[] hary = {0, h};
        for (int i = 0; i < n; i++) {
            ary[i][0] = Integer.parseInt(sc.next());
            ary[i][1] = Integer.parseInt(sc.next());
            int a = Integer.parseInt(sc.next());
            switch (a) {
                case 1:
                    if (ary[i][0] > wary[0]) {
                        wary[0] = ary[i][0];
                    }
                    break;
                case 2:
                    if (ary[i][0] < wary[1]) {
                        wary[1] = ary[i][0];
                    }
                    break;
                case 3:
                    if (ary[i][1] > hary[0]) {
                        hary[0] = ary[i][1];
                    }
                    break;
                case 4:
                    if (ary[i][1] < hary[1]) {
                        hary[1] = ary[i][1];
                    }
                    break;
            }
        }
        int x = wary[1] < wary[0] ? 0 : wary[1] - wary[0];
        int y = hary[1] < hary[0] ? 0 : hary[1] - hary[0];
        System.out.println(x * y);
    }
}

Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
                     
#define int             long long
#define ld              long double
#define mp              make_pair
#define ff              first
#define ss              second
#define pb              push_back
#define fo(i,n)         for(i=0;i<n;i++)
#define fo1(i,n)        for(i=1;i<=n;i++)
#define FO(i,k,n)       for(i=k;k<=n?i<=n:i>=n;k<=n?i++:i--)
#define all(c)          c.begin(),c.end()
#define rall(c)         c.rbegin(),c.rend()
#define si              set<int>
#define vi              vector<int>
#define mii             map<int,int>
#define pii             pair<int,int>
#define vpii            vector<pii>
#define vvi             vector<vi>
#define usi             unordered_set<int>
#define umii            unordered_map<int,int>
#define pqmx            priority_queue<int>
#define pqmn            priority_queue<int,vi,greater<int> >
#define sp(x)           cout<<setprecision(x)<<fixed;
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)     __builtin_ctzll(x)
#define in(a,n)         vi a(n);fo(i,n)cin>>a[i];
#define in1(a,n)        vi a(n+1);fo1(i,n)cin>>a[i];
#define w(t)            int t;cin>>t;while(t--)
#define sz(v)           (int)v.size()
#define gcd             __gcd
#define lcm(x,y)        x*(y/gcd(x,y))
#define endl            '\n'
#define PI              3.14159265358979323846
const int inf =         1e18;
const int mod =         1e9+7;
void __p(int x) {cout<<x;}
void __p(int32_t x){cout<<x;}
void __p(float x){cout<<x;}
void __p(double x){cout<<x;}
void __p(ld x) {cout<<x;}
void __p(char x){cout <<'\''<<x<<'\'';}
void __p(const char *x){cout <<'\"' <<x<<'\"';}
void __p(const string &x) {cout<<'\"'<<x<<'\"';}
void __p(bool x) {cout<<(x?"true":"false");}
void _p() {cout << "]\n";}
template<typename T,typename V>     void __p(const pair<T,V> &x) {cout<<'{';__p(x.first);cout<<',';__p(x.second);cout<<'}';}
template<typename T>                void __p(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __p(i); cout << "}";}
template <typename T,typename... V> void _p(T t, V... v) {__p(t);if(sizeof...(v))cout<<", ";_p(v...);}
int po(int x,int p,int m = inf) {int ans=1;x%=m;while(p>0){if(p&1)ans=(ans*x)%m;p=p>>1;x=(x*x)%m;}return ans;}
int inv(int x,int m=mod){return po(x,m-2,m)%m;}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_p(x)
#else 
#define dbg(x...)
#endif
//=================================================================================




const int N=1e6+6;
int n,m,k,x,y,z,a,b,c,d,i,j,l,r,f;








void sol()
{   
    cin>>n;
    in(a,n);
    c=0;
    for(auto p:a)c+=p;
    c/=n;

    x=0;
    for(auto p:a)x+=(c-p)*(c-p);
    y=0;c++;
    for(auto p:a)y+=(c-p)*(c-p);
    
    cout<< min(x,y) <<endl;
}





int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //sp(10);
    // w(t)
    sol();
    return 0;
}

Measured memory_bytes: 3564
import random
import math
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
yes = lambda: print("Yes")
no = lambda: print("No")
I = lambda: list(input())
J = lambda x: "".join(x)
II = lambda: int(input())
SI = lambda: input()
#---khan17---template
k = II()
s = SI()
if len(s) <=k:
	print(s)
else:
	print(s[:k]+"...")

Measured memory_bytes: 9568
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let (N, M, L): (usize, usize, i64) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap()
        )
    };
    let (A, B, C): (Vec<usize>, Vec<usize>, Vec<i64>) = {
        let (mut A, mut B, mut C) = (vec![], vec![], vec![]);
        for _ in 0..M {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            A.push(iter.next().unwrap().parse().unwrap());
            B.push(iter.next().unwrap().parse().unwrap());
            C.push(iter.next().unwrap().parse().unwrap());
        }
        (A, B, C)
    };
    let Q: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let (s, t): (Vec<usize>, Vec<usize>) = {
        let (mut s, mut t) = (vec![], vec![]);
        for _ in 0..Q {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            s.push(iter.next().unwrap().parse().unwrap());
            t.push(iter.next().unwrap().parse().unwrap());
        }
        (s, t)
    };

    const INF: i64 = 1_000_000_000_000_000;
    let mut dp = vec![vec![INF; N + 1]; N + 1];
    for i in 0..M {
        dp[A[i]][B[i]] = C[i];
        dp[B[i]][A[i]] = C[i];
    }
    for k in 1..(N + 1) { for i in 1..(N + 1) { for j in 1..(N + 1) { dp[i][j] = std::cmp::min(dp[i][j], dp[i][k] + dp[k][j]); }}}
    let mut dp2 = (0..(N + 1))
        .map(|i| (0..(N + 1))
            .map(|j| if dp[i][j] <= L { 1 } else { INF })
            .collect::<Vec<_>>()
        ).collect::<Vec<_>>();
    for k in 1..(N + 1) { for i in 1..(N + 1) { for j in 1..(N + 1) { dp2[i][j] = std::cmp::min(dp2[i][j], dp2[i][k] + dp2[k][j]); }}}

    let ans = (0..Q)
        .map(|i| if dp2[s[i]][t[i]] == INF { -1 } else { dp2[s[i]][t[i]] - 1 } )
        .map(|res| res.to_string())
        .collect::<Vec<_>>()
        .join("\n");

    println!("{}", ans);
}

Measured memory_bytes: 14552
#include <stdio.h>

#define S_MAX 200000
#define T_MAX 100000

int search(int);

int S[S_MAX], T[T_MAX];
int n, q;

int main(){
  int i, num = 0;

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

  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &T[i]);
  }

  for(i = 0 ; i < q ; i++){
    if(search(i) == 0)num++;
  }

  printf("%d\n", num);
  
  return 0;
}

int search(int i){
  int left = 0, right = n, mid;

  while(left != right){
    mid = (left + right) / 2;
    if(S[mid] > T[i]){
      right = mid;
    }else if(S[mid] < T[i]){
      left = mid + 1;
    }else{
      return 0;
    }
  }

  return 1;  
}



Measured memory_bytes: 2376
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
#include <unistd.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/wait.h>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<LL, LL>
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int pos[qq];
vector<pill> G[qq];
int deg[qq];

int main(){
	int n, m;	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		LL a, b, c;	scanf("%lld%lld%lld", &a, &b, &c);
		G[a].pb(mk(b, c));
		deg[b]++;
	}
	queue<int> Q;
	mst(pos, -1);
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 0) {
			Q.push(i);
			pos[i] = 0;
		}
	}
	bool f = true;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int i = 0; i < G[u].size(); ++i) {
			LL v = G[u][i].fi;
			LL d = G[u][i].se;
			if (pos[v] == -1) {
				pos[v] = pos[u] + d;
				if (pos[v] > 1000000000LL)	f = false;
			} else {
				if (pos[v] - pos[u] != d)	f = false;
			}
			deg[v]--;
			if (deg[v] == 0)	Q.push(v);
			if (!f)	break;
		}
		if (!f)	break;
	}
	for (int i = 1; i <= n; ++i) {
		if (pos[i] == -1)	f = false;
	}
	if (f)	puts("Yes");
	else	puts("No");
	return 0;
}

Measured memory_bytes: 8448
a, b = map(int, input().split())

for x in range(a+1):
    for y in range((a+1) -(x)):
        z = a - x - y
        if x*10000 + y*5000 + z*1000 == b:
            print(x,y,z)
            exit()

print("-1 -1 -1")

Measured memory_bytes: 3060
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=1e5+5;const ll inf=1e18;
int a[N],k,n;ll f[N][2],res;
int main(){
	scanf("%d",&n);
	fp(i,1,n)scanf("%d",&a[i]);
	memset(f,0xef,sizeof(f));
	f[0][0]=0;
	fp(i,1,n){
		if(!a[i])f[i][0]=max(f[i-1][0],f[i-1][1]);
		else{
			f[i][0]=max(f[i-1][0]+(a[i]>>1),max(f[i-1][1]+(a[i]>>1),f[i-1][1]+((a[i]-1)>>1)+1));
			f[i][1]=max(f[i-1][0]+((a[i]-1)>>1),max(f[i-1][1]+((a[i]-1)>>1),a[i]>=2?f[i-1][1]+((a[i]-2)>>1)+1:-inf));
		}
	}
	printf("%lld\n",max(f[n][0],f[n][1]));
	return 0;
}

Measured memory_bytes: 2176
import itertools
n=input()
c=[0,0,6,36,150,540,1806,5796,18150]
b=len(list(a for a in itertools.product(["3","5","7"],repeat=len(n))if len(set(a))==3 and int("".join(a))<=int(n)))
print(sum(c[:len(n)-1])+b)

Measured memory_bytes: 5364
#include <iostream>
#include <stack>
using namespace std;
int main()
{
    string ch;
    while(cin>>ch){
        int cnt=0;
        if(ch.length()<2){
            cout<<cnt<<endl;
            continue;
        }
        stack<char> tmp;
        bool flag=true;
        for(int i=0;i<ch.length();i++){
            tmp.push(ch[i]);
        }
        char ans=tmp.top();
        tmp.pop();
        while(!tmp.empty()){
            if(ans==tmp.top()){
                tmp.pop();
                continue;
            }
            ans=tmp.top();
            tmp.pop();
            cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}


Measured memory_bytes: 512
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define veci vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vec>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))


using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
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;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
//template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
//template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x:vec) is >> x;
    return is;
}
const ll INF=1e9+7;

ll n,a,b,c;

vector<ll> l;

ll dfs(ll N, ll A, ll B, ll C){
    ll rec=INF;
    if(N==0){
        if(min({A,B,C})==0) return INF;
        rec=abs(A-a)+abs(B-b)+abs(C-c);
    }
    if(N>0){
        rec=min(rec,dfs(N-1, A+l[N-1], B, C)+10);
        rec=min(rec,dfs(N-1, A, B+l[N-1], C)+10);
        rec=min(rec,dfs(N-1, A, B, C+l[N-1])+10);
        rec=min(rec,dfs(N-1, A, B, C));
    }
    return rec;
}
int main()
{
    
    cin >> n >> a >> b >> c;
    rep(i,n){
        ll x;
        cin >> x;
        l.push_back(x);
    }
    cout << dfs(n,0LL,0LL,0LL)-30 << endl;
    return 0;
} 


Measured memory_bytes: 256
def main():
    n = int(input())
    v = list(map(int, input().split()))
    e = [0 for _ in range(1, 10 ** 5 + 2)]
    o = [0 for _ in range(1, 10 ** 5 + 2)]
    for i in range(0, n, 2):
        e[v[i]] += 1
        o[v[i + 1]] += 1
    ans = 0
    if len(set(v)) == 1:
        ans = n // 2
    else:
        me = max(e)
        mo = max(o)
        mei = e.index(me)
        moi = o.index(mo)
        if mei == moi:
            e[mei] = 0
            o[moi] = 0
            ans += n - me - max(max(e), max(o))
        else:
            ans = n - max(e) - max(o)
    print(ans)


main()


Measured memory_bytes: 17508