akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
class modint{
public:
  long long x;
  constexpr modint(long long x=0):x((x%MOD+MOD)%MOD){}
  constexpr modint operator-() const{return modint(-x);}
  constexpr modint& operator+=(const modint& a){
    if((x+=a.x)>=MOD) x-=MOD;
    return *this;
  }
  constexpr modint& operator-=(const modint& a){
    if((x+=MOD-a.x)>=MOD) x-=MOD;
    return *this;
  }
  constexpr modint& operator*=(const modint& a){
    (x*=a.x)%=MOD;
    return *this;
  }
  constexpr modint operator+(const modint& a) const{return modint(*this)+=a;}
  constexpr modint operator-(const modint& a) const{return modint(*this)-=a;}
  constexpr modint operator*(const modint& a) const{return modint(*this)*=a;}
  constexpr bool operator==(const modint& a) const{return this->x==a.x;}
  constexpr bool operator!=(const modint& a) const{return this->x!=a.x;}
  constexpr modint pow(long long expo) const{
    if(expo==0)  return 1;
    modint a=pow(expo>>1);
    a*=a;
    if(expo&1)  a*=(*this);
    return a;
  }
  //for prime MOD
  constexpr modint inv() const{return pow(MOD-2);}
  constexpr modint& operator/=(const modint& a){return (*this)*=a.inv();}
  constexpr modint operator/(const modint& a) const{return modint(*this)/=a;}
};
istream& operator>>(istream& is,const modint& a){return is >> a.x;}
ostream& operator<<(ostream& os,const modint& a){return os << a.x;}

//for binomial coefficients
const int MAX=510000;
vector<modint> fac(MAX,0);
vector<modint> finv(MAX,0);
vector<modint> inv(MAX,0);
void COMinit(){
  fac.at(0)=fac.at(1)=1;
  finv.at(0)=finv.at(1)=1;
  inv.at(1)=1;
  for(int i=2;i<MAX;i++){
    fac.at(i)=fac.at(i-1)*i;
    inv.at(i)=-inv.at(MOD%i)*(MOD/i);
    finv.at(i)=finv.at(i-1)*inv.at(i);
  }
}
modint COM(int n,int k){
  if(n<k) return 0;
  if(n<0 || k<0)  return 0;
  return fac.at(n)*finv.at(k)*finv.at(n-k);
}

int N,K;
modint ans=0;
void dfs(vector<vector<int>> &graph,int v,int pa,int depth){
  if(depth==0)  ans=K;
  int cnt=0;
  for(int i=0;i<sz(graph.at(v));i++){
    int nv=graph.at(v).at(i);
    if(nv==pa)  continue;
    if(depth==0){
      int tmp=K-1-cnt;
      if(tmp<=0)  ans=0;
      ans*=modint(tmp);
    }
    else{
      int tmp=K-2-cnt;
      if(tmp<=0)  ans=0;
      ans*=modint(tmp);
    }
    cnt++;
    dfs(graph,nv,v,depth+1);
  }
}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin >> N >> K;
  vector<vector<int>> graph(N);
  for(int i=0;i<N-1;i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    graph.at(a).p_b(b);
    graph.at(b).p_b(a);
  }

  dfs(graph,0,-1,0);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 27580
package main

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

func main() {
	sc := NewScanner()
	N, M := sc.NextInt(), sc.NextInt()
	H := sc.NextIntArray()
	edge := make([]int, N)
	win := make([]int, N)
	for i := 0; i < M; i++ {
		A, B := sc.NextInt(), sc.NextInt()
		A--
		B--
		edge[A]++
		edge[B]++
		if H[A] > H[B] {
			win[A]++
		} else if H[A] < H[B] {
			win[B]++
		}
	}
	ans := 0
	//fmt.Printf("%+v\n", win)
	for k, v := range win {
		if v == edge[k] {
			ans++
		}
	}

	fmt.Println(ans)

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextFloat() float64 {
	v, _ := strconv.ParseFloat(s.Next(), 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 8756
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int inf=1<<30;
struct ask{
	int b,c;
}p[N];
long long i,j,k,m,n,tot,flag;
int a[N],ver[N],nxt[N],edge[N],head[N];
char s[N],t[N];
void add(int x,int y,int w)
{
	ver[++tot]=y,edge[tot]=w,nxt[tot]=head[x],head[x]=tot;
}
bool cmp(ask x,ask y){return x.c>y.c;}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&p[i].b,&p[i].c);
	}
	sort(p+1,p+m+1,cmp);
	sort(a+1,a+n+1);
	j=1;
	tot=0;
	for(int i=1;i<=n;i++)
	{
		if(flag||j>m) tot+=a[i];
		else
		{
			if(p[j].c>a[i])
			{
				if(p[j].b)
				{
					tot+=p[j].c;
					p[j].b--;
				}
				else
				{
					j++;
					if(p[j].c>a[i]) tot+=p[j].c,p[j].b--;
					else tot+=a[i],flag=1;
				}
			}
			else 
			{
				tot+=a[i],flag=1;
			}
		}
	}
	printf("%lld",tot);
	return 0;
}

Measured memory_bytes: 4352
#include <cstdio>
int main() {
  int n, a, c = 0, c2 = 0;
  for (scanf("%d", &n); n; --n) {
    scanf("%d", &a);
    if (a & 1) --c;
    else if (a & 2) ++c2;
    else ++c;
  }
  puts(c + !c2 >= 0 ? "Yes" : "No");
  return 0;
}

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

int main() {

    string s;
    cin >> s;
    if(s.at(2) == s.at(3) && s.at(4) == s.at(5)) cout << "Yes" << endl;
    else                                         cout << "No"  << endl;

    return 0;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String [] args)
    {
        long even, odd;


        Scanner sc = new Scanner(System.in);
        even = sc.nextLong();
        odd = sc.nextLong();

        long evenTot = (even*(even-1))/2;
        long oddTot = (odd*(odd-1))/2;
        System.out.print(evenTot+oddTot);
    }
}


Measured memory_bytes: 21844
#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()

using namespace std;

namespace Dump {
#define dump(...) Dump::print(#__VA_ARGS__, __VA_ARGS__)
static std::vector<string> dumpKey;
static string dumpKeyBuf;

void print() { cerr << endl; }
template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) {
  if (dumpKey.empty()) {
    dumpKeyBuf = head;
    dumpKeyBuf.erase(std::remove_if(dumpKeyBuf.begin(), dumpKeyBuf.end(),
                                    [](char c) { return c == ' '; }),
                     dumpKeyBuf.end());

    std::istringstream stream(dumpKeyBuf);
    string field;
    while (std::getline(stream, field, ','))
      dumpKey.push_back(field);

    reverse(dumpKey.begin(), dumpKey.end());
  } else {
    cerr << dumpKey.back() << ":" << head << "  ";
    dumpKey.pop_back();
  }
  Dump::print(std::move(tail)...);
}
}

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef vector<unsigned long long> vull;
typedef pair<int, int> pii; // p.first p.second

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

void solve(long long N, vector<long long> t, vector<long long> x,
           vector<long long> y) {
  ll preT = 0;
  ll preX, preY;
  preX = preY = 0;

  REP(i, N) {
    ll diffT = t[i] - preT;
    ll diffP = abs(preX - x[i]) + abs(preY - y[i]);
    // dump(t[i], preT, preX, preY, x[i], y[i], diffT, diffP);
    if (diffP <= diffT && abs(diffP - diffT) % 2 == 0) {
    } else {
      cout << "No" << endl;
      return;
    }
    preT = t[i];
    preX = x[i];
    preY = y[i];
  }
  cout << "Yes" << endl;
}

int main() {
  ios::sync_with_stdio(false);
  long long N;
  cin >> N;
  vector<long long> t(N - 1 + 1);
  vector<long long> x(N - 1 + 1);
  vector<long long> y(N - 1 + 1);
  for (int i = 0; i <= N - 1; i++) {
    cin >> t[i];
    cin >> x[i];
    cin >> y[i];
  }
  solve(N, t, x, y);
  return 0;
}


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

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

    int h, w;
    cin >> h >> w;

    vector<vector<int>> cost(10, vector<int>(10));
    rep(i, 10) rep(j, 10) cin >> cost[i][j];

    vector<vector<int>> a(h, vector<int>(w));
    rep(i, h) rep(j, w) cin >> a[i][j];

    const int INF = 1001001001;
    vector<int> dist2one(10, INF);
    dist2one[1] = 0;

    rep(s, 10){
        if(s == 1) continue;
        vector<int> dist(10, INF);
        dist[s] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push(make_pair(0, s));

        while(!pq.empty()){
            pair<int, int> p = pq.top();
            int v = p.second;
            pq.pop();

            rep(nv, 10){
                if(nv == v) continue;

                if(dist[nv] > dist[v] + cost[v][nv]){
                    dist[nv] = dist[v] + cost[v][nv];

                    pq.push(make_pair(dist[nv], nv));
                }
            }
        }

        dist2one[s] = dist[1];
    }

    int res = 0;
    rep(i, h) rep(j, w){
        if(a[i][j] == -1) continue;
        res += dist2one[a[i][j]];
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 384
package main

import "fmt"

func main() {
        var a, b, c, x, y, sum int
        fmt.Scan(&a, &b, &c, &x, &y)
        if a+b < 2*c {
                sum = a*x + b*y
        } else if x <= y {
                if 2*c <= b {
                        sum = 2 * c * y
                } else {
                        sum = 2*c*x + (y-x)*b
                }
        } else {
                if 2*c <= a {
                        sum = 2 * c * x
                } else {
                        sum = 2*c*y + (x-y)*a
                }
        }
        fmt.Printf("%d\n", sum)
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string>
#include <cstdlib>

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int main() {
	
	int k, t; cin >> k >> t;
	int a[t], sum_a = 0, max_a;
	for(int i = 0; i < t; i++) {
		cin >> a[t];
		sum_a += a[t];
		max_a = max(max_a, a[t]);
	}
	if(t == 1) { cout << k-1 <<endl; return 0; }
	if(max_a > sum_a-max_a) cout << max_a - (sum_a - max_a) -1 << endl;
	else cout << 0 <<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static class State {
        int[] visited;
        int now;

        public State(int[] visited, int now) {
            this.now = now;
            this.visited = visited.clone();
        }

        public String toString() {
            return Arrays.toString(this.visited) + String.format(" now: %d", this.now);
        }

        private boolean isAllVisited() {
            for (int i = 0; i < this.visited.length; i++) {
                if (this.visited[i] != 1)
                    return false;
            }

            return true;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int count = 0;

        Queue<State> queue = new LinkedList<>();
        List<List<Integer>> paths = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            paths.add(i, new ArrayList<>());
        }

        int x,y;
        for (int i = 0; i < M; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            paths.get(x-1).add(y);
            paths.get(y-1).add(x);
        }
//        for (List<Integer> list : paths) {
//            System.out.println(list.toString());
//        }
        int[] visited = new int[N];
        visited[0] = 1;

        queue.add(new State(visited, 1));

        while(!queue.isEmpty()) {

            State state = queue.poll();
            int now = state.now;
//            System.out.println(state);
            if (state.isAllVisited()) {
                count += 1;
            } else {
                for (Integer i : paths.get(now-1)) {
                    if (state.visited[i-1] == 0) {
                        int[] v = state.visited.clone();
                        v[i-1] = 1;
                        queue.add(new State(v, i));
                    }
                }
            }
        }

        System.out.println(count);

    }

    private static int calc(int x) {
        return x;
    }

    private static void test() {
        assert calc(0) == 0;
    }
}


Measured memory_bytes: 25940
#include <iostream>
#include <cstdio>
#include <complex>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;

int main()
{
    int d;
    int S;
    while(cin >> d && d)
    {
        S=0.0;
        int a = 600/d;
        for(int i=1;i<a;i++)
        {
            S += d*i*d*i*d;
        }
        cout << S << endl;
    }
    return 0;
}


Measured memory_bytes: 3056
#include <stdio.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n;
int color[MAX], d[MAX], f[MAX],cnt;
int M[MAX][MAX];

void visit(int u){
	int v;
	color[u] = GRAY;
	d[u] = ++cnt;
	for(v=0;v<n;v++){
		if(M[u][v] == 0) continue;
		if(color[v] == WHITE){
			visit(v);
		}
	}
	color[u] = BLACK;
	f[u] = ++cnt;
}

void print(){
	int u;
	for(u=0;u<n;u++) color[u] = WHITE;
	cnt = 0;

	for(u=0;u<n;u++){
		if(color[u] == WHITE) visit(u);
	}
	for(u=0;u<n;u++){
		printf("%d %d %d\n",u+1,d[u],f[u] );
	}
}

	int main(){
		int u,v,k,i,j;

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

		for(i=0;i<n;i++){
			scanf("%d %d",&u,&k);
			u--;
			for(j=0;j<k;j++){
				scanf("%d",&v);
				v--;
				M[u][v] = 1;
			}
		}

		print();

	return 0;
}


Measured memory_bytes: 2052
#include <iostream>
#include <string>
using namespace std;
int main(){
    int a; cin >> a;
    string s; cin >> s;
    int ans = 0;
    for(int i = 1; i < s.size(); i++){
        string a = s.substr(0,i);
        string b = s.substr(i);
        int cnt = 0;
        for(char c = 'a'; c <= 'z'; c++){
            bool flag1 = false, flag2 = false;
            for(char m:a) if(m == c) flag1 = true;
            for(char m:b) if(m == c) flag2 = true;
            if(flag1&&flag2) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}
//Saw the solution video

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>> n ;
    for(int i=0;i<n;i++){
        int x ;cin>>x;
        if( x & 1 ) continue;
        else{
            if(x %3 != 0 && x%5!=0){
                cout<<"DENIED"<<endl;
                return 0;
            }
        }
    }
    cout<<"APPROVED"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=200,W=1e5+100;
int v[N],w[N];
long long dp[N][W];
int main(){
    int n,we;
    cin>>n>>we;
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];

    for(int i=n-1;i>=0;i--)
        for(int j=0;j<=we;j++)
            dp[i][j]=max(dp[i+1][j],(j-w[i]>=0?dp[i+1][j-w[i]]+v[i]:-1));

    cout<<dp[0][we];
    
    return 0;
}

Measured memory_bytes: 80128
n = gets.chomp.to_i
h = gets.chomp.split(' ').map(&:to_i)
ans = 0
while(true) do
  min = 10 ** 7
  l = -1
  r = -1
  h.each_with_index do |v, i|
    if l == -1 && v > 0
      l = i
    elsif l != -1 && r == -1 && v == 0
      r = i - 1
    end
    min = [v, min].min if v != 0
  end
  break if r == -1 && l == -1
  if r == -1
    r = n - 1
  end
  l.upto r do |i|
    h[i] -= min
  end
  ans += min
end
puts ans


Measured memory_bytes: 1788
#include<iostream>
#include <string> 
#include <vector>  
#include<math.h>

#define INF 1000000000
using namespace::std;

void m_sort(int a[], int tmp[], int left, int right);
void m_sort(int a[], int tmp[], int left, int right);
void sort(int a[], int total) {
	int tmp;
	for (int i = 0; i < total; i++) {
		for (int j = i + 1; j < total; j++) {
			if (a[i] < a[j]) {
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
	}

}

void mergeSort(int a[], int tmp[], int size)
{
	m_sort(a, tmp, 0, size - 1);
}
void merge(int a[], int tmp[], int left, int mid, int right)
{
	int i, left_end, num_elements, tmp_pos;

	left_end = mid - 1;
	tmp_pos = left;
	num_elements = right - left + 1; // 要素 

	while ((left <= left_end) && (mid <= right))
	{
		if (a[left] <= a[mid])
		{
			tmp[tmp_pos] = a[left];
			tmp_pos = tmp_pos + 1;
			left = left + 1;
		}
		else
		{
			tmp[tmp_pos] = a[mid];
			tmp_pos = tmp_pos + 1;
			mid = mid + 1;
		}
	}


	while (left <= left_end)
	{
		tmp[tmp_pos] = a[left];
		left = left + 1;
		tmp_pos = tmp_pos + 1;
	}

	while (mid <= right)
	{
		tmp[tmp_pos] = a[mid];
		mid = mid + 1;
		tmp_pos = tmp_pos + 1;
	}


	for (i = 0; i <= num_elements; i++)
	{
		a[right] = tmp[right];
		right = right - 1;
	}
}
void m_sort(int a[], int tmp[], int left, int right)
{
	int mid;

	if (right > left)
	{
		mid = (right + left) / 2;
		m_sort(a, tmp, left, mid);
		m_sort(a, tmp, mid + 1, right);

		merge(a, tmp, left, mid + 1, right);
	}
}


long Lmax(long x, long y) {
	if (x > y)return x;
	return y;
}

int max(int x, int y) {
	if (x > y)return x;
	return y;
}

long Lmin(long x, long y) {
	if (x < y)return x;
	return y;
}


int min(int x, int y) {
	if (x < y)return x;
	return y;
}

int abs(int a) {
	if (a < 0) {
		return -a;
	}
	return a;
}

int N, M,F,K, W,L,X[2000000], Y[2000000], Z[2000000], ans, k[5],B,C,n[2];
string s, t[100];
bool a, b, c;
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> X[i];
		Z[i] = X[i];
	}
	mergeSort(X, Y, N);

	F = X[((N) / 2)-1];
	B = X[((N) / 2) ];
	for (int i = 0; i < N; i++) {
		if (Z[i]<=F) {
			cout << B << endl;
		}
		else {
			cout << F << endl;
		}
	}
	
	return 0;
}




Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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
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;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
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;
}
vector<int>kaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
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;
}
int comb(int a,int b){
    //if(!kaijo[0])init_fact(2000010);
    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;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}

signed main(){
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%k==0){
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;
    return 0;
}


Measured memory_bytes: 3640
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res
def solve():
    n = I()
    S = list(input())
    m = ord("z")-ord("a")+1
    s = [SegmentTree(n,0) for i in range(m)]
    for i in range(n):
        k = ord(S[i])-ord("a")
        s[k].update(i,1)
    Q = I()
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1])-1
            if S[i] == q[2]:
                continue
            k = ord(S[i])-ord("a")
            s[k].update(i,0)
            k = ord(q[2])-ord("a")
            s[k].update(i,1)
            S[i] = q[2]
        else:
            l,r = q[1:]
            l = int(l)
            r = int(r)
            ans = 0
            for k in range(m):
                if s[k].get(l-1,r):
                    ans += 1
            print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 285084
#include <bits/stdc++.h>
#define ll      	long long int
#define PI      	acos(-1)
#define read    	freopen("in.txt","r",stdin)
#define uu      	first
#define vv      	second
#define write   	freopen("out.txt","w",stdout)
#define pii     	pair<int,int>
#define pll         pair<ll,ll>
#define INF     	1e9
#define EPS     	1e-8
#define MAX     	100005
#define MOD     	1000000007
#define fastRead 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
int n;
vector<int>edg[MAX];
ll dp[MAX][2];


int dfs(int node ,int par , int col ) {

    ll &ret = dp[node][col];
    if( ret!= -1) return ret;
    ret  = 1;

    for(auto x : edg[node]) {
        if(x == par) continue;
        if( col == 1) ret =(ret * dfs(x , node , 0) )%MOD ;
        else {
            ll tmp = ( dfs(x , node , 0)%MOD + dfs(x , node , 1)%MOD) % MOD ;
            ret = (ret * tmp)%MOD;
        }
    }
    return ret;
}


int main()
{
    fastRead;
    cin>>n;
    for(int i =0 ; i < n-1 ; i++ ) {
        int u , v;
        cin>>u>>v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    memset(dp , -1 , sizeof dp);
    int ans = (dfs(1 , 0 , 0)  + dfs(1, 0 , 1)  ) %MOD;
    cout<<ans<<endl;


}


Measured memory_bytes: 15616
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[111111];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	cout<<a[n/2]-a[n/2-1]<<endl;
	return 0;
}


Measured memory_bytes: 640
{-# LANGUAGE BangPatterns #-}
module Main where
import qualified Data.ByteString.Char8 as B
import Data.List(foldl', unfoldr)
import Data.Char(isSpace)
import Data.Monoid((<>))
import Debug.Trace
import System.Mem.Weak
import System.Mem
import Control.Exception

sort :: Ord a => [a] -> [a]
sort = sortBy compare

{-# NOINLINE sort #-}
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy compare = mergeAll . sequences
    where
    sequences (a:b:xs)
      | a `compare` b == GT = descending b [a]  xs
      | otherwise       = ascending  b (a:) xs
    sequences xs = [xs]

    descending a as (b:bs)
      | a `compare` b == GT = descending b (a:as) bs
    descending a as bs  = (a:as): sequences bs

    ascending a as (b:bs)
      | a `compare` b /= GT = ascending b (\ys -> as (a:ys)) bs
    ascending a as bs   = let !x = as [a]
                          in x : sequences bs

    mergeAll [x] = x
    mergeAll xs  = mergeAll (mergePairs xs)

    mergePairs (a:b:xs) = let !x = merge a b
                          in x : mergePairs xs
    mergePairs xs       = xs

    merge as@(a:as') bs@(b:bs')
      | a `compare` b == GT = (b: ) $! merge as  bs'
      | otherwise       = (a: ) $! merge as' bs
    merge [] bs         = bs
    merge as []         = as

data PI = PI {-# UNPACK #-}!Int {-# UNPACK #-} !Int {-# UNPACK #-} !Int
    deriving (Eq, Ord)

parse :: B.ByteString -> [PI]
parse = unfoldr step
  where
  step !s | B.null s = Nothing
          | otherwise = do
               (n1, s1) <- B.readInt s
               (n2, s2) <- B.readInt (B.tail s1)
               let !s3 = B.dropWhile isSpace s2
               return (PI (- (n1 + n2)) n1 n2, s3)

main :: IO ()
main = do
    n <- fmap read getLine :: IO Int
    content <- B.getContents
    let asbs = parse content
    let l  = sort asbs
        ps = cycle [1,-1 :: Int]
        ans = sum $ zipWith (\(PI _ a b) p -> if p == 1 then a else -b) l ps
    evaluate l
    traceMarker "sort" (print ans)


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

int main(){
    string S;
    cin >> S;
    int a[26]={};
    for(int i=0; i<4; i++){
        int j = S[i] - 'A';
        a[j]++;
    }
    int anscount=0;
    for(int i=0; i<26; i++){
        if(a[i]==2){
            anscount++;
        }
    }    
    if(anscount==2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()
B = MAP()
C = MAP()

ans = 0
for idx,a in enumerate(A):
	ans += B[a-1]
	if idx < len(A)-1 and A[idx+1] == a+1:
		ans += C[a-1]

print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FT first
#define SC second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int INF = 1e9;
const double EPS = 1e-9;



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

  return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <tuple>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

const std::vector<int>
    dx{-1, 0, 1, 0},
    dy{0, -1, 0, 1};

void solve() {
    int h, w;
    std::cin >> h >> w;

    auto xss = vec(h, vec(w, 0));
    std::vector<std::pair<int, int>> pos(h * w);
    for (int x = 0; x < h; ++x) {
        for (int y = 0; y < w; ++y) {
            auto& a = xss[x][y];
            std::cin >> a;
            pos[--a] = std::make_pair(x, y);
        }
    }

    auto to = vec(h, vec(w, 0));
    for (auto p : pos) {
        int x, y;
        std::tie(x, y) = p;

        std::set<int> tos;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i],
                ny = y + dy[i];
            if (nx < 0 || h <= nx || ny < 0 || w <= ny ||
                xss[nx][ny] > xss[x][y]) continue;

            if (to[nx][ny] < 0) to[x][y] = -1;
            tos.insert(to[nx][ny]);
        }

        if (to[x][y] < 0) continue;

        if (tos.empty()) tos.insert(xss[x][y]);
        if (tos.size() >= 2) tos.insert(-1);
        to[x][y] = *tos.begin();
    }

    int ans = 0;
    for (int x = 0; x < h; ++x) {
        for (int y = 0; y < w; ++y) {
            if (to[x][y] < 0) ++ans;
        }
    }

    std::cout << ans << std::endl;
}

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

    solve();

    return 0;
}



Measured memory_bytes: 18648
#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

LL A, B, C;

void MAIN() {
    scanf("%lld%lld%lld", &A, &B, &C);
    // A + 2sqrt(AB) + B < C;
    // 2sqrt(AB) < C-A-B;
    // 4AB < (C-A-B)^2;
    LL R = C-A-B;
    bool yes;
    if (R > 0) {
	LL L = 4*A*B;
	R *= R;
	yes = (L < R);
    } else {
	yes = false;
    }
    puts(yes? "Yes": "No");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>

int main(){
    int h, w;
    std::cin >> h >> w;

    std::vector<std::string> grid;
    std::string dummy(w + 2, '$');
    grid.push_back(dummy);
    for(int i = 0; i < h; ++i){
        std::string s;
        std::cin >> s;
        grid.push_back("$" + s + "$");
    }
    grid.push_back(dummy);

    bool flg = true;
    int i = 1;
    while(flg && i < h - 1){
        for(int j = 1; j < w - 1; ++j){
            if('#' == grid.at(i).at(j)){
                std::string buf =   grid.at(i - 1).substr(j, 1);
                            buf +=  grid.at(i + 1).substr(j, 1);
                            buf +=  grid.at(i).substr(j - 1, 1);
                            buf +=  grid.at(i).substr(j + 1, 1);
                if(std::string::npos == buf.find("#")){
                    flg = false;
                }
            }
        }
        ++i;
    }

    std::string ans = "No";
    if(flg){
        ans = "Yes";
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int arr[] = new int[x];
        for (int i = 0; i < x; i++)
            arr[i] = sc.nextInt();
        int dp[] = new int[x];
        if(x==1)
            System.out.println(arr[0]);
        for (int i = 1; i < x; i++) {
            int abs1 = Math.abs(arr[i] - arr[i - 1]);
            if (i == 1) {
                int abs = abs1;
                dp[i] = abs;
            } else {
                dp[i] = Math.min(abs1+dp[i-1], Math.abs(arr[i] - arr[i - 2])+dp[i-2]);
            }
        }
        System.out.println(dp[x - 1]);
    }
}


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

int main() {
  ll n;
  cin >> n;
  if (n % 2 == 1) {
    cout << 0 << endl;
    return 0;
  }
  
  vector<ll> r;
  for (ll ret = 5; ret < 1e18; ret *= 5) {
    r.push_back(n / 2 / ret);
  }
  
  ll ans = accumulate(r.begin(), r.end(), 0LL);
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	a = Int[n-1]
	t = 2
	while t<=sqrt(n)
		if n%t==0
			push!(a,div(n,t)+t-2)
		end
		t+=1
	end
	println(minimum(a))
end

main()

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

#define debug(x) (cerr << #x << " = " << x << endl;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

const int maxn = 2e5 + 100;

ll a[maxn];

ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

ll lcm(ll a, ll b)
{
  return a * (b / __gcd(a,b));
}

char f(char c)
{
  if(c == 'r')
    return 'p';
  else if(c == 'p')
    return 's';
  else
    return 'r';
}


int main()
{

  ios::sync_with_stdio(0);
  int n,k,r,s,p;
  string t;
  cin >> n >> k >> r >> s >> p;
  cin >> t;
  int ans = 0;
  map<char, int>vals;
  vals['r'] = r;
  vals['s'] = s;
  vals['p'] = p;
  vector<bool>win(n, false);
  for(int i = n - 1 ; i >= 0; i--)
  {
    int next = i + k;
    if(next < n)
    {
      if(t[i] == t[next] && win[next])
        continue;
    }
    win[i] = true;
    ans += vals[f(t[i])];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3712
#include<stdio.h>


int main()
{
    long long int a,b,k;
    scanf("%lld %lld %lld",&a,&b,&k);

    if(k<=a){
        printf("%lld %lld\n",a-k,b);
    }
    else if(k<=a+b){
        printf("0 %lld\n",b-(k-a));
    }
    else{
        printf("0 0\n");
    }

}

Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    long x,max,min,num;
    cin>>x;
    max=x;
    min=x;
    num+=x;
    for (int i = 2;i <=n; ++i) {
        cin>>x;
        if(x>max)max=x;
        if(x<min)min=x;
        num+=x;
    }
    printf("%ld %ld %ld\n",min,max,num);
    return 0;

}


Measured memory_bytes: 3232
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)	
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<string> vs;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
Def inf = sizeof(Def) == sizeof(ll) ? 2e18 : 1e9+10;
int main(){
	vi w;
	loop(i,1,200)if(i*(i+1)*(i+2)/6<1000100)w.pb(i*(i+1)*(i+2)/6);
	const int n=1000100;
	vi dp(n+1,inf),dp2(n+1,inf);
	dp[0]=dp2[0]=0;
	rep(i,w.size())rep(j,n){
		int t=j+w[i];
		if(t<n+1)dp[t]=min(dp[t],dp[j]+1);
		if(t<n+1&&w[i]%2)dp2[t]=min(dp2[t],dp2[j]+1);
	}
	int m;
	while(cin>>m,m){
		cout<<dp[m]<<" "<<dp2[m]<<endl;
	}
}











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

vector<bool> seen;

void DFS(vector<vector<int>> G, int p, int N){
  seen.at(p)=true;
  for(int i=0; i<N; i++){
    if(p!=i){
      if(seen.at(i)==true){
        continue;
      }
      else{
        if(G.at(p).at(i)==1){
          DFS(G, i, N);
        }
      }
    }
  }
}

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G0(N, vector<int>(N));
  vector<int> A(M), B(M);
  for(int i=0; i<M; i++){
    cin >> A.at(i) >> B.at(i);
    G0.at(A.at(i)-1).at(B.at(i)-1)++;
    G0.at(B.at(i)-1).at(A.at(i)-1)++;
  }
  vector<vector<int>> G(N, vector<int>(N));
  int Ans=0;
  for(int i=0; i<M; i++){
    G=G0;
    G.at(A.at(i)-1).at(B.at(i)-1)--;
    G.at(B.at(i)-1).at(A.at(i)-1)--;
    seen.assign(N, false);
    DFS(G, 0, N);
    int k=1;
    for(int i=0; i<N; i++){
      k*=seen.at(i);
    }
    Ans+=(!k);
  }
  cout << Ans << endl;
}
  

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

int main(){
    string s,t;
    cin >> s;
    t=s;
    int ans=0;
    int n=s.size();
    //cout << n << endl;
    reverse(s.begin(),s.end());
    //cout << s << endl;
    rp(i,n/2){
        if(s.at(i)!=t.at(i)) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

int N;
map<ll, int> mp;

int main(void){
    
    scanf("%d", &N);
    for(int i = 0; i < N; ++i){
        ll a; scanf("%lld", &a);
        if(mp.find(a) == mp.end()) ++mp[a];
        else mp.erase(a);
    }
    printf("%d\n", (int)mp.size());
    
    return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 101000
#define ac 300000
#define LL long long

int n, cnt, num, m, k;
LL ans, v[AC];
int s[AC], f[AC];
int Head[AC], Next[ac], date[ac], tot;
bool vis[AC];

inline int read()
{
	int x = 0;char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x; 
}

inline void add(int f, int w)
{
	date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot;
	date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot;
}

void pre()
{
	n = read(), m = read();
	for(R i = 1; i <= n; i ++) v[i] = read();
	for(R i = 1; i <= m; i ++)
	{
		int a = read() + 1, b = read() + 1;
		add(a, b);
	}
}

void dfs(int x)
{
	vis[x] = true, s[++ cnt] = v[x];
	for(R i = Head[x]; i; i = Next[i])
	{
		int now = date[i];
		if(vis[now]) continue;
		dfs(now);
	}
}

void work()
{
	for(R i = 1; i <= n; i ++)
	{
		if(vis[i]) continue;
		cnt = 0, dfs(i), ++k;
		sort(s + 1, s + cnt + 1);
		ans += s[1];
		for(R j = 2; j <= cnt; j ++) f[++ num] = s[j];
	}
	if(k == 1) {printf("0\n"); return ;}
	sort(f + 1, f + num + 1);
	if(n < 2 * k - 2) {printf("Impossible\n"); return ;}
	int have = 2 * k - 2 - k;
	for(R i = 1; i <= have; i ++) ans += f[i];
	printf("%lld\n", ans);
}

int main()
{
	//freopen("in.in", "r", stdin);
	pre();
	work();
	//fclose(stdin);
	return 0;
}

Measured memory_bytes: 4224
import java.util.*;

public class Main {

    public void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            countMap.put(a, countMap.getOrDefault(a, 0) + 1);
        }

        List<Integer> counts = new ArrayList<>(countMap.values());
        Collections.sort(counts);

        int ans = 0;
        for (int i = 0; i < counts.size() - k; i++) {
            ans += counts.get(i);
        }

        System.out.println(ans);
    }

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

Measured memory_bytes: 103100
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b

signed main(){
	ll n; cin>>n;
	map<ll,ll> mp;
	ll cnt=0;
	rep(i,0,n){
		int a; cin>>a;
		if(a<400)mp[1]++;
		else if(a<800)mp[2]++;
		else if(a<1200)mp[3]++;
		else if(a<1600)mp[4]++;
		else if(a<2000)mp[5]++;
		else if(a<2400)mp[6]++;
		else if(a<2800)mp[7]++;
		else if(a<3200)mp[8]++;
		else cnt++;
	}
	cout<<(mp.size()==0 ? 1:mp.size())<<" "<<mp.size()+cnt<<endl;
	return 0;
}

Measured memory_bytes: 3640
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int main(){
	int K,T;
	cin>>K>>T;
	vector<int> a(T);
	int tmp=0;
	for(int i=0;i<T;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end(),greater<int>());
	for(int i=1;i<T;i++){
		tmp+=a[i];
	}
	if(a[0]<=tmp){
		cout<<"0"<<endl;
	}else{
		cout<<a[0]-tmp-1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lln long long int
#define llu unsigned lln
#define sc(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define scd(n) scanf("%lf",&n);
#define pf(res) printf("%d\n",res);
#define pfl(res) printf("%lld\n",res);
#define pfd(res) printf("%lf\n",res);
#define pb(n) push_back(n);
#define maxii 200005
using namespace std;
typedef pair<int,int> pii;
typedef pair<lln,lln> pll;
vector<int> vi;
vector<lln> vl;
vector<pii> vii;
vector<pll> vll;


lln arr[maxii];
lln arr2[maxii];
//bool check[maxii];
bool check2[1000][1000];
//lln n,m;

int main()
{
   int n,k;
   cin>>n>>k;
   for(int i=0;i<n;i++)
   {
       cin>>arr[i];
   }
   lln sum=0;
   sort(arr,arr+n);
   reverse(arr,arr+n);
   for(int i=0;i<n && i<k;i++)
   {
       sum+=arr[i];
   }
   cout<<sum;
}






Measured memory_bytes: 3624
n = int(input())
S = input()
moji = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ans = []
for s in S:
    for m in moji:
        if m == s:
            ans.append(moji[(moji.index(m) + n) % len(moji)])
ans = "".join(ans)
print(ans)


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

using namespace std;

const int max_n = -1, inf = 1000111222;

long long a, b, c;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> a >> b >> c;
    long long ans = min(c, a + b + 1) + b;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import Debug.Trace

main :: IO ()
main = do
  n <- readLn :: IO Int
  print $ solve n

solve :: Int -> Int
solve n
  | n== 0 = 2
  | n== 1 = 1
  | otherwise = let (x, y) = f (n-1) in
--            trace (show (x, y)) $
            y * 2 + x
  where
    f i
      |i == 0 = (1, 0)
      |i == 1 = (1, 1)
      |otherwise = let (n1, n2) = f (i-1) in
                     (n1+n2, n1)


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

int main() {
  int n,m;
  cin>>n>>m;

  using Graph = vector<vector<int>>;
  Graph graph(n);
  for(int i=0; i<m; i++) {
    int a,b;
    cin>>a>>b;
    graph[a-1].push_back(b-1);
    graph[b-1].push_back(a-1);
  }

  int group[n];
  for(int i=0; i<n; i++) group[i]=0;

  queue<int> todo;
  int num = 1;
  for(int i=0; i<n; i++) {
    if(group[i]==0) {
      group[i] = num;
      todo.push(i);
      while(!todo.empty()) {
        int now = todo.front();
        todo.pop();
        for(int next : graph[now]) {
          if(group[next]!=0) continue;
          group[next] = num;
          todo.push(next);
        }
      }
      num++;
    }
  }

  int numbers[n+1];
  for(int i=0; i<n+1; i++) numbers[i]=0;

  for(int i=0; i<n; i++) {
    numbers[group[i]]++;
  }

  int ans = *max_element(numbers, numbers+n+1);

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 16348
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

void dfs(vector<string> &ss, int n, int index, char c, const string &s) {
    if (index == n) ss.push_back(s);
    else {
        for (int i = 0; i <= c - 'a' + 1; ++i) {
            dfs(ss,n,index+1,max(c, char('a'+i)),s+char('a'+i));
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<string> ss;
    dfs(ss,n,1,'a',"a");
    sort(all(ss));
    for (auto &s: ss) cout << s << endl;
}

signed main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 7796
// Problem : A - Circle Pond
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);

int main()
{
	fastio;
	int r;
	cin>>r;
	printf("%.3lf\n",2*3.14159265*r);
   	return 0;
}


Measured memory_bytes: 3744
import itertools
N = int(input())
A = list(map(int,input().split()))
A.sort()
acum = list(itertools.accumulate(A))

def solve():
    unreachable = None
    for i in range(N-2,-1,-1):
        if 2*acum[i] < A[i+1]:
            unreachable = i
            break
    if unreachable is None:
        return N
    return N - 1 - unreachable

print(solve())

Measured memory_bytes: 14428