akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cctype>
#define rep(x,y,z) for(long long x=y;x<z;++x)
#define dwn(x,y,z) for(long long x=y;x>z;--x)
using namespace std;

typedef long long ll;

ll n, m;
const ll mod = 1000000007;

int main() {
    cin >> n >> m;
    unordered_map<ll, bool> map_;
    unordered_map<ll, ll> map1[2];
    vector<ll> a(n), b(m);
    rep(i,0,n) {
        cin >> a[i];
        map_[a[i]] = false;
        ++map1[0][a[i]];
    }
    rep(i,0,m) {
        cin >> b[i];
        map_[b[i]] = false;
        ++map1[1][b[i]];
    }
    vector<pair<ll, ll>> d;
    vector<ll> free(n + m);
    rep(i,0,n) {
        free[i] = m;
    }
    rep(i,0,m) {
        free[n + i] = n;
    }
    rep(i,0,n) {
        d.push_back(make_pair(a[i], i));
    }
    rep(i,0,m) {
        d.push_back(make_pair(b[i], n + i));
    }
    sort(begin(d), end(d));
    ll res = 1;
    ll cnt = 0;
    rep(i,0,n + m) {
        ll max_i = d[i].first;
        ll id = d[i].second;
        if (!map_.at(max_i)) {
            if (map1[1][max_i] > 1 || map1[0][max_i] > 1) {
                res *= 0;
                break;
            } else if (map1[0][max_i] == 1 && map1[1][max_i] == 1) {

            } else {
                res = (res * free[id]) % mod;
            }
            cnt++;
            --free[id];
            map_[max_i] = true;
        }
        rep(j,0,free[id]) {
            res = (res * (max_i - cnt)) % mod;
            ++cnt;
        }
        free[id] = 0;
        if (id < n) {
            rep(j,0,m) {
                --free[n + j];
            }
        } else {
            rep(j,0,n) {
                --free[j];
            }
        }
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main(){
    int n,b,c,count = 0;
    cin >> n;

    for(int i = 0;i < 4;i++){
        if(count>=3)break;
        b = n%10;
        n /= 10;
        if(i == 0){
            c = b;
            count++;
            }
        else if(b == c){
            count++;
        }else{
            count = 1;
            c = b;
        }
    }

    if(count >= 3)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
n,m,c=map(int,input().split())
b=list(map(int,input().split()))
ans=0
for i in range(n):
    a=list(map(int,input().split()))
    num=0
    for l in range(m):
        num+=a[l]*b[l]
    if num+c>0:
        ans+=1
print(ans)

Measured memory_bytes: 9192
N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

def solve(a):
  if a[0]!=0:
    return -1
  ans=0
  for i in range(1,len(a)):
    if a[i]==a[i-1]+1:
      ans+=1
    elif a[i]<=a[i-1]:
      ans+=a[i]
    else:
      return -1
  return ans

print(solve(A))

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int mod = 1e9 + 7;
    int n;
    ll sum = 1;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        sum = sum * i % mod;
    }

    OP(sum);

    return 0;
}

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

using namespace std;

using ll = long long;

template <typename T>
struct SegmentTree {
    int n;
    vector<T> data;
    T INITIAL_VALUE;

    //使うときは、この2つを適宜変更する
    static T merge(T x, T y);
    void updateNode(int k, T x);

    SegmentTree(int size, T initial_value) {
        n = 1;
        INITIAL_VALUE = initial_value;
        while (n < size) n *= 2;
        data.resize(2 * n - 1, INITIAL_VALUE);
    }

    SegmentTree(const vector<T>& v, T initial_value) {
        int size = v.size();
        n = 1;
        INITIAL_VALUE = initial_value;
        while (n < size) n *= 2;
        data.resize(2 * n - 1, INITIAL_VALUE);

        for (int i = 0; i < size; i++) data[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--) data[i] = merge(data[i * 2 + 1], data[i * 2 + 2]);
    }

    T getLeaf(int k) {
        return data[k + n - 1];
    }

    void update(int k, T x) {
        k += n - 1; //葉の節点
        updateNode(k, x);
        while (k > 0) {
            k = (k - 1) / 2;
            data[k] = merge(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }

    //区間[a, b)に対するクエリに答える
    //k:節点番号, [l, r):節点に対応する区間
    T query(int a, int b, int k, int l, int r) {
        //[a, b)と[l, r)が交差しない場合
        if (r <= a || b <= l) return INITIAL_VALUE;
        //[a, b)が[l, r)を含む場合、節点の値
        if (a <= l && r <= b) return data[k];
        else {
            //二つの子をマージ
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return merge(vl, vr);
        }
    }

    //外から呼ぶ用
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }

    //非再帰版: バグってるかもしれないので定数倍高速化する時以外使わないで
    //区間[a, b)に対するクエリに答える
    T query_fast(int a, int b) {
        T vl = INITIAL_VALUE, vr = INITIAL_VALUE;
        for (int l = a + n, r = b + n; l != r; l >>= 1, r >>= 1) {
            if (l & 1) vl = merge(vl, data[l++ - 1]);
            if (r & 1) vr = merge(data[--r - 1], vr);
        }
        return merge(vl, vr);
    }
};

//使うときは以下2つを変更
//非可換の場合は順序に注意！！！
template <typename T>
T SegmentTree<T>::merge(T x, T y) {
    return max(x, y);
}

template <typename T>
void SegmentTree<T>::updateNode(int k, T x) {
    data[k] = x;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    SegmentTree<int> st(a, 0);
    for (int i = 0; i < n; i++) {
        int ans = max(st.query(0, i), st.query(i + 1, n));
        cout << ans << "\n";
    }
    return 0;
}

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

signed main(){
  int H,W;
  cin>>H>>W;
  vector<vector<char>> A(H+2,vector<char>(W+2));
  rep(i,H+2){
    rep(j,W+2){
      if(i==0||j==0||i==H+1||j==W+1){
        A[i][j]='#';
      }else{
        cin>>A[i][j];
      }
    }
  }
  rep(i,H+2){
    rep(j,W+2){
      cout<<A[i][j];
    }
    cout<<endl;
  }
}

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

template <typename T>
class FenwickTree
{
public:
  int N;
  vector<T> dat;

  FenwickTree(int n, T m = 0)
  {
    init(n, m);
  }

  void init(int n, int m)
  {
    N = n;
    dat.resize(n + 1);
    for (int i = 0; i < dat.size(); i++)
    {
      dat[i] = m;
    }
  }

  int64_t sum(int i)
  {
    T s = 0;
    while (i > 0)
    {
      s += dat[i];
      i -= i & -i;
    }
    return s;
  }

  void add(int i, T x)
  {
    while (i <= N)
    {
      dat[i] += x;
      i += i & -i;
    }
  }
};

int main()
{
  int n;
  cin >> n;
  vector<int64_t> A(n);
  for (int i = 0; i < n; i++)
  {
    cin >> A.at(i);
  }
  vector<int64_t> copy = A;
  map<int64_t, int64_t> mp;
  sort(copy.begin(), copy.end());
  copy.erase(unique(copy.begin(), copy.end()), copy.end());
  int m = copy.size();
  for (int i = 0; i < m; i++)
  {
    mp[copy[i]] = i + 1;
  }
  for (int i = 0; i < n; i++)
  {
    A[i] = mp[A[i]];
  }
  int64_t ans = 0;
  FenwickTree<int64_t> ft(m + 1);
  for (int i = 0; i < n; i++)
  {
    ans += i - ft.sum(A[i]);
    ft.add(A[i], 1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 20064
#include<stdio.h>
#include<math.h>
#define true 1
#define false 0


int isPrime(int );

int main(){
  int num,a,i,cnt;
  while(1){
    scanf("%d",&num);
    if(num>=1&&num<=pow(10,4)) break;
  }
    for(i=0;i<num;i++){
      scanf("%d",&a);
      if(a>pow(10,8)||a<2) break;
      a = isPrime(a);
      if(a==1) cnt++;
    
    }
      


    printf("%d\n",cnt);

  return 0;
}

int isPrime(int x){

  int i;

  if(x==2) return true;

  if(x<2||x%2==0) return false;

  i = 3;
  while(i*i<=x){
    if(x%i == 0) return false;

    i = i + 2;

  }

  return true;

}




Measured memory_bytes: 2068
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	
	while(a > 0 and c > 0) {
		c -= b;
		if(c <= 0) {
			cout << "Yes" << '\n';
			return 0;
		}
		a -= d;
		if(a <= 0) {
			cout << "No" << '\n';
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;

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

int main() {
  int n, k, c;
  cin >> n >> k >> c;
  string s;
  cin >> s;
  auto getPos = [&]() {
    vector<int> res;
    for (int i = 0; i < n && res.size() < k;) {
      if (s[i] == 'o') {
        res.push_back(i);
        i += c+1;
      }else i++;
    }
    return res;
  };
  vector<int> l, r;
  l = getPos();
  reverse(all(s));
  r = getPos();
  if (l.size() != k || r.size() != k) return 0;
  REP(i, r.size()) r[i] = n-1-r[i];
  reverse(all(r));
  REP(i, k) {
    if (l[i] == r[i]) cout << l[i]+1 << endl;
  }

  return 0;
}

Measured memory_bytes: 3448
#include <stdio.h>

int main(void) {

  int a, b, c, x, y, z;
  scanf("%d %d %d", &a, &b, &c);
  if(a < b) {
    if(a < c) {
      x = a;
      if(b < c) {
	y = b;
	z = c;
      } else {
	y = c;
	z = b;
      }
    } else {
      x = c;
      y = a;
      z = b;
    }
  } else {
    if(b < c) {
      x = b;
      if(a < c) {
	y = a;
	z = c;
      } else {
	y = c;
	z = a;
      }
    } else {
      x = c;
      y = b;
      z = a;
    }
  }
  printf("%d %d %d\n", x, y, z);

 return 0;
}

Measured memory_bytes: 596
def nrc_mod(n, r, mod=10**9+7):
    r = min(n - r, r)
    if r == 0:
        return 1

    over = 1
    for i in range(n, n - r, -1):
        over = over * i % mod

    under = 1
    for i in range(1, r + 1):
        under = under * i % mod

    inv = pow(under, mod - 2, mod)
    return over * inv % mod


n, a, b = map(int, input().split())
MOD = 10**9 + 7

# 0本を選ぶは無しなので-1
# 取るか取らないかの２択がn種類ある
ans = pow(2, n, MOD) - 1
ans -= nrc_mod(n, a, MOD)
ans -= nrc_mod(n, b, MOD)
while ans < 0:
    ans += MOD
print(ans)


Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,a[110];
double cnt;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],cnt+=(double)1/a[i];
	cout<<(double)1/cnt<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> G(100000);
vector<int> c(100000);
void dfs(int s, int x){
    if(c[s]) return;
    c[s]=x;
    for(auto a:G[s]) dfs(a,x);
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=0;i<n;++i) dfs(i,i+1);
    int q;
    cin>>q;
    for(int i=0;i<q;++i){
        int a,b;
        cin>>a>>b;
        cout<<(c[a]-c[b]?"no":"yes")<<endl;
    }
}

Measured memory_bytes: 11764
#include <stdio.h>

int main(void){
	int N;
	scanf("%d",&N);
	int S = 0;
	int j,n=N,m;
	while(n > 9){
		m = n/10;
		j = n-m*10;
		S += j;
		n = m;
	}
	S += n;
	
	if(N%S ==0)	printf("Yes");
	else		printf("No");

	return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define llint long long int
#define vvint vector<vector<int>>
#define vint vector<int>

using namespace std;

int main() {
	string a, b, c;
	cin >> a >> b >> c;
	int A = 0, B = 0, C = 0;
	int now = 0;
	while (1) {
		char ch;
		if (now == 0) {
			ch = a[A];
			A++;
		}
		else if (now == 1) {
			ch = b[B];
			B++;
		}
		else {
			ch = c[C];
			C++;
		}
		if (ch == 'a')now = 0;
		if (ch == 'b')now = 1;
		if (ch == 'c')now = 2;
		if (A == a.size()+1) {
			cout << "A" << endl;
			break;
		}
		if (B == b.size()+1) {
			cout << "B" << endl;
			break;
		}
		if (C == c.size()+1) {
			cout << "C" << endl;
			break;
		}
	}
	return 0;
}

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

using namespace std;

int main() {
    int N;
    cin >> N;
    int x;
    cin >> x;
    vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    if( accumulate(A.begin(), A.end(), 0ll) == x ){
        cout << N << endl;
    }else{
        int ans = 0;
        long long tot = 0;
        for(int i = 0 ; i < N ; i++){
            if( tot + A[i] <= x ){
                tot += A[i];
                ans++;
            }else{
                break;
            }
        }
        cout << min(N-1, ans) << endl;
    }


}


Measured memory_bytes: 256
import math
import collections

def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    ans = [1]*N

    for m in range(M):
        A, B = map(int, input().split())
        if H[A-1] == H[B-1]:
            ans[A - 1] = 0
            ans[B - 1] = 0
        elif H[A-1] < H[B-1]:
            ans[A-1] = 0
        else:
            ans[B-1] = 0

    #print(ans)
    print(sum(ans))
    return 0

if __name__ == '__main__':
    main()

Measured memory_bytes: 20584
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
map<string,int>mp;
int main() {
	int q;
	cin >> q;
	while (q--) {
		int Q;
		cin >> Q;
		string s;
		int x;
		switch (Q) {
		case 0:
			cin >> s >> x;
			mp[s] = x;
			break;
		case 1:
			cin >> s;
			cout << mp[s] << endl;
			break;
		case 2:
			cin >> s;
			mp.erase(s);
		}
	}
	return 0;
}


Measured memory_bytes: 27768
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

#include<atcoder/lazysegtree>
using namespace atcoder;

const int M=1000000;
int n,q;
ll a[M],b[M];

struct S{
	ll x,s;
};

using F=ll;

S op(S l,S r){
	S t={(l.x*a[r.s]+r.x)%mod,l.s+r.s};
	return t;
}
S e(){return S{0,0};}
S mapping(F l,S r){
	if(l==0) return r;
	return S{l*b[r.s-1]%mod,r.s};
}
F composition(F l,F r){
	if(l==0) return r;
	return l;
}
F id(){return 0;}

int main(){
	cin>>n>>q;
	a[0]=b[0]=1;
	for(int i=1;i<M;i++) a[i]=a[i-1]*10%mod;
	for(int i=1;i<M;i++) b[i]=(a[i]+b[i-1])%mod;
	lazy_segtree<S,op,e,F,mapping,composition,id> st(vector<S>(n,{1,1}));
	for(int i=0;i<q;i++){
		int l,r,x;
		cin>>l>>r>>x;
		l--;
		st.apply(l,r,x);
		cout<<st.prod(0,n).x<<endl;
	}
}

Measured memory_bytes: 32300
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String str = scanner.next();
        List<Character> list = new ArrayList<>();
        String left = "";
        String right = "";
        for (int i = 0; i < n; i++) {
            list.add(str.charAt(i));
            if (list.size() >= 2 && list.get(list.size()-2) < list.get(list.size()-1)){
                list.remove(list.size()-1);
                list.remove(list.size()-1);
            }
        }
        for (char c:list
             ) {
            if (c == ')'){
                left += '(';
            }else {
                right += ')';
            }
        }
        System.out.println(left+str+right);
    }
}


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

struct hello{
	int num;
	int rank;
	string city;
};

bool comp(hello a,hello b){
	if(a.city != b.city){
		return a.city<b.city;
	}
	else return a.num>b.num;
}

int main() {
	// your code goes here
	int n;
	cin>>n;
	hello hel[n];
	for(int i = 0;i < n;i++){
		hel[i].rank = i+1;
		cin>>hel[i].city;
		cin>>hel[i].num;
	}
	sort(hel,hel+n,comp);
	for(int i = 0;i < n;i++){
		cout<<hel[i].rank<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>

#pragma GCC optimize("O3")

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

#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define repd(i, n) for(ll i = (n) - 1; i >= 0; --i)
#define FOR(i, a, b) for(ll i = a; i <= ll(b); ++i)
#define FORD(i, a, b) for(ll i = a; i >= ll(b); --i)
#define loop while(true)
#define asort(array, size) std::sort(array, array + size)
#define cauto const auto&
#define bit(n) (1LL << (n))

int main()
{
    ll N;
    cin >> N;
    ll count = 0;
    ll max = 0;
    rep(i, N) {
        ll A;
        cin >> A;
        if (max < A) max = A;
        else {
            count += (max - A);
        }
    }
    cout << count << endl;
}


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

using namespace std;

#define INF 1e9 + 5

typedef long long ll;

int main(){
	int n;
	cin >> n;
	vector<int> dp(3, 0);
	for(int i = 0;i<n;i++){
		vector<int> v(3);
		for(int i = 0;i<3;i++)
			cin >> v[i];
			
		vector<int> dp_change(3, 0);
		for(int i = 0;i<3;i++){
			for(int j = 0;j<3;j++){
				if(i != j)
					dp_change[j] = max(dp_change[j], dp[i] + v[j]);
			}
		}
		dp = dp_change;
	}
	
	cout << max({dp[0],dp[1],dp[2]}) << "\n";
}

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

int main(){
	
	string l; cin>>l;
	vector<vector<ll>> dp(l.size(),vector<ll>(2));
	dp.at(0).at(0) = 2;
	dp.at(0).at(1) = 1;
	for(int i=1; i<l.size(); i++){
		if(l.at(i)=='0'){
			(dp.at(i).at(0)+=dp.at(i-1).at(0))%=MOD;
			(dp.at(i).at(1)+=dp.at(i-1).at(1)*3)%=MOD;
		}
		if(l.at(i)=='1'){
			(dp.at(i).at(0)+=dp.at(i-1).at(0)*2)%=MOD;
			(dp.at(i).at(1)+=dp.at(i-1).at(1)*3)%=MOD;
			(dp.at(i).at(1)+=dp.at(i-1).at(0))%=MOD;
		}
	}
	cout << (dp.back().at(0)+dp.back().at(1))%MOD << endl;
	
}



Measured memory_bytes: 5760
from itertools import product


def main():
    N = int(input())
    L = len(str(N))
    result = 0
    if N < 357:
        print(0)
        return

    for i in range(3, L+1):
        for p in product("357", repeat=i):
            c = [p.count(i) for i in ("3", "5", "7")]
            x = int("".join(p))
            if x > N:
                break
            if all(c):
                result += 1

    print(result)
    return


if __name__ == '__main__':
    main()


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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);  
	
	int n;
	cin >> n;
	vector<vector<int>> f(n, vector<int>(10));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 10; j++) {
			cin >> f[i][j];
		}
	}
	vector<vector<int>> p(n, vector<int>(11));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 11; j++) {
			cin >> p[i][j];
		}
	}
	long long ans = -LLONG_MAX;
	for(int i = 1; i < (1 << 10); i++) {
		long long tmp = 0;
		vector<int> num(n);
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < 10; k++) {
				if((i >> k) & 1 && f[j][k]) num[j]++;
			}
		}
		for(int j = 0; j < n; j++) {
			tmp += p[j][num[j]];
		}
		ans = max(tmp, ans);
	}
	cout << ans << endl;
	return 0;	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uset unordered_set
#define umap unordered_map
#define db(x) cout << #x << " == " << x << ";\n"
#define a(x) x.begin(),x.end()
#define input(v,n) for(int i=0;i<n;i++)cin>>v[i]
typedef vector<int> vi;
typedef pair<int,int> pi;

const int inf = 1e5+7;
// ===================== MANASH =================== //

void test() {

	int a,b,c,k;
	cin >> a >> b >> c >> k;
	int sum = 0;
	if( a > 0 ) sum = min(a,k), k-=a;
	if( b > 0 and k > 0) k-= b;
	if ( c > 0 and k > 0) sum -=k;

	cout << sum;

}

int32_t main() {

	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);

	#ifdef LOCAL
	freopen("input.txt","r",stdin);
	#endif

	int T = 1;
	while(T--) {
		test();
		cout << "\n";
	}
	return 0;

}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
//#include <iostream>
//#include <vector>
//#include <string>
//#include <iomanip>
//#include <ctime>


using namespace std;

#define pb push_back
#define mp make_pair
#define eb emplace_back


typedef long long ll;
typedef long double ld;


const ll inf = 2e9;
const ll base = 998244353;
ll mod = 1e9 + 7;


int main() {
//    srand(time(NULL));
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
//    std::random_device rd;
//    std::mt19937 g(rd());
    auto start = clock();

    int n; cin >> n;
    vector<int> key_to_value(n);
    vector<int> cnt(n);
    for (int i = 0; i < n; ++i) {
        cin >> key_to_value[i];
        key_to_value[i]--;
        cnt[key_to_value[i]]++;
    }
    if (n == 2 && key_to_value[0] == 1 && key_to_value[1] == 0) {
        cout << -1;
        return 0;
    }
    set<int> not_used;
    vector<char> used(n, 0);
    vector<int> ans;
    for (int i = 0; i < n; ++i) not_used.insert(i);

    int bad = -1;
    for (int i = 0; i < n - 3; ++i) {
        for (auto c : not_used) {
            if (c == bad) continue;
            if (cnt[key_to_value[c]] >= n - i - 1 && !used[key_to_value[c]]) {
                continue;
            }
            used[c] = 1;
            not_used.erase(c);
            ans.pb(c);
            cnt[key_to_value[c]]--;
            bad = key_to_value[c];
            break;
        }
    }
    pair<pair<int, int>, int> best = {{INT_MAX, INT_MAX}, INT_MAX};
    for (auto i : not_used) {
        for (auto j : not_used) {
            for (auto k : not_used) {
                if ((set<int>{i, j, k}).size() != 3) continue;
                if (bad == i) continue;
                if (j == key_to_value[i]) continue;
                if (k == key_to_value[j]) continue;
                best = min(best, {{i, j}, k});
            }
        }
    }
    ans.pb(best.first.first);
    ans.pb(best.first.second);
    ans.pb(best.second);
    for (auto c : ans) {
        cout << c + 1 << ' ';
    }


    std::cerr << double(clock() - start) / CLOCKS_PER_SEC << std::endl;
    return 0;
}

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

int main(){
    int n; cin >> n;
    vector<ll> a(n),b(n),c(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n) cin >> c[i];
    sort(a.begin(),a.end());
    sort(c.begin(),c.end());
    ll ans=0;
    rep(i,n){
        auto itr=upper_bound(c.begin(),c.end(),b[i]);
        ll ng = distance(itr,c.end());
        auto itr2=lower_bound(a.begin(),a.end(),b[i]);
        ll sg = distance(itr2,a.end());
        ans+=ng*(n-sg);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
import bisect
a,b,q=map(int,input().split())
A=[-1*(10**12)]
B=[-1*(10**12)]
for i in range(a):
    A.append(int(input()))
for i in range(b):
    B.append(int(input()))

A.append(10**12)
B.append(10**12)

for i in range(q):
    x=int(input())
    ia=bisect.bisect_right(A,x)

    ms=A[ia-1]
    ps=A[ia]
    
    ib=bisect.bisect_right(B,x)
    
    mt=B[ib-1]
    pt=B[ib]
        
    ans=min(x-min(ms,mt),max(ps,pt)-x,(ps-mt)+min(ps-x,x-mt),(pt-ms)+min(pt-x,x-ms))
    print(ans)

Measured memory_bytes: 12088
#include <functional>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <math.h>
using namespace std;


int main() {
   int n,m;
 
   cin >> n >> m;
   if(n%m!=0){
      cout << n/m+1 << endl;
   }else{
      cout << n/m << endl;
   }
  
  
   
  return 0;
}

Measured memory_bytes: 256
import Data.Char -- for words func.
import Control.Monad -- for forM_ replicateM func.
import Numeric 
formatFloatN floatNum numOfDecimals = showFFloat (Just numOfDecimals) floatNum ""

type Vector = (Double, Double)
type Scalar = Double

---------------------------------------------------
-- alithmetic functions for vector calculations. --
---------------------------------------------------
vadd :: Vector -> Vector -> Vector
vadd (x, y) (z, w) = (x + z, y + w)

vsub :: Vector -> Vector -> Vector
vsub (x, y) (z, w) = (x - z, y - w)

vdot :: Vector -> Vector -> Scalar
-- vdot defines dot product for 2D vector.
vdot (x, y) (z, w) = x * z + y * w

smul :: Scalar -> Vector -> Vector
-- smul defines scalar multiplication of 2D vector.
smul a (x, y) = (a * x, a * y)

sqnorm :: Vector -> Scalar
-- calculate squared euclidean norm(sqnorm(x) = ||x||^2).
sqnorm (x, y) = x * x + y * y

projection_point :: Vector -> Vector -> Vector -> Vector
-- find the projection point when p_1, p_2, p are geven.
-- p_1, p_2 are the point on a straight line called l.
-- projection point are defined as the point on the l
-- is the most close to point p.
projection_point p_1 p_2 p
  | p_1 /= p_2 = (a `vdot` b / sqnorm a) `smul` a `vadd` p_1
  | otherwise  = p_1
  where
    a = p_2 `vsub` p_1
    b = p `vsub` p_1

--------------------------------------
-- functions for string formatting. --
--------------------------------------
line2ps :: String -> [Vector]
-- this function formatting line include p_1 and p_2 value
-- to list of p_1 and p_2.
-- e.g.
-- input: "0 0 2 0" -- i.e. "p_1x p_1y p_2x p_2y"
-- output: [(0, 0), (2, 0)] -- i.e. [p_1, p_2]
line2ps line = [p_1, p_2]
  where
    ps = words line
    p_1 = line2p . unwords $ take 2 ps
    p_2 = line2p . unwords $ drop 2 ps

line2p :: String -> Vector
-- transform string to vector.
-- input: "0 1" -- i.e. "p_x p_y"
-- output: (0, 1)
line2p line = p
  where
    ps = words line
    p_x = read (ps!!0) :: Double
    p_y = read (ps!!1) :: Double
    p = (p_x, p_y)

vec2line :: Vector -> String
vec2line (x, y) = (formatFloatN x 8) ++ " " ++ (formatFloatN y 8)

---------------------
-- main statement. --
---------------------
main :: IO()
main = do
  ps <- getLine
  q  <- getLine
  plist <- replicateM (read q) getLine
  let proj p = vec2line $ projection_point ((line2ps ps)!!0) ((line2ps ps)!!1) (line2p p) in putStrLn . init . unlines $ map proj plist


Measured memory_bytes: 5080
#!/usr/bin/env python3

import collections


def solve(cards):
    next_turn = "a"
    while cards:
        if not cards[next_turn]:
            return next_turn.upper()
        else:
            next_turn = cards[next_turn].popleft()


def main():
    cards = dict()
    cards["a"] = collections.deque(input())
    cards["b"] = collections.deque(input())
    cards["c"] = collections.deque(input())
    print(solve(cards))


if __name__ == '__main__':
    main()


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

int main() {
  string w;
  cin>>w;
  map<char, int> m;
  for (char c: w) {
    ++m[c];
  }
  for (auto i: m) {
    if (i.second % 2 != 0) {
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
N, K, Q = list(map(int, input().split()))
a = [int(input()) for i in range(Q)]

a_p = []
for i in range(N):
    a_p.append(Q)

for i in range(Q):
    a_p[a[i]-1] -= 1

result = []
for i in range(N):
    result.append(K - a_p[i])

for i in range(N):
    if result[i] > 0:
        print("Yes")
    else:
        print("No")
        

Measured memory_bytes: 14440
n = int(input())
h = list(map(int, input().split()))
rh = h[::-1]
result = [rh[0]]
for i in range(1, len(h)):
  if result[i - 1] >= rh[i]:
    result.append(rh[i])
  elif result[i - 1] == rh[i] - 1:
    result.append(rh[i] - 1)
  else:
    print('No')
    break
else:
  print('Yes')


Measured memory_bytes: 14396
if __name__ == '__main__':
    n = int(input())
    lst = list(map(int, input().split()))

    ans = (50*100)*(50*100)
    for i in range(-100,101):
        mn = 0
        for c in lst:
            mn += (i-c)*(i-c)
        ans = min(ans,mn)

    print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <string.h>
#include <map>
#define Z class
#define ln cout<<'\n'
#define ll long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
//ASCII a=97, A=65
// int H[N]; rep(i,N) scanf("%d", &H[i]);
// int max_x = *std::max_element(x.begin(), x.end());
// int min_y = *std::min_element(y.begin(), y.end());
// sort(vec.begin(), vec.end()); std::greater<>()
// reverse(vec.begin(), vec.end());
// scanf("%s",s);
// printf("%d\n",end-start+1);
using namespace std;
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<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
const long long INF = 1LL << 60;

int main(){
    int k,s; cin >> k >> s;
    int res = 0;
    
    for(int i=0; i<=k; ++i){
        for(int j=0; j<=k; ++j){
            int z = s - i - j;
            if(0 <= z && z <= k) res++;
        }
    }
    
    pr(res);
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[111][11111],N,W,c[111],d[111],bnu;
int kei(int i,int j){
    if(dp[i][j])return dp[i][j];
    if(i==N)return 0;
    if(j<d[i])return kei(i+1,j);
    return dp[i][j]=bnu=max(kei(i+1,j),kei(i+1,j-d[i])+c[i]);
}
int main(){
    cin>>N>>W;
    for(int i=0;i<N;i++)cin>>c[i]>>d[i];
    cout<<kei(0,W)<<endl;
}

Measured memory_bytes: 6844
///╔══╗
///╚╗╔╝
///╔╝╚(¯`v´¯)
///╚══╝`.¸.´farzin


#include <bits/stdc++.h>

#define int int64_t
#define pb push_back
#define ibsws ios_base::sync_with_stdio
#define gcd __gcd
#define S second
#define F first

using namespace std;

int t,x,y,n,k;
multiset<pair<int,int> > a;

int32_t main(){
	ibsws(true==false);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        a.insert({x,y});
    }
    multiset<pair<int,int> >::iterator it=a.begin();
    while(t<k){
        t+=(*it).S;
        x=(*it).F;
        it++;
    }
    cout<<x;
}


Measured memory_bytes: 6528
#include <stdio.h>
#include <stdlib.h>
#define Mod 1000000007

int **g;
int used[100000] = {};
int in[100000] = {};
int k;

long long ans;

long long P(long long a, long long b){
  long long r =  1;
  if(a < b) return 0;
  for(int i = 0; (long long)i < b; i++){
    r = r * a % Mod;
    a--;
  }
  return r;
}



void dfs(int u){
  used[u] = 1; int cnt = 0;
  for(int i = 0; i < in[u]; i++){
    if(used[g[u][i]] == 0) cnt++;
   
  }
  
  ans = ans * P((long long)k - 2, (long long)cnt) % Mod;
  for(int i = 0; i < in[u]; i++){
    if(used[g[u][i]] == 0){
      used[g[u][i]] = 1;
      dfs(g[u][i]);
    }
  }
  return;
}
      
  

int
main(int argc, char *atgv[])
{
  
  
  int n;
  used[0] = 1;
  int a, b;
  scanf("%d %d", &n, &k);
  g = malloc(sizeof(int *) * n);
  for(int i = 0; i < n; i++){
    g[i] = (int *)malloc(sizeof(int) * n);
  }
  for(int i = 0; i < n - 1; i++){
    scanf("%d %d", &a, &b);
    a--; b--;
    g[a][in[a]] = b; in[a]++;
    g[b][in[b]] = a; in[b]++;
  }
 
    
  ans = (long long)k * P((long long)k - 1, (long long)in[0]) % Mod;

  for(int i = 0; i < in[0]; i++){
    dfs(g[0][i]);
  }

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

  for(int i = 0; i < n; i++){
    free(g[i]);
  }
  free(g);

  return 0;
}

  
  


Measured memory_bytes: 414592
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const ll MOD = (ll) (1e9 + 7);
const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

//------------------------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << setiosflags(ios::fixed);

    int n;
    cin >> n;
    ld v[50];
    rep(i, n) cin >> v[i];
    sort(v, v + n);

    rep(i, n - 1) {
        v[i + 1] = (v[i] + v[i + 1]) / 2.0;
    }
    cout << v[n - 1] << endl;
    return 0;
}


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

int main(){

    int a,b,l1,l2;

    scanf("%d",&a);
    scanf("%d",&b);
    l1= a*b;
    l2= a+b-1;
    int luas  = l1-l2 ;
    printf("%d",luas);

    return 0;
}


Measured memory_bytes: 128
using System;

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input1 = Console.ReadLine().Split(' ');
            string[] input2 = Console.ReadLine().Split(' ');
            int c = 0;
            int a0 = int.Parse(input1[0]);
            int a1 = int.Parse(input1[1]);
            int a2 = int.Parse(input1[2]);
            int a3 = int.Parse(input1[3]);
            int a4 = int.Parse(input1[4]);
            int a5 = int.Parse(input1[5]);

            int b0 = int.Parse(input2[0]);
            int b1 = int.Parse(input2[1]);
            int b2 = int.Parse(input2[2]);
            int b3 = int.Parse(input2[3]);
            int b4 = int.Parse(input2[4]);
            int b5 = int.Parse(input2[5]);

            if ((a0 == b3 || a0 == b2) && (a5 == b3 || a5 == b2))
            {
                c = b1;
                b1 = b2;
                b2 = b4;
                b4 = b3;
                b3 = c;
            }


            //????????? ????????¢
            for (int i = 0; i < 3; i++)
            {
                if (a0 == b0 && a5 == b5)
                {
                    break;
                }
                else
                { 
                    c = b0;
                    b0 = b1;
                    b1 = b5;
                    b5 = b4;
                    b4 = c;
                }
            }
            //2??????????¨??????¢
            for (int i = 0; i < 3; i++)
            {
                if (a1 == b1 && a4 == b4)
                {
                    break;
                }
                else
                {
                    c = b1;
                    b1 = b2;
                    b2 = b4;
                    b4 = b3;
                    b3 = c;
                }
            }
            if (a0 == b0 && a0 == b0 && a1 == b1 && a2 == b2 && a3 == b3 && a4 == b4 && a5 == b5)
                Console.WriteLine("Yes");
            else
            Console.WriteLine("No");

        }
    }
}

Measured memory_bytes: 9040
#include <bits/stdc++.h>
using namespace std;
// 287644PV
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(10)<<(x)
int mod = 1000000000+7;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<double> prob(n);
    for (int i = 0; i < n; ++i) {
        cin >> prob[i];
    }
    vector<vector<double>> dp(n,vector<double>());
    dp[0].push_back(1-prob[0]);
    dp[0].push_back(prob[0]);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= i+1 ; ++j) {
            double ssolution = 0;
            if(j-1 >= 0)
            {
                ssolution += dp[i-1][j-1]*prob[i];
            }
            if(j <= i)
            {
                ssolution += dp[i-1][j]*(1-prob[i]);

            }
            dp[i].push_back(ssolution);
        }
    }

    double solution = 0;
    for (int k = 0; k < dp[n-1].size(); ++k) {
        solution += (dp[n-1][k] * (k>n/2));
    }

    cout << FIXED_FLOAT(solution);


}

Measured memory_bytes: 43776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;} return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;} return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W,K; cin >> H >> W >> K;
    vector<string> field(H);
    rep(i,H) cin >> field[i];
    vector<int> boundary;
    rep(i,H){
        int cnt=0;
        rep(j,W) if (field[i][j]=='#') ++cnt;
        if (cnt) boundary.emplace_back(i+1);
    }
    boundary.back()=H;
    vector<vector<int>> ans(H,vector<int>(W));
    int now=1,bound=0;
    for (int b:boundary){
        vector<int> num;
        rep(j,W) for (int i=bound;i<b;++i){
            if (field[i][j]=='#') num.emplace_back(j);
        }
        num.back()=W-1;
        int cnt=0;
        rep(j,W){
            while(num[cnt]<j) ++cnt,++now;
            for (int i=bound;i<b;++i) ans[i][j]=now;
        }
        ++now; bound=b;
    }
    rep(i,H) rep(j,W){
        cout << ans[i][j];
        if (j!=W-1) cout << ' ';
        else cout << endl;
    }
}

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

using namespace std;

int sg[200][200];
typedef long long LL;

int main() {
	LL x,y;
	scanf("%lld%lld",&x,&y);
	puts(abs(x-y)<=1?"Brown":"Alice");
	/*
	sg[0][0] = 0;
	for (int s=1;s<=40;s++) {
		for (int i=0;i<=s;i++) {
			int j = s - i;
			sg[i][j] = 0;
			for (int k=1;k<=i/2;k++) {
				sg[i][j] |= (sg[i-k*2][j+k] == 0);
			}
			for (int k=1;k<=j/2;k++) {
				sg[i][j] |= (sg[i+k][j-k*2] == 0);
			}
		}
	}
	for (int i=0;i<=15;i++) {
		for (int j=0;j<=15;j++) {
			printf("%d",sg[i][j]);
		}
		puts("");
	}
	*/
}

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

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair

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

using namespace std;

typedef pair<int,int> pii;

llong dp[2][201][20001] = {};
int main(){

  int n, W;
  scanf("%d %d", &n, &W);

  vector<llong> w(n);
  REP(i,n){
    scanf("%lld", &w[i]);
  }
  SORTV(w);

  dp[0][0][0] = 1;
  int now, next;
  REP(i,n){
    now = i&1; next = 1 - now;
    REP(j,n){
      REP(k,W+1){
        dp[next][j][k] = 0;
      }
    }

    REP(j,i+1){
      REP(k,W+1){
        if(k + w[i] <= W){
          if(i == j && i + 1 < n){
            dp[next][i+1][k + w[i]] += dp[now][j][k] % MOD; 
          }else{
            dp[next][j][k + w[i]] += dp[now][j][k] % MOD;
          }
        }
        dp[next][j][k] += dp[now][j][k] % MOD;
      }
    }
  }

  llong ans = 0;
  REP(i,n){
    REP(j,W+1){
      if(w[i] + j > W){ 
        ans += dp[next][i][j] % MOD;
        ans %= MOD;
      }
    }
  }
  cout << ans << endl;
  return 0;
}




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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int A,B,H;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>H;
	cout<<(A+B)*H/2<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int main() {
    int n;
    cin >> n;
    int a[n], b[n], c[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(c, c + n);
    long long result = 0, count[n + 1];
    count[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        auto it = upper_bound(c, c + n, b[i]);
        count[i] = distance(it, c + n) + count[i + 1];
    }
    for (int i = 0; i < n; i++) {
        auto it = upper_bound(b, b + n, a[i]);
        result += count[distance(b, it)];
    }
    cout << result;
    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr int inf = 3e18;

int mod_pow(int x,int y,int m=mod){
	int res=1;
	while(y>0){
		if(y&1)(res*=x)%=m;
		(x*=x)%=m;
		y>>=1;
	}
	return res;
}
vector<int>perm,inv;
void init_perm(){
	int x=1e6+1;perm.resize(x);inv.resize(x);
	perm[0]=1;
	REP(i,x+1)perm[i]=perm[i-1]*i%mod;
	inv[x]=mod_pow(perm[x],mod-2);
	for(int i=x-1;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}
int nCk(int x,int y){
	if(x<y)return 0;
	return perm[x]*inv[x-y]%mod*inv[y]%mod;
}

int B,W;
int p,q;
signed main(){
	init_perm();
	cin>>B>>W;
	REP(i,B+W+1){
		(p+=nCk(i-2,W-1)*mod_pow(mod_pow(2,i-1),mod-2)%mod)%=mod;
		(q+=nCk(i-2,B-1)*mod_pow(mod_pow(2,i-1),mod-2)%mod)%=mod;
		cout<<(1+p-q+mod)%mod*inv[2]%mod<<endl;
	}
}


Measured memory_bytes: 17792
#include<cstdio>
int main()
{
	int n;
	scanf("%d",&n);
	int ans = n;
	int pos = 0;
	while(n--)
	{
		int t,a,b;
		scanf("%d%d%d",&t,&a,&b);
		if(a+b > t)
		continue;
		if((a+b-t)%2==0)
		pos++;
		else
		continue;
	}
	if(pos == ans)
	printf("Yes");
	else
	printf("No");
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

void trace(int A[], int N)
{
	int i;
	for(i=0; i<N; i++){
		if(i>0) printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
}


void insertionSort(int A[], int N)
{
	int i, j, v;
	
	for(i=1; i<N; i++){
		v = A[i];
		j = i-1;
		while(j>=0 && A[j]>v){
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = v;
		trace(A,N);
	}
}


int main(void)
{
	int N, i, j;
	int A[100];
	
	scanf("%d", &N);
	for(i=0; i<N; i++){
		scanf("%d", &A[i]);
	}
	
	trace(A, N);
	insertionSort(A,N);
	
	return 0;
}


Measured memory_bytes: 2036
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define N 55
using namespace std;

int n,m;
char mark[N][N];
int num[N];

int coun(int x,int y)
{
    int d=0;
    int dx,dy;
    for(int i=-1; i<=1; i++)
        for(int j=-1; j<=1; j++)
        {
            dx=x+i;
            dy=y+j;
            if(dx<0||dy<0)continue;
            if(dx>=n||dy>=m)continue;
            if(mark[dx][dy]=='#')
                d++;
        }
    return d;

}

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        scanf(" %s",mark[i]);
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            int x;
            if(mark[i][j]=='.')
            {
                x=coun(i,j);
                printf("%d",x);
            }
            else
                printf("#");
        }
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 256
def main():
    n=int(input())
    h=list(map(int,input().split()))

    inf = 10**18
    # min -> inf, max -> 0
    dp = [inf]*n

    # shoki joken
    dp[0] = 0
    for i in range(1,n):
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))

    print(dp[-1])

if __name__ == '__main__':
    main()


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

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) (x).begin(),(x).end()
#define int ll

#define pt pair<int, int>
#define x first
#define y second

ld dist(pt a, pt b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void solve() {
	int a, b;
	cin >> a >> b;
	cout << a * (a - 1) / 2 + b * (b - 1) / 2;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cout.precision(20);
	int t;
	//cin >> t;
	t = 1;
	while (t--)
		solve();
	return 0;
}

Measured memory_bytes: 256