akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int p[800];
int d[800];
vector<int> et[800];
vector<int> ec[800];

int dfs(int p, int v) {
	int i;
	
	int ret = 0;
	for (i = 0; i < et[v].size(); i++) {
		int nv = et[v][i];
		if (nv == p || et[nv].size() == 1) continue;
		int res = dfs(v, nv);
		ret += res + ec[v][i];
	}
	return ret;
}

int dfs2(int p, int v) {
	int i;
	
	int ret = 0;
	for (i = 0; i < et[v].size(); i++) {
		int nv = et[v][i];
		if (nv == p || et[nv].size() == 1) continue;
		int res = dfs2(v, nv);
		ret = max(ret, res + ec[v][i]);
	}
	return ret;
}

int main() {
	while (cin >> n) {
		if (!n) break;
		int i;
		for (i = 0; i < n - 1; i++) { cin >> p[i]; p[i]--; }
		for (i = 0; i < n - 1; i++) cin >> d[i];
		int sumD = 0;
		for (i = 0; i < n - 1; i++) {
			et[p[i]].push_back(i + 1);
			ec[p[i]].push_back(d[i]);
			et[i + 1].push_back(p[i]);
			ec[i + 1].push_back(d[i]);
			sumD += d[i];
		}
		
		int minCst = 1e+9;
		for (i = 0; i < n; i++) {
			int cst = dfs(-1, i) * 2 - dfs2(-1, i);
			minCst = min(minCst, cst);
		}
		cout << minCst + sumD << endl;
		
		for (i = 0; i < n; i++) {
			et[i].clear();
			ec[i].clear();
		}
	}
	return 0;
}


Measured memory_bytes: 3348
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  vector<int> tower(a);
  for(int i = 0;i < b;i++){
    vector<int> road(2);
    for(int i = 0;i < 2;i++){
      cin >> road.at(i);
    }
    int c,d;
    c = road.at(0);
    d = road.at(1);
    for(int i = 0;i < a;i++){
      if(c == i+1||d == i+1)
        tower.at(i) += 1;
    }
  }
  for(int i = 0;i < a;i++){
      cout << tower.at(i) << endl;
  }
}
    
    

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

int64_t mod = 1000000007;
int64_t large = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int N, tmp, free = 0;
    cin >> N;
    map<int, int> list;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        if (tmp >= 3200)
            free++;
        else
            list[tmp / 400]++;
    }
    int size = list.size();
    if (size == 0)
        cout << 1 << ' ';
    else
        cout << list.size() << ' ';
    cout << size + free;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a,b;
    int i;
    scanf("%d %d",&a,&b);
    if(a>b)
    {
        for(i=0;i<a;i++)
        {
            printf("%d",b);
        }
    }
    else if(a<=b)
    {
        for(i=0;i<b;i++)
        {
            printf("%d",a);
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int dp[400][400],dp2[400][400];
int w[400];

int rec(int l,int r){
	if(r-l==0)return true;
	if(dp[l][r]!=-1)return dp[l][r];
	for(int k=l+1;k<r;k++){
		if(abs(w[l]-w[k])<=1){
			if(rec(l+1,k)&&rec(k+1,r))return dp[l][r]=true;
		}
	}
	return dp[l][r]=false;
}
int rec2(int l,int r){
	if(r-l==0)return 0;
	if(dp2[l][r]!=-1)return dp2[l][r];
	if(rec(l,r))return r-l;
	dp2[l][r]=0;
	for(int k=l+1;k<r;k++){
		dp2[l][r]=max(dp2[l][r],rec2(l,k)+rec2(k,r));
	}
	return dp2[l][r];
}
int main(){
	int n;
	while(scanf("%d",&n),n){
		rep(i,n)scanf("%d",&w[i]);
		memset(dp,-1,sizeof(dp));
		memset(dp2,-1,sizeof(dp2));
		cout<<rec2(0,n)<<endl;
	}
}


Measured memory_bytes: 4392
## coding: UTF-8
N = int(input())

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

ans = 1
limit = 10**18

for i in range(N):
    ans = ans * A[i]
    if(ans > limit):
        ans = '-1'
        break

for i in range(N):
    if(A[i] == 0):
        ans = 0
        break

print(ans)


Measured memory_bytes: 84636
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
	int N;
	cin >> N;
	vector<ll> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	ll ans = 0;
	for (int i = 1; i < N; i++) {
		ll diff = A[i - 1] - A[i];
		if (diff > 0) {
			ans += diff;
			A[i] += diff;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4772
program laminate
  implicit none
  integer(8), parameter :: inf = 10000000000000000_8
  integer :: n, k, i, j, l
  integer(8) :: h(0:300) = 0_8, dp(0:300,0:300) = inf
  read(*,*) n, k
  if (k == n) then
    write(*,'(i0)') 0
    stop
  end if
  read(*,*) h(1:n)
  dp(0,0) = 0_8
  do i = 1, n
    do j = 1, min(i,n-k)
      do l = 0, i-1
        dp(i,j) = min(dp(i,j),dp(l,j-1)+max(0_8,h(i)-h(l)))
      end do
    end do
  end do
  write(*,'(i0)') minval(dp(1:n,n-k))
end program laminate

Measured memory_bytes: 896
N=int(input())
Ki=[list(map(int,input().split())) for i in range(N)]
f=False
for i in Ki:
  t,x,y=i
  s=x+y
  if (t%2==0 and s%2!=0) or (t%2!=0 and s%2==0) or t<s:
    f=True
    break
if f:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 27300
#include <iostream>
using namespace std;
int main(){
	char graph[42] = {0,0,0,0,0,0,0,0,97,102,107,112,117,122,0,98,103,108,113,118,'.',0,99,104,109,114,119,'?',0,100,105,110,115,120,'!',0,101,106,111,116,121,' '};
	string s;
	while(cin >> s,!cin.eof()){
		string ans = "";
		if(s.size() % 2 == 1)ans = "NA";
		else{for(int i = 0;i < s.size();i += 2){
			if(s[i] - '0' <= 0 || s[i+1] - '0' <= 0 || s[i] - '0' > 6 || s[i+1] - '0' > 5){ans = "NA";break;}
			ans += graph[(s[i+1] - '0') * 7 + s[i]-'0'];
		}
		}
		cout << ans << endl;
	}	
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
typedef long long lint;

namespace utils{
	template <class T> inline void apn(T &x,const T y){x>y?x=y:0;}
	template <class T> inline void apx(T &x,const T y){x<y?x=y:0;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=(c=='-')&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

int main(){
	int n=nxi(),l=0,r=n,mid;
	while(l!=r){
		mid=(l+r)>>1;
		if((lint)mid*(mid+1)>>1>=n) r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}


Measured memory_bytes: 256
N,A,B,C,D=[int(i) for i in input().split()]
diff=B-A

found=False
for i in range(N):
    j=N-1-i
    left=i*C-j*D
    right=i*D-j*C
    if left<=diff and diff<=right:
        print("YES")
        found=True
        break
if not(found):
    print("NO")

Measured memory_bytes: 3064
n,m=map(int,input().split())
a=list(map(int,input().split()))
r=[0]*(n+1)
for i in range(n):
    r[i+1]=r[i]+a[i]
for i in range(n):
    r[i+1]%=m
r.sort()
r.append(-1)
ans=0
f=1
for i in range(len(r)-1):
    if r[i]==r[i+1]:
        f+=1
    else:
        ans+=f*(f-1)//2
        f=1
print(ans)

Measured memory_bytes: 14408
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=1000000000000000;
#define rep(i,l,r) for(ll i=l;i<=r;i++)

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

int main(){
    ll n,k;cin>>n>>k;
    ll a[n],f[n];
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    for(ll i=0;i<n;i++){
        cin>>f[i];
    }
    sort(a,a+n);
    sort(f,f+n,greater<>());
    ll l=-1;
    ll r=pow(10,18);
    ll c;
    ll mid;
    while(r-l>1){
        c=0;
        mid=(r+l)/2;
        for(ll i=0;i<n;i++){
            c+=max(0,a[i]-(mid/f[i]));
        }
        if(c<=k){
            r=mid;
        }else{
            l=mid;
        }
    }
    cout<<r<<endl;
    return 0;
}


Measured memory_bytes: 3328
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		Set<Integer> set = new HashSet<>();
		int ac = 0, wa = 0;
		int[] cnt = new int[n+1];
		for(int i=0;i<m;i++) {
			int p = sc.nextInt();
			String s = sc.next();
			
			if(s.equals("WA"))
				cnt[p]++;
			else {
				if(!set.contains(p)) {
					ac++;
					wa+=cnt[p];
					set.add(p);
				}
			}
		}
		
		System.out.println(ac+" "+wa);
	}
}


Measured memory_bytes: 66500
n,c=map(int,input().split())
X,V=[0],[0]
X2,V2=[],[]
for _ in range(n):
    x,v=map(int,input().split())
    X.append(x)
    V.append(v)
    X2.append(c-x)
    V2.append(v)
X2.append(0)
V2.append(0)
X2.reverse()
V2.reverse()
r=[0]
l=[0]
for i in range(n):
    V[i+1]+=V[i]
    V2[i+1]+=V2[i]
rr=[0]
ll=[0]
for i in range(1,n+1):
    r.append(max(r[-1],V[i]-X[i]))
    rr.append(max(rr[-1],V[i]-2*X[i]))
for i in range(1,n+1):
    l.append(max(l[-1],V2[i]-X2[i]))
    ll.append(max(ll[-1],V2[i]-2*X2[i]))
ans=0
for i in range(n+1):
    ans=max(ans,r[i]+ll[n-i],l[i]+rr[n-i])

print(ans)
    

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

int main_()
{
    int a, b;
    cin >> a >> b;
    if (a <= 0 && 0 <= b)
    {
        cout << "Zero" << endl;
    }
    else if (a > 0)
    {
        cout << "Positive" << endl;
    }
    else if (b < 0)
    {
        if ((b - a) % 2 == 0)
        {
            cout << "Negative" << endl;
        }
        else
        {
            cout << "Positive" << endl;
        }
    }
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


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

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

	set < string > st;
	vector< string > v;
	string s;
	for(int i = 0; i < n; i++){
		cin >> s;
		v.push_back(s);
	}

	st.insert(v[0]);
	bool yes = true;
	for(int i = 1; i < n; i++){
		if(st.find(v[i]) == st.end() && v[i][0] == v[i-1][v[i-1].size()-1]){
			st.insert(v[i]);
		}else{
			cout << "No";
			return 0;
		}
	}

	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
LL n, s;
int main() {
	std::cin >> n >> s;
	int q = std::sqrt(n);
	if (n == s) {
		std::cout << s + 1 << std::endl;
		return 0;
	}
	for (LL i = 2; i <= q; i++) {
		LL copy = n;
		LL sum = 0;
		while (copy) {
			sum += copy % i;
			copy /= i;
		}
		if (s == sum) {
			std::cout << i << std::endl;
			return 0;
		}
	}
	for (int i = q; i > 0; i--) {
		LL b = (n - s) / i + 1;
		LL sum = i + (n - i * b);
		if (b <= i || n - i * b >= b || n - i * b < 0)continue;
		if (s == sum) {
			std::cout << b << std::endl;
			return 0;
		}
	}
	std::cout << -1 << std::endl;
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    string s, t;
    cin >> s >> t;
    int ns = s.size();
    int nt = t.size();
    vvi q(26);
    rep(i, ns) {
        q[s[i]-'a'].push_back(i);
    }

    ll ans = 0LL;
    int now = -1;
    vi noww(26);
    rep(i, nt) {
        while(noww[t[i] - 'a'] != q[t[i] - 'a'].size() && q[t[i] - 'a'][noww[t[i] - 'a']] < now) {
            noww[t[i] - 'a']++;
        }
        if(noww[t[i] - 'a'] == q[t[i] - 'a'].size()) {
            if(q[t[i] - 'a'].empty()) {
                cout << -1 << endl;
                return 0;
            } else {
                ans += ns;
                noww.assign(26, 0);
            }
        }
        int nn = q[t[i] - 'a'][noww[t[i] - 'a']];
        //cout << nn << endl;
        noww[t[i] - 'a']++;
        //cout << ans << endl;
        ans += nn-now;
        //cout << ans << endl;
        now = nn;
    }

    cout << ans << endl;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S 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 (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N, K; cin >> N >> K;

    i64 ans = 0;

    i64 cnt = 0;
    REPS(i, N) {
        if (i % K == 0) cnt++;
    }
    ans += pow(cnt, 3);

    if (K % 2 == 0) {
        cnt = 0;
        REPS(i, N) {
            if (i % K == K / 2) cnt++;
        }
        ans += pow(cnt, 3);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  int n,q;
  string s;
  cin>>n>>q>>s;
  vector<char> t(q),d(q);
  for(int i=0;i<q;i++){
    cin>>t[i]>>d[i];
  }
  
  int l,r;
  int ok=-1,ng=n,mid;
  while(ng-ok>1){
    mid=(ng+ok)/2;
    if(mid==-1||mid==n)break;
    int k=mid;
    for(int i=0;i<q;i++){
	 if(k==-1)break;
	 if(s[k]==t[i]){
	   if(d[i]=='L')k--;
	   else k++;
	 }
    }
    if(k==-1)ok=mid;
    else ng=mid;
  }
  l=ok;

  ng=ok;
  ok=n;
  while(ok-ng>1){
     mid=(ng+ok)/2;
    if(mid==n)break;
    int k=mid;
    for(int i=0;i<q;i++){
	 if(k==n)break;
	 if(s[k]==t[i]){
	   if(d[i]=='L')k--;
	   else k++;
	 }
    }
    if(k==n)ok=mid;
    else ng=mid;
  }
  r=ok;

  cout<<max(0,r-l-1)<<endl;
  return 0;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp make_pair
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

vector<int> g[100005];

vector<int> diameter(int n, vector<int> *vec){
  if(n==1) return {0};
  vector<int> dist(n);
  vector<int> pre(n);
  auto bfs = [&](int ini){
    queue<pair<int,int>> q;
    q.push({ini,-1});
    dist[ini] = 0;
    int farthest = ini;
    while(q.size()){
      auto p = q.front(); q.pop();
      int v = p.first;
      int from = p.second;
      if(dist[farthest] < dist[v]){
        farthest = v;
      }
      for(auto to : vec[v]) if(to!=from){
        q.push({to, v});
        dist[to] = dist[v] + 1;
        pre[to] = v;
      }
    }
    return farthest;
  };
  int p = bfs(0);
  int q = bfs(p);
  int cur = q;
  vector<int> res;
  res.push_back(cur);
  while(cur != p){
    cur = pre[cur];
    res.push_back(cur);
  }
  assert(res[0]==q && res.back()==p);
  return res;
}


bool solve(){
  int n;
  cin>>n;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].pb(b);
    g[b].pb(a);
  }

  auto dia = diameter(n, g);

  vector<bool> is_dia(n, false);
  for(auto x: dia) is_dia[x] = true;
  rep(i,n) if(!is_dia[i] && g[i].size() > 1) return false;

  vector<vector<int>> cand;
  rep(_, 2){
    int cur = 1;
    vector<int> tmp;
    int s = dia[0];
    int t = dia.back();
    for(auto x : dia){
      if(x == s || x == t) tmp.pb(cur++);
      else {
        int r = g[x].size()-2;
        rep(i, r) tmp.pb(cur + i + 1);
        tmp.pb(cur);
        cur += r+1;
      }
    }
    // dbg(tmp);
    assert(tmp.size() == n);
    cand.pb(tmp);
    reverse(all(dia));
  }
  // dbg(cand);

  auto res =  min(cand[0], cand[1]);
  rep(i,n) cout << res[i] << " \n"[i==n-1];

  return true;
}

int main(){
  if(!solve()) cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 8048
using System;

class sample8{
    static void Main(string[] args){

            string[] str_number = Console.ReadLine().Split(' ');
            int W = int.Parse(str_number[0]);
            int H = int.Parse(str_number[1]);
            int x = int.Parse(str_number[2]);
            int y = int.Parse(str_number[3]);
            int r = int.Parse(str_number[4]);

            if(x < -100){
        
                Console.WriteLine("xは-100以上の値で入力してください。");
                Environment.Exit(0);
        
            }else if( y < -100 ){
                
                Console.WriteLine("yは-100以上の値で入力してください。"); 
                Environment.Exit(0);
            
                
            }else if( x > 100 ){
        
                Console.WriteLine("xは100以下の値で入力してください。");
                Environment.Exit(0);
          
            }else if( y > 100 ){
                
                Console.WriteLine("yは100以下の値で入力してください。");
                Environment.Exit(0);
                
            }else if(H <= 0 ){
                
                Console.WriteLine("Hは1以上の値で入力してください。");
                Environment.Exit(0);
                
            }else if(W <= 0 ){
                
                Console.WriteLine("Wは1以上の値で入力してください。");
                Environment.Exit(0);
                
            }else if(r <= 0 ){
                
                Console.WriteLine("rは1以上の値で入力してください。");
                Environment.Exit(0);
                
            }else if(H > 100 ){
                
                Console.WriteLine("Hは100以下の値で入力してください。");
                Environment.Exit(0);
                
            }else if(W > 100 ){
                
                Console.WriteLine("Wは100以下の値で入力してください。");
                Environment.Exit(0);
                
            }else if(r > 100 ){
                
                Console.WriteLine("rは100以下の値で入力してください。");
                Environment.Exit(0);
                
            }
            
            if( (x-r) >= 0 && (y-r) >= 0 && (y+r) <= H && (x+r) <= W){
                Console.WriteLine("Yes");
            }else{ 
                 Console.WriteLine("No");
            }
    }
}


Measured memory_bytes: 17952
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


n = int(sys.stdin.readline().rstrip())
hn = list(map(int, sys.stdin.readline().rstrip().split())) + [0]*2
dp = [-1] * (n+2)

dp[0] = 0
for i in range(n):
  for j in range(1,3):
    if dp[i+j] < 0:
      dp[i+j] = dp[i] + abs(hn[i+j]-hn[i])
    else:
      dp[i+j] = min(dp[i+j], dp[i] + abs(hn[i+j]-hn[i]))

print(dp[n-1])

Measured memory_bytes: 13928
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<(n); i++)
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; }
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
const int MAX = 510000;
const int mod = 1e9+7;

long long fac[MAX], finv[MAX], inv[MAX];

void combInit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main(){
    ll n,k; cin>>n>>k;
    ll res=0;
    combInit();
    for(ll i=k; i<=n+1; i++){
        ll tmp=0;
        tmp+=(n-i)*i + (i*(i+1)/2);
        tmp-=(i-1)*i/2;
        res+=tmp+1;
        res%=mod;
    }
    cout<<res<<endl;
    
    return 0;
}

Measured memory_bytes: 15576
function Main(input) {
  "use strict";
	const lines = input.split("\n");
	const n = parseInt(lines[0].split(" "), 10);
	const line2 = lines[1].split(" ");

  let nums = line2.map(s => parseInt(s, 10));

  const is_even = n => n%2 === 0;
  const divide_2 = n => n/2;
  let count = 0;

  while (true) {
    if (nums.every(is_even)) {
      count++;
      nums = nums.map(divide_2);
    } else {
      break;
    }
  }
	console.log('%s',count)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29604
#include <iostream>
#include <string>
int main(void){
	int N,A,B;
	int kaigairank=0;
	int tuuka=0;
	std::string s;
	std::cin>>N>>A>>B;
	std::cin>>s;
	for(int i=0;i<N;i++){
		if(s[i]=='a'){//国内
			if(tuuka<A+B){
				std::cout<<"Yes"<<std::endl;
				tuuka++;
			}else {
				std::cout<<"No"<<std::endl;
			}
		}else if(s[i]=='b'){//海外
			kaigairank++;
			if(tuuka<A+B && kaigairank<=B){
				std::cout<<"Yes"<<std::endl;
				tuuka++;
			}else {
				std::cout<<"No"<<std::endl;
			}

		}else {//論外
				std::cout<<"No"<<std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 896
import java.util.*;
    public class Main {
    	public static void main(String[] args){
    		Map<Integer, List<Integer>> map = new HashMap<>();
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();
    		int M = sc.nextInt();
    		for (int i = 0; i < M; i++) {
    			int p = sc.nextInt(),q = sc.nextInt();
    			List<Integer> l1= map.getOrDefault(p, new ArrayList<>());
    			l1.add(q);
    			map.put(p, l1);
    			List<Integer> l2= map.getOrDefault(q, new ArrayList<>());
    			l2.add(p);
    			map.put(q, l2);
    		}
    		Queue<Integer> queue = new LinkedList<>();
    		List<Integer> first = map.getOrDefault(1, new ArrayList<>());
    		boolean connected = false;
    		for (int i = 0; i < first.size() && !connected; i++) {
    			queue.offer(first.get(i));
    			if (i == N)  connected = true;
    		}
    		
    		while (!queue.isEmpty() && !connected) {
    			int start = queue.poll();
    			List<Integer> sec = map.get(start);
    			if (sec.contains(N))  connected = true;
    		}
    		// output
    		
    		if (connected)  System.out.println("POSSIBLE");
    		else  System.out.println("IMPOSSIBLE");   	
    	}
    }



Measured memory_bytes: 163812
// Sky's the limit :)
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int T = 1; 
    // cin >> T; 
    while (T--) {
        int n;
        cin >> n;

        int ans = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++)
                    ans += __gcd(i, __gcd(j, k));
            }
        }

        cout << ans << '\n';
    }
    
    return 0;
}



Measured memory_bytes: 3656
import java.util.*;

public class Main{
  static final double EPS = 0.00001;

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

    while(true){
      double q = sc.nextInt();
      if(q < 0) break;

      double x = q / 2.0;

      while(Math.abs(x * x * x - q) >= EPS * q){
        x = x - (x * x * x - q) / (3 * x * x);
      }

      System.out.printf("%.6f\n", x);
    }
  }
}

Measured memory_bytes: 12000
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){

  int n;
  int p[56];
  int i,j;
  int x;
  int cnt = 0;

  scanf("%d", &n);
  for(i = 1;i <= n;i++) scanf("%d", &p[i]);

  for(i = 1;i <= n;i++){
    if(p[i] != i) cnt++;
  }

  if(cnt > 2) printf("NO\n");

  else printf("YES\n");

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long

signed main(){
    string S;
    cin>>S;
  	int k=stoi(S.substr(0,2));
    int z=stoi(S.substr(2,2));
    if(k<=12&&k>0&&z<=12&&z>0)cout<<"AMBIGUOUS"<<endl;
    else{
        if(k<=12&&k>0) cout<<"MMYY"<<endl;
        else{
            if(z<=12&&z>0) cout<<"YYMM"<<endl;
            else{
                cout<<"NA"<<endl;
            }
        }  
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int m,n;
	int mp[100005];	
	scanf("%d %d",&m,&n);
	memset(mp,0,sizeof(mp));
	int t=n;
	while(t--)
	{
		int l,r;
		scanf("%d %d",&l,&r);
	for(int i=l;i<=r;i++)
	{
		mp[i]++;
	}
    }
    int sum=0;
    for(int i=1;i<=m;i++)
    {
    	if(mp[i]==n)
    	sum++;
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 3588
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;



int main() {
	int a, p;
	cin >> a >> p;

	p += a * 3;
	cout << p / 2 << endl;

}


Measured memory_bytes: 3588
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] ary = s.toCharArray();
        List<Character> oary = Arrays.asList('R', 'U', 'D');
        List<Character> eary = Arrays.asList('L', 'U', 'D');
        Set<Character> hso = new HashSet<>();
        Set<Character> hse = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if ((i + 1) % 2 == 0) {
                hse.add(ary[i]);
            } else {
                hso.add(ary[i]);
            }
        }
        hso.removeAll(oary);
        hse.removeAll(eary);
        if (hso.isEmpty() && hse.isEmpty()) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 2e5 + 10;
int a[M], b[M], c[M], d[M];
bool cmp(int a, int b) {
    return a > b;
}
int main(){
    int n, m, A, B, C;
    scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
    for(int i = 1; i <= A; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= B; i++) scanf("%d", &b[i]);
    for(int i = 1; i <= C; i++) scanf("%d", &c[i]);
    sort(a + 1, a + A + 1, cmp);
    sort(b + 1, b + B + 1, cmp);
    sort(c + 1, c + C + 1, cmp);
    ll sum = 0;
    int cnt = 0;
    for(int i = 1; i <= n; i++) sum += a[i], d[++cnt] = a[i];
    for(int i = 1; i <= m; i++) sum += b[i], d[++cnt] = b[i];
    sort(d + 1, d + cnt + 1);
    for(int i = 1, j = 1; i <= C && j <= cnt; i++, j++) {
        if(c[i] > d[j]) {
            sum -= d[j];
            sum += c[i];
        }
        else break;
    }
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 2176
using System;
using System.Collections.Generic;
using System.Linq;

public static class Program
{
    public static void Main(string[] args)
    {
        var vals = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        Console.Write(vals[2] + " " + vals[0] + " " + vals[1]);
    }
}

Measured memory_bytes: 18764
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let a: Vec<i32> = (0..n).map(|_| read()).collect();

    let mut x = 0;
    for y in a {
        let mut z = y;
        while z % 2 == 0 {
            z /= 2;
            x += 1;
        }
    }

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


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define INF 1e9+7
#define ll long long
#define F first
#define S second
#define N 100005
#define M 1000000009
#define mp make_pair
#define ull unsigned long long
#define sc(n) scanf("%d",&n)
#define gcd __gcd
#define pb push_back
using namespace std;

std::vector<int> v[N],jh;
stack<pair<int,pair<int,int> > > qu;
pair<int,pair<int,int> > pa;

int dis[N],col[N];
void line(int s,int d,int c){
	if(!col[s])
		col[s]=c;
	if(dis[s]>=d || d<1)
		return;
	dis[s]=max(dis[s],d);
	for(int i: v[s]){
		line(i,d-1,c);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for (int i = 0; i < m; ++i)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int u,d,c,q;
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>u>>d>>c;
		qu.push(mp(u,mp(d,c)));
	}
	while(!qu.empty()){
		pa = qu.top();
		qu.pop();
		line(pa.F,pa.S.F,pa.S.S);
	}
	for(int i=1;i<=n;i++)
		cout<<col[i]<<endl;
	return 0;
}

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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(10);

}

signed main() {
	ll x;

	cin >> x;

	if (x == 7 || x == 5 || x == 3) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

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

int main() {
    int a1, a2, a3;
    cin >> a1 >> a2 >> a3;
    int ans = max({a1, a2, a3}) - min({a1, a2, a3});
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define N	    100001
#define rep(i,a,b)  for(int i=a;i<b;i++)
const int n = 4 * 1e3;
long long dp[n][2];
int main() {
	int c;
	cin>>c;
	int A[c + 1];
	rep(i, 1, c + 1)
		cin>>A[i];
	for(int i = c; i >= 1; i--) {
		dp[i][0] = A[i];
		for(int j = i + 1; j <= c; j++) {
			if(A[i] + dp[j][1] >= A[j] + dp[j - 1][1]) {
				long long tem = dp[j][0];
				dp[j][0] = A[i] + dp[j][1];
				dp[j][1] = tem;
			}
			else {
				dp[j][0] = A[j] + dp[j - 1][1];
				dp[j][1] = dp[j - 1][0];
			}
		}
	}
	cout<<dp[c][0]-dp[c][1]<<endl;
}


Measured memory_bytes: 256
def prepare(n):
    global nodes,diff_weight
    # ノードは-1で初期化, Nは頂点数
    nodes = [-1]*n
    # 差分重みは0で初期化, Nは頂点数
    diff_weight = [0]*n

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    # xの重みを知りたいので経路圧縮
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# x,yの根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xの木の高さを返す
def rank(x):
    return -nodes[root(x)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 再帰的に根を調べる
        root_x = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        # xを根に直接繋ぎ直す
        nodes[x] = root_x
        return root_x

def unite(x,y,w):
    rx = root(x); ry = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if rx == ry:
        return
    rank_x = rank(rx); rank_y = rank(ry)
    # xの方が木が高いことを想定しているので下の場合はx,yとrx,ryをスワップ,wを-wに
    if rank_x < rank_y:
        x,y = y,x; rx,ry = ry,rx; w = -w
    # 木の高さが同じ場合は繋いだ後の高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[rx] -= 1
    # 低い木の根の差分重みを設定
    diff_weight[ry] = w + weight(x) - weight(y)
    # 低い木の根を高い木の根に繋ぎ直す
    nodes[ry] = rx

N,M = map(int,input().split())
prepare(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
print(ans)

Measured memory_bytes: 8804
from math import sqrt

result = []
while True:
    n = int(input())
    if (n == 0):
        break
    num = input().split()
    total = 0
    for i in num:
        total += int(i)
    average = total / n
    v = 0
    for i in num:
        v += (int(i) - average) ** 2
    result.append(sqrt(v / n))

for i in result:
    print(i)


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

#define ll long long int
#define Mod 1000000007

const int N = 1e5+10;
int dp[N][14];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s; cin>>s;
    int n; n=s.size();
    reverse(s.begin(),s.end());
    int mul=1;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='?'){
            for(int dig = 0;dig <= 9;dig++){
                for(int j=0;j<13;j++){
                    dp[i][(j+dig*mul)%13]=(dp[i-1][j] + dp[i][(j+dig*mul)%13])%Mod;
                }
            }
        }
        else{
            int dig=(s[i-1] - '0');
            for(int j=0;j<13;j++){
                dp[i][(j+dig*mul)%13]=(dp[i-1][j] + dp[i][(j+dig*mul)%13])%Mod;
            }
        }
        
        mul = (mul * 10) % 13;
    }
    cout<<dp[n][5];
    return 0;
}


Measured memory_bytes: 5968
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;

#define pb push_back
#define FOR(i, s, e) for (int (i) = (s); (i) < (e); (i)++)

int main() {
    int x; cin >> x;
    if(x == 3 || x == 5 || x == 7) cout << "YES" << endl;
    else cout << "NO" << endl;
}


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

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k,zb=0;
    cin >> n >> k;
    vector<int> v(n);
    for (int i=0;i<n;i++)
        cin >> v[i];
    sort(v.begin(),v.end());
    for (int i=0;i<k;i++)
        zb+=v[i];
    cout << zb;
}


Measured memory_bytes: 3600
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	if (a < b) return -1;
	return a > b;
}

int N, T;
int A[114514];

int sorted[114514];
char visited[114514];

int get_id(int num) {
	int left = 0, right = N - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (sorted[mid] == num) return mid;
		else if (sorted[mid] < num) left = mid + 1;
		else right = mid - 1;
	}
	return -1;
}

int main(void) {
	int i;
	int min_price, max_rieki = 0;
	int answer = 0;
	if (scanf("%d%d", &N, &T) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
		sorted[i] = A[i];
	}
	if (N < 0) {
		puts("NO TOWNS");
		return 1;
	}
	qsort(sorted, N, sizeof(*sorted), cmp);

	/* max利益を求める */
	min_price = A[0];
	for (i = 0; i < N; i++) {
		if (A[i] < min_price) min_price = A[i];
		if (A[i] - min_price > max_rieki) max_rieki = A[i] - min_price;
	}

	/* 高値に対して対応する安値があるかをチェックしてカウントする */
	for (i = 0; i < N; i++) {
		int this_id = get_id(A[i]);
		int yasune_id = get_id(A[i] - max_rieki);
		if (yasune_id >= 0 && visited[yasune_id]) answer++;
		visited[this_id] = 1;
	}
	printf("%d\n", answer);

	return 0;
}

/*

最安の所で買って一番高い所で売るのが一番儲かる (全部ぶっこむ)
青木君はこのdiffがmaxの所を全て潰せばよい

買→売のペアが交差することは考えなくていい (前の買→後ろの売を使えばいいはずなので)
買(このとき必然的に売も)の価格が同じ時に注意

→二部グラフの最小点被覆

二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！ - Qiita
https://qiita.com/drken/items/7f98315b56c95a6181a4

二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方
https://www.slideshare.net/drken1215/ss-86894312

→答えは最大マッチングサイズ

1 2 1 2 1 2 … のようなケースだと辺の数がでかくてヤバい！
→ 「Aiは相異なる」という条件があるので多分大丈夫やろ
→ ということは、「買(このとき必然的に売も)の価格が同じ時」も無いやんけ

→ 高値に対応してmax利益を生む安値があるかをチェックしてカウントでおｋ

*/


Measured memory_bytes: 1404
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#ifndef JHELPER1_COMMON_H
#define JHELPER1_COMMON_H

#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

typedef long long ll;
using namespace std;

constexpr ll MOD = 1000 * 1000 * 1000 + 7;

// Returns x^y modulo MOD. O(log2(y)).
ll modPow(ll x, ll y) {
  ll res = 1, a = x;
  while (y > 0) {
    if ((y & 1) > 0) {
      res = (res * a) % MOD;
    }
    a = (a * a) % MOD;
    y >>= 1;
  }
  return res;
}

// Returns a^-1 module MOD.
ll inverse(ll a) {
  /*
   * Fermat's little theorem
   * http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem
   *
   * <pre>
   * a^p = a (mod p)
   * a^(p-1) = 1 (mod p)
   * ..
   * 1/a = a^(p-2) (mod p)
   * </pre>
   */
  return modPow(a, MOD - 2);
}

#endif //JHELPER1_COMMON_H


#define READ(v) for(auto &e: v){in >> e;}
#define ALL(c) std::begin(c), std::end(c)

class DChatInACircle {
public:
  void solve(std::istream& in, std::ostream& out) {
    int N;
    in >> N;
    vector<ll> A(N);
    READ(A);
    sort(ALL(A), greater<ll>());
    ll tot = A[0];
    int next = 1;
    for (int i = 1; i < N-1; ++i) {
      tot += A[next];
      if (i % 2 == 0) next++;
    }
    out << tot << endl;
  }
};


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


Measured memory_bytes: 4384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

vector<vector<int>> graph(100010, vector<int>());
vector<int> cnt(100010), deg(100010);
bool ans = true;

int dfs(int n, int p) {
	int sum = 0;
	int mx = 0;
	int check = 0;
	for (int i : graph[n]) {
		if (i == p) continue;
		check++;
		int d = dfs(i, n);
		sum += d;
		chmax(mx, d);
	}
	if (check == 0) return cnt[n];
	if (check == 1 && sum != cnt[n] || sum < cnt[n] || sum > 2 * cnt[n] || mx > cnt[n]) ans = false;
	return 2 * cnt[n] - sum;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	cin >> n;
	rep(i, n) cin >> cnt[i];
	rep(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].pb(b);
		graph[b].pb(a);
		deg[a]++; deg[b]++;
	}
	int d = INF; int p = -1;
	rep(i, n) if (deg[i] == 1) p = i;
	if (dfs(p, -1) != cnt[p]) ans = false;
	cout << (ans ? "YES" : "NO") << endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  ll ans[2] = {};
  for (int j = 0; j < 2; j++) {
    ll cumsum = 0;
    if (j == 0 && a[0] <= 0) {
      cumsum = 1, ans[j] = 1 - a[0];
    } else if (j == 1 && a[0] >= 0) {
      cumsum = -1, ans[j] = 1 + a[0];
    } else {
      cumsum = a[0];
    }

    for (int i = 1; i < n; i++) {
      if (cumsum > 0) {
        if (cumsum + a[i] >= 0) {
          ans[j] += cumsum + a[i] + 1;
          cumsum = -1;
        } else
          cumsum += a[i];
      } else {
        if (cumsum + a[i] <= 0) {
          ans[j] += 1 - cumsum - a[i];
          cumsum = 1;
        } else
          cumsum += a[i];
      }
    }
  }
  cout << min(ans[0], ans[1]) << endl;
}

Measured memory_bytes: 1024
n = gets.chomp.to_i
s = gets.chomp

btow = []
wtob = []

n.times do |i|
  if i == 0
    btow[i] = (s[i] == '#') ? 1 : 0
    wtob[(n-1)-i] = (s[(n-1)-i] == '.') ? 1 : 0
  else
    btow[i] = btow[i-1] + ((s[i] == '#') ? 1 : 0)
    wtob[(n-1)-i] = wtob[n-i] + ((s[(n-1)-i] == '.') ? 1 : 0)
  end
end

max = [btow[n-1], wtob[0]].min
(n-1).times do |i|
  max = btow[i] + wtob[i+1] if max > btow[i] + wtob[i+1]
end

puts max

Measured memory_bytes: 5452
A, B, C, D = gets.split.map(&:to_i)

def gcd(a, b)
  if a > b
    return a if b == 0

    gcd(b, a % b)
  else
    return b if a == 0

    gcd(a, b % a)
  end
end

def lcm(a, b)
  a * b / gcd(a, b)
end

num = (B - A + 1)

num_c = B/C - (A-1)/C
num_d = B/D - (A-1)/D

lcm = lcm(C, D)
num_lcm = B/lcm - (A-1)/lcm

# p num_c, num_d, num_lcm

ans = num - num_c - num_d + num_lcm
puts ans


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int main() {
	int n;
	while (scanf("%d", &n), n) {
		bitset<100>b[100], t;
		rep(i, n) {
			int m; scanf("%d", &m);
			rep(j, m) {
				int p; scanf("%d", &p); p--;
				b[i] |= bitset<100>(1) << p;
			}
		}
		int k; scanf("%d", &k);
		rep(i, k) {
			int l; scanf("%d", &l); l--;
			t |= bitset<100>(1) << l;
		}
		bool ok = true;
		int id = -1;
		rep(i, n) {
			if ((b[i] | t) == b[i]) {
				if (id == -1)id = i + 1;
				else ok = false;
			}
		}
		if (ok)printf("%d\n", id);
		else puts("-1");
	}
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn =3e5+10;
struct Edge{
	int to,corlor,w;
};
vector<Edge> G[maxn];

int depth[maxn],vs[maxn],ID[maxn],dis[maxn];
int n;
int f[maxn][20];
void dfs(int node,int fa,int d,int &k){
   	ID[node] = k;
   	vs[k] = node;
 	depth[k++] = d;
 	// dis[node] = distance;
 	for(int i = 0;i < G[node].size(); ++i){
 		Edge &t = G[node][i];
 		if(t.to == fa) continue;
 		dis[t.to] = dis[node]+t.w;
 		dfs(t.to,node,d+1,k);
        vs[k] = node;
        depth[k++] = d;
 	}
}



void init_rmq(int n){
	
	for(int i = 1;i <= n ; ++i) f[i][0] = i;
    for(int j = 1;(1<<j) <= n; ++j){
    	for(int i = 1;i + (1<<j)-1 <= n; ++i){
    		if(depth[f[i][j-1]]< depth[f[i+(1<<(j-1))][j-1]])
    			f[i][j] = f[i][j-1];
    		else
    			f[i][j] = f[i+(1<<(j-1))][j-1];

    	}
    }
}
int rmq_query(int l,int r){
	int x = 0;
	while((1<<(x+1)) <= r-l+1) x++;
	if(depth[f[l][x]] < depth[f[r-(1<<x)+1][x]])
		return f[l][x];
	else
		return f[r-(1<<x)+1][x];
}
void init_lca(){
	int k = 1;
	dfs(1,-1,0,k);
	init_rmq(2*n-1);
}
int lca(int u,int v){
	// cout<<rmq_query(ID[u],ID[v])<<endl;
	return vs[rmq_query(min(ID[u],ID[v]),max(ID[u],ID[v]))];
}
struct que{
	int corlor,w,coe,id;
};
vector<que> Query[maxn];
int ans[maxn],num[maxn],value[maxn];// num[i] 个数，value 值
void dfs(int u,int fa){
	for(auto qu:Query[u]){
		// cout<<dis[u]<<endl;
		ans[qu.id] +=(dis[u]+num[qu.corlor]*qu.w-value[qu.corlor])*qu.coe;
	}
	for(auto p: G[u]){
		int to = p.to;
		if(to == fa) continue;
		num[p.corlor]++;
		value[p.corlor] += p.w;
		dfs(to,u);
		num[p.corlor]--;
		value[p.corlor] -= p.w;
	}
}
int main(void)
{
	int q;
    cin>>n>>q;
    for(int i = 1;i < n;++i){
    	int u,v,c,w;
    	scanf("%d%d%d%d",&u,&v,&c,&w);
    	G[u].Pb(Edge{v,c,w});
    	G[v].Pb(Edge{u,c,w});
    }
    init_lca();
    for(int i = 1;i <= q; ++i){
    	int x,y,u,v;
    	scanf("%d%d%d%d",&x,&y,&u,&v);
    	int fa = lca(u,v);

    	Query[u].Pb(que{x,y,1,i});
    	Query[v].Pb(que{x,y,1,i});
    	Query[fa].Pb(que{x,y,-2,i});
    }
    dfs(1,-1);
    for(int i  = 1;i <= q; ++i){
    	printf("%d\n",ans[i]);
    }

   return 0;
}

Measured memory_bytes: 56180
//THINK FIRST CODE NEXT!!!!!!!!!!!!!!!!!
//It does not matter how slowly you go as long as you do not stop. - Confucius
#include<bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << ':' << x << endl;
#define loop3(i, k, n) for(i=k; i<n; i++)
#define ll  long long 
#define loop(i,n) for(int i=0;i<n;i++)
#define loop2(i,n) for(int i = 1;i<=n;i+=1)
#define pb push_back
#define mp make_pair
#define v1d vector<ll>
#define v2d vector<vector<ll>>
#define Sort(v) sort(v.begin(),v.end())
const int INF = 1e9 +5 ;
#define ll        long long
// #define mp      make_pair
#define eb         emplace_back
#define pb         push_back
#define ss         second
#define ff         first
#define IOS        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod        998244353
#define MOD        (1000*1000*1000+7)
#define MN         LLONG_MIN
#define MX         LLONG_MAX
#define v1d        vector<ll>
#define v2d        vector<vector<ll>>
#define vip        vector<pair<ll,ll> >
#define v1s        vector<string>
#define pa         pair<ll,ll>
#define mxpq(T)    priority_queue <T>
#define mnpq(T)    priority_queue<T,vector<T>,greater<T>>
#define print(v)   for(auto i:v)cout<<i<<" ";cout<<endl;
#define p2d(v)     for(auto a:v){for(auto b:a)cout<<b<<" ";cout<<endl;}
#define p1d(v)     for(auto a:v)cout<<a<<" ";cout<<endl;
#define ppd(v)     for(auto a:v)cout<<a.ff<<" "<<a.ss<<endl;
#define input(b,n) for(int i=0;i<n;i++)cin>>b[i];
#define Sort(v)    sort(v.begin(),v.end())
#define RSort(v)   sort(v.rbegin(),v.rend())
#define all(v)     v.begin(),v.end()
int gcd(int a,int b){return b?gcd(b,a%b):a;}
//string s = bitset<64>(a).to_string();
void solve()
{
    ll a;
    cin>>a;
    cout<<a + (a*a) + (a*a*a)<<endl;

}

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

Measured memory_bytes: 3628