akhauriyash/Code-Regression huggingface dataset:
module CharSet = Set.Make (Char)

let rec solve n c s =
  if List.for_all (( = ) c) @@ Array.to_list s then n
  else
    solve (n + 1) c (Array.init (Array.length s - 1) (fun i ->
      if s.(i) = c || s.(i + 1) = c then c
      else s.(i)))
let solve = solve 0

let () =
  let s = read_line () in
  let a = Array.init (String.length s) (fun i -> s.[i]) in
  CharSet.of_list (Array.to_list a)
  |> CharSet.elements
  |> List.map (fun c -> solve c a)
  |> List.fold_left min max_int
  |> Printf.printf "%d\n"

Measured memory_bytes: 2560
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;

const double EPS = 1e-10;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
struct L : VP{
    L(const P& a, const P& b){ resize(2); at(0)=a; at(1)=b; }
    L(){ resize(2); }
};
struct C{
    P p;
    double r;
    C(const P& p, const double& r) : p(p), r(r) {}
};

namespace std{
    bool operator < (const P& a, const P& b){
        return !EQ(a.X, b.X) ? a.X<b.X : a.Y<b.Y;
    }
}

double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}

int ccw(P a, P b, P c){
    b -= a;
    c -= a;
    if(cross(b,c) > EPS) return +1; //counter clockwise
    if(cross(b,c) <-EPS) return -1; //clockwise
    if(dot(b,c) < EPS) return +2; //c-a-b
    if(norm(b) < norm(c)) return -2; //a-b-c
    return 0; //a-c-b
}

bool intersectSS(const L& s, const L& t){
    return ( ccw(s[0],s[1],t[0]) *ccw(s[0],s[1],t[1]) <= 0 ) &&
        ( ccw(t[0],t[1],s[0]) *ccw(t[0],t[1],s[1]) <= 0 );
}

P crosspointLL(const L &l, const L &m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  return m[0] + B /A *(m[1]-m[0]);
}


int main(){
  int num;
  cin >> num;
  for(int rep=0; rep<num; rep++){ 
    int xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    int n;
    cin >> n;
    L mine(P(xa,ya), P(xb,yb));

    vector<pair<P, int> > cp;
    for(int i=0; i<n; i++){
      int xs,ys,xt,yt, o,l;
      cin >> xs >> ys >> xt >> yt >> o >> l;
      L line(P(xs, ys), P(xt,yt));
      if(intersectSS(mine, line)){
        cp.push_back(make_pair(crosspointLL(mine, line), o^l));
      }
    }
    sort(cp.begin(), cp.end());

    int ans=0;;
    for(int i=0; i<(int)cp.size()-1; i++){
      if(cp[i].second != cp[i+1].second){
        ans++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3072
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0317
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] dl = RArInt();
            Console.WriteLine(dl[0] / dl[1] + dl[0] % dl[1]);
        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}



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

int main() {
	int h, w; cin >> h >> w;
	char c[210][210];

	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			cin >> c[y][x];
		}
	}

	for (int y = 0; y < h; y++) {
		for (int i = 0; i < 2; i++) {
			for (int x = 0; x < w; x++) {
				cout << c[y][x];
			}
			cout << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
		var scs = Console.In.ReadToEnd().Split(new[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
		Console.WriteLine(Enumerable.Range(0, 1000).Select(i => $"{i}").FirstOrDefault(x => x.Length == h[0] && scs.All(sc => x[sc[0] - '1'] == sc[2])) ?? "-1");
	}
}


Measured memory_bytes: 28336
#include <bits/stdc++.h>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
//#define INF             1000000000
//#define INF             100000000000000

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

void init(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

const int N = 305;
const int M = N*3;

double dp[N][N][N];

int n;

double solve(int sush_1, int sush_2, int sush_3){
	int sum = sush_1 + sush_2 + sush_3;
	if(sum == 0)
		return 0;
	double & ans = dp[sush_1][sush_2][sush_3];
	if(ans != -1)
		return ans;
	double calc = 0.0;
	if(sush_1 > 0)
		calc += (1.0 * sush_1 / sum) * solve(sush_1-1, sush_2, sush_3);
	if(sush_2 > 0)
		calc += (1.0 * sush_2 / sum) * solve(sush_1+1, sush_2-1, sush_3);
	if(sush_3 > 0)
		calc += (1.0 * sush_3 / sum) * solve(sush_1, sush_2+1, sush_3-1);
//	cout << ans << " " << calc << endl;
	return ans = calc + (1.0 * n / sum);
}

int main()
{
	int sum[3] = {0, 0, 0}, num;
	lp(i, N)
		lp(j, N)
			lp(k, N)
				dp[i][j][k] = -1;
	cin >> n;
	lp(i, n){
		cin >> num;
		++sum[num-1];
	}
	cout << setprecision(15) << solve(sum[0], sum[1], sum[2]);
	return 0;
}


Measured memory_bytes: 221952
n=int(input())
s=input()
lt=[s]
lw=s[-1]
msg='Yes'
for i in range(1, n):
    s=input()
    if s[0] != lw or lt.count(s) > 0:  
        msg='No'
        break
    else:
        lw=s[-1]
        lt.append(s)
print(msg)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdint>

using namespace std;

int main()
{
	int64_t a, b, x;
	cin >> a >> b >> x;

	int64_t a_r{ a % x }, b_r{ b % x };


	cout << (b - b_r) / x - (a - a_r) / x + ( a_r == 0 ? 1 : 0 ) << endl;
}


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

using namespace std;

int main() {
    int N;
    cin >> N;
    long long int L_i_2 = 2;
    long long int L_i_1 = 1;
    long long int L_i = L_i_1 + L_i_2;
    if(N == 1) {
        cout << L_i_1 << endl;
        return 0;  
    }
    if(N == 2) {
        cout << L_i << endl;
        return 0;  
    }

    for(size_t i = 3; i < N+1; i++) {
        swap(L_i, L_i_1);
        L_i += L_i_1;
    }
    cout << L_i << endl;
    return 0;
}

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

int main() {
  int s1s2s3;
  cin >> s1s2s3;
  int k1 = s1s2s3 / 100;
  int k2 = (s1s2s3 - k1 * 100) / 10;
  int k3 = s1s2s3 - k1 * 100 - k2 *10;
  cout << k1 + k2 + k3 << endl;
}


Measured memory_bytes: 3632
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n, m;
	string u[256], t[256];
	cin >> n;
	for (int i = 0; i < n; i++)cin >> u[i];
	cin >> m;
	bool open = false;
	for (int i = 0; i < m; i++) {
		cin >> t[i];
		bool know = false;
		for (int j = 0; j < n; j++) {
			if (t[i] == u[j]) {
				know = true;
				if (!open) {
					open = true;
				}
				else {
					open = false;
				}
				break;
			}
		}
		if (know) {
			if (open)cout << "Opened by " << t[i] << endl;
			else cout << "Closed by " << t[i] << endl;
		}
		else cout << "Unknown " << t[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1232
N = int(input())
seq = list(map(int, input().rstrip().split(' ')))

odd = [[0, i] for i in range(int(1e5 + 1))]
even = [[0, i] for i in range(int(1e5 + 1))]

for i in range(0, N, 2):
    even[seq[i]][0] += 1
    
for i in range(1, N, 2):
    odd[seq[i]][0] += 1

sorted_even = sorted(even, key=lambda x: x[0])[::-1]
sorted_odd = sorted(odd, key=lambda x: x[0])[::-1]

if sorted_even[0][1] == sorted_odd[0][1]:
    if sorted_even[0][0] + sorted_odd[1][0] > sorted_even[1][0] + sorted_odd[0][0]:
        max_even = sorted_even[0][0]
        max_odd = sorted_odd[1][0]
    else:
        max_even = sorted_even[1][0]
        max_odd = sorted_odd[0][0]
else:
    max_even = sorted_even[0][0]
    max_odd = sorted_odd[0][0]
 
count = 0
count += N // 2 - max_even
count += N // 2 - max_odd

print(count)

Measured memory_bytes: 37428
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <utility>
#include <cstdio>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)

template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}

int x,y;

int main()
{
    
    cin>>x>>y;
  	cout<<x+y/2<<endl;
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define show(a) cout<<""#a""<<" is "<<a<<endl;
#define shw(a,b)cout<<"-->"<<a<<" "<<b<<endl;
#define print(arr,xx)for(int i=0;i<xx;i++)cout<<arr[i]<<" \n"[i>=xx];
#define here cout<<"here\n"; 
int caseno=0;
#define print_case cout<<"Case "<<++caseno<<": ";
#define fout freopen("output.txt","w",stdout);
#define fin freopen("input.txt","r",stdin);
#define pb push_back
#define ll long long
const int primemod=1e9+7;
#define fastio   
ll max(ll a,ll b) {return (a>b)?a:b;}
//string max(string a,string b) {return (a>b)?a:b;}
//ll min(ll a,ll b) {return (a<b)?a:b;}
const int maxsize = 100000+9;
void solve(){
	int a,b,k;
	cin>>k>>a>>b;
	bool ok =0;
	for(int i=a;i<=b;i++)if(i%k==0)ok=1;
	if(ok)cout<<"OK"<<endl;
	else cout<<"NG"<<endl;
}

int main(){
	#ifndef ONLINE_JUDGE
 	fout	
 	fin
 	int kase=1; 	
 	while(kase--){
 	#endif     
 	///-----		
 	//fastio
 	int T;
 	// cin>>T;
 	T=1;
 	while(T--){
 		 // if(solve())cout<<"Yes"<<endl;
 		 // else cout<<"No"<<endl;
 		solve();
 	}
 	///-----
 }
 
 #ifndef ONLINE_JUDGE
 }			
 #endif


Measured memory_bytes: 3636
#include <bits/stdc++.h>
//#define Ak

using namespace std;

template< class t>
long long int gcd( t g,t h )
{
    return ( h==0 ? g : gcd(h,g%h) );
}

int main()
{
   /* #ifdef Ak
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    */
    long long int n,i,j,ans=0,a[300005]={0},sum=0;
    
   // list< long long int >v;
   vector< long long int>v;
   // map< long long int >m;
   
    cin>>n;
    j=3*n;
    for(i=0;i<j;i++)
    {
        cin>>a[i];
        v.push_back(a[i]);
    }
    
    j=3*n;
    sort(a,a+j);
    sort(v.begin(),v.end());
    
   /* for(i=0;i<j;i++)
    {
        cout<<a[i]<<endl;
    }
    
    cout<<endl;
    */
    while(n--)
    {
        sum+=a[j-2];
       // cout<<sum<<endl;
        j-=2;;
    }
    //cout<<j;
    cout<<sum;
    
    return 0;
    
}


Measured memory_bytes: 8816
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define NIL -1
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<char>>;
using P =pair<int,int>;

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

int main(){
    ll n;
    cin>>n;
    cout<<(n-1)*n/2<<endl;
}

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

int main()
{
	int n;
	cin>>n;
	vector<long long int> v(n);
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
	}
	long long int ans=0;
	long long int x=v[0];
	for(int i=1;i<n;i++)
	{
		x=max(x,v[i]);
		if(v[i]-x<0)
		{
			ans+=abs(x-v[i]);
		}
	}
	
	cout<<ans<<endl;
}

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

int main() {
  int N;
  cin >> N;;
  
  N = N%10;
  
  if(N==2||N==4||N==5||N==7||N==9)
    cout << "hon" << endl;
  else if(N==3)
    cout << "bon" << endl;
  else
    cout << "pon" << endl;
}


Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    string S;
    cin >> S;
    
    int max = 0;
    int tmp=0;

    for(int i=0;i<S.length();i++){
        if (S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T'){
            tmp +=1;
            if (max<tmp) max=tmp;
        }else{
            tmp=0;
        }
    }
    cout << max << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REPS(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
using ll = long long;
using ld = long double;

int main(void) {
    ll N, M;
    cin >> N >> M;
    ll X[M];
    set<ll> set_X;
    REP (i, M) {
        cin >> X[i];
        set_X.insert(X[i]);
    }

    sort (X, X+M);
    ll d[M-1];
    REP (i, M-1) {
        d[i] = X[i+1] - X[i];
    }
    sort (d, d+M-1);
    ll ans = 0;
    if (set_X.size() > N) {
        REP (i, M-N) {
            ans += d[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S,T;cin>>S>>T;
  vector<string>A;
  for(int i=0;i<S.size()-T.size()+1;i++){
    string s=S;
    bool b=false;
    for(int j=i;j<i+T.size();j++){
      if(S.at(j)=='?'){s.at(j)=T.at(j-i);continue;}
      if(S.at(j)!=T.at(j-i)){b=true;break;}
      }
    if(!b){
      for(int k=0;k<S.size();k++)if(s.at(k)=='?')s.at(k)='a';
      A.push_back(s);
    }
  }
  if(A.size()==0)puts("UNRESTORABLE");
  else{
    sort(A.begin(),A.end());
    cout<<A[0]<<endl;
  }
}

Measured memory_bytes: 3620
#include<cstdio>
#include<cstring>
#define For(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int main(){
	int l; char f[100005]; scanf("%s",f); l=strlen(f);
	For(i,0,l-1) if (i%2==0) printf("%c",f[i]);
	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; scanf("%d", &n);
	rep(i, n) {
		string s; cin >> s;
		if (s.size() < 4 || s.size() % 2 == 1) {
			puts("NA");
			continue;
		}
		if (s[0] == '>'&&s[1] == '\''&&s[s.size() - 1] == '~') {
			int cnt = 0;
			bool flag = false;
			bool ok = false;
			for (int i = 2; i < s.size() - 1; i++) {
				if (s[i] != '='&&s[i] != '#') { puts("NA"); goto g; }
				if (flag&&s[i] == '#') { puts("NA"); goto g; }
				if (s[i] == '#')flag = true;
				else {
					ok = true;
					if (flag)cnt--;
					else cnt++;
				}
			}
			if (!ok) { puts("NA"); goto g; }
			puts(cnt ? "NA" : "A");
		}
		else if (s[0] == '>'&&s[1] == '^'&&s[s.size() - 2] == '~'&&s[s.size() - 1] == '~') {
			if (s.size() == 4) { puts("NA"); goto g; }
			for (int i = 2; i < s.size() - 2; i += 2) {
				if (s[i] != 'Q' || s[i + 1] != '=') {
					puts("NA"); goto g;
				}
			}
			puts("B");
		}
		else puts("NA");
	g:;
	}
}

Measured memory_bytes: 3140
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static int[] next(int[] a) {
		int n = a.length;
		int[] cnt = new int[10000];
		for (int i=0; i<n; i++) {
			cnt[a[i]]++;
		}
		int[] res = new int[n];
		for (int i=0; i<n; i++) {
			res[i] = cnt[a[i]];
		}
		return res;
	}

	static boolean solve() {
		int n = in.nextInt();
		if (n == 0) return false;

		int[] a = new int[n];
		for (int i=0; i<n; i++) {
			a[i] = in.nextInt();
		}

		int cnt = 0;
		while (true) {
			int[] b = next(a);
			boolean f = true;
			for (int i=0; i<n; i++) {
				if (a[i] != b[i]) f = false;
			}
			if (f) {
				out.println(cnt);
				for (int i=0; i<n-1; i++) {
					out.print(a[i] + " ");
				}
				out.println(a[n-1]);
				break;
			}
			a = b;
			cnt++;
		}

		return true;
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.currentTimeMillis();

		while(solve());
		out.flush();

		long end = System.currentTimeMillis();
		dump((end-start) + "ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

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

using namespace std;
using ll=int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi=vector<int>;
using vii=vector<vi>;
using vl=vector<ll>;
using vll=vector<vl>;
using tpi=tuple<int, int, int>;

using vqi=vector<queue<int>>;

using vqi=vector<queue<int>>;
using bs=bitset<60>;
using vbi=vector<bs>;
constexpr ll MOD = 1e9 + 7;


int main() {
    int N;
    cin >> N;
    ll counter = 1;

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (a == counter) {
            counter++;
        } else {
            ans++;
        }
    }
    if (counter == 1) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

vector<vector<P> > G;

int bfs(){
  int n = G.size();
  deque<P> Q;
  vector<int> D(n,INF);
  vector<unordered_set<int> > visited(n);
  Q.push_back(P(0,0));
  D[0] = 0;
  
  while(!Q.empty()){
    auto t = Q.front();Q.pop_front();
    int pos = t.first;
    int comp = t.second;
    if(pos == n-1) return D[pos];
    
    if(comp != 0 && !visited[pos].count(0)){
      visited[pos].insert(0);
      Q.push_back(P(pos,0));
    }
    
    int i = lower_bound(G[pos].begin(),G[pos].end(),P(comp,-INF)) - G[pos].begin();
    for(;i<(int)G[pos].size();i++){
      auto p = G[pos][i];
      int to = p.second;
      int comp2 = p.first;
      int ncost = D[pos] + (comp != comp2);
      if(comp != 0 && comp != comp2) break;
      if(D[to] < ncost) continue;
      if(visited[to].count(comp2)) continue;
      visited[to].insert(comp2);
      
      D[to] = ncost;
      if(comp == comp2) Q.push_front(P(to,comp));
      else Q.push_back(P(to,comp2));
    }
  }
  return -1;
}

signed main(){
  
  int n,m;
  cin>>n>>m;
  G.resize(n);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c; a--,b--;
    G[a].push_back(P(c,b));
    G[b].push_back(P(c,a));
  }

  for(int i=0;i<n;i++) sort(G[i].begin(),G[i].end());
  int ans = bfs();
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 29136
H,W=list(map(int,input().split()))
S=[]
for h in range(H):
    S.append(list(input()))

for h in range(H):
    for w in range(W):
        count=0
        if S[h][w]=='#':
            continue
        # left up
        if w==0 or h==0:
            pass
        elif S[h-1][w-1]=='#':
            count+=1

        # Left
        if w==0:
            pass
        elif S[h][w-1]=='#':
            count+=1

        # Left down
        if w==0 or h==H-1:
            pass
        elif S[h+1][w-1]=='#':
            count+=1

        # Up
        if h==0:
            pass
        elif S[h-1][w]=='#':
            count+=1

        # Right up
        if h==0 or w==W-1:
            pass
        elif S[h-1][w+1]=='#':
            count+=1

        # Right
        if w==W-1:
            pass
        elif S[h][w+1]=='#':
            count+=1

        # Right down
        if w==W-1 or h==H-1:
            pass
        elif S[h+1][w+1]=='#':
            count+=1

        # Down
        if h==H-1:
            pass
        elif S[h+1][w]=='#':
            count+=1
        
        S[h][w]=str(count)

for h in range(H):
    print("".join(S[h]))



Measured memory_bytes: 3188
#include <iostream>
using namespace std;
int main()
{
	int a, b, c;
	cin >> a >> b;
	c = a - b;
	if(a - b < 0)
	{
		cout << 0 << endl;
	}
	else
	{
		cout << c << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int a, b, c, d, e, f, g, h, t, s1, s2;
int main()
{
    cin >> a >> b >> c >> d >> e >> f;
    a *= 100;//100A
    b *= 100;//100B
    for (int i = 0; i <= 30 && i * a <= f; i++)//for A 
        for (int j = 0; j <= 30 && i * a + j * b <= f; j++)//for B
            if (i + j)//i+j>=1
            {
                g = i * a + j * b;//amount of water
                h = min(g * e / 100, f - g);//sugar melted by g gram water and decreased from f (maximum amount)
                t = 0;
                for (int k = 0; k <= 100 && c * k <= h; k++)
                    for (int l = 0; l <= 100 && c * k + d * l <= h; l++)
                        t = max(t, c * k + d * l);// t ... maximum amount of sugar no more than h
                if (s1 == 0 || t * (s1 + s2) > s2 * (g + t))
                {
                    s1 = g;//s1 ... water
                    s2 = t;//s2 ... sugar
                }
            }
    cout << s1 + s2 << " " << s2 << endl;
    return 0;
}

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

#define		fuckshitup  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) // don't use for small inputs
#define		endl		"\n"
#define		ll			long long int
#define		mod			1000000007
#define		f(i,a,b)	for(ll i = (ll)(a); i < (ll)(b); i++)
#define		rf(i,a,b)   for(ll i = (ll)(a); i > (ll)(b); i--)
#define		ull			unsigned long long
#define		ld			long double

struct custom_hash{
    static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
}
};

int main()
{
	fuckshitup;
    ll n, a, b;
    cin >> n >> a >> b;
    ll sum = a + b;
    ll count = n / sum;
    ll rem = n % sum;
    ll left = min(a, rem);
    cout << a * count + left << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const ll INF = 2e15;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main(){
  ll n;
  cin>>n;
  vl z(n);
  vl w(n);
  rep(i,n){
    ll x,y;
    cin>>x>>y;
    z[i]=x+y;
    w[i]=x-y;
  }
  ll maxi_z=-INF;
  ll mini_z=INF;
  ll maxi_w=-INF;
  ll mini_w=INF;
  rep(i,n){
    chmax(maxi_z,z[i]);
    chmin(mini_z,z[i]);
    chmax(maxi_w,w[i]);
    chmin(mini_w,w[i]);
  }
  ll s=maxi_z-mini_z;
  ll t=maxi_w-mini_w;
  cout<<max(s,t)<<endl;
}


Measured memory_bytes: 6380
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repa(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define PI (acos(-1))
#define _GLIBCXX_DEBUG

int main(){
  
  int n;
  cin >> n;
  
  int m = n / 1.08;

  repa(i, m, ceil(n/1.08)+1){
    if(floor(i*1.08) == n){
      cout << i << endl;
      return 0;
    }
  }

  cout << ":(" << endl;

}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main{
    static MyReader in = new MyReader();

    public static void main(String[] args){
        int[][] d = {{0, 0, 0, 0, 0, 0},
                    {2, 0, 9, 0, 0, 0},
                    {0, 3, 0, 0, 0, 0},
                    {0, 0, 4, 0, 0, 0},
                    {0, 0, 0, 5, 0, 0},
                    {0, 0, 0, 0, 6, 0},
                    {2, 0, 7, 0, 0, 0},
                    {0, 8, 0, 0, 0, 0},
                    {2, 0, 9, 11, 0, 0},
                    {0, 10, 0, 0, 0, 0},
                    {0, 0, 0, 11, 0, 0},
                    {0, 0, 0, 0, 0, 12},
                    {0, 0, 13, 0, 0, 0},
                    {2, 1, 9, 0, 0, 0}};
        int s = 1;
        String S = in.s();
        final int N = S.length();

        for(int i = 0; i < N; i++){
            char c = S.charAt(i);
            int x = c == 'd' ? 0 :
                    c == 'r' ? 1 :
                    c == 'e' ? 2 :
                    c == 'a' ? 3 :
                    c == 'm' ? 4 :
                    c == 's' ? 5 : 6;
            if(x == 6 || (s = d[s][x]) == 0) {
                out.println("NO");
                return;
            }
        }

        out.println((s-1)*(s-6)*(s-8)*(s-13) == 0 ? "YES" : "NO");
    }

    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }

        String s(){
            try{return readLine();}catch(IOException e){return "";}
        }

        String[] ss(){
            return s().split(" ");
        }

        int i(){
            return Integer.parseInt(s());
        }

        int[] ii(){
            String[] ss = ss();
            int[] ii = new int[ss.length];
            for(int j = 0; j < ss.length; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }

        ArrayList<Integer> li(){
            String[] ss = ss();
            ArrayList<Integer> li = new ArrayList<>();
            for(int j = 0; j < ss.length; j++) li.add(Integer.parseInt(ss[j]));
            return li;
        }

        long l(){
            return Long.parseLong(s());
        }

        long[] ll(){
            String[] ss = ss();
            long[] ll = new long[ss.length];
            for(int j = 0; j < ss.length; j++) ll[j] = Long.parseLong(ss[j]);
            return ll;
        }
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    char a, b;
    cin >> a >> b;
    string s(a - '0', b);
    string t(b - '0', a);
    cout << min(s, t) << endl;
    return 0;
}


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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};



int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int x,a,b;
    cin >>x>>a>>b;
  

    //cout <<fixed<<setprecision(16)<< << endl;
    //cout<<ans<<endl;
    if(abs(x-a) < abs(x-b) )cout << "A" <<endl;
    else cout << "B" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    S = Scanner.string()
    if S == 'RRR':
        print(3)
    elif 'RR' in S:
        print(2)
    elif 'R' in S:
        print(1)
    else:
        print(0)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()


Measured memory_bytes: 10704
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,Q;
    cin >> a >> b >> Q;
    vector<long long>s(a+2),t(b+2);
    s[0]=-(1e11);t[0]=-(1e11);
    s[a+1]=1e12;t[b+1]=1e12;
    for(int i=0;i<a;i++)cin >> s[i+1];
    for(int i=0;i<b;i++)cin >> t[i+1];

    for(int i=0;i<Q;i++){
        long long x;
        cin >> x;
        int l=-1;int r=a+2;
        while(r-l>1){
            int mid=(l+r)/2;
            if(s[mid]<x)l=mid;
            else r=mid;
        }
        int ll=-1;int rr=b+2;
        while(rr-ll>1){
            int mid=(ll+rr)/2;
            if(t[mid]<x)ll=mid;
            else rr=mid;
        }
        long long ans = (1e12);
        ans=min(ans,max(abs(x-s[l]),abs(x-t[ll])));
        ans=min(ans,max(abs(x-s[r]),abs(x-t[rr])));
        ans=min(ans,abs(s[r]-t[ll])+min(abs(x-s[r]),abs(x-t[ll])));
        ans=min(ans,abs(t[rr]-s[l])+min(abs(x-t[rr]),abs(x-s[l])));
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 2944
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h> 
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <boost/math/common_factor.hpp>
#include <algorithm>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include<chrono>
 
using namespace std;
//using namespace std::chrono;
 
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define vl int64_t


int main()
{
  ll n;
  cin>>n;
  if(n%2==1)
    cout<<0;
  
  else
  {
  	/*ll prod=1;
  	for(ll i=2;i<=n;i+=2)
  	prod*=i;
  	
  	cout<<prod<<endl;*/
    ll ctr=0;
    n/=2;
    for(ll i=1; ;i++)
    {
    	ll val=pow(5,i);
    	if(n/val==0)
    	break;
    	
    	else
    	ctr+=n/val;
    }
    
    cout<<ctr;
  }
}

Measured memory_bytes: 512
import std.stdio : readln, writeln, chomp, stdin;
import std.conv : to;
import std.string : split;
import std.algorithm : min, max;

void solve()
{
	int sum, num, count;
	
	while(true){
		string str = readln.chomp;
		
		if(stdin.eof())	break;
		
		string[] sp = str.split(",");
		int v = sp[0].to!int;
		int m = sp[1].to!int;
		
		++count;
		sum += v*m;
		num += m;
	}
	writeln = sum;
	writeln = cast(int)((num / cast(double)count) + .5);
}

void main()
{
	solve();
}

Measured memory_bytes: 980
N,M=map(int,input().split())

#Union-Find

par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
root=set()

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            if b in root:
                root.remove(b)
            root.add(a)
            siz[a]+=siz[b]
        else:
            par[a]=b
            if a in root:
                root.remove(a)
            root.add(b)
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)
    
edge=[]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    edge.append([a,b])
p=N*(N-1)//2
res=[p]
for i in reversed(range(1,M)):
    if(not same(edge[i][0],edge[i][1])):
        p=p-size(edge[i][0])*size(edge[i][1])
        union(edge[i][0],edge[i][1])
    res.append(p)
print(*res[::-1],sep='\n')

Measured memory_bytes: 123552
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){
 double N, T, A;
 int ten = 0;
 cin >> N >> T >> A;
 vector<int> H(N);

 for(int i = 0; i < N; i++){
   cin >> H.at(i);
 }
 double difference = (T - H.at(0) * 0.006);
 double result = abs(A - difference);

 for(int i = 1; i < N; i++){
  difference = abs(A - (T - H.at(i) * 0.006));
  if( result > difference ){
    result = abs(A - (T - H.at(i) * 0.006));
    ten = i;
  }
 }
 cout << ten + 1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dist(int a, int b, int c, int d) {
	return abs(a - c) + abs(b - d);
}
int main () {
	long long n, T = 0, px = 0, py = 0;
	cin >> n;
	for (int i = 0; i < n; i++) 
	{
		long long t, x, y;
		cin >> t >> x >> y;
		long long dt = t - T, dx = dist(x, y, px, py);
		if ((dt >= dx && dt % 2 == dx % 2) == 0) 
		{
		    cout << "No"; 
		    return 0;
		}
		T = t;
		px = x;
		py = y;
	}
	cout << "Yes";
}

Measured memory_bytes: 3588
using System;
using System.Linq;

namespace MINAPC2019
{
    class C
    {
        static void Main(string[] args)
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long K = input[0];
            long A = input[1];
            long B = input[2];

            if (K < A)
            {
                Console.WriteLine(K + 1);
            }
            else if (A <= K)
            {
                if (B <= A) Console.WriteLine(K + 1);
                else if (A < B)
                {
                    long count = 1;
                    long ope = 0;
                    while (ope < K)
                    {
                        if (ope < K - 1 && A <= count && 2 <= B - A) { count -= A; count += B; ope += 2; }
                        else { count++; ope++; }
                        //Console.WriteLine("{0} {1}", ope, count);
                    }
                    Console.WriteLine(count);
                }
            }
        }
    }
}


Measured memory_bytes: 11348
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <string.h>
using namespace std ;

int main()
{
   char ch1[400000];
   char ch2[400000];
   cin>>ch1>>ch2;
  int n = strlen(ch1);
  int m = strlen(ch2);
  int count = 0;
   for(int i=0;i<n;i++)
   {
       if(ch1[i] != ch2[i])
       {
           count++;
       }
   }
   cout<<count;
    return 0;
}


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

int main() {
  int K, A, B;
  cin >> K >> A >> B;
  bool judge = false;
  for (int i = A; i <= B; i++) {
    if (i % K == 0) {
      judge = true;
      break;
    }
  }
  if (judge == true) {
    cout << "OK" << endl;
  } else {
    cout << "NG" << endl;
  }
}

Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<map>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int a = 0;a < i;a++){for(int b = 0;b < j;b++)cerr << v[a][b] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int mp[1<<26];
int memo[200001];

int main()
{
	string str;
	cin >> str;
	
	
	REP(i,1<<26)
	{
		mp[i] = 100000000;
	}
	REP(i,str.size()+1)
	{
		memo[i] = 1000000;
	}
	
	int d = 0;
	memo[0] = mp[0] = 0;
	REP(i,str.size())
	{
		memo[i+1] = min(memo[i+1],memo[i]+1);
		
		d ^= (1 << (str[i] - 'a'));
		
		REP(j,26)
		{
			memo[i+1] = min(memo[i+1] ,mp[d ^ (1 << j)]+1);
		}

		memo[i+1] = min(memo[i+1] , mp[d]+1);
		mp[d] = min(memo[i+1],mp[d]);

	}
		
	cout << memo[str.size()] << endl;
	
	return 0;
}





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

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

	int ans = 0, d[3] = {3,5,7};
	for (int i = 3; i < 10; i++){ // 桁数
		for (int bit = 0; bit < pow(3, i); bit++){
			int a = 0, p = bit;
			for (int j = 0; j < i; j++){
				a += d[p%3] * pow(10, j);
				p /= 3;
			}

			if(a > n) continue;

			// 以下,条件に合うかチェック
			string s = to_string(a);
			bool check[4] = {0};
			for (int j = 0; j < s.size(); j++){
				if(s[j] == '3') check[0] = 1;
				else if(s[j] == '5') check[1] = 1;
				else if(s[j] == '7') check[2] = 1;
				else check[3] = 1;
			}
			if(check[0] && check[1] && check[2] && !check[3]){
				ans++;
			}
		}
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/************************************************
 * Au: Hany01
 * Prob: c
 * Email: hany01dxx@gmail.com & hany01@foxmail.com
 * Inst: Yali High School
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define Rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define X first
#define Y second
#define PB(a) push_back(a)
#define MP(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read() {
	static int _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}
//EOT


const int maxn = 405, maxm = 1e5 + 5;

int n, m, cnt;
bitset<maxn> f[maxn], fuck;
PII E[maxm];

inline void check(int x) {
	f[x][x] = 1;
	Fordown(i, m, 1) {
		if (f[x][E[i].X] && f[x][E[i].Y]) { fuck[x] = 1; return; }
		if (f[x][E[i].X] || f[x][E[i].Y]) f[x][E[i].X] = f[x][E[i].Y] = 1;
	}
}

int main()
{
#ifdef hany01
	freopen("c.in", "r", stdin);
	freopen("c.out", "w", stdout);
#endif

	n = read(), m = read();
	For(i, 1, m) E[i].X = read(), E[i].Y = read();
	For(i, 1, n) check(i);

	For(i, 1, n) if (!fuck[i]) For(j, i + 1, n) if (!fuck[j])
		if (!(f[i] & f[j]).any()) ++ cnt;
	printf("%d\n", cnt);

	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int N;
int boss[7],height[7];

int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	if(height[x] > height[y]){

		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void init(){
	for(int i = 0; i < 7; i++){
		boss[i] = i;
		height[i] = 0;
	}
}

int main(){

	int array[7],num,num_KI,num_boss;

	char buf[3];
	int a,b;

	bool FLG;

	while(scanf("%d",&N) != EOF){

		init();
		for(int i = 0; i < 7; i++)array[i] = 0;

		for(int i = 0; i < N; i++){
			scanf("%s",buf);
			a = buf[0] - '0';
			b = buf[1] - '0';
			array[a]++;
			array[b]++;
			unite(a,b);
		}
		FLG = true;

		num_KI = 0;

		for(int i = 0; i < 7; i++)if(array[i]%2 == 1)num_KI++;

		if(num_KI > 2){
			printf("No\n");
			continue;
		}

		num_boss = 0;
		for(int i = 0; i < 7; i++){
			if(array[i] > 0 && i == get_boss(i))num_boss++;
		}
		if(num_boss > 1)FLG = false;

		if(FLG){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}

	return 0;
}

Measured memory_bytes: 3104
N,A,B = list(map(int,input().split()))
 
v = list(map(int,input().split()))
 
v.sort()
v=v[::-1]
 
a=v[A-1]
is_first = True
end=-1
for i in range(N):
    if v[i]==a:
        if is_first:
            first=i
            is_first=False
    else:
        if not is_first:
            end=i
            break
 
def comb(n,k):
    a = 1
    b = 1
    for i in range(min(n-k,k)):
        a*=n-i
        b*=i+1
    return a//b
#print(comb(3,1))
if end==-1:
    end=N
if first==0:
    print(a)
    print(sum([comb(end,i) for i in range(A,min(B,end)+1)]))
else:
    print(sum(v[:A])/A)
    print(comb(end-first,A-first))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e2+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXM][MAXM];
int red[MAXM][MAXM];
int blue[MAXM][MAXM];
int res[MAXM][MAXM];
char S[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;

    for(int i=1;i<=n;i++){
        cin>>S;
        for(int j=1;j<=m;j++)
            if(S[j-1]=='#')A[i][j] = 1;
    }

    for(int i=2;i<n;i++)
        red[i][1] = blue[i][m] = 1;

    for(int i=2;i<n;i++)
        for(int j=2;j<m;j++){
            if(i&1)red[i][j] = 1;
            else blue[i][j] = 1;

            if(A[i][j])red[i][j] = blue[i][j] = 1;
        }

    for(int i=1;i<=n;i++,cout<<"\n")
        for(int j=1;j<=m;j++)
            if(red[i][j])cout<<"#";
            else cout<<".";

    cout<<"\n";

    for(int i=1;i<=n;i++,cout<<"\n")
        for(int j=1;j<=m;j++)
            if(blue[i][j])cout<<"#";
            else cout<<".";

    return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define M 1000000007
#define N 100001
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

int t, n, doublet = 0, a, b, f = 0;
void printArray(int*, int);

int main() {
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d %d", &a, &b);

        if(a == b) doublet++;
        else doublet = 0;

        if(doublet == 3) f = 1;
    }

    if(f) cout<<"Yes\n";
    else cout<<"No\n";
	return 0;
}

void printArray(int *nums, int n) {
    for(int i=0; i<n; i++) printf("%d ", nums[i]);
    printf("\n");
}

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

int main(){
  ll dp[1000100][3];
  ll n;
  cin >> n;
  ll v[100010][3];
  rep(i,n) cin >> v[i][0] >> v[i][1] >> v[i][2];
  rep(i,3) dp[0][i] = v[0][i];
  rep(i,n) {
    rep(j,3) {
      rep(k,3) {
        if(j != k) dp[i+1][k] = max(dp[i+1][k], dp[i][j] + v[i+1][k]);
      }
    }
  }
  ll ans = 0;
  rep(i,3) ans = max(ans, dp[n][i]);
  cout << ans << endl;
}

Measured memory_bytes: 6912