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

int count;

void comb(int n, int x) {                                                       
    int i;                                                                      
    for (i = 0; i < 10; i++) {                                                  
        if (n - i < 0)                                                          
            return;                                                             
        if (n - i == 0 && x == 0) {                                             
            count++;                                                            
            return;                                                             
        }                                                                       
        if (x > 0) {                                                            
            comb(n - i, x - 1);                                                 
        }                                                                       
    }                                                                           
}

int main(void) {                                                                
    int n;                                                                      
                                                                                
    while(scanf("%d", &n) != EOF) {                                             
        count = 0;                                                              
        comb(n, 3);                                                             
        printf("%d\n", count);                                                  
    }                                                                           
    return 0;                                                                   
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define ll long long
#define MAX 1000005
#define MOD (ll)(1e9+7)
#define INF INT32_MAX
#define INFL INT64_MAX
using namespace std;

void solve()	{
	int n,l;
	cin >> n >> l;
	string s[n];
	for(int i=0; i<n; i++)	cin >> s[i];
	sort(s,s+n);
	for(int i=0; i<n; i++)	cout << s[i];
	cout << endl;
}

int main()	
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin >> t;
	for(int i=1; i<=t; i++)	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cmath>
using namespace std;

int a[100010];
int d[100010];
int n,k;

bool check(int m){
    for(int i=1;i+m-1<=n;++i){
        if(d[i+m-1]-d[i-1]+(a[i]==0&&a[i-1]==0?1:0)<=k){
            return 1;
        }
    }
    return 0;
}

int main() {
    cin>>n>>k;
    a[0]=1;
    for(int i=1;i<=n;++i){
        scanf("%1d",&a[i]);
        d[i]=d[i-1];
        if(a[i]==0&&a[i-1]==1)d[i]++;
    }
    int lo=0,hi=n,mid;
    int ans=0;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(check(mid))ans=mid,lo=mid+1;
        else hi=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()

int main(){
  string s; cin >> s;
  ll n = s.size();
  string t = "";
  FOREACH(c,s) if(c!='x') t = t + c;
  ll m = t.size();
  if(m==0){
    cout << 0 << endl;
    return 0;
  }
  REP(i,m/2) if(t[i]!=t[m-1-i]){
    cout << -1 << endl;
    return 0;
  }

  ll cnt = 0;
  ll l,r;
  char c;
  REP(i,n){
    if(s[i]!='x') cnt++;
    if(cnt==(m+1)/2){
      l = i-1; 
      c = s[i];
      break;
    }
  }
  if(m%2==0){
    FOR(i,l+2,n){
      if(s[i]==c){
        r = i+1;
        break;
      }
    }
  }else r=l+2;
  ll ans = 0;
  while(1){
    if(l<0 && r>n-1) break;
    if(l<0){
      ans++;
      r++;
    }else if(r>n-1){
      ans++;
      l--;
    }else if(s[l] != s[r]){
      ans++;
      if(s[l] == 'x') l--;
      else r++;
    }else{
      l--;
      r++;
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 696
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
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;}
ll mod= 1e9 + 7;


int main(){
  string s;
  cin >> s;
  int n=s.size();
  int ans=0;
  rep(i,n){
    ans+=s[i]-48;
  }
  if((ans+9)%9==0){cout << "Yes" << endl;}else{cout << "No" << endl;}
}


Measured memory_bytes: 3744
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int A = sc.nextInt();
    static int B = sc.nextInt();
    static int H = sc.nextInt();
    static int M = sc.nextInt();

    public static void main(String[] args) {
        //角度を求める
        double kHour = H * 30 + M * 0.5;
        double kMin = M * 6;
        double kakudo = kHour - kMin;
        if (kakudo > 180){
            kakudo = 360 - kakudo;
        } else if (kakudo < 0){
            kakudo *= -1;
        }
        double dC = A * A + B * B - 2 * A * B * Math.cos(Math.toRadians(kakudo));
//        BigDecimal x = new BigDecimal(Math.sqrt(dC));
//        MathContext mc = new MathContext(50, RoundingMode.UP);
//        BigDecimal result = x.round(mc);
        double result = Math.sqrt(dC);
        System.out.print(result);

    }

}

Measured memory_bytes: 35976
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
 
template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<endl;}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}
 
const double EPS =1e-9;
const long INF =2147483647;//32bit 2*1e+9
const long MOD =1e+9+7;
#define PI 3.14159265258979
 
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

int main(void){
	int H,W;
	string S[55];
	cin>>H>>W;
	FOR(i,1,H+1) cin>>S[i];
	
	S[0]="";
	S[H+1]="";

	FOR(i,1,H+1){
		REP(j,W){
			if(S[i][j]=='#') cout<<'#';
			else{
				int counter=0;
				REP(r,8) if(S[i+dy[r]][j+dx[r]]=='#') counter++;
				cout<<counter;
			}
		}
		cout<<endl;
	}
	
	return 0;
}



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

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

    cin >> a >> b >> c >> d;
    if(a+b > c+d){
        cout << "Left" << endl;
    }else if(a+b < c+d){
        cout << "Right" << endl;
    }else{
        cout << "Balanced" << endl;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node
{
	int key;
	Node prev, next;

	Node()
	{
		key = -1;
		prev = next = null;
	}
}

class DoublyLinkedList
{
	Node nil;
	int N;

	DoublyLinkedList()
	{
		nil = new Node();
		nil.next = nil;
		nil.prev = nil;
		N = 0;
	}

	//先頭に挿入
	void insertNode(Node t, int val)
	{
		Node x = new Node();
		x.key = val;
		x.next = t.next;
		t.next.prev = x;
		x.prev = t;
		t.next = x;
		N++;
	}

	void insertFirst(int val)
	{
		insertNode(nil, val);
	}

	void insertLast(int val)
	{
		insertNode(nil.prev, val);
	}

	void deleteNode(Node t)
	{
		if (t == nil)
		{
			return;
		}
		t.prev.next = t.next;
		t.next.prev = t.prev;
		N--;
	}

	void deleteFirst()
	{
		deleteNode(nil.next);
	}

	void deleteLast()
	{
		deleteNode(nil.prev);
	}

	Node searchKey(int key)
	{
		Node cur = nil.next;
		while (cur != nil && cur.key != key)
		{
			cur = cur.next;
		}
		return cur;
	}

	void deleteKey(int key)
	{
		deleteNode(searchKey(key));
	}

	void print()
	{
		for (Node cur = nil.next; cur != nil; cur = cur.next)
		{
			if (cur != nil.next)
			{
				System.out.print(" ");
			}
			System.out.print(cur.key);
		}
		System.out.println();
	}
}

public class Main
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		DoublyLinkedList L = new DoublyLinkedList();
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; ++i)
		{
			String line = br.readLine();
			if (line.charAt(6) == ' ')
			{
				//****** x
				String[] com = line.split(" ");
				if (com[0].charAt(0) == 'i')
				{
					L.insertFirst(Integer.parseInt(com[1]));
				} else if (com[0].charAt(0) == 'd')
				{
					L.deleteKey(Integer.parseInt(com[1]));
				}
			} else
			{
				if (line.charAt(6) == 'F')
				{
					L.deleteFirst();
				} else if (line.charAt(6) == 'L')
				{
					L.deleteLast();
				}
			}
		}
		L.print();
	}
}



Measured memory_bytes: 192244
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a.append(10**9+7)
exnum_list=[]
ctr=0
for i in range(n):
    if a[i]==a[i+1]:
        ctr+=1
    else:
        exnum_list.append(ctr+1)
        ctr=0
exnum_list.sort()
en=len(exnum_list)
if en<=k:
    print(0)
else:
    print(sum(exnum_list[:en-k]))


Measured memory_bytes: 24996
#include <iostream>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int a[n][m], b[m];

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> a[i][j];
		}
	}
	for(int i=0; i<m; i++) {
		cin >> b[i];
	}
	int sum = 0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			sum += a[i][j] * b[j];
		}
		cout << sum << endl;
		sum = 0;
	}

	return 0;
}


Measured memory_bytes: 3136
from collections import defaultdict
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

dp = defaultdict(int)
dp[0] = 0
for w, v in wv:
    dp_cur = list(dp.items())
    for w_cur, v_cur in dp_cur:
        if w_cur+w <= W:
            dp[w_cur+w] = max(dp[w_cur+w], v_cur+v)
print(max(dp.values()))

Measured memory_bytes: 4072
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
#include <deque>
using namespace std;

int n, s, a[110000], b[110000], ans;

int main() {
	scanf("%d", &n);
	s = 0;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]), s ^= a[i];
	for (int j = 1; j <= n; j++) {
		for (int i = 31; i >= 0; i--)
			if (a[j] % (1 << i) == 0) {
				b[i] += 1;
				break;
			}
	}
	for (int i = 31; i >= 0; i--)
		if (s & (1 << i)) {
			if (!b[i]) {
				printf("-1\n");
				return 0;
			}
			s ^= (1 << i) - 1;
			ans += 1;
		}
	printf("%d\n", ans);
	// for (int i = 0; i <= 31; i++) {
	// 	for (int j = 1; j <= n; j++)
	// 		if (a[j] % (1 << i) == 0)
	// 			b[i][j] = 1;
	// 	if (s & (1 << i))
	// 		b[i][0] = 1;
	// 	else
	// 		b[i][0] = 0;
	// }

	// for (int i = 1; i <= n; i++)
	// 	for (int j = 0; j <= 31; j++)
	// 		if (b[j][i]) {
	// 			for (int p = j + 1; p <= 31; p++)
	// 				if (b[p][i]) {
	// 					for (int q = 0; q <= n; q++)
	// 						b[p][q] ^= b[j][q];
	// 				}
	// 			break;
	// 		}
	// for (int i = 0; i <= 30; i++) {
	// 	int cur = 0;
	// 	for (int j = 1; j <= n; j++)
	// 		cur += b[i][j];
	// 	if (!cur && b[i][0]) {
	// 		printf("-1\n");
	// 		return 0;
	// 	}
	// }

}


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

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

using namespace std;

int main(){
	bool f[128]={};
	f['q']=f['w']=f['e']=f['r']=f['t']=f['a']=f['s']=f['d']=f['f']=f['g']=f['z']=f['x']=f['c']=f['v']=f['b']=true;

	for(string s;cin>>s,s!="#";){
		int len=s.length(),ans=0;
		rep(i,len) if(i>0 && f[s[i-1]]!=f[s[i]]) ans++;
		cout<<ans<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
a,b,c,d = input()
for i in range(2**3):
    ls = ["+","+","+"]
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = "-"
    if eval(a+ls[0]+b+ls[1]+c+ls[2]+d) == 7:
        print(a+ls[0]+b+ls[1]+c+ls[2]+d+"=7")
        break

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <math.h> 
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>
#include <numeric>
#include <bitset>
#include <queue>
#include <map>

using namespace std;


int main() {

	//input
	int n;
	cin >> n;

	//全ての項目に対して3重でforループを回して各項目で条件を満たす組み合わせを出力する


	vector<int> data_x;
	vector<int> data_y;
	vector<int> data_h;
	vector<int> data_h2;

	for (int i = 0; i < n; ++i) {
		int x, y, h;
		vector<int> data;
		cin >> x >> y >> h;
		data_x.push_back(x);
		data_y.push_back(y);
		data_h.push_back(h);
		data_h2.push_back(h);
	}

	sort(data_h2.begin(), data_h2.end());
	int h_couho;
	h_couho = data_h2[n - 1];


	//x座標ループ
	for (int i = 0; i <= 100; ++i) {
		//y
		for (int j = 0; j <= 100; ++j) {
			//h
			for (int k = data_h2[0]; k <= h_couho + 100; ++k) {
				int t_cnt = 0;
				//調査結果
				for (int p = 0; p < n; ++p) {
					//右辺
					int uhen = 0;
					uhen = max((k - abs(data_x[p] - i) - abs(data_y[p] - j)), 0);
					if (uhen == data_h[p]) {
						t_cnt++;
						if (t_cnt == n) {
							cout << i << " " << j << " " << k << endl;
							return 0;
						}
						else {
							continue;
						}
					}
					else {
						continue;
					}
				}
			}
		}
	}


	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int n,m;
int x[100],a[10],b[10],c[10];

int dp[101][101][10];
int dfs(int l, int r, int f)
{
    if(dp[l][r][f]>=0) return dp[l][r][f];

    if(r-l==1) return (x[l]==a[f]);

    int ret = 0;
    for(int i=l+1; i<r; ++i) ret |= dfs(l,i,b[f])&dfs(i,r,c[f]);

    return dp[l][r][f]=ret;
}

int main()
{
    cin >>n;
    rep(i,n) cin >>x[i];
    cin >>m;
    rep(i,m)
    {
        cin >>a[i] >>b[i] >>c[i];
        --b[i];
        --c[i];
    }

    memset(dp,-1,sizeof(dp));
    string ans = "No";
    if(dfs(0,n,0)==1) ans = "Yes";
    cout << ans << endl;
    return 0;
}

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

int n;

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

    int next = 0;

    cin >> n;

    int roop_count = log10(n);

    int total = 0;

    for (int i = roop_count; i >= 0; i--)
    {
        total += (int)(n / (int)pow(10, i)) % 10;
    }
    cout << ((n % total == 0) ? "Yes" : "No") << "\n";
}

Measured memory_bytes: 512
#include <stdio.h>
#include <math.h>

int main(int argc, char const *argv[])
{
  int n,m;

  scanf("%d",&n);
  m=ceil(n/1.08);
  if(n==(int)(m*1.08)) printf("%d",m);
  else printf(":(");
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int k=0;k<10000;k++){
    int h,w;
    cin >> h >> w;
    if(h==0 || w==0)break;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout << "#";
        }
    cout << endl;
    }
    cout << endl;
}}


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

int a[110][110];
int b[110][110];
long c[110][110];

int main(){
	int n, m, l;
	scanf("%d%d%d", &n, &m, &l);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%d", &a[i][j]);
	for(int i = 0; i < m; i++)
		for(int j = 0; j < l; j++)
			scanf("%d", &b[i][j]);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < l; j++)
			for(int k = 0; k < m; k++)
				c[i][j] += a[i][k] * b[k][j];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < l-1; j++) {
			printf("%ld ", c[i][j]);
		}
		printf("%ld\n", c[i][l-1]);
	}
}



Measured memory_bytes: 3368
import heapq
n,m, = map(int,input().split())
E = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append((c,b))
    E[b].append((c,a))


def dijkstra(x):
    dis = [float("inf")]*n
    dis[x] = 0
    q = []
    heapq.heappush(q,(0,x))
    
    while q:
        cost,bef = heapq.heappop(q)

        if dis[bef] < cost:
            continue

        for ncost,nex in E[bef]:
            dist = ncost+cost

            if dist < dis[nex]:
                dis[nex] = dist
                heapq.heappush(q,(dist,nex))
    return dis

short = []
for i in range(n):
    short.append(dijkstra(i))
count = 0
for i in range(n):
    for dist,nex in E[i]:
        if short[i][nex] < dist:
            count += 1
print(count//2)



Measured memory_bytes: 3572
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vv = vector<vector<ll>>;
using vvv = vector<vector<vector<ll>>>;
using edge = struct {
  int to;
  int cost;
};
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define BIT(n, num) std::bitset<(n)>((num)).to_string()
#define REV(T) greater<T>()
#define PQ priority_queue<ll, vector<ll>, greater<ll>>
#define VVI(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVI(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))

typedef pair<ll, ll> Pair;
bool pairCompare(const Pair &a, const Pair &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp) % MOD;
  } else {
    return (n * POW(n, m - 1)) % MOD;
  }
}

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

int main() {
  ll N;
  vector<ll> A;
  string S;
  cin >> N >> S;
  vector<ll> D(27, 0);
  D[(int)S[0] - (int)'a'] = 1;
  ll ans = 1;
  FOR(i, 1, N) { D[(int)S[i] - (int)'a']++; }
  REP(j, 27) {
    ans *= (D[j] + 1) % MOD;
    ans %= MOD;
  }
  cout << ans - 1 << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
 ll dp[3500][3500][3]; 
 int a[3500];
 ll n;
 ll solve(int s,int e,int turn){
     if(s>e||e<s){
         return 0;
     }
     ll &ret=dp[s][e][turn];if(ret!=-1){return ret;}
     if(turn==0){
         ret=max(solve(s+1,e,turn^1)+a[s],solve(s,e-1,turn^1)+a[e]);
     }else{
          ret=min(solve(s+1,e,turn^1)-a[s],solve(s,e-1,turn^1)-a[e]);
     }return ret;
     
   
 }
int main()
{
    
  cin>>n;
   for(int i=0;i<n;i++){
       cin>>a[i];
   }
   memset(dp,-1,sizeof dp);
   
  ll ans= solve(0,n-1,0);
  cout<<ans;
  
}

Measured memory_bytes: 291036
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <cmath>         // sqrt
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <bits/stdc++.h> // isupper, islower, isdigit, toupper, tolower
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, n) for (int i = (a); i < (n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pl;
typedef pair<int, int> P;
typedef tuple<ll, ll, string> Tlls;

// Greatest Common Divisor (最大公約数)
ll gcd(ll a, ll b)
{
  // Eucledean algorithm
  while (a)
  {
    if (a < b)
    {
      std::swap(a, b);
    }
    a %= b;
  }
  return b;
}

// Least Common Multiple 最小公倍数
ll lcm(ll a, ll b)
{
  return a / gcd(a, b) * b;
}

// key: value of prime factor素因数分解
// value: number of prime factor
map<ll, ll> prime_factorization(ll n)
{
  map<ll, ll> prime_factors;
  for (ll i = 2; i * i <= n; i++)
  {
    while (n % i == 0)
    {
      prime_factors[i]++;
      n /= i;
    }
  }
  if (n != 1)
    prime_factors[n] = 1;
  return prime_factors;
}

// 約数リスト約数の列挙
vector<ll> get_divisors(const ll n)
{
  vector<ll> divs;
  for (ll i = 1; i < (ll)sqrt((ld)n) + 1; i++)
  {
    if (n % i == 0)
    {
      divs.push_back(i);
      if (i != n / i)
      {
        divs.push_back(n / i);
      }
    }
  }

  // 必要に応じてソート
  // sort(divs.begin(), divs.end());

  return divs;
}

template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

int main()
{
  ll N, K;
  // int INF = 100000000;
  cin >> N >> K;
  const long long INF = 1LL << 60;

  // 入力
  // int N;
  long long h[110000];

  // DP テーブル
  long long dp[110000];

  for (int i = 0; i < N; ++i)
    cin >> h[i];

  // 初期化 (最小化問題なので INF に初期化)
  for (int i = 0; i < 110000; ++i)
    dp[i] = INF;
  // vector<ll> h(N + K + 1);
  // vector<ll> dp(N + K + 1, INF);
  // rep(i, N)
  // {
  //   cin >> h.at(i);
  // }
  dp[0] = 0;
  for (int i = 0; i < N; ++i)
  {
    for (int j = 1; j <= K; ++j)
    {
      chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
    }
  }
  // 答え
  cout << dp[N - 1] << endl;
  return 0;
}


Measured memory_bytes: 1920
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
#define M(a,b) memset(a,b,sizeof(a))
#define pb push_back
const int maxn = 100000+10;
const LL mod = 1000000007;
struct Node {
    int l,r;
}s[maxn+(maxn<<1)];
struct Seg {
    int l,r,s;
}t[maxn<<2];
int d[maxn<<2];
vector<int>g[maxn];
int n,m;
void build(int l,int r,int rt) {
    t[rt].l=l;
    t[rt].r=r;
    d[rt]=0;
    if (l==r) {
        t[rt].s=0;
        return ;
    }
    int mid = l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    t[rt].s=t[rt<<1].s+t[rt<<1|1].s;
    return ;
}
void pd(int &rt) {

    if (d[rt]==0) {
        return ;
    }
    int len=t[rt].r-t[rt].l+1;
    t[rt<<1].s+=d[rt]*(len-(len>>1));
    t[rt<<1|1].s+=d[rt]*(len>>1);
    d[rt<<1]+=d[rt];
    d[rt<<1|1]+=d[rt];
    d[rt]=0;
    return ;
}
void update(int l,int r,int rt) {

    if (l<=t[rt].l&&t[rt].r<=r) {
        t[rt].s+=t[rt].r-t[rt].l+1;
        ++d[rt];
        return ;
    }
    pd(rt);
    int mid = t[rt].l+t[rt].r>>1;
    if (l<=mid) {
        update(l,r,rt<<1);
    }
    if (r>mid) {
        update(l,r,rt<<1|1);
    }
    return ;
}
int query(int rt,int where) {

    if (t[rt].l==t[rt].r) {
        return t[rt].s;
    }
    pd(rt);
    int mid = t[rt].l+t[rt].r>>1;
    if (where<=mid) {
        return query(rt<<1,where);
    }
    if (where>mid) {
        return query(rt<<1|1,where);
    }
}
int main() {

    scanf("%d%d",&n,&m);
    for (int i=0;i<=m;++i) {
        g[i].clear();
    }
    for (int i=1;i<=n;++i) {
        scanf("%d%d",&s[i].l,&s[i].r);
        int len=s[i].r-s[i].l+1;
        g[len].pb(i);
    }
    build(1,m,1);
    for(int i=1;i<=m;++i) {
        int ans=0;
        for (int j=0;j<g[i].size();++j) {
            int &pos=g[i][j];
            update(s[pos].l,s[pos].r,1);
        }
        for (int j=i;j<=m;j+=i) {
            ans+=query(1,j);
        }
        n-=g[i].size();
        printf("%d\n",ans+n);
    }
    return 0;
}


Measured memory_bytes: 14976
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1 << 30;
ll ans = 0;

int main()
{
ll n;
cin >> n;
string s[n] = {};
rep(i, n)
{
    cin >> s[i];
}
ll a=0,b=0,c=0;
rep(i,n){
    if(s[i][0]=='B'&&s[i][(int)(s[i].length())-1]=='A')c++;
    else if(s[i][0]=='B')b++;
    else if(s[i][(int)(s[i].length())-1]=='A')a++;
    rep(j,(int)(s[i].length())){
    if(j!=0&&s[i][j]=='B'&&s[i][j-1]=='A')ans++;
}
}

if(c>0){
    ans+=c-1;
    if(a>0){ans++;a--;}
    if(b>0){ans++;b--;}
}
ans+=min(a,b);

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

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

using namespace std;

const int N = 1e5 + 7, mod = 1e9 + 7;
int n, ans, f[N][2];

char s[N];
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    f[0][1] = 1;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '1') {
            f[i][0] = (3ll * f[i - 1][0] + f[i - 1][1]) % mod;
            f[i][1] = 2ll * f[i - 1][1] % mod;
        }else {
            f[i][0] = 3ll * f[i - 1][0] % mod;
            f[i][1] = f[i - 1][1];
        }
    }
    ans = (f[n][0] + f[n][1]) % mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <map>
#include <ctime>
using namespace std;

int K;
void input()
{
    cin >> K;
}

void solve()
{
    int ten = 10 % K;
    map<int,int> M;
    int before,itr;
    before = itr = 7 % K;
    int cnt = 0;
    while (M[itr] == 0){
        // cout << itr << endl;
        M[itr]++;
        itr = (before * ten + 7) % K;
        before = itr;
        ++cnt;
    }
    if(M[0] != 0) cout << cnt << endl;
    else cout << -1 << endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    // int ti = clock();
    input();
    solve();
    // printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

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

int main() {
  vector<vector<int>> A(3, vector<int>(3));
  rep( i, 0, 3 ) {
    rep( j, 0, 3 ) cin >> A.at(i).at(j);
  }
  int N; cin >> N;
  vector<int> b(N);
  rep( i, 0, N ) cin >> b.at(i);

  vector<vector<bool>> Kekka(3, vector<bool>(3, false));

  rep( i, 0, N ) {
    rep( j, 0, 3 ) {
      rep( k, 0, 3 ) {
        if ( A.at(j).at(k) == b.at(i) ) {
          Kekka.at(j).at(k) = true;
        }
      }
    }
  }

  bool flag = false;
  rep( i, 0, 3 ) {
    if (   Kekka.at(i).at(0) == true
        && Kekka.at(i).at(1) == true
        && Kekka.at(i).at(2) == true ) flag = true;
  }
  rep( i, 0, 3 ) {
    if (   Kekka.at(0).at(i) == true
        && Kekka.at(1).at(i) == true
        && Kekka.at(2).at(i) == true ) flag = true;
  }

  if (   Kekka.at(0).at(0) == true
      && Kekka.at(1).at(1) == true
      && Kekka.at(2).at(2) == true ) flag = true;

  if (   Kekka.at(0).at(2) == true
      && Kekka.at(1).at(1) == true
      && Kekka.at(2).at(0) == true ) flag = true;

  cout << ( flag ? "Yes" : "No" ) << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.util.stream.*;
class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String S;
        int m;
        int h;
        int lens;
        while (true){
            S = input.next();
            if (S.equals("-")){
                break;
            }
            lens = S.length();
            m = input.nextInt();
            for (int i = 0; i < m; i++){
                h = input.nextInt();
                S = S.substring(h,lens) + S.substring(0,h);
            }
            System.out.println(S);
        }
    }
}


Measured memory_bytes: 26392
<?php
list($K) = ints();
$sum = 0;
for($i = 1; $i <= $K; $i++)
for($j = 1; $j <= $K; $j++)
$memo[$i][$j] = $memo[$j][$i] = (int)gmp_gcd($i, $j);

for($i = 1; $i <= $K; $i++)
for($j = 1; $j <= $K; $j++){
    $ij = $memo[$i][$j];
    for($k = 1; $k <= $K; $k++)
        $sum+=$memo[$ij][$k];
}

echo $sum;


function str(){return trim(fgets(STDIN));}
function ints(){return array_map('intval',explode(' ',trim(fgets(STDIN))));}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function o(...$val){
    if(count($val)==1)$val=array_shift($val);
    echo debug_backtrace()[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0)echo "empty array";
        elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
        else{
            echo "array:array\n";
            if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
            else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
        }
    }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

function dfs($current, $from = -1, $d = 0){
  global $G, $distance;
  $distance[$current] = $d;
  foreach($G[$current] as $to){
    if($from != $to){
      dfs($to, $current, $d + 1);
    }
  }
}

function loadTree($N = false){
  if($N === false)$N = $GLOBALS['N'];
  return loadGraph($N, $N-1);
}
function loadGraph($N = false, $M = false, $both = true){
  if($N === false)$N = $GLOBALS['N'];
  if($M === false)$N = $GLOBALS['M'];
  $G = array_fill(1, $N, []);
  for($i = 0; $i < $M; $i++){
    $values = ints();
    if(count($values) == 2){
      list($a, $b) = $values;
      $G[$a][] = $b;
      if($both)$G[$b][] = $a;
    }else{
      list($a, $b, $d) = $values;
      $G[$a][] = [$b, $d];
      if($both)$G[$b][] = [$a, $d];
    }
  }
  return $G;
}


Measured memory_bytes: 18860
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>  
#include<set>
#include<iterator>
#include<list>
#include<utility>
#include<cstdlib>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
#define PI  2*acos(0.0)
#define pb push_back

       
using namespace std;
using ll = long long;
using lli = long long int;
using ld = long double;



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

int a,b;
cin>>a>>b;
for(int i=0;i<max(a,b);i++)
{
	cout<<min(a,b);
}

cout<<"\n";







	
	
	return 0;
	
	
	       /***Israil Hosen
	            Computer Science & Engineering
	         University Of Rajshahi.
	         ***/
	
	
	
}

Measured memory_bytes: 3164
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
 
   int N = sc.nextInt();
   
   int[] a = new int[N];
   for(int i=0;i<N;i++) a[i] = sc.nextInt();
   Arrays.sort(a);
   
   int count =1;
   int tmp =0;
   int ans=0;
   for(int i=1;i<N;i++)
   {
     if(a[i]>N) 
     {
       ans+=N-i;
       break;
     }
     else if(a[i]==a[i-1])
     {
       count++;
     }
     else
     {
       if(count<a[i-1])
       {
         ans+=count;
         count=1;
       }
       else if(count>=a[i-1])
       {
         ans+=count-a[i-1];
         count=1;
       }
     }   
   }
   if(count<a[N-1])
       {
         ans+=count;
         count=1;
       }
       else if(count>=a[N-1])
       {
         ans+=count-a[N-1];
         count=1;
       }
   System.out.println(ans);
 }
}

Measured memory_bytes: 51108
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

double tans(int a,int b,int r){
    double x=double(a);
    double y=double(b);
    double a1=1;
    double b1=-1*y*2;
    double c1=x*x+y*y-r*r;
    double ans1=(-b1-sqrt(b1*b1-4*a1*c1))/2*a1;
    double ans2=(-b1+sqrt(b1*b1-4*a1*c1))/2*a1;
    double ans;
    if(ans1>=0){
        ans=min(ans1,ans2);
    }else{
        ans=ans2;
    }
    return ans;


}

int main() {

    int r,n;
    while(true){
        cin>>r>>n;
        if(r+n==0)break;
        int x[41],x1[41],x2[41];
        rep(i,41){x[i]=0;x1[i]=0;x2[i]=0;}
        rep(i,n){
            int a,b,c;
            cin>>a>>b>>c;
            a+=20;b+=20;
            for(int j=a;j<=b-1;j++){
                x[j]=max(x[j],c);
            }
        }
        for(int i=0;i<41;i++){
           if(i==0){
               x2[i]=x[0];
               x1[i]=x[0];
           }else if(i==40){
               x1[i]=x[39];
               x2[i]=x[39];
           }else{
               x1[i]=x[i-1];
               x2[i]=x[i];
           }
        }

        rep(i,41){
            x1[i]+=r;
            x2[i]+=r;
        }

        double t=INF;
        for(int j=1+20-r;j<20+r;j++){
            //cout<<abs(20-j)<<" "<<x1[j]<<" "<<x2[j]<<endl;
            double t1=tans(abs(20-j),x1[j],r);
            double t2=tans(abs(20-j),x2[j],r);
           // cout<<t1<<t2<<endl;
            t=min({t1,t2,t});
        }

        printf("%.4f\n",t);
    }


    return 0;
}



Measured memory_bytes: 3152
from collections import defaultdict
import math
sieve=[1]*10001
i=2
while i*i<=10001:
    if sieve[i]:
        for j in range(i+i,10001,i):
            sieve[j]=0
        
    i+=1    
lol=[]
for i in range(2,10001):
    if sieve[i]:
        lol.append(i)
mod=10**9+7
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)    
x=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in a:
    k=0

    while lol[k]*lol[k]<=i:
        c=0
        #print("AScasc",i)
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                c+=1
            d[j]=max(c,d[j])    
        k+=1    
    if i>=2:
        c=1
        d[i]=max(c,d[i])
        
y=0
s=d.keys()
#print(s,d)
z=1
for i in s:
    z*=pow(i,d[i])
for i in a:
    y+=((z%mod)*pow(i,mod-2,mod))%mod
print(y%mod)        

Measured memory_bytes: 47084
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
int main() {
 int N;
 cin>>N;
 vector<int>A(N);
 for(int i=0;i<N;i++){
     cin>>A[i];
 }
 for(int i=0;i<N;i++){
     if(A[i]%2==0){if(A[i]%5!=0&&A[i]%3!=0){cout<<"DENIED"<<endl;return 0;}
 }}
 cout<<"APPROVED"<<endl;
 return 0;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MAX 2000000
#define MOD 1000000007
using Graph=vector<vector<int>>;

int main(){
  ll N,M;
  cin>>N>>M;
  vector<ll> A(M);
  ll sum=0;
  for(int i=0;i<M;i++){
    cin>>A.at(i);
    sum+=A.at(i);
  }
  if(sum<=N){
    cout<<N-sum<<endl;
  }else{
    cout<<-1<<endl;
  }

}


Measured memory_bytes: 3708
bignum=1000000000000
dir=[[1,0],[-1,0],[0,1],[0,-1],[0,0]]

def movable(loc,d,H,W):
    if (loc[0]+d[0]>=0 and loc[0]+d[0]<H and loc[1]+d[1]>=0 and loc[1]+d[1]<W):
        return 1
    else:
        return 0
def vecsum(loc,d):
    return [loc[0]+d[0],loc[1]+d[1]]

def decodeghost(cn):
    if cn==5:
        return dir[4]
    if cn==2:
        return dir[0]
    if cn==4:
        return dir[3]
    if cn==6:
        return dir[2]
    if cn==8:
        return dir[1]

while(1):
    H,W=map(int,raw_input().split())
    if H==0:    break
    L=[]
    F=[[bignum for i in range(W)] for j in range(H)]
    Aloc=[0,0]
    Bloc=[0,0]
    for h in range(H):
        L.append(raw_input())
        if 'A' in L[-1]:
            Aloc=[h,L[-1].index('A')]
        if 'B' in L[-1]:
            Bloc=[h,L[-1].index('B')]
    F[Aloc[0]][Aloc[1]]=0
    nf=[Aloc[:]]
    ac=1
    while(len(nf)>0):
        nnf=[]
        for loc in nf:
            for d in dir:
                if movable(loc,d,H,W):
                    v=vecsum(loc,d)
                    if F[v[0]][v[1]]>ac and L[v[0]][v[1]]!='#':
                        F[v[0]][v[1]]=ac
                        nnf.append(v)
        nf=nnf[:]
        ac+=1
    
    cmd=raw_input()
    C=[[[0 for i in range(W)] for j in range(H)] for k in range(len(cmd))]
    cm=0
    ans=1
    while(1):
        if C[cm][Bloc[0]][Bloc[1]]==1 and ans>H*W:
            print 'impossible'
            break
        C[cm][Bloc[0]][Bloc[1]]=1
        cn=int(cmd[cm])
        d=decodeghost(cn)
        if movable(Bloc,d,H,W):
            v=vecsum(Bloc,d)
            Bloc=v[:]
        if F[Bloc[0]][Bloc[1]]<=ans:
            print ans,' '.join([str(b) for b in Bloc])
            break
        cm+=1
        if cm>=len(cmd):
            cm=0
        ans+=1
                

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
ll INF = LLONG_MAX;
 
using vc = vector<char>;
using vi = vector<int>;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N; cin >> N;
    vi arr (N);
    F0R(i, N) cin >> arr[i];

    ll lo = 2; 
    ll hi = 2;
    R0F(i, N) {
        lo = (lo % arr[i] == 0) ? (arr[i] * (lo / arr[i])) : (arr[i] * (1 + lo / arr[i]));
        hi = (arr[i] * (hi / arr[i])) + arr[i] - 1;
    }
    if (lo > hi) 
        cout << -1 << endl;
    else 
        cout << lo << " " << hi << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

ll n, m;
vector<ll> par;
vector<ll> siz;

int root(int x) {
  while (x != par[x]) x = par[x];
  return x;
}

bool merge(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y) return false;
  if (siz[x] < siz[y]) swap(x, y);
  siz[x] += siz[y];
  par[y] = x;
  return true;
}

int main() {
  cin >> n >> m;
  vector<pair<ll, ll>> p(m);
  rep(i, m) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    p[i] = make_pair(a, b);
  }
  par.resize(n);
  siz.resize(n);
  rep(i, n) par[i] = i;
  rep(i, n) siz[i] = 1;
  vector<ll> ans(m);
  ans[m - 1] = n * (n - 1) / 2;
  for (int i = m - 1; i >= 1; --i) {
    if (root(p[i].first) == root(p[i].second)) {
      ans[i - 1] = ans[i];
    } else {
      ans[i - 1] = ans[i] - siz[root(p[i].first)] * siz[root(p[i].second)];
      merge(p[i].first, p[i].second);
    }
  }
  rep(i, m) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 5248
#include<iostream>

using namespace std;

int main(){
    int A, B, C;
    int X;
    cin >> A >> B >> C;
    cin >> X;

    int ans = 0;
	for (int a = 0; a <= A; a++) {
		for (int b = 0; b <= B; b++) {
			for (int c = 0; c <= C; c++) {
				if (a * 500 + b * 100 + c * 50 == X) ans++;
			}
		}
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define sz(v) (int)(v).size()
using namespace std;
using P = pair<int, int>;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b + c >= 22)	cout << "bust" << '\n';
	else cout << "win" << '\n';
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {
    int64_t x;
    cin >> x;

    int64_t ans = x / 11 * 2;
    x %= 11;
    if(x > 0) ++ans;
    if(x > 6) ++ans;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 100005

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int a,b; cin>>a>>b;
	if(a>b) swap(a,b);
	
	forn(i,0,b) cout<<a;
	cout<<'\n';
	
	return 0;
}


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

int main(){
    int N,A,B,C,D;
    string str;
    bool check2=0,check3=0;

    cin >> N >> A >> B >> C >> D;
    cin >> str;

    int i;

    for(i = A-1; i < C-1; i++){
        if((str[i] == '#')&&(str[i+1] == '#')){
            check2 = 1;
            break;
        }
    }
    for(i = B-1; i < D-1; i++){
        if((str[i] == '#')&&(str[i+1] == '#')){
            check2 = 1;
            break;
        }
    }
  if(C>D){
    for(i = B-1; i < D; i++){
        if((str[i-1] == '.')&&(str[i] == '.')&&(str[i+1] == '.')){
            check3 = 1;
            break;
        }
    }
  }
    if(check2){
        cout << "No";
    } else if(C < D){
        cout << "Yes";
    } else if(check3){
        cout << "Yes";
    } else {
        cout << "No";
    }


    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

typedef vector<int> vi;

bool tarjan(vi e[], int x, int p[], bool st[], int disc[], int &dn, vi &t) {
    int dmax = -1, dmaxp = -1;
    for (int y : e[x]) {
        if (st[y] && disc[y] > dmax) {
            dmax = disc[y];
            dmaxp = y;
        }
    }

    disc[x] = dn++;
    st[x] = true;

    if (dmaxp != -1) {
        int y = dmaxp;
        while (y != x) {
            t.push_back(y);

            int dmax = -1, dmaxz = -1;
            for (int z : e[y]) {
                if (st[z] && disc[z] > dmax) {
                    dmax = disc[z];
                    dmaxz = z;
                }
            }
            y = dmaxz;
        }
        t.push_back(x);
        return true;
    }

    for (int y : e[x]) {
        if (p[y] != -2) {
            continue;
        }
        p[y] = x;
        bool f = tarjan(e, y, p, st, disc, dn, t);
        if (f) {
            return true;
        }
    }

    st[x] = false;
    return false;
}

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vi e[n];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        e[a].push_back(b);
    }

    int p[n];
    fill(p, p+n, -2);
    bool st[n];
    memset(st, false, sizeof(st));
    int disc[n];
    fill(disc, disc+n, -1);
    int dn = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] == -2) {
            p[i] = -1;
            vi t;
            if (tarjan(e, i, p, st, disc, dn, t)) {
                cout << t.size() << endl;
                for (int x : t) {
                    cout << x + 1 << endl;
                }
                return 0;
            }
        }
    }

    cout << -1 << endl;

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  int total = 0;

  for (int i = 0; i < N; i++) {
    int l,r;
    
    cin >> l >> r;
    
    total += (r - l + 1);
  }
  
  cout << total << endl;
  
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <array>
#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>
#include <tuple>
#include <utility>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int res = n + m;
  res = max(res, n - m);
  res = max(res, n * m);
  cout << res << '\n';
  return 0;
}



Measured memory_bytes: 256