akhauriyash/Code-Regression huggingface dataset:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
a.sort()
if n%2:
    e=n//2
    cor=[0]+[2*i for i in range(1,e+1)]*2
    cor.sort()
    if a==cor:
        ans=1
        for i in range(e):
            ans*=2
            ans%=mod
        print(ans)
    else:print(0)
else:
    e=n//2
    cor=[2*i+1 for i in range(e)]*2
    cor.sort()
    if a==cor:
        ans=1
        for i in range(e):
            ans*=2
            ans%=mod
        print(ans)
    else:print(0)


Measured memory_bytes: 14008
def resolve():
    N, M, X = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    ans = 1<<60
    for bit in range(1<<N):
        G = [0]*M
        cost = 0
        ok = False
        for i in range(N):
            if bit>>i & 1:
                c, *book = AB[i]
                cost += c
                for num, b in enumerate(book):
                    G[num] += b
        for g in G:
            if g < X:
                break
        else:
            ok = True
        if ok:
            ans = min(ans, cost)
    print(ans if ans < 1<<60 else -1)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 9228
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
using namespace std;
int main(void) {
    
   char a,b;
   cin>>a>>b;
   if(a==b)cout<<"="<<endl;
   else if(a<b)cout<<"<"<<endl;
   else cout<<">"<<endl;

    return 0;
}

Measured memory_bytes: 256
import java.*;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		List<String> alph = Arrays.asList("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");
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String str = sc.next();
		
		for (int i = 0; i < str.length(); i++) {
		    String str2 = String.valueOf(str.charAt(i));
		    int num = alph.indexOf(str2);
		    String newWord = alph.get((num + N ) % 26);
		    System.out.print(newWord);
		}
	}
}

Measured memory_bytes: 25556
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    ans = {}
    for _ in range(N):
        tmp = inputInt()
        if tmp in ans:
            ans[tmp] += 1
        else:
            ans[tmp] = 1
        
    o = 0
    for v in ans.values():
        if v % 2 == 1:
            o += 1
    print(o)
        
            	
if __name__ == "__main__":
	main()


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

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <class T, class U>
void chmax(T &a, U b) {
    if (a < b) a = b;
}
template <class T, class U>
void chmin(T &a, U b) {
    if (b < a) a = b;
}

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

#define MOD 1000000007
#define MAX 2000010

ll f[MAX] = {};
ll rf[MAX] = {};

ll pw(long long x, long long y) {
    long long ret = 1LL;

    for (long long mask = 0; mask < 50; ++mask) {
        if (y >> mask & 1) ret = ret * x % MOD;
        x = x * x % MOD;
    }
    return ret % MOD;
}

long long getComb(int n, int k) {
    if (k > n) return 0;
    long long ret = f[n];
    ret = ret * rf[k] % MOD;
    ret = ret * rf[n - k] % MOD;
    return ret;
}

long long initComb(int n) {
    rf[0] = f[0] = 1;
    for (int i = 1; i < n + 1; i++) {
        f[i] = f[i - 1] * i % MOD;
        rf[i] = pw(f[i], MOD - 2);
    }
    return 1;
}

void solve(std::vector<long long> r, std::vector<long long> c) {
    initComb(2000005);
    cout << (getComb(r[1] + c[1] + 2, r[1] + 1) - getComb(r[1] + c[0] + 1, c[0]) - getComb(r[0] + c[1] + 1, r[0]) + getComb(r[0] + c[0], r[0]) + 4LL * MOD) % MOD << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    std::vector<long long> r(2);
    std::vector<long long> c(2);
    for (int i = 0; i < 2; i++) {
        scanf("%lld", &r[i]);
        scanf("%lld", &c[i]);
    }
    solve(std::move(r), std::move(c));
    return 0;
}


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

using namespace std;

#define ll long long
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef set<int> si;
typedef set<vi> svi;
typedef set<ll> sll;
typedef set<vll> svll;
typedef set<pii> spii;
typedef set<vpii> svpii;
typedef set<pll> spll;
typedef set<vpll> svpll;
typedef vector<si> vsi;
typedef vector<sll> vsll;
typedef vector<spii> vspii;
typedef vector<spll> vspll;
#define ft first
#define sc second
#define pb push_back
#define ins insert
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define sortarr(a,n) sort(a,a+n)
#define tt ll tc; cin >> tc; while(tc--)
#define rep(var,start,end,interval) for(ll var=start;(interval>0 and var<end) or (interval<0 and var>end);var+=interval)
#define each(x,v) for(auto x : v)
#define takearr0(a,n) rep(z,0,n,1) cin >> a[z];
#define takearr1(a,n) rep(z,1,n+1,1) cin >> a[z];

const ll max_n = 2e5 + 5;

ll n;
string s1,s2;
ll nw = 0,nr = 0;

int main()
{
	io;
	cin >> n >> s1;
	for(auto c : s1)
	{
		if(c == 'R')
			++nr;
		else
			++nw;
	}
	s2 = "";
	rep(i,0,nr,1) s2 += "R";
	rep(i,0,nw,1) s2 += "W";
	ll d = 0;
	rep(i,0,n,1) if(s1[i] != s2[i]) ++d;
	d /= 2;
	cout << min(d,min(nw,nr)) << endl;
	return 0;
}

Measured memory_bytes: 3852
from math import sqrt
q3 = sqrt(3)
fmt = "%.8f %.8f"
def koch(x0, y0, x1, y1, c):
    if c == n:
        return (fmt % (x0, y0),)
    xp = (x0*2 + x1) / 3
    yp = (y0*2 + y1) / 3
 
    xq = (x0 + x1*2) / 3
    yq = (y0 + y1*2) / 3
 
    dx = (x1 - x0) / 6
    dy = (y1 - y0) / 6
 
    xr = xp + (dx - dy * q3)
    yr = yp + (dx * q3 + dy)
 
    return koch(x0, y0, xp, yp, c+1) + koch(xp, yp, xr, yr, c+1) + koch(xr, yr, xq, yq, c+1) + koch(xq, yq, x1, y1, c+1)
n = int(input())
print(*koch(0, 0, 100, 0, 0)+(fmt % (100, 0),), sep='\n')



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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define For(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define sz(x) ((int)(x).size())
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef long long ll;
typedef unsigned long long ull;

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

  string s[] = {"Sunny", "Cloudy", "Rainy"};

  string t; cin>>t;
  int i = 0;
  while(s[i]!=t) i++;
  i++; i%=3;
  cout<<s[i]<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep2(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i,n) rep2(i,0,n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using ll = long long;
template <typename T>
T sq(T x){
  return x * x;
}

signed main (){
  int H,W;
  cin >> H >> W;
  vector<vector<char>> C(H,vector<char>(W));
  rep(i,H)rep(j,W)cin >> C.at(i).at(j);  
rep(i,H){
  rep(k,2){
  rep(j,W){
  cout << C.at(i).at(j);
  if(j == W-1){cout << endl;}
  }
  }
}
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string T, P;
    int Tlen, Plen;

    cin >> T >> P;
    Tlen = T.size();
    Plen = P.size();

    for (int i = 0; i <= Tlen - Plen; i++) {
        if (T[i] == P[0]) {
            if (P == T.substr(i, Plen)) {
                cout << i << "\n";
            }
        }
    }
    
    return 0;
}

Measured memory_bytes: 2708
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};

struct e{
    string s;
    ll cost;
    bool rev;
};

bool ispa(string s){
    int n = s.size();
    for(int i=0;i<n;i++){
        if(s[i] != s[n-1-i]){
            return false;
        }
    }
    return 1;
}

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

    int n;
    cin>>n;
    string s[n],rev[n];
    ll a[n];
    map<string, ll> used[2];
    for(int i=0;i<n;i++){
        cin>>s[i]>>a[i];
        if(used[0].count(s[i]))chmin(used[0][s[i]], a[i]);
        else used[0][s[i]] = a[i]; 
        rev[i] = s[i];
        reverse(rev[i].begin(),rev[i].end());
        if(used[1].count(rev[i]))chmin(used[1][rev[i]], a[i]);
        else used[1][rev[i]] = a[i];
    }
    ll ans = 1e18;
    queue<e> q;
    for(int i=0;i<n;i++){
        q.push((e){s[i],a[i],0});
    }
    map<string,vector<e>> mp[2];
    for(int i=0;i<n;i++){
        string now = "";
        string rnow="";
        for(int j=0;j<s[i].size();j++){
            now += s[i][j];
            rnow += rev[i][j];
            mp[0][now].push_back((e){s[i].substr(j+1), a[i], 0});
            mp[1][rnow].push_back((e){rev[i].substr(j+1), a[i], 1});
        }
    }
    map<string,ll> visited[2];
    while(q.size()){
        e p = q.front();
        q.pop();
        bool x = p.rev;
        string str = p.s;
        if(visited[x].count(str) && visited[x][str] <= p.cost)continue;
        visited[x][str] = p.cost;
        if(ispa(str)){
            chmin(ans, p.cost);
            continue;
        }
        // check mp[x^1][str] -> x^1
        int nx = x^1;
        if(mp[nx].count(str)){
            for(e i:mp[nx][str]){
                q.push((e){i.s, p.cost + i.cost, nx});
            }
        }
        string now = "";
        // check mp[c^1][str[0:i]] -> x
        for(int j=0;j<p.s.size()-1;j++){
            now += p.s[j];
            if(used[nx].count(now)){
                q.push((e){p.s.substr(j+1), p.cost + used[nx][now], x});
                
            }
        }
    }
    if(ans > 1e17)ans = -1;
    cout << ans << endl;
}   

Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N,a,b;
  long K,sum=0;
  cin>>N>>K;
  map<int,long> A;
  for(int i=0;i<N;i++){
    cin>>a>>b;
    A[a]+=b;
  }
  for(auto itr=A.begin();itr!=A.end();itr++){
    sum+=itr->second;
    if(sum>=K){
      cout<<itr->first<<endl;
      break;
    }
  }
}

Measured memory_bytes: 4224
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>
#include<random>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
int d;
int c[30]={};
int s[370][30];
int num=130000;
int koho=5;
int calc(vector<int>const& t,vector<vector<int>>& last_list){
  int res=0;
  vector<int> last(30,0);
  rep1(i,d){
    res+=s[i][t[i]];
    last[t[i]]=i;
    last_list[i]=last;
    int buf=0;
    rep1(j,26){
      buf+=c[j]*(i-last[j]);
    }
    res-=buf;
    //cout<<res<<"\n";
  }
  return res;
}
int change(int nd,int nq,int& res,vector<int>& t,vector<vector<int>>& last_list){
  int flag_t=false;
  int flag_q=false;
  int x=t[nd];
  t[nd]=0;
  res+=s[nd][nq];res-=s[nd][x];
  for(int i=nd;i<=d;++i){
    if(flag_t&&flag_q)break;
    if(t[i]==x||flag_t)flag_t=true;
    else{
      res+=c[x]*(i-last_list[i][x]);
      last_list[i][x]=last_list[i-1][x];
      res-=c[x]*(i-last_list[i][x]);
    }
    if(t[i]==nq||flag_q)flag_q=true;
    else{
      res+=c[nq]*(i-last_list[i][nq]);
      last_list[i][nq]=nd;
      res-=c[nq]*(i-last_list[i][nq]);
    }
  }
  t[nd]=nq;
  return res;
}
vector<int> greedy(int d,vector<vector<int>>& t_koho){
  vector<int> res(d+1,0);
  vector<int> last(30,0);
  rep1(i,d){
    int mx=-inf;
    int mx_ind=0;
    vector<P> kouho(26);
    rep1(j,26){
      int tmp=s[i][j];
      rep1(k,26){
        if(k==j)continue;
        tmp-=c[k]*(i-last[k]);
      }
      if(mx<tmp){
        mx=tmp;
        mx_ind=j;
      }
      kouho[j-1]={tmp,j};
    }
    sort(kouho.begin(),kouho.end());
    reverse(ALL(kouho));
    rep(x,koho){
      t_koho[i][x]=kouho[x].second;
    }
    last[mx_ind]=i;
    res[i]=mx_ind;
  }
  return res;
}
signed main(){
  cin>>d;
  rep1(i,26)cin>>c[i];
  rep1(i,d){
    rep1(j,26)cin>>s[i][j];
  }
  vector<vector<int>> t_koho(d+5,vector<int>(koho+5,0));
  vector<int> t=greedy(d,t_koho);
  vector<vector<int>> last_list(d+1,vector<int>(30,0));
  int res=calc(t,last_list);
  //cout<<res<<"\n";
  int param=1;
  rep(xx,num){
    random_device rand;
    mt19937 mt(rand());
    int dev=koho;
    if(xx>num/2)dev/=2;
    vector<int> nd(param);
    rep(i,param){
      nd[i]=mt()%d;
      if(nd[i]==0)++nd[i];
    }
    vector<int> bq(param);rep(i,param)bq[i]=t[nd[i]];
    int bval=res;
    rep(i,param){
      change(nd[i],t[nd[i]+1],res,t,last_list);
      change(nd[i]+1,bq[i],res,t,last_list);
    }
    int yakinamasi=mt()%100;
    //if(yakinamasi<(20-(xx*30)/num)&&res+res/10000>bval)continue;
    if(bval>res){
      rep(i,param){
        change(nd[i]+1,t[nd[i]],res,t,last_list);
        change(nd[i],bq[i],res,t,last_list);
      }
    }
  }
  rep1(i,d){
    cout<<t[i]<<"\n";
  }
  //cout<<res<<"\n";
  return 0;
}

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

int main() {
	int N;
	cin >> N;
	
	vector<int> d(N);
	for (int i = 0; i < N; ++i) {
		cin >> d.at(i);
	}
	
	vector<int> num(110);
	for (int i = 0; i < N; ++i) {
		num.at( d.at(i) )++;
	}
	
	int ans = 0;
	for (int i = 1; i <= 100; ++i) {
		if (num.at(i)) {
			++ans;
		}
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int D = sc.nextInt();
    int T = sc.nextInt();
    int S = sc.nextInt();
    
    if(S*T>=D) {
      System.out.println("Yes");
    }
    else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 35544
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int main() {
  vector<pair<int, int>> a(100);
  vector<bool> x(100);
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      int a_ij;
      cin >> a_ij;
      --a_ij;
      a.at(a_ij) = make_pair(i, j);
      x.at(a_ij) = true;
    }
  }

  int n;
  cin >> n;

  vector<vector<bool>> check(3, vector<bool>(3, false));
  for (int i = 0; i < n; ++i) {
    int b;
    cin >> b;
    --b;
    if (x.at(b))
      check.at(a.at(b).first).at(a.at(b).second) = true;
  }

  for (int i = 0; i < 3; ++i) {
    if (check.at(i).at(0) && check.at(i).at(1) && check.at(i).at(2)) {
      puts("Yes");
      return 0;
    }
    if (check.at(0).at(i) && check.at(1).at(i) && check.at(2).at(i)) {
      puts("Yes");
      return 0;
    }
  }
  if (check.at(0).at(0) && check.at(1).at(1) && check.at(2).at(2)) {
    puts("Yes");
    return 0;
  }
  if (check.at(2).at(0) && check.at(1).at(1) && check.at(0).at(2)) {
    puts("Yes");
    return 0;
  }
  puts("No");
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			var lrs = new LR[n];
			for (int i = 0; i < n; i++) {
				long[] lr = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
				lrs[i] = new LR(i, lr[0], lr[1]);
			}

			var lp = lrs.OrderByDescending(x => x.L).ToArray();
			var rp = lrs.OrderBy(x => x.R).ToArray();

			long ans = Calc(n, lp, rp, true);
			ans = Math.Max(ans, Calc(n, lp, rp, false));
			Console.WriteLine(ans);
		}

		private static long Calc(int n, LR[] lp, LR[] rp, bool turnLeft)
		{
			bool[] used = new bool[n];
			long ans = 0;
			long current = 0;
			int indexL = 0;
			int indexR = 0;
			for (int i = 0; i < n; i++) {
				LR next;
				if (turnLeft) {
					next = lp[indexL];
					while (used[next.Index]) {
						++indexL;
						next = lp[indexL];
					}

					turnLeft = false;
				} else {
					next = rp[indexR];
					while (used[next.Index]) {
						++indexR;
						next = rp[indexR];
					}

					turnLeft = true;
				}

				used[next.Index] = true;

				if (current > next.R) {
					ans += current - next.R;
					current = next.R;
				} else if (current < next.L) {
					ans += next.L - current;
					current = next.L;
				}
			}

			ans += Math.Abs(current);

			return ans;
		}
	}

	public struct LR
	{
		public LR(int index, long l, long r)
		{
			Index = index;
			L = l;
			R = r;
		}

		public int Index { get; set; }

		public long L { get; set; }
		public long R { get; set; }
	}
}


Measured memory_bytes: 34352
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	a := iSScan(n)
	a = append([]int{0}, a...)
	a = append(a, 0)
	d := make([]int, n+1)
	s := 0
	for i := 0; i <= n; i++ {
		d[i] = a[i+1] - a[i]
		s += abs(d[i])
	}
	for i := 1; i <= n; i++ {
		if d[i-1]*d[i] > 0 {
			fmt.Println(s)
		} else {
			fmt.Println(s - abs(d[i]) - abs(d[i-1]) + abs(a[i+1]-a[i-1]))
		}
	}
}


Measured memory_bytes: 5616
n,k = map(int, input().split())
a=list(map(int, input().split()))
cnt_bit=[0]*42
for ai in a:
  bit=1
  for i in range(0,42):
    if ai&bit==bit:
      cnt_bit[i]+=1
    bit*=2

ans=0
cur_k=0
bit=2**41
for cnt in cnt_bit[::-1]:
  if cur_k+bit<=k:
    if cnt>n-cnt:
      ans+=bit*cnt
    else:
      ans+=bit*(n-cnt)
      cur_k+=bit
  else:
    ans+=bit*cnt
  bit//=2
    
print(ans)



Measured memory_bytes: 14700
#include <iostream> 
#include <vector>
#include <cmath>
#include <string>
#include <sstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <cctype>
#include <climits>

using namespace std;

using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;

using ll = long long int;

#define mp(a,b) make_pair(a,b)

const int MOD = 1000 * 1000 * 1000 + 7;

bool res() {
	int n;
	cin >> n;
	if (!cin) return false;

	int mvotos = 0;
	map<string, int> m;

	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		if (m.find(s) != m.end()) ++m[s];
		else m.insert(mp(s,1));

		if (m[s] > mvotos) mvotos = m[s];
	}

	vector<string> sol;
	for (auto it = m.begin(); it != m.end(); ++it) {
		if (it->second == mvotos) sol.push_back(it->first);
	}

	for (int i = 0; i < sol.size(); ++i){
		cout << sol[i] << '\n';
	}

	return true;
}

int main() {
	while (res()) {}
	return 0;
}

Measured memory_bytes: 26868
package main

import (
	"fmt"
)

func main() {
	var n, w int
	fmt.Scanf("%d %d", &n, &w)
	items := make([]struct{ w, v int }, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d %d", &items[i].v, &items[i].w)
	}
	answer := findMaxSumDp(items, w)
	fmt.Println(answer)
}

func findMaxSumDp(items []struct{ w, v int }, limitWeight int) int {
	var dp [101][10001]int
	dp[0][0] = 0
	maxSum := 0
	for i := 0; i < len(items); i++ {
		for j := 0; j <= limitWeight; j++ {
			if j >= items[i].w {
				nextValue := dp[i][j-items[i].w] + items[i].v
				if nextValue > dp[i][j] {
					dp[i+1][j] = nextValue
					if maxSum < nextValue {
						maxSum = nextValue
					}
					continue
				}
			}
			dp[i+1][j] = dp[i][j]
		}
	}
	return maxSum
}


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

using namespace std;

int idx;
string str;

int solve(){
  int res = 0;
  idx++;
  if(str[idx] == '['){
    vector<int> v;
    while(str[idx] == '['){
      v.push_back(solve());
    }
    idx++;
    sort(v.begin(),v.end());
    for(int i = 0 ; i < (int)v.size()/2+1 ; i++){
      res += v[i];
    }
  }else{
    while(isdigit(str[idx])){
      res *= 10;
      res += str[idx]-'0';
      idx++;
    }
    idx++;
    res = res/2 + 1;
  }
  return res;
}

int main(){
  int Tc;
  cin >> Tc;
  while(Tc--){
    cin >> str;
    idx = 0;
    cout << solve() << endl;
  }
  return 0;
}

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

int m;

void solve(int n, bool d){
  
  if(n == m){
    cout << n << endl;
    return;
  }
  
  cout << n << " ";
  
  if(n == 9) solve(5, false);
  else if(!n || d) solve(n+1, true);
  else solve(n-1, false);
  
}

int main(){
  
  int n, l;

  cin >> l;
  
  while(l--){
    
    cin >> n >> m;
    
    if(n == 9 || (n < 6 && n > m)) solve(n, false);
    else solve(n, true);
        
  }
}

Measured memory_bytes: 1160
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

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

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

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
#define max_N 301

class Solve {
public:
    int N;
    int A = 0;
    int X = 0;
    int Y = 0;
    int Z = 0;
    double dp[max_N][max_N][max_N];

    void input() {
        cin >> N;

        rep(i, 0, N) {
            int tmp;
            cin >> tmp;
            A += 1;
            if (tmp == 1) {
                Z++;
            } else if (tmp == 2) {
                Y++;
            } else if (tmp == 3) {
                X++;
            }
        }

        rep(i, 0, max_N) {
            rep(j, 0, max_N) {
                rep(k, 0, max_N) {
                    dp[i][j][k] = -1;
                }
            }
        }
        dp[0][0][0] = 0;
    }

    double rec(int x, int y, int z) {
        if (x < 0 || y < 0 || z < 0) return 0.0;
        if (dp[x][y][z] != -1) return dp[x][y][z];

        double ret = 1.0 * A / (x + y + z);
        double kou = 1.0 / (x + y + z) * (x * rec(x - 1, y + 1, z) + y * rec(x, y - 1, z + 1) + z * rec(x, y, z - 1));
        ret += kou;

        return dp[x][y][z] = ret;
    }


    void solve() {
        input();
        double ans = rec(X, Y, Z);

        cout << fixed << setprecision(10);
        cout << ans << endl;

    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 213376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

/* modとる */
inline ll modu(ll a){
    return(a % mod + mod) % mod;
}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int power = 1;
    int N = in();
    REPS(i,N){
        power = modu(power*i);
    }
    cout << power << "\n";
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long total = 1;
		long input[] = new long[N];
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextLong();
			if (input[i] == 0) {
				total = 0;
				break;
			}
		}
		if (total != 0) {
			for (int i = 0; i < N; i++) {
				if (input[i] > 1000000000000000000L / total) {
					total = -1;
					break;
				}
				total *= input[i];
			}
		}
		System.out.println(total);
	}
}

Measured memory_bytes: 60828
#include <bits/stdc++.h>
using namespace std;
#define PI 3.141592653589793
#define MOD 1000000007
typedef long long ll;
typedef long double ld;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> x(N, 0);
    for(int i = 0; i < N; i++){
        cin >> x[i];
    } 
    
    ll ans = MOD;
    
    for(int i = 0; i < N - K + 1; i++){
        ll tmp_ans = abs(x[i]);
        tmp_ans += abs(x[i + K - 1] - x[i]);
        ll tmp_ans2 = abs(x[i + K - 1]);
        tmp_ans2 += abs(x[i + K - 1] - x[i]);
        tmp_ans = min(tmp_ans2, tmp_ans);
        ans = min(ans, tmp_ans);
    }
    cout << ans << endl;
}


Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  cin >> c;
  
  if (c == 'a') {
    cout << "vowel" << endl;
  }
  else if (c == 'e') {
    cout << "vowel" << endl;
  }
  else if (c == 'i') {
    cout << "vowel" << endl;
  }
  else if (c == 'o') {
    cout << "vowel" << endl;
  }
  else if (c == 'u') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define pragi(a,b) for(ll i = a;i<b;i++)
#define pragj(a,b) for(ll j = a;j<b;j++)
#define pragk(a,b) for(ll k = a;k>=b;k--)
#define all(v) (v.begin(),v.end())
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define MP make_pair
#define MT make_tuple
#define F first
#define S second
#define KAKA ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int mod = 1e9 + 7;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef long double ld;
typedef pair<int, int> pii;
//typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef pair<ll, ll> pll;

void Compute(ll n,ll k)
{
    KAKA
    vl v(n + 1);
    pragi(1,n + 1)
    {
        cin>>v[i];
    }
    ll start = 1;
    ll cnt = 0;
    vector<ll> vec;
    vector<bool> vis(n + 1,false);
    map<ll,ll> mp;
    vec.eb(start);
    vis[start] = true;
    mp[start] = 0;
    ll idx;
    ll siz;
    pragi(0,n + 1)
    {
        start = v[start];
        cnt++;
        if(!vis[start]){
        vec.eb(start);
        mp[start] = vec.size() - 1;
        vis[start] = true;}
        else
        {
            idx = mp[start];
            siz = i - idx + 1 ;
            break;
        }
        
    }
    if(k < idx) cout<<vec[k]<<"\n";
    else
    {
        cout<<vec[idx + ((k - idx)%siz)]<<"\n";
    }
    

}
int main()
{
    KAKA
    ll n,k;
    cin>>n>>k;
    Compute(n,k);
}

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

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

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)



Measured memory_bytes: 217868
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (a).size()
#define pb(a) push_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
using namespace std;
using pii = pair<int, int>;
constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr double EPS = 1e-10;

int N, K;
int a[5010];
int dp[5010];

bool check(int x) {
  fill(dp, dp+5010, 0);
  dp[0] = 1;
  rep(i, 0, N) if (i != x) repr(j, K, 0) {
    if (j+a[i] <= K) dp[j+a[i]] |= dp[j];
  }
  bool ok = 0;
  rep(i, max(0LL, K-a[x]), K) ok |= dp[i];
  return !ok;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> K;
  rep(i, 0, N) cin >> a[i];
  sort(a, a+N);
  int ok = -1, ng = N;
  while (ng-ok > 1) {
    int m = (ok+ng)/2;
    if (check(m)) ok = m;
    else ng = m;
  }
  cout << ng << endl;

  return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
int main(void){
	int n,i,j,a=0;
	scanf("%d",&n);
	for(i=0;2*i+1<=n;i++){
		int m=2*i+1,b=0;
		for(j=1;j<=m;j++){if(m%j==0){b++;}}
		if(b==8){a++;}
	}
	printf("%d",a);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define LL long long
const int MOD = 1E9+7;
using namespace std;
LL a[25]={1,2,4,5,8,10,13,14,18,21,26,28,33,36,40,41,46,50,57,60,68};
map<LL,LL> mp;
LL cal(LL x) {
    if(x<=20)
        return a[x];
    if(mp[x])
        return mp[x];
    if(x%2)
        return mp[x]=(2*cal(x/2)%MOD+cal(x/2-1)%MOD)%MOD;
    else
        return mp[x]=(2*cal(x/2-1)%MOD+cal(x/2)%MOD)%MOD;
}
int main() {
    LL n;
    scanf("%lld",&n);
    printf("%lld\n",cal(n));
    return 0;
}

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

using namespace std;

int main(){
  int n,tmp,min=INT_MAX,max=INT_MIN;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&tmp);
    if(max<tmp-min) max=tmp-min;
    if(min>tmp) min=tmp;
  }
  printf("%d\n",max);
  return 0;
}
  


Measured memory_bytes: 2764
#include<bits/stdc++.h>
#define re register
int p3[(1<<18)+1];
long long c[60][60];
bool pp[(1<<18)+1];
char f[387420489];
int main()
{
	re int n,k,S,T,x;
	re long long ans=0;
	scanf("%d%d%d%d",&n,&k,&S,&T);
	for(re int j=0;j<(1<<18);j++)pp[j]=pp[j>>1]^(j&1),p3[j]=p3[j>>1]*3+(j&1);
	for(re int i=1;i<=n;i++)scanf("%d",&x),f[p3[x]]++;
	c[0][0]=1;
	for(re int i=1;i<=n;i++)
	{
		c[i][0]=1;
		for(re int j=1;j<=i;j++)c[i][j]+=c[i-1][j-1]+c[i-1][j];
	}
	for(re int i=1;i<=n;i++)
	{
		for(re int j=1;j<k;j++)c[i][k]+=c[i][j];
	}
	for(re int i=0;i<=T;i++)if((i|T)==T&&((T^i)&S)==S)
	{//printf("*****%d\n",i);
		for(re int j=T^i;;j=(j-1)&(T^i))
		{
			if((j&S)==S)
			{
				if(i)f[p3[j]+2*p3[i]]=f[p3[j]+2*p3[i-(i&-i)]]+f[p3[j+(i&-i)]+2*p3[i-(i&-i)]];
			//	printf("****%d %d %d\n",i,j,f[p3[j]+2*p3[i]]);
				if(pp[i]^pp[S]^pp[T])ans-=c[f[p3[j]+2*p3[i]]][k];
				else ans+=c[f[p3[j]+2*p3[i]]][k];
			}
			if(!j)break;
		}
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 383512
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <double, double>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << 0; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const double eps = 1e-6;

double dist(pi A, pi B) {
    return sqrt((A.F - B.F) * (A.F - B.F) + (A.S - B.S) * (A.S - B.S));
}

bool good(double R, vector <pi> & p) {
    for (pi u : p) 
        for (pi v : p) {
            if (u == v)
                continue;
            if (2 * R <= dist(u, v))
                return false;
            double mx = (u.F + v.F) / 2, my = (u.S + v.S) / 2;
            double A = u.F - mx, B = u.S - my;
            double d = sqrt(A * A + B * B);
            double len = sqrt(R * R - dist(u, v) * dist(u, v) / 4);
            A *= len / d; B *= len / d;
            pi p1 = { mx - B, my + A }, p2 = { mx + B, my - A };
            bool ok1 = 1, ok2 = 1;
            for (pi w : p) {
                if (dist(p1, w) > R + eps)
                    ok1 = 0;
                if (dist(p2, w) > R + eps)
                    ok2 = 0;
            }
            if (ok1 || ok2)
                return true;
        }
    return false;
}

void solve() {
    int n;
    cin >> n;
    vector <pi> p(n);
    loop(i, n)
        cin >> p[i].F >> p[i].S;
    double l = 0, r = 3000;
    while (r - l > eps) {
        double m = (r + l) / 2;
        if (good(m, p))
            r = m;
        else
            l = m;
    }
    cout << fixed << setprecision(7) << (r + l) / 2;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3796
import java.util.*
import java.util.Collections.min

val da = kotlin.arrayOf(-1, 0, 1, 0)

fun main(args: Array<String>) {
    val (h, w, K) = readLine()!!.split(" ").map { it.toInt() }

    val f = Array(h + 2) {CharArray(w + 2) {'#'}}

    for(i in 1..h) {
        f[i] = "#${readLine()!!}#".toCharArray()
    }

    val si = f.indexOfFirst { it.contains('S') }
    val sj = f[si].indexOf('S')

    f[si][sj] = ' '

    val v = ArrayList<Pair<Int, Int>>()
    val Q = ArrayDeque<Triple<Int, Int, Int>>()
    Q.addLast(Triple(si, sj, 0))
    v.add(Pair(si, sj))

    while(Q.isNotEmpty()) {
        val p = Q.first
        Q.pop()
        if (p.third == K) {
            continue
        }

        for(i in 0..3) {
            val np = Triple(p.first + da[i], p.second + da[3 - i], p.third + 1)
            if (f[np.first][np.second] != '.') {
                continue
            }
            f[np.first][np.second] = ' '
            v.add(Pair(np.first, np.second))
            Q.addLast(np)
        }
    }

    var mn = 1000
    for (p in v) {
        mn = min(arrayListOf(mn, p.first - 1, h - p.first, p.second - 1, w - p.second))
    }
    println((mn + K - 1) / K + 1)
}


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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

typedef pair<ll, ll> P;

// 移動を簡単に表現するための配列
int dy[] = {1, 0, 0, -1};
int dx[] = {0, 1, -1, 0};

int main() {
    int n; cin >> n;
    int ans = 800 * n;
    ans -= (n/15)*200;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
s = [input() for _ in range(h)]

nums = [[0] * w for _ in range(h)]
ans = 0

for i in range(h):
    tmp = 0
    head = 0
    for j in range(w):
        if(s[i][j] == '#'):
            for k in range(head,j):
                nums[i][k] += tmp
            tmp = 0
            head = j+1
        else:
            tmp += 1
            if(j == w-1):
                for k in range(head,j+1):
                    nums[i][k] += tmp

for j in range(w):
    tmp = 0
    head = 0
    for i in range(h):
        if(s[i][j] == '#'):
            for k in range(head,i):
                nums[k][j] += tmp -1
            tmp = 0
            head = i+1
        else:
            tmp += 1
            if(i == h-1):
                for k in range(head,i+1):
                    nums[k][j] += tmp -1

for i in range(h):
    ans = max(ans, max(nums[i]))

print(ans)

Measured memory_bytes: 99928
package main

import (
	"fmt"
	"math"
)

func main() {
	var d, n int
	fmt.Scan(&d, &n)

	min := math.Pow(100, float64(d))
	if n <= 99 {
		fmt.Println(int(min) * n)
	} else {
		fmt.Println(int(min) * 101)
	}
}


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

int n;
int main(){
    std::cin>>n;
    long long ans=0;
    for(int a=1;a<=n;++a){
        for(int b=1;b*a<n;++b){
            ans++;
        }
    }
    std::cout<<ans<<'\n';
    return 0;
}

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


int main(){
    char a;
    bool alp[26];
    
    for(int i=0;i<26;i++)alp[i]=true;
    while(cin >> a){
        alp[a-'a']=false;
    }
    
    for(char i='a';i<='z';i++){
        if(alp[i-'a']){
            cout << i << endl;
            return 0;
        }
    }
    
    cout << "None" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll a,b,c,d,t,n,k,ct=0,r;
    string s;
    vector<ll>v;
    set<ll>st;
    map<ll,ll>mp;
    cin>>n>>k;
    for(ll i=0;i<k;i++)
    {
       cin>>d;
       for(ll j=0;j<d;j++)
       {
           cin>>a;
           mp[a]++;
       }
    }
    ct=0;
    for(ll i=1;i<=n;i++)
    {
        if(mp[i]==0) ct++;
    }
    cout<<ct<<endl;
}




Measured memory_bytes: 3632
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
  if a < K:
    B.append(a)

N = len(B)
B.sort(reverse=True)
check = [True] + [False]*N
dp = [[False]*(K+1) for i in range(N+1)]
dp[0][0] = True
for i, b in enumerate(B, 1):
  for j in range(K+1):
    dp[i][j] = dp[i-1][j]
    if K-b <= j <= K - 1 and dp[i][j]:
      check[i] = True
    if j >= b and dp[i-1][j-b]:
      dp[i][j] = True

ans = 0
for i in range(N, -1, -1):
  if check[i]:
    break
  ans += 1

print(ans)

Measured memory_bytes: 230792
formula = gets
arr = formula.split(" ")
while arr.size != 1
	(arr.size).times do |i|
		if arr[i] == "+" and ((arr[i - 1] != "-" or arr[i - 1] != "*") and (arr[i - 2] != "-" or arr[i - 2] != "*"))
			arr[i] = arr[i - 2].to_i + arr[i - 1].to_i
			arr.delete_at(i - 1)
			arr.delete_at(i - 2)
			break
		elsif arr[i] == "-" and ((arr[i - 1] != "+" or arr[i - 1] != "*") and (arr[i - 2] != "+" or arr[i - 2] != "*"))
			arr[i] = arr[i - 2].to_i - arr[i - 1].to_i
			arr.delete_at(i - 1)
			arr.delete_at(i - 2)
			break
		elsif arr[i] == "*" and ((arr[i - 1] != "-" or arr[i - 1] != "+") and (arr[i - 2] != "-" or arr[i - 2] != "+"))
			arr[i] = arr[i - 2].to_i * arr[i - 1].to_i
			arr.delete_at(i - 1)
			arr.delete_at(i - 2)
			break
		end
	end
end
puts arr[0]

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    vec.at(i) = a;
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  int A, B, i, j;
  A = 0;
  B = 0;
  i = 0;
  j = 1;
  while (i < N) {
    A += vec.at(i);
    i += 2;
  }
  while (j < N) {
    B += vec.at(j);
    j += 2;
  }
  cout << A - B << endl;
}


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

typedef long long LL;
int main() {
    string s; cin>>s;
    int len = s.size();
    int ans = 0, sum = 0;
    for(int i=0; i<len; i++) {
        if(i&1) {
            if(s[i] == '0') sum++;
        }
        else {
            if(s[i] == '1') sum++;
        }
    }
    ans = sum;
    sum = 0;
    for(int i=0; i<len; i++) {
        if(i&1) {
            if(s[i] == '1') sum++;
        }
        else {
            if(s[i] == '0') sum++;
        }
    }
    ans = min(ans, sum);
    cout<<ans<<endl;
    return 0;
}


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

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    int w,h,c;
    cin>>w>>h>>c;
    if(w<h)swap(w,h);
    cout<<w*h/gcd(w,h)/gcd(w,h)*c<<endl;
    
    return 0;
}


Measured memory_bytes: 3096
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();
            var k = cin.nextInt();
            var a = cin.ArrayLong(n);

            Array.Sort(a);

            var ans = long.MaxValue;
            for (int i = 0; i <= n-k; i++)
            {
                var d = Math.Abs(a[i] - a[i + k-1]);
                ans = Math.Min(d, ans);
            }
            
            Console.WriteLine(ans);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 15956
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <set>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <cassert>

using namespace std;
using ll = long long;

#define nl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define trav(x) for(auto& i: x)

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

	string s;
	cin >> s;
	if(s == "Sunny") {
		cout << "Cloudy";
	} else if(s == "Cloudy") {
		cout << "Rainy";
	} else {
		cout << "Sunny";
	}
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
 
int compareInt(const void* a, const void* b)
{
    int aNum = *(int*)a;
    int bNum = *(int*)b;

    return aNum - bNum;
}

int main(void){
  int n, m, sum=0;
  scanf("%d %d", &n, &m);
  int x[m], c[m-1];
  for(int i=0; i<m; i++){
    scanf("%d", &x[i]);
  }
  qsort(x, m, sizeof(int), compareInt);
  for(int j=0;j<m-1;j++){
    c[j] = x[j+1]-x[j];
  }
  qsort(c, m-1, sizeof(int), compareInt);
  for(int k = 0; k< m-n; k++){
    sum+=c[k];
  }
  printf("%d", sum);
  return 0;
}

Measured memory_bytes: 2908
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=998244353
from collections import deque
########################################################
a,b,c,x,y=INPUT()
#cost of 1 pi is a+b or 2*c
if 2*c<(a+b):
    cost=2*c*min(x,y)
    if x>y:
        r=x-y
        if 2*c>a:
            cost+=r*a
        else:
            cost+=r*(2*c)
        print(cost)
    else:
        r=y-x
        if 2*c>b:
            cost+=r*b
        else:
            cost+=r*(2*c)
        print(cost)
else:
    print(x*a+y*b)


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

using namespace std;

struct person { 
	person *right;
	bool isMenjyo = true;
	person *left;
};

int main(){
	int n,m,q;
	cin >> n >> m >> q;
	person p[200000];
	for(int i=0;i<n;i++){
		if(i==0) p[i].right = &p[n-1];
		else p[i].right = &p[i-1];
		
		if(i==n-1) p[i].left = &p[0];
		else p[i].left = &p[i+1];
	}
	person* current = &p[0];
	for(int i=0;i<m;i++){
		int a;
		cin >> a;
		if(a%2==0){
			// even
			for(int i=0;i<a;i++){
				current = current->left;
			}
		} else {
			// odd
			for(int i=0;i<a;i++){
				current = current->right;
			}
		}
		current->isMenjyo = false;
		current->right->left = current->left;
		current->left->right = current->right;
		current = current->left;
	}
	for(int i=0;i<q;i++){
		int q;
		cin >> q;
		if(p[q].isMenjyo){
			cout << 1 << endl;
		} else {
			cout << 0 << endl;
		}
	}
	
	return 0;
}

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

int main() {
	int a,b;
	cin >> a>>b;
	int c;
	c=a+b;
	if(c%2==0){
		cout << c/2<<endl;
	}
	else{
		cout <<"IMPOSSIBLE"<<endl;
	}
}

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

int main() {
  int N, K;
  string S;
  
  cin >> N >> S >> K;
  
  char tgt = S.at(K - 1);
  
  for (int i = 0; i < S.size(); i++) {
    char c = S.at(i);
    if (c != tgt) {
      S.at(i) = '*';
    }
  }
  
  cout << S << endl;
}


Measured memory_bytes: 256