akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using P = pair<ll, ll>;

constexpr double PI = 3.14159265358979323846;
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

class ECardCollector {
public:

    vector<P> cost;
    vector<P> pos;

    std::vector<int> par;
    std::vector<int> rak; // number of the vertices
    std::vector<int> rak2;

    void init(int n) {
      par.resize(n);
      rak.resize(n);
      rak2.resize(n);
      for(int i=0; i<n; i++) {
        par[i] = i;
        rak[i] = 1;
      }
    }

    int find(int x) {
      if (par[x] == x) {
        return x;
      } else {
        return par[x] = find(par[x]);
      }
    }

    void unite(int x, int y) {
      x = find(x);
      y = find(y);
      if (x==y) return;
      if (rak[x] < rak[y]) {
        rak[y] += rak[x];
        rak2[y] += rak2[x];
        par[x] = y;
      } else {
        rak[x] += rak[y];
        rak2[x] += rak2[y];
        par[y] = x;
      }
    }

    bool same(int x, int y) {
      return find(x) == find(y);
    }

    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n, h, w; cin >> n >> h >> w;
      rep(i, n) {
        int r, c, a; cin >> r >> c >> a;
        r--; c--;
        pos.emplace_back(r, c);
        cost.emplace_back(a, i);
      }
      init(h+w);

      sort(cost.rbegin(), cost.rend());
      ll ans = 0;
      rep(i, n) {
        int co = cost[i].first;
        int p = cost[i].second;
        int x = pos[p].first;
        int y = pos[p].second;

        unite(x, y+h);
        int pa = find(x);

        if (rak2[pa] < rak[pa]) {
          ans += co;
          rak2[pa]++;
        }
      }
      cout << ans << endl;
    }
};

signed main() {
  ECardCollector solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 5732
#include<iostream>
using namespace std;
int main(){
  int N, AM = 0, count = 0;
  int A[21];
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
    if(AM <= A[i]){
      AM =A[i];
      ++count;
    }
  }
  cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
t,a = map(int,input().split())
H = list(map(int,input().split()))
minitemp = 10*100
for i in range(len(H)):
  H[i] = abs(a-(t-H[i]*0.006))
  minitemp = min(minitemp,H[i])
for j in range(len(H)):
  if H[j] == minitemp:
    print(j+1)
    break



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

#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
const double pi = 3.14159265358979;



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

    string s;
    cin >> s;

    ll n = s.size();

    if (n != 26){
        vector<bool> m(26,false);
        for (ll i = 0;i < n;i++){
            m[s[i] - 'a'] = true;
        }

        for (ll i = 0; i < 26; i++){
            if (!m[i]){
                char x = 'a' + i;
                cout << s << x << endl;
                break;
            }
        }
    }
    else if (s == "zyxwvutsrqponmlkjihgfedcba"){
        cout << -1 << endl;
    }
    else{
        vector<bool> m(26,false);
        ll c = 0;
        ll j = 0;
        for (ll i = 25; i >= 1; i--){
            if (s[i] < s[i-1]){
                m[s[i] - 'a'] = true;
            }
            else{
                m[s[i] - 'a'] = true;
                m[s[i-1] - 'a'] = true;
                c = s[i-1] - 'a';
                j = i-1;
                //cout << c << endl;
                //cout << j << endl;
                break;
            }
        }

        /*for (ll i = 0; i < 26; i++){
            if (m[i]){
                cout << i << endl;
            }
        }
        char x = s[c];
        cout << x << endl;*/

        for (ll i = c+1; i < 26; i++){
            if (m[i]){
                s[j] = 'a' + i;
                //cout << s[c] << endl; 
                break;
            }
        }
        
        for (ll i = 0; i <= j; i++){
            cout << s[i];
        }
        cout << endl;
    }
}

Measured memory_bytes: 3640
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
left = [0]*n
right = [0]*n
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i-1])
    right[-1-i] = gcd(right[-i],a[-i])
gcds = []
for i in range(n):
    gcds.append(gcd(left[i],right[i]))
print(max(gcds))

Measured memory_bytes: 16136
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main(){
  ll x;
  ll ans = 100;
  cin >> x;
  ll count=0;
  rep(i,x){
    if(x<=ans){
      cout <<count << endl;
      return 0;
    }
    ans = floor(ans*1.01);
    count++;
  }
  return -1;
}

Measured memory_bytes: 3744
def dfs(sum_v, index)
  ANS[index] = sum_v
  CHECK[index] = true
  n = G[index].size
  n.times do |i|
    unless CHECK[G[index][i]]
      dfs(sum_v + SUM[G[index][i]], G[index][i])
    end
  end
end

N,Q = gets.split.map(&:to_i)
ab = (N-1).times.map{gets.split.map(&:to_i)}
px = Q.times.map{gets.split.map(&:to_i)}

G = Array.new(N){[]}
ab.each do |a, b|
  G[a-1] << b-1
  G[b-1] << a-1
end

SUM = Array.new(N, 0)
px.each do |p, x|
  SUM[p-1] += x
end

ANS = Array.new(N, 0)
CHECK = Array.new(N, false)
dfs(SUM[0], 0)

puts ANS.join(' ')


Measured memory_bytes: 293420
n = gets.to_i
i = 1
ans = 100
loop {
    break if i * i > n
    if n % i != 0
        i += 1
        next
    end
    ans = [ans, [i.to_s.size, (n / i).to_s.size].max].min
    i += 1
    }
p ans

Measured memory_bytes: 1788
function Main(input) {
    input = input.split("\n");
    var line = input[0].split(" ");
    var aa = input[0];
    var bb = input[1];
    var cc = input[2];
    var count = [0,0,0];
    var limit = [aa.length,bb.length,cc.length];
    var current = "a";
    var tes = 0
    while(1){
        if(current==="a"){
            if(count[0]>=limit[0]){
                console.log("A");
                break;
            }
            current = aa[count[0]];
            count[0]++;
        } else if (current==="b"){
            if(count[1]>=limit[1]){
                console.log("B");
                break;
            }
            current = bb[count[1]];
            count[1]++;
        } else if (current==="c"){
            if(count[2]>=limit[2]){
                console.log("C");
                break;
            }
            current = cc[count[2]];
            count[2]++;
        }

    }
 
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

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

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
//最初に設定する.
ll MOD=998244353;
const int  MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];  void modcinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } long long modc(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; }
int main( ){
    modcinit();
    ll N,M;
    ll K;
    cin>>N>>M>>K;
    ll ans=0;
    rep(i,0,K+1){
       ll add=((M*modc(N-1,i)%MOD+MOD)%MOD*modpow(M-1,N-1-i,MOD)%MOD+MOD)%MOD;
       ans=((add+ans)%MOD+MOD)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 15560
#include <iostream>
using namespace std;
int n, a[10];

bool dfs(int b, int c, int cnt) {
	bool ans = false;
	if (cnt == 10) {
		return true;
	}
	if (b < a[cnt]) {
		ans = dfs(a[cnt], c, cnt + 1);
	}
	if (c < a[cnt]) {
		ans = dfs(b, a[cnt], cnt + 1);
	}
	return ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) cin >> a[j];
		if (dfs(0, 0, 0)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

Measured memory_bytes: 3000
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

int a[2000000];
int b[2000000];

void Counting_Sort(int k) {
	int i, j;
	int C[10001];
	for (i = 0; i<10001; i++)C[i] = 0;
	for (j = 0; j<k; j++)C[a[j]]++;
	for (i = 1; i<10001; i++)C[i] += C[i - 1];
	for (j = k - 1; j >= 0; j--) {
		C[a[j]]--;
		b[C[a[j]]] = a[j];
	}
}

int main() {
	int n, i;

	cin >> n;
	for (i = 0; i<n; i++)cin>>a[i];
	Counting_Sort(n);
	for (i = 0; i<n; i++) {
		if (i)cout << " ";
		cout<<b[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 18748
#include <stdio.h>
int main(){
  int N,i,j,v,k;
  scanf("%d", &N);
  int A[N];
  for(i=0; i<N; i++){
    scanf("%d",&A[i]);
  }
   for(k=0; k<N; k++){
      printf("%d",A[k]);
      if ( k != N - 1)printf(" ");
    }
  if (i != N -1)printf("\n",N); 
  for(i=1; i<N; i++){
    v = A[i];
    j = i-1;
    while (j >= 0 && A[j] > v){
      A[j+1] = A[j];
      j--;
      A[j+1] = v;
    }
    for(k=0; k<N; k++){
      printf("%d",A[k]);
      if ( k != N - 1)printf(" ");
    }
printf("\n",N);
  }
  return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)

const ll mod = (ll)1e9+7;
const ll maxn = (ll)2e5+5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = 1e18;

ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};

ll sum(ll n){
	n--;
	if(n <= 0) return 0;
	return ((n)*(n+1))/2;
}

void solve(){
	
	ll n , k;
	cin >> n >> k;
	ll ans = 0;
	k--;
	for(ll i = k; i <= n; i++){
		ans += (sum(n+1)-sum((n-i)) - sum(i+1))+1;
		//cout << (sum(n+1)-sum(n-i)) << ' ' << sum(i+1) << ' ' << i << '\n';
		ans %= mod;
	}
	cout << ans;
	return;
}


int main() {
   
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    ll T;
    T=1;
   // cin >> T;
    //scanf("%lld",&T);
    ll CT = 0;
    //work();
    while(T--){
    	//cout << "Case " << ++CT <<": " ;
    	//printf("Case %lld: ",++CT);
		solve();
	}
    
    return 0;
}


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

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	vector<int> a(n);
	for(int& x:a) cin>>x;
	sort(a.begin(),a.end());
	cout<<a[n-1]-a[0]<<'\n';
}




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

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
        a = 14;
    }
    if (b == 1) {
        b = 14;
    }
    if (a > b) {
        cout << "Alice" << endl;
    } else if (a == b) {
        cout << "Draw" << endl;
    } else {
        cout << "Bob" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
x = list(map(int, input().split()))
if x[0] + x[1] <= x[2] * 2:
    cost = x[0] * x[3] + x[1] * x[4]
else:
    if x[3] > x[4]:
        a = x[3] - x[4]
        b = 0
        ab = x[4] * 2
        if x[0] >= x[2] * 2:
            a = 0
            b = 0
            ab = x[3] * 2
    else:
        a = 0
        b = x[4] - x[3]
        ab = x[3] * 2
        if x[1] >= x[2] * 2:
            a = 0
            b = 0
            ab = x[4] * 2
    cost = x[0] * a + x[1] * b + x[2] * ab
print(cost)

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
public static void main(String[] args){
try(Scanner sc = new Scanner(System.in)){
String line = sc.nextLine();
String answer = "";
int length = line.length();
for(int i = 0; i<length; i++){
char ch = line.charAt(i);
if(Character.isLowerCase(ch)){
ch = Character.toUpperCase(ch);
}else{
ch = Character.toLowerCase(ch);
}
System.out.printf("%c", ch);
}
System.out.println(answer);
}
}
}


Measured memory_bytes: 29540
#include <bits/stdc++.h>
typedef long long ll;
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using namespace std;

//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------


int main() {
    int k;
    cin>>k;
    if(k>=30)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  
}



Measured memory_bytes: 3620
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	string s;
	cin>>s;
	int n=s.size();
	for(int i=1;i<=n;i++){
		cout<<'x';
	} 
	return 0;
}
//xxxxxxx


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int K = sc.nextInt();
        int X = sc.nextInt();

        if (K * 500 >= X) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int n, k;
  cin >> n >> k;
  vector< tuple< int, int > > p(n);
  for (int i=0; i<n; ++i) {
    int xi, yi;
    cin >> xi >> yi;
    p[i] = make_tuple(xi, yi);
  }
  sort(p.begin(), p.end());
  ll ans = 0;
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) {
      ll yi=get<1>(p[i]);
      ll yj = get<1>(p[j]);
      if (yi>yj) continue;
      int cnt = 0;
      ll ii=0, jj=0;
      if (yi <= get<1>(p[jj]) && get<1>(p[jj]) <= yj) cnt++;
      while (jj < n) {
	if (cnt < k) {
	  jj++;
	  if (yi <= get<1>(p[jj]) && get<1>(p[jj]) <= yj) cnt++;
	} else {
	  if (ans == 0) ans = (yj-yi) * (get<0>(p[jj])-get<0>(p[ii]));
	  else ans = min(ans, (yj-yi) * (get<0>(p[jj])-get<0>(p[ii])));
	  if (yi <= get<1>(p[ii]) && get<1>(p[ii]) <= yj) cnt--;
	  ii++;
	}
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const ll mod = 1e9+7;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

vector<string> Split(const string& s,const string d){
  string item(s);
  vector<string> res(0);
  for(auto pos = item.find(d); pos != string::npos; pos = item.find(d,pos)){
    item.replace(pos,d.size()," ");
  }
  stringstream buf(item);
  while(buf >> item){
    res.push_back(item);
  }
  return res;
}
template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  ll ans = 0;
  for(int i = 0; i < (1 << s.size()-1);++i){
    string t = "";
    rep(j,s.size()){
      t += s[j];
      if(i & (1 << j)) t += "+";
    }
    auto r = Split(t,"+");
    rep(j,r.size()){
      ans += ston(r[j],0LL);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <numeric>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

typedef unsigned long long ull;

int main()
{
  int ans = 0;
  string str;
  cin>>str;
  
  REP(i, str.size()) ans += str[i] == '+' ? 1 : -1;

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

//find_by_order gives kth-largest element
//order_of_key gives the number of items in the set that are strictly smaller!!

// OT.find_by_order(k-1)
// 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define db4(x, y, z, w) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << "," << #w << "=" << w << endl
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define X first
#define Y second
#define sz(x) (int)((x).size())
#define pii pair<int,int>
#define MOD (ll)(1e9 + 7)
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
typedef vector<int> vi;
#define inf (ll)(1e18)
#define double long double
#define int long long

//////////////////////

int32_t main() {

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

    map<array<int,26>,int> M;
    int n;
    cin >> n;

    string st;
    rep(i,n) {
        cin >> st;
        array<int, 26> arr;
        rep(j,26) arr[j] = 0;
        rep(j,sz(st)) {
            arr[st[j] - 'a']++;
        }

        M[arr]++;
    }

    int total = 0;
    trav(i,M) {
        total += (i.Y * (i.Y - 1)) / 2;
    }

    cout << total << '\n';
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
const int Maxn=505;
int edge[Maxn][Maxn],ct,n;
void solve(int lt,int rt,int ct)
{
	if(lt==rt) return ;
	int mid=(lt+rt)/2;
	for(int i=lt;i<=mid;i++)
		for(int j=mid+1;j<=rt;j++)
			edge[i][j]=ct;
	solve(lt,mid,ct+1),solve(mid+1,rt,ct+1);
}
int main()
{
	scanf("%d",&n);
	solve(1,n,1);
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
			printf("%d ",edge[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1408
loop = gets.to_i
loop.times do
    x1, y1, x2, y2, x3, y3 = gets.split.map(&:to_f)
    
    a = ((x2 - x1)**2 + (y2 - y1)**2) ** (1/2.0)
    b = ((x3 - x2)**2 + (y3 - y2)**2) ** (1/2.0)
    c = ((x1 - x3)**2 + (y1 - y3)**2) ** (1/2.0)
    
    s = (a + b + c) / 2
    r = (a * b * c) / (((s * (s - a) * (s - b) * (s - c)) ** ( 1 / 2.0)) * 4)
    
    a1 = 2*(x2 - x1)
    b1 = 2*(y2 - y1)
    c1 = x1**2 - x2**2 + y1**2 - y2**2
    a2 = 2*(x3 - x1)
    b2 = 2*(y3 - y1)
    c2 = x1**2 - x3**2 + y1**2 - y3**2
     
    x = (b1*c2 - b2*c1) / (a1*b2 - a2*b1)
    y = (c1*a2 - c2*a1) / (a1*b2 - a2*b1)
    
    printf "%.3f %.3f %.3f\n", x, y, r
end


Measured memory_bytes: 6964
#include<stdio.h>
int main(){
	int a,b,c,d,s;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(a-b>0)s=a*c-(c-d)*(a-b);
	else s=a*c;
	printf("%d\n",s);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main(){fastio
    ll n;cin>>n;
    ll a[3*n+1];rep(i,1,3*n)cin>>a[i];
    ll b[3*n+1];rep(i,1,3*n)b[i]=a[3*n+1-i];
    ll dp[3*n+1],ep[3*n+1];
    
    ll sum=0;
    multiset<ll> st;
    rep(i,1,n){
        sum+=a[i];
        st.insert(a[i]);
    }
    dp[n]=sum;
    rep(i,n+1,n*2){
        if((ll)*st.begin()<a[i]){
            sum-=*st.begin();
            st.erase(st.begin());
            sum+=a[i];
            st.insert(a[i]);
            dp[i]=sum;
        }else{
            dp[i]=sum;
        }
    }
    
    sum=0;
    st.clear();
    rep(i,1,n){
        sum+=b[i];
        st.insert(b[i]);
    }
    ep[n]=sum;
    rep(i,n+1,n*2){
        auto itr=st.end();
        --itr;
        if((ll)*itr>b[i]){
            sum-=*itr;
            st.erase(itr);
            sum+=b[i];
            st.insert(b[i]);
            ep[i]=sum;
        }else{
            ep[i]=sum;
        }
    }
    ll maxi=-inf;
    rep(i,n,n*2){
        maxi=max(maxi,dp[i]-ep[3*n-i]);
    }
    /*
    rep(i,n,n*2){
        cout<<dp[i]<<' '<<ep[i]<<endl;
    }*/
    cout<<maxi<<endl;
    
    return 0;
}





Measured memory_bytes: 14520
<?php
  
$n = trim(fgets(STDIN));
$a = explode(' ', trim(fgets(STDIN)));
$b = explode(' ', trim(fgets(STDIN)));
$c = explode(' ', trim(fgets(STDIN)));

$s = $b[$a[0]-1];
for($i=1; $i<$n; $i++){
  $s += $b[$a[$i]-1];
  if ($a[$i]-$a[$i-1] == 1) $s += $c[$a[$i-1]-1];
}

echo $s;

?>

Measured memory_bytes: 4604
Uses math;
var
	n,i:Longint;
	a:array[1..200000]of Longint;
	s:array[0..200000]of int64;
	reta,retb,x,y,z,w,ans:int64;
procedure f(L,R:Longint);
var
	sum,c,d,e,f:int64;
	ll,rr,mm,k:Longint;
begin
	sum:=(s[R]+s[L])div 2;
	ll:=L;
	rr:=R-1;
	while rr-ll>1 do begin
		mm:=(ll+rr)div 2;
		if s[mm]>sum then rr:=mm else ll:=mm;
	end;
	k:=rr;
	c:=s[k]-s[L];
	d:=s[R]-s[k];
	dec(k);
	if k>L then begin
		e:=s[k]-s[L];
		f:=s[R]-s[k];
		if Max(c,d)-Min(c,d)>Max(e,f)-Min(e,f)then begin
			reta:=Min(e,f);
			retb:=Max(e,f);
			exit;
		end;
	end;
	reta:=Min(c,d);
	retb:=Max(c,d);
end;
begin
	read(n);
	for i:=1 to n do begin
		read(a[i]);
		s[i]:=s[i-1]+a[i];
	end;
	ans:=s[n];
	for i:=2 to n-2 do begin
		f(0,i);
		x:=reta;
		z:=retb;
		f(i,n);
		y:=reta;
		w:=retb;
		ans:=Min(ans,Max(z,w)-Min(x,y));
	end;
	writeln(ans);
end.


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

string inverse(string s){
  string s_inverse = "";
  for(int i = s.size()-1; i >= 0; i--){
    s_inverse += s[i];
  }
  return s_inverse;
}

int main(){
  string S;
  int Q;
  cin >> S;
  cin >> Q;
  
  int t, f;
  char c;
  string left_s = "";
  string right_s = "";
  
  bool flag = true;
  
  for(int i = 0; i < Q; i++){
    cin >> t;
    if(t == 1){
      flag = !flag;
    }
    else if(t == 2){
      cin >> f >> c;
      if(flag){
        if(f == 1)
          left_s += c;
        else if(f == 2)
          right_s += c;
      }
      else if(!flag){
        if(f == 2)
          left_s += c;
        else if(f == 1)
          right_s += c;
      }
    }
  }
  
  if(flag){
    S = inverse(left_s) + S + right_s;
  }
  else{
    S = inverse(right_s) + inverse(S) + left_s;
  }
  
  cout << S << endl;
  
  return 0;
}

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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Po pop_back
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

LL dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
LL dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

///**************************DONE****************************///

int main()
{
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

    LL n, m;
    cin >> n >> m;

    if(n - m)
        cout << "No\n";
    else
        cout << "Yes\n";
    return 0;
}




Measured memory_bytes: 256
def solve(n, a_list):
    search = 1
    for i in range(n):
        if a_list[i] == search:
            search += 1
    if search == 1:
        return -1
    else:
        return n - search + 1


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(3, [2, 1, 2]) == 1
    assert solve(3, [2, 2, 2]) == -1
    assert solve(10, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]) == 7
    assert solve(1, [1]) == 0


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 26140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;
const int maxs = 6001;

ll n;
//{x,y}:ノードxに銀貨y枚を持っている
P i2p(ll i){
    return {i%n,i/n};
}
ll p2i(P p){
    return p.first+p.second*n;
}
struct edge{ll to, cost;};
vector<vector<edge>> G;
vector<ll> d;
ll V;
void dijkstra(ll s){
    priority_queue<P,vector<P>,greater<P>> que;
    d = vector<ll>(V,INF);
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty()){
        P p = que.top();que.pop();
        ll v = p.second;
        if(d[v]<p.first)continue;
        for(edge e:G[v]){
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //
    ll m,s;cin>>n>>m>>s;
    s=min(s,5000LL);
    V=n*maxs;
    G = vector<vector<edge>>(n*maxs);
    rep(i,m){
        ll u,v,a,b;cin>>u>>v>>a>>b;
        u--;v--;
        for(int j=a; j<maxs; j++){
            G[p2i({u,j})].push_back({p2i({v,j-a}),b});
            G[p2i({v,j})].push_back({p2i({u,j-a}),b});
        }
    }
    rep(i,n){
        ll c,d;cin>>c>>d;
        for(int j=0; j<maxs-c; j++){
            G[p2i({i,j})].push_back({p2i({i,j+c}),d});
        }
    }
    dijkstra(p2i({0,s}));
    for(int i=1; i<n; i++){

        ll ans = INF;
        for(int j=0; j<maxs; j++){
            ans = min(ans,d[p2i({i,j})]);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

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

#define  __  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  int  long long
#define  endl  '\n'
const double pi = acos(-1);
const int mod = 1e9 + 7;
//______________________



int32_t main()
{ 
  __
 
  
  
  int n,k;

  double cur=0,sum=0.0;

  cin>>n>>k;

  double base = 1.0/(double)n;

  for(int i=1;i<=n;i++)
  {
    int j=i,times=0;
    if(i>=k)
    {
        sum += base;
        continue;
    }
    while(j<k)
    {
        j <<= 1;
        times++;
    }

    double p = pow(double(0.5),times);
    sum+= (base * p);
  }

  cout<<setprecision(12)<<sum;
 

 return 0;
}

Measured memory_bytes: 256
use proconio::input;
use std::cmp::*;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};

const MAX_SCORE: i64 = 10000*1000000i64*15+1;



#[allow(dead_code)]

//#[proconio::fastout]
fn main() {
    input! {
        n:usize,
        v:[(i32,i32,i64);n],
    }

    let mut distx = vec![vec![0;n];1<<n]; // distx[j][i] : ビットパターンj の線路が南北に引いてあるときに、集落iの人がx方向に移動して線路に到達するまでの距離
    let mut disty = vec![vec![0;n];1<<n];
    for i in 0..n {
        distx[0][i] = v[i].0.abs();
        disty[0][i] = v[i].1.abs();
    }

    for j in 1..1<<n {
        // ビットパターンjの、最も下の1になっているビットを探す
        let mut k = 1;
        let mut m = 0;
        while j & k == 0 {
            k <<= 1;
            m += 1;
        }

        for i in 0..n {
            distx[j][i] = min(distx[j^k][i], (v[m].0-v[i].0).abs());
        }
        for i in 0..n {
            disty[j][i] = min(disty[j^k][i], (v[m].1-v[i].1).abs());
        }
    }

    let mut score = vec![MAX_SCORE;n+1];
    let mut jx = 0;
    let mut jy = 0;
    let max_t = 1<<n;
    loop {
        let mut num_rail = 0;
        for i in 0..n {
            if (1<<i) & (jx|jy) != 0 {
                num_rail += 1;
            }
        }
        
        let mut s = 0;
        for i in 0..n {
            s += min(distx[jx][i], disty[jy][i]) as i64 * v[i].2;
        }
        score[num_rail] = min( score[num_rail], s );
        
        // 3進数(jx&jy=0)で1を足す
        //println!("{} {} {}", jx, jy, jx&jy );

        let b = (jy+1) ^ (jy & (jy+1)); // jyに1を足してどこまで繰り上がるか
        jy += 1;
        if b == max_t {
            break;
        }
        if jx & b == 0 {
            jx |= b;
            jy &= !b;
        } else {
            jx &= !b;
        }
    }

    for i in 0..=n {
        println!("{}", score[i] );
    }

}


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

#define int long long

int32_t main() {
	// your code goes here
	int n;
	cin>>n;
	vector< vector<int> > h(n, vector<int> (3));
	for(int i=0; i<n; i++){
	    for(int j=0; j<3; j++)cin>>h[i][j];
	}
	vector< vector<int> > dp(3, vector<int> (n));
	for(int j=0; j<3; j++)dp[j][0]=h[0][j];
	for(int i=1; i<n; i++){
	    dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + h[i][0];
	    dp[1][i] = max(dp[0][i-1], dp[2][i-1]) + h[i][1];
	    dp[2][i] = max(dp[0][i-1], dp[1][i-1]) + h[i][2];
	}
	cout<<max({dp[0][n-1], dp[1][n-1], dp[2][n-1]});
	return 0;
}


Measured memory_bytes: 8832
#include<iostream>

using namespace std;

int map[11][10001],turn[11],r,c,ans;

void serch(int n)
{
	int i,j;
	if(n==r)
	{
		int ss,ssans=0;
		for(i=0;i<c;i++)
		{
			ss=0;
			for(j=0;j<r;j++)
			{
				if(turn[j]==0)
				{
					if(map[j][i]==1)
						ss++;
				}
				else if(turn[j]==1)
				{
					if(map[j][i]==0)
						ss++;
				}
			}
			if(ss<=r/2)
				ssans+=r-ss;
			else
				ssans+=ss;
		}
		if(ans<ssans)
			ans=ssans;
		return ;
	}
	turn[n]=0;
	serch(n+1);
	turn[n]=1;
	serch(n+1);
	return ;
}
int main()
{
	int i,j;
	
	for(;;)
	{
		cin >> r >> c ;
		if(r==0 && c==0)
			break;
		
		for(i=0;i<r;i++)
			for(j=0;j<c;j++)
				cin >> map[i][j] ;
		
		ans=0;
		
		serch(0);
		
		cout << ans << endl;
	}
}

Measured memory_bytes: 1256
--[[
sig{(x_i - c)^2}
= sig{x_i^2} -2c * sig{x_i} + nc^2
c = sig{x_i} / n
]]
local n = io.read("*n")
local sum = 0
local sumsq = 0
for i = 1, n do
  local a = io.read("*n")
  sum = sum + a
  sumsq = sumsq + a * a
end
local cmin, cmax = math.floor(sum / n), math.ceil(sum / n)
print(math.min(sumsq - 2 * cmin * sum + n * cmin * cmin, sumsq - 2 * cmax * sum + n * cmax * cmax))


Measured memory_bytes: 1008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);

int main(){
	ll H,A;
	cin >> H >> A;

	ll ans = (H+A-1)/A;
	cout << ans << endl;

}


Measured memory_bytes: 256
import sys
n = int(input())
s = [int(input())for S in range(n)]
ans = sum(s)
box = []
if ans%10 != 0:
	print(ans)
	sys.exit()
for i in range(n):
	if (ans-s[i])%10 != 0:
		box.append(ans-s[i])
if len(box) > 0:
	print(max(box))
else:
	print(0)

Measured memory_bytes: 8940
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
using namespace std;


int main() {
    
    ll n;
    cin>>n;
    
    cout<<n * (n-1)/2<<endl;
    return 0;
}


Measured memory_bytes: 256
from bisect import bisect
from collections import defaultdict


class Bit:
    def __init__(self, n, MOD):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
        self.mod = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s % self.mod

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % self.mod
            i += i & -i

    def debug_print(self):
        for i in range(1, self.size + 1):
            j = (i & -i).bit_length()
            print('  ' * j, self.tree[i])

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


n, m = map(int, input().split())
xxx = list(map(int, input().split()))
yyy = list(map(int, input().split()))
ab = defaultdict(set)
coordinates = set()

for x in xxx:
    if x < yyy[0] or yyy[-1] < x:
        continue
    i = bisect(yyy, x)
    a = x - yyy[i - 1]
    b = yyy[i] - x
    ab[a].add(b)
    coordinates.add(b)

# Bitのindexは1から始まるように作っているが、"0"を取れるようにするため、全体を1ずらす
cor_dict = {b: i for i, b in enumerate(sorted(coordinates), start=2)}
cdg = cor_dict.get
MOD = 10 ** 9 + 7
bit = Bit(len(coordinates) + 1, MOD)
bit.add(1, 1)

for a in sorted(ab):
    bbb = sorted(map(cdg, ab[a]), reverse=True)
    for b in bbb:
        bit.add(b, bit.sum(b - 1))

print(bit.sum(bit.size))


Measured memory_bytes: 61768
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

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

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

//////////////////////////////////////


int main() {
	ll N;
	cin >> N;
	vector<ll> V(N + 1), W(N + 1);
	repn(i, N) cin >> V[i] >> W[i];

	ll M = min(1000,N);
	ll K = 100000;

	vvll dp(M + 1, vll(K + 1, 0));

	repn(i, M) {
		rep(j, K+1) {
			dp[i][j] = dp[i / 2][j];
			if (j >= W[i]) { dp[i][j] = max(dp[i][j], dp[i / 2][j - W[i]] + V[i]); }
		}
	}

	ll Q;
	cin >> Q;
	repn(q, Q) {
		ll v, l;
		cin >> v >> l;

		if (v <= M) {
			cout << dp[v][l] << endl; continue;
		}

		vll wei, val;
		ll ori = v;
		for (ll i = v; i > M; i /= 2) {
			val.push_back(V[i]);
			wei.push_back(W[i]);
			ori = i;
		}

		ll S = val.size();
		ll ans = 0;

		rep(i, 1 << S) {
			ll nowv = 0;
			ll noww = 0;
			
			rep(j, S) {
				if ((i >> j) & 1) { noww += wei[j]; nowv += val[j]; }
			}

			if (noww > l) { continue; }
			nowv += dp[ori / 2][l - noww];
			ans = max(ans, nowv);
		}

		cout << ans << endl;
	}
}

Measured memory_bytes: 792880
#include <cstdio>
#include <algorithm>

const int MAXN = 1e5 + 5;

template<typename _T>
void read( _T &x )
{
	x = 0; char s = getchar(); int f = 1;
	while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + s - '0', s = getchar(); }
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ) { putchar( '-' ), x = -x; }
	if( 9 < x ) write( x / 10 );
	putchar( x % 10 + '0' );
}

int a[MAXN];
int N;

bool cmp( const int &a, const int &b ) { return a > b; }

int main()
{
	read( N );
	for( int i = 1 ; i <= N ; i ++ ) read( a[i] );
	std :: sort( a + 1, a + 1 + N, cmp );
	int fir = 1;
	for( ; fir <= N && fir + 1 <= a[fir + 1] ; fir ++ );
	bool up = ( a[fir] - fir + 1 ) & 1, rig = true;
	for( int i = fir + 1 ; i <= N && a[i] >= fir ; i ++, rig ^= 1 );
	bool tag = ! ( up & rig );
	puts( tag ? "First" : "Second" );
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<stack>

#define INF (1 << 21)

int main() {
	int node_num;

	std::cin >> node_num;
	std::vector<std::vector<int> > node(node_num, std::vector<int>(node_num, -1));

	for (size_t i = 0; i < node.size(); i++) {
		int out, node_number;
		std::cin >> node_number >> out;
		for (int j = 0; j < out; j++) {
			int to, distance;
			std::cin >> to >> distance;
			node[node_number][to] = distance;
		}
	}

	std::vector<int> distance(node.size(), INF);
	std::stack<int> s;
	distance[0] = 0;

	s.push(0);
	while(!s.empty()) {
		int node_number = s.top(); s.pop();
		for (size_t j = 0; j < node[node_number].size(); j++) {
			if (node[node_number][j] != -1 && node[node_number][j] + distance[node_number] < distance[j]) {
				distance[j] = node[node_number][j] + distance[node_number];
				s.push(j);
			}
		}
	}

	for (size_t i = 0; i < distance.size(); i++) {
		std::cout << i << " " << distance[i] << std::endl;
	}
}

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

#define int long long

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


signed main(void) {
  int num; // num
  num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  int N;
  int M;
  array<int, 100000> A;;
  // string S;
  // string T;

  int X, Y;

  cin >> N >> M >> X >> Y;

  int XM, Ym;

  for (int i = 0; i < N; ++i) {
    int x;
    cin >> x;    
    if (i == 0) XM = x;
    else XM = max(XM, x);
  }

  for (int i = 0; i < M; ++i) {
    int y;
    cin >> y;
    if (i == 0) Ym = y;
    else Ym = min(Ym, y);
  }

  bool flag = false;
  if (XM <= Ym) {
    for (int i = XM + 1; i <= Ym; ++i) {
      if (i > Ym) break;
      if (X < i && i <= Y) flag = true;
    }
  }

  if (flag) cout << "No War" << endl;
  else cout << "War" << endl;
  
  
  // cin >> N;
  // for (auto it = A.begin(); it < A.begin() + N; ++it) cin >> *it;

  // for (auto it = A.begin(); it < A.begin() + N; ++it) if (*it % 2 == 0) ++num;

  // cout << num << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for (ll i = m; i < (n); i++)
#define RFOR(i, m, n) for (ll i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << (ele) << "\n"
#define print10(ele) cout << fixed << setprecision(10) << (ele) << "\n"

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  double l;
  cin >> l;
  double ans = pow(l / 3, 3);
  // FOR(x, 1, l) {
  //   FOR(y, x, l) {
  //     int z = l - x - y;
  //     ll s = x * y * z;
  //     ans = max(ans, s);
  //   }
  // }
  // if (l == 1) {
  //   print10(pow(0.333333333333, 3));
  //   return 0;
  // } else if (l == 2) {
  //   print10(pow(0.666666666667, 3));
  //   return 0;
  // }
  print10(ans);
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define SpeeD ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ll long long
int main() {
	long double  a, b, c;
cin>>a>>b>>c;
	if (a + b+2*sqrt(a)*sqrt(b) < c)cout << "Yes";
	else cout << "No";
}
    

Measured memory_bytes: 256