akhauriyash/Code-Regression huggingface dataset:
# https://beta.atcoder.jp/contests/abc095/tasks/abc095_b


def inp(): return map(int, input().split())


n, x = inp()

most_cheap = 1001
all_one_cost = 0

for i in range(n):
    cost = int(input())
    if cost < most_cheap:
        most_cheap = cost
    all_one_cost += cost


rest_x = x - all_one_cost
if rest_x > 0:
    print(str(n + rest_x // most_cheap))
else:
    print(str(n))


Measured memory_bytes: 3060
#include <iostream>
#include <string>

using namespace std;

int main(void){
	string s;
	cin >> s;
	int len = s.size();
	int part = 1;
	char tag = s.front();
	for(int i=1;i<len;i++){
		if(s[i] != tag){
			tag = s[i];
			part++;
		}
	}
	cout << part-1 << endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
const ll mod = 1000000007;

ll dp[101][4010];
long long ruijo(long long x,ll n){
	long long p,ans;
	if(n==0)return 1;
	if(n==1)return x;
	if(n%2){
		p = ruijo(x,n/2);
		ans = (x*p)%mod;
		ans = (ans*p)%mod;
		return ans;
	}else{
		p = ruijo(x,n/2);
		ans = (p*p)%mod;
		return ans;
	}
}
ll n,k;

ll element_count(ll x,ll y,ll z){
	ll a = max((ll)0,y*z-x);
	ll b = min(y,y*(z+1)-1-x);
	if(a>b)return (ll)0;
	else return b-a+1;
}


int main(){
	cin >> n >> k;
	for(ll i=n;i>k;i--){
		dp[i][0] = ruijo(k+1,(n-i+1));
	}
	dp[k][0] = k * ruijo(k+1,n-k);
	dp[k][1] = 1 * ruijo(k+1,n-k);
	for(ll i = k-1;i>=1;i--){
		ll p;
		if(i==1){
			p=4000;
		}
		if(i==2){
			p = 3000;
		}
		if(i==3){
			p = 2000;
		}
		if(i>=4){
			p = 1000;
		}
		for(ll j=0;j<p;j++){
			if(j==0){
				dp[i][0] = k*dp[i+1][0]%mod;
			}else{
				for(ll m=0;m<=j;m++){
					if(j!=m){
						dp[i][j] = (dp[i][j] + element_count(m,i,j-m)*dp[i+1][m])%mod;
					}else{
						dp[i][j] = (dp[i][j] + (k-i)*dp[i+1][m])%mod;
						if(i-m-1>=0){
							dp[i][j] = (dp[i][j] + (i-m)*dp[i+1][m])%mod;
						}
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<4000;i++){
		ans = (ans + i*dp[1][i])%mod;
	}
	ll w = (n * ruijo(k+1,n-1) ) %mod;
	ll s = ((k*(k+1))/2)%mod;
	s = (s*w)%mod;
	cout << (s - ans+mod)%mod << endl;
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
typedef long long ll;
const ll mod = 1e9+7;

 
int main(){
	string s1,s2;
	cin >> s1 >> s2;
	int cnt = 0;
	for(int i = 0; i < s1.length(); i++){
		if(s1[i] != s2[i])
			cnt++;
	}
	cout << cnt << endl;
    return 0; 
}

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


#define vt vector
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define ar array
#define inf() ifstream cin("d.txt")
#define onf() ofstream cout("test.txt")
#define mod 1000000007
#define pb push_back
#define endl cout<<"\n";
#define prt1(a) cout<<a<<" "
#define prt2(a,b) cout<<a<<" "<<b<<" "
#define prt3(a,b,c) cout<<a<<" "<<b<<" "<<c<<" "
#define in(a) cin>>a
#define inn(a,b) cin>>a>>b
#define innn(a,b,c) cin>>a>>b>>c 
#define rep(i,st,end) for(int i=st;i<end;i++)
#define repv(i,st,end) for( i=st;i>=end;i--)
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define TEST ll tc;cin>>tc;while(tc--)
#define EACH(x, a) for (auto& x: a)

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
    cin >> x;
}
void read(double& d) {
    string t;
    read(t);
    d=stod(t);
}
void read(long double& d) {
    string t;
    read(t);
    d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class A> void read(vt<A>& x) {
    EACH(a, x)
        read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
    EACH(a, x)
        read(a);
}
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a <<"\n";
    err(++it, args...);
}
ll check(vt<ll>&v, ll b)
{
    ll ans= 0,i=1;
    EACH(it,v)
    ans+=abs(it-(b+i)),i++;
    return ans ;
}


void solve()
{
    ll n;
    read(n);
    vt<ll>v(n);
    read(v);
    rep(i,0,n)
    v[i]-=(i+1);
    sort(all(v));
    int b = v[(n - 1) / 2];
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += abs(v[i]-b);
    }
    cout<<ans;
}

 int main()
 {
    fio;
    ll k = 1;
    ll tc = 1;
    // cin>>tc;
    while(tc--){
       // cout<<"Case #"<<k<<": ";k++;
        solve();
        endl;
    }
    
 }




Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
std::vector<int> v;
int main() {
	int n,k;
	cin >> n >> k;
	std::vector<int> best(n,0);
	for(int i=0;i<n;i++){
	     int x;
	     cin >> x;
	     v.push_back(x);
	}
     best[0]=0;
     best[1]=abs(v[0]-v[1]);
     for(int i=2;i<n;i++){
          int mina = 9999999999;
          for(int g = 1;g<=k;g++){
               if((i-g)<0){
                    break;
               }
               mina = min(mina,(abs(v[i]-v[i-g])+best[i-g]));
               
               // cout << ((abs(v[i]-v[i-g])+best[i-g])) << " ";
          }
          best[i] = mina;
          // cout << endl;
          
     }
     // for(auto x:best){
     //      cout << x << endl;
     // }
     cout << best[n-1];
	return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i < n - 1) {
            cout << " ";
        }
        cout << a[i];
    }
    cout << '\n';
    return 0;
}


Measured memory_bytes: 3160
#include<stdio.h>
main(n,m,i,o,r,t)
{
	for(;~scanf("%d",&n)&&n!=0;)
	{
		for(m=t=r=0;m<12;m++)
		{
			scanf("%d%d",&i,&o);
			r=!r&&(t+=i-o)>=n?printf("%d\n",m+1):r;
		}
		!r?puts("NA"):r;
	}
	exit(0);
}

Measured memory_bytes: 612
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;
int a,b,i,n,c,ans;
vector<int> hight(1000);

int main(){
  cin >> a >> b;
  for(i=1;i<1000;i++){
    n += i;
    hight.at(i) += n;
  }
  c = b - a;
  ans = hight.at(c) - b;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
/*|In The Name of Allah|*/

#include <bits/stdc++.h>

using namespace std;

int n;
int A;
int B;
int AA[45];
int BB[45];
int cost[45];
int dp[45][405][405];

int go(int idx , int a , int b){
    if(a * B == A * b && b != 0 && a != 0)
       return 0;
    if(idx > n)
        return 1e5;
    if(dp[idx][a][b] != -1)
        return dp[idx][a][b];
    int best = go(idx + 1 , a , b);
    best = min(best , cost[idx] + go(idx + 1 , a + AA[idx] , b + BB[idx]));
    return dp[idx][a][b] = best;
}

int main(){
    scanf("%d%d%d" , &n , &A , &B);
    memset(dp , -1 , sizeof dp);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d" , &AA[i] , &BB[i] , &cost[i]);
    }
    int ans = go(1 , 0 , 0);
    if(ans >= 1e5){
        puts("-1");
        return 0;
    }
    printf("%d\n" , ans);
}


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


ll H, W;

ll calc(ll a, ll b, ll c){
  ll mi = min(a, b); mi = min(mi, c);
  ll ma = max(a, b); ma = max(ma, c);
  return ma - mi;
}

ll divi(ll h, ll w){
  ll ans = (ll)1e9;
  if(h >= 3){
    ans = min(ans, (h%3?w:0));
  }
  
  ll a = (w / 3) * h;
  ll b = (w - (a / h)) * (h / 2);
  
  ans = min(ans, calc(a, b, h * w - a - b));
  
  a += h;
  b = (w - (a / h)) * (h / 2);
  ans = min(ans, calc(a, b, h * w - a - b));
  return ans;
}

int main(){
  cin >> H >> W;
  ll ans = 1e9;
  ans = min(ans, divi(H, W));
  ans = min(ans, divi(W, H));
  cout << ans<< endl;
}


Measured memory_bytes: 256
Scanf.scanf "%d %d %d" (fun n m k ->
    let rec loop_a a =
        let rec loop_b b =
            if b > n then loop_a (a + 1) else
                if a * n + b * m - 2 * a * b = k then true else loop_b (b + 1)
        in
        if a > m then false else
            loop_b 0
    in
    print_endline @@ if loop_a 0 then "Yes" else "No"
)

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

//.define
// #define FILE_IN_OUT
#define RET(_x)                       return cout << (_x) << '\n', 0;
#define all(_obj)                     (_obj).begin(), (_obj).end()
#define loop(_n)                      for (int i = 0; i < (_n); ++i)
#define CeilDiv(_dividend, _divider)  (((_dividend) - 1LL + (_divider)) / (_divider))
#define sz(_obj)                      static_cast<int>((_obj).size())
#ifdef SHJ_LOCAL
#define debug(_x)                     std::cerr << (#_x) << " = " << (_x) << '\n' << std::flush;
#else
#define debug(_x)                     {}
#endif
#define endl "\n"
template<typename Tp>
inline void outarr(Tp _begin, Tp _end, const char* _delim = " ") {
    for (Tp current = _begin; current != _end; ++current) {
        std::cout << *current << _delim;
    }
    std::cout << '\n';
}

//.constant
using ll  = long long;
using pii = std::pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = static_cast<const int>(1e9 + 7);

//.data
struct Camel {
    int K;
    int L;
    int R;
};

bool operator<(const Camel& lhs, const Camel& rhs) {
    return abs(lhs.R - lhs.L) < abs(rhs.R - rhs.L);
}

//.code
int main() {
#ifdef FILE_IN_OUT
    std::ifstream cin ("input.txt",  std::ios::in);
    std::ofstream cout("output.txt", std::ios::out);
#else
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

    int n;
    cin >> n;
    vector<int> ans(7000000, 0);
    for (int x = 1; x < 100; ++x) {
        for (int y = 1; y < 100; ++y) {
            for (int z = 1; z < 100; ++z) {
                ++ans[x * x + y * y + z * z + x * z + x * y + z * y];
            }
        }
    }
    loop(n) {
        cout << ans[i + 1] << endl;
    }

#ifdef FILE_IN_OUT
    cin.close();
    cout.close();
#endif
    return 0;
}

Measured memory_bytes: 30576
n = int(input())
cmin = [114514 for i in range(26)]

for i in range(n):
    s = input()
    for j in range(26):
        cmin[j] = min(cmin[j], s.count(chr(ord('a') + j)))

for i in range(26):
    print(chr(ord('a') + i) * cmin[i], end='')

print()


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

int A[1010];
int B[1010];
int C[1010];
int dp[1010][1<<12];

void solve() {
    int N, M; cin >> N >> M;
    REP(i, M) {
        cin >> A[i] >> B[i];
        REP(j, B[i]) {
            int x; cin >> x;
            C[i] |= (1 << (x - 1));
        }
    }

    REP(i, M+1) REP(j, 1 << N) dp[i][j] = 1 << 30;
    dp[0][0] = 0;

    REP(i, M) REP(j, 1 << N) if (dp[i][j] < (1 << 30)) {
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        dp[i+1][j|C[i]] = min(dp[i+1][j|C[i]], dp[i][j] + A[i]);
    }

    cout << (dp[M][(1<<N)-1] == 1<<30 ? -1 : dp[M][(1<<N)-1]) << endl;
}

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


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

int main(){
     int N,A,B;
     int tmp;
     int x=0,y=0,z=0;
     cin >> N >> A >> B;
     for (int i=0; i<N; i++){
        cin >> tmp;
        if (tmp <= A){
            x++;
        }else if (tmp <= B){
            y++; 
        }else{
            z++;
        }
     }
     cout << min(min(x,y),z) << endl;
     return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll          long long
#define mp	    make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define MOD        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define N	 100
char A[N][N];
int dx[] = {1,-1,0,0,1,1,-1,-1};
int dy[] = {0,0,1,-1,1,-1,1,-1};
void check(int x, int y){
	int cnt = 0;
	rep(i,0,8)
		if(A[x+dx[i]][y+dy[i]] == '#')
			cnt++;
	A[x][y] = cnt + '0';
}
void solve(){
	int h,w;
	cin>>h>>w;
	memset(A, -1, sizeof(A));
	rep(i,1,h+1)
		rep(j,1,w+1)
			cin>>A[i][j];
	rep(i,1,h+1)
		rep(j,1,w+1)
			if(A[i][j]=='.')
				check(i, j);
	rep(i,1,h+1){
		rep(j,1,w+1)
			cout<<A[i][j];
		cout<<endl;
	}
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t =1;
//     cin>>t;
    while(t--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 256
import numpy as np

N, K = map(int, input().split())
S = np.array([int(x) for x in input()] + [2])

blocks = [] # 同じ数の塊
seq = 1
for i in range(N):
    if S[i+1] == S[i]:
        seq += 1
    else:
        blocks.append(seq)
        seq = 1
blocks = np.array(blocks)

answer = blocks[:2*K].sum()

start = 0 if S[0] == 1 else 1
for i in range(start, len(blocks), 2):
    answer = max(answer, blocks[i:i+(2*K+1)].sum())

print(answer)

Measured memory_bytes: 16760
import java.util.*;
 
public class Main {
    Scanner sc = new Scanner(System.in);
 
    public static void main(String[] args) {
    	new Main(); 
    }
 
    public Main() {
    	new A().doIt();
    }
    class A{
    	void doIt(){
    		while(true){
    			boolean map[][] = new boolean[21][21];
    			int n = sc.nextInt();
    			if(n == 0)break;
    			int x,y;
    			for(int i = 0;i < n;i++){
    				x = sc.nextInt();y = sc.nextInt();
    				map[y][x] = true;
    			}
    			x = 10;y = 10;
    			int n2 = sc.nextInt();
    			int cnt = 0;
    			if(map[y][x])cnt++;
    			for(int i = 0;i < n2;i++){
    				String s = sc.next();
    				int num = sc.nextInt();
    				if(s.equals("N")){
    					for(int j = 0;j < num;j++){
    						if(map[++y][x]){
    							cnt++;
    							map[y][x] = false;
    						}
    					}
    				}else if(s.equals("E")){
    					for(int j = 0;j < num;j++){
    						if(map[y][++x]){
    							cnt++;
    							map[y][x] = false;
    						}
    					}
    				}else if(s.equals("S")){
    					for(int j = 0;j < num;j++){
    						if(map[--y][x]){
    							cnt++;
    							map[y][x] = false;
    						}
    					}
    				}else{
    					for(int j = 0;j < num;j++){
    						if(map[y][--x]){
    							cnt++;
    							map[y][x] = false;
    						}
    					}
    				}
//    				System.out.println(cnt);
    			}
    			if(cnt == n)System.out.println("Yes");
    			else System.out.println("No");
    		}
    	}
    }
}

Measured memory_bytes: 41540
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> k(m),p(m);
    vector<vector<int>> s(m,vector<int>(n));
    rep(i,m){
        cin>>k[i];
        rep(j,k[i]){
            cin>>s[i][j];        
        }
    }
    rep(i,m) cin>>p[i];
    int cnt2 =0;
    for (int bit =0; bit<(1<<n);bit++){
        bitset<10> sw(bit);
        bool ok =true;
        rep(i,m){
            int cnt =0;
            rep(j,k[i]){
                if (sw[s[i][j]-1]==1) cnt++;
            }
            if (cnt%2 != p[i]) ok =false;
        }
        if(ok) cnt2++;
    }
    cout << cnt2 <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include<math.h>
#include<string.h>
using namespace std;
#define MAX 300005
#define MOD 1000000007
#define INF 1000000000000000000
#define EPS 0.0000000001
#define CHAINS 18
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
int main()
{
    int N,i;
    scanf("%d",&N);
    long long add=1,sub=1,both=1;
    for(i=1;i<=N;i++)
    {
        add=(add*10)%MOD;
        sub=(sub*9)%MOD;
        both=(both*8)%MOD;
    }
    long long ans=(add-sub*2+both)%MOD;
    ans=(ans+MOD)%MOD;
    printf("%lld",ans);
    return 0;
}


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

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a, b) a = min((a),(b))
#define CHMAX(a, b) a = max((a),(b))
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main() {
    int x, a, b;
    cin >> x >> a >> b;
    auto ans = "dangerous";
    if (a >= b) {
        ans = "delicious";
    } else if (a + x >= b) {
        ans = "safe";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
set<int> S[maxn];
int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= k; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		S[y].insert(x);
	}
	for (int i = 1; i <= m; i++)
		S[i].insert(n + 1);
	int res = *(S[1].begin());
	int cur_x = 1, cur_y = 1;
	while (true)
	{
		if (S[cur_y].find(cur_x + 1) != S[cur_y].end()) break;
		if (cur_y == m) break;
		cur_x++;
		if (S[cur_y + 1].find(cur_x) != S[cur_y + 1].end()) continue;
		cur_y++;
		res = min(res, *(S[cur_y].upper_bound(cur_x)));
	}
	printf("%d\n", res - 1);
	return 0;
}

Measured memory_bytes: 28416
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
ll dfs(int n, int m, int k){
  if(n == 0) return max(1, k);
  ll res = 0;
  for(int i = 1; i <= m; i++){
    res += dfs(n-1, m, k + i);
  }
  return res;
}
int main(){
  int n,m,k;
  while(cin>>n>>m>>k && n){
    ll sum = dfs(n, m, -k);
    double ans = (double)sum/pow((double)m, (double)n);
    printf("%.8lf\n",ans);
  }
  return 0;
}

Measured memory_bytes: 924
import numpy as np

def solve(N, edge):
    x_arr = np.zeros(N).astype(int)
    visited = np.zeros(N).astype(bool)
    
    isValid = True
    for n in range(N):
        if not(visited[n]):
#            print("start with {}".format(n))
            stack = []
            stack.append((n, 0))
            while len(stack) > 0:
#                print(stack)
                i, x = stack[-1]
                stack.pop()
                
                if visited[i] and x_arr[i] != x: # if already visited
#                    print("err", i, x, x_arr[i])
                    isValid = False
                elif not(visited[i]): # if first time to visit
                    visited[i] = True
                    x_arr[i] = x
                    for j, c in edge[i]:
                        stack.append((j, x + c))
    return isValid
  
N, M = [int(_) for _ in input().split()]
edge = [[] for _ in range(N)]

for _ in range(M):
    left, right, dist = [int(_) for _ in input().split()]
    left -= 1
    right -= 1
    edge[left].append((right, dist))
    edge[right].append((left, -dist))
    
if solve(N, edge):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 89464
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-8;

string cat_string (const string& lhs,const string& rhs){

  for(int smoothing = min(lhs.size(),rhs.size());
      smoothing >= 0 ;
      smoothing--){
    string front = lhs.substr(lhs.size()-smoothing,smoothing);
    string rear = rhs.substr(0,smoothing);
    
    if(front == rear){
      return rhs.substr(smoothing,rhs.size()-smoothing);
    }
  }
  return rhs;
}

string compute_short_string(const string& lhs,const string& rhs){
  return (lhs.size() < rhs.size()) ? lhs : rhs;
}

int main(){
  int n;
  while(~scanf("%d",&n)){
    if(n==0) break;

    vector<int> order;
    for(int i=0;i<n;i++){
      order.push_back(i);
    }

    vector<string> tmp_constituents;

    for(int i=0;i<n;i++){
      string str;
      cin >> str;
      tmp_constituents.push_back(str);
    }
    
    bool can_use[n];
    memset(can_use,true,sizeof(can_use));

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(i==j) continue;

	if(tmp_constituents[i].size() <= tmp_constituents[j].size()){
	  for(int idx=0;idx<tmp_constituents[j].size();idx++){
	    if(tmp_constituents[j].size() < idx+tmp_constituents[i].size()) break;
	    string candidate = tmp_constituents[j].substr(idx,tmp_constituents[i].size());
      
	    if(candidate == tmp_constituents[i]){
	      can_use[i] = false;
	    }
	  }
	}
      }
    }
    vector<string> constituents;
    for(int i=0;i<tmp_constituents.size();i++){
      if(can_use[i]) constituents.push_back(tmp_constituents[i]);
    }

    n = constituents.size();

    string edge[n][n];
    for(int i=0;i<constituents.size();i++){
      for(int j=0;j<constituents.size();j++){
	edge[i][j] = cat_string(constituents[i],constituents[j]);
      }
    }

    string dp[n][1<<n];

    for(int i=0;i<n;i++) {
      dp[i][(1<<i)] = constituents[i];
    }

    for(int S=0;S<=(1<<n)-1;S++){
      for(int from=0;from < n; from++){
	if((S & (1<<from)) == 0) continue;	     
	for(int to=0;to < n; to++){
	  if(from == to) continue;
	  if(S & (1<<to)) continue;
	  if(dp[to][S | (1<<to)] == ""){
	    dp[to][S | (1<<to)]
	      =	dp[from][S] + edge[from][to];
	  }
	  else{
	    dp[to][S | (1<<to)]
	      = compute_short_string(dp[from][S] + edge[from][to],dp[to][S | (1<<to)]);
	  }
	}
      }
    }

    string res = dp[0][(1<<n)-1];

    for(int i=0;i<n;i++){
      res = compute_short_string(res,dp[i][(1<<n) - 1]);
    }
    cout << res.size() << endl;
  }
}

Measured memory_bytes: 30772
#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--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int l = 0, r = 0, c = 0;

    rep(i, n){
        if (s[i] == '(') l++;
        else r++;
        if (l < r) c++, l++;
    }
    rep(i, c) cout << '(';
    cout << s;
    rep(i, l - r) cout << ')';
    cout << endl;

    return 0;
}


Measured memory_bytes: 3596
# -*- coding: utf-8 -*-


def main():
    from math import sqrt

    n, m = map(int, input().split())
    ans = 1

    # See:
    # https://www.youtube.com/watch?v=CURWJ1Dr44A
    for k in range(1, int(sqrt(m)) + 1):
        if m % k != 0:
            continue

        if k * n <= m:
            ans = max(ans, k)

        b = m // k

        if b * n <= m:
            ans = max(ans, b)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main(){
    int n,d;
    cin >> n >> d;
    int max=n,min=1,count=0;
    while(1){
        ++count;
        max -= d*2+1;
        if(max<min) break;
    }
    cout << count << endl;
    return 0;
}


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

int main()
{
        string s;
        while(cin>>s)
        {
           int ans=0;
            for(int i=0;i<=s.size();i++)
              if(s[i]=='0')
                  ans++;
           int  sum;
           if(ans<s.size()-ans)
               sum=ans;
           else
               sum=s.size()-ans;
              cout<<sum*2<<endl;
        }
        return 0;
}

Measured memory_bytes: 512
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;

int main(){

    //freopen("planting.in", "r", stdin);
    //freopen("planting.out", "w", stdout);

    string s;
    cin >> s;
    int cnt = 0, best = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'R') cnt++;
        else cnt = 0;
        best = max(best, cnt);
    }
    cout << best;
}


Measured memory_bytes: 3620
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
	vector<ll> v;
	rep(i,0,3){
		ll a;
		cin>>a;
		v.pb(a);
	}
	sort(all(v));
	if(v[0]==v[2]){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

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

int n,v[Nmax];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    n *= 2;
    for (int i=1;i<=n;i++) cin >> v[i];
    sort(v+1,v+n+1);
    ll ans = 0;
    for (int i=1;i<=n;i+=2) ans += v[i];

    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
fun main(){
    var n = readLine()!!.toInt()

    n = (n % 100) % 10
    if(n in listOf(2,4,5,7,9)) println("hon")
    if(n in listOf(0,1,6,8)) println("pon")
    if(n in listOf(3)) println("bon")
}

Measured memory_bytes: 37964
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  int A,B;
  cin >> A >> B;
  int x = ceil(max(100*A/8.0, 10.0*B));
  if (x >= min(100*(A+1)/8.0, 10.0*(B+1))) x = -1;
  cout << x << endl;
  return 0;
}

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

#define fordebug int hoge;cin>>hoge;

#define DEKAI 1000000007
#define floot10 cout<<fixed<<setprecision(15)
#define all(v) v.begin(),v.end()
double PI = acos(-1);

signed main(){
  int n,a,b,c,d;
  cin>>n>>a>>b>>c>>d;
  a--,b--,c--,d--;
  string s;
  cin>>s;
  string ans="Yes";
  
  //まずは、一人だけの時辿り着けるか考える
  //間に石が２個 並んでたら無理
  //a-c
  for(int i=a+1;i<=c;i++){
    if(s[i]=='#'&&s[i-1]=='#'){
      ans="No";
    }
  }

  //b-d
  for(int i=b+1;i<=d;i++){
    if(s[i]=='#'&&s[i-1]=='#'){
      ans="No";
    }
  }

  //追い越し必要？
  if(b<c&&d<c){
    //マスが3つ連続で空いてないとダメ！
    //追い越せるのはb-dの間
    bool check=false;
    for(int i=b+1;i<=d+1;i++){
      if(s[i-2]=='.'&&s[i-1]=='.'&&s[i]=='.'){
        check=true;
      }
    }
    if(check==false){//falseのままだったら、追い越せないのでNO
      ans="No";
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3708
#include<bits/stdc++.h>
#define int long long
#define fi first
#define sc second
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define msi map<string,int>
#define si set<int>
#define all(v) v.begin(),v.end()
#define sz(v)  int((v).size())
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define dep(i,a,b)    for(int i=a;i>=b;i--)
#define isinarr(i,n) ((i>=0)?((i<n)?1:0):0)
#define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppb pop_back
#define present(container, element) (container.find(element) != container.end())      //set,map etc.
#define cpresent(container, element) (find(all(container),element) != container.end())    //vector
#define hell 1000000007
#define PI 3.14159265
#define mp make_pair
#define inparr(a,n) rep(i,0,n)cin>>a[i];
#define give(x,y) cout<<x<<" "<<y<<endl;
#define setp(n) cout<<fixed<<setprecision(n);
#define    endl '\n'

using namespace std;
int i,j,k,l;
void solve()
{
	int x,y,z;
	cin>>x>>y>>z;
	cout<<z<<" "<<x<<" "<<y;
} 



signed main()
{
    fastio
    int t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

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

using namespace std;

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

	int n;
	string s[300];
	cin >> n;
	for( int i = 0; i < n; i++ )cin >> s[i];
	int ret = 0;
	for( int mx = 0; mx < n; mx++ )
	{
		bool ok = true;
		for( int x = 0; x < n; x++ )
			for( int y = 0; y < n; y++ )
			{
				if( s[( x + mx ) % n][y] != s[( y + mx ) % n][x] )ok = false;
			}
		if( ok )ret++;
	}
	cout << ret * n << endl;

	return 0;
}


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

int main() {
    int n, m, X, Y; cin >> n >> m >> X >> Y;
    vector<int> x(n), y(m);

    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < m; i++) cin >> y[i];

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    int ans = x[n - 1] + 1;
    if (ans > X && ans <= Y && ans <= y[0]) {
        cout << "No War" << endl;
    }
    else cout << "War" << endl;

    return 0;
}


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

using namespace std;

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp
// 挿入ソート
void printArray(vector<int> vector) {
    int size = vector.size();
    for (int i = 0; i < size; ++i) {
        if (i == size - 1) {
            cout << vector[i] << endl;
        } else {
            cout << vector[i] << " ";
        }
    }
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    printArray(A);

    for (int i = 1; i < N; ++i) {
        int v = A[i];
        int j = i - 1;

        while (j >= 0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;

        bool islast = (i == N - 1);
        printArray(A);
    }

    return 0;
}




Measured memory_bytes: 3164
'use strict'
const Main = (arg) => {
  let input = arg.trim().split('\n');
  let S = input[0].split('');
  // console.log({ S });
  let Ans = 'No';
  if (S[0] === S[1] && S[2] === S[3] && S[0] !== S[2]) {
    Ans = 'Yes'
  } else if (S[0] === S[2] && S[1] === S[3] && S[0] !== S[1]) {
    Ans = 'Yes'
  } else if (S[0] === S[3] && S[1] === S[2] && S[0] !== S[1]) {
    Ans = 'Yes'
  }
  
  console.log(Ans)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {//223
	int n,h,w,cnt=0;
	cin>>n>>h>>w;
	while(n--) {
		int a,b;
		cin>>a>>b;
		if(h<=a&&w<=b)cnt++;
	}
	cout<<cnt;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3644
//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int main(){
    StarBurstStream

    int n, k;
    cin >> n >> k;

    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];

    vector<int> dp(n, MAX);
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = max(0, i - k); j < i; j++){
            dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
        }
    }
//    printv(dp, cerr);

    cout << dp[n - 1] << "\n";

    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


int fac(int num) {
  if(num==1) return 1;
  else return num*fac(num-1);
}


ll a[110000];

int main() {
  int N;cin >> N;
  int cntminus = 0;
  ll m = inf;
  ll sum = 0;
  rep(i,N) {
    cin >> a[i];
    if(a[i] < 0) cntminus++;
    sum += abs(a[i]);
    m = min(m,abs(a[i]));
  }
  if(cntminus % 2 == 0) cout << sum << endl;
  else cout << sum - 2*m << endl;

  

  
  
  return 0;
}


Measured memory_bytes: 1024
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
for i in ans:
    print(i)

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

int main(){
	int N;
	scanf("%d", &N);
	bool a[N];
	for (int i = 0; i < N; ++i){
		int tmp;
		scanf("%d", &tmp);
		a[i] = tmp == 1;
	}
	for (int i = N; i > 0; --i){
		for (int j = 2; j <= N/i; ++j){
			a[i - 1] ^= a[i*j - 1];
		}
	}
	vector<int> ans;
	for (int i = 0; i < N; ++i){
		if(a[i]) ans.push_back(i + 1);
	}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); ++i){
		if(i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1912
#include <stdio.h>

int sum(int n,int *a){
	if(n==0){
		return 0;
	}
	else{
		return a[n-1]+sum(n-1,a);
	}
}

void doit(int n,int k){
	int i,j;
	int s[k];
	int b[k][n];
	int f=0;
	for(i=0;i<k;i++){
		scanf("%d",&s[i]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<k;j++){
			scanf("%d",&b[j][i]);
		}
	}
	
	i=0;
	while((f==0)&&(i<k)){
		if(sum(n,b[i])>s[i]){
			printf("No\n");
			f=1;
		}
		i++;
	}
	
	if(f==0){
		printf("Yes\n");
	}
}

int main(void) {
	int n,k;
	scanf("%d %d",&n,&k);
	while((n!=0)&&(k!=0)){
		doit(n,k);
		scanf("%d %d",&n,&k);
	}
	return 0;
}

Measured memory_bytes: 624
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 100005;

int n,K,a[105];
bool dp[MAXN][2];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>K;
	forn(i,0,n) cin>>a[i];
	
	forn(j,0,2) dp[0][j]=0;
	fore(i,1,K) forn(j,0,2)
	{
		forn(k,0,n)
		{
			if(i-a[k]<0) continue;
			dp[i][j]|=!dp[i-a[k]][j^1];
		}
	}
	
	if(dp[K][0]) cout<<"First\n";
	else cout<<"Second\n";
	
	return 0;
}


Measured memory_bytes: 3824
#include <iostream>
#include <cstdio>
using namespace std;
int n;
long long ans =0;
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        if (i % 3 != 0 && i % 5 != 0) 
        {
            ans += i;
        }
    }
    cout << ans;
}

Measured memory_bytes: 3636
public class Main {

    public static void main(String[] args) {

        java.util.Scanner sc = new java.util.Scanner(System.in);

        int n = sc.nextInt();
        int[] arrn = new int[n];

        for (int i = 0; i < n - 1; i++) {
            arrn[sc.nextInt() - 1]++;
        }

        for (int i : arrn) {
            System.out.println(i);
        }
    }

}

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

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 3632
import sys
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, K = mi()
    a, b = i2(N)
    d = defaultdict(int)
    for i in range(N):
        d[a[i]] += b[i]
    d = [(k, v) for k, v in d.items()]
    d.sort()
    s = 0
    for k, v in d:
        s += v
        if s >= K:
            print(k)
            return



if __name__ == '__main__':
    main()


Measured memory_bytes: 105124
#include<stdio.h>

int main(void){
	int a[3][3],n,s[3][3]={};
	char ans[4]="No";
	for(int i=0;i<3;i++){
		for(int m=0;m<3;m++){
			scanf("%d",&a[i][m]);
		}
	}
	scanf("%d",&n );
	int b[n];
	for(int i=0;i<n;i++){
		scanf("%d",&b[i]);
	}
	for(int k=0;k<n;k++){
		for(int i=0;i<3;i++){
			for(int m=0;m<3;m++){
				if(a[i][m]==b[k]){
					s[i][m]=1;
				}
			}
		}
	}
	for(int i=0;i<3;i++){
		if(s[i][0]==1 && s[i][1]==1 && s[i][2]==1){
			ans[0]='Y';
			ans[1]='e';
			ans[2]='s';
		}
	}
	for(int i=0;i<3;i++){
		if(s[0][i]==1 && s[1][i]==1 && s[2][i]==1){
			ans[0]='Y';
			ans[1]='e';
			ans[2]='s';
		}
	}
	if(s[0][0]==1 && s[1][1]==1 &&s[2][2]==1){
		ans[0]='Y';
		ans[1]='e';
		ans[2]='s';
	}	if(s[0][2]==1 && s[1][1]==1 && s[2][0]==1){
		ans[0]='Y';
		ans[1]='e';
		ans[2]='s';
		}
		printf("%s",ans );
		return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  string s;
  cin >> s;

  if (s <= "2019/04/30") cout << "Heisei" << endl;
  else cout << "TBD" << endl;
}


Measured memory_bytes: 3600
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N = input()
ans = 0
for i in range(1, N + 1, 2):
    cnt = 0
    for j in range(1, i + 1):
        if i % j == 0:
            cnt += 1
    if cnt == 8:
        ans += 1

print ans

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, a, b ,c, d;
  cin >> N;
  
  a = N / 1000;
  b = ( N % 1000) / 100;
  c = (( N % 1000) % 100)/10;
  d = (( N % 1000) % 100)%10;
  
  if ( a == b && b == c ){
    cout << "Yes" << endl;
  }
  else if ( b == c && c == d ){
    cout << "Yes" << endl;
  }
  else if ( a == b && b == c && c == d ){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}

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

using namespace std;

#define LL long long
#define pii pair<int,int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define rep(i,a,b) for(int i = (a) ; i <= (b) ; i++)
#define per(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define mem(a) memset(a,0,sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define fast_io ios::sync_with_stdio(false)

const int INF = 1e9;
const LL mod = 1e9 + 7;
const int maxn = 2e5 + 7;

vector<int>v[maxn];

int main() {
    int n;
    sd(n);
    rep(i,2,n) {
        int x;
        sd(x);
        v[x].push_back(i);
    }
    rep(i,1,n) {
        pd(v[i].size());
    }
    return 0;
}


Measured memory_bytes: 14692
def checkContinuous(line, memo, count, w)
    1.upto(w-1) do |i|
        if line[i] === "#" && line[i-1] === "#" then
            memo[count][i] = 1
            memo[count][i-1] = 1
        end
    end
end

def main(h, w)
    s = []
    memo = Array.new(h).map{Array.new(w,0)}
    count = 0
    h.times do
        line = gets.chomp.split("")
        s << line
        checkContinuous(line, memo, count, w)
        count += 1
    end
    s = s.transpose
    memo = memo.transpose
    count = 0
    s.each do |arr|
        checkContinuous(arr, memo, count, h)
        arr.each_with_index do |item, index|
            if item === "#" && memo[count][index] === 0 then
                print "No"
                exit
            end
        end 
        count += 1
    end
    print "Yes"
end

h, w = gets.chomp.split(" ").map(&:to_i)
main(h, w)

Measured memory_bytes: 2172
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, k = input_int_list()
    ans = 0
    if k % 2 == 0:
        # a,b,c == k//2 + p*k を満たすとき
        cnt = ((n - (k // 2)) // k) + 1
        ans += pow(cnt, 3)

    # a,b,c == p*k を満たすとき
    ans += pow(n // k, 3)

    print(ans)

    return


if __name__ == "__main__":
    main()


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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e10;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

typedef priority_queue<P, vector<P>, greater<P>> PQ_ASK;
const int mod = 1000000007;

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
ll pow2(ll a, ll b) {
    ll res = a;
    for (ll i = 1; i < b; i++) {
        res *= a;
    }
    return res;
}

int main() {

    int x;
    cin >> x;

    vector<ll> kohos;
    kohos.push_back(1);
    for (int a = 2; a < x; a++) {
        for (int b = 2; b < x; b++) {
            ll p = pow2(a, b);
            if (p > x) {
                break;
            }
            kohos.push_back(p);

        }
    }

    ll ans = 0;
    for (int i = 0; i < kohos.size(); i++) {
        cmax(ans, kohos[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}
macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.cin();
    let xs = sc.vec(n);
    let sum: i64 = xs.iter().sum();
    let ans = xs[1..n-1].iter().fold(((sum - xs[0] - xs[0]).abs(), xs[0]), |(mindiff, left), &x| {
        let left = left + x;
        let right = sum - left;
        (min!(mindiff, (left - right).abs()), left)
    });
    put!(ans.0);
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> { self.cin::<String>().chars().collect() }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.cin()).collect() }
}


Measured memory_bytes: 17524
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

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

Measured memory_bytes: 256