akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

//BEGIN CUT HERE
//Dinic
class Dinic{
public:
    explicit Dinic(int v):vertex(static_cast<unsigned int>(v)){//v->MAX_VERTEX_SIZE
        G.resize(vertex+10);
        //for (auto &i : G)i.resize(vertex+10);
    }
    void add_edge(int from,int to,int cap){
        G[from].push_back((edge){to, cap, static_cast<int>(G[to].size())});
        G[to].push_back((edge){from, 0, static_cast<int>(G[from].size() - 1)});
    }
    ll max_flow(int s,int t){//s->start , t->end
        ll flow=0;
        for(;;){
            bfs(s);
            if(level[t]<0)return flow;
            iter.clear();
            iter.resize(vertex+10,0);
            ll f;
            while((f=dfs(s,t,INF))>0)flow+=f;
        }
    }
private:
    unsigned int vertex;
    struct edge{
        int to;
        ll cap;
        int rev;
    };
    vector<vector<edge> > G;
    vector<int> level;
    vector<int> iter;
    ll INF=(ll)1e16;
    void bfs(int start){
        level.clear();
        level.resize(vertex+10,-1);
        queue<int> q;
        q.push(start);
        level[start]=0;
        while(!q.empty()){
            int now=q.front();
            q.pop();
            for(int i=0;i<(int)G[now].size();i++) {
                if(G[now][i].cap>0 && level[G[now][i].to]<0){
                    level[G[now][i].to]=level[now]+1;
                    q.push(G[now][i].to);
                }
            }
        }
    }
    ll dfs(int now,int t,ll f){
        if(now==t)return f;
        for(int &i=iter[now];i<(int)G[now].size();i++){
            edge &e=G[now][i];
            if(e.cap>0 && level[now]<level[e.to]){
                ll d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }
};
//END CUT HERE

//ARC092-B 2D Plane 2N Points
/*int main(){
    int n;cin>>n;
    Dinic f(2*n);
    int s=2*n;
    int t=s+1;
    vector<pair<int,int> > aka,ao;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        aka.push_back({a,b});
        f.add_edge(s,i,1);
    }
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        ao.push_back({a,b});
        f.add_edge(n+i,t,1);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(aka[j].first<ao[i].first && aka[j].second<ao[i].second){
                f.add_edge(j,n+i,1);
            }
        }
    }
    cout<<f.max_flow(s,t)<<endl;
}*/

int main(){
    int v,e;cin>>v>>e;
    Dinic f(v);
    for(int i=0;i<e;i++){
        int from,to,cap;cin>>from>>to>>cap;
        f.add_edge(from,to,cap);
    }
    cout<<f.max_flow(0,v-1)<<endl;
}


Measured memory_bytes: 3232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
ll n,md=1000000007;
char choice[5];
vector <str> query;
bool calc[200][5000];
ll memo[200][5000];
ll conv(str y){
    ll a,b,c;
    a=0;
    b=0;
    c=0;
    for(int i=1;i<=4;i++){
        if(y[0]==choice[i]){a=i;break;}
    }
    for(int i=1;i<=4;i++){
        if(y[1]==choice[i]){b=i;break;}
    }
    for(int i=1;i<=4;i++){
        if(y[2]==choice[i]){c=i;break;}
    }
    return 16*(a-1) + 4*(b-1) + c;
}
ll dp (ll x, str z){
    ll num = conv(z);
    if(x==n){return 1;}
    else if(calc[x][num]){return memo[x][num];}
    else{
        bool notc,notg;
        notc=false;notg=false;
        if(z[1]=='A' && z[2]=='G'){notc=true;}
        if(z[1]=='A' && z[2]=='C'){notg=true;}
        if(z[1]=='G' && z[2]=='A'){notc=true;}
        if(z[0]=='A' && z[2]=='G'){notc=true;}
        if(z[0]=='A' && z[1]=='G'){notc=true;}

        str t="";
        t+=z[1];
        t+=z[2];
        ll ans = 0;
        for(int i=1;i<=4;i++){
            str temp = t;
            if(notc && i==2)continue;
            if(notg && i==3)continue;

            temp += choice[i];
            ans = ( (ans%md) + (dp(x+1,temp)%md) ) % md ;
        }
        memo[x][num]=ans;
        calc[x][num]=true;
        return ans;
    }
}
int main(){
    cin>>n;
    choice[1]='A';
    choice[2]='C';
    choice[3]='G';
    choice[4]='T';
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                str temp = "";
                temp+=choice[i];
                temp+=choice[j];
                temp+=choice[k];
                if(temp=="AGC" || temp=="ACG" || temp=="GAC")continue;
                query.push_back(temp);
            }
        }
    }

    ll tot = 0;
    for(int i=0;i<query.size();i++){
        tot = ((tot % md) + (dp(3,query[i]) % md) )%md ;
    }
    cout<<tot<<endl;
}


Measured memory_bytes: 4736
import java.lang.Math

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    var min = 0
    var max = n
    for (x in (0 until m)) {
        val (l, r) = readLine()!!.split(" ").map { it.toInt() }
        min = Math.max(l, min)
        max = Math.min(r, max)
    }

    if (max >= min) {
        println(1 + max - min)
    } else {
        println(0)
    }

}



Measured memory_bytes: 55724
#include <cstdio>
#include <iostream>

int main()
{
	int n,max=0,sum=0;
	scanf("%d",&n);
	int a[2][n];
	for(int i=0;i<2;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&a[i][j]);
		for(int j=0;j<n;j++)
			sum+=a[1][j];
			sum+=a[0][0];
			max=sum;
	for(int i=1;i<n;i++)
	{
		sum=sum-a[1][i-1]+a[0][i];
		
		if(sum>max)
			max=sum;
	}
	printf("%d",max);
}

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

using namespace std;

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

    vector<int> x(N), y(N), w(N);
    map<pair<int, int>, int> W;
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i] >> w[i];
        W[make_pair(x[i], y[i])] = w[i];
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        int sum = 0;
        for (int dx = 0; dx <= 1; ++dx) {
            for (int dy = 0; dy <= 1; ++dy) {
                auto p = make_pair(x[i] + dx, y[i] + dy);
                if (W.count(p)) sum += W[p];
            }
        }
        ans = max(ans, sum);

        sum = 0;
        for (int dx = -1; dx <= 0; ++dx) {
            for (int dy = 0; dy <= 1; ++dy) {
                auto p = make_pair(x[i] + dx, y[i] + dy);
                if (W.count(p)) sum += W[p];
            }
        }
        ans = max(ans, sum);
    }

    cout << ans << " / 1" << endl;
    return 0;
}



Measured memory_bytes: 10228
y1_list = list(map(int,input().split()))
y2_list = list(map(int,input().split()))
y3_list = list(map(int,input().split()))
L = [y1_list,y2_list,y3_list]
 
a1 = list()
a2 = list()
b1 = list()
b2 = list()
 
for i in range(3):
    a1.append(y1_list[i] - y2_list[i])
    a2.append(y2_list[i] - y3_list[i])

 
 
if (a1[0] == a1[1] and a1[2] == a1[0]):
    if (a2[0] == a2[1] and a2[2] == a2[0]):
        print("Yes")
        
    else:
        print("No")
else:
    print("No")

Measured memory_bytes: 9224
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

const long long inf = 1e10;
const long long mod = 1e9+7;

typedef vector<vector<int> > G;
G graph;

int color[100050];

bool dfs(int u, int c){
    color[u] = c;
    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if(color[v] == c){
            return false;
        }
        if(color[v] == 0 && !dfs(v, -c) ){
            return false;
        }
    }   
    return true;
}

int main(void){
    long long n, m;
    cin >> n >> m;
    graph = G(n);
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    long long B=0, W=0;
    if(dfs(0, 1)){
        for(int i=0; i<n; i++){
            if(color[i] == 1){
                B++;
            }else if(color[i] == -1){
                W++;
            }
        }
        cout << B*W - m << endl;
    }else{
        cout << ( (n*(n-1)) /2) - m << endl;
    }
    
    return 0;
}

Measured memory_bytes: 6528
n = int(input())
s = list()

for a in range(n):
    s.append(input())

t = list()
m = int(input())

for a in range(m):
    t.append(input())

kind = list(set(s))
kind_length = len(kind)

counter = dict()
for a in range(kind_length):
    counter[kind[a]] = 0

for a in range(n):
    counter[s[a]] += 1

for a in range(m):
    if t[a] not in counter:
        continue
    counter[t[a]] -= 1

print(max(max(counter.values()), 0))


Measured memory_bytes: 9112
import sys
input = sys.stdin.readline
 
N = int(input())
AC = 0
WA = 0
TLE = 0
RE = 0
 
for _ in range(N):
  str1 = input()
  if str1[0] == 'A':
    AC += 1
  elif str1[0] == 'W':
    WA += 1
  elif str1[0] == 'T':
    TLE += 1
  elif str1[0] == 'R':
    RE += 1
print('AC x ' + str(AC))
print('WA x ' + str(WA))
print('TLE x ' + str(TLE))
print('RE x ' + str(RE))

Measured memory_bytes: 67884
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(a+b==c){
		cout<<"Yes";
	}else if(a+c==b){
		cout<<"Yes";
	}else if(b+c==a){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
	return 0;
}

Measured memory_bytes: 256
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
sys.setrecursionlimit(int(1e+7))  # スタック上限

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    XY = ii2nnn(N)
    M = int(1e+5) + 5

    # 二部グラフ
    to = [[] for _ in range(M*2)]
    cnt = [0] * (M*2)
    visited = [False] * (M*2)

    # 二部グラフを構築
    for x, y in XY:
        y += M
        to[x].append(y)
        to[y].append(x)

    cnt = [0, 0]
    def bfs(n):
        q = deque()
        q.append(n)
        while q:
            i = q.popleft()
            if visited[i]:
                continue
            visited[i] = True
            cnt[i // M] += 1
            for j in to[i]:
                q.append(j)

    # 二部グラフを走査
    ans = 0
    for i in range(M*2):
        if visited[i]:
            continue
        cnt[0] = 0
        cnt[1] = 0
        bfs(i)
        ans += cnt[0] * cnt[1]
    
    ans -= N  # 既にある点は操作数に含まれない
    print(ans)

main()


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

int main()
{
	bool ff = true;
	string s, p;
	cin >> s >> p;
	int ls = s.size(), lp = p.size();
	for (int i = 0; i < ls; i++) {
		bool flag = true;
		for (int j = 0; j < lp; j++) {
			if (s[(i + j) % ls] != p[j]) {
				flag = false;
				break;
			}
		}
		if (flag) {
			ff = false;
			cout << "Yes" << endl;
			break;
		}
	}
	if (ff) {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3192
N = int(input())
ans = 0
both = 0
start_B = 0
end_A = 0
for _ in range(N):
    s = input()
    ans += s.count("AB")
    isB = s.startswith("B")
    isA = s.endswith("A")
    if isA and isB:
        both += 1
    if isA:
        end_A += 1
    if isB:
        start_B += 1
ans += min(start_B, end_A)
if start_B == both and both == end_A and start_B != 0:
    ans = max(0, ans - 1)
print(ans)

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

int main()
{
  int t;
  cin >> t;
  string s;
  map<string, int> mp;
  while(t--)
  {
    cin >> s;
    mp[s]++;
  }
  cout << "AC x " << mp["AC"] << "\n";
  cout << "WA x " << mp["WA"] << "\n";
  cout << "TLE x " << mp["TLE"] << "\n";
  cout << "RE x " << mp["RE"] << "\n";
}

Measured memory_bytes: 3632
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
//#include "MyMath.h"
//#include "MyDisjointset.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
typedef pair<int, int> P; typedef long long int ll; typedef vector <int> vecint; typedef vector <vecint> dvecint; typedef vector <dvecint> vecdvecint; typedef vector <vector <dvecint> > dvecdvecint;
const int INF = 100000000;
int match[200], used[200];
vector <int> G[200];
bool dfs(int v) {
	used[v] = 1;
	for (int i = 0; i < G[v].size(); i++) {
		int u = G[v][i]; int w = match[u];
		if (w < 0 ||!used[w] && dfs(w) ){
			match[u] = v;
			match[v] = u;
			return true;
		}
	}
	return false;
}
int main() {
	int nx, ny, ne; cin >> nx >> ny >> ne;
	for (int i = 0; i < ne; i++) {
		int x, y; cin >> x >> y;
		G[x].push_back(y + nx);
		G[y + nx].push_back(x);
	}
	int v = nx + ny;
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int i = 0; i < v; i++) {
		if (match[i] < 0) {
			memset(used, 0, sizeof(used));
			if (dfs(i))
				res++;
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3284
#include <iostream>
#include <string>
#include <map>
#include <math.h>
using namespace std;

#define ll long long

int main(){
    int R,G,B,N,count = 0;
    cin >> R >> G >> B >> N;
    for(int i = 0;i <= N/R;i++){
        for(int j = 0;j <= (N - i*R)/G;j++){
            if((N - i*R - j*G)%B == 0)count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(int i=(ll)(b);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll h,w;cin>>h>>w;
  vector<vector<ll>>a(h,vector<ll>(w));
  auto b=a;
  rep(i,h)rep(j,w)cin>>a[i][j];
  rep(i,h)rep(j,w)cin>>b[i][j];
  const ll geta=80*160,sz=geta*2+7;
  vector<bitset<sz>>dp(w);
  auto tdp=dp;
  auto isin=[&](ll y,ll x){
    if(y>=0&&y<h&&x>=0&&x<w)return 1;
    return 0;
  };
  ll d=a[0][0]-b[0][0];
  tdp[0][geta-d]=1;
  tdp[0][geta+d]=1;
  rep(i,h){
    if(i!=0)rep(j,w)tdp[j]=0;
    rep(j,w){
      d=abs(a[i][j]-b[i][j]);
      if(isin(i-1,j)){
        tdp[j]|=dp[j]<<d;
        tdp[j]|=dp[j]>>d;
      }
      if(isin(i,j-1)){
        tdp[j]|=tdp[j-1]<<d;
        tdp[j]|=tdp[j-1]>>d;
      }
    }
    swap(dp,tdp);

  }
  ll res=1e9;
  rep(i,sz){
    if(dp[w-1][i])chmin(res,abs(i-geta));
  }
  cout<<res<<endl;


  return 0;

}


Measured memory_bytes: 896
N = int(input())

W = []
for i in range(N):
    W.append(str(input()))

for i in range(N):
    if i != 0:
        tmp = list(W[i-1])
        last_end = tmp[-1]

        tmp = list(W[i])
        current_start = tmp[0]
        if (last_end != current_start) or (len(W) != len(list(set(W)))):
            print('No')
            exit()
print('Yes')


Measured memory_bytes: 3060
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  int n;cin>>n;
  vector<int> a(n);
  int ma=-1;
  rep(i, n){
    cin>>a[i];
    ma = max(ma, a[i]);
  }
  int dif=-1, b;
  rep(i, n){
    if(a[i]==ma)continue;
    if(dif<min(ma-a[i], a[i])){
      dif=min(ma-a[i], a[i]);
      b = a[i];
    }
  }
  cout<<ma<<" "<<b<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;

typedef pair <int, int> pii;
const int N = 3e3 + 5;
const long long INF = 1e18;
const int mod = 998244353;//786433;//998244353;
const double Pi = acos(-1);

 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int n;
int a[200005];
map <int, int> M;

int main()
{
	int t = 0;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		M[a[i]]++;
	}
	sort(a + 1, a + n + 1);
	for(int i = n; i >= 1; i--)
	{
		if(M[a[i]] == 0)
		{
			continue;
		}
		int temp = log2(a[i]);
		temp = 1 << (temp + 1);
		M[a[i]]--;
		if(M[temp - a[i]] > 0)
		{
			t++;
			M[temp - a[i]]--;
		}
	}
	cout << t;
}

Measured memory_bytes: 19712
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
#define double long double
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-6;
const int MOD=1000000007;

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

signed main(){
	int n,m,yoko[2010][2010] = {},tate[2010][2010] = {},ans = 0;
	string field[2010];
	cin >> n >> m;
	for(int i = 0;i < n;i++) cin >> field[i];
	for(int i = 0;i < n;i++){
		int cnt = 0;
		for(int j = 0;j <= m;j++){
			if(j == m || field[i][j] == '#'){
				for(int k = j - cnt;k < j;k++) yoko[i][k] = cnt;
				cnt = 0;
			}
			else if(field[i][j] == '.') cnt++;
		}
	}
	for(int i = 0;i < m;i++){
		int cnt = 0;
		for(int j = 0;j <= n;j++){
			if(j == n || field[j][i] == '#'){
				for(int k = j - cnt;k < j;k++) tate[k][i] = cnt;
				cnt = 0;
			}
			else if(field[j][i] == '.') cnt++;
		}
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++) chmax(ans,yoko[i][j] + tate[i][j]);
	}
	cout << ans - 1 << endl;
}


Measured memory_bytes: 67456
#include<bits/stdc++.h>
#include <iostream>
#include <numeric>
#include <math.h>
#define ll  long long
#define ull unsigned long
#define mpa make_pair
#define pb push_back
#define ff first
#define pii pair<ll,ll>
#define dd double
#define trace(x) cerr << #x << " : " << x << endl
#define ss second
#define boost ios_base::sync_with_stdio(0)
#define forp(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n)    for(ll i=0;i<n;++i)
#define ren(i,n)    for(ll i=n-1;i>=0;i--)
#define forn(i,a,b) for(ll i=a;i>=b;i--)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end();
#define sc(x) scanf("%lld",&x)
#define clr(x,val) memset(x,val,sizeof(x))
#define pr(x) printf("%lld\n",x) 
#define gc getchar
#define pdd pair<dd,dd>
#define prec(x) cout<<fixed<<setprecision(x)
using namespace std;
map<ll,ll> help;
int main(){
   ll n,m,j,s=0;
   cin>>n;
   for(ll i=2;i<=n;i++){
   	ll j;
   	cin>>j;
   	help[j]++;
   }
   for(ll i=1;i<=n;i++)cout<<help[i]<<endl;
   
   
  
}


Measured memory_bytes: 16072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[200005]={0};
vector<ll> col_pos[200005];
ll col[200005]={0};
int main(){
  ll n;
  cin>>n;
  for(int i=1;i<=n;i++){
    ll a;
    cin>>a;
    col[i]=a;
    col_pos[a].push_back(i);
  }
  dp[1]=1;
  for(int i=1;i<=n;i++){
    dp[i+1]+=dp[i];
    dp[i+1]%=mod;

    ll n_col=col[i];
    ll pos=lower_bound(col_pos[n_col].begin(),col_pos[n_col].end(),i)-col_pos[n_col].begin();
    pos++;
    if(pos==col_pos[n_col].size()) continue;
    if(col_pos[n_col][pos]-i<=1) continue;
    ll npos=col_pos[n_col][pos];
    dp[npos]+=dp[i];
    dp[npos]%=mod;
  }
  cout<<dp[n]<<endl;
}


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

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

    int m,n;
    cin >> m >> n;
    int a[n],s=0;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        s+=a[i];
    }
    if (s>m)
        cout << "-1";
    else
        cout << m-s;

}

Measured memory_bytes: 3684
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
typedef pair<ll,ll> ipair;
#define F first
#define S second

int main() {
	ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    
	ll n,i,j,p,k,m,ans=0,x,y;
    cin>>n>>x>>y;
    vector<ll> a(n,0);
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            m=min(j-i, abs(x-i)+1+abs(y-j));
            a[m]++;
        }
    }
    for(i=1;i<n;i++)
    {
        cout<<a[i]<<endl;
    }
    
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
string s; 
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='9')
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n ;
  vector<int> p(n);
  for (int i = 0; i < n; i++ ){
    cin >> p.at(i) ;
  }
  vector<int> q(n-1);
  for (int i = 0; i < n - 1; i++ ){
    q.at(i) = p.at(i+1) - p.at(i);
  }
  int count = 0;
  for (int i = 0; i < n - 2; i++ ){
    if (q.at(i) * q.at(i+1) > 0) {
      count++;
    }
  }
  printf("%d\n",count);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  int a=-100;
  int b=100;
  for(int i=0;i<N;i++){
    int x;
  cin>>x;
    a=max(a,x);
  }
  for(int j=0;j<M;j++){
    int y;
  cin>>y;
    b=min(b,y);
  }
  if(a<b&&X<=a&&Y>=b){
  cout<<"No War"<<endl;
  }
  else{
  cout<<"War"<<endl;
  }
  
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	for (auto &u : v) os << u << el;
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

int main() {
	int N, R;
	cin >> N >> R;
	
	if (N >= 10) cout << R << endl;
	else cout << R + 100 * (10 - N) << endl;
	return (0);
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outv(x) cerr<<#x" = "<<x<<"  "
#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
	For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int mod=998244353;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
void ckmax(int &x,int y){
	if (x<y)
		x=y;
}
void ckmin(int &x,int y){
	if (x>y)
		x=y;
}
const int N=305;
int n,k;
char s[N];
int dp[N][N][N];
int a[N],b[N];
int c0=0,c1=0;
int main(){
	cin>>(s+1);
	n=strlen(s+1);
	k=read();
//	n=300;
//	For(i,1,n)
//		s[i]=rand()%2?'1':'0';
//	k=300;
	For(i,1,n)
		if (s[i]=='1')
			c0++;
		else
			a[++c1]=c0,b[c1]=a[c1]-a[c1-1];
	k=min(k,c0);
	dp[0][0][0]=1;
//	outval(c0),outval(c1);
//	outarr(a,0,c1);
	For(i,1,c1)
		For(j,0,c0)
			For(t,0,k){
//				outval(i);
				int v=dp[i-1][j][t];
				if (!v||j<a[i-1])
					continue;
//				printf("dp[%d][%d][%d] = %d\n",i-1,j,t,v);
				int ub=min(c0-j,k-t+b[i]);
				For(now,0,ub){
					if (now<=b[i])
						Add(dp[i][j+now][t],v);
					else
						Add(dp[i][j+now][t+now-b[i]],v);
				}
			}
	int ans=0;
	For(j,a[c1],c0)
		For(t,0,k){
//			if (dp[c1][j][t])
//				printf("dp[%d][%d][%d] = %d\n",c1,j,t,dp[c1][j][t]);
			Add(ans,dp[c1][j][t]);
		}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 17848
#include <bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define int long long

using namespace std;

const int N = 2e5 + 5;

int n, k, a[N];

bool check(double m) {
    int kol = 0;
    for (int i = 1; i <= n; i++) {
        double c = a[i] / m;
        c = floor(c);
        if (abs(c * m - a[i]) < 1e-8)
            kol += (c - 1);
        else
            kol += c;
    }
    return kol <= k;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    double l = 0, r = 1e9;
    for (int i = 0; i < 300; i++) {
        double m = (l + r) / 2;
        if (check(m))
            r = m;
        else
            l = m;
    }
    cout << fixed << setprecision(0) << ceil(r);
    return 0;
}


Measured memory_bytes: 5336
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::string s, t;
    long long q;
    std::cin >> s >> t >> q;
    std::vector<long long> vs(s.size() + 1), vt(t.size() + 1);
    for (auto i = 0ll; i < s.size(); i++) {
        vs[i + 1] = vs[i] + (s[i] == 'A' ? 2 : 1);
    }
    for (auto i = 0ll; i < t.size(); i++) {
        vt[i + 1] = vt[i] + (t[i] == 'A' ? 2 : 1);
    }
    for (;q--;) {
        long long a, b, c, d;
        std::cin >> a >> b >> c >> d;
        std::cout << (((vs[b] - vs[a - 1]) % 3 == (vt[d] - vt[c - 1]) % 3) ? "YES" : "NO") << std::endl;
    }

    return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n, ans = 0; cin >> n;
    vi a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    sort(all(a));
    sort(all(b));
    // nが偶数の場合
    if(n%2 == 0) ans = (1.0*(b[n/2-1]+b[n/2])/2.0 - 1.0*(a[n/2-1]+a[n/2])/2.0)*2.0 + 1.0;
    // nが奇数の場合
    else ans = b[(n+1)/2-1]-a[(n+1)/2-1]+1;
    cout << ans << endl;
}

Measured memory_bytes: 6368
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    par = [None] * (n + 1)
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                par[z] = (x, dat[y/3*3+2])
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        px = []
        pz = []
        x, z = f
        while x != 1:
            px.append(par[x])
            x = par[x][0]
        while z != 1:
            pz.append(par[z])
            z = par[z][0]
        while px and pz and px[-1] == pz[-1]:
            px.pop()
            pz.pop()
        px += pz[::-1]
        k = [x[1] for x in px]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = 1 - min(dp[i] for i in xrange(1, n + 1) if col[i] == 1)
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] += x
        else:
            dp[i] -= x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()


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

int main() {
  int N;
  string type = "Three";
  cin >> N;

  // ここにプログラムを追記
  for(int i=0; i<N; i++){
    char S;
    cin >> S;

    if(S == 'Y'){
      type = "Four";
      break;
    }
  }
  cout << type << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define Nmax 200010
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;

int main() {
	int N;
	int a,guu=0,ki=0;
	cin >> N;
	REP(i,N){
		cin >>a;
		if(a%2==0) guu++;
		else ki++;
	}
	if(ki%2==0) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
s = input()
flg = [0,0]

for i in range(len(s)):
	if s[i] == "C":
		if flg[0] == 0:
			flg[0] = 1
		else:
			continue

	if s[i] == "F":
		if flg[0] == 1 and flg[1] == 0:
			flg[1] = 1
		else:
			continue

if flg == [1,1]:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
vector<set<int>> G;
string C;
void far(int node, int prev, int dist, int &maxnode, int &maxdist) {
    dist += (G[node].size() % 2) ^ (C[node] == 'W');
    if (dist > maxdist) {
        maxdist = dist;
        maxnode = node;
    }
    for (int next : G[node]) if (next != prev) {
        far(next, node, dist, maxnode, maxdist);
    }
}
int main() {
    int N; cin >> N;
    G.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y; cin >> x >> y; x--, y--;
        G[x].insert(y);
        G[y].insert(x);
    }
    cin >> C;
    int cnt_w = count(begin(C), end(C), 'W');
    if (cnt_w <= 1) {
        cout << cnt_w << '\n';
    } else {
        queue<int> Q;
        for (int i = 0; i < N; i++) {
            if (G[i].size() == 1 && C[i] == 'B') {
                Q.emplace(i);
            }
        }
        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            int next = *begin(G[node]);
            G[node].erase(next);
            G[next].erase(node);
            if (G[next].size() == 1 && C[next] == 'B') {
                Q.emplace(next);
            }
        }
        int x = find(begin(C), end(C), 'W') - begin(C);
        int flip = 0;
        for (int i = 0; i < G.size(); i++) {
            flip += (!G[i].empty() && ((G[i].size() % 2) ^ (C[i] == 'W')));
        }
        int cnt_v = count_if(begin(G), end(G), [&](auto& S) { return !S.empty(); });
        int maxnode = 0, maxdist = 0;
        far(x, x, 0, maxnode, maxdist);
        maxdist = 0;
        far(maxnode, maxnode, 0, maxnode, maxdist);
        cout << (cnt_v - 1) * 2 + flip - maxdist * 2 << '\n';
    }
    return 0;
}


Measured memory_bytes: 25412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll
#define INF 1e16
#define mod 1000000007
int main(){
    ll l,r;
    cin>>l>>r;
    ll dp[61][2][2][2];
    rep(i,61)rep(j,2)rep(k,2)rep(l,2) dp[i][j][k][l]=0;
    dp[60][0][0][0]=1;
    for(int i=59;i>=0;i--){
        ll lb = l >> i&1;
        ll rb = r >> i&1;
        rep(j,2)rep(k,2)rep(s,2){
            ll pre = dp[i+1][j][k][s];
            rep(x,2)rep(y,2){
                if(x && !y) continue;
                int nj = j, nk = k, ns = s;
                if(!s && x!=y) continue;
                if(x && y) ns = 1;

                if(!j && !x && lb) continue;
                if(x && !lb) nj = 1;

                if(!k && y && !rb) continue;
                if(!y && rb) nk = 1;

                dp[i][nj][nk][ns] += pre%mod;
                dp[i][nj][nk][ns] %= mod;

            }
        }
    }

    ll ans = 0;
    rep(j,2)rep(k,2)rep(s,2){
        ans += dp[0][j][k][s]%mod;;
        ans %= mod;
    }
    cout<< ans<<endl;
    return 0;
}

Measured memory_bytes: 256
MOD = 1000000007
M = 2*10**5 + 10
fact = [1] * M
ifact = [1] * M
for i in range(2, M):
    fact[i] = fact[i - 1] * i % MOD
ifact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(2, M - 1)[::-1]:
    ifact[i] = ifact[i + 1] * (i + 1) % MOD


def comb(n, k):
    if n < 0 or k > n:
        return 0
    return (fact[n] * ifact[k] % MOD) * ifact[n - k] % MOD


class DP:
    def __init__(self, dp = 1, size = 0):    
        self.dp = dp
        self.size = size

    def __add__(self, other):
        dp = self.dp
        dp *= other.dp
        dp %= MOD
        size = self.size + other.size
        dp *= comb(size, self.size)
        dp %= MOD
        return DP(dp, size)

    def __sub__(self, other):
        size = self.size - other.size
        dp = self.dp
        dp *= pow(comb(self.size, size), MOD - 2, MOD)
        dp %= MOD
        dp *= pow(other.dp, MOD - 2, MOD)
        dp %= MOD
        return DP(dp, size)

    def addRoot(self):
        return DP(self.dp, self.size + 1)


N = int(input())
e = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [v - 1 for v in map(int, input().split())]
    e[a].append(b)
    e[b].append(a)

order = []
parent = [-1] * N
stack = [0]
while stack:
    v = stack.pop()
    order.append(v)
    for c in e[v]:
        if c == parent[v]:
             continue
        stack.append(c)
        parent[c] = v

dp = [DP() for _ in range(N)]
for v in order[::-1]:
    if parent[v] == -1:
        continue
    dp[parent[v]] += dp[v].addRoot()
for v in order[1:]:
    d = dp[parent[v]] - dp[v].addRoot()
    dp[v] += d.addRoot()
for d in dp:
    print(d.dp)

Measured memory_bytes: 132652
#include<bits/stdc++.h>
#include<sstream>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define strep(it,v) for(it=v.begin();it!=v.end();++it)
#define ii pair<pair<ll,ll>,pair<ll,ll> >
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
#define rs resize
int main()
{
   std::ios::sync_with_stdio(false);
   int n,i,sum = 0,avg,a1 = 0,a2 = 0;
   cin>>n;
   int a[n];
   rep(i,0,n) cin>>a[i],sum += a[i];
   avg = sum/n;
   rep(i,0,n)
   {
      a1 = a1 + pow(a[i] - avg,2);
      a2 = a2 + pow(a[i] - avg - 1,2);
   }
   cout<<min(a1,a2);
   return 0;
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;

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

    map<long int, int> write;
    set<long int> a;

    REP(i, n) {
        long idx;
        cin >> idx;

        write[idx]++;
        a.insert(idx);
    }
    
    long cnt = 0;

    for (auto idx : a) {
        if (write[idx]%2 == 1)    cnt++;
    }
    
    cout << cnt << endl;
}

Measured memory_bytes: 11136
import java.util.*;

class Main{

    int[] par, rank;
    int INF = Integer.MAX_VALUE;

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

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

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

        if(rank[x] < rank[y]) par[x] = y;
        else{
            par[y] = x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

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

    class Edge{
        int u, v, cost;
        Edge(int u, int v, int cost){
            this.u = u;
            this.v = v;
            this.cost = cost;
        }
    }

    void solve(){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt(), m = sc.nextInt();
            if(n==0 && m==0) break;

            Edge[] e = new Edge[m];
            for(int i=0; i<m; i++){
                int a = sc.nextInt()-1, b = sc.nextInt()-1;
                int w = sc.nextInt();
                e[i] = new Edge(a, b, w);
            }

            Arrays.sort(e, new Comparator<Edge>(){
                    public int compare(Edge e1, Edge e2){
                        return e1.cost - e2.cost;
                    }
                });

            int min = INF;
            for(int start=0; start<m; start++){
                int ma = 0, mi = INF;
                init(n);
                int cnt = 0;
                for(int i=start; i<m; i++){
                    Edge ee = e[i];
                    if(!same(e[i].u, e[i].v)){
                        unite(e[i].u, e[i].v);
                        ma = Math.max(ma, e[i].cost);
                        mi = Math.min(mi, e[i].cost);
                        cnt++;
                    }
                }
                if(cnt!=n-1) continue;
                min = Math.min(min, ma-mi);
            }
            if(min==INF) min = -1;
            System.out.println(min);
        }
    }

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

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


int main() {
    int n; cin >> n;
    double ans = (n+1)/2;
    ans /= n;

    cout << fixed << setprecision(9);
    cout << ans << endl;

    return 0;
}



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

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

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

using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define REP(i, n) for(int i=1;i<=n;i++)
typedef long long ll;

int main() {
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	if(k % 2 == 0){
		cout << a - b << endl;
	}else{
		cout << b - a << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

using ll = long long;

int main(int argc, const char *argv[])
{
  int n;
  cin >> n;

  unordered_map<string, ll> cnts;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    cnts[s]++;
  }

  long long ans = 0;
  for (auto &cnt : cnts) {
    if (cnt.second >= 2) {
      ans += cnt.second * (cnt.second - 1) / 2;
    }
  }
 
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 10660
#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define PR printf
#define pb push_back
#define mp make_pair
#define SZ(v) ((int)(v).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define db double
#define ldb long double
#define uint unsigned
#define ll long long
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef pair<pii,pii> ppp;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef map<int,int> mii;
const int INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const int xx[4]={1,-1,0,0};
const int yy[4]={0,0,1,-1};
int inline nextin(){
	int t;
	if(scanf("%d",&t)!=1)exit(0);
	return t;
}
int inline in(){
	int x=0,c;
	for(;(uint)((c=getchar())-'0')>=10;){
		if(c=='-')return -in();
		if(!~c)throw ~0;
	}
	do{
		x=(x<<3)+(x<<1)+(c-'0');
	}while((uint)((c=getchar())-'0')<10);
	return x;
}
void solve(const int &n,const string &s,int t1,int t2){
	vi sh(n);
	sh[0]=t1;sh[1]=t2;
	for(int i=2;i<n;i++){
		sh[i]=(sh[i-1]+sh[i-2]+(s[i-1]=='x'))%2;
	}
	if((sh[n-1]+sh[0]+sh[1]+(s[0]=='x'))%2==0&&(sh[n-2]+sh[n-1]+sh[0]+(s[n-1]=='x'))%2==0){
		rep(i,n)putchar(sh[i]?'W':'S');
		exit(0);
	}
}
int main(){
    cin.sync_with_stdio(false);cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	solve(n,s,0,0);
	solve(n,s,0,1);
	solve(n,s,1,0);
	solve(n,s,1,1);
	puts("-1");
	return 0;
}

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

int main() {
  int a;
  string Eve = "Christmas Eve Eve Eve";
  cin >> a;
  for(int i=22;i<=25;i++){
    if(i==a){
      cout << Eve << endl;
      break;
    }else{     
      Eve.erase(Eve.end()-4,Eve.end());
    }
  }
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	static class Pair implements Comparable<Pair>{
		long left;
		long right;
		public Pair(long l , long r) {
			left = l;
			right = r;
		}
		@Override
		public int compareTo(Pair o) {
			if(left == o.left) {
				return Long.compare(right, o.right);
			}
			return Long.compare(left, o.left);
		}
		@Override
		public String toString() {
			return left + " " + right + " " + (right - left + 1);
		}
	}
	static long len(List<Pair> ps) {
		if(ps.size() == 0) {
			return 0;
		}
		Pair p = ps.get(0);
		long l = p.left;
		long r = p.right;
		for(Pair pp : ps) {
			l = Math.max(l, pp.left);
			r = Math.min(r, pp.right);
		}
		if(l > r) {
			return 0;
		}
		return r - l + 1;
	}
	static long solve(long L[] , long R[]) {
		int N = L.length;
		if(N == 2) {
			return R[1] + R[0] - L[1] - L[0] + 2;
		}
		Pair ps[] = new Pair[N];
		int mi = 0;
		long mlen = 0;
		for(int i = 0 ; i < N ; ++i) {
			ps[i] = new Pair(L[i] , R[i]);
			long len = ps[i].right - ps[i].left + 1;
			if(mlen < len) {
				mlen = len;
				mi = i;
			}			
		}
		long ret = 0;
		{
			List<Pair> l1 = new ArrayList<>();
			List<Pair> l2 = new ArrayList<>();
			l1.add(ps[mi]);
			for(int i = 0 ; i < N ; ++i) {
				if(i != mi) {
					l2.add(ps[i]);					
				}
			}
			long ll = len(l1) + len(l2);
			ret = Math.max(ll, ret);
		}
		Arrays.sort(ps);
		long mls1[] = new long[N];
		long mrs1[] = new long[N];
		mls1[0] = ps[0].left;
		mrs1[0] = ps[0].right;
		long mls2[] = new long[N];
		long mrs2[] = new long[N];
		mls2[N - 1] = ps[N - 1].left;
		mrs2[N - 1] = ps[N - 1].right;
		for(int i = 1 ; i < N ; ++i) {
			mls1[i] = Math.max(mls1[i - 1], ps[i].left);
			mrs1[i] = Math.min(mrs1[i - 1], ps[i].right);
		}
		for(int i = N - 2 ; i >= 0 ; --i) {
			mls2[i] = Math.max(mls2[i + 1], ps[i].left);
			mrs2[i] = Math.min(mrs2[i + 1], ps[i].right);			
		}
		for(int i = 1 ; i < N ; ++i) {
			long l0 = mls1[i - 1];
			long r0 = mrs1[i - 1];
			long l1 = mls2[i];
			long r1 = mrs2[i];
			long ll = 0;
			if(l0 <= r0) {
				ll += r0 - l0 + 1;
			}
			if(l1 <= r1) {
				ll += r1 - l1 + 1;				
			}
			ret = Math.max(ret, ll);
		}
		return ret;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long L[] = new long[N];
		long R[] = new long[N];
		for(int i = 0 ; i < N ; ++i) {
			L[i] = sc.nextLong();
			R[i] = sc.nextLong();
		}
		System.out.println(solve(L, R));
	}
}


Measured memory_bytes: 98468