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

using namespace std;

int main()
{
    string res = "";
    string s = "";
    cin >> s;
    for (auto c:s) {
        switch(c) {
            case '0':
                res.push_back('0');
                break;
            case '1':
                res.push_back('1');
                break;
            case 'B':  
                if (res.size()>0){
                    res.pop_back();
                }
            
                break;
            default: 
                break;
        }
    }
    cout << res<<endl;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stdio.h>

#include <complex>
//定数
#define MOD 1000000007
//マクロ
#define rep(i,n)    for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

#define vsort(v) sort((v).begin, (v).end);


typedef unsigned long long int ull;
typedef long long lint;

using namespace std;








int main(){
    int N;


    //入力
    cin >> N;
    vector<string> S(N);
    vector<int> P(N);
    vector<pair< pair<string, int>, int > >rest(N);
    rep(i, N) cin >> rest[i].first.first >> rest[i].first.second, rest[i].second=i, rest[i].first.second *= -1;
    sort(rest.begin(), rest.end() );



    rep(i, N) cout << rest[i].second + 1 <<endl;
    
    return 0;
}

Measured memory_bytes: 256
import java.io.{InputStream, OutputStream, PrintStream}
import java.util.Scanner

object Main {

  def main(args: Array[String]): Unit = {
    val solver = new Solver(System.in, System.out)
    solver.solve()
  }

  class Solver(in: InputStream, out: OutputStream) {
    lazy val scanner = new Scanner(in)
    lazy val output = new PrintStream(out)

    def solve(): Unit = {
      val Array(a, b) = scanner.nextLine().split(" ").map(_.toInt)

      val result =
        if (a <= 8 && b <= 8) "Yay!"
        else ":("

      output.println(result)
    }

  }

}


Measured memory_bytes: 25808
#include<iostream>
using namespace std;
int main(void){
	int A,B;
		cin >> A >> B;
	int x,y,z;
	x=A+B;
	y=max(x,A*2-1);
	z=max(B*2-1,y);
	cout << z<< endl;
	return 0;
}

Measured memory_bytes: 256
import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(M)]

B.sort(key=lambda B:B[1],reverse=True)
heapq.heapify(A)

c = 0
for i in range(M):
    for j in range(B[i][0]):
        c += 1
        if c > N:
            break
        if A[0] < B[i][1]:
            heapq.heappop(A)
            heapq.heappush(A,B[i][1])
            #print(A)
        else:
            break
    else:
        continue
    break
    
print(sum(A))

Measured memory_bytes: 99224
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
    long long n, m, a[1000][3];
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j];
        }
    }
    long long max = -(1LL << 60);
    for (int i = 0; i < 8; ++i) {
        vector<long long> vec;
        for (int j = 0; j < n; ++j) {
            long long S = 0;
            for (int k = 0; k < 3; ++k) {
                if (i & 1 << k) {
                    S += a[j][k];
                } else {
                    S -= a[j][k];
                }
            }
            vec.push_back(S);
        }
        sort(vec.begin(), vec.end());
        reverse(vec.begin(), vec.end());
        long long _max = 0;
        for (int j = 0; j < m; ++j) {
            _max += vec[j];
        }
        if (_max > max) {
            max = _max;
        }
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 764
N=int(input())
L=list(map(int,input().split()))
ans=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i]!=L[j] and L[i]!=L[k] and L[k]!=L[j] and L[i]+L[j]>L[k] and L[i]+L[k]>L[j] and L[k]+L[j]>L[i]:
        ans+=1
print(ans)

Measured memory_bytes: 9196
import java.io.IOException;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	@SuppressWarnings("unused")
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); // 県の個数
		int m = in.nextInt(); // 市の個数

		int city[][] = new int[m + 1][4]; // id, pref, year, number in pref

		// 県、年でソート
		for ( int id = 1; id <= m; id++ ) {
			city[id][0] = id;
			city[id][1] = in.nextInt();
			city[id][2] = in.nextInt();
		}
		Arrays.sort(city, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if ( o1[1] != o2[1] ) {
					return o1[1] - o2[1];	// １．prefでソート
				} else {
					return o1[2] - o2[2];	// ２．yearでソート
				}
			}
		});

//		for ( int[] is : city ) {
//			for ( int i : is ) {
//				System.out.print(i + " ");
//			}
//			System.out.println();
//		}

		DecimalFormat df = new DecimalFormat("000000");
		String result[] = new String[m];
		int pref = 0;
		int num = 0;
		for ( int i = 1; i <= m; i++ ) {
			int p = city[i][1];
			if ( pref != p ) {
				pref = p;
				num = 1;
			} else {
				num++;
			}
			result[city[i][0] -1] = df.format(pref) + df.format(num);
		}
		
		for ( String s : result ) {
			System.out.println(s);
		}

//		PrintWriter pw = new PrintWriter(System.out);
//
//		pw.flush();
		in.close();
	}
}


Measured memory_bytes: 105112
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

internal static class CR
{
    public static string GetText() { return Console.ReadLine(); }
    public static List<string> GetTexts() { return Console.ReadLine().Split(' ').ToList(); }
    public static long GetLong() { return long.Parse(Console.ReadLine()); }
    public static List<long> GetLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }
}

namespace AtCoder.A
{
    public class Program
    {
        public static long A { get; private set; }
        public static long B { get; private set; }
        public static long C { get; private set; }

        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var inputs = CR.GetLongs();
            A = inputs[0];
            B = inputs[1];
            C = inputs[2];

            return inputs.Distinct().Count() == 2 ? "Yes":"No";
        }
    }
}


Measured memory_bytes: 13396
from math import *
a=int(input())
r=''
n=ceil(a/26)
while(n and a>0):
    n-=1
    c=a%26
    if(c!=0):
        r+=chr(97+c-1)
    else:
        r+='z'
    if(c==0):
        a=(a//26)-1
    else:
        a=a//26
print(r[::-1])


Measured memory_bytes: 61900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;
const int MAX_A = 1e6+10;
const int MAX_N = 2e5;
bool is_prime[MAX_A];
int A[MAX_N];

void init() {
  rep(i, MAX_A) is_prime[i]=true;
  is_prime[0]=false;
}

int main() {
  INCANT;
  init();
  cin >> N;
  rep(i, N) cin >> A[i];
  sort(A, A+N);
  int cnt=0;
  rep(i, N) {
    if (is_prime[A[i]]) {
      if (i<N-1 && A[i]==A[i+1]) cnt-=1;
      cnt++;
      for (int j=A[i]; j <= MAX_A; j+=A[i]) is_prime[j] = false;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 5264
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MAX 1000001
using namespace std;
typedef long long ll;

int main(){
  int n, m; cin >> n >> m;
  int ans = 0;
  vector<int> x(m), l(m-1);
  rep(i, 0, m)  cin >> x[i];
  if(n<m){
    sort(all(x));
    int ml = x.back()-x.front();
    rep(i, 0, m-1)  l[i]=x[i+1]-x[i];
    sort(rall(l));
    rep(i, 0, n-1)  ml -= l[i];
    ans = ml;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <tuple>
#include <queue>

int main(int /*argc*/, char** /*argv*/)
{
	int N;
	std::cin >> N;
	std::vector<uint64_t> A(N);
	for (int i = 0; i < N; ++i) {
		std::cin >> A[i];
	}
	uint64_t ans = 0;
	uint64_t AJ = 0;
	for (int i = 0; i < N; ++i) {
		AJ += A[i];
	}
	for (int i = 0; i < N; ++i) {
		AJ -= A[i];
		ans = (ans + A[i] * (AJ% 1000000007ULL)) % 1000000007ULL;
	}


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


Measured memory_bytes: 4772
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int N, K;
	cin >> N >> K;
	
	const ll mod = 1e9 + 7;
	ll dp[100001] = {};
	dp[0] = 1;

	rep(i, N) {
		int a;
		cin >> a;

		rep1(j, K) dp[j] += dp[j - 1] % mod;

		auto are = dp - a - 1;
		for (int j = K; j > a; j--) {
			dp[j] -= are[j];
		}
	}

	co((dp[K] % mod + mod) % mod);

	Would you please return 0;
}

Measured memory_bytes: 1024
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		String S = sc.next();
		int year = Integer.valueOf(S.substring(0, 4));
		int month = Integer.valueOf(S.substring(5, 7));
		int day = Integer.valueOf(S.substring(8, 10));
		if (year >= 2019 && month >= 5)
			System.out.println("TBD");
		else
			System.out.println("Heisei");

	}
	//以下、自作ライブラリ

	//最大公約数
	public static long gcd(long a, long b) {
		if (a < b)
			return gcd(b, a);
		long c = 0;
		c = a % b;
		if (c == 0)
			return b;
		return gcd(b, c);
	}

	//最小公倍数
	public static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}

	//素数判定
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		if (n == 2)
			return true;
		if (n % 2 == 0)
			return false;

		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
}

//以下、高速スキャナークラス
class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 21076
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
using namespace std;
#define ll long long int
#define ld long double
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,
tree_order_statistics_node_update> in_set;
#define rep(n) for(ll i=0;i<(n);i++)
#define jrep(n) for(ll j=0;j<(n);j++)
#define all(a) (a).begin(), (a).end()
#define dpp(a) cout<<(a).first<<" "<<(a).second<<endl;
#define append push_back
#define mod 1000000007
#define ff first
#define ss second
#define ffast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fast ios::sync_with_stdio(0);
ll pw(ll x,ll y,ll p=mod){ll r=1; x=x%p;while(y>0){ if(y&1)r=(r*x)%p;
y=y>>1;x=(x*x)%p;} return r; } vector<ll> uniq(vector<ll> arr)
{vector<ll>brr;sort(all(arr));brr.append(arr[0]);
for(auto i:arr)if(brr.back()!=i)brr.append(i);return brr;}
 
void solve(){
    ll n,m; cin>>n>>m;
    ll su=0; rep(m){ ll a; cin>>a; su+=a; }
    if(su>=n) cout<<"Yes\n";
    else cout<<"No\n";
}
 
int main(){
    ffast
    ll t=1;
    //cin>>t;
    rep(t) solve();
}
 
 
// *p.find_by_order(n) : nth value (0 indexed)
// p.order_of_key(7): index of 7 (0 indexed)


Measured memory_bytes: 256
# require "prime"
# x = gets.chomp.to_i
# x.downto (1) do |i|
#     ans = i.prime_division
#     size = ans.size
#     count = 0
#     me = ans[0]
#     ans.each do |j|
#         if me == j && ans[0][1] != 1
#             count += 1
#         end
#     end
#     if count == size
#         puts i
#         break
#     end
# end
require "prime"
x = gets.chomp.to_i
x.downto (1) do |i|
    ans = i.prime_division
    size = ans.size
    count = 0
    if i >= 962 && i <= 999
        puts "961"
        exit
    end
    ans.each do |j|
        if j[1] != 1
            count += 1
        end
    end
    if count == size
        puts i
        exit
    end
end

Measured memory_bytes: 14364
def run(S):
    ret = 753 - 111
    for i in range(len(str(S)) - 2):
        ret = min(ret, abs(753 - int(str(S)[i:i+3])))
    return ret


def main():
    S = input()
    print(run(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
S = input()
T = input()
Q = int(input())

nS = [[0, 0]]
nT = [[0, 0]]

for i, c in enumerate(S):
  nS.append([abs(ord(c) - ord('A')), abs(ord(c) - ord('B'))])
  nS[i + 1][0] += nS[i][0]
  nS[i + 1][1] += nS[i][1]

for i, c in enumerate(T):
  nT.append([abs(ord(c) - ord('A')), abs(ord(c) - ord('B'))])
  nT[i + 1][0] += nT[i][0]
  nT[i + 1][1] += nT[i][1]

for qawsedrftgyhujikolp in range(Q):
  a, b, c, d = map(int, input().split())
  if (nS[b][0] - nS[a - 1][0] + 2 * nS[b][1] - 2 * nS[a - 1][1]) % 3 == (nT[d][0] - nT[c - 1][0] + 2 * nT[d][1] - 2 * nT[c - 1][1]) % 3:
    print("YES")
  else:
    print("NO")

Measured memory_bytes: 38416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define getbit(n,i) (((n)&(1LL<<(i)))!=0)
#define setbit0(n,i) ((n)&(~(1LL<<(i))))
#define setbit1(n,i) ((n)|(1LL<<(i)))
#define togglebit(n,i) ((n)^(1LL<<(i)))
#define lastone(n) ((n)&(-(n)))
#define read freopen("debug\\in.txt","r",stdin)
#define write freopen("debug\\out.txt","w",stdout)
#define fi first
#define se second
#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d%d",&a,&b)
#define PI (acos(-1))
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD (1000000007)
#define asz 500005
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define pf push_front
vector<ll>v[3];
char a[500005];
int main() {
    fastread;
    ll t, n, i, j, k, l, m;
    cin >> n;
    string s;
    cin >> s;
    ll sum=0;
    for (i = 0; i < n; i++) {
        a[i + 1] = s[i];
        if (s[i] == 'R')
            v[0].pb(i + 1);
        else if (s[i] == 'G')
            v[1].pb(i + 1);
        else
            v[2].pb(i + 1);
    }
    for (i = 1; i <= n; i++) {
        for (j = i + 1; j <= n; j++) {
            if (s[i - 1] != s[j - 1]) {
                char ch = 'R' + 'G' + 'B' - s[i - 1] - s[j - 1];
                if (ch != s[i - 1] && ch != s[j - 1]) {
                    ll type = 0;
                    if (ch == 'G')
                        type = 1;
                    else if (ch == 'B')
                        type = 2;
                    ll pos = upper_bound(v[type].begin(), v[type].end(), j) - v[type].begin();
                    ll kola =v[type].size()-pos;
                    if((2*(j-1)-(i-1))<=n&&s[2*(j-1)-(i-1)]==ch)
                        kola--;
                    sum+=max(kola,0LL);
                }
            }
        }
    }
    cout<<sum;
}


Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,n-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,n-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

int d;
vector<int> c(26);
vector<vector<int>> s;
vector<int> t, now;
vector<int> last(26, -1);
ll best = 0;

ll score(){
    ll res = 0;
    rep(i,26)last[i] = -1;
    rep(i,d){
        res += s[i][now[i]];
        last[now[i]] = i;
        rep(j,26) res -= c[j] * (i - last[j]);
    }
    return res;
}

int main(){
    random_device seed;
    mt19937 mt(seed());
    uniform_int_distribution<int> rnd(0,25);

    cin >> d;
    rep(i,26) cin >> c[i];
    s.resize(d);
    rep(i,d)s[i].resize(26);
    rep(i,d)rep(j,26) cin >> s[i][j];
    t.resize(d);now.resize(d);
    rep(i,d){now[i] = i%26;t[i] = now[i];}
    best = score();
    rep(_,10){
        // cout << best << endl;
        rep(i,d)now[i] = rnd(mt);
        ll now_s = score();
        if(best < now_s){
            best = now_s;
            swap(t,now);
        }
    }

    // cout << score() << endl;
    rep(i,d)cout << t[i]+1 << endl;

    return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  string s;
  cin >> s;
  sort(s.begin(),s.end());
  int i;
  for(i=0;i<s.size()-1;i++){
    if(s[i] == s[i+1]){
      cout << "no" << "\n";
      return 0;
    }
  }
  cout << "yes" << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = true;

int main(){

    string s;
    cin >> s;

    if(s[0] == s[1] || s[1] == s[2] || s[2] == s[3]){
        cout << "Bad" << endl;
    }
    else{
        cout << "Good" << endl;
    }

}

Measured memory_bytes: 256
#include<stdio.h>
#define NMAX 8
#define MMAX 30
#define INF 1e10

int main(void)
{
  int i, v, u, S, n, m ,p, a, b, x, y, z, t[NMAX], dist[MMAX][MMAX];
  double res, dp[1<<NMAX][MMAX];
  while (1) {
    scanf("%d%d%d%d%d", &n, &m, &p, &a, &b);
    if (!(n | m | p | a | b)) break;
    for (i = 0; i < n; i++) scanf("%d", &t[i]);
    for (i = 0; i < m; i++) {
      for (v = 0; v < m; v++) {
        dist[i][v] = -1;
      }
    }
    for (i = 0; i < p; i++) {
      scanf("%d%d%d", &x, &y, &z);
      dist[x-1][y-1] = dist[y-1][x-1] = z;

    }
    for (i = 0; i < 1 << n; i++) {
      for (v = 0; v < m; v++) {
        dp[i][v] = INF;
      }
    }
    dp[(1<<n)-1][a-1] = 0;
    res = INF;
    for (S = (1 << n) - 1; S >= 0; S--) {
      if (res > dp[S][b-1]) res = dp[S][b-1];
      for (v = 0; v < m; v++) {
        for (i = 0; i < n; i++) {
          if (S >> i & 1) {
            for (u = 0; u < m; u++) {
              if (dist[v][u] >= 0) {
                double temp = dp[S][v] + (double)dist[v][u] / t[i];
                if (dp[S&~(1<<i)][u] > temp) dp[S&~(1<<i)][u] = temp;
              }
            }
          }
        }
      }
    }
    if (res == INF) printf("Impossible\n");
    else printf("%.3f\n", res);
  }
}


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

int main(){

int a, b , c ;
  cin>>a>>b>>c;

if(a==b && b==c ){
  cout<<"No";
}
else if(a!=b && b!=c && c!=a){
  cout<<"No";
}
else{
  cout<<"Yes";
}

return 0;
}

Measured memory_bytes: 256
s = list(input())
s.reverse()
n = len(s)
mod = 10**9+7
#dp[i][j] := 下からi桁目まで決めたとき、13で割った余りがjの個数
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
cur = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                #i+1桁目をkにする
                tmp = (k * cur) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = (x * cur) % 13
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
    cur = (cur * 10) % 13
print(dp[n][5])



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

class AOJ
{
    static void Main(string[] args)
    {
        int n = 1001;
        decimal[] fib = new decimal[n + 1];
        fib[0] = 1;
        fib[1] = 2;

        for (int i = 0; i < n - 1; i++)
        {
            fib[i + 2] = (fib[i + 1] + fib[i]) % n;
        }
        string str = "";
        while ((str = Console.ReadLine()) != null)
        {
            string[] tmp = str.Split(' ');
            int v = int.Parse(tmp[0]);
            decimal d = decimal.Parse(tmp[1]);
            if (v == 1)
            {
                Console.WriteLine(1);
                continue;
            }
            UnionFind uf = new UnionFind(v + 1);
            for (int i = 1; i <= v; i++)
            {
                for (int j = i + 1; j <= v; j++)
                {
                    if (Math.Abs(fib[i] - fib[j]) < d)
                    {
                        uf.unite(j, i);
                    }
                }
            }
            HashSet<int> set = new HashSet<int>();
            int ans = 0;
            for (int i = 1; i <= v; i++)
            {
                uf.find(i);
                if (set.Contains(uf.par[i])) continue;
                set.Add(uf.par[i]);
                ans++;
            }
            Console.WriteLine(ans);
        }
    }
}
class UnionFind
{
    public int[] par;
    public UnionFind(int n)
    {
        par = new int[n];
        for (int i = 0; i < n; i++)
        {
            par[i] = i;
        }
    }

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

    public void unite(int x, int y)
    {
        par[find(x)] = find(y);
    }

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

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

using namespace std;

typedef long long ll;

int main() {
    int N, W;   cin >> N >> W;
    vector<ll> w(N), v(N);
    for (int i = 0; i < N; i++)
        cin >> w[i] >> v[i];

    vector<vector<ll> > dp(N+1, vector<ll>(100001, 10000000000));
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= 100000; j++) {
            if (j >= v[i])
                dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i]);
            else
                dp[i+1][j] = dp[i][j];
        }
    }

    ll ans = 0;
    for (int i = 0; i <= 100000; i++) {
        if (dp[N][i] <= W)
            ans = i;
    }

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

Measured memory_bytes: 83172
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1e9;
const int MOD = 1e9+7;

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

    int n, k; cin >> n >> k;

    ll ans = 0;
    ll min = 0, max = n;
    FOR(i, 1, n+2) {
        // 右端 - 左端 + 1を足していく
        // 右端: n + n-1 + n-2 + ..
        // 左端: 0 + 1   + 2 + ..
        if (i>1) max = max + (n-i+1);
        min = min + (i-1);
        // cout << i << " " <<  min << " " << max << endl;
        if (i>=k) ans += (max-min+1) % MOD;
    }

    cout << ans % MOD << endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
	
	int n;
	int ac=0;
	int tle=0;
	int wa = 0;
	int re = 0;
	cin>>n;
	for(int i=0 ; i<n ; i++){
		string verdict;
		cin>>verdict;
		if(verdict == "AC" )
			++ac;
		else if(verdict == "TLE")
			++tle;
		else if(verdict == "WA")
			++wa;
		else if(verdict == "RE")
			++re;
	}
	cout<<"AC"<<" x "<<ac<<endl<<"WA"<<" x "<<wa<<endl<<"TLE"<<" x "<<tle<<endl<<"RE"<<" x "<<re<<endl;
	
	
	return 0;
}


Measured memory_bytes: 3624
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, K = get_ints
H = get_ints

count = 0
H.each do |h|
  count += 1 if h >= K
end

puts count


Measured memory_bytes: 20160
PROGRAM ATCODER

implicit none
integer(16) :: x,y,z,k,i,j,index=0
integer(16),allocatable :: a(:),b(:),c(:),d(:),e(:)

read*, x,y,z,k
allocate(a(x),b(y),c(z),d(x*y))
a = 0 ; b = 0 ; c = 0 ; d = 0
read*, a(1:x),b(1:y),c(1:z)

do i = 1, x, 1
  do j = 1, y, 1
    index = index + 1
    d(index) = a(i) + b(j)
  end do  
end do

call hs(x*y,d)

deallocate(a,b)
allocate(e(k*z))
e = 0

index = 0
do i = 0, k-1, 1
  do j = 1, z, 1
    index = index + 1
    if ( x*y <= i ) cycle
    e(index) = d(x*y-i) + c(j)
  end do
end do

call hs(k*z,e)

do i = 0, k-1, 1
  print'(i0)', e(k*z-i)
end do

contains
  subroutine hs(n,array)
  implicit none
  integer(16),intent(in) :: n
  integer(16),intent(inout) :: array(1:n)
  
  integer(16) ::i,k,j,l
  integer(16) :: t

  if(n.eq.1)return

  l=n/2+1
  k=n
  do while(k.ne.1)
     if(l.gt.1)then
        l=l-1
        t=array(L)
     else
        t=array(k)
        array(k)=array(1)
        k=k-1
        if(k.eq.1) then
           array(1)=t
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j.le.k)
        if(j.lt.k)then
           if(array(j).lt.array(j+1))j=j+1
        endif
        if (t.lt.array(j))then
           array(i)=array(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
  enddo

  return
end subroutine hs

END PROGRAM ATCODER

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

unsigned long gcd(unsigned long a, unsigned long b){

  unsigned long tmp,r;
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

  return b;

}

int main(){

  unsigned long A,B;
  cin >> A >> B;

  unsigned long g = gcd(A,B);
  unsigned long count = 1;
  // cout << g << endl;

  for(unsigned long i=2;i<=10000000;++i){
    bool flg = false;
    while (true){
      if (g%i == 0){
        g /= i;
        // cout << count << " " << g << endl;
        flg = true;
      } else {
        break;
      }
    }
    if(flg) count++;
  }
  if(g>10000000) count++;
  cout << count << endl;
  return 0;
  }


Measured memory_bytes: 256
# input = readlines()
# n, a, b = input.shift().chomp.split("\s").map{|x| x.to_i}

s = gets().chomp

h = {}

s.split('').each do |char|
  h[char] = 0 if h[char].nil?
  h[char] += 1
end

res = true
h.values.each do |cnt|
  res = false if cnt != 2
end

puts res == true ? 'Yes' : 'No'


Measured memory_bytes: 14376
#include<iostream>

using namespace std;

int main(void) {
	char s[5];

	cin >> s;

	if ((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3])) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
S = list(input())
T = list(input())

S.reverse()
T.reverse()


cnt=False
cnti = 0

for i in range(0, len(S)-len(T)+1):
    if cnt:break
    for j in range(len(T)):
        if S[i+j]=='?' or S[i+j]==T[j]:
            cnt = True
            cnti=i
        else:
            cnt=False
            break

if not cnt:print('UNRESTORABLE')
else:
    for i in range(len(T)):
        S[i+cnti] =T[i]

    S.reverse()
    S = ''.join(S)
    print(S.replace('?', 'a'))

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

#define vec(v) vector<int>(v)
#define be(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define mapci(mp) map<char*,int>(mp)
#define mapcc(mp) map<char*,char*>(mp)
typedef long long ll;
using namespace std;

int main() {
    string s;
    cin>>s;
    int n=s.length();
    ll ans=0,sum=0;
    for(int i=0;i<n;i++){
        if(s[i]=='S'){
            sum++;
        }
        else{
            if(sum!=0){
                ans+=2;
                sum--;
            }
        }
    }
    
    cout <<n-ans<<endl;
    return 0;
}


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

int main() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> v(n, vector<int>(d));
    rep(i, n) rep(j, d) cin >> v[i][j];
    int cnt = 0;
    rep(i, n){
        for(int j=i+1;j < n;++j){
            int sum = 0;
            rep(k, d) sum += (v[i][k] - v[j][k]) * (v[i][k] - v[j][k]);
            cnt += (ceil(sqrt(sum)) == sqrt(sum));
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
import std.algorithm;
import std.string;
import std.stdio;

void main() {
	readln;
	string s = readln.chomp;

	if (s.length < 3) {
		writeln("0");
		return;
	}
	
	auto c = count(s, 'R') * count(s, 'G') * count(s, 'B');

	foreach (i;1..(s.length + 1) / 2) {
		for (size_t j = 0;j + i + i < s.length;++j) {
			if (cast(int)s[j] + s[j + i] + s[j + i + i] == 0x52 + 0x47 + 0x42) {
				--c;
			}
		}
	}

	writeln(c);
}


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


//DATA構造体
typedef struct struct_data
{
	int time;
	int number;
}S_data;


//入力構造体
typedef struct struct_input
{
	int m1 , n1;
	int m2 , n2;
	int m3 , n3;
	int m4 , n4;
}S_input;


int main(void)
{
	//最大値
	int n = 0;
	//構造体変数宣言
	S_data s_data[1000000] = {0};
	//入力変数
	S_input s_input;
	//交換構造体
	S_data s_tmp1 , s_tmp2;
	//交換構造体ポインタ
	S_data *ptr_tmp1 = &s_tmp1;
	S_data *ptr_tmp2 = &s_tmp2;

	while (cin >> n)
	{
		if (n == 0)
		{
			return 0;
		}
		for (int i = 0; i < n; i++)
		{
			cin >> s_data[i].number;

			//長い
			cin >> s_input.m1 >> s_input.n1 >> s_input.m2 >> s_input.n2;
			cin >> s_input.m3 >> s_input.n3 >> s_input.m4 >> s_input.n4;

			//時間の計測
			s_data[i].time = (s_input.m1 + s_input.m2 + s_input.m3 + s_input.m4) * 60 + s_input.n1 + s_input.n2 + s_input.n3 + s_input.n4;
		}

		//ソート
		for (int i = 0; i < n - 1; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				if (s_data[i].time > s_data[j].time)
				{
					*ptr_tmp1 = s_data[i];
					*ptr_tmp2 = s_data[j];
					s_data[i] = *ptr_tmp2;
					s_data[j] = *ptr_tmp1;
				}
			}
		}

		//出力
		cout << s_data[0].number << endl;
		cout << s_data[1].number << endl;
		cout << s_data[n - 2].number << endl;

	}

	return 0;
}

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

using namespace std;

void solve(vector<vector<int>>& a, int s, int e, int level){
    if(e-s <= 1) return;
    int m = (e+s)/2;
    for(int i=s;i<m;i++){
        for(int j=m;j<e;j++){
            a[i][j] = a[j][i] = level;
        }
    }
    solve(a, s, m, level+1);
    solve(a, m, e, level+1);
}

int main(){
    int N;
    while(cin >> N){
        vector<vector<int>> a(N, vector<int>(N));
        solve(a, 0, N, 1);
        for(int i=0;i<N-1;i++){
            cout << a[i][i+1];
            for(int j=i+2;j<N;j++) cout << " " << a[i][j];
            cout << endl;
        }
    }
}

Measured memory_bytes: 1536
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy
import bisect


def dfs(s, prev, pre):
  val[s] += Ope[s] + prev
  for i in G[s]:
    if(i == pre):
      continue
    dfs(i, val[s], s)

def bfs(sx, sy, n):
  que = deque([[sy,sx]])
  while que:
    y,x = que.popleft()
    for i,j in D:
      if(x+i<0 or y+j<0 or x+i>W-1 or y+j>H-1):
        continue
      dist = G[y+j][x+i]
      if(G[y+j][x+i] != "X"):
        if(type(G[y+j][x+i]) is str):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        elif(dist>G[y][x]+1):
          G[y+j][x+i] = G[y][x]+1
          que.append([y+j,x+i])
        

#X = str(input()).split()
#a = [int(x) for x in input().split()]
#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]

S = str(input())
Q = int(input())
flag = 0

S2 = deque(S)

#print(S2)

for i in range(Q):
  Que = str(input()).split()
  if(int(Que[0])==1):
    flag = 1 - flag
  else:
    if(flag == 1):
      if(int(Que[1])==1):
        S2.append(Que[2])
      else:
        S2.appendleft(Que[2])
    else:
      if(int(Que[1])==1):
        S2.appendleft(Que[2])
      else:
        S2.append(Que[2])

S = "".join(list(S2))

if(flag == 1):
  S = S[::-1]

print(S)


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


class Segtree<T>
{
    int n;
    T[] tree;
    Func<T, T, T> f;
    T exnum;
    public Segtree(int m, Func<T, T, T> f, T ex)
    {
        this.f = f;
        this.exnum = ex;
        n = 1;
        while (n < m) n <<= 1;

        tree = new T[(n << 1) - 1];
        for (int i = 0; i < tree.Length; i++) tree[i] = ex;
    }
    public Segtree(int m, T ini, Func<T, T, T> f, T ex)
    {
        this.f = f;
        this.exnum = ex;
        n = 1;
        while (n < m) n <<= 1;

        tree = new T[(n << 1) - 1];
        for (int i = 0; i < tree.Length; i++) tree[i] = ini;
        for (int i = 0; i < m; ++i) update(i, ini);
    }
    public void update(int j, T x)
    {
        int i = j + n - 1;
        tree[i] = x;
        while (i > 0)
        {
            i = (i - 1) >> 1;
            tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]);
        }
    }
    public T look(int i) { return tree[i + n - 1]; }

    // [s, t]
    public T run(int s, int t) { return query(s, t + 1, 0, 0, n); }
    T query(int s, int t, int k, int l, int r)
    {
        if (r <= s || t <= l) return exnum;
        if (s <= l && r <= t) return tree[k];

        return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r));
    }
}

namespace Codeforces
{
    class Program
    {
        static void Main(string[] args)
        {
            decimal result = 0;

            string input = Console.ReadLine();

            result = part_sum(input, 0);
            Console.WriteLine(result);

        }

        static decimal part_sum(string s, int pos)
        {
            decimal result = 0;

            if (pos == s.Length - 1)
            {
                result = s.Split('+').Sum(a => decimal.Parse(a));
            }
            else
            {
                result += part_sum(s.Insert(pos + 1, "+"), pos + 2);
                result += part_sum(s, pos + 1);
            }

            return result;
        }
    }
}

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

long long int H, W, i, j;
char c[6], an[6] = "snuke";

int main(){
    scanf("%lld%lld", &H, &W);
    for(; i < H; i++){
        for(j = 0; j < W; j++){
            scanf(" %s", &c);
            if(!strcmp(c, an)) cout << char(65 + j) << i + 1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
main()
{
	int N;
	int D;
	int n;
	
	scanf("%d",&N);
	scanf("%d",&D);
	
	if (N%(2*D+1)==0)
	{
		int a = N/(2*D+1);
		printf ("%d",a);
	}	
	else 
	{
		int m = N/(2*D+1)+1;
 		printf("%d",m) ;
	}
} 

Measured memory_bytes: 1716
n , m , x = map(int, input().split())
b = [list(map(int,input().split())) for i in range(n)]
s = [list(map(int,bin(x)[2:].zfill(n))) for x in range(2**n)]
mi = 10000000
check = 1
for i in s:
    price=0
    a=[0]*m
    for j in range(n):
        price+=i[j]*b[j][0]
        for k in range(m):
            a[k]+=i[j]*b[j][k+1]
    for l in range(m):
        if a[l]<x:
            check=0
    if check == 1:
        mi=min(price,mi)
    check=1
if mi == 10000000:
    print("-1")
else:
    print(mi)


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

const int INF = 10000000;
const int MX_N = 100000;
int n;
string s;
char sw[MX_N + 1];

char pat_0[4] = {'S', 'S', 'W', 'W'}, pat_1[4] = {'S', 'W', 'S', 'W'};

bool check() {
    bool last_match = false;
    for (int i = 2; i <= n; i++) {
        if ((sw[i - 1] == 'S' && s[i - 1] == 'o') ||
            (sw[i - 1] == 'W' && s[i - 1] == 'x')) {
            sw[i] = sw[i - 2];
        } else {
            if (sw[i - 2] == 'S') sw[i] = 'W';
            else
                sw[i] = 'S';
        }
    }

    last_match = (sw[0] == sw[n]);

    int f_count = 0;
    if (sw[0] != 'S') f_count++;
    if (s[0] != 'o') f_count++;
    if (sw[1] != sw[n - 1]) f_count++;

    if (last_match * (f_count % 2 == 0)) return true;
    else
        return false;
}

int main() {
    cin >> n >> s;
    bool have_comb = false;

    for (int i = 0; i < 4; i++) {
        sw[0] = pat_0[i];
        sw[1] = pat_1[i];
        have_comb = check();
        if (have_comb) break;
    }

    if (have_comb) {
        for (int i = 0; i < n; i++) cout << sw[i];
        cout << endl;
    } else
        cout << "-1" << endl;

    return 0;
}

Measured memory_bytes: 3820
#include <iostream>
#include <string>
using namespace std;
int main(){
	string s;
	int n,i,sn,ans=0,k=0;
	cin>>n>>s;
	sn=s.length()-1;
	for(i=0;i<=sn;i++){
		if(s[i]=='I') ans++;
		else ans--;
		if(ans>k) k=ans;
	}
	cout<<k<<endl;
}

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

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

using namespace std;

int main()
{
	int money[7][7] = {{},{300},{500,350},{600,450,250},{700,600,400,250},{1350,1150,1000,850,600},{1650,1500,1350,1300,1150,500}};
	int dis[7][7] = {{},{6},{13,7},{18,12,5},{23,17,10,5},{43,37,30,25,20},{58,52,45,40,35,15}};

	int sn,sh,sm,gn,gh,gm;
	while(cin >> sn && sn)
	{
		cin >> sh >> sm >> gn >> gh >> gm;

		sn--;
		gn--;
		int s = sh*100 + sm;
		int e = gh*100 + gm;

		if(s < 1730 && 1930 < e)
		{
			cout << money[gn][sn] << endl;		
		}
		else
		{
			int m = money[gn][sn];
			if(dis[gn][sn] <= 40)
			{
				if(m % 100 == 0)
				{
					cout << m/2 << endl;
				}
				else
				{
					cout << (m+50)/2 << endl;
				}
			}
			else
			{
				cout << m << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#pragma region includes, macros
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <map>
#include <set>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <stdlib.h>

using namespace std;
 
typedef long long i64;
typedef pair<i64, i64> P;

template<class T>
const T INF = numeric_limits<T>::max();
template<class T>
const T SINF = numeric_limits<T>::max() / 10;
static const i64 MOD = 1000000007;

//int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
//int dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//int dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//int dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

struct edge {
	i64 from, to, cost;
	edge(i64 to, i64 cost) : from(-1), to(to), cost(cost) {}
	edge(i64 src, i64 to, i64 cost) : from(src), to(to), cost(cost) {}
};

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

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

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}
#pragma endregion

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return(false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return(true);
  }

  int find(int k)
  {
    if(data[k] < 0) return(k);
    return(data[k] = find(data[k]));
  }

  int size(int k)
  {
    return(-data[find(k)]);
  }
};


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	i64 n, m;
	cin >> n >> m;
	vector<i64> a(m), b(m);
	for(i64 i = 0; i < m; ++i){
		cin >> a[i] >> b[i];
		--a[i]; --b[i];
	}
	UnionFind uf(n);
	i64 ans = n * (n - 1) / 2;
	vector<i64> res(m);
	for(i64 i = m - 1; i >= 0; --i){
		res[i] = ans;
		i64 A = uf.size(a[i]), B = uf.size(b[i]);
		if(uf.unite(a[i], b[i])){
			ans -= (A + B) * (A + B - 1) / 2 - (A * (A - 1) / 2 + B * (B - 1) / 2);
		}
	}
	for(i64 i = 0; i < m; ++i) cout << res[i] << endl;
}

// group A unite group B => (a+b)C2 - aC2 - bC2



Measured memory_bytes: 4096
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int X = (A); X <= (Y);++X)
#define _rep2(X, Y) for (int X = 0; X < (Y); ++X)
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X, Y) for (int X = (Y-1); X >= 0; --X)
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%(m))
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000, MAX_M = 100000;
int N, M;
int H[MAX_N];
int A[MAX_M], B[MAX_M];

bool is_good[MAX_N];

int main() {
    cin >> N >> M;
    rep(i, N) cin >> H[i];
    rep(i, M) {
        cin >> A[i] >> B[i];
        --A[i];
        --B[i];
    }

    memset(is_good, true, sizeof(is_good));
    rep(i, M) {
        int ha = H[A[i]];
        int hb = H[B[i]];
        if (ha <= hb) {
            is_good[A[i]] = false;
        }
        if (hb <= ha) {
            is_good[B[i]] = false;
        }
    }

    int ans = 0;
    rep(i, N) {
        if (is_good[i]) ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4864
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define EB(x) emplace_back(x)
#define DEBUG(x) cout << (#x) << ": " << (x) << endl
#define DEBUG_VEC(v)            \
    cerr << #v << ": ";         \
    REP(__i, (v).size())        \
    cerr << ((v)[__i]) << ", "; \
    cerr << endl

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

class UnionFind
{

    std::vector<int> parent;

public:
    UnionFind(int n)
    {
        parent.resize(n, -1);
    }

    int root(int x)
    {
        while (parent[x] >= 0)
        {
            x = parent[x];
        }
        return x;
    }

    int size(int x)
    {
        return -parent[root(x)];
    }

    bool connect(int x, int y)
    {
        if (size(x) < size(y))
            std::swap(x, y);

        int root_x = root(x);
        int root_y = root(y);

        if (root_x == root_y)
            return false;

        parent[root_x] += parent[root_y];
        parent[root_y] = root_x;

        return true;
    }

    bool is_connected(int x, int y)
    {
        return (root(x) == root(y));
    }
};

int main()
{
    ios::sync_with_stdio(false);
    int N, M;

    cin >> N >> M;
    UnionFind uf(N + 1);

    cerr << endl;

    REP(i, M)
    {
        int x, y, z;
        cin >> x >> y >> z;
        uf.connect(x, y);
    }

    set<int> res;
    for (int i = 1; i <= N; ++i)
    {
        int r = uf.root(i);
        if (res.find(r) == res.end())
        {
            res.insert(r);
        }
    }

    cout << res.size() << endl;
    return 0;
}


Measured memory_bytes: 5376