akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<string>
#include<cassert>
using namespace std;
#define N 4
#define N2 16
#define LIMIT 100
static const int dx[4]={0,-1,0,1};
static const int dy[4]={1,-0,-1,0};
static const char dir[4]={'r','u','l','d'};
int MDT[N2][N2];
struct Puzzle{int f[N2],space,MD;};
Puzzle state;
int limit;
int path[LIMIT];
int getALLMD(Puzzle pz){
  int sum=0;
  for(int i=0;i<N2;i++){
    if(pz.f[i]==N2)continue;
    sum += MDT[i][pz.f[i]-1];
  }
  return sum;
}
bool isSolved(){
  for(int i=0;i<N2;i++) if(state.f[i] != i+1) return false;
  return true;
}
bool dfs(int depth,int prev){
  if(state.MD==0) return true;
  if(depth+state.MD>limit) return false;
  int sx=state.space/N;
  int sy=state.space%N;
  Puzzle tmp;
  for(int r=0;r<4;r++){
    int tx=sx+dx[r];
    int ty=sy+dy[r];
    if(tx<0||ty<0||tx>=N||ty>=N) continue;
    if(max(prev,r)-min(prev,r)==2) continue;
    tmp=state;
    state.MD -=MDT[tx*N+ty][state.f[tx*N+ty]-1];
    state.MD +=MDT[sx*N+sy][state.f[tx*N+ty]-1];
    swap(state.f[tx*N+ty],state.f[sx*N+sy]);
    state.space=tx*N+ty;
    if(dfs(depth+1,r)){path[depth]=r;return true;}
    state = tmp;
  }
  return false;
}
 string iterative_deepening(Puzzle in){
    in.MD=getALLMD(in);
    for(limit = in.MD;limit<=LIMIT;limit++){
      state=in;
      if(dfs(0,-100)){
	string ans = "";
	for(int i=0;i<limit;i++) ans+=dir[path[i]];
	return ans;
      }
    }
    return "unsolvable";
  }
  int main(){
    for(int i=0;i<N2;i++)
      for(int j=0;j<N2;j++)
	MDT[i][j]=abs(i/N-j/N)+abs(i%N-j%N);
    Puzzle in;
    for(int i=0;i<N2;i++){
      cin >> in.f[i];
      if(in.f[i]==0){
	in.f[i]=N2;
	in.space=i;
      }
    }
    string ans = iterative_deepening(in);
    cout << ans.size() << endl;
    return 0;
  }
  
      



Measured memory_bytes: 3212
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<map>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define pb push_back
#define pf push_front
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
 
ll gcd(ll x, ll y) {
	ll r;
	while ((r = x % y) != 0) {
		x = y;
		y = r;
	}
	return y;
	}
ll lcm(ll x, ll y) {
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x*y);
}

int main()
{
	string s;
	int cnt=0;
	cin >> s;
	rep(i,s.size()){
		if(s[i]=='2') cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
a = []
b = []
a = list(map(int,input().split()))
del a[0]
for i in range(n-1):
  c = list(map(int,input().split()))
  del c[0]
  for j in range(len(a)):
    if a[j] not in c:
      a[j] = "#"
print(len(a) - a.count("#"))
    
  

Measured memory_bytes: 3060
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include<bits/stdc++.h>

using namespace std;
 
#define  fastio         ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  f              first                 
#define  s              second
#define  endl           "\n"
#define  pb             push_back  
#define  mset(a,x)      memset(a,x,sizeof(a))
#define  debv(a)        for(auto it: a)cout<<it<<" ";cout<<endl;
#define  deb1(a)        cout<<a<<endl;
#define  deb2(a,b)      cout<<a<<" "<<b<<endl;
#define  deb3(a,b,c)    cout<<a<<" "<<b<<" "<<c<<endl;
#define  deb4(a,b,c,d)  cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;            
 
typedef  long long             ll;
typedef  long double           ld;
typedef  pair<ll,ll>           pll;
typedef  vector<ll>            vll;
typedef  unordered_map<ll,ll>  um;
typedef  vector<pll>           vpll;
 
const ll   N     =  5e5+5;
const ll   mod   =  1e9+7;
const ll   INF   =  1e18;
const int  INFi  =  0x7f7f7f7f;

ll test = 1, n, k;
vll pos, neg;

void solve(){
    cin>>n>>k;
    for(int i = 0; i < n; i++){
        ll x;
        cin>>x;
        if(x > 0) pos.pb(x);
        else neg.pb(-x);
    }
    sort(pos.rbegin(), pos.rend());
    sort(neg.rbegin(), neg.rend());
    ll ans = 1;
    if(pos.size() == 0){
        if(k&1) reverse(neg.begin(), neg.end());
        for(int i = 0; i < k; i++) ans = (ans*neg[i])%mod;
        if(k&1) ans = (mod-ans);
        deb1(ans%mod)
        return;
    }
    int i = 0, j = 0;
    if(k&1) ans = pos[0], i++, k--;
    for(int kk = 0; kk < k; kk += 2){
        if(i+1 == pos.size() and j+1 == neg.size()){
            ans = ans*pos[i]%mod*neg[j]%mod, i++, j++;
            ans = mod-ans;
        }
        else if(j+1 >= neg.size()) ans = ans*pos[i]%mod*pos[i+1]%mod, i += 2;
        else if(i+1 >= pos.size()) ans = ans*neg[j]%mod*neg[j+1]%mod, j += 2;
        else{
            ll x = pos[i]*pos[i+1], y = neg[j]*neg[j+1];
            if(x > y) ans = ans*(x%mod)%mod, i += 2;
            else ans = ans*(y%mod)%mod, j += 2;
        }
    }
    deb1(ans%mod)
}

int main(){
    fastio;
    //cin>>test;
    for(int i = 1; i <= test; i++){
        solve();
    }
}


Measured memory_bytes: 5632
import java.util.*;
import java.io.*;
public class Main{
   public static void main(String[] main) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      PrintWriter out = new PrintWriter(System.out);
      int n = Integer.parseInt(st.nextToken());
      st = new StringTokenizer(br.readLine());
      long a1 = 0, a2 = 0;
      long xor = 0;
      for(int i = 0; i < n; i++) {
    	  long a = Long.parseLong(st.nextToken());
    	  if(i == 0)
    		  a1 = a;
    	  else if(i == 1)
    		  a2 = a;
    	  else
    		  xor = a ^ xor;
      }
      long sum = a1 + a2;
      long res = 0;
      PriorityQueue<Long> one = new PriorityQueue<Long>();
      boolean works = true;
      long pow = 1;
      while(sum > 0) {
    	  if(sum%2 == xor%2) {
    		  if(sum%2 == 1)
    			  one.add(-pow);
    		  else {
    			  if(sum%4 != xor%4) {
	    			  res += pow;
	    			  sum -= 2;
    			  }
    		  }
    	  }
    	  else {
    		  works = false;
    		  break;
    	  }
    	  sum /= 2;
    	  xor /= 2;
    	  pow *= 2;
      }
      if(!works || res > a1 || xor > 0)
    	  out.println(-1);
      else {
    	  while(one.size() > 0) {
    		  pow = -one.remove();
    		  if(res + pow <= a1)
    			  res += pow;
    	  }
    	  if(res == 0)
    		  out.println(-1);
    	  else
    		  out.println(a1 - res);
      }
      out.close();
   }
}

Measured memory_bytes: 33148
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2005;

int n,m,q,f[N][N],g[N][N],s[N][N];
char ch[N];
bool ma[N][N];

int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int main()
{
	n=read();m=read();q=read();
	for (int i=1;i<=n;i++)
	{
		scanf("%s",ch+1);
		for (int j=1;j<=m;j++) ma[i][j]=ch[j]-'0';
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
			g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			if (ma[i][j]&&ma[i][j-1]) f[i][j]++;
			if (ma[i][j]&&ma[i-1][j]) g[i][j]++;
			if (ma[i][j]) s[i][j]++;
		}
	while (q--)
	{
		int x1=read(),y1=read(),x2=read(),y2=read(),ans=0;
		ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
		ans-=f[x2][y2]-f[x1-1][y2]-f[x2][y1]+f[x1-1][y1];
		ans-=g[x2][y2]-g[x1][y2]-g[x2][y1-1]+g[x1][y1-1];
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 52864
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
result='Yay!'
q=[a,b,c,d,e]
for i in q:
    for x in q:
        if i-x>k:
            result=':('
print(result)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>


// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

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

struct UnionFind{
	vector<int> par, sz;
	UnionFind(int n){
		par = sz = vector<int>(n);
		for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1;
	}
	int find(int x){
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y){
		x = find(x), y = find(y);
		if (x == y) return;
		par[x] = y;
		sz[y] += sz[x];
	}
	bool same(int x, int y){
		return find(x) == find(y);
	}
	int size(int x){
		return sz[find(x)];
	}
};

bool cmp(const tuple<int, int, int> &a, const tuple<int, int, int> &b){
	return get<1>(a) < get<1>(b);
}

int main(){
	int n, w, h;
	cin >> n >> w >> h;

	vector<tuple<int, int, int>> v(n);

	bool edge = false;
	rep(i, n){
		int x, y;
		cin >> x >> y;
		v[i] = MT(x, y, i);
		if (x == w || y == h) edge = true;
		if (x == 1 || y == 1) edge = true;
	}

	UnionFind uf(n);

	sort(ALL(v));
	rep(i, n - 1) if (get<0>(v[i]) == get<0>(v[i + 1])) uf.unite(get<2>(v[i]), get<2>(v[i + 1]));
	sort(ALL(v), cmp);
	rep(i, n - 1) if (get<1>(v[i]) == get<1>(v[i + 1])) uf.unite(get<2>(v[i]), get<2>(v[i + 1]));

	set<int> st;
	rep(i, n) st.insert(uf.find(i));

	int mv = st.size();
	if (mv == 1 || edge) --mv;

	cout << n - 1 + mv << endl;

	return 0;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000


int main(){

	string S;
	cin>>S;
	
	if(S[0]==S[1]&&S[1]==S[2]){
		cout<<"Yes"<<endl;
		return 0;
	}
	if(S[1]==S[2]&&S[2]==S[3]){
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	
    return 0;
}



Measured memory_bytes: 256
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)
#define fcout cout << fixed << setprecision(10)

using namespace std;

int N, M, D;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> D;

    int t = 0;

    int d = D > 0 ? 2 : 1;
    t += max(0LL, (N - 2 * D)) * d;
    t += min(N, 2 * D);
    double ans = (double)t * (M - 1) / (double)(N * N);
    fcout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	// input1 = input[0].split(' ').map((n) => (parseInt(n)))
	input1 = input[1].split(' ').map((n) => (parseInt(n)))
	// ans = input.filter((n) => (s <= n)).length

	ans = 0
	for (var i = 0; i < input1.length; i++) {
		ans += ( 1 / input1[i])
	}
	ans = (1 / ans)

	//出力
	console.log(ans)
}
// *この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
// Main(require('fs').readFileSync('./input.txt', 'utf-8'));

Measured memory_bytes: 7500
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int k,a,b;ll ans;
int main(){
	scanf("%d%d%d",&k,&a,&b);
	if(a>b||k<a||a+1==b){printf("%d\n",k+1);return 0;}
	ans=a+1ll*(b-a)*((k-a+1)>>1);
	if((k-a+1)&1)ans++;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,n) for(int i=l; i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
using Graph = vector<vector<int>>;

vector<bool> seen;
vector<int> first_order;
vector<int> last_order;

void dfs(const Graph &G, int v, int& ptr) {

    first_order[v] = ptr++;

    seen[v] = true; 
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v, ptr);
    }

    last_order[v] = ptr++;
}

int main() {
    int N; cin >> N;

    // グラフ入力受取
    Graph G(N);
    REP(i,N){
        int u,k; cin>>u>>k;
        REP(j,k){
            int vlist;
            cin >> vlist;
            G[u-1].push_back(vlist-1);
        }
    }

    // 頂点 0 をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    first_order.resize(N);
    last_order.resize(N);
    int ptr = 1;

    REP(i,N){
        if(seen[i]==true) continue;
        else dfs(G, i, ptr);
    }

    REP(v,N){
        cout << v+1 << " " << first_order[v] << " " << last_order[v] << endl;
    }
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int i,x,n,tmp;
  cin>>x>>n;
  vector<int> flag(100);
  for(i=0;i<n;i++){
    cin>>tmp;
    tmp-=x;
    if(tmp>0){flag.at(tmp)+=1;}
    else if(tmp<0){flag.at(-tmp)+=2;}
    else{flag.at(0)=3;}
  }
  i=0;
  while(flag.at(i)==3){
    i++;
  }
  if(flag.at(i)==2){cout<<x+i;}
  else{cout<<x-i;}
}

Measured memory_bytes: 3632
var
	n,h,w,i,x,y:longint;
    ans:int64;
begin
	readln(n,h,w);
    ans:=0;
    for i:=1 to n do
    begin
    	read(x,y);
        if (x>=h) and (y>=w) then inc(ans);
    end;
    writeln(ans);
end.

Measured memory_bytes: 128
S = input()
s1 = S[0]
s2 = S[1]
s3 = S[2]
s4 = S[3]
SL = [s1, s2, s3, s4]
SL.sort()
if SL[0] == SL[1] and SL[2] == SL[3] and SL[0] != SL[2]:
    print("Yes")
else:
    print("No")


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

int N;
vector< pair<int, int> > edge[100010];
int color[100010] = {};
int cmax = -1;

void dfs(int cur, int par, int used) {
    int cnt = 1;
    for(pair<int, int> &p : edge[cur]) {
        int child = p.first;
        if(child == par) continue;
        int i = p.second;
        color[i] = (cnt == used) ? ++cnt : cnt;
        cnt++;
        cmax = max(cmax, color[i]);
        dfs(child, cur, color[i]);
    }
}

int main() {
    cin >> N;
    for(int i = 0; i < N-1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        edge[b].push_back(pair<int, int>(a, i));
        edge[a].push_back(pair<int, int>(b, i));
    }

    dfs(0, -1, -1);

    cout << cmax << endl;;
    for(int i = 0; i < N-1; ++i) {
        cout << color[i] << endl;
    }
}


Measured memory_bytes: 9344
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    vector<ll> v(1000000);
    vector<ll> dp(1000000);
    dp[0] = 1;
    ll mod = 1e9+7;
    rep(i,n){
        cin >> v[i+1];
    }
    vector<ll> tmp;
    tmp.push_back(v[0]);
    for(int i = 1; i <=n;i++){
        if(tmp.back()!=v[i]){
            tmp.push_back(v[i]);
        }
    }
    vector<ll> s(1000000);
    for(int i = 1;i<tmp.size();i++){
        s[tmp[i]]+=dp[i-1];
        s[tmp[i]]%=mod;
        dp[i]=s[tmp[i]];
    }
    cout << dp[tmp.size()-1] << endl;
    return 0;
}

Measured memory_bytes: 25328
#include <iostream>
#include<algorithm>
using namespace std;
int main(void){
    long long N,i,count,ans;
    cin>>N;
    long long A[N];
    count=0;ans=0;
    for(i=0;i<N;i++){
        cin>>A[i];
        if(A[i]<0){
            count++;
            A[i]=-A[i];
        }
        ans+=A[i];
    }
    sort(A,A+N);
    if(count%2==1){
        ans=ans-A[0]*2;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const ll INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////


int main() {
	int N, M; cin >> N >> M;
	vector<int>V(N, 0);
	REP(i, M) {
		int a, b; cin >> a >> b;
		a--, b--;
		V[a]++;
		V[b]++;
	}
	bool ok = true;
	REP(i, N) {
		if (V[i] % 2 ==1) {
			ok = false;
			break;
		}
	}
	if (ok)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
#define loop(n, i) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;

using namespace std;
typedef long long ll;

struct State { int node, dist, cost; };
bool operator>(const State& a, const State& b) {
    return tie(a.dist, a.cost) > tie(b.dist, b.cost);
}

int main()
{
    while (1) {
        int n, m; cin >> n >> m;
        if (!n) break;

        vector<vector<State>> G(n);
        loop (m, i) {
            int u, v, d, c; cin >> u >> v >> d >> c;
            u--, v--;
            G[u].push_back({ v, d, c });
            G[v].push_back({ u, d, c });
        }

        priority_queue<State, vector<State>, greater<State>> Q;
        Q.push({ 0, 0, 0 });
        vector<int> vis(n);
        ll ans = 0;
        while (Q.size()) {
            auto crr = Q.top(); Q.pop();

            if (vis[crr.node]) continue;
            vis[crr.node] = 1;
            ans += crr.cost;

            for (auto nxt : G[crr.node]) {
                Q.push({ nxt.node, crr.dist + nxt.dist, nxt.cost });
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4404
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 99999999
#define eps 1e-9

int main(){
    int n;
    while(cin>>n&&n){
        vector<pair<double,string> > v;
        rep(i,n){
            string l;
            double p,a,b,c,d,e,f,s,m;
            cin>>l>>p>>a>>b>>c>>d>>e>>f>>s>>m;
            double x = ( (f*s*m)-p )/( a+b+c+(d+e)*m );
            v.pb(make_pair(999999.0-x,l));
        }
        sort(all(v));
        rep(i,v.size()){
            cout<<v[i].second<<endl;
        }
        cout<<"#"<<endl;
    }
}

Measured memory_bytes: 1252
# aba
# 最も小さい一文字はa
# a
# それに続く文字はb, （空文字）なので、ab
# それに続くのはaba
# ここで空文字しか続かなくなるため、
# 次はb
# たかだか5なので強引にいけんじゃね？

S=input()
K=int(input())
ans = []

from collections import defaultdict
dic = defaultdict(list)
for i in range(len(S)):
  dic[S[i]].append(i)

sortedS = sorted(dic.items(),key = lambda x:x[0])

# print(sortedS)

ans = set()
for candi in sortedS:
  ch,inds = candi[0],candi[1]
#  print(ch,inds)
  for i in inds:
    for j in range(K):
      ans.add(S[i:i+j+1])
  if len(ans) >= K:
    break
      
print(sorted(list(ans))[K-1])


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

using namespace std;

int a, b, c, d;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> a >> b >> c >> d;

    if(d <= a) cout << min(d, a) << "\n";
    else if (d <= a + b) cout << a << "\n";
    else cout << a - (d - (a + b)) << "\n";

    return 0;
}


Measured memory_bytes: 3600
/*
 * Author: .-O_O-.
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define en end()
#define f first
#define s second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define nx cout<<"\n"
#define int long long
// void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
                                                     
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]"<<endl;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
const ll mod = 1000000007;
const ll maxn = 100005;
const ll mm = 1e+18;
void solve()
{
    int n;
    cin>>n;
    int ans=0;
    rep1(i,n){
        int how=n/i;
        if(n%i==0) how--;
        ans+=how;
    }
    cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    rep1(_i,t){
        //cout<<"Case #"<<_i<<": ";
        solve();
        //nx;
    }
    return 0;
}

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

string s[100];
int main(){
	int h,w;scanf("%d%d",&h,&w);
	rep(i,h)cin>>s[i];
	rep(i,h)rep(j,w){
		if(s[i][j]=='#')continue;
		s[i][j]='0';
		for(int dx=-1;dx<=1;dx++){
			for(int dy=-1;dy<=1;dy++){
				int nx=i+dx,ny=j+dy;
				if(0<=nx&&nx<h&&0<=ny&&ny<w){
					if(s[nx][ny]=='#')s[i][j]++;
				}
			}
		}
	}
	rep(i,h)cout<<s[i]<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int vx[4] = {0, 1, 0, -1};
int vy[4] = {1, 0, -1, 0};
vector<vector <char> > s(50, vector<char>(50));
vector<vector <int> > counter(50, vector<int>(50, -1));
int main() {
    int H, W;
    int white = 0;
    cin >> H >> W;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> s.at(i).at(j);
            if(s.at(i).at(j) == '.') white++;
        }
    }

    queue<vector <int> > q;
    q.push({0, 0});
    counter.at(0).at(0) = 0;
    while(!q.empty()) {
        vector<int> now = q.front();
        q.pop();

        if(now[0] == H-1 && now[1] == W-1) break;

        for(int i = 0; i < 4; i++) {
            int next_y = now[0] + vy[i];
            int next_x = now[1] + vx[i];

            if(next_y >= 0 && next_y < H && next_x >= 0 && next_x < W) {
                if(s.at(next_y).at(next_x) == '.' && counter.at(next_y).at(next_x) == -1)  {
                    q.push({next_y, next_x});
                    counter.at(next_y).at(next_x) = counter.at(now[0]).at(now[1]) + 1;
                }
            }
        }
    }

    if(counter.at(H-1).at(W-1) != -1) {
        cout << white - counter.at(H-1).at(W-1) - 1 << endl;
    }else {
        cout << counter.at(H-1).at(W-1) << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef long double ld;
#define mp make_pair
#define pb push_back
// const ll mod = 1000000007;
const ll mod = 998244353;

const ll LLMAX = numeric_limits<long long>::max();

void sayNo() {
	cout << "NO" << endl;
}

void sayYes() {
	cout << "YES" << endl;
}


int main() {
	ll N;
	cin >> N;

	vi A(N + 1);
	vi B(N);

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

	ll count = 0;
	for (int i = 0; i < N; i++) {
		cin >> B[i];
		if (A[i] >= B[i]) {
			count += B[i];
		}
		else {
			if (A[i] + A[i + 1] >= B[i]) {
				count += B[i];
				A[i + 1] -= B[i] - A[i];
			}
			else {
				count += A[i] + A[i + 1];
				A[i + 1] = 0;
			}
		}
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 1792
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Integer[] pointArray = new Integer[n];
		for(int i =0;i < n;i++) {
			pointArray[i] = sc.nextInt();
		}
		Arrays.sort(pointArray,Collections.reverseOrder());
		int alice = 0;
		int bob = 0;
		for(int i =0;i < n;i++) {
			if(i % 2 ==0) {
				alice += pointArray[i];
			}else {
				bob += pointArray[i];
			}
		}
		System.out.println(alice -bob);
	}
}

Measured memory_bytes: 35884
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,k,i,ans=0;
    cin>>n>>k;
    ll arr[n];
    for(i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n,greater<ll>());
    for(i=0;i<n;i++){
        if(k>0)
            k-=1;
        else
            ans+=arr[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  long long sum=0;
  int m=arr[0];
  for(int i=0;i<n;i++){
    if(arr[i]<m)
      sum+=m-arr[i];
     m=max(m,arr[i]);
  }
  cout<<sum<<endl;
  return 0;
}

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

int cnt(int x){
    if (x%100!=0) return 0;
    return cnt(x/100)+1;
}
int main() {
	int D, N;
	cin >> D >> N;
	int count=0;
	for (int i=1; ; i++){
	    if (cnt(i)==D){
	        count++;
	    }
	    if (count==N){
	        cout << i << endl;
	        return 0;
	    }
	}
}

Measured memory_bytes: 256
fun main(args:Array<String>) {
    val k = readLine()!!.toInt()
    val (a,b) = readLine()!!.split(" ").map { it.toInt() }
    val num = (b/k)*k
    if(num in(a..b)) {
        println("OK")
    } else {
        println("NG")
    }
}


Measured memory_bytes: 36356
#include<iostream>
using namespace std;
int main()
{
	int n,m,c;
	cin>>n>>m>>c;
	int b[m],a[n][m];
	for(int i=0;i<m;i++)
	{
		cin>>b[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j];
		}
	}
	int sum=0,ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			sum+=a[i][j]*b[j];
		}
		sum+=c;
		if(sum>0)
		{
			ans++;
		}
		sum=0;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
int main(){
 int x,a ;cin>>x>>a ; 
 if(x<a) cout<<0<<endl ;
  else cout<<10<<endl ;
    return 0;
  }

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int n, CX[600], CY[600], ck, Mn;
char w[600][600];
int main(){
    int i, j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%s",w[i]+1);
        for(j=1;j<=n;j++){
            if(w[i][j]=='#')CX[i]++, CY[j]++, ck++;
        }
    }
    if(!ck){
        printf("-1\n");
        return 0;
    }
    Mn = n+1;
    for(i=1;i<=n;i++){
        Mn = min(Mn, n+1-CX[i] - (CY[i]!=0));
    }
    for(i=1;i<=n;i++)if(CY[i]!=n)Mn++;
    printf("%d\n",Mn);
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
using namespace std;



const long long int mod=1000000007;
const long long int INF=99999999999999999;
long long int mode=0;
string s,t;

long long int n,w,d,a[310000],q,L[120000],R[120000],mp_consumption[100000];
pair<long long int,long long int>ij[300005];

//最長単調増加列,0-indexed,要素数Nと配列a
class LIS{
    public:
    
	long long int LIS_Do(long long int N,long long int a[]){
		long long int LIS_table[250005];
		long long int LIS_start=250000,now=LIS_start,ng=now,ok=now+1,mid;
		for(int i=0;i<=LIS_start;i++){
			LIS_table[i]=INF;
		}
		for(int i=0;i<N;i++){
			ng=now;
			ok=LIS_start+1;
			
			while(ok-ng>1){
				mid=(ng+ok)/2;
				if(LIS_table[mid]>a[i]){
					ng=mid;
				}else{ok=mid;}
			}
			
			LIS_table[ng]=a[i];
			if(ng==now){
				now--;
			}
			
		}
		for(int i=LIS_start;i<=now;i++){
			cout<<LIS_table[i]<<endl;
		}
		return LIS_start-now;
	}
    
};

int main() {
	cout << fixed << setprecision(18);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]=10000000000-a[i];
    }
    LIS lis;
    cout<<lis.LIS_Do(n,a);

} 


Measured memory_bytes: 4224
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,a[4][N],f[N],g[N],w[N];
void biu()
{
	puts("No");
	exit(0);
}
void add(int x)
{
	for (int i=x;i<=n;i+=i&-i)
		w[i]++;
}
int qry(int x)
{
	int ans=0;
	for (int i=x;i;i-=i&-i)
		ans+=w[i];
	return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=3;i++)
	for (int j=1;j<=n;j++)	
		scanf("%d",&a[i][j]);
	int s1=0,s2=0,a1=0,a2=0;
	for (int i=1;i<=n;i++)
	{
		if ((a[2][i]-2)%3) biu();
		f[i]=(a[2][i]+1)/3;
		if ((f[i]^i)&1) biu();
		if (a[1][i]==a[2][i]-1) g[i]=0;
		else if (a[1][i]==a[2][i]+1) g[i]=1;
		else biu();
		if (a[1][i]+a[3][i]!=a[2][i]*2) biu();
	}
	for (int i=n;i>=1;i-=2)
	{
		a1^=g[i];
		s1+=qry(f[i]);
		add(f[i]);
	}
	memset(w,0,sizeof w);
	for (int i=n-1;i>=1;i-=2)
	{
		a2^=g[i];
		s2+=qry(f[i]);
		add(f[i]);
	}
	if ((a2!=(s1&1))||(a1!=(s2&1))) biu();
	puts("Yes");
}

Measured memory_bytes: 4480
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	pr := make([]int, m)
	yr := make([]int, m)
	mp := map[int][]int{}
	for i := 0; i < m; i++ {
		var p, y int
		fmt.Scan(&p, &y)
		pr[i] = p
		yr[i] = y
		if v, ok := mp[p]; ok {
			mp[p] = append(v, y)
		} else {
			mp[p] = []int{y}
		}
	}
	for k := range mp {
		sort.Ints(mp[k])
	}
	for i := 0; i < m; i++ {
		ar := mp[pr[i]]
		ind := sort.SearchInts(ar, yr[i])
		s := fmt.Sprintf("%06d%06d", pr[i], ind+1)
		fmt.Println(s)
	}
}


Measured memory_bytes: 20864
K=4000
S=[input()for i in range(3)]
A,B,C=S
a,b,c=len(A),len(B),len(C)
def F(S,T):
 R=[1]*(K*2+1)
 for i in range(-len(T),len(S)):
  for j in range(max(i,0),min(len(S),len(T)+i)):
   if S[j]!=T[j-i]and S[j]!="?"and T[j-i]!="?":
    R[i]=0
    break
 return R
S=F(A,B)
T=F(A,C)
U=F(B,C)
m=K*3
for p in range(-K,K+1):
 if S[p]!=0:
  for q in range(-K,K+1):
   if T[q]!=0 and U[q-p]!=0:
    m=min(m,max(p+b,q+c,a)-min(p,q,0))
print(m)

Measured memory_bytes: 55516
class SearchI
  def solve
    n = gets.chomp.to_i
    s = gets.scan(/\d+/).map(&:to_i)
    q = gets.chomp.to_i
    t = gets.scan(/\d+/).map(&:to_i)

    cnt = 0
    t.each do |x|
      if is_include(x, s)
        cnt += 1
      end
    end
    return cnt.to_s
  end

  def is_include(e, ls)
    ls.each do |x|
      if e == x
        return true
      end
    end
    return false
  end
end

if $0 == __FILE__
  puts SearchI.new.solve
end

Measured memory_bytes: 6884
#include <stdio.h>

int main(void){
  int a[4];
  int temp;
  for(int i = 0; i < 4; i++) scanf("%d", &a[i]);
  for(int i = 0; i < 4; i++){
    for(int j = i + 1; j < 4; j++){
      if(a[i] < a[j]){
	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
      }
    }
  }
  if(a[0] == 9 && a[1] == 7 && a[2] == 4 && a[3] == 1) printf("YES\n");
  else printf("NO\n");
  return 0;
}

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

using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    s = "#" + s;
    if (s[1] != '1') {
        cout << -1; return;
    }
    if (s[n] == '1') {
        cout << -1; return;
    }
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
            if (s[n - i] != '1') {
                cout << -1; return;
            }
        }
    }
    vector<int> vt;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') vt.push_back(i);
    }
    vt.push_back(n);
    int k = vt.size();
    for (int i = 1; i < k; i++) {
        if (i > 0) cout << vt[i - 1] << ' ' << vt[i] << "\n";
        for (int j = vt[i - 1] + 1; j < vt[i]; j++) {
            cout << j << ' ' << vt[i] << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(20);
    solve();
}


Measured memory_bytes: 2024
n, m = input().split()
N = int(n)
M = int(m)
P = [input().split() for i in range(M)]

num = [[0 for i in range(2)] for j in range(N)]
cntwa = 0
cntac = 0
for i in range(M):
    if num[int(P[i][0]) - 1][0] == 0:
        if P[i][1] == "AC":
            num[int(P[i][0]) - 1][0] = 1
            cntac += 1
        else:
            num[int(P[i][0]) - 1][1] += 1
            cntwa += 1

for j in range(N):
    if num[j][0] == 0:
        cntwa -= num[j][1]
print(cntac, cntwa)

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

int main(){
   int n;
   cin >> n;
   for (int i=0;4*i<=n;i++){
      for (int j=0;7*j<=n;j++){
         if (4*i+7*j==n){
            cout << "Yes" << endl;
            return 0;
         }
      }
   }
   cout << "No" << endl;
}


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

#define ll long long

ll n;

void solve(){
    cin>>n;
    ll sum;
    sum=0LL;
    for(int i=1; i<n; i++){
        sum+=i;
    }
    cout<<sum<<endl;
}

signed main(){
    //while(1)
    solve();
}

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

#define ll long long int
#define str string
#define ALL(a)  (a).begin(),(a).end()
#define P pair<ll,ll>

using Graph = vector<vector<int>>;

const int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
ll INFL = 1ll << 60, INF = 1 << 30, mod = 1e9 + 7, Min = INFL, Max = -1;
ll a, b, c, n, sum, A[500010], B[500000], rui[500000], dp[5000];
str S; bool check = true;	vector<ll> v;



int main() {
	//Code Line
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	a = 1;
	for (int i = 0; i < n; i++) {
		if (A[i] == a)a++;
	}
	if (a != 1)cout << n - a +1 << endl;
	else cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);

		String[] three = sc.nextLine().split(" ");
		int n1 = Integer.parseInt(three[0]);
		int n2 = Integer.parseInt(three[1]);
		int n3 = Integer.parseInt(three[2]);

		int[] nArray = {n1, n2, n3,};

		java.util.Arrays.sort(nArray);

		System.out.println(nArray[0] + " " + nArray[1] + " " + nArray[2]);
	}

}

Measured memory_bytes: 26156
#include <bits/stdc++.h>
int n;

int main() {
    std::cin >> n;
    int sum = 0;
    int max = 0;
    int tmp;
    for (int i = 0; i < n; i++) {
        std::cin >> tmp;
        sum += tmp;
        if (tmp > max) 
            max = tmp;
    }
    sum -= max;
    sum += (max/2);
    std::cout << sum << std::endl;
}


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

multiset<ll>st;

int main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;
    // ll ap[n+11];

    for(int i=0;i<n;i++){
    	ll l;
    	cin>>l;
    	st.insert(l);
    }

    while(st.size()>1){

    	auto x = st.begin();
    	ll val = (*x);
    	st.erase(x);
    	x= st.begin();
    	ll val1 = (*x);
    	st.erase(x);
    	st.insert((val1+val)/2);
    }

    auto x = st.begin();

    ll val = (*x);

    cout<<setprecision(15)<<val<<fixed;

    
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)
#define log2(x) (log(x)/log(2))

using namespace std;

ll pow(int x, int n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}


/*

 */
int n;
ll k,a[100000];
ll dp[50][2];

int main(){
  cin>>n>>k;
  REP(i,n)
    cin>>a[i];

  sort(a, a+n);
  int l = max(floor(log2(k)), floor(log2(a[n-1])));

  for(int i = l; i >=0; i--){
    sort(a,a+n);
    int j = a+n - lower_bound(a, a+n, pow(2,i)); //number of bit 1

    LOG("i=%d, j=%d, k=%d\n",i,j,(int)BIT(k,i));
    
    if(BIT(k,i) == 1){
      dp[i][1] = max(dp[i+1][1] + pow(2,i) * max(j,n-j), dp[i+1][0] + pow(2,i) * j);
      dp[i][0] = dp[i+1][0] + pow(2,i) * (n-j);
    } else {
      dp[i][1] = dp[i+1][1] + pow(2,i) * max(j,n-j);      
      dp[i][0] = dp[i+1][0] + pow(2,i) * j;
    }

    if(i >= floor(log2(k)))
      dp[i][1] = max(dp[i+1][1] + pow(2,i) * j, dp[i+1][0] + pow(2,i) * j);


    LOG("dp[%d][1]=%lld, dp[%d][0]=%lld\n", i,dp[i][1],i, dp[i][0]);
    
    FOR_IN(m, n-j, n)
      a[m] -= pow(2,i);
  }

  cout << max(dp[0][0], dp[0][1]) << endl;

  return 0;
}


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

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
template <typename T>
constexpr T INF = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity() : numeric_limits<T>::max() / 2;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (int i = start, i##_len = stop; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)
#define ALL(v) (v).begin(), (v).end()

template<typename T>
istream& operator>>(istream& in, vector<T>& a) { for (T& x : a) cin >> x; }

void LOG(const int& x) { cerr << x << "\n"; }
void LOG(const vector<int>& a) { for (int x : a) cerr << x << " "; cerr << "\n"; }

int ceil(int a, int b) { return (a - 1) / b + 1; }
i64 gcd(i64 a, i64 b) { while (b != 0) { i64 t = b; b = a % b; a = t; } return a; }
i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
i64 gcd(const vector<i64>& v) { return accumulate(ALL(v), 1LL, static_cast<i64(*)(i64, i64)>(gcd)); }
i64 lcm(const vector<i64>& v) { return v.empty() ? 0LL : accumulate(v.begin() + 1, v.end(), v[0], static_cast<i64(*)(i64, i64)>(lcm)); }

class UnionFind {
private:
  vector<int> par;
  vector<int> rnk;
  int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
public:
  UnionFind(int size) { par.resize(size); rnk.resize(size); REP(i, size) par[i] = i, rnk[i] = 0; }
  void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rnk[x] < rnk[y]) { par[x] = y; } else { par[y] = x; if (rnk[x] == rnk[y]) rnk[x]++; } }
  bool same(int x, int y) { return find(x) == find(y); }
};

struct InitCpp { InitCpp() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
} } initCpp;

signed main() {
  int n, t;
  cin >> n >> t;
  int s = 0;
  int c = 0;
  REP(_, n) {
    int x = 0;
    cin >> x;
    if (x < c) {
      s += x + t - c;
    } else {
      s += t;
    }
    c = max(c, x + t);
  }
  cout << s << endl;
}

Measured memory_bytes: 256
//#pragma GCC optimize ('O3')
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define pb push_back

const int N = 1e5 + 5;
const int M = 5e5 + 5;
const int OO = 1e9;
const int mod = 1e9 + 7;

int a,b,c,k;

void init() {}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> a >> b >> c >> k;

    while(b<=a) b *= 2, --k;
    while(c<=b) c *= 2, --k;

    cout << (k < 0 ? "No" : "Yes") << '\n';

    return 0;
}

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

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

struct UnionFind {
  vi p, sz;
  int n;

  UnionFind(int n): n(n) {
    p.resize(n);
    sz.assign(n, 1);
    
    for (int i = 0; i < n; i++)
      p[i] = i;
  }

  int find_set(int u) {
    return p[u] = u == p[u] ? u : find_set(p[u]);
  }

  void union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (v != u) {
      if (sz[u] > sz[v]) swap(u, v);
      p[u] = v;
      sz[v] += sz[u];
    }
  }
};

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

  int n, m;

  cin >> n >> m;

  UnionFind dsu(n);

  int u, v;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    dsu.union_set(u - 1, v - 1);
  }

  int ans = 0;
  for (int i = 0; i < n; i++)
    ans = max(ans, dsu.sz[dsu.find_set(i)]);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4728
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)
const long double PI = (acos(-1));

int main() {

	string s;
	cin >> s;

	int n = s.size(), mini = 1000;
	rep(i, 0, n - 2) {
		int ans = (s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
		mini = min(mini, abs(ans - 753));
	}

	cout << mini << endl;

	return 0;
}

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

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

// Lib
//

int main(){
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif
    string X; cin >> X;
    int stack = 0, count = 0;
    for (int i = 0; i < X.size(); ++i) {
        if (X[i] == 'S'){
            ++stack;
        }
        else if(X[i] == 'T' && stack > 0){
            --stack;
            ++count;
        }
    }
    int ans = X.size() - count*2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> P;

int h, w;
vector<string> s;

int max_dist(int sx, int sy) {
    if (s[sx][sy] == '#') return -1;
    queue<P> q;
    vector<vector<int>> dist(h, vector<int>(w, -1));
    dist[sx][sy] = 0;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    q.push(P(sx, sy));
    int res;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || h <= nx) continue;
            if (ny < 0 || w <= ny) continue;
            if (s[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push(P(nx, ny));
            res = dist[nx][ny];
        }
    }
    return res;
}

int main() {
    cin >> h >> w;
    s.resize(h);
    for (int i = 0; i < h; ++i) cin >> s[i];
    int ans = -1;
    rep(i, h) {
        rep(j, w) {
            ans = max(ans, max_dist(i, j));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3584
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const long long INF = 114514;
int a[100005][3];
long long dp[100005][3];
int main() {
  int n;
  cin >> n;
  for(int i=0; i<n; ++i) {
    cin >> a[i][0] >> a[i][1] >> a[i][2];
    dp[i][0] = dp[i][1] = dp[i][2] = 0;
  }
  for(int i=0;i<n; ++i) for(int j=0; j<3; ++j) for(int k=0; k<3; ++k) if(k!=j) dp[i+1][j]=max(dp[i+1][j], a[i][j]+dp[i][k]);
  cout << max(max(dp[n][0], dp[n][1]), dp[n][2]) << endl;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
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;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[5];
    for(int i = 0; i < 5; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < 5; i++) {
        if(a[i] == 0) {
            print(i + 1);
            return 0;
        }
    }
}

Measured memory_bytes: 3564
#include"bits/stdc++.h"
#include"math.h"
using namespace std;

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

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

#define REP(i,m,n) for(ll i = m; i < (ll)(n);++i)
#define rep(i,n) REP(i,0,n)
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
 
using vi=vc<int>;

const ll mod=1e9+7;
const ll INF = 1e18;
const int MAX = 8000;
const int MOD = 1000000007;



int main(){
  int n,k;cin >> n >> k;int ans=1;
  rep(i,n)ans=min(ans+k,ans*2);
  cout << ans;}

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

map<int,bool>mp;

main()
{
	int n;
	int ta=0,tb=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		if(mp[a])tb++;
		else
		{
			ta++;
			mp[a]=1;
		}
	}
	if(tb%2==1)ta--;
	printf("%d",ta);
}

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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

const int N = 110;

int n,W,w[N],v[N],sum;
ll dp[100100],ans;

int main()
{
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&v[i]);
        sum += v[i];
    }

    for(int i=1;i<=sum;i++)
        dp[i] = 1e18;

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

    for(int i=1;i<=sum;i++)
        if( dp[i] <= W )
            ans = i;

    printf("%lld\n",ans);
}


Measured memory_bytes: 4532