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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

const int INF=1001001001;

int N;
int S[1<<18];

queue<int>bucket[20];
signed main(){
	cin>>N;
	rep(i,1<<N)cin>>S[i];
	sort(S,S+(1<<N));

	bucket[N].push(INF);
	for(int i=(1<<N)-1;i>=0;i--){
		bool ok=false;
		for(int k=N;k>=0;k--){
			if(bucket[k].size()==0||bucket[k].front()==S[i])continue;
			ok=true;
			bucket[k].pop();
			for(int l=0;l<k;l++)bucket[l].push(S[i]);
			break;
		}
		if(!ok){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

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

using namespace std;

int main(){
	int n;cin>>n;
	vector<int> vc;
	int total= 0;
	for(int i=0;i<n;i++){
	    int item;cin >> item;
	    vc.push_back(item);
	}
	for(int i=0;i<n;i++){
	   for(int j=0;j<i;j++){
	       total+=vc[i]*vc[j];
	   }
	}
	cout << total;
}

Measured memory_bytes: 3612
import Data.List
import qualified Data.IntSet as ISet
import Data.Tuple
import Data.Bool

main = do
    ss <- getLine
    [x,y] <- map read . words <$> getLine
    let (xs,ys) = accum ss [0] [0]
        xs' = solve xs
        ys' = solve ys
    putStrLn . bool "No" "Yes" $ any (==x) xs' && any (==y) ys'

accum ss as bs = (reverse as',reverse bs')
    where (as',bs') = accum' ss as bs

accum' [] as bs = (as,bs)
accum' ('T':ss) as bs = swap $ accum' ss (0:bs) as
accum' ('F':ss) (a:as') bs = accum' ss ((a+1):as') bs

solve ns = ISet.elems . foldl' expand (ISet.singleton n) $ ns''
    where
        (n:ns') = ns
        ns'' = filter (/=0) ns'

expand :: ISet.IntSet -> Int -> ISet.IntSet
expand ns x
    | ISet.null ns = ISet.empty
    | otherwise = ISet.union (ISet.map (+x) ns) (ISet.map (subtract x) ns)


Measured memory_bytes: 2428
h, w = map(int, input().split())
n = int(input())
ns = map(int, input().split())
s = []
rslt = []
for i, num in enumerate(ns):
    s += [str(i+1)] * num
i = 0
j = 0
while i < h:
    if i % 2 == 0:
        rslt.append(s[i * w:(i + 1) * w])
    else:
        rslt.append(s[i * w:(i + 1) * w][::-1])
    i += 1
for i in range(h):
    print(' '.join(rslt[i]))

Measured memory_bytes: 3700
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!$BDs=P;~$K%3%a%s%H%"%&%H(B!!
#ifdef DEBUG_
#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

    template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int mod = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    VI a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(),a.end());
    cout << a[0] * a[1] / 2 << endl;

}

Measured memory_bytes: 256
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower

using namespace std;
using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
        int r, g, b;
        cin >> r >> g >> b;
        if ((r * 100 + g * 10 + b) % 4 == 0)
        {
                puts("YES");
        }
        else
        {
                puts("NO");
        }

        return 0;
}


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

int main(){
    int n;
    cin >> n;
    
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec.at(i);
    }
    
    int count = 0, maxnum = 0;
    for (int i = 0; i < n - 1; i++) {
        if (vec.at(i) >= vec.at(i + 1)) {
            count++;
        } else {
            count = 0;
        }
        maxnum = max(count,maxnum);
    }
    
    cout << maxnum << endl;
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
#define countof(a) (sizeof(a)/sizeof((a)[0]))
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define bzero(p, n) memset(p, 0, n)
#define all(a) begin(a),end(a)
template<class T> inline void sort_uniq(T& c) { sort(ALL(c)); c.erase(unique(ALL(c)), c.end()); }
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class K, class V> void cout_v(map<K, V>& m)
{ for(auto it=m.begin();it!=m.end();it++)cout<<it->first<<":"<<it->second<<endl;}
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
inline ll powll(ll x,ll y) {ll p=1; while(y--) p*=x; return p;}
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    const ll MOD = 2019;
    ll L, R; cin >> L >> R;
    ll ans = 0;
    
    if (R - L + 1 < MOD) {
        ans = LLONG_MAX;
        for (ll i = L; i <= R - 1; i++) {
            ll i_mod = i % MOD;
            for (ll j = i + 1; j <= R; j++) {
                ll j_mod = j % MOD;
                ll ixj = (i_mod * j_mod) % MOD;
                chmin(ans, ixj);
            }
        }
    }


    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define ull unsigned long long
#define ld long double

#define mod 1000000007
#define EULER 2.7182818284
#define INF 1000000000

#define pb push_back
#define ins insert
#define IT iterator
#define PQ priority_queue

#define fi first
#define se second
#define maxe max_element
#define mine min_element
#define er erase
#define lb lower_bound
#define ub upper_bound

#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define pi pair<int,int>
#define pll pair<ll,ll>


#define mem(v,i) memset(v,i,sizeof(v)) // v is array. To set all elements to 0 or -1 only. mem(arr,0);


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORd(i,a,b) for(int i=(a);i>=(b);i--)
#define FORl(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORN(i,n) for(int i=(0);i<(n);i++)
#define FORR(i,n) for(int i=(n);i>=0;i--)
#define bs bitset
#define bpc(a) __builtin_popcount(a)

ll max(ll a,ll b)
{
    if(a>b)return a;return b;
}
ll min(ll a,ll b)
{
    if(a<b)return a;return b;
}

ll mypow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}
//..............................!!!!!!Get ready to fight!!!!!!............................



int main()
{
    fast
    ll x;
    cin>>x;
    ll ans=(x/500)*1000;
    x=x%500;
    ans=ans+(x/5)*5;
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 256
import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	ss = s[i]
	dpp = defaultdict(int)
	for key, value in dp.items():
		dpp[key] += (n-1-i) * value
		dpp[key%ss] += value
	for key in dpp.keys():
		dpp[key] %= MOD
	dp = dpp
ans = 0
for key, value in dp.items():
	ans += value * key
	ans %= MOD
print(int(ans))

Measured memory_bytes: 68512
import java.util.*;
public class Main {
  
	public static void main(String[] args) {
      
    	Scanner sc = new Scanner(System.in);
      	int k = sc.nextInt();
      	int n = sc.nextInt();
      	int maxDistance = 0;
      	int newPoint;
      	int lastPoint = sc.nextInt();
      	int firstPoint = lastPoint;
      	int distance;
      	for (int i = 0; i <  n; i++) {
          if (i == n - 1) {
            newPoint = firstPoint + k;
          } else {
          	newPoint = sc.nextInt();
          }
          distance = Math.abs(newPoint - lastPoint);
          lastPoint = newPoint;
          maxDistance = maxDistance < distance ? distance : maxDistance;
        }
      System.out.println(k - maxDistance);
    }
 }

Measured memory_bytes: 64936
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define _GLIBCXX_DEBUG
#define V vector<ll>
using namespace std;
using ll = long long;

int main(){
   int n,y;
   cin>>n>>y;
   for(int i=0; i<=n; i++){
      for(int j=0; j<=n-i; j++){
         for(int k=0; k<=n-i-j; k++){
            if(10000*i+5000*j+1000*k==y&&i+j+k==n){
               cout<<i<<" "<<j<<" "<<k<<endl;
               return 0;
            }
         }
      }
   }
   cout<<-1<<" "<<-1<<" "<<-1<<endl;
}


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

int main(void){
	int  A, B, C;
	cin >> A >> B >> C;
  	int tmp = C - (A -B);
	if(tmp < 0) cout << 0 << endl;
  	else cout << tmp << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
bool is_integer(double x)
{
  return floor(x) == ceil(x);
}
int main()
{
  int n;
  cin >> n;
  int l[100];
  int max, a, b;
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> l[i];
  }
  for (int i = 0; i < n - 2; i++)
  {
    for (int j = i + 1; j < n - 1; j++)
    {
      for (int k = j + 1; k < n; k++)
      {
        if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i])
        {
          continue;
        }
        if (l[i] > l[j])
        {
          max = l[i];
          a = l[j];
        }
        else
        {
          max = l[j];
          a = l[i];
        }
        if (max > l[k])
        {
          b = l[k];
        }
        else
        {
          b = max;
          max = l[k];
        }

        if (max < a + b)
        {
          cnt++;
        }
      }
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string ans="safe";
    int a,b;
    cin>>a>>b;
    if(b>=a) ans="unsafe";
    cout<<ans<< endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;

  long red[a], green[b], white[c];
  for (int i = 0; i < a; i++) { cin >> red[i]; }
  for (int i = 0; i < b; i++) { cin >> green[i]; }
  for (int i = 0; i < c; i++) { cin >> white[i]; }

  sort(red, red + a, [](const long &a, const long &b) -> bool { return a > b; });
  sort(green, green + b, [](const long &a, const long &b) -> bool { return a > b; });
  sort(white, white + c, [](const long &a, const long &b) -> bool { return a > b; });

  long use[x + y];
  for (int i = 0; i < x; i++) { use[i] = red[i]; }
  for (int i = 0; i < y; i++) { use[x + i] = green[i]; }

  sort(use, use + x + y);
  int wi = 0;
  for (int i = 0; i < x + y && wi < c; i++) {
    if (white[wi] > use[i]) use[i] = white[wi];
    wi++;
  }

  long res = 0;
  for (int i = 0; i < x + y; i++) { res += use[i]; }
  cout << res << endl;
}


Measured memory_bytes: 3968
import java.util.Stack;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main
{
    public static void main(String[] args)throws IOException
    {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] S = br.readLine().split("\\s");

	Stack <Integer>s1 = new Stack<Integer>();
	int a = 0;
int b = 0;

	for(int i = 0; i < S.length; i++)
	    {
		switch(S[i])
		    {
		    case "+":
			a = s1.pop();
			b = s1.pop();
			s1.add(a + b);
			continue;

		    case "-":
			a = s1.pop();
			b = s1.pop();
			s1.add(b - a);
			continue;

		    case "*":
			a = s1.pop();
			b = s1.pop();
			s1.add(a * b);
			continue;
		    }
		s1.push(Integer.parseInt(S[i]));
	    }
	System.out.println(s1.pop());
    }
}

Measured memory_bytes: 24288
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll N,X;
ll ans=0;
void calc(ll a,ll b){
	if(b==0){
		ans-=a;
		return;
	}
	ans+=(a/b)*b*2;
	// show(a);
	// show(b);
	// show((a/b)*b*2);
	calc(b,a%b);
}
int main(){
	cin>>N>>X;
	calc(max(X,N-X),min(X,N-X));
	cout<<N+ans<<endl;
}


Measured memory_bytes: 256
#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 REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<int,ll> Pil;
typedef pair<ll,ll> Pll;
typedef pair<string,int> Psi;
typedef pair<Psi,int> Psii;

const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main() {
	int n,p;
	cin>>n;
	int res=0;
	rep(i,n){
		cin>>p;
		if(p!=(i+1))res++;
	}
	if(res==2||res==0){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>

using namespace std;

int value[100],weight[100];
int table[101][10001]={};

int main(){
  int N,W;
  cin>>N>>W;
  for(int i=0;i<N;++i){
    cin>>value[i]>>weight[i];
  }

  for(int i=1;i<=N;++i){
    for(int w=0;w<=W;++w){
      if(w>=weight[i-1])
        table[i][w] = max(table[i-1][w],value[i-1]+table[i][w-weight[i-1]]);
      else
        table[i][w] = table[i-1][w];
    }
  }

  cout << table[N][W] << endl;
  return 0;
}

Measured memory_bytes: 6988
function Main(input) {
  input = input.replace(/\n/g, ' ');
  input = input.split(" ");
  var A = Number(input[0]);
  var P = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
  var ans = "";
  var num = [];
  var l = 0;
  while(true){
    num[l] = A%26 - 1;
    if(num[l] == -1)num[l]=25;
    A=(A-num[l]-1)/26;
    if(A == 0){break;}
    l++;
  }
  for(var i=num.length-1;i>=0;i--){
    ans+=P[Number(num[i])];
  }
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29624
import heapq

N, M = map(int, input().split())
jobs = [[] for _ in range(M+1)]
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)


Measured memory_bytes: 72480
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
using namespace std;
int main(){
  int a,b,c,d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  printf("%d",min(a,b) + min(c,d));
}

Measured memory_bytes: 256
#include <stdio.h>

void gcd(int a,int b,int cnt){
  if (b==0){
    printf("%d %d\n",a,cnt);
    return ;
  }else{
    cnt++;
    gcd(b,a%b,cnt);
  }
}
int main(){
  int a,b;
  while(scanf("%d %d",&a,&b)){
    if (a==0 && b==0)
      break;
    if (b>a){
      int t=b;b=a;a=t;
    }
    gcd(a,b,0);
  }
  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>

using namespace std;

int main() {
	long long X, K, D, result = 0;
	cin >> X >> K >> D;

	long long div = abs(X) / D;
	long long mod = abs(X) % D;
	
	if (K > div) {
		K -= div;
		if (K % 2 == 0) {
			result = mod;
		}
		else {
			if (D > mod) {
				result = D - mod;
			}
			else {
				result = mod - D;
			}
		}
	}
	else if (K < div) {
		result = abs(X) - (D * K);
	}
	else {
		result = abs(X) % D;
	}

	cout << result << endl;
	return 0;
}



Measured memory_bytes: 3620
'use strict'


function Main(input) {
  input = input.trim().split(' ')
  const H = parseInt(input[0])
  const A = parseInt(input[1])

  if (H < A) {
    console.log(1)
    return
  }

  let total = H
  let count = 0
  while(total > 0) {
    total -= A
    count++
  }


  console.log(count)

}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
    int x, y;
    cin >> x >> y;
    for(int i=0; i<=x; ++i){
        if(i*2 + (x-i)*4 == y){
            cout("Yes");
            return 0;
        }
    }
    cout("No");
}


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

#define     F       first
#define     S       second
typedef pair<int, int>  pi;
typedef long long       ll;

int h, w, k;
char grid[2][9][9];

bool Check() {
    int cnt=0;
    for (int i=0; i<h; ++i) {
        for (int j=0; j<w; ++j) {
            if (grid[1][i][j]=='#') {
                ++cnt;
            }
        }
    }

    return cnt==k;
}

void FillRows(int mask) {
    for (int i=0; i<h; ++i) {
        if ((1<<i) & mask) {
            for (int j=0; j<w; ++j) {
                grid[1][i][j]='R';
            }
        }
    }
}

void FillCols(int mask) {
    for (int j=0; j<w; ++j) {
        if ((1<<j) & mask) {
            for (int i=0; i<h; ++i) {
                grid[1][i][j]='R';
            }
        }
    }
}

void Initialize() {
    for (int i=0; i<h; ++i) {
        for (int j=0; j<w; ++j) {
            grid[1][i][j]=grid[0][i][j];
        }
    }
}

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

    cin >> h >> w >> k;
    for (int i=0; i<h; ++i) {
        for (int j=0; j<w; ++j) {
            cin >> grid[0][i][j];
        }
    }

    int ans=0;
    for (int rows=0; rows<(1<<h); ++rows) {
        for (int cols=0; cols<(1<<w); ++cols) {
            Initialize();
            
            FillRows(rows);
            FillCols(cols);

            ans+=Check();
        }
    }

    cout << ans;

    return 0;
}


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

double dp[3001][3001];

int main() {
    Int n;
    cin >> n;
    vector<double> p(n);
    for (Int i = 0; i < n; i++) {
        cin >> p[i];
    }
    dp[0][0] = 1.0;
    for (Int i = 0; i < n; i++) {
        for (Int j = 0; j < n; j++) {
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i]);
            dp[i + 1][j + 1] += dp[i][j] * p[i];
        }
    }
    double res = 0.0;
    for (Int i = n / 2 + 1; i <= n; i++) {
        res += dp[n][i];
    }
    printf("%.12lf\n", res);
    return 0;
}

Measured memory_bytes: 70528
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

class BIT{//1-indexed
public:

  vector<ll> bit;
  BIT(){}
  BIT(int size){
    bit.resize(size,0);
  }

  ll sum(int i){
    ll s=0;
    while(i>0){
      s+=bit[i];
      i-=i&(-i);
    }
    return s;
  }

  void add(int i,ll x){//i!=0
    while(i<bit.size()){
      bit[i]+=x;
      i+=i&(-i);
    }
  }
};


int N;
vector<int> A,B;

int main(){
  cin>>N;
  A.resize(N);
  B.resize(N);
  rep(i,N) cin>>A[i];
  rep(i,N) cin>>B[i];

  bool ok=false;
  int ans=1e9;
  for(int bit=0;bit<(1<<N);bit++){
    if(__builtin_popcount(bit)!=((N+1)/2)) continue;
    vector<pair<int,int>> odd,even;
    for(int i=0;i<N;i++){
      if(bit&(1<<i)){
        if((i+1)%2) odd.push_back(mkp(A[i],i));
        else odd.push_back(mkp(B[i],i));
      }else{
        if((i+1)%2) even.push_back(mkp(B[i],i));
        else even.push_back(mkp(A[i],i));
      }
    }

    sort(odd.begin(),odd.end());
    sort(even.begin(),even.end());

    vector<pair<int,int>> v;
    for(int i=0;i<N;i++){
      if((i+1)%2) v.push_back(odd[i/2]);
      else v.push_back(even[i/2]);
    }
    bool f=true;
    for(int i=1;i<N;i++) if(v[i-1].first>v[i].first) f=false;


    if(f){
      ok=true;
      BIT bit(N+1);
      int res=0;
      for(int i=0;i<N;i++){
        int tar=v[i].second;
        int num=bit.sum(tar+1);
        int fr=i+(i-num);
        res+=(fr-i);
        bit.add(tar+1,1);
      }
      ans=min(ans,res);
    }
  }

  if(ok==false){
    cout<<"-1"<<endl;
    return 0;
  }else cout<<ans<<endl;

  return 0;
}


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

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

int main(void){
    int n, d;
    cin >> n >> d;
    vector<vector<int>> x(n, vector<int>(d));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < d; j++) cin >> x.at(i).at(j);
    }
    vector<int> sq;
    for(int i = 1; i*i <= 40*40*10; i++){
        sq.push_back(i*i);
    }
    int dist;
    int c = 0;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            dist = 0;
            for(int k = 0; k < d; k++){
                dist += pow(x.at(i).at(k) - x.at(j).at(k), 2);
            }
            // cout << x.at(i) << " " << x.at(j) << endl;
            // cout << dist << endl;
            for(auto w : sq){
                if(w == dist) c++;
            }
        }
    }
    cout << c << endl;
    return 0;
}


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

int64_t div2(int64_t i) {
  int64_t ans = 0ll;
  while (i>1) {
    ans++;
    i /= 2;
  }
  return ans;
}

int main() {
  int64_t H;
  cin >> H;
  int64_t N = div2(H);
  int64_t ans = pow(2, N+1)-1;
  cout << ans << endl;
}

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

int main()
{
    //freopen("vidu.inp","r",stdin);
    //freopen("vidu.out","w",stdout);
    long long N;
    string S;
    cin >> N;
  if(N == 0) cout << 0 << endl;

  while(N!=0)
  {
    if(N%2!=0)
    {
      S = "1" + S;
      N--;
    }
    else {
      S = "0" + S;
    }
    N = -N/2;
  }
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 2000000

void countingSort(int,int);
int a[MAX],b[MAX];

int main(){
  
  int i,n,k=0;

  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&a[i+1]);
    if(a[i+1]>k) k=a[i+1];
  }

  countingSort(k,n);

  for(i=0;i<n;i++){
    if(i==0) printf("%d",b[i+1]);
    else printf(" %d",b[i+1]);
  }
  printf("\n");

  return 0;
}

void countingSort(int k,int n){
  int i,j,c[MAX];

  for(i=0;i<k+1;i++){
    c[i]=0;
  }

  for(j=1;j<n+1;j++){
    c[a[j]]++;
  }

  for(i=1;i<k+1;i++){
    c[i] = c[i]+c[i-1];
  }
  
  for(j=n;j>0;j--){
    b[c[a[j]]] = a[j];
    c[a[j]]--;
  }
}

Measured memory_bytes: 16272
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(){

    const string keyword[] = {"the", "this", "that"};
    string str = "";

    while(getline(cin, str)){
        int len = str.length();
        vector <bool> match(3, false);

        int i,j;

        for(j=0; j<26; j++){
            string current = str;
            for(i=0; i<len; i++){
                if(isalpha(str[i])){
                        current[i] = (str[i] - 'a' + j) % 26 + 'a';
                }
            }

            for(i=0; i<3; i++){
                if(current.find(keyword[i]) != string::npos){
                    match[i] = true;
                }
            }

            if((int)count(match.begin(), match.end(), true) > 0){
                cout << current << endl;
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;

int main() {

    int N, M;
    cin >> N >> M;

    vector<int> A(M + 1);
    for (int i = 0; i < M + 1; ++i) {
        A[i] = 0;
    }

    for (int i = 0; i < N; ++i) {
        int K;
        cin >> K;

        for (int j = 0; j < K; ++j) {
            int food;
            cin >> food;
            ++A[food];
        }
    }

    int counter = 0;
    for (int i = 0; i < M + 1; ++i) {
        if (A[i] == N) {
            ++counter;
        }
    }

    cout << counter << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 111111;
vector<pair<int, ll> > tree[N];
ll dists[N];
int n, q, k;

void dfs(int node, int p = 0) {
    for(nnode : tree[node]) {
        if(nnode.first != p) {
            dists[nnode.first] = dists[node] + nnode.second;
            dfs(nnode.first, node);
        }
    }
}

ll solve(int x, int y) {
    return dists[x] + dists[y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        tree[u].push_back(make_pair(v, c));
        tree[v].push_back(make_pair(u, c));
    }
    cin >> q >> k;
    dfs(k);
    while(q--) {
        int x, y;
        cin >> x >> y;
        cout << solve(x, y) << endl;
    }
    return 0;
}

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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846
#define ALL(X) (X).begin(),(X).end()

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int K,X;

void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    cin >> K >> X;
}

void solve(){
    vector<int> ans;
    ans.push_back(X);
    for(int i=1;i<K;i++) {
        ans.push_back(X+i);
        ans.push_back(X-i);
        }
    VSORT(ans)
    cout << ans << endl;
}

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


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define fr(i,n) for(int i=0;i<n;i++)

int main(){
  ll n,a[200010],b[200010],d[200010]={1},ans=0,kari,c;
  cin>>n;
  fr(i,n){
    cin>>a[i];
  }
  b[0]=a[0];
  fr(i,n-1){
    b[i+1]=b[i]+a[i+1];
  }
  sort(b,b+n);
  kari=0;
  fr(i,n){
    if(b[i]==0) ans++;
    if(b[i]>0) break;
  }
  c=b[0];
  fr(i,n-1){
    if(b[i]==b[i+1]) d[kari]++;
    else{kari++;d[kari]++;}
  }
  fr(i,kari+1){
    ans+=(d[i]*(d[i]-1))/2;
  }
  cout<<ans;
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int X = sc.nextInt();
		
		if (A > X) {
			System.out.println("NO");
		} else if (X - A <= B) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21844
import java.util.Scanner;
import java.util.Arrays;
// import java.util.HashMap;
// import java.util.List;
// import java.util.ArrayList;
// import java.util.Map.Entry;
// import java.util.Comparator;
// import java.io.IOException;
// import java.io.InputStream;
// import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long A[] = new long[N];
        for(int i = 0; i < N; i++){
            A[i] = sc.nextLong();
        }
        Arrays.sort(A);
        boolean ok = true;
        for(int i = 0; i < N-1; i++){
            if(A[i] == A[i+1]) ok = false;
        }
        if(ok){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
        




    }
 
}

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

typedef long long ll;

#define F first 
#define S second 
#define PB push_back
#define MP make_pair 
#define rep(i,a,b) for (ll i=a;i<b;i++)
const ll INF = 1LL << 60;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;


int main()
{
    int n;
    cin>>n;
    vi x(n);
    rep(i,0,n) cin>>x[i];

    int avg =0;

    rep(i,0,n) {
        avg +=x[i];
    }
    double mid = (double) avg/ (double) x.size();
    mid = round(mid);

    int res=0;
    rep(i,0,n) {

        res += ((x[i]-mid)*(x[i]-mid));
    }
    cout<<res<<endl;

    return 0; 
}



Measured memory_bytes: 384
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    int x;
    cin>>x;
    int ans=1;
    for(int p=2;p<10;p++){
        for(int i=1;i<100;i++){
            int q=pow(i,p);
            if(q<=x) ans=max(ans,q);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath> //abs();
using namespace std;

int main(void)
{
    long long int a,b,c,d,i,j,k,n,x[10];
    string s;

    cin >> s;

    s.at(5) = ' ';
    s.at(13) = ' ';

    cout << s;

    return 0;
}


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

int main()
{
	int n;
	int a[10001];
	int max = -1000000, min = 1000000;
	long sum = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (max < a[i]) max = a[i];
		if (min > a[i]) min = a[i];
		sum += a[i];
	}
	cout << min << " " << max << " " << sum << endl;
    return 0;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h> 
#define int long long
using namespace std; 
  
const int M = 500; 
  
// states - position, count, tight 
int dp[M][M][2]; 
  
// K is the number of non zero digits 
int K; 
  
// This function returns the count of 
// required numbers from 0 to num 
int countInRangeUtil(int pos, int cnt, int tight, 
                     vector<int> num) 
{ 
    // Last position 
    if (pos == num.size()) { 
        // If count of non zero digits 
        // is less than or equal to K 
        if (cnt == K) 
            return 1; 
        return 0; 
    } 
  
    // If this result is already computed 
    // simply return it 
    if (dp[pos][cnt][tight] != -1) 
        return dp[pos][cnt][tight]; 
  
    int ans = 0; 
  
    // Maximum limit upto which we can place 
    // digit. If tight is 1, means number has 
    // already become smaller so we can place 
    // any digit, otherwise num[pos] 
    int limit = (tight ? 9 : num[pos]); 
  
    for (int dig = 0; dig <= limit; dig++) { 
        int currCnt = cnt; 
  
        // If the current digit is nonzero 
        // increment currCnt 
        if (dig != 0) 
            currCnt++; 
  
        int currTight = tight; 
  
        // At this position, number becomes 
        // smaller 
        if (dig < num[pos]) 
            currTight = 1; 
  
        // Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, 
                                currTight, num); 
    } 
    return dp[pos][cnt][tight] = ans; 
} 
  
// This function converts a number into its 
// digit vector and uses above function to compute 
// the answer 
int countInRange(string x) 
{ 
    vector<int> num; 
    for(int i = 0;i<x.size();i++) { 
        num.push_back(x[i]-'0'); 
      
    } 
    
    // Initialize dp 
    memset(dp, -1, sizeof(dp)); 
    return countInRangeUtil(0, 0, 0, num); 
} 
  
// Driver Code to test above functions 
signed main() 
{ 
   	
   	string s;
   	cin>>s;
   	cin>>K;
   	cout<<countInRange(s)<<endl;

} 

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define rzip(i,a,b) for(int i=a;i>=b;i--)
#define ll unsigned int
#define test int t;cin>>t; while(t--)
#define en '\n'
typedef pair<int, int>     pii;
typedef pair<char, int>    pci;
typedef pair<char, char>   pcc;
typedef vector<pii>       vii;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(x) (int)x.size()
#define INF (1e18+5)
#define inf (1e9+5)
#define mod 1000000007


void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
// You should only debug a pair of simple data types. For example,
// the debug won't work if one of pair's elements is collection type
// (std::vector, std::map, std::set...).
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


// bool check_prime(int n)  return whether a number is prime or not O(sqrt(N));
// int BE(int x,int n,int m)  return x^n%m; O(logN);
// void sieve()  from number 1-1000001 saare prime store kar lega  in bool is_prime[1000001] array
// vector<int> z_array(string s)  return vector which is Z-array of string s;
// vector<int> lps(string s)      return vector which is lps array of string s;
// int power(int x,int n) return x^n; O(logN);
// using_ordered_set (template for using ordered set , replace first 2 lines of this page with this code..);
const int gf = 1e6 + 9;

bool check_prime(long long n)
{
	int flag = 0;
	for (long long i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			flag = 1;
			break;
		}
	}
	if (n == 1)
		return false;
	else if (flag == 0 || n == 2 || n == 3)
	{
		return true;
	}
	else
	{
		return false;
	}

}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	if (fopen("input.txt", "r"))
	{
		freopen ("input.txt" , "r" , stdin);
		freopen ("output.txt" , "w" , stdout);
	}
#endif
	//_______________________________-code starts-_______________________________________________

	int n;
	cin >> n;
	vi v;
	rep(i, 1, 55555)
	{
		if (check_prime(i) && i % 5 == 1)
		{
			v.pb(i);
		}
	}
	debug(sz(v));
	zip(i, 0, n)
	cout << v[i] << " ";


	return 0;
}




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

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

int main() {
	int x, y, s;
	while(cin >> x >> y >> s, x||y||s) {
		int res = 0;
		for(int a=1; a<s; a++) {
			for(int b=1; b<s; b++) {
				if(a*(100+x)/100 + b*(100+x)/100 == s) {
					res = max(res, a*(100+y)/100+b*(100+y)/100);
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}

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

int main(){
      string s;cin >> s;
      if(s[0] == s[1] && s[1] == s[2] ||
            s[1] == s[2] && s[2] == s[3] ||
            s[0] == s[1] && s[1] == s[2] && s[2] == s[3]){
                  cout << "Yes";
            }
      else cout << "No";
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<string> vst;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

const ll mod=1e9+7;
const ll inf=1e16; 

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)

const long nmax=1000000;


long long fac[nmax],finv[nmax],inv[nmax];

void comint(){
 fac[0]=fac[1]=1;
 finv[0]=finv[1]=1;
 inv[1]=1;
 for(long i=2;i<nmax;i++){
  fac[i]=fac[i-1]*i%mod;
  inv[i]=mod-inv[mod%i]*(mod/i)%mod;
  finv[i]=finv[i-1]*inv[i]%mod;
}
}

auto com(auto n, auto k){
 if(n<k||n<0||k<0) return 0;
 return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}




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

  comint();
  
  ll n,k;
  cin >> n >> k;
  ll res=0;
  rep(m,0,min(n,k)+1) res+=(com(n,m)*com(n-1,n-m-1))%mod,res%=mod;
   
 cout << res << endl;
}

Measured memory_bytes: 23680
loop do
  n = gets.to_i
  break if n == 0

  tw = Hash.new(0)
  n.times do
    m, a, b = gets.split(' ').map(&:to_i)
    tw[a] += m
    tw[b] += -1*m
  end

  sum = 0
  flag = true
  tw.sort_by{ |k,v| k }.each do |ti,we|
    sum += we
    if sum > 150
      flag = false
      break
    end
  end
  puts flag ? "OK" : "NG"
end

Measured memory_bytes: 6140
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define test int t;cin>>t;while(t--)
typedef long long int ll;
#define REP(i,n) for (int i = 1; i <= n; i++)
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define lli long long int
#define INF 1000000000
const double pi = 3.14159265358979323846;


int main() {
    fast
    //test
    {
        int i,j,n,m=1;
        //cin>>n;
		string s,t;
      	cin>>s>>t;
        if(s.size()!=t.size()-1)
            cout<<"No";
        else{
        for(i=0;i<s.size();i++)
            {if(s[i]!=t[i])
                {
                cout<<"No";
                m=0;
                break;
                }
            }
            if(m==1)
            cout<<"Yes";
        }
		      
    }
    return 0;
}


Measured memory_bytes: 3648
n, k, c = map(int, input().split())
s = input()
INF = 10 ** 9

work = [i for i, e in enumerate(s, 1) if e == "o"]
l = [0] * (n + 1)
r = [0] * (n + 1)

prev = -INF
cnt = 0
for e in work:
    if e - prev > c:
        cnt += 1
        l[cnt] = e
        prev = e

prev = INF
cnt = 0
for e in work[::-1]:
    if prev - e > c:
        cnt += 1
        r[cnt] = e
        prev = e

l = l[1:k+1]
r = r[1:k+1][::-1]

ans = []
for el, er in zip(l, r):
    if el == er:
        ans.append(el)

print(*ans, sep="\n")


Measured memory_bytes: 21780
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=2e9;
const double PI=acos(-1);


int main() {
    ios_base::sync_with_stdio(false);

    int n;
    string s;
    cin >> n >> s;
    int cnt=0; 
    rep(i,n) {
        if (s[i]=='R') ++cnt;
    }
    int ans=0;
    rep(i,cnt) {
        if (s[i]=='W') ++ans;
    }
    cout << ans << endl;
   
    return 0;   
}

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

using namespace std;

int main(void)
{
    int n, l, tmp = 0, ans = 0x3f3f3f3f;
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; ++i)
        tmp += l + i - 1;
    int x = tmp, ansx;
    for (int i = 1; i <= n; ++i)
        if (abs(tmp - (l + i - 1) - x) < ans) ans = abs(tmp - (l + i - 1) - x), ansx = tmp - (l + i - 1);
    printf("%d\n", ansx);
    return 0;
}

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

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

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

void shellSort( int A[], int n) {
	for ( int h = 1; ; ) {
		if ( h > n) break;
		G.push_back(h);
		h = 3*h + 1;
	}

	for ( int i = G.size() - 1; i >= 0; i--) {
		insertionSort(A, n, G[i]);
	}
}

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

	shellSort(A, n);

	cout << G.size() << endl;
	for ( int i = G.size() - 1; i >= 0; i-- ) {
		printf("%d", G[i]);
		if (i) printf(" ");
	}
	printf("\n");
	printf("%lld\n", cnt);

	for ( int i = 0; i < n; i++ ) printf("%d\n", A[i]);

	return 0;
}

Measured memory_bytes: 7180
# 2020/04/25
# CODE FESTIVAL 2016 Final - B

# Input
n = int(input())

# Calc
wk_val = 0

x = 1
# while (x*(x+1)) / 2 <= n:
while (x*(x+1)) / 2 < n:
    x = x + 1

wk_ans = 0
anslist = list()
while(x > 0):
    if wk_ans + x <= n:
        wk_ans = wk_ans + x
        anslist.append(x)

    if wk_ans == n:
        break
    
    x = x - 1

# Output
for i in range(len(anslist)):
    print(anslist[i])


Measured memory_bytes: 3444
import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]

li = [a[0]]
ans = 1

for i in range(1,n):
    if li[0] < a[i]:
        li[0] = a[i]
    elif li[-1] >= a[i]:
        li.append(a[i])
    else:
        p = 0
        q = len(li) - 1
        while p != q:
            c = (p + q) // 2
            if li[c] >= a[i]:
                p = c + 1
            else:
                q = c
        li[p] = a[i]

print(len(li))


Measured memory_bytes: 49500
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 87;
int p[N],vis[N],tt;
vector<int> g[N],tmp;
void dfs(int u)
{
    if (vis[u] == tt)
        return;
    vis[u] = tt;
    tmp.push_back(p[u]);
    for (int v : g[u])
        dfs(v);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (vis[i])
            continue;
        ++tt;
        tmp.clear();
        dfs(i);
        for (int v : tmp)
            ans += vis[v] == tt;
    }
    cout << ans << endl;
}


Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

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

    vector<string> vs;
    for (int i=0; i<(int)s.size(); ++i) {
        for (int j=1; j<=K; ++j) {
            vs.push_back(s.substr(i, j));
        }
    }
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    cout << vs[K-1] << endl;

    return 0;
}

Measured memory_bytes: 1660