akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
const int N = 1e5+7, p = 1e9+7;
ll f[N][2];
vector<int> vec[N];
void dfs(int x, int fa)
{
    f[x][0] = f[x][1] = 1;
	for(int i = 0; i < vec[x].size(); i++)
	{
		int y = vec[x][i];
		if(y!=fa)
		{
			dfs(y, x);
			f[x][1] = f[x][1]*f[y][0]%p;
			f[x][0] = f[x][0]*(f[y][1]+f[y][0])%p;
		}
	}
	return;
}
int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 2; i <= n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1, 0);
	printf("%d\n", (f[1][0]+f[1][1])%p);
	return 0;
}

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


int main() {
string S,T;
cin >> S >> T;
ll ans = 0;
rep(i,S.size()) {
    if (S.at(i) != T.at(i)) {
        ans++;
    }
}
cout << ans << endl;




return 0;
}


Measured memory_bytes: 3856
package main

import (
	"fmt"
)

func main() {
	var num, elem int
	var elems []int
	fmt.Scan(&num)
	for i := 0; i < num; i++ {
		fmt.Scan(&elem)
		elems = append(elems, elem)
	}
	for i := 0; i < num; i++ {
		v := elems[i]
		j := i - 1
		for j >= 0 && elems[j] > v {
			elems[j+1] = elems[j]
			elems[j] = v
			j--
		}
		for i, elem2 := range elems {
			if i+1 == len(elems) {
				fmt.Println(elem2)
			} else {
				fmt.Printf("%d ", elem2)
			}
		}
	}
}


Measured memory_bytes: 1172
import bisect
X, N=map(int, input().split())
if N==0:print(X);exit()
p=sorted(list(map(int, input().split())))
#print(p)
m=min(p)-1
M=max(p)+1
#for i in range(m,M+1):
#  p.append(i)
#p=sorted(p)
m=X;i=0
for i in range(m,min(p)-2,-1):
  if i not in p:break
M=X;j=0
for j in range(M,max(p)+2):
  if j not in p:break
if abs(i-X)==abs(j-X):print(min(i,j))
elif abs(i-X)<abs(j-X):
  print(i)
else:print(j)

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

int N;
int X, Y;
int tx[2100], ty[2100];
int SX, SY;
bool isIn[2100][2100];

int main() {
  while (cin >> N) {
    if (N == 0) break;
    cin >> X >> Y;
    memset(isIn, 0, sizeof(isIn));
    for (int i = 0; i < N; ++i) {
      cin >> tx[i] >> ty[i];
      isIn[tx[i]-1][ty[i]-1] = true;
    }
    cin >> SX >> SY;
    int Max = -1;
    for (int x = 0; x + SX <= X; ++x) {
      for (int y = 0; y + SY <= Y; ++y) {
	int con = 0;
	for (int i = 0; i < SX; ++i) {
	  for (int j = 0; j < SY; ++j) {
	    if (isIn[x+i][y+j])
	      ++con;
	  }
	}
	if (con > Max) Max = con;
      }
    }
    cout << Max << endl;
  }
}


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

char c[110][110];
int h, w;

int main() {
	for (int i = 0; i < 110; i++) {
		for (int j = 0; j < 110; j++) {
			c[i][j] = '#';
		}
	}
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> c[i + 1][j + 1];
		}
	}
	for (int i = 0; i < h + 2; i++) {
		for (int j = 0; j < w + 2; j++) {
			cout << c[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
N=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
def fac(N):
	if N==0:
		return 1
	else:
		return(fac(N-1)*N)
def count(a):
	co=0
	for i in range(len(a)):
		b=sorted(a)
		for j in range(len(a)):
			if b[j]==a[0]:
				p=j
		co+=fac(len(a)-1)*p
		a=a[1:]
	return co
print(abs(count(p)-count(q)))

Measured memory_bytes: 3064
import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print("1\n1 2" if k == 0 else -1)


Measured memory_bytes: 3608
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<map>
#include<time.h>
#include<cstring>
#include<iomanip>
#include<numeric>
#define ll long long
#define h 0.000000001
#define pf push_front
#define pb push_back
#define ub upper_bound
#define lb lower_bound
using namespace std;
int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 ll int x, k, d, p, q, z, l;
 cin>>x>>k>>d;
 z=abs(x);
 if(z>=d) 
 {
 	l=z/d;
 	p=z%d;
 	if(k<=l) 
 	cout<<abs(z-(k*d))<<endl;
 	else
 	{
 		if((k-l)%2==0)cout<<p<<endl;
 		else
 		cout<<abs(p-d)<<endl;
 	} 
 } 
 else
 {
 	if(k%2==0)cout<<z<<endl;
 	else cout<<abs(z-d)<<endl;
} 
  return 0;
} 



Measured memory_bytes: 3624
n,m = map(int,input().split())

l=list(input().split() for _ in range(m))

w=[0]*n
a=[0]*n
seitou=0
pena=0

for i in l:
    k=int(i[0])-1
    if a[k]==0:
        if i[1]=="AC":
            a[k]+=1
        else:
            w[k]+=1

seitou=sum(a)
for j in range(n):
    if int(a[j])==1:
        pena+=w[j]
        
print(seitou,pena)

Measured memory_bytes: 33684
A,B,C,X,Y = map(int, input().split())

## ABピザを買うパターン、買わないパターンの2パターンを計算して、小さい方を出力する

## 1.ABピザを買わないパターン
ans = A*X + B*Y

## 2.ABピザを買うバターン
## 2-1.余計なピザは買わない
if X > Y:
  _ = Y*C*2 + abs(X-Y)*A
else:
  _ = X*C*2 + abs(X-Y)*B
ans = min(ans,_)  

## 2-2.余計なピザを買う
_ = max(X,Y)*C*2
ans = min(ans,_)

## 3.answer
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>

int main(void){

    int a[5], k;
    int f, l, count = 0;

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

    for(f = 0; f < 4; f++){
        for(l = f + 1; l < 5; l++){
            if((a[l] - a[f]) <= k){
                count++;
            }
        }
    }

    if(count == 10){
        printf("Yay!");
    } else {
        printf(":(");
    }

    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

#define SIZE 100

int main(void) {
  int a[SIZE] = {0};
  int n = 0;
  int i = 0;

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

  for (i = n - 1; i > 0; i--) {
    printf("%d ", a[i]);
  }

  printf("%d\n", a[0]);

  return 0;
}

Measured memory_bytes: 596
/*
    Reference :-
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forn1(i, n) for (int i = 1; i < int(n); i++)
#define PI pair<int,int>
#define all(vec) vec.begin(),vec.end()
ll mod=1000000007;
ll power(ll n,ll k){
    ll ans=1;
    while(k){
        if(k&1)ans=(ans*n)%mod;
        k/=2;
        n=(n*n)%mod;
    }
    //ans=(ans-1+mod)%mod;
    return ans;
}

int main(){
    //std::ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    int ar[n],fl=1;
    forn(i,n){
        cin>>ar[i];
        if(!(ar[i]&1)){
            if(ar[i]%3!=0&&ar[i]%5!=0)fl=0;
        }
    }
    if(fl==1)cout<<"APPROVED";
    else cout<<"DENIED";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i=0; i < n; i++)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x, y, z) max((x), max((y), (z)))
#define tmin(x, y, z) min((x), min((y), (z)))
ll MM = 1000000000; ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
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;}
const ll INF = 1LL << 60;
//cout << fixed << setprecision(10);
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main(){
    ll a, b;
    cin>>a>>b;
    if(a<=5) cout<<0<<endl;
    else if(6 <= a && a <= 12) cout<<b/2<<endl;
    else cout<<b<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin >> n >> k;
    int ans = 1;
    for(int i = 0; i < n; i++){
        if(ans * 2 > ans + k){
            ans += k;
        }else{
            ans *= 2;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
int w,h,x,y,r,f;

scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);

f=0;
if(x+r>w)f=1;
if(y+r>h)f=1;
if(r>x)f=1;
if(r>y)f=1;

if(f==0)printf("Yes\n");
else printf("No\n");

return 0;
}


Measured memory_bytes: 2044
x, y = map(int, input().split())
 
a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
 
if (x in a and y in a) or (x in b and y in b):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 2940
import java.util.HashSet;
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			int n = sc.nextInt();
			int[] a = new int[n];
			HashSet<Integer> ret = new HashSet<Integer>();
			for(int i=0;i<n;i++) {
				a[i]=sc.nextInt();
			}
			
			int x = 400;
			int plus = 0;
			
			for(int i=0;i<n;i++) {
				if(a[i]<x) {
					ret.add(x);
				}else if(a[i]<2*x) {
					ret.add(2*x);
				}else if(a[i]<3*x) {
					ret.add(3*x);
				}else if(a[i]<4*x) {
					ret.add(4*x);
				}else if(a[i]<5*x) {
					ret.add(5*x);
				}else if(a[i]<6*x) {
					ret.add(6*x);
				}else if(a[i]<7*x) {
					ret.add(7*x);
				}else if(a[i]<8*x) {
					ret.add(8*x);
				}else {
					plus++;
				}
			}
			
			if(ret.size()==0) {
				System.out.println(1+" "+(ret.size()+plus));
			}else {
				System.out.println(ret.size()+" "+(ret.size()+plus));
			}
			
		}	
	}

Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
int main() {
	string a, b, c, ans;
	cin >> a >> b >> c;
	if (b[0] == a[a.length() - 1] && c[0] == b[b.length() - 1]) { ans = "YES"; }
	else { ans = "NO"; }
	cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<pair<int, int> > > vvp;
typedef vector<pair<int, int> > vp;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<vector<ll> > vvl;
typedef vector<ll> vl;
typedef vector<vector<bool> > vvb;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<string, int> psi;
typedef pair<int, int> pii;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define yn(f) (f?"yes":"no")
#define YN(f) (f?"YES":"NO")
#define Yn(f) (f?"Yes":"No")
#define puts(s) cout<<s<<endl
#define inf (1000000007)
#define nil -1

int main() {
	int n, w;
	cin >> n >> w;
	vi V(n);
	vi W(n);
	for (int i = 0; i < n; i++)
	{
		cin >> V[i] >> W[i];
	}
	vvi dp(n + 1, vi(w + 1));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= w; j++)
		{
			if (j - W[i - 1] < 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - W[i - 1]] + V[i - 1]);
			}

		}
	}
	puts(dp[n][w]);
}



Measured memory_bytes: 6848
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>

#include <inttypes.h>
using namespace std;

int main()
{
	int32_t N;
	scanf("%d", &N);

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

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

	double max_v[40001];
	int32_t max_v_index = 0;
	for (int32_t i = 0; i < N; i++) {
		for (int32_t j = 0; j < 2 * t[i]; j++) {
			if (i > 0 && j == 0)
				max_v[max_v_index++] = min(v[i - 1], v[i]);
			else
				max_v[max_v_index++] = v[i];
		}
	}

	max_v[0] = 0;
	max_v[2 * T] = 0;

	for (int32_t i = 1; i < 2 * T + 1; i++)
		max_v[i] = min(max_v[i], max_v[i - 1] + 0.5);
	for (int32_t i = 2 * T - 1; i >= 0 ; i--)
		max_v[i] = min(max_v[i], max_v[i + 1] + 0.5);

	double res = 0;
	for (int32_t i = 0; i < 2 * T; i++) {
		res += min(max_v[i], max_v[i + 1]) * 0.5;
		if (max_v[i] != max_v[i + 1])
			res += 0.5 * 0.5 / 2;
	}

	printf("%.17f\n", res);

	return 0;
}


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

int main()
{
  int i, n,m,k;
  cin>>n;

  m=n%10;
  k=((n-m)%100)/10;
  
    if((n-k*10-m)/100==9) cout<<"1";
    else cout<<"9";

  
    if(k==9) cout<<"1";
    else cout<<"9";

    if(m==9) cout<<"1";
    else cout<<"9";

  cout<<endl;
  /*
  cout<<n-k*100-m*10<<endl;
  cout<<m<<"  "<<k<<endl;
    */
  return 0;
}


Measured memory_bytes: 256
// Contest: AtCoder Beginner Contest 165 (https://atcoder.jp/contests/abc165)
// Problem: A: We Love Golf (https://atcoder.jp/contests/abc165/tasks/abc165_a)


// region {{{ boilerplate
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <chrono>
#include <cstdint>
#include <deque>
#include <exception>
#include <forward_list>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#if __cplusplus >= 201703L
#   include <optional>
#   include <string_view>
#   include <variant>
#endif

using namespace std;

#if __cplusplus >= 201703L
#   define all(a)      begin(a),end(a)
#   define sz(x)       ((int)size(x))
#else
#   define all(a)      (a).begin(),(a).end()
#   define sz(x)       ((int)(x).size())
#endif

#define rep(a, b)      for(int a = 0; a < (b); ++a)
#define reps(a, b, c)  for(int a = (b); a < (c); ++a)
#define trav(a, b)     for(auto& a : b)

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using u32 = uint32_t;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vpi = vector<pi>;

#if __cplusplus >= 201703L
#   define MAYBE_UNUSED [[maybe_unused]]
#else
#   define MAYBE_UNUSED
#endif

MAYBE_UNUSED static constexpr int INF = (int)1e9 + 5;
MAYBE_UNUSED static constexpr ll INFL = (ll)1e18 + 5;
MAYBE_UNUSED static mt19937 rng((u32)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
//endregion }}}

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

    int k, a, b; cin >> k >> a >> b;
    reps(i, a, b + 1)
        if (i % k == 0)
            cout << "OK\n", exit(0);
    cout << "NG\n";

    return 0;
}

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

int main(){
	int a;
	cin>>a;
	while(100<=a){
		if(5 <= a%100){ a -= 105; }
		else if(4 <= a%100){ a -= 104; }
		else if(3 <= a%100){ a -= 103; }
		else if(2 <= a%100){ a -= 102; }
		else if(1 <= a%100){ a -= 101; }
		else {a -= 100; }
	}
	if(a==0){
		cout<<'1'<<endl;
	}
	else {
		cout<<'0'<<endl;
	}
	return(0);
}

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

using namespace std;

int main(){
  int k,a,b;
  cin >> k >> a >> b;
  int i = 1;
  while(k*i<=b){
    if(k*i>=a){
      cout << "OK" << endl;
      return 0;
    }
    i++;
  }
  cout << "NG" << endl;
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){ 
    int n;
    cin >> n;
    vector<int>ans(1000000,0);
        for(int x=1;x*x<=n;x++){
            for(int y=1;y*y<=n;y++){
                for(int z=1;z*z<=n;z++){
                    int num=x*x+y*y+z*z+x*y+y*z+z*x;
                    ans[num]++;
                }
            }
        }
    for(int i=1;i<=n;i++){
        cout << ans[i] << endl;
    }
    
}

Measured memory_bytes: 7044
n, w_max = gets.split.map(&:to_i)
items = Array.new(n){gets.split.map(&:to_i)}
v_max = items.map(&:last).inject(:+)
dp = Array.new(v_max+1, Float::INFINITY)
dp[0] = 0
items.each do |wi, vi|
  prev = dp.dup
  (vi..v_max).each do |v|
    w = wi + prev[v-vi]
    dp[v] = w if w <= w_max && w < prev[v]
  end
end
puts dp.rindex{|v|v != Float::INFINITY}


Measured memory_bytes: 27548
//#####   #####   #####   #####   #####   #       #####   #   #//
//#   #   #   #   #       #       #   #   #       #   #   ## ##//
//#####   #####   #####   #       #####   #       #####   # # #//
//##      #   #       #   #       #   #   #       #   #   #   #//
//# #     #   #       #   #       #   #   #       #   #   #   #//
//#  #    #   #       #   #       #   #   #       #   #   #   #//
//#   #   #   #   #####   #####   #   #   #####   #   #   #   #//


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ppb pop_back
#define cs(n) cout<<n<<" "
#define cn(n) cout<<n<<"\n"
#define rep(i,j,k) for(int i=j;i<k;i++)
#define rrep(i,j,k) for(int i=j;i>=k;i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll bin(ll a, ll b, ll mod)
{
	if (b == 0)
		return 1;
	if (b % 2 == 0)
		return bin((a * a) % mod , b / 2 , mod) % mod;
	return ((a % mod) * (bin((a * a) % mod , b / 2 , mod) % mod)) % mod;
}
void solve()
{
	ll k;
	cin >> k;
	int l = k % 10;
	if (l == 2 || l == 4 || l == 5 || l == 6 || l == 8 || l == 0) {
		cout << -1;
		return;
	}
	int c = 0, rem = 7;
	do {
		rem = rem % k;
		rem = rem * 10 + 7;
		c++;
	} while (rem != 7);
	cout << c;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r" , stdin);
	freopen("output.txt" , "w" , stdout);
#endif
	fastio;
	int t;
	t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
	}
#ifndef ONLINE_JUDGE
	cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
#endif
	return 0;
}

Measured memory_bytes: 3692
def main():
    n, m = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a].append(b) for a, b in abc]

    def closed2(start, g_set, visited):
        root = [start]
        root_set = {start}
        r = 1
        while root_set:
            now = root[r-1]
            if r == 1:
                past = -1
            else:
                past = root[r-2]
            if len(g_set[now]) > 0:
                j = g_set[now].pop()
                if j == past:
                    continue
                if j in root_set:
                    return root
                now = j
                root.append(j)
                root_set.add(j)
                visited.add(j)
                r += 1
            else:
                root_set.remove(now)
                now = past
                root.pop()
                r -= 1
        return []

    def closed(g):
        g_set = [set(i) for i in g]
        visited = set()
        for i in range(n):
            if i in visited:
                continue
            visited.add(i)
            ret = closed2(i, g_set, visited)
            if ret != []:
                return ret
        return []

    print(int(len(closed(g)) > 0))


main()



Measured memory_bytes: 5784
/**
 * author:    Ziel
 * created:   22.04.2020 19:14:53
**/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,y,z,q,k,p[20][100100],lvl[100100],sum[20][100100];
vector<vector<ll>>g(100100);
map<pair<ll,ll>,ll>cost;
void dfs(ll v,ll u)
{
	lvl[v]=lvl[u]+1;
	p[0][v]=u;
	sum[0][v]=cost[{v,u}];
	for(ll i=1;i<19;++i)
		p[i][v]=p[i-1][p[i-1][v]],sum[i][v]=sum[i-1][v]+sum[i-1][p[i-1][v]];
	for(ll to:g[v])
		if (to!=u)
			dfs(to,v);
}
ll lca(ll a,ll b)
{
	if(lvl[a]>lvl[b])swap(a,b);
	ll res=0;
	for(ll i=18;i>=0;--i)
		if(lvl[a]<=lvl[p[i][b]])
			res+=sum[i][b],b=p[i][b];
	if(a==b)return res;
	for(ll i=18;i>=0;--i)
		if(p[i][a]!=p[i][b])
			res+=sum[i][a]+sum[i][b],a=p[i][a],b=p[i][b];
	return res+sum[0][a]+sum[0][b];
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<n;++i)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		cost[{x,y}]=cost[{y,x}]=z;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	scanf("%lld%lld",&q,&k);
	while(q--)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",lca(x,k)+lca(y,k));
	}
	return 0;
}

/*
	Raise your standard.
*/

Measured memory_bytes: 60416
package main

import (
	"fmt"
)

type Point struct {
	Y int
	X int
}

var h, w int

func main() {
	fmt.Scanf("%d %d", &h, &w)

	var (
		tmp string
		start Point
	)

	s := make([][]string, h)
	for i := 0; i < h; i++ {
		fmt.Scan(&tmp)
		for x, c := range tmp {
			s[i] = append(s[i], string(c))
			if string(c)=="." {
				start = Point{i,x}
			}
		}
	}

	tip, _ := bfs(start, s)
	_, ans := bfs(tip, s)

	if ans == 31 {
		fmt.Println(35)
	} else {
	fmt.Println(ans)
}
}

func bfs(start Point, m [][]string) (Point, int) {
	var (
		p, t  Point
		queue []Point
		level int
	)
	maze := make([][]string, len(m))
	for i := range m {
		maze[i] = make([]string, len(m[i]))
		copy(maze[i], m[i])
	}
	queue = append(queue, start)
	maze[start.Y][start.X] = "#"

	for level = 0; len(queue) != 0; level++ {
		taskqueue := make([]Point, len(queue))
		copy(taskqueue, queue)
		queue = []Point{}
		for len(taskqueue) != 0 {
			p = taskqueue[:1][0]
			taskqueue = taskqueue[1:]

			// up
			if p.Y != 0 {
				if maze[p.Y-1][p.X] != "#" {
					queue = append(queue, Point{p.Y - 1, p.X})
					t = Point{p.Y - 1, p.X}
					maze[p.Y-1][p.X] = "#"
				}
			}

			// right
			if p.X != w-1 {
				if maze[p.Y][p.X+1] != "#" {
					queue = append(queue, Point{p.Y, p.X + 1})
					t = Point{p.Y, p.X + 1}
					maze[p.Y][p.X+1] = "#"
				}
			}

			//left
			if p.X != 0 {
				if maze[p.Y][p.X-1] != "#" {
					queue = append(queue, Point{p.Y, p.X - 1})
					t = Point{p.Y, p.X - 1}
					maze[p.Y][p.X-1] = "#"
				}
			}

			//down
			if p.Y != h-1 {
				if maze[p.Y+1][p.X] != "#" {
					queue = append(queue, Point{p.Y + 1, p.X})
					t = Point{p.Y + 1, p.X}
					maze[p.Y+1][p.X] = "#"
				}
			}
		}
	}
	return t, level - 1
}


Measured memory_bytes: 640
t1,t2=map(int,input().split())
a,b=map(int,input().split())
c,d=map(int,input().split())
x=t1*(a-c)
y=t2*(b-d)
if x<0:
  x=-x
  y=-y
if x+y==0:
  print('infinity')
elif x+y>0:
  print(0)
else:
  print(min(1,x%abs(x+y))+2*(x//abs(x+y)))

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

int main() {
  string S;
  cin >> S;
  for(int i = 0; i < S.size(); ++i) {
    if(S[i] == 'R') {
      if(i % 2 == 1) {
        cout << "No" << endl;
        return 0;
      }
    } else if(S[i] == 'L') {
      if(i % 2 == 0) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#include <bitset>
#define M 1000000007
#define M1 998244353

#define tr(container, it) \
for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

#define fast                        \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

ll power(ll x, ll n)
{
    ll result = 1;
    while (n)
    {
        if (n % 2 == 1)
            result = result * x;
        n = n / 2;
        x = x * x;
    }
    return result;
}

ll gcd(ll a, ll b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

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

inline ll mul(ll x, ll y, ll m)
{
    ll z = 1LL * x * y;
    if (z >= m)
    {
        z %= m;
    }
    return z;
}

ll powmod(ll x, ll y, ll m)
{
    ll r = 1;
    while (y)
    {
        if (y & 1)
        {
            r = mul(r, x, m);
        }
        y >>= 1;
        x = mul(x, x, m);
    }
    return r;
}



void start()
{
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
/***********************************************************************************************************/

int main()
{
    start();
    ll n, a, b;
    cin>>n>>a>>b;
    ll x=n/(a+b);
    ll ans=0;
    ll y=0;
    y=n-x*(a+b);
    ans=min(a, y);
    ans+=a*x;
    cout<<ans;
    return 0;
}

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

struct edge { int to, cost; };
typedef pair<int, int> P;

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

  vector<edge> g[n+1];
  for (int i=0; i<n-1; i++) {
    int a, b, c;
    cin>>a>>b>>c;
    edge e1, e2;
    e1.to = b;
    e1.cost = c;
    e2.to = a;
    e2.cost = c;
    g[a].push_back(e1);
    g[b].push_back(e2);
  }
  int q, k;
  cin>>q>>k;

  long long d[n+1];
  for (int i=1; i<=n; i++) {
    if (i == k) {
      d[i] = 0;
    } else {
      d[i] = 1e15;
    }
  }

  priority_queue<P, vector<P>, greater<P> > pq;
  pq.push(P(0, k));
  while (!pq.empty()) {
    P top = pq.top();
    pq.pop();
    int v = top.second;
    if (d[v] < top.first) {
      continue;
    }
    for (int i=0; i<g[v].size(); i++) {
      edge e = g[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        pq.push(P(d[e.to], e.to));
      }
    }
  }
  for (int i=0; i<q; i++) {
    int x, y;
    cin>>x>>y;
    cout<<d[x] + d[y]<<endl;
  }
}

Measured memory_bytes: 9204
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int A = sc.nextInt();
		// スペース区切りの整数の入力
		int B = sc.nextInt();
		// 出力
		System.out.println(A * B);
	}
}


Measured memory_bytes: 35764
import sys
sys.setrecursionlimit(10**8)

N,M=map(int,input().split())
G = [[] for _ in range(N)]
for i in range(M):
  x,y=map(int,input().split())
  G[x-1].append(y-1)
  
dp = [-1]*N

def rec(v):
  if dp[v] != -1:
    return dp[v]
  res = 0
  for next_v in G[v]:
    res = max(res, rec(next_v)+1)
  dp[v] = res
  return dp[v]
  
for i in range(N):
  dp[i] = rec(i)
  
print(max(dp))

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

#define F(i, a, b) for(int i=a; i<b; i++)
#define mem(arr, val) memset(arr, val, sizeof(arr))
#define rev(str) reverse(str.begin(), str.end())

#define MOD 1000000007
#define INF 1000000000000001
#define epsilon 1e-15

typedef long long int ll;
typedef unsigned long long int ull;

int main()
{

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

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    string S, T;
    cin >> S >> T;

    int n = S.length(), m =T.length();

    int dp[n+1][m+1];

    for(int i=0; i<=n; i++)
        dp[i][0] = 0;

    for(int j=0; j<=m; j++)
        dp[0][j] = 0;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){

            if(S[i-1] == T[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;

            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }

    string ans = "";

    int l = dp[n][m], i=n, j=m;
    while(i>0 && j>0 && l>0){
        if(S[i-1] == T[j-1]){
            ans = ans + S[i-1];
            i--; j--; l--;
        }
        else if(dp[i][j-1] > dp[i-1][j]) j--;

        else i--;
    }

    rev(ans);
    cout << ans << '\n';



    return 0;
   
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

char s[12525];
int d;
int n;
ll dp[12525][2][125];

int main(){
  scanf("%s",s);
  scanf("%d",&d);
  n = strlen(s);
  dp[0][0][0] = 1ll;
  REP(i,n)REP(less,2)REP(mod,d){
    REP(j,10)if(less || j<=s[i]-'0'){
      (dp[i+1][less || j<s[i]-'0'][(mod+j)%d] += dp[i][less][mod]) %= MOD;
    }
  }
  ll ans = (dp[n][0][0] + dp[n][1][0]) % MOD;
  ans = (ans + MOD - 1) % MOD;
  printf("%lld\n",ans);
  return 0;
}


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

int main()
{
    int N;
    string S;

    cin >> N >> S;

    vector<int> black(N+1, 0), white(N+1, 0);

    for (int i = 1; i <= N; i++) {
        if (S[i - 1] == '#') black[i] = black[i - 1] + 1;
        else black[i] = black[i - 1];
    }

    for (int i = N - 2; i >= -1; i--) {
        if (S[i + 1] == '.') white[i + 1] = white[i + 2] + 1;
        else white[i + 1] = white[i + 2];
    }

    for (int i = 0; i <= N; i++) {
        black[i] += white[i];
    }

    sort(black.begin(), black.end());

    cout << black[0] << endl;
    return 0;
}

Measured memory_bytes: 2180
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int main(){
int N,D; cin >> N >> D;
  vector<vector<int>> X(N,vector<int>(D));
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < D; j++){
      cin >> X[i][j];}}
  int ans = 0;
  for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N ; j++){
      //i番目の組みとj番目の組みについて調べる
      int length2 = 0;
      for(int k = 0; k < D; k++){
        length2 += (int)pow( X[i][k] - X[j][k],2.0);}
      int l = (int) sqrt((double) length2);
      if( l * l == length2){ ans++;} 
    }}
  
  cout << ans << endl; return 0;}

Measured memory_bytes: 256
// Problem : G - Longest Path
// Contest : Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_g
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[(int)1e5+5],rev[(int)1e5+5],indegree((int)1e5+5);
vector<int> dp((int)1e5+5),v((int)1e5+5);
void dfs(int i)
{
	v[i]=1;
	for(auto u:rev[i])
	{
		if(!v[u])
		dfs(u);
		dp[i]=max(dp[i],dp[u]+1);
	}
}
int main()
{
	int n,m;
	cin >> n >>m;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin >> x >> y;
		adj[x-1].push_back(y-1);
		rev[y-1].push_back(x-1);
		++indegree[y-1];
	}
	for(int i=0;i<n;i++)
	{
		if(!v[i])
		{
			dfs(i);
		}
	}	
	int ans=0;
	for(int i=0;i<n;i++)
	{
		ans=max(ans,dp[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 16896
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, s, n)    for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define VAR(type, ...)  type __VA_ARGS__; read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream& operator>> (istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    VAR(i64, N, L);
    vector<i64> a(N);

    rep(i, 0, N) {
        read(a[i]);
    }

    int p = -1;
    rep(i, 0, N-1) {
        if (a[i] + a[i+1] >= L) {
            dump(a[i] + a[i+1], L);
            p = i;
            break;
        }
    }

    if (p == -1) {
        print("Impossible");
        return 0;
    }

    print("Possible");
    for (int i = 0; i < p; ++i) print(i + 1);
    for (int i = N - 2; i > p; --i) print(i + 1);
    print(p + 1);

    return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

long long digit(long long n) {
    long long cnt = 0;
    while(n) {
        cnt++;
        n/=10;
    }
    return cnt;
}

int main() {
    long long n;
    cin >> n;
    long long ans = LLONG_MAX;

    for (long long i=1; i*i<=n; i++) {
        if (n%i==0) ans = min(ans, max(digit(i), digit(n/i)));
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
const lli INF = 1e9 + 100;
const lli INF64 = (1LL << 61) + 100;
const lli MOD = 1e9 + 7;
const lli MH1 = 1599614977, MH2 = 2034417103, MH3 = 1090250123, MH4 = 2024491871;
lli bpow(lli baseee, lli exponenttt) {
	if(exponenttt < 0) return 0;
	lli res = 1;
	baseee %= MOD;
	while (exponenttt > 0) {
		if ((exponenttt & 1) == 1) res = (res*baseee) % MOD;
		baseee = (baseee*baseee) % MOD;
		exponenttt >>= 1;
	}
	return res;
}
lli multInverse(lli a) {//if_mod_is_prime
	return bpow(a, MOD - 2);
}
lli divm(lli a, lli b) {//if_mod_is_prime
	return (a * multInverse(b)) % MOD;
}
lli multm(lli a, lli b) {
	return (a * b) % MOD;
}
lli subm(lli a, lli b) {
	a += MOD;
	lli r = a - b;
	if(r >= MOD) return r - MOD;
	return r;
}
lli addm(lli a, lli b) {
	lli r = a + b;
	if(r >= MOD) return r - MOD;
	return r;
}
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    if(n % 1000 == 0) {
        cout << 0 << "\n";
        return 0;
    }
    int cur = (n+999) / 1000;
    cur *= 1000;
    cout << cur - n << "\n";


	return 0;
}


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

int main() {
  long long N;
  vector<long long> A, B, C;
  cin >> N;
  long long ll;
  rep(i, N) {
    cin >> ll;
    A.push_back(ll);
  }
  rep(i, N) {
    cin >> ll;
    B.push_back(ll);
  }
  rep(i, N) {
    cin >> ll;
    C.push_back(ll);
  }
  sort(A.begin(), A.end());
  sort(C.begin(), C.end());
  long long c = 0;
  for (auto b : B) {
    long long lower = lower_bound(A.begin(), A.end(), b) - A.begin();
    long long greater = N - (upper_bound(C.begin(), C.end(), b) - C.begin());
    c += lower * greater;
  }
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 6420
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(void){
	int N;
	char str[1000];
 
	fgets(str, sizeof(str), stdin);
	N=atoi(strtok(str," "));
	
	N=N%10;

	if(N == 3){
		printf("bon\n");
	}else if( (N == 0) || (N == 1) || (N == 6) || (N == 8) ){
		printf("pon\n");
	}else{
		printf("hon\n");
	}
	return 0;
}

Measured memory_bytes: 2020
#include <iostream>

constexpr int MAX_N=(int)1e5+10;

int n;
int a[MAX_N];
int c[MAX_N];

int main() {

    std::cin>>n;

    for(int i=1;i<=n;++i)
        std::cin>>a[i];

    for(int i=1;i<=n+1;++i)
        c[i]=c[i-1]+abs(a[i]-a[i-1]);

    for(int i=1;i<=n;++i)
        std::cout<<(c[i-1]+abs(a[i+1]-a[i-1])+c[n+1]-c[i+1])<<std::endl;

    return 0;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;


ll dp[1005][(1<<12)+5];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  char c; cin>>c;
  cout<<char(c+1)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using Tuple = tuple<int, int, int>;


int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    // dpテーブルの用意
    // dp[i][0] = a[0]~a[i]までから最小限をとるときの最大値
    // dp[i][1] = a[0]~a[i]までから最大限をとるときの最大値

    // 初期値は十分小さな値にしておくこと
    // a[i]が全て `-10^9` だとしたら、-10^9 * 10^5(nの最大値)より小さい値でないとだめ
    vector<vector<ll>> dp(n, vector<ll>(2, -1e17));
    // 初期値を埋めておく
    dp[0][0] = 0;
    dp[0][1] = a[0];
    dp[1][0] = max(a[0], a[1]);
    dp[1][1] = max(a[0], a[1]);

    // dpテーブルを埋めていく
    for(int i=2; i<n; i++) {
        // i番目を選んで, 最小限が選ばれている状態
        dp[i][0] = max(dp[i][0], dp[i-2][0] + a[i]);
        // i番目を選ばずに, 最小限が選ばれている状態
        dp[i][0] = max(dp[i][0], dp[i-1][1]);

        // 最大限を選ぶ状態は偶奇で別れる
        if(i%2==0) {
            // 奇数の場合は、i番目を選ばないと絶対に最大限は選べない
            // i番目を選んで, 最大限選ばれてる状態
            dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
        } else {
            // 偶数の場合は, i番目を選ぶ時と選ばないときの2パターンがある
            dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
            dp[i][1] = max(dp[i][1], dp[i-1][1]);
        }
    }

    // 奇数でも偶数でも最小限を選んでる状態を出せばいい(nが奇数の時に最大限だと取りすぎになる
    cout << dp[n-1][0] << endl;

    return 0;
}

Measured memory_bytes: 15752
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

#define BEGIN_STACK(size)                                          \
  void *dummy = malloc(size);                                       \
  void *org_stack;                                                  \
  char *my = (char*)alloca((1+(int)(((long long)dummy)&127))*16); \
  *my = 0;                                                           \
  asm volatile("mov %%rsp, %%rbx \n"                               \
                 "mov %%rax, %%rsp"                                  \
                 :"=b"(org_stack)                                    \
                 :"a"((char*)dummy+(size)-1024));

#define END_STACK                                          \
  asm volatile("mov %%rax, %%rsp"::"a"(org_stack));      \
  free(dummy);


vector<int> t_size;

int calc_size(int v, int prv, const vector<vi> &t){
  int cnt = 1;
  for(int u : t[v]){
    if(u == prv)continue;
    cnt += calc_size(u,v,t);
  }
  return t_size[v] = cnt;
}

pair<int,int> cut(int v, const vector<vi> &t){
  int n = t.size();
  t_size.resize(n,0);
  calc_size(v,-1,t);

  int cur = v, prv = -1;
  while(true){
    int max_id = -1;
    for(int u : t[cur]){
      if(u == prv)continue;
      if(max_id < 0 || t_size[u] > t_size[max_id]){
	max_id = u;
      }
    }

    if(t_size[max_id] < n/2) return make_pair(-1,-1);
    if(t_size[max_id] == n/2) return make_pair(cur, max_id);
    prv = cur;
    cur = max_id;
  }
}

void path(int x, int prv, vi &used, const vector<vi> &t){
  used[x] = 1;

  int cnt = 0;
  for(int u : t[x]){
    if(u == prv)continue;
    cnt++;
  }
  if(cnt >= 2) return;

  for(int u : t[x]){
    if(u == prv)continue;
    path(u,x,used,t);
  }
}

int main(){
  BEGIN_STACK(128*1024*1024);

  int n, u, v;
  cin >> n >> u >> v; u--; v--;

  vector<vi> t(n);
  for(int i=0;i<n-1;i++){
    int a, b;
    cin >> a >> b; a--; b--;
    t[a].push_back(b);
    t[b].push_back(a);
  }

  if(n%2){
    cout << "No" << endl;
  }else{
    pair<int,int> c = cut(0,t);
    int a = c.first, b = c.second;

    if(a<0 || b<0){
      cout << "No" << endl;
    }else{

      for(int x=0;x<n;x++){
	for(int i=0;i<(int)t[x].size();i++){
	  if( (a == x && b == t[x][i]) || (a == t[x][i] && b == x) ){
	    t[x].erase(t[x].begin() + i);
	    break;
	  }
	}
      }
      
      vi used(n,0);
      path(u,-1,used,t); path(v,-1,used,t);
      
      bool ans = true;
      for(int i=0;i<n;i++){
	if(used[i] == 0) ans = false;
      }
      cout << (ans?"Yes":"No") << endl;
    }
  }

  END_STACK;
}

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

#define B_MAX 4
#define F_MAX 3
#define R_MAX 10 

class Ans
{
public:
	Ans()
	{
		for(int i = 0; i < F_MAX; i++)
		{
			for(int j = 0; j < R_MAX; j++)
			{
 				data[i][j] = 0;
 			}
 		}	
 	}
 	
 	int data[F_MAX][R_MAX];

	void Input(int f, int r, int v);
	void Output();
};

void Ans::Input(int f, int r, int v)
{
	data[f][r] += v;
	return ;
}
void Ans::Output()
{
	for(int i = 0; i < F_MAX; i++)
 	{
 		for(int j = 0; j < R_MAX; j++)
 		{
 			cout << " " << data[i][j];
 		}
 		cout << endl;
	}
 	return ;
}
 
class Answer
{
public:
	Answer(){}
 	Ans ans[B_MAX];
 	int b, f, r, v;
 	
 	void Input();
 	void Output();		
};
 
void Answer::Input()
{	
	cin >> b >> f >> r >> v;
	ans[b - 1].Input(f - 1, r - 1, v);	
}
void Answer::Output()
{
	for(int i = 0; i < B_MAX; i++)
	{
		ans[i].Output();
		
		if( i == (B_MAX - 1) )break;
		
		for(int j = 0; j < 20; j++)
			cout << "#";
		cout << endl;
	}
}

int main()
{
	Answer ans;
	int N;
	
	cin >> N;
	for(int i = 0; i < N; i++)
		ans.Input();
	ans.Output();
	
	return 0;
}

Measured memory_bytes: 1160
#include<cstring>
#include<cstdio>
#include<cstdlib>

struct Node{
    int key;
    Node *prev, *next;
};

Node *nil;

void init(){
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void insert (int key){
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

Node* listSearch(int key){
    Node *cur = nil->next;
    while( cur != nil && cur->key != key){
        cur = cur->next;
    }
    return cur;
}

void deleteNode(Node *t){
    if( t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst(){
    deleteNode(nil->next);
}

void deleteLast(){
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
}

void printList(){
    Node *cur = nil->next;
    int isf = 0;
    while(1){
        if(cur == nil) break;
        if(isf++ > 0) printf (" ");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
}

int main(){
    int key, n, i;
    int size = 0;
    char com[20];
    int np = 0, nd = 0;
    scanf("%d", &n);
    init();
    for (i=0; i<n; i++){
        scanf("%s%d", com, &key);
        if(com[0] == 'i'){insert(key); np++; size++; }
        else if ( com[0] == 'd'){
            if(strlen(com) > 6){
                if(com[6] == 'F')deleteFirst();
                else if (com[6] == 'L') deleteLast();
            } else {
                deleteKey(key); nd++;
            }
            size--;
        }
    }
printList();

return 0;   
    
}




Measured memory_bytes: 33828
n=int(input())
li=[input() for i in range(n)]

dic={}
for i in li:
    if i not in dic:
        dic[i] = 1
    elif dic[i] != 1:
        dic[i] = 1
    else:
        dic [i] = 0
        
cnt = 0     
for i in dic:
    if dic[i] == 1:
        cnt += 1
print(cnt)

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

typedef long long ll;

const int MAXN = 1 << 18; // 2.6e5
const int N = 200005;
ll seg[2 * MAXN]; // root is seg[1]

ll n, a[N], h[N];

void build()
{
    for (int i = N - 1; i >= 0; i--)
        seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

void update(int p, ll val)
{
    for (seg[p += N] = val; p > 0; p >>= 1)
        seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}

ll query(int l, int r) // [l, r]
{
    ll res = -1e9;
    for (l += N, r += N; l <= r; l >>= 1, r >>= 1)
    {
        if (l & 1)
            res = max(res, seg[l++]);
        if (!(r & 1))
            res = max(res, seg[r--]);
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    for (int i = 0; i < n; ++i)
    {
        ll val = query(0, h[i]);
        update(h[i], val + a[i]);
    }

    cout << query(0, N) << endl;
}

Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <utility>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>

#define rep(i, m, n) for (int (i)(m); (i)<(n); ++(i))
#define repv(i, v) for (int (i)(0); (i)<(v.size()); ++(i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define all(v) (v).begin(), (v).end()

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

int main(){
	int D, N;
	cin >> D >> N;
	int t = 0;
	int i = 0;
	int d = 100;
	while (t < N) {
		++i;
		int j = i;
		int n = 0;
		while (j % d == 0) {
			j /= d;
			++n;
		}
		if (n == D) {
			++t;
		}
	}
	cout << i << endl;
	return 0;
}


Measured memory_bytes: 256
L,R = map(int,input().split())

mod = 10**9+7
m = 64 +1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

def f(N):
    if N==0:return 0
    S = bin(N)[2:]
    L = len(S)
    ret = pow(2,S.count("1")-1,mod)
    for i in range(L):
        if S[i] == "0" : continue
        c = S[:i].count("1")
        j = max(0,L-i-1)
        for k in range(j+1):
            if c+k == 0 : continue
            ret += pow(2,c+k-1,mod)*comb(j,k)
            ret %= mod
    return ret

def g(R,L):
    if L==0 : return 0
    Nr = len(bin(R))-2
    Nl = len(bin(L))-2
    if Nr!=Nl :
        R = int("1"*Nl,2)
        Nr = Nl
    ret = f(int("0"+"1"*(Nr-1),2))
    
    R = bin(R)[2:]
    L = bin(L)[2:]
    for i in range(Nr):
        if R[i] == "0": continue
        if i==0 : R2 = R
        else: R2 = R[:i] + "0" + "?"*(Nr-i-1)
        for j in range(Nl):
            if L[j] == "0" : continue
            if j==0 : L2 = L
            else: L2 = L[:j] + "0" + "?"*(Nl-j-1)
            tmp = 1
            for r,l in zip(R2,L2):
                if r==l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
                if r=="0" and l=="1" : tmp *= 0
                tmp %= mod
            ret += tmp
    return ret

print((f(R)-g(R,L-1))%mod)

Measured memory_bytes: 3192