akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

int main() {
    std::vector<long long> cost(4);
    std::cin >> cost[0] >> cost[1] >> cost[2] >> cost[3];
    cost[0] *= 4;
    cost[1] *= 2;
    long long smallMin = std::min(cost[0], std::min(cost[1], cost[2]));
    long long ans = 0;
    long long n;
    std::cin >> n;
    if (n < 2) {
        std::cout << n * smallMin;
    }
    else {
        if (n % 2 == 0) {
            std::cout << (n * std::min(cost[3], smallMin * 2)) / 2;
        } else {
            std::cout << ((n - 1) * std::min(cost[3], smallMin * 2)) / 2 + smallMin;
        }
    }
}

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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7



int main()
{
	int N;
	string s;
	cin >> N >> s;
	reverse(s.begin(), s.end());
	vector<vector<int>> dp(N, vector<int>(2));
	if (s.front() == '#') {
		dp[0][1] = 1;
	}
	else {
		dp[0][0] = 1;
	}
	REP(i, N - 1) {
		if (s[i + 1] == '#') {
			dp[i + 1][0] = dp[i][0];
			dp[i + 1][1] = min(dp[i][0] + 1, dp[i][1] + 1);
		}
		else {
			dp[i + 1][0] = dp[i][0] + 1;
			dp[i + 1][1] = min(dp[i][0], dp[i][1]);
		}
	}
	cout << min(dp.back()[0], dp.back()[1]) << endl;
	return 0;
}


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

int main() {
    int n;
    std::cin >> n;
    std::vector<int> costs(n, 0);
    std::vector<int> values(n, 0);

    
    for (int i = 0; i < n; i++) {
        std::cin >> values[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> costs[i];
    }
    int s = 0;
    
    for (int i = 0; i < n; i++) {
        if (values[i] - costs[i] >= 1) {
            s += (values[i] - costs[i]);
        }
    }
    
    std::cout << s << std::endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>

using namespace std;

class Counting {
	unsigned long long p, n;
	vector<long long> invMemo, facMemo, facInvMemo;
public:
	Counting(unsigned long long nn, unsigned long long np) {
		p = np;
		n = nn;
		invMemo.resize(n + 1);
		facMemo.resize(n + 1);
		facInvMemo.resize(n + 1);
		facMemo[0] = 1;
		facMemo[1] = 1;
		facInvMemo[0] = 1;
		facInvMemo[1] = 1;
		invMemo[0] = 0;
		invMemo[1] = 1;
		for (unsigned long long i = 2; i <= n; i++) {
			invMemo[i] = p - (p / i)*invMemo[p%i] % p;
			facMemo[i] = (facMemo[i - 1] * i) % p;
			facInvMemo[i] = (facInvMemo[i - 1] * invMemo[i]) % p;
		}
	}
	unsigned long long fac(unsigned long long k) {
		return facMemo[k];
	}
	unsigned long long facInv(unsigned long long k) {
		return facInvMemo[k];
	}
	unsigned long long choose(unsigned long long n, unsigned long long k) {
		if (!(0 <= k && k <= n))
			return 0;
		return (((facMemo[n] * facInvMemo[k]) % p)*facMemo[n - k]) % p;
	}
	unsigned long long divide(unsigned long long a, unsigned long long b) {
		return (a * invMemo[b]) % p;
	}
	unsigned long long mod(unsigned long long a) {
		a %= p;
		if (a < 0) a += p;
		return a;
	}
	unsigned long long power(unsigned long long a, unsigned long long e) {
		unsigned long long ans = 1;
		for (; e > 0; e /= 2) {
			if (e % 2 != 0)
				ans = ans * a % p;
			a = a*a%p;
		}
		return ans;
	}
};


int n;
int p[1000] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191 ,193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257 ,263, 269, 271, 277, 281, 283, 293 ,307 ,311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523 ,541 ,547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607, 613, 617, 619, 631, 641, 643, 647, 653 ,659 ,661 ,673 ,677 ,683 ,691 ,701, 709, 719, 727, 733 ,739, 743, 751, 757, 761, 769 ,773 ,787, 797 ,809 ,811, 821 ,823 ,827 ,829 ,839 ,853, 857 ,859 ,863 ,877 ,881, 883 ,887 ,907 ,911 ,919 ,929 ,937 ,941, 947 ,953 ,967, 971, 977, 983, 991, 997 };
vector<long long> a;
long long ans = 1;
Counting c(1, 1000000007);

int main() {
	cin >> n;
	for (int i = 0; i < 888; i++) {
		if (p[i] == 0) {
			break;
		}
		a.push_back(1);
	}
	//for (int i = 2; i <= n; i++) {
		bool b = true;
		for (int j = 0; j < 999; j++) {
			if (p[j] == 0) {
				break;
			}
			for (int nn = n; nn >= 2; nn/=p[j]) {
				a[j] += nn / p[j];
			}
		}
	//}
	for (int i = 0; i < a.size(); i++) {
		ans = (ans * a[i]) % 1000000007;
	}
	cout << ans << endl;
	//cin >> n;
	return 0;
}

Measured memory_bytes: 256
//Name-Deepesh Bhatt
//Institute-IIT Dhanbad

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

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll lcm(ll a ,ll b)
{
    return a/gcd(a,b)*b;
}
ll power(ll a, ll n, ll m)
{
    if (n == 0)
        return 1;
    ll p = power(a, n / 2, m);
    p = (p * p) % m;
    if (n % 2)
        return (p * a) % m;
    else
        return p;
}
ll combination(ll x)
{
    if(x==0||x==1)
        return 0;
    return (x*(x-1))/2;
}
int main()
{
    ios_base::sync_with_stdio(false);    //for fast I/O operation
    cin.tie(NULL);
    ll k,n;
    cin>>k>>n;
    ll a[n];
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    ll clock=abs((a[n-1]-a[0]));
    ll anti=abs(k-abs(a[0]-a[1]));
    ll m=min(clock,anti);
    for(ll i=1;i<n-1;i++)
    {
        clock=abs(k-abs(a[(i+n-1)%n]-a[i]));
        anti=abs(k-abs(a[i]-a[(i+1)%n]));
        if(m>min(clock,anti))
            m=min(clock,anti);
    }
    clock=abs(k-abs(a[(n-1+n-1)%n]-a[n-1]));
    anti=abs((a[n-1]-a[0]));
    if(m>min(clock,anti))
        m=min(clock,anti);
    cout<<m;
    return 0;
}

Measured memory_bytes: 1792
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, x int
	fmt.Scan(&N, &x)
	a := make([]int, N)
	for i := range a {
		fmt.Scan(&a[i])
	}
	sort.Ints(a)
	cnt := 0
	for i, v := range a {
		if v > x {
			continue
		} else {
			cnt++
			x -= v
		}
		if i == (N-1) && x > 0 {
			cnt--
		}
	}
	fmt.Println(cnt)
}


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


int main()
{
	char str[100];
	int i,flag=1;
	map<char,int> data;
	
	scanf("%s",str);
	
	for(i=0;i<strlen(str);i++)
	{
		data[str[i]]++;
	}
	
	for(i='a';i<'z';i++)
	{
		if(data[i]>1)
		{
			flag = 0;
			break;
		}
	} 
	
	if(flag == 1) cout << "yes";
	else cout << "no";
	
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;

int main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];
    ll a,b;
    vector<ll> nmax(n,0);
    rep(i,m){
        cin>>a>>b;
        a--; b--;
        nmax[a]=max(nmax[a],h[b]);
        nmax[b]=max(nmax[b],h[a]);
    }
    ll ans=0;
    rep(i,n) ans+=(h[i]>nmax[i]);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4780
#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 = 5e3+10;

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

int A[MAXN];
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>>k;

    a = b = 0;

    for(int i=1;i<=n;i++){
        if(((i<<1)%k)==0){
            if(i%k)a++;
            else b++;
        }
    }

    ll res = 1LL*a*a*a+1LL*b*b*b;

    cout<<res<<"\n";

    return 0;
}


Measured memory_bytes: 3644
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String b = getString(sc);

		switch (b) {
		case "A":
			System.out.println("T");
			break;
		case "C":
			System.out.println("G");
			break;
		case "G":
			System.out.println("C");
			break;
		case "T":
			System.out.println("A");
			break;
		}

	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
// Begin Header {{{
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const double PI = acos(-1);
using namespace std;
using Graph = vector<vector<lli>>;
using P = pair<int, int>;
// }}} End Header

int main(){
	vector<vector<int>> a(3, vector<int>(3));
	rep(i,3){
		rep(j,3){
			cin >> a[i][j];
		}
	}
	int n;
	cin >> n;
	rep(t,n){
		int b;
		cin >> b;
			rep(i,3){
				rep(j,3){
					if(a[i][j] == b){
						a[i][j] = -1;
					}
				}
			}
	}
	bool ans = false;
	if(a[0][0] == -1 && a[0][1] == -1 && a[0][2] == -1) ans = true;
	if(a[1][0] == -1 && a[1][1] == -1 && a[1][2] == -1) ans = true;
	if(a[2][0] == -1 && a[2][1] == -1 && a[2][2] == -1) ans = true;
	if(a[0][0] == -1 && a[1][0] == -1 && a[2][0] == -1) ans = true;
	if(a[0][1] == -1 && a[1][1] == -1 && a[2][1] == -1) ans = true;
	if(a[0][2] == -1 && a[1][2] == -1 && a[2][2] == -1) ans = true;
	if(a[0][0] == -1 && a[1][1] == -1 && a[2][2] == -1) ans = true;
	if(a[0][2] == -1 && a[1][1] == -1 && a[2][0] == -1) ans = true;
	if(ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main(){
	char a[4][4];
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			scanf(" %c",&a[i][j]);
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		if(i==j)printf("%c",a[i][j]);
		printf("\n");
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		double a,b,c,d;

		Scanner sc = new Scanner(System.in);

		a = sc.nextDouble();
		b = sc.nextDouble();
		c = sc.nextDouble();
		d = sc.nextDouble();

		double sum = a * b / 2;
		int ans = 0;

		if (a/2 == c && b/2 == d) {
			ans = 1;
		}

		System.out.println(sum + " " + ans);


	}
}


Measured memory_bytes: 23252
import math
import itertools
N = int(input())
towns = [list(map(int, input().split())) for _ in range(N)]
seqs = list(itertools.permutations(range(N)))
length = 0
for seq in seqs:
    for i in range(1, N):
        x_s = towns[seq[i-1]][0]
        x_e = towns[seq[i]][0]
        y_s = towns[seq[i-1]][1]
        y_e = towns[seq[i]][1]
        length += math.sqrt((x_e-x_s)**2+(y_e-y_s)**2)
print(length/len(seqs))

Measured memory_bytes: 8052
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cctype>
#include <ctime>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#ifndef M_PI
    #define M_PI 3.14159265358979323846
#endif

#define mp make_pair
#define mt make_tuple
#define fr first
#define sc second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;
typedef tuple<long long, long long, long long> tlll;
typedef tuple<int, int, int> tiii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int INF = 1000000007;
const double eps = 0.000001;
const int SZ = 100;
char a[100][100];
int c[(int)'z' + 1];

int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int h, w;
    cin >> h >> w;
    char ch;
    fill(c, c + (int)'z' + 1, 0);
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
        {
            cin >> ch;
            c[(int)ch]++;
        }

    int cn4 = ((h - 1) / 2 + 1) * ((w - 1) / 2 + 1);
    int cn2 = 0, cn1 = 0;
    if (w % 2 == 1 && h % 2 != 1)
    {
        cn4 -= (h - 1) / 2 + 1;
        cn2 += (h - 1) / 2 + 1;
    }
    else if (w % 2 != 1 && h % 2 == 1)
    {
        cn4 -= (w - 1) / 2 + 1;
        cn2 += (w - 1) / 2 + 1;
    }
    else if (w % 2 == 1 && h % 2 == 1)
    {
        cn4 -= (h - 1) / 2 + 1 + (w - 1) / 2;
        cn2 += (h - 1) / 2 + (w - 1) / 2;
        cn1 += 1;
    }

    for (int i = 0; i < cn4; i++)
    {
        int cn = 4;
        auto in = max_element(c, c + (int)'z' + 1) - c;
        c[in] -= cn;
        if (c[in] < 0)
        {
            cout << "No" << endl; return 0;
        }
    }

    for (int i = 0; i < cn2; i++)
    {
        int cn = 2;
        auto in = max_element(c, c + (int)'z' + 1) - c;
        c[in] -= cn;
        if (c[in] < 0)
        {
            cout << "No" << endl; return 0;
        }
    }

    for (int i = 0; i < cn1; i++)
    {
        int cn = 1;
        auto in = max_element(c, c + (int)'z' + 1) - c;
        c[in] -= cn;
        if (c[in] < 0)
        {
            cout << "No" << endl; return 0;
        }
    }



    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int k, x, y; cin >> k >> x >> y;
	
	if(k % 2 == 0 && (x + y) % 2){
		cout << "-1" << endl;
		return 0;
	}
	
	vector<pi> res;
	int cx = 0, cy = 0;
	while(cx != x || cy != y){
		int d = abs(cx - x) + abs(cy - y);
		if(d == k){
			cx = x; cy = y;
		}
		else if(d >= 2 * k || d % 2){
			int dx = min(k, abs(cx - x)), dy = k - dx;
			cx += cx < x ? dx : -dx;
			cy += cy < y ? dy : -dy;
		}
		else {
			int tx = cx + (cx < x ? k : -k);
			int nd = abs(tx - x) + abs(cy - y);
			if(nd >= k){
				int dy = (nd - k) / 2;
				int dx = k - dy;
				cx += cx < x ? dx : -dx;
				cy += cy < y ? dy : -dy;
			}
			else{
				int ty = cy + (cy < y ? k : -k);
				int nd = abs(cx - x) + abs(ty - y);
				
				int dx = (nd - k) / 2;
				int dy = k - dx;
				cx += cx < x ? dx : -dx;
				cy += cy < y ? dy : -dy;
			}
		}
		res.emplace_back(cx, cy);
	}
	
	cout << res.size() << endl;
	for(pi p : res) cout << p.first << " " << p.second << endl;
	return 0;
}

Measured memory_bytes: 3952
#include "bits/stdc++.h"
#include <boost/multi_array.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/numeric.hpp>
#include <boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
using index_t = std::size_t;

namespace lib
{
	using graph_t = std::vector<std::set<index_t>>;
	template<class T>using weighted_graph_t = std::vector<std::map<index_t, T>>;
	template<class T>using pair = std::pair<T, T>;

	struct max_t
	{
		template<class T>constexpr T operator()(T const& lhs, T const& rhs)const
		{
			return std::max(lhs, rhs);
		}
	};
	struct min_t
	{
		template<class T>constexpr T operator()(T const& lhs, T const& rhs)const
		{
			return std::min(lhs, rhs);
		}
	};

	constexpr max_t max;
	constexpr min_t min;

	template<class T>auto order_by(T func)
	{
		return [=](auto&& lhs, auto&& rhs)
		{
			return func(lhs) < func(rhs);
		};
	}

	template<class T>constexpr auto max_v = std::numeric_limits<T>::max();
	template<class T>constexpr auto min_v = std::numeric_limits<T>::min();

	template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;
	
	template<class T>constexpr T pow(T val, std::uint64_t p)
	{
		auto ret = T(1);
		auto s = 1ULL;
		for (auto i = 0; i < 63; ++i, s <<= 1)
		{
			if (p & s)
			{
				ret *= val;
			}
			val *= val;
		}
		return ret;
	}
}

class union_find
{
	mutable std::vector<std::optional<index_t>> parent;
	std::vector<index_t> rank, elem;
	std::set<index_t> tops;
	std::size_t sz;
public:
	union_find(std::size_t N) :parent(N), rank(N), elem(N, 1), tops(), sz(N)
	{
		for (index_t i = 0; i < N; ++i)
		{
			tops.emplace(i);
		}
	}
	index_t find(index_t a)const
	{
		if (!parent[a])
		{
			return a;
		}
		else
		{
			return *(parent[a] = find(*parent[a]));
		}
	}
	void merge(index_t a, index_t b)
	{
		auto x = find(a);
		auto y = find(b);
		if (x != y)
		{
			--sz;
			if (rank[x] < rank[y])
			{
				tops.erase(x);
				parent[x] = y;
				elem[y] += elem[x];
			}
			else if (rank[y] < rank[x])
			{
				tops.erase(y);
				parent[y] = x;
				elem[x] += elem[y];
			}
			else
			{
				tops.erase(y);
				parent[y] = x;
				elem[x] += elem[y];
				++rank[x];
			}
		}
	}
	std::size_t size(std::optional<index_t> index = std::nullopt)const
	{
		return index ? elem[find(*index)] : sz;
	}
	auto begin()const
	{
		return tops.begin();
	}
	auto end()const
	{
		return tops.end();
	}
};

void Main()
{
	std::size_t N, M;
	std::cin >> N >> M;
	union_find uf(N);
	for (auto _ : boost::irange(M))
	{
		index_t a, b;
		std::cin >> a >> b;
		--a; --b;
		uf.merge(a, b);
	}
	std::cout << uf.size() - 1 << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

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

using namespace std;

using ll = long long;

const int C = 26, mod = 1e9+7; int n, g[C]; string s; ll m = 1;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr), cin >> n >> s;

    for (auto c: s)
        g[c-'a']++;

    for (int i = 0; i < C; ++i)
        if (g[i])
            m *= ll(g[i]+1), m %= mod;

    cout << m-1;
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

const long long int mod=1000000007;
const long long int INF=99999999999999999;

long long int n,res=0,cou=0,y,m,d;
queue<pair<long long int,long long int> >que;
string str[1100],strtmp;
int main() {
	cout << fixed << setprecision(10);
    cin>>m>>d;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=d;j++){
			if(j%10>=2&&j/10%10>=2&&(j%10)*(j/10%10)==i){
				res++;
			}
		}
	}
	cout<<res<<endl;





} 


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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import sys
n = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
min = 0
for k in li:
    min += (k-1) ** 2
i = 2
while i <= 100:
  s = 0
  for k in li:
    s += (k-i) ** 2
  if s < min:
    min = s
  i += 1
print(min)
    


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
using namespace std;

ll n,m,ar[N],sum,t,dp[N],vis[N],pref[N],pref2[N],mn=-1e18;


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

	fs(ar,n);
	fo(i,1,n)
	if(ar[i]>0)
		sum+=ar[i];
	fo(i,1,n)
	{
		pref[i]=pref[i-1];
		pref2[i]=pref2[i-1];
		if(ar[i]>0)
			pref[i]-=ar[i];
		else
			pref2[i]+=ar[i];
	}
	fo(i,m,n)
	{
		mn=max(mn,pref[i]-pref[i-m]);
		mn=max(mn,pref2[i]-pref2[i-m]);
	}
	// for(int i=1;i<=n;i++)
	// 	cout<<pref[i]<<sp;
	// cout<<endl;
	// for(int i=1;i<=n;i++)
	// 	cout<<pref2[i]<<sp;
	// cout<<endl;
	// cout<<mn<<endl;
	cout<<sum+mn<<endl;
	// ll a=0;
	// ll b=0;

}



/*     cd onedrive\desktop\kod
cls

Sinav:21-22 aralik
Aciklama: Muhtemelen 25 aralik
*/

Measured memory_bytes: 7168
n = int(input())
h = list(map(int, input().split()))

dp = [0] * n
dp[0] = 0
for i in range(1, n):
    if i - 2 < 0:
        dp[i] = dp[i-1] + abs(h[i] - h[i-1])
    else: 
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))

print(dp[n-1])
        

Measured memory_bytes: 20544
function Main(input) {
  const numbers = input.split(' ');
  for (var i=0; i<numbers.length; i++) {
    if (numbers[i] == 0) {
      const ans = i + 1;
      console.log(ans.toString());
      break;
    }
  }
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 30612
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double lld;
ll MOD = (1e9)+7;
inline void fastIO(){
    ios_base::sync_with_stdio(0);cin.tie(0);
}

int main(){
   int n,maxx=0;
   cin>>n;
   map<string,int>rep;
   for(int i=0;i<n;i++){
     string s;
     cin>>s;
     rep[s]++;
     maxx=max(maxx,rep[s]);
   }
   vector<string>ans;
   map<string,int>::iterator it;
   for(it=rep.begin();it!=rep.end();++it){
        int t=it->second;
        string s=it->first;
        if(t==maxx){
            ans.push_back(s);
        }
   }
   sort(ans.begin(),ans.end());
   for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<endl;
   }
}
// - VERIFICAR LONG VS INT -


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

typedef long long ll;
typedef pair<int, int> P;

#define pb push_back
#define in ,
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

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

  if(a > 0) cout << "Positive" << endl;
  else if(a <= 0 && b >= 0) cout << "Zero" << endl;
  else {
    if((abs(a) - abs(b)) % 2 == 0) {
      cout << "Negative" << endl;
    }else {
      cout << "Positive" << endl;
    }
  }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
ll INF = 214748364700000000;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

int main(){
   ll N;cin >> N;
   vector<ll> A(N);
   rep(i,N) cin >> A[i];
   ll GCD = A[0];
   rep(i,N) GCD = __gcd(A[i],GCD);
   cout << GCD << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
using namespace std;
int n,m,i,j,vis[200005],a[200005];
int main()
{
	scanf("%d%d",&n,&m);
	if(m==1||m==n+n-1){
		puts("No");
		return 0;
	}
	puts("Yes");
	if(m!=2){
		a[n]=m;
		a[n+1]=n*2-1;
		a[n-1]=1;
		a[n+2]=2;
		vis[m]=vis[n*2-1]=vis[1]=vis[2]=1;
		j=1;
		fz1(i,n*2-1)if(!a[i]){
			while(vis[j])j++;
			vis[j]=1;a[i]=j;
		}
	}
	else{
		a[n]=m;
		a[n+1]=1;
		a[n-1]=n*2-1;
		a[n+2]=n*2-2;
		vis[m]=vis[1]=vis[n*2-1]=vis[n*2-2]=1;
		j=1;
		fz1(i,n*2-1)if(!a[i]){
			while(vis[j])j++;
			vis[j]=1;a[i]=j;
		}
	}
	fz1(i,n*2-1){
		printf("%d ",a[i]);
	}
	return 0;
}

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

#define ll long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define ep emplace_back
int main(void) 
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie();
	int n; 
	cin >> n;
	bool flag = false; 
	for (int i=1; i<=9; i++) 
	{
		int a = i; 
		if (n%a==0) 
		{
			int b = n/a; 
			if (b>=1 && b<=9)
			{
				//cout << "a:"<<a<<" " << "b:"<<b<<"\n";
				flag = true; 
				break;
			}
		}
	}
	if (flag) cout << "Yes\n";
	else cout << "No\n";

		

	return false; 
}




Measured memory_bytes: 256
fn main() {
    proconio::input! {
        n: usize,
        s: usize,
        a: [usize;n],
    }
    let mut dp = vec![[0;3];s+1];
    dp[0][0]=1;
    for a in a {
        for i in (0..=s).rev() {
            let mut v: usize=dp[i][0..3].iter().sum();
            for w in dp[i][0..3].iter_mut().rev() {
                v-=*w;
                *w=(*w+v)%MOD;
            }
            if i>=a {
                let v: usize=dp[i-a][0..2].iter().sum();
                for w in dp[i][1..3].iter_mut() {
                    *w=(*w+v)%MOD;
                }
            }
        }
    }
    println!("{}",dp[s][2]);
}
const MOD: usize=998244353;

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

int main() {
  int n; cin >> n;
  vector<pair<string, int>> p(n);
  vector<pair<string, int>> p0(n);
  for (int i=0; i<n; i++){
    cin >> p.at(i).first >> p.at(i).second;
    p0.at(i).first = p.at(i).first;
    p0.at(i).second = p.at(i).second;
  } // pairの列をpに格納。初期値をp0にコピー
  
  sort(p.begin(), p.end());
  // 辞書順早い順、点数低い順
  
  int same = 0;
  string cache1 = "";
  int cache2 = -1;
  for (int i=0; i<n; i++){
    if (i == 0){
      cache1 = p.at(i).first;
      same++;
      continue;
    }
    if (i == n-1){
      if (p.at(i).first == cache1){
        same++;
        for (int j=0; j<same/2; j++){
          cache2 = p.at(i-j).second;
          p.at(i-j).second = p.at(i-same+j+1).second;
          p.at(i-same+j+1).second = cache2;
        }
        continue;
      }
      else if (same>1){
        for (int j=0; j<same/2; j++){
          cache2 = p.at(i-1-j).second;
          p.at(i-1-j).second = p.at(i-same+j).second;
          p.at(i-same+j).second = cache2;
        }
        continue;
      }
    }
    if (p.at(i).first == cache1){
      same++;
      continue;
    }
    else{
      for (int j=0; j<same/2; j++){
        cache2 = p.at(i-1-j).second;
        p.at(i-1-j).second = p.at(i-same+j).second;
        p.at(i-same+j).second = cache2;
      }
      same = 1;
      cache1 = p.at(i).first;
    }
  } // 辞書早い順、点数低い順になったはず
  
  for (int i=0; i<n; i++){
    for (int j=0; j<n; j++){
      if (p.at(i) == p0.at(j)){
        cout << j+1 <<endl;
      }
    }
  }
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000)

def input():
    return sys.stdin.readline()[:-1]
n = int(input())
l = list(map(int, input().split(" ")))
output = 1

if 0 in l:
    print(0)
    sys.exit()

for i in range(n):
    output = output * int(l[i])
    if output > 10 ** 18:
        output = -1
        break
print(output)


Measured memory_bytes: 21588
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <sstream>
#include <set>
typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}
using namespace std;
int main(){
    double n,k,x,cnt,y;
    double ans = 0;
    cin >> n >>k;

    
        for(int j=1;j<=n;j++){
            double tmp = 1/n;
            int x = j;
            while (x < k){
                x *=2;
                tmp /= 2;
            }
            ans += tmp;
        }

    printf("%.12f\n",ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair<int,int>
#define f first
#define se second
using namespace std;
double pi=acos(-1.0);
int m=1000000007;
bool cmp2(int n,pii p)
 {return n<p.f;}
int abst(int a)
{return a<0?-a:a;}
struct HASH{
  size_t operator()(const pii &x)const{
    return (size_t) x.first * 37U + (size_t) x.second;}};
int Pow(int n,int x){int ans=1;
 while(x>0)
 {if(x&1)ans=(ans*n)%m;n=(n*n)%m;x=x>>1;}
 return ans;}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
string s;
cin>>s;
if(n&1)
cout<<"No";
else
{
    string st;
    for(int i=0;i<n/2;i++)
    st+=s[i];
    if(st+st==s)
    cout<<"Yes";
    else
    cout<<"No";
}
}

Measured memory_bytes: 256
D, G = map(int, input().split())
problem = [list(map(int, input().split())) for _ in range(D)]

ans = 10**15
for i in range(2**D):
    score = 0
    prob = 0
    lst = []
    for j in range(D):
        if((i >> j) & 1):
            score += (j+1)*100*problem[j][0]+problem[j][1]
            prob += problem[j][0]
        else:
            lst.append(j)
            
            
    if(score < G):
        r = lst[-1]
        for _ in range(problem[r][0]-1):
            score += 100*(r+1)
            prob += 1
            if(score >= G):
                break
        
    if(score >= G):
        ans = min(ans, prob)
            
print(ans)

Measured memory_bytes: 9016
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using u32 = unsigned int;
typedef pair<int, int> p;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int Inf = (1<<30);
ll inf = (1LL<<60);
bool cheak(int a, int b, int c, int d, int bit) {
	int tmp = a;
	(1 & bit) ? tmp += b : tmp -= b;
	bit >>= 1;
	(1 & bit) ? tmp += c : tmp -= c;
	bit >>= 1;
	(1 & bit) ? tmp += d : tmp -= d;
	return tmp == 7 ? 1 : 0;
}
void out(int a, int b, int c, int d, int bit) {
	char op1 = (1 & bit) ? '+' : '-';
	bit >>= 1;
	char op2 = (1 & bit) ? '+' : '-';
	bit >>= 1;
	char op3 = (1 & bit) ? '+' : '-';
	char A = a + '0';
	char B = b + '0';
	char C = c + '0';
	char D = d + '0';
	cout << A << op1 << B << op2 << C << op3 << D << "=7";
}
int main(){
	string s;
	cin >> s;
	int a = s[0] - '0';
	int b = s[1] - '0';
	int c = s[2] - '0';
	int d = s[3] - '0';
	for (int bit = 0; bit < (1 << 3); bit++) {
		if (cheak(a, b, c, d, bit)) {
			out(a, b, c, d, bit);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left, bisect_right

n = int(input())
*l, = map(int, input().split())

l = sorted(l)

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        idx = bisect_left(l, l[j] - l[i] + 1)
        ans += max(0, i - idx)

print(ans)

Measured memory_bytes: 3316
x1 = list(map(int,input().split()))
x2 = list(map(int,input().split()))
x3 = list(map(int,input().split()))
x1.sort()
x2.sort()
x3.sort()
count = []
for i in range(5):
  count.append(x1.count(i)+x2.count(i)+x3.count(i))
if max(count)>2:
  print("NO")
  exit()
if x1==x2 or x2==x3 or x3==x1:
  print("NO")
else:
  print("YES")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxN = 1e5 + 10;

int n;
int a[maxN], b[maxN], c[maxN], fen[maxN * 4];

void add(int pos, int val){
    for(int i = pos; i <= 2 * n; i += i&-i)
        fen[i] += val;
}

int get(int pos){
    int res = 0;
    for(int i = pos; i; i -= i&-i)
        res += fen[i];
    return res;
}

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

    for(int i = 1; i <= n; ++i){
        if(a[i] >= x)
            b[i] = 1;
        else
            b[i] = -1;
    }

    int res = 0;

    add(n, 1);
    for(int i = 1; i <= n; ++i){
        b[i] += b[i - 1];
        res += get(b[i] + n);
        add(b[i] + n, 1);
    }

    return (res >= n * (n + 1) / 4);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
    cin >> n;

    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        c[i] = a[i];
    }

    sort(c + 1, c + n + 1);

    int high = unique(c + 1, c + n + 1) - c - 1;

    int low = 1, ans;
    while(low <= high)
    {
        int mid = (low + high) / 2;

        if(check(c[mid])){
            low = mid + 1;
            ans = mid;
        }
        else
            high = mid - 1;
    }

    cout << c[ans];
}


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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RFOR(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); --i)
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define RREP(i, n) for (int i = (int)(n - 1); i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(a) ((int)(a).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define SQ(x) ((x) * (x))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

    bool visited[60] = {0};
    int d = 0, e = 0;
    while (1) {
        if (visited[d]) break;
        visited[d] = true;
        if (c <= d + a && d + a < c+a) {
            cout << c - d + e << endl;
            return 0;
        }
        d = (d + a + b) % 60;
        e += a + b;
    }
    cout << -1 << endl;
}

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

using namespace std;

typedef vector<vector<int> > Matrix; //隣接行列
typedef pair<int, int> P;

const int INF = 1000000000;

Matrix dist;

//trueなら負の閉路を検出
bool warshall_floyd(int n) { //nは頂点数
    for (int k = 0; k < n; k++) { //経由点
        for (int i = 0; i < n; i++) { //始点
            for (int j = 0; j < n; j++) { //終点
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    //負の閉路を検出
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	dist = Matrix(n, vector<int>(n, INF));
	Matrix g(n, vector<int>(n, INF));
	for (int i = 0; i < n; i++) {
		dist[i][i] = 0;
		g[i][i] = 0;
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		dist[a][b] = c;
		dist[b][a] = c;
		g[a][b] = c;
		g[b][a] = c;
	}
	warshall_floyd(n);
	int ans = m;
	for (int t = 1; t < n; t++) {
		for (int f = 0; f < t; f++) {
			if (g[f][t] == INF) continue;
			if (g[f][t] == dist[f][t]) ans--;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    int c = 0;
    string S;
    cin >> S;
    string T = "CODEFESTIVAL2016";
    for(int i = 0; i < 16; i++) {
        if(S.at(i) != T.at(i))
            c++;
    }
    cout << c << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a] += [b]
    edges[b] += [a]
candy = [[1]]
for _ in range(N - 1):
    tmp = []
    for c in candy:
        for next in edges[c[-1]]:
            tmp += [c + [next]]
    candy = tmp
print(sum(len(set(c)) == N for c in candy))

Measured memory_bytes: 141808
import sys
p=[1]*999999
p[0]=p[1]=0
p[4::2]=[0]*len(p[4::2])
for i in xrange(3,1000,2):p[i*i::i]=[0]*len(p[i*i::i])
for n in sys.stdin:print p[0:int(n)+1].count(1)

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

ll solve() {
    ll N, d, dm = 0;
    ll M = 1e5+1;
    cin >> N;
    vector<ll> D(N);
    vector<ll> dn(M);
    for ( int i = 0; i < N; i++ ) {
        cin >> D[i];
        dn[D[i]]++;
        dm = max(dm, D[i]);
    }
    if ( D[0] != 0 ||  dn[0] != 1 ) return 0;
    for ( int i = 1; i <= dm; i++ ) {
        if ( dn[i] == 0 ) return 0;
    }
    const ll MOD = 998244353;
    auto Add = [&](ll& x, ll y) { x = ( x + y % MOD ) % MOD; };
    auto Mul = [&](ll& x, ll y) { x = ( x * y % MOD ) % MOD; };
    ll w = 1;
    for ( int i = 1; i <= dm; i++ ) {
        for ( int j = 0; j < dn[i]; j++ ) {
            Mul(w, dn[i-1]);
        }
    }
    ll ans = w;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <time.h>
#include <stdio.h>
#include <vector>
#define int long long
#define end getchar();getchar();return 0
int inf = 1000000000;
using namespace std;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int mypow(int x, int y) {
	if (y == 0)return 1;
	if (y % 2)return mypow(x, y - 1)*x;
	else return mypow(x, y / 2)*mypow(x, y / 2);
}
int Max(int x, int y) {
	if (x > y)return x;
	else return y;
}
int Min(int x, int y) {
	if (x < y)return x;
	else return y;
}
int kai(int x) {
	int cnt=1;
	if (x == 0)return 1;
	cnt = kai(x - 1);
	return x * cnt;
}
int prime(int n) {
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
void prime_factor(int n){
	int cnt = 1;
	map<int, int>res;
	int m = n;
	for (int i = 2; i<= n; i++) {
		if(prime(i)){
			while (m%i == 0) {
				++res[i];
				m /= i;
			}
		}
	}
	cout << n <<":"<< endl;
	for (int i = 2; i<= n; i++) {
		if (res[i]) {
			cout << i << " " << res[i] << endl;
		}
	}
	cout << endl;
}
/*Library End!*/
int a, b, c;
signed main() {
	cin >> a >> b >> c;
	for (int i = 0; i < 500; i++) {
		if (a % 2 || b % 2 || c % 2) {
			cout << i << endl;
			end;
		}
		int aa = a, bb = b, cc = c;
		a = bb / 2 + cc / 2;
		b = aa / 2 + cc / 2;
		c = cc / 2 + bb / 2;
	}
	cout << -1 << endl;
	end;
}

Measured memory_bytes: 256
from collections import deque
import sys
input = sys.stdin.readline

def solve():
    MOD = 10**9 + 7

    H, W, N = map(int, input().split())
    rcs = [tuple(map(int, input().split())) for _ in range(N)]

    adjL = [[] for _ in range(N)]
    for i in range(N):
        r1, c1 = rcs[i]
        for j in range(i+1, N):
            r2, c2 = rcs[j]
            if r1 <= r2 and c1 <= c2:
                adjL[i].append(j)
            if r1 >= r2 and c1 >= c2:
                adjL[j].append(i)

    def TopologicalSort(adjList):
        numV = len(adjList)
        indegs = [0] * numV
        for v in range(numV):
            for v2 in adjList[v]:
                indegs[v2] += 1
        anss = [v for v in range(numV) if indegs[v] == 0]
        Q = deque(anss)
        while Q:
            vNow = Q.popleft()
            for v2 in adjList[vNow]:
                indegs[v2] -= 1
                if indegs[v2] == 0:
                    anss.append(v2)
                    Q.append(v2)
        return anss
    nos = TopologicalSort(adjL)

    def getFacts(n, MOD):
        facts = [1] * (n+1)
        for x in range(2, n+1):
            facts[x] = (facts[x-1] * x) % MOD
        return facts
    facts = getFacts(H+W, MOD)
    def getInvFacts(n, MOD):
        invFacts = [0] * (n+1)
        invFacts[n] = pow(facts[n], MOD-2, MOD)
        for x in reversed(range(n)):
            invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
        return invFacts
    invFacts = getInvFacts(H+W, MOD)

    def getNum(r, c, MOD):
        return facts[r+c] * invFacts[r] * invFacts[c] % MOD

    dp = [0] * N
    for i in range(N):
        noi = nos[i]
        r1, c1 = rcs[noi]
        v = getNum(r1-1, c1-1, MOD)
        for j in range(i):
            noj = nos[j]
            r0, c0 = rcs[noj]
            if i == j or r0 > r1 or c0 > c1:
                continue
            dr, dc = r1-r0, c1-c0
            v -= dp[noj] * getNum(dr, dc, MOD)
            v %= MOD
        dp[noi] = v

    ans = getNum(H-1, W-1, MOD)
    for i, (r, c) in enumerate(rcs):
        dr, dc = H-r, W-c
        ans -= dp[i] * getNum(dr, dc, MOD)
        ans %= MOD

    print(ans)


solve()


Measured memory_bytes: 145884
#include <bits/stdc++.h>
using namespace std;
 
signed main () {
	int a[3][3];
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j)
			cin >> a[i][j];
	}
	int n; 
	cin >> n;
	for (int q = 0; q < n; ++q) {
		int x;
		cin >> x;
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (x == a[i][j])
					a[i][j] = -1;
			}
		}
	}
	bool diag = 0, vert = 0, hori = 0;
	for (int i = 0; i < 3; ++i) {
		bool k = true;
		for (int j = 0; j < 3; ++j) {
			if (a[i][j] != -1)
				k = false;
		}
		vert |= k;
	}
	for (int i = 0; i < 3; ++i) {
		bool k = true;
		for (int j = 0; j < 3; ++j) {
			if (a[j][i] != -1)
				k = false;
		}
		vert |= k;
	}
	diag = (a[0][0] == -1 && a[1][1] == a[2][2] && a[1][1] == -1) || (a[0][2] == a[1][1] && a[1][1] == -1 && a[2][0] == a[0][2]);
	if (diag || vert || hori)
		cout << "Yes\n";
	else
		cout << "No\n";
}


Measured memory_bytes: 256
#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>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#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 //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

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) {
    int n,k;
    cin >> n >> k;
    vector<vi> a(n);
    rep(i,n){
        int t,d;
        cin >> t >> d;
        t--;
        a[t].push_back(d);
    }
    vp v;
    rep(i,n)if(a[i].size()){
        sort(all(a[i]));
        reverse(all(a[i]));
        rep(j,a[i].size()){
            v.push_back(pii(a[i][j],!j));
        }
    }
    int sum = 0, cnt = 0;
    sort(all(v));
    reverse(all(v));
    rep(i,k){
        sum += v[i].first;
        cnt += v[i].second;
    }
    int ans = sum + cnt*cnt;
    int l = k-1, r = k;
    while(l >= 0 && v[l].second)l--;
    while(r < n && !v[r].second)r++;
    while(l >= 0 && r < n){
        sum += -v[l].first+v[r].first;
        cnt++;
        ans = max(ans, sum + cnt*cnt);
        l--,r++;

        while(l >= 0 && v[l].second)l--;
        while(r < n && !v[r].second)r++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 7924
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
 int N,K,Q;
int S[222222];
signed main(){
    cin>>N>>K>>Q;
    rep(i,N)S[i]=K-Q;
    rep(i,Q){
        
        int a;cin>>a;a--;S[a]++;
    }
    rep(i,N){
        if(S[i]>0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <cctype>

int n, ans = 0;
int a[3010];

int read() {
    int ret, f = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * f;
}

void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

signed main() {
    n = read();
    for(int i = 1; i <= n; ++i) ans += read();
    print(ans - n);
    return 0;
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] cnt = new int[100010];
    for (int i = 0; i < n; i++) {
      int tmp = sc.nextInt();
      cnt[tmp]++;
      cnt[tmp + 1]++;
      cnt[tmp + 2]++;
    }

    Arrays.sort(cnt);
    System.out.println(cnt[cnt.length - 1]);

  }
}

Measured memory_bytes: 59488