akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main()
{
  int i;
  string s[3],ans;
  while(cin>>s[0]>>s[1]>>s[2],s[0]!="0"){
    ans="NA";
    for(i=0;i<3;i++){
      if(s[i][0]!='+' && s[i][0]==s[i][1] && s[i][0]==s[i][2])ans=s[i][0];
      if(s[0][i]!='+' && s[0][i]==s[1][i] && s[0][i]==s[2][i])ans=s[0][i];
    }
    if(s[1][1]!='+' && s[1][1]==s[0][0] && s[1][1]==s[2][2])ans=s[1][1];
    if(s[1][1]!='+' && s[1][1]==s[0][2] && s[1][1]==s[2][0])ans=s[1][1];

    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    for(auto& s: a) cin >> s;

    const ll MOD = 1e9+7;
    Vvec<ll> dp(H, vector<ll>(W, 0));
    dp[0][0] = 1;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(a[i][j]=='#') continue;
            if(i>0) dp[i][j] += dp[i-1][j];
            if(j>0) dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    }

    cout << dp[H-1][W-1] << endl;
}

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

int n, m, x, currentPrice;
int c[13], a[13][13], price[13], skill[13], ans = 1200000;
bool found;

bool cmp(int i, int j) {
    if (c[i] < c[j])
        return true;
    return false;
}

void findMinPrice(int next, int currentPrice, bool ok) {
    if (ok) {
        found = true;
        ans = min(ans, currentPrice);
        return;
    }

    if(next == n + 1) {
        if (!found)
            ans = -1;
        return;
    }

    for (int i = next; i <= n; i++) {
        ok = true;
        for (int j = 1; j <= m; j++) {
            skill[j] += a[price[i]][j];
            if(skill[j] < x)
                ok = false;
        }
        findMinPrice(i + 1, currentPrice + c[price[i]], ok);
        for (int j = 1; j <= m; j++)
            skill[j] -= a[price[i]][j];
    }
}

int main() {
    cin >> n >> m >> x;

    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        price[i] = i;
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    }

    sort(price + 1, price + n + 1, cmp);

    findMinPrice(1, 0, 0);

    if (found == false)
        cout << -1;
    else
        cout << ans;
    return 0;
}


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

typedef long long ll;


int main() {
  int n; cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  
  a.erase(unique(a.begin(),a.end()),a.end());

  int i=0;
  for(auto itr=a.begin(); itr!=a.end(); itr++,i++){
    if(i!=0) cout <<" ";
    cout << *itr;
  }
  cout << endl;
}


Measured memory_bytes: 3100
#include <iostream>

using namespace std;

int n;
int a[100001], b[100001], c[100001];
bool found[100001][3];
long long int dp[100001][3];

long long int m(long long int a, long long int b){
    return ((a > b) ? a : b);
}

long long int f(int now, int k){
    if (now == n){
        if (k == 0){
            return max(b[now], c[now]);
        } else if (k == 1){
            return max(a[now], c[now]);
        } else if (k == 2) {
            return max(b[now], c[now]);
        } else {
            return max(a[now], max(b[now], c[now]));
        }
    } else {
        if (found[now][k]){
            return dp[now][k];
        } else {
            if (k == 0){
                dp[now][k] = m(b[now] + f(now+1, 1), c[now] + f(now+1, 2));
            } else if (k == 1){
                dp[now][k] = m(a[now] + f(now+1, 0), c[now] + f(now+1, 2));
            } else if (k == 2){
                dp[now][k] = m(b[now] + f(now+1, 1), a[now] + f(now+1, 0));
            } else {
                dp[now][k] = m(a[now] + f(now+1, 0), m(b[now] + f(now+1, 1), c[now] + f(now+1, 2)));
            }
            found[now][k] = true;
            return dp[now][k];
        }
    }
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[1][0] = a[1];
    dp[1][1] = b[1];
    dp[1][2] = c[1];
    for (int i = 1; i <= n; i++){
        dp[i][0] = a[i] + m(dp[i-1][1], dp[i-1][2]);
        dp[i][1] = b[i] + m(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = c[i] + m(dp[i-1][0], dp[i-1][1]);
    }
    cout << m(dp[n][0], m(dp[n][1], dp[n][2])) << endl;
}


Measured memory_bytes: 3712
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
	ll a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	ll res = 1e18;
	for (ll d = 0; d <= 2 * max(x, y); ++d) {
		ll A = max(0ll, x - d / 2);
		ll B = max(0ll, y - d / 2);
		res = min(res, d*c + A*a + B*b);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const char *Yes = "Possible";
const char *No = "Impossible";
multiset < int, greater < int > > g;
multiset < int, greater < int > > :: iterator it;

int main(){
	int n, a;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a);
		g.insert(a);
	}
	int len = *g.begin(); 
	for(int i = len / 2 + 1; i <= len; i++){
		for(int j = 0; j < 2; j++){
			it = g.find(i);
			if(it == g.end()){
				return puts(No), 0;
			}
			g.erase(it);
		}
	}
	if(!(len & 1)){
		it = g.find(len / 2);
		if(it == g.end()){
			return puts(No), 0;
		}
		g.erase(it);
	}
	len = (len + 1) / 2 + 1;
	for(it = g.begin(); it != g.end(); ++it){
		if(*it < len){
			return puts(No), 0;
		}
	}
	puts(Yes);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;
signed main(){
    int N; cin>>N;
    int ans = 0;
    int X = 100;
    while(X<N){
        X *= 1.01;
        ans++;
    }
    Out(ans);
}

Measured memory_bytes: 3652
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


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

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w, n,m,k; string s,t;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}


char field[60][60];
bool seen[60][60];
int cost[60][60];

ll bfs() {
	memset(seen, false, sizeof(seen));
	seen[0][0] = true;
	cost[0][0] = 0;
	P g = P(h - 1, w - 1);
	queue<P> q;
	q.push(P(0, 0));
	while (!q.empty()) {
		P now = q.front();
		q.pop();
		if (now == g) {
			return cost[now.first][now.second];
		}
		rep(i, 4) {
			P next = now;
			next.first += dy[i];
			next.second += dx[i];
			if (next.first >= 0 && next.second >= 0 && next.first < h && next.second < w
				&& field[next.first][next.second] != '#' && !seen[next.first][next.second]) {
				q.push(next);
				seen[next.first][next.second] = true;
				cost[next.first][next.second] = cost[now.first][now.second] + 1;
			}
		}
	}
	return -1;
}

int main() {
	cin >> h >> w;
	ll dis = 0;
	ll black = 0;
	rep(i, h) {
		rep(j, w) {
			cin >> field[i][j];
			if (field[i][j] == '#') {
				black++;
			}
		}
	}
	dis = bfs();
	if (dis == -1) {
		cout << -1 << endl;
		return 0;
	}
	cout << h * w - (black + dis + 1) << endl;
}


Measured memory_bytes: 256
N=int(input())

Z=[0]*10005
for i in range(1,102):
    for j in range(1,102):
        for k in range(1,102):
            n=i**2+j**2+k**2+i*j+j*k+k*i
            if n<=N:
                Z[n-1]+=1
for i in range(N):
    print(Z[i])

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

#define REP(i, a) for(int64 i = 0; i < (a);i++)
#define FOR(i, a, b) for(int64 i = (a); i < (b); i++)
#define INF (int64)1e9
#define INF_LL (int64)1e18
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

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

template<typename CommutativeMonoid>
class FenwickTree{
public:
  using value_structure = CommutativeMonoid;
  using value_type = typename CommutativeMonoid::value_type;
  using size_type = ::std::size_t;

private:
  ::std::vector<value_type> tree;
  size_type N;

  static value_type calc(const value_type& a, const value_type& b){
    return value_structure::operation(a, b);
  }

public:
  FenwickTree(){}
  FenwickTree(const size_type& N):N(N+10), tree(N+11, value_structure::identity()){}
  FenwickTree(const FenwickTree& bit):tree(bit.tree), N(bit.N){}

  void update(size_type k, const value_type& diff){ // update k in [1, N]
    for(;k <= N;k += k & -k){
      tree[k] = calc(tree[k], diff);
    }
  }

  value_type query(size_type k) const { // sum of [1, k]
    value_type res = value_structure::identity();
    for(;k > 0;k -= k & -k){
      res = calc(res, tree[k]);
    }
    return res;
  }

  void updatez(size_type k, value_type v){ // 0-indexed
    update(k+1, v);
  }

  value_type queryz(size_type k) const { // [0, k)
    return query(k);
  }

  size_type search(const std::function<bool(value_type)>& f) const { // Find k :[0, k) -> True, [0, k-1) -> False
    if(f(value_structure::identity()))
      return 0;
    if(!f(query(N)))
      return N+1;
    value_type x = value_structure::identity();
    size_type k = 1, idx = 0;
    while(k <= N) k <<= 1;
    k >>= 1;
    for(;k > 0;k >>= 1){
      if((idx|k) <= N && !f(tree[idx|k]+x))
        x = calc(x, tree[idx |= x]);
    }
    return idx+1;
  }

  size_type size() const {return N;}
};

class v_monoid {
public:
  using value_type = int64;
  static const value_type identity() { return 0; }
  static const value_type operation(const value_type& a, const value_type& b) {
    return a + b;
  }
};

int main(void) {
  set<int64> st;
  int64 N;
  cin >> N;
  REP(i, N) {
    int64 a;
    cin >> a;
    st.insert(a);
  }
  cout << st.size() << endl;
}




Measured memory_bytes: 7720
n,k,*x=map(int,open(0).read().split())
ans=float('inf')
if 0 in x:
  k-=1
  n-=1
  del x[x.index(0)]

if k==0:
  print(0)
else:
  for i in range(n-k+1):
    ans=min(ans,abs(x[i])+abs(x[i]-x[i+k-1]))
  for i in range(k-1,n):
    ans=min(ans,abs(x[i])+abs(x[i]-x[i-(k-1)]))
  print(ans)

Measured memory_bytes: 20020
import sys

def crossMulti(p1, p2):
    return p1[0] * p2[1] - p1[1] * p2[0]
           
lines = sys.stdin.readlines()
for line in lines:
    Zd = []
    x1, y1, x2, y2, x3, y3, xp, yp = map(float, line.split())
    Ps = [(x2-x1, y2-y1),(x3-x2, y3-y2),(x1-x3, y1-y3)]
    Px = [(xp-x1, yp-y1),(xp-x2, yp-y2),(xp-x3, yp-y3)]
    for p in range(3):
        Zd.append(crossMulti(Ps[p], Px[p]))
    Zd = [x > 0 for x in Zd]

    if (Zd[0] and Zd[1] and Zd[2]) or not(Zd[0] or Zd[1] or Zd[2]):
        print('YES')
    else:
        print('NO')
    

Measured memory_bytes: 7544
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	string s;
	cin >> s;
	int n = s.size();
	int dp[10][2][2][2][2][2] =
		{}; // dp[桁]['3']['5']['7'][n未満][0以外使用したか]
	dp[0][0][0][0][0][0] = 1;
	REP(i, n) {
		REP(j, 2) {
			REP(k, 2) {
				REP(l, 2) {
					REP(m, 2) {
						REP(o, 2) {
							for(int x = 0; x <= (m ? 9 : (s[i] - '0')); x++) {
								int m2 = 1;
								int o2 = 1;
								if(!m && x == s[i] - '0') {
									m2 = 0;
								}
								if(!o && x == 0) {
									o2 = 0;
								}

								if(x == 3) {
									dp[i + 1][1][k][l][m2][o2] +=
										dp[i][j][k][l][m][o];
								} else if(x == 5) {
									dp[i + 1][j][1][l][m2][o2] +=
										dp[i][j][k][l][m][o];
								} else if(x == 7) {
									dp[i + 1][j][k][1][m2][o2] +=
										dp[i][j][k][l][m][o];
								} else if(!o && x == 0) {
									dp[i + 1][j][k][l][m2][o2] +=
										dp[i][j][k][l][m][o];
								}
							}
						}
					}
				}
			}
		}
	}

	cout << dp[n][1][1][1][1][1] + dp[n][1][1][1][0][1] << endl;

	return 0;
}


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

int main() {
  int A, B;
  cin >> A >> B;
  
  if ( A % 3 == 0 || B % 3 == 0 || (A+B) % 3 == 0) {
    cout << "Possible" << endl;
  } else {
    cout << "Impossible" << endl;
  }

}


Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(), vec.end()
#define rever(vec) reverse(all(vec));
#define cend printf("\n");
#define prique(T) priority_queue<T, vector<T>, greater<T>>
#define prique2(T) priority_queue<T>
struct edge { int to, cost; };
using P = pair<int, int>;
using PP = pair<P, int>;
using D = pair<double, double>;
const int mod2 = 998244353;
const int mod = (int)1e9 + 7, inf = (int)1e16;
const string sp = " ";

int modpow(int x, int n) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) {
			ans *= x;
			if (mod <= ans) ans %= mod;
		}
		x *= x;
		if (mod <= x) x %= mod;
		n >>= 1;
	}
	return ans;
}

int fact[1000000];
void f_init(int n) {
	if (1000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= n; ++i) {
		fact[i] *= fact[i - 1];
		if (mod <= fact[i]) fact[i] %= mod;
	}
	return;
}

int comb(int n, int r) {
	if (n < r) return 0;
	int ans = fact[n] * modpow(fact[n - r], mod - 2) % mod * modpow(fact[r], mod - 2);
	if (ans < 0) return ans + mod;
	return ans;
}

int perm(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	int ans= fact[n] * modpow(fact[n - r], mod - 2) % mod;
	if (ans < 0) return ans + mod;
	return ans;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

bool pri(int p) {
	for (int i = 2; i * i <= p; ++i) if (p % i == 0) return false;
	return p > 1;
}

map<int, int>factring(int n) {
	map<int, int>ans;
	for (int i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++ans[i];
		}
	}
	if (n != 1) ++ans[n];
	return ans;
}

P operator+(const P& a, const P& b) {
	return P(a.first + b.first, a.second + b.second);
}
P operator-(const P& a, const P& b) {
	return P(a.first - b.first, a.second - b.second);
}

class unionfind {
private:
	int par[200010], rankth[200010], sizeth[200020];
public:
	void init(int n) {
		rep(i, n) {
			par[i] = i;
			rankth[i] = 0;
			sizeth[i] = 1;
		}
	}
	int root(int x) {
		while (par[x] != x) {
			x = par[x] = par[par[x]];
		}
		return x;
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return;
		if (rankth[x] < rankth[y]) {
			par[x] = y;
			sizeth[y] += sizeth[x];
		}
		else {
			par[y] = x;
			if (rankth[x] == rankth[y]) rankth[x]++;
			sizeth[x] += sizeth[y];
		}
	}
};

int n, m;
int a, ans;
prique2(int)q;
signed main() {
	cin >> n >> m;
	rep(i, n) {
		cin >> a;
		q.push(a);
	}
	rep(i, m) {
		int p = q.top(); q.pop();
		p /= 2;
		q.push(p);
	}
	rep(i, n) {
		ans += q.top(); q.pop();
	}
	cout << ans << endl;
}

Measured memory_bytes: 1400
// AOJ 2670 Cram School Schedule
// 2018.3.19 bal4u

#include <stdio.h>
#include <string.h>

// [library]

//#define getchar_unlocked()  getchar()
int in()	// get non-negative integer from stdin
{
	int n = 0, c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int tm()	// get time format (hh:mm)
{
	int hh, mm;

	hh = getchar_unlocked() & 0xf;
	hh = hh*10 + (getchar_unlocked() & 0xf); getchar_unlocked();   // skip ':'

	mm = getchar_unlocked() & 0xf;
	mm = mm*10 + (getchar_unlocked() & 0xf); getchar_unlocked();   // skip '-' or ' '
	return hh*60+mm;
}

#define MAX 205
int  hi[MAX], to[MAX][MAX];
char seen[MAX];
int  match[MAX];

int bpm(int u);
int bipartiteMatching(int m, int n)			// bipartite matching (BPM)
{
	int u, max;

	memset(match, -1, (m+n)*sizeof(int));
	max = 0;
	for (u = 0; u < m+n; u++) {
		if (match[u] < 0) {
			memset(seen, 0, m+n);
			if (bpm(u)) max++;
		}
	}
	return max;
}

int bpm(int u)								// sub module for BPM
{
	int i, v, w;

	seen[u] = 1;
	for (i = 0; i < hi[u]; i++) {
		v = to[u][i], w = match[v];
		if (w < 0 || !seen[w] && bpm(w)) {
			match[u] = v, match[v] = u;
			return 1;
		}
	}
	return 0;
}
// [\library]  

typedef struct { int s, e; } T;		// start, end time
T    tbl[102];
int teacher[102][102], wt[102];
int student[102][102], ws[102];

int main()
{
	int K, N, M, i, j, k, m, s, e, ans;

	K = in(); for (i = 0; i < K; i++) tbl[i].s = tm(), tbl[i].e = tm();
	
	N = in(); for (i = 0; i < N; i++) {
		m = in(); while (m--) {
			s = tm(), e = tm();
			for (k = 0; k < K; k++) if (s <= tbl[k].s && tbl[k].e <= e) {
				teacher[k][wt[k]++] = i;
			}
		}
	}

	M = in(); for (i = 0; i < M; i++) {
		m = in(); while (m--) {
			s = tm(), e = tm();
			for (k = 0; k < K; k++) if (s <= tbl[k].s && tbl[k].e <= e) {
				student[k][ws[k]++] = i;
			}
		}
	}

	ans = 0;
	for (k = 0; k < K; k++) {
		memset(hi, 0, (N+M)<<2);
		for (i = 0; i < wt[k]; i++) {
			s = teacher[k][i];
			for (j = 0; j < ws[k]; j++) {
				e = student[k][j];
				to[s][hi[s]++] = N+e;
			}
		}
		ans += bipartiteMatching(N, M);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2092
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
const ll powll = 1LL<<1;

int main(){
  ll n,k; cin >> n >> k;
  ll ans = k;
  rep(i,n-1) ans *= k-1;
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int r,c,a[101][101]={};
    cin>>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            a[i][c]+=a[i][j];
            a[r][j]+=a[i][j];
        }
        a[r][c]+=a[i][c];
    }
    for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++){
            if(j<c)
            cout<<a[i][j]<<" ";
            else cout<<a[i][j];
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    int ans=0;
    for(int i=0;i<s.size();i++){
        if(s[i]==t[i])ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CStrangeBank solver = new CStrangeBank();
        solver.solve(1, in, out);
        out.close();
    }

    static class CStrangeBank {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int res = n;
            for (int i = 0; i <= n; i++) {
                int cc = 0;
                int t = i;
                while (t > 0) {
                    cc += t % 6;
                    t /= 6;
                }
                t = n - i;
                while (t > 0) {
                    cc += t % 9;
                    t /= 9;
                }
                res = Math.min(res, cc);
            }
            out.println(res);
        }

    }
}



Measured memory_bytes: 22864
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


ll N,M,T;
ll POW[21],dp[21][1000],table[1000][2];


int main(){
	for(int i = 0; i < 21; i++)POW[i] = pow(2,i);

	for(int i = 0; i < 21; i++){
		for(int k = 0; k < 1000; k++)dp[i][k] = -1;
	}

	scanf("%lld %lld %lld",&N,&M,&T);

	ll tmp;
	dp[0][0] = 0;
	for(int loop = 0; loop < N; loop++){
		scanf("%lld",&tmp);
		dp[0][tmp%T] = max(dp[0][tmp%T],tmp); //余り毎に最大値を求める
	}

	//ダブリング
	for(int i = 0; POW[i+1] <= M;i++){
		for(int a = 0; a < T; a++){
			if(dp[i][a] == -1)continue;
			for(int b = 0; b < T; b++){
				if(dp[i][b] == -1)continue;
				dp[i+1][(a+b)%T] = max(dp[i+1][(a+b)%T],dp[i][a]+dp[i][b]);
			}
		}
	}

	int CURRENT = 0,NEXT = 1;
	for(int i = 0; i < T; i++)table[i][CURRENT] = -1;
	ll rest = M;

	bool FIRST = true;
	//
	for(int i = 20; i >= 0; i--){
		if(rest < POW[i])continue;
		rest -= POW[i];

		if(FIRST){ //初めての場合
			for(int b = 0; b < T; b++){ //dpのループ
				if(dp[i][b] == -1)continue;

				table[b][CURRENT] = dp[i][b];
			}
			FIRST = false;
			continue;
		}

		for(int k = 0; k < T; k++){
			table[k][NEXT] = -1;
		}

		for(int a = 0; a < T; a++){
			if(table[a][CURRENT] == -1)continue;
			for(int b = 0; b < T; b++){
				if(dp[i][b] == -1)continue;

				table[(a+b)%T][NEXT] = max(table[(a+b)%T][NEXT],table[a][CURRENT]+dp[i][b]);
			}
		}
		swap(CURRENT,NEXT);
	}

	//右から左に情報を伝える
	for(int i = T-2; i >= 0; i--){
		table[i][CURRENT] = max(table[i+1][CURRENT],table[i][CURRENT]);
	}

	int Q;
	scanf("%d",&Q);

	ll A,B;

	for(int loop = 0; loop < Q; loop++){
		scanf("%lld %lld",&A,&B);

		if(table[A][CURRENT] != -1 && table[A][CURRENT]/T >= B){
			printf("yes\n");
		}else{
			printf("no\n");
		}
	}

	return 0;
}



Measured memory_bytes: 3468
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int t = sc.nextInt();
		int max = 0;
		int now = 0;
		int cnt = 0;
		for(int i = 0; i < n; i++){
		    int a = sc.nextInt();
		    if(i == 0){
		        now = a;
		        continue;
		    }
		    if(now > a) now = a;
		    if(now < a){
		        if(a-now > max){
		            max = a-now;
		            cnt = 1;
		        }else if(a-now == max){
		            cnt++;
		        }
		    }
		}
		
		// 計算
		int result = cnt;
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 36188
N = int(input())
# len(info) == N,  len(info[i]) == 10
info = [list(map(int,input().split())) for i in range(N)]
p = [list(map(int,input().split())) for i in range(N)]

def bfs(list_hoge=[[]],depth=0):
    queue = []
    for e in list_hoge:
        for b in [0,1]:
            copy = e[:]
            copy.append(b)
            queue.append(copy)
    if depth == 10:
        return list_hoge[1:]
    list_hoge = queue[:]
    return bfs(list_hoge,depth+1)

ans = -float("inf")
for e in bfs():
    common = []
    for i in range(N):
        c = 0
        for j in range(10):   
            if e[j] == 1 and info[i][j] == 1:
                c += 1
        common.append(c)
    benefit = 0
    for i in range(N):
        c_i = common[i]
        benefit += p[i][c_i]
    if benefit > ans:
        ans = benefit
print(ans)

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

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n; cin >> n;
	vector<int> a(n); rep(i, n)cin >> a[i];
	vector<int> p(1001001);
	for (int i = 2; i <= 1000000; ++i)
	{
		if (p[i])continue;
		for (int j = i; j <= 1000000; j += i)
		{
			if (p[j])continue;
			p[j] = i;
		}
	}
	vector<bool> used(1001001);
	bool pairwise = true;
	rep(i, n)
	{
		int now = a[i];
		while (now > 1)
		{
			int d = p[now];
			if (used[d])pairwise = false;
			used[d] = true;
			while (p[now] == d)
			{
				now /= d;
			}
		}
	}
	if (pairwise)
	{
		cout << "pairwise coprime" << endl;
		return 0;
	}
	int g = 0;
	rep(i, n)g = gcd(a[i], g);
	if (g == 1)cout << "setwise coprime" << endl;
	else cout << "not coprime" << endl;
}

Measured memory_bytes: 11320
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
const int INF = 1e9+8;
int dp[N*1004];
//dp(i) denote the smallest total weight that values exactly i
int val[N],w[N];
int n,W;
signed main()
{
	int sum_val = 0;
	cin>>n>>W;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&w[i],&val[i]);
		sum_val += val[i];
	}
	for(int i=0;i<N*1004;i++)
	{
		dp[i] = INF;
	}
	
	dp[0] = 0;

	for(int i=1;i<=n;i++)
	{
		for(int j=sum_val;j>=0;j--)
		{
			if(j - val[i] >= 0)
				dp[j] = min(dp[j],dp[j-val[i]] + w[i]);

			
				
		}
	}
	
	int ans = 0;
	for(int i=0;i<=sum_val;i++)
	{
		if(dp[i] <= W)
		{
			ans = max(ans,i);
		}
	}
	
	cout<<ans;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String str = in.readLine();
		String s[] = str.split(" ");
		int a = Integer.parseInt(s[0]);
		int b = Integer.parseInt(s[1]);
		int c = Integer.parseInt(s[2]);
		if (a < b && b < c) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 24436
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String a = sc.next();
        String b = sc.next();
        
        String s = "EQUAL";

        if (a.length() > b.length()) {
            System.out.println("GREATER");
            System.exit(0);
        }
        if (a.length() < b.length()) {
            System.out.println("LESS");
            System.exit(0);
        }


        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) > b.charAt(i)) {
                s = "GREATER";
                break;
            }
            if (a.charAt(i) < b.charAt(i)) {
                s = "LESS";
                break;
            }
        }

        System.out.println(s);
        System.exit(0);
    }
}


Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  int n,d;
  cin >> n >> d;
  int ans=0;
  rep(i,n) {
    double x,y;
    cin >> x >> y;
    double z=sqrt(x*x+y*y);
    if(z<=d) ans++;
  }
  pr(ans);
}

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


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

int n, k;
string s;

void reverse(int a, int b) {
    for (int i = a; i <= b; i++) {
        if (s[i] == 'L') s[i] = 'R';
        else s[i] = 'L';
    }
    rep(i, (abs(a-b)+1)/2) {
        swap(s[a+i], s[b-i]);
    }
}

int count() {
    int res = 0;
    rep(i, n-1) {
        if (s.substr(i, 2) == "LL" || s.substr(i, 2) == "RR") {
            res++;
        }
    }
    return res;
}

int main(){
    cin >> n >> k >> s;
    int max_happy = n-1, now_happy = count();

    rep(i, k) {
        if(now_happy + 2 <= max_happy) {
            now_happy += 2;
        } else if (now_happy + 1 <= max_happy) {
            now_happy++;
        }
    }

    cout << now_happy << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF=INT_MAX;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))



int main(){
	int N,W,H;
	cin>>N>>W>>H;
	vector<int>width(W+1,0),height(H+1,0);
	
	REP(i,N){
		int x,y,w;
		cin>>x>>y>>w;
		height[max(y-w,0)]++;
		height[min(y+w,H)]--;
		width[max(x-w,0)]++;
		width[min(x+w,W)]--;
	}
	bool covered=true;
	int tmp=0;
	REP(i,H){
		tmp+=height[i];
		if(tmp<=0)covered=false;
	}
	tmp=0;
	REP(i,W){
		tmp+=width[i];
		if(tmp<=0&&!covered){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 1800
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

// Self settings
// clang-format off
#define MAX_N 100
#define MAX_V 1000
#define INF 1000000001
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
// clang-format on

ll N, W;
// ll dp[MAX_N + 1][MAX_V + 1];
ll dp[MAX_N + 1][MAX_N * MAX_V + 1];
ll w[MAX_N], v[MAX_N];

void solve()
{
  REP(i, N + 1) REP(j, MAX_N * MAX_V + 1) dp[i][j] = INF;
  dp[0][0] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= MAX_N * MAX_V + 1; j++) {
      if (j < v[i] || dp[i][j - v[i]] == INF) {
        dp[i + 1][j] = dp[i][j];
      }
      else {
        dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
      }
    }
  }
  ll ans = 0;
  // REP(j, MAX_V + 1) cout << dp[N][j] << " ";
  REP(j, MAX_N * MAX_V + 1) if (dp[N][j] <= W) ans = j;
  cout << ans << endl;
}

int main(void)
{
  cin >> N >> W;
  REP(i, N) cin >> w[i] >> v[i];
  solve();
  return 0;
}


Measured memory_bytes: 79104
N = int(input())

def dfs(s): # 文字列 s で始まる七五三数の個数
	if int(s) > N:
		return 0
	ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1
	for c in '753':
		ret += dfs(s + c)
	return ret

print(dfs('0'))

Measured memory_bytes: 3316
N=int(input())
Hs=[0] + list(map(int,input().split()))
Hs.append(0)
ma = max(Hs)

res = 0
for _ in range(ma):
    cnt = 0
    last1 = -1
    for i in range(N+2):
        if Hs[i] > 0:
            Hs[i] -= 1
            if last1+1 != i:
                cnt += 1
            last1 = i
    # print(Hs)
    res += cnt

print(res)


Measured memory_bytes: 3060
unittest
{
	assert( [ "4 5", "1 2", "1 3", "3 2", "2 4", "3 4" ].parse.expand.solve == 3 );
	assert( [ "6 3", "2 3", "4 5", "5 6" ].parse.expand.solve == 2 );
	assert( [ "5 8", "5 3", "2 3", "2 4", "5 2", "5 1", "1 4", "4 3", "1 3" ].parse.expand.solve == 3 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nm = input.front.split.to!( long[] );
	auto xys = new long[][]( nm[ 0 ] );
	for( auto i = 0L; i < nm[ 1 ]; i++ )
	{
		input.popFront;
		auto xy = input.front.split.to!( long[] );
		xys[ xy[ 0 ] - 1 ] ~= xy[ 1 ] - 1;
	}
	return tuple( nm[ 0 ], xys );
}

auto solve( long n, long[][] xys )
{
	auto ans = 0L;
	memo = memo.init;
	foreach( x, xy; xys )
	{
		ans = max( ans, xys.f( x ) );
	}
	return ans;
}

static long[ long ] memo;

long f( long[][] xys, long x )
{
	if( x !in memo )
	{
		auto ans = 0L;
		foreach( y; xys[ x ] )
		{
			ans = max( ans, 1 + xys.f( y ) );
		}
		memo[ x ] = ans;
	}
	
	return memo[ x ];
}


Measured memory_bytes: 23676
//https://atcoder.jp/contests/dp/tasks/dp_e
//E - Knapsack 2
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll N,W; cin>>N>>W;
    ll V=0;
    vector<pair<ll,ll>> wvn(N+1); //w,v
    FOR(i,1,N+1){
        cin>>wvn[i].first>>wvn[i].second;
        V+=wvn[i].second;
    }
    ll INFW=1e+11;
    vector<vector<ll>> dp(N+2,vector<ll>(V+1,INFW));
#if 1
    dp[1][0]=0;
    FOR(i,1,N+1){
        ll w=wvn[i].first;
        ll v=wvn[i].second;
        FOR(j,0,V+1){
            if(j<v){
                dp[i+1][j]=dp[i][j];
            }else{
                dp[i+1][j]=min(dp[i][j], dp[i][j-v]+w);
            }
        }
    }
    ll res=0;
    FOR(i,0,V+1) if (dp[N+1][i]<=W) res=i;
    cout<<res<<endl;
#else
    FOR(j,0,V+1){
        dp[0][j]=0;
    }
    FOR(i,1,N+1){
        ll w=wvn[i].first;
        ll v=wvn[i].second;
        FOR(j,0,V+1){
            if (j-v>=0) {
                dp[i][j]=min(dp[i-1][j-v]+w,dp[i][j]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    ll ans=0;
    FOR(i,0,V+1){
        if (dp[N][i]<=W) chmax(ans,i);
    }
    cout<<ans<<endl;
#endif
    return 0;
}

Measured memory_bytes: 81400
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String s = sc.next();

		String komoji = s.toLowerCase();

		if (s.equals(komoji)) {
			System.out.println("a");
		} else {
			System.out.println("A");
		}

	}
}

Measured memory_bytes: 35676
#include<bits/stdc++.h>
#define ll long long 

using namespace std ;

int main ()
{
    ll n , a , b ;
    cin >> n >> a >> b ;
    ll ans = (n / ( a  + b ) ) * a ;
    n %= (a+b);
    ans += min(a, n);
    cout << ans ;
    return 0 ;
}


Measured memory_bytes: 256
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor.hpp>
#include <boost/algorithm/string.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::math;

using ll = long long;
namespace bst = boost;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<int> N;
  
  string r;

  auto solve = [&](auto f, int n, int prev) -> void {
    if (n <= 0) {
      cout << r << endl;
      return;
    }
    REP(i, (n==N-1 ? 2 : prev + 2)) {
      r.push_back('a' + i);
      f(f, n - 1, max(prev, i));
      r.pop_back();
      if (N == n)
        return;
    }

  };
  solve(solve, N, 0);
}

template<typename T> void plot(const T& func) { cout << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }
template<> void plot<double()>(double(&func)()) { cout << setprecision(9) << func() << endl; }

int main() {
  plot(solve);

  return 0;
}



Measured memory_bytes: 1536
N,C = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]

n = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        n[(i+j)%3][c[i][j]] += 1

ans = 500*500*1000
for c0 in range(C):
    for c1 in range(C):
        if c1 == c0:
            continue
        for c2 in range(C):
            if c2 in (c0,c1):
                continue
            score = 0
            for a in range(C):
                score += n[0][a] * D[a][c0] + n[1][a] * D[a][c1] + n[2][a] * D[a][c2]
            ans = min(ans,score)
print(ans)

Measured memory_bytes: 5492
n = int(input())
h = list(map(int,input().split()))
ans = 0
while True:
    f = 0
    if all(x==0 for x in h):
        break
    for i in range(n):
        if f and h[i] == 0:
            break
        if h[i]>0:
            h[i] -= 1
            f = 1
    ans += 1
    
print(ans)

Measured memory_bytes: 3064
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <climits>
# include <iostream>
# include <string>
# include <queue>
# include <vector>
# include <set>
# include <map>
# include <cstdlib>
# include <stack>
# include <ctime>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define mct(a,b) memset(a,b,sizeof(a))
# define gc getchar()
typedef long long ll;
const int N=1e5+5;
const int inf=0x7fffffff;
const double eps=1e-7;
template <typename T> void read(T &x){
	x=0;int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
	x*=f;
}

int a,b;

int main()
{
	read(a),read(b);
	if((b-1)%(a-1)==0)printf("%d\n",(b-1)/(a-1));
	else printf("%d\n",(b-1)/(a-1)+1);
	return 0;
}

Measured memory_bytes: 256
import collections

H, W  = map(int, input().split())
A = []
for _ in range(H):
    for c in input():
        A.append(c)
A.sort()
B = collections.Counter(A).most_common()
# print(A)
# print(B)
success = False
if H % 2 == 0 and W % 2 == 0:
    if all([val[1] % 4 == 0 for val in B]):
        success = True
elif H % 2 == 1 and W % 2 == 0:
    if all([val[1] % 2 == 0 for val in B]):
        four = 0
        two = 0
        for el in B:
            x = el[1]
            if x % 4 == 0:
                four += 1
            elif x % 2 == 0:
                two += 1
        if two <= W // 2 and (W // 2 - two) % 2 == 0:
            success = True
elif H % 2 == 0 and W % 2 == 1:
    if all([val[1] % 2 == 0 for val in B]):
        four = 0
        two = 0
        for el in B:
            x = el[1]
            if x % 4 == 0:
                four += 1
            elif x % 2 == 0:
                two += 1
        if two <= H // 2 and (H // 2 - two) % 2 == 0:
            success = True
else:
    odd = 0
    two = 0
    four = 0
    for el in B:
        x = el[1]
        if x % 2 == 1:
            odd += 1
            x -= 1
        if x % 4 == 0:
            four += 1
        elif x % 2 == 0:
            two += 1
    if odd == 1:
        if two <= H // 2 + W // 2 and (H // 2 + W // 2- two) % 2 == 0:
            success = True
if success:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 39152
def check(k, p, w_list):
    i_w = 0
    for i_k in range(k):
        sum_w = 0
        while True:
            if i_w >= len(w_list):
                return len(w_list)
            if sum_w + w_list[i_w] > p:
                break
            sum_w += w_list[i_w]
            i_w += 1
    return i_w

n, k = list(map(int, input().split()))
w_list = list()

for _ in range(n):
    w = int(input())
    w_list.append(w)

left = 0
right = 100000 * 10000
mid = None

while left < right:
    mid = (left + right) // 2
    v = check(k, mid, w_list)
    if v >= n:
        right = mid
    else:
        left = mid + 1

print(right)

Measured memory_bytes: 11520
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    
    if(a+b+c>=22) cout<<"bust"<<endl;
    else cout<<"win"<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
using namespace std;
#define ll long long
#define mod 1000000007;

ll gcd(ll a, ll b){
	return (b > 0)? gcd(b, a % b) : a ;
}

ll lcm(int a, ll b){
	return a / gcd(a, b) * b;
}

int main() {
    int n,a[300000],now,count=1;
    bool flag =false;
    vector<int> b;
    cin >> n;
    for(int i=0;i<n;i++)cin >> a[i];
    now = 0;
    for(int i=0;i<n;i++){
        if(a[i] == now + 1){
            now++;
            flag = true;
        }
    }
    if(!flag){
        cout << -1 <<endl;
        return 0;
    }
    cout << n - now << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		char[] n = sc.next().toCharArray();
		int flg=0,a,b;
		if (n[0]==n[1]&&n[1]==n[2]){
        flg=1;
        }
		if (n[3]==n[1]&&n[1]==n[2]){
        flg=1;
        }
		if (flg==0){
		System.out.print("No");
        }else{
        System.out.print("Yes");
        }
 
    }
}

Measured memory_bytes: 21588