akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define int long long
#define double long double
#define pb push_back
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define diff(a,b) (a>b?a-b:b-a)
const int N=1e6+5;
void pairsort(int a[], int b[], int n){
    pair<int, int> pairt[n];
    for (int i = 0; i < n; i++) 
    {
        pairt[i].first = a[i];
        pairt[i].second = b[i];
    }
    sort(pairt, pairt + n);
    for (int i = 0; i < n; i++) 
    {
        a[i] = pairt[i].first;
        b[i] = pairt[i].second;
    }
}
int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b); 
}
int isPrime(int n){
    if(n < 2)
        return 0;
    if(n < 4)
        return 1;
    if(n % 2 == 0 or n % 3 == 0)
        return 0;
    for(int i = 5; i*i <= n; i += 6)
        if(n % i == 0 or n % (i+2) == 0)
            return 0;
    return 1;
}
long long C(int n, int r) {
    if(r>n-r) 
        r=n-r;
    long long ans=1;
    for(int i=1;i<=r;i++){
        ans*=n-r+i;
        ans/=i;
    }
    return ans;
}
int mod = 1e9+7;
int modexpo(int x,int p){
    int res = 1;
    x = x%mod;
    while(p){
        if(p%2)
            res = res * x;
        p >>= 1;
        x = x*x % mod;
        res %= mod;
    }
    return res;
}
int n,a[N],ans;
map<int,int> M;
int32_t main()
{
    IOS;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],M[a[i]]++;
    for(auto it=M.begin();it!=M.end();it++)
    {
        int x=it->second;
        ans+=(x*(x-1))/2;
    }
    for(int i=1;i<=n;i++)
    {
        if(M[a[i]]>1)
            cout<<ans-M[a[i]]+1<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue> //std::priority_queue<int> que; // 4, 3, 2, 1 (defualt, less) : 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>  // std::accumulate(m.begin(), m.end(), 0LL);
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  int N; std::cin >> N;
  std::vector<int> a(N); for(int i=0; i<N; i++) std::cin >> a[i];

  std::unordered_map<int,int> L;
  for(int i=0; i<N; i++) {
    if ( L.count(a[i]) == 0 ) L[a[i]] = 1;
    else L[a[i]]++;
  }

  int ans = 0;
  for(auto&& l : L) {
    if ( l.first != l.second ) {
      if ( l.first > l.second ) ans += l.second;
      else ans += std::min(l.second, std::abs(l.first-l.second));
    }
  }
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 4644
N = gets.to_i
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)

husoku = 0
overpoints = []
result = 0

N.times do |i|
  if A[i] > B[i]
    overpoints.push(A[i] - B[i])
  elsif A[i] < B[i]
    husoku += B[i] - A[i]
    result += 1
  end
end

overpoints = overpoints.sort

while husoku > 0 do
  point = overpoints.pop
  unless point 
    puts -1
    exit
  end
  husoku -= point
  result += 1
end

puts result

Measured memory_bytes: 16576
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
const long long mod = 1000000007;

struct W {
	int a, b, d;
};
W *w;
std::vector<W*> *p;
int *out;
int *c;
bool *checked;
W **tree;
int cnt = 0;
int N, M;

void MakeTree(int id = 0) {
	checked[id] = true;
	c[cnt] = id;
	cnt++;
	for (int i = 0; i < p[id].size(); i++) {
		int r = p[id][i]->a == id ? p[id][i]->b : p[id][i]->a;
		if (!checked[r]) {
			tree[cnt] = p[id][i];
			MakeTree(r);
		}
	}
}


int main() {
	scanf("%d %d", &N, &M);
	w = new W[M];
	p = new std::vector<W*>[N];
	out = new int[N];
	c = new int[N];
	checked = new bool[N];
	tree = new W*[N];
	for (int i = 0; i < N; i++) {
		out[i] = 0;
		checked[i] = false;
	}
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--;
		b--;
		w[i].a = a;
		w[i].b = b;
		w[i].d = 0;
		p[a].push_back(w + i);
		p[b].push_back(w + i);
		out[a]++;
	}
	if (M % 2 == 1) {
		printf("-1");
	}
	else {
		MakeTree();
		for (int i = N - 1; i >= 1; i--) {
			if (out[c[i]] % 2 == 1) {
				tree[i]->d = 1;
				out[tree[i]->a == c[i] ? tree[i]->b : tree[i]->a]++;
			}
		}
		for (int i = 0; i < M; i++) {
			if (w[i].d == 0) {
				printf("%d %d\n", w[i].a + 1, w[i].b + 1);
			}
			else {
				printf("%d %d\n", w[i].b + 1, w[i].a + 1);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> a(n), b(n);
    ll sum_a = 0, sum_b = 0;
    REP(i,n) {
        cin >> a[i];
        sum_a += a[i];
    }
    REP(i,n) {
        cin >> b[i];
        sum_b += b[i];
    }
    bool ans = true;
    ll cnt = sum_b - sum_a;
    ll x = 0, y = 0;
    REP(i,n) {
      if(a[i]>b[i]) y += a[i]-b[i];
      else {
        x += (b[i]-a[i])/2;
        if((b[i]-a[i])%2==1) {
          ++ x, ++ y;
        }
      }
    }
    ans = (x <= cnt && y <= cnt);
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long in;
typedef pair<in,in> ii;
#define F first
#define S second
#define sqr(x) (x)*(x)
#define pb(x) push_back(x)
#define sz(x) (in)x.size()
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,x,y) for(in i=x;i<(y);++i)
#define per(i,x,y) for(in i=y;i>=(x);--i)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */
 
int main()
{
      IOS;
      in a,b,k;
      cin >> a >> b >> k;
      if(a>=k)
      {
            a-=k;
            cout << a << " " << b << "\n";
      }
      else
      {
            k-=a;
            a = 0;
            cout << a << " " << max(0LL,b-k) << "\n";
      }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;

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

    vector<pair<ll,ll>> lst(n+1,make_pair(0,0));
    rep(i,n) cin >> lst.at(i+1).first >> lst.at(i+1).second;

    vector<vector<ll>> dp(w+1,vector<ll>(n+1,0));

    for(int j=1;j<=n;j++){
        for(int i=0;i<=w;i++){
            ll notincluded = dp.at(i).at(j-1);
            ll included = 0;
            if(i-lst.at(j).first>=0){
                included = dp.at(i-lst.at(j).first).at(j-1) + lst.at(j).second;
            }
            dp.at(i).at(j) = max(notincluded,included);
        }
    }

    cout << dp.at(w).at(n) << endl;
}

Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
#define LL long int
#define ULL unsigned long int


int main(){
    int x;
    cin >> x;
    LL ans = 0;
    ans += x / 500 * 1000;
    x -= x / 500 * 500;
    ans += x / 5 * 5;
    cout << ans << endl;

    return 0;
}

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

int main() {
    ll K, A, B;
    cin >> K >> A >> B;
    if (B - A <= 2) {
        cout << 1 + K << endl;
        return 0;
    }
    if (1 + K <= A) {
        cout << 1 + K << endl;
        return 0;
    }
    ll left_time = K - (A - 1);
    ll ans = A + (left_time / 2) * (B - A);
    if (left_time % 2 == 1) {
        ans += 1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) begin(c), end(c)
using namespace std;
using ll = long long;
using ld = long double;

const int mod = 998244353;
const int N = 1e6+6;

ll inv(ll a, ll mod){
    if(a==1) return 1;
    ll x = inv(mod%a, a);
    return mod-mod*x/a;
}

int main(){
	//freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
	
	int n;
	
	cin>>n;
	vector<int> a(n);
	for(auto &_ : a) cin>>_;
	
	vector<ll> cnt(N);
	for(int i=0;i<n;++i) cnt[a[i]] = (cnt[a[i]] + a[i]) %mod;
	for(int i=1;i<N;++i){
		ll c = 0;
		for(int j=i;j<N;j+=i) c+=cnt[j];
		cnt[i] = c%mod;
	}
	
	for(int i=1;i<N;++i) cnt[i] = cnt[i]*cnt[i] %mod;
	
	for(int i=N-1;i>0;--i){
		for(int j=i*2;j<N;j+=i){
			cnt[i]-=cnt[j];
			if(cnt[i]<0) cnt[i]+=mod;
		}
	}
	
	ll ans = 0;
	
	for(int g=1;g<N;++g){
		ll cur = cnt[g] * inv(g,mod) %mod;
		ans+=cur;
		ans%=mod;
	}
	
	for(int x : a){
		ans = (ans - x + mod) %mod;
	}
	
	ans = ans*inv(2,mod) %mod;
	
	cout<<ans<<endl;
	
	
	return 0;
}


Measured memory_bytes: 8832
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
vector<ll> v;

int main(void)
{
	vector<ll> v;
	int n, k;
	ll t[1000000];
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> t[i];
		if (i!=0) {
			v.push_back(t[i] - t[i - 1] - 1);
		}
	}
	sort(v.begin(), v.end());
	ll ans = n;
	for (int i = 0; i < n-k; i++) {
			ans += v[i];
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 4700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(x) (int)(x).size()
#define endl '\n'
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
#define CEIL(a, b) ((a) + (b)-1) / (b)
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout \
  if (DEBUG) std::cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << mt(__VA_ARGS__) << "] "
template <typename T>
struct IsC {
  template <typename C>
  static char test(typename C::const_iterator*);
  template <typename C>
  static int test(...);
  static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
  static const bool value = false;
};
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream&, const C&);
template <typename T1, typename T2>
ostream& operator<<(ostream&, const pair<T1, T2>&);
template <typename... T> using TS = tuple_size<tuple<T...>>;
template<size_t idx, typename... T>
typename enable_if<TS<T...>::value == idx + 1, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return o << ", " << get<idx>(t) << ')';
}
template<size_t idx, typename... T>
typename enable_if<0 < idx && idx + 1 < TS<T...>::value, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << ", " << get<idx>(t), t);
}
template<size_t idx = 0, typename... T>
typename enable_if<1 < TS<T...>::value && !idx, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << '(' << get<idx>(t), t);
}
template<typename T>
ostream& operator<<(ostream& o, const tuple<T>& t) {
  return o << get<0>(t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p) {
  return o << mt(p.fi, p.se);
}
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(
    ostream& o, const C& c) {
  o << '[';
  for (auto it = c.cbegin(); it != c.cend(); ++it)
    o << *it << (next(it) != c.cend() ? ", " : "");
  return o << ']';
}
template <typename T>
void tprint(vector<vector<T>>& v, size_t width = 0, ostream& o = cerr) {
  if (!DEBUG) return;
  for (const auto& vv : v) {
    for (const auto& i : vv) o << setw(width) << i;
    o << endl;
  }
}



int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0); cin.tie(0);

  int n; cin >> n;
  ll ans = 0;
  FOR (a, 1, n) {
    for (int b = 1; a * b < n; ++b) {
      ++ans;
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3648
from functools import reduce
from fractions import gcd

N, K = map(int, input().split())
A = set(map(int, input().split()))

if K in A:
    print('POSSIBLE')
    exit()

if K > max(A):
    print('IMPOSSIBLE')
    exit()

g = reduce(gcd, A)

if g == 1:
    print('POSSIBLE')
    exit()

for a in A:
    if K > a:
        continue
    if (a - K) % g == 0:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 21804
import sys
C = list(map(int, input().split()))

res = 0

for c in C:
  if c % 2 == 0:
    print(res)
    sys.exit()

C.sort(reverse=True)

if C[0] % 2 == 0:
  print(0)
else:
  print(C[1] * C[2])

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

int main(){
    string s;
    cin>>s;
    string t;
    int ans=0;
    int check=0;
    while(1){
        check=0;
        cin>>t;
        if(t=="END_OF_TEXT"){
            break;
        }
        if(s.size()==t.size()){
            rep(i, s.size()){
                if(t.at(i)!=s.at(i)&&t.at(i)!=s.at(i)+32&&t.at(i)!=s.at(i)-32){
                    check=1;
                    break;
                }
            }
            if(check==0){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << '\n';
#define all(x) x.begin(), x.end()
#define fi first
#define se second
typedef int64_t Int;
Int mod = 1e9+7;
Int INF = 1e9+7;

Int dp[5001 * 2];
Int dp2[5000 * 5000 + 1];

int main() {
    Int n;
    cin >> n;
    Int a[2][3] = {};
    for (Int i = 0; i < 2; i++) {
        for (Int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    for (Int i = 0; i <= n; i++) {
        dp[i] = i;
    }
    Int w[3], v[3];
    for (Int i = 0; i < 3; i++) {
        w[i] = a[0][i];
        v[i] = max(a[0][i], a[1][i]);
    }
    for (Int i = 0; i < 3; i++) {
        for (Int j = 0; j <= 5000; j++) {
            dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
        }
    }
    Int m = dp[n];
    for (Int i = 0; i <= m; i++) {
        dp2[i] = i;
    }
    for (Int i = 0; i < 3; i++) {
        w[i] = a[1][i];
        v[i] = max(a[0][i], a[1][i]);
    }
    for (Int i = 0; i < 3; i++) {
        for (Int j = 0; j <= 5000 * 5000; j++) {
            if (j + w[i] > 5000 * 5000) continue;
            dp2[j + w[i]] = max(dp2[j + w[i]], dp2[j] + v[i]);            
        }
    }
    dump(dp2[m]);
    return 0;
}

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

namespace AOJ.Volume0
{
    public class Trading
    {
        public static void Main()
        {
            var company = new Dictionary<int, int>();
            var output = new List<int>();

            // 今月
            while (true)
            {
                var input = Console.ReadLine();
                if (string.IsNullOrEmpty(input)) { break; }

                int id = int.Parse(input.Substring(0, input.IndexOf(',')));
                if (company.ContainsKey(id)) { company[id]++; }
                else { company.Add(id, 1); }
            }

            // 先月
            while (true)
            {
                var input = Console.ReadLine();
                if (string.IsNullOrEmpty(input)) { break; }

                int id = int.Parse(input.Substring(0, input.IndexOf(',')));
                // 出現回数をカウントするが、今月取引がなかった場合は何もしない
                if (company.ContainsKey(id)) { company[id]++; }
                // 出力リストに入っていない場合は今月の取引があるかチェック
                if (!output.Contains(id))
                {
                    if (company.ContainsKey(id)) { output.Add(id); }
                }
            }

            // 出力
            output.Sort();
            foreach (var id in output)
            {
                Console.WriteLine(string.Format("{0} {1}", id, company[id]));
            }
        }
    }
}

Measured memory_bytes: 9760
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"
#define P           pair<int, int>
#define dint        long double


void solve() {
    string s; cin >> s;
    if(s=="ABC") cout << "ARC\n";
    else cout << "ABC\n";
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;
    for(int i=1; i<=T; i++) {
        solve();
    }
    return 0;

}



Measured memory_bytes: 3636
#include <iostream>
#include <set>
#include <string>

int main() {
    std::string s;
    std::cin >> s;

    std::set<char> ss;
    
    for(int i = 0; i < 3; i++) {
        ss.insert(s[i]);
    }

    if(ss.size() != 1) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a[5];
  for(int i=0;i<5;i++)
  {
    int temp;
    cin>>temp;
    if(temp==0)
    {
      cout<<i+1<<"\n";
      break;
    }
  }
}

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

int main()
{
  int n, k;
  cin >> n >> k;
  double a[n];
  for(int i = 0; i < n; i++)
    cin >> a[i];
  for(int i = 0; i < n; i++)
  {
    a[i] = a[i] * (a[i] + 1) / (2.0 * a[i]); 
  }
  double ans = 0, sum = 0;
  for(int i = 0; i < n; i++)
  {
    sum += a[i];
    if(i < k - 1)
      continue;
    ans = max(ans, sum);
    sum -= a[i - k + 1]; 
  }
  printf("%.10f", ans);
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

const int INF=1000100010;
const int MAX_N=101;
struct edge{
    int to,cap,rev;
    edge(int to,int cap,int rev):
    to(to),cap(cap),rev(rev){}
    };

vector<edge> g[MAX_N];
bool used[MAX_N];
void add_edge(int src,int dst,int cap){
    g[src].pb(edge(dst,cap,g[dst].size()));
    g[dst].pb(edge(src,0,g[src].size()-1));
}
int dfs(int v,int t,int f){
    if(v==t) return f;
    used[v]=true;
    rep(i,g[v].size()){
        edge &e=g[v][i];
        if(!used[e.to]&&e.cap>0){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                g[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t){
    int flow=0;
    while(1){
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0) return flow;
        flow+=f;
    }
}
int main(){
    int n,e;
    cin>>n>>e;
    int s,t,c;
    rep(i,e){
        cin>>s>>t>>c;
        add_edge(s,t,c);
    }
    cout<<max_flow(0,n-1)<<endl;
    return 0;
}


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int cnt = 0;
    while(a%2==0 and b%2==0 and c%2==0){
        int a2 = b/2+c/2;
        int b2 = a/2+c/2;
        int c2 = a/2 + b/2;
        if(a==a2 and b==b2 and c==c2){
            cnt = -1;
            break;
        }
        a=a2;
        b=b2;
        c=c2;
        cnt+=1;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3616
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define revrep(i,begin,end) for(int i=begin; i>end; i--)
#define lld long long int

int main(){
    int n;
    scanf("%d", &n);
    int a[2][n];
    rep(i, 0, 2){
        rep(j, 0, n){
            scanf("%d", &a[i][j]);
        }
    }
    int x[n+1], y[n+2];
    x[0] = 0; y[n+1] = 0;
    rep(i, 1, n+1){
        x[i] = x[i-1] + a[0][i-1];
        y[n-i+1] = y[n-i+2] + a[1][n-i];
    }
    int ans = 0;
    rep(i, 1, n+1){
        int buf = x[i] + y[i];
        if(ans < buf){
            ans = buf;
        }
    }
    printf("%d", ans);

    return 0;
}

Measured memory_bytes: 128
import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)


#nCrの計算。nこの中から、r個を取り出す。
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

import copy


n = int(input())
a = list(map(int,input().split()))

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

#print(b)

#c = [0]*(n+1)
#c = copy.copy(b)
#c = list(set(c))
#print(c)

import collections
c = collections.Counter(b)
#print(c)
#print(c.values())

ans = 0

for i in c.values():
	#print(i)
	#chk = b.count(i)

	#print(chk)
	if i >= 2:
		ans = ans + i*(i-1)//2

print(ans)




Measured memory_bytes: 112012
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> h(n);
    rep(i,n) cin >> h[i];

    sort(all(h));

    ll ans = 0;
    if (k>=n) {
        cout << 0 << endl;
        return 0;
    }
    rep(i,k) {
        if (h.size()==0) break;
        h.pop_back();
    }
    rep(i,n-k) {
        ans += h[i];
    }
    cout << ans << endl;
    return 0;
}



























Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
	  Scanner scan = new Scanner(System.in);
      int n = scan.nextInt();
      if(400<=n && n<600){
        System.out.println(8);
      }else if(600<=n && n<800){
        System.out.println(7);
      }else if(800<=n && n<1000){
        System.out.println(6);
      }else if(1000<=n && n<1200){
        System.out.println(5);
      }else if(1200<=n && n<1400){
        System.out.println(4);
      }else if(1400<=n && n<1600){
        System.out.println(3);
      }else if(1600<=n && n<1800){
        System.out.println(2);
      }else if(1800<=n && n<2000){
        System.out.println(1);
      }
	}
}

Measured memory_bytes: 35648
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 922337203685477;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define maxN 200007
using namespace std;
vector<ll>adj[maxN];
vector<bool>vis(maxN, false);
ll c = 0;
ll dfs(ll s) {
  ++c;
  vis[s] = true;
  for (auto i : adj[s]) {
    if (!vis[i])
      dfs(i);
  }
  return c;
}
int main() {
  fastio;
  ll n = 0, m = 0;
  cin >> n >> m;
  for (ll i = 0; i < m; ++i) {
    ll u = 0, v = 0;
    cin >> u >> v;
    --u, --v;
    adj[u].pb(v);
    adj[v].pb(u);
  }
  ll ans = 0;
  for (ll i = 0; i < n; ++i) {
    if (!vis[i]) {
      c = 0;
      dfs(i);
      ans = max(ans, c);
    }
  }
  cout << ans;
}

Measured memory_bytes: 20728
// Example program
#include <iostream>
#include <string>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  if(a==b)cout<<"Draw"<<endl;
  else if(a==1&&b!=1||a!=1&&b!=1&&a>b)cout<<"Alice"<<endl;
  else if(a!=1&&b==1||a!=1&&b!=1&&a<b)cout<<"Bob"<<endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

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

	int n, m;
	cin >> n >> m;
	int sum = 0;

	int a[n];
	for(int i =0; i< n; i++){
		cin >> a[i];
		sum += a[i];
	}
	double z = double(sum)/(4*m);

	sort(a, a+n);
	string ans;

	if(a[n-m] >= z)
		ans = "Yes";
	else
		ans = "No";

	cout << ans << '\n';

	return 0;
}

/*template < typename T >
long long modexp(T a, T b, T p) {
	// returns a to the power b mod p by modular exponentiation

	long long res = 1;
	long long mult = a % p;
	while (b > 0) {
		if (b & 1) {
			res = (res * mult) % p;
		}
		b >>= 1;
		mult = (mult * mult) % p;
	}

	return res;
}*/

/*int primeModInverse(int a, int n) {
	// returns inverse of a mod n by mod exponentiation, use only if n is prime
	return (int) modexp(a, n - 2, n);
}*/

/*template < typename T >
T gcd(T a, T b) {

	if (b == 0) {
		return a;
	}

	return gcd(b, a % b);

}*/


Measured memory_bytes: 3652
#include <iostream>
#include <cstdint>

const int MOD = 1000000007;

using namespace std;

int main() {

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

  int a, b, c;
  cin >> a >> b >> c;
  if (a > b) {
    if (a < c) {
      cout << a + b << endl;
    } else {
      cout << b + c << endl;
    }
  } else if (a == b) {
    if (a <= c) {
      cout << a + b << endl;
    } else {
      cout << c + a << endl;
    }
  } else {
    if (b <= c) {
      cout << a + b << endl;
    } else {
      cout << a + c << endl;
    }
  }
}



Measured memory_bytes: 256
import itertools
n = int(input())

graph = [[-1]*n for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        graph[i][x - 1] = y


def check(_ts):
    _ts = list(_ts)
    ts = list(_ts[:])
    a = [-1] * n
    while ts:
        t = ts.pop()
        for i in range(n):
            if a[i] == -1:
                a[i] = graph[t][i]
                if graph[t][i] == 1:
                    ts.append(i)
                    _ts.append(i)
            if graph[t][i] == -1:
                pass
            elif a[i] != graph[t][i]:
                return False
    for t in _ts:
        if a[t] == 0:
            return False
    return True


for m in range(n, 0, -1):
    for p in itertools.combinations(range(n), r=m):

        if check(p):
            print(m)
            exit()
print(0)


Measured memory_bytes: 56560
#include <iostream>
#include <vector>
#include <map>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

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

    bool fp[N+1];
    vector<int> p;
    fill(fp, fp+N+1, true);
    for(int i=2; i<=N; i++){
        if(!fp[i]) continue;
        p.push_back(i);
        int t = 2*i;
        while(t <= N){
            fp[t] = false;
            t += i;
        }
    }
    

    map<int, int> m;
    for(auto prime : p){
        m[prime] = 0;
        for(int i=2; i<=N; i++){
            int t = i;
            while(t % prime == 0){
                m[prime]++;
                t /= prime;
            }
        }
    }

    long dp[p.size()+1][76];
    for(int i=0; i<p.size()+1; i++){
        for(int j=0; j<=75; j++){
            dp[i][j] = 0;
        }
    }
    dp[0][1] = 1;
    for(int i=0; i<p.size(); i++){
        for(int j=1; j<=75; j++){
            for(int k=0; k<=m[p[i]]; k++){
                if(j*(k+1)>75) continue;
                dp[i+1][j*(k+1)] += dp[i][j];
            }
        }
    }

    cout << dp[p.size()][75] << endl;

    return 0;
}


Measured memory_bytes: 256
void main() {
	auto ip = readAs!(int[]), A = ip[0], B = ip[1];
	if(A==B) {
		writeln("Draw");
		return;
	}
	if(A == 1) {
		writeln("Alice");
	} else if(B == 1) {
		writeln("Bob");
	} else if(A > B) {
		writeln("Alice");
	} else {
		writeln("Bob");
	}
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include<cstdio>
int main()
{
	char ch[5];
	for(int i = 1; i <= 4; i++)
	{
		scanf("%c", &ch[i]);
	}
        if(ch[1] == ch[2] && ch[2] == ch[3] || ch[2] == ch[3] && ch[3] == ch[4])
        {
	       printf("Yes\n");
		}
        else
		{
            printf("No\n");
		}
		return 0;

}





Measured memory_bytes: 128
n = int(input())
if n == 1:
    print(0)
    exit()
ans1 = 1
ans2 = 1
ans3 = 1
for i in range(n):
    ans1 = (ans1*10)%1000000007
    ans2 = (ans2*9)%1000000007
    ans3 = (ans3*8)%1000000007

ans = (ans1 - ans2*2 + ans3)%1000000007

print(ans)

Measured memory_bytes: 9212
n = int(input())
P = [int(i) for i in input().split()]

ans = 0

for i in range(1, n - 1):
    if P[i - 1] <= P[i] <= P[i + 1] or P[i + 1] <= P[i] <= P[i - 1]:
        ans += 1

print(ans)

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

#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

char ch;

int main() {
	scanf("%c", &ch);
	if ('A' <= ch && ch <= 'Z') printf("A\n");
	else printf("a\n");
	return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <cmath>
#include <climits>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
// scanf
#pragma warning(disable: 4996)
// v:vector  type:型  order:greater or less
#define _sort(v,type,order) do { sort(v.begin(),v.end(),order<type>()); } while(0)
// v:vector  default_value:初期値
#define _sum(v,default_value) accumulate(v.begin(),v.end(),default_value )
// 丸め
#define _round(v) round(v)
// 2乗 / 3乗
#define _square(v) pow(v,2)
#define _cube(v)   pow(v,3)
// 大小判定
#define _max(x,y) max(x,y)
#define _min(x,y) min(x,y)
// string ⇒ int
#define _stringtoi(s) stoi(s)
// double 平方根
#define _sqrt(x) sqrt(x)
// double 引数 x 以上で最小の整数値
#define _ceil(x) ceil(x)


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

//	uint32_t temp;
	string temp;
	bool is_found = false;
	for (uint32_t i= 0; i < n; i++) {
		cin >> temp;
		if (temp == "Y") {
			is_found = true;
		}
	}
	if (is_found) {
		printf("Four\n");
	}
	else {
		printf("Three\n");
	}

	return 0;
	//	std::cout << "Hello World!\n"; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (1E9+7)
#define PI 3.1415926535897932384626433832795

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	int a, b,x=100,y=100;
	vector<vector<bool>> m(100,vector<bool>(100, true));
	cin >> b >> a;
	int aa = 1, bb = 1;
	cout << x <<" "<< y << endl;
	rep(i, 50) {
		rep(j, 100) {
			m[i][j] = false;
		}
	}
	while (aa < a) {
		m[((aa * 2 - 1) / 100) * 2][((aa * 2 - 1) % 100)] = true;
		aa++;
	}
	while (bb < b) {
		m[((bb * 2 - 1) / 100) * 2+51][((bb * 2 - 1) % 100)] = false;
		bb++;
	}
	rep(i, 100) {
		rep(j, 100) {
			cout << (m[i][j] ? "#" : ".");
		}
		cout << endl;
	}
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <map>
#include <utility>

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using usize = std::size_t;

using pair = std::pair<i64, i64>;

constexpr i64 MOD = 1000000007;

auto main() -> i32 {
	i32 x, y;
	scanf("%d%d", &x, &y);
	bool ok = false;
	for (i32 i = 0; i <= x; ++i) {
		if (2 * i + 4 * (x - i) == y) {
			ok = true;
			break;
		}
	}
	puts(ok ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 1616
#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

int main(){
    long long n, m, d;
    cin >> n >> m >>d;
    double res;

    if(d == 0){
        res = (double)(m-1)/n;
    }else{
        res = (double)(m-1)*2*(n-d)/ n /n;
    }

    cout << fixed << setprecision(10) << res << endl;
}

Measured memory_bytes: 384
n = int(input())
al = [list(map(lambda x: int(x) - 1, input().split()))[2:] for _ in range(n)]
queue = [0]
d = [-1] * n
d[0] = 0
while len(queue) > 0:
    u = queue.pop(0)
    for v in al[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            queue.append(v)
for i, x in enumerate(d):
    print('{} {}'.format(i + 1, x))




Measured memory_bytes: 5616
#include <stdio.h>
#include <algorithm>
long long p = 1000000007;
long long n, k;
long long ans, s, t;
long long a[100000];
long long c[100000];
long long b[100000];
long long rui(long long rui_a, long long rui_b) {
	if (rui_b == 0)return 1;
	if (rui_b == 1)return rui_a % p;
	long long rui_c;
	rui_c = rui(rui_a, rui_b / 2);
	rui_c = rui_c * rui_c % p;
	if (rui_b % 2) {
		return rui_c * rui_a % p;
	}
	return rui_c;
}
int main() {
	scanf("%lld%lld", &n, &k);
	for (long long i = 0; i < n; i++) {
		scanf("%lld", a + i);
	}
	std::sort(a, a + n);
	b[0] = a[0];
	for (int i = 1; i < n; i++) {
		b[i] = a[i] + b[i - 1];
		b[i] %= p;
	}
	c[0] = 1;
	for (long long i = 1; i < n; i++) {
		c[i] = (c[i - 1] * (k + i - 2) % p) * rui(i, p - 2) % p;
	}
	if (k == 1) {
		printf("0\n");
		return 0;
	}
	for (long long i = 0; i <= n - k; i++) {
		s = b[n - k - i];
		t = b[n - 1] - b[k + i - 2];
		if (t < s)t += p;
		ans += (t - s) * c[i];
		s = 0;
		t = 0;
		ans %= p;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define vi vector<int>
int main()
{
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[i]==a[j])  continue;
            for(int k=j+1;k<n;k++)
            {
                if(a[j]==a[k]|| a[i]==a[k])  continue;
                if(a[i]+a[j]>a[k] && a[j]+a[k]>a[i] && a[k]+a[i]>a[j])
                {    ans++;
                    // cout<<i<<" "<<j<<" "<<k<<endl;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3648
// AOJ 2492: goto busters
// 2018.1.8 bal4u@uu

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

#define HASHSIZ 199
typedef struct { char *s; int n; } HASH;
HASH hash[HASHSIZ+2], *hashend = hash + HASHSIZ;			// Hash table

int lookup(char *s, int w)
{
	int i = (101 * *s + 103 * *(s+w-1) + 107 * w) % HASHSIZ;
	HASH *tp = hash + i;

	while (tp->s != NULL) {
		if (!strcmp(tp->s, s)) return tp->n;
		if (++tp == hashend) tp = hash;
	}
	return -1;
}

void insert(char *s, int w, int n)
{
	int i = (101 * *s + 103 * *(s+w-1) + 107 * w) % HASHSIZ;
	HASH *tp = hash + i;

	while (tp->s != NULL) {
		if (!strcmp(tp->s, s)) return;
		if (++tp == hashend) tp = hash;
	}
	tp->s = s, tp->n = n;
}

#define QMAX 5000
typedef struct { int t, s; } QUE;
QUE que[QMAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
//	if (qsize == 0) return 0;
//	*n = que[0].node, *t = que[0].t, *c = que[0].c;
	que[0] = que[--qsize];
	min_heapify(0);
//	return 1;
}

void enq(int s, int t)
{
	int i, min;
	QUE qt;

	i = qsize++;
	que[i].s = s, que[i].t = t;
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		i = min;
	}
}

char text[101][20], f[101];
char to[101][101], d[101][101], hi[101];
char used[101];

int dijkstra(int start, int goal)
{
	int i, s, t, e;

	t = 0, qsize = 0;
	enq(start, 0);
	while (qsize) {
		s = que[0].s, t = que[0].t, deq();
		if (s == goal) break;
		if (used[s]) continue;
		used[s] = 1;
		for (i = 0; i < hi[s]; i++) {
			e = to[s][i];
			if (used[e]) continue;
			enq(e, t+d[s][i]);
		}
	}
	return t;
}

int main()
{
	int n, i, k;
	char *p, *q;

	fgets(p=text[0], 10, stdin);
	n = atoi(p);
	for (i = 0; i < n; i++) {
		fgets(p=text[i], 20, stdin);
		if (memcmp(p, "goto ", 5) == 0) { f[i] = 1; continue; }
		q = p; while (*p != ':') p++;
		*p = 0, insert(q, p-q, i);
	}
	for (i = 0; i < n; i++) {
		if (!f[i]) to[i][hi[i]++] = i+1;
		else {
			p = q = text[i] + 5;
			while (*p != ';') p++;
			*p = 0, k = lookup(q, p-q);
			to[i][hi[i]++] = k;
			if (k != i+1) to[i][hi[i]] = i+1, d[i][hi[i]++] = 1;
		}
	}
	if (!f[n-1]) to[n-1][hi[n-1]++] = n;

	printf("%d\n", dijkstra(0, n));
	return 0;
}


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

#define LL long long

#define FOR(INDEX, START, END) for (LL INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (LL INDEX = 0; INDEX < (COUNT); ++INDEX)

bool isOK(string const& str, int s, int e) {
	for (int i = s; i < e; ++i) {
		if (str[i] == 'A' || str[i] == 'C' || str[i] == 'G' || str[i] == 'T') {

		}
		else {
			return false;
		}
	}
	return true;
}

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

	int maxLen = 0;
	for (int i = 0; i < s.size(); ++i) {
		for (int k = s.size(); k > i; --k) {
			if (isOK(s, i, k)) {
				maxLen = max(maxLen, k - i);
			}
		}
	}

	cout << maxLen << endl;

	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve() {
	a, b := getInt(), getInt()
	x := getInt()

	untilA := (a-1)/x + 1
	if a == 0 {
		untilA = 0
	}
	untilB := b/x + 1
	ans := untilB - untilA
	fmt.Fprintln(wr, ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func getRunes() []rune {
	return []rune(getString())
}


Measured memory_bytes: 640
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define  mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int a,b,c,d;cin>>a>>b>>c>>d;
    cout<<mmax(a*b,c*d)<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------






Measured memory_bytes: 256
fun main(args: Array<String>) {
    readLine()!!
    val w = readLine()!!.split(" ").map { it.toInt() }
    var tmp = 0
    val s = w.map { tmp+=it; tmp }
    val sum = w.sum()
    val ans = s.map { Math.abs(sum-it*2) }.min()!!
    println(ans)
}


Measured memory_bytes: 38000
def check(k):
    ret = 0
    b = 2 * k - 1
    for j in range(k):
        t = aaa[j] + aaa[b - j]
        if t >= m:
            return -1
        ret = max(ret, t)
    b = 2 * k
    c = 2 * n - 1
    for j in range(n - k):
        t = aaa[b + j] + aaa[c - j]
        if t < m:
            return -2
        ret = max(ret, t - m)
    return ret


n, m = map(int, input().split())
aaa = sorted(map(int, input().split()))

l, r = 0, n
ans = -1
while l < r:
    mid = (l + r) // 2
    res = check(mid)
    if res == -1:
        r = mid
    elif res == -2:
        l = mid + 1
    else:
        ans = res
        r = mid
if ans == -1:
    ans = check(n)
print(ans)


Measured memory_bytes: 27028
#include <cstdio>
#define MODD 1000000007
int c[2005][2005];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	
	int upper;
	if (n - k + 1 > k - 1)
		upper = n - k + 1;
	else
		upper = k - 1;
		
	for (int i = 0; i <= upper; i++) {
		c[i][0] = 1;
	}
	
	for (int i = 1; i <= upper; i++) {
		for (int j = 1; j <= i; j++) {
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MODD;
		}
	}
	
	for (int i = 1; i <= k; i++) {
		printf("%d\n", ((long long) c[n - k + 1][i] * c[k - 1][i - 1]) % MODD);
	}
	
	return 0;
}

Measured memory_bytes: 14976
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    decp(10);
    int n,k;cin>>n>>k;
    double sum=(double)0;
    vector<double> p(n);
    rep(i,n){
        cin>>p[i];
        if(i<k-1)sum+=(p[i]+1)/2;
    }
    int j=0;double M=0;
    rep2(i,k-1,n){
        sum+=(p[i]+1)/2;
        M=max(M,sum);
        sum-=(p[j]+1)/2;
        j++;
    }
    cout<<M<<endl;
}

Measured memory_bytes: 1792
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    costs = [10**9]*(N)
    costs[0] = 0
    for i in range(1,len(costs)):
        for j in range(1,K+1):
            if i - j < 0:
                continue
            costs[i] = min(costs[i],costs[i-j]+abs(h[i]-h[i-j]))
    print(costs[-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


Measured memory_bytes: 53156
import sys
sys.setrecursionlimit(200000)
from collections import Counter, defaultdict
from bisect import bisect_left


def read():
    S = input().strip()
    T = input().strip()
    return S, T


def have_ahswer(S, T):
    cs = Counter(S)
    ct = Counter(T)
    for k in ct.keys():
        if cs[k] == 0:
            return False
    return True


def solve(S, T):
    Z = "abcdefghijklmnopqrstuvwxyz"
    if not have_ahswer(S, T):
        return -1
    D = defaultdict(list)
    for i, s in enumerate(S):
        D[s].append(i)
    ans = 0
    prev_index = -1
    N = len(S)
    for t in T:
        a = D[t]
        i = bisect_left(a, prev_index + 1)
        if i < len(a):
            next_index = a[i]
            ans += next_index - prev_index
        else:
            next_index = a[0]
            ans += N + next_index - prev_index
        prev_index = next_index
    return ans


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Measured memory_bytes: 13896
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<string> name(n);
    for(int i=0; i<n; ++i)
        cin >> name[i];

    string x;
    cin >> x;

    int cnt1 = 0;
    int cnt2 = 0;
    for(int i=0; i<n; ++i){
        string s = name[i];
        string t = name[i];
        for(unsigned j=0; j<s.size(); ++j){
            if(s[j] == '?'){
                s[j] = 'a';
                t[j] = 'z';
            }
        }

        if(t < x)
            ++ cnt1;
        else if(s <= x)
            ++ cnt2;
    }

    vector<int> ans;
    for(int i=0; i<=cnt2; ++i)
        ans.push_back(cnt1 + 1 + i);

    cout << ans[0];
    for(unsigned i=1; i<ans.size(); ++i)
        cout << ' ' << ans[i];
    cout << endl;

    return 0;
}


Measured memory_bytes: 896