akhauriyash/Code-Regression huggingface dataset:
/**
 *    author: gxfireball       
**/
#include <bits/stdc++.h>
#define ll double
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
using namespace std;

double Convert(double degree){ 
    return((degree / 360) * 2 * M_PI); 
} 

void solve(){
   ll a,b,h,m;
   cin >> a >> b >> h >> m;
   ll deg_m = m*6;
   ll deg_h = h*30;
   deg_h += m*0.5;
   ll deg = abs(deg_m - deg_h);
   // c^2 = sqrt(a^2 + b^2 - 2*a*b*cos(deg))
//    deg = 180 - deg;
    if(deg > 180){
        deg = 360 - deg;
    }
   deg = Convert(deg);
//    cout << deg << endl;
   ll ans  = sqrt(a*a + b*b - 2*a*b*cos(deg));
   cout << fixed << setprecision(16);
   cout << ans;
}

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



Measured memory_bytes: 4244
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

int n, m, bas, son, a[N], b[N], c[N];
deque < int > q;
long long ans, ans2;

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		scanf("%d",a + i);
	sort(a + 1, a + n + 1);
	q.push_front(a[1]);
	bas = 2; son = n;
	while(bas <= son){
		if(son >= bas)
			q.push_front(a[son--]);
		if(son >= bas)
			q.push_back(a[son--]);
		if(bas <= son)
			q.push_front(a[bas++]);
		if(bas <= son)
			q.push_back(a[bas++]);
	}
	while(!q.empty()){
		b[++m] = q.front();
		q.pop_front();
	}

	m = 0;
	q.push_front(a[n]);
	bas = 1; son = n - 1;
	while(bas <= son){

		if(bas <= son)
			q.push_front(a[bas++]);
		if(bas <= son)
			q.push_back(a[bas++]);

		if(son >= bas)
			q.push_front(a[son--]);
		if(son >= bas)
			q.push_back(a[son--]);
	}
	while(!q.empty()){
		c[++m] = q.front();
		q.pop_front();
	}

	for(int i = 1; i < n; i++)
		ans += abs(b[i + 1] - b[i]);

	for(int i = 1; i < n; i++)
		ans2 += abs(c[i + 1] - c[i]);
	printf("%lld\n", max(ans, ans2));
	return 0;
}

Measured memory_bytes: 9216
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)
#include <queue>

using namespace std;
#define ll long long

int main(){
  int N;
  cin >> N;
  vector<ll> A(3*N);
  for(int i=0; i<3*N; i++)
    cin >> A[i];

  vector<ll> Memoa(N+1, 0), Memob(N+1, 0);
  priority_queue<ll, vector<ll>, std::greater<ll> > Qa;
  priority_queue<ll, vector<ll>, std::less<ll> > Qb;
  for(int i=0; i<N; i++){
    Qa.push(A[i]);
    Qb.push(A[i+2*N]);
  }
  Memoa[0] = accumulate(A.begin(), A.begin()+N, 0LL);
  for(int i=0; i<N; i++){
    ll tmp = A[i+N];
    Memoa[i+1] = Memoa[i];
    if(tmp > Qa.top()){
      Memoa[i+1] += - Qa.top() + tmp;
      Qa.pop();
      Qa.push(tmp);
    }
  }
  Memob[0] = accumulate(A.begin()+2*N, A.end(), 0LL);
  for(int i=0; i<N; i++){
    ll tmp = A[2*N-1-i];
    Memob[i+1] = Memob[i];
    if(tmp < Qb.top()){
      Memob[i+1] += - Qb.top() + tmp;
      Qb.pop();
      Qb.push(tmp);
    }
  }
  ll max = Memoa[0] - Memob[N];
  for(int i=0; i<N+1; i++){
    if(max < Memoa[i] - Memob[N-i])
      max = Memoa[i] - Memob[N-i];
  }
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 5996
#include <iostream>
#include <string>
#include <vector>
std::string  S,T,U;
int A,B;
 
int main(void){
    std::cin >> S >> T;
    std::cin >> A >> B;
    std::cin >> U;

    if(S == U){
        A = A - 1;
    }

    if(T == U){
        B = B - 1;
    }

    std::cout << A << " " << B;
    return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



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

  ll x;
  cin >> x;
  ll tmp = 100;
  ll cnt = 0;
  while(tmp < x) {
    cnt++;
    tmp += tmp/100;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;

int N;

ll sum(int n) {
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 3 == 0 || i % 5 == 0) continue;
        res = res + i;
    }
    return res;
}

int main() {
#ifdef ACM_LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    scanf("%d", &N);
    printf("%lld\n", sum(N));


    return 0;
}

Measured memory_bytes: 3824
#include<bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define M        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	vector <ll> v(3);
	cin>>v[0]>>v[1]>>v[2];
	sort(all(v));
	ll m=1e9;
	do{
	    m=min(m,abs(v[1]-v[0])+abs(v[2]-v[1]));
	}while(next_permutation(all(v)));
	cout<<m;
	return 0;
}
  

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

#define int long long
#define uint unsigned int
#define pii pair<int, int>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORR(i,a,b) for(int i=(a);i>=(b);--i)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) FORR(i,n,0)
#define EACH(i,c) for (auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

#define PB(a) push_back(a)
#define EMPB(...) emplace_back(__VA_ARGS__)
#define EMP(...) emplace(__VA_ARGS__)
#define MP(a,b) make_pair(a,b)
#define MT(...) make_tuple(__VA_ARGS__)

#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))

#define PW(n) (1LL << (n))

using namespace std;

template <class T> inline bool CHMIN(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool CHMAX(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> inline void SORT(T &a) { sort(a.begin(), a.end()); }
template <class T> inline void REV(T &a) { reverse(a.begin(), a.end()); }
template <class T> inline void UNI(T &a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }

template <class S, class T> ostream& operator << (ostream& os, const pair<S, T> v) {
  os << "(" << v.first << ", " << v.second << ")"; return os;
}

const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;

/* ---------------------------------------------------------------------------------------------------- */

int N, M;
pii p[100010];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> M;
  REP(i, N) cin >> p[i].first >> p[i].second;
  sort(p, p+N);
  int ans = 0;
  int rem = M;
  REP(i, N) {
    int num = min(rem, p[i].second);
    ans += p[i].first * num;
    rem -= num;
    if (rem <= 0) break;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	int i,j,high[10];

	for(i=0;i<10;i++) {
		scanf("%d",&high[i]);
	}
	for(i=0;i<10;i++) {
		for(j=i+1;j<10;j++) {
			if(high[i]<high[j]) {
				int tmp=high[i];
				high[i]=high[j];
				high[j]=tmp;
			}
		}
	}
	for(i=0;i<3;i++) {
		printf("%d\n",high[i]);
	}
	return 0;
}

Measured memory_bytes: 600
import std.stdio, std.conv, std.string, std.array, std.math, std.regex, std.range, std.ascii, std.numeric, std.random;
import std.typecons, std.functional, std.traits,std.concurrency;
import std.algorithm, std.container;
import core.bitop, core.time, core.memory;
import std.bitmanip;
import std.regex;

enum INF = long.max/3;
enum MOD = 10L^^9+7;

//辞書順順列はiota(1,N),nextPermituionを使う


void end(T)(T v)
if(isIntegral!T||isSomeString!T||isSomeChar!T)
{
    import core.stdc.stdlib;
    writeln(v);
    exit(0);
}

T[] scanArray(T = long)()
{
    static char[] scanBuf;
    readln(scanBuf);
    return scanBuf.split.to!(T[]);
}

dchar scanChar()
{
    int c = ' ';
    while (isWhite(c) && c != -1)
    {
        c = getchar;
    }
    return cast(dchar)c;
}

T scanElem(T = long)()
{
    import core.stdc.stdlib;
    static auto scanBuf = appender!(char[])([]);

    scanBuf.clear;

    int c = ' ';
    while (isWhite(c) && c != -1)
    {
        c = getchar;
    }
    while (!isWhite(c) && c != -1)
    {
        scanBuf ~= cast(char) c;
        c = getchar;
    }
    return scanBuf.data.to!T;
}

dchar[] scanString(){
    return scanElem!(dchar[]);
}


void main()
{
  max(scanElem*scanElem,scanElem*scanElem).writeln;
}


Measured memory_bytes: 256
x,y,z=gets.split.map(&:to_i)
A=gets.split.map(&:to_i)
B=gets.split.map(&:to_i)

a=*b=[0]
A.each do |i| a<< a[-1]+i end
B.each do |i| b<< b[-1]+i end

ans=0
0.upto(x) do |n|
  k=z-a[n]
  break if k<0
  m=b.bsearch_index{|i|k<i}
  m=(m)? m-1: y
  ans=[ans,n+m].max
end
p ans


Measured memory_bytes: 45180
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  vector<int> B(N);
  rep(i, N) cin >> B[i];
  vector<int> X(N);
  rep(i, N) X[i] = i+1;
  map<vector<int>, int> mp;  // 配列が辞書順で何番目か
  do {
    mp[X] = sz(mp);
  } while (next_permutation(X.begin(), X.end()));
  int ans = abs(mp[A] - mp[B]);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 8636
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define print(x) cout << x << endl;
using namespace std;
typedef long long ll;

int main()
{
    string s;
    cin >> s;
    int K;
    cin >> K;

    int n = s.size();

    vector<string> vec;
    
    rep(i, 1, min(n, 5) + 1) {
        rep (j, 0, n - i + 1) {
            vec.push_back(s.substr(j, i));
        }
    }

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    cout << vec[K - 1] << endl;
    return 0;
}

Measured memory_bytes: 1660
N=int(input())
S=input()

ans=0

for slide in range(1,N):
    pos=slide
    bpos=0
    while pos<N:
        clen=0
        while pos<N and clen<slide and S[pos]==S[bpos]:
            pos+=1
            bpos+=1
            clen+=1
        
        ans=max(ans,clen)

        if clen==0:
            pos+=1
            bpos+=1

print(ans)


Measured memory_bytes: 73700
from operator import itemgetter

n, m = [int(i) for i in input().split()]

# 区間の終端でソート
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

for a in ab:
    # a が removed より大きい = まだ取り除いてない
    if a[0] > removed:
        #print(a)
        removed = a[1] - 1
        ans += 1

print(ans)

Measured memory_bytes: 29912
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;

int main() {

	string S; cin >> S;

	if (S == "SUN") cout << 7 << endl;
	if (S == "MON") cout << 6 << endl;
	if (S == "TUE") cout << 5 << endl;
	if (S == "WED") cout << 4 << endl;
	if (S == "THU") cout << 3 << endl;
	if (S == "FRI") cout << 2 << endl;
	if (S == "SAT") cout << 1 << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		
		int[] pat = new int[3001];
		
		for(int i = 0; i <= 1000; ++i){
			for(int j = 0; j <= 1000; ++j){
				for(int k = 0; k <= 1000; ++k){
					pat[i+j+k]++;
				}
			}
		}
		// 1,000,000,000
		
		
		while(sc.hasNextInt()){
			int n = sc.nextInt();
			int res = 0;
			
			for(int i = 0; i <= 1000; ++i){
				for(int j = 0; j <= 3000; ++j){
					if( i+j == n ){
						res += pat[j];
					}
				}
			}
			
			System.out.println(res);
		}
	}
}

Measured memory_bytes: 20308
def use_fast_io():
    global input
    import io
    import sys
    f = io.BytesIO(sys.stdin.buffer.read())
    input = f.readline


#use_fast_io()

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def solve():
    n, m, l = map(int, input().split())
    graph = np.full((n, n), 10 ** 10)
    for _ in range(m):
        s, t, w = map(int, input().split())
        if w <= l:
            graph[s - 1][t - 1] = graph[t - 1][s - 1] = w
    graph = floyd_warshall(graph, directed=False)
    graph = floyd_warshall(graph <= l, directed=False)
    graph[np.isinf(graph)] = 0
    Q = int(input())
    ans = []
    for _ in range(Q):
        s, t = map(int, input().split())
        ans.append(int(graph[s - 1][t - 1]) - 1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


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

int main() {
  string s;
  bool a = true;
  cin >> s;
  int ans,x = s.size() / 2;
  if(s.size() % 2 == 0){
    x--;
  }
  for(int i = x; true; i--){
    a = true;
    for(int j = 0; j < i; j++){
      if(s.at(j) != s.at(i + j)){
        a = false;
        break;
      }
    }
    if(a){
      ans = i * 2;
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mxn 1000010
#define LL long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair<int,int> 
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define node(a,b,c) (node){a,b,c}
using namespace std;
const int inf=1e9,mod=1e9+7;
int n,m,sl,fh,top,ans,f[mxn],dp[110][mxn];
int rd()
{
	sl=0;fh=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
void upd(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
int main()
{
	n=rd();m=rd();
	for(int r,l=1;l<=n;l=r+1)
	{
		r=min(n,n/(n/l));
		f[++top]=r-l+1;
	}
	for(int i=1;i<=top;++i) dp[1][i]=f[i];
	for(int i=2;i<=m;++i)
		for(int j=1;j<=top;++j)
			upd(dp[i-1][j],dp[i-1][j-1]),dp[i][top-j+1]=1ll*dp[i-1][j]*f[top-j+1]%mod;
	for(int i=1;i<=top;++i) upd(ans,dp[m][i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 233728
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>


using namespace std;

#define ASIZE 100010

void dfs(const long& i, const long& start, const long& rootW,  const long& n, vector< pair<long,bool> > (&ad)[ASIZE], vector<bool>& visited, vector<bool>& ans) {
    if ( visited[i] ) return;
    visited[i] = true;
    ans[i] = rootW%2==0 ? ans[start] : !ans[start];

    for (auto v : ad[i] ) {
        dfs(v.first, start, rootW + v.second, n, ad, visited, ans);
    }
}

int main() {
    long n;
    cin >> n;
    vector < pair<long,bool> > ad [ASIZE];
    vector <bool> visited (ASIZE, false);
    vector <bool> ans (ASIZE, false);

    for (long i=1; i<n; i++) {
        long u,v,w;
        cin >> u >> v >> w;
        // ad[u][v] = ad[v][u] = w;
        ad[u].push_back( make_pair(v,w%2) );
        ad[v].push_back( make_pair(u,w%2) );
    }
    

    for (long i=1; i<=n; i++) {
        if ( visited[i] ) continue;
        ans[i] = true;
        dfs(i, i, 0, n, ad, visited, ans);
    }

    for (long i=1; i<=n; i++) {
        cout << ans[i] << endl;
    }
    // cout << endl;
  
}

Measured memory_bytes: 11776
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;

#define LEN 100005

typedef struct pp{
	char name[100];
	int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
	Q[tail] = x;
	tail = (tail + 1) % LEN;
}

P dequeue(){
	P x = Q[head];
	head = (head + 1) % LEN;
	return x;
}

int min(int a, int b){
	if(a > b)return b;
	else return a;
}


int main(){
	int elaps = 0, c;
	int i, q;
	P u;
	cin >> n >> q;

	for(i = 1; i <= n; i++){
		cin >> Q[i].name;
		cin >> Q[i].t;
	}
	head = 1;
	tail = n + 1;

	while(head != tail){
		u = dequeue();
		c = min(q, u.t);
		u.t -= c;
		elaps += c;
		if(u.t > 0){
			enqueue(u);
		}
		else{
			cout << u.name << " " << elaps << endl;
		}
	}
}


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

using namespace std;
using ll = long long;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;

int main() {
    string A;
    cin >> A;
    ll n = sz(A);

    map<char, ll> cnt;
    for (int i = 0; i < n; i++) {
        cnt[A[i]]++;
    }

    ll ans = n * (n - 1) / 2 + 1;
    for (char i = 'a'; i <= 'z'; i++) {
        ll c = cnt[i];
        ans -= c * (c - 1) / 2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	List<List<Integer>> G;
	int n;
	int[] color;

	private void run() {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		int m = scanner.nextInt();
		G = new ArrayList<List<Integer>>();
		color = new int[n];
		for (int i = 0; i < n; i++) {
			G.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < m; i++) {
			int s = scanner.nextInt();
			int t = scanner.nextInt();
			G.get(s).add(t);
			G.get(t).add(s);
		}
		assiginColor();

		int q = scanner.nextInt();
		for (int i = 0; i < q; i++) {
			int s = scanner.nextInt();
			int t = scanner.nextInt();
			if (color[s] == color[t]) {
				System.out.println("yes");
			} else {
				System.out.println("no");
			}
		}
	}

	private void assiginColor() {
		Arrays.fill(color, -1);
		int id = 1;
		for (int i = 0; i < n; i++) {
			if (color[i] == -1)
				dfs(i, id++);
		}
	}

	private void dfs(int r, int c) {
		Deque<Integer> deque = new ArrayDeque<Integer>();
		deque.push(r);
		color[r] = c;
		while (!deque.isEmpty()) {
			int u = deque.poll();
			for (int i = 0; i < G.get(u).size(); i++) {
				int v = G.get(u).get(i);
				if (color[v] == -1) {
					color[v] = c;
					deque.push(v);
				}
			}
		}
	}
}

Measured memory_bytes: 111172
import sys
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n=II()
	A=LI()
	A.sort(reverse=True)

	ans=A[0]
	ans+=2*sum(A[1:(n+1)//2-1])

	if n%2:
		ans+=A[n//2]
	elif n>3:
		ans+=2*A[(n-1)//2]

	print(ans)











if __name__ == "__main__":
	main()


Measured memory_bytes: 92856
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,k;cin>>n>>k;
  int num=1;
  rep(i,n)
  {
    num+=min(num,k);
  }
  cout<<num<<endl;

  return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int N; cin>>N;
  string S; cin>>S;
  if(N<=1 || N%2==1){
    cout<<"No"<<endl;
  }else{
    if(S.substr(0,N/2)==S.substr(N/2,N/2)){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
  }
}


Measured memory_bytes: 256
n = int(input())
prevA, prevB, prevC = 0, 0, 0
for i in range(n):
    a,b,c = map(int, input().split())
    act_a_on_ith_day = a + max(prevB, prevC)
    act_b_on_ith_day = b + max(prevA, prevC)
    act_c_on_ith_day = c + max(prevA, prevB)
    prevA, prevB, prevC = act_a_on_ith_day, act_b_on_ith_day, act_c_on_ith_day
print(max(prevA, prevB, prevC))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int n = s.length();
  int m = t.length();
  vector<int> acm(n + 1, 0);
  vector<int> bcm(m + 1, 0);
  for (int p = 0; p < 2; p++) {
    for (int i = 1; i <= n; i++) {
      acm[i] = acm[i - 1];
      if (s[i - 1] == 'A') acm[i]++; else acm[i]--;
      acm[i] = (acm[i] + 3) % 3;
    }
    swap(acm, bcm);
    swap(n, m);
    swap(s, t);
  }
  int q;
  cin >> q;
  while (q--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((acm[b] - acm[--a] - bcm[d] + bcm[--c] + 12) % 3) {
      cout << "NO" << '\n';
    } else {
      cout << "YES" << '\n';
    }
  }
  return 0;
}

Measured memory_bytes: 1744
#include <iostream>
#include<algorithm>
#include<math.h>
using namespace std;
long long a,b;
long long out;
int main(){
	cin >> a >> b ;
	long long x=0;
	if(a>=b) {
		if(a%b) x = min(a%b,llabs(a%b-b));
		else x=0;
	}
	else x = min(a,llabs(a-b));
	cout <<x<<endl;
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
#define int long long
#define read(a) int a; cin >> a;
#define readarr(a, n) int a[(n) + 1] = {}; fori(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; fori(i, 1, n) {fori(j, 1, m) cin >> a[i][j];}
#define pb push_back
#define fi first
#define se second
#define rz resize
#define fori(i, a, b) for(int i = a; i <= b; i++)
#define ford(i, a, b) for(int i = a; i >= b; i--)
#define  sort1(v) sort(v.begin(), v.end()) 
#define endl '\n'
 
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair <int, int>> vpi;
typedef vector < vector <int> > vvi;
 
const long long inf2 = (long long)1e18;
const long long mod = (long long)(1e9+7);
const long long inf1 =(long long)(1e6+1);
 
 
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, ans = 0;
    cin >> n >> m;

    char a[n+1][m+1];
 
    fori(i, 1, n) fori(j, 1, m) cin >> a[i][j];
    
    fori(i, 1, n)
    {
        fori(j, 1, m)
        {
            if(a[i][j] == '.')
            {
                int vis[n+1][m+1] = {}, d[n+1][m+1] = {};
                vis[i][j] = 1;
                queue < pair <int, int>> q;
                q.push({i, j});
             
                while(!q.empty())
                {
                    int ii = q.front().fi;
                    int jj = q.front().se;
                    
                    q.pop();
             
                    if(ii < n)
                    {
                        if(a[ii+1][jj] == '.' && vis[ii+1][jj] == 0) {q.push({ii+1, jj}); vis[ii+1][jj] = 1; d[ii+1][jj] = d[ii][jj]+1;}
                    }
                    
                    if(ii > 1)
                    {
                        if(a[ii-1][jj] == '.' && vis[ii-1][jj] == 0) {q.push({ii-1, jj}); vis[ii-1][jj] = 1; d[ii-1][jj] = d[ii][jj] + 1;}
                    }
             
                    if(jj < m)
                    {
                        if(a[ii][jj+1] == '.' && vis[ii][jj+1] == 0) {q.push({ii, jj+1}); vis[ii][jj+1] = 1; d[ii][jj+1] = d[ii][jj] + 1; }
                    }
                    
                    if(jj > 1)
                    {
                        if(a[ii][jj-1] == '.' && vis[ii][jj-1] == 0) {q.push({ii, jj-1}); vis[ii][jj-1] = 1; d[ii][jj-1] = d[ii][jj] + 1;}
                    }
                }

                fori(k, 1, n) fori(l, 1, m) ans = max(ans, d[k][l]);
            }
        }
    }
 
    cout << ans;
 
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){int n,w,t,i,m;string s;while(1){cin>>i;n=2,w=3,t=1;if(i==0)break;for(int j=0;j<i;j++){cin>>s;if(s=="north")m=n,n=t,t=7-m;if(s=="south")m=t,t=n,n=7-m;if(s=="west")m=t,t=7-w,w=m;if(s=="east")m=t,t=w,w=7-m;}cout<<t<<"\n";}}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a;i<(int)b;++i)
int main(){
  string s;cin>>s;
  vector<bool> v(26,false);
  rep(i,s.size())v[s[i]-'a']=true;
  rep(i,26)if(v[i]==false){
   cout<<(char)('a'+i)<<endl;
    return 0;
  }
  cout<<"None"<<endl;
    return 0;
}

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

using namespace std;

typedef long long int64;

int64 N, A[100000];
vector< int > g[100000];

void rec(int idx, int par)
{
  if(g[idx].size() == 1) return;
  int64 ret = 0, large = 0;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    rec(to, idx);
    ret += A[to];
    large = max(large, A[to]);
  }
  if(A[idx] > ret || ret > 2 * A[idx]) {
    puts("NO");
    exit(0);
  }
  int64 rest = ret - A[idx];
  if(rest > ret - large) {
    puts("NO");
    exit(0);
  }
  A[idx] -= rest;
}

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }

  if(N == 2) {
    if(A[0] == A[1]) puts("YES");
    else puts("NO");
    return (0);
  }

  for(int i = 0; i < N; i++) {
    if(g[i].size() >= 2) {
      rec(i, -1);
      if(A[i] == 0) puts("YES");
      else puts("NO");
      return (0);
    }
  }

}


Measured memory_bytes: 13184
import scala.annotation.tailrec

object Main extends App {

  import scala.io.StdIn._
  //calTheOtherPrice(5, 105, 13)
  solve
  @tailrec def solve: Unit = {
    val Array(x, y, s) = readLine.trim.split(' ').map(_.toInt)
    if (x == 0) return
    else {
      println(maxWithTax(x, y, s))
      solve
    }
  }
  def maxWithTax(x: Int, y: Int, sum: Int): Int = {
    (1 to sum / 2).flatMap{i ⇒ calTheOtherPrice(x, sum, i).map{o ⇒
      calPrice(y, i) + calPrice(y, o)
    }}.max
  }
  def calTheOtherPrice(x: Int, sum: Int, price:Int): Option[Int] = {
    val res = upperBound(1, sum){other ⇒
          calPrice(x, price) + calPrice(x, other) <= sum
    }
    if (res != 1 && calPrice(x, price) + calPrice(x, res - 1) == sum) Some(res - 1)
    else None
  }
  def calPrice(x: Int, price:Int): Int = {
    ((100 + x) * price / 100.0).toInt
  }
  @tailrec def upperBound(min: Int, max:Int)(func:Int ⇒ Boolean): Int = {
    val mid = (min + max) / 2
    if (min >= max) max
    else if (func(mid)) upperBound(mid + 1, max)(func)
    else upperBound(min, mid)(func)
  }
}



Measured memory_bytes: 54500
//g++ -std=c++14 test.cpp -o test.out
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL A,B,C,D;

LL ans = 0;

void solve(){
	ans = max(max(A*C,A*D),max(B*C,B*D));
}
 
int main(){
	cin >> A >> B >> C >> D;
 
    solve();

	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3188
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n;
		
		while((n = sc.nextInt()) != 0){

			int[][] list = new int[n + 1][n + 1];
			
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					list[i][j] = sc.nextInt();
					list[i][n] += list[i][j];
		}
				list[n][n] += list[i][n];
				
				for(int j = 0; j < n; j++)
					list[n][j] += list[i][j];
		}
			for(int i = 0; i < n + 1; i++){
				for(int j = 0; j < n + 1; j++)
					System.out.printf("%5d", list[i][j]);
				
				System.out.println();
			}
		}
	}
}

Measured memory_bytes: 23928
using System;
using System.Collections.Generic;

namespace AtCoderCpp
{
    // ABC-126
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var K = int.Parse(input[1]);

            double p = 0;

            for (int i = 1; i <= N; i++)
            {
                var n = 0;
                while (Math.Pow(2, n) * i < K)
                {
                    n++;
                }
                p += Math.Pow(0.5, n) / N;
            }
            Console.WriteLine(p);
        }
    }

}

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

int main()
{
    int n,number[101]={0},max=0;
    while(cin>>n){
        number[n]++;
        if(number[n]>max){
            max=number[n];
        }
    }
    for(int i=1;i<101;i++){
        if(number[i]==max){
            cout<<i<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1164
N = int(input())
A = [int(input()) for i in range(N)]

counter_hash = {}


for i in A:
        if i in counter_hash:
                counter_hash[i] = (counter_hash[i] + 1) % 2
        else:
                counter_hash[i] = 1
        
print(sum(counter_hash.values()))

Measured memory_bytes: 16272
w, h, n = gets.split.map &:to_i
a = (1..n).map { gets.split.map &:to_i }
total = 0 
a.each_cons(2){|u, v|
    x1, y1 = u 
    x2, y2 = v 
    if (x1 - x2) * (y1 - y2) >= 0
        total += [(x1-x2).abs, (y1-y2).abs].max
    else
        total += (x1-x2).abs + (y1-y2).abs
    end 
}
p total

Measured memory_bytes: 6116
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
bool Cmp(char a,char b){
    return a<b;
}
int main(){
    char str[50][55];
    memset(str,0,sizeof(str));
    int n,len[26];
    for(int i=0;i<26;i++)len[i]=500;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>str[i];
        sort(str[i],str[i]+strlen(str[i]),Cmp);
    }
    for(int i=0;i<n;i++){
        int k=0;
        for(int j=0;j<26;j++){
            int count=0;
            while(k<strlen(str[i])&&str[i][k]==char('a'+j)){
                k++;
                count++;
            }
            if(count<len[j])len[j]=count;
        }
    }
    for(int i=0;i<26;i++){
        if(len[i]==500)continue;
        for(int j=0;j<len[i];j++){
            cout<<(char)('a'+i);
        }
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
G=UnionFind(N)
for i in range(M):
    x,y,z=map(int,input().split())
    G.unite(x-1,y-1)
X=[G.find(i) for i in range(N)]
print(len(set(X)))


Measured memory_bytes: 17960
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		sc.close();
		
		int res = 0;
		if(n % 1000 == 0)
			res = 0;
		else
			res = Math.abs(n % 1000 - 1000);
		System.out.println(res);
	}

}

Measured memory_bytes: 35300
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(),x.end()
#define ln '\n'
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<MOD>;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,A,B; cin >> N >> A >> B;
    int K = N;
    mint ans = 1;
    mint t = 2;
    while (K > 0) {
        if (K&1) ans *= t;
        K /= 2;
        t *= t;
    }

    mint p = 1;
    for (int i = N; i > N-A; i--) {
        p *= i;
    }
    for (int i = 1; i <= A; i++) {
        p /= i;
    }
    mint q = 1;
    for (int i = N; i > N-B; i--) {
        q *= i;
    }
    for (int i = 1; i <= B; i++) {
        q /= i;
    }
    ans -= p+q+1;

    cout << ans.a << ln;
}

Measured memory_bytes: 256
package main
import "fmt"

func main() {
	var s []byte
	fmt.Scanf("%s", &s)

	var before byte = s[0]
	var c int = 0
	for _, b := range s {
		if before != b {
			before = b
			continue
		}
		c += 1
		if b == '0' {
			before = '1'
		} else {
			before = '0'
		}
	}
	if len(s)/2 < c {
		c = len(s) - c
	}

	fmt.Println(c)
}



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

int main() {
    string s;
    cin >> s;
    int c = 0;
    int m = 0;
    for(int i=0;i<s.size();i++) {
        if (s[i] == 'R') {
            c += 1;
            if (m <= c) {
                m = c;
            }
        } else {
            c = 0;
        }
    }
    cout << m << endl;
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    char s[12];
    cin >> s;
    for(int i=0; i<a; i++){
        if(!('0'<=s[i]&&s[i]<='9')){
            cout << "No" << endl;
            return 0;
        }
    }
    if(s[a]!='-'){
        cout << "No" << endl;
        return 0;
    }
    for(int i=a+1; i<=a+b; i++){
        if(!('0'<=s[i]&&s[i]<='9')){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}




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

int main() {
  int N;
  cin >> N ;
  
  vector<int> vec(N);
  int max, mnum, sec, snum;
  
  max = 0;
  
  for(int i = 0; i < N; i++){
  	cin >> vec.at(i) ;
    if(vec.at(i) > max){
      sec = max;
      snum = mnum;
      max = vec.at(i);
      mnum = i;
    }else if(vec.at(i) > sec){
      sec = vec.at(i);
      snum = i;
    }
  }
  
  for(int i=0; i<N; i++){
    if(i != mnum)
      cout << max << endl;
    else
      cout << sec << endl;
  }
}

Measured memory_bytes: 2432
###############################################################################
#Imports
import collections
import itertools
from functools import lru_cache
import sys
import math
###############################################################################
#Constants
MOD = int(1e9)+7
###############################################################################
#Helper
def helper():
	pass
###############################################################################
#Solver
def solve():
	a, b = map(int, input().split(' '))
	print(a*b)

###############################################################################
#Driver
t = 1
for _ in range(t):
	solve()
###############################################################################


Measured memory_bytes: 67440
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(dist, start, goal):
    H,W = len(dist),len(dist[0])

    q = [start]
    dist[start[0]][start[1]] = 0
    cnt = 0
    while q:
        nq = []
        while q:
            x,y = q.pop()
            if (x,y) == goal:
                return cnt
            if dist[x][y] < cnt:
                continue
            for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
                nx,ny = x+dx,y+dy
                if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt:
                    dist[nx][ny] = cnt
                    q.append((nx,ny))
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx,ny = x+dx,y+dy
                    if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt+1:
                        dist[nx][ny] = cnt+1
                        nq.append((nx,ny))
        q = nq
        cnt += 1
    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)-1,readline().split()))
    goal = tuple(map(lambda i:int(i)-1,readline().split()))

    dist = [[10**7 if c=='.' else -1 for c in t.decode()] for t in read().split()]

    print(solve(dist,start,goal))

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

int main() {
    long long R, G, B, N;
    cin >> R >> G >> B >> N;
    long long ans = 0;
    for (long long  r = 0; r <= N; r++)
        for (long long  g = 0; g <= N; g++) {
            int tmp = N - r * R - g * G;
            if (tmp < 0 || tmp % B != 0)
                continue;
            ans++;
        }
    cout << ans << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG=20;

ll n, A, B, u, v, x, y, t, a, b, ans;
ll H[MAXN];

bool check(ll x){
	ll res=0;
	for (int i=1; i<=n; i++) res+=(max(0ll, H[i]-x*B)+A-B-1)/(A-B);
	return res<=x;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>A>>B;
	for (int i=1; i<=n; i++) cin>>H[i];
	ll dwn=-1, up=inf;
	while (up-dwn>1){
		ll mid=(dwn+up)>>1;
		if (check(mid)) up=mid;
		else dwn=mid;
	}
	cout<<up<<'\n';
	
	
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
typedef pair<int,int> PP;
typedef long long ll;
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; }
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE cout << -1 << endl;return 0
#define MM <<" "<<
#define Endl endl


signed main(void){
    int N,K;
    cin >> N >> K;
    int pas[2001][2001];
    REP(i,2000){
        pas[0][i]=1;
        pas[i][0]=1;
    }
    REP(i,1999){
        REP(j,1999){
            pas[i+1][j+1]=(pas[i+1][j]+pas[i][j+1])%MOD;
        }
    }
    REP(i,K){
        int Ans=1;
        if(K-1-i>=0 && i>=0){
            Ans=(Ans*pas[K-i-1][i])%MOD;
        }else{
            Ans=0;
        }
      //cout << Ans << endl;
        if(N-K-i>=0 && i+1>=0){
            Ans=(Ans*pas[N-K-i][i+1])%MOD;
        }else{
            Ans=0;
        }
        cout << Ans << endl;
    }
    return 0;
}



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

s = [0]
for i in range(n):
    s.append((s[-1] + a[i] - 1) % k)

# dic = {remainder:number}
dic = {0:1}
ans = 0
if n < k:
    for i in range(1, n+1):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

else:
    for i in range(1, k):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

    for i in range(k, n+1):
        dic[s[i-k]] -= 1
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

print(ans)

Measured memory_bytes: 111044
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
using namespace std;
template<typename V,typename Weight>
class Dijekstra {
public:
	struct edge {
		Weight dist;V node;V prev;
		bool operator<(edge const& a) const {
			return dist < a.dist;
		}
		bool operator>(edge const& a) const {
			return dist > a.dist;
		}
	};
	//vector<V> trace;
	vector<vector<pair<V,Weight>>> E;
	V const sz;
	Weight const inf = numeric_limits<Weight>::max();
	vector<Weight> D;
	Dijekstra(V v) :
		E(v),sz(v),D(v,inf) {}

	void inline addEdgeDirected(V from,V to,Weight dis){
		E[from].push_back(make_pair(to,dis));
	}
	void inline addEdgeUndirected(V from,V to,Weight dis){
		E[from].push_back(make_pair(to,dis));
		E[to].push_back(make_pair(from,dis));
	}

	V size() {return sz;}
	Weight & operator[] (V n) { if (0 <= n && n < sz) return D[n];} 

	void dijekstra(V start){
		priority_queue<pair<Weight,V>,vector<pair<Weight,V>>,greater<pair<Weight,V>>> que;
		D[start] = 0;
		que.push(make_pair(0,start));
		while(!que.empty()){
			pair<Weight,V> cur = que.top();que.pop();
			Weight d = cur.first;
			V v = cur.second;
			if (D[v] < d) continue; //既により最適が見つかっている
			for(V i = 0;i < E[v].size();i++){
				V next = E[v][i].first;
				Weight newCost = d + E[v][i].second;
				if (D[next] > newCost) {
					D[next] = newCost;
					que.push(make_pair(newCost,next));
				}
			}
		}
	}
/*
	vector<V> show_trace(V start,V goal){ // startからgoalの最短距離上のノード
		vector<V> ret;
		for (V node = goal;node != start;node = trace[node]) ret.push_back(node);
		ret.push_back(start);
		return ret; // 配列の先頭がgoal,末尾がstart
	}
*/
};

int main(void){
	long V,E,R;
	long s,t,d;
	cin >> V >> E >> R;
	Dijekstra<long,long> dij(V);

	REP(i,E){
		cin >> s >> t >> d;
		dij.addEdgeDirected(s,t,d);
	}
	dij.dijekstra(R);
	REP(i,V) {
		if (dij[i] == dij.inf) cout << "INF" << endl;
		else cout << dij[i] << endl;
	}

	return 0;
}





Measured memory_bytes: 19288
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct diameter{
	static const int MAX=300000;
	static const int INF=300000;
	vector<int> G[MAX];
	int n;
	int d[MAX];
	bool vis[MAX];
	int d2[2][MAX];

	void bfs(int s){
		fill(d,d+n,INF);
		queue<int> que;
		que.push(s);
		d[s]=0;
		int v;
		while(que.size()){
			v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				int e=G[v][i];
				if(d[e]==INF){
					d[e]=d[v]+1;
					que.push(e);
				}
			}
		}
	}

	int diameter_points(int s=0){
		bfs(s);
		int maxv=0;
		int tgt=0;
		for(int i=0;i<n;i++){
			if(d[i]==INF)continue;
			if(maxv<d[i]){
				maxv=d[i];
				tgt=i;
			}
		}
		bfs(tgt);
		maxv=0;
		int v=0;
		for(int i=0;i<n;i++){
			if(d[i]==INF)continue;
			if(maxv<d[i]){
				maxv=d[i];
				v=i;
			}
		}
		return maxv;
	}
};

int n;
diameter dia;

int main(void){
	scanf("%d",&n);
	dia.n=n;
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		dia.G[a].push_back(b);
		dia.G[b].push_back(a);
	}
	int val=dia.diameter_points();
	if(val%3==1){
		printf("Second\n");
	}else{
		printf("First\n");
	}
	return 0;
}


Measured memory_bytes: 16244
import java.util.Scanner;

public class Main {

	public static int gcd2(int a, int b) {
		if (a % b == 0) {
			return b;
		} else {
			return gcd2(b, a % b);
		}
	}

	public static int gcd(int a, int b, int c) {
		return gcd2(a, gcd2(b, c));
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		int a, b, c;
		long sum = 0;
		for (a = 1; a <= K; a++) {
			for (b = 1; b <= K; b++) {
				for (c = 1; c <= K; c++) {
					sum += gcd(a, b, c);
				}
			}
		}

		System.out.println(sum);
	}
}


Measured memory_bytes: 27248
nhw=list(map(int,input().split()))
ab = [[0,0] for i in range(nhw[0])]
for i in range(nhw[0]):
    ab[i]=list(map(int,input().split()))
c=0
for i in range(nhw[0]):
     if ab[i][0] >= nhw[1] and ab[i][1] >= nhw[2]:
        c += 1
print(c)


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

int main()
{
    string s, t;
    cin >> s >> t;

    s += s;

    vector<vector<int>> position(26, vector<int>());
    for (int i = 0; i < s.size(); i++)
    {
        position[s[i] - 'a'].push_back(i);
    }

    long long ans = 0;
    int current = -1;
    int next;
    for (char c : t)
    {
        if (position[c - 'a'].empty())
        {
            cout << -1 << endl;
            return 0;
        }

        auto itr = upper_bound(position[c - 'a'].begin(), position[c - 'a'].end(), current);
        if (itr == position[c - 'a'].end())
        {
            itr = position[c - 'a'].begin();
        }
        next = *itr;

        ans += next - current;
        current = next;
        if (current >= (s.size() / 2))
        {
            current -= s.size() / 2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1788