akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int c(char *p,int d){return ((26+*p-*(p+1))%26==d);}
//int a(char *p){return((*p<'a')||(*p>'z'));}
int a(char *p){return((*p>'`')&&(*p<'{'));}

char *decode (char *inbuf, int s) {
  int p = 0;
  while (inbuf[p]){
    if(a(&inbuf[p])) {
      int t = inbuf[p] + s;

      if (t > 'z')      inbuf[p] = (char)(t - 26);
      else if (t < 'a') inbuf[p] = (char)(t + 26);
      else              inbuf[p] = (char)t;
    }
    p++;
  }
  return (inbuf);
}
int main(s){
  char inbuf[82];
  while(fgets(inbuf,80,stdin)){
    char *p=inbuf-1;
    while(*++p){
      if((c(p,12))&&((c(p+1,3)&&!a(p+3))||(c(p+1,7)&&c(p+2,7)&&!a(p+4))||(c(p+1\
,25)&&c(p+2,16)&&!a(p+4)))){s='t'-*p;p+=3;break;}
    }
    printf("%s",decode(inbuf, s));
  }
  return 0;
}

Measured memory_bytes: 520
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			
			int H = scan.nextInt();
			int W = scan.nextInt();
			String[] S = new String[H];
			char [][]s = new char[H][W];
			int [][]D = new int[H][W];
			
			for(int i = 0;i<H;i++) {
				S[i] = scan.next();
				s[i] = S[i].toCharArray();		
			}
			
			for(int i = 0;i<H;i++) {
				int count = 0;
				for(int j = 0;j<W;j++) {
					if(j==W-1) {
						if(s[i][j]=='.') {
							count++;
						for(int z = j-count+1;z<=j;z++) {
							D[i][z]+=count;
						}
						
						}else {
							for(int z = j-count;z<j;z++) {
								D[i][z]+=count;
							}
						}
						count = 0;
					}
					
					
					if(s[i][j]=='.') {
						count++;
					}else if(s[i][j]=='#'){
						for(int z = j-count;z<j;z++) {
							D[i][z]+=count;
						}
						count = 0;
					} 

				}
			}
			
			for(int j = 0;j<W;j++) {
				int count = 0;
				for(int i = 0;i<H;i++) {
					if(i==H-1) {
						if(s[i][j]=='.') {
							count++;
						for(int z = i-count+1;z<=i;z++) {
							D[z][j]+=count;
						}
						
						}else {
							for(int z = i-count;z<i;z++) {
								D[z][j]+=count;
							}
						}
						count = 0;
					}
					
					
					if(s[i][j]=='.') {
						count++;
					}else if(s[i][j]=='#'){
						for(int z = i-count;z<i;z++) {
							D[z][j]+=count;
						}
						count = 0;
					} 

				}
			}
			
			int max = 0;

			for(int i = 0;i<H;i++) {
				for(int j = 0;j<W;j++) {
					if(max<D[i][j])max = D[i][j];
					
					//System.out.print(D[i][j]);
					//System.out.print(" ");
				}
				//System.out.println();
			}
			
			
			System.out.println(max-1);
			
			
		}
	}
	
}


Measured memory_bytes: 74976
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main () {

    int N;
    scanf("%d", &N);

    int d[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &d[i]);
    }

    sort(d, d + N);

    printf("%d\n", d[N/2] - d[N/2-1]);

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int log2(int a) {
    int c = 0;
    while (a % 2 == 0) {
        a /= 2;
        c++;
    }
    return c;
}

int main(void) {
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];

    int c = 0;
    rep(i, n) {
        if ( a[i] % 2 == 1 ) continue;
        c += log2(a[i]);
    }
    cout << c << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
    int N;
    std::cin >> N;
    
    std::string S;
    std::cin >> S;
    
    int r = 0;
    int b = 0;
    
    for (int i=0; i<N; ++i) {
        if (S[i]=='R') r++;
        else b++;
    }
    
    if (r > b) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
}

Measured memory_bytes: 256
/**
DufauX-XuafuD
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define reset(x) memset(x,-1,sizeof(x))
#define CheckBit(a,b) (a&(1ll<<b))
#define SetBit(a,b) a=(a|(1ll<<b))
#define UnSetBit(a,b) a=(a&(~(1ll<<b)))
#define maxx 10000006
#define PI 2*acos(0.0)
const long long INF = 2000000000000000000LL;	// 2e18
const int inf = 0x3f3f3f3f;	// 1061109567
const long double EPS = 1e-9;
//bitset<maxx/2>vis;
//bitset<maxx>pr;
//int mobi[maxx+10];
//vector<ll>prime;
//void sieve(){
//    ll x=maxx/2, y=sqrt(maxx)/2;
//    for(ll i=1;i<=y;i++){
//        if(vis[i]==0){
//            for(ll j=(i*(i+1)*2);j<x;j+=(2*i)+1)
//                vis[j]=1;
//        }
//    }
//    prime.push_back(2);
//    for(ll i=3;i<maxx;i+=2)
//        if(vis[i/2]==0)
//        prime.push_back(i);
//}
//void generate_mobius()
//{
//    for(int i=0;i<maxx;i++)mobi[i]=1;
//    for(int i=2;i<maxx;i++){
//        if(!pr[i]){
//            mobi[i]*=-1;
//            for(int j=i+i;j<maxx;j+=i){
//                pr[j]=1;
//                mobi[j]*=(j%(i*i)?-1:0);
//            }
//        }
//    }
//}
//bool isprime(ll a)
//{
//    if(a==1)return false;
//    if(a==2)return true;
//    if(a%2==0)return false;
//    for(ll i=0;i<prime.size() && prime[i]*prime[i]<=a;i++)
//        if(a%prime[i]==0)return false;
//    return true;
//}
/* Calculate ( a*b ) %c */
inline ll mulmod(ll a, ll b, ll c) {
    ll ret = 0 , cur = a % c ;
    while(b) { if(b%2) ret=(ret+cur)%c; cur=(cur<<1)%c; b=b>>1; }
    return ret%c;
}
//Calculate (b^p)%m || modular inverse: b^-1 = bigmod(b, m-2, m)
inline ll bigmod(ll b, ll p, ll m){
    ll ret = 1, cur = b % m;
    while(p) { if(p&1) ret=(ret*cur)%m; cur=(cur*cur)%m; p=p>>1; }
    return ret;
}
inline ll modulo(ll a,ll b,ll c) { //Same as big mod, use for numbers over 1e10
    ll ret = 1 , cur = a%c ;
    while(b) { if(b%2) ret=mulmod(ret,cur,c); cur=mulmod(cur,cur,c); b=b>>1; }
    return ret%c ;
}
inline ll power(ll b, ll p){
    ll ret = 1, cur = b;
    while(p) { if(p&1) ret=(ret*cur); cur=(cur*cur); p=p>>1; }
    return ret;
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
ll gcd(ll a,ll b)
{
    return __gcd(a,b);
}
void Dufaux()
{
    ll w,a,b;
    cin>>w>>a>>b;
    ll firstax=a;
    ll secondax=a+w;
    ll firstay=b;
    ll seconday=b+w;
    if((firstay>=firstax && firstay<=secondax) || (seconday>=firstax && seconday<=secondax)){
        cout<<"0"<<endl;
    }
    else{
        ll aa=abs(firstax-firstay);
        ll bb=abs(firstax-seconday);
        ll cc=abs(secondax-firstay);
        ll dd=abs(secondax-seconday);
        cout<<min(aa,min(bb,min(cc,dd)))<<endl;
    }
}
int main()
{
    FastIO;
	///sieve();
	///generate_mobius();
	int test=1;
	while(test--){
        Dufaux();
	}
	return 0;
}






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

//.define
// #define FILE_IN_OUT
#define RET(_x)                       return cout << (_x) << '\n', 0;
#define all(_obj)                     (_obj).begin(), (_obj).end()
#define loop(_n)                      for (int i = 0; i < (_n); ++i)
#define CeilDiv(_dividend, _divider)  (((_dividend) - 1LL + (_divider)) / (_divider))
#define sz(_obj)                      static_cast<int>((_obj).size())
#ifdef SHJ_LOCAL
#define debug(_x)                     std::cerr << (#_x) << " = " << (_x) << '\n' << std::flush;
#else
#define debug(_x)                     {}
#endif
#define endl "\n"
template<typename Tp>
inline void outarr(Tp _begin, Tp _end, const char* _delim = " ") {
    for (Tp current = _begin; current != _end; ++current) {
        std::cout << *current << _delim;
    }
    std::cout << '\n';
}

//.constant
using ll  = long long;
using pii = std::pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = static_cast<const int>(1e9 + 7);

//.data
int Mul(int x, int y) {
    return int(1LL * x * y % MOD);
}

//.code
int main() {
#ifdef FILE_IN_OUT
    std::ifstream cin ("input.txt",  std::ios::in);
    std::ofstream cout("output.txt", std::ios::out);
#else
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

    int n, k;
    cin >> n >> k;
    vector<int> pos;
    vector<int> neg;
    int tot = 1;
    loop(n) {
        int x;
        cin >> x;
        if (x >= 0) {
            pos.push_back(x);
        } else if (x < 0) {
            neg.push_back(x);
        }
        tot = Mul(tot, abs(x));
    }
    if (k == n) {
        if (sz(neg) & 1) {
            RET((MOD - tot) % MOD);
        }
        RET(tot);
    }
    sort(all(neg));
    if (empty(pos)) {
        if (k & 1) {
            reverse(all(neg));
        }
        int ans = 1;
        loop(k) {
            ans = Mul(ans, -neg[i]);
        }
        if (k & 1) {
            RET((MOD - ans) % MOD);
        }
        RET(ans);
    }
    vector<ll> arr;
    for (int i = 1; i < sz(neg); i += 2) {
        arr.emplace_back(1LL * neg[i] * neg[i - 1]);
    }
    sort(all(pos));
    int ans = 1;
    if (k & 1) {
        ans = Mul(ans, pos.back());
        pos.pop_back();
        --k;
    }
    reverse(all(pos));
    vector<ll> brr;
    for (int i = 1; i < sz(pos); i += 2) {
        brr.emplace_back(1LL * pos[i] * pos[i - 1]);
    }
    vector<ll> res;
    sort(all(arr));
    sort(all(brr));
    merge(all(arr), all(brr), back_inserter(res));
    reverse(all(res));
    loop(k >> 1) {
        ans = Mul(ans, res[i] % MOD);
    }
    cout << ans << endl;

#ifdef FILE_IN_OUT
    cin.close();
    cout.close();
#endif
    return 0;
}

Measured memory_bytes: 6376
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdio>
using namespace std;

#define int long long
#define INF 1e18

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

    for(int i = 0; i < s.size(); i++) {
        if(s == t) {
            cout << "Yes" << endl;
            return 0;
        }
        t = t.back() + t.substr(0, t.size() - 1);
    }

    cout << "No" << endl;
}


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

#define MAX 2020

char g[MAX][MAX];

int main(){
  int H,W;cin>>H>>W;
  vector<vector<int>> row(H),col(W);
  rep(i,H){row[i].push_back(0);row[i].push_back(W+1);}
  rep(j,W){col[j].push_back(0);col[j].push_back(H+1);}
  rep(i,H){
    string s;cin>>s;
    rep(j,W){
      g[i][j]=s[j];
      if(s[j]=='#'){row[i].push_back(j+1);col[j].push_back(i+1);}
    }
  }
  rep(i,H) sort(all(row[i]));
  rep(j,W) sort(all(col[j]));
  //rep(i,H){rep(j,row[i].size()){cout<<row[i][j];}cout<<endl;}
  int ans=0;
  rep(i,H){
    rep(j,W){
      if(g[i][j]=='#')continue;
      int r = lower_bound(all(row[i]),j+1)-row[i].begin();
      int c = lower_bound(all(col[j]),i+1)-col[j].begin();
      ans = max(ans,row[i][r]-row[i][r-1]-1 + col[j][c]-col[j][c-1]-1 - 1);
      //cout << "i,j" << i << j << "rc" << row[i][r]-row[i][r-1]-1 << col[j][c]-col[j][c-1]-1 << endl;
    }
  }
  cout<<ans<<endl;
}

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

int main(){
	int a, b;
	cin >> a >> b;
	
	int price = -1; 
	rep(i, 10000) {
      if (a == (int)(i*0.08) && b == (int)(i*0.1)) {
        price = i;
        break;
      }
    }
	
	cout << price << endl;
}

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

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

bool ok[200009];

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n, k, r, s, p;
    string t, a, b;
    cin >> n >> k >> r >> s >> p >> t;

    a.resize(n);
    b.resize(n);

    int ans(0);

    for (int i = 0; i < n; ++i) {
        if (t[i] == 'r') {
            if (i >= k) {
                if (a[i - k] == 'p' && t[i - k] == 'r')
                    a[i] = 'r', b[i] = 's';
                else if (a[i - k] == 'p')
                    a[i - k] = b[i - k], a[i] = 'p', b[i] = 'r' + 'p' + 's' - a[i] - a[i - k], ans += p;
                else
                    a[i] = 'p', b[i] = 'r' + 'p' + 's' - a[i - k], ans += p;
            }
            else {
                a[i] = 'p', b[i] = 'r', ans += p;
            }
        }
        else if (t[i] == 'p') {
            if (i >= k) {
                if (a[i - k] == 's' && t[i - k] == 'p')
                    a[i] = 'p', b[i] = 'r';
                else if (a[i - k] == 's')
                    a[i - k] = b[i - k], a[i] = 's', b[i] = 'r' + 'p' + 's' - a[i] - a[i - k], ans += s;
                else
                    a[i] = 's', b[i] = 'r' + 'p' + 's' - a[i - k], ans += s;
            }
            else {
                a[i] = 's', b[i] = 'p', ans += s;
            }
        } else {///'s'
            if (i >= k) {
                if (a[i - k] == 'r' && t[i - k] == 's')
                    a[i] = 's', b[i] = 'p';
                else if (a[i - k] == 'r')
                    a[i - k] = b[i - k], a[i] = 'r', b[i] = 'r' + 'p' + 's' - a[i] - a[i - k], ans += r;
                else
                    a[i] = 'r', b[i] = 'r' + 'p' + 's' - a[i - k], ans += r;
            }
            else {
                a[i] = 'r', b[i] = 's', ans += r;
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
 
using namespace std;
 
#define rip(i, n, s) for (int i = (s);i < ( int )( n ); i++)
#define all(a) (a).begin(), (a).end()
typedef long long ll; 

struct modint {
	long long num;
	long long p;
	modint() {
		num = 0;
		p = 1000000007;
	}
	modint(int x) {
		p = 1000000007;
		num = (long long)x%p;
	}
	modint(long long x) {
		p = 1000000007;
		num = x % p;
	}
	modint operator+(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num + other.num) % p;
		return ret;
	}
	modint operator+(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num + (other%p)) % p;
		return ret;
	}
	modint operator-(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num - other.num + p) % p;
		return ret;
	}
	modint operator-(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num - (other%p) + p) % p;
		return ret;
	}
	modint operator*(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*other.num) % p;
		return ret;
	}
	modint operator*(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*(other%p)) % p;
		return ret;
	}
	void operator+=(const long long &other) {
		num = (num + other) % p;
	}
	void operator+=(const modint &other) {
		num = (num + other.num) % p;
	}
	void operator-=(const long long &other) {
		num = (num - other + p) % p;
	}
	void operator-=(const modint &other) {
		num = (num - other.num + p) % p;
	}
	void operator*=(const long long &other) {
		num = (num*other) % p;
	}
	void operator*=(const modint &other) {
		num = (num*other.num) % p;
	}
};

template<typename T>
struct matrix{
	int size;
	vector<vector<T> > table;
	matrix(int n){
		size=n;
		table=vector<vector<T> >(n,vector<T>(n));
	}
	matrix<T> operator*(const matrix<T> &othor){
		matrix<T> ret(size);
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				for(int k=0;k<size;k++){
					ret.table[i][j]+=table[i][k]*othor.table[k][j];
				}
			}
		}
		return ret;
	}
	T all_sum(){
		T ret = table[0][0];
		for(int i=1;i<size;i++){
			ret+=table[0][i];
		}
		for(int i=1;i<size;i++){
			for(int j=0;j<size;j++){
				ret+=table[i][j];
			}
		}
		return ret;
	}
};

template<typename T>
T pow(ll n,T &da){
	if (n==1){
		return da;
	}
	if (n%2){
		return pow(n-1,da)*da;
	}
	else{
		T ret = pow(n/2,da);
		return ret*ret;
	}
}

int main(){
	int n;
	ll k;
	cin >> n >> k;
	matrix<modint> mt(n);
	rip(i,n,0){
		rip(j,n,0){
			cin >> mt.table[i][j].num;
		}
	}
	mt=pow(k,mt);
	cout << mt.all_sum().num << endl;
}

Measured memory_bytes: 384
use std::io::Read;

fn main() {
    let mut buf = String::new();

    std::io::stdin().read_to_string(&mut buf).unwrap();

    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let mut a: Vec<usize> = vec![];
    let mut b: Vec<usize> = vec![];
    let mut c: Vec<usize> = vec![];

    for _ in 0..n {
        a.push(iter.next().unwrap().parse::<usize>().unwrap() - 1);
    }
    for _ in 0..n {
        b.push(iter.next().unwrap().parse().unwrap());
    }
    for _ in 0..(n - 1) {
        c.push(iter.next().unwrap().parse().unwrap());
    }

    let mut ans = 0;
    let mut prev = a[0];

    for a in a.into_iter() {
        ans += b[a];

        if a > 0 && prev == a - 1 {
            ans += c[prev];
        }
        prev = a;
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<29;
int main(){
  
  //入力
  int H; int N;
  cin >> H >> N;
  int A[N]; int B[N];
  for(int i=0;i<N;i++) cin >> A[i] >> B[i];
  
  int DP[H+1]; //min{-i~に必要な魔力}
  DP[0]=0;
  for(int i=1;i<=H;i++){
    int minA=INF;
    for(int j=0;j<N;j++){
      minA=min(minA,DP[max(0,i-A[j])]+B[j]);
    }
    DP[i]=minA;
  }
  
  cout << DP[H] << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const int INF = 100000;
typedef pair<int, int> P;
int n;
int main()
{
    int a,b,c,d,e,k;
    cin>>a>>b>>c>>d>>e>>k;
    if(e-a<=k)cout<<"Yay!"<<endl;
    else cout<<":(";
} 

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

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = 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; }
template<class T>
T GCD(T a, T b) { if (b == 0) return a; else return GCD(b, a % b); }
template<class T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	ll a, b, c, k;
	cin >> a >> b >> c >> k;

	if (k <= a + b) {
		cout << min(k, a) << endl;
	}
	else {
		ll tmp = k - (a + b);
		cout << a - tmp << endl;
	}
}


Measured memory_bytes: 3580
// Sakhiya07 - Yagnik Sakhiya

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>

#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 200005;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));
ll sz[N],ans,p[N],n;
vector<ll> v[N];
ll modularExponentiation(ll x,ll n)
{
    int result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%MOD;
        x=(x*x)%MOD;
        n=n/2;
    }
    return result;
}

void dfs(ll id,ll p1)
{
    ll sum = 0;
    for(auto X:v[id])
    {
        if(X!=p1)
        {
            dfs(X,id);
            sum += sz[X];
        }
    }
    sz[id] = 1 + sum;
}
void dfs1(ll id,ll p1)
{
    ll sum = 1;
    ll cnt = 0;
    for(auto X:v[id])
    {
        ll temp = p[sz[X]] - 1;
        cnt = (cnt + temp)%MOD;
        sum = (sum * (temp+1))%MOD;
    }
    sum = (sum - cnt - 1 + MOD)%MOD;
    ans = (ans + sum)%MOD;
    for(auto X:v[id])
    {
        if(X!=p1) 
        {
            sz[id] -= sz[X];
            sz[X] = n;
            dfs1(X,id);
            sz[X] = n - sz[id];
            sz[id] += sz[X];
        }    
    }

}
void solve()
{
    p[0] = 1;
    for(ll i=1;i<N;i++)   p[i] = (p[i-1] * 2)%MOD;
    cin >> n;
    for(ll i=0,x,y;i<n-1;i++)
    {
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,0);
    dfs1(1,0);
    ans = (ans * modularExponentiation(p[n],MOD-2))%MOD;
    cout<<ans;
}

int main()
{
    FAST;
    ll t = 1;
  //  cin >> t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 23552
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define tp tuple<int,int,int>
#define mtp make_tuple
using namespace std;

const int N=15;
int n,m,a[N][N],x,c[N],cnt[N];

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)
    {
        cin>>c[i];
        for(int j=0;j<m;j++) cin>>a[i][j];
    }
    int res=1e18;
    for(int mask=0;mask<(1<<n);mask++)
    {
        int cost=0;
        memset(cnt,0,sizeof cnt);
        for(int i=0;i<n;i++)
        {
            if(mask>>i&1)
            {
                cost+=c[i];
                for(int j=0;j<m;j++) cnt[j]+=a[i][j];
            }
        }
        bool kt=true;
        for(int i=0;i<m;i++) if(cnt[i]<x) kt=false;
        if(kt) res=min(res,cost);
    }
    if(res==1e18) res=-1;
    cout<<res;
}


Measured memory_bytes: 3608
#include<iostream>
using namespace std;
int main()
{
	int a, b,c;
	cin >> a >> b >> c;
	if(b+c>a)
	{
		cout << (b + c - a) << endl;
	}
	else
	{
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m = LI()
    aa = [LI_() for _ in range(m)]
    uf = UnionFind(n)
    for a,b,c in aa:
        uf.union(a,b)
    r = 0
    for i in range(n):
        if uf.table[i] < 0:
            r += 1

    return r


print(main())




Measured memory_bytes: 24812
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<ll>
#define pb push_back
#define ff first
#define ss second
#define inf 2e18
#define ull unsigned long long
#define pi acos(-1.0)
#define mod 1000000007
#define lop0(n) for(ll i=0;i<n;i++)
#define lopj(n) for(ll j=0;j<n;j++)
#define lop1(n) for(ll i=1;i<=n;i++)
#define all(v) v.begin(),v.end()
ll Set(ll N,ll pos){ return N=N | (1LL<<pos); }
ll reset(ll N,ll pos){ return N= N & ~(1LL<<pos); }
bool check(ll N,ll pos){ return (bool)(N & (1LL<<pos)); }
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

main()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll cnt=0;
    lop0(s.size())
    {
        if(s[i]=='W') cnt++;
    }
    reverse(all(s));
    ll ans=cnt;
    lop0(cnt)
    {
        if(s[i]=='W') ans--;
    }
    cout<<ans;
}



Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
    int w,h,n;
    cin >> w >> h >> n;
    int wmin=0,hmin=0,wmax=w,hmax=h;
    REP(i,n){
        int x,y,a;
        cin >> x >> y >> a;
        if(a==1)wmin=max(x, wmin);
        if(a==2)wmax=min(x, wmax);
        if(a==3)hmin=max(y, hmin);
        if(a==4)hmax=min(y, hmax);
    }
    int ans=max(0, (wmax-wmin))*max(0, (hmax-hmin));
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<int> d(N);
  rep(i,N)
  {
    cin >> d[i];
  }
  int sum = 0;
  rep(i,N-1)
  {
    for(int j=i+1;j<N;j++)
    {
      sum += d[i]*d[j];
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define MAX_N 51
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
ll n, k, x[MAX_N], y[MAX_N];

signed main(){
	// const ll INF = 1e18;
	cin >> n >> k;
	REP(i, n) cin >> x[i] >> y[i];
	ll ret = 9223372036854775807;
	// x
	REP(i, n){
		REP(j, n){
			// y
			REP(l, n){
				REP(m, n){
					ll cnt = 0;
					REP(p, n) if((x[p] - x[i]) * (x[p] - x[j]) <= 0 && (y[p] - y[l]) * (y[p] - y[m]) <= 0) cnt++;
					// cout << cnt << endl;
					if(cnt >= k) ret = min(ret, abs(x[i] - x[j]) * abs(y[l] - y[m]));
				}
			}
		}
	}
	cout << ret << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e7 + 10;
const ll mod = 998244353;

ll powmod(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b /= 2;
	}
	return res;
}

inline ll inv(ll a) {
	return powmod(a, mod-2);
}

int n;
ll fact[maxn];
ll invfact[maxn];
ll pow2[maxn];

ll choose(ll a, ll b) {
	if (a < b) return 0;
	ll res = fact[a];
	res = (res * invfact[b]) % mod;
	res = (res * invfact[a-b]) % mod;
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	fact[0] = invfact[0] = 1;
	pow2[0] = 1;
	ll pow3 = 1;
	for (int i = 1; i <= n; ++i) {
		fact[i] = (fact[i-1] * i) % mod;
		invfact[i] = inv(fact[i]);
		pow2[i] = (pow2[i-1] * 2) % mod;
		pow3 = (pow3 * 3) % mod;
	}
	ll ans = pow3;
	for (int i = n/2 + 1; i <= n; ++i) {
		ll res = 2;
		res = (res * choose(n, i)) % mod;
		res = (res * pow2[n - i]) % mod;
		ans = (ans - res + mod) % mod;
	}
	cout << ans << endl;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
//typedef vector<vector<ll>> Graph;

const ll mod = 1e9 + 7;
//const ll mod = 998244353;

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second

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 (a>b) { a=b; return 1; } return 0; }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};

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

    bool same = true;
    REP(i, N) if(A[i] != B[i]) same = false;

    if(same){
        cout << 0 << endl;
    }else{
        ll S = 0;
        ll mi = (1ll<<60);
        REP(i, N){
            S += A[i];
            if(A[i]>B[i]) chmin(mi, B[i]);
        }
        cout << S - mi << endl;
    }

    return 0;
}

Measured memory_bytes: 3644
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <bitset>
#include <cassert>

using namespace std;

const int SIZE = 1 << 17;

int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0,sign = 1;
    char ch = Advance();
    while (!isdigit(ch) && ch != '-')
        ch = Advance();
    if (ch == '-') {
        ch = Advance();
        sign = -1;
    }
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer * sign;
}

char ReadCh() {
    char ch = Advance();
    while (!isalpha(ch))
        ch = Advance();
    return ch;
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    if (a + b - 1 > n) {
        printf("-1\n");
        return 0;
    }
    if (1LL * a * b < n) {
        printf("-1\n");
        return 0;
    }
    int r = n - a, x = 0;
    for (int i = 1; i <= a; i++) {
        int add = min(b - 1, r);
        r -= add;
        for (int j = x + add + 1; j > x; j--)
            printf("%d ", j);
        x += add + 1;
    }
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define ft first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=1e5+7;
static const ll MOD=1e9+7;
ll max(ll a, ll b) {return a>b?a:b;}
ll min(ll a, ll b) {return a<b?a:b;}



int main(void) {
  ll N;
  cin >> N;
  ll a[MAX]={}, b[MAX]={};
  ll h[MAX]={};
  ll i;
  
  ll ma=0, mb=0;
  for(i=1; i<=N; i++) {
    cin >> a[i];
    chmax(ma, a[i]);
  }
  for(i=1; i<=N; i++) {
    cin >> b[i];
    chmax(mb, b[i]);
  }
  
  if(ma!=mb) {
    pt(0);
    return 0;
  }
  
  ll H=ma;
  ll ida=0, idb=0;
  for(i=1; i<=N; i++) {
    if(a[i]==H) {
      ida=i;
      break;
    }
  }
  
  for(i=N; i>=1; i--) {
    if(b[i]==H) {
      idb=i;
      break;
    }
  }
  
  if(idb<ida) {
    pt(0);
    return 0;
  }
  
  ll ans=1;
  for(i=1; i<ida; i++) {
    if(a[i-1]==a[i]) {
      moC(ans, *, a[i]);
    }
  }
  
  for(i=ida+1; i<=idb-1; i++) {
    moC(ans, *, H);
  }
  
  for(i=N; i>idb; i--) {
    if(b[i]==b[i+1]) {
      moC(ans, *, b[i]);
    }
  }
  
  pt(ans);
}








Measured memory_bytes: 1792
package main

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

func main() {
	x := nextInt()
	var c int
	for i := 100; i < x; i += int(float64(i) * 0.01) {
		c++
	}

	fmt.Println(c)
}

// =================================
// I/O util
// =================================

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

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

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


Measured memory_bytes: 1756
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M,K = IL()
a = IL()
b = IL()

ruia = [0]
for i in range(N):
  ruia.append(ruia[-1] + a[i])

ruib = [0]
for i in range(M):
  ruib.append(ruib[-1] + b[i])

r = N
l = 0
ans = 0
for l in range(M+1):
  while ruia[r] + ruib[l] > K:
    r -= 1
    if r == -1:
      break  
  cnt = r+l
  ans = max(ans, cnt)
  if r == -1:
    break
print(ans)

Measured memory_bytes: 137124
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
int error(vector<int> A,int x){
    int sum = 0;
    for(auto i:A){
        sum += (i - x) * (i - x);
    }
    return sum;
}
main(){
    int N;
    cin >> N;
    vector<int> A(N);
    int sum = 0;
    rep(i,0,N){
        cin >> A[i];
        sum += A[i];
    }
    int ave = sum / N;
    cout << min({error(A,ave) , error(A,ave+1)}) << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = Integer.parseInt(scan.nextLine());
		String S = scan.nextLine();
		int ans = 0;
		String tmpS;

		for (int i = 0; i + ans <= S.length(); i++) {
			boolean exist = true;
			while (exist) {
				if (i + ans + 1 > S.length()) {
					break;
				}
				tmpS = S.substring(i, i + ans + 1);
				if (i + ans + 1 + tmpS.length() > S.length()) {
					break;
				}
				for (int j = i + ans + 1; j + tmpS.length() <= S.length(); j++) {
					String wkS = S.substring(j, j + tmpS.length());
					if (tmpS.equals(wkS)) {
						ans = Math.max(ans, tmpS.length());
						exist = true;
						break;
					}
					else {
						exist = false;
					}
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 348468
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<unsigned char, unsigned char> pcc;
typedef pair<double, double> pdd;
typedef vector<vector<ll>> matrix;

int l[100005];
ll pref[100005];
ll firstOdd[100005];
ll firstEven[100005];
int n, q;

void solve(int x) {
  int lhs = 0;
  int rhs = (n+1)/2;
  while(lhs != rhs) {
    int mid = (lhs+rhs+1)/2;
    int lastTaken = l[n-mid];
    if(lastTaken < x) {
      rhs = mid-1;
      continue;
    }
    int otherTaken = l[n-mid-(mid-1)];
    if(abs(x-otherTaken) > abs(x-lastTaken)) rhs = mid-1;
    else lhs = mid;
  }
  ll ret = 0;
  ret += pref[n] - pref[n-lhs];
  if(n%2) ret += firstEven[(n+1)/2-lhs];
  else ret += firstOdd[(n+1)/2-lhs];
  cout << ret << "\n";
}

void solve() {
  cin >> n >> q;
  for(int i = 0; i < n; i++) {
    cin >> l[i];
    pref[i+1] = pref[i] + l[i];
  }
  for(int i = 1; i < n; i += 2) {
    firstOdd[i/2+1] = firstOdd[i/2] + l[i];
  }
  for(int i = 0; i < n; i += 2) {
    firstEven[i/2+1] = firstEven[i/2] + l[i];
  }
  while(q--) {
    int x;
    cin >> x;
    solve(x);
  }
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ":" << "\n";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}


Measured memory_bytes: 3712
f :: [Int]->[[Int]]->Int
f ans []=length ans
f ans ((x:xs):ys)=f [e|e<-xs,e `elem` ans] ys

main = do
       e<-getLine
       es<-getContents
       let (n:m:[])=map read (words e)::[Int]
           xs = map (map read . words) (lines es)::[[Int]]
       putStrLn $ show $ f [1..m] xs

Measured memory_bytes: 1020
#include<iostream>
using namespace std;
 
int main(){
    int a, b;
    for(int i=0; i>=0; i++){
        cin >> a >> b;
        if(a==0 && b==0) break;
        for(int j=0; j<a; j++){
            for(int k=0; k<b; k++){
                if(j==0||k==0||j==a-1||k==b-1)
                    cout << "#";
                else
                    cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1152
import sys
input = sys.stdin.buffer.readline
from itertools import accumulate
from bisect import bisect_left

INF = 10 ** 18

N = int(input())
A = list(map(int, input().split()))

Acum = [0] + list(accumulate(A))
answer = INF

for i in range(2, N - 1):
  bpq = bisect_left(Acum,  (Acum[i] - Acum[0]) // 2)
  brs = bisect_left(Acum,  (Acum[N] - Acum[i]) // 2 + Acum[i])
  
  P1, Q1 = Acum[bpq] - Acum[0], Acum[i] - Acum[bpq]
  P2, Q2 = Acum[bpq - 1] - Acum[0], Acum[i] - Acum[bpq - 1]
  R1, S1 = Acum[brs] - Acum[i], Acum[N] - Acum[brs]
  R2, S2 = Acum[brs - 1] - Acum[i], Acum[N] - Acum[brs - 1]  
  
  tmp = []
  tmp.append(max(P1, Q1, R1, S1) - min(P1, Q1, R1, S1))
  tmp.append(max(P1, Q1, R2, S2) - min(P1, Q1, R2, S2))
  tmp.append(max(P2, Q2, R1, S1) - min(P2, Q2, R1, S1))
  tmp.append(max(P2, Q2, R2, S2) - min(P2, Q2, R2, S2))
  
  answer = min(answer, min(tmp))
  
print(answer)

Measured memory_bytes: 71408
n=int(input())
l=list(map(int,input().split()))
if n%2==0:
  a=0
else:
  a=1
for i in range((n+1)//2):
  print(l[n-2*i-1],end=' ')
for i in range(n//2):
  print(l[2*i+a],end=' ')

Measured memory_bytes: 26180
#!/usr/bin/env python
# coding: utf-8

# In[2]:


import math


# In[25]:


N,M = map(int, input().split())
S = input()
T = input()


# In[26]:


g = math.gcd(N,M)
for i in range(g):
    if S[(N//g)*i] != T[(M//g)*i]:
        print(-1)
        break
else:
    print(N*M//g)


# In[ ]:






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

using namespace std;

int main(){
    int w,h;
    while(true){
        cin >> w >> h;
        if(w == 0 && h == 0){
            break;
        }
        for(int i=0;i<w;i++){
            for(int y=0;y<h;y++){
                cout << "#";
            }
            cout << endl;
        }  
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3116
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
#include <cstdint>
using namespace std;
using LL = long long;

int N;
vector<pair<int, int>>vec;
int ans[123456];

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N - 1; ++i) {
		int B;
		cin >> B;
		vec.push_back({ B,i });
	}
	sort(vec.rbegin(), vec.rend());
	for (auto p : vec) {
		ans[p.second] = ans[p.second + 1] = p.first;
	}
	LL sum = 0;
	for (int i = 0; i < N; ++i) {
		sum += ans[i];
	}
	cout << sum << endl;
	return 0;
}

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

struct mint {
    ll x;

    mint(ll 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;
    }

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

const int N = 2005;
mint dp[N];

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

  dp[0] = 1;
  //それまでの合計がiで
  for (int i = 0; i <= s; i++) {
    //あらたにjを足すことになったときのとおり
    for (int j = 3; j <= s; j++) {
      if(i - j < 0) continue;
      dp[i] += dp[i - j];
    }
  }

  cout << dp[s].x << '\n';


}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>

typedef long long ll;
#define fi first
#define se second

using namespace std;

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

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


int N;
int a[112345];
int wa[112345];
int d = 0;
ll ans1 = 0;
ll ans2 = 0;
ll num = 0;

int main(){
  
  cin>>N;
  
  int i;
  
  for( i = 0; i < N; i++ ){
    scanf("%d", a+i);
  }
  
  wa[0] = a[0];
  
  for( i = 1; i < N; i++ ){
    wa[i] = wa[i-1] + a[i];
    //cout<<wa[i]<<endl;
  }
  
  int jdg = 1;
  
  d = 0;
  
  
  
  //負の数スタート
  for( i = 0; i < N; i++ ){
    num = wa[i] + d;
    if( jdg ){
      if( num >= 0 ){
        ans1 += num+1;
        d -= num + 1;
      }
      jdg = 0;
    }
    else{
      if( num <= 0 ){
        ans1 -= num - 1;
        d -= num - 1;
      }
      jdg = 1;
    }
   //cout<<ans1<<endl;
  }
  
  jdg = 0;
  d = 0;
  for( i = 0; i < N; i++ ){
    num = wa[i] + d;
    if( jdg ){
      if( num >= 0 ){
        ans2 += num+1;
        d -= num+1;
      }
      jdg = 0;
    }
    else{
      if( num <= 0 ){
        ans2 -= num-1;
        d -= num-1;
      }
      jdg = 1;
    }
    //cout<<num<<endl;
  }
  
  if( ans1 < ans2 ){
    cout<<ans1<<endl;
  }
  else{
    cout<<ans2<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 1024
//Date:06-01-17
 
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<float.h>
#include<math.h>
#include<ctype.h>
#include<limits.h>
#include<time.h>
#define ll long long
#define For(i,n)	for(i=0;i<n;i++)
#define rep(i ,a ,b)	for(i=(a);i<=(b);i++)
#define mset(a ,value)	memset(a ,value ,sizeof(a))
#define s(a)	scanf("%d" ,&a);
#define ls(a)	scanf("%ld" ,&a)
#define reg(i)	register int i
#define infinite INT_MAX
#define MAX 100005
#define NIL -1
int min(int a,int b){	return (a<b?a:b);	}
int max(int a,int b){	return (a>b?a:b);	}
/*main(){
	int sx ,sy ,tx ,ty;
	scanf("%d%d%d%d" ,&sx ,&sy ,&tx ,&ty);
	int x=sx ,y = sy;
	while(y!=ty){	printf("U");	y++;	}
	while(x!=tx){	printf("R");	x++;	}
	while(y!=sy){	printf("D");	y--;	}
	while(x!=sx){	printf("L");	x--;	}
	printf("L");	x--;
	while(y!=(ty+1)){	printf("U");	y++;	}
	while(x!=tx){	printf("R");	x++;	}
	printf("D");	y--;
	printf("R");	x++;
	while(y!=(sy-1)){	printf("D");	y--;}
	while(x!=sx){	printf("L");	x--;	}
	printf("U");	y++;
	assert((x==sx)&&(y==sy));
	return 0;
}*/
main(){
	int k ,s ,x ,y ,z ,c=0;
	scanf("%d %d" ,&k ,&s);
	rep(x ,0 ,k)
		rep(y ,0 ,k){
				z = s-(x+y);
				if(z>=0&&z<=k)	c++;
	}
	printf("%d" ,c);
	return 0;
}

Measured memory_bytes: 128
package main

import (
	"fmt"
	"os"
	"bufio"
	"strconv"
  	"sort"
)
func main(){
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
  	loopNum, _ := strconv.Atoi(sc.Text())
  	
  	mochiList := make([]int, 0)
  	
  	for i:=0; i<loopNum; i++ {
  	    sc.Scan()
  	    diameter, _ := strconv.Atoi(sc.Text())
  	    mochiList = append(mochiList, diameter)
  	}
  	sort.Ints(mochiList)
  	
  	count := 0
  	nowMochi := 0
  	for _, m := range mochiList {
  	    if nowMochi < m {
  	        count++
  	        nowMochi = m
  	    }
  	}
  	
  	fmt.Println(count)
}

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<int,int>
using namespace std;
const int maxn = 1100;
char matrix[maxn][maxn];
int dist[maxn][maxn], n, m;
bool visited[maxn][maxn];

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int main() {
    cin>>n>>m;
    queue<pair<int,int> > q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>matrix[i][j];
            if(matrix[i][j] == '#') {
                visited[i][j] = true;
                q.push(mp(i,j));
            }
        }
    }

    int max_dist = 0;
    while(!q.empty()) {
        P curr = q.front();
        q.pop();

        max_dist = max(max_dist, dist[curr.first][curr.second]);

        for(int d=0;d<4;d++) {
            if(curr.first + dx[d] >= 1 && curr.first + dx[d] <= n && curr.second + dy[d] >= 1 && curr.second + dy[d] <= m) {
                if(!visited[curr.first+dx[d]][curr.second+dy[d]]) {
                    visited[curr.first+dx[d]][curr.second+dy[d]] = true;
                    dist[curr.first+dx[d]][curr.second+dy[d]] = dist[curr.first][curr.second] + 1;
                    q.push(mp(curr.first+dx[d], curr.second+dy[d]));
                }
            }
        }
    }
    cout<<max_dist<<"\n";
    return 0;
}

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

using ll=long long; 

void solve(){
	int n;
	cin>>n;
	vector<int> a(n);
	for(auto& e:a)cin>>e;
	cout<<*max_element(a.begin(), a.end())-*min_element(a.begin(), a.end())<<endl;
	
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 256
#include <iostream>

int main(void){
    int year;
    std::cin >> year;
    char trash;
    std:: cin >> trash;
    int month;
    std::cin >> month;
    std:: cin >> trash;
    int day;
    std::cin >> day;

    if(year < 2019){
        std::cout << "Heisei";
        return 0;
    }
    else if(year > 2019){
        std::cout << "TBD";
        return 0;
    }
    // year == 2019
    else{
        if(month <= 4){
            std::cout << "Heisei";
            return 0;
        }
        else if(month > 4){
            std::cout << "TBD";
            return 0;
        }
    }
}

Measured memory_bytes: 256
N, K = map(int, input().split())

MOD = 10 ** 9 + 7

ans = 0
for k in range(K, N + 2):
    min_ = k * (k - 1) // 2
    max_ = ((N + (N - k + 1)) * k) // 2
    ans += (max_ - min_ + 1)
    ans %= MOD

print (ans)

Measured memory_bytes: 9188