akhauriyash/Code-Regression huggingface dataset:
let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  Printf.printf "%d\n" @@
  fst @@
  Array.fold_left (fun (sum, prev) a ->
    sum + max prev a - a, max prev a) (0, min_int) as_



Measured memory_bytes: 7536
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<class F>auto recursive(F f){return[f](auto...a){return f(f,a...);};}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int p;fixprec(int p):p(p){}};
ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.p);}

int main() {
    int N, M, lK;
    i64 K;
    cin >> N;
    vector<i64> x(N), dx(N - 1), y(N);
    for(i64 &x_ : x) cin >> x_;
    for(int i = 0; i < N - 1; i++) {
        dx[i] = x[i + 1] - x[i];
    }
    cin >> M >> K;
    vector<int> perm_base(N - 1), perm_ans(N - 1), perm_tmp(N - 1);
    for (int i = 0; i < N - 1; i++) {
        perm_base[i] = perm_ans[i] = i;
    }
    for(int i = 0; i < M; i++) {
        int a;
        cin >> a;
        a--;
        swap(perm_base[a - 1], perm_base[a]);
    }
    // 繰り返し二乗法
    for(int b = 0; (1ll << b) <= K; b++) {
        if (K & (1ll << b)) {
            for (int i = 0; i < N - 1; i++) {
                perm_ans[i] = perm_base[perm_ans[i]];
            }
        }
        for (int i = 0; i < N - 1; i++) perm_tmp[i] = i;
        for (int i = 0; i < N - 1; i++) {
            perm_tmp[i] = perm_base[perm_base[i]];
        }
        swap(perm_tmp, perm_base);
    }
    for(int i = 0; i < N; i++) {
        y[i] = i ? dx[perm_ans[i - 1]] + y[i - 1] : x[0];
        cout << y[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 4736
fun main(args: Array<String>) {
    val list = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(", ").map(String::toInt)
    val k = readLine()!!.toInt()
    println(list[k - 1])
}

Measured memory_bytes: 37676
#include<cmath>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstdio>
#include<map>
#include<utility>
#include<list>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fori(i,k,n) for(int i=k;i<(int)n;i++)
using namespace std;
const int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
const int dX[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }, dY[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
/*
(char)'1' - (int)48 = (int)1;


*/
list<int> seito;
bool ans[200001] = {false};
int main()
{
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++)seito.push_back(i);
	list<int>::iterator it = seito.begin();
	while (m--)
	{
		int x;
		cin >> x;
		if (x % 2==0)
		{
			for (int i = 0; i < x; i++)
			{
				it++;
				if (it == seito.end())it = seito.begin();
			}
		}
		else
		{
			for (int i = 0; i < x; i++)
			{
				if (it == seito.begin())
				{
					it = seito.end();
					it--;
				}
				else
				{
					it--;
				}
			}
		}
		ans[*it] = true;
		if (it == seito.end())
		{
			it = seito.erase(it);
			it = seito.begin();
		}
		else it = seito.erase(it);
		if (it == seito.end())it = seito.begin();
	}
	/*
	it = seito.begin();
	for (int i = 0; i < seito.size(); i++)
	{
		cout << *it << endl;
		it++;
	}
	*/
	
	while (q--)
	{
		int x;
		cin >> x;
		if (ans[x])cout << 0 << endl;
		else cout << 1 << endl;
	}
	
}

Measured memory_bytes: 7636
/* Author: $%U%$
 * Time: $%Y%$-$%M%$-$%D%$ $%h%$:$%m%$:$%s%$
**/
#include <bits/stdc++.h>
using namespace std;
#define fore(i, a, b) for (int i = a, to = b; i < to; i++)
#define foref(i, a, b) for (int i = b - 1, to = a; i >= to; i--)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define SZ(v) (int)v.size()
#define pb push_back
typedef long long Long;
typedef pair<int, int> Pair;
const int MX = (1e6);
Long vis[MX + 2];
void update(Long x) {
  if (vis[x] > 2) return;
  for (Long i = x; i <= MX; i += x) {
    vis[i]++;
  }
}
void solve() {
  int n;
  cin >> n;
  vector<int> v(n);
  fore(i, 0, n) cin >> v[i];
  fore(i, 0, n) update(v[i]);
  int ans = 0;
  fore(i, 0, n) {
    if (vis[v[i]] == 1) {
      ans++;
    }
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);
  int t = 1;
  //cin >> t;
  while (t--) solve();

  return 0;
}

Measured memory_bytes: 11864
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
int a[2000001],n,p;
ll ans,cnt;
int main() 
{
	cin>>n;
	for(re int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>i-1) {
			cout<<"-1";
			return 0;
		}
	}
	ans=a[n];
	cnt=a[n];
	a[1]=-1;
	for(re int i=n-1;i>=2;i--){
		if(cnt-a[i]>1) {
			cout<<"-1";
			return 0;
		}
		if(cnt!=a[i]+1){
			ans+=a[i];
		}
		cnt=a[i];
	}
	cout<<ans;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get(ll x)
{
    return x*x*x*x*x;
}
int main()
{
    ll x;
    cin >>x;
    for(ll i=-500;i<=500;i++)
    {
        int flag=0;
        for(ll j=-500;j<=500;j++)
        {
            if(get(i)-get(j)==x)
            {
                flag=1;
                cout <<i<<" "<<j<<endl;
                break;
            }
        }
        if(flag) break;
    }
}

Measured memory_bytes: 3632
A = list(map(int, input().split()))

min_cost = sum(A)
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i != j and i != k and j != k:
                cost = abs(A[j]-A[i])+abs(A[k]-A[j])
                min_cost = min(min_cost, cost)
print(min_cost)


Measured memory_bytes: 3060
#include "bits/stdc++.h"

using namespace std;

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    if (a[a.length()-1] == b[0] && b[b.length()-1] == c[0]) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
abc = input()
abc_int = int(abc)
ququ = []
checksum = 0
for count1 in range(9):
    for count2 in range(9):
        ququ.append((count1+1)*(count2+1))
for check in ququ:
    if check == abc_int:
        checksum = 1
if checksum == 0:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,a,b;
	cin>>n>>m>>a>>b;
	long long kpk=(a*b)/__gcd(a,b);
	long long terbagi=0;
	long long tempa,tempb,tempc;
	tempa=(m/a)-(n/a)+((n%a==0));
	tempb=(m/b)-(n/b)+((n%b==0));
	tempc=(m/kpk)-(n/kpk)+((n%kpk==0));
	long long ans=(tempa+tempb)-tempc;
	long long sel=(m-n)+1;
	cout<<sel-ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const long long INF = 1e18+10;

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

signed main(){
	int n;
	cin>>n;
	map<int,int> mp;

	rep(i,n){
		int a;cin>>a;
		mp[a]=1-mp[a];
	}
	int ans=0;

	for(auto p:mp){
		ans+=p.second;
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 9752
a = [int(input())for i in range(5)]
b = int(input())
for i in range(5):
    for j in range(5):
        if i != j:
            if i < j:
                if a[j] - a[i] > b:
                    print(":(")
                    exit()
            else:
                if a[i] - a[j] >  b:
                    print(":(")
                    exit()
print("Yay!")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	ll x;
	ll ans=0;

	cin>>x;
	ans=x;

	ll total=0;
	for(ll i=1; i<x+1; i++){
		total+=i;
		if(total>=x){
			cout<<i<<endl;
			return 0;
		}
	}

	return 0;
}


Measured memory_bytes: 256
N = int(input())
a = [0] + list(map(int, input().split()))
ans = [0] * (N + 1)
an = []
for i in range(N, 0, -1):
	if sum(ans[i * 2 :: i]) % 2 != a[i]:
		ans[i] = 1
		an.append(i)
print(len(an))
Ans = [str(x) for x in an]
print(' '.join(Ans))

Measured memory_bytes: 22368
var n: string;
sum,sum1: longint;
begin
read(n);
val(n[1]+n[2],sum);
val(n[3]+n[4],sum1);
if (sum>0) and (sum<=12) and (sum1>0) and (sum1<=12) then
write('AMBIGUOUS') else
if (sum<=12) and (sum>0) then write('MMYY') else if (sum1<=12) and (sum1>0) then
write('YYMM') else write('NA');
end.


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
#define el putchar('\n')
#define ta putchar('	')
using namespace std;
typedef long long ll;
inline void open(const char *s)
{
	#ifndef ONLINE_JUDGE
	char str[20];
	sprintf(str,"%s.in",s);
	freopen(str,"r",stdin);
//	sprintf(str,"%s.out",s);
//	freopen(str,"w",stdout);
	#endif
}
inline int rd()
{
	static int x,f;
	x=0;f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return f>0?x:-x;
}
const int N=100010,mod=1000000007;
int n,cnt[27];
char s[N];

int main()
{
	n=rd();
	scanf("%s",s+1);
	fo(i,1,n)++cnt[s[i]-'a'];
	ll ans=1;
	fo(i,0,25)(ans*=(cnt[i]+1))%=mod;--ans;
	if(ans<0)ans+=mod;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 384
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
r = 0

for i in range(n):
	if a[i]+a[i+1] >= b[i]:
		r += b[i];
		if a[i] < b[i]:
			a[i+1] -= b[i]-a[i]
	else:
		r += a[i]+a[i+1]
		a[i+1] = 0

print(r)


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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl;
#define CNO cout<<"No"<<endl;

typedef long long LL;
typedef long double LD;

int main(){
  int n,k;
  cin >> n >> k;
  cout << n -k+1 << endl;
  return 0;
}


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

int main() {
    int n;
    cin >> n;
    pair<int, int> r[n];
    pair<int, int> b[n];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &r[i].first, &r[i].second);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &b[i].first, &b[i].second);
    }
    sort(r, r + n);
    sort(b, b + n);
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (r[i].first != r[i-1].first) continue;
            if (r[i].second < r[i-1].second) {
                swap(r[i].first, r[i-1].first);
                swap(r[i].second, r[i-1].second);
            }
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (b[i].first != b[i-1].first) continue;
            if (b[i].second < b[i-1].second) {
                swap(b[i].first, b[i-1].first);
                swap(b[i].second, b[i-1].second);
            }
        }
    }
    bool rb[n], bb[n];
    for (int i = 0; i < n; i++) {
        rb[i] = bb[i] = false;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (bb[i]) continue;
        int ri = -1, max = -1;
        for (int j = 0; j < n; j++) {
            if (b[i].first < r[j].first) break;
            if (rb[j]) continue;
            if (b[i].second < r[j].second) continue;
            if (max <= r[j].second) {
                max = r[j].second;
                ri = j;
            }
        }
        if (ri == -1) continue;
        ans++;
        bb[i] = rb[ri] = true;
    }
    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    string s;
    int  k;
    cin>>s>>k;
    int count = 0;
//    long long int count = 0;
//    for (int i =0; i< s.length(); i++){
//        if (s[i]=='1'){
//            count++;
//            continue;
//        }
//        int temp = s[i]-'0';
//        count+=temp*5*pow(10, 15);
//        if (count>=k){
//            cout << s[i]<<endl;
//            break;
//        }
//
//    }
    for (int i =0; i< s.length(); i++){
        if (s[i]=='1'){
            count++;
            if (count ==k){
                cout <<'1';
                break;
            }
        }
        else{
            cout << s[i];
            break;
        }
    }
    
    
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
	int a;
	int b;
	int N;

	cin >> N;



	if (N <= 81) {
		for (int i = 1; i <= 9; i++) {
			if (N % i == 0) {
				if (N / i <= 9) {
					cout << "Yes";
					return 0;
				}

			}
		}

	}

	cout << "No";

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <climits>
#include <utility>
#include <deque>
#include <list>
using namespace std;

int main()
{
	cout << fixed << setprecision(6);
	string s;
	cin >> s;
  
	sort(s.begin(), s.end());
	cout << (s[0] == s[1] && s[1] != s[2] && s[2] == s[3] ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
<?php
  $a = trim(fgets(STDIN));
  $b = trim(fgets(STDIN));
  $c = trim(fgets(STDIN));
  $x = trim(fgets(STDIN));
  $count = 0;
  $sum = 0;
  for($i=0; $i<=$a; $i++){
    for($j=0; $j<=$b; $j++){
      for($k=0; $k<=$c; $k++){
        $sum = ($i*500)+($j*100)+($k*50);
        if($x == $sum){
          $count++;
        }
      }
    }
  }
  echo $count."\n";

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

int main(void)
{
    int n; cin >> n;
    map<string, int> memo;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        memo[s]++;
    }

    int best = 0;
    for (auto x:memo)
        best = max(best, x.second);
    for (auto it = memo.begin(); it != memo.end(); it++)
    {
        if (it->second == best)
            cout << it->first << endl;
    }
}

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

typedef long long ll;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)
#define mod 1000000007

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

    if(a>=3200){
        cout<<s<<endl;
    }
    else{
        cout<<"red"<<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);cout.tie(NULL);
        string s;
        cin>>s;
        if(s[s.length()-1]=='s') s+="es";
        else s+="s";
        cout<<s;
return 0;
}
/*

        creation time:  20.09.2020 12:21:18

*/                      



Measured memory_bytes: 3648
# abc123 A
a = [gets.to_i]
a << gets.to_i
a << gets.to_i
a << gets.to_i
a << gets.to_i
k = gets.to_i

puts a.combination(2).to_a.all? {|(x,y)|
  (x - y).abs <= k
} ? 'Yay!' : ':('



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

const int MaxN = 1e5 + 15;
const int MOD = 1e9 + 7;

string s;

vector <int> ans;

void rec(int pos, int sum)
{
    if(pos == 4)
    {
        if(sum == 7)
        {
            cout << ans[0];
            for(int i = 1; i < ans.size(); ++i)
            {
                if(ans[i] >= 0)
                    cout << '+';
                cout << ans[i];
            }
            cout << '=' << 7 << '\n';
            exit(0);
        }
        return;
    }

    ans.push_back(s[pos] - '0');
    rec(pos + 1, sum + s[pos] - '0');
    ans.pop_back();

    ans.push_back(-s[pos] + '0');
    rec(pos + 1, sum - s[pos] + '0');
    ans.pop_back();
}

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

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s;

    ans.push_back(s[0] - '0');

    rec(1, s[0] - '0');
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp13
{
    class Program
    {
        static void Main(string[] args)
        {
            int ass = int.Parse( Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            bool iuu = true;
            for(int i=0; i<ass; i++)
            {
                if(int.Parse(str[i]) %2 == 0)
                {
                    if(int.Parse(str[i]) %3 ==0 || int.Parse(str[i]) % 5 == 0)
                    {
                        iuu = true;
                    }
                    else
                    {
                        iuu = false;
                        break;
                    }
                }
                if (!iuu)
                {
                    break;
                }
            }
            if (iuu)
            {
                Console.WriteLine("APPROVED");
            }
            else
            {
                Console.WriteLine("DENIED");
            }
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,M;
  string S,T;
  cin>>N>>M>>S>>T;
  int K=__gcd(N,M);
  for(int i=0;i<K;i++)
    if(S[N/K*i]!=T[M/K*i]){
      puts("-1");
      return 0;
    }
  cout<<N/K*M<<endl;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
void rd(long long &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(long long x){
  char f[20];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
int main(){
  long long A, B, C, res;
  rd(A);
  rd(B);
  rd(C);
  res = B +min_L(A+B+1, C);
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20180730-1

// --- original code ---
// {
//   ll A, B, C, res;
//   rd(A,B,C);
//   res = B + min(A+B+1, C);
//   wt(res);
// }


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

int main(){
  int n, m;
  cin >> n >> m;
  Graph g(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  
  vector<int> dist(n, -1);
  queue<int> que;
  dist[0] = 0;
  que.push(0);
  while(!que.empty()){
    int v = que.front();
    que.pop();
    for(int nv : g[v]){
      if (dist[nv] != -1) continue;
      dist[nv] = v;
      que.push(nv);
    }
  }
  
  bool flag = false;
  rep(i, n){
    if (dist[i] == -1) flag = true;
  }
  
  if (flag) cout << "No" << endl;
  else{
    rep(i, n){
      if (i == 0) cout << "Yes" << endl;
      else cout << dist[i] + 1 << endl;
    }
  }
  
  
  return 0;
}

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

using namespace std;
typedef long long ll;

const int N=300;
vector<vector<vector<double>>> dp(N+2,vector<vector<double>>(N+2,vector<double>(N+2,-2)));

double solve(int x,int a,int b,int c)
{
    if(dp[a][b][c]>-1) return dp[a][b][c];
    dp[a][b][c]=1;
    double s=(x+a+b+c);
    if(a>0) dp[a][b][c]+=((a/s)*solve(x+1,a-1,b,c));
    if(b>0) dp[a][b][c]+=((b/s)*solve(x,a+1,b-1,c));
    if(c>0) dp[a][b][c]+=((c/s)*solve(x,a,b+1,c-1));
    dp[a][b][c]/=(1-(x/s));
    return dp[a][b][c];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> cnt(4,0);
    for(int i=0;i<n;i++)
    {
        int a;
        cin >> a;
        cnt[a]++;
    }
    dp[0][0][0]=0;
    cout << fixed << setprecision(14) << solve(0,cnt[1],cnt[2],cnt[3]) << "\n";
    return 0;
}


Measured memory_bytes: 219776
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#pragma warning(disable : 4996)
using namespace std;
int n, a[300009]; long long dpl[300009], dpr[300009];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < 3 * n; i++) scanf("%d", &a[i]);
	priority_queue<int> que1, que2;
	for (int i = 0; i < 3 * n; i++) {
		que1.push(-a[i]); dpl[i + 1] = dpl[i] + a[i];
		while (que1.size() > n) dpl[i + 1] += que1.top(), que1.pop();
	}
	for (int i = 3 * n - 1; i >= 0; i--) {
		que2.push(a[i]); dpr[i] = dpr[i + 1] + a[i];
		while (que2.size() > n) dpr[i] -= que2.top(), que2.pop();
	}
	long long ret = -1LL << 60;
	for (int i = n; i <= 2 * n; i++) ret = max(ret, dpl[i] - dpr[i]);
	printf("%lld\n", ret);
	return 0;
}

Measured memory_bytes: 7032
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;
	int cont = 1;
	vector<pair<int, int> > seq;
	for (int i = 1; i <= N; ++i) {
		if (i == N || S[i] != S[i - 1]) {
			seq.push_back(make_pair(S[i - 1] - '0', cont));
			cont = 0;
		}
		++cont;
	}
	vector<int> sum(seq.size() + 1);
	for (int i = 0; i < seq.size(); ++i) {
		sum[i + 1] = sum[i] + seq[i].second;
	}
	int ans = 0;
	for (int i = 0; i < seq.size(); ++i) {
		int ptr = min(i + 2 * K + seq[i].first, int(seq.size()));
		ans = max(ans, sum[ptr] - sum[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4616
#include<iostream>
using namespace std;
int main(){
    int n,i,j,sum=0;
    cin>>n;
    int b[n-1];
    for(i=0; i<n-1;i++)
    {
        cin>>b[i];
    }
    int a[n];
    a[0]= b[0];
    for(i=1; i<n; i++){
        if(b[i]>b[i-1])
        {
            a[i]=b[i-1];
        }
        else
        a[i]= b[i];
    }
    a[n-1]= b[n-2];
      for(j=0; j<n; j++){
        sum =sum+ a[j];
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;

int main()
{
	const double PI=3.14159265358979323846;
	double R;
	cin>>R;
	cout<<2*PI*R<<endl;
	return 0;
}



Measured memory_bytes: 3784
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mt make_tuple
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
typedef ll SegT;
class SegTree{
	private:
		vector<SegT>val;
		ll n,defvalue;
		SegT combine(SegT a,SegT b){return defvalue==INF?min(a,b):max(a,b);}
	public:
		SegTree(ll size,ll a){
			defvalue=a;
			n=1;
			while(n<size)n<<=1;
			val=vector<SegT>(2*n,defvalue);
		}
		SegTree(const vector<SegT> &in,ll a){
			n=1;
			defvalue=a;
			while(n<in.size())n<<=1;
			val=vector<SegT>(2*n,defvalue);
			for(ll i=n-1+in.size()-1;i>=0;i--){
				if(n-1<=i)val[i]=in[i-(n-1)];
				else val[i]=combine(val[i*2+1],val[i*2+2]);
			}
		}
		void update(ll i,SegT a){
			i+=n-1;
			val[i]=a;
			while(i>0){
				i=(i-1)/2;
				val[i]=combine(val[i*2+1],val[i*2+2]);
			}
		}
		SegT query(ll a,ll b,ll k=0,ll l=0,ll r=-1){//[a,b)
			if(r==-1)r=n;
			if(r<=a||b<=l)return defvalue;
			if(a<=l&&r<=b)return val[k];
			else return combine(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
		}
		void tmp(){
			rep(i,val.size())cout<<" "<<val[i];cout<<endl;
		}
};
int main(){
	ll out=INF;
	int n;
	vp in;
	cin>>n;
	in=vp(n);
	
	rep(i,n){
		ll a,b;
		cin>>a>>b;
		if(a<b)swap(a,b);
		in[i]=pii(a,b);
	}
	sort(all(in));
	vi A(n),B(n);
	rep(i,n){
		A[i]=in[i].first;
		B[i]=in[i].second;
	}
	SegTree st1(A,INF),st2(A,-INF),st3(B,INF),st4(B,-INF);
	out=(st1.query(0,n+1)-st2.query(0,n+1))*(st3.query(0,n+1)-st4.query(0,n+1));
	for(int i=n-1;i>=0;i--){
		st1.update(i,in[i].second);
		st2.update(i,in[i].second);
		st3.update(i,in[i].first);
		st4.update(i,in[i].first);
		
		out=min(out,(st1.query(0,n+1)-st2.query(0,n+1))*(st3.query(0,n+1)-st4.query(0,n+1)));
	}
	cout<<out<<endl;
}











Measured memory_bytes: 22912
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

enum EventType { End_rw, Person, Start_rw };

struct Event {
  EventType type;  // Start/End roadwork or Person walk
  int64_t t;  // Time of event
  int64_t x;  // Distance in the road
  int64_t inter; // Intercept
  
  Event(EventType _type, int64_t _t, int64_t _x) {
    type = _type;
    t = _t;
    x = _x;
    inter = t - x;
  }

  friend bool operator<(const Event &lhs, const Event &rhs) {
    if (lhs.inter == rhs.inter) {
      return lhs.type < rhs.type;
    }
    return lhs.inter < rhs.inter;
  }
};

int main() {
  
  int64_t n, q;
  std::cin >> n >> q;
  std::vector<Event> events;
  std::set<int64_t> activeBarriers;

  int64_t s, t, x;
  for (auto i=0; i < n; ++i) {
    std::cin >> s >> t >> x;
    events.emplace_back(Start_rw, 2*s-1, 2*x);
    events.emplace_back(End_rw, 2*t-1, 2*x);
  }

  int64_t d;
  for (auto i=0; i < q; ++i) {
    std::cin >> d;
    events.push_back(Event(Person, 2*d, 0));
  };

  std::sort(events.begin(), events.end());

  for (Event event:events) {
    if (event.type == Start_rw) {
      activeBarriers.insert(event.x);
    } else if (event.type == Person) {
      auto distance = activeBarriers.begin();
      if (distance == activeBarriers.end()) {
        std::cout << -1 << '\n';
      } else {
        std::cout << (*distance)/2 << '\n';
      }
    } else if (event.type == End_rw) {
      activeBarriers.erase(event.x);
    }
  }
  
  return 0;
}

Measured memory_bytes: 34660
#include <bits/stdc++.h>
using namespace std;
void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail) != 0)
        cout << " ";
    print(forward<Tail>(tail)...);
}
template <class T>
void print(vector<T> &vec) {
    for (auto &a : vec) {
        cout << a;
        if (&a != &vec.back())
            cout << " ";
    }
    cout << endl;
}
template <class T>
void print(vector<vector<T>> &df) {
    for (auto &vec : df) {
        print(vec);
    }
}
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define xrep(i, a, b) for (int i = int(a); i < int(b); ++i)
using ll = long long;
const int INF = 1001001001;



int main() {
    int N;
    cin >> N;
    vector<int> A;
    A.push_back(INF);
    rep(i, N) {
        int a;
        cin >> a;
        A.push_back(a);
    }
    int cnt = 0;
    xrep(i, 1, N+1) {
        if(i%2==1 && A[i]%2==1) {
            cnt++;
        }
    }
    print(cnt);

    return 0;
}

Measured memory_bytes: 3512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,sum=0;
  cin>>a>>b;
  
  for(int i=a; i<=b; i++){
    if(i/10000==i%10&&(i/1000)%10==(i%100)/10){
      sum++;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
local mod = 998244353
local mfl = math.floor

local function bmul(x, y)
  return (x * y) % mod
end

local function badd(x, y)
  return (x + y) % mod
end

local function bsub(x, y)
  return x < y and x - y + mod or x - y
end

local function modpow(src, pow)
  local res = 1
  while 0 < pow do
    if pow % 2 == 1 then
      res = bmul(res, src)
      pow = pow - 1
    end
    src = bmul(src, src)
    pow = mfl(pow / 2)
  end
  return res
end

local function modinv(src)
  return modpow(src, mod - 2)
end

local fact = {1}
local invs = {1}
local invfact = {1}
for i = 2, 300010 do
  fact[i] = bmul(fact[i - 1], i)
  invs[i] = bmul(mfl(mod / i), mod - invs[mod % i])
  invfact[i] = bmul(invfact[i - 1], invs[i])
end

local function getComb(n, k)
  if k == 0 or k == n then return 1 end
  return bmul(fact[n], bmul(invfact[k], invfact[n - k]))
end

local ret = 0
local n, a, b, k = io.read("*n", "*n", "*n", "*n")
for ai = 0, n do
  local acomb = getComb(n, ai)
  local rem = k - ai * a
  if 0 <= rem and rem % b == 0 and rem // b <= n then
    local bi = rem // b
    local bcomb = getComb(n, bi)
    ret = badd(ret, bmul(acomb, bcomb))
  end
end
print(ret)


Measured memory_bytes: 24952
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

int a, b, c, d;

int main(){
	//IO("input.txt", "output.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> a >> b >> c >> d;
	cout << max(a * b, c * d) << "\n";
	return 0;
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8'); 
var lines = [];
var reader = require('readline').createInterface({
	input: process.stdin,
	output: process.stdout
});
 
reader.on('line', (line) => {
	lines.push(line);
});

reader.on('close', () => {
	const meals = lines.map(Number);
	
	const shortenTime = meals.reduce((cur, next) => Math.max(cur, (10-next%10)%10 ), 0);
	
	console.log(meals.reduce((cur, next) => cur + Math.ceil(next/10)*10, 0) - shortenTime);
});

Measured memory_bytes: 7628
#define _CRT_SECURE_NO_WARNINGS
#define forn(i, a, n) for(ll i = a; i < n; i++)

#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<iomanip>
#include<cassert>
#include<stack>
#include<deque>
#include<list>
#include<sstream>
#include<unordered_map>
#include<time.h>
#include<functional>
#pragma comment(linker, "/STACK:8809999999")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<ld, ld> pld;
typedef pair<ll, pll> pllp;
typedef pair<pll, ll> ppll;
typedef pair<pll, pll> ppp;
typedef vector<vector<vector<ll>>> vvv;
const ll mod = 1e9 + 7;
const ll atcmod = 998244353;
const ld eps = 1e-9;
const ll settled = 400007;


int main()
{
	ios_base::sync_with_stdio(false); cout.tie(NULL);
#ifndef overlord
	/*freopen("capitals.in", "r", stdin);
	freopen("capitals.out", "w", stdout);*/
#else
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll n;
	cin >> n;
	vector<string> st(n);
	forn(i, 0, n)
		cin >> st[i];
	
	ll a = 0, b = 0, ab = 0;

	forn(i, 0, n)
	{
		if (st[i][0] == 'B' && st[i].back() == 'A')
		{
			ab++;
			continue;
		}

		if (st[i][0] == 'B')
			b++;

		if (st[i].back() == 'A')
			a++;
	}

	ll ans = 0;
	ans += max((ll)0, ab - 1);
	if (ab > 0 && a > 0)
	{
		a--;
		ans++;
	}

	if (ab > 0 && b > 0)
	{
		b--;
		ans++;
	}

	ans += min(a, b);

	for (string s : st)
	{
		forn(i, 0, s.size() - 1)
		{
			if (s[i] == 'A' && s[i + 1] == 'B')
				ans++;
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define inf 0x3f3f3f3f
using namespace std;

const int maxn = 100050;

int n,m;

bool vis[maxn][4];
vector<int>G[maxn];

struct node{
    int v,p;
};

int bfs(int s,int t){
    queue<node>q;
    q.push(node{s,0});
    while(!q.empty()){
        node u=q.front();q.pop();
        if(vis[u.v][u.p%3])continue;
        vis[u.v][u.p%3]=1;
        if(u.v==t&&u.p%3==0)return u.p/3;
        for(auto v:G[u.v]){
            q.push(node{v,u.p+1});
        }
    }
    return -1;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        G[x].push_back(y);
    }
    int s,t;
    scanf("%d%d",&s,&t);
    int ans=bfs(s,t);
    cout<<ans<<endl;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int K,A,B;
    cin>>K>>A>>B;
    for(int i=0;K*i<=B;i++){
        if(A<=K*i){
            cout<<"OK"<<endl;
            return 0;
        }        
    }
    cout<<"NG"<<endl;
}

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

using namespace std;

const int max_n = -1, inf = 1000111222;

int n, ans = inf;

int sum(int x) {
    int res = 0;
    while (x) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        ans = min(ans, sum(i) + sum(n - i));
    }
    cout << ans << endl;
    return 0;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; cin >> N;
    vector<ll> a(N), b(N), c(N);
    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];
    rep(i, N) cin >> c[i];
    sort(all(a)); sort(all(b)); sort(all(c));

    ll res = 0;
    rep(i, N){
        res += distance(a.begin(), lower_bound(all(a), b[i])) * distance(upper_bound(all(c), b[i]), c.end());
    }

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 6784
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def kaizyo(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
def haba(x,n)
  que = [[x,0]]
  while(que.size > 0)
    data = que.shift
    xx = data[0]
    d = data[1] 
    return if(d > @dd)
    next if(@t[xx] >= @dd - d)
    @t[xx] = @dd - d
    @tab[xx].each do |dd|
      que.push([dd,d+1]) 
    end
    @data[xx] = @col if(@data[xx] == 0)
  end
end
n,m = inp
@tab = na2(n+1,0)
@data = na(n+1,0)
m.times do
  da = inp
  @tab[da[0]].push(da[1])
  @tab[da[1]].push(da[0])
end
q = inp[0]
dat = []
q.times do
  dat.push(inp)
end
dat.reverse!
@t = na(n+1,-1)
q.times do |i|
  da = dat[i]
  @col = da[2]
  @dd = da[1]
  haba(da[0],n)
end
(1..n).each do |i|
  puts @data[i]
end

=begin
=end


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

using namespace std;

using int64 = long long;

// Verified: AOJ-DSL2A, AOJ-DSL2B
template <typename T>
class SegmentTree {
 private:
  function<T(T, T)> merge_fn;
  T empty_value;
  vector<T> nodes;
  int num_nodes;

  // Returns the fold of overwrap between [node_l, node_r) and [l, r).
  // nodes[node_index] needs to correspond to [node_l, node_r).
  T GetRangeInternal(int node_index, int node_l, int node_r, int l, int r) {
    if (node_r <= l || r <= node_l) return empty_value;
    if (l <= node_l && node_r <= r) return nodes[node_index];
    int node_m = (node_l + node_r) / 2;
    return merge_fn(
        GetRangeInternal(2 * node_index, node_l, node_m, l, r),
        GetRangeInternal(2 * node_index + 1, node_m, node_r, l, r));
  }

 public:
  // Arguments:
  // in_merge: The function to merge two values. It should be a monoid.
  // in_empty_value: The identity of the monoid.
  // xs: The initial values.
  SegmentTree(
      function<T(T, T)> merge_fn, T empty_value, const vector<T>& xs) :
          merge_fn(merge_fn), empty_value(empty_value) {
    int n = xs.size();
    num_nodes = 1;
    while (num_nodes < n) num_nodes *= 2;
    num_nodes *= 2;
    nodes = vector<T>(num_nodes, empty_value);
    for (int i = 0; i < xs.size(); ++i) {
      nodes[num_nodes / 2 + i] = xs[i];
    }
    for (int i = num_nodes / 2 - 1; i >= 1; i--) {
      nodes[i] = merge_fn(nodes[2 * i], nodes[2 * i + 1]);
    }
  }

  // Updates the i-th element to x.
  void Update(int i, T x) {
    nodes[num_nodes / 2 + i] = x;
    for (int cur = (num_nodes / 2 + i) / 2; cur > 0; cur /= 2) {
      nodes[cur] = merge_fn(nodes[2 * cur], nodes[2 * cur + 1]);
    }
  }

  // Returns the value of the range [l, r) merged by merge_fn.
  T GetRange(int l, int r) {
    return GetRangeInternal(1, 0, num_nodes / 2, l, r);
  }

  T Get(int i) {
    return nodes[num_nodes / 2 + i];
  }
};

constexpr int DEBUG = 0;

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

  int n;
  int64 length;
  int64 t;
  cin >> n >> length >> t;
  vector<int64> xs(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> xs[i];
  }

  vector<int64> dp(n + 1);

  function<int64(int64, int64)> merge_fn = [](int64 x, int64 y) {
    return min(x, y);
  };
  constexpr int64 EMPTY_VALUE = INT64_MAX / 4;
  SegmentTree<int64> tree1(merge_fn, EMPTY_VALUE, vector<int64>(n + 1, EMPTY_VALUE));
  SegmentTree<int64> tree2(merge_fn, EMPTY_VALUE, vector<int64>(n + 1, EMPTY_VALUE));
  tree1.Update(0, dp[0] - xs[0]);
  tree2.Update(0, dp[0] - xs[0] - 2 * xs[1]);

  for (int i = 1; i <= n; i++) {
    if (DEBUG) cout << "i: " << i << endl;
    int k =
        distance(xs.begin(), lower_bound(xs.begin(), xs.end(), xs[i] - t / 2));
    if (DEBUG) cout << "k: " << k << endl;
    int64 min1 = tree1.GetRange(k - 1, i) + xs[i] + t;
    int64 min2 = tree2.GetRange(0, k - 1) + 3 * xs[i];
    dp[i] = min(min1, min2);
    if (DEBUG) cout << "dp[i]: " << dp[i] << endl;
    if (i < n) {
      tree1.Update(i, dp[i] - xs[i]);
      tree2.Update(i, dp[i] - xs[i] - 2 * xs[i + 1]);
    }
  }

  int64 ans = dp[n] + length - xs[n];
  cout << ans << endl;
}

Measured memory_bytes: 6768
#include<stdio.h>

int main(void) {
  int K,S;
  scanf("%d",&K);
  scanf(" %d",&S);
  int ans=0;

  for (int x = 0; x <=K; x++) {
    for (int y = 0; y <=K; y++) {
      if (S-x-y<=K && 0<=S-x-y) {
        ans+=1;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 128
//白昼夢

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

int main (){
    string S,word[4] = {"dream", "dreamer", "erase", "eraser"};
    bool flag = true;
    cin >> S;
    reverse(S.begin(),S.end());
    for(int i = 0;i<4;i++)reverse(word[i].begin(),word[i].end());

    for(int i= 0;i<S.size();){
        for(int j =0;j<4;j++){
            if(S.substr(i,word[j].size())==word[j]){
                i += word[j].size();
                flag = true;
                break;
            }else{
                flag = false;
            }
        }
        if(flag == false)break;
    }
    if(flag == true)cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner Input = new Scanner(System.in);

        long X, Y;
        String S;

        X = Input.nextLong();
        S = Input.next();
        Y = Input.nextLong();

        if (S.equals("-")) {
            System.out.println(X - Y);
        } else {
            System.out.println(X + Y);
        }

    }

}

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

int main(){ 
  int A, B; cin >> A >> B;
  
  cout << (B - 1) / (A - 1) + min((B-1)%(A-1), 1) << endl;

}

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

int ans=0;

void CountPattern(int n, int x){
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            for(int k=j+1; k<=n; k++){
                if(x==i+j+k)
                    ans++;
                    //printf("%d %d %d\n",i, j, k);                
            }
        }
    }    
}

int main(void)
{
    int n,x;
    cin >> n >> x;
    while(n!=0 || x!=0){
        CountPattern(n,x);
        cout << ans << endl;
        cin >> n >> x;
        ans = 0;
    }
    return 0;    
}


Measured memory_bytes: 3096
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  dp=[0]*100010

  n,m=LI()

  dp[0]=1
  dp[1]=1

  for _ in range(m):
    dp[I()]=-1

  for i in range(2,n+1):
    if dp[i]==-1:
      continue

    if dp[i-2]!=-1:
      dp[i]+=dp[i-2]
    if dp[i-1]!=-1:
      dp[i]+=dp[i-1]

    dp[i]%=mod

  return dp[n]%mod

print(main())


Measured memory_bytes: 9328
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	const maxWord = (1 << 30)
	buf := []byte{}
	sc.Buffer(buf, maxWord)
	sc.Split(bufio.ScanWords)
}

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

func main() {
	w, _ := strconv.Atoi(input())
	h, _ := strconv.Atoi(input())
	x, _ := strconv.Atoi(input())
	y, _ := strconv.Atoi(input())

	area := float64(w*h) / 2
	isMulti := 0
	if x*2 == w && y*2 == h {
		isMulti = 1
	}
	fmt.Println(area, isMulti)
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n, q;
  cin >> n >> q;
  vector<vi32> g(n);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  vi32 s(n);
  rep(i, q) {
    int p, x;
    cin >> p >> x;
    p--;
    s[p] += x;
  }
  vi32 ans(n, 1e9);
  auto dfs = [&](auto dfs, int u, int sum) -> void {
    if (ans[u] != 1e9) return;
    ans[u] = sum;
    for (auto v : g[u]) {
      dfs(dfs, v, sum + s[v]);
    }
  };
  dfs(dfs, 0, s[0]);
  cout << ans << endl;
}

Measured memory_bytes: 21504