akhauriyash/Code-Regression huggingface dataset:
package main

import "fmt"

func main() {
	var N, W int
	fmt.Scanf("%d %d", &N, &W)
	w := make([]int, N)
	v := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d %d", &w[i], &v[i])
	}
	dp := make([][]int, N)
	for i := 0; i < N; i++ {
		dp[i] = make([]int, W+1)
	}
	for j := 0; j <= W; j++ {
		if w[0] <= j {
			dp[0][j] = v[0]
		}
	}
	for i := 1; i < N; i++ {
		for j := 0; j <= W; j++ {
			dp[i][j] = dp[i-1][j]
			if j-w[i] >= 0 {
				chmax(&dp[i][j], dp[i-1][j-w[i]]+v[i])
			}
		}
	}
	fmt.Println(dp[N-1][W])
}

func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}

func chmin(v1 *int, v2 int) {
	if *v1 > v2 {
		*v1 = v2
	}
}

func chmax(v1 *int, v2 int) {
	if *v1 < v2 {
		*v1 = v2
	}
}


Measured memory_bytes: 81408
using System;

namespace ConsoleApp1 {
    class Program {
        static void Main(string[] args) {
            int num = int.Parse(Console.ReadLine());
            string data = Console.ReadLine();
            int res = 1;
            for(int k = 0; k < num; k++) {
                if (k != (num - 1)) {
                    if (data.Substring(k,1) != data.Substring(k + 1,1)) {
                        res += 1;
                    }
                }
          
            }
            Console.Write(res);
        }
    }
}


Measured memory_bytes: 17376
#include<bits/stdc++.h>
using namespace std;
int A[27];
int main(){
	string S;
	cin>>S;
	for(int i=0;i<S.length();i++)A[S[i]-'A']++;
	for(int i=0;i<26;i++)if(A[i]>0&&A[i]!=2){
		cout<<"No";
		return 0;
	}
	cout<<"Yes";
}

Measured memory_bytes: 256
import std.stdio, std.math, std.algorithm, std.array, std.string, std.conv, std.container, std.range;
pragma(inline, true) T[] Reads(T)() { return readln.split.to!(T[]); }
alias reads = Reads!int;
pragma(inline, true) void scan(Args...)(ref Args args) {
    string[] ss = readln.split;
    foreach (i, ref arg ; args) arg = ss[i].parse!int;
}

void main() {
    int a,b; scan(a,b);
    writeln(max(a+b, a-b, a*b));
}


Measured memory_bytes: 256
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 500010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int n, d1, d2, group[MAXN], color[MAXN], cnt[10];
vector<int> edge[2][MAXN];
bool visited[MAXN];

int dist(II a, II b) {
    return (a.FI - b.FI) * (a.FI - b.FI) + (a.SE - b.SE) * (a.SE - b.SE);
}

void build(int d, int cs) {
    vector<II> a;
    FOR(i,-n,n)
        FOR(j,-n,n)
            if (i * i + j * j == d) a.push_back(II(i, j));
    FOR(i,0,n-1)
        FOR(j,0,n-1)
            for (II x : a) {
                int u = i + x.FI, v = j + x.SE;
                if (u >= 0 && u < n && v >= 0 && v < n) edge[cs][n * i + j].push_back(n * u + v);
            }
}

void dfs(int u, int col, int hs) {
    visited[u] = true;
    color[u] += hs * col;
    for (int v : edge[hs-1][u])
        if (!visited[v]) dfs(v, 1-col, hs);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> d1 >> d2;
    n <<= 1;
    build(d1, 0);
    build(d2, 1);

    FOR(i,0,n*n-1)
        if (!visited[i]) dfs(i, 0, 1);
    MS(visited, false);
    FOR(i,0,n*n-1)
        if (!visited[i]) dfs(i, 0, 2);

    FOR(i,0,n*n-1) cnt[color[i]]++;
    int res = 0, Max = 0, dem = 0;
    FOR(i,0,3)
        if (cnt[i] > Max) {
            Max = cnt[i];
            res = i;
        }
    FOR(i,0,n-1)
        FOR(j,0,n-1)
            if (color[n*i+j] == res) {
                cout << i << ' ' << j << "\n";
                dem++;
                if (dem * 4 == n * n) return 0;
            }
    return 0;
}


Measured memory_bytes: 126612
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class ABC
{
    public static void Main()
    {
        var split = Console.ReadLine().Split();
        int N = int.Parse(split[0]);
        int K = int.Parse(split[1]);
        double output = 0;

        for (int i = 1; i <= N; i++)
        {
            int coins = 0;
            int score = i;
            for (int j = 1; score <= K-1; j++)
            {
                score *= 2;
                coins++;
            }

            output += (1.0 / N) * Math.Pow(1.0 / 2, coins);


        }
        Console.WriteLine(output);


    }
}

Measured memory_bytes: 11092
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int main()
{

	int n;
	int ts = 0;
	int hs = 0;
	char taro[100+1] = {0};
	char hana[100+1] = {0};
	scanf("%d", &n);
	
	
	while (n)
	{
		int tlen, hlen, len, cmp;
		
		scanf("%s %s", taro, hana);
		tlen = strlen(taro);
		hlen = strlen(hana);
		len = tlen < hlen ? hlen : tlen;
		cmp = strncmp(taro, hana, len);
		if (cmp > 0)
			ts += 3;
		else if (cmp < 0)
			hs += 3;
		else
		{
			ts++;
			hs++;
		}
		n--;
	}
	printf("%d %d\n", ts, hs);
	return 0;
	
}

Measured memory_bytes: 608
#include <stdio.h>
 
int main(void)
{
    char str[128];
    char original[128];
 
    while (scanf("%s", str) != EOF){
        int i, j;
        int loop;
        char loop_char;
 
        for (i = j = 0; str[i] != 0; i++){
            if (str[i] == '@'){
                loop = str[++i] - '0';
                loop_char = str[++i];
                while (loop-- > 0){
                    original[j++] = loop_char;
                }
            }
            else {
                original[j++] = str[i];
            }
        }
        original[j] = 0;
        puts(original);
    }
 
    return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
#define re register
std::vector<int>to[1010],t[1010];
int ans[200100],fr[1010][1010],tg[1010][1010],I;
void dfs(re int a,re int*ff)
{
	for(re int i=0;i<to[a].size();i++)if(!ff[to[a][i]])
	{
		ff[to[a][i]]=ff[a];dfs(to[a][i],ff);
	}
}
int main()
{
	re int n,m,x,y;
	scanf("%d%d",&n,&m);
	for(re int i=1;i<=m;i++)scanf("%d%d",&x,&y),to[x].push_back(y),t[x].push_back(i);
	for(I=1;I<=n;I++)
	{
		fr[I][I]=tg[I][I]=-1;
		for(re int i=0;i<to[I].size();i++)if(!fr[I][to[I][i]])
		{
			fr[I][to[I][i]]=to[I][i];dfs(to[I][i],fr[I]);
		}
		for(re int i=to[I].size()-1;i>=0;i--)if(!tg[I][to[I][i]])
		{
			tg[I][to[I][i]]=to[I][i];dfs(to[I][i],tg[I]);
		}
	}
	for(I=1;I<=n;I++)
	{
		for(re int i=0;i<to[I].size();i++)if(to[I][i]==I)ans[t[I][i]]=1;
		else{//printf("**%d %d %d\n",I,i->to,tg[I][i->to]);
			ans[t[I][i]]=(fr[I][to[I][i]]==to[I][i]&&tg[I][to[I][i]]==to[I][i])==(fr[to[I][i]][I]==0);
		}
	}
	for(re int i=1;i<=m;i++)puts(ans[i]?"same":"diff");
}

Measured memory_bytes: 13056
#include <stdio.h>

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

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

const LL INF = 1LL << 61;

int H;
int W;
char C[314][314];
LL dp[314][314];
LL table[314][314];

LL Calc(int k) {
  fill(table[0], table[H+1], INF);
  reps(d, -H, H+1) {
    LL cost = 0;
    rep(i, H) {
      int j = i+d;
      if (j < 0 || j >= H) continue;
      cost += C[i][k] == C[j][k+1];
    }

    int h1 = min(H+d, H);
    int h2 = min(H-d, H);
    if (h1 < 0 || h2 < 0) continue;
    table[h1][h2] = cost;
    while (min(h1, h2) >= 1) {
      cost -= (C[H-h1][k] == C[H-h2][k+1]);
      h1--;
      h2--;
      table[h1][h2] = cost;
    }
  }

  rep(i, H+1) assert(table[i][0] == 0);
  rep(i, H+1) assert(table[0][i] == 0);
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> H >> W;
  rep(i, H) {
    rep(j, W) {
      cin >> C[H-1-i][j];
    }
  }

  LL ans = 0;
  rep(k, W-1) {
    Calc(k);
    fill(dp[0], dp[H+1], INF);
    dp[H][H] = 0; 

    rrep(h1, H+1) {
      rrep(h2, H+1) {
        LL c = table[h1][h2];
        if (h1 > 0) MN(dp[h1-1][h2], dp[h1][h2]+c);
        if (h2 > 0) MN(dp[h1][h2-1], dp[h1][h2]+c);
      }
    }
    
    ans += dp[0][0];
  }
  cout << ans << endl;
}


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

int main() {
  int A,B,C,X,Y;
  cin >> A >> B >> C >> X >> Y ;
  int N = max(X,Y);
  vector<long long> costArr;
  for(int i=0;i<=N;i++){ //C
    long long cost;
    cost = 2*C*i + max(0,A*(X-i)) + max(0,B*(Y-i));
    costArr.push_back(cost);
  }
  sort(costArr.begin(), costArr.end());
  cout << costArr.at(0) << endl;
  return 0;
}

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

A = list(map(int, input().split(' ')))

B = list(map(int, input().split(' ')))

if sum(A) < sum(B):
    print(-1)
    exit()
    
# 少ないところの合計 + 差が大きい順にソートして、全マイナス分を引ききるまでの個数

point = 0
upper = []
count = 0

for a, b in zip(A, B):
    if a < b:
        # 準備不足
        point += b - a
        count += 1
        
    else:
        # 準備OK
        upper.append(a - b)
        
upper.sort(reverse = True)

index = 0
while point > 0:
    point -= upper[index]
    index += 1
    
print(count + index)

Measured memory_bytes: 18356
#include <iostream>
using namespace std;
void ABC50(void);
void ABC52(void);
void ABC53(void);
void ABC54(void);
void ABC55(void);
void ABC56(void);
void ABC57(void);
void ABC58(void);
void ABC59(void);

int main(void){
    ABC58();
    return 0;
}

void ABC58(void){
    int a,b,c;
    cin>>a>>b>>c;
    if(c-b==b-a)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n = int(readline())
ab = [list(map(int,readline().split())) for i in range(n)]
ab.sort(key=lambda x: -x[0]-x[1])
ans = 0
for i in range(n):
    if i%2:
        ans -= ab[i][1]
    else:
        ans += ab[i][0]
print(ans)



Measured memory_bytes: 32124
#include <iostream>
#define N_MAX 100
using namespace std;

int N,A,B,i,j,k;
int a[N_MAX];
int num[N_MAX] = {0};
int ans=0;
int r,g,b;

int main(){
  cin >> N;
  cin >> A;
  while(N >= 500){
    N-=500;
  }

  if (A < N) cout << "No" << endl;
  else  cout << "Yes" << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int mod = (int)1e9 + 7;
const int inf = mod;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 200+4;

int n, adj[N][N];

int solve(int start){

   queue<int> q;
   q.push(start);

   vector<int> vis;

   vis.assign(n, 0);
   vis[start] = 1;

   while(!q.empty()){
      int x = q.front();
      q.pop(); 

      for (int i = 0; i < n; ++i)
      {
         if(i == x)
            continue;
         if(!adj[x][i]){
            continue;
         }
         if(vis[i]){
            // tr(start, i, x, vis[i], vis[x]);
            if(abs(vis[i] - vis[x]) != 1){
               return -1;
            }
         }
         else{
            q.push(i);
            vis[i] = vis[x] + 1;
         }
      }
   }

   return *max_element(vis.begin(), vis.end());;
}

int32_t main(){_

   cin >> n;

   for (int i = 0; i < n; ++i)
   {
      for (int j = 0; j < n; ++j)
      {
         char x;
         cin >> x;
         adj[i][j] = x - '0';
      }
   }
   
   int ans = -1;
   for (int i = 0; i < n; ++i)
   {
      smax(ans, solve(i));
   }

   cout<<ans;

   return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
  int sum=0;
  string s,t;
  cin>>s>>t;
  for(int i=0;i<s.size();i++){
    if(s[i]==t[i])
      sum++;
  }
  if(sum==s.size())cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 3556
from collections import deque

def bfs(loc):
    global tem_ans
    d = [[float('inf')] * w for i in range(h)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque([])
    que.append(loc)
    d[loc[0]][loc[1]] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and d[nx][ny] == float('inf'):
                d[nx][ny] = d[p[0]][p[1]] + 1
                que.append([nx,ny])
                if tem_ans < d[nx][ny]:
                    tem_ans = d[nx][ny]
    return tem_ans

h,w = map(int,input().split())

maze = [list(input()) for i in range(h)]


ans = 0
tem_ans = 0

loc = []
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            loc = [i,j]
        else:
            continue
        ans = max(ans,bfs(loc))

print(ans)


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

using namespace std;

template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int H, W, M;
  cin >> H >> W >> M;
  set<pair<int, int>> st;
  vector<int> HC(H, 0), WC(W, 0);
  for (int i = 0; i < M; i++) {
    int h, w;
    cin >> h >> w;
    h--, w--;
    HC[h]++, WC[w]++;
    st.insert(make_pair(h, w));
  }
  int mh = 0, mw = 0;
  for (int i = 0; i < H; i++) {
    chmax(mh, HC[i]);
  }
  for (int i = 0; i < W; i++) {
    chmax(mw, WC[i]);
  }
  vector<int> ih, iw;
  for (int i = 0; i < H; i++) {
    if (HC[i] == mh) ih.emplace_back(i);
  }
  for (int i = 0; i < W; i++) {
    if (WC[i] == mw) iw.emplace_back(i);
  }
  int res = mh + mw;
  for (const auto& h : ih) {
    for (const auto& w : iw) {
      if (st.find(make_pair(h, w)) != st.end()) continue;
      cout << res << '\n';
      return 0;
    }
  }
  cout << res - 1 << '\n';
  return 0;
}


Measured memory_bytes: 23756
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int S;
    cin>>S;
    int x1,x2,y1,y2;
    x1=1000000000-S%1000000000;
    x2=1;
    int y=S+x1;
    int n=0;
    while(y%10==0){
        n++;
        y/=10;
    }
    y1=1;
    rep(i,n){
        y1*=10;
        if(i==8) break;
    }
    y2=(S+x1)/y1;
    if(S==1000000000000000000){
        x1=1000000000;
        x2=x1;
        y1=0;
        y2=0;
    }
    cout<<0<<" "<<0<<" "<<x1<<" "<<y1<<" " << y2 << " "<<x2<<endl;



}


Measured memory_bytes: 256
from collections import defaultdict
n,m=map(int,input().split())
h=list(map(int,input().split()))
ma=[0 for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  ma[a-1]=max(ma[a-1],h[b-1])
  ma[b-1]=max(ma[b-1],h[a-1])
cnt=0
for i,hh in enumerate(ma):
  if h[i] > hh:
    cnt+=1
print(cnt)
  


Measured memory_bytes: 20388
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
// #define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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; }

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    
    ll n;
    cin>>n;
    ll l[200];
    rep(i,n){
        cin>>l[i];
    }
    sort(l,l+n);
    ll sum=0;
    rep(i,n-1) sum+=l[i];
    if(l[n-1]<sum) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


    return 0;
}


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

bool checkPalindrominNum(int input){
        int n = input;
        int tmp = 0;
        while(n!=0){
                tmp*=10;
                tmp+=n%10;
                n/=10;
        }
        if(input==tmp){
                return true;
        }else{  
                return false;
        }
}

int A,B;

int main()
{       
        cin >> A >> B;
        int ans = 0;
        
        for(int i=A;i<=B;i++){
                if(checkPalindrominNum(i)){
                        ans+=1;
                }       
        }       
        cout << ans << endl;
}       

Measured memory_bytes: 256
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

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

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

const int INF = 1001001001;

void sit(char c, char chair[], int n)
{
	if(c == 'A'){
		rep(i, n){
			if(chair[i] == '#'){
				chair[i] = 'A';
				return;
			}
		}
	}
	else if(c == 'B'){
		int pos = -1;
		for(int i=n-1; i>=0; --i){
			if(chair[i] == '#'){
				pos = i;
				if(i!=0 && chair[i-1]=='A')
					continue;
				if(i!=n-1 && chair[i+1]=='A')
					continue;
				chair[i] = 'B';
				return;
			}
		}
		chair[pos] = 'B';
	}
	else if(c == 'C'){
		rep(i, n){
			if(chair[i] != '#'){
				if(i!=n-1 && chair[i+1]=='#'){
					chair[i+1] = 'C';
					return;
				}
				if(i!=0 && chair[i-1]=='#'){
					chair[i-1] = 'C';
					return;
				}
			}
		}
		chair[n/2] = 'C';
	}
	else{
		int B = 0;
		int Bid;
		rep(i, n){
			int dist = INF;
			rep(j, n){
				if(chair[j] != '#')
					dist = min(dist, abs(i-j));
			}
			if(dist > B){
				B = dist;
				Bid = i;
			}
		}
		chair[Bid] = 'D';
	}
}

int main()
{
	int n, m;
	while(scanf("%d%d", &n, &m), n){
		char chair[100];
		fill(chair, chair+n, '#');
		rep(i, m){
			char c;
			scanf(" %c", &c);
			sit(c, chair, n);
		}
		rep(i, n)
			putchar(chair[i]);
		puts("");
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;
typedef pair<int, int> pii;

int main(){

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

        string s[n], t[n];
        for(int i=0; i<n; i++) cin>> s[i]>> t[i];
        int a[n], b[n];
        for(int i=0; i<n; i++){
            a[i]=60*60*stoi(s[i].substr(0, 2))+60*stoi(s[i].substr(3, 2))+stoi(s[i].substr(6, 2));
            b[i]=60*60*stoi(t[i].substr(0, 2))+60*stoi(t[i].substr(3, 2))+stoi(t[i].substr(6, 2));
        }
        int v[24*60*60]={};
        for(int i=0; i<n; i++){
            v[a[i]]+=1;
            v[b[i]]-=1;
        }
        for(int i=1; i<24*60*60; i++){
            v[i]+=v[i-1];
        }
        int k=0;
        for(int i=0; i<24*60*60; i++){
           	k=max(k, v[i]);
        }
        cout<< k<< endl;
    }

    return 0;
}

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

using namespace std;

typedef long long LL;

#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LEN(a) int((a).size())
#define SORT(a) sort((a).begin(), (a).end())
#define CLR(a) memset((a), 0, sizeof(a))

const double EPS = 1e-10;

int main() {
    int n, k;
    cin >> n >> k;
    if (k == 1) cout << 0 << endl;
    else cout << n - k << endl;
    return 0;
}


Measured memory_bytes: 256
function Main(input) {
    var N = parseInt(input[0])
    var H = input.slice(1);
    var count = 0;
    var maxH = 0;
    H.forEach(element => {
        var h = parseInt(element);
        if(maxH <= h) {
            count++;
            maxH = h;
        }
    });
    console.log(count);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));


Measured memory_bytes: 7372
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = sorted(Counter(A).values(),reverse=True)
    ans = 0
    while K < len(c):
        ans += c.pop()
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 98896
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<vector<int> > Graph;
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; }

int temp;
bool ok(int i){
    if(temp&(1<<i)) return true;
    else return false;
}
int main(){
    string s;
    cin >> s;
    int a,b,c,d;
    a=s[0]-'0';
    b=s[1]-'0';
    c=s[2]-'0';
    d=s[3]-'0';
    for(temp=0;temp<(1<<3);temp++){
        int now=a;
        for(int i=0;i<3;i++){
            if((1<<i)&temp){
                now= now + s[i+1]-'0';
            }
            else{
                now= now - s[i+1]+'0';
            }
        }
        if(now==7){
            string ans = "";
            ans += s[0];
            if(ok(0))ans+="+";
            else ans += "-";
            ans+=s[1];
            if(ok(1))ans+="+";
            else ans += "-";
            ans+=s[2];
            if(ok(2))ans+="+";
            else ans += "-";
            ans+=s[3];
            ans+="=7";
            cout << ans << endl;
            return 0;
        }
    }

    return 0;
}

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

int main(void) {
    long long n, a, b;
  	cin >> n >> a >> b;
  	
  	if((b - a) % 2 == 0) {
        cout << (b - a) / 2;
    } else {
      	cout << min(a - 1, n - b) + 1 + (b - a - 1) / 2;
    }

  	return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

int RankOfF2Vectors(const vector<int64>& input_xs) {
  vector<int64> xs(input_xs.begin(), input_xs.end());
  sort(xs.begin(), xs.end());
  reverse(xs.begin(), xs.end());
  for (int k = 59; k >= 0; k--) {
    for (int i = 0; i < xs.size(); i++) {
      if (xs[i] >= (1LL << (k + 1))) {
        continue;
      } else if (xs[i] >= (1LL << k)) {
        // xs[i] is an axis.
        for (int j = i + 1; j < xs.size(); j++) {
          if (xs[j] >= (1LL << k)) {
            xs[j] ^= xs[i];
          }
        }
        sort(xs.begin(), xs.end());
        reverse(xs.begin(), xs.end());
        // cout << "axis: " << xs[i] << endl;
        // cout << "xs: " << xs << endl;
        break;
      } else {
        break;
      }
    }
  }

  int count = 0;
  for (int64 x : xs) {
    if (x > 0) count++;
  }
  return count;
}

int Solve() {
  int n;
  cin >> n;
  vector<int64> as(n);
  for (int i = 0; i < n; i++) {
    cin >> as[i];
  }
  string s;
  cin >> s;

  vector<int64> xs;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '0') {
      xs.push_back(as[i]);
    } else {
      int r1 = RankOfF2Vectors(xs);
      vector<int64> ys(xs.begin(), xs.end());
      ys.push_back(as[i]);
      int r2 = RankOfF2Vectors(ys);
      if (r2 > r1) return 1;
    }
  }
  return 0;
}

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

  // cout << RankOfF2Vectors({6, 4}) << endl;
  // cout << RankOfF2Vectors({6, 4, 2}) << endl;
  // cout << RankOfF2Vectors({1, 5, 9, 8, 1}) << endl;

  int num_cases;
  cin >> num_cases;
  for (int i = 0; i < num_cases; i++) {
    cout << Solve() << endl;
  }
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define vi vector<int>
#define srt(a) sort(a.begin(), a.end());
#define se second
#define fi first
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10);
    cout << fixed;
    LL h,n; 
    cin>>h>>n;
    vector <LL> v(n);
    forn(i,n) cin>>v[i];
    LL s = 0;
    for(auto i:v) s+=i;
    cout<<((s>=h?"Yes":"No"))<<endl;
    return 0;
}



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

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

ll solv(ll H, ll W) {
	ll ans = W*H, s1, s2, s3;
	for(ll i=1; i<H-1; i++) {
		ll x = H-i;
		s1 = W * i;
		s2 = W * (x/2);
		s3 = W * (x/2 + x%2);
		ans = min(ans, mmm(s1,s2,s3));
	}
	for(ll i=1; i<H; i++) {
		ll x = H-i;
		s1 = i * W;
		s2 = x * (W/2);
		s3 = x * (W/2 + W%2);
		ans = min(ans, mmm(s1,s2,s3));
	}
	return ans;
}

int main() {

	int H, W;
	cin >> H >> W;

	cout << min(solv(H,W), solv(W,H)) << endl;

}

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

using namespace std;
 
void fac(int x)
{
    int i;
    for(i=1; x>0; i+=2)
    {
        x-=i;
    }
    if(x==0)
        printf("Yes\n");
    else
        printf("No\n");
}
int main()
{
    string a, b;
    cin >> a >> b;
    string m;
    m = a + b;
    int t;
    stringstream ss;
    ss << m;
    ss >> t;
    //cout << m;
    //scanf("%d",&x);
    fac(t);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=998244353 ;


ll dp[333][101010],dp2[333][101010];
int main(){
    int n;
    cin>>n;
    int a[n];
    int sum=0;
    rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }
    dp[0][0]=dp2[0][0]=1;
    rep(i,n)rep(j,90010){
        (dp[i+1][j]+=2*dp[i][j])%=mod;
        (dp[i+1][j+a[i]]+=dp[i][j])%=mod;
        (dp2[i+1][j]+=dp2[i][j])%=mod;
        (dp2[i+1][j+a[i]]+=dp2[i][j])%=mod;
    }
    ll res=0;
    if(sum%2==0)res=dp2[n][sum/2];
    sum=(sum+1)/2;
    ll cnt=0;
    rep(i,100000){
        if(i>=sum)cnt+=dp[n][i];
        cnt%=mod;
    }
    ll ans=1;
    rep(i,n)ans=ans*3%mod;
    cout<<(ans+3*mod-3*cnt+3*res)%mod<<endl;
    return 0;
}

Measured memory_bytes: 476544
import io.StdIn.{readInt, readLine}
object Main extends App {
  val n = readInt
  val _s = readLine.toSeq
  val s = _s.tail :+ _s.head

  sealed abstract class Animal
  final case object Sheep extends Animal {
    override def toString = "S"
  }
  final case object Wolf extends Animal {
    override def toString = "W"
  }

  println {
    solve(s, List(Sheep, Sheep)) match { case a1 :: a2 :: as if (a1, a2) == (Sheep, Sheep) => as.mkString.reverse; case _ =>
    solve(s, List(Sheep, Wolf)) match { case a1 :: a2 :: as if (a1, a2) == (Sheep, Wolf) => as.mkString.reverse; case _ =>
    solve(s, List(Wolf, Sheep)) match { case a1 :: a2 :: as if (a1, a2) == (Wolf, Sheep) => as.mkString.reverse; case _ =>
    solve(s, List(Wolf, Wolf)) match { case a1 :: a2 :: as if (a1, a2) == (Wolf, Wolf) => as.mkString.reverse; case _ => "-1" }}}}
  }

  def solve(s: Seq[Char], as: List[Animal]): List[Animal] = {
    if (s.isEmpty) as
    else {
      val s1 = s.head
      val List(a1, a0) = as.take(2)
      val a2 = if (a0 == a1) (if (s1 == 'o') Sheep else Wolf)
                        else (if (s1 == 'x') Sheep else Wolf)
      solve(s.tail, a2 :: as)
    }
  }
}


Measured memory_bytes: 113288
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int rn,rm,n,i,t,q[N];
struct arr{int x,y;}a[N];
bool operator < (arr A,arr B){return A.x<B.x;}
int read(){
	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
int get(){
	int x=read(),y=read();
	if (x==0||y==rm) return x+y;
	if (x==rn||y==0) return (rn+rm<<1)-x-y;
	return -1;
}
int main(){
	rn=read();rm=read();
	for (i=read();i--;){
		int x=get(),y=get();if (x>y) swap(x,y);
		if (x>=0) a[++n]=(arr){x,y};
	}
	sort(a+1,a+n+1);
	for (i=1;i<=n;i++){
		for (;t&&q[t]<a[i].x;t--);
		if (t&&a[i].y>q[t]){puts("NO");return 0;}
		q[++t]=a[i].y;
	}
	puts("YES");
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
 
using namespace std;

int binpow(int,int);
void dfs( vector< vector<int> >&, int , vector<int>& );
void bfs( vector< vector<int> >&, int , vector<int>& );

void solve()
{
    int x;
    cin>>x;

    rep(a,-1000,1000)
    {
        rep(b,-1000,1000)
        {
            if ( (binpow(a,5)-binpow(b,5)) == x )
            {
                cout<<a<<" "<<b<<endl;
                return;
            }
        }
    }
}

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

void dfs ( vector< vector<int> > &v , int x , vector<int> &vis )
{
    vis[x] = 1;

    rep(i,0,v[x].size())
    {
        if( vis[v[x][i]] == 0 )
        {
            dfs(v,v[x][i],vis);
        }
    }
}

void bfs( vector< vector<int> > &v , int x , vector<int> &vis )
{
    queue<int> q;
    q.push(x);

    while( !q.empty() )
    {
        int p = q.front();
        q.pop();

        rep(i,0,v[p].size())
        {
            if ( vis[v[p][i]] == 0 )
            {
                vis[v[p][i]] = 1;
                q.push(v[p][i]);
            }
        }
    }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
int main() {
    string s;
    cin >> s;
    vector<int> arr(s.size());
    int count0 = 0;
    int count1 = 0;
    rep(i,s.size()){
        arr[i] = s[i] - '0';
        //cout << arr[i] << endl;
        if (i % 2 == 0){
            if (arr[i] == 0){
                count1 ++;
            }else{
                count0 ++;
            }
        }else{
            if (arr[i] == 0){
                count0 ++;
            }else{
                count1 ++;
            }

        }
    }
    if (count0 > count1){
        cout << count1<<endl;
    }else{
        cout <<count0<<endl;
    }
    return 0;
    
}

Measured memory_bytes: 896
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <set>

using namespace std;
using ll = long long;

typedef pair<ll, ll> P;

const int MOD = 1000000007;
const ll INF = 1LL << 60;


// LRUD
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
// const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

vector<vector<int> > vvi;
vector<vector<vector<int> > > vvvi;

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; }

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }


int main(int argc, char**argv){
    int n, k;
    cin >> n >> k;
    vector<ll> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];

    vector<ll> left, right;
    bool zero_exists = false;
    for (int i = 0; i < n; i++){
        if (x[i] > 0) right.push_back(x[i]);
        else if (x[i] < 0) left.push_back(-x[i]);
        else zero_exists = true;
    }
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    if (zero_exists) k--;

    if (k == 0){
        cout << 0 << endl;
        return 0;
    }

    ll ans = 9999999999;

    if (left.size() >= k) chmin(ans, left[k-1]);
    if (right.size() >= k) chmin(ans, right[k-1]);

    for (int i = 0; i < k; i++){
        if (i < left.size() && 0 <= k-i-2 && k-i-2 < right.size()){
            chmin(ans, 2 * left[i] + right[k-i-2]);
        }
    }
    for (int i = 0; i < k; i++){
        if (i < right.size() && 0 <= k-i-2 && k-i-2 < left.size()){
            chmin(ans, left[k-i-2] + 2 * right[i]);
        }
    }

    cout << ans << endl;

    return 0;
}





















Measured memory_bytes: 2424
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using namespace std;
const ll MOD=1e9+7;

map<pair<ll,ll>,ll> mp;
const ll MAX_N = 1e6+5;
ll fuct(ll n) {
	ll res = 1;
	for(ll i=1;i<=n;i++) {
		res *= i;
		res %= MOD;
	}
	return res;
}

//aのb乗
ll calc(ll a, ll b) {
	ll res = 1;
	while(b > 0) {
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
	/*
	if(mp.count(make_pair(a,b))) {
		return mp[make_pair(a,b)];
	}
    if (b==0){
      return mp[make_pair(a,b)] = 1;
    }else if (b==1){
      return mp[make_pair(a,b)] = a;
    }else if (b%2==0){
      ll tmp=calc(a,b/2);
      return mp[make_pair(a,b)] = tmp*tmp%MOD;
    }else{
      return mp[make_pair(a,b)] = a*calc(a,b-1)%MOD;
    }
	*/
}

ll x, y;

int main(){
	cin >> x >> y;
	if( !((2*x-y)%3== 0 && (2*y-x)%3 == 0) ) {
		cout << 0 << endl;
		return 0;
	}
	ll a = (2*x-y)/3;
	ll b = (2*y-x)/3;
	if(a < 0 || b < 0) {
		cout << 0 << endl;
		return 0;
	}
	cout << ((fuct(a+b)*calc(fuct(a),MOD-2))%MOD*calc(fuct(b),MOD-2))%MOD << endl;
}

Measured memory_bytes: 256
#include <stdint.h>
#include <array>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <limits>
#include <tuple>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);
static const ll MOD = 1000000007;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout << #x << ": " << x << endl

int main() {
  ll N;
  cin >> N;
  ll count = 0;
  ll remain = 0;
  REP(i, N) {
    ll A;
    cin >> A;
    if (A == 0) {
      remain = 0;
    } else {
      ll b = (A + remain) / 2;
      count += b;
      remain = A + remain - b * 2;
    }
  }
  std::cout << count << std::endl;
}


Measured memory_bytes: 256
import math
from collections import defaultdict
N = int(input())


def trial_division(n):
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            d[num] += 1
    if n != 1:
        d[n] += 1


d = defaultdict(int)
mod = 10**9 + 7
for i in range(2, N+1):
    trial_division(i)

ans = 1
for v in d.values():
    ans *= v+1
    ans %= mod
print(ans)


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

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

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

    int ans = 1;
    for(int i = 1; i < n; i++){
        bool can = true;
        for(int j = 0; j < i; j++){
            if(h[i] < h[j]) can = false;
        }
        if(can) ans++;
    }
    cout << ans << endl;
}

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

int main() {
  int n, cnt = 0;
  cin >> n;
  
  for(int i = 0; i < n; i++){ 
    int l, r;
    cin >> l >> r;
    for(; l <= r; l++)
      cnt++;
  }
  cout << cnt;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main () {
  int N ;
  cin >> N;
  int a = 0;
  for (int i = 0; i < N ; i ++) {
    int ai;
    cin >> ai;
    while (true) {
      if (ai % 2 == 1) break;
      ai /= 2;
      a ++;
    }
  }
  cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#define MAX_CALC_N (1<<10)

int dp[MAX_CALC_N][100005];

int v[300005];
int w[300005];

void dfs(int now, int p){
  if(now >= MAX_CALC_N) return;

  rep(i,100005){
    dp[now][i] = max(dp[now][i], dp[p][i]);
    if(i+w[now]<100005) dp[now][i+w[now]] = max(dp[now][i+w[now]], dp[p][i]+v[now]);
  }

  dfs(2*now, now);
  dfs(2*now+1, now);
}


int main(){
  int N;
  cin >> N;
  rep(i,N){
    cin >> v[i+1] >> w[i+1];
  }

  dfs(1, 0);
  
  int Q;
  cin >> Q;

  rep(q,Q){
    int x, L;
    cin >> x >> L;

    if(x < MAX_CALC_N){
      cout << dp[x][L] << endl;
    }else{
      vector<int> pp;
      while(x >= MAX_CALC_N){
        pp.push_back(x);
        x /= 2;
      }
      int ret = dp[x][L];
      for(ll S=0; S<(1<<pp.size()); S++){
        int wsum = 0;
        int vsum = 0;
        rep(i,pp.size()){
          if((S>>i)&1){
            wsum += w[pp[i]];
            vsum += v[pp[i]];
          }
        }
        if(wsum <= L){
          ret = max(ret, dp[x][L-wsum] + vsum);
        }
      }
      cout << ret << endl;
    }
  }
  
  
  return 0;
}



Measured memory_bytes: 405312
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n;
    long a,b,ans=0,maxa=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&a,&b);
        if(maxa<a){
            maxa=a;
            ans=a+b;
        }
    }
    printf("%ld\n",ans);
}

Measured memory_bytes: 256
import java.util.*;
import java.awt.*;
import static java.lang.System.*;
import static java.lang.Math.*;
//Loopで使う文字列の長さは固定！
//intで大丈夫？オーバーフローしない？
//Loop回数は本当に10⁹以内になってる？Loopは回る？？
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(in);
        long a=sc.nextLong();
        long b=sc.nextLong();
        long k=sc.nextLong();
        for (int i = 0; i <k ; i++) {
            if(i%2==0){
                if(a%2==1){
                    a--;
                }
                a/=2;
                b+=a;
            }else{
                if(b%2==1){
                    b--;
                }
                b/=2;
                a+=b;
            }
        }
        out.println(a+" "+b);
    }
}

Measured memory_bytes: 21716
import sys

sys.setrecursionlimit(10000)


def memoize(f):
    cache = {}

    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    return func


@memoize



def combi(n, r):
  if r == 0 or n == r:
    return 1
  return combi(n-1, r-1) + combi(n-1, r)

n, a, b = map(int, input().split())
items = sorted(map(int, input().split()), reverse=True)
max_ave_list = items[:a]
print(sum(max_ave_list)/len(max_ave_list))

m = max_ave_list.count(max_ave_list[-1])
l = items.count(max_ave_list[-1])
if l == m:
  print(1)
elif max_ave_list[0] != max_ave_list[-1]:
  print(combi(l, m))
else:
  print(sum(combi(l, k) for k in range(m, min(b, l) + 1)))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;
typedef vector<char> vech;

int main() {
    ll A,B; cin>>A>>B;
    vech S(A+B+1);rep0(i,A+B+1){cin>>S[i];}
    ll m=S.size();
    bool flag=true;
    rep0(i,A){
        if(!(S[i]-'0'<=9&&0<=S[i]-'0')){
            flag=false;
        }
    }
    for(ll i=A+1;i<=A+B;i++){
        if(!(S[i]-'0'<=9&&0<=S[i]-'0')){
            flag=false;
        }
    }
    if(S[A]=='-'&&flag){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
}


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

using namespace std;
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++){
        int a;
        scanf("%d", &a);
        n -= a;
    }
    if (n < 0) printf("-1");
    else printf("%d\n", n);
}





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

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000000000000007;
const int MOD=998244353;
const int MOD1=1e9+7;
class Seg_Tree{
    private:
    int e=1000000000000000007;
    int n;
    vector<int> node;
    public:
    int process(int left,int right){
        if(left==e)return right;
        if(right==e)return left;
        return max(right,left);
    }
    Seg_Tree(vector<int> v){
        int num=1;
        int size=v.size();
        while(num<size){
            num*=2;
        }
        n=num;
        node.resize(2*num-1,e);
        for(int i=0;i<size;i++)node[i+num-1]=v[i];
        for(int i=n-2;i>=0;i--)node[i]=process(node[i*2+1],node[i*2+2]);
    }
    void update(int x,int val){
        x+=(n-1);
        node[x]=val;
        while(x>0){
            x=(x-1)/2;
            node[x]=process(node[x*2+1],node[x*2+2]);
        }
    }
    int out(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(a>=r||b<=l)return e;
        if(a<=l&&b>=r)return node[k];
        int vl=out(a,b,k*2+1,l,(l+r)/2);
        int vr=out(a,b,k*2+2,(l+r)/2,r);
        return process(vl,vr);
    }
};
signed main(){
  int n;cin>>n;
  vector<int> x(n);
  vector<int> d(n);
  vector<P> buf(n);
  rep(i,n){
    cin>>buf[i].first>>buf[i].second;
    buf[i].first+=MOD1;
  }
  sort(buf.begin(),buf.end());
  rep(i,n){
    x[i]=buf[i].first;
    d[i]=buf[i].second;
  }
  x.push_back(inf);
  Seg_Tree right(vector<int>(n+10,0));
  rep(i,n+1){
    right.update(i,i);
  }
  for(int i=n-1;i>=0;--i){
    auto it=lower_bound(ALL(x),x[i]+d[i]);
    int ind=it-x.begin();
    right.update(i,right.out(i,ind));
  }
  vector<int> sum(n+5,1);
  sum[n]=1;
  vector<int> dp(n+1,0);
  dp[n]=1;
  for(int i=n-1;i>=0;--i){
    int buf=1;
    dp[i]=(sum[right.out(i,i+1)+1])*(buf);
    dp[i]%=MOD;
    sum[i]=sum[i+1]+dp[i];
    sum[i]%=MOD;
  }
  cout<<sum[0]<<"\n";
  rep(i,n+1){
    //printf("dp[%lld]=%lld ",i,dp[i]);
  }
  //cout<<"\n";
  return 0;
}

Measured memory_bytes: 17280
n = int(input())
s = input()
ans = ""
def next_animal(pre,now,letter):
    if pre == "S" and now == "S" and letter == "o":
        return "S"
    if pre == "S" and now == "S" and letter == "x":
        return "W"
    if pre == "S" and now == "W" and letter == "o":
        return "W"
    if pre == "S" and now == "W" and letter == "x":
        return "S"
    if pre == "W" and now == "S" and letter == "o":
        return "W"
    if pre == "W" and now == "S" and letter == "x":
        return "S"
    if pre == "W" and now == "W" and letter == "o":
        return "S"
    if pre == "W" and now == "W" and letter == "x":
        return "W"

for case in range(4):
    if case == 0:
        ans = "SS"
    if case == 1:
        ans = "SW"
    if case == 2:
        ans = "WS"
    if case == 3:
        ans = "WW"
    for i in range(1,n-1):
        next = next_animal(ans[-1],ans[-2],s[i])
        ans += next
    if ans[-1] == next_animal(ans[1],ans[0],s[0]) and ans[0] == next_animal(ans[-2],ans[-1],s[-1]):
        print(ans)
        exit()

print(-1)

Measured memory_bytes: 3444
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < (int)n;i++)
#define repb(i, n) for(int i = (int)n;i >= 0;i--)
#define reps(i, m, n) for(int i = (int)m;i < (int)n;i++)
#define repsb(i, m, n) for(int i = (int)m;i >= (int)n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define INF 999999999999999999
using namespace std;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
using namespace std;
int main(int argc, char const *argv[]) {
    int n;
    cin>>n;
    rep(i,11){
      if(i*111>=n){
        cout<<i*111<<endl;
        return 0;
      }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100000
int main(){
	int n1,n2,cnt=0,i=0,j=0;
	int s[MAX],key;
	int right,left,mid;
	
	
	scanf("%d",&n1);
	
	for(i=0;i<n1;i++){
		scanf("%d",&s[i]);
	}
	
	scanf("%d", &n2);
	

	for(j=0;j<n2;j++){
		scanf("%d",&key);
		left = 1;
		right = n1;
		while(left < right){
			mid = (left+right)/2;
			//printf("left:%d\nmiddle:%d\nright:%d\n\ncnt:%d\n",left,mid,right,cnt);
			if( s[mid] > key ) right = mid;
			
			else if( s[mid] < key ) left = mid + 1;
			
			else if(s[mid]==key){
				cnt++;
				break;
			}
		}
	}
	printf("%d\n",cnt);
	return 0;
}
		


Measured memory_bytes: 2104