akhauriyash/Code-Regression huggingface dataset:
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector<PII> stone[155];
int dp[155][15][100];
signed main(void)
{
  while(true) {
  int n, m;
  cin >> n >> m;
  if(!n) break;
  REP(i, n) {
    int k;
    cin >> k;
    stone[i].clear();
    REP(j, k) {
      int x, d;
      cin >> x >> d;
      stone[i].PB({x, d});
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  REP(i, stone[0].size()) dp[0][i][0] = 0;
  REP(i, stone[1].size()) dp[1][i][1] = 0;
  // i??????j??? ???????£???°??????k????????£???
  REP(i, n-1) REP(j, stone[i].size()) REP(k, m+1) {
    if(dp[i][j][k] == 0x3f3f3f3f) continue;
    // (i, j)?????????????£???°??????????????¨???
    // dp[i+1][l][k] ??? min??§??´??°
    REP(l, stone[i+1].size()) {
      int dif = abs(stone[i][j].first - stone[i+1][l].first);
      int tmp = dif*(stone[i][j].second + stone[i+1][l].second);
      chmin(dp[i+1][l][k], dp[i][j][k] + tmp);
    }

    // (i, j)?????????????£???°???????????¨???
    // dp[i+2][l][k+1] ??? min??§??´??°
    if(i == n-2 || k == m) continue;
    REP(l, stone[i+2].size()) {
      int dif = abs(stone[i][j].first - stone[i+2][l].first);
      int tmp = dif*(stone[i][j].second + stone[i+2][l].second);
      chmin(dp[i+2][l][k+1], dp[i][j][k] + tmp);
    }
  }

  // n-1?????????min???n-2????????§m-1??\??????min
  int ret = INF;
  REP(i, stone[n-1].size()) REP(k, m+1) chmin(ret, dp[n-1][i][k]);
  REP(i, stone[n-2].size()) REP(k, m) chmin(ret, dp[n-2][i][k]);
  cout << ret << endl;
  }

  return 0;
}

Measured memory_bytes: 4036
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        long X = scan.nextLong();
        X = Math.abs(X);
        long K = scan.nextLong();
        long D = scan.nextLong();
        
        if(K <= X/D){
            System.out.println(Math.abs(X-D*K));
            return;
        }
        
        K -= X/D;
        X %= D;
        
        if(K%2==0) System.out.println(Math.abs(X));
        else System.out.println(Math.abs(X-D));
    }
}

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

using namespace std;

int main()
{
    int a[100];int n,m,x;
    scanf("%d %d %d",&n,&m,&x);
    int i,tou=0,we=0;
    for(i=0;i<m;i++)
    {scanf("%d",&a[i]);
    if(a[i]<x)
        tou++;
    else
        we++;
    }
    if(we<tou)
        tou=we;
    printf("%d\n",tou);
    return 0;
}


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

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  set<int> x;
  while (n--) {
    int a;
    scanf("%d", &a);
    if (x.find(a) != x.end()) {
      x.erase(a);
    } else {
      x.insert(a);
    }
  }
  printf("%d\n", (int) x.size());
  return 0;
}

Measured memory_bytes: 4864
import java.util.Scanner;

public class Main {

    private static boolean[] prime = new boolean[100001];

    private static boolean isPrime(int x) {
        if (x < 2) {
            return false;
        } else if (x == 2) {
            return true;
        }
        if (x % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        int[] l = new int[q];
        int[] r = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
        }
        for (int i = 2; i <= 100000; i++) {
            prime[i] = isPrime(i);
        }
        int[] primeSum = new int[100001];
        int sum = 0;
        for (int i = 0; i <= 100000; i++) {
            if (prime[i] && prime[(i + 1) / 2]) {
                sum++;
            }
            primeSum[i] = sum;
        }
        for (int i = 0; i < q; i++) {
            System.out.println(primeSum[r[i]] - primeSum[l[i] - 1]);
        }
    }

}


Measured memory_bytes: 74140
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300001;
int len;
string input;
bool ismonth(char a, char b){
	if(a == '0' and b == '0')return false;
	if(a == '0')return true;
	if(a == '1' and b <= '2')return true;
	return false;
}
int main(){
	cin >> input;
	if(ismonth(input[0], input[1])){
		if(ismonth(input[2], input[3]))cout << "AMBIGUOUS\n";
		else cout << "MMYY\n";
	}
	else if(ismonth(input[2], input[3]))cout << "YYMM\n";
	else cout << "NA\n";
}


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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)
#define BR "\n"

vector<int> face(6);
void rotate(char d) {
  vector<int> newFace(6);
  newFace = face;
  if (d == 'N') {
    newFace[0] = face[1];
    newFace[1] = face[5];
    newFace[5] = face[4];
    newFace[4] = face[0];
  } else if (d == 'S') {
    newFace[0] = face[4];
    newFace[1] = face[0];
    newFace[5] = face[1];
    newFace[4] = face[5];
  } else if (d == 'E') {
    newFace[0] = face[3];
    newFace[2] = face[0];
    newFace[5] = face[2];
    newFace[3] = face[5];
  } else if (d == 'W') {
    newFace[0] = face[2];
    newFace[2] = face[5];
    newFace[5] = face[3];
    newFace[3] = face[0];
  }
  face = newFace;
}

int main() {
  rep0(i, 6) cin >> face[i];
  int q; cin >> q;

  string s = "NEWS";

  rep0(i, q) {
    int u, f;
    cin >> u >> f;
    while (true) {
      char c = s[rand() % 4];
      rotate(c);
      if (face[0] == u && face[1] == f) {
        cout << face[2] << BR;
        break;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 3168
n=gets.to_i
edges = (1...n).map do
  u,v=gets.split(' ').map(&:to_i)
  u,v=v,u if u>v
  [u,v]
end
count=edges.sum do |tuple|
  tuple[0]*(n+1-tuple[1])
end
p n*(n+1)*(n+2)/6-count

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

using namespace std;

typedef long long ll;

const ll ts = 100005;

#define IOS  ios::sync_with_stdio(0); cin.tie(0);
#define endl "\n"

signed main() {

    IOS;
    int h , a; cin >> h >> a;
    int x = h / a; 
    h = h % a; 
    x = x + (h != 0);
    cout << x; 
    
 }


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;
using namespace std;

void Main()
{
   string str;
   cin >> str;
   vector<int> ans(10);
   int i, j = 0;
   for (i = 0; i < str.length(); i++)
   {
      switch (str[i])
      {
      case 'A':
      case 'C':
      case 'G':
      case 'T':
         ans[j]++;
         break;
      default:
         j++;
         break;
      }
   }
   cout << *max_element(ans.begin(), ans.end()) << endl;
}

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

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };




signed main() {
	ll s;
	vector<int>list;

	cin >> s;

	list.push_back(s);

	while (true)
	{

		if (s % 2 == 0) {
			s = (s / 2);
		}
		else {
			s = (3 * s + 1);
		}

		list.push_back(s);

		for (int i = 0; i < list.size() - 1; i++) {
			if (list[i] == s) {
				cout << list.size() << endl;
				return 0;
			}
		}

	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll ; 
typedef long double ld ;
typedef pair<ll , ll> pll ;

const ll N = 2e2 + 30 , Mod = 1e9 + 7 ;
const ll SQ = 330 ;

char a[N][N] ;
ll cnt[N] , cnt2[N] ;

ll c2(ll x) {
	return x * (x - 1) / 2 ;
}
int main () {
    ios::sync_with_stdio(0), cin.tie(0) ;
    ll n ;
    cin >> n ;
    ll cur = 0 ;
    for (int i = 0 ; i  < n ; i ++) {
    	ll x ;
    	cin >> x ;
    	cur += (x & 1) ;
	}
	if (cur & 1) cout << "NO" ;
	else cout << "YES" ;
    return (0) ;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;

int count(const vector< vector<int> > &G, int v, int p, int dist, int dist_max){
  if(dist > dist_max) return 0;
  int ret = 1;
  for(size_t i = 0; i < G[v].size(); ++i){
    int v_ = G[v][i];
    if(v_ == p) continue;
    ret += count(G,v_,v,dist+1,dist_max);
  }
  return ret;
}

int main(){
  int N, K;
  cin >> N >> K;
  vector< vector<int> > T(N);
  for(int i = 0; i < N-1; ++i){
    int a, b;
    cin >> a >> b;
    --a,--b;
    T[a].push_back(b);
    T[b].push_back(a);
  }
  int ans = N;
  if(K%2){
    for(int i = 0; i < N; ++i){
      for(size_t j = 0; j < T[i].size(); ++j){
        int k = T[i][j];
        ans = min(ans,N-count(T,i,k,0,K/2)-count(T,k,i,0,K/2));
      }
    }
  }else{
    for(int i = 0; i < N; ++i){
      ans = min(ans,N-count(T,i,-1,0,K/2));
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
N,M = map(int, input().split())
S = [list(map(int, input().split())) for i in range(M)]
 
Mini = 0
Max = N
 
for i in range(M):
    if Mini <= S[i][0]:
        Mini = S[i][0]
    if Max >= S[i][1]:
        Max = S[i][1]
print(max(Max-Mini+1,0))

Measured memory_bytes: 60248
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
res = 0
for i in range(n):
    if i != 0 and a[i] == a[i-1]:
        continue
    ko = bisect.bisect_right(a,a[i]) - i
    if ko > a[i]:
        res += ko - a[i]
    elif ko < a[i]:
        res += ko

print(res)

Measured memory_bytes: 63856
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int INF = 1e6 + 10, A = 5e3 + 10;
int main() {
    fast_cin();
    int n,k;
    cin>>n;
    cin>>k;
    vector<int>h(n);
    for(int i=0;i<n;i++) {
            cin>>h[i];
    }
    vector<int>dp(n,2147483647);
    dp[0]=0;
    for(int i=1;i<n;i++) {
        for(int j=0;j<=k&&j<=i;j++) {
            
                dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));  
        }
    }
    cout<<dp[n-1];
      
}


Measured memory_bytes: 1024
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long n = in.nextInt();
            long ans = (n * (n - 1)) / 2;
            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



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

using namespace std;

#define ll long long
#define ld long double
#define pll pair <ll , ll>

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair

#define X first
#define Y second

#define LB(x) ((x) & -(x))
#define BIT(a , b) (((a)>>(b)) & 1)

map < pair <string , string> , ll > w;

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

	ll n , res=0;
	cin>>n;

	string s;
	cin>>s;

	for(int mask=0;mask<(1<<n);mask++)
    {
        string z="" , e="";

        for(int i=0;i<n;i++)
        {
            if (BIT(mask , i))
            {
                z+=s[i];
            }
            else
            {
                e+=s[i];
            }
        }

        w[mp(z , e)]++;;
    }

    for(int mask=0;mask<(1<<n);mask++)
    {
        string z="" , e="";

        for(int i=0;i<n;i++)
        {
            if (BIT(mask , i))
            {
                z=s[n+i]+z;
            }
            else
            {
                e=s[n+i]+e;
            }
        }

        res+=w[mp(z , e)];
    }

    cout<<res;
}


Measured memory_bytes: 88832
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1LL << 60;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


// 入力
int N, K;
ll h[100010];

// DP テーブル
ll dp[101000];

int main() {
    cin >> N >> K;
    rep1(i, N) cin >> h[i];

    // 初期化 (最小化問題なので INF に初期化)
    rep1(i, 100010) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (ll i=0; i<N; i++) {
        for (ll j=1; j<=K; j++)
            chmin(dp[i+j], dp[i] + abs(h[i+j] - h[i]));
    }

    // 答え
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1792
import collections as coll

def test():
    n = int(input())
    a = list(map(int,input().split()))
    b = coll.Counter(a)
    ans = 0
    for i,j in b.items():
        if i < j:
            ans += j - i
        elif i > j:
            ans += j
    print(ans)


if __name__ == "__main__":
    test()


Measured memory_bytes: 18676
#include <iostream>

using namespace std;

int main()
{
	int R, G, B, N;

	cin >> R >> G >> B >> N;

	int ret = 0;

	for (int r = 0; r * R <= N; r++)
	{
		for (int g = 0; r * R + g * G <= N; g++)
		{
			if ((N - r * R - g * G) % B == 0)
			{
				ret++;
			}
		}
	}

	cout << ret;

	return 0;
}


Measured memory_bytes: 256
//### In The Name Of GOD ###

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;

const int MOD = 1000000007;
const int INF = 30 * 1000 + 20;
const int MAXN = 2600;
const int MLOG = 18;
const int NMAX = 60;

#define int ll
#define pb push_back
#define pp pop_back
#define X first
#define Y second
#define IO ios_base::sync_with_stdio(false);
#define sz(a) (int)(a.size())
#define ct(x) const_cast<const int&>(x)

int what[MAXN][NMAX][NMAX];

int32_t main(){
	int n,A;
	cin >> n >> A;
	int x[ct(n)];
	for(int i=0;i<=n;i++)
	what[0][i][0] = 1;
	for(int i = 0 ; i < n; i++){
		cin >> x[i];
		for(int j=0;j<x[i];j++){
			for(int k = 1; k < NMAX; k++){
				what[j][i+1][k] = what[j][i][k];
			}
		}
		for(int j=x[i];j<2550;j++){
			for(int k = 1; k < NMAX; k++){
				what[j][i+1][k] = what[j-x[i]][i][k-1] + what[j][i][k];
//				if(what[j][i+1][k] > 0)
//				cerr << j << ' ' << i+1 << ' ' << k << ' '<< what[j][i+1][k] << endl;
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		ans += what[A*i][n][i];
	}
	cout << ans;
}

Measured memory_bytes: 71936
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)
	answer := is7contains(n)
	fmt.Println(answer)
}

func is7contains(n int) string {
	nStr := strconv.Itoa(n)
	for i := 0; i < len(nStr); i++ {
		if d, _ := strconv.Atoi(string(nStr[i])); d == 7 {
			return "Yes"
		}
	}
	return "No"
}


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

int main(void){
  int n,i;
  double moe,ans;
  char han[4];
  while(scanf("%d",&n)!=1);
  for(i=0;i<n;i++){
    while(scanf("%lf%s",&moe,han)!=2);
    if(strcmp(han,"JPY")==0){
      ans+=moe;
    }else if(strcmp(han,"BTC")==0){
      ans+=moe*380000;
    }
  }
  printf("%f\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
typedef long long ll;

int main() {
  int r, D, x;
  cin >> r >> D >> x;
  for (int i = 0; i < 10; i++) {
    x = r * x - D;
    cout << x << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    
    int a,b,c,x,y,z;
    
    scanf("%d %d %d",&a,&b,&c);
    
    if(a < b){
        x = a;
        z = b;
    }else{
        x = b;
        z = a;
    }
    if(c < x){
        y = x;
        x = c;
    }else if(c > z){
        y = z;
        z = c;
    }else{
        y = c;
    }
    
    printf("%d %d %d\n",x,y,z);
    
    return 0;
}

Measured memory_bytes: 2668
N, A ,B = list(map(int,input().split()))
def problem2(N, A, B):
  if A <= N % (A+B):
    answer = (N // (A+B)) * A + A
  else:
    answer = (N // (A+B)) * A + N % (A+B)
  return answer
print(problem2(N, A, B))

Measured memory_bytes: 3060
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer inte[] = new Integer[n];
    
    for(int i=0; i<n; i++){
      inte[i] = sc.nextInt();
    }
    
    Arrays.sort(inte, Comparator.reverseOrder());
    int Alice = 0;
    int Bob   = 0;
    
    for (int i=0; i<n; i+=2) {
      Alice += inte[i];
    }
    for (int i=1; i<n; i+=2) {
      Bob += inte[i];
    }
    
  	System.out.println(Alice - Bob);
  }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Khela ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define llu long long unsigned int
#define pf printf
#define sf scanf
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define pii pair<int ,int>
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
 
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
const int Max=1e9+100;
const ll Maxx=1e18+500;
const int sz=1e3+100;
vector<pii> test;
int main()
{
    Khela
    int  a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,n,mx;
    char ch;
    double d;
    string str1,str2,str;
    bool bl,bl1;
    int t,cs=1;
    while(cin>>n>>k)
    {
         test.clear();
         test.pb({0,0});
         int id,last=0;
         cin>>str;
         for(i=0;i<n;i++){
             if(str[i]=='0') {
                 if(last==0) id=i+1;
                 ++last;
             }
             else{
                 if(last>0){
                     test.pb({id,i});
                 }
                 last=0;
             }
         }
         if(last>0) test.pb({id,n});

         test.pb({n+1,n+1});
         
         int siz=test.size();
         int mx=0;
         for(i=0;i<siz;i++)
         {
             if(i+k<siz){
                 p=test[i+k].f-test[i-1].s-1;
                 mx=max(p,mx);
             }
             else {
                 p=test[siz-1].first-test[i-1].s-1;
                 mx=max(mx,p);
             }
         }

         if(siz==2) mx=n;

         cout<<mx<<endl;
    }





}

Measured memory_bytes: 1020
N=int(input())
r=[]
for i in range(N):
    r.append(tuple(map(int,input().split())))
r.sort(key=lambda x:x[1]) # y座標で昇順ソート
b=[]
for i in range(N):
    b.append(tuple(map(int,input().split())))
b.sort() # x座標で昇順ソート

# print(r)
# print(b)

ans=0
for bi in b:
    # print(bi)
    rs=[ri for ri in r if ri[0]<bi[0] and ri[1]<bi[1]]
    # print(rs)
    if rs:
        ans+=1
        r.remove(rs[-1])
    # print(r)

print(ans)

Measured memory_bytes: 39024
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    char s[10];
    cin >> s;
    int ans = 0;
    imfor(i, 6) {
        if (s[i] == '1') {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 2e5+100;
ll f[N], r[N];
ll comb(ll a, ll b){
  return f[a]*r[b]%MOD*r[a-b]%MOD;
}
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  f[0] = 1;
  FOR(i, 1, N) f[i]=f[i-1]*i%MOD;
  r[N-1] = modInv(f[N-1], MOD);
  FORR(i, N-1, 1) r[i-1]=r[i]*i%MOD;
  ll n, a, b, c, _ab;
  cin >> n >> a >> b >> c;
  ll ans = 0;
  _ab = modInv(a+b, MOD);
  if(a && b){
    FOR(i, 0, n) ans += (modPow(a, n, MOD)*modPow(b, i, MOD)%MOD + modPow(b, n, MOD)*modPow(a, i, MOD)%MOD) % MOD * comb(i+n-1, i) % MOD * modPow(_ab, n+i, MOD) % MOD * (n+i) % MOD;
  }else{
    ans = n;
  }
  cout << ans%MOD*_ab%MOD*100%MOD << endl;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x,y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x,y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define d4(x,y,z,w)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z << " | "<< #w << "--> " << w <<endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;
ll mode=1e9+7;
const long long maxn=2*1e5+10;
const long long inf=99999999999;
ll __lcm(ll a, ll b){ return (a*b)/__gcd(a,b); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRand(ll l, ll r){ uniform_int_distribution<ll> uid(l, r); return uid(rng); }
 
ll power(ll x, ll y){  
	ll p=mode, res=1;
    x = x % p;
    while (y > 0) {  
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
    }  
    return res;  
}  

vector<ll> adj[maxn];

void solve(){
	
	ll n,k;
	cin>>n>>k;
	for (int i=1;i<=k;i++){
		ll x;
		cin>>x;
		for (int j=1;j<=x;j++){
			ll y;
			cin>>y;
			adj[y].pb(i);
		}
	}
	
	ll ans=0;
	for (int i=1;i<=n;i++){
		ans+=(adj[i].size()==0);
	}
	cout<<ans<<endl;
	
	return;
}
 
int main(){ 
    
    #ifndef ONLINE_JUDGE
		//freopen("input.txt", "r", stdin);
    #endif
    srand(time(0)); 
    
    ios::sync_with_stdio(0);
    cin.tie(0);
 	
	//T{ solve(); }
	solve();
	
	return 0;
}

Measured memory_bytes: 8480
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
bool comp(pair<ll, ll> a, pair<ll , ll> b) {
    // 基本はfirstで比較
    if(a.first != b.first){
         return a.first < b.first; // 昇順
        //return a.first > b.first; // 降順
    }

    // それ以外はsecondで比較
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        // どちらも同じ
        return true;
    }
}

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

    ll  a,b,c,d,e,n,k,maxi=0,f=0,mini=INF,sum=0,q;
	string str,stra,straa;
    ll x,y,z;
    char ca,cb,cc;
    cin>>n>>e;
    vector<pair<ll,ll>> p(n);
    rep(i,n){
        cin>>a>>b;
        p[i]=make_pair(a,b);
    }
    sort(all(p),comp);
    rep(i,n){
        if(p[i].second<=e){
            cout<<p[i].first<<endl;
            return 0;
        }
    }
    cout<<"TLE"<<endl;

    

    return 0;
}


Measured memory_bytes: 3628
from collections import *

N = int(input())
c = Counter()
for i, _ in enumerate(range(N)):
    s = input()
    c2 = Counter()
    for ch in s:
        c2[ch] += 1

    if i == 0:
        c = c2
    else:
        c_new = Counter()
        for k, v in c.items():
            c_new[k] = min(v, c2[k])
        c = c_new

ans = ''
for k in sorted(c.keys()):
    ans += k * c[k]
print(ans)


Measured memory_bytes: 3828
//
// Created by yamunaku on 2020/06/20.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

ll modpow(ll x, ll a){
    ll ans = 1;
    while(a){
        if(a & 1) ans = ans * x % MOD;
        a >>= 1;
        x = x * x % MOD;
    }
    return ans;
}

ll inv(ll x){
    return modpow(x, MOD - 2);
}

int main(){
    //CFS;
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll h = c - a + 1, w = d - b + 1;
    mtl dp(h, vl(w, 0));
    dp[0][0] = 1;
    repl(i, 1, w) dp[0][i] = a * dp[0][i - 1] % MOD;
    repl(i, 1, h){
        ll sum = 0;
        ll v = inv(a + i);
        rep(j, w){
            sum = sum * (a + i) % MOD;
            ll tmp = dp[i - 1][j] * (b + j) % MOD;
            dp[i][j] = (tmp + sum) % MOD;
            sum = (sum + tmp * v) % MOD;
        }
    }
    cout << dp[h - 1][w - 1] << endl;
    return 0;
}

Measured memory_bytes: 73592
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int w,a,b;
  cin >> w >> a>> b;
  int output = 0;
  if(a+w<b){
    output = b-a-w;
  }else if(a>b+w){
    output = a-b-w;
  }
  cout << output << endl;
}

Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}

#define int ll
int grid[31][31] = {};
int h, w, n;

int calc() {
	int gogo[31][31] = {};
	REP(i, 31) {
		REP(q, 31) {
			gogo[i][q] = grid[i][q];
		}
	}
	while (true) {
		int cnt[31] = {};
		REP(i, h) {
			REP(q, w) {
				if (gogo[i][q] == 0) continue;
				swap(gogo[i][q], gogo[cnt[q]][q]);
				cnt[q]++;
			}
		}
		int D[31][31] = {};
		REP(i, h) {
			int te = 1;
			for (int q = 1; q < w+1; ++q) {
				if (gogo[i][q - 1] != gogo[i][q]) {
					if (te >= n) {
						for (int j = q - 2; j >= -1; --j) {
							D[i][j + 1] = 1;
							if (j==-1||gogo[i][j] != gogo[i][j + 1]) {
								break;
							}
						}
					}
					te = 0;
				}
				te++;
			}
		}
		REP(q, w) {
			int te = 1;
			for (int i = 1; i < h + 1; ++i) {
				if (gogo[i][q] != gogo[i - 1][q]) {
					if (te >= n) {
						for (int j = i - 2; j >= -1; --j) {
							D[j + 1][q] = 1;
							if (j == -1||gogo[j][q] != gogo[j + 1][q]) {
								break;
							}
						}
					}
					te = 0;
				}
				te++;
			}
		}
		int erased = 0;
		REP(i, h) {
			REP(q, w) {
				if (D[i][q] == 1) {
					if (gogo[i][q] != 0) erased = 1;
					gogo[i][q] = 0;
				}
			}
		}
		if (erased == 0) break;
	}

	REP(i, 30) {
		REP(q, 30) {
			if (gogo[i][q]) return false;
		}
	}
	return true;
}

void solve() {
	cin >> h >> w >> n;
	REP(i, h) {
		string s;
		cin >> s;
		REP(q, w) {
			if (s[q] != '.') {
				grid[h - i - 1][q] = s[q] - 'A' + 1;
			}
		}
	}

	REP(i, h) {
		REP(q, w-1) {
			swap(grid[i][q], grid[i][q + 1]);
			if (calc() == true) {
				cout << "YES" << endl;
				return;
			}
			swap(grid[i][q], grid[i][q + 1]);
		}
	}
	cout << "NO" << endl;
}

#undef int
int main() {
	init();
	solve();
}


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

using namespace std;

#define int				long long
#define pb 				push_back
#define endl 			'\n'
#define F				first
#define S				second
#define mod				(ll)998244353
#define mp              make_pair
#define lb				lower_bound
#define ub				upper_bound
#define ios 			ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inf				1e18
#define mem(a,x)		for(int i=0;i<(int)(sizeof(a)/sizeof(a[0]));i++) a[i] = x;
#define trace(a)		cout<<(#a)<<" --> "<<a<<endl
#define trace2(a,b)		{trace(a);trace(b);}
#define trace3(a,b,c)	{trace(a);trace(b);trace(c);}
#define trace4(a,b,c,d) {trace(a);trace(b);trace(c);trace(d);}
#define M_PI           	3.14159265358979323846

signed main(){
	ios;
	int n;
	cin>>n;
	int h[n];
	for(int i=0;i<n;i++)
		cin>>h[i];
	bool ans = true;
	for(int i=1;i<n;i++){
		if(h[i]>h[i-1])
			h[i]--;
		else if(h[i]<h[i-1]){
			ans = false;
			break;
		}
	}
	if(ans)
		cout<<"Yes";
	else
		cout<<"No";

	return 0;
}






Measured memory_bytes: 1024
n, x = map(int, input().split())
while n != 0:
    count = 0
    for i in range(1, n-1):
        for j in range(i+1, n):
            for k in range(j+1, n+1):
                if i+j+k == x:
                    count+=1
    print(count)
    n,x = map(int, input().split())


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

int N;
int R;
int x[200010], y[200010];

unordered_map<int, unordered_set<int>> g;
set<pair<int,int>> vis;

void dfs(int y, int x){
    vis.insert(make_pair(y,x));
    // cout << x*R << " " << y*R << endl;
    rep(i,3)rep(j,3){
        int dx = i-1;
        int dy = j-1;
        if(dx == 0 && dy == 0) continue;
        if(g.count(y+dy) == 0) continue;
        if(g[y+dy].count(x+dx) == 0) continue;
        if(vis.count(make_pair(y+dy, x+dx))) continue;
        dfs(y+dy, x+dx);
    }
}

int solve(){
    vis.clear();
    g.clear();
    rep(i,N){
        g[y[i]/R].insert(x[i]/R);
    }
    int ans = 0;
    for(const auto &row : g){
        for(const auto &x : row.second){
            int y = row.first;
            if(vis.count(make_pair(y,x))) continue;
            ans++;
            // cout << "b" << endl;
            dfs(y,x);
        }
    }
    return ans;
}

int conv(string s){
    s.erase(s.find('.'),1);
    stringstream ss(s);
    int x;
    ss >> x;
    return x;
};


int main(){
    string RR;
    while(cin >> N >> RR){
        R = conv(RR);
        rep(i,N){
            string xx, yy;
            cin >> xx >> yy;
            x[i] = conv(xx), y[i] = conv(yy);
        }
        cout << solve() << endl;
    }
}

Measured memory_bytes: 45968
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P;
typedef priority_queue<int> Pr;
int const MOD = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
vector< long long > divisor(long long n) {
  vector< long long > ret;
  for(long long i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

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

    Int n,m,ans=1; cin>>n>>m; vector<Int> div=divisor(m);
    for (int i = 0; i < div.size(); i++){
        if(div[i]>=n)chmax(ans,m/div[i]);
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public double calcAverage(int[] buf, int num) {
        double sum = 0;
        for (int i = 0; i < num; i++) {
            sum += (double)buf[i];
        }

        return sum/(double)num;
    }
    public double calcSD(int[] buf, int num) {
        double average = calcAverage(buf, num);
        double bunsan;
        double sum = 0.0;

        for (int i = 0; i < num; i++) {
            sum += Math.pow((double)buf[i] - average, 2.0);
        }
        bunsan = sum / (double)num;
        return Math.sqrt(bunsan);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Main app = new Main();

        while (true) {
            int num = Integer.parseInt(scan.next());
            if (num == 0) {
                break;
            }
            int[] score = new int[num];
            double sd;
            for (int i = 0; i < num; i++) {
                score[i] = Integer.parseInt(scan.next());
            }

            sd = app.calcSD(score, num);
            System.out.println(sd);
        }
    }
}



Measured memory_bytes: 30876
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <random>
#include <time.h>
#include <chrono>
#include <sstream>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define sort(s) sort(s.begin(), s.end());
#define reverse(s) reverse(s.begin(), s.end());
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }

unsigned int randxor()
{
	static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned int t;
	t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

//10進数を2進数に変換_63個の要素を持つ配列
vector<int> Convert10to2(ll n) {
	vector<int> ans(63);
	rep(i, 63) {
		ans[i] = n % 2;
		n -= n % 2;
		n /= 2;
	}
	return ans;
}
//2進数を10進数に変換_63個の要素を持つ配列
ll Convert2to10(vector<int> a) {
	ll ans = 0;
	ll j = 1;
	rep(i, a.size()) {
		ans += a[i] * j;
		if (i != a.size() - 1) {
			j *= 2;
		}
	}
	return ans;
}
//XORを計算
vector<int> CalcXOR2to2(vector<int> a, vector<int> b) {
	rep(i, 63) {
		if (a[i] != b[i]) {
			a[i] = 1;
		}
		else {
			a[i] = 0;
		}
	}
	return a;
}

//最大公約数
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a%b);
}

int VectorSum(vector<int> x) {
	int ans = 0;
	rep(i, x.size()) {
		ans += x[i];
	}
	return ans;
}

class UnionFind {
public:
	vector<int> Parent;

	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	int root(int A) {
		if (Parent[A] < 0) {
			return A;
		}
		return Parent[A] = root(Parent[A]);
	}

	int size(int A) {
		return -Parent[root(A)];
	}

	bool connect(int A, int B) {
		A = root(A);
		B = root(B);
		if (A == B) {
			return false;
		}
		if (size(A) < size(B)) {
			swap(A, B);
		}
		Parent[A] += Parent[B];
		Parent[B] = A;
	}
};





int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(m), b(m);
	rep(i, m) {
		cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
	}
	reverse(a);
	reverse(b);
	UnionFind UF(n);
	
	//vector<ll> ans(m);
	//ans[0] = (ll)n*(n - 1) / 2;
	//for (int i = 1; i < m; i++) {
	//	if (UF.root(a[i-1]) != UF.root(b[i-1])) {
	//		ans[i] = ans[i - 1] - (ll)UF.size(a[i-1])*UF.size(b[i-1]);
	//		UF.connect(a[i-1], b[i-1]);
	//	}
	//	else {
	//		ans[i] = ans[i - 1];
	//	}
	//}

	vector<ll> ans;
	ans.push_back((ll)n*(n - 1) / 2);
	int i = 0;
	while (ans.size() < m) {
		if (UF.root(a[i]) != UF.root(b[i])) {
			ans.push_back(*(--ans.end()) - (ll)UF.size(a[i])*UF.size(b[i]));
			UF.connect(a[i], b[i]);
		}
		else {
			ans.push_back(*(--ans.end()));
		}
		i++;
	}

	reverse(ans);
	rep(i, m) {
		cout << ans[i] << endl;
	}

	return 0;



}



Measured memory_bytes: 3444
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;

int n,m,block;
vector<int> vec[100005];
bool vis[100005];
int part[100005],p[100005];

void dfs(int u, int fa)
{
    vis[u]=true;
    part[u]=block;
    for (int i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if (vis[v]) continue;
        if (v==fa) continue;
        dfs(v,u);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&p[i]);
    }
    for (int i=1; i<=m; i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    memset(vis,false,sizeof(vis));
    block=1;
    for (int i=1; i<=n; i++)
    {
        if (vis[i]) continue;
        dfs(i,-1);
        block++;
    }
    int ans=0;
    for (int i=1; i<=n; i++)
    {
        if (part[i]==part[p[i]] || i==p[i])
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 9600
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	max := (n - 2) * (n - 1) / 2
	if max < k {
		fmt.Println(-1)
		return
	}

	m := (n - 1) + (max - k)
	fmt.Println(m)
	for i := 2; i <= n; i++ {
		fmt.Println(1, i)
		m--
	}
	for i := 2; i <= n-1; i++ {
		for j := i + 1; j <= n; j++ {
			if m <= 0 {
				return
			}
			fmt.Println(i, j)
			m--
		}
	}
}


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

using namespace std;

const int SIZE = 50;

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



char str[SIZE];
map <P, int> mp;

int main() {
	int n;
	scanf("%d", &n);
	scanf("%s", str);
	for (int msk = 0; msk < (1<<n); ++msk) {
		string A = "", B = "";
		for (int i = 0; i < n; ++i) {
			if (msk & (1<<i)) {
				A += str[i];
			}
		} 
		for (int i = n-1; i >= 0; --i) {
			if (!(msk & (1<<i))) {
				B += str[i];
			}
		} 
		mp[P(A, B)]++;
	}

	ll ans = 0;
	for (int msk = 0; msk < (1<<n); ++msk) {
		string A = "", B = "";
		for (int i = 0; i < n; ++i) {
			if (msk & (1<<i)) {
				A += str[n+i];
			}
		} 
		for (int i = n-1; i >= 0; --i) {
			if (!(msk & (1<<i))) {
				B += str[n+i];
			}
		} 
		ans += mp[P(B, A)];
	}


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



}

Measured memory_bytes: 91904
//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b-1,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int long long
#define zero 0LL
#define pb PB
using namespace std;
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr, Vpr ,greater<pr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
int dx[] = { 0,1,0,-1,0 }, dy[] = { 1,0,-1,0,0 };
const int SIZE1 =3e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 22;
const int SIZE = SIZE1;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
ut N, M, K, X, L, Y,H,W,Q;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE], nums[SIZE], maps[SIZE3][SIZE3], answer = zero;
LL A[SIZE], B[SIZE];
LL solve() {
	cin >> N;
	LL now = 1;
	char c;
	REP(i, N) {
		cin >> c;
		if (c == 'F' and now) now = 0;
		else now = 1;
	}
	cout << (now ? "T" : "F") << endl;
	return 0;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	solve();
	cin >> N;
	return 0;
}


Measured memory_bytes: 10196
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define INF 1<<31-1
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
#define NUM 100001
int main()
{
    int N,M,i,k=0;
    scanf("%d%d",&N,&M);
    int a[M],ans[N+2];
    FOR(i,0,M)scanf("%d",&a[i]);
    ans[0]=0;ans[1]=1;
    
    for(i = 2; i < N+2; i++){
        ans[i] = ans[i-1] + ans[i-2];
        if(a[k] == i-1 ){
            ans[i] = 0;
            k++;
        }
        if(ans[i] > MOD)ans[i] %= MOD;
    }
    
    printf("%d\n", ans[N+1]);
    
    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <functional>
#include <list>
#include <utility>
#include <map>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll, ll> Pll;
typedef pair<int, Pii > P1;

#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define mp1(a,b,c) P1(a,P(b,c))
#define get_arsize(a) (sizeof(a)/sizeof(a[0]))
const ll mod = 1000000007;
const double eps = 1e-10;
const int MAX = 200000;

int main() {
	int k, t, tmp;
	vector<int> a;
	cin >> k >> t;
	rep(i,t){
		cin >> tmp;
		a.push_back(tmp);
	}
	sor(a); rev(a);
	int ma = (k+1)/2;
	rep(i,t) {
		ma -= a.at(i);
		if (ma <= 0) {
			if(i==0){
				if(k % 2) {
					cout << -ma * 2  << endl;
				} else {
					cout << -ma * 2 - 1<< endl;
				}
			return 0;
			} else {
				cout << 0 << endl;
				return 0;
			}
		}
	}

  return 0;
}

Measured memory_bytes: 256