akhauriyash/Code-Regression huggingface dataset:
N,M = (int(x) for x in input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
sc.sort()
broke = False
if N == 1:
    temp1 = 0
    temp2 = False
    if M == 0:
        print(0)
    else:
        for i in range(M):
            if temp2 == False:
                temp1 = sc[i][1]
                temp2 = True
            else:
                if sc[i][1] != temp1:
                    print(-1)
                    broke = True
                    break
        if broke == False:
            print(temp1)
elif N == 2:
    temp1 = [1,0]
    temp2 = [False,False]
    if M == 0:
        print(10)
    else:
        for i in range(M):
            if sc[i][0] == 1:
                if temp2[0] == False:
                    temp1[0] = sc[i][1]
                    temp2[0] = True
                else:
                    if sc[i][1] != temp1[0]:
                        print(-1)
                        broke = True
                        break
            else:
                if temp2[1] == False:
                    temp1[1] = sc[i][1]
                    temp2[1] = True
                else:
                    if sc[i][1] != temp1[1]:
                        print(-1)
                        broke = True
                        break
        if broke == False:
            if temp1[0] == 0:
                print(-1)
            else:
                map1 = map(str,temp1)
                print("".join(map1))
else:
    temp1 = [1,0,0]
    temp2 = [False,False,False]
    if M == 0:
        print(100)
    else:
        for i in range(M):
            if sc[i][0] == 1:
                if temp2[0] == False:
                    temp1[0] = sc[i][1]
                    temp2[0] = True
                else:
                    if sc[i][1] != temp1[0]:
                        print(-1)
                        broke = True
                        break
            elif sc[i][0] == 2:
                if temp2[1] == False:
                    temp1[1] = sc[i][1]
                    temp2[1] = True
                else:
                    if sc[i][1] != temp1[1]:
                        print(-1)
                        broke = True
                        break
            else:
                if temp2[2] == False:
                    temp1[2] = sc[i][1]
                    temp2[2] = True
                else:
                    if sc[i][1] != temp1[2]:
                        print(-1)
                        broke = True
                        break
        if broke == False:
            if temp1[0] == 0:
                print(-1)
            else:
                map1 = map(str,temp1)
                print("".join(map1))

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;



int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    int c = 0;
    rep(i,n) {
        if (a[i] < 0) c ^= 1;
    }
    ll ans = 0;
    rep(i,n) ans += abs(a[i]);
    if (c) {
        ll mn = 1e10;
        rep(i,n) {
            mn = min(mn, abs(a[i]));
        }
        ans -= mn*2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4028
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
using namespace std;

int main()
{
    char blood[3];
    map<string,int> count;
    while(scanf("%*d,%s",blood)!=EOF){
        count[blood]++;
    }
    cout<<count["A"]<<endl<<count["B"]<<endl<<count["AB"]<<endl<<count["O"]<<endl;
    return 0;
}

Measured memory_bytes: 1228
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll powmod(ll x, ll n) { // like pow(x, n)
  ll r = 1;
  while (n) {
    if (n & 1) {
      r = r * x % MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return r;
}

int main(int argc, char** argv) {
  int N;
  cin >> N;
  vector<ll> A(N);
  rep(i, N) {
    cin >> A[i];
  }

  vector<int> d;
  rep(i, N) {
    auto it = lower_bound(d.rbegin(), d.rend(), A[i]);
    if (it == d.rbegin()) {
      d.push_back(A[i]);
    } else {
      --it;
      *it = A[i];
    }
  }
  int ans = d.size();
  cout << ans << endl;
}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define INF 1145141919
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}

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 N, W;
ll w[100001], v[100001];
ll dp[110][1000000];

////////////////////////////////////////////////////////////////////
int main()
{
    cin >> N >> W;
    REP(i,N){
        cin >> w[i] >> v[i];
    }

    REP(i,N){
        REP(sum_w, W+1){
            if(sum_w-w[i]>=0){
                chmax(dp[i+1][sum_w], dp[i][sum_w-w[i]]+v[i]);
            }
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }

    cout << dp[N][W] << endl;

    return 0;
}


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

#define MN 1001000

using namespace std;
typedef long long ll;

ll n, ans, sxa, sbx, sba;
char s[MN]; string str;

int main() {
    scanf("%lld", &n);

    for(int i = 0; i < n; i++) {
        scanf("%s", s); str = s;
        for(int j = 1; j < str.size(); j++)
            if(str[j-1] == 'A' && str[j] == 'B') ans++;

        if(str[0] == 'B') {
            if(str.back() == 'A') sba++;
            else sbx++;
        } else {
            if(str.back() == 'A') sxa++;
        }
    }

    if(sxa && sbx) {
        sxa--; sbx--;
        ans += sba + 1;
        ans += min(sxa, sbx);
    } else if(sxa || sbx) {
        ans += sba;
    } else if(sba) {
        ans += sba - 1;
    }

    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()

ansCandi = []
for i in range(1,1000):
    a = (i+1)*i/2
    ansCandi.append(a)

if N not in ansCandi:
    print("No")
else:
    a = ansCandi.index(N)+1
    A = [[0] * (a+1) for _ in range(a+1)]

#    print(a)
    k = int(1)
    for i in range(a+1):
        for j in range(i+1,a+1):
            A[i][j] = k
            A[j][i] = k
            k += 1

    print("Yes")
    print(a+1)

    for v in A:
        v.remove(0)
        v.insert(0,a)

    for v in A:
        print(*v)






Measured memory_bytes: 9240
from collections import Counter


def check(A):
    N = len(A)
    even = Counter()
    odd = Counter()
    for i, a in enumerate(A):
        if i % 2 == 0:
            odd[a] += 1
        else:
            even[a] += 1
    
    even = even.most_common() + [(None, 0)]
    odd = odd.most_common() + [(None, 0)]
    
    if even[0][0] != odd[0][0]:
        return N - even[0][1] - odd[0][1]
    else:
        return min(N - even[0][1] - odd[1][1], N - odd[0][1] - even[1][1])

N = int(raw_input())
A = map(int, raw_input().split())

ans = check(A)
print ans

Measured memory_bytes: 18880
#include <iostream> 
#include <vector>
#define ll long long
using namespace std;
int main(){
    vector<int> stack;
    int n, arr[200005];
    ll score = 0, L[200005], R[200005];
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
        L[arr[i]]=1;
        if(i==1){
            stack.push_back(arr[i]);
        }
        else{
            while(!stack.empty() && stack.back()>arr[i]){
                L[arr[i]]+=L[stack.back()];
                stack.pop_back();
            }
            stack.push_back(arr[i]);
        }
    }
    stack.clear();
    for(int i=n; i>=1; i--){
        R[arr[i]]=1;
        if(i==n){
            stack.push_back(arr[i]);
        }
        else{
            while(!stack.empty() && stack.back()>arr[i]){
                R[arr[i]]+=R[stack.back()];
                stack.pop_back();
            }
            stack.push_back(arr[i]);
        }
    }
    for(int i=1; i<=n; i++){
        score += L[i]*R[i]*i;
    }
    cout << score << endl;
    return 0;
}

Measured memory_bytes: 8104
N, Q = gets.strip.split.map(&:to_i)
S = gets.strip

lr = Q.times.map { gets.strip.split.map(&:to_i) }

a = Array.new(N + 1) {0}

N.times do |i|
  a[i + 1] = S[i..(i+1)].eql?('AC') ? a[i] + 1 : a[i]
end

lr.each do |l, r|
  puts a[r - 1] - a[l - 1]
end


Measured memory_bytes: 11004
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=1;
    for(int i=0;i<s.size()-1;i++){
        if(s.at(i)!=s.at(i+1))
        ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3764
#include<iostream>
using namespace std;
int main(){
    int r,c,i,k,a,m,b,n;
  
    cin >>r>>c;
    int hyou[r+1][c+1];
    for( i=0; i<r+1; i++){
        
		for(int k=0; k<c+1; k++){
			hyou[i][k]=0;
		}
	}  
    for(i=0;i<r;i++){
        b=0;
        for(k=0;k<=c;k++){
            
            if(k<c){
        
                cin >>a;
                hyou[i][k]=a;
                b+=a;
                cout<<a<<" ";
            }
            else if(k==c){
                hyou[i][k]=b;
                cout<<b<<endl;
            }
        }
            
    }
    for(k=0;k<=c;k++){
        
        n=0;
        for(i=0;i<r;i++){
            n+=hyou[i][k];
            
        }
        hyou[r][k]=n;
        if(k!=c){
            cout<<n<<" ";
        }
        else{
            cout<<n;
        }
        
    }
    
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3096
from functools import reduce

A = input()
dic = {}
for c in A:
    if c in dic.keys():
        dic[c] += 1
    else:
        dic[c] = 1

length = len(A)
print(int(1 + (length * (length - 1) - reduce(lambda a, b: a + b * (b - 1), dic.values(), 0)) / 2))

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

inline bool is_happy(char cur,char lat)
{
	if (cur != '\0' && cur == lat)
		return true;
	else
		return false;
}

int main()
{
	int n, k, sum_happy = 0;
	cin >> n >> k;
	string str;
	char c;
	while (cin >> c)
		str.push_back(c);
	str.push_back('\0');
	for (int i = 0, j = 1; str[i] != '\0'; ++i, ++j)
		if (is_happy(str[i], str[j]))
			sum_happy++;
	cout << min(sum_happy + 2 * k, n - 1) << endl;
	return 0;
}

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

const int kN = 2e3 + 5;

char s[kN]; int x1, x2, x3, x4;

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for(int i = 1; i <= n; ++i) {
		if(s[i] == 'N') x1 = 1;
		if(s[i] == 'S') x2 = 1;
		if(s[i] == 'W') x3 = 1;
		if(s[i] == 'E') x4 = 1;
	}
	if((x1 ^ x2) || (x3 ^ x4)) printf("No\n");
	else printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> ans;
void bfs(ll n, ll m, ll num){
	queue<ll> q;
	q.push(num);
	while (!q.empty()){
		ll stepNum = q.front();
		q.pop();
		//cout<<stepNum<<endl;
        if (stepNum <= m && stepNum >= n)ans.push_back(stepNum);
		if (stepNum > m)continue;
        ll lastDigit = stepNum % 10;
        ll stepNumA = stepNum * 10 + (lastDigit- 1);
		ll stepNumB = stepNum * 10 + (lastDigit + 1);
		q.push(stepNum*10 + lastDigit);
        if (lastDigit == 0)q.push(stepNumB);
        else if(lastDigit == 9)q.push(stepNumA);
		else{
			q.push(stepNumA);
			q.push(stepNumB);
		}
	}
}
void displaySteppingNumbers(ll n, ll m){
	for (ll i=1;i<=9;i++)bfs(n, m, i);
}
int main(){
	ll n = 1, m = 3234566667;
	displaySteppingNumbers(n,m);
	sort(ans.begin(),ans.end());
	//for(ll i=0;i<20;i++)cout<<ans[i]<<" ";
	ll k;cin>>k;
	cout<<ans[k-1];
	return 0;
}


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

int main(){
  int n, a, b, c, d;
  cin >> n;
  a = n / 1000;
  b = (n / 100) % 10;
  c = (n / 10) % 10;
  d = n % 10;
  if(b == c){
    if((a == b) || (c == d)){
      cout << "Yes" << endl;
    }else {
      cout << "No" << endl;
    }
  }else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 384
// https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/3/ITP2_3_C
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> A(n);
    for (auto &x : A)
    {
        std::cin >> x;
    }
    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++)
    {
        int b, e, k;
        std::cin >> b >> e >> k;
        std::cout << std::count(A.begin() + b, A.begin() + e, k) << std::endl;
    }
    return 0;
}



Measured memory_bytes: 3120
//
//AtCoder Beginner Contest 137
//B - One Clue
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    int k, x;

    cin >> k >> x;

    int offset = x - (k-1);

    REP(i,k*2-1){
        cout << i+offset << " ";
    }
    cout << endl;
    return 0;
}


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

int main() {
  string s;
  vector<string> wh(3);
  wh.at(0) = "Sunny";
  wh.at(1) = "Cloudy";
  wh.at(2) = "Rainy";
  cin >> s;
  int i = 0;
  for(int j = 0;j < 3;j++){
    if(s  == wh.at(j)){
      i = j+1;
      if(i > 2){
        i = 0;
        break;
      }
    }
  }
  cout << wh.at(i) << endl;

  return 0;
}


Measured memory_bytes: 256
// FFT部分はtsutajさんのコードからコピペhttps://atcoder.jp/contests/atc001/submissions/2739303

#include <cassert>
#include <algorithm>
#include <cctype>
#include <complex>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <typeinfo>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REPD(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define PB(e) push_back(e)
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef long long ll;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}

// tsutajさんのコードからコピペhttps://atcoder.jp/contests/atc001/submissions/2739303
// https://atcoder.jp/contests/atc001/submissions/2739303

using Complex = complex<double>;
vector<Complex> dft(vector<Complex> A, int N, int sgn = 1) {
    if(N == 1) return A;
 
    vector<Complex> F(N / 2), G(N / 2);
    for(int i=0; i<N/2; i++) {
        F[i] = A[2 * i + 0];
        G[i] = A[2 * i + 1];
    }
 
    F = dft(F, N / 2, sgn);
    G = dft(G, N / 2, sgn);
 
    Complex zeta(cos(2.0 * M_PI / N), sin(2.0 * M_PI / N) * sgn);
    Complex pow_zeta = 1;
 
    for(int i=0; i<N; i++) {
        A[i] = F[i % (N / 2)] + pow_zeta * G[i % (N / 2)];
        pow_zeta *= zeta;
    }
    return A;
}
 
vector<Complex> inv_dft(vector<Complex> A, int N) {
    A = dft(A, N, -1);
    for(int i=0; i<N; i++) {
        A[i] /= N;
    }
    return A;
}
 
vector<Complex> multiply(vector<Complex> A, vector<Complex> B) {
    int sz = A.size() + B.size() + 1;
    int N = 1; while(N < sz) N *= 2;
 
    A.resize(N), B.resize(N);
    A = dft(A, N);
    B = dft(B, N);
 
    vector<Complex> F(N);
    for(int i=0; i<N; i++) {
        F[i] = A[i] * B[i];
    }
    return inv_dft(F, N);
}

const int P = 200003;

int main(int argc, char *argv[]) {
  int pow2[P * 2];
  pow2[0] = 1;
  unordered_map<int, int> num2coef;
  REP(i, P * 2 - 1) {
    if (i < P - 1) {
      num2coef[pow2[i]] = i;
    }
    pow2[i + 1] = (pow2[i] * 2) % P;
  }
  int N;
  cin >> N;
  vector<Complex> vec(P);
  vector<int> nums;
  REP(i, N) {
    int v;
    cin >> v;
    if (v > 0) {
      nums.push_back(v);
      vec[num2coef[v]] += Complex(1);
    }
  }

  vector<Complex> pol = multiply(vec, vec);
  ll res = 0;
  REP(i, pol.size()) {
    if (i < P * 2) {
      res += ll(pol[i].real() + 0.5) * pow2[i];
    }
  }

  REP(i, nums.size()) {
    res -= ll(nums[i]) * nums[i] % P;
  }
  cout << res / 2 << endl;
}


Measured memory_bytes: 82904
list = Array.new(4).map{Array.new(3).map{Array.new(10,0)}}
n  = gets.chomp.to_i

n.times do
  b,f,r,v = gets.chomp.split(" ").map(&:to_i)
  list[b-1][f-1][r-1] += v
end

list.each_with_index do |b,i|
  b.each do |f|
    puts " " + f.join(" ")
  end
  puts "#"*20 if i != b.size
end

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

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

    int v = 1;
    int count = 0;
    while (v <= n) {
        string s = to_string(v);
        if (strlen(s.data()) % 2 == 1) {
            count++;
        }
        v++;
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 256
using System;

namespace A___Colorful_Transceivers
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var a = int.Parse(input[0]);
            var b = int.Parse(input[1]);
            var c = int.Parse(input[2]);
            var d = int.Parse(input[3]);
            if (Math.Abs(a - c) <= d || (Math.Abs(a - b) <= d && Math.Abs(b - c) <= d))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string.h>
#include <deque>
#define REP(i,j,n) for(int i=j;i<n;i++)
#define SORT(x) sort(x.begin(),x.end())

using namespace std;

int main() {
	int n,count=0;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)cin >> v[i];
	for (int i = 0; i < n; i++) {
		int min=v[i],zi=i;
		for (int j = i; j < n; j++) {
			if (min > v[j]) {
				min = v[j];
				zi = j;
			}
		}
		if (v[i] > v[zi]) {
			int swap;
			swap = v[i];
			v[i] = v[zi];
			v[zi] = swap;
			count++;
		}
	}

	for (int i = 0; i < n; i++) {
		if (i != n - 1)cout << v[i] << " ";
		else cout << v[i] << endl;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n+1); i++)
//二項係数の計算
int nCr(int A, int B) {
    ll ans = 1;
    for (int i = 0; i < B; i++) {
        ans *= A - i;
    }
    for (int i = 0; i < B; i++) {
        ans /= i + 1;
    }
    return ans;
}
// vector<vector<int>> A(3, vector<int>(4));
int main() {
    string S;
    cin>>S;
    vector<int>A(26);
    rep(i,S.size()){
        A[int(S[i])-97]++;
    }
    bool ans=true;
    rep(i,26){
        if(A[i]%2!=0){
            ans=false;
            break;
        }
    }
    if(ans==true){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


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

int dis(int x, int y){
    return max(x-y, y-x);
}

int main(){
    int n;
    bool ans = true;
    cin >> n;
    vector<int> t(n+1);
    vector<int> x(n+1);
    vector<int> y(n+1);
    for(int i = 1 ; i <= n ; i++){
        cin >> t[i] >> x[i] >> y[i];
    }
    for(int i = 1 ; i <= n ; i++){
        int a = t[i] - t[i-1], b = dis(x[i], x[i-1]) + dis(y[i], y[i-1]);
        if(a < b || a % 2 != b % 2){
            ans = false;
            break;
        }
    }
    if(ans){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int i,n,state,cc;
char snake[20000];

int main(){
	for(scanf("%d",&n);n>0;n--){
		scanf("%s",snake);
		if(strlen(snake)%2==0 && strlen(snake)>4){
			if(strncmp(snake,">'",2)==0 && snake[strlen(snake)-1]=='~'){
				for(i=2;i<strlen(snake)-1;i++){
					if(snake[i]!=(i==strlen(snake)/2 ? '#' : '='))break;
				}
				if(i>=strlen(snake)-1){printf("A\n");continue;}
			}
			else if(strncmp(snake,">^",2)==0 && strncmp(&snake[strlen(snake)-2],"~~",2)==0){
				for(i=2;i<strlen(snake)-2;i++){
					if(snake[i]!=(i%2 ? '=' : 'Q'))break;
				}
				if(i>=strlen(snake)-2){printf("B\n");continue;}
			}
		}
		printf("NA\n");
	}
	return 0;
}

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

template<typename T, typename U> bool chmin(T &a, const U &b) {
	return (a > b ? a = b, true : false);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
	return (a < b ? a = b, true : false);
}
const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;

ll d[1100][20010];
int A[1100],B[1100];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int h,n;cin>>h>>n;

	for(int i=0; i<1005; i++){
		for(int j=0; j<20000; j++){
			d[i][j] = INF;
		}
	}
	d[0][0] =0;

	for(int i=0; i<n; i++){
		int a,b;cin>>a>>b;

		A[i] = a; B[i] = b;
	}

	for(int i=0; i<n; i++){
		for(int j=0; j<10010; j++){

			if(j <A[i]){
				d[i+1][j] = d[i][j];
			}else {

		/*		if(d[i][j-A[i]] !=INF){*/
					d[i+1][j] = min(d[i][j],d[i+1][j-A[i]]+B[i]);
/*				}*/
			}
		}
	}

/*	for(int i=0; i<=n; i++){
		for(int j=0; j<=h+A[i]; j++){
			cout<<d[i][j]<<" ";
		}
		cout<<endl;
	}*/


		ll ans = 100000000;
		for(int j=h; j<=20000; j++){
	/*		cout<<d[n][j]<<" ";*/
			if(d[n][j])ans = min(ans,d[n][j]);
		}
	/*	cout<<endl;
*/
		cout<<ans<<endl;
}


Measured memory_bytes: 157952
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>

using namespace std;

typedef long long ll;
const ll nmax = 1e9 + 7;
const ll mod = 998244353;
const double PI = 2 * asin(1);

int main(){

  int N, K; cin >> N >> K;
  ll R, S, P; cin >> R >> S >> P;
  string T; cin >> T;

  vector <bool> win(N);

  ll ans = 0;
  for (int i = 0; i < N; i++){
    if (i < K){
      win[i] = true;
      if (T[i] == 's'){
        ans += R;
      }else if (T[i] == 'p'){
        ans += S;
      }else{
        ans += P;
      }
    }else{
      if (win[i - K] == true && T[i] == T[i - K]){
        /* code */
      }else{
        win[i] = true;
              if (T[i] == 's'){
        ans += R;
      }else if (T[i] == 'p'){
        ans += S;
      }else{
        ans += P;
      }
        
      }
    }
  }
  cout << ans << endl;
  

  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;
int main(){
    ll h,w,K,mod=1e9+7,d[101][9]={0};
    cin>>h>>w>>K;
    d[0][0]=1;
    rep(i,h){
        rep(j,pow(2,w-1)){
            int p=j,B[8]={0},z=1;
            rep(k,w-1) B[k]=p%2,p=p/2;
            rep(k,w-2) if(B[k]&&B[k+1]) z=0;
            if(z)rep(k,w){
                if(B[k-1]) d[i+1][k-1]+=d[i][k]%mod;
                else if(B[k]) d[i+1][k+1]+=d[i][k]%mod;
                else d[i+1][k]+=d[i][k]%mod;
            }
        }
    }
    cout<<d[h][K-1]%mod;
}

Measured memory_bytes: 384
MOD = 10 ** 9 + 7
n, m = map(int, input().split())

if abs(n - m) >= 2:
	print(0)

else:
	n, m = (max(n, m), min(n, m))
	ans = 1
	for i in range(1, m + 1):
		ans = (ans * i) % MOD

	if n == m:
		print((ans ** 2 * 2) % MOD)
	else:
		print((ans ** 2 * n) % MOD)

Measured memory_bytes: 3064
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

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

    cout << 3 * r * r << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<int(n);i++)
using namespace std;
int main() {
	int n,ans=0;
	string s;

	cin >>n;
	cin >>s;
	rep(i,n-2){
		if (s.substr(i,3)=="ABC"){
			ans++;
		}
	}
	cout << ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ld long double
#define dd double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef vector<pll> vplll;
ll mod = 1e9+7;
const ld PI = 2 * acos(0.0);
const vector<ll> dx = {1, -1, 0, 0};
const vector<ll> dy = {0, 0, 1, -1};
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define len(x) (ll) x.length()
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))
long double dp[3001][3001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,c,t,n,m,k,q; 
    t = 1;
    // cin>>t;
    while(t--)
    {
    	cin>>n;
    	long double ar[n];
    	for(int i=0;i<n;i++)
    		cin>>ar[i];
    	dp[0][0] = 1;
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<=i+1;j++)
    		{
    			if(j!=0)
    			dp[i+1][j] = dp[i][j]*(1-ar[i]) + dp[i][j-1]*(ar[i]);
    			else
    			dp[i+1][j] = dp[i][j]*(1-ar[i]);
    		}
    	}
    	long double ans = 0;
    	for(int j=(n+1)/2;j<=n;j++)
    	{
    		ans += dp[n][j];
    	}
    	// cout<<ans<<endl;
    	printf("%.12Lf \n",ans);
    }
    return 0;
}

Measured memory_bytes: 139136
#include <iostream>
#include <string>

using namespace std;

int A[3];
string ans;

int main()
{
    cin >> A[0] >> A[1] >> A[2];
    ans = (A[0] + A[1] + A[2] >= 22) ? "bust" : "win";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i= s; i <t; i++)
using LL = long long; using ll = long long;
const int INF = 1e9;
const LL LINF = 1e18;
using pii = pair<int, int>; using PII = pii;
using PLL = pair<LL, LL>; using pll = PLL;


void solve() {
	const string str = "AIDUNYAN";
	int key[26] = { 0 };
	for (auto c : str) {
		key[c - 'A']++;
	}
	string D; cin >> D;
	vector<vector<int>> cusum(D.length() + 1, vector<int>(26));
	for (int i = 0; i < D.length(); i++) {
		for (int j = 0; j < 26; j++) {
			cusum[i + 1][j] += cusum[i][j];
		}
		cusum[i + 1][D[i] - 'A']++;
	}
	string ans;
	for (int i = 0; i < D.length(); i++) {
		int j = i + str.length();
		if (j > D.length()) {
			ans += D[i];
			continue;
		}
		else {
			bool ok = true;
			for (int k = 0; k < 26; k++) {
				if (cusum[j][k] - cusum[i][k] == key[k]) continue;
				ok = false;
			}
			if (ok) {
				ans += "AIZUNYAN";
				i += str.length() - 1;
			}
			else {
				ans += D[i];
			}
		}
	}
	cout << ans << endl;
}

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

	return 0;
}


Measured memory_bytes: 3384
# coding=utf-8

###
### for python program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_check(self, n):
        if (n==1):
            return False
        elif (n==2):
            return True
        else:
            for x in range(2,n):
                if(n % x==0):
                    return False
            return True

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
# print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
# print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
# print(" {}".format(i), end="")

# def printA(A):
#     for i, n in enumerate(A):
#         print(n, end='')
#         if i != N-1:
#             print(' ', end='')
#     print()

# リスト内包表記 ifあり
# [x-k if x != 0 else x for x in C]

# ソート
# N = N.sort()

# 10000個の素数リスト
# P = mymath.pnum_eratosthenes(105000)

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

def dist(A, B):
    d = 0
    for i in range(len(A)):
        d += (A[i]-B[i])**2            
    d = d**(1/2)
    return d

def get_input():
    N = []
    while True:
        try:
            N.append(input())
            #N.append(int(input()))
            #N.append(float(input()))
        except EOFError:
            break
    return N

data = get_input()
data = data[1:]

rui = 0
out = 0

ans = 0

for s in data:
    if s == 'HIT':
        if rui != 3:
            rui += 1
        else:
            ans += 1
    elif s == 'OUT':
        if out != 2:
            out += 1
        else:
            print(ans)
            out = 0
            rui = 0
            ans = 0
    elif s == 'HOMERUN':
        ans += (rui+1)
        rui = 0




Measured memory_bytes: 5648
N = int(input())
dp = [[0 for _ in range(3)] for i in range(N)]
a,b,c = list(map(int,input().split()))
dpa = a
dpb = b
dpc = c
for i in range(1,N):
    dpap = dpa
    dpbp = dpb
    dpcp = dpc
    a,b,c = list(map(int,input().split()))
    dpa = max(dpbp + a, dpcp + a)
    dpb = max(dpap + b, dpcp + b)
    dpc = max(dpap + c, dpbp + c)
print(max(dpa,dpb,dpc))



Measured memory_bytes: 14844
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}
vector<long long> dev;
vector<int> id;

void prime_factor(long long N){
    for(int i=2;(long long)i*i<=N;i++){
        int cnt = 0;
        while(N%i == 0){
            cnt++;
            N /= i;
        }
        if(cnt){
            dev.push_back(i);
            id.push_back(cnt);
        }
    }
    if(N != 1){
        dev.push_back(N);
        id.push_back(1);
    }
    return;
}

template <typename T>
void extgcd(T a, T b, T& x, T& y)
{
    if(b != 0){
        extgcd(b,a%b,y,x);
        y -= (a/b)*x;
    }else{
        x = 1;
        y = 0;
    }
}

ll p[10000];
ll mi = 1LL<<60;
ll n;
void dfs(ll K,int id){
    if(id==dev.size()){
        ll x = K;
        ll y = n/K;
        if(x==1||y==1){
            if(n%2==0){
                chmin(mi,2*n-1);
            }else{
                chmin(mi,n-1);
            }
            return;
        }
        ll a,b;
        extgcd(x,y,a,b);
        // cerr << x << " " << y << " " << a << " " << b << endl;
        chmin(mi,min(abs(x*a),abs(y*b)));
    }else{
        dfs(K*p[id],id+1);
        dfs(K,id+1);
    }
}
int main(){
    
    cin >> n;
    if(n==1){
        cout << 1 << endl;
        return 0;
    }
    n*=2;
    prime_factor(n);
    for(int i=0;i<dev.size();i++){
        ll c = 1;
        for(int j=0;j<id[i];j++){
            c *= dev[i];
        }
        p[i] = c;
    }
    dfs(1,0);
    cout << mi << endl;
    return 0;
}


Measured memory_bytes: 3604
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = int(input())
diff = (a[1]-b[1])*t # 1秒ごとに縮まる
adiff = abs(a[0]-b[0]) # 元々の差
if diff >= adiff:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 9188
DBG = !true


def ufinit(n)
  $ufsz = Array.new(n,1)
  $ufances = Array.new(n)
  for i in 0...n
    $ufances[i] = i
  end
end

def ufroot(x)
  a = []
  y = x
  while $ufances[y] != y
    a << y
    y = $ufances[y]
  end
  for z in a
    $ufances[z] = y
  end
  return y
end

def ufconn(x,y)
  i = ufroot(x)
  j = ufroot(y)
  return if i==j
  #k  = [i,j].min
  k  = ($ufsz[i]<$ufsz[j]) ? j : i
  if k==j
    $ufances[i] = j
  else
    $ufances[j] = i
  end
  $ufsz[k] = $ufsz[i] + $ufsz[j]
end

n,m = gets.split.map{|z| z.to_i}
a = []
b = []
for i in 0...m
  aa,bb = gets.split.map{|z| z.to_i}
  a << aa-1
  b << bb-1
end


ufinit(n)
sum = n*(n-1)/2
ans = Array.new(n)
ans[m-1] = sum
if DBG
  print a
  puts " - a"
  print b
  puts " - b"
  print $dboss
  puts " - dboss"
end
(m-1).downto(1) { |z|
  x = a[z]
  y = b[z]  # x<y
  i = ufroot(x)
  j = ufroot(y)
  if i==j
    ans[z-1] = sum
    next
  end
  p = $ufsz[i]
  q = $ufsz[j]
  sum -= ((p+q)*(p+q-1)-p*(p-1)-q*(q-1))/2 if sum > 0
  ufconn(x,y)
  ans[z-1] = sum
}
for i in 0...m
  puts "#{ans[i]}"
end
#puts ""



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

typedef long long ll;

int main(void){
    int n; cin >> n;
    int odd = 0;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        if (a % 2 == 1) {
            odd++;
        }
    }
    if (odd == 0) {
        cout << "second" << endl;
    } else {
        cout << "first" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cnt = 0

for i in range(10 ** 5):
    for j in range(len(a)):
        if a[j] % 2 != 0:
            print(cnt)
            exit()
        else:
            a[j] /= 2
    cnt += 1


Measured memory_bytes: 3064
s = gets.chomp
f, c = 0, 0
p = []
0.upto(s.size - 1) do |i|
  if s[i] == 'R' && f == 1
    f = 0
    p.push(c)
    c = 0
  elsif s[i] == 'L' && f == 0
    f = 1
    p.push(c)
    c = 0
  end
  c += 1
  p.push(c) if s.size - 1 == i
end
ans = ''
while p.size > 0
  x = p.shift
  y = p.shift
  if (x + y).even?
    (x - 1).times do
      ans.concat('0 ')
    end
    ans.concat(((x + y) / 2).to_s)
    ans.concat(' ')
    ans.concat(((x + y) / 2).to_s)
    ans.concat(' ')
    (y - 1).times do
      ans.concat('0 ')
    end
  elsif (x.even?)
    (x - 1).times do
      ans.concat('0 ')
    end
    ans.concat(((x + y) / 2).to_s)
    ans.concat(' ')
    ans.concat(((x + y) / 2 + 1).to_s)
    ans.concat(' ')
    (y - 1).times do
      ans.concat('0 ')
    end
  else
    (x - 1).times do
      ans.concat('0 ')
    end
    ans.concat(((x + y) / 2 + 1).to_s)
    ans.concat(' ')
    ans.concat(((x + y) / 2).to_s)
    ans.concat(' ')
    (y - 1).times do
      ans.concat('0 ')
    end
  end
end
puts ans

Measured memory_bytes: 3448
from operator import itemgetter

N = int(input())
work = list()
for i in range(0, N):
    A, B = map(int, input().split())
    work.append([A, B])

total = 0
work.sort(key=itemgetter(1))

flag = True
for [a, b] in work:
    total = total + a
    if total > b:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")


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

int main() {
	int n, m, mx[110], mn[110], ans = 0, cnt = 0;
	string s[110], t[110];

	cin >> n;
	for (int i = 0; i < n; i++) cin >> s[i];
	cin >> m;
	for (int i = 0; i < m; i++) cin >> t[i];

	for (int i = 0; i < n; i++) {
		cnt = 0;
		for (int j = 0; j < n; j++) {
			if (s[i] == s[j]) cnt++;
		}		
		for (int j = 0; j < m; j++) {
			if (s[i] == t[j]) cnt--;
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
n,m,l = gets.split(" ").map{|x| x.to_i}
l_mat =Array.new()
r_mat=Array.new()
n.times do |i|
    l_mat[i]=gets.split(" ").map{|x| x.to_i}
end
m.times do |i|
    r_mat[i]=gets.split(" ").map{|x| x.to_i}
end
ans_mat=Array.new()
n.times do |i|
    ans_mat[i]=Array.new(l)
    l.times do |j|
        ans_mat[i][j]=0
        m.times do |k|
            ans_mat[i][j]+=l_mat[i][k]*r_mat[k][j]
        end
    end
end
n.times do|i|
    l.times do |j|
        print(ans_mat[i][j])
        if(j!=l-1)
            print(" ")
        end
    end
    puts()
end


Measured memory_bytes: 7204
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <queue>
using namespace std;
using ll = long long;
const int mod = 1000000007;
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main(){
    ll N,M;
    cin>>N>>M;
    vector<ll> A(M),B(M);
    for(ll i=0;i<M;i++){
        cin>>A[i]>>B[i];
        A[i]--;B[i]--;
    }
    vector<ll> res(M);
    UnionFind tree(N);
    ll cur=N*(N-1)/2;
    for(ll i=1;i<=M;i++){
        res[M-i] = cur;
        if(tree.issame(A[M-i],B[M-i]))continue;
        ll sa = tree.size(A[M-i]),sb=tree.size(B[M-i]);
        cur -= sa*sb;
        tree.merge(A[M-i],B[M-i]);
    }
    for(ll i=0;i<M;i++){
       cout<<res[i]<<"\n";
    }
}

Measured memory_bytes: 4096
N,K=map(int,input().split())
x=[int(i) for i in input().split()]

cost=10**13

for i in range(N-K+1):
    c=x[i+K-1]-x[i]+min(abs(x[i]),abs(x[i+K-1]))
    cost=min(cost,c)

print(cost)

Measured memory_bytes: 14384
n, q = gets.chomp.split.map(&:to_i)
s = gets.chomp
ac = Array.new(n + 1, 0)
1.step(n) do |i|
  ac[i] += ac[i - 1]
  next if s[i - 1] != "C"
  if i > 1 && s[i - 2] == "A"
    ac[i] += 1
  end
end

q.times do |_|
  l, r = gets.chomp.split.map(&:to_i)
  puts ac[r] - ac[l]
end

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

using namespace std;

typedef long long I64;

int main()
{
    I64 N;
    cin >> N;
    for( int sum = 17 * 9;  sum >= 1;  --sum ) {
        int full = sum / 9;
        int rest = sum % 9;
        I64 nr = rest;
        for( int i = 1;  i <= full;  ++i )
            nr = nr * 10LL + 9;
        if( nr <= N ) {
            cout << sum << '\n';
            return 0;
        }
    }
    cout << "1\n";
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
	long long nx,np,n1;

	np=1;
	scanf("%lld",&n1);
	for (nx=1;nx<=n1;nx++){
		np=(np*nx)%1000000007;
	}
	printf("%d",np);
	
	return 0;
}

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

int main(){
  
  string S; cin >> S;
  int former = std::stoi(S.substr(0,2));
  int latter = std::stoi(S.substr(2,2));
  //cout << former << endl; //test
  //cout << latter << endl; //test
  
  if (former == 0){
    //この時点で前者はY確定
    if (latter == 0){
      //後者もYはありえない
      cout << "NA" << endl;
    }else if (latter < 13){
      cout << "YYMM" << endl;
    }else{
      //後者もYはありえない
      cout << "NA" << endl;
    }
  }else if(former < 13){
    //前者はYかMかわからない
    if (latter == 0){
      cout << "MMYY" << endl;
    }else if (latter < 13){
      //どちらもありえる
      cout << "AMBIGUOUS" << endl;
    }else{
      cout << "MMYY" << endl;
    }
  }else{
    //この時点で前者はY確定
    if (latter == 0){
      //後者もYはありえない
      cout << "NA" << endl;
    }else if (latter < 13){
      cout << "YYMM" << endl;
    }else{
      //後者もYはありえない
      cout << "NA" << endl;
    }
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
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; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    string s;
    cin >> s;
    if(s[s.size()-1]!='s'){
        s+='s';
    }
    else{
        s+="es";
    }
    cout << s;
    
    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define l long long
int main(){
	
	
	string s,t,u;
	cin>>s>>t;
	int a, b;
	cin>>a>>b;
	cin>>u;
	if(u == s) a-=1;
	else b-=1;
	cout<<a<<" "<<b;
	return 0;
}


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

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
int main(){
  string s;
  cin>>s;
  int cnt=0;
  for(int i=0;i<s.size();i++)
    {
      string a=s.substr(0,i);
      if(a=="")
	a="0";
      string b=s.substr(i,s.size()-i);
      if(b=="")
	b="0";
      if(b[0]=='0')
	continue;
      int x=(toInt(a)+toInt(b))/2;
      int y=(toInt(a)-toInt(b))/2;
      if(y<0)
      	y=-y;
      string aa=toString(x-y);
      if(aa=="0")
	aa="";
      string bb=toString(x+y);
      if(bb=="0")
	bb="";
      if(s==aa+bb && x>=0 && y>=0)
	{
	  //	  cout<<"Hit"<<x<<" "<<y<<endl;
	  cnt++;
	}
      //      else
      //	cout<<x<<" "<<y<<endl;
    }
  cout<<cnt<<endl;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);
    Int(m);

    while (m) {
        vi code(m);
        rep(i, m) {
            cin >> code[i];
        }
        vi x(n);
        rep(i, n) {
            cin >> x[i];
        }
        vvi dp(n, vi(256, INF));
        int st = 128;
        rep(i, m) {
            int tmp = st + code[i];
            tmp = (tmp < 0) ? 0 : tmp;
            tmp = (tmp > 255) ? 255 : tmp;
            dp[0][tmp] = min(dp[0][tmp], (x[0] - tmp) * (x[0] - tmp));
        }
        rep(i, n-1) {
            rep(j, 256) {
                if (dp[i][j] != INF) {
                    st = j;
                } else {
                    continue;
                }
                rep(k, m) {
                    int tmp = st + code[k];
                    tmp = (tmp < 0) ? 0 : tmp;
                    tmp = (tmp > 255) ? 255 : tmp;
                    dp[i+1][tmp] = min(dp[i+1][tmp], 
                            dp[i][j] + (x[i+1] - tmp) * (x[i+1] - tmp));
                }
            }
        }
        int ret = INF;
        rep(i, 256) {
            ret = min(ret, dp[n-1][i]);
        }
        cout << ret << endl;
        cin >> n >> m;
    }

    return 0;
}

Measured memory_bytes: 43816
import Data.List
f n x=if x==0 then 0 else if even x then f (n+1) (x`div`2) else n
main=do
 q<-map read.words<$>getLine :: IO [Int]
 let s=sort q
     p=map(f 0)[s!!1-head s,last s-head s,last s-s!!1]
 print$if all(==(0))p && even(head s) then -1 else minimum p

Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    string s;
    cin >> s;
    int ans;
    if (s == "SUN") ans = 7;
    else if (s == "MON") ans = 6;
    else if (s == "TUE") ans = 5;
    else if (s == "WED") ans = 4;
    else if (s == "THU") ans = 3;
    else if (s == "FRI") ans = 2;
    else if (s == "SAT") ans = 1;
    cout << ans << endl;
}

Measured memory_bytes: 256