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

int cmp(const void *a, const void *b){
    int p = *(int*)a, q = *(int*)b;
    if( p > q) { return 1; }
    else if( p == q) { return 0; }
    else { return -1; }
}

int cmp1(const void *a, const void *b){
    int p = *(int*)a, q = *(int*)b;
    if( p > q) { return -1; }
    else if( p == q) { return 0; }
    else { return 1; }
}

void solve(int *a, int n, int m) {
    if(n > m) { printf("0\n"); return ;}
    qsort(a, m, sizeof(int), cmp);
    int i, ans;
    int *b = (int*)malloc(m*sizeof(int));
    for(i = 1; i < m; ++i) {
        b[i-1] = a[i] - a[i-1]; 
    }
    qsort(b, m-1, sizeof(int), cmp1);
    ans = a[m-1] - a[0];
    for(i = 0; i < n-1; ++i) {
        ans -= b[i];
    }
    printf("%d\n", ans);
    free(b); free(a);
}

int main(void)
{
    int n, m, i;
    scanf("%d %d", &n, &m);
    int *a = (int*)malloc((m+1)*sizeof(int));
    for(i = 0; i < m; ++i) { scanf("%d", &a[i]); }
    solve(a, n, m);
    return 0;
}

Measured memory_bytes: 1268
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <utility>
#include <vector>
#include <map>
#include <cstdlib>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    long long N, max=1, i=2, del, sum=0, j;

    cin >> N;

    while(N > max){
        max += i;

        i++;
    }
    
    i--;

    for(j=1; j<=i; j++){
        sum += j;
    }

    del = sum - N;

    for(j=1; j<=i; j++){
        if(j != del){
            cout << j << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
ll n;
const int N=60;
ll a[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rep(i,0,n) cin>>a[i];
	ll mx=LLONG_MAX;
	ll ans=0;
	while(mx>(n-1)) {
		ll act=0;
		rep(i,0,n) {
			act+=(a[i]-(n-1)+(n-1))/n;
		}
		ans+=act;
		rep(i,0,n) {
			ll cur=(a[i]-(n-1)+(n-1))/n;
			a[i]-=cur*n;
			a[i]+=(act-cur);
		}
		mx=0;
		rep(i,0,n) mx=max(mx,a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3528
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int  N = 2e5;
int n;
vector<int> h(N,0);
vector<int> val(N,0);
vector<ll>tree(4*N,0);

ll query(int tree_l,int tree_r,int treeix,int q_l,int q_r)
{
  //cout<<"tree_range : "<<tree_l<<":"<<tree_r<<endl;
  if(q_l<=tree_l && q_r>=tree_r)
  {
    return tree[treeix];
  }
  else if(q_l>tree_r || q_r<tree_l)
  {
    return 0;
  }
  int m = (tree_l + tree_r)/2;
  ll left = query(tree_l,m,2*treeix,q_l,q_r);
  ll right = query(m+1,tree_r,2*treeix+1,q_l,q_r);
  return max(left,right);
  //cout<<"timestamp : "<<left.timestamp<<" "<<right.timestamp<<endl;
  //cout<<"for range "<<tree_l<<" "<<tree_r<<" : "<<ans.data<<endl;
  //ans.timestamp = max(left.timestamp,right.timestamp);
}

void update(int tree_l,int tree_r,int treeix,int valix,ll value)
{
  //cout<<"tree_range : "<<tree_l<<":"<<tree_r<<endl;
  if(tree_l == tree_r)
  {
    tree[treeix] = max(tree[treeix],value);
    return;
  }
  int m = (tree_l + tree_r)/2;
  if(m<valix)
  {
    update(m+1,tree_r,2*treeix+1,valix,value);
  }
  else
  {
    update(tree_l,m,2*treeix,valix,value);
  }
  ll l = tree[2*treeix];
  ll r = tree[2*treeix+1];
  tree[treeix] = max(l,r);
}


int main()
{
  cin>>n;
  for(int i=1;i<=n;i++) cin>>h[i];
  for(int i=1;i<=n;i++) cin>>val[i];
  vector<ll> sol(n+1);
  ll ans = 0;
  for(int i=1;i<=n;i++)
  {
    sol[i] = val[i] + query(1,N,1,0,h[i]-1);
    ans = max(ans,sol[i]);
    update(1,N,1,h[i],sol[i]);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 12776
#include <stdio.h>
int main() {
	double  a, b, c, k, sum = 0;
	scanf("%lf%lf%lf%lf", &a, &b, &c, &k);
	if ((k - a - b) >= 1) { //cまで到達する
		sum += -1 * (k - a - b);
		sum += a;
	}
	else if ((k - a) >= 1) sum += a;
	else sum += k;
	printf("%0.0f\n", sum);
	return 0;
}

Measured memory_bytes: 1752
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] data = Console.ReadLine().Split(' ');
        int a = int.Parse(data[0]);
        int b = int.Parse(data[1]);
        int d = a / b;
        int r = a % b;
        double f = Math.Round(double.Parse(data[0])/double.Parse(data[1]), 7);
        Console.WriteLine("{0} {1} {2:f5}", d, r, f);
    }
}

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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int n;
ll k;
vector<ll> a;
vector<ll> f;

bool check(ll x) {
  ll sum = 0;
  REP(i, n) sum += max(0ll, a[i] - (x / f[i]));
  return sum <= k;
}

int main() {
  cin >> n >> k;
  a.resize(n), f.resize(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> f[i];
  sort(ALL(a));
  sort(ALL(f));
  reverse(ALL(f));
  ll ok = 1e12 + 1, ng = -1;
  while (1 < abs(ok - ng)) {
    ll mid = (ok + ng) / 2;
    if (check(mid)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  cout << ok << endl;
  return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>
char cha(char);

int main(){
  char a;
  while(1){
    scanf("%c",&a);    
    if(a=='\n')break;
    printf("%c",cha(a));
}
  printf("\n");

return 0;
}


char cha(char w){
  if(w>='a'&&w<='z') return 'A'-'a'+w;
  return w;
}

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

using namespace std;

int main() {
  int64_t N, K;
  cin >> N >> K;
  int64_t L = N / K;
  int64_t R = L + 1;
  cout << min(abs(N - L * K), abs(N - R * K)) << endl;

  return 0;
}


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

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

    while(t-- > 0){
        int n, k, x, y;
        cin >> n >> k >> x;
        vector<int> v(n-1);
        for(int i = 0; i < n-1; i++){
            cin >> y;
            v[i] = y-x;
            x = y;
        }
        sort(v.rbegin(), v.rend());
        int ans = 0;
        for(int i = k-1; i < n-1; i++)  ans += v[i];
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3488
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE BangPatterns #-}

module Main where

import Debug.Trace
import Data.List
--import qualified Data.Set.Strict as Set
--import qualified Data.Map.Strict as Map

main :: IO ()
main = do
  [n, k] <- map read . words <$> getLine
  ps <- map read . words <$> getLine
  --a `traceShow`
  print $ solve k ps

solve :: Int -> [Int] -> Int
solve p ps = sum . take p . sort $ ps


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


int main(){
  int s[6][2];
  s[0][0]=2;
  s[0][1]=5;
  s[1][0]=5;
  s[1][1]=2;
  s[2][0]=10;
  s[2][1]=3;
  s[3][0]=4;
  s[3][1]=1;
  s[4][0]=1;
  s[4][1]=5;
  s[5][0]=2;
  s[5][1]=10;
  
  string str;
  while(1){
    cin>>str;
    if(str[0]=='#') break;
    
  int  now=0;
  for(int i=0;i<str.size();i++){
    now=s[now][str[i]-'0'];
    if(now==10) break;
  }
  if(now==1) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1176
A, B = map(int, input().split())
ans = [['#'] * 100 for _ in range(50)] + [['.'] * 100 for _ in range(50)]
for i in range(0, 50, 2):
    for j in range(0, 100, 2):
        if A > 1:
            ans[i][j] = '.'
            A -= 1

for i in range(51, 100, 2):
    for j in range(0, 100, 2):
        if B > 1:
            ans[i][j] = '#'
            B -= 1
print(100, 100)
for row in ans:
    print(*row, sep='')

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

int main() {
	int N;
	long A;
	cin >> N;
	int s = 100;
	for (int i = 0; i <N; i++) {
		cin >> A;
		int x = 0;
		while (A % 2 == 0) {
			x++;
			A = A / 2;
		}
		if (x < s) {
			s = x;
		}
	}
	cout << s << endl;

	return 0;
}




Measured memory_bytes: 256
/**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define set_vect(a,n); vector<int>a(n); for(int i=0;i<n;i++)cin>>a[i];
#define db(x) cerr << #x << " = "  << (x) << ' ';
const int N = 200005;

string s;
void solve(){
    cin >> s;
    int sum = 0;
    for (auto x : s) sum += x -'0';
    cout << (sum % 9 == 0 ? "Yes" : "No");
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int t = 1; //cin >> t;
    while(t--){solve();}
    return 0;
}

// Code By Pain (Bao Trung)

Measured memory_bytes: 3780
#include<iostream>
#include<math.h>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<stdlib.h>
using namespace std;
#define PI 3.14159265358979
typedef  long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#include<set>


//---------------------------------------------
 


int main (void)
{
    ll n,c,k;
    cin>>n>>c>>k;

    vector<ll> t(n);
    rep(i,n) cin>>t[i];


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

    ll bus =0;
    ll firsttime =-1;
    ll pop = 0;
    for(int i=0;i<n;i++)
    {
        if(pop==0)
        {
            firsttime = t[i];
            pop =1;
        }
        else
        {
            if(t[i]-firsttime<=k&&pop+1<=c)
            {
                pop++;
            }

            else
            {
                bus ++;
                pop=1;
                firsttime = t[i];
            }
        }

    }

    if(pop>0) bus ++;
    cout<<bus<<endl;
}

Measured memory_bytes: 1024
module AOJ_Volume0100;

import std.stdio,std.string,std.conv,std.array;

int main()
{
	while(true)
	{
		int n = readln.chomp.to!int;
		if(n == 0) break;

		ulong v[4001];
		foreach(i;0..4001) v[i] = 0;
		int ans[];
		int num;
		ulong k,m;
		foreach(i;0..n)
		{
			string[] s = readln.chomp.split(" ");
			num = s[0].to!int;
			k = s[1].to!int;
			m = s[2].to!int;

			bool flag = true;

			foreach(j;0..ans.length)
			{
				if(ans[j] == num) flag = false;
			}

			if(flag)
			{
				v[num] += k*m;
				if(v[num] >= 1000000)
				{
					ans ~= num;
				}
			}
		}

		if(ans.length == 0)
		{
			writeln("NA");
		}
		else
		{
			foreach(i;0..ans.length)
			{
				ans[i].writeln;
			}
		}
	}
	return 0;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    Scd(N);

    printf ("%d\n", (N+1)/2 );

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
typedef map<int,int> ma;
typedef set<int> se;
typedef vector<int> ve;
const int maxn=1e5+7;
const int mod=1e9+7;
const int N=1e5+7;
const int inf=1e9+7;
//int a[maxn];
int main() {
    string a,b;
    cin>>a;
    int s=a.length();
    while(s--){
        cout<<'x';
    }
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

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

    int a[n],b[n];
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    int d=0,c=a[0];

    for(int i=0;i<n;i++){
        if(b[i]>t){
            d++;
        }
        else{
            if(c>a[i]){
                c=a[i];
            }

        }

       }
        
        
    
    


    
    if(d==n){
        printf("TLE");
    }
    else{
        printf("%d\n",c);
    }

}

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

typedef pair<int, int> P;

int main() {

    int t[3];
    vector<int> d(3);
    rep(i,3){
        cin >> t[i];
        d[i] = i;
    }

    int ans = 1e9;
    int tmp;
    do{
        tmp = 0;
        rep(i,2){
            tmp+=abs(t[d[i+1]]-t[d[i]]);
        }
        ans = min(ans,tmp);
    }while(next_permutation(d.begin(),d.end()));

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

Measured memory_bytes: 256
function Main(input) {
  var inputs = input.split(" ").map(n => parseInt(n, 10));
  var a = inputs[0];
  var b = inputs[1];

  if ((a + b) % 2 === 0) {
    console.log((a + b) / 2);
  } else {
    console.log(Math.ceil((a + b) / 2));
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
import math
N,D = map(int,input().split())
X=[[Xi for Xi in map(int,input().split())] for j in range(N)]

count=0
for i in range(N):
    for j in range(i+1,N):
        dist=0
        for k in range(D):
            dist+=(X[i][k] - X[j][k])**2
        if math.floor(math.sqrt(dist))**2 == dist:
            count+=1
print(count)


Measured memory_bytes: 3060
#include<stdio.h>
#include<string.h>
int MAX(int a,int b){return a<b?b:a;}
//int P[1010],L[1010],R[1010],H[1010],C=1;
int P[4][1010],C=1,H[1010];
//int hyouka(int i,int x){return N[i]<=x?N[i]<x?-1:0:1;}
char N[1010][110];
int hyouka(int i,char *s){return strcmp(N[i],s);}
int h(int a){return H[P[2][a]]-H[P[1][a]];}
void rot(int a,int t){
  int b=P[t][a],r=P[0][a];
  P[t][r]==a?(P[1][r]=b):(P[2][r]=b);
  if(P[3-t][b])P[0][P[3-t][b]]=a;
  P[t][a]=P[3-t][b];
  P[3-t][b]=P[0][b];
  P[0][b]=P[0][a];
  P[0][a]=b;
  H[a]=MAX(H[P[1][a]],H[P[2][a]])+1;
  H[b]=MAX(H[P[1][b]],H[P[2][b]])+1;
}
int mfind(char *x){
  int i,j,r,n,t;
  if(C==1){
    P[1][0]=C;
    //N[C]=x;
    strcpy(N[C],x);
    P[0][C++]=0;
    return 1;
  }
  for(i=1;r=hyouka(i,x);i=n){
    if(r<0)t=1;
    else   t=2;
    if(P[t][i]==0){
      P[t][i]=C;
      P[0][C]=i;
      H[i]=MAX(1,H[i]);
      //N[C]=x;
      strcpy(N[C],x);
      C++;
    }
    n=P[t][i];
  }//printf("%d\n",i);
  j=P[0][i];
  while(j){
    if(h(j)<-1){
      if(h(P[1][j])>0)rot(P[1][j],1);
      rot(j,2);
      break;
    }
    if(h(j)>1){
      if(h(P[2][j])<0)rot(P[2][j],2);
      rot(j,1);
      break;
    }
    if(h(j)==0)break;
    j=P[0][j];
    //if(j==0)break;
  }//printf("%d\n",i);
  return i;
}      
int main(){
  int i,l,max=0,mj=1,r,a[1010]={};
  char *c,*mi,s[1020];
  fgets(s,1010,stdin);
  mi=strtok(s," \n");
  a[mj=mfind(mi)]++;
  max=strlen(mi);
  // printf("%s\n",mi);
  while(c=strtok(NULL," \n")){
    //printf("%s\n",c);
    a[r=mfind(c)]++;
    //printf("%d\n",r);
    l=strlen(c);//printf("%s %d\n",mi,l);
    if(max<l){
      max=l;
      strcpy(mi,c);
    }//printf("a\n");
    if(a[r]>a[mj])mj=r;//printf("a\n");
  }
  //printf("%s %d\n",mi,mj);
  printf("%s %s\n",N[mj],mi);
  return 0;
}

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

int main() {
	int n;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++)cin >> a.at(i);
	if (a.at(0) != 0) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 1; i < n; i++) {
		if (a.at(i) - a.at(i - 1) >= 2){
			cout << -1 << endl;
			return 0;
		}
	}
	ll ans = 0;
	for (int i = 1; i < n; i++) {
		if (a.at(i) <= a.at(i - 1))ans+=a.at(i - 1);
	}
	ans += a.at(n - 1);
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main() {
  int A, B;
  cin >> A >> B;
  int lower = max((100 * A + 7) / 8, 100 * B / 10);
  int upper = min((100 * (A + 1) + 7) / 8, 100 * (B + 1) / 10);
  cout << (lower < upper ? lower : -1) << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int a = sc.nextInt();
  int b = sc.nextInt();
  if (b > a){
   System.out.println("a < b");
  }else if (a > b){
   System.out.println("a > b");
  }else{
   System.out.println("a == b");
  }
 }
}


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

int main(){
  int N;
  cin >> N;
  vector<int> d(N);
  for(int i=0; i<N; i++){
    cin >> d[i];
  }
  int sum=0;
  for(int i=0; i<N;i++){
    for(int j=i+1; j<N; j++){
      sum+=d[i]*d[j];
    }
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
n = $stdin.gets.chomp.to_i
a = $stdin.gets.chomp.split(" ")
a.map! do |a_j|
a_j.to_i
end
b = $stdin.gets.chomp.split(" ")
b.map! do |a_j|
a_j.to_i
end
c = $stdin.gets.chomp.split(" ")
c.map! do |a_j|
a_j.to_i
end

ans = 0

for i in 1..n - 1
    if a[i] == a[i - 1] + 1
        ans += c[a[i - 1] - 1]
    end

end

for i in 0..n - 1
    ans += b[i]
end

puts ans

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	int n,k;
	cin >> n >> k;
	int x[n];
	FOR(i,0,n) cin >> x[i];
	int ans = 0;
	FOR(i,0,n) ans += min(x[i],abs(x[i]-k));
	cout << ans*2;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int d[6];
int v[30];
int main(){
    int a,b;
    while(scanf("%d%d",&a,&b),b){
        v[0]=a;
        int i=0;
        bool ok=false;
        while(!ok){
            int c=v[i];
            for(int j=0;j<b;j++){
                d[j]=c%10;
                c/=10;
            }
            i++;
            std::sort(d,d+b);
            int p=0;
            int q=0;
            for(int j=0;j<b;j++){
                p*=10;q*=10;
                p+=d[j];
                q+=d[b-1-j];
            }
            v[i]=q-p;
            for(int j=0;j<i;j++)if(v[j]==v[i]){
                printf("%d %d %d\n",j,v[j],i-j);
                ok=true;
                break;
            }
        }
    }
}

Measured memory_bytes: 2728
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def members(self, x):
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.all_roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.all_roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.all_roots())

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())

uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]

ans = [0]*m
ans[-1] = (n * (n-1))//2

for i, (a,b) in enumerate(reversed(ab)):
    a,b = a-1,b-1

    if -i-2 == -m-1:
        break

    if uf.is_same(a,b):
        ans[-i-2] = ans[-i-1]

    else:
        ans[-i-2] = ans[-i-1] - uf.size(a)*uf.size(b)
        uf.union(a,b)

print(*ans, sep='\n')


Measured memory_bytes: 104156
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;


public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();

        int a = scanner.nextInt();
        HashSet<Integer> hs = new HashSet<Integer>();
        hs.add(a);

        int tmp=a;
        int size=hs.size();

        for(int i=0;i<1000000;i++) {
        	if(tmp%2==0) {
        		tmp/=2;
        	}else {
        		tmp=tmp*3+1;
        	}
        	hs.add(tmp);

        	if(size==hs.size()) {
        		System.out.println(i+2);
        		break;
        	}else {
        		size=hs.size();
        	}
        }

    }

    private class MyScanner {
        String[] s;
        int i;
        BufferedReader br;
        String reg = " ";
        MyScanner () {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public String next() {
            try {
                if (i < s.length) return s[i++];
                String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0);
                i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}

Measured memory_bytes: 21204
#include <iostream>
 
using namespace std;
 
int main() {
  long long N;
  cin >> N;
  long long ans = N - 1;
  for (long long i = 1; i * i <= N; i++) {
    // N / i にあまりが発生したら i は N の約数ではない
    if (N % i) continue;
    long long j = N / i;
    ans = min(ans, i + j - 2);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3668
// #include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;

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

int main() {
    string s;
    cin >> s;

    map<string, int> m;
    m["SSS"] = 0;
    m["RSS"] = 1;
    m["SRS"] = 1;
    m["SSR"] = 1;
    m["RSR"] = 1;
    m["RRS"] = 2;
    m["SRR"] = 2;
    m["RRR"] = 3;

    cout << m[s] << endl;

    return 0;
}

Measured memory_bytes: 3628
from sys import stdin
 
input = stdin.readline
lines = stdin.readlines
 
N = int(input())
 
txy = ((map(int, line.split())) for line in lines())
t,x,y =(0, 0, 0)
for nt, nx, ny in txy:
    dis=abs(nx-x)+abs(ny-y)
    tim = nt - t
    if tim >= dis and (tim - dis) % 2 ==0:
        t,x,y=nt, nx, ny
    else:
        print('No')
        break
else:
    print('Yes')

Measured memory_bytes: 10284
import scala.io.StdIn._
import scala.annotation.tailrec
import scala.collection._

object Main {

  def makeSoE_PrimesTo(top: Int) = {
    import scala.annotation.tailrec
    val topNdx = (top - 3) / 2 + 1
    val (cmpsts, sqrtLmtNdx) = (new Array[Int]((topNdx >>> 5) + 1), (Math.sqrt(top).toInt - 3) / 2)

    @inline def isCmpst(ci: Int): Boolean = (cmpsts(ci >>> 5) & (1 << (ci & 31))) != 0

    @inline def setCmpst(ci: Int): Unit = cmpsts(ci >>> 5) |= 1 << (ci & 31)

    @tailrec def forCndNdxsFrom(cndNdx: Int): Unit =
         if (cndNdx <= sqrtLmtNdx) {
           if (!isCmpst(cndNdx)) { //is prime
             val p = cndNdx + cndNdx + 3

             @tailrec def cullPrmCmpstsFrom(cmpstNdx: Int): Unit =
               if (cmpstNdx <= topNdx) { setCmpst(cmpstNdx); cullPrmCmpstsFrom(cmpstNdx + p) }

             cullPrmCmpstsFrom((p * p - 3) >>> 1) }

           forCndNdxsFrom(cndNdx + 1) }; forCndNdxsFrom(0)

    @tailrec def getNxtPrmFrom(cndNdx: Int): Int =
      if ((cndNdx > topNdx) || !isCmpst(cndNdx)) cndNdx + cndNdx + 3 else getNxtPrmFrom(cndNdx + 1)

    Iterator.single(2) ++ Iterator.iterate(3)(p => getNxtPrmFrom(((p + 2) - 3) >>> 1)).takeWhile(_ <= top)
  }

  @tailrec
  def loop(s: String){
    if(s != null){
       val Array(n,_*) = s.split(" ").map(_.toInt)
       if(n<2) println(0)
       else println(makeSoE_PrimesTo(n).size)
       loop(readLine)
    }
  }

  def main(args: Array[String]): Unit ={
    loop(readLine)
  }
}

Measured memory_bytes: 65152
#include <bits/stdc++.h>
#define N 200010
using namespace std;

int cnt[N], n, k;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		int k; scanf("%d", &k);
		cnt[k]++;
	}
	sort(cnt + 1, cnt + 1 + n);
	int Ans = n;
	for (int i = n; i > n - k; i--) Ans -= cnt[i];
	cout << Ans << endl;
	return 0;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  while(H!=0 || W!=0) {
      for (int i=0; i<H; i++) {
          for (int j=0; j<W; j++) {
              if ((i+j)%2==0) cout << "#";
              else cout << ".";
              if (j==W-1) cout << endl;
          }
          if (i==H-1) cout << endl;
      }
      cin >> H >> W;
  }
}


Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int x;
    cin >> x;
    if(x >= 30) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 3576
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    string t; cin >> t;
    for (auto &c:t) {
        if (c == '?') c = 'D';
    }
    cout << t << '\n';
    return 0;
}

Measured memory_bytes: 3752
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,k,f[200005];
ll s;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)++f[i%k];
    for(int i=0;i<k;++i){
        int x=(k-i)%k;
        if(x*2%k==0)s+=f[i]*1ll*f[x]*1ll*f[x];
    }
    printf("%lld\n",s);
	//system("pause");
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(n) for (int i = 0; i < (n); ++i)
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N + 1);
    vector<ll> B(N);
    rep(N + 1)
    {
        cin >> A[i];
    }
    rep(N)
    {
        cin >> B[i];
    }
    ll ans = 0;
    rep((N + 1) / 2)
    {
        //cout << "A[" << i << "]:" << A[i]
        //     << " B[" << i << "]:" << B[i]
        //     << " A[" << i + 1 << "]:" << A[i + 1];
        ll m = min(A[i], B[i]);
        A[i] -= m;
        B[i] -= m;
        ans += m;
        //cout << " m1:" << m;
        m = min(A[i + 1], B[i]);
        A[i + 1] -= m;
        B[i] -= m;
        ans += m;
        //cout << " m2:" << m;
        //cout << " ans:" << ans << endl;
    }
    for (int i = N; i > (N + 1) / 2; --i)
    {
        //cout << "A[" << i << "]:" << A[i]
        //     << " B[" << i - 1 << "]:" << B[i - 1]
        //     << " A[" << i - 1 << "]:" << A[i - 1];
        ll m = min(A[i], B[i - 1]);
        A[i] -= m;
        B[i - 1] -= m;
        ans += m;
        //cout << " m1:" << m;
        m = min(A[i - 1], B[i - 1]);
        A[i - 1] -= m;
        B[i - 1] -= m;
        ans += m;
        //cout << " m2:" << m;
        //cout << " ans:" << ans << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
N = int(input())
def get_num(a,b,N):#aで始まり、bで終わるN以下の数の個数
    cnt = 0
    if(a == b and N >= a):
        cnt += 1#1keta
    if(a*10+b <= N):
        cnt += 1#2keta
    #3keta~
    if(100<=N<1000):
        c = 100*a + b
        while(c <= N and c < 100*a + 90 + b + 1):
            cnt += 1
            c += 10
    elif(1000<=N<10000):
        c = 1000*a+b
        cnt += 10
        while(c <= N and c < 1000*a + 990 + b + 1):
            cnt += 1
            c += 10
    elif(10000<=N<100000):
        c = 10000*a + b
        cnt += 110
        while(c <= N and c < 10000*a + 9990 + b + 1):
            cnt += 1
            c += 10
    elif(100000<=N<=200000):
        c = 100000*a + b
        cnt += 1110
        while(c <= N and c < 100000*a + 99990 + b + 1):
            cnt += 1
            c += 10
    return cnt
sum = 0
for i in range(1,10):
    for j in range(1,10):
        sum += get_num(i,j,N)*get_num(j,i,N)
print(sum)

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

int main() {

	int n;
	std::cin >> n;

	std::vector<int> x(n);
	for (int i = 0; i < n; i++) {
		std::cin >> x[i];
	}

	std::vector<int> sortX = x;
	sort(begin(sortX), end(sortX));

	for (int i = 0; i < n; i++) {
		int idx = std::distance(std::begin(sortX), std::lower_bound(std::begin(sortX), std::end(sortX), x[i]));
		std::cout << (idx < n / 2 ? sortX[n / 2] : sortX[n / 2 - 1]) << std::endl;
	}
	return 0;
}


Measured memory_bytes: 3712
INF = 1000000000000000000
N = int(input())
flag = 1
l = list(map(int,input().split()))
if 0 in l:
  print(0)
  import sys
  sys.exit()
sum = 1
for i in l:
  sum = sum*i
  if sum > INF:
    print(-1)
    flag = 0
    break
  else:
    pass
    
if flag:
  print(sum)

Measured memory_bytes: 21704
import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])

Measured memory_bytes: 277768
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define ff first
#define pii pair<int, int>
#define vii vector< pair<int,int> >
#define vi vector<int>
#define vvi vector< vector< int> >
#define ss second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define int long long
#define all(a) a.begin(), a.end()
#define inf (1LL<<61)
#define ull unsigned long long
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace4(x, y, z, d)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#d<<": "<<d<<endl

#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define debug1(x) cerr << #x << ": " << x <<'\n'
#define debug2(x, y) cerr << #x << ": " << x << '\t' << #y << ": " << y <<'\n'
#define debug3(x, y, z) cerr << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": " << z <<'\n'
using namespace std;
int dx[]={1,0,-1, 0};int dy[]={0,1,0, -1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
bool compare(const pair<int,int> &a,
             const pair<int,int> &b)
{
    if(a.ff == b.ff) {
        return (b.ss < a.ss);
    }
    return (a.ff<b.ff);
}
bool prime[1000001];
void SieveOfEratosthenes(int n) 
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.

    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
}

int32_t main()
{
    IOS;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    /********************* From here ***********************/
    
    int n, m;
    cin >> n >> m ;
    vii v;
    rep(i, 0, n){
        int a,b;
        cin >> a >> b;

        v.pb(mp(a,b));
    }
    int can = 0, cost = 0;
    sort(all(v));
    int i = 0;
    while(can < m && i<n){
        if(can+v[i].ss <= m){
            can = can+v[i].ss;
            cost += v[i].ss*v[i].ff;
            i++;
        }
        else if(can + v[i].ss>m){
            cost += v[i].ff*(m-can);
            can = m;
            i++;
        }
        //trace3(can, i, cost);
    }

    cout << cost;
}



Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long 
signed main() 
{
    
    IOS;    
    int n;cin>>n;
    int ans=0;
    vector<int>v(100002,0);
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
        v[i*i+j*j+k*k+i*j+i*k+j*k]++;
            
        
        }
    }
    }
    for(int i=1;i<=n;i++)cout<<v[i]<<endl;

    
    return 0; 
} 

Measured memory_bytes: 3904
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= k; j++)
            if (i - j >= 0)
                chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]));
    cout << dp[n - 1] << endl;
}

Measured memory_bytes: 4052
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int M = 1e5 + 10;
const int N = 200 + 10;
int64 dp[M];
int64 F[N], G[N];
int a[N];
int n;

int64 power_mod(int64 a, int n) {
  int64 ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * a % MOD;
    a = a * a % MOD;
  }
  return ret;
}

int64 solve(int x, int len) {
  // trace(x, len);
  int64& ret = dp[x];
  if (ret >= 0) return ret;
  if (len == 0) return ret = x;
  if (len == 1) return ret = x % a[0];
  ret = 0;
  for (int i = 0; i < len; ++i) {
    int y = x % a[i];
    int nxt_len = upper_bound(a, a + len, y) - a;
    ret += F[len - 1] * G[nxt_len] % MOD * solve(y, nxt_len) % MOD;
    ret %= MOD;
  }
  return ret;
}

int main() {
  F[0] = G[0] = 1;
  for (int i = 1; i < N; ++i) {
    F[i] = F[i - 1] * i % MOD;
    G[i] = power_mod(F[i], MOD - 2);
  }
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);
  memset(dp, 255, sizeof(dp));
  int len = upper_bound(a, a + n, m) - a;
  int ret = F[n] * G[len] % MOD * solve(m, len) % MOD;
  printf("%d\n", ret);
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	vector<ULL> fac, inv, ifac;
	static const ULL M = 998244353;
	ULL C(UL n, UL m) { if (n < m) return 0; return fac[n] * ifac[m] % M * ifac[n - m] % M; }

	void Solve() {
		UL N, K; cin >> N >> K;
		{
			ULL sz = N + 2 * K;
			fac.resize(sz); inv.resize(sz); ifac.resize(sz);
			fac[0] = 1; for (ULL i = 1; i < sz; i++) fac[i] = fac[i - 1] * i % M;
			inv[1] = 1; for (ULL i = 2; i < sz; i++) inv[i] = M - (M / i * inv[M % i]) % M;
			ifac[0] = 1; for (ULL i = 1; i < sz; i++) ifac[i] = ifac[i - 1] * inv[i] % M;
		}
		ULL ans = 0;
		for (ULL m = K % 2; m <= min(K, N); m += 2) {
			ULL oe = C(N, m);
			ULL al = C((3 * K - m) / 2 + N - 1, N - 1);
			ULL ov = C((K - m) / 2 + N - 1, N - 1) * m % M;
			ULL ev = C((K - m) / 2 + N - 2, N - 1) * (N - m) % M;
			ULL dance = (al + (M - ov) + (M - ev)) % M;
			dance = dance * oe % M;
			//cout << m << ":" << oe << " " << al << " " << ov << " " << ev << endl;
			ans += dance;
		}
		cout << (ans % M) << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


Measured memory_bytes: 47104
#include <iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#include<cmath>
#include<iomanip>
using namespace std;

const double PI  =3.141592653589793238463;
#define pb push_back
#define pf push_front
typedef unsigned long long ull;
typedef long long ll;

typedef vector<int> vi;
typedef pair<int,int> pi;
//2 7 3 4 9


int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
map<string,ll>MAP;
MAP["AC"]=0;
MAP["WA"]=0;
MAP["TLE"]=0;
MAP["RE"]=0;
ll t;cin>>t;
string s;
while(t--){
    cin>>s;
    MAP[s]++;
}

for(int i=0;i<4;i++){
if(i==0){
    auto it=MAP.find("AC");
    cout<<it->first<<" x "<<it->second<<endl;
    continue;
}
if(i==1){
    auto it=MAP.find("WA");
    cout<<it->first<<" x "<<it->second<<endl;
    continue;
}
if(i==2){
    auto it=MAP.find("TLE");
    cout<<it->first<<" x "<<it->second<<endl;
    continue;
}
if(i==3){
    auto it=MAP.find("RE");
    cout<<it->first<<" x "<<it->second<<endl;
    continue;
}
}
    return 0;
}


Measured memory_bytes: 3636
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  if (__builtin_popcount(n) == 1) {
    cout << "No\n";
    return 0;
  }
  cout << "Yes\n";
  vector<int> a, b;
  a.emplace_back(1); b.emplace_back(2);
  a.emplace_back(2); b.emplace_back(3);
  a.emplace_back(3); b.emplace_back(1 + n);
  a.emplace_back(1 + n); b.emplace_back(2 + n);
  a.emplace_back(2 + n); b.emplace_back(3 + n);
  for (int i = 5; i <= n; i += 2) {
    a.emplace_back(i - 1); b.emplace_back(i);
    a.emplace_back(i); b.emplace_back(1 + n);
    a.emplace_back(1 + n); b.emplace_back(i - 1 + n);
    a.emplace_back(i - 1 + n); b.emplace_back(i + n);
  }
  if (n % 2 == 0) {
    int tmp = n | 1, one = 0;
    for (int i = 17; i >= 0; --i) {
      if (tmp >> i & 1) {
        one = 1 << i;
        tmp ^= 1 << i;
        break;
      }
    }
    a.emplace_back(n); b.emplace_back(one + n);
    a.emplace_back(tmp); b.emplace_back(n + n);
  }
  REP(i, 2 * n - 1) cout << a[i] << ' ' << b[i] << '\n';
  return 0;
}


Measured memory_bytes: 4588
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

long long a[200001] = {0};

int binsearch(int l, int u){
   int n = l-1, m = u;
   int k;
   while(l+1 < u){
      k = (l+u)/2;
      long long x = a[k] - a[n];
      long long y = a[m] - a[k];

      if(x > y)
         u = k;
      else
         l = k;
   }
   if(abs((a[m] - a[l]) - (a[l] - a[n])) > abs((a[m] - a[l+1]) - (a[l+1] - a[n])))
      return l+1;

   return l;
}



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

   long long sum = 0;
   for(int i=1; i<=n; i++){
      cin >> a[i];
      a[i] += a[i-1];
   }

   long long ans = a[n];

   for(int c=2; c<=n-2; c++){
      int b = binsearch(1, c);
      int d = binsearch(c+1, n);

      long long p, q, r, s;
      p = a[b];
      q = a[c] - a[b];
      r = a[d] - a[c];
      s = a[n] - a[d];

      long long buf = max({p, q, r, s}) - min({p, q, r, s});

      if(ans > buf){
         ans = buf;
//         cout << ans<< " " << b<<" " << c<<" " << d << endl;
      }

   }

   cout << ans << endl;



   return 0;
}


Measured memory_bytes: 1792
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int,input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
box = []
for i in range(n):
    box.append(uf.size(i))
print(max(box))

Measured memory_bytes: 22492
#include <bits/stdc++.h>
using namespace std;
int jeo[105];
int cnt,A,B,C,D,maxi;

int main()
{
    cin>>A>>B>>C>>D;
    for(int i=A;i<=B;i++)
    {
        jeo[i]=jeo[i]+1;

    }
    for(int i=C;i<=D;i++)
    {
        jeo[i]=jeo[i]+1;
    }
    maxi=max(B,D);
    for(int i=0;i<=maxi;i++)
    {
        if(jeo[i]==2)
        {
            cnt=cnt+1;
        }
    }
    if(cnt-1>0){
    cout<<cnt-1;
    }
    else
    {
        printf("0");
    }
    
}



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

using namespace std;
 int k;
    string s;
int main()
{
   
    cin>>k>>s;
    if(s.size()<=k)
        cout<<s<<endl;
    else
    {
        
        for(int i=0;i<k;i++)
            cout<<s[i];
        cout<<"..."<<endl;
    }

    return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define N 100
using namespace std;

int main(){
  int m,n,a[N][N],f,ans=0;
  cin>>m>>n;
  for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)cin>>a[i][j];
  for(int i=1;i<m;i++)
    for(int j=0;j<n;j++)
      a[i][j]=!a[i][j];
  for(int i=0;i<m;i++)
    for(int j=1;j<n-1;j++)
      a[i][j]=!a[i][j];
  for(int i=0;i<m;i++){
    f=0;
    for(int j=0;j<n;j++){
      if(a[i][j])ans++;
      if(!a[i][j])f=1;
    }
    if(n!=1){
      if(f)ans++;
      else ans--;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1200
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

/*
 <url:https://cf17-relay-open.contest.atcoder.jp//tasks/relay2_a>
 問題文============================================================
 ButCoder株式会社 は、プログラミングコンテストサイト「ButCoder」を運営しています。
 このサイトでは、ユーザーにはレーティングという技量を表す整数値が与えられ、
 その値はユーザーがコンテストに参加するたびに変動します。
 新規ユーザーのレーティングの初期値は 0 であり、レーティングが K 以上に達したユーザーは 皆伝 と呼ばれます。
 なお、レーティングは負になることもあります。
 
 低橋くんというユーザーが ButCoder に新たに登録しました。
 彼のレーティングは、彼が奇数回目に参加するコンテスト（1 回目、3 回目、5 回目…）では毎回 A 増加し、
 偶数回目に参加するコンテスト（2 回目、4 回目、6 回目…）では毎回 B 減少することが予測されます。
 
 この予測によると、彼が初めて皆伝になるのは何回のコンテストに参加した直後でしょうか、
 もしくは彼は永遠に皆伝になれないでしょうか？
 =================================================================
 解説=============================================================
 
 A <= B の時
     AがKを超えているならば 1
             いないならば -1
 
 それ以外の時を考える
 
まず、レーティングがKを超える時の式は
 n*A - m*B >= K  (m = n-1, n)
 
 式変形すると
 n*A - (n + x)*B >= K (x = -1,0)
 
 n*(A-B) >= K + x*B
 n >= (K + x*B)/(A-B)
 これを満たす n を求め、実際のコンテスト数に反映した時の最小値を求めればよい
 
 ================================================================
 */

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll K,A,B; cin >> K >> A >> B;
    if(A <= B){
        if(K <= A){
            cout << 1 << endl;
        }else{
            cout << -1 << endl;
        }
        return 0;
    }
    ll res = LLONG_MAX;
    for(int i = -1; i <= 0;i++){
        ll cost = B*i;
        ll tmp = (K + cost)/(A-B);
        if((K+cost)%(A-B) != 0) tmp++;
        res = min(res,tmp*2 + i);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256