akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int INT_INF = 500000000;
const long long LONG_LONG_INF = (long long)pow(10, 18);
const int MOD = pow(10, 9) + 7;
/* contest template */
int n;
int a[100000];
int m;
/*
int med(int s, int t, int n) {
  if (s >= t) return t;
  if (a[(s + t) / 2] < a[n - 1] / 2) {
    return med(s, (s + t) / 2 - 1, n);
  } else if (a[(s + t) / 2] > a[n - 1] / 2) {
    return med((s + t) / 2 + 1, t, n);
  } else {
    return (s + t) / 2;
  }
}
*/

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);
  m = a[0];
  for (int i = 0; i < n; i++) {
    if (abs(a[n - 1] / 2.0 - a[i]) < abs(a[n - 1] / 2.0 - m)) m = a[i];
  }
  cout << a[n - 1] << " " << m << endl;
  return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
struct UnionFind{
  vector<int> par;
  vector<int> sizes;
  UnionFind(int n) : par(n), sizes(n, 1) {
    rep(i,n) par[i] = i;
  }
  int root(int x) {
    if (x == par[x]) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (sizes[x] < sizes[y]) swap(x, y);
    par[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return sizes[root(x)];
  }
};
int main(){
	int N,M;
	int K[100001];
	scan(N>>M);
	UnionFind uf(N+M);
	rep(i,N){
		scan(K[i]);
		rep(j,K[i]){
			int l;
			scan(l);
			l--;
			uf.unite(i,N+l);
		}
	}
	int flag=1;
	rep1(i,N-1){
		if(!uf.same(0,i)) flag=0;
	}
	if(flag) prin("YES");
	else prin("NO");
	return 0;
}


Measured memory_bytes: 2176
#include <stdio.h>

#define BUF_SIZE 11
int main(void) {
  char line[BUF_SIZE];
  FILE *fp;
  fp = stdin;
  if(!fgets(line, BUF_SIZE, fp)) return 0;
  line[3] = '8';
  printf("%s\n", line);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
using namespace std;
int main(void){
    long a,b,max=-1000001,min=1000001,ans=0;
    cin>>a;
    for(int z=1;z<=a;z++){
        cin>>b;
        ans+=b;
        if(min>b){
            min=b;
        }
        if(max<b){
            max=b;
        }
       // cout<<ans<<endl;
    }
    cout<<min<<" "<<max<<" "<<ans<<endl;
}


Measured memory_bytes: 3096
#include<cstdio>
#define N 100001
int n,m,i,c,a[N],p[N],x,y;
int f(int j){
	if(p[j]==j)return j;
	return p[j]=f(p[j]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",a+i),p[i]=i;
	while(m--){
		scanf("%d%d",&x,&y);
		if(f(x)!=f(y))p[f(x)]=f(y);
	}
	for(i=1;i<=n;i++)if(f(i)==f(a[i]))c++;
	printf("%d",c);
}


Measured memory_bytes: 896
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr double DINF =100000000000000000.0;
constexpr long long INF = 100000000000000000;
const double PI = acos(-1);
 
int main() {
	string s;
	cin >> s;
	cout << s.substr(0, s.size() - 8) << endl;
}

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

int main() {
  int n;
  cin >> n;
  int ans = 0, x = 999;
  for (int i = 0; i < n; i++) {
    int s;
    cin >> s;
    ans += s;
    if (s%10 != 0 && s < x) {
      x = s;
    }
  }
  if (ans%10 != 0) {
    cout << ans << endl;
  }
  else if (ans%10 == 0 && x != 999) {
    ans -= x;
    cout << ans << endl;
  }
  else {
    cout << 0 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,int> pii;
typedef pair<int,pi> pij;
int root[100010];
int n;
vector<pii> xa,ya;
vector<pi> corx,cory;
priority_queue<pij,vector<pij>,greater<pij> > qu;
map<pi,bool> check;
int fin(int x)
{
    if(root[x]==x) return x;
    return root[x]=fin(root[x]);
}
void join(int x,int y)
{
    int p=fin(x);
    int q=fin(y);
    if(p!=q) root[p]=q;
}
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        root[i]=i;
        int x,y;
        scanf("%d%d",&x,&y);
        if(check[pi(x,y)]==1) continue;
        check[pi(x,y)]=1;
        corx.push_back(pi(x,i));
        cory.push_back(pi(y,i));
    }
    sort(corx.begin(),corx.end());
    sort(cory.begin(),cory.end());
    for(int i=1;i<corx.size();i++)
    {
        qu.push(pij(corx[i].fi-corx[i-1].fi,pi(corx[i].se,corx[i-1].se)));
        qu.push(pij(cory[i].fi-cory[i-1].fi,pi(cory[i].se,cory[i-1].se)));
    }
    int sum=0;
    while(qu.size())
    {
        pij t;
        t=qu.top();
        qu.pop();
        int x,y;
        x=t.se.fi;
        y=t.se.se;
        if(fin(x)==fin(y)) continue;
        sum+=t.fi;
        join(x,y);
    }
    cout<<sum;
}

Measured memory_bytes: 20060
class PriorityQueue
  MIN = -(1 << 60)

  attr_reader :size

  def initialize(&block)
    @size = 0
    @heap = Array.new
    @get_key = block || :itself.to_proc
  end

  def empty?
    size == 0
  end

  def pop
    return nil if @size <= 0
    max = @heap[1]
    @heap[1] = @heap[@size]
    @size -= 1
    max_heapify(1)
    max
  end

  def push(x)
    @size += 1
    i = @size
    @heap[i] = x
    while i > 1 && (@get_key.call(@heap[i / 2]) <=> @get_key.call(@heap[i])) < 0
      t = @heap[i / 2]
      @heap[i / 2] = @heap[i]
      @heap[i] = t
      i = i / 2
    end
  end

  def top
    return nil if @size <= 0
    @heap[1]
  end

  def to_a
    return [] if @size == 0
    @heap[1..@size]
  end

  private

  def max_heapify(i)
    l = 2 * i
    r = 2 * i + 1
    largest =
      l <= @size && (@get_key.call(@heap[l]) <=> @get_key.call(@heap[i])) > 0 ? l : i
    largest = r \
      if r <= @size && (@get_key.call(@heap[r]) <=> @get_key.call(@heap[largest])) > 0
    unless largest == i
      t = @heap[i]
      @heap[i] = @heap[largest]
      @heap[largest] = t
      max_heapify(largest)
    end
  end
end


N, M, R = gets.split.map(&:to_i)
rs = gets.split.map { |s| s.to_i - 1 }
edges = M.times.map { gets.split.map(&:to_i) }
graph = Array.new(N) { [] }
edges.each do |(u, v, c)|
  u -= 1
  v -= 1
  graph[u].push([v, c])
  graph[v].push([u, c])
end

def shortest_path(graph, s)
  w_list = Array.new(graph.size, 1 << 60)
  w_list[s] = 0
  queue = PriorityQueue.new
  queue.push([s, 0])
  while !queue.empty?
    v, w = queue.pop
    next if w > w_list[v]
    graph[v].each do |(u, c)|
      if w_list[u] > w_list[v] + c
        w_list[u] = w_list[v] + c
        queue.push([u, w_list[u]])
      end
    end
  end
  w_list
end

ds = {}
rs.each do |r|
  ds[r] = shortest_path(graph, r)
end

def dfs(rs, u, sum_d, ds)
  return sum_d if rs.size == 0
  min = 1 << 60
  rs.map do |r|
    trs = rs.dup
    trs.delete(r)
    d = dfs(trs, r, sum_d + ds[u][r], ds)
    min = d if d < min
  end
  min
end

ans = rs.map do |r|
  trs = rs.dup
  trs.delete(r)
  dfs(trs, r, 0, ds)
end.min
puts ans


Measured memory_bytes: 6140
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
static const int MAX = 200000;

int main()
{
	string s, t;
	cin >> s >> t;
	if (s[0] == t[2] && s[1] == t[1] && s[2] == t[0])cout << "YES" << endl;
	else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define X first
#define Y second

const int maxn=1e5+10;

int H,W,n,m,st[maxn];
pair<int,int> P[maxn];

int getrank(int x,int y)
{
	if (x==0) return y;
	if (y==W) return W+x;
	if (y==0) return -x;
	if (x==H) return -H-y;
}

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i,x1,x2,y1,y2;
	scanf("%d%d%d",&H,&W,&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		bool A=x1==0||x1==H||y1==0||y1==W;
		bool B=x2==0||x2==H||y2==0||y2==W;
		if (A&&B)
		{
			m++;
			P[m].X=getrank(x1,y1);
			P[m].Y=getrank(x2,y2);
//			printf("%d ~ %d\n",P[m].X,P[m].Y);
			if (P[m].X>P[m].Y) swap(P[m].X,P[m].Y);
		}
//		else puts("");
	}
	sort(P+1,P+m+1);
	bool flag=1;
	for (i=1;i<=m;i++)
	{
		while (st[0]&&P[i].X>st[st[0]]) st[0]--;
		if (st[0]) flag&=P[i].Y<st[st[0]];
		st[++st[0]]=P[i].Y;

//		printf("flag=%d:",flag);
//		for (int j=1;j<=st[0];j++)
//			printf("%d ",st[j]);
//		puts("");
	}


	puts(flag?"YES":"NO");

//	for (i=1;i<=m;i++)
//		printf("%d ~ %d\n",P[i].X,P[i].Y);
//	for (i=1;i<=m;i++)
//	for (int j=i+1;j<=m;j++)
//	{
//		bool A=P[i].X<P[j].X&&P[j].X<P[i].Y;
//		bool B=P[i].X<P[j].Y&&P[j].Y<P[i].Y;
//		if (A^B) printf("fuck %d %d\n",i,j);
//	}
}


Measured memory_bytes: 1280
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

using namespace std;

void b_balance(void) {
	int n;
	int* w;
	cin >> n;
	w = (int*)calloc(n, sizeof(int));
	for (int i = 0; i < n; i++)cin >> w[i];

	int sum_e = 0, sum_o = 0;
	int min_tmp;
	int min = 100000;

	
		for (int j = 1; j < n; j++) {
			sum_e = 0;
			sum_o = 0;
			for (int k = 0; k < j; k++) sum_e += w[k];
			for (int l = j; l < n; l++) sum_o += w[l];

			min_tmp = abs(sum_e - sum_o);
			if (min > min_tmp) min = min_tmp;
		}
	

	cout << min << endl;
}

int main()
{
    b_balance();

    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
using namespace std;
typedef long long ll;
ll n, a, res, ans;
int main(void){
    // Your code here!
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a;
        ans = 0;
        while(a % 2 == 0) {
            ans++;
            a /= 2;
        }
        res += ans;
    }
    cout << res << endl;
}


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

int main(){
	int N,K,R;
	int bad[50] = {};
	cin >> N >> K;
	vector< vector<int> > boat;
	for(int i = 0 ; i < K ; i++){
		int M;
		cin >> M;
		vector<int> b;
		for(int j = 0 ; j < M ; j++){
			int t;
			cin >> t;
			t--;
			b.push_back(t);
		}
		boat.push_back(b);
	}
	cin >> R;
	for(int i = 0 ; i < R ; i++){
		int a,b;
		cin >> a >> b;
		a--,b--;
		for(int j = 0 ; j < K ; j++){
			for(int l = 0 ; l < boat[j].size() ; l++){
				for(int p = 0 ; p < boat[j].size() ; p++){
					if( a == boat[j][l] && b == boat[j][p] ){
						bad[a] = bad[b] = 1;
					}
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0 ; i < N ; i++)
		ans += bad[i];
	cout << ans << endl;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define mp make_pair
#define pb push_back
int main()
{
	SPEED
	int a,b;
	cin >> a >> b;
	if (a>=13)
	{
		cout << b << '\n';
	}
	else if (a>=6 && a<=12)
	{
		cout << b/2 << '\n';
	}
	else
		cout << 0;
	return 0;
}

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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n;
	cin >> n;
	VI p(n + 1);
	FOR(i, 1, n + 1) cin >> p[i];
	int ans = 0;
	
	FOR(i, 2, n)
	{

		if (p[i] < p[i + 1] && p[i] > p[i - 1]) ans++;
		if (p[i] < p[i - 1] && p[i] > p[i + 1]) ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}



Measured memory_bytes: 256
from collections import Counter

N = int(input())
A = list(map(int,input().split()))

A_cnt = list(Counter(A).items())
A_cnt.sort(key=lambda x:x[0], reverse=True)

sides = []
for i in range(len(A_cnt)):
  if A_cnt[i][1] >= 4:
    sides.extend([A_cnt[i][0]]*2)
  elif A_cnt[i][1] >= 2:
    sides.append(A_cnt[i][0])
  if len(sides) >= 2:
    break

if len(sides) < 2:
  ans = 0
else:
  ans = int(sides[0] * sides[1])
  
print(ans)

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = 10e10;
const ll MINF = -10e10;
const int INF = INT_MAX;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)
typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
//ifstream myfile("C:\\Users\\riku\\Downloads\\01.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;

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

    set<tuple<ll, int, int>> cities; // <prefecture, year, index>

    rep(i, m) {
        ll y;
        int p;
        cin >> p >> y;
        tuple<ll, int, int> city(p, y, i);
        cities.insert(city);
    }

    set<tuple<int, int, int>> city_ranks;// <index, prefecture, rank>
    int before_prefecture;
    int before_rank = 1;
    {
        auto top = *cities.begin();
        int prefecture = get<0>(top);
        int index = get<2>(top);
        tuple<int, int, int> t(index, prefecture, 1);
        city_ranks.insert(t);
        before_prefecture = prefecture;
    }

    for (auto it = ++cities.begin(); it != cities.end(); it++) {
        auto city = *it;
        int prefecture = get<0>(city);
        int index = get<2>(city);
        int rank;
        if (before_prefecture == prefecture) {
            rank = ++before_rank;
        } else {
            rank = 1;
            before_rank = 1;
            before_prefecture = prefecture;
        }
        tuple<int, int, int> t(index, prefecture, rank);
        city_ranks.insert(t);
    }

    for (auto p : city_ranks) {
        int prefecture = get<1>(p);
        int rank = get<2>(p);
        cout << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
    }

}



Measured memory_bytes: 13952
/**
 *   created: 20 August 2019  11:36:13
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) c.begin(),c.end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================

int main()
{
	optimizeIO();
	int tt=1;
	//cin>>tt;
	while(tt--){
		int n;
		cin>>n;
		vector< vi > v(n, vi(3));
		rep(i,0,n)
			cin>>v[i][0]>>v[i][1]>>v[i][2];
		vector< vi > mem(n, vi(3,0));
		rep(i,0,3)
			mem[0][i] = v[0][i];
		rep(i,1,n){
			mem[i][0] = v[i][0] + max(mem[i-1][1],mem[i-1][2]);
			mem[i][1] = v[i][1] + max(mem[i-1][0],mem[i-1][2]);
			mem[i][2] = v[i][2] + max(mem[i-1][1],mem[i-1][0]);
		}
		cout<<max(mem[n-1][0],max(mem[n-1][1], mem[n-1][2]));
	}
	return 0;
}


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

int yakusuu(long long a) {
  int count = 0;
  for (int i = 2; i <= sqrt(a); i++) {
    if (a % i == 0) {
      if (i == sqrt(a))
        count++;
      else
        count += 2;
    }
  }
  count++;
  return count;
}

int main() {
  long long n;
  cin >> n;
  long long count = 0;
  count += yakusuu(n - 1);
  if (n == 2) {
    cout << 1;
    return 0;
  }
  for (int i = 2; i <= sqrt(n); i++) {
    long long a = n;
    while (a % i == 0) {
      a /= i;
      if (a == 1) {
        count++;
        break;
      }
    }
  }
  for (int i = 2; i <= sqrt(n); i++) {
    long long a = n;

    if (a % i != 0) continue;
    while (a % i == 0) {
      a /= i;
    }
    if (a == 1) continue;
    if ((a - 1) % i == 0) count++;
  }
  cout << count + 1;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
long long pow(int a, int b){
	if(b == -1)
		return 0;
	if(b == 0)
		return 1;
	return (long long)a*pow(a, b-1);
}

int main(){
	int a, b;
	cin >> a >> b;
	int out = (long long)b * pow(100, a);
	if(b == 100)
		out+=pow(100, a);
	cout << out << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H,W;
  cin >> H >> W;
  string h_f(W+2,'#');
  cout << h_f << endl;
  for(int i=0;i<H;i++){
    string temp;
    cin >> temp;
    cout << '#' << temp << '#' << endl;
  }
  cout << h_f << endl;
  
}

Measured memory_bytes: 256
module union_find_mod
    use,intrinsic :: iso_fortran_env
    integer(int32), allocatable:: ar(:)
contains
subroutine init(n)
    allocate(ar(n), source=[(i,i=1,n)])
end subroutine

recursive function root(x) result(ret)
    integer(int32):: x,ret
    if(ar(x) == x) then
        ret = x
    else
        ar(x) = root(ar(x))
        ret = ar(x)
    end if
end function

subroutine unite(x,y)
    integer(int32):: x,y
    x = root(x)
    y = root(y)
    if (x==y) return
    ar(x) = ar(y)
end subroutine
end module


program main
    use,intrinsic :: iso_fortran_env
    use union_find_mod
    implicit none
    integer(int32):: n,m,i,a,b,ans
    integer(int32), allocatable:: cnt(:)


    read*, n,m
    allocate(cnt(n),source=0)
    call init(n)

    do i=1,m
        read*, a,b
        call unite(a,b)
    end do

    do i=1,n
        ar(i) = root(i)
    end do
    do i=1,n
        cnt(ar(i)) = cnt(ar(i)) + 1
    end do
    ans=0
    do i=1,n
        if (cnt(i) > 0) ans=ans+1
    end do
    print'(i0)',ans-1
end program main

Measured memory_bytes: 4072
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;

int N,M;
vector<vector<int>> G;
int res = 0;

void dfs(int i,vector<int> &used){
   if(used[i] == 1) return;

   used[i] = 1;

   rep(j,N){
      if(G[i][j] == -1) continue;
      if(used[j] == 1) continue;
      dfs(j,used);
   }
}

int main(){
   cin >> N >> M;
   G.resize(N,vector<int>(N,-1));
   rep(i,M){
      int a,b;
      cin >> a >> b;
      a--; b--;
      G[a][b] = 1;
      G[b][a] = 1;
   }
   
   rep(i,N){
      repr(j,i+1,N){
         if(G[i][j] == 1){
            G[i][j] = -1;
            G[j][i] = -1;
            vector<int> used(N,-1);
            dfs(0,used);
            bool ok = false;
            rep(k,N){
               if(used[k] == -1) ok = true;
            }
            if(ok) res++;
            G[i][j] = 1;
            G[j][i] = 1;
         }
      }
   }
   cout << res << endl;
}



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

const int MAX = 510000;
const int mod = 1000000007;

long long fac[MAX]; //i!%mod=fac[i]
long long finv[MAX]; //pow(i!,-1)%mod=finv[i]
long long inv[MAX]; //pow(i,-1)%mod=inv[i]

// テーブルを作る前処理
void cominit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
long long com(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main(int argc, char const *argv[])
{
	cominit();
	long long n,m;
	cin>>n>>m;
	long long now=m,ans=1LL;
	for (long long i = 2LL; i*i <= m; ++i)
	{
		long long cnt=0LL;
		while (now%i==0)
		{
			now/=i;
			++cnt;
		}
		if (cnt>0)
		{
			ans*=com(n+cnt-1,cnt);
			ans%=mod;
		}
	}
	if (now>1)
	{
		ans*=n;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}


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

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
get_into = [0]*N
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    get_into[b-1] += 1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        get_into[nx] -= 1
        if get_into[nx]==0:
            parents[nx] = v
            Q.append(nx)

for p in parents:
    print(p+1)

Measured memory_bytes: 88468
require 'set'

roll = lambda do |dice, p|
  dice.each_with_index.sort_by {|_, i| p[i] }.map(&:first)
end
permutations = Set.new
permutations << [0, 1, 2, 3, 4, 5]
todo = [[0, 1, 2, 3, 4, 5]]
until todo.empty?
  dice = todo.pop
  [[2, 1, 5, 0, 4, 3], [4, 0, 2, 3, 5, 1]].each do |p|
    d = roll[dice, p]
    unless permutations.member? d
      permutations << d
      todo << d
    end
  end
end
dices = gets.to_i.times.map { gets.split.map(&:to_i) }
puts(dices.group_by {|d| d.sort }.each_value.all? {|ds| (0...ds.size-1).all? {|i| (i+1...ds.size).all? {|j| permutations.all? {|p| roll[ds[i], p] != ds[j] } } } } ? 'Yes' : 'No')

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

int n, m, a, total = 0;

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++){
	    cin >> a;
	    total += a;
	}
	
	cout << (n - total >= 0 ? n - total : -1);
	
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int N;
    cin >> N;
    int W[100], S[100], sum;
    cin >> W[0];
    S[0] = W[0];
    for(int i=1;i<N;i++){
        cin >> W[i];
        S[i] = S[i-1] + W[i];
    }
    sum = S[N-1];

    int ans = INT_MAX;
    for(int i=1;i<N;i++){
        if( abs(S[i] - (sum - S[i]) ) < ans )
            ans = abs(S[i] - (sum - S[i]) );
    }
    
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <random>
#include <chrono>
using namespace std;

int S;
long long power[18];
const int mod = 1e9 + 7;

int qpow(int a, int n){
    int ret = 1;
    while(n > 0){
        if(n & 1)
            ret = 1LL * ret * a % mod;
        a = 1LL * a * a % mod;
        n >>= 1;
    }
    return ret;
}

void add(int &a, int b){
    a += b;
    if(a >= mod)
        a -= mod;
}

const int maxn = 3e7 + 5;
int digit[maxn];

int main(){
    cin >> S;
    power[0] = 1;
    for(int i = 1;i < 18;i++){
        power[i] = power[i - 1] * 10;
    }
    int i;
    int ans = 0;
    for(i = 1; S / i >= 8;i++){
        if(S % i == 0){
            int digit = S / i;
            int p = qpow(10, digit - 1);
            p = 1LL * p * 9 % mod;
            p = (p + 1 - i + mod) % mod;
            add(ans, p);
        }else{
            add(ans, 1);
        }
    }
    digit[0] = 0;
    int ans1 = 0;
    for(int i = 0;i <= 3e6;i++){
        int tmp = digit[i];
        for(int j = 0;j < 10;j++){
            digit[i * 10 + j] = tmp + 1;
        }
    }
    digit[0] = 0;
    for(int i = 1;i < maxn;i++){
        digit[i] = digit[i - 1] + digit[i];
    }
    int l = 0;
    for(int r = 1;r < maxn;r++){
        while(digit[r] - digit[l] > S){
            l++;
        }
        if(digit[r] - digit[l] == S and (r - l) >= i){
            ans1++;
        }
    }
    add(ans, ans1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 117504
import java.util.*;

class Main {


    public static void main (String [] args) {

        Scanner sc = new Scanner(System.in);
        boolean first = true;

        while (sc.hasNext()) {
            String word = sc.next();
            if (word.charAt(word.length() - 1) == ',' || word.charAt(word.length() - 1) == '.') {
                word = word.substring(0, word.length() - 1);
            }
            if (3 <= word.length() && word.length() <= 6) {
                if (first) {
                    System.out.print(word);
                    first = false;
                } else {
                    System.out.print(" " + word);
                }
            }
        }
        System.out.println("");
    }
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back

using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

const int inf=1000000007;
void chmax(int& a,int b){
	if(a<b)
		a=b;
}
void chmin(int& a,int b){
	if(a>b)
		a=b;
}
int c[34][34],d[34];
vi g[34];
int dp[1001][34][34][16];

int main(){
	int n=read(),m=read(),r=read();
	REP(i,n)
		d[i]=read();
	REP(i,n)REP(j,n)c[i][j]=1145;
	REP(i,m){
		int a=read()-1,b=read()-1,_c=read();
		c[a][b]=c[b][a]=_c;
	}
	REP(k,n)REP(i,n)REP(j,n)
		chmin(c[i][j],c[i][k]+c[k][j]);
	REP(t,r+1)REP(i,n)REP(j,n)REP(k,16)
		dp[t][i][j][k]=-inf;
	dp[0][0][0][0]=0;
	REP(t,r){
		REP(i,n)REP(j,n)REP(k,16){
			REP(to,n){
				if(to==i){
					if(t+15<=r)
						chmax(dp[t+15][to][i][15],dp[t][i][j][k]+d[to]);
				}else if(to==j){
					int s=max(0,15-k-c[i][j]);
					if(t+s+c[i][j]<=r)
						chmax(dp[t+s+c[i][j]][to][i][min(15,s+c[i][j])],dp[t][i][j][k]+d[to]);
				}else if(t+c[i][to]<=r)
					chmax(dp[t+c[i][to]][to][i][min(15,c[i][to])],dp[t][i][j][k]+d[to]);
			}
		}
	}
	int ans=0;
	REP(t,r+1)REP(i,n)REP(j,16)
		ans=max(ans,dp[t][n-1][i][j]);
	cout<<ans<<endl;
}

Measured memory_bytes: 70732
#include <iostream>

using namespace std;

int main()
{
    int n,w,q,r;
    cin >> n;
    if(n<=999 && n>=100){
    q=n%10;
    w=(n/10)%10;
    r=n/100;
    if(q==r)
    {
        cout << "Yes";
    }
    else
            cout << "No";
    }
        return 0;
}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

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

  int64 n;
  while (cin >> n && n) {
    int64 res = 0;
    for (int64 j = 1; j < (n+1)/2; j++) {
      int64 sum = 0;
      for (int64 i = j; sum+i <= n; i++) {
        sum += i;
      }
      if (sum == n) res++;
    }
    cout << res << endl;
  }
}



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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(false);\
				cin.tie(0);\
				cout.tie(0)
#define REP(_i, _a) for(int _i = 0; _i < (int)_a; ++_i)
#define FOR(_i, _a, _b) for(int _i = (int)_a; _i <= (int)_b; ++_i)
#define FORD(_i, _a, _b) for(int _i = (int)_a; _i >= (int)_b; --_i)
#define RESET(_a, _value) fill_n(_a,sizeof(_a)/sizeof(_a[0]),_v)
#define ALL(_a) _a.begin(), _a.end()
#define SIZE(_a) _a.size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define newline '\n';

// DEBUG UTIL
#define DEBUG(args...) { cerr << "> "; \
						 string _s = #args; \
						 replace(_s.begin(), _s.end(), ',', ' '); \
						 stringstream _ss(_s); istream_iterator<string> _it(_ss); \
						 err(_it, args); }

void err(istream_iterator<string> it) { cerr << endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << ": " << a << " ";
	err(++it, args...);
}

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const double PI = acos(-1.0);
const int MOD = 1e9 + 7;
const int INF = 2e9;

int n;
vi arr;

void read() {
	cin >> n;
	arr.resize(n);
	REP(i, n) {
		cin >> arr[i];
	}
	sort(ALL(arr));
}

void solve() {
	int minimum = 2e9;
	int minimumValue = 0;
	REP(i, n-1) {
		int cur = max(arr[n-1] - arr[i], arr[i]);
		if (cur < minimum) {
			minimum = cur;
			minimumValue = arr[i];
		}
	}
	cout << arr[n-1] << " " << minimumValue << endl;
}

int main() {
	FAST_IO;
	
	int TC = 1;
	// cin >> TC;
	FOR(tc, 1, TC) {
		read();
		solve();
	}

	return 0;
}


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

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;
ll INF=100000000000001;
vector<ll> value; // ノードの値を持つ配列
ll N;             // 葉の数
 
void update(ll i, ll x) {
    // i 番目の葉の値を x に変える
    i += N - 1; // i 番目の葉のノード番号
    value[i] = x;
    while (i > 0) {
        i = (i - 1) / 2; // ノード i の親ノードの番号に変える
        value[i] = min(value[i * 2 + 1],
                       value[i * 2 + 2]); // 左右の子の min を計算しなおす
    }
}
 
ll query(ll a, ll b, ll k, ll l, ll r) {
    // [a, b) の区間に対するクエリについて
    // ノード k （区間 [l, r) 担当）が答える
    if (r <= a || b <= l) return INF; // 区間が被らない場合は INF を返す
    if (a <= l && r <= b)
        return value[k]; // ノード k の担当範囲がクエリ区間 [a, b)
                         // に完全に含まれる
    else {
        ll c1 = query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子に値を聞く
        ll c2 = query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子に値を聞く
        return min(c1, c2); // 左右の子の値の min を取る
    }
}
signed main(){
    llin(n);
    llin(k);
    vllin(h,n);
    rSORT(h);
    ll p=0;
    FOR(i,k,n-1){
        p+=h[i];
    }
    sal(p)
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main()
{
	int A[100][100], i, j, amount, k;
	int sum[100];
	cin>>amount;
	for(i=1; i<=2; i++)
	{
		for(j=1; j<=amount; j++)
		{
			cin>>A[i][j];
		}
	}
	int l;
	k=1;
	for(l=1; l<=amount; l++)
	{
		sum[k]=0;
		for(i=1; i<=l; i++)
		{
			sum[k]=sum[k]+A[1][i];
		}
		for(j=l; j<=amount; j++)
		{
			sum[k]=sum[k]+A[2][j];
		}
		k++;
	}
	int max=sum[1];
	for(i=2; i<=amount; i++)
	{
		if(sum[i]>max)
		{
			max=sum[i];
		}
	}
	cout<<max;
	
	
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll h, n;
  cin >> h >> n;
  VLL a(n), b(n);
  rep(i, n) { cin >> a[i] >> b[i]; }
  ll dp[n+1][h + 1];
  rep(i, n+1) rep(j, h + 1) dp[i][j] = 1e10;
  dp[0][0] = 0;
  
  rep(i,n){
    rep(j,h + 1){
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
      if(dp[i+1][j] <= 1e10)dp[i + 1][min(j + a[i], h)] =  min(dp[i + 1][min(j + a[i], h)], b[i] + dp[i+1][j]);
    }
  }
  // rep(i,n+1){
  //   rep(j, h + 1) { cout << dp[i][j] << " "; }
  //   cout << endl;
  // }
  cout << dp[n][h] << endl;
  return 0;
}


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

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

using namespace std;

int main(){
	int n; scanf("%d",&n);

	multiset<int> S;
	rep(i,n){
		int a; scanf("%d",&a);
		auto it=S.lower_bound(a);
		if(it!=S.begin()) S.erase(--it);
		S.emplace(a);
	}

	printf("%d\n",S.size());

	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600

int main(){
  int n,m;
  cin>>n>>m;
  vector<int> vec(n);
  rep(i,n) cin>>vec[i];

  int ans = 0;
  int i = 0;
  do {
    int mn=INF,mx=-INF;
    rep(j,m){
      int idx = (i+j)%n;
      mn = min(mn, vec[idx]);
      mx = max(mx, vec[idx]);
    }
    i += m;
    ans += mx-mn;
  } while(i%n!=0);

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007ll;
void ad(long long &a,long long b){a+=b;a%=mod;}
void mn(long long &a,long long b){a+=mod-b;a%=mod;}
void ml(long long &a,long long b){a*=b;a%=mod;}
long long sq(long long a){return a*a%mod;}
long long pw(long long a,long long n)
{
  return n==0?1ll:sq(pw(a,n/2))*(n%2==1?a:1ll)%mod;
}
long long inv(long long a){return pw(a,mod-2);}

const int MN=100000;



int main()
{
  int n;
  scanf("%d",&n);
  long long A,B;
  scanf("%lld%lld",&A,&B);
  static long long S[MN];
  for(int i=0;i<n;i++){
    scanf("%lld",S+i);
  }
  if(A<B){
    swap(A,B);
  }
  bool F=0;
  for(int i=0;i+2<n;i++){
    if(S[i+2]-S[i]<B){
      F=1;
    }
  }
  if(F){
    printf("%d\n",0);
    return 0;
  }
  static int SB[MN];
  SB[0]=0;
  for(int i=0;i+1<n;i++){
    SB[i+1]=SB[i]+(S[i+1]-S[i]>=B?1:0);
  }
  static long long dp[2][MN]={0};
  dp[0][0]=dp[1][0]=1ll;
  for(int i=0;i+1<n;i++){
    if(S[i+1]-S[i]>=B){
      ad(dp[0][i+1],dp[0][i]);
    }
    ad(dp[1][i+1],dp[0][i]);
    int k=lower_bound(S,S+n,S[i]+A)-S;
    //printf("%lld %lld %d\n",dp[0][i],dp[1][i],k);
    if(k<n&&(k-i<=2||SB[k-1]-SB[i+1]==k-i-2)){
      ad(dp[1][k],dp[1][i]);
    }
    if(k<n&&(k-i<=1||SB[k]-SB[i+1]==k-i-1)){
      ad(dp[0][k],dp[1][i]);
    }
    if(k==n&&(n-i<=2||SB[n-1]-SB[i+1]==n-i-2)){
      ad(dp[0][n-1],dp[1][i]);
    }
  }
  printf("%lld\n",(dp[0][n-1]+dp[1][n-1])%mod);
  return 0;
}

      


Measured memory_bytes: 3072
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		int count[] = new int[11];
		while(N != 0 || M != 0){
			for(int i = 0;i <= 10;i++) count[i] = 0;
			int countP = 0;
			for(int i = 0;i < N;i++){
				int D = in.nextInt();
				int P = in.nextInt();
				count[P] = count[P] + D;
			}
			for(int i = 0;i < M;i++){
				int n = 0;
				for(int j = 10;j > 0;j--){
					n = j;
					if(count[j] > 0) break;
				}
				if(count[n] > 0){
					if(i + count[n] < M){
						i = i + count[n] - 1;
						count[n] = 0;
					}else {
						count[n] = count[n] - (M-i);
						i = M;
					}
				}
				else break;
			}
			for(int i = 1;i < 11;i++) {
				if(count[i] > 0){
					countP = countP + i*count[i];
				}
			}
			System.out.println(countP);
			N = in.nextInt();
			M = in.nextInt();
		}
	}
}

Measured memory_bytes: 66260
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

vector<vector<int>> calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(26, -1));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'a'] = i;
    }
    return res;
}

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    s += s;
    s += s;
    auto p = calcNext(s);
    ll ans = 0, cur = -1;
    for (auto &&i : t) {
        int curr = p[cur+1][i-'a'];
        if(curr == -1){
            puts("-1");
            return 0;
        }
        ans += curr-cur;
        cur = (curr)%n;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 53948
#include<stdio.h>
#define N 100

int main(){
  int i, j, k, n, Adj[N][N+1], m[N][N], a, b, c;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      m[i][j] = 0;
    }
  }
  for(k=0;k<n;k++){
    scanf("%d%d",&a,&b);
    for(i=0;i<b;i++){
      scanf("%d",&c);
      m[a-1][c-1] = 1;
    }
  }

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j) printf(" ");
      printf("%d",m[i][j]);
    }
    printf("\n");
  }
  return 0;
}







Measured memory_bytes: 2112
def solve(N):
    if N == 0: return '0'
    s = []
    b = 1
    while N != 0:
        s.append('0' if N % 2 == 0 else '1')
        if N % 2 != 0:
            N -= b
        N //= 2
        b = -b
    s.reverse()
    return ''.join(s)

N = int(input())
print(solve(N))

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

double calcuate(int y,int t,int r) {
	if(t==1) {
		return 1.0*(1.0+y*(double)r/100);
	} else {
		return 1.0*pow(1.0+(double)r/100,y);
	}
}

int main(void) {
	int n,y,b,r,t;
	int i;
	double max,now;
	int maxno;
	while(1) {
		scanf("%d",&n);
		if(n==0)break;
		scanf("%d",&y);
		max=maxno=0;
		for(i=0;i<n;i++) {
			scanf("%d%d%d",&b,&r,&t);
			now=calcuate(y,t,r);
			if(now>max){max=now;maxno=b;}
		}
		printf("%d\n",maxno);
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
int main(){
    int x;
    scanf("%d",&x);
    if(x>=30){
        printf("Yes");
        return 0;
    }
    printf("No");
    return 0;
}

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

bool vis[305];
int a[305][305], n, m, p[305], ct[305];

bool check(int x) {
    memset(vis, 0, sizeof(vis));
    memset(p, 0, sizeof(p));

    while (true) {
        memset(ct, 0, sizeof(ct));
        for (int i = 0; i < n; ++i)
            ct[a[i][p[i]]]++;
        bool z = 1;
        for (int i = 0; i < m; ++i)
            if (ct[i] > x) {
                vis[i] = 1;
                z = 0;
            }

        if (z == 1)
            return 1;

        for (int i = 0; i < n; ++i) {
            while (vis[a[i][p[i]]] == 1) {
                p[i]++;
                if (p[i] == m)
                    return 0;
            }
        }
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            a[i][j]--;
        }

    for (int i = 1; i <= 300; ++i) {
        if (check(i)) {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 640
import sys
sys.setrecursionlimit(10**6)

n, u, v = map(int, input().split())
# よりたかはしくんが早く辿り着ける葉のうち、青木君から最も遠いで
u -= 1
v -= 1

g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    g[a].append(b)
    g[b].append(a)

INF = 1 << 30
t = [INF] * n
a = [INF] * n

t[u] = 0
a[v] = 0


def dfs(v, p, d):
    for nv in g[v]:
        if nv == p:
            continue
        if d[nv] == INF:
            d[nv] = d[v] + 1
            dfs(nv, v, d)


dfs(u, -1, t)
dfs(v, -1, a)

ans = 0
for i in range(n):
    if t[i] < a[i]:
        ans = max(ans, a[i] - 1)
print(ans)


Measured memory_bytes: 106404
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

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

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int w = scanner.nextInt();
			int h = scanner.nextInt();
			if ((w | h) == 0)
				break;
			list = new ArrayList<List<Pair>>();
			for (int i = 0; i < 6; i++) {
				list.add(new ArrayList<Pair>());
			}
			boolean[] b = new boolean[6];
			for (int i = 0; i < h; i++) {
				char[] cs = scanner.next().toCharArray();
				for (int j = 0; j < w; j++) {
					if (cs[j] == 'S') {
						sy = i;
						sx = j;
					} else if (cs[j] == 'G') {
						gy = i;
						gx = j;
					} else if (cs[j] != '.') {
						int c = Character.getNumericValue(cs[j]);
						list.get(c).add(new Pair(i, j));
						b[c] = true;
					}
				}
			}
			int sum = 0;
			for (int i = 1; i < 6; i++) {
				if (b[i])
					sum++;
			}
			min = Integer.MAX_VALUE;
			int index = -1;
			if (sum == 4) {
				for (int i = 1; i < 6; i++) {
					if (!b[i]) {
						min = slove(i, i == 1 ? 5 : i - 1);
						index = i;
					}
				}
			} else if (sum == 5) {
				for (int i = 1; i < 6; i++) {
					int cos = slove(i, i == 1 ? 5 : i - 1);
					if (min > cos) {
						min = cos;
						index = i;
					}
				}
			}
			System.out.println(index == -1 ? "NA" : index + " " + min);

		}

	}

	private int slove(int k, int g) {
		PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
		int s = k == 5 ? 1 : k + 1;
		for (int i = 0; i < list.get(s).size(); i++) {
			int y = list.get(s).get(i).y;
			int x = list.get(s).get(i).x;
			int dis = Math.abs(y - sy) + Math.abs(x - sx);
			int gdis = Math.abs(y - gy) + Math.abs(x - gx);
			pq.add(new Pair(y, x, dis, k + 1, dis + gdis));
		}
		while (!pq.isEmpty()) {
			Pair pair = pq.poll();
			int y = pair.y;
			int x = pair.x;
			int cost = pair.cost;
			int id = pair.id;
			int tmpid = id > 5 ? id - 5 : id;
			if (min <= pair.md)
				return Integer.MAX_VALUE;
			if (id == 10) {
				return cost;
			}
			if (tmpid != g) {
				for (Pair i : list.get(tmpid == 5 ? 1 : tmpid + 1)) {
					int dis = Math.abs(y - i.y) + Math.abs(x - i.x);
					int gdis = Math.abs(i.y - gy) + Math.abs(i.x - gx);
					pq.add(new Pair(i.y, i.x, cost + dis, id + 1, cost + dis
							+ gdis));
				}
			} else {
				int dis = Math.abs(y - gy) + Math.abs(x - gx);
				pq.add(new Pair(0, 0, cost + dis, 10, cost));
			}
		}
		return Integer.MAX_VALUE;
	}

	List<List<Pair>> list;
	int sy;
	int gy;
	int sx;
	int gx;
	int min;

	class Pair implements Comparable<Pair> {
		int y;
		int x;
		int cost;
		int id;
		int md;

		@Override
		public int compareTo(Pair o) {
			if (this.md == o.md)
				return o.id - this.id;
			return this.md - o.md;
		}

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		public Pair(int y, int x, int cost, int id, int md) {
			super();
			this.y = y;
			this.x = x;
			this.cost = cost;
			this.md = md;
			this.id = id;
		}

	}
}

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

using namespace std;

int a[100002];

int main(){
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n; ++i) cin >> a[i];
  sort(a, a + n);
  int res = 1000000001;
  for(int i = 0; i < n - k + 1; ++i){
    res = min(res, a[k + i - 1] - a[i]);
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct t{
  ll w,s,v;
  bool operator<(const t&q)const{
      return w+s<q.w+q.s;
  }
  bool operator>(const t&q)const{
      return w+s>q.w+q.s;
  }
};
ll n,dp[1005][20005],ans;
t a[1005];
int main(void){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)scanf("%lld%lld%lld",&a[i].w,&a[i].s,&a[i].v);
    sort(a,a+n);
    for(int i=0;i<n;i++){
        for(int j=0;j<=10000;j++){
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            if(j<=a[i].s){
                dp[i+1][j+a[i].w]=max(dp[i+1][j+a[i].w],dp[i][j]+a[i].v);
                ans=max(ans,dp[i+1][j+a[i].w]);
            }
        }
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 156544