akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

void sayYes() {puts("Yes");}
void sayNo() {puts("No");}
template<class T> bool chmin(T&a,T b) {if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b) {if(a<b){a=b;return true;}return false;}

class FastIO {
public:
    FastIO() {
        cin.tie(0);
        ios::sync_with_stdio(false);
    }
    ~FastIO() {}

    template <class T>
    void scan(T &v) {
        cin >> v;
    }
    template <class T, class... Rest>
    void scan(T &v, Rest&... rest) {
        scan(v);
        scan(rest...);
    }

    template <class T>
    void print(T v) {
        cout << v;
    }
    template <class T, class... Rest>
    void print(T v, Rest... rest) {
        print(v);
        print(" ");
        print(rest...);
    }
    template <class T>
    void prints(vector<T> v) {
        for (T t: v) {
            print(t);
            print(" ");
        }
        print("\n");
    }
    template <class T>
    void prints(T v) {
        print(v);
        cout << "\n";
    }
    template <class T, class... Rest>
    void prints(T v, Rest... rest) {
        print(v);
        print(" ");
        prints(rest...);
    }
};
FastIO io;


int main() {
    string s; io.scan(s);
    
    int N = s.size();
    REP(i, N) {
        if (i%2 == 0) {
            if (s[i] == 'L') {
                sayNo();
                return 0;
            }
        }
        else if (s[i] == 'R') {
            sayNo();
            return 0;
        }
    }
    sayYes();
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main (void) {
    int n;
    int nx = 0;
    int ny = 0;
    int nt = 0;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        int x;
        int y;
        cin >> t >> x >> y;
        if (t - nt < abs(x - nx) + abs(y - ny)) {
            cout << "No" << endl;
            return 0;
        } else {
            if (((t - nt) - (abs (x - nx) + abs(y - ny))) % 2 != 0) {
                cout << "No" << endl;
                return 0;
            }
        }
        nt = t;
        nx = x;
        ny = y;
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
# ABC058C - 怪文書 / Dubious Document (ARC071C)
from string import ascii_lowercase


def main():
    N = int(input())
    S = tuple(input() for _ in range(N))
    ans = ""
    for i in ascii_lowercase:
        if all(i in s for s in S):
            ans += i * min(s.count(i) for s in S)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3768
n=int(input())
a=list(map(int,input().split( )))
q=int(input())
for i in range(q):
    b,e,k=map(int,input().split( ))
    count=0
    for a_i in a[b:e]:
        if a_i==k:
            count+=1
    print(count)



Measured memory_bytes: 5636
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;


int main(){
  ll a,b,c,k;
  cin >> a >> b >> c >> k;
  ll ans = 0;
  if(a >= k){
    ans = k;
  }else{
    ans += a;
    k -= a;
    if(b >= k){

    }else{
      k -= b;
      ans -= k;
    }
  }
  printf("%lld\n", ans);
  return 0;
}


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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MAX=1<<18;
const ll INF=0x3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
ll seg1[2*MAX],seg2[2*MAX],add,N,Q,pt[MAX],A,B,ans=INF;
ll seg_init(ll *seg){
    for(ll i=0;i<2*MAX;i++) seg[i]=INF;
}
ll seg_put(ll* seg,ll x,ll v){
    ll p=x+MAX;
    seg[p]=min(seg[p],v);
    for(p/=2;p>=1;p/=2){
        seg[p]=min(seg[p*2],seg[p*2+1]);
    }
    return 1;
}
ll seg_min(ll* seg,ll a,ll b,ll x,ll y,ll node){
    if(a<=x&&y<=b) return seg[node];
    if(b<=x||y<=a) return INF;
    return min(seg_min(seg,a,b,x,(x+y)/2,node*2),seg_min(seg,a,b,(x+y)/2,y,node*2+1));
}
ll dist(ll a,ll b){return abs(pt[a]-pt[b]);}
int main(){
    scanf("%lld%lld%lld%lld",&N,&Q,&A,&B);
    pt[0]=A,pt[1]=B;
    for(ll i=2;i<Q+2;i++) scanf("%lld",&pt[i]);
    seg_init(seg1),seg_init(seg2);
    seg_put(seg1,pt[0],dist(1,2)-pt[0]), seg_put(seg1,pt[1],dist(0,2)-pt[1]);
    seg_put(seg2,pt[0],dist(1,2)+pt[0]), seg_put(seg2,pt[1],dist(0,2)+pt[1]);
    for(ll i=3;i<Q+2;i++){
        //for(ll j=1;j<=N;j++) printf("index %lld : %lld\n",j,seg1[MAX+j]+j+add);
        ll u1=seg_min(seg1,1,pt[i],0,MAX,1)+pt[i]+add,u2=seg_min(seg2,pt[i],N+1,0,MAX,1)-pt[i]+add;
        add+=dist(i,i-1);
        seg_put(seg1,pt[i-1],min(u1,u2)-add-pt[i-1]);
        seg_put(seg2,pt[i-1],min(u1,u2)-add+pt[i-1]);
    }
    for(ll i=1;i<=N;i++){
        //printf("index %lld : %lld\n",i,seg1[MAX+i]+i+add);
        ans=min(ans,seg1[MAX+i]+i+add);
    }
    printf("%lld\n",ans);
    return 0;
}


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

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

    if (n.at(n.size()-1) == '3') {cout << "bon" << endl;}
    else if (n.at(n.size()-1) == '0' || n.at(n.size()-1) == '1' || n.at(n.size()-1) == '6' || n.at(n.size()-1) == '8') {cout << "pon" << endl;}
    else {cout << "hon" << endl;}
}

Measured memory_bytes: 3596
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<(n);i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll
// #define MAX 20
#define INF (int)1e18

template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.F<<','<< P.S<<')';}


signed main()
{
	fio
	inp(s) inp(w)
	if(w>=s)
	{
		cout<<"unsafe";
	}
	else
		cout<<"safe";
	cout<<'\n';
	printclock;
}

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

int main() {
	int N, cnt=0;
  	cin >> N;
  	vector<int> N_a(N);
  	for(int i=0;i<N;i++){
    	cin >> N_a.at(i);
    }
  	for(int i=0;i<N;i++){
    	if((i+1)%2==1&&N_a.at(i)%2==1){
        	cnt++;
        }
    }
  	cout << cnt << endl;
}


Measured memory_bytes: 3600
from numpy import array, int64, minimum
from sys import stdin

def main():
    input = stdin.buffer.readline

    N, K = map(int, input().split())

    A, F = array(input().split(), int64), array(input().split(), int64)
    A.sort()
    F.sort()
    F = F[::-1]

    sum_A = A.sum()

    ng, ok = -1, 10 ** 12
    while ng + 1 < ok:
        mid = (ok + ng) // 2
        if (sum_A - minimum(A, mid // F).sum()) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()


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

int main() {
long long N,K;
  cin >> N >> K;
  vector<long long> A(N);
  vector<long long> B(N); // aはB[a]回目に通った
  vector<long long> C(0); // a回目にC[a]にいた
  int now = 1;
  int flag = 0;
  for(int a = 0;a < N;a++)cin >> A[a];
  for(int a = 0;a < N;a++)B[a] = -1;
  for(long long a = 0;a < K;a++){
    B[now - 1] = a;
    C.push_back(now);
    now = A[now - 1];
    if(B[now - 1] != -1&&flag == 0){
      K -= ((K - a - 1) / (a - B[now - 1] + 1)) * (a - B[now - 1] + 1);
        flag = 1;
    }
  }
   cout << now << endl;
}

Measured memory_bytes: 8500
// Nurbakyt Madibek
// Look at my code! IT'S AWESOME

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <unordered_set>

using namespace std;

#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair
#define sz(a) (int)((a).size())
#ifdef _WIN32
#  define I64 "%I64d"
#else
#  define I64 "%lld"
#endif
#define fname "."

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pi;
typedef pair < int, ull > pu;
typedef pair < ll, ll > pl;

const int inf = (int)1e9;
const ll infl = (ll)1e18 + 123;
const double eps = 1e-9;

const int MAX_N = (int)1e5 + 123;
const int mod = (int)1e9 + 7;
const int P = 123457;

string s;
int k;

int dp[305][305][305];

int calc(int l, int r, int x) {
    int &res = dp[l][r][x];
    if (res != -1)
        return res;
    if (l == sz(s) || r == -1 || l > r)
        return res = 0;
    if (l == r)
        return res = 1;
    res = max(calc(l + 1, r, x), calc(l, r - 1, x));
    if (s[l] == s[r])
        res = max(res, 2 + calc(l + 1, r - 1, x));
    else if (x > 0)
        res = max(res, 2 + calc(l + 1, r - 1, x - 1));
    return res;
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> k;
    memset(dp, -1, sizeof dp);
    cout << calc(0, sz(s) - 1, k) << endl;
    return 0;
}


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

int main() {
    int l, r;
    cin >> l >> r;
    int d;
    cin >> d;
    int cnt  = 0;

    for (int i = l;i <= r;i++) {
        if (!(i % d)) cnt++;
    }

    cout << cnt << endl;

    return(0);
}


Measured memory_bytes: 3620
c=vcat([(x->parse(Int,x)).(split(i))' for i in readlines()]...)
f(x)=length(unique(x))
print(f(c[:,1]-c[:,2])==f(c[:,2]-c[:,3])==f(c[1,:]-c[2,:])==f(c[2,:]-c[3,:])==1 ? "Yes" : "No")

Measured memory_bytes: 178544
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const ll N = 100001;
string s,k="a",no="zyxwvutsrqponmlkjihgfedcba";
bool alf[26];
vector<char> c;

int main(){
	cin>>s;
	if(s==no){
		cout<<-1<<endl;
		return 0;
	}
	FOR(i,0,26)alf[i]=false;
	FOR(i,0,s.size()){
		alf[s[i]-'a']=true;
	}
	if(s.size()!=26){
		FOR(i,0,26){
			if(alf[i]==false){
				k[0]='a' + i;
				s+=k;
				cout<<s<<endl;
				return 0;
			}
		}
	}else{
		ll i=25;
		while(1){
			alf[s[i]-'a']=false;
			if(s[i]>s[i-1]){
				FOR(k,0,i-1){
					cout<<s[k];
				}
				FOR(q,s[i-1]-'a',26){
					if(alf[q]==false){
						char p='a'+q;
						cout<<p<<endl;
						return 0;
					}
				}
				
			}
			i--;
		}

	}

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		//int c=scan.nextInt();
		int ans=0;
		/*
		 if(){
		 ans=;
		 }
		 else{
		 ans=;
		 }
		  
		 */
		System.out.println(a-b+1);
	}
}

Measured memory_bytes: 23252
import java.util.*
import kotlin.math.*

fun main() {
    val s = readString()
    val t = readString()

    val dp = List(s.length + 1) { MutableList(t.length + 1) { 0 } }

    for (i in s.indices) {
        for (j in t.indices) {
            dp[i + 1][j + 1] = if (s[i] == t[j]) {
                dp[i][j] + 1
            } else {
                max(dp[i][j + 1], dp[i + 1][j])
            }
        }
    }

    var len = dp[s.length][t.length]
    val ans = CharArray(dp[s.length][t.length])
    var i = s.length
    var j = t.length
    while (i > 0 && j > 0) {
        when {
            dp[i][j] == dp[i - 1][j] -> i--
            dp[i][j] == dp[i][j - 1] -> j--
            else -> {
                ans[len - 1] = s[i - 1]
                i--
                j--
                len--
            }
        }
    }
    println(ans)
}


fun readString() = readLine()!!

Measured memory_bytes: 203600
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  lint a; cin >> a;
  string b; cin >> b;
  string t = "";
  t += b[0];
  t += b[2];
  t += b[3];

  lint c = stoll(t);

  lint ans = (a * c);
  ans /= 100;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
void setcomb() {
	fac[0] = 1;
	ifac[0] = 1;
	for (ll i = 0; i < 1000000; i++) {
		fac[i + 1] = fac[i] * (i + 1) % M; // n!(mod M)
	}
	ifac[1000000] = mpow(fac[1000000], M - 2);
	for (ll i = 1000000; i > 0; i--) {
		ifac[i - 1] = ifac[i] * i%M;
	}
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
ll perm(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	return fac[a] * ifac[a - b] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b, int n) {
	int i, j, k, t;
	vector<vector<ll>> c(n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			t = 0;
			for (k = 0; k < n; k++)
				t = (t + a[i][k] * b[k][j] % M) % M;
			c[i].push_back(t);
		}
	}
	return c;
}

template< typename Monoid >
struct SegmentTree {

	int sz;
	vector< Monoid > seg;

	const Monoid M1;

	SegmentTree(int n, const Monoid &M1) : M1(M1) {
		sz = 1;
		while (sz < n) sz <<= 1;
		seg.assign(2 * sz, M1);
	}

	void set(int k, const Monoid &x) {
		seg[k + sz] = x;
	}

	void build() {
		for (int k = sz - 1; k > 0; k--) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	void update(int k, const Monoid &x) {
		k += sz;
		seg[k] = x;
		while (k >>= 1) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	Monoid query(int a, int b) {
		Monoid L = M1, R = M1;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) L = f(L, seg[a++]);
			if (b & 1) R = f(seg[--b], R);
		}
		return f(L, R);
	}

	Monoid value(const int &k) const {
		return seg[k + sz];
	}

	Monoid f(Monoid a, Monoid b) {
		return a + b;
	}

};

int main() {
	int a, b;
	cin >> a >> b;
	cout << max(a + b, max(a - b, a*b)) << endl;
}

Measured memory_bytes: 4992
from itertools import product
def main():
    h, w, k = map(int, input().split())
    cs = [input() for _ in range(h)]
    ans = 0
    for a in product([True, False], repeat=h):
        for b in product([True, False], repeat=w):
            cnt = 0
            for i in range(h):
                if a[i]:
                    continue
                for j in range(w):
                    if b[j]:
                        continue
                    if cs[i][j] == "#":
                        cnt += 1
            if cnt == k:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
using ll = long long;
using Graph = vector<vector<int>>;
const ll INFTY = 4e18+1;

struct coord {ll x; ll y;};

int main() {
  int N, K;
  cin >> N >> K;
  coord point[N];
  rep(i,N) cin >> point[i].x >> point[i].y;
  
  ll ans = INFTY;

  /* width fixed */
  rep(i,N) {
    rep(j,i) {
      ll w = abs(point[i].x - point[j].x);
      ll h = abs(point[i].y - point[j].y);
      int count = 0;  // number of points in the rectangle
      vector<ll> high;
      vector<ll> low;

      rep(k,N) {
        if (point[k].x > max(point[i].x, point[j].x)) continue;  // out of range
        if (point[k].x < min(point[i].x, point[j].x)) continue;  // out of range
        if (point[k].y > max(point[i].y, point[j].y)) {
          high.push_back(point[k].y - max(point[i].y, point[j].y));
          continue;
        }
        if (point[k].y < min(point[i].y, point[j].y)) {
          low.push_back(min(point[i].y, point[j].y) - point[k].y);
          continue;
        }
        count++;
      }

      if (count >= K) {
        if (w*h < ans) ans = w*h;
        continue;
      }

      int res = K-count;
      if (high.size() + low.size() < res) continue;

      while (high.size() < res) high.push_back(INFTY);
      while (low.size() < res) low.push_back(INFTY);
      high.push_back(0);
      low.push_back(0);
      sort(high.begin(), high.end());
      sort(low.begin(), low.end());
      ll add_h = INFTY;

      rep(k,res+1) {
        if (high[k] + low[res-k] < add_h) {
          add_h = high[k] + low[res-k];
        }
      }

      if (w*(h+add_h) < ans) ans = w*(h+add_h);
    }
  }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#include<string.h>
#define inf 1000000000000000000
#define maxn 1000001
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
#define endl '\n'
#define mapint_iterator map<int,int> :: iterator
#define mapll_iterator map<ll,ll> :: iterator
#define setint_iterator set<int> :: iterator
#define setll_iterator set<ll> :: iterator
#define setpint_iterator set<pint> :: iterator
#define setpll_iterator set<pll> :: iterator
#define trace(x) cout<<#x<<": "<<x<<" "<<endl
#define trace2(x,y) cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x,y,z) cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a,b,c,d) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define cout1(a) cout<<a<<endl
#define cout2(a,b) cout<<a<<" "<<b<<endl
#define cout3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define cout4(a,b,c,d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define vcout(v,i) cout<<v[i].fi<<" "<<v[i].se<<endl
typedef priority_queue<ll,vector<ll>,greater<ll> > pqset;
typedef priority_queue<pint,vector<pint>,greater<pint> > pqset_ll;
#define pb push_back
#define fi first
#define se second
#include<ext/pb_ds/assoc_container.hpp>
ll dxk[]={0,0,1,-1,1,1,-1,-1};
ll dyk[]={1,-1,0,0,1,-1,1,-1};
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
typedef tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update> os_pair;
#define mp make_pair
#define acc (ios::sync_with_stdio(false),cin.tie(0))
#define rep(i,n) for(ll i=0;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define per1(i,n) for(ll i=n;i>0;i--)
#define repeat(i,start,n) for(ll i=start;i<n;i++)
#define print(a,n) for(ll i=0;i<n;i++){ cout<<a[i]<<" ";}
ll ll_max(ll a,ll b,ll c){return max(a,max(b,c));}
int int_max(int a,int b,int c){return max(a,max(b,c));}
ll ll_min(ll a,ll b,ll c){return min(a,min(b,c));}
int int_min(int a,int b,int c){return min(a,min(b,c));}
ll max(int a,ll b){ return max((ll)a,b);}
ll min(int a,ll b){ return min((ll)a,b);} 
ll min(ll a,int b){ return min(a,(ll)b);}
ll max(ll a,int b){ return max(a,(ll)b);}
//ifstream cin("b_read_on.txt"); ofstream cout("output3.txt");
//Chronology: Binary Search,Greedy,dp,dfs and similar
//Use (<<) for multiplication
//Use (>>) for division
// In dp, first try top-down,then bottom-up
//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed;cerr.tie(NULL);cout.precision(10);
void solve(int countu){
	int n,k;
	cin>>n>>k;
	bool dp[k+1]={false};
	int a[n];
	rep(i,n)
		cin>>a[i];
	for(int i=k;i>=1;i--){
		int x=0;
		if(dp[i])
			x=1;
		rep(j,n){
			if(i-a[j]>=0&&dp[i-a[j]]==false)
				dp[i-a[j]]=(x^1);
		}
	}
	int count=0;
	rep(i,n){
		if(dp[a[i]])
			count++;
	}
	if(count==n)
		cout<<"Second"<<endl;
	else
		cout<<"First"<<endl;
}
int main(){
    int t=1;
	//cin>>t;
	int countu=1;
    while(t--){
    	solve(countu);
    	countu++;
    }
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#include "math.h"
#include "string.h"
#include "algorithm"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())

int main(){
  ll n,ans=0;
  cin>>n;
  vll x(n);
  REP(i,n){
    cin>>x[i];
    while(x[i]%2==0){x[i]/=2;ans++;}
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
	int N;
	cin>>N;
	int i,j;
	int ans=0;
	for (i=1;i<N;i++){
		j=N-i;		
		if (j>=1 &&j<=N){
			ans++;
		}else{
			break;
		}
	}
	cout<<ans/2<<endl;


	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    long long N, x, R, G, B, i, j, k;
    char S[4005];
    scanf("%lld%s", &N, S);
    R=0; G=0; B=0;
    for (i=0; i<N; i++) {
        if (S[i]=='R') R++;
        if (S[i]=='G') G++;
        if (S[i]=='B') B++;
    }
    x=R*G*B;
    for (i=0; i<N-1; i++) {
        for (j=i+1; j<N; j++) {
            k=2*j-i;
            if (k>=N) continue;
            if (S[i]!=S[j] && S[i]!=S[k] && S[j]!=S[k]) x--;
        }
    }
    printf("%lld", x);
    return 0;
}

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

vector<int64_t> d;

int64_t Luca(int N){
  if(d.at(N)>=0) return d.at(N);
  if(N==0){
    return d.at(N)=2;
  }
  if(N==1){
    return d.at(N)=1;
  }
  int64_t s = Luca(N-1);
  int64_t t = Luca(N-2);
    return d.at(N)=s+t;
}

int main(){
  int N;
  cin >> N;
  for(int i=0;i<=N;i++) d.push_back(-1);

  cout<< Luca(N) << endl;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define ll  long long int
#define ull unsigned long long 
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back 
#define mp make_pair
#define inf 2000000009
#define mod 1000000007
#define ld long double
using namespace std;

int main()
{ 
fast;
ll x;
cin>>x;


for(ll a=0;a<=120;a++)
    for(ll b=-64;b<=119;b++)
        if(a*a*a*a*a-b*b*b*b*b==x)
        {
          cout<<a<<" "<<b<<endl;
           return  0;
        }
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>

int main(){
  int n,s,d1,d2;
  std::cin >> n;
  std::vector<int> d(n);
  for(int i=0;i<n;i++){
    std::cin >> d[i];
  }
  std::sort(d.begin(),d.end());

  s=d.size()/2;
  d1=d[s]; d2=d[s-1];
  std::cout << d1-d2;
}

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

int main()
{
  int N;
  int a[210];
  int res=0;
  cin >> N;

  rep(i,N) cin >> a[i];

  bool allEven=true;
  while(allEven){
    rep(i,N){
      if(a[i]%2==1) {
        allEven=false;
        break;
      }
    }
    if(allEven){
      rep(i,N) a[i] = a[i] >> 1;
      res++;
    }
  }

  cout << res << endl;
}


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

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

    long long M = 1000000007;
    vector<vector<long long>> T(n+1, vector<long long>(n*n+1));
    T[1][0] = 1;
    T[0][0] = 1;

    for (int i=1; i<n; i++)
    {
        vector<vector<long long>> P(n+1, vector<long long>(n*n+1));
        P.swap(T);

        for (int j=0; j<=n; j++)
        for (int k=0; k<=n*n; k++)
        if (P[j][k] != 0)
        {
            //  0
            T[j][k+2*j] += P[j][k]*(2*j+1);
            T[j][k+2*j] %= M;

            //  +1
            T[j+1][k+2*j] += P[j][k];
            T[j+1][k+2*j] %= M;

            //  -1
            if (j>0)
            {
                T[j-1][k+2*j] += P[j][k]*j*j;
                T[j-1][k+2*j] %= M;
            }
        }

        //cout<<i<<endl;
        //for (int j=0; j<=n; j++)
        //{
        //    for (int k=0; k<=n*n; k++)
        //        cout<<" "<<T[j][k];
        //    cout<<endl;
        //}
    }

    //for (int k=0; k<=n*n; k+=2)
    //    cout<<" "<<T[0][k];
    //cout<<endl;

    cout<<T[0][k]<<endl;
}


Measured memory_bytes: 2316
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    G=[[] for _ in range(N)]
    for i in range(N):
        A=int(input())
        for _ in range(A):
            x,y=map(int, input().split())
            x=x-1
            G[i].append((x,y))

    ans=0
    for p in range(1<<N):
        s=[0]*N
        tmp=0
        for i in range(N):
            if p&(1<<i):
                s[i] = 1
                tmp+=1
        for i in range(N):
            if s[i]==0: continue
            for x,y in G[i]:
                if s[x]!=y: break
            else:
                continue
            break
        else:
            ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

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

int main(void){
    int n, m, q;
    cin>>n>>m>>q;
    vector<pair<int, int> > v(m);
    vector<pair<int, int> > p(q);
    rep(i, m) {
        int a, b;
        cin>>a>>b;
        --a;--b;
        v[i]=make_pair(a, b);
    }
    sort(v.begin(), v.end());
    vector<int>left(m);
    vector<vector<int> > right(n, vector<int>(n));
    rep(i, m){
        left[i] = v[i].first;
        right[v[i].first][v[i].second]++;
    }
    vector<vector<int> > rightsum(n, vector<int>(n));
    rep(i, n){
        rightsum[i][0] = right[i][0];
        rep(j, n-1){
            rightsum[i][j+1] = rightsum[i][j] + right[i][j+1];
        }
    }
    rep(i, q){
        int a, b;
        cin>>a>>b;
        --a;--b;
        p[i]=make_pair(a, b);
    }
    rep(i, q){
        int a = p[i].first;
        int b = p[i].second;
        int ans = 0;
        for(int i = 0;i<n;i++){
            if(i<a) continue;
            ans += rightsum[i][b];
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 6016
n = int(input())
plist = list(map(int, input().split()))
pd = {}
for i, p in enumerate(plist):
  pd[p] = i + 1

al = [30000 * i for i in range(1, n+1)]
print(*al)
bl = [30000 * (n - i) + pd[i] for i in range(1, n+1)]
print(*bl)


Measured memory_bytes: 7844
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB push_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[200005],n,b[200005],cnt0;
int cnta,cntb,maxi=1e18;
int check(int p){
	int re;
	if(p>=0){
		re=cnta*cntb+(cnta+cntb)*cnt0+cnt0*(cnt0-1)/2;
		if(!p)RE re;
		FOR(i,1,cnta){
			if(a[i]*a[i]>=p)break;
			re=re+upper_bound(a+1,a+cnta+2,p/a[i])-a-1-i;
		}
		FOR(i,1,cntb){
			if(b[i]*b[i]>=p)break;
			re=re+upper_bound(b+1,b+cntb+2,p/b[i])-b-1-i;
		}
		RE re;
	}else{
		re=0;p=-p;
		FOR(i,1,cnta){
			re=re+cntb-(lower_bound(b+1,b+cntb+2,p/a[i]+(p%a[i]!=0))-b)+1;
		}
		RE re;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m;
	cin>>n>>m;
	int x;
	FOR(i,1,n){
		cin>>x;
		if(x>0)a[++cnta]=x;
		else if(x<0)b[++cntb]=-x;
		else cnt0++;
	}
	sort(a+1,a+cnta+1);
	sort(b+1,b+cntb+1);
	a[cnta+1]=b[cntb+1]=maxi+10;
	int l=-maxi,r=maxi,mid,ans;
	while(r>=l){
		mid=(r+l)>>1;
		if(check(mid)>=m){
			ans=mid;
			r=mid-1;
		}else l=mid+1;
	}
	cout<<ans;
	RE 0;
}



Measured memory_bytes: 1664
package main

import (
	"bufio"
	"container/heap"
	. "fmt"
	"io"
	"os"
	"sort"
)

type pair struct{ r, l int }

type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].l-h[i].r > h[j].l-h[j].r }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func (h *hp) push(v pair)        { heap.Push(h, v) }
func (h *hp) pop() pair          { return heap.Pop(h).(pair) }
func (h hp) empty() bool         { return len(h) == 0 }
func (h hp) top() pair           { return h[0] }

type hp2 []pair

func (h hp2) Len() int            { return len(h) }
func (h hp2) Less(i, j int) bool  { return h[i].r-h[i].l > h[j].r-h[j].l }
func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func (h *hp2) push(v pair)        { heap.Push(h, v) }
func (h *hp2) pop() pair          { return heap.Pop(h).(pair) }
func (h hp2) empty() bool         { return len(h) == 0 }
func (h hp2) top() pair           { return h[0] }

// github.com/EndlessCheng/codeforces-go
func run(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()

	var n int
	var s []byte
	Fscan(in, &n)
	checks := make([]pair, n)
	for i := range checks {
		Fscan(in, &s)
		l := 0
		r := 0
		for _, b := range s {
			if b == '(' {
				l++
			} else {
				if l == 0 {
					r++
				} else {
					l--
				}
			}
		}
		checks[i] = pair{r, l}
	}
	sort.Slice(checks, func(i, j int) bool { a, b := checks[i], checks[j]; return a.r < b.r })


	h := &hp{}
	cntL := 0
	for i := 0; i < n; {
		if checks[i].r > cntL {
			Fprintln(out, "No")
			return
		}
		for ; i < n && checks[i].r <= cntL; i++ {
			h.push(checks[i])
		}
		for !h.empty() && h.top().l >= h.top().r {
			p:=  h.pop()
			cntL +=p.l-p.r
		}
	}

	checks = []pair{}
	for !h.empty() {
		checks = append(checks, h.pop())
	}
	sort.Slice(checks, func(i, j int) bool { a, b := checks[i], checks[j]; return a.l < b.l })


	h2 := &hp2{}
	cntR := 0
	for i := 0; i < len(checks); {
		if checks[i].l > cntR {
			Fprintln(out, "No")
			return
		}
		for ; i < len(checks) && checks[i].l <= cntR; i++ {
			h2.push(checks[i])
		}
		for !h2.empty() && h2.top().r > h2.top().l {
			p:=h2.pop()
			cntR += p.r-p.l
		}
	}
	for !h2.empty() {

		p:=h2.pop()
		cntR += p.r-p.l
	}


	if cntL==cntR {
		Fprintln(out, "Yes")
	} else {
		Fprintln(out, "No")
	}
}

func main() { run(os.Stdin, os.Stdout) }


Measured memory_bytes: 65796
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#define REP(i, n) for(int i=0; i<(n); i++)
#define FOR(i, a, n) for(int i=(a); i<(n); i++)
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;

ll mod = 1000000007;
char zero = '0';

int main(){
    ll N;
    cin >> N;
    cout << ((N-1)*N)/2 << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque

n = int(input())
a = [0]*n

for i in range(n):
    a[i] = list(map(lambda x:int(x)-1,input().split()))
    a[i].append(-1)

t = [a[i][0] for i in range(n)]

l = [0]*n
day = [0]*n

q = deque([i for i in range(n)])

while q:
    u = q.popleft()
    v = a[u][l[u]]
    if a[v][l[v]] == u:
        day[u] = day[v] = max(day[u],day[v]) + 1
        l[u] += 1
        l[v] += 1
        q.append(u)
        q.append(v)

if any(x != n-1 for x in l):
    print(-1)
    exit()

print(max(day))

Measured memory_bytes: 63580
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<numeric>
#include<set>
#include<map>
#include<deque>
#include<list>
#include<forward_list>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define ll long long
#define v vector<ll>
const ll w = (1e9 + 7);
using namespace std;
void fireman()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
struct great {
	//descending order
	bool operator()(int x, int y)
	{
		return x < y;
	}
};


struct small {
	//asecending order
	bool operator()(int x, int y)
	{
		return x > y;
	}
};

int prime(int x)
{
	bool b = true;
	if (x == 2)
	{
		return true;
	}
	else if (x == 1 || x % 2 == 0)
	{
		return false;
	}
	for (int i = 3; i * i <= x; i += 2)
	{
		if (x % i == 0)
		{
			b = false;
			return false;
			break;
		}
	}
	return true;
}
bool great1(int a, int b)
{
	//descending order 
	return a > b;
}
bool small1(int a, int b)
{
	//asecending order 
	return a < b;
}
/*int sum_range(ll i, ll j, ll k, ll l, vector<vector<ll>>& S) {
	return S[k][l] - S[k][j - 1] - S[i - 1][l] + S[i - 1][j - 1];
}*/
int main()
{
	fireman();
	long long x,s=0;
	cin >> x;
	for(int i=1;i<=x;i++)
	{
		ll z = x / i;
		s += i * ((z * (z + 1)) / 2);
	}
	cout << s << endl;
}







Measured memory_bytes: 3596
x1,y1,x2,y2=map(int,input().split())
fx=1
fy=1
if x1>x2:
	x1,x2=x2,x1
	fx=-1
if y1>y2:
	y1,y2=y2,y1
	fy=-1

n=int(input())
p=[]
for i in range(n):
	x,y=map(int,input().split())
	if x1<=x<=x2 and y1<=y<=y2:
		p.append((fx*x,fy*y))
p=[y for x,y in sorted(p)]

from bisect import bisect_left as bl

b=[]

for y in p:
	pos=bl(b,y)
	if len(b)<=pos:
		b.append(y)
	else:
		b[pos]=y
	
from math import pi

l=len(b)

if l==min(x2-x1,y2-y1)+1:
	print(100*(x2-x1+y2-y1)+(5*pi-20)*(l-1)+(10*pi-20))
else:
	print(100*(x2-x1+y2-y1)+(5*pi-20)*l);


Measured memory_bytes: 33940
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105,mod=1e9+7;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline int ksm(int x,int y)
{
	if(y<=0) return 1;//为什么要加这一句？ 
	int res=1;
	for(;y;y>>=1,x=(x*x)%mod)if(y&1)res=(res*x)%mod;
	return res;
}
int a[N],Has[N],tot,f[N][N],n,ans;
signed main(void)
{
	n=read();
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		Has[++tot]=a[i];
	}
	sort(Has+1,Has+tot+1);
	tot=unique(Has+1,Has+tot+1)-Has-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(Has+1,Has+tot+1,a[i])-Has;
	for(int i=1;i<=n;i++)
	{
		int now=ksm(2,Has[a[i]]-Has[a[i-1]]);
		f[i][0]=(f[i-1][0]<<1)%mod;
		for(int j=a[i]+1;j<=a[i-1];j++)f[i][0]=(f[i][0]+((f[i-1][j])<<1)%mod)%mod;
		for(int j=1;j<=min(a[i-1],a[i]);j++)f[i][j]=f[i-1][j]*now%mod;
		for(int j=a[i-1]+1;j<=a[i];j++)
		if(j==1)f[i][j]=f[i-1][0]*(ksm(2,Has[j])-2)%mod*ksm(2,Has[a[i]]-Has[j])%mod;
		else f[i][j]=(f[i-1][0]<<1)*(ksm(2,Has[j]-Has[j-1])-1)%mod*ksm(2,Has[a[i]]-Has[j])%mod;
	}
	for(int i=0;i<=tot;i++)ans=(ans+f[n][i])%mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
const ll mod=1e9+7;


int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n,m;
    cin>>n>>m;
    vector<ll> a(m);
    ll sum=0;
    for(ll i=0;i<m;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum>n)
        cout<<-1;
    else
        cout<<n-sum;

    return 0;
}

Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
using namespace std;
typedef long long LL;
const int N = 305;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

namespace ModCalculator {
	const int MOD = 1e9 + 7;
	inline void Inc(int &x, int y) {
		x += y; if (x >= MOD) x -= MOD;
	}
	inline void Dec(int &x, int y) {
		x -= y; if (x < 0) x += MOD;
	}
	inline int Add(int x, int y) {
		Inc(x, y); return x;
	}
	inline int Sub(int x, int y) {
		Dec(x, y); return x;
	}
	inline int Mul(int x, int y) {
		return 1LL * x * y % MOD;
	}
	inline int Ksm(int x, int k) {
		int ret = 1;
	   	for (; k; k >>= 1) {
		    if (k & 1) ret = Mul(ret, x);
		    x = Mul(x, x);
		}
		return ret;
	}
	inline int Inv(int x) {
		return Ksm(x, MOD - 2);
	}
}
using namespace ModCalculator;

int n, d[N];
int fac[N], finv[N];
int dp[N][N][2];

void init() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(d[i]);
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = Mul(fac[i - 1], i);
	}
	finv[n] = Inv(fac[n]);
	for (int i = n; i >= 1; --i) {
		finv[i - 1] = Mul(finv[i], i);
	}
}

void solve() {
	bool cir = 1;
	for (int i = 1; i <= n; ++i) {
		cir &= (d[i] == 2);
	}
	if (cir) {
		printf("%d\n", Mul(fac[n - 1], finv[2]));
		return;
	}
	dp[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int k = 0; k < 2; ++k) {
				Inc(dp[i][j][k], Mul(dp[i - 1][j][k], finv[d[i] - 1]));
				if (d[i] > 1) {
					Inc(dp[i][j + 1][k], Mul(dp[i - 1][j][k], finv[d[i] - 2]));
				}
				if (!k && d[i] > 2) {
					Inc(dp[i][j + 1][1], Mul(dp[i - 1][j][k], finv[d[i] - 3]));
				}
			}
		}
	}
	int ans = 0;
	for (int i = 3; i < n; ++i) {
		Inc(ans, Mul(dp[n][i][1], Mul(fac[n - i - 1], Mul(fac[i - 1], finv[2]))));
	}
	printf("%d\n", ans);
}

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


Measured memory_bytes: 4416
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <queue>
using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
    ll a, b, c, tmp;
    // __int128 tmp, d;

    cin >> a >> b >> c;

    tmp = c - a - b;

    if(tmp*tmp > 4*a*b){
        if(tmp > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

// t * 0.1  = B
// t * 0.08 = A

// t = (B+r1)/0.1
// t = (A+r2)/0.08


Measured memory_bytes: 256
N = int(input())
L = []

for _ in range(N):
	a, b = map(int, input().split())
	L.append((a-b, a+b))

L = sorted(L, key = lambda x:x[1])
start = L[0][1]
ans = 1

for i in range(1, N):
	if start <= L[i][0]:
		ans += 1
		start = L[i][1]
print(ans)			

Measured memory_bytes: 19028
# ビット演算でなく, itertoolsモジュールのproductとrange(2)の組み合わせを活用.
# ※を！

from itertools import product

h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
#print(c)

ans = 0

#l = list(product(range(2), repeat=h))
#m = list(product(range(2), repeat=w))
#print(l)
#print(m)

for row_bit in product(range(2), repeat=h):# ※長さがhで, 要素が'1'か'0'であるすべての組み合わせをすべて列挙
    for col_bit in product(range(2), repeat=w):
        cnt = 0
        for row in range(h):
            for col in range(w):
                if row_bit[row] == 0 and col_bit[col] == 0:# 縦横赤で塗られることなく...
                    if c[row][col] == "#": #もともと黒で塗られている場合
                        cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Measured memory_bytes: 9012
#include <stdio.h>

int main(){
	int a, b, c, d, n;
	
	while( scanf("%d", &n) != EOF){
		int count = 0;
		for( a = 0; a < 10; a++){
			for( b = 0; b < 10; b++){
				for( c = 0; c < 10; c++){
					for( d = 0; d < 10; d++){
						if( a + b + c + d == n){
							count++;
							break;
						}
					}
				}
			}
		}
		printf("%d\n", count);
	}
		
	return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    int N;
    int a[11000];
    cin >> N;

    int res = 0;
    for (int i = 0; i<N; i++) {
        cin >> a[i];
        while (a[i] > 1) {
            if (a[i] % 2 == 0) {
                ++res;
                a[i] /= 2;
            }
            else break;
        }
    }
    
    cout << res << endl;

}


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

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
using vvl = vector<vl>;
using pll = pair<ll,ll>;
using vb = vector<bool>;

const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;

#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define xx first
#define yy second

#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define FORD(i,a,b) for (int i=int(b)-1; i>=(a); i--)

#define rv(type,name,count) vector<type> name(count); FOR(_i,0,count) cin >> name[_i];
#define grid(type,name,c1,c2) vector<vector<type>> name(c1, vector<type>(c2)); FOR(_i,0,c1)FOR(_j,0,c2)cin >> name[_i][_j];

ll n;
const ll MAXN = 302;
double dp[MAXN][MAXN][MAXN];
/*double e(vl & v) {
	if (v[0] == n) return 0;
	if (dp[v[0]][v[1]][v[2]] >= 0) return dp[v[0]][v[1]][v[2]];
//	if (m.find(v) != m.end()) return m[v];
}*/

int main() {
	cin >> n;
	FOR(a,0,MAXN)
	FOR(b,0,MAXN)
	FOR(c,0,MAXN) dp[a][b][c] = 0;
	vl v(4);
	FOR(i,0,n) {
		ll x;
		cin >> x;
		v[x]++;
	}
	//vl v(4);
	FOR(rem, 1, n+1)
	FORD(a1, 0, rem+1) {
		FORD(a2, 0, rem+1 - a1) {
			ll a3 = rem - a1 - a2;
			//FOR(a3, 0, rem+1 - a1 - a2) {
				if (a1 + a2 + a3 == 0) continue;
				double res = 0;
				if (a1) {
					double d = double(a1) / n;
					res += d * dp[a1-1][a2][a3];
				}
				if (a2) {
					double d = double(a2) / n;
					res += d * dp[a1+1][a2-1][a3];
				}
				if (a3) {
					double d = double(a3) / n;
					res += d * dp[a1][a2+1][a3-1];
				}

				double leave = (a1 + a2 + a3) / double(n);
				dp[a1][a2][a3] = (1 + res) / leave;
			//}
		}
	}
	
	cout << fixed << setprecision(15) << dp[v[1]][v[2]][v[3]] << endl;
}


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

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

#define vi vector<int>
#define vll vector<long long>
#define ll long long
#define ull unsigned long long
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl cout<<'\n'
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define pll pair<long long,long long>
#define vpii vector<pair<int,int> >
#define vpll vector<pair<ll,ll> >
#define si set<int>
#define sll set<long long>
#define all(v) (v).begin(),(v).end()
#define Unique(x)           (x).erase(unique(all(x)), x.end())
#define v_present(vec,x)  (find(all(vec),x)!=(vec).end())
#define present(myset,x)    ((myset).find(x)!=(myset).end())
#define Cprint(c)  for(auto i:(c)) { cout<<i<<" "; } nl
#define trace2(x,y) cout<<x<<" "<<y<<endl;
#define trace3(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;
#define trace4(x,y,z,a) cout<<x<<" "<<y<<" "<<z<<" "<<a<<endl;
ll mod = 1e9+7;
const int MAX = 1e5+5;
using namespace std;

ll dp[3003][3003]; //represents length LCS between substring ending at ith index of s1 and jth index of s2

int main()
{
    FAST_IO;
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.size(); int m=s2.size();

    for(int i=0;i<=n;i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
                continue;
            }

            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                if (dp[i - 1][j] > dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
    }
    string ans="";
    int tot=dp[n][m];
    int i=n; int j=m;

    for(int len=tot;len>0;){
        if(s1[i-1]==s2[j-1]){
            ans+=s1[i-1];
            i--; j--;
            len--;
        }
        else{
            if(dp[i-1][j]>dp[i][j-1]){
                i--;
            }
            else{
                j--;
            }
        }
    }
    reverse(all(ans));
    cout<<ans;
    return 0;

}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L

bool isPrime(long long x) {
    if (x == 1) return true;
    for (long long i = 2; i*i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

long long gcd(long long a, long long b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

vector<long long> common_divisors(long long a, long long b) {
    long long n = gcd(a, b);
    vector<long long> ans;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (n / i == i) {
                ans.push_back(i);
            }
            else {
                ans.push_back(n / i);
                ans.push_back(i);
            }
        }
    }
    return ans;
}

int main() {
    int a, b;
    cin >> a >> b;
    int mx = max(a + b, max(a - b, a * b));
    cout << mx;
    return 0;
}

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

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        char s[]=bu.readLine().toCharArray();
        for(int i=0;i<s.length;i++)
        if(s[i]=='?') sb.append('D');
        else sb.append(s[i]);
        System.out.print(sb);
    }
}


Measured memory_bytes: 37568
using System;
using System.IO;

    class Program
    {
        static void Main(string[] args)
        {
            var money = long.Parse(Console.ReadLine());
            var ret = 0;
            var after = money;

            while(true)
            {
                var tmp = after - 500;
                if(tmp < 0)
                {
                    break;
                }
                ret += 1000;
                after = tmp;
            }

            while (true)
            {
                var tmp = after - 5;
                if (tmp < 0)
                {
                    break;
                }
                ret += 5;
                after = tmp;
            }
            MyConsoleWrightLine(ret.ToString());
        }

        private static void MyConsoleWrightLine(string str)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            Console.WriteLine(str);

            Console.Out.Flush();
        }
}


Measured memory_bytes: 11220