akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << 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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

struct Edge {
  int to;
  int id;
  Edge(int to, int id) : to(to), id(id) {}
};

vector<vector<Edge>> g(55);

vector<int> es;
bool dfs(int v, int tv, int p=-1) {
  if (v == tv) {
    es.clear();
    return true;
  }
  for (Edge e : g[v]) {
    if (e.to == p) { continue; } // skip parent
    if (dfs(e.to, tv, v)) {
      es.push_back(e.id);
      return true;
    }
  }
  return false;
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n, m;
  cin >> n;
  rep(i, n-1) {
    int a, b;
    cin >> a >> b;
    --a; --b; // 0-indexed
    g[a].emplace_back(b, i);
    g[b].emplace_back(a, i);
  }

  cin >> m;
  vector<ll> eset(m); // The edge set for each condition
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    --a; --b; // 0-indexed
    dfs(a, b);
    for (int e : es) {
      eset[i] |= 1ll << e;
    }
  }

  ll ans = 0;
  rep(i, 1<<m) {
    ll mask = 0; // represents the white edges.
    rep(j, m) {
      if (i>>j & 1) {
        mask |= eset[j];
      }
    }
    int white = __builtin_popcountll(mask);
    ll now = 1ll << (n-1-white);
    // Calculate the count by Exclusion principle.
    if (__builtin_popcountll(i) % 2 == 0) { // even. plus.
      ans += now;
    } else { // odd. minus.
      ans -= now;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    ll N;
    cin >> N;
    // 10^N - 9^N - 9^N + 8^N
    ll a, b, c;
    ll m = 1000000000+7;
    a = b = c = 1;
    for (int i = 0; i < N; i++) {
        a *= 10, b *= 9, c *= 8;
        a %= m, b %= m, c %= m;
    }
    cout << ((a+c-b-b) % m + m + m) % m << endl;
}

Measured memory_bytes: 3648
##Just for prctice
n=int(input())
d,x=map(int,input().split())
sum=0
for k in range(n):
    a=int(input())
    i=1
    while a*(i-1)+1<=d:
        sum+=1
        i+=1

print(sum+x)

"""
3
7 1
2
5
10

8

2
8 20
1
10

29

5
30 44
26
18
81
18
6

56
"""




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

typedef long long ll;
int n;
int a[102][3];
int mx=0;
void calc(int sum,int idx,bool top){
    //cout<<idx<<' '<<sum<<' '<<top<<endl;
    if(!top&&idx>=n){
        mx=max(mx,sum);
        return;
    }
    if(idx>=n)return;
    if(top){
        calc(sum+a[idx][0]+a[idx][1],idx+1,false);
        calc(sum+a[idx][0],idx+1,true);
    }
    else{
        calc(sum+a[idx][1],idx+1,false);
    }
}

int main(){
    cin>>n;
    for(int i=0;i<2;i++){
        for(int j=0;j<n;j++){
            cin>>a[j][i];
        }
    }
    calc(0,0,true);
    cout<<mx<<endl;
    return 0;
}


Measured memory_bytes: 256
// AOJ 2149: Luck Manipulator
// 2017.11.9 bal4u@uu

#include <stdio.h>
#include <string.h>

int y[102];

int main()
{
	int n, a, b, c, x, i, j, ans;
	
	while (scanf("%d%d%d%d%d", &n, &a, &b, &c, &x) && n > 0) {
		for (i = 0; i < n; i++) scanf("%d", y+i);
		ans = -1;
		for (j = 0, i = 0; i <= 10000; i++) {
			if (y[j] == x) if (++j == n) { ans = i; break; }
			x = (a*x+b) % c;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repc(i, b, e) for(auto i = (b); i != (e); i++)

ll repsq(ll m, ll n){
    if (n == 1){
        return m % 1000000007;
    }else if(n % 2 == 0){
        ll mm = (m*m)%1000000007;
        return repsq(mm, n/2) % 1000000007;
    }
    ll mm = (m*m)%1000000007;
    return repsq(mm, n/2) * m % 1000000007;
}

int main(){
    ll m, n;
    cin >> m >> n;
    cout << repsq(m%1000000007, n) << endl;
    return 0;
}


Measured memory_bytes: 3112
#include <algorithm>
#include <cassert>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

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

    vector<set<int>> G(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].insert(b);
        G[b].insert(a);
    }

    vector<int> dists(N, -1);
    vector<int> prevs(N, -1);

    deque<tuple<int, int, int>> q;
    q.push_back(make_tuple(0, 0, 0));
    while (!q.empty()) {
        int n, d, p;
        tie(n, d, p) = q.front();
        q.pop_front();

        if (dists[n] != -1)
            continue;

        dists[n] = d;
        prevs[n] = p;

        for (int m : G[n]) {
            q.push_back(make_tuple(m, d + 1, n));
        }
    }

    vector<int> path = {N - 1};
    while (path.back() != 0) {
        path.push_back(prevs[path.back()]);
    }

    reverse(path.begin(), path.end());

    // for (int x : path)
    //     cerr << ' ' << x;
    // cerr << endl;

    static constexpr int BLACK = 0;
    static constexpr int WHITE = 1;
    static constexpr int INDET = -1;
    vector<int> colors(N, INDET);
    int nb = 0;
    int nw = 0;
    deque<int> qq;

    size_t pathsz = path.size();
    for (size_t i = 0; i < (pathsz + 1) / 2; ++i) {
        colors[path[i]] = BLACK;
        ++nb;
        qq.push_back(path[i]);
    }
    for (size_t i = (pathsz + 1) / 2; i < pathsz; ++i) {
        colors[path[i]] = WHITE;
        ++nw;
        qq.push_back(path[i]);
    }

    while (!qq.empty()) {
        int n = qq.front();
        qq.pop_front();
        int c = colors[n];

        for (int m : G[n]) {
            if (colors[m] == INDET) {
                colors[m] = c;
                if (c == BLACK)
                    ++nb;
                else
                    ++nw;
                qq.push_back(m);
            }
        }
    }

    // cerr << "nb = " << nb << endl;
    // cerr << "nw = " << nw << endl;

    assert(nb + nw == N);

    cout << (nb > nw ? "Fennec" : "Snuke") << '\n';

    return 0;
}


Measured memory_bytes: 16252
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
  int x,y,top=0;
  char s[100];
  int a[10000];
  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
      top--;
      x=a[top];
      top--;
      y=a[top];
      a[top]=x+y;
      top++;
    }
    else if ( s[0] == '-' ){
      top--;
      x=a[top];
      top--;
      y=a[top];
      a[top]=y-x;
      top++;
    }
    else if ( s[0] == '*' ){
      top--;
      x=a[top];
      top--;
      y=a[top];
      a[top]=x*y;
      top++;
    }
    else {
      x = atoi(s);
      a[top]=x;
      top++;
    }
  }

  printf("%d\n",a[top-1]);

  return 0;
}



Measured memory_bytes: 2104
#include<stdio.h>
#include<stdlib.h>

#define MAX 100004
#define NIL -1

struct Node{
  int p;
  int num;
  int depth;
  int* child;
};

struct Node T[MAX];



void depth(int d,int dep){
  T[d].depth=dep;
  int i;
  for(i=0;i<T[d].num;i++){
    depth(T[d].child[i],dep+1);
  }
}

void print(int q){

  int i;
  printf("node %d: ",q);

  printf("parent = %d, ",T[q].p);

  printf("depth = %d, ",T[q].depth);


  if(T[q].p==NIL){
    printf("root, [");
    for(i=0;i<T[q].num;i++){
      if(i) printf(", ");
	printf("%d",T[q].child[i]);
      }
    printf("]\n");
    }

  else if(T[q].p!=NIL && T[q].num!=0){
    printf("internal node, [%d",T[q].child[0]);
    for(i=1;i<T[q].num;i++){
      printf(", %d",T[q].child[i]);
    }
    printf("]\n");
  }

  else if(T[q].num==0){
    printf("leaf, []\n");
  }
}
 
int main(){
  int i,j,n,nn,z,c,b,a;

  scanf("%d",&n);

  for(i=0;i<n;i++)
    T[i].p=-1;

  for(i=0;i<n;i++){
    scanf("%d%d",&nn,&z);
    T[nn].num=z;
    T[nn].child = (int*)malloc( z * sizeof(int) );

    for(j=0;j<z;j++){
      scanf("%d",&T[nn].child[j]);
      T[ T[nn].child[j] ].p=nn;
    }
  }

  int root=0;
  for(i=0;i<n;i++)
    if(T[i].p==-1)root=i;

  depth(root,0);

  for(i=0;i<n;i++){
    print(i);
  }
  return 0;
}

Measured memory_bytes: 6468
#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
	string s; cin >> s;
	deque<char> dq;
	int len = s.length();

	for (int i = 0; i < len; ++i)
		dq.push_back(s[i]);

	int q, type; cin >> q;
	bool front = true;
	int dir;
	while (q--)
	{
		cin >> type;
		if (type == 1)  front = !front;
		else
		{
			cin >> dir >> s;
			if (front)
			{
				if (dir == 1)
				{
					dq.push_front(s[0]);
				}
				else
				{
					dq.push_back(s[0]);
				}
			}
			else
			{
				if (dir == 1)
				{
					dq.push_back(s[0]);
				}
				else
				{
					dq.push_front(s[0]);
				}
			}
		}
	}

	if (front)
	{
		while (dq.size())
		{
			cout << dq.front(); dq.pop_front();
		}
	}
	else
	{
		while (dq.size())
		{
			cout << dq.back(); dq.pop_back();
		}
	}
	return 0;
}

Measured memory_bytes: 896
N, L = [int(_) for _ in input().split()]
#L...L+N-1
if L * (L + N - 1) <= 0:
    print((2 * L + N - 1) * N // 2)
else:
    print((2 * L + N - 1) * N // 2 - min([L, L + N - 1], key=abs))


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

int main() {
    int n, a;
    cin >> n >> a;
    int count = 0;
    for (int i = 0; i <= a; i++) {
        if ((n - i) % 500 == 0) {
            count++;
            break;
        } 
    }
    if (count == 1) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
S = input()
rev_S = list(reversed(S))


while len(rev_S) >= 5:
    if rev_S[0] == "m" and rev_S[0:5] == ['m', 'a', 'e', 'r', 'd']:
        del rev_S[:5]
    elif rev_S[0] == "e" and rev_S[0:5] == ['e', 's', 'a', 'r', 'e']:
        del rev_S[:5]
    elif rev_S[0] == "r" and rev_S[0:7] == ['r', 'e', 'm', 'a', 'e','r', 'd']:    
        del rev_S[:7]
    elif rev_S[0] == "r" and rev_S[0:6] == ['r', 'e', 's', 'a','r', 'e']:    
        del rev_S[:6]
    else:
        break
if len(rev_S) == 0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3956
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

x=sum(b)-sum(a)
y=0
for i in range(n):
    if a[i]<b[i]:
        y+=-((a[i]-b[i])//2)
print("No" if x<y else "Yes")

Measured memory_bytes: 40560
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct rule {
  bool is_p;
  string src, dst;
  rule(bool is_p, string src, string dst):
    is_p(is_p), src(src), dst(dst){}
};

struct pack {
  string src, dst, msg;
  pack(string src, string dst, string msg):
    src(src), dst(dst), msg(msg){}
};

vector<rule> rules;
vector<pack> packets;

bool is_permit(string src, string dst, string msg)
{
  if (src.size() != 8 || dst.size() != 8) {
    cout << "!" << endl;
    return false;
  }
  bool permit = false;
  for (int i = 0; i < msg.size(); i++) {
    if (!isalpha(msg[i]) && !isdigit(msg[i])) {
      cout << "!!" << endl;
      return false;
    }
  }
  for (int i = 0; i < rules.size(); i++) {
    for (int j = 0; j < 8; j++) {
      if (src[j] != rules[i].src[j] && rules[i].src[j] != '?') {
	goto next;
      }
      if (dst[j] != rules[i].dst[j] && rules[i].dst[j] != '?') {
	goto next;
      }
    }
    permit = rules[i].is_p;
  next:;
  }
  return permit;
}

int main()
{
  int N, M;
  while (scanf("%d %d ", &N, &M)) {
    if (N == 0 && M == 0) {break;}
    rules.clear(), packets.clear();
    string per, src, dst;
    for (int i = 0; i < N; i++) {
      cin >> per >> src >> dst;
      cin.ignore();
      rules.push_back(rule(per == "permit", src, dst));
    }
    //reverse(rules.begin(), rules.end());
    /*    for (int i = 0; i < rules.size(); i++) {
      cout << rules[i].src << " " <<rules[i].dst << " " << endl;
      }*/
    string msg;
    int c = 0;
    for (int i = 0; i < M; i++) {
      cin >> src >> dst >> msg;
      cin.ignore();

      //cout << src << " " <<dst << " " << msg << endl;
      if (is_permit(src, dst, msg)) {
	c++;
	packets.push_back(pack(src, dst, msg));
      }
    }
    
    cout << c << endl;
    for (int i = 0; i < packets.size(); i++) {
      cout << packets[i].src << " " << packets[i].dst << " " <<
	packets[i].msg << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1088
package main

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

func solution(s string) int {
        c := 0
        out := 0
        for i := 0; i < len(s); i++ {
                if s[i] == 'B' {
                        c++
                } else {
                        out += c
                }
        }
        return out
}

func main() {
        reader := bufio.NewReaderSize(os.Stdin, 10240*10240)
        str, _, _ := reader.ReadLine()
        fmt.Println(solution(strings.TrimRight(string(str), "\r\n")))
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
double eps=1e-8;
ll mod=1e9+7;
ll inf=1e9;
priority_queue<P,vector<P>,greater<P> > pq;

template <typename T>
int Count(const vector<T> &v, T l,T r){
  //counting [l,r]
  auto L = lower_bound(v.begin(), v.end() , l );
  auto R = upper_bound(v.begin(), v.end(), r );
  // [l,r) change upper -> lower

  return R-L;
}
int n;

int cal(int l,int r){
  return r-l+1;
}

int main(){
  cin>>n;
  string t;
  int i=0,j=n;
  cout<<0<<endl<<flush;
  cin>>t;
  if(t=="Vacant")return 0;
  while(i<j){
    int m=(i+j)/2;
    if((m-i)%2==0)m++;
    cout<<m<<endl<<flush;
    string s;
    cin>>s;
    if(s=="Vacant")return 0;
    if(s!=t)i=m,t=s;
    else j=m-1;
  }
  return 0;
}

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

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

  vector<P> v(n + 1);
  rep(i, 1, n + 1) {
    cin >> a;
    v[i] = make_pair(a, i);
  }

  sort(v.begin(), v.end());
  rep(i, 1, n + 1) {
    if (i != 1) cout << " ";
    cout << v[i].second;
  }
  cout << endl;
}


Measured memory_bytes: 1536
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <climits>
#include <map>
using namespace std;

int main() {
    int a, b, c;
    
    cin >> a >> b >> c;
    
    int sum1 = a + b;
    int sum2 = b + c;
    int sum3 = c + a;
    
    int ans;
    ans = min(sum1, sum2);
    ans = min(ans, sum3);
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

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

    int ans = 0;
    for (auto i = 0; i < (int)s.size() - 2; i++) {
        if(s.substr(i, 3) == "ABC") ans++;
    }

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

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

public class Main {
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int N = sc.nextInt();
        int L = sc.nextInt();
        int[] arr = new int[N+1];
        for (int i=1; i<=N; i++) {
            arr[i] = i+L-1;
        }
        int mindist = 0x3f3f3f3f;
        int minpos = 0;
        for (int i=1; i<=N; i++) {
            if (Math.abs(arr[i])<mindist) {
                mindist = Math.abs(arr[i]);
                minpos = i;
            }
        }
        arr[minpos] = 0;
        int sum = 0;
        for (int i=1; i<=N; i++) {
            sum += arr[i];
        }
        System.out.println(sum);
    }
    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;
        }
    }
}


Measured memory_bytes: 22612
#include <stdio.h>

int main(){
  int a,b;
  scanf("%d %d", &a, &b);
  int tap = 1;
  int cnt=0;
  while(tap<b){
    tap-=1;
    tap+=a;
    cnt++;
  }
  printf("%d\n", cnt);
  return 0;
}


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

int main() {
    //Recieve the inputs
    int D, T, S;
    cin >> D >> T >> S;

    //Calculate the duration of Takahashi's journey
    double time = (double)D / S;

    //Output depending on the inequality between T and time
    if (T >= time) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define rep(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define rep_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9)+7;
const ll INF = ll(1e10);
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n) {
  vector< pair<ll, ll> > p;
  for (ll i = 2; i * i <= n; i++) {
    if ((n % i) != 0) continue;
    p.push_back(make_pair(i, 0));
    while ((n % i) == 0) {
      n /= i;
      p[i].second += 1;
    }
    p.push_back(make_pair(n, 0));
  }

  if (n != 1) p.push_back(make_pair(n, 1));
  return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a) {
	ll b = MOD, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0) { u += MOD; }
	return u;
}
// 順列
ll permutation(const ll n, const ll m) {
	ll result = 1;
	for (ll i = n; i > n - m; i--) { result = (result * i) % MOD; }
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x) {
	if (x == 0) return 1;
	ll res = repeat_square(n, x/2);
	res = res * res % MOD;
	if ((x % 2) == 1) res = res * n % MOD;
  return res;
}
// 組み合わせ
ll combination(const ll n, const ll a) {
	ll x = 1, y = 1;
  for(ll i = 0; i < a; i++){
    x = x * (n-i) % MOD;
    y = y * (i+1) % MOD;
  }
  return x * repeat_square(y, MOD-2) % MOD;
}

int result = 0;

void dfs(int N, int M, int Q, vector<int> A, map<int, vector<int> > m){
	if (A.size() == N) {
		int temp = 0;
		rep(i, Q) {
			int a = m[i][0];
			int b = m[i][1];
			int c = m[i][2];
			int d = m[i][3];
			if ((A[b-1] - A[a-1]) == c) temp += d;
		}

		if (temp > result) result = temp;
		return;
	}
	A.push_back(A.back()); // 直前の数を push（A1 <= A2 <= A3 ... An のため）
	while(A.back() <= M) {
		dfs(N, M, Q, A, m);
		A.back()++;
	}
}

int main() {
	int N, M, Q;
	map<int, vector<int> > m;
	cin >> N >> M >> Q;

	rep(i, Q) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		m[i] = vector<int>{a,b,c,d};
	}
	
	dfs(N, M, Q, vector<int> (1, 1), m);
	cout << result << endl;
  return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

ll fact[320009], invFact[320009]; 

long long power(long long x, long long c) {
    if(c==0) return 1;
    if(c==1) return x;
    if (c%2==1) return (power( (x*x)%MOD, c/2)*x)%MOD;
    else return power( (x*x)%MOD, c/2)%MOD;
}

void make_combT(ll n){
    fact[0]=1;
    rep1(i,n) fact[i]= fact[i-1]*i%MOD;
    
    invFact[n] = power(fact[n],MOD-2);
    rrep(i,n-1) invFact[i] = invFact[i+1] * (i+1) %MOD;
}

ll comb(ll n, ll m){
    return (fact[n] * invFact[m] %MOD) * invFact[n-m] %MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N, M;
    cin>>N>>M;
    
    V divisor;
    ll tmp=M;
    for(ll i=2; i*i<=M; i++){
        int cnt=0;
        while(tmp%i==0){
            cnt++;
            tmp/=i;
        }
        if(cnt){
            divisor.push_back(cnt);
            cnt=0;
        }
        if(tmp<i){
            break;
        }
    }
    
    if(tmp>1) divisor.push_back(1);
    
    make_combT(320000);
    
    ll ans=1;
    rep(i,divisor.size()){
        ans = ans * comb(divisor[i]+N-1,N-1) % MOD;
    }
    
    cout1(ans);
}

Measured memory_bytes: 5248
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  ll n,m;
  cin >> n >> m;
  vector<ll> h(n),a(m),b(m);
  vector<vector<ll>> G(n);
  for(int i=0;i<n;i++){
    cin >> h[i];
  }
  for(int i=0;i<m;i++){
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
    G[a[i]].push_back(b[i]);
    G[b[i]].push_back(a[i]);
  }
  ll ans = 0;
  for(int i=0;i<n;i++){
    bool can = true;
    for(auto nv:G[i]){
      if(h[i]<=h[nv]){
        can = false;
        break;
      }
    }
    if(can){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 11384
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};



int main(void) {
  int n;
  cin >> n;
  
  vector<double> a(n);
  rep(i,n) cin >> a[i];
  double sum = 0;
  rep(i,n) {
    a[i] = 1/a[i];
    sum += a[i];
  }
  cout << fixed << setprecision(8) << 1/sum << endl;
  
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
S = [0]*(N-1)
cnt = 0
Max = 0
for i in range(N-1):
    S[i] = H[i+1] - H[i]
for i in range(len(S)):
    if S[i] <= 0:
        cnt += 1
        if Max < cnt:
            Max = cnt
    else:
        cnt = 0
print(Max)

Measured memory_bytes: 14228
#include <algorithm>
#include <vector>
#include <deque>
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, M; 
	cin >> N >> M; 
	vector<int> E[100010] = {}; 
	int X = 0, Y = 0; 
	for(int i = 0; i < M; i++){
		int a, b; 
		cin >> a >> b; 
		E[a].push_back(b); 
		E[b].push_back(a); 
		if(i == 0){
			X = a, Y = b; 
		}
	}
	vector<int> bef = {X}; 
	vector<int> aft = {Y}; 
	bool used[100010] = {}; 
	used[X] = true; used[Y] = true; 
	for(int i = 0; i < 1145141919; i++){
		int s = bef.at(bef.size()-1); 
		bool finished = true; 
		for(int j = 0; j < E[s].size(); j++){
			if(!used[E[s].at(j)]){
				finished = false; 
				used[E[s].at(j)] = true; 
				bef.push_back(E[s].at(j)); 
				break;
			}
		}
		if(finished) break; 
	}
	for(int i = 0; i < 1145141919; i++){
		int s = aft.at(aft.size()-1); 
		bool finished = true; 
		for(int j = 0; j < E[s].size(); j++){
			if(!used[E[s].at(j)]){
				finished = false; 
				used[E[s].at(j)] = true; 
				aft.push_back(E[s].at(j)); 
				break; 
			}
		}
		if(finished) break; 
	}
	cout << bef.size() + aft.size() << endl; 
	for(int i = bef.size() - 1; i >= 0; i--){
		cout << bef.at(i) << " "; 
	}
	for(int i = 0; i < aft.size(); i++){
		cout << aft.at(i) << " "; 
	}
}

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

using ll = long long;
using ull = unsigned long long;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;(i) < ((int)(n));++(i))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline void print(T&& x){cout<<x<<endl;}// 改行付き出力
template<typename T>inline T SUM(vector<T> vec){return accumulate(all(vec),(T)0);} // vectorの中身を全部足す
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
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 ctoi(char c){return c-'0';}


// TODO: write
int main() {
  int h,w,n;cin>>h>>w>>n;
  vector<int> vH(h,0);
  vector<int> vW(w,0);
  set<pair<int,int>> hw;

  rep(i,n){
    int hi,wi;cin>>hi>>wi;
    hi--;wi--;
    vH[hi]++;
    vW[wi]++;
    hw.emplace(hi,wi);
  }

  int maxH = 0;
  int maxW = 0;
  rep(i,h)chmax(maxH,vH[i]);
  rep(i,w)chmax(maxW,vW[i]);

  vector<int> hPoint,wPoint;
  rep(i,h)if(maxH == vH[i])hPoint.push_back(i);
  rep(i,w)if(maxW == vW[i])wPoint.push_back(i);
  
  int ans = maxH + maxW - 1;

  for(int i : hPoint){
    for(int j : wPoint){
      if(!hw.count(mp(i,j))){
        print(ans+1);
        return 0;
      }
    }
  }

  print(ans);
  return 0;
}

Measured memory_bytes: 23756
// https://atcoder.jp/contests/abc116/tasks/abc116_c

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

int main() {
    int n, ans = 0;
    cin >> n;
    int h[n], w[n];
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        h[i] = tmp;
        w[i] = 0;
    }
    // 目標の高さ h、計算中の高さ w
    int i = 0;
    while (i < n) {
        if (h[i] > w[i]) {
            // 横並びの高さが現在以上なら、まとめて加算
            int j = i;
            while (j < n && h[j] > w[i]) {
                j++;
            }
            // 高さをまとめて加算
            for (int k = i; k < j; k++) {
                w[k]++;
            }
            ans++;
        } else {
            i++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int S[501][501] = { 0 };
int ans[501][501] = { 0 };

int main()
{
	int N, M, Q, L, R, p, q;

	cin >> N >> M >> Q;
	rep(i, M) {
		cin >> L >> R;
		S[L][R]++;
	}

	repc(i, 1, N) {
		repc(j, 2, N) {
			S[i][j] += S[i][j - 1];
		}
	}

	repc(i, 1, N) {
		repc(j, 1, N) {
			ans[i][j] = S[i][j];
		}
	}

	repc(i, 1, N) {
		repc(j, i + 1, N) {
			repc(k, 1, N) {
				ans[i][k] += S[j][k];
			}
		}
	}

	rep(i, Q) {
		cin >> p >> q;
		cout << ans[p][q] << endl;
	}

	return 0;
}


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

using namespace std;

int main(void)
{
	int n,r;
	cin>>n>>r;
	
	if(n >= 10) cout<<r<<endl;
	else{
		int n_rate = r + 100*(10-n);
		cout<<n_rate<<endl;
	}
	return 0;
}



Measured memory_bytes: 256
typedef long long ll;

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

int main(){
  const ll k = getInt();
  const ll a = getInt();
  const ll b = getInt();

  ll ans = k + 1;

  if(k >= a - 1){
    ll remain = k - (a - 1);
    ll tmp = a;
    tmp += (b - a) * (remain / 2);
    tmp += remain % 2;
    ans = max(ans, tmp);
  }

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

  return 0;
}

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

int main(){
  //ifstream in("input.txt");
  //cin.rdbuf(in.rdbuf());

  int N;
  cin>>N;

  vector<int> a(100002);
  for(int i=0;i<N;i++){
    int x;
    cin>>x;
    a.at(x)++;
    a.at(x+1)++;
    a.at(x+2)++;
  }
  cout<<*max_element(a.begin(),a.end())<<endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#define LL long long
#define mod 1000000007
LL sum,mn,mx;
int main()
{
    int s,w;
    scanf("%d%d",&s,&w);
    if(s<=w)
        printf("unsafe\n");
    else
        printf("safe\n");
    return 0;
}


Measured memory_bytes: 1660
#include <iostream>

using namespace std;

int main(){
    int n, x;
    int candy[100000];
    cin >> n >> x;
    for(int i=0; i<n; i++){
        cin >> candy[i];
    }
    long long int ans;
    for(int i=0; i<n-1; i++){
        int sum = candy[i] + candy[i+1];
        int tmp = sum - x;
        if(tmp <= 0)continue;
        if(tmp <= candy[i+1]){
            candy[i+1] -= tmp;
            ans += tmp;
        }else{
            candy[i] -= tmp - candy[i+1];
            ans += tmp;
            candy[i+1] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  string s;
  cin >> s;
  bool ok = true;
  rep(i, s.size()) {
    if ((i + 1) % 2 == 0) {
      if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D') ok = false;
    } else {
      if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D') ok = false;
    }
  }

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

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

using namespace std;

int main() {
    string s, buf;
    cin >> s;
    for (int i = 0; i < s.size(); ++i) {
        switch (s.at(i)) {
            case '0': buf.push_back('0'); break;
            case '1': buf.push_back('1'); break;
            case 'B': if (buf.size()) buf.pop_back(); break;
        }
    }
    cout << buf << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 10007;
static const int INF = 1 << 25;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { 1, -1, 0,  0 };
static const int dy[] = { 0,  0, 1, -1 };

int n, ans;
int dp[ 1001 ][ 8 ];
string a;
string str = "JOI";
int c[] = { 1, 2, 4 };

int solve( int now, int who ) {
	if ( now == n ) {
		return 1;
	}
	if ( dp[ now ][ who ] >= 0 ) {
		return dp[ now ][ who ];
	}
	int res = 0;
	bool s[] = { who % 2, ( who % 4 ) / 2, who / 4 };
	for ( int i = 1; i < 8; i++ ) {
		bool e[] = { i % 2, ( i % 4 ) / 2, i / 4 }, check = false;
		for ( int j = 0; j < 3; j++ ) {
			if ( s[ j ] && e[ j ] ) {
				check = true;
				break;
			}
		}
		if ( !check ) {
			continue;
		}
		if ( a[ now ] == 'J' && e[ 0 ] ) {
			res += solve( now + 1, i );
			res %= mod;
		}
		if ( a[ now ] == 'O' && e[ 1 ] ) {
			res += solve( now + 1, i );
			res %= mod;
		}
		if ( a[ now ] == 'I' && e[ 2 ] ) {
			res += solve( now + 1, i );
			res %= mod;
		}
	}
	return dp[ now ][ who ] = res;
}

int main() {
	scanf( "%d", &n );
	memset( dp, -1, sizeof( dp ) );
	cin >> a;
	ans = solve( 0, 1 );
	printf( "%d\n", ans );
	return 0;
}

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

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

    int N, M;
    cin >> N >> M;

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

    map<int, vector<int>> m;
    for(int i=0; i<M; i++){
        int tmpa, tmpb;
        cin >> tmpa >> tmpb;
        m[tmpa-1].push_back(tmpb-1);
        m[tmpb-1].push_back(tmpa-1);
    }

    int count = 0;
    for(int i=0; i<N; i++){
        bool good = true;
        for(auto x : m[i]){
            if(h[i] <= h[x]){
                good = false;
                break;
            }
        }
        if(good){
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 15004
import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer st;
    static BufferedReader br;  
    static PrintWriter out;
 
    static int parent[]; 

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = nextInt();
    
        char[] S = next().toCharArray();

        long cntR = 0; // need long for *
        long cntG = 0;
        long cntB = 0;
        
        for (int x=0; x<N; x++) {
            if(S[x]=='R') cntR++;
            if(S[x]=='G') cntG++;
            if(S[x]=='B') cntB++;
        }

        //no need, it never happen
        if(cntR*cntG*cntB==0){
            System.out.println(0);
            return;
        }

        long cnt = 0;
        for (int x=0; x<N; x++) {
            for (int y=x+1; y<N; y++) {
                int z= 2*y-x;
                if(z<N) {
                    if(S[x]!= S[y] & S[z]!= S[y] & S[x]!= S[z]){
                        cnt ++;
                    }
                }
            }
        }

        System.out.println(cntR*cntG*cntB - cnt);
        
    }
 
    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}

Measured memory_bytes: 32804
#include<bits/stdc++.h>
using namespace std;
const int MX=2002;

int N,M,Q,V[MX][MX],EC[MX][MX],EL[MX][MX];

inline int read()
{
    static int c,x;
    x=0,c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x;
}

int main()
{
    N=read(),M=read(),Q=read();
    for(int i=1;i<=N;i++,getchar())for(int j=1;j<=M;j++)
    {
        V[i][j]=getchar()-'0';
        if(V[i][j]&&V[i][j-1])EC[i][j]=1;
        if(V[i][j]&&V[i-1][j])EL[i][j]=1;
        EC[i][j]+=EC[i][j-1],EL[i][j]+=EL[i][j-1];
    }
    for(int i=2;i<=N;i++)for(int j=1;j<=M;j++)
        V[i][j]+=V[i-1][j],EC[i][j]+=EC[i-1][j],EL[i][j]+=EL[i-1][j];
    for(int i=1;i<=N;i++)for(int j=2;j<=M;j++)V[i][j]+=V[i][j-1];
    while(Q--)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        int _V=V[x2][y2]+V[x1-1][y1-1]-V[x2][y1-1]-V[x1-1][y2];
        int _E=EC[x2][y2]+EC[x1-1][y1]-EC[x1-1][y2]-EC[x2][y1];
        // cout<<"---->"<<_E<<endl;
        _E+=EL[x2][y2]+EL[x1][y1-1]-EL[x2][y1-1]-EL[x1][y2];
        // cout<<"---->"<<_E<<endl;
        printf("%d\n",_V-_E);
    }
    return 0;
}


Measured memory_bytes: 48768
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))

s = rls()
t = s[::-1]
a = 0
z = 0
for i in range(len(s)):
    if(s[i] == "A"):
        a = i
        break
for i in range(len(t)):
    if(t[i] == "Z"):
        z = len(s) - i
        break
print(z-a)

Measured memory_bytes: 6308
from collections import defaultdict

n = int(input())
A = list(int(x) for x in input().split())

count = defaultdict(int)
for a in A:
    count[a] += 1
A = sorted(set(A))

ans = 0
for a in reversed(A):
    t = a.bit_length()
    pair = 2**t - a
    if pair == a:
        ans += count[a] // 2
        count[a] -= count[a] // 2
    else:
        k = min(count[a], count[pair])
        ans += k
        count[a] -= k
        count[pair] -= k

print(ans)

Measured memory_bytes: 167860
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.lang.Math;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        int a = fs.nextInt(); int b = fs.nextInt(); int h = fs.nextInt(); int m = fs.nextInt();
        if ((2*Math.PI*((double)h/12)+((double)m/720)*2*Math.PI)>(2*Math.PI*((double)m/60))) {
            System.out.println(Math.sqrt(a*a+b*b-2*a*b*Math.cos((2*Math.PI*((double)h/12)+((double)m/720)*2*Math.PI)-(2*Math.PI*((double)m/60)))));
        } else {
            System.out.println(Math.sqrt(a*a+b*b-2*a*b*Math.cos((2*Math.PI*((double)m/60))-(2*Math.PI*((double)h/12)+((double)m/720)*2*Math.PI))));
        }

    }




    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }

}


Measured memory_bytes: 33340
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;

int N,Q;
vector<vector<Int>> G(200010);
vector<Int> cost(200010);
vector<bool> visited(200010,false);

void bfs(int s){
    queue<int> que;
    que.push(s);
    visited[s] = true;
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(auto nv:G[v]){
            if(visited[nv] == false){
                que.push(nv);
                cost[nv] += cost[v];
                visited[nv] = true;
            }
        }
    }
}

int main(){
    cin >> N >> Q;
    rep(i,N-1){
        int a,b;cin >> a >> b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(i,Q){
        int p,x;cin >> p >> x;
        p--;
        cost[p]+=x;
    }
    bfs(0);
    rep(i,N-1) cout << cost[i] << " ";
    cout << cost[N-1] << endl;
}

Measured memory_bytes: 17136
fun main(args: Array<String>) {

    val N = readInts()[0]

    var min = Long.MAX_VALUE
    for(i in 1 until N) {
        val t = sum(i) + sum(N - i)
        if (t <= min) {
            min = t
        }
    }

    println(min)
}

fun sum(i: Int): Long = i.toString().map { it.toString().toInt() }.sum().toLong()

fun readInts(): List<Int> = readStrings().map { it.toInt() }
fun readStrings(): List<String> = readLine()!!.split(" ")

Measured memory_bytes: 53096
///スマホコーディング
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  for(int i=0;i<3;i++){
    if(s[i]=='1')s[i]='9';
    else if(s[i]=='9')s[i]='1';
  }
  cout<<s<<endl;
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

mod=1000000007
def mpow2(n):
    ret=1
    while n>0:
        ret*=2
        ret%=mod
        n-=1
    return ret

def gcd(a,b):
    if a<0:
        a*=-1
    if b<0:
        b*=-1
    if a<b:
        a,b=b,a
    if a%b:
        return gcd(b,a%b)
    return b

shift=2**64
d=defaultdict(int)
n=int(input())
l=[]
cnt0=0
for i in range(n):
    a,b=map(int,input().split())
    if a==b==0:
        cnt0+=1
        continue
    elif a==0:
        b=1
    elif b==0:
        a=1
    else:
        g=gcd(a,b)
        a//=g
        b//=g
    l.append((a,b))
    d[a*shift+b]+=1
res=1
for p in l:
    a=p[0]
    b=p[1]
    c=d[a*shift+b]+d[-a*shift-b]
    if c==0:
        continue
    d[a*shift+b]=0
    d[-a*shift-b]=0
    a=-p[1]
    b=p[0]
    cc=d[a*shift+b]+d[-a*shift-b]
    d[a*shift+b]=0
    d[-a*shift-b]=0
    if cc==0:
        res*=mpow2(c)
        res%=mod
    else:
        res*=mpow2(c)+mpow2(cc)-1
        res%=mod
print((res+cnt0+mod-1)%mod)


Measured memory_bytes: 254988
#include <stdio.h>
#include <string.h>
#define MAX 21
 
void init(int);
void move(int);
 
int n, x, y;
char fld[MAX][MAX];
 
int main(void) {
    int m;
    while(~scanf("%d", &n), n) {
        init(n);
        scanf("%d", &m);
        move(m);
        printf("%s\n", n ? "No" : "Yes");
    }
    return 0;
}
 
void init(int i) {
    int a, b;
    x = y = 10;
    memset(fld, 0, sizeof(fld));
    while(i--) {
        scanf("%d %d", &a, &b);
        fld[b][a]++;
    }
}
 
void move(int i) {
    int a, d;
    char b[2];
    while(i--) {
        scanf("%1s %d", b, &a);
        while(a--) {
            *(*b % 75 > 10 ? &x : &y) += *b < 80 ? 1 : -1;
            fld[y][x] && (fld[y][x]--, n--);
        }
    }
}

Measured memory_bytes: 584
import sys
mod = 10**9+7

def main():
    n, m = map(int, input().split(' '))
    if m > 0:
        aaa = set(map(int, sys.stdin))
    else:
        aaa = set()
 
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in aaa else 0
    
    for i in range(2, n+1):
        if i in aaa:
            continue
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
    print(dp[n])
 
main()

Measured memory_bytes: 11884
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	lli r, D, x;
	cin >> r >> D >> x;

	for (int i = 0; i < 10; i++) {
		x = r * x - D;
		COUT(x);
	}

	return 0;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
#define PI 3.141592653589793238462643383279
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;

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

    for(int i = 0; i < n; i++){
        string a;
        cin >> a;
        if(a == "print"){
            int b,c;
            cin >> b >> c;
            cout << s.substr(b,c-b+1) << endl;
        }else if(a == "replace"){
            int b,c;
            string re;
            cin >> b >> c >> re;
            s.replace(s.begin()+b,s.begin()+c+1,re);
        }else{
            int b,c;
            cin >> b >>c;
            reverse(s.begin()+b,s.begin()+c+1);
        }


    }




}


Measured memory_bytes: 3200