akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
//NOT TO SUBMIT IN WRONG PLACE OR BY WRONG COMPILER
//ABC 157, task c, 2020/06/24
//ms,
/*
*/

int main(void){
  int N, M;
  int tmp_s=0;
  int tmp_c=0;
  vector<int> ans(3);
  vector<int> stable(3);
  int output=0;

  cin >>N >>M;
  for(int i=0;i<N;i++){
    stable[i]=0;
    ans[i]=0;
  }

  for(int i=0;i<M;i++){
    cin >>tmp_s >>tmp_c;
    //cout <<i <<endl;
    //for(int j=0;j<N;j++) cout <<ans[j];
    //cout <<endl;
    if(stable[N-tmp_s] && ans[N-tmp_s] != tmp_c) goto NOT_EXIST;
    else if(tmp_s == 1 && tmp_c == 0 && N != 1) goto NOT_EXIST;
    else {
      ans[N-tmp_s] = tmp_c;
      stable[N-tmp_s] = 1;
    }
  }

  if(ans[N-1] == 0 && N != 1) ans[N-1] = 1;


  for(int i=0;i<N;i++){
    output += ans[i];
    for(int j=i+1;j<N;j++) ans[j] *= 10;
  }
  cout <<output <<endl;
  return 0;

  NOT_EXIST:
    cout <<-1 <<endl;
    return 0;
}
/*
*/


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

using namespace std;

int main(void) {
    string s;
    cin >> s;
    string ans;
    for(int i=0; i<s.size(); i++) {
        if(s[i] == 'B') {
            if(!ans.empty()) ans.pop_back();
        } else {
            ans.push_back(s[i]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int stack[10];
int stackLength = 0;

void push(int number) {
	stack[stackLength++] = number;
}

int pop() {
	return stack[--stackLength];
}

int main () {
	int number;
	while(scanf("%d" , &number) > 0) {
		if (number > 0) {
			push(number);
		} else {
			printf("%d\n" , pop());
		}
	}
	return 0;
}

Measured memory_bytes: 600
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define INF 1e18
#define pll pair<ll, ll> 
#define vll vector<ll>
ll n,m,a,b,c,k,temp,x,y;
const int MAXN=1e5+11,mod=1e9+7;
ll max(ll a,ll b) {return ((a>b)?a:b);}
ll min(ll a,ll b) {return ((a>b)?b:a);}
vll read(int n) {vll v(n);for (int i = 0; i < v.size(); i++)cin>>v[i];return v;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int tree[6*MAXN];
int qfst(int l,int r)
{
    int res=0;
    for(l+=300001,r+=300001;l<r;l>>=1,r>>=1)
    {
        if(l&1) res=max(tree[l++],res);
        if(r&1) res=max(tree[--r],res);
    }
    return res;
}
void modify(int p, int value) 
{ 
for (tree[p += 300001] = value; p > 1; p >>= 1)
tree[p >> 1] = max(tree[p], tree[p ^ 1]);
}
void sol(void)
{
cin>>n>>k;
vll v=read(n);
for(int i=0;i<n;i++)
{
    int mx=qfst(v[i],v[i]+1);
    int ending=qfst(max(0,v[i]-k),min(v[i]+k+1,300001))+1;
    modify(v[i],max(mx,ending));
}
cout<<qfst(0,300001);
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test=1;
    //cin>>test;
    for(int i=1;i<=test;i++)
    sol();
}


Measured memory_bytes: 7948
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const array<pair<int,int>,4> fd{make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

ll gcd(ll a, ll b){
  if(b > a)swap(a, b);
  if(b == 0)return a;
  return gcd(b, a%b);
}

ll lcm(ll a, ll b){
  ll g = gcd(a,b);
  return a/g*b;
}

int main(){
  int n;cin>>n;
  ll l;cin>>l;
  rep(i,n-1){
    ll o;cin>>o;
    l = lcm(l,o);
  }
  cout << l << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

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

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

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

ll prod(ll b, ll e) {
    ll ans = 1;
    while (e) {
        if (e&1) ans *= b;
        ans %= MOD;
        e >>= 1;
        b *= b;
        b %= MOD;
    }
    return ans;
}

vector<ll> fact(2010), factinv(2010);

ll comb(int n, int k) {
    ll ans = fact[n];
    ans = ans * factinv[n-k] % MOD;
    ans = ans * factinv[k] % MOD;
    return ans;
}

void pp() {
    fact[0] = 1;
    for (int i=1;i<=2000;i++) fact[i] = fact[i-1]*i % MOD;
    factinv[0] = 1;
    factinv[1] = 1;
    for (int i=2;i<=2000;i++) factinv[i] = prod(fact[i],MOD-2);
}

int main(void) {
    int N, K;
    cin >> N >> K;
    pp();
    for (int i=1;i<=K;i++) {
        if (i > N-K+1) {
            cout << 0 << endl;
        } else {
            ll ans = comb(N-K+1,N-K-i+1);
            ans = ans * comb(K-1,K-i) % MOD;
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
//#include <cstdio>
#include <iostream>

#include <cstring>

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cassert>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define MAXN 21
int N;
int A[MAXN][MAXN];

const int MOD = 1e9 + 7;
int memo[1<<MAXN];
int go(int n = 0, int mask = 0) {
   if (n == N)
      return 1;
   int& res = memo[mask];
   if (res < 0) {
      res = 0;
      REP(j, N) {
         if (mask & (1<<j)) continue;
         if (!A[n][j]) continue;
         res += go(n+1, mask | (1<<j));
         if (res >= MOD)
            res -= MOD;
      }
   }
   return res;
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   cin >> N;
   REP(i, N)
      REP(j, N)
         cin >> A[i][j];

   memset(memo, -1, sizeof(memo));
   int res = go();
   cout << res << '\n';

   return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());
#define vecmin(A) *min_element(A.begin(),A.end());
#define vecmax(A) *max_element(A.begin(),A.end());
typedef long long ll;

int main(){
  int n,m;
  cin >> n >> m;
  vector<string> a(n),b(m);
  rep(i,n) cin >> a[i];
  rep(i,m) cin >> b[i];
  rep(i,n-m+1){
    rep(j,n-m+1){
      bool fail_at_least = 0;
      rep(k,m){
        rep(l,m){
          if(a[i+k][j+l] != b[k][l]){
            fail_at_least = 1;
          }
        }
      }
      if(fail_at_least == 0){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    group = {}
    city = []
    for i in range(n):
        s, p = input().split()
        if s not in city:
            city.append(s)
        if s in group:
            group[s].append([int(p), i + 1])
        else:
            group[s] = [[int(p), i + 1]]
    city.sort()
    for c in city:
        group[c].sort(key=lambda x: x[0], reverse=True)
        for _, n in group[c]:
            print(n)


if __name__ == '__main__':
    main()



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;

string s;

void read(){
  cin >> s;
}

void solv(){
  int n = s.size();
  int res0 = 0, res1 = 0;
  for(int i = 0; i < n; i++){
    if((i + s[i]) & 1)  res0++;
    else res1++;
  }

  cout << min(res0, res1) << '\n';
}

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

  read();
  solv();

  return 0;
}


Measured memory_bytes: 512
package main

import (
	"fmt"
)

func main() {
	// scan starts
	var s int
	fmt.Scan(&s)

	nums := []int{s}
	answer := -1
	for i := 1; true; i++ {
		// current num
		prev := nums[i-1]
		a := prev / 2
		if prev%2 != 0 {
			a = prev*3 + 1
		}

		// find answer
		for _, num := range nums {
			if num == a {
				// answer found
				answer = i + 1
				break
			}
		}

		if answer != -1 {
			break
		} else {
			nums = append(nums, a)
		}
	}

	fmt.Println(answer)
}


Measured memory_bytes: 512
n = int(input())
talk = [input() for i in range(n)]
a = 0
judge = True
for s in talk:
    if s == "A":
        a += 1
    else:
        if a == 0:
            judge = False
        else:
            a -= 1
if a > 0:
    judge = False

if judge:
    print("YES")
else:
    print("NO")


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

using namespace std;

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

  int N; cin>>N;
  string S; cin>>S;

  std::vector<size_t> posmap[10];
  for (int i = 0; i < N; i++) {
    int n = S[i] - '0';
    posmap[n].push_back(i);
  }
  auto find = [&](int n, int t) {
    int l = 0, r = posmap[n].size();
    int a = N;
    while (l < r) {
      int c = (l+r)/2;
      if (posmap[n][c] >= t) {
        r = c;
        a = posmap[n][c];
      } else {
        l = c+1;
      }
    }
    return a < N ? a : -1;
  };
  size_t ans = 0;
  for (int i = 0; i < 10; i++) {
    int p1 = find(i, 0);
    if (p1 == -1)
      continue;
    for (int j = 0; j < 10; j++) {
      int p2 = find(j, p1+1);
      if (p2 == -1)
        continue;
      for (int k = 0; k < 10; k++) {
        int p3 = find(k, p2+1);
        if (p3 == -1)
          continue;
        ans++;
//        cerr << i << j << k << endl;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


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

ll com(ll N, ll K, ll M) {
  ll a = 1, b = 1, c = 1, d = 1;
  for (ll h = 1; h <= N; h++) a= (a*h)%M;
  for (ll i = 1; i <= N-K; i++) b = (b*i)%M;
  for (ll j = 1; j <=K; j++) c = (c*j)%M;
  ll e = (b*c)%M, m_ = M-2;
  while(m_ != 0) {
    if (m_&1) d = (d*e)%M;
    e = e*e%M;
    m_ = m_ >> 1;
  }
  return (a*d)%M;
}

int main() {
  const ll mod = 1000000007;
  ll X,Y;
  cin >> X >> Y;
  const bool can_go = (Y <= 2*X && 2*Y >= X && (X+Y)%3 == 0);
  if (!can_go) cout << 0 << endl;
  else {
    ll ans = 0;
    ll m = (X+Y)/3;
    ll up2 = (2*X-Y)/3;
    cout << com(m,up2,mod) << endl;
  } 
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

using Graph = vector<vector<int>>;

int main(){
	int n, m; cin >> n >> m;
	int a[1010];
	int b = 0, sum = 0;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
	}
	rep(i, n)if(a[i] * 4 * m >= sum) b++;
	Yes(b >= m);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rng(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int MOD=1000000007;

int main() {
  string s;
  cin >> s;
  int n=s.size();
  vector<int> a(n);
  int cnt=0;
  rep(i,n-1) {
    while(s[i]=='R') {
      cnt++;  i++;
    }
    a[i-1]+=(cnt+1)/2;
    a[i]+=cnt/2;
    cnt=0;
  }
  for(int j=n-1; j>0; j--) {
    cnt=0;
    while(s[j]=='L') {
      cnt++; j--;
    }
    a[j]+=cnt/2;
    a[j+1]+=(cnt+1)/2;
    cnt=0;
  }
  rep(i,n) cout << a[i] << " ";
  cout << endl;
  return 0;
}

Measured memory_bytes: 1152
/*
tarun360
IIT Indore
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ll_s long
#define mod 1000000007
#define forn(i,start,lim) for(ll i=start;i<lim;i++)
#define forn_d(i,start,lim) for(ll i=start;i>=lim;i--)
#define forn_s(i,start,lim) for(ll_s i=start;i<lim;i++)
#define forn_d_s(i,start,lim) for(ll_s i=start;i>=lim;i--)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define debug1(a) cout<<a<<endl
#define debug2(a,b) cout<<a<<" "<<b<<endl
#define debug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define debug4(a) cout<<"chu "<<a<<endl

ll a[105];
ll dp[100005];

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  ll n,k;
  cin>>n>>k;
  forn(i,0,n) {
    cin>>a[i];
  }
  forn(i,1,k+1){
    forn(j,0,n){
      if(i-a[j]>=0)
        dp[i]=dp[i]||(1^dp[i-a[j]]);
    }
  }
  if(dp[k])
    cout<<"First";
  else
    cout<<"Second";
  cout<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

// dp[i][j] := ibit目まで見てそこまでの値がk未満で(0:ない, 1:ある)時の最大値
int dp[60][2];

signed main(){
	int n,k;
	cin >> n >> k;
	vector< int > a(n);
	for(int i=0; i<n; ++i) cin >> a[i];
	memset(dp, -1, sizeof(dp));

	dp[45][0] = 0;
	for(int bi=44; bi>=0; --bi){
		int on_bit_num = 0;
		for(int ai=0; ai<n; ++ai) {
			if ((a[ai] >> bi) & 1) ++on_bit_num;
		}
 
		int digit = (1LL << bi);
 	  if (dp[bi+1][1] >= 0) {
			dp[bi][1] = max(dp[bi][1], dp[bi+1][1] + digit*max(on_bit_num, n - on_bit_num));
		}
		if (dp[bi+1][0] >= 0) {   
			if ((k >> bi) & 1){
				dp[bi][1] = max(dp[bi][1], dp[bi+1][0] + digit*on_bit_num);
				dp[bi][0] = max(dp[bi][0], dp[bi+1][0] + digit*(n - on_bit_num));
				//cerr << "digit1" << digit << endl;
			} else {
				dp[bi][0] = max(dp[bi][0], dp[bi+1][0] + digit*on_bit_num);
				//cerr << "digit2" << digit << endl;
			}
		}
		/*
		cerr << "bi+1:" <<  dp[bi+1][0] << endl;
		cerr << "bi  :" << bi << endl;
		cerr << "on  :" << on_bit_num << endl;
		cerr << "dp-0:" << dp[bi][0] << endl;
		cerr << "dp-1:" << dp[bi][1] << endl << endl;
		*/
	}   

	int ans = max(dp[0][0], dp[0][1]);
	cout << ans << endl;
	/*
	for(int bi=41;bi>=0;--bi){
		cerr<< dp[bi][0] << " " << dp[bi][1] << endl;
	} 
	*/  
	
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
using P = pair<ll, ll>;

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

const ll MOD = 1000000007;
const int INF = 1<<29;

int main(){
  int N; cin >> N;
  string S, T; cin >> S >> T;

  string ans;
  rep(i, N) ans += S[i], ans += T[i];
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i,a,b;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n>>a>>b;
  std::vector<int> v(n);
  rep(i,n) cin>>v[i];
  ll left = 1,right = 1e9;
  while(left != right){
    ll mid = (left+right) / 2;
    ll num = 0;
    rep(i,n){
      int need = mmax(0,v[i]-b*mid);
      num += need/(a-b) + bool(need%(b-a));
    }
    /*
    numの回数が少なかったらもう少し最低限必要な魔法の回数の上限を下げることが出来て、
    numの回数が多かったらもう少し最低限必要な魔法の回数の下限をあげる必要がある
    */
    if(num <= mid) right = mid;
    else left = mid + 1 ;
  }
  cout<<left<<endl;
  
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 640
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, K = read_int()

def solve():
    if K == 1:
        return 0
    ans = N - K
    return ans

if __name__ == "__main__":
    print(solve())

Measured memory_bytes: 3952
#include<iostream>
#include<queue>
using namespace std;
static const int N = 100;
static const int INFTY = (1<<21);

int n, M[N][N];
int d[N];

void bfs(int s){
  queue<int> q;
  q.push(s);
  for(int i=0;i<n;i++) d[i] = INFTY;
  d[s] = 0;
  int u;
  while(!q.empty()){
    u = q.front();
    q.pop();
    for(int v=0;v<n;v++){
      if(M[u][v]==0) continue;
      if(d[v]!=INFTY) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  for(int i=0;i<n;i++){
    cout << i+1 << " " << ((d[i]== INFTY)?(-1):d[i]) << endl;
  }
}

int main(){
  int u,k,v;
  cin >> n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      M[i][j] = 0;
    }
  }
  for(int i=0;i<n;i++){
    cin >> u >> k;
    u--;
    for(int j=0;j<k;j++){
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }
  bfs(0);
  return 0;
}


Measured memory_bytes: 3120
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>
#include <cstdlib>
#include <cstdio>

#define INF_LL 1e18
#define INF 1e9+7

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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

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

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

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

int main(void){
	ll N, A, B;
	ll X[100010];
	ll res = 0;
	cin >> N >> A >> B;
	REP(i, N){
		cin >> X[i];
	}
	REP(i, N-1){
		if((X[i+1]-X[i])*A < B)
			res += (X[i+1]-X[i])*A;
		else
			res += B;
	}
	cout << res << endl;
}


Measured memory_bytes: 1152
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){ 
    int n, h, w; cin >> n >> h >> w;
    int cnt = 0;
    rep(i, n){
        int a, b; cin >> a >> b;
        if(a>=h && b>=w)cnt++;
    }
    cout << cnt << ln;
}


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

int main()
{
    string s;
    int fans=0,sans=0;
    cin>>s;
    
    //0101...
    for(int i=0;i<s.length();i++)
    {
        if(i%2==0&&s[i]=='0') fans++;
        if(i%2!=0&&s[i]=='1') fans++;
    }
    //1010...
    for(int i=0;i<s.length();i++)
    {
        if(i%2==0&&s[i]=='1') sans++;
        if(i%2!=0&&s[i]=='0') sans++;
    }

    cout<<(fans<sans ? fans:sans)<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int N;
    cin >> N;
    VI a(N);
    REP(i, N) {
        cin >> a[i];
    }

    map<int, int> mp;
    REP(i, N) {
        if (mp.size() == 0) {
            mp[a[i]]++;
            continue;
        }
        auto itr = mp.lower_bound(a[i]);
        if (itr != begin(mp)) {
            itr = prev(itr);
            if (itr->first < a[i]) {
                if (--itr->second == 0) {
                    mp.erase(itr);
                }
            }
        }
        mp[a[i]]++;
    }

    int ans = 0;
    FORE(e, mp) ans += e.second;
    cout << ans << endl;
}


Measured memory_bytes: 5248
from collections import deque

H, W = map(int, input().split())
s_l = [input() for _ in range(H)]
dist = [(-1, 0), (1, 0), (0, -1), (0, 1)]
results = [[0 for _ in range(W)] for _ in range(H)]
results[0][0] = 1

queue = deque()
queue.append((0, 0))

while queue:
    y, x = queue.popleft()
    if H - 1 == y and W - 1 == x:
        break
    for dy, dx in dist:
        ny = y + dy
        nx = x + dx
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if s_l[ny][nx] != "#" and results[ny][nx] == 0:
            results[ny][nx] = results[y][x] + 1
            queue.append((ny, nx))

ans = 0
if results[H - 1][W - 1] == 0:
    ans = -1
else:
    ans = sum([s.count(".") for s in s_l]) - results[H - 1][W - 1]

print(ans)


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

using namespace std;

const int INF = 0x7FFFFFFF;

// ST {{{
struct ST{

    // RMinQ
    // 0-indexed
    //
    // Number, datA, Delay(lazy)
    // TODO develop delay
    int N;
    vector<int> A;
    vector<int> D;

    ST( int _N ):N(_N){
        build(_N);
    }

    void build( int _N ){
        N = 1;
        while( N < _N ) N <<= 1;
        A.assign( N<<1,INF );
        D.assign( N<<1,0 );
    }

    // (a) -> x
    // Pay Attention Operator Precedence
    // (*,/,,+,-) --> (>>,<<) --> (>=,<=,,==,!=) --> (&,,^,,|) --> (&&,,||) --> ( a?b:c,+=,= )
    // example:
    //   X : A[a<<1+1]
    //   O : A[a<<1|1]
    void upd( int a, int x){
        a += N;
        A[a] = x;
        while( a >>= 1 ) {
            A[a] = min( A[a<<1|1], A[a<<1|0] );
        }
    }

    // query [l,r)
    int query(int l, int r){
        int lv = INF, rv = INF;
        for( l+=N,r+=N; l<r; l>>=1,r>>=1 ){
            if( l&1 ) lv = min( lv, A[l++] );
            if( r&1 ) rv = min( rv, A[--r] );
        }
        return min( lv,rv );
    }


};
// }}}


int main() {

    int N,Q;
    int q,l,r,a,x;

    scanf("%d %d", &N, &Q );

    ST st(N);
    for (int i = 0; i < Q; i++){
        scanf("%d", &q );
        if( q ){
            scanf("%d %d", &l, &r);
            printf( "%d\n", st.query(l,++r) );
        }else{
            scanf("%d %d", &a, &x);
            st.upd( a,x );
        }
    }

    return 0;
}




Measured memory_bytes: 4952
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Joy
 */

#include <bits/stdc++.h>
#define REP(i, N) for (ll i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define INF 1e9
#define INFL 1e18
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

class CRally {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int N;
	    in >> N;
	    int X[N];
	    REP(i, N) in >> X[i];
	    sort(X, X+N);
	    int ans = INF;
	    REP(i, 101) {
	        int sum = 0;
	        REP(j, N) {
	            sum += (X[j] - i) * (X[j] - i);
	        }
	        ans = min(ans, sum);
	    }
	    out << ans << '\n';
	}
};


int main() {
	CRally solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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


int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s1;
    cin>>s1;
    string s2=s1;
    reverse(s2.begin(),s2.end());
//    cout<<s2<<"\n";
    int n=s1.length();
    if(s1==s2){
        int p1=(n-1)/2;
        
        string s3=s1.substr(0,p1);
        string s5=s3;
        reverse(s5.begin(),s5.end());
//        cout<<s3<<" "<<s5<<"\n";
        if(s5==s3){
            
        }else{
            cout<<"No";
            return 0;
        }
        
        int p2=(n+3)/2;
        string s4=s1.substr(p2-1);
        string s6=s4;
        reverse(s6.begin(),s6.end());
    //    cout<<s4<<" "<<s6<<"\n";
        if(s6==s4){
            
        }else{
            cout<<"No";
            return 0;
        }
        
        cout<<"Yes";
        return 0;
    }
    
    cout<<"No";
    

       
        
        
    
   
    
    
   
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        if(num >= 30) {
        	System.out.println("Yes");
        }
        else {
        	System.out.println("No");
        }
    }
}

Measured memory_bytes: 35676
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <stdio.h>

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	if (A > B) {
		int tmp = A;
		A = B;
		B = tmp;
	}

	long long int result = B;
	while (1) {
		if (result%A == 0) {
			break;
		}
		result += B;
	}

	cout << result << endl;

	return 0;
}

Measured memory_bytes: 256
from collections import deque

def main():
    s = input()
    q = int(input())

    Q = deque(s)
    rev = False
    for i in range(q):
        tfc = input().split()

        if tfc[0] == '1':
            rev = not rev
        else:
            f = tfc[1]
            c = tfc[2]
            if (f == '1' and not rev) or (f != '1' and rev):
                Q.appendleft(c)
            else:
                Q.append(c)

    if rev:
        print(''.join(list(Q)[::-1]))
    else:
        print(''.join(Q))

if __name__ == "__main__":
    main()


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

using namespace std;

#define int long long
//#define cerr if(false)cerr
#define watch(x) cerr << (#x) << " is " << (x) << endl
#define faster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define cint int t;cin>>t;while(t--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int>
#define all(v) (v).begin(), (v).end()
#define pii pair<int,int>
#define pb push_back
#define N 100005
#define mm0(X) memset((X), 0, sizeof((X)))
#define mm1(X) memset((X), -1, sizeof((X)))
int mod=998244353;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
int powmod(int a,int b) {int res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define mp make_pair

int32_t main() {
    faster;

    int n; cin>>n;

    string s;
    cin>>s;

    int a[n]={};
    int b[n]={};
    int c[n]={};
    a[0]=(s[0]=='R');
    b[0]=(s[0]=='G');
    c[0]=(s[0]=='B');

    for(int i=1;i<n;i++){
//        if(s[i]=='R'){
            a[i]=a[i-1]+(s[i]=='R');

//        if(s[i]=='G'){
            b[i]=b[i-1]+(s[i]=='G');
//        }
//        if(s[i]=='B'){
            c[i]=c[i-1]+(s[i]=='B');
//        }
//        cout<<c[i]<<" ";
    }
//    cout<<endl;
    int ans=0;
//    cout<<c[2]<<" ";
    for(int i=0;i<n;i++){
        int tmp=0;

        for(int j=i+1;j<n-1;j++){
            tmp=0;
            if(s[i]==s[j]) continue;
            else{
                if(s[i]=='R'&&s[j]=='G'){
                    tmp=c[n-1]-c[j];
                    if(2*j-i<n&&2*j-i>j){
                        if(s[2*j-i]=='B') tmp--;
                    }
                }
                if(s[i]=='G'&&s[j]=='R'){
                    tmp=c[n-1]-c[j];
                    if(2*j-i<n&&2*j-i>j){
                        if(s[2*j-i]=='B') tmp--;
                    }
                }
                if(s[i]=='R'&&s[j]=='B'){
                    tmp=b[n-1]-b[j];
                    if(2*j-i<n&&2*j-i>j){
                        if(s[2*j-i]=='G') tmp--;
                    }
                }
                if(s[i]=='B'&&s[j]=='R'){
                    tmp=b[n-1]-b[j];
                    if(2*j-i<n&&2*j-i>j){
                        if(s[2*j-i]=='G') tmp--;
                    }
                }
                if(s[i]=='B'&&s[j]=='G'){
                    tmp=a[n-1]-a[j];
                    if(2*j-i<n&&2*j-i>j){
                        if(s[2*j-i]=='R') tmp--;
                    }
                }
                if(s[i]=='G'&&s[j]=='B'){
                    tmp=a[n-1]-a[j];
                    if(2*j-i<n&&2*j-i>j){
                        if(s[2*j-i]=='R') tmp--;
                    }
                }
                ans+=tmp;
//                cout<<tmp<<" ";
            }
        }
//        ans+=tmp;
//        cout<<tmp<<" ";
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3704
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def prime_factorize(N):
    prime_list = []
    while N % 2 == 0:
        prime_list.append(2)
        N //= 2
    f = 3
    while f**2 <= N:
        if N % f == 0:
            prime_list.append(f)
            N //= f
        else:
            f += 2
    if N != 1:
        prime_list.append(N)
    return prime_list

def main():
    N, K = map(int, input().split())
    if K == 0:
        print(N*N)
        exit()
    ans = 0
    for i in range(1,N+1):
        if i <= K:
            ans += N
        else:
            ans += K * (N//i) + min(K,N%i+1) - 1
        # print(ans)
    print(N*N - ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9412
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define str string
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define eps 1e-6
#define pi atan(1) * 4
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000000
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define FORl(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORDl(i, a, b) for (ll i = (a); i >= (b); i--)
using namespace std;
bool np[1000005];
vector<int> prime;
void sieve (int n) {
  FOR(i, 2, n) {
    if (np[i]) continue;
    prime.pb(i);
    for (ll j = 1LL * i * i; j <= n; j += i) np[j] = 1;
  }
}
int main () {
  ll n;
  scanf("%lld", &n);
  sieve(sqrt(n));
  int ans = 0;
  for (int p : prime) {
    if (p > sqrt(n)) break;
    int cnt = 0;
    while (n % p == 0) ++cnt, n /= p;
    for (int i = 1; cnt >= i; cnt -= i, ++i) ++ans;
  }
  if (n > 1) ++ans;
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 4908
from itertools import accumulate
from sys import stdin


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)

    def __sub__(self, other):
        return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)

    def __mul__(self, other):
        return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)

    def __truediv__(self, other):
        return (
            ModInt(self.x * pow(other.x, MOD - 2, MOD))
            if isinstance(other, ModInt)
            else ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, MOD))

    __radd__ = __add__

    def __rsub__(self, other):
        return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(other.x * pow(self.x, MOD - 2, MOD))
            if isinstance(other, ModInt)
            else ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, MOD))


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split()))

    a_ = map(ModInt, A)
    arr = list(accumulate(a_))
    ans = 0
    for i in range(N - 1):
        ans += A[i] * (arr[-1] - arr[i])
    print(ans)


MOD = 1000000007
main()


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

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

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

int main() {
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for (int i = 0; i < n*(n-1)/2; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(c > d) swap(a, b);
        if(c == d) v[a-1]++, v[b-1]++;
        else v[b-1] += 3;
    }
    vector<int> v2 = v;
    sort(v2.begin(), v2.end(), greater<>());
    for (int i = 0; i < n; ++i) {
        cout << lower_bound(v2.begin(), v2.end(), v[i], greater<>()) - v2.begin() + 1 << "\n";
    }
    return 0;
}



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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

int n,m,a,b;
vector<int> v[100001];
deque<int> ans;
bool visited[100001];

void kr(int k, bool f) {
    visited[k] = true;
    for(auto i : v[k]) {
        if (!visited[i]) {
            if (f) ans.push_front(i);
            else ans.push_back(i);
            kr(i,f);
            return;
        }
    }
}


signed main() {
    cin >> n >> m;
    rep(i,m) {
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    ans.pb(1);
    kr(1,false);
    kr(1,true);
    cout << ans.size() << endl;
    for(auto i : ans) cout << i << " ";cout << endl;
}




Measured memory_bytes: 11520
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())

# DP = [["s", "r", "p"] for _ in range(N + 1)]

res = 0
p = 0
commands = []
for i, t in enumerate(T):
    if t == 'r':
        commands.append('p')
        p = P
    elif t == 's':
        commands.append('r')
        p = R
    else:
        commands.append('s')
        p = S

    if (i - K) >= 0 and commands[i - K] == commands[i]:
        p = 0
        commands[i] = 'x'

    res += p

print(res)


Measured memory_bytes: 4792
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<deque>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<list>
#define For(i,a,b) for(int i=(a); i<=(b) ; i++)
#define _For(i,a,b) for(int i=(a); i>=(b) ; i--)
#define Memset(a,b); memset((a),(b),sizeof((a)));
#define Cout(a,b);  printf("%d",(a));printf(b);
#define Coutc(a,b);  printf("%c",(a));printf(b);
#define Couts(a,b);  printf("%s",(a));printf(b);
using namespace std;
const int INF = 0x3f3f3f3f;
typedef  long long LL;typedef  unsigned long long ULL;typedef  long double LDB;
inline LL CinLL(){LL x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline int Cin(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;}
int main()
{
	ios::sync_with_stdio(false);
	LL n,m;	cin>>n>>m;
	if(n == 1 && m == 1)
	{
		cout<<1<<endl;
		return 0;
	}
	else if(n==1 || m==1)
	{
		cout<<max(n,m)-2<<endl;
		return 0;
	}

	cout<<(n-2)*(m-2)<<endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>


using namespace std;

const int INF = 1000000001;
const int MAX = 2000000;
int N;
long int cnt;
int S[MAX] = {0}, L[1 + MAX/2] = {0}, R[1 + MAX/2] = {0};

void merge(int* A,int left,int mid,int right)
{
	int n1,n2,i,j;
	n1 = mid - left;
	n2 = right - mid;

	for(int i = 0; i < n1; i++)
	{
		L[i] = A[left + i];
		//cout << " L[i] = " << L[i];
	}
	for(int i = 0; i < n2; i++)
	{
		R[i] = A[mid + i];
		//cout << " R[i] = " << R[i];
	}

	L[n1] = INF;
	R[n2] = INF;

	i = 0;
	j = 0;

	for(int k = 0; k < right - left; k++)
	{
		if (L[i] <= R[j] )
		{
			A[left + k] = L[i];
			i++;
		}else
		{
			A[left + k] = R[j];
			j++;
			if (L[i] != INF)
			{
				cnt += n1 - i ;
				//cout << " cnt= " << cnt;
			}
		}
	}

	//cout << endl;
}


void mergesort(int* A,int left,int right)
{
	int mid;

	if(left + 1 < right)
	{
		mid = (left + right) / 2;
		mergesort(A,left,mid);
		mergesort(A,mid,right);
		merge(A,left,mid,right);
	}
}


int main()
{
	cnt = 0;

	scanf("%d", &N);

	for(int i = 0; i < N; i++)
	{
		scanf("%d", &S[i]);
		
	}

	mergesort(S,0,N);
	

	printf("%ld\n", cnt);
	
	return 0;
}
	

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

int main()
{
  int N, K;
  cin >> N >> K;
  
  int cnt = 0;
  int d[K];
  int A[K][N];
  int B[N] = {0};
  for(int i = 0; i < K; i++)
  {
    cin >> d[i];
    for(int j = 0; j < d[i]; j++)
    {
      cin >> A[i][j];
    }
  }
  
  int ans = 0;
  for(int i = 0; i < K; i++)
  {
    for(int j = 0; j < d[i]; j++)
    {
      B[A[i][j] - 1]++;
    }
  }
  for(int i = 0; i < N; i++)
  {
    if(B[i] == 0)
    {
      ans++;
    }
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#include <deque>
#include <list>
#include <stack>
#include <queue>
typedef long long ll;
typedef long double ld;

#define REP(i,s,n)for(ll i=s;i<(n);++i)
#define rep(i,n) REP(i,0,n)
using namespace std;
int S[1000] = { 0 };


int main() {
	ll N,Q;
	cin >>N>>Q;
	queue<ll>Y[N];
	rep(i, Q) {
		int a;
		cin >> a;
		if (a == 0) {
			int b,c;
			cin >> b>>c;
			Y[b].push(c);
		}
		else if (a == 1) {
			int b;
			cin >> b;
			if (0 < Y[b].size()) cout << Y[b].front() << endl;
		}
		else {
			int b;
			cin >> b;
			if (0 < Y[b].size()) Y[b].pop();
		}
	}
	return 0;
}





Measured memory_bytes: 5156
COUNT=$(cat - |\
  sed 1d |\
  tr ' ' '\n' |\
  factor |\
  cut -d ' ' -f2-|\
  egrep '2( |$)' |\
  egrep -v '(^| )3( |$)' |\
  egrep -v '(^| )5( |$)' |\
  wc -l )

[ $COUNT -eq 0 ] && echo APPROVED || echo DENIED


Measured memory_bytes: 3104
#include<bits/stdc++.h>
clock_t t=clock();
namespace IO
{
	using namespace std;
	char buf[1<<22],Out[1<<22],*p1=buf,*p2=buf;
	int p3=-1,f=0;
	inline void file()
	{
		#ifdef NTFOrz
		freopen("file.in","r",stdin);
		#endif
	}
	inline char getchar()
	{
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
	}
	inline void flush(){fwrite(Out,1,p3+1,stdout),p3=-1;}
	inline void check(){if (p3>(1<<21)) flush();}
	inline void putchar(char a){Out[++p3]=a;check();}
	inline void putline(string s)
	{
		int tmp=p3;
		while (p3-tmp<s.size()) putchar(s[p3-tmp]);
		putchar('\n');
	}
	inline char gc()
	{
		char c=getchar();
		while (!c||c=='\n'||c==' ') c=getchar();
		return c;
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		printf("%dms\n",clock()-t);
		#endif
	}
}
namespace my_std
{
	using namespace std;
	#define getchar IO::getchar
	#define putchar IO::putchar
    #define Re register
    #define rep(i,a,b) for (Re int i=(a);i<=(b);i++)
    #define drep(i,a,b) for (Re int i=(a);i>=(b);i--)
    #define repv(i,v) for (Re int i=0;i<v.size();i++)
    #define go(u) for (Re int i=head[(u)];i;i=e[i].nxt)
    #define writesp(x) write(x),putchar(' '),IO::check()
    #define writeln(x) write(x),putchar('\n'),IO::check()
    #define mem(x,v) memset(x,v,sizeof(x))
    #define pb push_back
    #define fir first
    #define sec second
    #define MP make_pair
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    const int INF=0x7fffffff;
    inline int read()
    {
        ll sum=0,f=0;char c=getchar();
        while (!isdigit(c)) f|=(c=='-'),c=getchar();
        while (isdigit(c)) sum=(sum<<1)+(sum<<3)+(c^48),c=getchar();
        return f?-sum:sum;
    }
    void write(int k)
    {
        if (k<0) putchar('-'),k=-k;
        if (k>=10) write(k/10);
        putchar(k%10+48);
    }
	#define templ template<typename T>
    templ inline void chkmax(T &x,T y){if (x<y) x=y;}
    templ inline void chkmin(T &x,T y){if (x>y) x=y;}
}
using namespace my_std;
const int N=100010;
int n,m,ecnt,head[N],siz,flag,path,cnt[5],col[N];
ll ans;
struct edge{int to,nxt,dis;}e[N<<1];
inline void add_edge(int u,int v,int w){e[++ecnt].to=v,e[ecnt].nxt=head[u],e[ecnt].dis=w,head[u]=ecnt;}
inline int add(int x,int y){return x+y>=3?x+y-3:x+y;}
void dfs(int u)
{
	siz++,cnt[col[u]]++;
	go(u)
	{
		int v=e[i].to;
		path+=(e[i].dis==1);
		if (col[v]==INF)
		{
			col[v]=add(col[u],e[i].dis);
			dfs(v);
		}
		else if (col[v]!=add(col[u],e[i].dis)) flag=1;
	}
}
int main()
{
	IO::file();
	n=read(),m=read();
	rep(i,1,n) col[i]=INF;
	rep(i,1,m)
	{
		int u=read(),v=read();
		add_edge(u,v,1),add_edge(v,u,2);
	}
	rep(i,1,n) if (col[i]==INF)
	{
		siz=flag=path=col[i]=0;
		memset(cnt,0,sizeof(cnt));
		dfs(i);
		if (!flag)
		{
			if (cnt[0]&&cnt[1]&&cnt[2]) ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
			else ans+=path;
		}
		else ans+=1ll*siz*siz;
	}
	cout<<ans<<endl;
	IO::flush();
	IO::chktime();
	return 0;
}

Measured memory_bytes: 12592
import numpy as np
a = []
for _ in range(3):
    a.append(list(map(int, input().split())))
a = list(np.array(a).flatten())
N = int(input())
index = []
for _ in range(N):
    b_i = int(input())
    if b_i in a:
        index.append(a.index(b_i))
for i in sorted(index):
    if 0 in index and 1 in index and 2 in index:
        print("Yes")
        exit()
    elif 0 in index and 3 in index and 6 in index:
        print("Yes")
        exit()
    elif 0 in index and 4 in index and 8 in index:
        print("Yes")
        exit()
    elif 1 in index and 4 in index and 7 in index:
        print("Yes")
        exit()
    elif 2 in index and 5 in index and 8 in index:
        print("Yes")
        exit()
    elif 2 in index and 4 in index and 6 in index:
        print("Yes")
        exit()
    elif 3 in index and 4 in index and 5 in index:
        print("Yes")
        exit()
    elif 6 in index and 7 in index and 8 in index:
        print("Yes")
        exit()
print("No")

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

string s;
char a = '0',  b = '1';

int main()
{
    cin >> s;
    int res1 = 0, res2 = 0;
    for (int i = 0; i < s.length(); i++) {
        res1 += s[i] != a;
        res2 += s[i] != b;
        swap(a, b);
    }
    printf("%d\n", min(res1, res2));
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;

ll pow(int n, int p)
{
    ll tmp = 1;
    for(int i = 0; i < p; i++){
        tmp *= n;
    }
    return tmp;
}

int main()
{
    int n;
    cin >> n;
    if(n % 2 == 0){
        cout << n/2;
    }else{
        cout << n/2+1;
    }
}

Measured memory_bytes: 256
n = int(input())
d = sorted(list(map(int, input().split())) + [0])

bit, cnt = [0] * 24, 1
for num in d:
    bit[((num - 12) * cnt + 12) % 24] += 1
    cnt *= -1

if any(i > 1 for i in bit):
    print(0)
    exit()
ans = [i for i, li in enumerate(bit * 2) if li == 1]
s = min(ans[i] - ans[i - 1] for i in range(1, len(ans)))
print(s)


Measured memory_bytes: 62028
n, m = map(int,input().split())
f = [False for _ in range(n)]
c = [1 for _ in range(n)]
f[0] = True
for i in range(m):
  x, y = map(int,input().split())
  f[y - 1] = f[y - 1] or f[x - 1]
  c[y - 1] += 1
  c[x - 1] -= 1
  if c[x - 1] == 0:
    f[x - 1] = False
ans = 0
for i in range(n):
  if f[i] and c[i] > 0:
    ans += 1
print(ans)


Measured memory_bytes: 4656