akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
      cin>>n>>k;

     int count=0;
      for(int i=1;i<=n;i++)
      {
         int height;
           cin>>height;

             if(height >= k)
              count++;
      }
      cout<<count;
}


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

int main() {
	int n;
	long long a, l = 0, tab = 0;
	cin>>n;
	for(int i = 0; i < n; i++) {
		cin>>a;
		if(i > 0 && l > a) {
			tab += (l - a);
			a = l;
		}
		l = a;
	}
	cout<<tab<<"\n";
	return 0;
}

Measured memory_bytes: 3628
N, K = 0, -1
while (N < 1 or N > 2 * 10**5) and (K < 0 or K > 2 * 10**5):
  N, K = input().split()
  N, K = int(N), int(K)

flag = False
while flag == False:
  H = input().split()
  flag = (sum([((int(i) >= 1) and (int(i) <= 10**9)) for i in H]) == len(H))

H = [int(s) for s in H]
H.sort(reverse=True)
attack = []
for i,v in enumerate(H):
  if(i >= K):
    attack.append(v)
print(sum(attack))



Measured memory_bytes: 26180
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define out(v) cout<<v<<"\n"

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int V, E; cin >> V >> E;

  vector<vector<bool>> edge(V, vector<bool>(V, false));
  vector<int> in(V, 0);

  queue<int> no_incoming_edge;
  rep(i, E) {
    int s, t;
    cin >> s >> t;
    edge[s][t] = true;
    ++in[t];
  }
  rep(i, V) {
    if (in[i] == 0)
      no_incoming_edge.push(i);
  }
  vector<int> ans;
  while (!no_incoming_edge.empty()) {
    int p = no_incoming_edge.front(); no_incoming_edge.pop();
    ans.push_back(p);
    rep(to, V) {
      if (edge[p][to] == 1) {
        --in[to];
        if (in[to] == 0)
          no_incoming_edge.push(to);
      }
    }
  }
  rep(i, V)
    out(ans[i]);

  return 0;
}


Measured memory_bytes: 15804
#include <iostream>
#include <algorithm>
#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define output(x) cout << ( x ? "YES" : "NO" ) << '\n' ;
#define mxn 100005
using namespace std;
void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int e=a*c,f=a*d,g=b*c,h=b*d;
    e=max(e,f);
    g=max(g,h);
    h=max(e,g);
    cout<<h;
}

int32_t main()
{
    FLASH
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <math.h>

typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION std::cout << std::fixed << std::setprecision(20);
  
using namespace std;
 
const ll inf = 1e18;
const ll N = 1e5+1;
const ll mod = 1e9+7;


int main(){

    FASTIO;
    PRECISION;

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

    if(n%2){
        int a = 1, b = n-1;
        while(m){
            cout<<a<<" "<<b<<"\n";
            a++;
            b--;
            m--;
        }
    }else{
        int a = 1, b = n-1;
        int done = false;
        while(m--){
            if(!done && b-a<=n/2){
                b--;
                done = true;
            }
            cout<<a<<" "<<b<<"\n";
            b--;
            a++;
        }
    }

}


Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFTY 1<<21
#define N 1001
int head=1;
int tail=1;
int n;
int d[N];
int M[N][N];
int color[N];
int Q[N];
void dfs(int);
void enqueue(int);

int main(){
  int i,j,v,k,c,u;

  scanf("%d",&n);
  
  for(i=0;i<N;i++){
    Q[i] = -1;
    for(j=0; j<N; j++){
      M[i][j] = INFTY;
    }
  }
  
  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      M[u][v] = 1;
    }
  }
  // printf("debug\n");
  dfs(0);

  return 0;
}

void dfs(int s){
  int i,u,v;
  for(i=0; i<n; i++){
    d[i] = INFTY;
    color[i] = WHITE;
  }
  d[s] = 0;
  color[s] = GRAY;
  enqueue(s);

  while(1){
   
 
    if( tail == head) break;
       u = dequeue();
    for(v = 0; v <n; v++){
      if(M[u][v] != INFTY && color[v] != BLACK &&d[v]==INFTY){
	color[v] = GRAY;
	d[v] = d[u] + 1;
	enqueue(v);
	}
    }
    color[u] = BLACK;

  }
  
  for(i = 0; i<n; i++){
    printf("%d %d\n",i+1,((d[i]==INFTY) ? (-1) : d[i]));
  }
}

void enqueue(int s){
  Q[tail++] = s;
}
int dequeue(){
  int r = Q[head++];
  return r;
}



Measured memory_bytes: 5788
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    const vector<string> v = {
        "dreamer", "dream", "eraser", "erase"
    };

    string s;
    cin >> s;
    int n = s.size();

    vector<bool> dp(n+1, false);
    dp[0] = true;
    for(int i=0; i<n; ++i){
        if(!dp[i])
            continue;
        for(int j=0; j<4; ++j){
            if(v[j] == s.substr(i, v[j].size()))
                dp[i+v[j].size()] = true;
        }
    }

    if(dp[n])
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  int c = a*b%2;
  if (c == 0){
    cout << "Even" << endl;
    }
  else {
    cout << "Odd" << endl;
  } 
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char s[3];
  int sum;
  cin >> s;
  for (int i = 0; i < 3; i++) {
    if(s[i] == '1'){
      sum += 1;
    }
  }
  cout << sum << endl;
}

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

int main () {
  string S, T;
  cin>>S>>T;
  
  int ans=0;
  int len=S.size();
  for (int i=0; i<len; i++){
    if(S[i]!=T[i]){
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3868
#include <iostream>
#include <string>
#include <cmath>

using namespace std;
int a[15];
int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    int sum=1;
    for(int i=0; i<n; i++)
        if(a[i]%2==0)
            sum*=2;
    cout << pow(3,n)-sum << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
		ArrayList<Integer> array = new ArrayList<Integer>();
		for(int i=0;i<n;i++){
			int a = sc.nextInt();
			Integer po = hash.get(a);
			if(po == null){
				po = 0;
			}
			hash.put(a, po+1);
		}
		for(Integer key:hash.keySet()){
			array.add(hash.get(key));
		}
		Collections.sort(array);
		int z = array.size() - k;
		int ans = 0;
		for(int i=0;i<z;i++){
			ans = ans + array.get(i);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 99456
#include <bits/stdc++.h>
using namespace std;
int n;
int a[50];
bool solve(int i, int key)
{
    if (key == 0)
        return true;
    else if (i >= n)
        return false;
    int res = solve(i + 1, key) || solve(i + 1, key - a[i]);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int q;
    cin >> q;
    int m[q];
    for (int i = 0; i < q; ++i)
        cin >> m[i];
    for (int i = 0; i < q; ++i)
    {
        if (solve(0, m[i]))
            cout << "yes" << endl;
        else
        {
            cout << "no" << endl;
        }
    }
}


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

int main() {
	int N;
	cin >> N;
	string s;
	cin >> s;
	int i;
	int R = 0;
	int B = 0;
	for (i = 0; i < N; i++) {
		if (s.at(i) == 'R') {
			R++;
		}
		else {
			B++;
		}
	}
	if (R > B) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
}

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


signed main() {
  int N;
  cin >> N;
  map<string, int> mp;
  int count = 0;
  for(int i=0; i<N; i++) {
    string s;
    cin >> s;
    mp[s]++;
    count = max(count , mp[s]);
  }

  vector<string> v;
  for(auto& s : mp) if(s.second==count) v.push_back(s.first);
  sort(v.begin(), v.end());

  for(auto &s : v) cout << s << endl;
}


Measured memory_bytes: 26868
from itertools import product
n, *XYH = map(int, open(0).read().split())
for cx, cy in product(range(101), repeat=2):
    B, C = set(), set()
    for x, y, h in zip(XYH[::3], XYH[1::3], XYH[2::3]):
        s = h + abs(x-cx) + abs(y-cy)
        if h:
            C.add(s)
        else:
            B.add(s)
    if len(C) == 1:
        h = C.pop()
        if all(h <= b for b in B):
            print(cx, cy, h)
            exit()

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>

using namespace std;
typedef long long ll;

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

int main() {

    ll N;
    cin >> N;
    ll btc = 380000;
    double out = 0;
    double x = 0;
    string u = "";
    rep(i,N){
        cin >> x >> u;
        if(u=="JPY") out += x;
        else out += x*btc;
    }
    cout << fixed << setprecision(6) << out << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<deque>

using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;


int solve(vvi& v)
{
	int n=v.size()-1;
	vi f(n+1, 0);
	vi s(2);
	deque<pair<int,int>> q;

	f[1]='F';
	q.push_back(make_pair(1, 0));

	f[n]='S';
	q.push_back(make_pair(n, 1));

	s[0]=s[1]=1;
	while(!q.empty())
	{
		int c=q.front().first;
		int p=q.front().second;
		q.pop_front();

		for(auto ve:v[c])
		{
			if(f[ve]) continue;
			f[ve]=1;
			s[p]++;
			q.push_back(make_pair(ve, p));
		}
	}
//printf("%d %d\n", s[0], s[1]);
	return s[0]>s[1];
}


int main(void)
{
	int n;

	while(scanf("%d", &n)==1)
	{
		vvi v(n+1);

		for(int i=0;i<n-1;i++)
		{
			int a, b;

			scanf("%d%d", &a, &b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		printf("%s\n", solve(v)?"Fennec":"Snuke");
	}

	return 0;
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#pragma 03
using namespace std;
using namespace __gnu_pbds;
// chctxdy
ll a[3][3];
bool mark[3][3];
int main(){
	fastio;
	for (ll i = 0; i<3; i++) for (ll j = 0; j<3; j++) cin >> a[i][j];
	ll n; cin >> n;
	for (ll i = 0; i<n; i++){
		ll ip; cin >> ip;
		for (ll j = 0; j<3; j++){
			for (ll k = 0; k<3; k++){
				if (a[j][k] == ip) mark[j][k] = true;
			}
		}
	}
	for (ll x1 = 0; x1<3; x1++){
		for (ll y1 = 0; y1<3; y1++){
			for (ll x2 = 0; x2<3; x2++){
				for (ll y2 = 0; y2<3; y2++){
					if (x1 == x2 && y1 == y2) continue;
					if ((x1 + x2) % 2 || (y1 + y2) % 2) continue;
					ll x3 = (x1 + x2) / 2, y3 = (y1 + y2) / 2;
					if (mark[x1][y1] && mark[x2][y2] && mark[x3][y3]){
						cout << "Yes\n"; return 0;
					}
				}
			}
		}
	}
	cout << "No\n";
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

const int N_MAX=144,T_MAX=6;
int Dreyfus_Wagner(int n,int d[N_MAX][N_MAX],int nt,int *t){
	rep(k,n) rep(i,n) rep(j,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

	static int dp[1<<T_MAX][N_MAX];
	rep(S,1<<T_MAX) rep(i,n) dp[S][i]=INF;
	rep(i,nt) rep(j,n) dp[1<<i][j]=d[t[i]][j];

	rep(S,1<<nt) if(S && S&S-1) { // |S|>=2
		rep(T,S+1) if((S|T)==S) rep(p,n) {
			rep(q,n) dp[S][p]=min(dp[S][p],d[p][q]+dp[T][q]+dp[S&~T][q]);
		}
	}

	return dp[(1<<nt)-1][t[0]];
}

int main(){
	for(int h,w;scanf("%d%d",&h,&w),h;){
		int d[N_MAX][N_MAX];
		rep(i,h) rep(j,w) rep(y,h) rep(x,w) d[i*w+j][y*w+x]=(i==y&&j==x?0:INF);

		int n=0,heart[6];
		rep(i,h) rep(j,w) {
			int choco; scanf("%d",&choco);
			if(choco) heart[n++]=i*w+j;
			rep(k,4){
				int y=i+dy[k],x=j+dx[k];
				if(0<=y && y<h && 0<=x && x<w) d[i*w+j][y*w+x]=1;
			}
		}

		printf("%d\n",h*w-Dreyfus_Wagner(h*w,d,n,heart)-1);
	}

	return 0;
}

Measured memory_bytes: 884
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
int n,x,y;
vector<int> a[MAXN],b[MAXN];
pair<int,int> l[MAXN];
int depA[MAXN],depB[MAXN];
int fa[MAXN][21];
void dfsA(int x,int f){
	depA[x]=depA[f]+1;
	for(int i=0;i<a[x].size();i++){
		int u=a[x][i];
		if(u==f)
			continue;
		dfsA(u,x);	
	}
}
void dfsB(int x,int f){
	depB[x]=depB[f]+1;
	fa[x][0]=f;
	for(int i=1;i<20;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=0;i<b[x].size();i++){
		int u=b[x][i];
		if(u==f)
			continue;
		dfsB(u,x);
	}
}
int lca(int u,int v){
	if(depB[u]<depB[v])
		swap(u,v);
	for(int i=19;i>=0;i--)
		if(depB[fa[u][i]]>=depB[v])
			u=fa[u][i];
	if(u==v)
		return u;
	for(int i=19;i>=0;i--)
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];	
		}
	return fa[u][0];
}
int ans;
void dfs(int x,int f){
	if(depA[x]>=depB[x])
		return ;
	if(ans!=-1)
		ans=max(ans,(depB[x]-1)*2);
	for(int i=0;i<a[x].size();i++){
		int u=a[x][i];
		if(u==f)
			continue;
		if(depB[u]+depB[x]-2*depB[lca(u,x)]>2)
			ans=-1;	
		dfs(u,x);	
	}
}
int main(){
	while(SF("%d%d%d",&n,&x,&y)!=EOF){
		int u,v;
		for(int i=1;i<n;i++){
			SF("%d%d",&u,&v);
			l[i]=make_pair(u,v);
			a[u].push_back(v);
			a[v].push_back(u);
		}
		for(int i=1;i<n;i++){
			SF("%d%d",&u,&v);
			b[u].push_back(v);
			b[v].push_back(u);	
		}
		dfsA(x,0);
		dfsB(y,0);
		ans=0;
		dfs(x,0);
		PF("%d\n",ans);
		for(int i=1;i<=n;i++){
			a[i].clear();
			b[i].clear();
		}
	}
}

Measured memory_bytes: 50300
#!/usr/bin/env python3
 
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


Measured memory_bytes: 3976
package main

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

type Tuple struct {
	A     string
	B     int
	index int
}

func main() {
	sc := NewScanner()
	N := sc.NextInt()

	data := make(SortInterFace, N)
	for i := 0; i < N; i++ {
		A, B := sc.Next(), sc.NextInt()
		data[i] = Tuple{A, B, i}
	}

	sort.Sort(data)
	for _, v := range data {
		fmt.Println(v.index + 1)
	}

}

type SortInterFace []Tuple

func (s SortInterFace) Len() int {
	return len(s)
}
func (s SortInterFace) Less(i, j int) bool {
	if s[i].A == s[j].A {
		return s[i].B > s[j].B
	}
	return s[i].A < s[j].A
}
func (s SortInterFace) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextFloat() float64 {
	v, _ := strconv.ParseFloat(s.Next(), 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
bool LTE(double a,double b) { return equals(a,b) || a < b; }
bool LT(double a,double b) { return !equals(a,b) && a < b; }

#define MAX 1010
int H,W,A[MAX],B[MAX];
const ll mod = 1000000007LL;

int bf() {
  vector<int> vec(H*W);
  rep(i,H) rep(j,W) vec[i+j*W] = i + j * W + 1;
  sort(ALL(vec));
  int cnt = 0;
  do {
    vector<int> a(H,-1), b(W,-1);
    rep(i,H) {
      rep(j,W) {
	a[i] = max(a[i],vec[i+j*W]);
	b[j] = max(b[j],vec[i+j*W]);
      }
    }
    bool ok = true;
    rep(i,H) if( a[i] != A[i] ) ok = false;
    rep(i,W) if( b[i] != B[i] ) ok = false;
    if( ok ) ++cnt;
  } while( next_permutation(ALL(vec)) );
  return cnt;
}

void compute() {
  ll ans = 1;
  map<int,int> mp_x, mp_y;
  rep(i,H) mp_y[A[i]] = i;
  rep(i,W) mp_x[B[i]] = i;
  set<int> put_x, put_y;
  for(int v=H*W;v>=1;--v) {
    bool exist_x = mp_x.count(v);
    bool exist_y = mp_y.count(v);
    if( exist_x && exist_y ) {
      put_x.insert(mp_x[v]);
      put_y.insert(mp_y[v]);
      
    } else if( exist_x ) {
      if( put_y.size() == 0 ) {
	puts("0");
	return;
      }
      ( ans *= (ll)put_y.size() ) %= mod;
      put_x.insert(mp_x[v]);
      
    } else if( exist_y ) {
      if( put_x.size() == 0 ) {
	puts("0");
	return;
      }
      ( ans *= (ll)put_x.size() ) %= mod;
      put_y.insert(mp_y[v]);
      
    } else {
      ll score = (ll)put_x.size() * (ll)put_y.size();
      score -= ( H * W - v );
      ans = ans * score;
      ans %= mod;
    }
  }
  cout << ans << endl;
  //cout << "ANS : " << bf() << endl;
}

int main() {
  cin >> H >> W;
  rep(i,H) cin >> A[i];
  rep(i,W) cin >> B[i];
  compute();
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
#include <vector>
#include <map>
#include <iterator>
#include <iterator>
#include <string>
#define pan(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define vi vector<int>
#define pb push_back
using namespace std;
 
 
 
int main() {
    string s;
    cin>>s;
    int n=s.size();
    pan(i,n) s[i]='x';
    cout<<s;
}

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

int main(){
    double r, ans;
    cin >> r;
    ans = r * 2.0 * 3.1415;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3752
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
#include <stdio.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

void dfs(vector<vector<int>>& g, unordered_set<int>& visited, int v)
{
    visited.insert(v);
    for(auto& next_v:g[v])
    {
        if(visited.count(next_v) > 0) continue;
        dfs(g, visited, next_v);
    }
}

int main()
{    
    int n,m;
    cin >> n >> m;
    vector<int> p(n);
    rep(i,n) cin >> p[i];

    vector<vector<int>> g(n);
    rep(i,m)
    {
        int x,y;
        cin >> x >> y;
        g[x-1].push_back(y-1);
        g[y-1].push_back(x-1);
    } 

    unordered_set<int> visited;    
    int cnt = 0;
    rep(i,n)
    {
        if(g[i].empty() && p[i]==i+1)
        {
            ++cnt;
            continue;
        }        
        else if(visited.count(i) > 0) 
            continue;
        
        unordered_set<int> tmp_vis;
        dfs(g,tmp_vis,i);
        for(auto& tv:tmp_vis)
        {
            if(tmp_vis.count(p[tv]-1) > 0) cnt++;
            visited.insert(tv);
        }
    }

    cout << cnt << endl;
    return 0;
}

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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    ll Q, H, S, D, N;
    cin >> Q >> H >> S >> D >> N;

    ll mins = std::min(S, std::min(2 * H, 4 * Q));
    ll mind = std::min(mins * 2, D);
    cout << (N / 2) * mind + (N % 2) * mins << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
using ll=long long;

int main(){
    ll n,m,k,x,y;
    cin>>n>>m>>k;
    vector<ll> a(n+1),b(m+1);
    for(int i=1;i<n+1;i++){
        cin>>x;
        a[i]=a[i-1]+x;
    }
    for(int i=1;i<m+1;i++){
        cin>>y;
        b[i]=b[i-1]+y;
    }

    int ans=0;
    int j=m;
    for(int i=0;i<n+1;i++){
        if(k<a[i]){
            break;
        }
        ll rest=k-a[i];
        while(rest<b[j]){
            j--;
        }
        ans=max(ans,i+j);
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 6412
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    const int mod = 1e9+7;
    vector<int> v(26,1);
    rep(i,n) v[s[i]-'a']++;
    ll ans = 1;
    rep(i,26) {
        ans *= v[i];
        ans %= mod;
    }
    cout << ans-1 << endl;
}


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

typedef vector<ll>vec;
typedef vector<vec>mat;

ll L,A,B,MOD;

mat mul(mat&a, mat&b) {
	mat c(a.size(), vec(b[0].size()));
	rep(i, a.size())rep(j, b[0].size())rep(k, b.size())
		(c[i][j] += a[i][k] * b[k][j]) %= MOD;
	return c;
}
mat ppow(mat&a, ll b) {
	mat res(a.size(), vec(a.size()));
	rep(i, a.size())res[i][i] = 1;
	while (b) {
		if (b & 1)res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

ll ppow(ll a,ll b){
	a%=MOD;
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

ll lb(ll x){
	ll ok=L,ng=-1;
	while(ok-ng>1){
		ll t=(ok+ng)/2;
		if(A+B*t>=x)ok=t;
		else ng=t;
	}
	return ok;
}

int main(){
	cin>>L>>A>>B>>MOD;
	ll d=1;
	ll ans=0;
	for(ll i=1;i<=18;i++){
		ll l=lb(d),r=lb(d*10);
		(ans*=ppow(d*10,(r-l)))%=MOD;
		ll s=(A+B%MOD*l)%MOD;
		mat M1{{d*10%MOD,1,0},{0,1,1},{0,0,1}};
		mat M2{{0},{s},{B%MOD}};
		mat res=ppow(M1,r-l);
		M2=mul(res,M2);
		(ans+=M2[0][0])%=MOD;
		d*=10;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3652
def InputData():
    
    sequence_len = int(input())
    sequence = list(map(int, input().split(" ")))

    return sequence_len, sequence

def partition(sequence, p, r):
    x = sequence[r]
    i = p - 1
    # sequence[j]
    for j in range(p, r):
        if sequence[j] <= x:
            # print(sequence[j])
            i += 1
            sequence[i], sequence[j]= sequence[j], sequence[i]
    
    sequence[i+1], sequence[r] = sequence[r], sequence[i+1]
    return i+1

def PrintOut(sequence):
    print(' '.join( map(str, sequence)))

def main():
    [sequence_len, sequence] = InputData()
    q = partition(sequence, 0, sequence_len-1)
    sequence[q] = "[" + str(sequence[q]) + "]"
    PrintOut(sequence)

if __name__=="__main__":
    main()


Measured memory_bytes: 16392
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) int ab;cin>>ab;(p).push_back(ab);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main() {
	

	int N;
	vecl(A)
	pb(A,0)
	map<ll,ll> S;
  cin>>N;
	fx(N){
		ll a;
		cin>>a;
		pb(A,a+A.at(x))
		S[A.at(x+1)]++;
	}
	ll ans=S[0];
	fyg(N+1,1){

		ans+=S[A.at(y)]*(S[A.at(y)]-1)/2;
		S[A.at(y)]=0;
	}
	ce(ans)
}

Measured memory_bytes: 16368
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int64;

int main() {
  int64 n, a, b;
  cin >> n >> a >> b;

  if (a > b) {
    cout << 0 << endl;
  } else if (n == 1 && a < b) {
    cout << 0 << endl;
  } else {
    cout << b * (n-1) + a - (a * (n-1) + b) + 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define MOD 1000000007

template< typename T >
size_t longest_increasing_subsequence(const vector< T > &a, bool strict) {
  vector< T > lis;
  for(auto &p : a) {
    typename vector< T >::iterator it;
    if(strict) it = lower_bound(begin(lis), end(lis), p);
    else it = upper_bound(begin(lis), end(lis), p);
    if(end(lis) == it) lis.emplace_back(p);
    else *it = p;
  }
  return lis.size();
}

void solve()
{
  int N;
  cin>>N;
  vector<int> vec(N,0);
  for (int i = 0; i < N; i++)
  {
    cin>>vec[i];
  }

  reverse(vec.begin(),vec.end());
  cout<<longest_increasing_subsequence(vec,0)<<endl;
  return;  
}

int32_t main(int32_t argc, const char *argv[])
{
  // std::ios::sync_with_stdio(false);
  // std::cin.tie(0);

  // std::cout << std::fixed;
  // std::cout << std::setprecision(8);

  solve();

 
  return 0;
}

Measured memory_bytes: 2168
import numpy as np

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

## pesmistic input (8916 ms)
#N = 100000
#K = 10000
#S = '10'*50000

## make 'next_lst'
## S='1100010000' --> next_lst=[2,3,1,4,1]
next_lst = []
pre_state = S[0]
cnt = 1
for i in range(1,len(S)):
  if S[i] == pre_state:
    cnt += 1
  else:
    next_lst.append(cnt)
    pre_state = S[i]
    cnt = 1
else:
  next_lst.append(cnt)
if S[0] == '0':
  next_lst = [0] + next_lst
if S[-1] == '0':
  next_lst = next_lst + [0]


if len(next_lst) <= 2*K+1:
  ans = sum(next_lst)
  print(ans)
  exit()

## 配列の区間和はcumsumで累積和を取ってその差分を取るほうが速い
ans = 0
lst = np.cumsum(np.array([0]+next_lst))
for i in range((len(next_lst)-2*K+1)//2):
  var = lst[2*i+2*K+1] - lst[2*i]
  ans = max(ans, var)

print(ans)


Measured memory_bytes: 15064
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>

#define llint long long

using namespace std;

llint n, k;
llint a[200005], f[200005];

bool check(llint x)
{
	llint sum = 0;
	for(int i = 1; i <= n; i++){
		llint need = x / f[i];
		sum += max(a[i] - need, 0LL);
	}
	return sum <= k;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> f[i];
	sort(a+1, a+n+1);
	reverse(a+1, a+n+1);
	sort(f+1, f+n+1);
	
	llint ub = 1e18+5, lb = -1, mid;
	while(ub-lb>1){
		mid = (ub+lb)/2;
		if(check(mid)) ub = mid;
		else lb = mid;
	}
	cout << ub << endl;
	
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define LLI long long int
using namespace std;

int w[100007];
int v[100007];
LLI dp[100007] = {};

int main() {
	
	int i,j;
	int N,W;
	
	cin >> N >> W;
	for( i=1; i<=N; i++) {
		cin >> w[i] >> v[i];
	}
	for( i=1; i<=N; i++) {
		for( j=W; j >= w[i]; j--) {
			dp[j] = max( dp[j], dp[j - w[i] ] + v[i]);
		}
	}
	cout << dp[W] << "\n";
	
	return 0;
}

Measured memory_bytes: 4380
class PriorityQueue
 
  def initialize(&compare)
    @items = []
    if block_given?
      @compare_proc = compare
    else
      @compare_proc = Proc.new { |a, b| a > b }
    end
  end
  
  def push(x)
    n = @items.size
    @items << x
    while n != 0
      p = (n - 1) / 2
      if @compare_proc.call(@items[n], @items[p])
        @items[p], @items[n] = @items[n], @items[p]
      end
      n = p
    end
  end
  
  def pop
    result = @items[0]
    @items[0] = @items[-1]
    @items.delete_at(-1)
 
    n = 0
    loop do
      left = 2 * n + 1
      break if left >= @items.size
 
      right = left + 1
      if (right < @items.size) && @compare_proc.call(@items[right], @items[left])
        c = right
      else
        c = left
      end
 
      break unless @compare_proc.call(@items[c], @items[n])
 
      @items[n], @items[c] = @items[c], @items[n]
      n = c
    end
    result
  end
 
  def empty?
    @items.empty?
  end
  
  def size
    @items.size
  end

  def sum
    @items.inject(:+)
  end
end
 
n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort.reverse
 
ans = 0
if n == 1
  ans = a[0] / 2 ** m
else
  queue = PriorityQueue.new
  a.each do |x|
    queue.push x
  end
  while m > 0
    x = queue.pop
    queue.push x / 2
    m -= 1
  end
  ans = queue.sum
end
 
puts ans
 


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

int a, p, ans;

int main() {
  cin >> a >> p;
  ans = (3*a + p) / 2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
        int N, M, i;
        int sumN, sumM;

        N = 0;
        M = 0;
        sumN = 1;
        sumM = 1;

        scanf("%d%d", &N, &M);

        for(i = 0; i < 2; i++)
        {
                sumN *= (N - i);
        }
        for(i = 0; i < 2; i++)
        {
                sumM *= (M - i);
        }

        printf("%d", sumN / 2 + sumM / 2);

        return 0;
}


Measured memory_bytes: 128
# 真ん中を通れば必ず二分できてこれが最大値だが、自分自身が真ん中の座標の場合は自分自信を通るどんな直線も二分できる
w, h, x, y = map(int, input().split())
ans1 = (w * h) / 2.0
ans2 = 1 if w / 2 == x and h / 2 == y else 0
print(ans1, ans2)


Measured memory_bytes: 38512
s=input()
acgt=["A","C","G","T"]
res=0
for i in range(len(s)):
    for j in range(i,len(s)):
        t=s[i:j+1]
        tmp=False
        for j in t:
            if not j in acgt:
                tmp=True
                break
        if tmp:
            continue
        res=max(res,len(t))
print(res)

Measured memory_bytes: 9028
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define repitr(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int w, h, n;
	cin >> w >> h >> n;
	int l, r, u, d;
	l = d = 0;
	r = w;
	u = h;
	bool flag = false;
	rep(i, n){
		int x, y, a;
		cin >> x >> y >> a;
		if(a == 1){
			l = max(l, x);
		}else if(a == 2){
			r = min(r, x);
		}else if(a == 3){
			d = max(d, y);
		}else if(a == 4){
			u = min(u, y);
		}
		if(l >= r || d >= u) flag = true;
		//cerr << l << " " << r << " " << d << " " << u << endl;
	}
	if(flag) cout << 0 << endl;
	else cout << (r-l)*(u-d) << endl;
	return 0;
}

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

int main(){
    int N,A,min,max,ans;
    cin >> N >> A;
    min = A;
    max = A;
    for(int i = 0;i < N;i++){
        cin >> A;
        if(min > A){
            min = A;
        }
        if(max < A){
            max = A;
        }
        
    }
    ans = max - min;
    cout << ans << endl;
}

Measured memory_bytes: 384
long B[3<<17],a,r,H,I;n,h[2<<17],i,j;main(n){for(scanf("%d",&n);i<n;)scanf("%d",h+i++);for(;~scanf("%d",&a);r=0){for(I=H=h[j++];H;H-=H&-H)r=fmax(r,B[H]);for(;I<3<<17;I+=I&-I)B[I]=fmax(B[I],a+r);}printf("%ld",B[2<<17]);}

Measured memory_bytes: 3840
//shara's here
//私は私は大きい男の子
//SPEEEEEEEEEED IS KEEEEEEEEEEY
//REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEAAAAAAAAAAAAAAAAAAAADDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
#include <bits/stdc++.h>
using namespace std;
typedef string s;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18 + 10;
const ll MINF = -(1e18 + 10);
#if defined(BANYANYA)
#include "/home/xsharawi/Desktop/cpp/debug.hpp"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define pb push_back
#define ins insert
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int main(){
	ll a , b , k;
	cin >> a >> b >> k;	
	if( a == b ){ cout << a << endl; return 0;}
	ll t1 = k , t2 = k; 
	set<ll>ss;
	for(ll i = a; t1-- ; i++ ){
	if( i >= b )break;
	ss.insert(i);
	}
	for(ll i = b; t2-- ; i-- ){
	if( i <= a )break;
	ss.insert(i);
	}
	for( auto &x : ss )cout << x << endl; 
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	





return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

//a^b % MOD
long long mod_pow(ll a,ll b){
	long long ret = 1;
	long long c = a;
	for(int i = 0;i <= 60;i++){
		if(b & (1LL << i))ret = (ret * c) % MOD;
		c = (c * c) % MOD;
	}
	return ret;
}

//ａをbで割る
long long mod_div(long long a,long long b){
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}

#define MAX_K 333333
vector<long long> kaijo(MAX_K);
long long combination(long long n, long long r){
    if(n < r || n < 0 || r < 0)
        return 0;
	if(kaijo[0] != 1){
		kaijo[0] = 1;
		for(long long i = 1;i < MAX_K;i++)kaijo[i] = (kaijo[i-1] * i) % MOD;
	}
    long long ret = kaijo[n];
	long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
    return mod_div(ret,tmp);
}


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

	ll n, a, b, c;cin >> n >> a >> b >> c;
	ll abb = mod_div(a, a + b);
	ll bab = mod_div(b, a + b);
	ll yc = mod_div(100, 100 - c);

	ll ans = 0;
	for(ll i = n;i < 2 * n;i++){
		ll A = mod_pow(abb, n) * mod_pow(bab, i - n) % MOD;
		ll B = mod_pow(abb, i - n) * mod_pow(bab, n) % MOD;
		ll C = i * yc % MOD;
		ll tmp = ((A + B) % MOD) * C % MOD;
		ans = (ans + combination(i - 1, n - 1) * tmp % MOD) % MOD;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long ll;
int n,a[N];
int zh(int a){
	return a<0?-a:a;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(a[1]>0) return puts("-1"),0;
	ll ans=a[n];
	for(int i=2;i<=n;i++) if(a[i-1]+1<a[i]) return puts("-1"),0;
	for(int i=n-1;i;i--){
		if(a[i]==a[i+1]-1) continue;
		ans+=a[i];
	}
	printf("%lld",ans);
	return 0;
}

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

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

using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;


#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;



int main() {
  ll n;
  	ci(n);
  vll A(n);
  vll B(n);
  vll C(n);
  
  FOR(i,0,n){
    ci(A[i])
    if(1<=i){
      A[i]+=A[i-1];
    }
  }
  
  FOR(i,0,n){
    ci(B[i])
    if(1<=i){
      B[i]+=B[i-1];
    }
  }
  
  C[0]=A[0]+B[n-1];
  FOR(i,1,n){
	C[i]=A[i]+B[n-1]-B[i-1];
  }
  SORT(C);
  co(C[n-1])
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <atcoder/scc>
using namespace std;
//using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pull = pair<ull, ll>;
using pis = pair<int, string>;
#define all(x) (x).begin(), (x).end()
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007ll

struct SegmentTree {
  //10^6要素まで対応
  vector<ll> d;
  int size = 1;
  SegmentTree(): d(1<<21, 0) {} //addなので0初期化

  //functions
  //OPERATION: ADD
  //init
  void init_SegmemtTree(vector<ll>&original) {
    int n = original.size();
    while (size < n) size *= 2;
    if (size > (1<<20)) cout << "Too Many Elements" << endl; //error
    for (int i = 0; i < n; i++) d[size+i] = original[i];
    for (int i = size-1; i > 0; i--) d[i] = d[2*i] + d[2*i+1]; //add
  }

  void init_SegmentTree_size(int n) {
    while (size < n) size *= 2;
    return;
  }

  //update: k番目をaに
  void update(int k, ll a) {
    k += size;
    ll temp = 0;
    while(k > 0) {
      d[k] = max(d[k], a);
      k /= 2;
    }
  }

  //query: [a, b)の区間のmax
  ll query(int a, int b, int k=1, int l=0, int r=-1) {
    if (r == -1) r = size;
    //範囲がまったく重ならないとき(add)
    if ((r <= a) || (b <= l)) return 0;
    //範囲に含まれるとき
    if ((a <= l) && (r <= b)) return d[k];
    //一部重なるとき(add)
    else return max(query(a, b, 2*k, l, (l+r)/2), query(a, b, 2*k+1, (l+r)/2, r));
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(15)
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  SegmentTree st;
  st.init_SegmentTree_size(300001);
  for (int i = 0; i < n; i++) {
    st.update(a[i], st.query(a[i]-k, a[i]+k+1) + 1);
  }

  ll ans = 0;
  for (int i = 0; i < 300001; i++) {
    ans = max(ans, st.d[i + st.size]);
    //if (i < 10) cout << st.d[i + st.size] << endl;
  }
  cout << ans << endl;
  
}


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

// 2つの整数の場合
long long GetLeastCommonMultiple(long long a, long long b)
{
	long long m = a;
	long long n = b;
	long long temp;

	while (m % n != 0) {
		temp = n;
		n = m % n;
		m = temp;
	}
	return a / n * b;
}

ll GetCnt(ll x, ll y) {
	return x / y;	
}

int main() {	

	ll a, b, c, d; cin >> a >> b >> c >> d;

	ll cd = GetLeastCommonMultiple(c, d);
	
	ll f_b = b;
	f_b -= GetCnt(b, c);
	f_b -= GetCnt(b, d);
	f_b += GetCnt(b, cd);

	ll f_a_1 = a - 1;
	f_a_1 -= GetCnt(a - 1, c);
	f_a_1 -= GetCnt(a - 1, d);
	f_a_1 += GetCnt(a - 1, cd);

	cout << f_b - f_a_1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a); i>=(b);i--) 

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

int n,a[maxn];
vector<int>cnt;
map<int,int>mp;

int main()
{
   ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
   cin >> n;
   //int tot = 0;
  // memset(cnt,-1,sizeof(cnt));
   rep(i,1,n) {
        cin >> a[i];
        if(!mp[a[i]])cnt.push_back(a[i]);
        mp[a[i]]++; 
   }
   sort(cnt.begin(),cnt.end());
   if(n % 3){
        if(mp[0] == n) cout << "Yes";
        else cout << "No";
   }
   else {
        int tot = cnt.size();
        int flag = 0;
        if(tot == 1 && mp[0] == n) flag = 1;
        if(tot == 2 && mp[0] == n / 3 && mp[cnt[1]] == n / 3 * 2) flag = 1;
        if(tot == 3 && (cnt[0]^cnt[1]^cnt[2]) == 0 && mp[cnt[0]] == mp[cnt[1]] && mp[cnt[1]] == mp[cnt[2]]) flag = 1;
        if(flag) cout << "Yes";
        else cout << "No";
   }

   return 0;
}

Measured memory_bytes: 4472
#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

vector<vector<pair<int,int>>>edges;

int memo[17][1 << 16];
struct aa {
	int now;
	bitset<17>eats;
	int time;
};
class Compare {
public:
	//aaが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};


int main() {
	while (1) {
		for (int i = 0; i < 17; ++i) {
			for (int j = 0; j < (1 << 16); ++j) {
				memo[i][j] =99999999;
			}
		}
		int N, M, L, S, T; cin >> N >> M >> L >> S >> T;
		if (!N)break;
		S--;
		edges.clear();
		edges.resize(L+1);
		int diss[300][300];
		for (int i = 0; i < N; ++i) {
			
			for (int j = 0; j< N; ++j) {

				diss[i][j] = i==j?0:99999999;

			}
			
		}
		for (int i = 0; i < M; ++i) {
			int a, b, c; cin >> a >> b >> c;
			a--; b--;
			diss[a][b] = c;
			diss[b][a] = c;
		}

		for (int i = 0; i < N; ++i) {
			for (size_t j = 0; j < N; j++)
			{
				for (size_t k = 0; k < N; k++)
				{
					diss[j][k] = min(diss[j][k],diss[j][i] + diss[i][k]);
				}
			}
		}
		vector<pair<int, int>>ramens;
		ramens.push_back(make_pair(S, 0));
		for (int i = 0; i < L; ++i) {
			int j, e; cin >> j >> e;
			j--;
			ramens.push_back(make_pair(j,e));
		}
		for (int i = 0; i < L+1; ++i) {
			for (int j = 0; j< L + 1; ++j) {
				if (i != j) {
					edges[i].push_back(make_pair(j, diss[ramens[i].first][ramens[j].first]));
				}
			}
		}

		priority_queue<aa, vector<aa>, Compare>que;
		que.push(aa{ 0,bitset<17>(1),0 });


		memo[0][0] = 0;
		int ans = 0;
		while (!que.empty()) {
			aa atop(que.top());
			que.pop();
			bitset<17>nbs(atop.eats);
			if (atop.now == 0) {
				ans = max(ans, int(nbs.count()));
				if (ans == L + 1)break;
			}

			for (auto j : edges[atop.now]) {
				const int nextplace = j.first;		
				const int nexttime = atop.time + j.second;
				if (nexttime < memo[nextplace][nbs.to_ulong()/2] && nexttime <= T) {
					if (nextplace == 0) {

						memo[nextplace][nbs.to_ulong() / 2] = nexttime;
						que.push(aa{ nextplace,nbs,nexttime });
					}

					if (!nbs[nextplace]) {
						nbs[nextplace] = true;
						int alltime = nexttime + ramens[nextplace].second;
						if (alltime < memo[nextplace][nbs.to_ulong() / 2] && alltime <= T) {
							memo[nextplace][nbs.to_ulong() / 2] = alltime;
							que.push(aa{ nextplace,nbs, alltime });
						}
						nbs[nextplace] = false;
					}
				}
			}
		}
		cout << ans-1 << endl;
	}
	return 0;
}

Measured memory_bytes: 28808
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

bool check(vector<int> s, vector<int> freq_s);

int main()
{
	int n;
	
	while (scanf("%d", &n), n != 0){
		vector<int> s, freq_s;
		map<int, int> freq;
		
		for (int i = 0; i < n; i++){
			int t;
			scanf("%d", &t);
			s.push_back(t);
		}
		int cnt;
		for (cnt = 0; ; cnt++){
			freq.clear();
			freq_s.clear();
			for (int i = 0; i < s.size(); i++){
				freq[s[i]]++;
			}
			for (int i = 0; i < s.size(); i++){
				freq_s.push_back(freq[s[i]]);
			}
			if (check(s, freq_s)) break;
			else s = freq_s;
		}
		printf("%d\n", cnt);
		printf("%d", freq_s[0]);
		for (int i = 1; i < freq_s.size(); i++){
			printf(" %d", freq_s[i]);
		}
		puts("");
	}
	
	return 0;
}

bool check(vector<int> s, vector<int> freq_s)
{
	if (s.size() != freq_s.size()) return false;
	for (int i = 0; i < s.size(); i++){
		if (s[i] != freq_s[i]) return false;
	}
	return true;
}

Measured memory_bytes: 1068