akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#endif

#define ITER(c)         __typeof__((c).begin())
#define FOREACH(it, c)  for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)        __typeof__((c).rbegin())
#define RFOREACH(it, c) for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)       REPEAT(i, 0, n)
#define REPEAT(i, k, n) for (int i = (k); i < (n); ++i)
#define REVREP(i, n)    for (int i = ((n)-1); i >= 0; --i)
#define FIND(c, n)      std::find((c).begin(), (c).end(), (n));
#define BSEARCH(c, n)   std::binary_search((c).begin(), (c).end(), (n))
#define LLPOW(p1,p2)    ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)      (sizeof(A)/sizeof((A)[0]))
#define MIN(p1,p2)      (((p1)<(p2))?(p1):(p2))
#define MAX(p1,p2)      (((p1)>(p2))?(p1):(p2))
#define CIN_NO_SYNC     do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)       fgets((p), sizeof(p), stdin)
#define CHOMP(p)        do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n' || *_q == '\r') *_q = 0; } while(0)

typedef long long ll;
typedef unsigned long long ull;

#ifdef _DEBUG
#define pf printf
#define pr(n) do { cout << #n " = " << (n) << endl; } while(0)
#else
#define pf(...) /* */
#define pr(...) /* */
#endif

int main(){
    char buf[1024];
    GETSTR(buf);
    CHOMP(buf);
    int len = strlen(buf);
    char *end = buf+len;

    char *p = buf;
    while(p < end){
        char *p1 = strstr(p, "apple");
        char *p2 = strstr(p, "peach");
        if(p1 == NULL) p1 = end;
        if(p2 == NULL) p2 = end;

        if(p1 < p2 && p1 != end){ memcpy(p1, "peach", 5); p = p1 + 5; continue; }
        if(p2 < p1 && p2 != end){ memcpy(p2, "apple", 5); p = p2 + 5; continue; }
        p++;
    }
    puts(buf);

    return 0;
}

Measured memory_bytes: 1100
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}

//INSERT ABOVE HERE
signed main(){
  int n,x,y,z;
  cin>>n>>x>>y>>z;
  using M = Mint<int>;

  const int sz=1<<18;
  vector<M> dp0(sz,0),dp1(sz,0);
  dp0[0]=M(1);

  int ms=sz-1;
  int ok=((((1<<x)|1)<<y)|1)<<z;
  for(int i=0;i<n;i++){
    vector<M> nx0(sz,0),nx1(sz,0);
    for(int b=0;b<sz;b++){
      for(int j=1;j<=10;j++){
        int nb=((b|1)<<j)&ms;
        ((nb&ok)==ok?nx1:nx0)[nb]+=dp0[b];
        nx1[nb]+=dp1[b];
      }
    }
    swap(dp0,nx0);
    swap(dp1,nx1);
  }

  M ans{0};
  for(M x:dp1) ans+=x;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4464
#include <stdio.h>
int p = 0, q[2000000];

int max_num(int x, int y){
    if(q[x]>q[y])
        return x;
    else   
        return y;
}

void insert(int k){
    int i, j, temp;
    p++;
    q[p] = k;
    i = p;
    while(q[i] > q[i/2] && i > 1){
        temp = q[i];
        q[i] = q[i/2];
        q[i/2] = temp;
        i = i/2;
    }
}

int extract(){
    int i, temp, max, a;
    a = q[1];
    q[1] = q[p];
    p--;
    i = 1;
    while(i*2 <= p){
        if(i*2+1<=p)    max = max_num(i*2, i*2+1);
        else    max =i*2;
        if(max_num(max, i)==max){
            temp = q[max];
            q[max] = q[i];
            q[i] = temp;
            i = max;
        }
        else break;
    }
    return a;
}

int main(){
    int i, j, k;
    char A[10];
    while(1){
        scanf("%s",A);
        if(A[0]=='i'){
            scanf("%d",&k);
            insert(k);
        }
        if(A[0]=='e' && A[1]=='x')
            printf("%d\n",extract());
        if(A[0]=='e' && A[1]=='n')  break;
    }
    return 0;
}



Measured memory_bytes: 5592
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
from collections import deque

n=int(input())
G=[0]*n
memo=[0]*n
dis=[0]*n
dis[0]=1
que=deque()
que.append((0,1))

for i in range(n):
    inp=tuple(map(int,input().split()))
    G[inp[0]-1]=inp[2:]

while que:
    vertex,d=que.popleft()
    for v in G[vertex]:
        if not dis[v-1]:
            dis[v-1]=d+1
            que.append((v-1,d+1))
        

for i in range(n):
    print(i+1,dis[i]-1)



Measured memory_bytes: 6028
using System;
using System.Collections.Generic;
class Solve{
    int W;
    int H;
    int[] p;
    int[] q;
    public Solve(){}
    public static int Main(){
        new Solve().Calc();
        return 0;
    }
    void Calc(){
        getinput();
        int[] a = new int[W+H];
        long count = 0;
        for(int i=0;i<W+H;i++){
            a[i] = i;
        }
        Array.Sort(a,(i,j) => compare(i,j));
        {
            int w = 0;
            int h = 0;
            for(int i=W+H-1;i>=0;i--){
                if(a[i] >= W){
                    count += (long)(w+1)*(long)q[a[i]-W];
                    h++;
                }
                else{
                    count += (long)(h+1)*(long)p[a[i]];
                    w++;
                }
            }
        }
        Console.WriteLine(count);
    }
    int compare(int i,int j){
        int a;
        int b;
        if(i >= W){
            a = q[i-W];
        }
        else{
            a = p[i];
        }
        if(j >= W){
            b = q[j-W];
        }
        else{
            b = p[j];
        }
        return a-b;
    }
    void getinput(){
        string[] str = Console.ReadLine().Split(' ');
        W = int.Parse(str[0]);
        H = int.Parse(str[1]);
        p = new int[W];
        q = new int[H];
        for(int i=0;i<W;i++){
            p[i] = int.Parse(Console.ReadLine());
        }
        for(int i=0;i<H;i++){
            q[i] = int.Parse(Console.ReadLine());
        }
    }    
}

Measured memory_bytes: 8408
Program Main

    Implicit None

    Integer, Allocatable :: A(:) 
    Integer              :: i,j,H,N,s,dum
    Logical              :: win

    win = .False.
    H = 0 ; N = 0
    Read(*,*) H,N
    Allocate (A(N)); A(:) = 0.0d0 
    Read(*,*)(A(i),i=1,N)

    Loop:Do i = 1,N
            H = H - A(i)
            If (H <= 0) then
               win = .True.
               Exit Loop
            Endif
         Enddo Loop

    If (win) then
       Write(*,"(a)")"Yes"
    Else
       Write(*,"(a)")"No"
    Endif

    Deallocate(A)

  End Program


Measured memory_bytes: 1152
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [-Q] * N
for a in A:
    ans[a-1] += 1

for i in range(N):
    ans[i] += K
    if ans[i] > 0:
        print('Yes')
    else:
        print('No')


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

int main()
{
	int n; cin>>n;
    int c = 0; int flag = 0;
    while(n--){
        int a, b;
        cin>>a>>b;
        if(a==b) c++;
        else c=0;
        
        if(c==3){
            flag = 1;
            break;
        }
    }
    
    if(flag==1) cout<<"Yes";
    else cout<<"No";
    
    return 0;
}

Measured memory_bytes: 3584
#include<cstdio>
int k,s,ac;
int main(){
	scanf("%d%d",&k,&s);
	ac=0;
	for (int i=0; i<=k; i++)
		for (int j=0; j<=k; j++)
			if (i+j<=s&&s-i-j<=k) ++ac;
	printf("%d\n",ac);
	return 0;
}

Measured memory_bytes: 128
import math

a, b, C = map(int, input().split())
S = a * b * math.sin(math.radians(C)) / 2
L = a + b + (a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(C))) ** 0.5
h = b * math.sin(math.radians(C))

print('%.7f\n%.7f\n%.7f\n' % (S, L, h))

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



int main() {
    int n;
    string s;
    cin >> n >> s;
    
    int cnt = 0;
    for(int i = 0; i < n-2; i++) {
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C')
            cnt++;
    }
    
    cout << cnt << endl;
    
    
    
    return 0;
}


Measured memory_bytes: 3616
#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 fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = 998244353;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}

int a[111111];
ll dp[5111][5111];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	/*
	dp[0][1] = a[0];
	cerr<<a[0]<<'\n';
	ll ans = a[0];
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=i+1;j++)
		{
			dp[i][j] = dp[i-1][j-1]*a[i];
			dp[i][j] += dp[i-1][j]*i;
		}
		ll gd = dp[i][1];
		cerr<<dp[i][1]<<' ';
		for(int j=2;j<=i+1;j++)
		{
			gd=__gcd(gd,dp[i][j]);
			cerr<<dp[i][j]<<' ';
		}
		cerr<<"ANSWER\n";
		ans*=__gcd(i,a[i]);
		cerr<<gd<<' '<<ans<<'\n';
	}
	*/
	ll ans = a[0]%MOD;
	for(int i=1;i<n;i++)
	{
		ans=mult(ans,__gcd(i,a[i]));
	}
	cout<<ans<<'\n';
	//remember 1e9 > MOD!
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
bool b[105];

int main()
{
	int N,K;
	cin >> N >> K;
	rep(i,K)
	{
		int d;
		cin >> d;
		rep(j,d)
		{
			int a;
			cin >> a;
			b[a-1] = true;
		}
	}
	int ans = 0;
	rep(i,N)
	{
		if (!b[i]) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
int all[100],pate[100];
int dfs(int level,int remain){
    if(remain == 0)return 0;
    int ret =0;
    //ban
    if(remain > 0){
        remain--;
    }

    //l-1
    if(remain >= all[level-1]){
        remain -= all[level-1];
        ret += pate[level-1];

    }
    else{
        ret += dfs(level-1,remain);
        remain = 0;
    }

    //pate
    if(remain > 0){
        ret++;
        remain--;
    }

    //l-1
    if(remain >= all[level-1]){
        remain -= all[level-1];
        ret += pate[level-1];

    }
    else{
        ret += dfs(level-1,remain);
        remain = 0;
    }


    //ban
    if(remain > 0){

        remain--;
    }
    return ret;
}
signed main(){
    int n,x;cin >> n >> x;
    pate[0] = 1;
    all[0] = 1;
    rep(i,n+1){
        if(i)all[i] = all[i-1]*2 + 3;
        if(i)pate[i] = pate[i-1]*2 + 1;
        //trace(i,all[i],pate[i]);
    }
    cout << dfs(n,x) << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;

int N,K;
set<int> use;

bool check(int t){
	bool ok = true;
	while(t > 0){
		if(use.count(t%10) == 0){ok = false; break;}
		t /= 10;
	}
	return ok;
}

int main(){
	cin>>N>>K;
	rep(i,10)use.insert(i);
	rep(i,K){
		int t; cin>>t;
		use.erase(t);
	}
	for(int i = N; i<N*100; ++i){
		if(check(i)){cout<<i<<endl; return 0;}
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
 
using namespace std;
 
signed main()
{
    fast;
    int n;
    cin>>n;

    string s;
    cin>>s;

    if ( n % 2 != 0 )
    {
        cout<<"No"<<endl;
    }
    else
    {
        int found = 0;
        for ( int i = 0 ; i < s.length()/2 ; i++ )
        {
            if ( s[i] != s[i+n/2] )
            {
                found = 1;
                break;
            }
        }

        if ( found == 0 )
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
}


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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t n, k;
  std::cin >> n >> k;

  const auto v = n % k;
  std::cout << std::min(v, k - v) << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
int n,k,a[114514],ma[114514],mi[114514],Max,ans;
signed main(){
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	mi[0]=a[0];
	for(int i=1;i<n;i++)mi[i]=min(a[i],mi[i-1]);
	ma[n-1]=a[n-1];
	for(int i=n-2;i>=0;i--)ma[i]=max(a[i],ma[i+1]);
	rep(i,n)Max=max(Max,ma[i]-mi[i]);
	rep(i,n){
		if(ma[i]-mi[i]==Max){
			if(i==0)ans++;
			else if(mi[i]!=mi[i-1])ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 2688
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
dp = [1000000000 for i in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j < 0 : break
        dp[i] = min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
print(dp[n-1])


Measured memory_bytes: 56544
#include<iostream>
#include<vector>

int main(){
    int N,M;
    std::cin>>N>>M;
    std::vector<int> height(N);
    std::vector<std::vector<int> > adjestList(N,std::vector<int>(0));
    for(int i=0;i<N;++i){
        std::cin>>height[i];
    }
    for(int i=0;i<M;++i){
        int A,B;
        std::cin>>A>>B;
        A-=1;
        B-=1;
        adjestList[A].push_back(B);
        adjestList[B].push_back(A);
    }
    int cnt=0;
    for(int i=0;i<N;++i){
        bool isHighest=1;
        for(int j=0;j<adjestList[i].size();++j){
            if(height[i]<=height[adjestList[i][j]]){
                isHighest=0;
                break;
            }
        }
        if(isHighest==1){
            cnt++;
        }
    }
    std::cout<<cnt<<std::endl;
}

Measured memory_bytes: 8616
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int mxn = 100005;

int n, m;

struct data {
	int x, y, w;

	data(int a = 0, int b = 0, int c = 0) : x(a), y(b), w(c) {} ;

	bool operator < (const data &d) const {
		return w < d.w;
	}
} a[mxn], b[mxn], c[mxn << 1];

int fa[mxn];

int find(int u) {
	return u == fa[u] ? u : fa[u] = find(fa[u]);
}

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

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].w), a[i].x = i;
		scanf("%d", &b[i].w), b[i].x = i;
	}

	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);

	for (int i = 1; i < n; ++i) {
		c[m++] = data(a[i].x, a[i + 1].x, a[i + 1].w - a[i].w);
		c[m++] = data(b[i].x, b[i + 1].x, b[i + 1].w - b[i].w);
	}

	sort(c, c + m);

	long long ans = 0;

	for (int i = 1; i <= n; ++i)fa[i] = i;

	for (int i = 0; i < m; ++i) {
		int x = find(c[i].x);
		int y = find(c[i].y);

		if (x != y) {
			ans += c[i].w, fa[x] = y;
		}
	}

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

Measured memory_bytes: 5376
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1<<29;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll dp[100001];

int main() {

	int n,k;
	int h[100001];

	cin>>n>>k;
	for(int i=1; i<n+1; i++){
		cin>>h[i];
	}
	dp[0]=0;
	dp[1]=0;
	dp[2]=labs(h[2]-h[1]);
	for(int i=3; i<n+1; i++){
		dp[i]=dp[i-1]+labs(h[i]-h[i-1]);
		for(int j=2; j<min(i,k+1); j++){
			dp[i]=min(dp[i],dp[i-j]+labs(h[i]-h[i-j]));
		}
	}
	cout<<dp[n]<<endl;

	return 0;
}


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

#define fi first
#define se second
#define endl '\n'
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mp make_pair
#define pb push_back
#define lowbit(a) (a&(-a))
#define sz(x) (int)(x).size()
#define all(x) x.begin(),x.end()
#define mst(a,v) memset(a,v,sizeof(a))
#define debug(x) cout<<#x": "<<x<<'\n';
#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

const int N=100010;
const int mod=1e9+7;
const ld PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

template<typename T>inline void gmax(T &A,T B) {(A<B)&&(A=B);}
template<typename T>inline void gmin(T &A,T B) {(A>B)&&(A=B);}

template <class T>
inline bool re(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}

int dp[N][3],a[N],b[N],c[N];

int main()
{
#ifdef local
    //freopen("in.txt", "r", stdin);
#endif
    IOS;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i]>>b[i]>>c[i];
    mst(dp,-0x3f);
    dp[0][0]=dp[0][1]=dp[0][2]=0;
    for(int i=1; i<=n; i++)
    {
        gmax(dp[i][0],max(dp[i-1][1],dp[i-1][2])+a[i]);
        gmax(dp[i][1],max(dp[i-1][0],dp[i-1][2])+b[i]);
        gmax(dp[i][2],max(dp[i-1][0],dp[i-1][1])+c[i]);
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
    return 0;
}


Measured memory_bytes: 2560
# coding: UTF-8
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    class SegmentTree:
        def __init__(self,n,ide_ele,segfunc):
            self.ide_ele=ide_ele
            self.segfunc=segfunc
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(n):
                self.dat[i+self.num-1]=iter[i]
            for i in range(self.num-2,-1,-1):
                self.dat[i]=self.segfunc(self.dat[2*i+1],self.dat[2*i+2])
        
        def update(self,k,x):
            k+=self.num-1
            self.dat[k]=x
            while k:
                k=(k-1)//2
                self.dat[k]=self.segfunc(self.dat[k*2+1],self.dat[k*2+2])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num-1
            q+=self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1==0:
                    res=self.segfunc(res,self.dat[p])
                if q&1==1:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=p//2
                q=(q-1)//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=list(input())
    Q=int(input())
    seg=[SegmentTree(N,0,lambda x,y:x+y) for _ in range(26)]
    
    S2=[0]*N
    
    for i in range(N):
        S2[i]=ord(S[i])-ord('a')
    
    for i,x in enumerate(S2):
        p=seg[x].query(i,i+1)
        seg[x].update(i,p+1)
    
    for _ in range(Q):
        a,b,c=input().split()
        if a=='1':
            b=int(b)-1
            c=ord(c)-ord('a')
            p=seg[c].query(b,b+1)
            seg[c].update(b,p+1)
            q=seg[S2[b]].query(b,b+1)
            seg[S2[b]].update(b,q-1)
            S2[b]=c
        else:
            b=int(b)-1
            c=int(c)-1
            ans=0
            for i in range(26):
                ans+=bool(seg[i].query(b,c+1))
            print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 288080
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/


string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    cout << S.substr(0, S.length() - 8) << endl;
}

Measured memory_bytes: 256
# ABC 104 C - All Green(my answer for bit)

D, G = map(int, input().split())
p, c = [], []
ans = float('inf')
for _ in range(D):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)

for bit in range(1 << D):  # bitで完答した問題を列挙
    score = 0
    cnt = 0
    comp = set(range(D))
    for i in range(D):  # 完答した問題のscoreを全て加算
        if bit & (1 << i):
            score += p[i] * 100 * (i + 1) + c[i]
            cnt += p[i]
            comp.discard(i)
    if score < G:  # scoreがGに満たなければ中途半端に解答する
        incomp = max(comp)
        # -が2つあるのは//で切り上げで計算するため．-がないと切り下げ
        # https://python.ms/division/#３つのやり方
        incomp_num = min(p[incomp],
                         -(-(G - score) // (100 * (incomp + 1))))  
        score += (incomp + 1) * incomp_num * 100
        cnt += incomp_num
    if score >= G:  # scoreが目標点G以上なら計算回数cntを記録
        ans = min(ans, cnt)
print(ans)

Measured memory_bytes: 9096
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;
	
	char buf[L], *S , *T, c;
	 
	char getchar() {
		if(S == T) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}
	
	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	char B[25], *outs=B+20, *outr=B+20;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;
		
		if(!a)*--outs = '0';
		else 
			while(a)
				*--outs = (a % 10) + 48, a /= 10;
		
		if(x)
			*--outs = x;
		
		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inp_ll;

const int MAXN = 100010;
const int INF = 1000000000;
const int MOD = 1000000007;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

int n, m;
int v[MAXN];
pii p[MAXN];
int F[MAXN];

int main()
{
	
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i)
		v[i] = n+1;
	for (int i = 1; i <= m; ++ i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		v[x] = min(v[x], y);
	}
	m = 0;
	for (int i = 1; i <= n; ++ i)
	{
		if (v[i] == n+1) continue;
		while (m >= 1 && p[m].X >= v[i]) -- m;
		p[++ m] = pii(v[i], i);
	}
	
	F[0] = 0;
	for (int i = 1; i <= m; ++ i)
	{
		int j = lower_bound(p+1, p+m+1, pii(p[i].Y+1, 0))-p-1;
		F[i] = F[j]+1;
	}
	cout << F[m] << endl;
	
	return 0;
}


Measured memory_bytes: 1408
N = int(input())

encryptionStr = input()

excludeStr = ""

result = ""

SHIFT_COUNT = N

for c in encryptionStr :

    if excludeStr.find(c) != -1 :
        result = result + c
        continue


    if ord('a') <= ord(c) <= ord('z') :
        result = result + chr(abs(((ord(c) + SHIFT_COUNT - ord('a')) % 26)) + ord('a'))
    else :
        result = result + chr(abs(((ord(c) + SHIFT_COUNT - ord('A')) % 26)) + ord('A'))

print (result)

Measured memory_bytes: 3064
def point_number_calc(dist, rad)
  d = dist / 100.0
  r = rad / 30.0

  [d.floor + 5 * r.floor, d.ceil + 5 * r.floor,
   d.floor + 5 * r.ceil, d.ceil + 5 * r.ceil].uniq.join(" ")
end

gets.to_i.times do
  dist, rad = gets.chomp.split(" ").map(&:to_i)
  puts point_number_calc(dist, rad)
end

Measured memory_bytes: 8644
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iomanip>

using namespace std;

int main(){
    int n, w;
    while (cin >> n >> w && n|w)
    {
        map<int, int> m;
        int h = 0;
        int bar_num = 0;
        for (int i = 0; i < n; i++)
        {
            int v; cin >> v;
            m[v / w]++;
            h = max(m[v / w], h);
            bar_num = max(bar_num, v / w);
        }
        double res = 0.01;
        for (auto & p : m){
            double col = 1. * (bar_num - p.first) / bar_num;
            res += col * p.second / h;
        }
        cout << fixed << setprecision(15) << res << endl;
    }
}

Measured memory_bytes: 1260
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

ll dp[2010][2010];

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

    int n, m, s[2123], t[2123];
    cin >> n >> m;
    REP(i, n)
    cin >> s[i + 1];
    REP(i, m)
    cin >> t[i + 1];

    memset(dp, 0, sizeof(dp));

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (i == 0 && j == 0)
            {
                dp[i][j] = 1;
                continue;
            }

            if (i > 0)
                (dp[i][j] += dp[i - 1][j]) %= MOD;
            if (j > 0)
                (dp[i][j] += dp[i][j - 1]) %= MOD;

            if (i > 0 && j > 0 && s[i] != t[j])
                (dp[i][j] += MOD - dp[i - 1][j - 1]) %= MOD;
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

Measured memory_bytes: 31872
#include <iostream>
#include <vector>
int main(){
    using namespace std;
    long long int a,b,x;
    char y;
    vector<long long int> v1;
    vector<char> v2;
    a = 1;
    b = 1;
    while(1){
        cin >> a >> y >> b;
        if(y=='?'){
            break;
        }else if(y=='+'){
            x = a+b;
        }else if(y=='-'){
            x = a-b;
        }else if(y=='*'){
            x = a*b;
        }else if(y=='/'){
            x = a/b;
        }
        v1.push_back(x);
    }
    int i;
    for(i=0;i<v1.size();i++){
        cout << v1[i] << endl;
    }
    return 0;
}

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

typedef pair<int, int> pii;
typedef long long ll;
int n;
vector<pii> v;
multiset<int> s;

int main() {
    cin >> n;
    rep(i, 1, n) {
        int x; cin >> x;
        v.push_back(make_pair(x, i));
    }
    s.insert(0), s.insert(0);
    s.insert(n + 1), s.insert(n + 1);
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    ll ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int num = v[i].first, pos = v[i].second;
        multiset<int>::iterator it = s.lower_bound(pos);
        int r1 = *it++;
        int r2 = *it--;
        --it;
        int l1 = *it--;
        int l2 = *it;
        if (l1) ans += 1ll * num * (r1 - pos) * (l1 - l2);
        if (r1 <= n) ans += 1ll * num * (pos - l1) * (r2 - r1);
        s.insert(pos);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 5748
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

val MOD = 1_000_000_007L

class Solver(stream: InputStream, private val out: java.io.PrintWriter) {
  fun solve() {
    val N = ni()
    val A = na(N)
    var ans = 0
    for (i in 0 until N) {
      if ((i + 1) % 2 == 1 && A[i] % 2 == 1) ans++
    }
    out.println(ans)
  }













































  private val isDebug = try {
    // なんか本番でエラーでる
    System.getenv("MY_DEBUG") != null
  } catch (t: Throwable) {
    false
  }

  private var tokenizer: StringTokenizer? = null
  private val reader = BufferedReader(InputStreamReader(stream), 32768)
  private fun next(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
      tokenizer = StringTokenizer(reader.readLine())
    }
    return tokenizer!!.nextToken()
  }

  private fun ni() = next().toInt()
  private fun nl() = next().toLong()
  private fun ns() = next()
  private fun na(n: Int, offset: Int = 0): IntArray {
    return map(n) { ni() + offset }
  }
  private fun nal(n: Int, offset: Int = 0): LongArray {
    val res = LongArray(n)
    for (i in 0 until n) {
      res[i] = nl() + offset
    }
    return res
  }

  private fun na2(n: Int, offset: Int = 0): Array<IntArray> {
    val a  = Array(2){IntArray(n)}
    for (i in 0 until n) {
      for (e in a) {
        e[i] = ni() + offset
      }
    }
    return a
  }

  private inline fun map(n: Int, f: (Int) -> Int): IntArray {
    val res = IntArray(n)
    for (i in 0 until n) {
      res[i] = f(i)
    }
    return res
  }

  private inline fun debug(msg: () -> String) {
    if (isDebug) System.err.println(msg())
  }

  private fun debug(a: LongArray) {
    debug { a.joinToString(" ") }
  }

  private fun debug(a: IntArray) {
    debug { a.joinToString(" ") }
  }

  private fun debug(a: BooleanArray) {
    debug { a.map { if (it) 1 else 0 }.joinToString("") }
  }

  private fun debugDim(A: Array<LongArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private fun debugDim(A: Array<IntArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }

  /**
   * 勝手にimport消されるのを防ぎたい
   */
  private fun hoge() {
    min(1, 2)
    max(1, 2)
    abs(-10)
  }
}

fun main() {
  val out = java.io.PrintWriter(System.out)
  Solver(System.`in`, out).solve()
  out.flush()
}

Measured memory_bytes: 34756
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int s = sc.nextInt();
		
		int c = 0;
		while(s>0){
			if(s%10!=0)
				c++;
			s/=10;
		}
		
		System.out.println(c);
	}

}


Measured memory_bytes: 21844
#include<map>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>

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

using namespace std;

struct Node{
	char name[32];
	Node *parent;
	vector<Node *> child;
};

bool isChild(Node *u,Node *v){
	rep(i,v->child.size()) if(v->child[i]==u) return true;
	return false;
}

bool isSibling(Node *u,Node *v){
	return u!=v && u->parent==v->parent;
}

bool isDescendant(Node *u,Node *v){
	for(;u->parent;u=u->parent) if(u->parent==v) return true;
	return false;
}

int main(){
	for(int n,m;scanf("%d%d",&n,&m),n;){
		getchar();

		Node root; root.parent=NULL;
		Node *target=&root;
		int sp_prev=-1;
		map<string,Node *> f;
		rep(i,n){
			char s[256];
			fgets(s,256,stdin);
			int len=strlen(s);
			s[--len]='\0';

			int sp=0;
			rep(j,len) if(s[j]!=' ') {
				sp=j; break;
			}

			Node *u=new Node;
			strcpy(u->name,s+sp);
			f[s+sp]=u;
			if(sp==sp_prev+1){
				target->child.pb(u);
				u->parent=target;
			}
			else{
				int back=sp_prev-sp;
				rep(j,back) target=target->parent;

				target->parent->child.pb(u);
				u->parent=target->parent;
			}

			sp_prev=sp;
			target=u;
		}

		rep(i,m){
			char x[32],y[32],rel[32];
			scanf("%s is %*s %s of %s",x,rel,y);
			y[strlen(y)-1]='\0';

			bool res;
			if     (strcmp(rel,"child"     )==0) res=isChild(f[x],f[y]);
			else if(strcmp(rel,"parent"    )==0) res=isChild(f[y],f[x]);
			else if(strcmp(rel,"sibling"   )==0) res=isSibling(f[x],f[y]);
			else if(strcmp(rel,"descendant")==0) res=isDescendant(f[x],f[y]);
			else /*(strcmp(rel,"ancestor")==0)*/ res=isDescendant(f[y],f[x]);
			puts(res?"True":"False");
		}

		putchar('\n');
	}

	return 0;
}

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

vector<int> par(100000, -1);
vector<int> treeSize(100000, 0);

void initialize(int N) {
  for (int i = 0; i < N; ++i) {
    par[i] = i;
    treeSize[i] = 1;
  }
}

int root(int x) {
  if (par[x] == x) {
    return x;
  } else {
    par[x] = root(par[x]);
    return par[x];
  }
}

bool same(int x, int y) {
  return root(x) == root(y);
}

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  
  if (x == y) {
    return;
  } else {
    par[x] = y;
    treeSize[y] += treeSize[x];
    treeSize[x] = 0;
  }
}

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  vector<int> a(M);
  vector<int> b(M);
  vector<int> edge(N, 0);
  for (int i = 0; i < M; ++i) {
    cin >> a[i] >> b[i];
    --a[i];
    --b[i];
    ++edge[a[i]];
    ++edge[b[i]];
  }
  vector<int> c(K);
  vector<int> d(K);
  vector<vector<int>> block(N);
  for (int i = 0; i < K; ++i) {
    cin >> c[i] >> d[i];
    --c[i];
    --d[i];
    block.at(c[i]).push_back(d[i]);
    block.at(d[i]).push_back(c[i]);
  }
  
  initialize(N);
  for (int i = 0; i < M; ++i) unite(a[i], b[i]);
  
  for (int i = 0; i < N; ++i) {
    int ans = treeSize[root(i)];
    --ans;
    ans -= edge[i];
    for (auto x : block[i]) {
      if (same(x, i)) --ans;
    }
    cout << ans;
    if (i < N - 1) cout << " ";
  }
  return 0;
}

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

 
/*
ll gcds(ll a,ll b){
    if(a<b){
        swap(a,b);
    }
    ll r=a%b;
    if(r==0){
        return b;
    }
    while(r>0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
 
 
ll lcms(ll a,ll b){
    ll mmr=gcds(a,b);
    a=a/mmr;
    b=b/mmr;
    return a*b*mmr;
}
*/

int main(){
    int N,M;
    cin>>N>>M;
    int ans=0;

    ans+=N*(N-1)/2;
    ans+=M*(M-1)/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace contest_Csharp
{
    class Program
    {
        

        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            //Console.ReadLine();
            var vals = Console.ReadLine().Split(' ');
                //.Select(x => double.Parse(x)).ToList();
            var A = long.Parse(vals[0]);
            var B = 0;
            var Bs = vals[1];
            var depth = 0;
            var flg = false;
            for (int i = 0; i <Bs.Length ; i++)
            {
                if (flg)
                {
                    depth++;
                }
                if (Bs[i] == '.')
                {
                    flg = true;
                    continue;
                }
                
                B = 10 * B + Bs[i]-'0';
            }
            long ans = (long)(A*B);
            for (int i = 0; i < depth; i++)
            {
                ans = ans / 10;
            }
            
            
            



            Console.WriteLine(ans);
            Console.Out.Flush();

        }



    }

}


Measured memory_bytes: 27516
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

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

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

    string s;
    cin >> s;

    int lplus = 0;
    int lcount = 0;
    REP(i, n){
        if(s[i]=='('){
            lcount += 1;
        } else {
            if(lcount == 0){
                lplus += 1;
            } else {
                lcount -= 1;
            }
        }
    }

    s = string(lplus, '(') + s + string(lcount, ')');
    cout << s << endl;
}


Measured memory_bytes: 256
def dfs(i, f):
    if i == n - 1:
        return sum(list(map(int, f.split("+"))))
    return dfs(i + 1, f + s[i + 1]) +\
           dfs(i + 1, f + "+" + s[i + 1])

s = input()
n = len(s)

print(dfs(0, s[0]))

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int f[8][8], n, m, p[10], res;

void dfs(int pos, int mask) {
    if (pos == n) {
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (f[p[i - 1]][p[i]] == 0) ans++;
        }
        if (ans == 0) res++;
        return;
    }
    for (int i = 1; i < n; i++) {
        if(mask & (1 << i)) {
            p[pos] = i;
            dfs(pos + 1, mask ^ (1 << i));
        }
    }
}

int main(void){
    // Your code here!
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        f[a - 1][b - 1] = 1;
        f[b - 1][a - 1] = 1;
    }
    dfs(1, (1 << n) - 2);
    cout << res << endl;
}


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

int main()
{
		vector<int> v;
		size_t sizeV;cin>>sizeV;
		for( int i=0, temp; i!=sizeV; i++ ){
				cin>>temp;
				v.push_back(temp);
		}

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


		for( size_t i=0; i!=sizeV-1; i++ ){
				cout<<v[i]<<' ';
		}
		cout<<v[sizeV-1]<<endl;
}
				

Measured memory_bytes: 10088
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define MOD 1000000007
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(v) (v).begin() , (v).end()
#define sumof(v) accumulate(all(v), 0LL, plus<ll>())
#define maxof(v) max_element(all(v))
#define minof(v) min_element(all(v))
#define inf INT_MAX

int main(){
    FASTIO
    int N; cin>>N;
    vector<int> dp(max(N+1, 7), 0);
    dp[3] = 1;
    dp[4] = 1;
    dp[5] = 1;
    dp[6] = 2;
    for(int i=7; i<=N; ++i){
        dp[i] = 1;
        for(int j=3; j<=i-3; ++j){
            dp[i] = (dp[i] + dp[j])%MOD;
        }
    }
    cout<<dp[N]%MOD<<endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;


int main() {
    ll n;
    cin>>n;
    cout<<n/2+n%2<<endl;
}


Measured memory_bytes: 256
package main

import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func Sum(A *[]int) int {
  s := 0
  for _, a := range (*A) {
    s += a
  }
  return s
}

func Max(A *[]int) int {
  m := 0
  for _, a := range (*A) {
    if m < a { m = a }
  }
  return m
}

func main() {
  NM := NextIntVec()
  N, M := NM[0], NM[1]
  G := make([][]int, N)
  for i := range G {
    G[i] = make([]int, 0)
  }
  for i := 0; i < M; i++ {
    ST := NextIntVec()
    s, t := ST[0] - 1, ST[1] - 1
    G[s] = append(G[s], t)
  }
  E := make([][]float64, N)
  for i := range E {
    E[i] = make([]float64, N)
  }
  for i := N - 2; -1 < i; i-- {
    for _, adj := range G[i] {
      E[0][i] += E[0][adj] / float64(len(G[i]))
    }
    E[0][i] += 1.0
  }
  for i := 1; i < N; i++ {
    t := N - 1
    for _, adj := range G[i - 1] {
      if E[0][t] < E[0][adj] { t = adj }
    }
    for j := N - 2; -1 < j; j-- {
      D := float64(len(G[j]))
      if i - 1 == j { D -= 1.0 }
      for _, adj := range G[j] {
        if i - 1 == j && adj == t { continue }
        E[i][j] += E[i][adj] / D
      }
      E[i][j] += 1.0
      if D < 1.0 { E[i][j] = float64(N * N) }
    }
  }
  ans := float64(N)
  for _, e := range E {
    if e[0] < ans { ans = e[0] }
  }
  Write(ans)
  Output()
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/combine.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    n %= 10;

    switch (n) {
        case 2:
        case 4:
        case 5:
        case 7:
        case 9:
            cout << "hon" << endl;
            return 0;
        case 0:
        case 1:
        case 6:
        case 8:
            cout << "pon" << endl;
            return 0;
        case 3:
            cout << "bon" << endl;
            return 0;
    }
}

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

int main(){
  int N;
  cin>>N;
  map<string,bool> s;
  rep(i,N){
    string s1;
    cin>>s1;
    s[s1]=true;
  }
  cout<<s.size();


  return 0;
}

Measured memory_bytes: 19128
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

int main(int argc, char* argv[])
{
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    if ((x - r) < 0 || (y - r) < 0 || (x + r) > W || (y + r) > H) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll h;
    int n,i,flag=0;
    cin>>h>>n;
    ll ara[n+5],sum=0;
    for(i=0;i<n;i++)
        cin>>ara[i];
    for(i=0;i<n;i++)
    {
        h-=ara[i];
        if(h<=0)
        {
            flag=1;
            break;
        }
    }
    if(flag)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n;
	int q;
	int box[100001];
	int i,j;
	int cnt;
	int low,high,mid,key,flg;
	cin>>n;
	for(i=0;i<n;i++)	cin>>box[i];
	sort(box,box+n);
	cnt=0;
	cin>>q;
	for(i=0;i<q;i++){
		cin>>key;
		flg=0;
		low=0;
		high=n-1;
		while(low<=high){
			mid=(low+high)/2;
			if(key<box[mid])		high=mid-1;
			else if(key>box[mid])	low=mid+1;
			else{
				flg=1;
				break;
			}
		}
		if(flg)	cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}
		



Measured memory_bytes: 3440