akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 1; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;

int gcd(int a, int b) {   //ユークリッドの互除法
    if (b == 0)
        return a;

    return gcd(b, a % b);
}

int main(){
    int K ;
    cin >> K;
    int ans = 0;
    for (int i = 1; i <= K; ++i) {
        for (int j = 1; j <= K; ++j) {
            for (int k = 1; k <= K; ++k) {
                ans += gcd(gcd(i, j), k);  //gcd(i, j, k) = gcd(gcd(i, j), k)
            }
        }
    }

    cout << ans <<endl;

    return 0;
}

Measured memory_bytes: 3624
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<locale.h>
#include<math.h>
#include<set>
#include<stack>
#include<queue>
using namespace std;
int main()
{
 int n,wc=0;
 string c;
 scanf("%d",&n);
 cin >> c;
 for(int i=0;i<n;i++)
 {
	if(c[i]=='W'){wc++;}
 }
 int ans=0;
 for(int i=n-1;i>(n-1-wc);i--)
 {
	if(c[i]=='R'){ans++;}
 }
 printf("%d",ans);
}

Measured memory_bytes: 3924
#include <stdio.h>
#include <stdlib.h>
int main(void){
	int i;
	int N,x;
	if(scanf("%d %d", &N, &x)<2){
		exit(1);
	}
	int a[N];
	for (i=0; i<N; i++){
		if(scanf("%d",&a[i])<1){
			exit(1);
		}
	}
	long count;
	count = 0;
	if(a[0]+a[1]>x){
		count += (a[0]+a[1]-x);
		if(a[0]<=x){
			a[1]= x-a[0];
		}
		else{
			a[1]=0;
			a[0]=x;
		}
	}			
	for (i=1; i<N-1; i++){
		if (a[i]+a[i+1]>x){
			count += (a[i]+a[i+1]-x);
			a[i+1]=x-a[i];

		}
	}
	printf("%ld",count);
	
	
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>

using namespace std;

#define ll long long
#define ld long double
#define v vector

#define rep(i, n)      for (int i = 0; i < (int)(n); ++i)
#define rep3(i, m, n)  for (int i = (m); i < (int)(n); ++i)
#define rrep(i, n)     for (int i = (int)(n)-1; i >= 0; --i)
#define rrep3(i, m, n) for (int i = (int)(n)-1; i >= (m); --i)
#define all(x) x.begin(), x.end()
#define rall(x) x.end(x), x.begin()

#define endl '\n'
const string YES = "YES";
const string NO = "NO";

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

bool solve(ll A, ll V, ll B, ll W, ll T) {
  if (A == B) return true;
  if (!(A < B)) {
      ll tmp = A;
      A = B;
      B = tmp;
    }
  B += W*T;
  A += V*T;
  if (A < B) return false;
  else return true;
}

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

    ll A, V, B, W, T;
    cin >> A >> V >> B >> W >> T;

    auto ans = solve(A, V, B, W, T);
    cout << (ans ? YES : NO) << endl;

    return 0;
}


Measured memory_bytes: 3052
// * Act locally, think globally.

#include <bits/stdc++.h>

using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

signed main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while (a > 0 && c > 0)
    {
        c -= b;
        if (c <= 0)
        {
            cout << "Yes";
            return 0;
        }
        a -= d;
        if (a <= 0)
        {
            cout << "No";
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3584
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

n, m = inp
s = gets.chomp
ans = []
ind = n

while true
  f = false
  ((ind-m)..(ind-1)).each.with_index do |i,step|
    next if i < 0
    if s[i] == "0"
      ans.push(m-step)
      ind = i
      f = true
      break
    end
  end
  unless f
    puts -1
    exit
  end
  break if ind == 0
end
puts ans.reverse.join(" ")

Measured memory_bytes: 4604
#include<cstdio>
#include<utility>

#define	mp	make_pair

using namespace std;

typedef	pair<int,int>	pii;

pii operator+(pii &p,pii &q){ return mp(p.first+q.first,p.second+q.second); }
pii operator-(pii &p,pii &q){ return mp(p.first-q.first,p.second-q.second); }

void rot(pii *p,int m){
	for(int i=0;i<m;i++)	p[i]=mp(-p[i].second,p[i].first);
}

bool equal(pii *p1,pii *p2,int m){
	for(int i=0;i<4;i++){

		pii shift=p1[0]-p2[0];
		bool ok=true;
		for(int k=0;k<m;k++)	if(p1[k]!=p2[k]+shift){ ok=false; break; }
		if(ok)	return true;

		shift=p1[0]-p2[m-1];
		ok=true;
		for(int k=0;k<m;k++)	if(p1[k]!=p2[m-k-1]+shift){ ok=false; break; }
		if(ok)	return true;

		rot(p2,m);
	}
	return false;
}

int main(){
	for(int n;scanf("%d",&n),n;){
		pii org[10];
		int m;	scanf("%d",&m);
		for(int i=0;i<m;i++){
			int x,y;	scanf("%d%d",&x,&y);
			org[i]=mp(y,x);
		}

		for(int k=1;k<=n;k++){
			pii poly[10];
			int mm;	scanf("%d",&mm);
			for(int i=0;i<mm;i++){
				int x,y;	scanf("%d%d",&x,&y);
				poly[i]=mp(y,x);
			}
			if(m==mm && equal(org,poly,m))	printf("%d\n",k);
		}

		puts("+++++");
	}

	return 0;
}

Measured memory_bytes: 0
n = int(input())
t = [int(input()) for i in range(n)]

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

ans = 1
for i in t:
    ans = lcm(ans, i)

print(ans)


Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(void){
    
    //変数：店舗 A の売上個数「s1 と s2」と置く
    int s1, s2;
    
    while(cin >> s1 >> s2){

        //条件：店舗 A の売上個数「s1 と s2」が「 0 と 0 」のとき break する
        if(s1 == 0 && s2 == 0) break;
        
        //代入：最大売上個数を「 max = s1 + s2 」と最大売上店舗「 store = 'A' 」と代入して置く
        int max = s1 + s2;
        char store = 'A';
        
        //繰返し：店舗 B ～  店舗 E の売上個数「s1 と s2」を入力するための繰返し
        for(int i = 1; i <= 4; i++){
            cin >> s1 >> s2;
            
            //条件：最大売上個数を求めるために比較する  ➡   最大個数を入れ替え  ＋   店舗に１加えBCDEへと変化させていく
            if(max < s1 + s2) max = s1 + s2, store = 'A' + i;
        }
        
        cout << store << " " << max << endl;
    }
}



Measured memory_bytes: 2992
s=input()
for i in range(8):
    ans=s[0]
    cnt=int(s[0])
    for j in range(3):
        if (i>>j) & 1:
            ans+="+"+s[j+1]
            cnt+=int(s[j+1])
        else:
            ans+="-"+s[j+1]
            cnt-=int(s[j+1])
    if cnt==7:
        print(ans+"=7")
        exit()



Measured memory_bytes: 3060
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
# Aの累積和
a_sum = [0]
for i in range(n):
    a_sum.append(a_sum[i] + a[i])
# Bの累積和
b_sum = [0]
for i in range(m):
    b_sum.append(b_sum[i] + b[i])
b_sum.append(10**20)
ans = 0
# Aを固定する
for i in range(n+1):
    t = a_sum[i]
    l = 0
    r = len(b_sum)
    # Bのうち何冊目まで読めるか二分探索する
    while l+1<r:
        # c:探索範囲の中央
        c = (l + r) // 2
        # 中央がK以下の場合は、求めたい位置が右にあるので
        # 探索範囲の左端を中央にする
        if t+b_sum[c]<=k:
            l = c
        # 中央がKよりも大きい場合は、求めたい位置が左にあるので
        # 探索範囲の右端を中央にする
        else:
            r = c
    # 合計がKを超えないか確認する
    if a_sum[i]+b_sum[l]<=k:
        ans = max(ans,i+l)
print(ans)

Measured memory_bytes: 47460
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
    ll n=3,c=0;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    if(a[2]-a[0]==0)
    {
        cout<<0<<endl;
        return 0;
    }
    if(a[2]-a[0]>=2)
    {
        ll temp=(a[2]-a[0])/2;
        a[0]+=(temp*2);
        c+=temp;
    }
    if(a[0]-a[1]>=2)
    {
        ll temp=(a[0]-a[1])/2;
        a[1]+=(temp*2);
        c+=temp;
    }
    sort(a,a+n);
    if(a[2]-a[0]>=2)
    {
        ll temp=(a[2]-a[0])/2;
        a[0]+=(temp*2);
        c+=temp;
    }
    sort(a,a+n);
    if(a[0]==a[1]&&a[2]-a[1]==1)
    {
        c+=1;
    }
    else if(a[1]==a[2]&&a[1]-a[0]==1)
    {
        c+=2;
    }
    cout<<c<<endl;
    

  //cerr<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    


}
return 0;
}

Measured memory_bytes: 256
//

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

ll dp[110][100010];

int main() {
    int N, W;
    cin >> N >> W;

    ll weight[N], value[N];
    for (int i = 0; i < N; ++i) cin >> weight[i] >> value[i];

    for (int i = 0; i < 110; ++i) {
        for (int j = 0; j < 100010; ++j) {
            dp[i][j] = 0;
        }
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= W; ++j) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (j >= weight[i - 1]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= 100010; ++i) {
        ans = max(ans, dp[N][i]);
    }

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

Measured memory_bytes: 86144
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define pill pair<int, ll> 
#define pii pair<int, int>
#define plli pair<ll, int>
#define piii pair<pii, int>
#define pll pair<ll,ll>
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define SZ(x) x.size()
#define REP(x,_cnt) for (int x=0; x<(_cnt); x++)
#define RREP(x,_cnt) for (int x=(_cnt)-1; x>=0; x--)
#define FOR(i, _b, _e) for (int i=_b; i<_e; i++)
#define MXTO(x,_n) x=max(x,(__typeof(x))(_n))
#define MNTO(x,_n) x=min(x,(__typeof(x))(_n))
#define f first
#define s second

#define debug(args...) { string _s = #args; replace(ALL(_s), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename Tem1, typename... Args>
void err(istream_iterator<string> it, Tem1 a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

bool big_cmp(int a, int b) {return a>b;}


/* Code Starts Here --------- */

const ll mod = 1e9+7;
const ll inf = 1ll<<60;
const int maxn = 10;



int main(){
    vector<int> a(26);
    int n; cin>>n;
    REP(i,n) {
    	char c; cin>>c; a[c-'a']++;
    }
    ll re = 1;
    REP(i,26){
    	(re *= (a[i]+1)) %= mod;
    }
    cout<<(re+mod-1)%mod<<'\n';
}

Measured memory_bytes: 256
/*
C++ ???????????????????????????????????¬??????
??????AOJ-ITP1??????????????????
*/
#define _USE_MATH_DEFINES

#include <iostream> // ?¨??????\??????
#include <fstream>  // ??????????????\??????
#include <string>   // ???????????¢???
#include <vector>   // ???????????????
#include <cmath>    // ??°??????
#include <iomanip>  // stream???????????¢???
#include <algorithm>// max??¢??°??????

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;        // ????´???°????????????????????????
using std::fixed;         // ???????????????????¨???????????????????????????????
using std::setprecision;  // ?????°????°???°?????\???????????°????????????????????¨????????\???

int main() {
	int Debt = 100000;
	int a;
	int b;
	cin >> a;
	for (size_t i = 0; i < a; i++)
	{
		// ?????±?????????????¨??????????
		Debt = Debt*1.05;
		// ????????????3???????¨??????????
		b = Debt % 1000;
		if (b > 0) {
			Debt += 1000;
		}
		// ????????????????????????
		Debt = Debt - b;
	}
	cout << Debt << endl;
	return 0;
}

Measured memory_bytes: 3072
program abc125c
  implicit none
  integer(8) n, i
  integer(8), dimension(:), allocatable :: a, lgcd, rgcd
  read *, n
  allocate(a(n), lgcd(n + 2), rgcd(n + 2))
  read *, a
  lgcd = 0
  rgcd = 0
  do i = 1, n
     lgcd(i + 2) = gcd(lgcd(i + 1), a(i))
     rgcd(n - i + 1) = gcd(rgcd(n - i + 2), a(n - i + 1))
  end do
  print *, maxval(gcd(lgcd, rgcd))
contains
  elemental function gcd(a, b) result(r)
    integer(8), intent(in) :: a, b
    integer(8) r, t, n
    n = a
    r = b
    do while (n /= 0)
       t = n
       n = mod(r, n)
       r = t
    end do
  end function gcd
end program abc125c


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

using namespace std;

int main(void)
{
	vector<int>list;

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		list.push_back(a);
	}

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

	int size = list.size() - 1;

	int alice = 0, bob = 0;
	int turn = 0;

	for (int i = size; i >= 0; i--)
	{
		if (turn == 0)
		{
			alice += list[i];
		}
		else
		{
			bob += list[i];
		}
		turn ^= 1;
	}

	cout << alice - bob << endl;

	return 0;
}

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

#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;
typedef pair<ll, ll> P;

int main()
{
    int N, M;
    cin >> N >> M;

    vector<P> price(N);
    rep(i, N) {
        cin >> price[i].first >> price[i].second;
    }

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

    ll ans = 0;
    rep(i, N) {
        if (M <= 0) {
            break;
        }
        if (M >= price[i].second) {
            ans += (price[i].first * price[i].second);
        }
        else {
            ans += (price[i].first * M);
        }
        M -= price[i].second;
    }

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

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

int main()
{
	map<string, int> sort_str;
	int N;
	string str;
	long long ans = 0;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> str;
		sort(str.begin(), str.end());
		if (sort_str[str] >= 1)ans += sort_str[str];
		sort_str[str] += 1;
	}

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

Measured memory_bytes: 11136
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	if(n<=m)
	{
		for(int i=1;i<=m;i++)
			cout<<n;
		cout<<endl;
	}
	else
	{
		for(int i=1;i<=n;i++)
			cout<<m;
		cout<<endl;
	}
	return 0;
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){} //初期化指定子
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator++() {
      if ((x++) >= mod) x-= mod;
      return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator--() {
      if ((x += mod-1) >= mod) x-= mod;
      return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int p[100010]; //各人数についてあり得る色の種類
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int kind = 0;
    rep(i,n) if(a[i]==0) kind++;
    if(kind>3){
        cout << 0 << endl;
        return 0;
    }
    p[0] = kind;
    mint ans = 1;
    if(kind==1||kind==2) ans*=3;
    rep(i,n){
        ans *= p[a[i]];
        p[a[i]]--;
        p[a[i]+1]++;
    }
    cout << ans.x << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
  int n,a[1000000],cnt=0,m=0,g[1000000];
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=1;i<=n;i=3*i+1)g[m]=i,m++;
  for(int i=m-1;i>=0;i--){
    for(int j=g[i];j<n;j++){
      int v=a[j],k=j-g[i];
      while(k>=0&&a[k]>v){
    a[k+g[i]]=a[k];
    k=k-g[i];
    cnt++;
      }
      a[k+g[i]]=v;
    }
  }
  cout<<m<<endl;
  for(int i=m-1;i>=0;i--){
    cout<<g[i];
    i==0?cout<<endl:cout<<" ";
  }
  cout<<cnt<<endl;
  for(int i=0;i<n;i++)cout<<a[i]<<endl;
  return 0;
}


Measured memory_bytes: 6916
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>

using namespace std;

int main(){

    int N, T;
    cin >> N >> T;

    vector<int> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    int maxValue = A[N - 1];
    int maxDiff = 0;
    for(int i = N - 2; i >= 0; i--){
        int diff = maxValue - A[i];
        maxDiff = max(maxDiff, diff);
        maxValue = max(maxValue, A[i]);
    }

    int ans = 0;
    maxValue = A[N - 1];
    for(int i = N - 2; i >= 0; i--){
        int diff = maxValue - A[i];
        if(diff == maxDiff){
            ans++;
        }
        maxValue = max(maxValue, A[i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std ;
#define ll  long long 
#define dl long double
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second


int main ()
{
   
    ll a;
    cin >>a ;
    cout<<a+(a*a)+(a*a*a)<<endl;

	return 0;

}

Measured memory_bytes: 3544
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace template
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }
 
        public void Solve(ConsoleInput cin)
        {
            Console.WriteLine(cin.ReadLine.Count(x => x == '1'));
        }
    }
 
    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) 
                {
                    return inputStream.Dequeue();
                }
 
                string[] tmp = _stream.ReadLine().Split(_separator);
                
                for (int i = 0; i < tmp.Length; ++i)
                {
                    inputStream.Enqueue(tmp[i]);
                }
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 11220
//
//  main.cpp
//  AT
//
//  Created by 黄道煜 on 2018/8/11.
//  Copyright © 2018年 黄道煜. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#define LL long long
using namespace std;

int n, vis[100000];

int main()
{
    scanf("%d", &n);
    for(int i=0; i<=25; i++)
        for(int j=0; j<=25; j++) vis[i*4+j*7]=1;
    if(vis[n]) printf("Yes\n");
    else printf("No\n");
                      }


Measured memory_bytes: 256
# coding: utf-8

class Proc:
    def __init__(self):
        n = int(input().rstrip())
        self.stairs = [int(i) for i in input().rstrip().split(" ")]

    def get_ans(self):
        for i in range(len(self.stairs)):
            if i == 0:
                self.stairs[i] -= 1
            else:
                if self.stairs[i] < self.stairs[i - 1]:
                    return False
                elif self.stairs[i] > self.stairs[i - 1]:
                    self.stairs[i] -= 1
        return True


print("Yes" if Proc().get_ans() else "No")


Measured memory_bytes: 14484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_size=100000;//количество факториалов, которых посчитает прога
int n;
int main() {
	ios_base::sync_with_stdio(false);
    ll n,h,w;
    cin>>n>>h>>w;
    cout<<(n-h+1)*(n-w+1);
	return 0;
}

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

int main(){

	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    if(s == "ARC"){
    	cout << "ABC\n";
    }
    else{
    	cout << "ARC\n";
    }
    

	return 0;
}

Measured memory_bytes: 3652
# coding: utf-8
# Your code here!

COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0

EPS = 0.0000000001

class Point:
    
    global EPS
    
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y
        
        
    def __add__(a, b):
        s = a.x + b.x
        t = a.y + b.y
        return Point(s, t)
        
    def __sub__(a, b):
        s = a.x - b.x
        t = a.y - b.y
        return Point(s, t)
            
    def __mul__(self, a):
        s = a * self.x
        t = a * self.y
        return Point(s, t)
        
    def __truediv__(self, a):
        s = self.x / a
        t = self.y / a
        return Point(s, t)
            
            
            
            
    def norm(self):
        return self.x * self.x + self.y * self.y
        
    def abs(self):
        return self.norm() ** 0.5
            
    
            
            
    def __eq__(self, other):
        return abs(self.x - other.y) < self.EPS and abs(self.y - other.y) < self.EPS
            
            
            
    def dot(self, b):
        return self.x * b.x + self.y * b.y
        
    def cross(self, b):
        return self.x * b.y - self.y * b.x
    
    
class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2


def ccw(p0, p1, p2):
    a = p1-p0
    b = p2-p0
    
    if a.cross(b) > 0:
        return COUNTER_CLOCKWISE
    elif a.cross(b) <0:
        return CLOCKWISE
    elif a.dot(b) < 0:
        return ONLINE_BACK
    elif a.abs() < b.abs():
        return ONLINE_FRONT
    else:
        return ON_SEGMENT

def intersect(p1, p2, p3, p4):
    return ccw(p1, p2, p3) *ccw(p1, p2, p4) <=0 and ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0

def intersectS(s1, s2):
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2)



        
n = int(input())
for i in range(n):
    nums=list(map(int,input().split()))
    p1 = Point(nums[0], nums[1])
    p2 = Point(nums[2], nums[3])
    p3 = Point(nums[4], nums[5])
    p4 = Point(nums[6], nums[7])
    s1 = Segment(p1, p2)
    s2 = Segment(p3, p4)
    if intersectS(s1, s2):
        print(1)
    else:
        print(0)





Measured memory_bytes: 5692
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define loop(k) rep(author_is_masa,k)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const long long INF = 1e18+10;

/*--------------------------------------------------------------------*/

signed main(){
	int n;cin>>n;
	int k;cin>>k;
	vi a(n);
	rep(i,n)cin>>a[i];

	int ok=1e9;
	int ng=0;
	int mid;

	while(abs(ok-ng)>1){
		mid=(ok+ng)/2;

		// cout<<"mid="<<mid<<endl;
		int cnt=0;
		rep(i,n){
			cnt+=(a[i]+mid-1)/mid-1;
		}
		if(cnt<=k) ok=mid;
		else ng=mid;

	}

	cout<<ok<<endl;
	return 0;
}



Measured memory_bytes: 4752
#include<iostream>
#include<bits/stdc++.h>
#include<climits>

#define forn(x,n,s) for(int i = x; i < n; i += s )
#define forr(x,n,s) for(int i = x; i>=n; i -= s)

using namespace std;

void go(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  #ifndef ONLINE_JUDGE
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
  #endif
}

int main(){
    go();

    // code here
    int n;cin>>n;
    if(n%1000==0) cout<<0;
    else {
        cout<<(1000 - (n%1000));
    }
   

}






Measured memory_bytes: 3612
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;


int main()
{
	char s[1010];
	scanf("%s", s);
	int n = strlen(s);
	if (s[n - 1] == 's') {
		printf("%ses\n", s);
	} else {
		printf("%ss\n", s);
	}
	
	return 0;
}




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

int main() {
	// your code goes here
	int n,i,a[30],b[30],c[30],ans=0;
	cin >> n;
	for(i=1;i<=n;i++) cin >> a[i];
	for(i=1;i<=n;i++) cin >> b[i];
	for(i=1;i<n;i++) cin >> c[i];
	for(i=1;i<=n;i++){
		ans+=b[i];
		if(i>=2&&a[i]==a[i-1]+1){
			ans+=c[a[i-1]];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
def count_up(idx_list, lv_list):
#  print(idx_list, "の組み合わせのカウントアップ")
  new_lv_list = []
  for j in range(M):
    each_total_lv = 0
    for i in idx_list:
      each_total_lv += lv_list[i][j]
#      print(each_total_lv)
      if(each_total_lv >= X):
#        print(j, "番地の能力は達成")
        break
    if(each_total_lv < X):
#      print(idx_list, "だと未達成。次")
      return -1
  
  price = 0;
  for a in idx_list:
    price += prices[a]
  
#  print("idx_list=", idx_list, "金額は", price)
  
  return price
    
  

from itertools import combinations

N,M,X = map(int, input().split(' '))

prices = []
lv_ups = []
max_price = 0

# i = 0から
for i in range(N):
  tmp = tuple(map(int, input().split(' ')))
  max_price += tmp[0]
  prices.append(tmp[0])
  lv_ups.append(tmp[1:len(tmp)])

#print("最大金額=", max_price)

all_read = []
complete = True
for j in range(M):
    each_total_lv = 0
    for i in range(len(lv_ups)):
      each_total_lv += lv_ups[i][j]
    
    if (each_total_lv < X):
      complete = False
    all_read.append(each_total_lv)
    
    
# 判定
if(complete):
  for z in reversed(range(1, N)):
    comb = combinations(range(N), z)
    for e in comb:
      counted_price = count_up(e, lv_ups)
      if(counted_price > 0 and max_price > counted_price):
        max_price = counted_price
  
  print(max_price)
  
else:
  print(-1)

Measured memory_bytes: 9148
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i = 0;i < n; i++)
#define REP(i,n) for(int i = 1;i <= n; i++)
// ----GCC ONLY---- //
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// ----        ---- //
#define ll long long
#define MOD 10000007
#define PB push_back
 
using namespace std;

int main(){

    ll a,b;
    cin >> a >> b;

    for(int i = 1;i <= b;i++){

        if(a*i % b == 0){
            cout << a*i << "\n";

            break;
        }
    }

}


Measured memory_bytes: 256
#include <stdio.h>
 
int main(void)
{
    int n,m,i,j;
    int a[100][100]={0};
    int b[100]={0};
    int c[100]={0};
     
    scanf("%d %d", &n, &m);
     
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++)
            scanf("%d", &a[i][j]);
    }
    for(j=0; j<m; j++)
        scanf("%d", &b[j]);
     
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++)
            c[i]+=a[i][j]*b[j];
        printf("%d\n", c[i]);
    }
     
    return 0;
}
 


Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int INF (1<<30);
int N, M, Q;
int ans = 0;

int dfs(int idx, int val, vector<int> &A, vector<vector<int>> &x) {
  A[idx] = val;
  if (idx == N) {
       // rep(i, N) cout << A[i];
       // cout << endl;
    int sum = 0;
    rep(i, Q) {
      if (A[x[1][i]-1]-A[x[0][i]-1] == x[2][i]) {
        sum += x[3][i];
      }
    }
    ans = max(ans, sum);
  }
  else {
    for (int i = val; i <= M; i++) {
      dfs(idx+1, i, A, x);
    }
  }
  
  return 0;
}

int main() {
  //int N, M, Q;
  cin >> N >> M >> Q;
  vector<vector<int>> x(4, vector<int>(Q));
  rep(i, Q) {
    cin >> x[0][i] >> x[1][i] >> x[2][i] >> x[3][i];
  }


  vector<int> A(N+1, 1);


  for (int i = 1; i <= M; i++) {
    A[0] = i;
    for (int j = i; j <= M; j++)  dfs(1, j, A, x);
  }

  cout << ans << endl;


  return 0;
}


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



int main(){
	string s;
	cin>>s;
	if(s=="Sunny"){
		cout<<"Cloudy"<<endl;
	}
	else if(s=="Cloudy"){
		cout<<"Rainy"<<endl;
	}
	else if(s=="Rainy"){
		cout<<"Sunny"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ABC043C{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            var N = sr.Next<int>();
            var A = sr.Next<int>(N);

            var res = int.MaxValue;
            for(var i = -100; i <= 100; i++){
                res = Math.Min(res, A.Sum(a => (a - i) * (a - i)));
            }

            Console.WriteLine(res);
            //---------------------------------
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = Console.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }

        public T[][] Next<T>(int y, int x){
            var ret = new T[y][];
            for(var i = 0; i < y; ++i) ret[i] = Next<T>(x);
            return ret;
        }
    }
}

Measured memory_bytes: 3160
#include<stdio.h>
int main(void){
    int a,b,i,tmp;
    
    for(i=0;;i++){
        scanf("%d %d",&a,&b);
        if(a==0 && b==0) break;
        if(a>b){
            tmp=a; a=b; b=tmp;
        }
        printf("%d %d\n",a,b);
        
    }
    return 0;
}


Measured memory_bytes: 2028
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		ArrayList<Integer> one = nextIntArray();
		int H = one.get(0);
		int W = one.get(1);
		String[] all = new String[W + 2];
		Arrays.fill(all, "#");
		myout(myconv(all, 0));
		for(int i = 0; i < H; i++){
			String s = "#" + next() + "#";
			myout(s);
		}
		myout(myconv(all, 0));
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 25392
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i <= n; i++) 

int main() {
    int N, a[220000];
    cin >> N;
    rep(i,N) cin >> a[i];
    int hakai = 0;
    int target = 1;
    int ans = 0;
    rep(i,N) {
        if (a[i] == target) {
            ans += hakai;
            hakai = 0;
            ++target;
        } else {
            ++hakai;
            if (hakai == N) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    ans += hakai;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define ces(d) cout<<" "<<endl;

int main() {

int N,n;
cin>>N>>n;
ce(N-n+1);




}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const int N=100005;
typedef long long ll;
int n;
char c[N];
ll l,sg;
struct tree{
	int ch[N][2],xb;
	inline void ins(char*c){
		int v=0;
		for(int i=0;c[i];++i){
			int u=c[i]-'0';
			if(!ch[v][u])ch[v][u]=++xb;
			v=ch[v][u];
		}
	}
	void dfs(int x){
		--l;
		if(ch[x][0])dfs(ch[x][0]);
			else if(ch[x][1])sg^=l&-l;
		if(ch[x][1])dfs(ch[x][1]);
			else if(ch[x][0])sg^=l&-l;
		++l;
	}
}t;
int main(){
	scanf("%d%lld",&n,&l);++l;
	while(n--){
		scanf("%s",c+1);
		t.ins(c+1);
	}
	t.dfs(0);
	return puts(sg?"Alice":"Bob"),0;
}

Measured memory_bytes: 3456
#include<iostream> 
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define c(a) cout<<a<<" ";
main(){c("1407 38");int t=2;r(i,38){c(1);r(j,37){c(t);t++;}}r(i,37){r(j,37){c(i+2)r(l,37)c(37*l+39+(j+i*l)%37)}}}


Measured memory_bytes: 3532
# AOJ 1568: String Conversion
# Python3 2018.7.13 bal4u

cha, chzn = ord('a'), ord('z')+1
S, T = [0]*128, [0]*128
input()
a = input()
for x in a: S[ord(x)] += 1
S = sorted(S[cha:chzn], reverse=True)
a = input()
for x in a: T[ord(x)] += 1
T = sorted(T[cha:chzn], reverse=True)
ans = 0
for i in range(26): ans += abs(S[i]-T[i])
print(ans >> 1)


Measured memory_bytes: 5860
#include <iostream>
#include <set>

using namespace std;

int d[114514];

int main()
{
	int k;
	cin >> k;
	set<pair<int, int>> q;
	q.insert(make_pair(0, 111111));
	while (!q.empty()) {
		int u = q.begin()->second;
		q.erase(q.begin());
		for (int i = 0; i < 10; i++) {
			if (u == 111111 && !i) {
				u = 0;
				continue;
			}
			int v = (u * 10 + i) % k;
			if (d[v] && d[v] <= d[u] + i)
				continue;
			auto it = q.find(make_pair(d[v], v));
			if (it != q.end())
				q.erase(it);
			d[v] = d[u] + i;
			q.insert(make_pair(d[v], v));
		}
	}
	cout << *d << endl;
	return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h> 
using namespace std;
int main() {
	long long n, res = 0, p = 2;
  	cin >> n;
  	if (n % 2) {
		cout << 0 << endl;
      	return 0;
    }
  	while (n / 5 >= p) { // n >= 5 * p
      p *= 5;
      res += n / p;
    }
	cout << res << endl;
	return 0; 
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define vec vector
#define ll long long

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> s;

    UnionFind(int N) : par(N), s(N, 1) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        s[ry] += s[rx];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

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

int main(void)
{
  ll n, m;
  cin >> n >> m;
  vec<pair<ll, ll> > in(m);
  vec<ll> out(m);
  rep(i, m) {
    ll x, y;
    cin >> x >> y;
    x--; y--;
    in[i].first = x;
    in[i].second = y;
  }
  reverse(in.begin(), in.end());
  ll ans = n * (n - 1) / 2;
  out[0] = ans;
  UnionFind uf(n);
  rep(i, m - 1) {
    if (uf.same(in[i].first, in[i].second)) {
      ans -= 0;
    } else {
      ans -= (ll)(uf.size(in[i].first)) * (ll)(uf.size(in[i].second));
      uf.unite(in[i].first, in[i].second);
    }
    out[i + 1] = ans;
  }
  reverse(out.begin(), out.end());
  rep(i, m) cout << out[i] << endl;
  return 0;
}





Measured memory_bytes: 4480
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
  long long x;
  cin >> x;
  long long a,b;
  for(a=-200;a<200;a++){
    for(b=-200;b<200;b++){
      if(a*a*a*a*a-b*b*b*b*b==x) break;
    }
    if(a*a*a*a*a-b*b*b*b*b==x) break;
  }
  cout << a << " " << b << endl;
  return 0;
}

Measured memory_bytes: 3624
n = int(input())
lis = list(map(int, input().split()))

lis.sort()
# print(lis)

ans = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if lis[i]!=lis[j] and lis[j]!=lis[k] and lis[k]!=lis[i] and lis[k] < lis[i]+lis[j]:
                ans += 1
print(ans)

Measured memory_bytes: 9188
#include <stdio.h>

int main() {
	int S;
	scanf("%d",&S);
	int prog[1000000];
	for (int i = 0; i < 1000000; i++) {
		if (i == 0) prog[i] = S;
		if (i > 0) {
			int a = prog[i-1];
			if (a%2 == 0) prog[i] = a/2;
			if (a%2 == 1) prog[i] = 3*a+1;
			for (int j = 0; j < i; j++) {
				if (prog[i] == prog[j]) {
					printf("%d\n",i+1);
					return 0;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 128
// ProblemURL : https://atcoder.jp/contests/abc129/tasks/abc129_b
// ---------------------------------------------
package main

import "fmt"

const inf = 1 << 60

func diff(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}
func chmin(a *int, b int) bool {
	if *a > b {
		*a = b
		return true
	}
	return false
}

func main() {
	var n int
	fmt.Scan(&n)
	w := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&w[i])
	}

	c := make([]int, n+1)
	for i := 0; i < n; i++ {
		c[i+1] = c[i] + w[i]
	}

	minDiff := inf
	for i := 1; i <= n; i++ {
		sumL := c[i] - c[0]
		sumR := c[n] - c[i]
		chmin(&minDiff, diff(sumL, sumR))
	}
	fmt.Println(minDiff)
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define db double
struct point{
    db x,y;
    point(){}
    point(db x,db y):x(x),y(y){}
    point operator + (point B){ return point(x+B.x,y+B.y); }
    point operator - (point B){ return point(x-B.x,y-B.y); }
    point operator * (db k){ return point(k*x,k*y); }
    db operator * (point B){ return x*B.y-y*B.x; }
    db operator ^ (point B){ return x*B.x+y*B.y; }
    bool operator < (point B){ return (y>0)!=(B.y>0)?y>0:((*this)*B)>0; }
};
db dis(point A,point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); }
struct line{
    point A,B;
    line(){}
    line(point A,point B):A(A),B(B){}
};
point projection(line l,point P){
    point dir=l.B-l.A; P=P-l.A;
    return dir*((P^dir)/(dir.x*dir.x+dir.y*dir.y))+l.A;
}
int main(){
    db x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
    line l(point(x1,y1),point(x2,y2));
    int q; scanf("%d",&q);
    while (q--){
        db x,y; scanf("%lf%lf",&x,&y);
        point proj=projection(l,point(x,y));
        printf("%.9f %.9f\n",proj.x,proj.y);
    }
}



Measured memory_bytes: 3224
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;



int main() {
	string s;
	int k;

	cin >> k >> s;

	if (s.length() <= k) {
		cout << s << endl;
	}
	else {
		cout << s.substr(0, k) << "..." << endl;
	}
}

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

using namespace std;
using ll = long long;

int main()
{
    int n; cin >> n;
    vector<int> a(n), sum(n);
    for(int i = 0; i < n; i++)cin >> a[i];
    sum[n - 1] = a[n - 1];
    for(int i = n - 2; i >= 0; i--)sum[i] = max(sum[i + 1], a[i]);
    //print(sum);

    int ans = -2e9;
    for(int i = 0; i < n - 1; i++) {
        ans = max(ans, sum[i + 1] - a[i]);
    }
    cout << ans << endl;

}


Measured memory_bytes: 4340
/// // // // // // // // // ///
// Author : Kh@ntil S@nghani //
/// // // // // // // // // ///

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define ll long long int
#define ld long double
#define ss second
#define ff first
#define inf LLONG_MAX
#define con continue
#define all(x)  x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define M 1000000007
#define endl '\n'
// if vector isn't soted then it will remove consecutive same elements
#define make_unique(vec) vec.erase(unique(all(vec)), vec.end())
template<class T> ostream& operator<<(ostream& cout,vector<T> V){cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
template <typename T>ostream& operator << (ostream& out, const set <T> &N_A) {out << "{ "; for(const auto &i: N_A) out << i << ", "; return out << "}" << endl;}
template <typename T, typename G>ostream& operator << (ostream& out, const map <T, G> &N_A) {out << "< "; for(const auto &i: N_A) out << i << ", "; return out << ">" << endl;}
template<typename T> inline istream &operator>>(istream &in,vector<T> &N_A){for(auto &x:N_A)in >> x;return in;}
#define MAXN   10000001 


int n;
const int N=100005;
int a[100005];
int cache[N];
int vis[N]={0};
vector<int> graph[N];

// int handle(int x)
// {
//     return (x%MOD + MOD)%MOD;
// }

void dfs(int u)
{
    vis[u]=1;
    for(auto x:graph[u])
    {
        if(!vis[x])
        {
            dfs(x);
        }
    }
}



int main() {
	#ifndef ONLINE_JUDGE
	 freopen("input.txt","r",stdin);
	 freopen("output.txt","w",stdout);
	#endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll _;
	_=1;
	// cin>>_;

	while(_--) 	
	{
		// cout<<fixed<<setprecision(9)<<y<<" "<<x<<endl;
		// cout<<_<<endl;
		int m;
	    cin>>n>>m;
	    for (int i = 0; i < m; ++i)
	    {
	        int u,v;
	        cin>>u>>v;
	        graph[u].push_back(v);
	        graph[v].push_back(u);
	    }
	    int ans = 0;
	    for (int i = 1; i <= n; i++)
	    {
	        if(!vis[i])
	        {
	            ans++;
	            dfs(i);
	        }
	    }
	    cout<<ans-1;

	}
	return 0;
}




Measured memory_bytes: 9968