akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	ll n;cin >> n;
	vector<ll> v(n);
	REP(i, n)cin >> v[i];
	REP(i, n){
		ll pre = 0;
		if(i){
			pre = v[i-1];
		}
		if(pre < v[i]){
			v[i]--;
		}
		else if(pre == v[i]){

		}
		else {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, h[MAXN], f[MAXN];

int main()
{
	scanf("%d", &n);
	for(rint i=1; i<=n; ++i) scanf("%d", &h[i]);
	for(rint i=2; i<=n; ++i)
	{
		f[i]=f[i-1]+abs(h[i]-h[i-1]);
		if(i>2) f[i]=min(f[i], f[i-2]+abs(h[i]-h[i-2]));
	}
	printf("%d\n", f[n]);
	return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#define MAXN 100010
#define LL long long
using namespace std;
LL d[MAXN],dis[MAXN],siz[MAXN];
int n,cnt; 
map<LL,int> mp;
struct Edge{int u,v;}E[MAXN];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&d[i]);
	for(int i=1;i<=n;i++) mp[d[i]]=i;
	sort(d+1,d+n+1);
	for(int i=1;i<=n;i++) siz[i]=1;
	//d0=di+m-(n-m)=di+2m-n;
	for(int i=n;i>1;i--){ 
		int u=mp[d[i]];
	//	cout<<u<<' '<<d[i]<<endl;
		LL d0=d[i]+2*siz[u]-n;
		int v=mp[d0];
	//	cout<<"-----"<<v<<' '<<d0<<endl; 
		if(v){
			siz[v]+=siz[u];
			dis[v]+=(dis[u]+siz[u]);
			E[++cnt].u=min(u,v);
			E[cnt].v=max(u,v);
		}
		else{
			puts("-1");
			return 0;
		}
	}
	if(dis[mp[d[1]]]!=d[1]){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=cnt;i++) printf("%d %d\n",E[i].u,E[i].v);
	return 0;
}

Measured memory_bytes: 10752
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll m1=b*d,m2=a*c,m3=b*c,m4=a*d;
	cout<<max(max(m1,m2),max(m3,m4));
	return 0;
}

Measured memory_bytes: 3648
from string import ascii_lowercase as lower
lower = list(lower)
n = int(input())
digit = 0
num = 0
while num < n:
    digit += 1
    num += 26**digit

num -= 26**digit
ans = [None]*digit
length = digit
while digit > 0 and num != n:
    for idx in range(26):
        new = num + 26**(digit-1)
        if new >= n:
            break

        else:
            num = new
    ans[length-digit] = lower[idx]
    digit -= 1

ans = [a if a is not None else 'a' for a in ans]
print(''.join(ans))

Measured memory_bytes: 9924
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <typeinfo>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    ll x, now = 100, count = 0;

    cin >> x;
    while (now < x)
    {
        count++;
        now *= 1.01;
    }

    cout << count << endl;
}

Measured memory_bytes: 3632
H, W = list(map(int, input().split()))
ans = float("inf")
if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    for i in range(1, W):
        a = H * i
        b = (W - i) * (H // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)
        # 縦割り
        a = H * i
        b = H * ((W - i) // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)
    for i in range(1, H):
        a = W * i
        b = (H - i) * (W // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)
        # 縦割り
        a = W * i
        b = W * ((H - i) // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)

print(ans)


Measured memory_bytes: 45416
#include<iostream>
#include<algorithm>

#define INFTY 1000000001

using namespace std;

int n, s[200010];
long long cnt;

long long merge(int *A, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  int i, j;
  cnt = 0;

  //generate L[0...n1], R[0...n2]
  int L[n1 + 10], R[n2 + 10];
  for(i = 0;i < n1;i++) L[i] = A[left + i];
  for(i = 0;i < n2;i++) R[i] = A[mid + i];

  L[n1] = INFTY;
  R[n2] = INFTY;

  i = 0;
  j = 0;

  for(int k = left;k < right;k++){
    if(L[i] <= R[j]){
      A[k] = L[i];
      i++;
    }else{
      cnt += n1 - i;
      A[k] = R[j];
      j++;
    }
  }

  return cnt;
}

long long mergeSort(int *A, int left, int right){
  long long a, b, c;

  if(left + 1 < right){
    int mid = (left + right) / 2;
    a = mergeSort(A, left, mid);
    b = mergeSort(A, mid, right);
    c = merge(A, left, mid, right);
    return a + b + c;
  }

  return 0;
}

int main(){

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

  /*mergeSort(s, 0, n);

  for(int i = 0;i < n;i++){
    cout << (i?" ":"");
    cout << s[i];
  }
  cout << endl;*/

  cout << mergeSort(s, 0, n) << endl;

  return 0;
}



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

long long cnt = 0, n;
vector<string> s;
map<pair<string, string>, long long> sets[2];
string ins, r, b;

void make(int now, int lr);
void check();
//第二引数まで"から"分ける
vector<string> split(string splitstring, int stringnum) {
  int i;
  vector<string> stringanswer;
  string answerstring1 = "";
  string answerstring2 = "";
  for(i = stringnum - 1; i < splitstring.size(); ++i)
    answerstring2 += splitstring[i];
  splitstring.erase(splitstring.begin() + stringnum - 1, splitstring.end());
  answerstring1 = splitstring;
  stringanswer.push_back(answerstring1);
  stringanswer.push_back(answerstring2);
  return stringanswer;
}

int main() {
  int i, j;
  cin >> n >> ins;
  s = split(ins, n + 1);
  reverse(s[1].begin(), s[1].end());
  make(0, 0);
  make(0, 1);
  check();

  cout << cnt << endl;
  return 0;
}

void make(int now, int lr) {
  if(now == n) {
    ++sets[lr][make_pair(r, b)];
    return;
  }
  r += s[lr][now];
  make(now + 1, lr);
  r.pop_back();

  b += s[lr][now];
  make(now + 1, lr);
  b.pop_back();
}

void check() {
  for(auto it = sets[0].begin(); it != sets[0].end(); ++it) {
    if(sets[1].find(it->first) != sets[1].end())
      cnt += it->second * sets[1][it->first];
  }
}

Measured memory_bytes: 86272
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
static const int N = 1000;

int lcs(string x, string y) {
	int c[N + 1][N + 1];
	int m = x.size();
	int n = y.size();
	int maxl = 0;
	x = ' ' + x;
	y = ' ' + y;
	for (int i = 0; i < m; i++) c[i][0] = 0;
	for (int j = 0; j < n; j++) c[0][j] = 0;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (x[i] == y[j]) {
				c[i][j] = c[i - 1][j - 1] + 1;
			}
			else {
				c[i][j]=max(c[i][j - 1], c[i - 1][j]);
			}
		}
	}
	maxl = c[m][n];
	return maxl;
}

int main() {
	int q;
	cin >> q;
	string x, y;
	for (int i = 0; i < q; i++) {
		cin >> x >> y;
		cout << lcs(x, y) << endl;
	}
}

Measured memory_bytes: 7012
#include<bits/stdc++.h>
#include<stdio.h>
    
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define _USE_MATH_DEFINES
#define f first
//#define s second
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF 1000000000000000000
#define MAXN (int)(1e7)+1
#define MOD 1000000007
    
using namespace std;
    
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pwi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vector<pair<ll,ll > > > wGraph;
typedef vector<vector<ll> > graph;
//typedef vector<vector<ll> > matrix;
    
    
    
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout<<std::fixed;
    cout<<std::setprecision(2);
    
    ll N;
    cin>>N;
    
    ll somatorio_stool = 0;
    ll altura_anterior = -1;
    while(N-->0){
        ll altura_atual;
        cin>>altura_atual;
    
        if(altura_anterior > altura_atual){
            somatorio_stool += altura_anterior - altura_atual;
        }else{
            altura_anterior = altura_atual;
        }
    }
    
    cout<<somatorio_stool<<endl;
    
    return 0;   
}

Measured memory_bytes: 3656
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String reg = ".";
		Pattern p = Pattern.compile(reg);
		Matcher m = p.matcher(s);
		String result = m.replaceAll("x");		
		System.out.println(result);

	}

}

Measured memory_bytes: 21716
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N; cin >> N;
    vector<int> As(N), sorted(N);
    for (int i = 0; i < N; ++i)
    {
        int Ai;
        cin >> Ai;
        As[i] = sorted[i] = Ai;
    }
    sort(sorted.rbegin(), sorted.rend());
    int second = sorted[1];
    int max = *max_element(As.begin(), As.end());
    for (const int Ai : As)
    {
        if (Ai == max) cout << second << endl;
        else cout << max << endl;
    }
}

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

int main() {
    lint x;
    cin >> x;
    lint now = 100;
    lint ans = 0;
    while (1) {
        ans += 1;
        now += now / 100;
        if (now >= x) {
            cout << ans << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3624
a=[]
a1 = list(map(int, input().split()))
a.append(a1)
a1 = list(map(int, input().split()))
a.append(a1)
a1 = list(map(int, input().split()))
a.append(a1)
N=int(input())
b = []
for _ in range(N):
    b.append(int(input()))

d=[[0,0,0],[0,0,0],[0,0,0]]
for k in range(N):
    for i in range(3):
        for j in range(3):
            if a[i][j]==b[k]:
                d[i][j]=1
c=[0]*8
for i in range(3):

    c[0]+=d[i][0]
    c[1] +=d[i][1]
    c[2] +=d[i][2]
    c[3] +=d[0][i]
    c[4] +=d[1][i]
    c[5] +=d[2][i]
    c[6] +=d[i][i]
    c[7] +=d[2-i][i]

if max(c)==3:
    print("Yes")
else:
    print("No")




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

unsigned long int GCD(unsigned long int m, unsigned long int n){
    unsigned long int r;
    while((r=m%n) != 0l){
        m = n;
        n = r;
    }
    return n;
}

int main(int argc, char *argv[]){
    int N;
    std::cin >> N;
    std::vector<unsigned long int>A(N);
    for(auto &a : A){
        std::cin >> a;
    }

    std::vector<unsigned long int> gcdForward(N);
    gcdForward[0] = A[0];
    for(int i=1; i<N; ++i){
        gcdForward[i] = GCD(gcdForward[i-1],A[i]);
    }

    std::vector<unsigned long int> gcdBackward(N);
    gcdBackward[N-1] = A[N-1];
    for(int i=N-2; i>=0; --i){
        gcdBackward[i] = GCD(gcdBackward[i+1],A[i]);
    }

    std::vector<unsigned long int> gcdExcept(N);
    gcdExcept[0] = gcdBackward[1];
    gcdExcept[N-1] = gcdForward[N-2];
    for(int i=1; i<N-1; ++i){
        gcdExcept[i] = GCD(gcdForward[i-1],gcdBackward[i+1]);
    }

    std::cout << *std::max_element(gcdExcept.begin(),gcdExcept.end()) << std::endl;

    return 0;
}


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

using namespace std;

int main() {
	string s;
	cin >> s;
	
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A') {
			cout << 'T';
		} else if (s[i] == 'T') {
			cout << 'A';
		} else if (s[i] == 'G') {
			cout << 'C';
		} else {
			cout << 'G';
		}
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>


#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

using namespace std;


map<ll,ll> memoization;

ll answer(ll n, ll a, ll b, ll c, ll d) {
    if (set_map_includes(memoization, n)) { return memoization[n]; }
    map<ll,ll> cost{{2,a}, {3,b}, {5,c}};

    ll ret;
    if (n >= 9223372036854775807/d) {
        ret = 9223372036854775807;
    } else {
        ret = n*d;
    }
    for (ll div : vector<ll>{2,3,5}) {
        ll cand_one = n/div;
        ll cand_two = cand_one+1;
        if (cand_two == n) { cand_two = cand_one; }
        ll val1 = answer(cand_one, a, b, c, d) + d*abs(n-cand_one*div)+(cand_one > 0 ? cost[div] : 0);
        ll val2 = answer(cand_two, a, b, c, d) + d*abs(n-cand_two*div)+(cand_two > 0 ? cost[div] : 0);
        ret = min(ret, min(val1, val2));
    }
    memoization[n] = ret;
    return ret;
}


int main()   {
    cout.precision(17);
    ll modd = 1000 * 1000 * 1000 + 7;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no
    ll infinit = 10000000000000000;

    readint(test_cases);
    forr(t, 1, test_cases) {
        readll(n); readll(a); readll(b); readll(c); readll(d);

        memoization.clear();
        memoization[0] = 0;
        memoization[1] = d;
        cout << answer(n, a, b, c, d) <<  endl;
    }
    return 0;
}


Measured memory_bytes: 4752
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>
#include <sstream>
#include <regex>

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

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

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

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
ll gcd(ll a, ll b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n; cin >> n;
	string s; cin >> s;
	int r, b;
	r = b = 0;
	for (char c : s)
	{
		if (c == 'R')++r;
		else ++b;
	}
	if (r > b)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 3540
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N, K = map(int, input().split())
    rest = N - K
    if K == 1:
        print(0)
    else:
        print(rest)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
n = int(input())
a = list(map(int,input().split()))

asum = [0]*(n+1)
for i in range(n):
    asum[i+1] = asum[i] + a[i]

dp = [[1e100]*(n+1) for _ in range(n+1)]

for i in range(n):
    dp[i][i+1] = 0

for j in range(2,n+1):
    for i in range(n+1-j):
        temp = 1e100
        for k in range(1,j):
            temp = min(temp, dp[i][i+k] + dp[i+k][i+j] + asum[i+j] - asum[i])
        dp[i][i+j] = temp
print(dp[0][n])


Measured memory_bytes: 46888
#include<stdio.h>
int main(){
    int a,b,d,r;
    double f;
    scanf("%d %d",&a,&b);
    d=a/b;
    r=a%b;
    f=(double)a/b;
    printf("%d %d %f\n",d,r,f);
    return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500005;
const int mod=998244353;
int n,m;
ll fac[maxn],inv_fac[maxn];
inline ll fpow(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ret=ret*a%mod;
	return ret;
}
inline ll C(int n,int m)
{
	if(n<m) return 0;
	return fac[n]*inv_fac[m]%mod*inv_fac[n-m]%mod;
}
int main()
{
	fac[0]=fac[1]=inv_fac[0]=inv_fac[1]=1;
	for(int i=2;i<maxn;i++) fac[i]=fac[i-1]*i%mod;
	for(int i=2;i<maxn;i++) inv_fac[i]=(mod-mod/i)*inv_fac[mod%i]%mod;
	for(int i=2;i<maxn;i++) inv_fac[i]=inv_fac[i]*inv_fac[i-1]%mod;
	scanf("%d%d",&n,&m);
	ll ans=0;
	for(int i=0;i<=min(n,m);i++)
		(ans+=((i&1)?mod-1:1)*C(n,i)%mod*C(m,i)%mod*fac[i]%mod
		*fpow(n+1,m-i)%mod*fpow(m+1,n-i))%=mod;
	printf("%lld\n",ans);
	return 0;
}

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

int main(int argc, char const *argv[])
{
	string s; cin >> s;
	rep(i, (int)s.size()) {
		s[i] = 'x';
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
lst = []
for i in range(N):
	a, b = map(int, input().split())
	lst.append([a, b])
	
lst = sorted(lst, key = lambda x : x[0])
money = 0
bottle = 0
flg = 0
for elm in lst:
	if flg == 1:
		break
	if bottle + elm[1] < M:
		money += elm[0] * elm[1]
		bottle += elm[1]
	else:
		for i in range(elm[1]):
			money += elm[0]
			bottle += 1
			if bottle >= M:
				flg = 1
				break
print(money)

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

int main() {
  int H, W;
  cin >> H >> W;

  string frame_row = "##";
  for (int i = 0; i < W; i++) {
    frame_row += "#";
  }

  cout << frame_row << endl;

  for (int i = 0; i < H; i++) {
    string row;
    cin >> row;
    cout << "#" + row + "#" << endl;
  }

  cout << frame_row << endl;
}

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

using namespace std;

const long long MOD = 1000000007;

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

int arr[100002];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);

    int n, cnt = 0;
    cin >> n;

    for(int i = 1; i <= n; ++i){
        cin >> arr[i];
        if(i < arr[i]) continue;
        if(arr[arr[i]] == i)
            ++cnt;
    }

    cout << cnt;

    return 0;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
int n, W, w[110];
long long v[110], dp[110][100010];
int main()
{
	cin >> n >> W;
	for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	long long ans = 0LL;
	for(int i = 1; i <= n; i++) for(int j = 1;j <= W; j++)
	{
		dp[i][j] = dp[i - 1][j];
		if(j - w[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
		ans = max(ans, dp[i][j]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 79360
#include "bits/stdc++.h"
#define fcout(d) cout << fixed << setprecision(d)
#define repU(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define repD(i,t,s) for(int i = (int)(t); i >= (int)(s); --i)
#define rep(i,n) repU(i,0,n - 1)
#define rep1(i,n) repU(i,1,n)
#define all(v) begin(v),end(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
#define q_ceil(n,d) ((n) > 0 ? ((n) - 1) / (d) + 1 : (n) / (d))
#define parity(a,b) (a & 1 == b & 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;

const pii dir[] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const int inf32 = (1 << 30) - 1;
const ll inf64 = (1LL << 62) - 1;
const int mod = 1e9 + 7;

int N,A,B,h[100100];

bool judge(ll n){
	ll s = 0;
	rep(i,N){
		s += max(0ll,q_ceil(h[i] - n * B,A - B));
		if(s > n) return 0;
	}
	return 1;
}

int solve(){
	ll upper = inf32;
	ll lower = 0;
	while(upper - lower > 1){
		ll mid = (upper + lower) / 2;
		if(judge(mid)) upper = mid;
		else lower = mid;
	}
	return upper;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
		
	cin >> N >> A >> B;
	rep(i,N) cin >> h[i];
	cout << solve() << endl;
}



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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define INF 1e15
ll N, A[4],B[4];
vector<ll> dp;
ll i, j, k,ans;

int main(){
    scanf("%lld", &N);
    fornum(i,0,3){
        scanf("%lld", &A[i]);
    }
    A[3] = 1;
    fornum(i,0,3){
        scanf("%lld", &B[i]);
    }
    B[3] = 1;
    ans = 0;
    dp.resize(N+1);
    dp[0] = 0;
    fornum(i,0,N){
        fornum(j,0,4){
            if(i+A[j]>N)
                continue;
            ll a = dp[i] + B[j];
            if(dp[i+A[j]]<a){
                dp[i + A[j]] = a;
            }
        }
    }
    ans = dp[N];
    dp.clear();
    dp.resize(ans+1);
    fornum(i,0,ans+1){
        //prinf("%lldd\n", i);
        fornum(j,0,4){
            if(i+B[j]>ans)
                continue;
            ll a = dp[i] + A[j];
            if(dp[i+B[j]]<a){
                dp[i + B[j]] = a;
            }
        }
    }
    ans = dp[ans];

    printf("%lld", ans);
    return 0;
}

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

using namespace std;

int main(){
  int n;
  bool flag=true;
  cin >> n;
  vector<char> s(n);
  for(int i=0;i<n;i++){
    cin >> s.at(i);
  }
  if(n%2==1){
    cout << "No" << endl;
    return 0;
  }
  for(int i=0;i<n/2;i++){
    if(s.at(i) != s.at(i+(n/2))){
      flag=false;
      break;
    }
  }

  if(flag){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int A, B, C, D;

i64 dp[3030][3030];

int main()
{
	scanf("%d%d%d%d", &A, &B, &C, &D);

	for (int i = A; i <= C; ++i) {
		for (int j = B; j <= D; ++j) {
			if (i == A && j == B) {
				dp[i][j] = 1;
				continue;
			}
			i64 tmp = 0;
			if (i == A) tmp = dp[i][j - 1] * A % MOD;
			else if (j == B) tmp = dp[i - 1][j] * B % MOD;
			else {
				ADD(tmp, dp[i - 1][j] * j % MOD);
				ADD(tmp, dp[i][j - 1] * i % MOD);
				ADD(tmp, MOD - (dp[i - 1][j - 1] * ((i - 1) * (j - 1)) % MOD));
			}
			dp[i][j] = tmp;
		}
	}
	printf("%lld\n", dp[C][D]);
	return 0;
}


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

int main(void){
    char a,b;
    cin>>a>>b;
    char ans;
    if (a == 'H') {
        if (b == 'H') ans = 'H';
        else ans = 'D';
    }
    else {
        if (b == 'H') ans = 'D';
        else ans = 'H';
    }
    cout<< ans <<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.*;

public class Main {
    private static final int MAX = 100005;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int m = in.nextInt();
        Job[] jobs = new Job[MAX];
        for (int i = 0; i < n; ++i) {
            int a = in.nextInt();
            int b = in.nextInt();
            if (jobs[a] == null) jobs[a] = new Job();
            jobs[a].pay.add(b);
        }
        long ans = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = m - 1; i >= 0; --i) {
            if (jobs[m - i] != null) {
                for (int pay : jobs[m - i].pay) {
                    queue.offer(pay);
                }
            }
            if (!queue.isEmpty()) {
                ans += queue.poll();
            }
        }
        out.println(ans);
        out.close();
    }

    private static class Job {
        List<Integer> pay;

        Job() {
            pay = new ArrayList<>();
        }
    }
}


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

int main() {
  int n;
  cin >> n;
  int a = n / 10;
  int b = n % 1000;
  
  if (a % 111 == 0 || b % 111 == 0) {
    cout << "Yes" << endl;
  }
  else 
    cout << "No" << endl; 
}

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

#define name ""
#define ini freopen(name".inp","r",stdin); freopen(name".out","w",stdout)
#define long long long
#define db double
#define pii pair <int, int>
#define pll pair <long, long>
#define all(c) c.begin(), c.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
template <class T> inline void chmin(T &a, const T& val) { if (a > val) a = val; }
template <class T> inline void chmax(T &a, const T& val) { if (a < val) a = val; }
template <class T> long sqr(T a) { return 1ll * a * a; }
template <class T> void compress(T &a){
  sort(all(a)); a.resize(unique(all(a)) - a.begin());  
}

const db pi = acos(-1.00);
const db eps = 1e-6;
const int INF = 1e9;
const int MOD = 1e9+7;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

const int N = 2e5+1;
int n, m;
long k, cur, a[N], b[N];

int main()
{
  fastio;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= m; i++){
    cin >> b[i]; cur += b[i];
  }
  int res = 0;
  int ptr = m;
  for (int i = 0; i <= n; i++){
    cur += a[i];
    while (ptr > 0 && cur > k){
      cur -= b[ptr]; ptr--;
    }
    if (cur > k) break; 
    chmax(res, i + ptr);
  }  
  cout << res;
  return 0;
}

Measured memory_bytes: 6776
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P; //ペア　タイプでふ

int main()
{
    int a, b, c;
    char d, e;
    cin >> a >> d >> b >> e >> c;
    if (b <= 4)
    {
        cout << "Heisei";
    }
    else
    {
        cout << "TBD";
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        int N = int.Parse(ReadLine());
        var v = ReadLine().Split().Select(double.Parse).ToArray();
        Array.Sort(v);
        var ave = v[0];
        for (int i = 0; i < N-1; i++)
        {
            ave = (ave + v[i + 1]) / 2;
        }
        WriteLine(ave);
    }
}


Measured memory_bytes: 28284
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
    enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
// #ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
       *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
// #else
// sim dor(const c&) { ris; }
// #endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const long long MOD=1e9+7;

void solve(){
    int n;
    cin>>n;
    int a[n];
    long long cur=0ll,ans=0ll;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ans+=a[i]*cur;
        ans%=MOD;
        cur+=a[i];
        cur%=MOD;
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 4432
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; using ll = long long; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

ll mpow(ll x, ll n) { ll y = 1; for (; n; n /= 2) { y = n % 2 ? y * x % MOD : y; x = x * x % MOD; } return y; }

struct UnionFindTree {
    vector<int> par, sz;
    int operator [](int x) { return find(x); }
    void build(int n) { par.assign(n, -1); sz.assign(n, 1); }
    int find(int x) { return par[x] < 0 ? x : (par[x] = find(par[x])); }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
    bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return 0;
        par[x] = min(par[x], par[y] - 1); par[y] = x; sz[x] += sz[y]; return 1;
    }
    bool uniteByRank(int x, int y) { return par[find(x)] > par[find(y)] ? unite(y, x) : unite(x, y); }
};

struct Combination {
    vector<ll> fact, ifact;
    Combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1; for (int i = 0; i < n; ++i) fact[i + 1] = fact[i] * (i + 1) % MOD;
        ifact[n] = mpow(fact[n], MOD - 2); for (int i = n; i > 0; --i) ifact[i - 1] = ifact[i] * i % MOD;
    }
    ll operator ()(int n, int k) const { return k < 0 || k > n ? 0 : fact[n] * ifact[n - k] % MOD * ifact[k] % MOD; }
} C(5e3);

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    rep(i, N) {
        cin >> P[i];
        if (P[i] != -1) P[i]--;
    }

    int A = 0;
    vector<int> B;
    ll confirmed = 0;
    {
        UnionFindTree uf;
        uf.build(N);
        rep(i, N) {
            if (P[i] != -1) uf.uniteByRank(i, P[i]);
        }

        vector<int> g(N, -1);
        rep(i, N) {
            if (P[i] == -1) g[uf[i]] = 1;
            else if (g[uf[i]] != 1) g[uf[i]] = 0;
        }

        rep(i, N) {
            if (g[i] != -1) confirmed += uf.size(i) - 1;
            if (g[i] == 0) A += uf.size(i);
            if (g[i] == 1) B.push_back(uf.size(i));
        }
    }

    int K = B.size();
    vv<ll> dp = vvec(K + 1, K + 1, 0LL);
    dp[0][0] = 1;
    rep(i, K) {
        rep(j, K) {
            dp[i + 1][j + 1] += dp[i][j] * (j + 1) % MOD * B[i] % MOD;
            dp[i + 1][j + 1] %= MOD;
            dp[i + 1][j] += dp[i][j] * (N - 1);
            dp[i + 1][j] %= MOD;
        }
    }

    ll ans = (confirmed + K) * mpow(N - 1, K) % MOD;

    rep(i, K) {
        ll t = (B[i] - 1) * mpow(N - 1, K - 1) % MOD;
        ans = (ans + MOD - t) % MOD;
    }

    rep(n, 2, K + 1) {
        ll t = dp[K][n] * mpow(n, MOD - 2) % MOD;
        ans = (ans + MOD - t) % MOD;
    }

    write(ans);
}


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

int main(){
  int m, k;
  cin >> m >> k;
  if(m == 1) {
    if(k >= 1) cout << -1 << endl;
    else if(k == 0) cout << 1 << " " << 1 << " " << 0 << " " << 0 << endl;  
    return 0;
  }
  if(k >= (1<<m)) {
    cout << -1 << endl;
    return 0;
  }
  rep(i,1<<m) {
    if(i != k) cout << i << " ";
  }
  cout << k << " ";
  for(int i = (1<<m)-1; i >= 0; i--) {
    if(i != k) cout << i << " ";
  }
  cout << k << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e9;
template<typename T> void cmax(T &a, T b) {a = max(a, b);}
template<typename T> void cmin(T &a, T b) {a = min(a, b);}


signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  rep(i,n)cin>>a[i];
  int even=0;
  rep(i,n){
    if(a[i]%2==0){
      int tmp=0;
      while(1){
        if(a[i]%2==0)tmp++;
        else break;
        a[i]/=2;
      }
      even+=tmp;
    }
  }
  cout<<even<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 102;

int f[2][N][N][N];
int n,m;
int a[N][N],lef[N][N],up[N][N];
int sx,sy;

int calc_h(int x,int l,int r){
	int L=max(r+1,sy-l),R=min(m-l,sy+r);
	return L>R?0:(lef[x][R]-lef[x][L-1]);
}

int calc_w(int y,int u,int d){
	int U=max(d+1,sx-u),D=min(n-u,sx+d);
	return U>D?0:(up[D][y]-up[U-1][y]);
}

int main(){
	n=get();m=get();
	fo(i,1,n){
		char s[N];
		scanf("%s",s+1);
		fo(j,1,m){
			if (s[j]=='o')a[i][j]=1;
			if (s[j]=='E')sx=i,sy=j;
		}
	}
	fo(i,1,n)
		fo(j,1,m){
			lef[i][j]=lef[i][j-1]+a[i][j];
			up[i][j]=up[i-1][j]+a[i][j];
		}
	int ans=0,now=0;
	f[0][0][0][0]=0;
	fo(step,1,n+m){
		int t=now^1;
		fo(u,0,sx-1)
			fo(l,0,sy-1)
				fo(r,0,m-sy){
					ans=max(ans,f[now][u][l][r]);
					f[t][u][l][r]=0;
				}
		fo(u,0,sx-1)
			fo(l,0,sy-1)
				fo(r,0,m-sy){
					int d=step-1-u-l-r;
					if (d<0||d>n-sx)continue;
					if (sx-u-1>d)f[t][u+1][l][r]=max(f[t][u+1][l][r],f[now][u][l][r]+calc_h(sx-u-1,l,r));
					if (sx+d+1<=n-u)f[t][u][l][r]=max(f[t][u][l][r],f[now][u][l][r]+calc_h(sx+d+1,l,r));
					if (sy-l-1>r)f[t][u][l+1][r]=max(f[t][u][l+1][r],f[now][u][l][r]+calc_w(sy-l-1,u,d));
					if (sy+r+1<=m-l)f[t][u][l][r+1]=max(f[t][u][l][r+1],f[now][u][l][r]+calc_w(sy+r+1,u,d));
				}
		now=t;
	}
	fo(u,0,sx-1)
		fo(l,0,sy-1)
			fo(r,0,m-sy)
				ans=max(ans,f[now][u][l][r]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
const int N = 2e4+100;
const int M =1e9+7;
#define int long long int
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define MAX 1e15+1
#define pi  pair<int,int>  
const int mod = 1e9 + 7;

int a[200];
int vist[N];
signed main() { 
    fast;
    int n,m;
    cin>>m>>n;
    if(n>m)swap(n,m);
    for(int i=0;i<m;i++)cout<<n;
   
   
}   

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

using namespace std;

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

    vector<int> nums(K, 0);
    for(int i = 0; i < N; i++){
        nums[i%K] ++;
    }

    int max = 0;
    int min = 99999999;
    for(int i = 0; i < K; i++){
        if(max < nums[i]) max = nums[i];
        if(min > nums[i]) min = nums[i];
    }

    cout << abs(max-min) << endl;
}

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

#define endl "\n"
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first 
#define ss second 
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vii vector<pii>
#define vvi vector<vi>
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N=100*1000;
const int mod=1e9+7;

int min3(int a,int b,int c){return min(a,min(b,c));}
int max3(int a,int b,int c){return max(a,max(b,c));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

//#define int int64_t
//int a[N+2];
#define ld long double
int32_t  main(){
	IOS;
  int n,k;
  scanf("%d %d",&n,&k);
  //cin>>n>>k;
  ld ans=0.0;
  for(int i=1;i<=n;++i){
    //for this i how many jumps to cross k 
    int cnt=0;
    int num=i;
    while(num<k){
      num*=2;
      cnt++;
    }
//    cout<<i<<" "<<cnt<<" i,cnt\n";
    ld val=(1.0/n)*pow(0.5,cnt);
    ans+=val;
  }
  printf("%0.10Lf\n",ans);
  //cout<<ans<<endl;

  return 0;
}



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

using ld=double;
using P=complex<ld>;
using Point=P;
const ld EPS=1e-9;
struct Line{
    P a,b;
};
ld cross(P x,P y){
    return real(x)*imag(y)-real(y)*imag(x);
}
Line halfLine(P x,P y){
    return Line{(x+y)/P(2,0),(x-y)*P(0,1)+(x+y)/P(2,0)};
}

bool isis_sp(Line x,P p){
    return abs(x.a-p)+abs(x.b-p)-abs(x.a-x.b)<EPS;
}
Point is_ll(Line s,Line t){
    P sv = s.b - s.a, tv = t.b - t.a;
    return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
bool isis_ll(Line x,Line y){
    return abs(cross(x.a-x.b,y.a-y.b))>EPS;
}
// P is_ll(Line x,Line y){
//     return x.a+(x.b-x.a)*cross(x.a-y.a,y.b-y.a)/cross(x.b-x.a,y.b-y.a);
// }
bool is_in_Polygon(P p,const vector<P> &poly){
    ld angle=0;
    int n=poly.size();
    for(int i=0;i<n;i++){
        P a=poly[i],b=poly[(i+1)%n];
        if(isis_sp(Line{a,b},p)) return true;
        angle+=arg((b-p)/(a-p));
    }
    if(abs(angle)<EPS) return false;
    return true;
}

ld area_of_Polygon(vector<P> p){
    ld res=0;
    for(int i=0;i<p.size();i++){
        ld xlen=real(p[(i+1)%p.size()]-real(p[i]));
        ld ylen=imag(p[(i+1)%p.size()])+imag(p[i]);
        res+=xlen*ylen/2;
    }
    return abs(res);
}
int solve(){
    int n,m;
    cin>>n>>m;
    if(n==0 && m==0) return false;
    vector<P> land(n);
    for(int i=0;i<n;i++){
        ld x,y;
        cin>>x>>y;
        land[i]={x,y};
    }
    vector<P> castle(m);
    for(int i=0;i<m;i++){
        ld x,y;
        cin>>x>>y;
        castle[i]={x,y};
    }

    auto isValid=[&](int idx,P p){
        if(!is_in_Polygon(p,land)) return false;
        vector<ld> dist(m);
        for(int i=0;i<m;i++) dist[i]=abs(castle[i]-p);
        ld mind=*min_element(dist.begin(),dist.end());
        return abs(mind-dist[idx])<EPS;
    };
    auto solve=[&](int idx){
        vector<Line> line;
        for(int i=0;i<m;i++){
            if(i!=idx){
                line.push_back(halfLine(castle[i],castle[idx]));
            }
        }
        for(int i=0;i<n;i++){
            line.push_back(Line{land[i],land[(i+1)%n]});
        }
        vector<P> poly;
        int s=line.size();
        for(int i=0;i<s;i++){
            for(int j=i+1;j<s;j++){
                if(isis_ll(line[i],line[j])){
                    P p=is_ll(line[i],line[j]);
                    if(isValid(idx,p)){
                        poly.push_back(p); 
                    }
                }
            }
        }
        sort(poly.begin(),poly.end(),[&](P x,P y){return arg(x-castle[idx])<arg(y-castle[idx]);});
        return area_of_Polygon(poly);
    };
    cout<<fixed<<setprecision(10);
    for(int i=0;i<m;i++){
        cout<<solve(i)<<endl;
    }
    return true;
}
int main(){
    while(solve());
}


Measured memory_bytes: 3464
#include <stdio.h>

#define N_MAX 100

int n, a, b, c, d[N_MAX];

int compare_int(const int *a, const int *b){
	return *b - *a;
}

int solve(void){
	int i;

	int mole = c;
	int deno = a;
	double ans = 0.0;

	i = 0;
	for(;;){
		double u = (double)mole / (double)deno;
		if (u > ans){
			ans = u;
		}
		if (i == n){
			return printf("%d\n", (int)ans);
		}
		mole += d[i];
		deno += b;
		i++;
	}
}

int main(void){
	int i;
	scanf("%d %d %d %d", &n, &a, &b, &c);
	for(i = n; i--; ){
		scanf("%d", &d[i]);
	}
	qsort(d, n, sizeof(int), compare_int);
	solve();
	return 0;
}

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

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define RFOR(i,a,b) for(long i=(a);i>=(b);--i)

#define REP(i,a) for(long i=0;i<(a);++i)
#define RREP(i,a) for(long i=(a);i>=0;--i)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) std::sort((a).begin(), (a).end())
#define UNIQUE(a) std::sort((a).begin(), a.end()), a.erase(std::unique((a).begin(), a.end()), a.end());
#define SUM(a) std::accumulate((a).begin(), (a).end(), 0);

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<char> VC;
typedef std::vector<int>  VI;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;

typedef std::vector< VC > VC2;
typedef std::vector< VI > VI2;
typedef std::vector< VL > VL2;
typedef std::vector< VLL > VLL2;

typedef std::pair<int,int> PII;

/*
3 1 0 2 nが偶数 => iが奇数がfront
2 0 1   nが奇数 => iが偶数がfront
*/

int n;
std::deque<int> deq;
int main() {
    std::cin >> n;
    const bool f = n % 2 == 0;
    REP(i, n) {
        int a;
        std::cin >> a;

        const bool g = i % 2 == 0;
        if( (f && !g) || (!f && g) ) {
            deq.push_front(a);
        } else {
            deq.push_back(a);
        }
    }

    int i = 0;
    for(auto x: deq) {
        if(i++ != 0) std::cout << " ";
        std::cout << x;
    }
    std::cout << std::endl;
}

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

using namespace std;

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

    vector<int> m(n);
    int remain = x, cnt = n;
    for(int i = 0; i < n; i++) {
        cin >> m[i];
        remain -= m[i];
    }

    sort(m.begin(), m.end());

    for(int i = 0; i < n; i++) {
        cnt += remain / m[i];
        remain %= m[i];
    }

    cout << cnt << endl;

    return 0;
}

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

int gcd(int p,int q)
{
	if(p%q==0)
		return q;
	return gcd(q,p%q);
}
int main()
{
	//code
	int k;
	cin>>k;
	int s=0;
	
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			for(int g=1;g<=k;g++)
				s+=gcd(i,gcd(j,g));
				
	cout<<s<<endl;
 	return 0;
}


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

class Dice{
public:
    int *arr;
    Dice(int arr2[]){arr = arr2;}

    void roll(char direction){
        int temp;
        switch(direction){
            case 'N':
                temp = arr[0]; arr[0] = arr[1]; arr[1] = arr[5]; arr[5] = arr[4]; arr[4] = temp;
                break;
            case 'E':
                temp = arr[0]; arr[0] = arr[3]; arr[3] = arr[5]; arr[5] = arr[2]; arr[2] = temp;
                break;
            case 'W':
                temp = arr[0]; arr[0] = arr[2]; arr[2] = arr[5]; arr[5] = arr[3]; arr[3] = temp;
                break;
            case 'S':
                temp = arr[0]; arr[0] = arr[4]; arr[4] = arr[5]; arr[5] = arr[1]; arr[1] = temp;
        }
    }

    int report(){return arr[0];}
};

int main(){
    int arr[6], l;
    for(int i = 0;i < 6; i++) cin >> arr[i];
    Dice dice(arr);
    string line;
    cin >> line;
    l = line.size();
    for(int i = 0;i < l; i++) dice.roll(line[i]);
    cout << dice.report() << endl;

    return 0;
}



Measured memory_bytes: 3212
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define len(n) (int)n.length()
#define pb push_back
#define ll long long
#define make_pair mkp
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n-1;i >= 0;i--)
#define ALL(v) (v).begin(), (v).end()
#ifdef DBGPRT
#define dbg(n) cerr << "//" << #n << ":" << n <<endl
#else
#define dbg(n) ;
#endif
typedef pair<ll, ll> LLARR;
#define INF 999999999
const double PI = 3.1415926535897932384626433832795;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a;

	REP(i,n){
		int t;
		cin >> t;
		a.pb(t);
	}
	sort(ALL(a));
	a.erase(unique(ALL(a)), a.end());
	cout << (a.size() % 2 == 1 ? a.size() : a.size()-1) << endl;
	return 0;
}

Measured memory_bytes: 892
#include<iostream>
#include<iomanip>
#include<limits>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>

#define big ((long long)(1e9)+7)

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  if(n%2 == 0)
    cout << n/2 << endl;
  else
    cout << n/2+1 << endl;
}


Measured memory_bytes: 256
// Author: Harshdeep Sharma , IIT  Indore
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
// #define MOD  998244353
#define ll long long
const double PI = atan(1.0) * 4;
// const ll INF = (int)1e9 ;
const int di[4] = { -1, 0, 1, 0} ;
const int dj[4] = {0, -1, 0, 1} ;
const ll INF = (ll)2e18 + 50;
const int maximum  = numeric_limits<int>::max();
const int minimum  = numeric_limits<int>::min();

ll power(ll x, ll y, ll p)  {
	ll res = 1;

	x = x % p;
	if (x == 0) return 0;

	while (y > 0)	{
		if (y & 1)
			res = (res * x) % p;
		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

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





int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	// int t ;
	// cin >> t ;
	// while (t--) {
	int n ;
	cin >> n;
	vector<ll> a(n) ;
	for (int i = 0 ; i < n ; i++) {
		cin >> a[i] ;
	}
	sort(a.begin(), a.end()) ;
	int ans = 0 ;
	for (int i = 0 ; i < n ; i++) {
		for (int j = i + 1 ; j < n; j++) {
			for (int k = j + 1 ; k < n ; k++) {
				if (a[i] != a[j] && a[j] != a[k]) {
					vector<ll> v ;
					v.push_back(a[i]) ;
					v.push_back(a[j]) ;
					v.push_back(a[k]) ;
					sort(v.begin(), v.end()) ;
					if (v[0] + v[1] > v[2]) ans++ ;
					v.clear() ;
				}
			}
		}
	}
	cout << ans << "\n";



	// }








	return 0 ;

}



Measured memory_bytes: 3648
fun main(args: Array<String>) {
    val s = readLine()!!.toInt()
    val x = s / 100
    val y = s % 100
    if (y in 1..12 && !(x in 1..12)) println("YYMM")
    else if (y in 1..12 && (x in 1..12)) println("AMBIGUOUS")
    else if (x in 1..12 && !(y in 1..12)) println("MMYY")
    else println("NA")
}


Measured memory_bytes: 31748