akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define fi first
#define se second

#define INF 2147483647

// Range Minimum Query
class RMQ {
private:
  int n;
  vector<int> data;
public:
  RMQ(int n_){
    n=1;
    while(n<n_) n*=2;
    data = vector<int>(2*n-1, INF);
  }
  void update(int k, int a){ // update data[k]=a, k(0-indexed)
    k+=n-1;
    data[k]=a;
    while(k>0){
      k = (k-1)/2;
      data[k] = min(data[k*2+1], data[k*2+2]);
    }
  }
  int query(int a,int b,int k=0,int l=0,int r=-1){ //min value in [a,b)
    if(r==-1) r=n;
    // k := current node, range of k := [l,r)
    if(r<=a || b<=l) return INF;
    if(a<=l && r<=b) return data[k];
    int vl=query(a,b,k*2+1,l,(l+r)/2);
    int vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
}; // END class RMQ

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

  RMQ rmq(n);

  rep(i,q){
    int c,x,y;
    cin>>c>>x>>y;
    if(c==0){
      rmq.update(x,y);
    } else {
      cout<<rmq.query(x,y+1)<<endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
	string x;
	int n,m;
    vector<int> p, a;
	p.push_back(-1);
	a.push_back(-1);
	getline(cin, x);
	while(n=x.find("peach", p.back() + 1), ~n){
		p.push_back(n);
    }
	while(m=x.find("apple", a.back() + 1), ~m){
		a.push_back(m);
    }
	for(int i = 1; i < p.size(); i++){
		x.replace(p[i], 5, "apple");
    }
	for(int j = 1; j < a.size(); j++){
		x.replace(a[j], 5, "peach");
    }
	cout<< x <<endl;
	return 0;
}


Measured memory_bytes: 3192
N = int(input())
S = input()

output = ''

hiraki = 0
toji = 0
for i in S:
    if i == '(':
        if toji > 0:
            output = '(' * toji + output
            toji = 0
            hiraki += 1
            output += i
        else:
            hiraki += 1
            output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            toji += 1
            output += i

output += ')' * hiraki
output = '(' * toji + output

print(output)


Measured memory_bytes: 3060
import java.util.*;

public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if(x == 7 || x == 5 || x == 3){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 22740
#include <iostream>
#include <vector>
#include <string>

int main(){
    int M, N, ans = 0, sum = 0, tmp;
    std::vector<int> A;
    std::cin >> N >> M;
    
    for(auto i = 0; i < N; i++){
        std::cin >> tmp;
        A.push_back(tmp);
        sum += tmp;
    }

    double a = (double)sum / (double)(4 * M);

    for(auto i = 0; i < N; i++){
        if((double)A.at(i) >= a){
            ans++;
        }
    }

    std::string str = ans >= M ? "Yes" : "No";

    std::cout << str << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1061109567
#define int long long
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
int cnt=0,val=0;
int fpow(int a,int p) {
	int ans=1;
	fw (i,0,p) ans*=a;
	return ans;
}
int N=41289;
string N2=to_string(N);
char query(int x) {
	string temp=to_string(x);
	if (x<=N&&temp<=N2) return 'Y';
	if (x>N&&temp>N2) return 'Y';
	return 'N';
}
signed main() {
	//in("aome.inp");
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	/*
	How to get the number of digits N have?
	Keep asking queries of 1e9 down to 1. Let's say N have k digits. Then 1e(k + 1) will return N and
	1ek will return Y.
	k have been found. Now, binary search on this range simply.
	Query for mid:
	mid <= N. How to ask?
	We can see, mid * 10 > N with all possible mids. Also, it's the same as mid when comparing as
	strings. So the relations can be found.
	If we receive a Y, mid > N. Else, mid <= N
	*/
	int cur=9;
	//Problem: N = 1eK. Simply ask a query for N + 1. Should return Y.
	for (int i=1e9;i>=1;i/=10) {
		cout<<"? "<<i<<endl<<flush;
		char temp;
		//temp=query(i);
		cin>>temp;
		if (temp=='Y') {cnt=cur; break;}
		cur--;
	}
	//cout<<"cnt="<<cnt<<"\n";
	if (cnt==9) {
		for (int i=1;i<=1e9;i*=10) {
			cout<<"? "<<i+1<<endl<<flush;
			char temp;
			//temp=query(i+1);
			cin>>temp;
			if (temp=='Y') {
				cout<<"! "<<i<<endl<<flush;
				return 0;
			}
		}
	}
	//cout<<"passed?\n";
	int l=fpow(10,cnt),r=fpow(10,cnt+1)-1;
	while (l<r) {
		int mid=(l+r)>>1;
		cout<<"? "<<mid*10<<endl<<flush;
		char temp;
		//temp=query(mid*10);
		cin>>temp;
		if (temp=='Y') r=mid;
		else l=mid+1;
	}
	cout<<"! "<<l<<endl<<flush;
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
vl li;
vl memo = {3,5,7};
int main(){
  ll l,r;
  cin>>l>>r;
  ll  ans =INF;

  for(ll i = 0;i<=min(2020LL,r-l);i++){
    for(ll j= i+1;j<=min(2020LL,r-l);j++){
      ll x=l+i,y=l+j;
      ans =min(ans,(x*y)%2019);
    }
  }
  cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
int l[100+5];
int choice(int n){
    return 0;
}
int main(void){
    int n;
    
    scanf("%d", &n);
    for(int i=0; i<n; i++)scanf("%d", &l[i]);
    
    int ans=0;
    for(int a=0; a<n-2; a++){
        for(int b=a+1; b<n-1; b++){
            for(int c=b+1; c<n; c++){
                if(l[a]!=l[b] && l[b]!=l[c] && l[c]!=l[a]){
                    if(l[a]+l[b]>l[c] && l[b]+l[c]>l[a] && l[c]+l[a]>l[b]){
                        ans++;
                    }
                }
            }
        }
    }
    
    printf("%d\n", ans);
    return 0;
}


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

#define int long long



typedef long long ll;
typedef long double ld;

int mod = 1e9+7;



int solve(int x){
	int ans = 100;
	while(x--){
		ans += ans/100;
	}
	//cout<<ans<<endl;
	return ans;
}



signed main(){
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k;
    cin>>k;
    int l = 0,r = 4000;
    //cout<<solve(4000)<<endl;
    while(l != r){
    	int mid = l + (r-l)/2;
    	if(solve(mid) < k) l = mid+1;
    	else r = mid;
	}
	cout<<l;
    return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>

//using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

using ll =  long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
template<typename T> void chadd(T& a, T b) { a = a + b; }

namespace {  // 名前なし名前空間
	// gcd, lcm は C++17 でstdに標準入りしたので言語のバージョンに注意
	// 最大公約数
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

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

	template<long long mod>
	class modint {
	private:
		long long a;
	public:
		constexpr modint(const long long x = 0) noexcept : a(x% mod) {}
		constexpr long long& value() noexcept { return a; }
		constexpr const long long& value() const noexcept { return a; }
		constexpr modint operator+(const modint rhs) const noexcept {
			return modint(*this) += rhs;
		}
		constexpr modint operator-(const modint rhs) const noexcept {
			return modint(*this) -= rhs;
		}
		constexpr modint operator*(const modint rhs) const noexcept {
			return modint(*this) *= rhs;
		}
		constexpr modint operator/(const modint rhs) const noexcept {
			return modint(*this) /= rhs;
		}
		constexpr modint& operator+=(const modint rhs) noexcept {
			a += rhs.a;
			if (a >= mod) a -= mod;
			return *this;
		}
		constexpr modint& operator-=(const modint rhs) noexcept {
			if (a < rhs.a) a += mod;
			a -= rhs.a;
			return *this;
		}
		constexpr modint& operator*=(const modint rhs) noexcept {
			a = a * rhs.a % mod;
			return *this;
		}
		constexpr modint& operator/=(modint rhs) noexcept {
			long long k = mod - 2;
			while (k > 0) {
				if (k & 1) {
					*this *= rhs;
				}
				rhs *= rhs;
				k /= 2;
			}
			return *this;
		}
		friend std::ostream& operator<<(std::ostream& os, const modint& X) {
			return os << X.a;
		}
		friend std::istream& operator>>(std::istream& is, modint& X) {
			is >> X.a;
			X.a %= mod;
			if (X.a < 0) X.a += mod;
			return is;
		}
	};

	using mint = modint<(int)1e9 + 7>;
}

int main() {

	ll n;
	std::cin >> n;
	std::vector<ll> x(n);
	rep(i, n) std::cin >> x[i];

	std::vector<mint> fact(n, 1);
	Rep(i, 2, n) {
		fact[i] = fact[i - 1] * i;
	}

	mint ans = 0;

	std::vector<mint> c(n);
	c[0] = fact[n - 1];
	for (int i = 0; i < n - 1; ++i) {
		// x[i + 1] - x[i] の距離を各スライムが移動する確率
		ll dist = x[i + 1] - x[i];

		ans += c[i] * dist;

		c[i + 1] = c[i] + fact[n - 1] / (i + 2);
	}

	std::cout << ans << std::endl;

	return 0;
}

Measured memory_bytes: 2560
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

using i8 = ::std::int_least8_t;
using i32 = ::std::int_least32_t;
using i64 = ::std::int_least64_t;
using u8 = ::std::uint_least8_t;
using u32 = ::std::uint_least32_t;
using u64 = ::std::uint_least64_t;
using isize = ::std::ptrdiff_t;
using usize = ::std::size_t;

template <class T = usize> class rep {
	const T f, l;

public:
	class itr {
		friend rep;
		T i;
		constexpr itr(T x) noexcept : i(x) {}

	public:
		void operator++() noexcept { ++i; }
		constexpr T operator*() const noexcept { return i; }
		constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
	};
	constexpr rep(const T first, const T last) noexcept : f(first), l(last) {}
	constexpr itr begin() const noexcept { return itr(f); }
	constexpr itr end() const noexcept { return itr(l); }
};
template <class T = usize> class revrep {
	const T f, l;

public:
	class itr {
		friend revrep;
		T i;
		constexpr itr(T x) noexcept : i(x) {}

	public:
		void operator++() noexcept { --i; }
		constexpr T operator*() const noexcept { return i; }
		constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
	};
	constexpr revrep(const T first, const T last) noexcept : f(first), l(last) {}
	constexpr itr begin() const noexcept { return itr(l - 1); }
	constexpr itr end() const noexcept { return itr(f - 1); }
};
template <class T> bool amax(T &a, const T &b) {
	return a <= b ? (a = b, 1) : 0;
}
template <class T> bool amin(T &a, const T &b) {
	return b <= a ? (a = b, 1) : 0;
}
template <class T> bool asmax(T &a, const T &b) {
	return b <= a ? 0 : (a = b, 1);
}
template <class T> bool asmin(T &a, const T &b) {
	return a <= b ? 0 : (a = b, 1);
}
template <class T> using vec_alias = ::std::vector<T>;
template <class T> auto md_vec(usize n, const T &value) {
	return ::std::vector<T>(n, value);
}
template <class... Args> auto md_vec(usize n, Args... args) {
	return ::std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> const T &as_const(const T &v) noexcept { return v; }
template <class T> constexpr T difference(const T &a, const T &b) {
	return a <= b ? b - a : a - b;
}

#include <algorithm>
#include <iostream>
#include <utility>

int main() {
	::std::vector<u32> n(4);
	for (auto &e : n) {
		::std::cin >> e;
	}
	::std::sort(n.begin(), n.end());
	::std::cout << ((n == std::vector<u32>({1, 4, 7, 9})) ? "YES" : "NO") << ::std::endl;
	return 0;
}


Measured memory_bytes: 256
def next(S='a'):
    idx = len(S)
    cnt = len(set(list(S)))
    if idx == N:
        print(S)
        return
    for i in range(min(N,idx)+1):
        if cnt < i:
            break
        next(S +ls[i])


N = int(input())
ls = ['a','b','c','d','e','f','g','h','i','j']
next()

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

///////////////////////////////////////////
//const long long int INF = 1000000000000000000LL;
const long long int INF = 1000000;
using ll = long long int;
using vi = vector<int>;
using Vi = vector<long long int>;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
auto min(auto x,auto y){if(x>y){return y;}else{return x;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return 1; } return 0; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return 1; } return 0; }
template<class T>T sqar(T x){ return x*x; }
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(    v[0])>()) //降順でVをソート
///////////////////////////////////////////

//C- strangeBank
ll N;
ll dp[100001];//dp[n]:=n円払うのに必要な最低の回数。

ll cal(ll n){
    if(n==0)return dp[0]=0;
    if(dp[n]!=INF)return dp[n];
    ll six=6,nine=9;
    while(1){if(nine>n){nine/=9;break;}nine*=9;}
    while(1){if(six>n){six/=6;break;}six*=6;}
    if(nine==six){
        dp[n]=min(dp[n],cal(n-1)+1);
    //}else if(nine>six){
    //    dp[n]=min(dp[n],cal(n-nine)+1);
    }else{
        dp[n]=min(cal(n-nine)+1 , min(dp[n],cal(n-six)+1) );
    }
   // cout<<"n,dp[n] : "<<n<<" , "<<dp[n]<<endl;
    return dp[n];
}

int main(){
    cin>>N;
    rep(i,100001)dp[i]=INF;
   // cout<<"test"<<endl;
    cout<<cal(N)<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
  long long int a,b,c,odd=0;
  cin >> a >> b >> c;
  if(a%2==1)odd++;
  if(b%2==1)odd++;
  if(c%2==1)odd++;
  if(odd<3)cout << 0;
  else cout << min(min(a*b,b*c),a*c);
}


Measured memory_bytes: 3608
X = int(input())
C= [i**5 for i in range(120)]

a = 0
b = 0

for a in range(len(C)):
    for b in range(len(C)):
        if C[a] + C[b] == X:
            print(a, -b)
            exit(0)
        elif C[a] - C[b] == X:
            print(a, b)
            exit(0)


Measured memory_bytes: 9068
def floor_linear_sum(n,m,a,b):
    res = 0
    while True:
        if a >= m:
            res += (n-1)*n*(a//m)//2
            a %= m
        if b >= m:
            res += n * (b//m)
            b %= m

        y_max = (a*n+b)//m
        if y_max == 0:
            return res
        x_max = y_max*m-b
        res += (n - (x_max + a - 1)//a)*y_max
        n,m,a,b = y_max, a, m, (a-x_max)%a

T = int(input())
for _ in range(T):
    print(floor_linear_sum(*map(int,input().split())))


Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
int a[100001],b[100001];
int main()
{
	int n;
	int ans;
	cin >> n;
	for(int i=0;i<n/2;i++)
{
		int c,d;
		cin >> c >> d;
		a[c]++;
		b[d]++;
	}
	int a1=0,a2=0,b1=0,b2=0;
	for(int i=0;i<=100000;i++)
{
		if(a[i]>a[a1])
{
			a2 = a1;
			a1 = i;
		}else if(a[i]>a[a2])a2=i;
		if(b[i]>b[b1]){
			b2 = b1;
			b1 = i;
		}else if(b[i]>b[b2])b2=i;
	}
	if(a1!=b1)ans = n - a[a1] - b[b1];
	else ans = min(n-a[a1]-b[b2],n-a[a2]-b[b1]);
	cout << ans << endl;
}

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

int a[3*100000];

signed main(){

  int n; cin >> n;
  for(int i = 0; i < n; i++){
    int d; cin >> d;
    a[i] = d/10;
  }

  int dmax = a[0];
  for(int i = 0; i < n; i++){
    if(dmax > a[i]) dmax--;
    else dmax = a[i];
    if(dmax <= 0){
      cout << "no" << endl;
      return 0;
    }
  }

  reverse(a,a+n);
  dmax = a[0];
  for(int i = 0; i < n; i++){
    if(dmax > a[i]) dmax--;
    else dmax = a[i];
    if(dmax <= 0){
      cout << "no" << endl;
      return 0;
    }
  }
  cout << "yes" << endl;

  return 0;
}



Measured memory_bytes: 4252
#include <stdio.h>

typedef struct List {
	struct List *next;
	int v;
} list;

int main()
{
	int i, N, M, u, w, H[100001];
	list *adj[100001] = {}, e[200001];
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++) scanf("%d", &(H[i]));
	for (i = 0; i < M; i++) {
		scanf("%d %d", &u, &w);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	int ans = 0;
	list *p;
	for (u = 1; u <= N; u++) {
		for (p = adj[u]; p != NULL; p = p->next) if (H[p->v] >= H[u]) break;
		if (p == NULL) ans++;
	}
	
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 6028
#include <iostream>
#include <iomanip>

using namespace std;

int main(){
	int64_t w, h, x, y;
	cin >> w >> h >> x >> y;

	double max_s;
	int way = 0;

	max_s = (double)(w) * (double)(h) / 2.0;
	if((2*x == w) && (2*y == h)){
		way = 1;
	}

	cout << fixed << setprecision(10) << max_s << " " << way << endl;


	return 0;
}

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

vector<ll> divisor(ll x){
  vector<ll> res;
  for(ll i = 1LL; i * i <= x; ++i){
    if(x % i == 0){
      res.push_back(i);
      if(i * i != x){
        res.push_back(x / i);
      }
    }
  }
  sort(res.begin(), res.end());
  reverse(res.begin(), res.end());
  return res;
}

int main(){
  ll n, m;
  cin >> n >> m;
  ll div = m / n;

  vector<ll> res = divisor(m);
  for(ll i = 0; i < res.size(); ++i){
    if(n * res[i] > m)  continue;
    if(n * res[i] <= m){
      cout << res[i] << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }

  ll ans = 0;
  for (ll i = 0; i < 70; i++)
  {
    ll z = 0, o = 0;
    for (ll j = 0; j < N; j++)
    {
      bitset<70> B(A.at(j));

      if (B.test(i))
        o++;
      else
        z++;
    }
    ll tmp = (1LL << i) % MOD;
    tmp *= z;
    tmp %= MOD;
    tmp *= o;
    tmp %= MOD;
    ans += tmp;
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2560
N=int(input())
MOD=10**9+7

def func(N):
    S=str(bin(N))[2:]
    L=len(S)
    dp=[[0]*3 for i in range(L+1)]
    dp[0][0]=1
    for i in range(L):
        n=ord(S[i])-ord('0')
        for k in range(3):
            for s in range(3):
                if 2*s+n-k<0:
                    continue
                sd=min(2*s+n-k,2)
                dp[i+1][sd]+=dp[i][s]
                dp[i+1][sd]%=MOD
    return (dp[L][0]+dp[L][1]+dp[L][2])%MOD
print(func(N))


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,d[1000],count;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>d[i];
	}
	sort(d,d+n);
	for(int j=0;j<n;j++){
		for(int k=j-1;k>=0;k--){
			if(d[j]==d[k])goto loop1;
		}
		count++;
		loop1:;
	}
	cout<<count<<endl;
}


Measured memory_bytes: 256
//http://drken1215.hatenablog.com/entry/2019/02/24/224100

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N;
vector<int> L;
vector<int> A; // A, B, C

int main() {
    cin >> N;
    A.resize(3);
    for (int i = 0; i < 3; ++i) cin >> A[i];
    L.resize(N);
    for (int i = 0; i < N; ++i) cin >> L[i];

    int res = 1<<29;
    vector<int> bit(3);
    for (bit[0] = 1; bit[0] < (1<<N); ++bit[0]) { // 0 は含めない
        for (bit[1] = 1; bit[1] < (1<<N); ++bit[1]) { // 0 は含めない
            // 共通要素あったらダメ
            if (bit[1] & bit[0]) continue;
            for (bit[2] = 1; bit[2] < (1<<N); ++bit[2]) { // 0 は含めない
                // 共通要素があったらダメ
                if (bit[2] & bit[0]) continue;
                if (bit[2] & bit[1]) continue;
                
                // sums: A〜C に選んだ竹の長さの合計、nums: A〜C に選んだ竹の本数
                vector<int> sums(3, 0), nums(3, 0);
                for (int i = 0; i < N; ++i) {
                    for (int j = 0; j < 3; ++j) {
                        if (bit[j] & (1<<i)) {
                            sums[j] += L[i];
                            nums[j]++;
                        }
                    }
                }

                // score を求める
                int score = 0;
                for (int i = 0; i < 3; ++i) {
                    score += abs(sums[i] - A[i]); // +1, -1 のコスト
                    score += (nums[i] - 1) * 10; // 合体のコスト
                }
                res = min(res, score);
            }
        }
    }
    cout << res << endl;
}

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

using namespace std;

using ll =  long long int;

#define int  long long int
#define mod  1000000007

ll mod_pow(ll a,ll b,ll m)
{
    ll res = 1;
    while(b)
    {
        if(b&1)
        {
            res=(res*a) % m;
        }
        a=(a*a) % m;
        b>>=1;
    }
    return res;
}

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

    ll n;
    
    cin >> n;
    
    if(n == 1) {
    	cout << 0;
    	return 0;
    }
    
    ll ans = mod_pow(10 , n ,mod);
    ll t1 = mod_pow(9 , n , mod);
    t1 = t1*2;
    t1 %= mod;
    ll t2 = mod_pow(8 , n , mod);
    
    t1 = (-t1+t2 + mod) % mod;
    
    cout << (ans + t1 + mod) % mod;
    
    return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
	int n,a,b,c,d;
	scanf("%d",&n);
	a=n/1000;
	b=n%1000/100;
	c=n%1000%100/10;
	d=n%10;
	if(a+b+c+d==7)
	{
		printf("%d+%d+%d+%d=7\n",a,b,c,d);
		return 0;
	}
	if(a+b-c+d==7)
	{
		printf("%d+%d-%d+%d=7\n",a,b,c,d);
		return 0;
	}
	if(a+b+c-d==7)
	{
		printf("%d+%d+%d-%d=7\n",a,b,c,d);
		return 0;
	}
	if(a+b-c-d==7)
	{
		printf("%d+%d-%d-%d=7\n",a,b,c,d);
		return 0;
	}
	if(a-b+c+d==7)
	{
		printf("%d-%d+%d+%d=7\n",a,b,c,d);
		return 0;
	}
	if(a-b-c+d==7)
	{
		printf("%d-%d-%d+%d=7\n",a,b,c,d);
		return 0;
	}
	if(a-b-c-d==7)
	{
		printf("%d-%d-%d-%d=7\n",a,b,c,d);
		return 0;
	}
	if(a-b+c-d==7)
	{
		printf("%d-%d+%d-%d=7\n",a,b,c,d);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <list>
#include <time.h>
#include <unordered_map>
#include <bitset>
#include <exception>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define FILE "file"
#define lc v << 1
#define rc (v << 1) + 1
#define inf 1e+9
#define linf ll(1e+18)
#define dinf 1e+14

typedef long long ll;
#define pb push_back
#define mp make_pair

const int maxn = 50 + 5;
ll a[maxn];
vector<pair<int, int>> v;

void solve()
{
    int n;
    cin >> n;
    
    ll m1 = -linf, m2 = linf;
    int ind1 = 0, ind2 = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        
        if(m1 < a[i])
        {
            m1 = a[i];
            ind1 = i;
        }
        
        if(m2 > a[i])
        {
            m2 = a[i];
            ind2 = i;
        }
    }
    
    if(abs(m2) <= m1)
    {
        for(int i = 0; i < n; i++)
        {
            v.pb(mp(ind1, i));
        }
        
        for(int i = 0; i < n - 1; i++)
        {
            v.pb(mp(i, i + 1));
        }
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            v.pb(mp(ind2, i));
        }
        
        for(int i = n - 1; i > 0; i--)
        {
            v.pb(mp(i, i - 1));
        }
    }
    
    cout << v.size() << "\n";
    for(int i = 0; i < (int) v.size(); i++)
    {
        cout << v[i].first + 1 << " " << v[i].second + 1 << "\n";
        a[v[i].second] += a[v[i].first];
    }
    
    
    
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);
    //freopen(FILE ".in", "r", stdin);freopen(FILE ".out", "w", stdout);
    //freopen("file.in", "r", stdin);freopen("file.out", "w", stdout);
    int t = 1;
    //cin >> t;
    
    while(t--)
    {
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int a,b,c=~(1<<31),M=(1<<16)-1;

int r(){
    a=36969*(a&M)+(a>>16);
    b=18000*(b&M)+(b>>16);
    return (c&((a<<16)+b))%1000000;
}

set<pair<int,int>> st[303030];
int main(){
    int m,n;
    while(cin>>m>>n>>a>>b,m+n!=0){
        int l=m+n;
        int x[l],y[l],z[l];
        rep(i,m)cin>>x[i]>>y[i]>>z[i];
        rep(i,n){
            x[i+m]=r();
            y[i+m]=r();
            z[i+m]=r();
        }
        vector<int> ord(l);
        rep(i,l)ord[i]=i;
        sort(ord.begin(),ord.end(),[&](int s,int t){return x[s]==x[t] ? y[s]>y[t] : x[s]<x[t];});
        rep(i,303030){
            if(st[i].size()==2)continue;
            st[i].clear();
            st[i].insert({inf,-inf});
            st[i].insert({-inf,inf});
        }
        int ans=0;
        for(auto i:ord){
            int left=0,right=ans+1;
            while(right-left>1){
                int mid=(left+right)/2;
                auto itr=--st[mid].lower_bound({y[i],-1});
                if(itr->second<z[i])left=mid;
                else right=mid;
            }
            int ret=left+1;
            ans=max(ret,ans);
            auto itr=--st[ret].lower_bound({y[i],inf});
            if(z[i]>=itr->second)continue;
            if(itr->first<y[i])itr++;
            while(itr->second>=z[i])itr=st[ret].erase(itr);
            st[ret].insert({y[i],z[i]});
        }
        cout<<ans<<endl;
    } 
    return 0;
}


Measured memory_bytes: 54900
n,m=map(int,input().split())
left=[]
rigth=[]
for i in range(m):
  l,r=map(int,input().split())
  left.append(l)
  rigth.append(r)

ans=min(rigth)-max(left)+1
if ans<0:
  print(0)
else:
  print(ans)

Measured memory_bytes: 10996
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int a,b;
    cin >> a >> b;
    int d = a/b;
    int r = a%b;
    double x = a;
    double y = b;
    double f = x/y;
    printf("%d %d %.5lf\n",d,r,f);
    return 0;
}


Measured memory_bytes: 3132
#include "bits/stdc++.h"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
using index_t = std::size_t;

namespace lib
{
	using graph_t = std::vector<std::set<index_t>>;
	template<class T>using weighted_graph_t = std::vector<std::map<index_t, T>>;

	struct max_t
	{
		template<class T>constexpr T operator()(T const& lhs, T const& rhs)const
		{
			return std::max(lhs, rhs);
		}
	};
	struct min_t
	{
		template<class T>constexpr T operator()(T const& lhs, T const& rhs)const
		{
			return std::min(lhs, rhs);
		}
	};

	constexpr max_t max;
	constexpr min_t min;

	template<class T>auto order_by(T func)
	{
		return [=](auto&& lhs, auto&& rhs)
		{
			return func(lhs) < func(rhs);
		};
	}

	template<class T>constexpr auto max_v = std::numeric_limits<T>::max();
	template<class T>constexpr auto min_v = std::numeric_limits<T>::min();

	template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;
}

void Main()
{
	std::int64_t A;
	double B;
	std::cin >> A >> B;
	B *= 100;
	A *= std::int64_t(B + 0.5);
	A /= 100;
	std::cout << A << std::endl;
}

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

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define v2i vector<vector<int>>
#define v2l vector<vector<ll>>
#define ppi pair<int,int>
#define vpi vector<ppi>
#define ppl pair<ll,ll>
#define all(x) x.begin(),x.end()
#define ii int,int 
#define ff first    
#define ss second
#define forn(i,a,b) for(int i=a;i<b;i++)
#define forr(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,m) for(auto i : m)
#define imx INT_MAX
#define imn INT_MIN
#define inf LONG_MAX
#define minf LONG_MIN
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sze size()
#define rvs reverse 
#define itr iterator 
#define pre cout<<fixed<<setprecision(10);
#define umap unordered_map
#define uset unordered_set

/*
#define MODM(a,b,md) ((a%md)*(b%md))%md
#define MODA(a,b,md) ((a%md)+(b%md))%md
#define ull unsigned long long int
#define si short int
*/

/*
bool compare(int a,int b) {return a > b;}
bool compare1(ppi a,ppi b) {return a.ff > b.ff;}
bool compare2(ppi a,ppi b) {return a.ss < b.ss;}
ll Npower(ll a,ll b) {ll product = 1; while(b){if(b&1){product = product*a;}a = a*a;b = b>>1;} return product;}
ll power(ll a,ll b,ll md) {ll product = 1; while(b){if(b&1){product = MODM(product,a,md);}a = MODM(a,a,md);b = b>>1;} return product%md;}
ll GCD(ll a,ll b) {return b==0 ? a:GCD(b,a%b);}
ll LCM(ll a,ll b) {return (a/GCD(a,b))*b; }
*/

int main()
{
    fast

    int n,we;
    cin>>n>>we;

    vi v(n),w(n);
    forn(i,0,n)
    {
        cin>>w[i]>>v[i];
    }

        
    // v2l dp(n+1,vl(we+1,0));

    vl dp(we+1,0);

    forn(i,0,n)
    {
        forr(j,we,w[i])
        {
            dp[j] = max(dp[j],v[i]+dp[j-w[i]]);
        }
    }

    cout<<dp[we];

    return 0;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <unordered_set>
#include <complex>
using namespace std;
 
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
// typedef complex<double> C;
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
int INF = INT_MAX / 2;
double EPS = 1e-10;

int main() {
	int N, M; cin >> N >> M;
	vector<vector<bool> > adj(N, vector<bool>(N));
	while (M--) {
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u][v] = adj[v][u] = true;
	}
	vector<int> p(N);
	for (int i = 0; i < N; i++) p[i] = i;
	int cnt = 0;
	do {
		bool ok = true;
		rep(i, N - 1) if (!adj[p[i]][p[i + 1]]) ok = false;
		if (ok) cnt++;
	} while (next_permutation(p.begin() + 1, p.end()));
	cout << cnt << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)
INF = 110110110
H, W, K = list(map(int, input().split()))
S = [''] * H
for i in range(H):
    S[i] = input()
ans = H * W

for bit in range(2**(H-1)):
    cnt = bin(bit).count('1')
    id = [0] * H
    for i in range(H-1):
        if bit>>i & 1:
            id[i+1] = id[i] + 1
        else:
            id[i+1] = id[i]
    num = [[0] * W for i in range(id[H-1]+1)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                num[id[i]][j] += 1
    for i in range(id[H-1]+1):
        for j in range(W):
            if num[i][j] > K:
                cnt = INF
    sum = [0] * (id[H-1]+1)
    for j in range(W):
        need = False
        for i in range(id[H-1]+1):
            if sum[i] + num[i][j] > K:
                need = True
        if need:
            cnt += 1
            for i in range(id[H-1]+1):
                sum[i] = num[i][j]
        else:
            for i in range(id[H-1]+1):
                sum[i] += num[i][j]
    ans = min(ans, cnt)

print(ans)


Measured memory_bytes: 48348
//shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 

const ll inf = (ll)(1e17 + 17);
const ll mod = (ll)(1e9 + 7);


int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  ll n;
  cin >> n;
  vll a(n);
  for(ll i = 0; i < n; i++) {
    cin >> a[i];
    // if(a[i] > 0) foo = true;
  }
  ll res = 1;
  ll enc = 0;
  vector<ll> ans(n, 0);
  for(ll i = 0; i < n; i++) {
    if(a[i] == 0) {
      res = (res%mod * (3 - enc)%mod)%mod;  
      ans[0]++;
      enc++;
      continue;
    }
    res = (res%mod * (ans[a[i] - 1])%mod)%mod;
    ans[a[i]-1]--;
    ans[a[i]]++;
  }
  cout << res << endl;
  return 0;
} //good night.

Measured memory_bytes: 1792
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

double rec(int n, double d, double x){
	if(n==0) return 0.0;
	return d+(n-0.5)*x+rec(n-1, ((2*n+2)*d+5*x)/(2*n), ((2*n+4)*x)/(2*n));
}

int main(){
	ll n, d, x;
	cin>>n>>d>>x;
	cout.precision(19);
	cout<<rec(n, d, x)<<endl;
	return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0;i <n;i++)
#define RFOR(i, n) for(int i = n;i >= 0;i--)
#define REP(i, m, n) for(int i = m;i < n;i++)
#define RREP(i, m, n) for(int i = m;i >= n;i--)
#define INF 999999999

using namespace std;
int main(int argc, char const *argv[])
{
  int a[100];
  int i,max = 0,min = INF;
  int n;
  cin >>n;
  FOR(i,n)
  {
    cin >>a[i];
    if(a[i] > max) max = a[i];
    if(min > a[i]) min = a[i];
  }
  cout<<max - min<<endl;
return 0;

}


Measured memory_bytes: 256
package main

import (
   "fmt"
   "os"
   "bufio"
)

func main() {
 	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	input := stdin.Text()

  	bases := make(map[string]string)
  	bases["A"] = "T"
  	bases["T"] = "A"
    bases["G"] = "C"
    bases["C"] = "G"

  	fmt.Print(bases[input])
}


Measured memory_bytes: 640
def acinput():
    return list(map(int, input().split(" ")))


import heapq

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[0])
#print(ab)

res=0
do=[0]*(M+1)
nowdate=M-1

koho=[]
k=0
while True:
    #print(k)
    #print(nowdate)
    i=k
    while True:
        if i>=len(ab):
            k=10**10
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        #koho=np.append(koho,ab[i][1])
        heapq.heappush(koho,-ab[i][1])
        i+=1
    #print(koho)
    try:
        tmp=heapq.heappop(koho)
        res+=(-tmp)
    except:
        pass

    
    nowdate-=1
    if nowdate<0:
        break
    

print(int(res))



Measured memory_bytes: 32748
n = int(input())

x1 = n / 1.08
x2 = (n + 1) / 1.08
if x1.is_integer():
        print(int(x1))
elif int(x1) == int(x2):
    print(':(')
elif int(x2) == int(x1 + 1) and x2.is_integer():
    print(':(')
else:
    print(int(x1 + 1))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000


int main(){
	
	int N,M;
	cin>>N>>M;
	
	vector<pair<int,int>> P(N);
	for(int i=0;i<N;i++)cin>>P[i].first>>P[i].second;
	sort(P.begin(),P.end());
	priority_queue<int,vector<int>,greater<int>> Q;
	vector<int> R;
	
	for(int i=0;i<N;i++){
		Q.push(P[i].second);
		if(Q.size()>P[i].first){
			R.push_back(Q.top());
			Q.pop();
		}
	}
	int L = Q.size();
	sort(R.rbegin(),R.rend());
	int ans = 0;
	int cnt = 0;
	for(int i=0;i<R.size();i++){
		int t = M+1-R[i];
		if(cnt+L==M){
			ans++;
			continue;
		}
		if(cnt>=t){
			ans++;
		}
		else{
			cnt++;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 6388
n = int(input())
A = []
B = []

for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A = A[::-1]
B = B[::-1]

t = 0

for i, j in zip(A, B):
    if (i+t) % j == 0:
        continue
    else:
        t += j - (i+t) % j
print(t)

Measured memory_bytes: 58200
//Battlefield control establishing...
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <iomanip>
#define MCV main
#define reset(a,b) memset(a,b,sizeof(a))
const int INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;
//Get ready? LET'S ROCK!
int vis[5];
int MCV()
{
    for(int i=1;i<=3;i++)
    {
        int tmp1,tmp2;
        cin>>tmp1>>tmp2;
        vis[tmp1]++;
        vis[tmp2]++;
    }
    int sign=0;
    for(int i=1;i<=4;i++)
        if(vis[i]==3)
        sign=1;
    if(sign==1)
        cout<<"NO"<<endl;
    else
        cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    bfs = [0]*n
    bfs[0] = 1
    q = deque([0])
    while q:
        x = q.popleft()
        if bfs[x] == 1:
            nb = 2
        elif bfs[x] == 2:
            nb = 1
        else:
            nb = 3
        for y in v[x]:
            if bfs[y]^nb:
                bfs[y] |= nb
                q.append(y)
    ans = 0
    f = [0]*3
    for b in bfs:
        if b == 1:
            ans += f[0]
            f[1] += 1
            f[2] += 1
        elif b == 2:
            ans += f[1]
            f[0] += 1
            f[2] += 1
        else:
            ans += f[2]
            f[0] += 1
            f[1] += 1
            f[2] += 1
    print(ans-m)
    return


#Solve
if __name__ == "__main__":
    solve()


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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2005;
const ll INF=0x3f3f3f3f;
const ll MOD=998244353;
int n,p[MAX],cum=1,ans;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&p[i]);
    for(int i=1;i<n+1;i++){
        if(p[i]==p[i-1]) cum++;
        else{
            ans+=cum/2;
            cum=1;
        }
    }
    printf("%d\n",ans);
}


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

int main(){
      int n, k;
      cin>>n>>k;
      vector<int>a(n);
      for(int i=0; i<n; i++)
            cin>>a[i];

      vector<bool>dp(k+1, false);
      for(int i=1; i<=k; i++){
            for(int j=0; j<n; j++){
                  if(a[j]<=i){
                        if(dp[i-a[j]]==false)
                              dp[i]=true;
                  }
            }
      }
      if(dp[k]==true)cout<<"First\n";
      else cout<<"Second\n";
}

Measured memory_bytes: 3628
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
import java.util.*;
  
public class Main
{ 
    //By shwetank_verma
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    static int mod=1000000007;
    static boolean primes[]=new boolean[1000007];
    
    static boolean seive(int n){
        Arrays.fill(primes,true);
        primes[0]=primes[1]=false;
        for(int i=2;i*i<=n;i++){
            if(primes[i]==true){
                for(int p=i*i;p<=n;p+=i){
                    primes[p]=false;
                }
            }
        }
        if(n<1000007){
            return primes[n];
        }
        return false;
        
    }
    static int gcd(int a,int b){
        if(b==0)
        return a;
        return gcd(b,a%b);
    }
    static long GCD(long a,long b){
        if(b==0)
        return a;
        return GCD(b,a%b);
    }
    
  
    public static void main(String[] args) 
    { 
        FastReader sc=new FastReader(); 
        try{
           
                long t=sc.nextLong();
                String str="";
                while(t!=0) {
                	long v=t%26;
                	t/=26;
                	if(v==0) {
                		str=(char)(122)+str;
                		t--;
                	}
                	else
                	str=(char)(96+v)+str;
                	
                	
                }
                System.out.println(str);
           
            
        }catch(Exception e){
            return;
        }
    } 
}


Measured memory_bytes: 38652
#include<iostream>
using namespace std;
int main(){
int A,B,C; cin >> A >> B >> C;
  if((B < C) && (C < A) ||  (A < C) && (C < B)){
    cout << "Yes" << endl;}
  else{cout << "No" << endl;}
 // if(A > B && B < C){;
    //cout << "Yes" << endl;}
}





Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int main() {
	string S;
	cin >> S;
	if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3])cout << "Bad";
	else cout << "Good";
}

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += a[i] - 1;
    }
    cout << ans << endl;
    return 0;
}



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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int N,Q; cin >> N >> Q;
    string S; cin >> S;
    VI n(N+1,0); n[1] = 0;
    REP(i,N-1){
        if(S[i+1]=='C' && S[i]=='A') n[i+2] = n[i+1]+1;
        else n[i+2] = n[i+1];
    }

    REP(i,Q){
        int l,r; cin >> l >> r;
        int ans = n[r]-n[l-1];
        if(l>1 && S[l-1]=='C' && S[l-2]=='A') ans--;
        cout << ans << endl;
    }
    return 0;
}

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

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniqueV(x)          \
  sort(x.begin(), x.end()); \
  x.erase(unique(x.begin(), x.end()), x.end());
#define debug(x) cerr << #x << ": " << x << '\n'
#define debug2(x, y) cerr << "(" << #x << ", " << #y << ") = " \
                          << "(" << x << ", " << y << ")" << '\n'

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

const long long INF = 3e18 + 12;
const int inf = 1e9;

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

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

  int a;
  cin >> a;

  vector<bool> v(a + 1);

  v[1] = 1;

  repi(i, 2, a + 1) {
    int b = i * i;
    while (b <= a) {
      debug(b);
      v[b] = 1;
      b *= i;
    }
  }

  for (int i = a; i >= 1; i--)
    if (v[i]) {
      cout << i << endl;
      return 0;
    }

  return 0;
}

Measured memory_bytes: 256