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

using namespace std;

/*helpfull*/
using vl  = vector<long long>;
using vpl = vector<pair<long long, long long>>;
using vs = vector<string>;
using pl  = pair<long long, long long>;
using ll  = long long int;
using vb  = vector<bool>;


struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1> {}(p.first);
        auto hash2 = hash<T2> {}(p.second);
        return hash1 ^ hash2;
    }
};
// #ifndef ONLINE_JUDGE
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
// #endif

// shortcut macros
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mp              make_pair
#define fi              first
#define se              second
// #define mt              make_tuple
#define pb              push_back
#define all(x)          (x).begin(), (x).end()
#define ini(a, v)       memset(a, v, sizeof(a))
#define rep(i, a, n)    for(ll i=a ; i<n ; ++i)
#define For(i, n)       rep(i, 0, n)
#define sz(x)           (int((x).size()))
#define ump(x,y)        unordered_map<x,y>
#define umpr(x,y,z)     unordered_map<x,y,z>
void printcase(ll &x) {
    cout << "Case #" << x << ": ";
}
void read(vector<ll>&v, ll &n) {
    For(i, n)
    cin >> v[i];
}
void read(ll &x) {
    cin >> x;
}
void read(string &s) {
    cin >> s;
}
void read(int &x) {
    cin >> x;
}
void read(ll a[], ll &n) {
    For(i, n)
    cin >> a[i];
}
void print() {
    cout << endl;
}
void write(vector<ll>&v, ll &n) {
    For(i, n)
    cout << v[i] << " ";
    cout << endl;
}
void write(vector<ll>&v) {
    ll n = v.size();
    For(i, n)
    cout << v[i] << " ";
    cout << endl;
}
void write(ll x) {
    cout << x << endl;
}
void write(string &s) {
    cout << s << endl;
}
void write(int &x) {
    cout << x << endl;
}
void write(ll a[], ll &n) {
    For(i, n)
    cout << a[i] << " ";
    cout << endl;
}
const ll mod = 1e9 + 7;


ll count_path(ll x, ll y, ll &n, ll &m, vector<string> &v, vector<vector<ll>> &memo) {
    if (memo[x][y] != -1)
        return memo[x][y] % mod;
    if (x == n - 1 && y == m - 1)
        memo[x][y] = 1;
    else if (x >= n || y >= m)
        memo[x][y] = 0;
    else if (v[x][y] == '#')
        memo[x][y] = 0;
    else
        memo[x][y] = (count_path(x + 1, y, n, m, v, memo) % mod + count_path(x, y + 1, n, m, v, memo) % mod) % mod;

    return memo[x][y] % mod;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS;
    ll n , m;
    cin >> n >> m;
    vector<string> v(n);
    For(i, n)
    cin >> v[i];

    vector<vector<ll>> memo(n + 1, vector<ll>(m + 1, -1));
    write(count_path(0, 0, n, m, v, memo));
    return 0;
}




Measured memory_bytes: 12356
#include <stdio.h>
int main(){
  int N, Q, i, j ,l ,r;
  scanf("%d %d", &N, &Q);
  int acnum[N];
  char S[N];
  scanf("%s",S);
  acnum[0]=0;
  for(i=1; i<N; i++){
    if(S[i] == 'C' && S[i-1] == 'A') {
        acnum[i]=acnum[i-1]+1;
    }else{
        acnum[i]=acnum[i-1];
    }
  }
  for(i=0; i<Q; i++){
    scanf("%d %d", &l, &r);
    printf("%d\n", acnum[r-1] - acnum[l-1]);
  }
  
}

Measured memory_bytes: 1280
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<set>
#define inf 1000000000
#define N 200005
#define lowbit(o) o&(-o)
using namespace std;
int i,j,k,l,s,n,m,a[N],da[N];
set<int>GT;
struct node {
	int a[2],d;
}f[N*4];
inline int Min(int x,int y) {
	if (a[x]<a[y]) return x;
	return y;
}
inline void build(int o,int l,int r) {
	f[o].a[0]=f[o].a[1]=f[o].d=0;
	if (l==r) {
		f[o].a[l&1]=l; return ;
	}
	int mid=(l+r)>>1;
	build(o*2,l,mid),build(o*2+1,mid+1,r);
	for (int i=0;i<=1;i++) f[o].a[i]=Min(f[o*2].a[i],f[o*2+1].a[i]);
}
inline void change(int o,int l,int r,int ll,int rr) {
	if (rr<ll) return ;
	if (l==ll&&r==rr) {
		f[o].d^=1;
		swap(f[o].a[0],f[o].a[1]);
		return ;
	}
	if (f[o].d) f[o*2].d^=1,f[o*2+1].d^=1,swap(f[o*2].a[0],f[o*2].a[1]),swap(f[o*2+1].a[0],f[o*2+1].a[1]),f[o].d=0;
	int mid=(l+r)>>1;
	if (rr<=mid) change(o*2,l,mid,ll,rr);
	else if (ll>mid) change(o*2+1,mid+1,r,ll,rr);
	else change(o*2,l,mid,ll,mid),change(o*2+1,mid+1,r,mid+1,rr);
	for (int i=0;i<=1;i++) f[o].a[i]=Min(f[o*2].a[i],f[o*2+1].a[i]);
}
inline int ask(int o,int l,int r,int ll,int rr) {
	if (l==ll&&r==rr) return f[o].a[0];
	if (f[o].d) f[o*2].d^=1,f[o*2+1].d^=1,swap(f[o*2].a[0],f[o*2].a[1]),swap(f[o*2+1].a[0],f[o*2+1].a[1]),f[o].d=0;
	int mid=(l+r)>>1;
	if (rr<=mid) return ask(o*2,l,mid,ll,rr);
	else if (ll>mid) return ask(o*2+1,mid+1,r,ll,rr);
	else return Min(ask(o*2,l,mid,ll,mid),ask(o*2+1,mid+1,r,mid+1,rr));
}
inline void Change(int o,int l,int r,int ll) {
	if (l==ll&&r==ll) {
		f[o].a[1]=f[o].a[0]=0; return ;
	}
	if (f[o].d) f[o*2].d^=1,f[o*2+1].d^=1,swap(f[o*2].a[0],f[o*2].a[1]),swap(f[o*2+1].a[0],f[o*2+1].a[1]),f[o].d=0;
	int mid=(l+r)>>1;
	if (ll<=mid) Change(o*2,l,mid,ll);
	else Change(o*2+1,mid+1,r,ll);
	for (int i=0;i<=1;i++) f[o].a[i]=Min(f[o*2].a[i],f[o*2+1].a[i]);
}
int main() {
	scanf("%d",&n);
	a[0]=inf;
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	GT.insert(n+1);
	for (i=1;i<=n/2;i++) {
		int gt=f[1].a[1];
		int R=(*GT.lower_bound(gt))-1;
		int gtw=ask(1,1,n,gt+1,R);
		GT.insert(gt),GT.insert(gtw);
		da[2*i-1]=a[gt],da[2*i]=a[gtw];
		Change(1,1,n,gt),Change(1,1,n,gtw);
		change(1,1,n,gt+1,gtw-1);
	}	
	for (i=1;i<=n;i++) printf("%d ",da[i]);
	puts("");
}


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


int main() {
    int W,a,b;cin >> W >> a >> b;
    if (a+W < b){
        cout << b-(a+W) << endl;
    }else if (b+W < a){
        cout << a-(b+W) << endl;
    }else{
        cout << 0 << endl;
    }

}       

Measured memory_bytes: 256
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
C = [[int(i) for i in input().split()] for j in range(n)]


ans = []

for bits in range(1, 2**4):
    cnt = 0
    used = [False] * n
    A.sort(key=lambda x:x[bits & 1], reverse=bits >> 1 & 1)
    C.sort(key=lambda x:x[bits >> 2 & 1], reverse=bits >> 3 & 1)

    for c, d in C:
        i = 0
        while i < n and (used[i] or A[i][0] >= c or A[i][1] >= d):
            i += 1
        if i >= n:
            continue
        cnt += 1
        used[i] = True

    ans.append(cnt)

print(max(ans))

Measured memory_bytes: 3188
#include<iostream>
#include<unordered_map>
#include<bitset>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<ctype.h>
#include<unordered_set>
#include<string>
#include<iomanip>
#include<queue>
#include<limits>
#include<map>
#include<stack>
#include<iterator>
#include<cstring>

#include<deque>
#define pi 3.141592653589793238
#include<chrono>

#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define f0 get<0>
#define f1 get<1>
#define f2 get<2>

using namespace std;

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

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
     //cin >> T;
    while (T--) {
       ll a, b, c ,d ,e, k;
       cin >> a>> b >> c >>d >> e >> k;
       if(e - a > k){
           cout << ":(";
       }
       else{
           cout << "Yay!";
       }
    }

    return 0;
}


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

int main()
{
  string s, t;
  int count = 0;
  cin >> s;
  cin >> t;
  for(int i=0; i < s.size(); i++)
  {
    if(s[i] != t[i])
      count++;
  }
  cout << count;
  return 0;
}

Measured memory_bytes: 3900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005],b[200005],m;
int c;
int C;
int main(void){
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i>=1;i--){
		c=0;
		if(a[i]==1) c++;
		for(int j=i;i+j<=n;j=j+i){
			if(b[i+j]==1){
				c++;
			}
		}
		if(c%2==1){
			b[i]=1;
			m++;
		}else{
			b[i]=0;
		}
		//cout<<3455<<endl;
	}
	cout<<m<<endl;
	for(int i=1;i<=n;i++){
		if(b[i]==1){
			cout<<i;
			C++;
			if(C!=m) cout<<" ";
		}
	}
	cout<<endl;
    
}


Measured memory_bytes: 2432
n = int(input().split()[0])
v_list = list(map(int, input().split()))

r_v_list = sorted(v_list)

total = 0

for i, v in enumerate(r_v_list[1:]):
    if i == 0:
        total = (r_v_list[0] + v) / 2
    else:
        total = (total + v) / 2

print(total)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rep2(i,k,n) for(int i=k;i>=n;i--)
using namespace std;
const int N=2e5+7;
int num[N][2],n,m,die[N];
vector<int> tu[N];
char s[N];
queue<int> Q;
int main(){
	scanf("%d%d%s",&n,&m,s+1);
	rep(i,1,m){
		int u,v;scanf("%d%d",&u,&v);
		tu[u].push_back(v);
		tu[v].push_back(u);
		num[u][s[v]-'A']++;
		num[v][s[u]-'A']++;
	}
	rep(i,1,n)if(!num[i][0] || !num[i][1])Q.push(i);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		if(die[u])continue;
		die[u]=1;
		for(int i=0;i<tu[u].size();i++){
			int v=tu[u][i];
			num[v][s[u]-'A']--;
			if(!num[v][s[u]-'A'])Q.push(v);
		}
	}
	int ok=0;
	rep(i,1,n)if(!die[i])ok=1;
	if(ok)puts("Yes");
	else puts("No");
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n;
void solve(){
	cin >> n;
	
	queue<i64> q;
	for(int i = 1; i < 10; i++){
		q.push(i);
	}
	while(1){
		i64 p = q.front(); q.pop();
		n--;
		if(n == 0){
			cout << p << endl;
			break;
		}
		int c = p%10;
		if(c-1 >= 0) q.push(p*10+c-1);
		q.push(p*10+c);
		if(c+1 < 10) q.push(p*10+c+1);
	}
}

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


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vector<ll> a(n),b(n);
    rep(i,n) cin>>a[i]>>b[i];
    reverse(begin(a),end(a));
    reverse(begin(b),end(b));
    ll ans=0;
    rep(i,n){
      a[i]+=ans;
      if(a[i]%b[i]==0) continue;
      if(a[i]<=b[i]) ans+=b[i]-a[i];
      else ans+=b[i]-a[i]%b[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1920
import java.io.PrintWriter

//private val inp = java.io.File("in")
private val inp = System.`in`
private val reader = inp.bufferedReader()
private val wr = PrintWriter(System.out.bufferedWriter())

private fun readLn(): String = reader.readLine()
private fun readInt(): Int = readLn().toInt()
private fun readStrs(): List<String> = readLn().split(" ")
private fun readInts(): IntArray = readStrs().map { it.toInt() }.toIntArray()
private fun readChars(): CharArray = readStrs().map { it.single() }.toCharArray()

fun main() {
    val (n, k) = readInts()
    val pref = LongArray(n + 2)
    val mod = 1e9 + 7
    for (i in 1..n + 1) {
        pref[i] += pref[i - 1] + i - 1
    }

    var ans = 0L
    for (i in k..n + 1) {
        val minSum = pref[i]
        val maxSum = pref[n + 1] - pref[n + 1 - i]
        ans += maxSum - minSum + 1
        ans = (ans % mod).toLong()
    }

    println(ans)
}


Measured memory_bytes: 38044
// first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
const ll mod = 1e9 + 7 ;
void add_self(ll& a , ll b){a =  (a + b)%mod;}
//#define (x)  get<0>(x) 
//#define (x)  get<1>(x)
//#define (x)  get<2>(x)
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n ; 
cin>>n;
vector<ll> h(n) ;
for(ll i = 0 ; i<n ; i++)cin>>h[i] ; 

// dp[i] min(dp[i-1] +abs(h[i] - h[i-1]),dp[i-2] +abs(h[i] - h[i-2]))
ll dp0 = 0 ;
ll dp1 = abs(h[0] - h [1]);
for(ll i =2 ; i<n ; i++){
	ll temp = dp1;
	dp1 = min(dp1 +abs(h[i] - h[i-1]),dp0 +abs(h[i] - h[i-2]));
	dp0 = temp;
}
	
cout<<dp1;
	
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;

    for (int i = 0; i < N; ++i) {
        cout << S[i] << T[i];
    }

    cout << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = LLONG_MAX;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

//点a,bの距離の2乗
ld dist2(pdd a, pdd b){
    ld x = b.first - a.first;
    ld y = b.second - a.second;
    return x*x + y*y;
}

//点a,bの距離
ld dist(pdd a, pdd b){
    return sqrt(dist2(a, b));
}

//内積a・b
ld dot(pdd a, pdd b){
    ld x = a.first * b.first;
    ld y = a.second * b.second;
    return x+y;
}

//a,bを横に並べた行列の行列式
ld det(pdd a, pdd b){
    ld x = a.first * b.second;
    ld y = a.second * b.first;
    return x-y;
}

//b-a
pdd dif(pdd a, pdd b){
    pdd p;
    p.first = b.first - a.first;
    p.second = b.second - a.second;
    return p;
}

//点a,bの中点
pdd mid(pdd a, pdd b){
    pdd p;
    p.first = (a.first + b.first)/2;
    p.second = (a.second + b.second)/2;
    return p;
}

int main(){
    int N;
    cin >> N;
    pdd p[N];
    map<pdd, int> mp;
    rep(i, N){
        cin >> p[i].first >> p[i].second;
        mp[p[i]] = i;
    }
    sort(p, p+N);
    pdd q[N+1];
    int k = 1;
    q[0] = p[0];
    rep2(i, 1, N-1){
        if(i < N-1 && p[i-1].first == p[i].first) continue;
        while(k > 1 && det(dif(q[k-1], p[i]), dif(q[k-1], q[k-2])) <= 0) k--;
        q[k] = p[i], k++;
    }
    int t = k;
    rep3(i, N-2, 0){
        if(i > 0 && p[i+1].first == p[i].first) continue;
        while(k > t && det(dif(q[k-1], p[i]), dif(q[k-1], q[k-2])) <= 0) k--;
        q[k] = p[i], k++;
    }
    k--;
    ld ans[N];
    fill_n(ans, N, 0);
    ld pi = 3.141592653589793238;
    rep(i, k){
        int j = (k+i-1)%k, l = (i+1)%k;
        pdd x[2];
        x[0] = mid(q[i], q[j]);
        x[1] = mid(q[i], q[l]);
        ld r[3], R[3];
        rep(a, 2){
            r[a] = dist(q[i], x[a]);
            R[a] = dist2(q[i], x[a]);
        }
        r[2] = dist(x[0], x[1]);
        R[2] = dist2(x[0], x[1]);
        ld cos = -(R[0]+R[1]-R[2])/(2*r[0]*r[1]);
        if(cos > 1) cos = 1;
        elif(cos < -1) cos = -1;
        ld the = acos(cos);
        int n = mp[q[i]];
        ans[n] = the/(2*pi);
    }
    rep(i, N) cout << setprecision(15) << ans[i] << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < (n); i++)

using namespace std;

void solve() {
  long N;
  cin >> N;
  vector<long> foo;
  long ans = 0;
  rep (i, N) {
    long s;
    cin >> s;
    if (s % 10) foo.push_back(s);
    else ans += s;
  }
  sort(foo.begin(), foo.end());
  long foosum = 0;
  for (auto it: foo) foosum += it;
  if (foosum == 0) cout << 0 << endl;
  else if (foosum % 10 == 0) {
    ans += foosum - foo[0];
    cout << ans << endl;
  } else {
    ans += foosum;
    cout << ans << endl;
  }
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <complex>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

set<ll> prime(ll x) {
  set<ll> res;
  for (ll i = 2; i * i <= x; i++) {
    while (x % i == 0) {
      x /= i;
      res.insert(i);
    }
  }
  if (x != 1) {
    res.insert(x);
  }
  return res;
}

int main() {
  ll a, b;

  while (cin >> a >> b) {
    set<ll> pa = prime(a);
    set<ll> pb = prime(b);

    int ans = 1;
    for (auto &el: pa) {
      if (pb.find(el) != pb.end()) {
        ans++;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

bool ok(ll n, ll m) {
  return m > 0 && n / m == n % m;
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  ll n;
  cin >> n;
  ll res = 0;
  for (ll d = 1; d * d <= n; ++d) {
    if (ok(n, d - 1)) res += d - 1;
    if (d * d != n && ok(n, n / d - 1)) res += n / d - 1;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int n;
    ll sum = 0;
    cin >> n;
    vector<vector<int> > G(n);
    vector<int> dp(n, -1), answer(n), c(n);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(i, n) {
        cin >> c[i];
        sum += c[i];
    }
    sort(c.begin(), c.end(), greater<int>());
    // bfs
    queue<int> que;
    que.push(0);
    dp[0] = c[0];
    int count = 0;
    while(que.size()) {
        int p = que.front();
        que.pop();
        rep(i, G[p].size()) {
            int to = G[p][i];
            if(dp[to] == -1) {
                count++;
                dp[to] = c[count];
                que.push(to);
            }
        }
    }
    cout << sum - c[0] << endl;
    rep(i, n) {
        if(i != n-1) cout << dp[i] << " ";
        else cout << dp[i] << endl;
    } 
}

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

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define LB lower_bound
#define UB upper_bound

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1e9;
const LL MOD = 1e9+7;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

int main() {
  int r;
  cin >> r;
  int ans = r* r;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    N--;
    ll tmp = 1;
    ll ind = 0;
    while (1) {
        tmp *= 26;
        ind++;
        if (N - tmp < 0) {
            break;
        } else {
            N -= tmp;
        }
    }
    string ans = "";
    REP(i, 0, ind) {
        ll rem = N % 26;
        char c = 'a' + rem;
        string cc = "";
        cc += c;
        ans = cc + ans;
        N /= 26;
    }
    cout << ans << endl;
}


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

int main(void){
  int E,Y;
  cin >> E >> Y;
  switch(E){
    
    case 0: if(1868 <= Y && Y <= 1911){
            cout << 'M' << Y - 1868 + 1<<endl;
            }else if(1912 <= Y && Y <= 1925){
            cout << 'T' << Y - 1912 + 1<<endl;
            }else if(1926 <= Y && Y <= 1988){
            cout << 'S' << Y - 1926 + 1 << endl;
            }else if(1989 <= Y && Y<=2016){
            cout << 'H' << Y-1989+1<<endl;
            }
            
            break;
            
    case 1: cout <<1868 + Y - 1 << endl;
    break;
    case 2: cout << 1912 + Y - 1 << endl;
    break;
    case 3: cout <<1926+Y-1<<endl;
    break;
    case 4:cout<<1989+Y-1<<endl;
    break;
    
  }
  
  return 0;
  
}
                
      
      
      
      
      
      
      
      
      
  


Measured memory_bytes: 3100
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout(val) cout << std::fixed << std::setprecision(20) << val;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };

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

  int H,W,K; cin >> H >> W >> K;
  vector<string> grid(H);
  rep(i, H) cin >> grid[i];
  vector<vector<int>> ans(H, vector<int>(W, 0));

  int lastIchigoH = -1;
  rep(h, H) {
    rep(w, W) {
      if(grid[h][w] == '#') {
        lastIchigoH = h;
        break;
      }
    }
  }

  int cur = 1;
  rep(h, H) {
    int curLineCnt = 0;
    rep(w, W) {
      if(grid[h][w] == '#') {
        ++curLineCnt;
      }
    }
    if(curLineCnt == 0) continue;

    int nowCnt = 0;
    rep(w, W) {
      bool wasBerry = grid[h][w] == '#';
      if(wasBerry) {
        ++nowCnt;
      }

      grid[h][w] = '*';
      ans[h][w] = cur;

      for(int nextH = h - 1; nextH >= 0; --nextH) {
        if(grid[nextH][w] == '.') {
          grid[nextH][w] = '*';
          ans[nextH][w] = cur;
        } else {
          break;
        }
      }

      if(lastIchigoH == h) {
        for(int nextH = h + 1; nextH < H; ++nextH) {
          ans[nextH][w] = cur;
        }
      }

      // 最後のいちごではないなら++cur
      if(wasBerry && nowCnt != curLineCnt) {
        ++cur;
        continue;
      }

      if(w == W - 1) {
        ++cur;
      }
    }
  }

  rep(h, H) {
    rep(w, W) {
      cout << ans[h][w];
      if(w != W - 1) {
        cout << " ";
      }
    }
    cout << endl;
  }
}


Measured memory_bytes: 1280
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: list of int (adjacency list)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__tour=[0]*(2*n-1)
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__tour[self.__k]=v
        self.__k+=1
        for u in self.__E[v]:
            if u==p: continue
            self.__dfs(u,v)
            self.__tour[self.__k]=v
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

    @property
    def tour(self):
        return self.__tour

def resolve():
    # input
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    # build
    tree=EulerTour(E)
    # calculate
    imos=[0]*(2*n)
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        imos[tree.begin[p]]+=x
        imos[tree.end[p]]-=x
    for i in range(2*n-1):
        imos[i+1]+=imos[i]
    # output
    print(*[imos[tree.begin[i]] for i in range(n)])
resolve()

Measured memory_bytes: 245072
<?php
fscanf(STDIN,'%d %d %d',$A,$B,$C);
for($i=0;$i<9;$i++){
  $C = $C*$A-$B;
  echo $C."\n";
}
//最後は改行なし
$C = $C*$A-$B;
echo $C;

Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
ll INF = pow(10,9)+7;

int main(){
  int n,m,ans,end;
  cin >> n >> m;
  vector<P> v;
  ans = 1;
  rep(i,m){
    int a,b;
    cin >> a >> b;
    v.push_back(make_pair(b,a));
  }
  sort(v.begin(),v.end());
  end=v[0].first;
  rep(i,m){
    if(v[i].second>=end){
      end = v[i].first;
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 4292
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES

#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <list>
#include <math.h>
#include <map>
#include <iomanip>
#include <functional>
#include <string>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) os << *i << (i == end(v) - 1 ? "" : " "); return os;
}
template<class T> istream& operator>>(istream& is, vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) is >> *i; return is;
}


int main()
{
#if defined(_DEBUG) 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);



	int n;
	cin >> n;

	vector<int> vec(n);
	vector<pair<long long, int>> dp(n);
	int best_i = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> vec[i];
		dp[i] = { vec[i],-1 };
		for (int j = i - 2; j >= 0; j -= 2)
		{
			if ((dp[j].first + vec[i]) > dp[i].first)
			{
				dp[i] = { dp[j].first + vec[i] , j };
			}
		}
		if (dp[i].first > dp[best_i].first)
		{
			best_i = i;
		}
	}

	long long best_sum = dp[best_i].first;
	vector<int> field(n,0);
	while (best_i >= 0)
	{
		field[best_i] = 1;
		best_i = dp[best_i].second;
	}

	vector<int> resp;
	while(field.size() > 0)
	{
		if (field[0] == 0)
		{
			resp.push_back(1);
			field.erase(field.begin());
		}
		else
		{
			break;
		}
	}

	for (int i = field.size() - 1; i >= 0; i--)
	{
		if (field[i] == 0)
		{
			resp.push_back(i + 1);
			field.erase(--field.end());
		}
		else
			break;
	}

	while (field.size() > 1)
	{
		bool any = false;
		for (int i = 2; i < field.size(); i++)
		{
			if (field[i] == 0 && field[i - 1] == 0 && field[i - 2] == 0)
			{
				any = true;
				resp.push_back(i);
				field.erase(field.begin() + i);
				field.erase(field.begin() + i - 2);
				break;
			}
		}
		if (!any)
			break;
	}

	int x = field.size();
	while (x > 1)
	{
		resp.push_back(2);
		x -= 2;
	}

	cout << best_sum << "\n";
	cout << resp.size() << "\n";
	for (int x : resp)
		cout << x << "\n";

	return 0;
}

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

int main(){
	

	int t = 1;
	//cin >> t;
	while(t--){
		string s;
		cin >> s;
		if(s == "AAA"|| s == "BBB"){
			cout <<"No";
		}
		else cout << "Yes";
	}
	return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc088/tasks/abc088_c

import sys

m = [list(map(int, input().split())) for _ in range(3)]

for a in range(-1000, 1001):
    b_1 = m[0][0] - a
    b_2 = m[0][1] - a
    b_3 = m[0][2] - a
    if (m[1][0] - b_1 ==
        m[1][1] - b_2 ==
        m[1][2] - b_3) and \
        (m[2][0] - b_1 ==
         m[2][1] - b_2 ==
         m[2][2] - b_3):
        print('Yes')
        sys.exit()
print('No')



Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String args[])
	{
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int v[]=new int[n];
		int c[]=new int[n];
		for(int i=0;i<n;i++)
		{
			v[i]=scan.nextInt();
			

		}
		for(int i=0;i<n;i++)
		{
			c[i]=scan.nextInt();
		}
		long sum=0;
		for(int i=0;i<n;i++)
		{
			if(v[i]>c[i])
			{
				sum+=(v[i]-c[i]);
			}
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 23764
n,m = map(int,input().split())
ans = [1]*n

if n == 1:
    print(1)
else:
    for i in range(m):
        a = int(input())
        ans[a-1] = 0

    if ans[0] != 0 and ans[1] != 0:
        ans[0] = 1
        ans[1] = 2

    for i in range(2,n):
        if ans[i] != 0:
            ans[i] = (ans[i-1] + ans[i-2])%1000000007
        
    print(ans[n-1])


Measured memory_bytes: 6900
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  vector<int> A(N, 0), B(N, 0), C(N, 0);
  REP(i, N) cin >> A[i];
  REP(i, N) cin >> B[i];
  REP(i, N) cin >> C[i];
  sort(A.begin(), A.end()); sort(C.begin(), C.end());
  ll ans = 0;
  REP(i, N){
    int mid = B[i];
    ll upp = lower_bound(A.begin(), A.end(), mid) - A.begin();
    ll low = C.end() - upper_bound(C.begin(), C.end(), mid);
    ans += upp * low;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h> 
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("bhar.txt", "w", stdout);
    #endif
    long long q(1);//cin>>q;
    while(q--){
       long long n,m,k,tot(0),p(0);
       string s,l;
       bool ok(0),okk(0);
       cin>>n;
       for(int i=1;i<n;i++){
       		tot+=n/i;
       		if(n%i==0) tot--;
       }
       cout<<tot;
    }
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int main(){

  int h, w;
  cin >> h >> w;

  string s[h];

  for (int i = 0; i < h; i++){
    cin >> s[i];
  }

  int idx;
  for (int i = 0; i < h; i++){
    cout << s[i] << endl;
    cout << s[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import sys
import math
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())
    ans = 0.0

    for i in range(1, N+1):
        c = 0
        if i < K:
            c = math.ceil(math.log2(K) - math.log2(i))
        # print(i, c, (1.0 / (2 ** c)), 1.0/N)
        ans += (1.0 / (2 ** c)) * 1.0/N

    print("{0:.20f}".format(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#!/usr/bin/env python3

def main():
    x, y, a, b, c = map(int, input().split())
    p = map(int, input().split())
    q = map(int, input().split())
    r = map(int, input().split())
    p = list(reversed(sorted(p)))[:x]
    q = list(reversed(sorted(q)))[:y]
    pq = sorted(p + q)
    r = list(reversed(sorted(r)))
    for i in range(min(len(pq), len(r))):
        pq[i] = max(pq[i], r[i])
    print(sum(pq))

if __name__ == "__main__":
    main()


Measured memory_bytes: 28992
N, Q = map(int, input().split())
S = input()
lr = [0] * Q
for i in range(Q):
  lr[i] = list(map(lambda x: int(x) - 1, input().split()))
 
b, t = 0, [0]*N
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    t[i] = t[i-1] + 1
  else: t[i] = t[i-1]
 
for i in range(Q):
  print(t[lr[i][1]] - t[lr[i][0]])

Measured memory_bytes: 30660
x, n = map(int, input().split())
li_p = list(map(int, input().split()))

answer = -1
for i in range(max(x - n, 0), x + n + 1):
    if i in li_p:
        continue
    if abs(answer - x) > abs(i - x):
        answer = i
print(answer)


Measured memory_bytes: 9176
#include <iostream>
using namespace std;
int main()
{
 int x, y;
 for(int i=0; ; ++i)
 {
   cin >> x >> y;
   if (x==0 && y==0) break;
   if(x > y) cout << y << " " << x << endl;
   else cout << x << " " << y << endl;
 }
 return 0;
}

Measured memory_bytes: 2984
import Control.Monad (replicateM, filterM, forM)
import Control.Monad.ST (ST, runST)
import Data.Array (Array, listArray, (!), bounds)
import qualified Data.Array.ST as STArr

type Field = Array (Int,Int) Bool
type Visited s = STArr.STUArray s (Int,Int) Bool

main = do
    m <- readLn
    n <- readLn
    if all (==0) [m,n] then return () else do
        lines <- replicateM n (getLine >>= return . map (=="1") . words)
        let field = listArray ((1,1),(n,m)) (concat lines)
        print $ solve m n field

        main

solve :: Int -> Int -> Field -> Int
solve m n field = runST $ do
    visited <- STArr.newArray ((1,1),(n,m)) False :: ST s (Visited s)
    maximum `fmap` mapM (longestFrom field visited) starts

    where
    starts = filter (field !) [(y,x)|y<-[1..n],x<-[1..m]]

longestFrom :: Field -> Visited s -> (Int,Int) -> ST s Int
longestFrom field visited (y,x) = do
    STArr.writeArray visited (y,x) True

    nexts <- filterM visitable [(y-1,x),(y+1,x),(y,x-1),(y,x+1)]
    longest <- ((1+) . maximum') `fmap` forM nexts (longestFrom field visited)

    STArr.writeArray visited (y,x) False
    return longest

    where
    (_,(n,m)) = bounds field

    maximum' [] = 0
    maximum' xs = maximum xs

    visitable (y,x)
        | x < 1 || y < 1 || x > m || y > n = return False
        | not (field ! (y,x)) = return False
        | otherwise = not `fmap` STArr.readArray visited (y,x)

Measured memory_bytes: 29796
import java.util.Scanner;

public class Main {

    /*
     * https://atcoder.jp/contests/abc164/tasks/abc164_a
     */

    public static void main(String[] args) {

        Scanner stdIn = new Scanner(System.in);
        String input = stdIn.nextLine();
        stdIn.close();

        String[] arguments = input.split(" ");
        int t_hp = Integer.valueOf(arguments[0]);
        int t_att = Integer.valueOf(arguments[1]);
        int a_hp = Integer.valueOf(arguments[2]);
        int a_att = Integer.valueOf(arguments[3]);

        String result = "Yes";

        while (true) {

            a_hp = a_hp - t_att;
            if (a_hp <= 0) {
                break;
            }

            t_hp = t_hp - a_att;
            if (t_hp <= 0) {
                result = "No";
                break;
            }
        }

        System.out.println(result);
    }
}

Measured memory_bytes: 27048
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


template<typename T>
class CumulativeSum{
public:
  Int n;
  vector<T> sum;
  vector<T> A;
  Int added;
  CumulativeSum():n(-1),added(0){}
  CumulativeSum(Int n):n(n), sum(n+1), A(n+1),added(0){}
  CumulativeSum(const vector<T> &B):n(B.size()), sum(n+1), A(n+1),added(0){
    for(Int i=1;i<=n;i++) sum[i] = sum[i-1] + B[i-1];
  }

  void apply(){
    for(Int i=1;i<=n;i++) A[i] = A[i] + A[i-1];
    for(Int i=1;i<=n;i++) A[i] = A[i] + A[i-1];
    for(Int i=1;i<=n;i++) sum[i] = sum[i] + A[i-1];
    added = 0; A.clear(); A.resize(n+1);
  }

  //[l, r)にxを加算
  void add(Int l, Int r, T x){
    added = 1;
    assert(l <= r && 0 <= l && r <= n);
    A[l] = A[l] + x;
    A[r] = A[r] - x;
  }

  //[l, r)の和を得る
  T get(Int l,Int r){
    assert(l<=r && 0<=l && r<=n);
    if(added) apply();
    return sum[r] - sum[l];
  }
};

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N;
  cin>>N;
  vector<Int> A(N);
  cin>>A;
  sort(A.begin(), A.end(), greater<Int>());


  const Int M = 50000;
  vector<Int> cnt(M);
  for(Int i=0;i<N;i++)
    for(Int j=i+1;j<N;j++) cnt[A[i] + A[j]]++;

  CumulativeSum<Int> sum(cnt);
  Int ans = 0;
  Int ofset = 0;
  for(Int i=0;i<N;i++){
    ofset -= N-(i+1);
    ans += sum.get(A[i]+1, M) + ofset;
  }

  cout<<ans<<endl;



  return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
using namespace std;
int main(void) {
	int x, y, z, cnt = 1;
	cin >> x >> y >> z;
	x -= y + 2 * z;
	
	while (1) {
		x -= y + z;
		if (x < 0) break;
		cnt++;
	}
	printf("%d", cnt);

	return 0;
}

Measured memory_bytes: 256
N = int(input())
T = list(map(int, input().split()))
sum_ = sum(T)
M = int(input())
ans = list()
for i in range(M) :
    P, X = map(int,input().split())
    gap = T[P-1] - X
    ans.append(sum_ - gap)

for i in range(len(ans)):
    print(ans[i])


Measured memory_bytes: 62904
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 1005
#define fi(a, b, c, d) for(int a = b; i < c; i += d)
#define fl(a, b, c, d) for(ll a = b; i < c; i += d)
#define quit exit(0)

ll N, K, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;

int main() {
	scanf("%lld", &N);
	double part = (N / 3.0);
	printf("%0.12lf\n", part * part * part);
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b;cin>>n>>a>>b;
    cout<<min(b,n*a)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[100002];

ll frog2(ll h[], ll k, ll n){
	if(n==2)
		return abs(h[1]-h[2]);
	if(n<=1)
		return 0;

	if(dp[n]!=-1)
		return dp[n];
	ll temp = INT_MAX;
	for(int i=1;i<=k;i++){
      	if((n-i)==0)
          break;
		temp = min(temp,abs(h[n] - h[n-i]) + frog2(h,k,n-i));
	}
	
	return dp[n] = temp;
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    ll h[n+1];
    for(int i=1;i<=n;i++){
    	cin>>h[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<frog2(h,k,n);
}


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

// dp[coins][heads]
double dp[3005][3005];

int main() {
	int n;
	cin >> n;
	vector<double> coins(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> coins[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i < j) {
				dp[i][j] = 0;
			}
			else if (i == 1 && j == 1) {
				dp[i][j] = coins[i - 1];
			}
			else if (i == 1 && j == 0) {
				dp[i][j] = (1 - coins[i - 1]);
			}
			else {
				dp[i][j] = dp[i - 1][j - 1] * coins[i - 1] + dp[i - 1][j] * (1 - coins[i - 1]);
			}
		}
	}
	double ans = 0;
	for (int i = n / 2 + 1; i <= n; i++) {
		ans += dp[n][i];
	}

	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}


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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    vector<llint> a(n);
    llint sumall = 0;
    for(int in=0;in<n;in++) {
        cin >> a.at(in);
        sumall += a.at(in);
    }
    vector<llint> sum(n+1);
    for(int in=0;in<n;in++) {
        if(in==0) sum.at(in) = 0;
        else sum.at(in) = sum.at(in-1) + a.at(in-1);
    }

    llint ans = 1e18, m1, m2;
    for(int in=0;in<n-1;in++) {
        m1 = sum.at(in+1);
        m2 = sumall - sum.at(in+1);
        ans = min(ans, abs(m1-m2));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328