akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>

using namespace std;

int main(){
	int n;
	double students[1000] = {0},sum,m,div;

	while(true){
		scanf("%d",&n);
		if(n == 0) break;
		div = sum = 0;
		for(int i = 0; i < n; i++){
			scanf("%lf",&students[i]);
			sum += students[i];
		}
		m = sum/n;
		for(int i = 0; i < n;i++){
			div += (students[i] - m)*(students[i] - m);
			students[i] = 0;
		}
		printf("%.8lf\n",sqrt(div/n));
	}
}



Measured memory_bytes: 2756
#include<stdio.h>
int a,n,s;
void k(int sum,int c,int j){
  int i;
  for(i=1;i+j<10;i++){
    sum+=(i*c);
    c--;
    if(c<=0){
      if(sum==s){
	a++;
	break;
      }
    }
    else k(sum,c,i+j);
    c++;
    sum-=i*c;
  }
}
int main(){
  int i,c,sum=0;
  while(scanf("%d %d",&n,&s)){
    if(n==0&&s==0)break;
    a=0;
    c=n;
    for(i=0;i*n<=s;i++){
      sum=i*c;
      k(sum,c-1,i); 
    }
    printf("%d\n",a);
  }
  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const double INF3 = 900000000000000;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll n, m, a[100010], cnt = 0, ans = 0;
vector<ll>node[100010], tree[100010];
bool used[100010] = { 0 };

void dfs(ll x, ll y) {
	if (used[x])return;
	used[x] = true;
	for (int i = 0;i < node[x].size();i++) {
		if (used[node[x][i]])continue;
		tree[cnt].pb(a[node[x][i]]);
		dfs(node[x][i], cnt);
	}
}

int main() {
	cin >> n >> m;
	if (m == n - 1) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 0;i < n;i++)cin >> a[i];
	for (int i = 0;i < m;i++) {
		ll x, y;
		cin >> x >> y;
		node[x].pb(y);
		node[y].pb(x);
	}
	for (int i = 0;i < n;i++) {
		if (used[i])continue;
		tree[cnt].pb(a[i]);
		dfs(i, cnt);
		cnt++;
	}
	ll c = 2 * (n - m - 1);
	if (n < c) {
		cout << "Impossible" << endl;
		return 0;
	}
	priority_queue<ll ,vector<ll>, greater<ll>>pq;
	for (int i = 0;i < cnt;i++) {
		sort(ALL(tree[i]));
		for (int j = 0;j < tree[i].size();j++) {
			if (j == 0)ans += tree[i][j], c--;
			else pq.push(tree[i][j]);
		}
	}
	for (int i = 0;i < c;i++) {
		ans += pq.top();
		pq.pop();
	}
	cout << ans << endl;
}

Measured memory_bytes: 11768
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
using namespace std;

int main(){
  int n; cin >> n;
  char s[n];

  bool flag=false;
  for(int i=0; i<n; i++){
    cin >> s[i];
    if(s[i]=='Y') flag = true;
  }

  string ans="Three";
  if(flag) ans="Four";

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
class UnionFindTree:
    '''
    Union Find Tree
    '''

    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


n, q = map(int, input().split())
uft = UnionFindTree()
for i in range(n):
    uft.make(i)

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uft.unite(x, y)
    else:
        print(1 if uft.same(x, y) else 0)



Measured memory_bytes: 6596
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

class Main {
	public static void main(String[] args)
	{
		FastScanner in =new FastScanner();
		int n=in.nextInt();
		int[] h=in.readArray(n);
		int[] dp=new int[n];
		for(int i=0;i<n;i++)
			dp[i]=Integer.MAX_VALUE;
		dp[0]=0;
		if(n>1)
		{
		dp[1]=Math.abs(h[1]-h[0]);
		for(int i=2;i<n;i++)
		{
			int diff1=Math.abs(h[i]-h[i-1]);
			int diff2=Math.abs(h[i]-h[i-2]);
			dp[i]=Math.min(dp[i-1]+diff1,dp[i-2]+diff2);
		}
		}
		System.out.println(dp[n-1]);
	}
	
static final Random random=new Random();
	
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 43032
import heapq
def prim(edges):
    visited = [False] * N
    visited[0] = True
    hq = [e for e in E[0]]
    heapq.heapify(hq)
    res = 0
    while len(hq) != 0:
        w, v = heapq.heappop(hq)
        if visited[v]:
            continue
        visited[v] = True
        res += w
        for z, u in E[v]:
            if visited[u]:
                continue
            heapq.heappush(hq, (z, u))
    return res


N = int(input())
X = [() for _ in range(N)]
Y = [() for _ in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i] = (x, i)
    Y[i] = (y, i)
X = sorted(X)
Y = sorted(Y)
E = [[] for _ in range(N)]
for i in range(N-1):
    x, v = X[i]
    nx, nv = X[i+1]
    E[v].append((nx-x, nv))
    E[nv].append((nx-x, v))
    y, u = Y[i]
    ny, nu = Y[i+1]
    E[u].append((ny-y, nu))
    E[nu].append((ny-y, u))

print(prim(E))

Measured memory_bytes: 84072
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200020];
int b[200020];
int main(){
	cin>>n;
	int cnt=0;
	int haha=0;
	int p=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
		cnt=max(cnt,a[i]);
	}
	for(int i=1;i<=n;i++){
		if(a[i]==cnt){
			p=i;
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]<=cnt&&p!=i){
			haha=max(haha,a[i]);
		}
	}
	for(int i=1;i<=n;i++){
		if(haha==0){
			cout<<cnt<<endl;
			continue;
		}
		if(a[i]==cnt){
			cout<<haha<<endl;
		}else{
			cout<<cnt<<endl;
		}
	}
}

Measured memory_bytes: 3200
#include <string>
#include <bits/stdc++.h>
#include <stdio.h>
#include<math.h>
#include <ctype.h>
using namespace std;

int main() {
  double m,n;
  cin >> m >> n;
  double answer;
  answer=m/n;
  cout << answer << endl;
  
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys
import io
import re
import math
import itertools
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
#start = time.clock()
ans=chk=0
a=[0,2,5,3]
b=[0,1,5,4]
c=[1,2,4,3]

def rolling(word,dice):
    if word=='S':
        dice[0],dice[1],dice[5],dice[4]=dice[4],dice[0],dice[1],dice[5]
    elif word=='N':
        dice[0],dice[1],dice[5],dice[4]=dice[1],dice[5],dice[4],dice[0]
    elif word=='W':
        dice[0],dice[2],dice[5],dice[3]=dice[2],dice[5],dice[3],dice[0]
    else:
        dice[0],dice[2],dice[5],dice[3]=dice[3],dice[0],dice[2],dice[5]
    return dice

def sortdice(dice1,dice2,p,q,r):
    for i in range(4):
        dice1[p[0]],dice1[p[1]],dice1[p[2]],dice1[p[3]]=dice1[p[1]],dice1[p[2]],dice1[p[3]],dice1[p[0]]
        for j in range(4):
            dice1[q[0]],dice1[q[1]],dice1[q[2]],dice1[q[3]]=dice1[q[1]],dice1[q[2]],dice1[q[3]],dice1[q[0]]
            for k in range(4):
                dice1[r[0]],dice1[r[1]],dice1[r[2]],dice1[r[3]]=dice1[r[1]],dice1[r[2]],dice1[r[3]],dice1[r[0]]
                if dice1==dice2:
                    print 'Yes'
                    exit()
    return 0

l1=map(int,raw_input().split())
l2=map(int,raw_input().split())
sortdice(l1,l2,a,b,c)
print 'No'

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

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;

//少数点表示
//cout <<std::fixed << std::setprecision(14) <<double値

int main(){
    cin.tie( 0 ); ios::sync_with_stdio( false );
    int n;
    cin >> n;
    double ans;
    if(n%2 == 0){
        ans = ((double)n/2)/n;
    }else{
        ans = (n/2+1.0)/n;
    }

    cout <<std::fixed << std::setprecision(10) << ans;


}

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

//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }


//typedef
//------------------------------------------
typedef long long LL;
typedef unsigned long long ULL;


//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())

//repetition
//------------------------------------------
#define REP(n) for(LL i=0; i<n; i++)
#define REPj(n) for(LL j=0; j<n; j++)
#define REPinit(a,n) for(LL i=a; i<n; i++)
#define REPinitj(a,n) for(LL j=a; j<n; j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
//clear memory
//#define CLR(a) memset((a), 0 ,sizeof(a))



int main()
{
	LL N, temp;
	vector<LL> a;
	cin >> N;
	

	REP(N) {
		cin >> temp;
		a.push_back(temp);
	}

	vector<LL> box(a.size(), 0);
	vector<LL> inBall;
	for (LL i = (N - 1); i >= (N / 2); i--) {
		if (a[i] == 1) {
			box[i] = 1;
			inBall.push_back(i);
		}
		else {
			box[i] = 0;
		}
		//cout << i + 1 << " : " << box[i] << endl;
	}

	for (LL i = (N / 2) - 1; i >= 0; i--) {
		LL sum = 0;
		LL num = N / (i + 1);
		for (LL j = 0; j < num; j++) {
			sum += box[(i + 1)*(j + 1) - 1];
		}

		sum = sum % 2;
		if (sum != a[i]) {
			box[i] = 1;
			inBall.push_back(i);
		}
		else {
			box[i] = 0;
		}
		//cout << i + 1 << " : " << box[i] << endl;
	}

	sort(inBall.begin(), inBall.end());

	cout << inBall.size() << endl;
	size_t s = inBall.size();
	for (size_t i = 0; i < s; i++) {
		if (i != (s - 1)) {
			cout << inBall[i]+1 << " ";
		}
		else {
			cout << inBall[i]+1 << endl;
		}
	}

	
	return 0;
}


Measured memory_bytes: 5872
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}


void solve() {
  int n;
  cin >> n;
  vector<int> a(1 << n);
  cin >> a;

  multiset<int> s;
  rep(i, 1 << n) s.insert(a[i]);

  vector<int> v;
  auto it = --s.end();
  v.eb(*it);
  s.erase(it);
  // cout << v << endl;
  // for (auto e : s) cout << e << " "; cout << endl;

  rep(i, n) {
    vector<int> v2;
    for (int vi : v) {
      auto it = s.lower_bound(vi);
      if (it-- == s.begin()) {
        cout << "No" << endl;
        return;
      }
      // cout << *it << endl;
      v2.eb(*it);
      s.erase(it);
      // for (auto e : s) cout << e << " "; cout << endl;
    }
    for (auto v2i : v2) v.eb(v2i);
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 15036
#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

string s;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    cin>>s;
    map<char,int> ma;
    rep(i,s.size()){
        ma[s[i]]++;
    }
    bool ans = true;
    rep(i,s.size()){
        if(ma[s[i]]!=2)ans = false;
    }
    Yes(ans);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100
#define WHITE 0  // 未訪問の頂点
#define GRAY 1  // 訪問した頂点
#define BLACK 2  // 訪問を完了した頂点

int n, M[N][N];
int color[N], d[N], f[N], tt;  // dは最初に訪問した時間，fは最後に訪問した時間

// 再帰関数による深さ優先探索
void dfs_visit(int u)
{
    int v;
    color[u] = GRAY;  // uを訪問したことにする
    d[u] = ++tt;  // 最初の訪問
    for (v = 0; v < n; v++) {
        // uの周りの頂点に関して
        // 未訪問のとき，再帰をして訪問したことにする
        if (M[u][v] == 0) {  // パスがない
            continue;
        }
        if (color[v] == WHITE) {  // 未訪問
            dfs_visit(v);
        }
    }
    // 上の再帰が終了(= uを始点としてすべてのパスを通ったとき)
    // すべての頂点に訪問を完了したら色を黒にする
    color[u] = BLACK;
    f[u] = ++tt;  // 訪問の完了
}

void dfs()
{
    int u;
    // 初期化
    for (u = 0; u < n; u++) {
        color[u] = WHITE;
    }
    tt = 0;

    for (u = 0; u < n; u++) {
        // 未訪問のuを始点として深さ優先探索
        if (color[u] == WHITE) {
            dfs_visit(u);
        }
    }
    for (u = 0; u < n; u++) {
        printf("%d %d %d\n", u + 1, d[u], f[u]);
    }
}

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

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

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

    dfs();

    return 0;
}


Measured memory_bytes: 2740
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    ll N = S.size();
    ll ans = N;
    rep(i,0,N-1){
        if(S[i] != S[i+1]){
            ll v = max(i+1, N - i - 1);
            ans = min(ans, v);
        }
    }
    print(ans);
    

}

Measured memory_bytes: 512
#include <stdio.h>
int main(void){
    char c = fgetc(stdin);
    if(c == 'A'){
        c = 'T';
    }else if(c == 'T'){
        c = 'A';
    }else if(c == 'G'){
        c = 'C';
    }else if(c == 'C'){
        c = 'G';
    }
    printf("%c\n",c);
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;

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

    if (N < 105) {
        cout << 0 << endl;
    }
    else if (105 <= N && N < 135) {
        cout << 1 << endl;
    }
    else if (135 <= N && N < 165) {
        cout << 2 << endl;
    }
    else if (165 <= N && N < 189) {
        cout << 3 << endl;
    }
    else if (189 <= N && N < 195) {
        cout << 4 << endl;
    }
    else {
        cout << 5 << endl;
    }
}

Measured memory_bytes: 256
l,r = map(int,input().split())
value = 2019
if r - l > 2019:
    print(0)
else:
    l1 = l%2019
    r1 = r%2019
    ans = 100000000
    if r1>l1:
        for i in range(l,r):
            for j in range(i+1,r+1):
                if ans>(i*j)%2019:
                    ans = (i*j)%2019
        print(ans)
    else:
        print(0)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
// //clang++ -std=c++11 -stdlib=libc++ 

vi to[104];
int dp[104][104];
int n,m;

int main() {
  cin >> n >> m;
  vector<pair<ii, int>> edges(m);
  rep(i, n)rep(j, n) {
    dp[i][j] = INF;
    dp[i][i] = 0;
  }
  rep(i,m) {
  int a,b,c; cin >> a >> b >> c; a--; b--;
  dp[a][b] = c;
  dp[b][a] = c;
  to[a].push_back(b);
  to[b].push_back(a);
  edges[i] = {ii(a,b), c};
  }
  rep(k, n) rep(i,n) rep(j,n) chmin(dp[i][j], dp[i][k]+dp[k][j]); 
  vector<bool> used(m, false);
  rep(s, n) {
    rep(i, m) {
      int k = edges[i].first.first;
      int t = edges[i].first.second;
      int e = edges[i].second;
      if (dp[s][k] > dp[s][t]) swap(k,t);
      if (dp[s][t] == dp[s][k] + e) used[i] = true;
    }
  }
  ll ans =0;
  rep(i, m) if (!used[i]) ans++;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3624
let rec seq a b = if a > b then [] else a :: seq (a+1) b
let (>>=) x f = List.map f x |> List.concat
let () =
  Scanf.scanf "%d %d" @@ fun n y ->
    (seq 0 n >>= fun i ->
     seq 0 (n-i) >>= fun j ->
       if 10000*i + 5000*j + 1000*(n-i-j) = y then [i, j, n-i-j] else [])
    |> function
      | (i,j,k)::_ -> Printf.printf "%d %d %d\n" i j k
      | [] -> print_endline "-1 -1 -1"

Measured memory_bytes: 5120
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var A = new int[2, N + 1];
            A[0, 0] = 0;
            A[1, 0] = 0;
            for(var i = 0; i < 2; i++)
            {
                var input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
                for(var j = 0; j < N; j++)
                {
                    A[i, j + 1] = A[i, j] + input[j];
                }
            }

            var ans = 0;
            for(var i = 1; i <= N; i++)
            {
                var sum = A[0, i] + A[1, N] - A[1, i - 1];
                if (sum > ans) ans = sum;
            }

            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
  
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}
  
int main()
{
  int i,j,right,third;
  ll tmp;
  int N; cin >> N;
  int L[1001] = {0};
  int LS[1001] = {0};
  ll ans = 0;

  rep(i,N){
      cin >> tmp;
      L[tmp]++;
  }
  LS[0]=0;
  for (int i = 1; i <= 1000; i++){
      LS[i] = LS[i-1] + L[i];
  }

  for (int i = 1; i <= 1000; i++){
    if(L[i]>=3){ans += (ll)(1ll * L[i] * (L[i]-1) * (L[i]-2) / 6);}
  }

  for (int i = 1; i <= 1000; i++){
    ans += L[i] * (L[i] - 1) / 2 * (LS[min(2*i-1,1000)] - L[i]);
  }

  for (int i = 1; i <= 1000; i++){
      if(L[i]<=0){continue;}
      for (int j = i + 1; j <= 1000; j++){
          if(L[j]<=0){continue;}
          right = min(i + j - 1,1000);
          third = LS[right] - LS[j];
          tmp = L[i] * L[j] * third;
          ans += tmp;
      }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
	typedef long long ll;
	#define double long double
	const int INF=0x3f3f3f3f;
	const ll LLINF=0x3f3f3f3f3f3f3f3fll;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void writeln(int num){write(num);puts("");}
	#define FR first
	#define SE second
	#define MP make_pair
	#define pr pair<int,int>
	#define PB push_back
	#define vc vector
	void chmax(int &x,const int y) {x=x>y?x:y;}
	void chmin(int &x,const int y) {x=x<y?x:y;}
	const int MAX_N=5e5+10;
	const int MOD=1e9+7;
	void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}

	int a[MAX_N];
	void main()
	{
		int n=qread(),L=qread();for(int i=1;i<=n;i++) a[i]=qread();
		for(int i=1;i<=n-1;i++) if(a[i]+a[i+1]>=L)
		{
			puts("Possible");
			for(int j=1;j<i;j++) printf("%d\n",j);
			for(int j=n-1;j>=i+1;j--) printf("%d\n",j);
			printf("%d",i);return;
		}
		puts("Impossible");
	}
};
int main()
{
	srand(time(0));
	bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
	lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
	mine::main();
}


Measured memory_bytes: 9472
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();
            var ans = 0;
            for (int i = 0; i < n; i++)
            {
                var l = cin.nextInt();
                var r = cin.nextInt();

                ans += r - l + 1;
            }
            Console.WriteLine(ans);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 11220
#include<bits/stdc++.h>
using namespace std;
#define INF INT_MAX
typedef pair<int, int> P;
int main(void){
	int v, e, r;
	cin >> v >> e >> r;
	int from[e], to[e], cost[e], sum = 0;
	for(int i = 0; i < e; i++) cin >> from[i] >> to[i] >> cost[i];
	int leng[v];
	fill(leng, leng + v, INF);
	leng[r] = 0;
	int i, upd;
	for(i = 0; i < v; i++){
		upd = 0;
		for(int j = 0; j < e; j++){
			int f = from[j], t = to[j], c = cost[j];
			if(leng[f] != INF && leng[t] > leng[f] + c) leng[t] = leng[f] + c, upd = 1;
		}
		if(!upd) break;
	}
	if(i == v && upd) cout << "NEGATIVE CYCLE" << endl;
	else {
		for(int i = 0; i < v; i++){
			if(leng[i] == INF) cout << "INF" << endl;
			else cout << leng[i] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3144
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <utility>
#include <vector>
#define FOR(i,a,b) for (int i=(a),for_##i##_max=(b);i<=(for_##i##_max);++i)
#define RFOR(i,a,b) for (int i=(a),rfor_##i##_min=(b);i>=(rfor_##i##_min);--i)
#define REP(i,n) for (int i=0,rep_##i##_len=(n);i<(rep_##i##_len);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

namespace { // Basics

template<typename T>
void chmin(T &x, T y) {
  x = std::min(x, y);
}

template<typename T>
void chmax(T &x, T y) {
  x = std::max(x, y);
}

template<typename T>
const auto minimum = static_cast<T const &(*)(T const &, T const &)>(std::min);

template<typename T>
const auto maximum = static_cast<T const &(*)(T const &, T const &)>(std::max);

template<typename T>
T constexpr infty = std::numeric_limits<T>::max / 3;
template<>
auto constexpr infty<int> = 1'100'100'100;
template<>
auto constexpr infty<long long int> = 100'500'400'300'200'100LL;

using lli = long long int;
using ld = long double;

} // namespace

using namespace std;

int main() {
  // cout << fixed << setprecision(10);

  string G;
  while (cin >> G && G != "#"s) {
    int Y, M, D; cin >> Y >> M >> D;
    int yymmdd = 10000 * Y + 100 * M + D;
    if (yymmdd >= 310501) {
      G = "?";
      Y -= 30;
    }
    cout << G << " " << Y << " " << M << " " << D << endl;
  }
  return 0;
}



Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>G;
long long ans[200200];
void dfs(int v,int prev,long long S){
    ans[v]=S+ans[v];
    for(auto nx:G[v]){
        if(nx==prev)continue;
        dfs(nx,v,ans[v]);
    }
}
int main()
{
    int N,Q;
    cin >> N >> Q;
    for(int i=0;i<N;i++){
        G.push_back(vector<int>());
    }
    for(int i=0;i<N-1;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=0;i<Q;i++){
        int p;
        long long x;
        cin >> p >> x;
        ans[p-1]+=x;
    }
    dfs(0,-1,0);
    for(int i=0;i<N;i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 25324
#include <iostream>
#include <cmath>

using namespace std;


int main()
{
	int a, b, c;

	cin >> a >> b >> c;

	if (a != b && a != c)
		cout << a << endl;

	if (b != a && b != c)
		cout << b << endl;

	if (c != b && c != a)
		cout << c << endl;


    return 0;
}



Measured memory_bytes: 256
from collections import deque
from copy import deepcopy

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

def BFS(m):
  t_l=deepcopy(l)
  del t_l[m]

  tree=[[] for j in range(n)]
  for a,b in t_l:
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

  dist=[-1 for i in range(n)]
  dist[0]=0

  que=deque()
  que.append(0)

  while que:
    x=que.popleft()
    for i in tree[x]:
      if dist[i]==-1:
        que.append(i)
        dist[i]=dist[x]+1

  global ans
  if -1 in dist:
    ans+=1

ans=0
for i in range(m):
  BFS(i)

print(ans)

Measured memory_bytes: 3572
x,y,z,k=map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort(key=lambda x: -x)
c.sort(key=lambda x: -x)
ans=[]
ct=[0]
ansc=[ab[0]+c[0]]
while (len(ans)<k):
    if(ct[-1]!=0 and len(ct)<z):
        ansc+=[ab[0]+c[len(ct)]]
        ct+=[0]
    ans+=[max(ansc)]
    tmp=ansc.index(max(ansc))
    if(ct[tmp]==len(ab)-1):
        ansc[tmp]=0
    else:
        ct[tmp]+=1
        ansc[tmp]=ab[ct[tmp]]+c[tmp]
for i in ans:
    print(i)

Measured memory_bytes: 99816
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
map<string ,int> mp;
const int maxn=10000;
string a[maxn];
int main()
{
	int n;
	scanf("%d",&n);
	bool sign1=false;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
		if(mp[a[i]]>1)
			sign1=true;
	}
	for(int i=0;i<n-1;i++)
	{
		int len=a[i].size();
		if(a[i][len-1]!=a[i+1][0]){
			sign1=true;break;
		}
	}
	if(sign1)
		puts("No");
	else	
		puts("Yes");
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    string s;
    int n,a,b,c,d,m;
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int N,i;
	scanf("%d",&N);
	int A[N];
	int ans[N];
	for(i=1;i<N+1;i++){
		scanf("%d",&A[i]);
	}
	for(i=1;i<N+1;i++){
		ans[A[i]]=i;
	}
	for(i=1;i<N+1;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
class Restaurant {
public:
    Restaurant(int serialNumber, string cityName, int score) : m_serialNumber(serialNumber), m_cityName(cityName), m_score(score) {
    }
    int getSerialNumber() const {
        return m_serialNumber;
    }
    string getCityName() const {
        return m_cityName;
    }
    int getScore() const {
        return m_score;
    }
private:
    const int m_serialNumber;
    const string m_cityName;
    const int m_score;
};
 
bool lexicalOrder(const Restaurant* front, const Restaurant* back);
 
int main() {
    int numOfRestaurant;
    cin >> numOfRestaurant;
    
    vector<Restaurant*> guideBook;
    string cityName;
    int score;
    for (int i = 1; i <= numOfRestaurant; ++i) {
        cin >> cityName >> score;
        guideBook.push_back(new Restaurant(i, cityName, score));
    }
    
    sort(guideBook.begin(), guideBook.end(), lexicalOrder);
    
    for (Restaurant* restaurant : guideBook) {
        cout << restaurant->getSerialNumber() << endl;
    }
 
    for (Restaurant* restaurant : guideBook) {
        delete restaurant;
    }  
    
}
 
bool lexicalOrder(const Restaurant* front, const Restaurant* back) {
    if (front->getCityName() == back->getCityName()) {
        return front->getScore() > back->getScore();
    } else {
        return front->getCityName() < back->getCityName();
    }
}

Measured memory_bytes: 3572
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, w = IN()
	#s = input()
	dp = [-1]*(w+1)
	dp[0]=0
	for _ in range(n):
		wi, vi = IN()
		for ri, v in enumerate(dp[::-1]):
			i=len(dp)-ri-1
			#print(i)
			if i + wi > w:
				continue
			if dp[i] >= 0:
				dp[i + wi] = max(dp[i+wi], dp[i]+vi)
		#print(dp)
	ret = max(dp)
	return ret
				
			
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    s = 0
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            s += 1
            if s >= n:
                break
            unite(a,b)
    print(ans)
    return

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


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

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define NCK_MAX 510000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main(int argc, char const *argv[]) {
	int s, w; std::cin >> s >> w;
	if (s > w) std::cout << "safe" << '\n';
	else std::cout << "unsafe" << '\n';
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,dp[100010],h;
    vector<int> a;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> h;
        a.emplace_back(h);
    }

    dp[1] = abs(a[0]-a[1]);
    for(int i=1;i<n;i++){
        dp[i+1] = min(dp[i-1]+abs(a[i-1]-a[i+1]),dp[i]+abs(a[i]-a[i+1]));
    }

    cout << dp[n-1] << endl;

    return 0;

}

Measured memory_bytes: 1144
#include <cstdio>
#include <queue> 

using namespace std;

#define EMPTY '.'
#define OBSTACLE 'X'
#define INF 0x7fffffff

typedef pair<int, int> Coor;

int h, w, n;
char map[1000][1000];
int cost[1000][1000];

int bfs(Coor start, Coor end) {
    queue<Coor> q;

    fill((int*)cost, (int*)(((char*)cost)+sizeof(cost)), INF);

    cost[start.second][start.first] = 0;
    q.push(start);
    while (!q.empty()) {
        Coor c = q.front();q.pop();
        int x = c.first;
        int y = c.second;
        int dx[] = {-1,  0, 1, 0};
        int dy[] = { 0, -1, 0, 1};

        for (int i=0; i<4; i++) {
            int x2 = x + dx[i];
            int y2 = y + dy[i];

            if (x2 < 0 || w <= x2 || y2 < 0 || h <= y2) continue;
            if (map[y2][x2] == 'X') continue;
            if (cost[y2][x2] != INF) continue;

            cost[y2][x2] = cost[y][x] + 1;
            if (make_pair(x2, y2) == end) return cost[y2][x2];
            q.push(make_pair(x2, y2));
        }
    }
}

int main() {
    Coor start[10];
    unsigned int sum = 0;
 
    scanf("%d %d %d", &h, &w, &n);
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            char c;
 
            scanf(" %c", &c);
            if (c == 'S') {
                start[0].first = j;
                start[0].second = i;
            } else if (c != 'X' && c != '.') {
                int ind = c - '0';
                start[ind].first = j;
                start[ind].second = i;
            }

            map[i][j] = c;
        }
    }

    for (int i=0; i<n; i++) {
        sum += (unsigned int)bfs(start[i], start[i+1]);
    }            

    printf("%u\n", sum);
}

Measured memory_bytes: 5932
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <utility>
#include <set>
#include <bitset>
#include <vector>
#define pi acos(-1.0)
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fLL
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int min3(int a,int b,int c)
{
    return min(min(a,b),c);
}
int max3(int a,int b,int c)
{
    return max(max(a,b),c);
}
int gcd(int x, int y)
{
    if(y==0)return x;
    return gcd(y, x%y);
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn = 5e5+5;
int dir[4][2] = {0,1,0,-1,-1,0,1,0};

ll n,m;
ll ans;
char s[405][405];
ll p[maxn],cnt[maxn],vis[maxn];
ll change(ll x,ll y)
{
    return x*450+y;
}
ll Find(ll x)
{
   return x == p[x]?x:p[x] = Find(p[x]);

}
void join(ll x,ll y)
{
    x = Find(x),y = Find(y);
    if(x!=y)
    {
        p[x] = y;
        cnt[y] += cnt[x];
        vis[y] += vis[x];
    }
}
void init()
{
    for(int i=0; i<maxn; i++)
    {
        p[i] = i;
        cnt[i] = 1;
    }
}
int main()
{
    init();
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%s",s[i]+1);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(s[i][j] == '#')
                vis[change(i,j)] = 1;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            for(int k=0; k<4; k++)
            {
                int x = i+dir[k][0];
                int y = j+dir[k][1];
                if(x>0 && x<=n && y>0 && y<=m && s[i][j]!=s[x][y])
                {
                    join(change(x,y),change(i,j));
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            ll xx = Find(change(i,j));
            if(cnt[xx]>1)
            {
                ans += vis[xx]*(cnt[xx]-vis[xx]);
                cnt[xx] = 0;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 11520
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
    return ret


from collections import deque
S = deque(read()[:-1])
Q = read_a_int()


is_flip = 0  # 0は反転してない
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        is_flip = 1 - is_flip
    else:
        _, f, c = q
        f = int(f)
        if is_flip:
            if f == 1:
                S.append(c)
            else:
                S.appendleft(c)
        else:  # flipしてないときは通常の処理
            if f == 1:
                S.appendleft(c)
            else:
                S.append(c)

if is_flip:
    print(''.join(S)[::-1])
else:
    print(''.join(S))


Measured memory_bytes: 8796
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
const double PI=acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

void solve(){
    int n; cin >> n;
    map<char, int> mp;
    REP(i, n){
        char c;
        cin >> c;
        mp[c]++;
    }
    if(mp.size()==3) cout << "Three" << endl;
    else cout << "Four" << endl;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000
#define MAX_M 100000
const int INF = 1e9;
#define PI 3.141592653589793

int main(){
  cout << setprecision(15) << std::fixed;
  int n,k;
  double ans=0;
  cin>>n>>k;
  for(int i=1;i<=n;i++){
    double ret=1.0/n;
    int now=i;
    while(now<k){
      now*=2;
      ret/=2;
    }
    ans+=ret;
  }
  cout<<ans<<endl;
}

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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

map<int,int> mapka;
int alfa = 'z' - 'a' + 1;

int daj(int x){
  auto xxx = mapka.find(x);
  if(xxx == mapka.end())return 1e9;
  debug(x,xxx->SE);
  return xxx->SE;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  string z;
  cin >> z;
  int n = SZ(z);
  mapka[0] = 0;
  int ak = 0;
  R(i,n){
    
    
    debug("--------------");
    ak ^= (1 << (z[i] - 'a'));
    int res = daj(ak);
    R(j,alfa){
      mini(res, daj(ak ^ (1 << j)));
    }
    res++;
    debug(i,res,ak);
    if(i == n-1){
      cout << res << "\n";
    }else{
      debug(ak,res);
      mini(res,daj(ak));
      mapka[ak] = res;
    }
  }
}


Measured memory_bytes: 12948
main = do
    ss <- getLine
    let hw = map (\x -> read x :: Int) $ words ss
    let h = hw!!0
    let w = hw!!1
    if (h==0 && w==0)
        then return ()
        else do
            draw h w
            main

draw h w = do
    drawFrame 1 h w
    
drawFrame i h w = do
    let line = if (i==1) || (i==h)
                   then replicate w '#'
                   else "#" ++ replicate (w-2) '.' ++ "#"
    putStrLn line
    if i==h
        then putStrLn ""
        else drawFrame (i+1) h w


Measured memory_bytes: 4084