akhauriyash/Code-Regression huggingface dataset:
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 2010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

ll MOD = 924844033;

ll add(ll a, ll b) {
    return (a + b) % MOD;
}

ll mul(ll a, ll b) {
    return a * b % MOD;
}

ll sub(ll a, ll b) {
    return (a - b + MOD) % MOD;
}

int n, k;
ll f[MAXN], dp[MAXN * 2], dptmp[MAXN * 2], F[MAXN*2][MAXN*2];
vector<int> b;

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

void getM() {
    FOR(i,0,4000) {
        F[i][0] = 1;
        FOR(j,1,i) {
            F[i][j] = F[i-1][j];
            if (j) {
                if (i > 1) F[i][j] = add(F[i][j], F[i-2][j-1]);
                else F[i][j] = 1;
            }
        }
    }

    FOR(i,1,k) {
        int gap = n - i;
        b.emplace_back(gap / k);
        b.emplace_back(gap / k);
    }

    int now = 0;
    dp[now] = 1;
    FOR(i,0,SZ(b)-1) {
        int x = b[i];
        int nextNow = x + now;
        FOR(j,0,nextNow) dptmp[j] = 0;
        FOR(j,0,now)
            FOR(p,0,x) dptmp[j+p] = add(dptmp[j+p], mul(dp[j], F[x][p]));
        FOR(j,0,nextNow) dp[j] = dptmp[j];
        now = nextNow;
    }

    // FOR(i,0,n) cout << dp[i] << ' ';
    // cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> k;
    f[0] = 1;
    FOR(i,1,n) f[i] = mul(f[i-1], i);

    getM();

    ll res = 0;
    FOR(i,0,n) {
        ll p = mul(dp[i], f[n-i]);
        if (i % 2) res = sub(res, p);
        else res = add(res, p);
    }
    cout << res;

    return 0;
}


Measured memory_bytes: 124288
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define printP(x) "(" << (x).first << ", " << (x).second << ")"
#define mod 1000000007
using namespace std;
typedef pair<llint, llint> P;

llint n, m;
vector<llint> G[100005];
llint color[100005];

bool dfs(int v, int p, int c)
{
	color[v] = c;
	bool ret = true;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		if(color[G[v][i]] == -c) continue;
		if(color[G[v][i]] == c){
			ret = false;
			continue;
		}
		ret &= dfs(G[v][i], v, -c);
	}
	return ret;
}

int main(void)
{
	cin >> n >> m;
	llint u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	llint cnt = 0, bcnt = 0, icnt = 0;
	for(int i = 1; i <= n; i++){
		if(color[i]) continue;
		if(G[i].size() == 0) icnt++;
		else if(dfs(i, -1, 1)) bcnt++;
		else cnt++;
	}
	llint ans = icnt*n*2 - icnt*icnt;
	ans += 2*bcnt*cnt + cnt*cnt;
	ans += 2*bcnt*bcnt;
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 14208
using System;
using System.Linq;

namespace AtCoder.Abc140
{
    public class QuestionC
    {
        public static void Main(string[] args)
        {
            // 整数の入力
            int n = int.Parse(Console.ReadLine());
            var bArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

            //a0はb0と一致する
            long result = bArray[0];
            for(int i = 1; i < bArray.Length; i++)
            {
                var ai = Math.Min(bArray[i - 1], bArray[i]);
                result += ai;
            }

            //a(n-1)はb(n-2)と一致する
            result += bArray[n - 2];

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 13268
#include <stdio.h>

int main(void) {
	int K;
	int X;
	int res;

	scanf("%d", &K);
	scanf("%d", &X);

	//K 個数　X　座標

	res = K * 2 - 1;

	for (int i = X - (K - 1); i < res + X - (K - 1); i++)
	{
		printf("%d ", i);
	}

	printf("\n");

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

void main_(); signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  main_(); return 0;
}

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
template<class T> constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y<H&&0<=x&&x<W; }

void main_() {

  for(int H, W; cin >> H >> W && (H || W);) {
    vector<string> F(H);
    rep(i, H) cin >> F[i];
    vector<vector<bool>> vis(H, vector<bool>(W));
    std::function<void(int, int, char)> dfs = [&](int y, int x, char ch) {
      rep(i, 4) {
        int ny = y+dy[i], nx = x+dx[i];
        if(!in_range(ny, nx, H, W)) { continue; }
        if(F[ny][nx] != ch) { continue; }
        if(vis[ny][nx]) { continue; }
        vis[ny][nx] = 1;
        dfs(ny, nx, ch);
      }
    };

    int ans = 0;
    rep(i, H) rep(j, W) {
      if(!vis[i][j]) {
        vis[i][j] = 1;
        dfs(i, j, F[i][j]);
        ans ++;
      }
    }
    cout << ans << endl;
  }

}

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

int main(){
    int n,a,b,c,d;
    string s;
    cin >> n >> a >> b >> c >> d >> s;
    for(int i = min(a,b); i < max(c,d)-2; i++){
        if(s.substr(i,2) == "##"){
            cout << "No" << endl;
            return 0;
        }
    }
    if(c < d){
        cout << "Yes" << endl;
        return 0;
    }else{
        for(int i = b-2; i < d-1; i++){
            if(s.substr(i,3) == "..."){
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
    }
    return 0;
}




Measured memory_bytes: 3764
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	mp := map[string]int{}
	for i := 0; i < n; i++ {
		s := next()
		mp[s]++
	}

	putf("AC x %d\n", mp["AC"])
	putf("WA x %d\n", mp["WA"])
	putf("TLE x %d\n", mp["TLE"])
	putf("RE x %d\n", mp["RE"])
}


Measured memory_bytes: 2200
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (4 * m * a[i] >= sum) {
      cnt++;
    }
  }
  cout << (m <= cnt ? "Yes" : "No") << endl;
  return 0;
}

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

int main() {
	int x, a, b;
	cin >> x >> a >> b;
	int xa, xb;
	if (x - a < 0)xa = (x - a) * -1;
	else xa = x - a;
	if (x - b < 0) xb = (x - b) * -1;
	else xb = x - b;
	if (xa < xb)cout << "A" << endl;
	else cout << "B" << endl;
}

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

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  int i = a;
  
  while(i<=b){
    if( i-a<k || b-i<k ){
      cout << i << endl;
    }
    i++;
  }  
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;
int main(void){
  int n, m;
  cin>>n>>m;
  cout<<(n-1)*(m-1)<<endl;
}

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

typedef long long ll;

int w[1000001];
int n,k;

bool check(ll p){
    ll cost=0;
    ll cou=0;
    for(int i=0;i<k;i++){
        cost=w[cou];
        while(p-cost>=0){
            cou++;
            if(cou==n){
                return true;
            }
            cost+=w[cou];
        }
    }
    return false;
}

ll solve(){
    ll l=0,r=1000000000LL;
    while(r-l>1){
        ll mid=(r+l)/2;
        if(check(mid)){
            r=mid;
        }else{
            l=mid;
        }
//        cout << r << endl;
    }

    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> w[i];
    }
//    for(int i=0;i<n;i++)cout << w[i] << (i!=n-1?" ":"\n");
    ll ans = solve();
    cout << ans << endl;
}



Measured memory_bytes: 3520
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Mll = M<ll, ll>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin(),ie=(c).rend();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n;

int main() {
    cin >> n;
    Vi a(n);
    REP(i, n) cin >> a[i];

    VVi bitcnt(n+1, Vi(20, 0));
    REP(i, n) {
        REP(j, 20) {
            if (a[i] & (1 << j)) {
                bitcnt[i+1][j]++;
            }
        }
    }

    ll res = 0;
    int right = 1;
    Vi cnt(20, 0);
    REP2(left, 1, n+1) {
        while (right <= n) {
            bool f = false;
            REP(i, 20) {
                f |= cnt[i] + bitcnt[right][i] > 1;
            }
            if (f) break;
            REP(i, 20) {
                cnt[i] += bitcnt[right][i];
            }
            right++;
        }
        res += right - left;

        REP(i, 20) {
            cnt[i] -= bitcnt[left][i];
        }
    }
    cout << res << '\n';

    return 0;
}


Measured memory_bytes: 24448
#include <stdio.h>
int main (){
int a=0,b=0,c=0;
scanf("%d %d %d",&a,&b,&c);
if(c>=a && c>=b)
printf("%d",a+b);
else if (b>=a && b>=c)
printf("%d",a+c);
else
printf("%d",c+b);

return 0;
}


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

typedef long long ll;
#define vi vector<int>
#define mii map<int,int>

int main() {
	int n,m,a,ans;
	ll sum = 0;
	cin >> n >> m;
	while(m--) {
		cin >> a;
		sum += a;
	}
	
	if(sum == n) {
		ans = 0;
	} else if(sum > n) {
		ans = -1;
	}
	else {
		ans = n-sum;
	}
		
	cout << ans << "\n";
}


Measured memory_bytes: 3632
/*
 * Author : Andrew J
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair <ll , ll> ii;
void in(ll &x);
#define fi first
#define se second
#define pb push_back
// const ll N = ;
ll x,k,d;

int main() {
   in(x); in(k); in(d);
   ll t = abs(x) / d;
   ll modular = abs(x) % d;
   if (k > t) {
      if (k % 2 == t % 2) {
         printf("%lld\n" , modular);
      } else {
         printf("%lld\n" , abs(modular - d));
      }
   } else {
      printf("%lld\n" , abs(x) - k * d);
   }
   return 0;
}

void in(ll &x){
	bool neg = false;
	register ll c;
	x = 0;
	c = getchar();
	if(c == '-'){
		neg = true;
		c = getchar();
	}
	for (; c > 47 && c < 58; c = getchar())
	x = (x << 1) + (x << 3) + c - 48;
	if (neg) x *= -1;
}


Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=10,M=1000;
int n,m,s;
char a[N+1][M+5];
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	int ans=inf;
	for(int i=0;i<1<<n-1;i++){//暴力枚举2^(n-1)种水平切割状态 
		vector<int> pos;//水平切割处 
		pos.pb(0);
		for(int j=1;j<n;j++)if(i&1<<j-1)pos.pb(j);
		pos.pb(n);
		int now=pos.size()-2;//此水平切割状态当前切割次数 
		vector<int> cnt(pos.size()-1,0);//水平切割的每一块当前'1'的个数 
		for(int j=1;j<=m;j++){//从左往右贪心 
			bool ok=true; 
			vector<int> cnt0(pos.size()-1,0);//本列水平切割的每一块'1'的个数 
			for(int k=0;k<cnt.size();k++){//枚举水平切割的每一块 
				for(int o=pos[k]+1;o<=pos[k+1];o++)cnt0[k]+=a[o][j]^48;
				if(cnt0[k]>s)goto label_end;//不能要 
				if(cnt[k]+cnt0[k]>s)ok=false;//需要竖直切割 
			}
			if(ok)for(int k=0;k<cnt.size();k++)cnt[k]+=cnt0[k];//不竖直切割
			else now++,cnt=cnt0;//竖直切割 
		}
		ans=min(ans,now);//更新答案 
	label_end:;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 19 20:52:57 2020

@author: over-
"""

H, N=map(int,input().split())
A=input().split()

S=0
for i in range(N):
    S+=int(A[i])

if S>=H:
    print('Yes')
else:
    print('No')


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

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

Measured memory_bytes: 640
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2242
// ??????1000??????Eraname????????????????????????????????¶?????????????????¨?????????????????´??¨???????????¨??????????????£????????????????????´???Eraname???Key????????£??????????????´?????¢?´¢??????
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int n, q, year1, year2, query;
string name;
int main() {
    while (scanf("%d%d",&n,&q)) {
        if (n==0&&q==0) break;
        map<string, P> era;
        vector<string> names;
        for (int i=0; i<n; i++) {
            cin >> name >> year1 >> year2;
            era[name] = P(year2-year1+1, year2);
            names.push_back(name);
        }
        for (int i=0; i<q; i++) {
            scanf("%d",&query);
            for (int j=0; j<names.size(); j++) {
                P p = era[names[j]];
                if (p.first <= query && p.second >= query) {
                    cout << names[j] << " " << query-p.first+1 << endl;
                    break;
                } else if (j == names.size()-1) {
                    puts("Unknown");
                }
            }
        }
    }
}

Measured memory_bytes: 1396
#include <cstdio>
#include <vector>

using namespace std;

struct node{
    int key;
    int parent, left, right;
    node(){ parent=-1; left=-1; right=-1; }
};

vector<node> tree;
int root=-1;

void print_pre(int id)
{
    if(id==-1){ return; }
    printf(" %d", tree[id].key);
    print_pre(tree[id].left);
    print_pre(tree[id].right);
}

void print_in(int id)
{
    if(id==-1){ return; }
    print_in(tree[id].left);
    printf(" %d", tree[id].key);
    print_in(tree[id].right);
}

void insert(int z)
{
    int y=-1;
    int x=root;
    while(x!=-1){
        y=x;
        if(tree[z].key<tree[x].key){
            x=tree[x].left;
        } else{
            x=tree[x].right;
        }
    }
    tree[z].parent=y;
    if(y==-1){
        root=z;
    } else if(tree[z].key<tree[y].key){
        tree[y].left=z;
    } else{
        tree[y].right=z;
    }
}

int find(int key)
{
    int x=root;
    while(x!=-1){
        int k=tree[x].key;
        if(key==k){
            return x;
        } else if(key<k){
            x=tree[x].left;
        } else{
            x=tree[x].right;
        }
    }
    return -1;
}

void delete_(int z)
{
    auto which=[z](){
        auto p=&tree[tree[z].parent];
        if(p->left==z){
            return &p->left;
        } else{
            return &p->right;
        }
    };
    if(tree[z].left==-1 && tree[z].right==-1){
        if(tree[z].parent!=-1){
            *(which())=-1;
        } else{
            root=-1;
        }
    } else if(tree[z].left!=-1 && tree[z].right!=-1){
        tree[z].key=tree[tree[z].right].key;
        delete_(tree[z].right);
    } else{
        if(tree[z].left!=-1){
            if(tree[z].parent!=-1){
                *(which())=tree[z].left;
            } else{
                root=tree[z].left;
            }
            tree[tree[z].left].parent=tree[z].parent;
        } else{
            if(tree[z].parent!=-1){
                *(which())=tree[z].right;
            } else{
                root=tree[z].right;
            }
            tree[tree[z].right].parent=tree[z].parent;
        }
    }
}

int main()
{
    int m;
    scanf("%d", &m);
    tree=vector<node>(m);
    int n=0;
    for(int i=0; i<m; i++){
        char buf[8]; scanf("%s", buf);
        if(*buf=='i'){
            int k; scanf("%d", &k);
            tree[n].key=k;
            insert(n);
            n++;
        } else if(*buf=='f'){
            int k; scanf("%d", &k);
            printf("%s\n", find(k)!=-1 ? "yes" : "no");
        } else if(*buf=='d'){
            int k; scanf("%d", &k);
            int id=find(k);
            if(id!=-1){
                delete_(id);
            }
        } else{
            print_in(root);
            printf("\n");
            print_pre(root);
            printf("\n");
        }
    }
    return 0;
}

Measured memory_bytes: 9924
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=2005;
bitset<N*N>dp;
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,sum=0;
    scanf("%d",&n);
    dp[0]=1;
    while(n--){
		int x;
		scanf("%d",&x);
		dp|=dp<<x;sum+=x;
	}
	for(int i=0;i<=sum;i++)
		if(i*2>=sum and dp[i]){
			printf("%d\n",i);
			return 0;
		}
	return 0;
}


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

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

const int MOD = 1e+9 + 7;
long long num_W = 1, num_B = 1;

void dfs(int pos, int par, vector<vector<int>>& G, vector<vector<long long>>& dist)
{
    dist[pos][0] = dist[pos][1] = 1;
    for(int v: G[pos]){
        if(v != par){
            dfs(v, pos, G, dist);
            dist[pos][0] *= dist[v][0]+dist[v][1];
            dist[pos][1] *= dist[v][0];
            dist[pos][0] %= MOD;
            dist[pos][1] %= MOD;
        }
    }
}

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    REP(i, N-1){
        int x, y;
        cin >> x >> y;
        --x, --y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    //dist[i][j]: 頂点 i の色が j のとき、頂点 i を根とした部分木の塗り方の数 (0: 白, 1: 黒)
    vector<vector<long long>> dp(N, vector<long long>(2));
    dfs(0, -1, G, dp);
    cout << (dp[0][0]+dp[0][1])%MOD << endl;

    return 0;
}

Measured memory_bytes: 19584
#include<iostream>
using namespace std;
int main(){
    int a[4],b[4];
    while(cin >> a[0]){
        int hit =0,blow = 0;
        for(int i=1;i<4;i++)
            cin >> a[i];
        for(int i=0;i<4;i++)
            cin >> b[i];
        for(int k=0;k<4;k++){
            for(int j=0;j<4;j++){
                if(a[k]==b[j]){
                    if(k==j) hit++;
                    else blow++;
                }
            }
        }
        cout << hit <<" "<< blow <<endl;
    }
}

Measured memory_bytes: 2984
import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline
n, q = list(map(int, readline().split()))
# 双方向に張る
tree = [[] for _ in range(n)]
for i in range(n-1):
    a, b = list(map(int, readline().split()))
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

# queryのスコア表を作る
total = [0 for _ in range(n)]
for i in range(q):
    p, x = list(map(int, readline().split()))
    total[p - 1] += x

# dfs
ans = [0 for _ in range(n)]
def dfs(v, p, value):
    value += total[v]
    ans[v] = value
    for c in tree[v]:
        if c == p: continue
        dfs(c, v, value)

dfs(0, -1, 0)
print(*ans)

Measured memory_bytes: 243396
// https://atcoder.jp/contests/abc131/tasks/abc131_a
//
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! dvec {
    ($t:expr ; $len:expr) => {
        vec![$t; $len]
    };

    ($t:expr ; $len:expr, $($rest:expr),*) => {
        vec![dvec!($t; $($rest),*); $len]
    };
}

#[allow(unused_macros)]
macro_rules! ifv {
    ($t:expr, $a:expr, $b: expr) => {
        if $t { $a } else { $b }
    }
}

#[allow(unused_macros)]
macro_rules! fill {
    ($t:expr, $v:expr) => {
        for i in 0..$t.len() {
            $t[i] = $v;
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
        s: chars
    };
    let bad = s[0] == s[1] || s[1] == s[2] || s[2] == s[3];
    println!("{}", ifv!(bad, "Bad", "Good"));
}


Measured memory_bytes: 4352
#include<iostream>
using namespace std;
int main() {
	int count = 0, n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (i * j < n)
				count++;
			else break;
		}
	}
	printf("%d", count);
}

Measured memory_bytes: 3760
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <typeinfo>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

int main(){

    int n;
    cin >> n;

    vector<int> r(n);

    for(int i=0; i<n; i++){
        cin >> r[i];
    }

    int maxv = -2000000000;
    int minv = r[0];

    for(int i=1; i<n; i++){
        maxv = max(maxv, r[i]-minv);
        minv = min(minv, r[i]);
    }

    cout << maxv << endl;

    return 0;



    // TLE
    // int max = r[1] - r[0];
    //
    // for(int i=0; i<n-1; i++){
    //     for(int j=i+1; j<n; j++){
    //         if(max<r[j]-r[i]){
    //             max = r[j]-r[i];
    //         }
    //     }
    // }
    //
    // cout << max << endl;

}



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

int main(){
  int a=0;
  vector <char> b(4);
  
  for(int i=0;i<4;i++)
    cin >> b.at(i);
  
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      if(b.at(i) == b.at(j))
        a++;
    }
  }
  if(a == 8)
    cout <<"Yes" <<endl;
  else
    cout <<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
typedef long double lb;
typedef long double ld;
typedef pair<int,int> P;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0L)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1e9+7;
#define INF 1e9;
#define EPS 1e-9;

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}initial_;


signed main(){
  int N;cin>>N;
  vector<int> A(N);
  REP(i,0,N)cin>>A[i];

  int ans,cnt=0;
  vector<int> tmp_A=A;
  // case 偶数が正
  for(int i=0;i<N;i++){
    if(i%2==0&&A[i]<=0){
      cnt+=-(tmp_A[i]-1);
      tmp_A[i]=1;
    }
    if(i%2==1&&A[i]>=0){
      cnt+=tmp_A[i]+1;
      tmp_A[i]=-1;
    }
  }
  int S=tmp_A[0];
  // debug(tmp_A)
  REP(i,1,N){
    if((S+tmp_A[i])*S>=0){
      cnt+=abs(S+tmp_A[i])+1;
      S=(tmp_A[i]<0?-1:1);
    }
    else{
      S+=tmp_A[i];
    }
  }
  ans=cnt;
  // case 偶数が負
  cnt=0;tmp_A=A;
  for(int i=0;i<N;i++){
    if(i%2==1&&A[i]<=0){
      cnt+=-(tmp_A[i]-1);
      tmp_A[i]=1;
    }
    if(i%2==0&&A[i]>=0){
      cnt+=tmp_A[i]+1;
      tmp_A[i]=-1;
    }
  }
  // debug(tmp_A)
  // debug(cnt)
  S=tmp_A[0];
  REP(i,1,N){
    if((S+tmp_A[i])*S>=0){
      // debug(i)debug(S)
      cnt+=abs(S+tmp_A[i])+1;
      S=(tmp_A[i]<0?-1:1);
      // debug(cnt)
    }
    else{
      S+=tmp_A[i];
    }
  }
  ans=min(ans,cnt);
  print(ans)



}


Measured memory_bytes: 1792
//****************************//
/**********  main *************/
//****************************//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(i=0;i<n;i++)
#define FOR(i,a,b) for(i=a;i<b;i++)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())


int main() {

	std::cin.tie(0);

	ll h,w ;
	cin >> h >> w ;

	ll htmp,hmod;
	ll wtmp,wmod;
	ll tmp;
    ll hh,ww;

    if(h==1 || w == 1){
        cout << 1 << endl;
        return 0;
    }

	wtmp = w/2;
	wmod = w%2;

	htmp = h/2;
	hmod = h%2;
    hmod==1 ? hh = h-1 : hh = h;

	tmp = wtmp * hh;

	if(wmod == 1) tmp = tmp + htmp;
	if(hmod == 1) tmp = tmp + wtmp;
	if(hmod == 1 && wmod == 1) tmp = tmp + 1;

    cout << tmp << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;

int main() {

	int A;
	int B;
	cin >> A;
	cin >> B;

	int num = A;
	int ans = 1;
	while (num < B) {
		ans += 1;
		num += A - 1;
	}

	if (B == 1) {
		ans = 0;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

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

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

    int64_t sum = 0;
    int64_t current = 0;
    int64_t n = 1;
    int64_t limit = 0;
    for (auto c : s) {
        if (c == '<') {
            ++current;
            limit = current;
            n = 0;
        } else {
            --current;

            if (current < 0) {
                --limit;
                if (limit == 0) {
                    ++n;
                }
                sum += (-current) * n;
            }
            current = 0;
            ++n;
        }
        sum += current;
    }

    cout << sum << endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using P = pair<long long,long long>;
template <class T> using vec = vector<T>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b; cin >> a >> b;
    cout << a*b << endl;
}

Measured memory_bytes: 3640
#include <iostream>

using namespace std;

int main(){
  long long N,A,B; cin >> N >> A >> B;
  if((B-A)%2==0) cout << (B-A)/2 << endl;
  else{
    //左行って折り返しか右行って折り返し
    //左の場合、Aが(A-1)下がって1回とどまる
    //その間BはA下がる
    //ここで両者1と(B-A)にいる
    //すると(B-A-1)は偶数なので÷2回でOK
    cout << min(A+(B-A-1)/2,(N-B)+1+(B-A-1)/2) << endl;
  }
}

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

int map[17][17];
bool disable[17][17];

int solve(int a, int b) {
  for (int x = 1; x <= a; x++) {
    for (int y = 1; y <= b; y++) {
      if (x == 1 and y == 1) {
        map[x][y] = 1;
      } else {
        map[x][y] = (disable[x][y])? 0 : map[x-1][y] + map[x][y-1];
      }
    }
  }
}

void init() {
  for (int x = 0; x < 17; x++) {
    for (int y = 0; y < 17; y++) {
      map[x][y] = 0;
      disable[x][y] = false;
    }
  }
}

int main() {
  int a, b;
  while (cin >> a >> b and (a != 0 or b != 0)) {
    init();
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
      int x, y;
      cin >> x >> y;
      disable[x][y] = true;
    }

    solve(a, b);

    cout << map[a][b] << endl;
  }
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <stdlib.h>//random,NULL
#include <string.h>
#include <time.h>
#include <unistd.h>//sleep()
#include <math.h>
#include <stdbool.h>

#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000


int main(){
  char buf[1024];
  int N;

  fgets(buf,sizeof(buf),stdin);
  sscanf(buf, "%d", &N);

  int *C=(int *)malloc(sizeof(int)*(N+1));
  C[0]=0;
  srep(i,1,N+1){
    fgets(buf,sizeof(buf),stdin);
    sscanf(buf, "%d", &C[i]);
  }

  long *dp=(long *)calloc(N+1, sizeof(long));
  dp[0]=1;

  //色jについて、それまでの合計を記録しておく。
  long *memo=(long *)calloc(200001, sizeof(long));

  srep(i,1,N+1){
    if(C[i]==C[i-1]){
      dp[i]=(dp[i]+dp[i-1])%1000000007;
    }
    else{
      dp[i]=(dp[i]+dp[i-1])%1000000007;
      dp[i]=(dp[i]+memo[C[i]])%1000000007;
      memo[C[i]]=(memo[C[i]]+dp[i-1])%1000000007;
    }
  }

  // rep(i,N+1){
  //   printf("dp[%d] = %ld\n", i, dp[i]);
  // }

  printf("%ld\n", dp[N]);


  return 0;
}


Measured memory_bytes: 4096
import java.util.*;

public class Main{
	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);

		int h = scan.nextInt();
		int w = scan.nextInt();
		String[] t = new String[h];
		for(int i = 0; i < h; i++)
			t[i] = scan.next();

		int r = scan.nextInt();
		int c = scan.nextInt();
		String[] p = new String[r];
		for(int i = 0; i < r; i++)
			p[i] = scan.next();

		PtFind f = new PtFind(t, p, false);

		scan.close();
		System.exit(0);
	}
}

class PtFind{
	boolean debug;

	public PtFind(String[] t, String[] p, boolean d){
		debug = d;

		boolean[][] jg = new boolean[t.length - p.length + 1][t[0].length() - p[0].length() + 1];
		//length????????????????´???°???length()??????????????°
		for(int y = 0; y < jg.length; y++)
			for(int x = 0; x < jg[0].length; x++)
				jg[y][x] = true; //true?????£??\??????

		for(int r = 0; r < p.length; r++){
			StFind stf = new StFind(p[r], d);
			for(int y = 0; y < jg.length; y++){
				boolean[] result = new boolean[jg[0].length];
				stf.find(t[y+r], p[r], result);
				for(int x = 0; x < jg[0].length; x++)
					jg[y][x] &= result[x];
					//a &= b??????a = a & b
			}
		}

		for(int y = 0; y < jg.length; y++)
			for(int x = 0; x < jg[0].length; x++)
				if(jg[y][x])
					System.out.println(y + " " + x);
	}
}

//
class StFind{
	boolean debug;
	int[] msft;
	int[] sft = new int[Character.MAX_CODE_POINT];

	public StFind(String p, boolean d){
		debug = d;
		createMatchPt(p);
	}

	public void find(String t, String p, boolean[] result){
		int x = 0;
		for(int st = 0; st < t.length() - p.length() + 1;){
			if((x = isBaEqual(t, p, st)) == p.length())
				result[st] = true;
			st += msft[x];
		}
	}

	private void createMatchPt(String p){
		msft = new int[p.length() + 1];
		msft[0] = p.length();

		for(int sft = p.length(); sft > 0; sft--){
			for(int m = 1; m < msft.length; m++){
				if(m > p.length() - sft){
					msft[m] = sft;
					continue;
				}
				if(p.charAt(p.length() - m) != p.charAt(p.length() - m- sft)){
					msft[m-1] = sft;
					break;
				}else if(m == p.length() -sft)
					msft[m] = sft;
			}
		}

		if(debug)
			for(int i = 0; i < msft.length; i++)
				System.out.println("--- " + i + " : " + msft[i]);
	}

	//
	int stPre = 0;
	int retPre = 0;

	private int isBaEqual(String t, String p, int st){
		int clen = p.length();
		int stlen = stPre + p.length();
		if(st >= stlen - retPre && st < stlen){
			clen -= stlen - st;
		}
		/*
		if(st >= stPre + p.length() - retPre && st < stPre + p.length()){
		
			clen -= stPre + p.length() - st;
		}
		*/
		for(int i = 0; i < clen; i++){
			if(t.charAt(p.length() - 1 - i + st) != p.charAt(p.length() - 1 - i)){
				stPre = st;
				retPre = i;
				return i;
			}
		}
		stPre = st;
		retPre = p.length();
		return p.length();
	}
}

Measured memory_bytes: 692208
#import <Foundation/Foundation.h>
#import <stdarg.h>

@interface StdIO : NSObject
+(NSMutableString*)stringFromStdIn; // 標準入力から NSString を得る
+(void)printf:(NSString*)format, ...; // 標準出力へ出力
@end

@implementation StdIO
+(NSMutableString*)stringFromStdIn
{
    NSFileHandle *handle = [NSFileHandle fileHandleWithStandardInput];
    NSMutableString *result = [NSMutableString string];
    NSData *data = [handle availableData];
    while ([data length] > 0) {
        [result appendString:[[[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding] autorelease]];
        data = [handle availableData];
    }
    NSUInteger length = [result length];
    if (length >= 1 && [result characterAtIndex:length-1] == '\n') { // 入力末尾に改行文字があれば削除
        [result deleteCharactersInRange:NSMakeRange(length-1,1)];
    }
    return result;
}
+(void)printf:(NSString*)format, ...
{
    va_list arguments;
    va_start(arguments, format);
    NSString *string = [[[NSString alloc] initWithFormat:format arguments:arguments] autorelease];
    NSFileHandle *fileHandle = [NSFileHandle fileHandleWithStandardOutput];
    [fileHandle writeData:[string dataUsingEncoding:NSUTF8StringEncoding]];
    va_end(arguments);
}
@end


NSInteger CEIL(double x) {
    NSInteger n = (NSInteger)x;
    return n + (((x != n) && (x > 0)) ? 1 : 0);
}

int main() {
    @autoreleasepool {
        NSArray *numbers = [[StdIO stringFromStdIn] componentsSeparatedByString:@"\n"];
        NSInteger A = [[numbers objectAtIndex:0] integerValue];
        NSInteger B = [[numbers objectAtIndex:1] integerValue];
        NSInteger C = [[numbers objectAtIndex:2] integerValue];
        NSInteger X = [[numbers objectAtIndex:3] integerValue] / 50;
        NSInteger count = 0;
        for (NSInteger x=0; x <= MIN(A,X/10); x++) {
            NSInteger Y = X-10*x;
            count += MAX( MIN(B, Y/2) - MAX(0, CEIL((double)(Y-C)/2)) + 1, 0);
        }
        [StdIO printf:@"%ld", count];
    }
    return 0;
}


Measured memory_bytes: 2404
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define MX              200005
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
void codeforces()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
int32_t main()
{
    
    // w(t)
    {
       int n, k;
       cin>>n>>k;
       int a[n];
       for(int i=0; i<n; i++) cin>>a[i];
       sort(a, a+n);
       int ans = 0;
       for(int i=0; i<k; i++) ans += a[i];
       cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 3604
N, M = map(int,input().split())

AC = [0] * N
WA = [0] * N
wa = 0
ac = 0
for i in range(M):
    p,S = input().split()
    if S == 'AC':
        if AC[int(p)-1] == 0:
            ac += 1
            AC[int(p)-1] += 1
    elif AC[int(p)-1] == 0:
        WA[int(p)-1] += 1

for i in range(N):
    if AC[i] > 0:
        wa += WA[i]

print(str(ac) + ' ' + str(wa))

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

int main(){
  int n;
  std::map<std::string, int> mp;
  cin >> n;
  while(n--){
    string s;
    cin >> s;
    mp[s] += 1;
  }

  int max=0;
  for(auto i = mp.begin(); i != mp.end(); i++){
    if(i->second>max)max=i->second;
  }
  for(auto i = mp.begin(); i != mp.end(); i++){
    if(i->second == max) cout<< i->first<< endl;
  }
}

Measured memory_bytes: 25216
/**
 *    author:  tourist
 *    created: 17.01.2020 01:59:15       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  auto IsSubset = [&](long long a, long long b) {
    return ((a & b) == a);
  };
  auto Get = [&](long long X, long long Y) {
    int z = 0;
    for (int i = 0; i < n; i++) {
      if (X >= x[i]) {
        z ^= IsSubset(X - x[i], y[i] - Y);
      }
    }
    return z;
  };
  auto AddSubsets = [&](vector<int>& p, long long xb, long long xs, long long b) {
    long long a = xb - xs + 1;
    int shift = ((int) (xs % 3) + 3) % 3;
    for (int bit = 61; bit >= 0; bit--) {
      if (a & (1LL << bit)) {
        int cc  = __builtin_popcountll(b & ~(1LL << bit) & 0x5555555555555555LL);
        cc += 2 * __builtin_popcountll(b & ~(1LL << bit) & 0xAAAAAAAAAAAAAAAALL);
        if (cc == 0) {
          p[shift] ^= 1;
        } else {
          int t = (shift + (cc % 3 == 2 ? 2 : (1 - cc % 3))) % 3;
          p[t] ^= 1;
          p[(t + 1) % 3] ^= 1;
        }
        shift = (shift + (bit % 2 == 0 ? 1 : 2)) % 3;
        if (!(b & (1LL << bit))) {
          break;
        }
      }
      b &= ~(1LL << bit);
    }
  };
  auto Get3 = [&](long long X, long long Y) {
    vector<int> ret(3);
    for (int i = 0; i < n; i++) {
      if (X >= x[i]) {
        AddSubsets(ret, X, x[i], y[i] - Y);
      }
    }
    return ret;
  };
  const long long inf = (long long) 5e17;
  long long Y = -inf / 2;
  long long low = -inf, high = inf;
  while (low < high) {
    long long mid = low + ((high - low) >> 1);
    auto ret = Get3(mid, Y);
    if (ret[0] + ret[1] + ret[2] == 0) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  long long X = low;
  assert(Get(X, Y) == 1);
  for (int bit = 60; bit >= 0; bit--) {
    if (Get(X - (1LL << bit), Y)) {
      X -= 1LL << bit;
    }
  }
  long long minX = X;
  for (int bit = 60; bit >= 0; bit--) {
    if (Get(X + (1LL << bit), Y)) {
      X += 1LL << bit;
    }
  }
  long long maxX = X;
  cout << minX << " " << Y + (maxX - minX) << '\n';
  return 0;
}


Measured memory_bytes: 484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("D.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int cnt[4005][4005][2];
int query(int x1,int y1,int x2,int y2,int o){
    int ans=cnt[x2][y2][o];
    if (x1)
        ans-=cnt[x1-1][y2][o];
    if (y1)
        ans-=cnt[x2][y1-1][o];
    if (x1 && y1)
        ans+=cnt[x1-1][y1-1][o];
    return ans;
}
int main(){
    init();
    int n=readint(),k=readint();
    for(int i=1;i<=n;i++){
        int x=readint()%(2*k),y=readint()%(2*k),c=readchar()=='B';
        cnt[x][y][c]++;
        cnt[x+2*k][y][c]++;
        cnt[x+2*k][y+2*k][c]++;
        cnt[x][y+2*k][c]++;
    }
    for(int i=0;i<4*k;i++)
        for(int j=0;j<4*k;j++)
            for(int o=0;o<2;o++){
                if (i)
                    cnt[i][j][o]+=cnt[i-1][j][o];
                if (j)
                    cnt[i][j][o]+=cnt[i][j-1][o];
                if (i&&j)
                    cnt[i][j][o]-=cnt[i-1][j-1][o];
            }
    int ans=0;
    for(int i=0;i<2*k;i++)
        for(int j=0;j<2*k;j++)
            ans=max(ans,query(i,j,i+k-1,j+k-1,1)+query(i+k,j+k,i+2*k-1,j+2*k-1,1)+query(i,j+k,i+k-1,j+2*k-1,0)+query(i+k,j,i+2*k-1,j+k-1,0));
    printf("%d",ans);
}

Measured memory_bytes: 129280
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main()
{
	int r, c;
	cin>>r>>c;
	int dp[r][c];
	for(int i=0; i<r; i++){
		string s;
		cin>>s;
		for(int j=0; j<c; j++){
			if(s[j] == '.')
				dp[i][j] = 0;
			else
				dp[i][j] = -1;
		}
	}
	dp[r-1][c-1] = 1;
	for(int i=r-2; i>=0; i--){
		if(dp[i][c-1] != -1)
			dp[i][c-1] = dp[i+1][c-1];
	}
	for(int i=c-2; i>=0; i--){
		if(dp[r-1][i] != -1)
			dp[r-1][i] = dp[r-1][i+1];
	}
	for(int i = r-2; i>=0; i--){
		for(int j=c-2; j>=0; j--){
			if(dp[i][j] == -1)
				continue;
			int a=0, b=0;
			if(dp[i+1][j] != -1) 
				a = dp[i+1][j];
			if(dp[i][j+1] != -1)
				b = dp[i][j+1];
			dp[i][j] = (a+b)%mod;
		}
	}
	cout<<dp[0][0];
	
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

#define pb push_back
#define MAX 1000000

int dp[MAX];

using namespace std;

int main(void)
{
	int n,x;
	int i1,i2;

	while(1){
		cin>>n>>x;
		if(n+x==0) break;

		vector<int> v(n);
		memset(dp,0,sizeof(dp));

		for(i1=0;i1<n;i1++){
			cin>>v[i1];
			dp[v[i1]]=1;
		}

		for(i1=0;i1<=x;i1++){
			if(dp[i1]==1) {
				for(i2=0;i2<n;i2++){
					if((i1+v[i2])<MAX) dp[i1+v[i2]]=1;
				}
			}
		}

		for(i1=x;i1>0;i1--){
			if(dp[i1]==1) {

				for(i2=2;i2*i2<=i1;i2++){
					if(i1%i2==0) break;
				}
				if(i2*i2>i1) break;
			}
		}

		if(i1==0) cout<<"NA"<<endl;
		else cout<<i1<<endl;
	}


	return 0;

}

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

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

using namespace std;
using graph=vector<vector<int>>;

class mint{
	static const int MOD=998244353;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }
	mint operator-()const{ return mint(-x); }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint operator+(long long y,const mint& m){ return m+y; }
mint operator*(long long y,const mint& m){ return m*y; }

mint pow(mint m,long long k){
	mint res=1;
	for(;k>0;k>>=1,m*=m) if(k&1) res*=m;
	return res;
}

int main(){
	int n; scanf("%d",&n);
	vector<graph> G(3,graph(n));
	rep(i,3){
		int m; scanf("%d",&m);
		rep(j,m){
			int u,v; scanf("%d%d",&u,&v); u--; v--;
			if(u>v) swap(u,v);
			G[i][u].emplace_back(v);
		}
	}

	vector<vector<int>> grundy(3,vector<int>(n));
	rep(i,3){
		vector<int> used(1e5+1,-1);
		for(int u=n-1;u>=0;u--){
			for(int v:G[i][u]){
				used[grundy[i][v]]=u;
				while(used[grundy[i][u]]==u) grundy[i][u]++;
			}
		}
	}

	int g_max=0;
	rep(i,3) rep(u,n) g_max=max(g_max,grundy[i][u]);

	vector<vector<mint>> wt(3,vector<mint>(g_max+1));
	rep(i,3) rep(u,n) wt[i][grundy[i][u]]+=pow(mint(10),18*(u+1));

	mint ans=0;
	rep(g0,g_max+1) rep(g1,g_max+1) {
		int g2=g0^g1;
		if(g2>g_max) continue;
		ans+=wt[0][g0]*wt[1][g1]*wt[2][g2];
	}
	cout<<ans<<'\n';

	return 0;
}


Measured memory_bytes: 14168
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  long long ans=0;
  cin>>n>>k;
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=n;j++)
    {
        if((k-i-j)>=0 && (k-i-j)<=n)ans++;
    }
  }
  cout<<ans<<endl;
 return 0;
}

Measured memory_bytes: 256