akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<cassert>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
ll fact(ll x, ll k, ll p) {//最大値、個数、あまり
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x%p;
		x = x * x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
short ctos(char a) {
	return (int)(a - '0');
}
#define int long long
const long long Inf = 4523372036854775807;
const int inf = 15000000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
int n;
int a[300000], b[300000];
int c[300000], d[300000];
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	int ans = 0;
	for (int i = 0; i < 30; i++) {
		int t = 1 << (i + 1);
		for (int j = 0; j < n; j++) {
			c[j] = a[j] % t;
			d[j] = b[j] % t;
		}
		sort(d, d + n);
		int sum = 0;
		for (int j = 0; j < n; j++) {
			sum += upper_bound(d, d + n, t - 1 - c[j]) -
				lower_bound(d, d + n, (1 << i) - c[j]);
			sum += upper_bound(d, d + n, 2 * t - 1 - c[j]) -
				lower_bound(d, d + n, t + (1 << i) - c[j]);
		}
		if (sum % 2 == 1) {
			ans |= (1 << i);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 8320
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())

int n;
LL a[200010], b[200010];
vector < pair <LL, LL > > v;

void solve() {
  cin >> n;
  REP(i, n) cin >> a[i] >> b[i];
  REP(i, n) v.PB(make_pair(b[i], a[i]));
  sort(ALL(v));
  LL sum = 0;
  REP(i, n) {
    sum += v[i].second;
    if (sum > v[i].first) {
      cout << "No" << endl;
      return;
    }
  }
  cout << "Yes" << endl;
}

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


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

int main() {
  int a,b,sum,i;
  sum = 0;
  cin >> a >> b;
  for(i = a; i <= b; i++) {
    if(i/10000 == i%10 && (i/1000)%10 == (i/10)%10) {
      sum++;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    int n;
    cin >> n;
    vector<ll> v(n);
    rep(i, n) cin >> v[i];
    bool b = [&] {
        for (ll l:v) if (l % 2 == 1) return true;
        return false;
    }();

    cout << (b ? "first" : "second") << endl;

}


Measured memory_bytes: 3992
D=int(input())
c=list(map(int,input().split()))
s=[0]
last=[0]*26
for i in range(D):
  s.append(list(map(int,input().split())))
score=0
for i in range(1,D+1):
  t=int(input())-1
  score+=s[i][t]
  last[t]=i
  for j in range(26):
    score-=c[j]*(i-last[j])
  print(score)

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

#define int long long
#define pii pair<int, int>
#define pb push_back

int const N = 2e5 + 10 ; 
int par[N];
int sz[N];
void init(){
    for(int i = 1 ; i < N ; i++){
        par[i] = i; 
        sz[i] = 1;
    }
}
int find_parent(int i){
    if(par[i] == i){
        return i; 
    }
    return find_parent(par[i]);
}
void merge(int x,int y){
    int X = find_parent(x);
    int Y = find_parent(y);
    if(X == Y) return; 
    if(sz[X] > sz[Y]){
        swap(X,Y);
    }
    par[X] = par[Y];
    sz[Y] += sz[X];
    sz[X] = 0;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    init();
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, sz[i]);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 6812
N = int(input())
F = [list(map(int,input().split())) for i in range(N)]
P = [list(map(int,input().split())) for i in range(N)]

## ビット全探索
solver = []
for i in range(1 << 10): # range(2**10)と同値
    if i == 0:
      continue
    C = [0]*N
    for j in range(10):  # 10個の要素それぞれに対し
        if ((i >> j) & 1) == 1: # iの右からj桁目が1なら
            for k in range(N):
                C[k] += F[k][j] 
    profit = sum([P[k][C[k]] for k in range(N)])
    solver.append(profit)

print(max(solver))

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

using namespace std;

int main()
{
    int n,b,poz=1,spart=0,nr;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>nr;
        if(nr==poz)
        {
            poz++;

        }
    }
    if(poz==1) cout<<-1;
    else
    cout<<n-poz+1;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
//printf("%.12lf\n",mid);
//const long long sze = 2*(2^(long long)(ceil(log(100000)/log(2))));
/*
// get part of decimal
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
const long long mod = 1000000007;
const double eps = .0000000001;
inline void prep()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
};

string itos(int num){
 string str;
 int curr = 10;
 while (num){
   int val = num%curr;
   str += '0'+val;
 
   num /= curr;
 }
 reverse(str.begin(), str.end());
 return str;
}
vector<int> arr[100001];
int main(){
    prep();
    int n, m;
    cin >> n >> m;
    vector<int> arr[n+1];
    set<int> prefs;
    vector<pair<int, int> > stuff;
    vector<pair<int, int> > other;
    for (int i=0; i<m; i++){
      int pref, y;
      cin >> pref >> y;
      stuff.push_back({y, pref});
      other.push_back({y, pref});
    }
    sort(other.begin(), other.end());
    map<int, int> yrs;
    for (int i=0; i<other.size(); i++){
      int yr = other[i].first;
      int pref = other[i].second;
      arr[pref].push_back(yr);
      yrs[yr] = arr[pref].size();
    }
    for (int i=0; i<m; i++){
      int y = stuff[i].first;
      int pref = stuff[i].second;
      
      string newpref = itos(pref);
      string newpl = itos(yrs.find(y)->second);
      
      for (int j=0; j<6-newpref.length(); j++){
        cout << 0;
      }
      cout << newpref;
      for (int j=0; j<6-newpl.length(); j++){
        cout << 0;
      }
      cout << newpl;
      cout << endl;
    }
    return 0;
}      

Measured memory_bytes: 15596
N, X, Y = map(int,input().split())

import numpy as np
mat=np.array([[0]*N]*N)

for i in range(N-1):
    mat[i][i+1]=1
    mat[i+1][i]=1
mat[X-1][Y-1]=1
mat[Y-1][X-1]=1

from scipy.sparse.csgraph import shortest_path

from collections import Counter
ans=np.array(list(Counter(shortest_path(mat).reshape(-1,N*N)[0]).values()))

ans=np.pad(ans,[0,N-len(ans)],"constant")

for a in ans[1:]:
    print(a//2)

Measured memory_bytes: 103620
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextLong();
		}
		long ans = 0;
		long m = a[0];
		for(int i = 1;i < n; i++) {
			if(m >= a[i]) {
				ans += m - a[i];
			}else {
				m = a[i];
			}
		}
		System.out.println(ans);
	}

	static class FastScanner {
		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

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

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

	        return tokenizer.nextToken("\n");
	    }

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

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

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

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }
	}
}


Measured memory_bytes: 55496
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1;c+=j
  else:A[k]=R[j];j+=1
def s(A,l,r):
 if l+1<r:m=(l+r)//2;s(A,l,m);s(A,m,r);g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(c)


Measured memory_bytes: 27484
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <typename T>
bool PN(T x){ if (x <= 1) return false; if (x == 2) return true; for (int i = 2; i < sqrt(x) + 1; i++) if (x % i == 0) return false; return true;}
const ll MOD = 1e9+7;
long long Comb(int n, int i){long long ans = 1; if(i == 0 || i == n) return 1; else {for(int j = 1; j <= i; ++j){
      ans *=(n+1-j);
      ans /= j;
      ans %= MOD;} }return ans;}


void solve(){
  int a, b, c;
  cin >> a >> b >> c;
  cout << a + b + c -max(a, max(b, c)) << endl;
}

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


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


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int a,b;

  cin>>a>>b;
  int c=0;
   int x=b;
  while(b){
     b=b/10;
      c++;
  }
  int d=a*pow(10,c)+x;
  int e=0;
  for(int i=0;i<1000;i++){
    if(i*i==d){
      e++;
    }
  }
  if(e==0){
    cout<<"No";
  }else{
    cout<<"Yes";
  }
}



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

const int INF = std::numeric_limits<int>::max() / 2;
const long long INFLL = std::numeric_limits<long long>::max() / 2;

typedef std::pair<int, int> pii;
typedef std::pair<long long, long long> pll;

const int MAX_N = 205;

int t, n;
long long a[MAX_N];
std::vector<long long> v;
std::string s;

bool add(long long a)
{
	v.push_back(a);
	for (int i = 0; i < v.size(); ++i)
	{
		std::sort(v.begin() + i, v.end(), std::greater<long long>());
		for (int j = i + 1; j < v.size(); ++j)
			v[j] = std::min(v[j], v[j] ^ v[i]);
	}
	if (v.back() != 0)
		return true;
	else
	{
		v.pop_back();
		return false;
	}
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	
	std::cin >> t;
	while (t--)
	{
		std::cin >> n;
		for (int i = 0; i < n; ++i)
			std::cin >> a[i];
		std::cin >> s;
		v.clear();
		for (int i = n - 1; i >= 0; --i)
			if (add(a[i]) && s[i] == '1')
			{
				std::cout << "1\n";
				goto done;
			}
		std::cout << "0\n";
	done:
		continue;
	}
	
	return 0;
}

Measured memory_bytes: 3520
mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]
        
        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r): 
        return self.ncr(n+r-1, n-1)

X, Y = map(int, input().split())

comb = Combination(max(X, Y))

if 2*Y - X < 0 or 2*X - Y < 0 or (2*Y - X) % 3 != 0 or (2*X - Y) % 3 != 0:
    print("0")
else:
    M = (2*Y - X) // 3
    N = (2*X - Y) // 3
    print(comb.ncr(M+N,M))


Measured memory_bytes: 115660
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define LIM 100005
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define vi vector <int>
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(), x.end()


int32_t main()
{
  IOS;
  int tt,x,y,k,q,n,i,j;
  cin>>n;
  int add=0,minus=0;
  for(i=1;i<=n;i++){
    add+= i*(n-i+1);
  }
  for(i=0;i<n-1;i++)
  {
    cin>>x>>y;
    if(x>y)swap(x,y);
    minus+= x*(n-y+1);
  }
  cout<<add-minus;
}


Measured memory_bytes: 3648
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;

struct node
{
	int key;
	node* lc, * rc, * p;
};

node* root = 0;

void insert(int x)
{
	node* pre = root;        //设当前节点为根，以根为起点
	node* temp = pre;        //用来保存当前节点的临时指针

	node* in = (node*)malloc(sizeof(node));
	in->key = x;
	in->lc = 0;
	in->rc = 0;
	in->p = 0;

	while (pre != 0)        //找到将要插入的节点的父节点(当前节点)
	{
		temp = pre;
		if (in->key < pre->key)
			pre = pre->lc;
		else
			pre = pre->rc;
	}
	pre = temp;

	if (pre == 0)           //插入
		root = in;
	else
	{
		if (in->key < pre->key)
			pre->lc = in;
		else
			pre->rc = in;
		in->p = pre;
	}
}

node* Findlater(node* f)
{
	if (f->rc != 0)
	{
		f = f->rc;
		while (f->lc != 0)
			f = f->lc;

		return f;
	}
	else
	{
		while (true)
		{
			if (f->p->key > f->key)
				return f->p;
			else
				f = f->p;
		}
	}
}

void Delete(int de)
{
	node* find = root;             
	node* De;              //将要删除的节点
	node* c;               //De的子节点  

	while (find != 0)
	{
		if (de < find->key)
			find = find->lc;
		else if (de > find->key)
			find = find->rc;
		else
		{
			if (find->lc == 0 || find->rc == 0)           //确认将要删除的节点
				De = find;
			else
				De = Findlater(find);

			if (De->lc != 0)                      //确认De的子节点
				c = De->lc;
			else
				c = De->rc;

			if (c != 0)
				c->p = De->p;

			if (De->p == 0)
				root = c;
			else
			{
				if (De == De->p->lc)
					De->p->lc = c;
				else
					De->p->rc = c;
			}

			if (De != find)
				find->key = De->key;

			break;
		}
	}
}

bool Find(int f)
{
	bool fin = false;

	node* pre = root;
	while (pre != 0)
	{
		if (f < pre->key)
			pre = pre->lc;
		else if (f > pre->key)
			pre = pre->rc;
		else
		{
			fin = true;
			break;
		}

	}

	return fin;
}

void Inorder(node* r)
{
	if (r->lc != 0)
		Inorder(r->lc);

	cout << " " << r->key;
	
	if (r->rc != 0)
		Inorder(r->rc);
}

void Preorder(node * r)
{
	cout << " " << r->key;

	if (r->lc != 0)
		Preorder(r->lc);
	if (r->rc != 0)
		Preorder(r->rc);
}

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

	int n, x;
	string p;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> p;

		if (p == "insert")
		{
			cin >> x;
			insert(x);
		}
		else if (p == "find")
		{
			cin >> x;
			if (Find(x))
				cout << "yes\n";
			else
				cout << "no\n";
		}
		else if (p == "delete")
		{
			cin >> x;
			Delete(x);
		}
		else
		{
			Inorder(root);
			cout << endl;
			Preorder(root);
			cout << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 21976
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010, mod =1e9+7;

int a[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);

    sort(a, a + n);

    int l  = 0, r = n - 1;
    int ans = 1;
    int sign  = 1;

    if(k % 2)
    {
        ans = a[r];
        r --;
        k --;

        if(ans < 0) sign = -1;
    }

    while(k)
    {
        LL x = (LL)a[l] * a[l + 1], y =(LL)a[r] * a[r - 1];
        if(x * sign > y * sign)
        {
            ans = x % mod * ans % mod;
            l += 2;
        }
        else
        {
            ans = y % mod * ans % mod;
            r -= 2;
        }
        k -= 2;
    }
    ans%=mod;
    ans=(ans+mod)%mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4436
#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 924844033;
const int MAXN = 800000;
const int G = 5;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL * x * y % MOD;}

int pow_mod(int b, int p) {
	int ret = 1;
	for(int i=p;i;i>>=1,b=mul(b,b))
		if( i & 1 ) ret = mul(ret, b);
	return ret;
}

int w[21], iw[21];
int fct[MAXN + 5], ifct[MAXN + 5], inv[MAXN + 5];
int comb(int n, int m) {
	return mul(fct[n], mul(ifct[m], ifct[n-m]));
}
void init() {
	for(int i=0;i<=20;i++) {
		w[i] = pow_mod(G, (MOD - 1) / (1 << i));
		iw[i] = pow_mod(w[i], MOD - 2);
	}
	inv[1] = 1;
	for(int i=2;i<=MAXN;i++)
		inv[i] = sub(0, mul(MOD/i, inv[MOD%i]));
	fct[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fct[i] = mul(fct[i-1], i);
	ifct[MAXN] = pow_mod(fct[MAXN], MOD - 2);
	for(int i=MAXN-1;i>=0;i--)
		ifct[i] = mul(ifct[i+1], i+1);
}

int length(int n) {
	int len; for(len = 1; len < n; len <<= 1);
	return len;
}
void ntt(int *A, int n, int type) {
	for(int i=0,j=0;i<n;i++) {
		if( i < j ) swap(A[i], A[j]);
		for(int k=(n>>1);(j^=k)<k;k>>=1);
	}
	for(int i=1;(1<<i)<=n;i++) {
		int s = (1 << i), t = (s >> 1);
		int u = (type == 1 ? w[i] : iw[i]);
		for(int j=0;j<n;j+=s) {
			for(int k=0,p=1;k<t;k++,p=mul(p,u)) {
				int x = A[j+k], y = mul(A[j+k+t], p);
				A[j+k] = add(x, y), A[j+k+t] = sub(x, y);
			}
		}
	}
	if( type == -1 ) {
		int iv = inv[n];
		for(int i=0;i<n;i++)
			A[i] = mul(A[i], iv);
	}
}

struct edge{
	int to; edge *nxt;
}edges[MAXN + 5], *adj[MAXN + 5], *ecnt = edges;
void addedge(int u, int v) {
	edge *p = (++ecnt);
	p->to = v, p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->nxt = adj[v], adj[v] = p;
}

int a[MAXN + 5], b[MAXN + 5], N;
int dfs(int x, int f) {
	int ret = 1;
	for(edge *p=adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		int t = dfs(p->to, x);
		a[t]++, a[N - t]++, ret += t;
	}
	return ret;
}
int main() {
	init();
	scanf("%d", &N);
	for(int i=1;i<N;i++) {
		int u, v; scanf("%d%d", &u, &v);
		addedge(u, v);
	}
	dfs(1, 0);
	for(int i=0;i<=N;i++) a[i] = mul(a[i], fct[i]), b[i] = ifct[i];
	for(int i=1,j=N;i<j;i++,j--) swap(a[i], a[j]);
	int len = length(2*N + 1);
	ntt(a, len, 1), ntt(b, len, 1);
	for(int i=0;i<len;i++) a[i] = mul(a[i], b[i]);
	ntt(a, len, -1);
	for(int i=1,j=N;i<j;i++,j--) swap(a[i], a[j]);
	for(int i=1;i<=N;i++)
		printf("%d\n", sub(mul(comb(N, i), N), mul(a[i], ifct[i])));
}

Measured memory_bytes: 32396
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    
    int ot = (n - n%100) / 100;
    int tf = n % 100;
    
	if ( ot < 13 && ot != 0 && tf < 13 && tf != 0) {
      System.out.println("AMBIGUOUS");
      return;
    }
    
    if (ot<13 && ot!=0 && (tf==0 || tf>12)) {
      System.out.println("MMYY");
      return;
    }
    
    if (tf<13 && tf!=0 && (ot==0 || ot>12)) {
      System.out.println("YYMM");
      return;
    }
    
    System.out.println("NA");
  }
}


Measured memory_bytes: 21716
#include <stdio.h>
#include <algorithm>
long long p = 1000000007;
long long n, t, ans;
long long c[200000];
long long b[200000];
int main() {
	scanf("%lld", &n);
	for (long long i = 0; i < n; i++) {
		scanf("%lld", c + i);
	}
	t = 1;
	for (long long i = 1; i < n; i++) {
		t *= 4;
		t %= p;
	}
	b[0] = t * 2 % p;
	for (long long i = 1; i < n; i++) {
		b[i] = (b[0] + (t * i)) % p;
	}
	std::sort(c, c + n);
	for (long long i = 0; i < n; i++) {
		ans += c[i] * b[n - 1 - i];
		ans %= p;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 3328
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

template<class T>
bool UpdateMax(T &a, const T &b){
  if(a<b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template<class T>
bool UpdateMin(T &a, const T &b){
  if(a>b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n;
  cin>>n;
  vector<int> a(n+1);
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }

  int cnt=0;
  for(int i=1;i<=n;i+=2){
    if(a[i]%2==1){
      cnt++;
    }
  }
  cout<<cnt<<endl;

  return 0;
}



Measured memory_bytes: 3636
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.Arrays;

@SuppressWarnings("unchecked")
public class Main {
    static final int INF = 1000000007;
    static final char Q = '?';
    static final String ABC = "ABC";

    // aとbを足した値をmodする(a + b mod p)
    static int modadd(int a, int b) {
        return (a + b) % INF;
    }

    // aとbを掛けた値をmodする(a * b mod p)
    static int modmulti(int a, int b) {
        int res = 0;
        int mod = a % INF;
        while (b > 0) {
            if ((b & 1) == 1) {
                res += mod;
                if (res > INF) res -= INF;
            }
            mod <<= 1;
            if (mod > INF) mod -= INF;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        final String S;

        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            S = reader.readLine();
        }

        PrintWriter out = new PrintWriter(System.out);

        int len = S.length();

        int[][] dp = new int[len + 1][ABC.length() + 1];

        for (int i = 0; i < len + 1; i++) Arrays.fill(dp[i], 0);

        dp[len][ABC.length()] = 1;

        for (int i = len - 1; 0 <= i; i--) {
            int n = 1;
            boolean q = false;

            if (S.charAt(i) == Q) {
                n = ABC.length();
                q =  true;
            }

            for (int j = 0; j <= ABC.length(); j++) {
                // ○ 3
                if (j == ABC.length())
                    dp[i][j] =
                        modadd(dp[i][j], modmulti(dp[i + 1][j], n));
                // ○ 3 以外
                else {
                    int m = 1;

                    if (!q && ABC.charAt(j) != S.charAt(i)) m = 0;

                    dp[i][j] =
                        modadd(dp[i][j], modmulti(dp[i + 1][j], n));

                    dp[i][j] =
                        modadd(dp[i][j], modmulti(dp[i + 1][j + 1], m));
                }
            }
        }

        out.println(dp[0][0]);

        out.flush();
    }
}


Measured memory_bytes: 29364
#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define memr(dp, val) memset(dp, val, sizeof(dp))
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> inline bool int_ceil(T a, T b) { T res = a / b; if(a % b != 0) res++; return res; }
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define print(...)
#endif

int main(int argc, const char * argv[]) {
	std::cout << std::fixed << std::setprecision(15);

	int x; cin >> x;

	int n; cin >> n;
	if(n == 0){
		cout << x << endl;
		return 0;
	}
	vector<int> p(n);
	rep(i, n) cin >> p[i];

	int ans = INTINF;
	int ans2 = INTINF;
	rep(i, 1000){
		int now = i - 500;
		bool ok = true;
		rep(j, p.size()){
			if(p[j] == now) {
				ok = false;
				break;
			}
		}
		if(!ok) continue;
		if(ans > abs(now - x)){
			ans = abs(now - x);
			ans2 = now;
		}
		else if(ans == abs(now - x)){
			ans2 = min(ans2, now);
		}
	}

	cout << ans2 << endl;

	return 0;
}


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

const int INF = 1001001001;

ll pow(ll base, ll order) {
	ll ans = 1;
	rep(i,order - 1) ans *= base;
	return ans;
}

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

	if (n % 10 == 7) {
		cout << "Yes" << endl;
		return 0;
	}
	n -= (n % 10);
	n /= 10;
	if (n % 10 == 7) {
		cout << "Yes" << endl;
		return 0;
	}
	n -= (n % 10);
	n /= 10;
	if (n == 7) {
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<double> VD;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;

inline int add(int x, int y)
{
	if (x + y < mod)
		return x + y;
	return x + y - mod;
}

inline int sub(int x, int y)
{
	if (x >= y)
		return x - y;
	return x - y + mod;
}

inline int mult(int x, int y)
{
	return x * (LL) y % mod;
}

inline int power(int x, int y)
{
	int r = 1;
	while(y)
	{
		if (y & 1)
			r = mult(r, x);
		x = mult(x, x);
		y >>= 1;
	}
	
	return r;
}

inline int inverse(int x)
{
	return power(x, mod - 2);
}

const int N = 1 << 22;
int f[N];
int inv[N];

inline int C(int n, int m)
{
	int res = f[n];
	res = mult(res, inv[m]);
	res = mult(res, inv[n - m]);
	return res;
}

inline int count(int n, int m)
{
	return C(n - 1 + m, m);
}

int jebu(int n, int odd, int m)
{
	return count(n, (3 * m - odd) / 2);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	//freopen("In.txt", "w", stdout);
	
	int n, m;
	cin >> n >> m;
	f[0] = 1;
	FOR(i, 1, N)
		f[i] = mult(f[i - 1], i);
	FOR(i, 0, N)
		inv[i] = inverse(f[i]);
		
	int ans = count(n, 3 * m);
	int tut = 0;
	FOR(i, 2 * m + 1, 3 * m + 1)
		tut = add(tut, count(n - 1, 3 * m - i));
		
	tut = mult(tut, n);	
	ans = sub(ans, tut); 
	
	int odd = 0;
	for(int cnt = m + 2; cnt <= n && cnt <= 3 * m; cnt += 2)
	{
		int coef = C(n, cnt);
		int here = jebu(n, cnt, m);	
		odd = add(odd, mult(coef, here));
	}
	
	ans = sub(ans, odd);
	cout << ans << endl;
		
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}


Measured memory_bytes: 33024
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define   ull unsigned long long 
const int MAX=3e5;
const int mod=1e9+7;
using namespace std;

int main(){
	ll n;
	cin>>n;
	ll a[n+1], b[n+1];
	ll mx=-1;
	ll tot=0;
	map<ll,ll>mp;
	int f=0;
	pair<int , int> p[n+1];
	for(int i=1;i<=n;i++){
		cin>>p[i].second>>p[i].first;
	}
	sort(p+1 , p+n+1);
	for(int i=1;i<=n;i++){
		tot=tot+p[i].second;
		if(tot>p[i].first)
			f=1;
	}
	if(!f)
		cout<<"Yes";
	else
		cout<<"No";



}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    string S;
    cin >> S;
    int N = S.size() + 1;

    vector<i64> lt(N, 0), gt(N, 0);;
    for(int right = 1; right < N; right++){
        while(S[right-1] == '<' && right < N){
            lt[right] = lt[right - 1] + 1;
            right++;
        }
    }
    for(int left = N-2; left >= 0; left--){
        while(S[left] == '>' && left >= 0){
            gt[left] = gt[left + 1] + 1;
            left--;
        }
    }
    i64 ans = 0;
    for(int i = 0; i < N; i++) ans += max(lt[i], gt[i]);

    cout << ans << endl;
}

Measured memory_bytes: 8708
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;
//debug 
#ifdef _DEBUG
#define debug(var)  do{cout << #var << " :";view(var);}while(0)
#else
#define debug(...)
#endif
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vector<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vector<vector<T> >& vv){ for(const auto& v : vv){ view(v); } }


int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  REP(i,n) cin >> a[i] >> b[i];

  int cnt = 0;
  REP(i,n){
    if(a[i] == b[i]) cnt++;
    else cnt = 0;

    if(cnt == 3){
      cout << "Yes" << endl;
      return 0;
    }

  }
  cout << "No" << endl;


  return 0;
}

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

typedef long long ll;

using namespace std;

int main() {
    ll ans = 0, cnt = 0;
    string s;
    cin >> s;
    for (ll i = 0; i < s.size(); ++i) {
        if (s.at(i) == 'B') ++cnt;
        else ans += cnt;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    int n, m;
    cin >> n >> m;

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

    vector<vector<int>> edge(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int high = true;
        for (int to : edge[i]) {
            if (h[to] >= h[i]) {
                high = false;
                break;
            }
        }
        if (high) ans++;
    }

    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 8724
import java.util.Scanner;

// E - Double Factorial
// https://atcoder.jp/contests/abc148/tasks/abc148_e
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N = Long.parseLong(scanner.next());
        scanner.close();

        long ans = Math.min(g2(N, 2), g2(N, 5));

        System.out.println(ans);
    }

    private static long g1(long n, int p) {
        if (n == 0) return 0;
        return n / p + g1(n / p, p);
    }

    private static long g2(long n, int p) {
        if (n % 2 == 1) {
            return g1(n, p) - g2(n - 1, p);
        }
        long res = g1(n / 2, p);
        if (p == 2) res += n / 2;
        return res;
    }
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)
using P =pair<int,int>;

ll f(ll x,ll c,ll d){
    ll res =x;
    res -=x/c;
    res -=x/d;
    res+= x/lcm(c,d);
    return res;
}

int main(){
   ll n,k;
   cin>>n>>k;
   double sum=0;
   vector<ll>v(n);
   rep(i,n)cin>>v[i];
   vector<double>s(n);
   rep(i,n){
       double a=((1+v[i])/2.0);
       s[i]=a;
   }
   sum=0;
   rep(i,k)sum+=s[i];
   double ans=sum;
   rep(i,n-k){
       sum-=s[i];
       sum+=s[i+k];
       ans=max(ans,sum);
   }
          cout<<fixed<<setprecision(10)<<ans<<endl;
}


Measured memory_bytes: 6360
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import math

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	R = int(input())
	P = math.pi
	ans = 2 * P * R
	print(ans)



if __name__ == '__main__':
	main()

Measured memory_bytes: 65148
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N;
    scan(N);
    auto x = new int[][](N, 0);
    auto y = new int[][](N, 0);
    foreach (i ; 0 .. N) {
        int Ai;
        scan(Ai);
        while (Ai--) {
            int xi, yi;
            scan(xi, yi);
            xi--;
            if (yi) {
                x[i] ~= xi;
            }
            else {
                y[i] ~= xi;
            }
        }
    }

    int ans;

    foreach (s ; 0 .. (1 << N)) {
        bool ok = true;

        foreach (j ; 0 .. N) if (s & (1 << j)) {
            foreach (xk ; x[j]) {
                if (!(s & (1 << xk))) {
                    ok = false;
                }
            }
            foreach (yk ; y[j]) {
                if (s & (1 << yk)) {
                    ok = false;
                }
            }
        }

        if (ok) ans = max(ans, s.popcnt);
    }

    writeln(ans);
}




void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

using namespace std;

int main() {
   int n,k;
	cin >> n >> k;
   ll ans=k;
	rep(i,n-1)
   ans *=(k-1);
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
range = xrange

inp = [int(x) for x in sys.stdin.read().split()]
ii = 0

n = inp[ii]
ii += 1

coupl = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = inp[ii]-1, inp[ii+1]-1
    ii += 2
    
    coupl[u].append(v)
    coupl[v].append(u)

root = 0
for _ in range(2):
    depth = [-1]*n
    depth[root] = 1
    Q = [root]
    for node in Q:
        d = depth[node]
        for nei in coupl[node]:
            if depth[nei]==-1:
                depth[nei] = d+1
                Q.append(nei)

    root = max(range(n), key = lambda i:depth[i])
dia = depth[root]
if dia%3!=2:
    print 'First'
else:
    print 'Second'

Measured memory_bytes: 98020
n,W = map(int,input().split())
lst = [[0]*(n+1) for _ in range(4)]
for i in range(n):
    w,v = map(int,input().split())
    if i == 0: x = w
    lst[w-x].append(v)
for i in range(4):
    lst[i].sort(reverse=True)
    for j in range(n): lst[i][j+1] += lst[i][j]
ans = 0
for a in range(n+1):
    for b in range(n+1-a):
        for c in range(n+1-a-b):
            if x*a+(x+1)*b+(x+2)*c > W: continue
            d = max((W-x*a-(x+1)*b-(x+2)*c)//(x+3),0)
            sumv = 0
            for i,j in enumerate((a,b,c,d)):
                if j == 0: continue
                sumv += lst[i][j-1]
            ans = max(sumv,ans)
print(ans)

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

using namespace std;

string S;

char rights[11] = {'y','u','i','o','p','h','j','k','l','n','m'};

bool isright(char c) {
	for (int i = 0; i < 11; i++) if (rights[i] == c) return true;
	return false;
}

void solve() {
	int cnt = 0;
	int n = (int)S.size();	
	bool prev = 0;
	
	for (int i = 0; i < n; i++) {
		bool cur = isright(S[i]);
		if (i != 0 && cur != prev) cnt++;
		prev = cur;
	}
	
	cout << cnt << endl;
}

int main() {
	while (1) {
		cin >> S; if (S[0] == '#') break;
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 1184
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#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 all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;

int mod=1e9+7;
long long modpow(long long x,long long n,long long mod)
{
  if(n==0)return 1;
  long long res=modpow(x*x%mod,n/2,mod);
  if(n&1)res=res*x%mod;
  return res;
}
long long modinv(long long a,long long m=mod)//extgcdの方がいいらしい
{
  return modpow(a,m-2,m);
}
vector<ll>cal(200001),inv(200001);

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

  int h,w,a,b;
  cin>>h>>w>>a>>b;
  cal[0]=1;
  repi(i,1,200001)
  {
    cal[i]=(ll)cal[i-1]*i%mod;
  }
  inv[200000]=modinv(cal[200000]);
  for(int i=200000;i>0;i--)
  {
    inv[i-1]=(ll)inv[i]*i%mod;
  }
  ll res=0;
  ll tres=cal[h-a-1+b]*cal[a+w-b-1]%mod;
  ll m=min(h-a,w-b);
  rep(i,m)
  {
    res+=(ll)inv[b+i]*tres%mod*inv[h-a-1-i]%mod*inv[a+i]%mod*inv[w-b-1-i]%mod;
    res%=mod;
  }
  cout<<res<<endl;



  return 0;

}


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

using namespace std;
#define DIM 100007
#define INF 2E60
#define MAXN 1023
#define LG 18
typedef int ll;
typedef long double ld;
typedef ll arr[DIM];
typedef vector<ll> vec;
typedef vector<ll> graph[DIM];
typedef pair<ll, ll> pll;

struct pp {
	ll a, b;
	bool operator <(const pp& V)const {
		if (a == V.a)return b < V.b;
		return a < V.a;
	}
	bool operator ==(const pp& V)const {
		if (a == V.a && b == V.b)return 1;
		return 0;
	}
};


ll n,k;
arr A,D;
int main()
{
	cin >> n>>k;
	for (int i = 1; i <= n; i++)cin >> A[i];
	for (int i = n; i >= 1; i--) {
		if (i == n)continue;
		else D[i] = INF;
		for (int j = i + 1; j <= min(n, i + k); j++) {
			D[i] = min(D[j] + abs(A[i] - A[j]),D[i]);
		}

	}
	cout << D[1] << endl;
}
// 11
// 

Measured memory_bytes: 1024
import sys
import copy
import itertools
sys.setrecursionlimit(10**6)


def sum(table):
    t = 0
    for i in range(len(table)):
        for j in range(len(table[i])):
            t += table[i][j]
    return t


def main(input, print):
    h, w, K = map(int, input().split())
    table = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        s = list(input())
        for j in range(w):
            if s[j] == '#':
                table[i][j] = 1
    ht = []
    for i in range(h+1):
        for v in itertools.combinations(range(h), i):
            ht.append(v)
    wt = []
    for i in range(w+1):
        for v in itertools.combinations(range(w), i):
            wt.append(v)

    ans = 0
    for i in range(len(ht)):
        now = copy.deepcopy(table)
        for j in range(len(ht[i])):
            for k in range(w):
                now[ht[i][j]][k] = 0
        for j in range(len(wt)):
            now2 = copy.deepcopy(now)
            for k in range(len(wt[j])):
                for l in range(h):
                    now2[l][wt[j][k]] = 0
            if sum(now2) == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


Measured memory_bytes: 72232
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

ll K;

void solve(){
	cin >> K;
	int N = 50;
	ll A[55] = {};
	for(int i=1;i<=N;i++) A[i] = K / N + N - 1;
	K %= N;
	for(int i=1;i<=K;i++) {
		A[i] += N;
		for(int j=1;j<=N;j++) if(i != j) A[j]--;
	}
	printf("%d\n", N);
	for(int i=1;i<=N;i++) printf("%lld ", A[i]);puts("");
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
A, B = map(int, input().split())
def xor_upto(n):
    ans = 0
    if n%2 == 0:
        ans = n
    if ((n+1)//2)%2 == 1:
        ans = ans^1
    return ans
print(xor_upto(A-1)^xor_upto(B))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
#define debug(x) cerr << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    V<ll> a(n);
    rep(i,n) cin >> a[i];

    auto dp = make_vec(n+1, n+1, 2, 0LL);
    auto rec = [&](auto self, int l, int r, bool is_first) -> ll
    {
        if(abs(r - l) < 1)
        {
            return 0;
        }
        if(dp[l][r][is_first])
        {
            return dp[l][r][is_first];
        }
        if(is_first) //先手番
        {
            ll res = -LINF;
            chmax(res, self(self, l+1, r, 0) + a[l]);
            chmax(res, self(self, l, r-1, 0) + a[r-1]);
            chmax(dp[l][r][is_first], res);
            return res;
        }
        else
        {
            ll res = LINF;
            chmin(res, self(self, l+1, r, 1) - a[l]);
            chmin(res, self(self, l, r-1, 1) - a[r-1]);
            chmin(dp[l][r][is_first], res);
            return res;
        }
    };
    cout << rec(rec, 0, n, 1) << endl;


    return 0;
}

Measured memory_bytes: 496304