akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std; // 575

const int MAX = 3001;
int main() {
	string s, t;
	cin >> s >> t;
	static int dp[MAX][MAX];
	for (int i = 0;i <= s.size();++ i) for (int j = 0;j <= t.size();++ j) dp[i][j] = 0;
	for (int i = 1;i <= s.size();++ i) for (int j = 1;j <= t.size();++ j) dp[i][j] = min(max(dp[i - 1][j], dp[i][j - 1]) + (s[i - 1] == t[j - 1] ? 1 : 0), min(dp[i - 1][j - 1], dp[i][j - 1]) + 1);
	
	string ans = "";
	for (int i = s.size(), j = t.size();dp[i][j] > 0;-- j) {
		while (dp[i][j] == dp[i - 1][j]) -- i;
		while (dp[i][j] == dp[i][j - 1]) -- j;
		ans = t[j - 1] + ans;
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

        a b y x b
    : 0 0 0 0 0 0
a   : 0 1 1 1 1 1
ax  : 0 1 1 1 2 2
axy : 0 1 1 2 2 2
axyb: 0 1 2 2 2 3

               a v a d a k e d a v r a
:            0 0 0 0 0 0 0 0 0 0 0 0 0
a:           0 1 1 1 1 1 1 1 1 1 1 1 1
ab:          0 1 1 1 1 1 1 1 1 1 1 1 1
abr:         0 1 1 1 1 1 1 1 1 1 1 2 2
abra:        0 1 1 2 2 2 2 2 2 2 2 2 3
abrac:       0 1 1 2 2 2 2 2 2 2 2 2 3
abraca:      0 1 1 2 2 3 3 3 3 3 3 3 3
abracad:     0 1 1 2 3 3 3 3 4 4 4 4 4
abracada:    0 1 1 2 3 4 4 4 4 5 5 5 5
abracadab:   0 1 1 2 3 4 4 4 4 5 5 5 5
abracadabr:  0 1 1 2 3 4 4 4 4 5 5 6 6
abracadabra: 0 1 1 2 3 4 4 4 4 5 5 6 7
*/

Measured memory_bytes: 35456
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
move = [(0, 1), (1, 1), (-1, 1), (0, -1), (1, -1), (-1, -1), (1, 0), (-1, 0)]
#A
def A():
    a, b, c = LI()
    if a == b:
        print(c)
    if b == c:
        print(a)
    if a == c:
        print(b)
    return

#B
def B():
    h, w = LI()
    s = SR(h)
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                b = 0
                for my, mx in move:
                    ym = my + y
                    xm = mx + x
                    if 0 <= ym < h and 0 <= xm < w:
                        if s[ym][xm] == "#":
                            b += 1
                s[y][x] = b
    for i in range(h):
        print("".join(map(str, s[i])))
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    ab = LIR_(m)
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    ans = 0
    for a, b in ab:
        c = [True] * n
        ed = defaultdict(int)
        q = deque()
        q.append(0)
        c[0] = False
        ed[(a,b)] = True
        while q:
            now = q.pop()
            for e in edg[now]:
                if ed[(now,e)] or ed[(e,now)]:
                    continue
                ed[(now, e)] = True
                c[e] = False
                q.appendleft(e)
        if True in c:
            ans += 1
    print(ans)
    return

#D
def D():
    n, k = LI()
    xy = LIR(n)
    fullserch = list(itertools.combinations(range(n), 2))
    ans = inf
    for a, b in fullserch:
        minx = min(xy[a][0], xy[b][0])
        maxx = max(xy[a][0], xy[b][0])
        for c, d in fullserch:
            miny = min(xy[c][1], xy[d][1])
            maxy = max(xy[c][1], xy[d][1])
            x = 0
            
            for i in range(n):
                if minx <= xy[i][0] <= maxx and miny <= xy[i][1] <= maxy:
                    x += 1

            if x >= k:
                ans = min(ans, (maxx - minx) * (maxy - miny))
    print(ans) 
    return

#Solve
if __name__ == '__main__':
    D()


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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 100000000000000;
double PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

int main(){
  ll N;cin >> N;
  ll dp[110][4][4][4]={0};
  dp[0][3][3][3] = 1;
  for(int i = 0;i < N;i++){
    for(int j = 0;j < 4;j++){
      for(int k = 0;k < 4;k++){
        for(int l = 0;l < 4;l++){
          if((j == 0 && k == 1 && l == 2) ||
             (j == 0 && k == 2 && l == 1) ||
             (j == 2 && k == 0 && l == 1)
          ){
            continue;
          } 
          for(int m = 0;m < 4;m++){
            if((j == 0 && l == 2 && m == 1) ||
               (j == 0 && k == 2 && m == 1) ||
               (k == 0 && l == 1 && m == 2) ||
               (k == 0 && l == 2 && m == 1) ||
               (k == 2 && l == 0 && m == 1)
            ){
              continue;
            }
            dp[i+1][k][l][m] += dp[i][j][k][l];
            dp[i+1][k][l][m] %= MOD;
          }
        }
      }
    }
  }
  ll ans = 0;
  for(int i = 0;i < 4;i++){
    for(int j = 0;j < 4;j++){
      for(int k = 0;k < 4;k++){
        ans += dp[N][i][j][k];
      }
    }
  }
  cout << ans % MOD << endl;
}


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

#define llint long long int

using namespace std;

int main(){
    int N;

    cin >> N;

    vector<int> A(N), B(N);

    for(int i = 0; i < N; i ++){
        cin >> A[i] >> B[i];
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater<int>());

    if(N % 2 == 1){
        int start = A[(N - 1) / 2];
        int end = B[(N - 1) / 2];

        cout << end - start + 1 << endl;
    }else{
        int start = A[(N - 2) / 2] + A[(N - 2) / 2 + 1];
        int end = B[(N - 2) / 2] + B[(N - 2) / 2 + 1];

        cout << end - start + 1 << endl;
    }
}

Measured memory_bytes: 4792
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());
		System.out.println((S/3600)+":"+(S%3600/60)+":"+(S%3600%60));
	}
}

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

int main(){
    int N, x;  cin >> N >> x;
    if(x==2*N-1 || x==1){
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    vector<int> ans(2*N,-1);
    ans[N] = x;
    ans[N-1] = x + 1;
    ans[N+1] = x - 1;
    if(x >= 3){
        ans[N-2] = x - 2;
        int nxt = 1;
        for(int i=1; i<=2*N-1; i++){
            if(ans[i] != -1) continue;
            else{
                if(nxt==x-2) nxt = x+2;
                ans[i] = nxt;
                nxt++;
            }
        }
    }else{
        ans[N+2] = x + 2;
        int nxt = 1;
        for(int i=1; i<=2*N-1; i++){
            if(ans[i] != -1) continue;
            else{
                if(nxt==x-1) nxt = x+3;
                ans[i] = nxt;
                nxt++;
            }
        }
    }
    for(int i=1; i<=2*N-1; i++){
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#pragma region Macros
#define ios\
    ios::sync_with_stdio(false);\
    cin.tie(nullptr);
#define VEC(type, name, size)\
    V<type> name(size);\
    IN(name)
#define VVEC(type, name, h, w)\
    VV<type> name(h, V<type>(w));\
    IN(name)
#define INT(...)\
    int __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LL(...)\
    ll __VA_ARGS__;\
    IN(__VA_ARGS__)
#define STR(...)\
    string __VA_ARGS__;\
    IN(__VA_ARGS__)
#define CHAR(...)\
    char __VA_ARGS__;\
    IN(__VA_ARGS__)
#define DOUBLE(...)\
    DOUBLE __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LD(...)\
    LD __VA_ARGS__;\
    IN(__VA_ARGS__)
template <class T> void scan(T &a) { cin >> a; }
template <class T> void scan(vector<T> &a) { for(auto &i : a) scan(i); }
template <class T, class L> void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); }
template <class T> inline void print(T x){ cout << x << '\n';}
#define ll long long
#define ld long double
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
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; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
const ll INF = 1e18;
#pragma endregion

int main(){
    ios;
    STR(s);
    stack<char> st;
    REP(i, SZ(s)){
        if(s[i] == 'B') if(SZ(st)) st.pop();
        if(s[i] == '0') st.push('0');
        if(s[i] == '1') st.push('1');
    }
    string res = "";
    while(SZ(st)){
        res = st.top() + res;
        st.pop();
    }
    print(res);
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int N, A;
    cin >> N;
    int _max, _nmax, maxi, nmaxi;
    _max = 0;
    _nmax = 0;
    maxi = 0;
    nmaxi = 0;
 
    rep(i, N){
        int a;
        cin >> a;
        if(_max == a){
            _nmax = a;
        }
        if(a > _max){
            _max = a;
            maxi = i;
        } else if(a > _nmax){
            _nmax = a;
        }
    }
    rep(i, N){
        if(i == maxi){
            cout << _nmax << endl;
        } else {
            cout << _max << endl;
        }
    }
    
    return 0;
}


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

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e3+1e1;

struct Node{
	int u,v;
}ed[MAXN];
struct Edge{
	int nxt,to;
}e[MAXN<<1];
bool vis[MAXN];
int head[MAXN],dep[MAXN],n,k,cnt,tot=0,ans=inf;

void Addedge(int u,int v){
	e[++tot]=(Edge){head[u],v};
	head[u]=tot;
	return;
}

void Dfs(int u,int depth){
	vis[u]=true,dep[u]=depth;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!vis[v]) Dfs(v,depth+1);
	}
	return;
}

void Solve(int x){
	memset(vis,false,sizeof(vis)),cnt=0;
	if(k&1){
		if(x==n) return;
		int u=ed[x].u,v=ed[x].v;
		vis[u]=true,Dfs(v,0),Dfs(u,0);
	}
	else Dfs(x,0);
	for(int i=1;i<=n;i++) if(dep[i]>(k/2)) ++cnt;
	ans=min(cnt,ans);
	return;
}

int main(void){

	// freopen("testdata.in","r",stdin);
	// freopen("testdata.out","w",stdout);

	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		ed[i].u=readint,ed[i].v=readint;
		Addedge(ed[i].u,ed[i].v),Addedge(ed[i].v,ed[i].u);
	}
	for(int i=1;i<=n;i++) Solve(i);
	printf("%d\n",max(ans,0));

	return 0;
}

Measured memory_bytes: 3904
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,ans=0,i;
  string s;
  map <string,int> m;
  cin>>n;
  for(i=0;i<n;i++)
  {
  	cin>>s;
  	m[s]++;
  }
  for(auto it:m)
  		ans=max(ans,it.second);
  for(auto it:m)
  {
  	if(ans==it.second) cout<<it.first<<"\n";
  }
}

Measured memory_bytes: 25216
size = gets.to_i
size.times do
  sides = STDIN.readline.split(" ").map(&:to_i)
  long = sides.max
  sides.each_with_index do |v, i|
    if v == long
      sides.delete_at(i)
      break
    end
  end

  if long**2 == sides[0]**2 + sides[1]**2
    puts "YES"
  else
    puts "NO"
  end
end

Measured memory_bytes: 6108
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MAX 26

struct Node {
	int p, l, r; //??????????????????
};
struct Node T[MAX];
int D[MAX], H[MAX];

//??¨node?????±??????D???????´?
void set_depth(int id, int d) {
	D[id] = d;
	if (T[id].r != -1) {
		set_depth(T[id].r, d + 1);
	}
	if (T[id].l != -1) {
		set_depth(T[id].l, d + 1);
	}
}

//??¨node????????????H???????´?
int set_height(int id) {
	int hr = 0, hl = 0;
	if (T[id].r != -1) {
		hr = 1 + set_height(T[id].r);
	}
	if (T[id].l != -1) {
		hl = 1 + set_height(T[id].l);
	}
	return H[id] = max(hr, hl);
}

void print(int id) {
	int sib = -1,
		deg = 0;
	if (T[id].p != -1)
		sib = (T[T[id].p].l == id) ? T[T[id].p].r : T[T[id].p].l;
	deg += (T[id].l != -1) ? 1 : 0;
	deg += (T[id].r != -1) ? 1 : 0;

	string type = "internal node";;
	if (T[id].r == -1 && T[id].l == -1)type = "leaf";
	if (T[id].p == -1)type = "root";

	cout << "node " << id;
	cout << ": parent = " << T[id].p;
	cout << ", sibling = " << sib;
	cout << ", degree = " << deg;
	cout << ", depth = " << D[id];
	cout << ", height = " << H[id];
	cout << ", " << type << endl;
}

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

	//?????????
	for (int i = 0; i < n; i++) {
		T[i].p = T[i].l = T[i].r = -1;
	}

	for (int i = 0; i < n; i++) {
		int id, l, r; cin >> id >> l >> r;
		T[id].l = l; T[id].r = r;
		T[l].p = id; T[r].p = id;
	}

	//??????????????????
	int root;
	for (int id = 0; id < n; id++) {
		if (T[id].p == -1) { root = id; }
	}

	set_depth(root, 0);
	set_height(root);

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

	return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <string>
#include <cmath>
#include<iomanip>
#include<algorithm>
#include<list>
using namespace std;


int main()
{
	int n;
	string a[101], b[101];

	//入力
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		b[i] = a[i];
	}

	//バブルソート
	for (int i = 0; i < n; i++){
		for (int j = n - 1; j > i; j--){
			if (a[j][1] < a[j - 1][1]){
				string tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
			}
		}
	}

	//出力
	for (int i = 0; i < n; i++){
		if (i < n - 1){
			cout << a[i] << " ";
		}
		else{
			cout << a[i] << endl<<"Stable"<<endl;
		}
	}

	//選択ソート
	for (int i = 0; i < n; i++){
		int minj = i;
		for (int j = i; j < n; j++){
			if (b[j][1] < b[minj][1]){
				minj = j;
			}
		}
		string tmp = b[i];
		b[i] = b[minj];
		b[minj] = tmp;
	}



	//出力
	for (int i = 0; i < n; i++){
		if (i < n - 1){
			cout <<b[i] << " ";
		}
		else{
			cout << b[i] << endl;
		}
	}
	//安定かどうかの判定
	bool flag = true;
	for (int i = 0; i < n; i++){
		if (a[i] != b[i]){
			flag = false;
		}
	}
	if (flag){
		cout << "Stable" << endl;
	}
	else{
		cout << "Not stable" << endl;
	}

	return 0;
}

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

int main() {
  int n,k;
  cin >> n >> k;
  vector <int> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  int sum = 0;
  for(int i = 0; i < k; i++){
    sum += v[i];
  }
  cout << sum << endl;
}

Measured memory_bytes: 3548
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>
#include <ctime>
#include <set>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <sstream>
#include <cstdio>
#include <bitset>
#include <iomanip>

using namespace std;

long long dp[123456];
long long h[123456];

int main()
{
    ios_base::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
        cin >> h[i];

    for (int i = 0; i <= n; ++i)
        dp[i] = (1LL<<60);

    dp[1] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (i + j <= n) {
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
            }
        }
    }

    cout << dp[n] << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
typedef long long ll;
const int MaxN=200010,mod=1000000007;
int N,X,Y,c[MaxN],w[MaxN],list[MaxN];
std::vector<int>V[MaxN];
int cur[MaxN];
bool cmp(int i,int j){return w[i]<w[j];}
struct item{
	int x;
	bool operator<(const item&it)const{
		int i=V[x][cur[x]],j=V[it.x][cur[it.x]];
		return w[i]!=w[j]?w[i]<w[j]:i<j;
	}
};
std::set<item>S;
int col[MaxN],len;
int top(int i){return cur[i]<V[i].size()?V[i][cur[i]]:-1;}
void dfs(int i){
	int t=col[len++]=c[i],to;
	S.erase((item){t});
	if(++cur[t]<V[t].size())S.insert((item){t});
	while(S.size()){
		if(top(t)>-1&&w[i]+w[to=top(t)]<=X)dfs(to);
		else{
			std::set<item>::iterator it=S.begin();
			if((to=it->x)==c[i])to=S.size()>1?(++it)->x:-1;
			if(to>-1&&w[i]+w[top(to)]<=Y)dfs(top(to));
			else return;
		}
	}
}
ll fac[MaxN],ifac[MaxN];
ll inv(int a,int p=mod){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
int main(){
	scanf("%d%d%d",&N,&X,&Y);
	for(int i=0;i<N;i++)scanf("%d%d",c+i,w+i),list[i]=i;
	std::sort(list,list+N,cmp);
	for(int*i=list;i<list+N;i++)V[c[*i]].push_back(*i);
	for(int i=1;i<=N;i++)if(top(i)>-1)S.insert((item){i});
	for(int i=*fac=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
	ifac[N]=inv(fac[N]);
	for(int i=N;i;i--)ifac[i-1]=ifac[i]*i%mod;
	int ans=1;
	while(S.size()){
		len=0;
		dfs(top(S.begin()->x));
		std::sort(col,col+len);
		ans=ans*fac[len]%mod;
		for(int i=0,j=0;i<len;i=j){
			while(j<len&&col[i]==col[j])j++;
			ans=ans*ifac[j-i]%mod;
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 32512
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll N,ans,dp[62][300100];

int main(){
    cin>>N;
    ll A[N];
    rep(i,62)dp[i][0]=0;
    rep(i,N){
        cin>>A[i];
        rep(j,62)dp[j][i+1]=dp[j][i]+(A[i]>>j)%2;
    }
    rep(i,N){
        rep(j,62){
            if((A[i]>>j)%2){
                ans=((ans+((i-dp[j][i])*((1LL<<j)%1000000007))%1000000007))%1000000007;
            }
            else{
                ans=((ans+(dp[j][i]*((1LL<<j)%1000000007))%1000000007))%1000000007;
            }
        }
    }
    out(ans);


    

}


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

int d[4][4];

bool check(int i, int j, int k) {

	int b[4];

	b[1] = d[1][1] - i;
	b[2] = d[1][2] - i;
	b[3] = d[1][3] - i;

	for (int n=1; n < 4; n++) {
		if (d[2][n] != j + b[n]) return false;
		if (d[3][n] != k + b[n]) return false;
	}

	return true;
}


int main() {



	for (int i = 1; i < 4; i++) {
		for (int j = 1; j < 4; j++) {
			cin >> d[i][j];
		}
	}

	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			for (int k = 0; k <= 100; k++) {

				if (check(i, j, k)) {
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
	}

	cout << "No" << endl;
}

Measured memory_bytes: 256
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>


vector<vector<int>> ans;
void fill_ans(int start, int gam, int n) {
  if (n == 1) {
    ans[start].push_back(1);
    ans[start + 1].push_back(1);
    return;
  }
  for (int i = 0; i < gam; i++) {
    ans[start].push_back(n - i);
  }
  for (int i = 0; i < gam; i++) {
    ans[start + 1 + i].push_back(n - i);
  }
  fill_ans(start + 1, gam - 1, n - gam);
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int n;
  cin >> n;
  int gam = -1;
  for (int i = 1; i < 10000; i++) {
    if (i * (i + 1) / 2 == n) {
      gam = i;
      break;
    }
  }
  if (gam == -1) {
    cout << "No\n";
    return 0;
  }
  cout << "Yes\n";
  ans.resize(gam + 1);
  fill_ans(0, gam, n);
  cout << sz(ans) << "\n";
  for (int i = 0; i < sz(ans); i++) {
    cout << sz(ans[i]) << " ";
    for (int j = 0; j < sz(ans[i]); j++) {
      cout << ans[i][j] << " ";
    }
    cout << "\n";
  }
}



Measured memory_bytes: 3328
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;
void log(A...)(A arg) { stderr.writeln(arg); }
int size(T)(in T s) { return cast(int)s.length; }

void main() {
    int A, B; readf("%d %d\n", &A, &B);
    int f() {
        if (A == B) return 0;
        if (A == 1) return 1;
        if (B == 1) return -1;
        return A - B;
    }
    int x = f();
    if (x > 0) {
        writeln("Alice");
    } else if (x == 0) {
        writeln("Draw");
    } else {
        writeln("Bob");
    }
}


Measured memory_bytes: 256
s=gets.chomp
l=s.size
i=0
while i<=l
    if s[-i-5,5]=='dream'||s[-i-5,5]=='erase'
        i+=5
    elsif s[-i-7,7]=='dreamer'
        i+=7
    elsif s[-i-6,6]=='eraser'
        i+=6
    elsif i==l
        puts 'YES'
        break
    else
        puts 'NO'
        break
    end
end

Measured memory_bytes: 3964
n,y=gets.chomp.split(" ").map(&:to_i)

(0..n).each do |i1|
  (0..(n-i1)).each do |i2|
    i3 = n - i1 - i2
    if 10000 * i1 + 5000 * i2 + 1000 * i3 == y then
      puts "#{i1} #{i2} #{i3}"
      exit
    end
  end
end

puts "-1 -1 -1"




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

using namespace std;

int main()
{
  int n, a, b, c = 1;
  cin >> n;
  cin >> a >> b;  
  int ans = __gcd(a, b);
  if(n == 3) cin >> c, ans = __gcd(ans, c);
  for(int i = 1; i <= ans; i++){
    if(a % i == 0 && b % i == 0){
      if(n == 2 || n == 3 && c % i == 0) cout << i << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>

#define SIZE 500000
#define INFTY 1200000000
int count = 0;

void show(int* a, int size)
{
    int i;
    printf("%d", a[0]);
    for(i = 1; i < size; i++) printf(" %d", a[i]);
	printf("\n");
}

void Merge(int* A, int left, int mid, int right)
{
    int R[SIZE], L[SIZE];
    int i, j, k, n1, n2;
    n1 = mid - left;
    n2 = right - mid;
    for(i = 0; i < n1; i++) L[i] = A[i + left];
    for(j = 0; j < n2; j++) R[j] = A[j + mid];

    L[n1] = INFTY;
    R[n2] = INFTY;
    i = j = 0;

    for(k = left; k < right; k++){

		if(L[i] <= R[j]){ A[k] = L[i]; i++; }

        else{ A[k] = R[j]; j++; }

        count++;
    }
}

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);
    }
    return;
}

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

    MergeSort(S, 0, n);
    show(S, n);
    printf("%d\n", count);

    return 0;
}

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

int main(){
    string S; cin>>S;
    string A,B; A="",B="";
    for(int i=0;i<S.size();i++){
        if(i%2==0){
            A+='0';
            B+='1';
        }
        else{
            A+='1';
            B+='0';
            }
    }
    int a=0;
    int b=0;
    for(int i=0;i<S.size();i++){
        if(S[i]!=A[i]){
            a+=1;
        }
        if(S[i]!=B[i]){
            b+=1;
        }
    }
    cout<<min(a,b)<<endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279
 
#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ll INF = LLONG_MAX;
const ull MOD = 1000000007;
#define VEC(type,A,N) vector<type> A(N)
#define VECi(type,A,N,i) vector<type> A(N,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N,vector<type>(M))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N,vector<type>(M,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
ll digitPoor(ll n)
{
    assert(INT_MAX == 2147483647);
    assert(n >= 0);

    if (n < 10)         return 1;
    if (n < 100)        return 2;
    if (n < 1000)       return 3;
    if (n < 10000)      return 4;
    if (n < 100000)     return 5;
    if (n < 1000000)    return 6;
    if (n < 10000000)   return 7;
    if (n < 100000000)  return 8;
    if (n < 1000000000) return 9;
    return 10;
}
struct p{
  ll x;
  bool b;
};
int main(){
    string S,T;
    cin>>S>>T;
    
    ll cnt=0;
    REP(i,S.length()){
        if(S[i]!=T[i]){
            cnt++;
        }
    }
    cout<<cnt;
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3916
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
//        int t = in.nextInt();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task {
        public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {
            int n = in.nextInt();
            int[] b = new int[n-1];
            for (int i = 0; i < n - 1; i++) {
                b[i] = in.nextInt();
            }

            int[] a = new int[n];
            a[0] = b[0];
            a[1] = b[0];
            for (int i = 1; i < b.length; i++) {
                a[i+1] = b[i];
                if (a[i] > b[i]){
                    a[i] = b[i];
                }
            }

            long sum = 0;
            for (int i = 0; i < n; i++) {
                sum += a[i];
            }
//            out.println(Arrays.toString(a));
            out.println(sum);
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

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

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextLine() throws IOException {
            return reader.readLine().trim();
        }
    }
}


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

using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define SORT(v) sort(ALL(v))
//#define scanf scanf_s
typedef pair<int, int> P;

string l = "qwertasdfgzxcvb";
string r = "yuiophjklnm";
int hand[30];

int main()
{
	memset(hand, 0, sizeof(hand));
	REP(i, l.size())
	{
		hand[l[i] - 'a'] = 1;
	}
	string s;
	while (cin >> s)
	{
		if (s == "#") break;
		int cnt = 0;
		int buf = hand[s[0]-'a'];
		REP(i, s.size())
		{
			if (buf != hand[s[i]-'a'])
			{
				buf = hand[s[i]-'a'];
				cnt++;
			}
		}
		cout << cnt << endl;
	}

	return 0;
}

Measured memory_bytes: 1192
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a[ohara], b, c, d, tmp, m, h, w, x, y, sum, k, q;
ll tate[100];

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

  cin >> n >> s;
  rep(i, n) { a[i] = (s[i] - '0') - 1; }

  rep(i, 50) {
    if ((n - 1) & (1 << i)) tate[i]++;
  }
  rep(i, n) {
    if (a[i] != 1) continue;
    int ok = 0;
    rep(j, 50) {
      if (i & (1 << j)) {
        if (tate[j] == 0) ok = 1;
      }
    }
    if (ok) continue;
    cnt++;
  }
  cnt %= 2;
  if (cnt == 1) {
    Cout(1);
  } else {
    rep(i, n) {
      if (a[i] == 1) {
        Cout(0);
        return 0;
      }
    }
    cnt = 0;
    rep(i, n) {
      if (a[i] != 2) continue;
      int ok = 0;
      rep(j, 50) {
        if (i & (1 << j)) {
          if (tate[j] == 0) ok = 1;
        }
      }
      if (ok) continue;
      cnt++;
    }
    cnt %= 2;
    if (cnt == 1)
      Cout(2);
    else
      Cout(0);
  }
  return 0;
}

Measured memory_bytes: 9116
#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<ll,ll>;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}


int main() {
  ll a,b,n;
  cin >> a >> b >> n;
  ll c=0,ans=0;
  ll d=n/b*b-1;
  if(n-d==b) d=n;
  if(n/b==0) {
      ans=a*n/b-a*(n/b);
  }
  else {
      ans=a*d/b-a*(d/b);
  }
  
  pt(ans);
  return 0;
}


Measured memory_bytes: 3628
n, m = map(int, input().split())
a = list(map(int, input().split()))
a_t = [0]
for i in range(n):
    a_t.append(a[i] + a_t[i])
dict = {}
for i in range(n + 1):
    b = a_t[i] % m
    if b in dict:
        dict[b] += 1
    else:
        dict[b] = 1
ans = 0
for i in dict.values():
    ans += i * (i - 1) // 2
print(ans)

Measured memory_bytes: 16556
def main():
    N = int(input())
    V = list(map(int, input().split()))
    
    sort_V = sorted(V)
    ave = (sort_V[0] + sort_V[1]) / 2
    if N > 2:
        for i in range(2, N):
            ave = (ave + sort_V[i]) / 2

    print(ave)

main()

Measured memory_bytes: 38256
#include <iostream>
#include <math.h>
#include <string>

using namespace std;

int main(){

	int N;

	cin >> N;

	string result = "";

	if (N == 0){
		cout << "0" << endl;
		return 0;
	}

	while (true){
		if (N == 0) break;
		if (N > 0){
			int mod = N % 2;
			N = -N / 2;
			result = (mod == 0 ? "0" : "1") + result;
		}
		else{
			int mod = abs(N) % 2;
			if (mod == 0) N = -N / 2;
			else	N = -N / 2 + 1;
			result = (mod == 0 ? "0" : "1") + result;
		}
	}

	cout << result << endl;

	return 0;
}

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

int main(){
	int w, h, n;
	cin >> w >> h >> n;
	vector<vector<int>> rec(h, vector<int>(w, 0));
	for(int i = 0; i < n; i++){
		int x, y, a;
		cin >> x >> y >> a;
		if(a == 1){
			for(int j = 0; j < h; j++){
				for(int k = 0; k < x; k++){
					rec.at(j).at(k) = 1;
				}
			}
		}
		else if(a == 2){
			for(int j = 0; j < h; j++){
				for(int k = x; k < w; k++){
					rec.at(j).at(k) = 1;
				}
			}
		}
		else if(a == 3){
			for(int j = 0; j < y; j++){
				for(int k = 0; k < w; k++){
					rec.at(j).at(k) = 1;
				}
			}
		}
		else{
			for(int j = y; j < h; j++){
				for(int k = 0; k < w; k++){
					rec.at(j).at(k) = 1;
				}
			}
		}
		// // cout << endl;
		// for(int j = 0; j < h; j++){
		// 	for(int k = 0; k < w; k++){
		// 		cout << rec.at(j).at(k) << " ";
		// 	}
		// 	cout << endl;
		// }
	}
	int ans = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(rec.at(i).at(j) == 0){
				ans += 1;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N,M,S=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    E[u].append((v,a,b))
    E[v].append((u,a,b))

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<60]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print(min(DP[i]))



Measured memory_bytes: 116120
from collections import deque
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=deque([self.unit])
        self.fold_l=deque([self.unit])
        self.data_r=deque()
        self.data_l=deque()
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(list(self.data_l)[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(list(self.data_r))
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

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

int main(){
	int N;
	cin >> N;
	int A[N], B[N];
	rep(i,N) cin >> A[i] >> B[i];
	ll ans = 0;
	for (int i = N-1; i >= 0; i--) {
		int p = (ans+A[i]+B[i])%B[i];
		if (p != 0) p = B[i] - p;
		ans += p;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4388
#include "stdio.h"
#define rep(i,n) for(i=0;i<n;i++)
int main(){
	int n,i,j,x,y,sz,ret,minus;
	char mt[1000][1000];

	while( scanf("%d\n",&n) , n){
		ret = 0;

		rep(i,n)scanf("%s\n",mt[i]);
	
		rep(y,n)rep(x,n){
		
			if(mt[y][x] == '.'){
			
				minus = (x>y?x:y);
				rep(sz,n-minus){
					rep(i,sz+1)if(mt[y+sz][x+i] == '*'){goto l;}
					rep(i,sz+1)if(mt[y+i][x+sz] == '*'){goto l;}
					
					if(ret<sz+1)ret = sz+1;
				}
				l:;
			}
		}
		printf("%d\n",ret);
	}
	return 0;
}

Measured memory_bytes: 1180
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
using Graph = vector< vector<int> >;

bool exist_edge[710][710], dp[710];
int used[710];

long long int edges(long long int A) {
    return A * (A - 1) / 2;
}

int na = 0, nb = 0;
bool check_bipartite(Graph &G, int cur, int col=0) {
    bool res = true;
    used[cur] = col;
    (col == 0 ? na : nb)++;
    for(auto to : G[cur]) {
        if(used[to] >= 0) {
            if(used[to] == used[cur]) res = false;
        }
        else {
            res &= check_bipartite(G, to, 1-col);
        }
    }
    return res;
}

int main() {
    int N, M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        exist_edge[u][v] = exist_edge[v][u] = true;
    }

    Graph G(N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(i == j) continue;
            if(!exist_edge[i][j]) G[i].push_back(j);
        }
    }

    bool ok = true;
    vector< pair<int, int> > vtxs;
    fill(used, used + N, -1);
    for(int i=0; i<N; i++) {
        if(used[i] >= 0) continue;
        int pa = na, pb = nb;
        ok &= check_bipartite(G, i);
        vtxs.emplace_back(na - pa, nb - pb);
    }

    if(ok) {
        dp[0] = true;
        for(auto x : vtxs) {
            int A = x.first, B = x.second;
            for(int i=N; i>=0; i--) {
                if(dp[i]) {
                    dp[i] = false;
                    dp[i+A] = dp[i+B] = true;
                }
            }
        }

        long long int ans = 1LL << 60;
        for(int i=0; i<=N; i++) {
            if(dp[i]) {
                int A = i, B = N-i;
                ans = min(ans, edges(A) + edges(B));
            }
        }
        cout << ans << endl;
    }
    else {
        cout << -1 << endl;
    }
    return 0;
}

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

typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;

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

    int n, k;    
    cin >> n >> k;
    vi a(n);
    vector<bool> dp(k + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < k; ++i) {
        if (!dp[i]) {
            for (int j = 0; j < n; ++j) {
                if (i + a[j] > k) {
                    break;
                }
                dp[i + a[j]] = true;
            }
        }
    }

    if (dp[k]) {
        cout << "First\n";
    }
    else {
        cout << "Second\n";
    }

    return 0;
}

Measured memory_bytes: 256
use std::io::stdin;

macro_rules! read {
    ($t: ty) => {{
        let mut line = String::new();
        stdin().read_line(&mut line);
        line.trim().parse::<$t>().unwrap()
    }};
    ($($t: ty), *) => {{
        let mut line = String::new();
        stdin().read_line(&mut line);
        let mut iter = line.split_whitespace();
        (
            $(iter.next().unwrap().parse::<$t>().unwrap(), )*
        )
    }}
}
macro_rules! reads {
    ($e:expr, $t:ty) => {{
        let mut v = vec![];
        for _ in 0..$e {
            let mut line = String::new();
            stdin().read_line(&mut line);
            v.push(line.trim().parse::<$t>().unwrap());
        }
        v
    }};
}

fn main() {
    let n = read!(u32);
    let mut v = 0f32;
    for _ in 0..n {
        let (x, u) = read!(f32, String);
        if u == "BTC" {
            v = v + x * 380000f32;
        } else {
            v = v + x;
        }
    }
    println!("{}", v);
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
int max(const void *a, const void *b){return *(int*)b - *(int*)a;}

int n;
uint8_t a[200001];
uint8_t b[200001];

int main(void)
{
    int m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%hhd",&(a[i]));
    }
    
    m = 0;
    for(int i =n;i>=1;i--)
    {
        int cnt;
        cnt = 0;
        for(int j = 2; i*j <=n ;j++)
        {
            cnt += b[i*j];
        }
        b[i] = ((cnt % 2) + a[i]) % 2;
        if(b[i]==1) m++;
    }

    printf("%d\n",m);
    for(int i=1;i<=n;i++)
    {
        if(b[i]==1) printf("%d\n",i);
    }

    return 0;
}


Measured memory_bytes: 1280
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
A = Counter([int(input()) for _ in range(N)])
ans = 0
for k, v in A.items():
    if v % 2 == 1:
        ans += 1
print(ans)




Measured memory_bytes: 20880
import itertools as it

def horizontal_input(T=str):
    return list(map(T,input().split()))

def vertical_input(n,T=str,sep=False,septype=tuple):
    data=[]
    if sep:
        for i in range(n):
            data.append(septype(map(T,input().split())))
    else:
        for i in range(n):
            data.append(T(input()))
    return data

while 1:
    n,m=horizontal_input(int)
    if n==0 and m==0:
        break
    h=[0]+list(it.accumulate(vertical_input(n,int)))
    w=[0]+list(it.accumulate(vertical_input(m,int)))
    _h={}
    for i in range(n+1):
        for j in range(i+1,n+1):
            if h[j]-h[i] in _h:
                _h[h[j]-h[i]]+=1
            else:
                _h[h[j]-h[i]]=1
    _w={}
    for i in range(m+1):
        for j in range(i+1,m+1):
            if w[j]-w[i] in _w:
                _w[w[j]-w[i]]+=1
            else:
                _w[w[j]-w[i]]=1
    ans=0
    for k in _h.keys():
        ans+=_h[k]*(_w[k] if k in _w else 0)
    print(ans)


Measured memory_bytes: 54428
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>

#define rep(i,n) for (int i = 0; i< (n); i++)
using namespace std;

int main() {
  int a,b, c;
  
  cin>>a>>b>>c;
  
  if(a+b+c>=22) cout<<"bust"<<endl;
  else cout<<"win"<<endl;
  
  return 0;
}

Measured memory_bytes: 256
// C - HSI

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

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

	int E = pow(2, M);

	int ans = (N - M) * 100 * E + M * 1900 * E;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
//container util
//------------------------------------------
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
 
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define REACH(i,c) for(typeof((c).end()) i=(c).end(); i!=(c).begin(); --i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
 
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).begin(),(c).end(),greater<int>())
 
#define PB(a) push_back(a)
#define PF(a) pop_front(a)

#define MP(a,b) make_pair(a,b)
 
#define FS first
#define SE second
 
#define ALL(x) (x).begin(),(x).end()
#define MAX_EL(c) *max_element((c).begin(),(c).end())
#define MIN_EL(c) *min_element((c).begin(),(c).end())
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef string str;
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 
//grobal var
//------------------------------------------
const int MAX = 2*10e5+2;


int main(){
// magic spell------------------------------
  cin.tie(0);
  ios::sync_with_stdio(false);
//------------------------------------------
  int r,D,x;
  while(cin >> r >> D >> x){
    LL dp[11];
    dp[0] = x;
    REP(i,10){
      dp[i+1]=r*dp[i]-D;
    }
    REP(i,10){
      cout << dp[i+1] << endl;
    }
    }
  return 0;
}

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

using namespace std;

int main(){
    
    int N, M;
    cin >> N >> M;
    int a[M];
    long int dp[N+2];
    long int mod = 1000000007;
    
    for (int i = 0; i <= N+1; i++) {
        dp[i] = 0;
    }
    dp[1] = 1;
    
    for (int i = 0; i < M; i++) {
        cin >> a[i];
        dp[a[i] + 1] = -1;
    }
    
    for (int i = 1; i <= N; i++) {
        if (dp[i+1] == -1) {
            dp[i+1] = 0;
        }else{
            dp[i+1] += (dp[i] + dp[i-1]);
            dp[i+1] = dp[i+1] % mod;
            
        }
    }
    
    /*
    for (int i = 0; i <= N+1; i++) {
        cout << dp[i] << endl;
    }
    */
    
    cout << dp[N+1] << endl;
    
}


Measured memory_bytes: 1408