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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> n_candies(n, 0);
    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            a--;
            n_candies[a]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (n_candies[i] == 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

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

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

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

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

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

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    int ans = 0;
    if(n % k != 0) ans = 1;
    PUTS(ans);
}

Measured memory_bytes: 892
#pragma GCC optimize("O3")
 #pragma GCC optimize("unroll-loops")
 #pragma GCC optimize("fast-math")
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define int long long
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

void accell() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
const int N = 1e5 + 5;

int dp[N][4];

signed main() {
    accell();
    int n, x;
    cin >> n >> x;
    vector<int>a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<int>ans(n, 1e18);
    int ass = 1e18;
    for (int k = 1; k <= n; ++k) {
        for (int j = 0; j < n; ++j) {
            int p = (j - k + 1 + n) % n;
            ans[j] = min(ans[j], a[p]);
        }
        int res = 0;
        for (int j = 0; j < n; ++j)
            res += ans[j];
        ass = min(ass, res + (k - 1) * x);
    }
    cout << ass << '\n';
    return 0;
}


Measured memory_bytes: 256
import java.io.*
import java.util.*

fun solve(N: Int){
    println(N/3)
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toInt()
    solve(N)
}



Measured memory_bytes: 29608
N, M, Q = map(int, input().split())
G = [[0]*N for i in range(N)]
for i in range(M):
  L, R = map(int, input().split())
  L, R = L-1, R-1
  G[L][R] += 1
#print(G)
S = [[0]*N for i in range(N)]
for i in range(N):
  s = 0
  for j in range(N):
    s += G[i][j]
    S[i][j] = s
#print(S)
T = [[0]*N for i in range(N)]
for j in range(N):
  s = 0
  for i in reversed(range(N)):
    s += S[i][j]
    T[i][j] = s
#print(T)
for i in range(Q):
  p, q = map(int, input().split())
  p, q = p-1, q-1
  print(T[p][q])


Measured memory_bytes: 15220
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>

using namespace std;
int main(){
	int n,l;
	int sum=0,eat=10000,eat_;

	scanf("%d %d",&n,&l);

	for(int i=1;i<=n;i++){
		sum+=l+i-1;
		//cout<<l+i-1<<endl;
		if(eat>abs(l+i-1)){
			eat=abs(l+i-1);
			eat_=l+i-1;
		}
	}	
	sum-=eat_;

	//cout<<"eat"<<eat_;
	//cout<<"ans"<<sum;

	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    int i = 1;
    FOR(i, 1, B + 1, 1) {
        if (A * i % B == C) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}


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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    string s;
    cin >> s;
    int n = s.size();

    reverse(all(s));

    vector<vector<ll>> dp(n+1, vector<ll>(13, 0));
    dp[0][0] = 1;
    int pow10 = 1;

    REP(i, n){
        int d = (s[i] == '?' ? -1 : s[i] - '0');
        REP(j, 10){
            if(d == -1 || d == j){
                REP(k, 13){
                    int m = (k + pow10 * j) % 13;
                    dp[i+1][m] += dp[i][k];
                    dp[i+1][m] %= MOD;
                }
            }
        }
        pow10 = pow10 * 10 % 13;
    }

    cout << dp[n][5] << endl;
    return 0;
}


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

using namespace std;

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

void solve()
{
	int n;
	cin >> n;
	vector<int> b(n);
	for (auto&& i : b)
	{
		cin >> i;
	}
	stack<int> s;
	while(n)
	{
		for(int i = n - 1; i >= 0; i--)
		{
			if(b[i] == i + 1)
			{
				b.erase(begin(b) + i);
				s.push(i + 1);
				break;
			}
		}
		if(b.size() == n--)
		{
			cout << "-1\n";
			return;
		}
	}
	while(s.size())
	{
		cout << s.top() << "\n";
		s.pop();
	}
}

int main()
{
	solve();
}


Measured memory_bytes: 256
// AtCoder template
// 見た奴全員saba!
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)

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

    int n,x; cin >> n >> x;
    int l[n]; rep(i,n) cin >> l[i];
    int d = 0;
    int ans = 0;
    rep(i,n){
        if(d + l[i] > x) break;
        ans++;
        d += l[i];
    }
    cout << ans+1 << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(int i = 0; i < n; i++)



int main() {
    ll n, k;
    cin >> n >> k;
    
    vector<ll> a(n), b(n), c(n);
    REP(i, n){
        cin >> a[i];
    }
    
    b[0] = a[0];
    c[0] = max(0LL, a[0]);
    for(int i = 1; i < n; i++){
        b[i] = b[i - 1] + a[i];
        c[i] = c[i - 1] + max(0LL, a[i]);
    }
    
    ll ans = max(b[k - 1], 0LL) + c[n - 1] - c[k - 1];
    for(int i = 0; i < n - k; i++){
        ans = max(ans, max(b[i + k] - b[i], 0LL) + c[n - 1] - c[i + k] + c[i]);
    }
    
    cout << ans << endl;
}

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

int main(){
    int N, S;
    int cnt = 0;
    cin >> N >> S;
    for(int X = 0; X < N+1; X++){
        for(int Y = 0; Y < N+1-X; Y++){
            int Z = N - X - Y;
            if(10000*X + 5000*Y + 1000*Z == S){
                cnt +=1;
                cout << X << " " << Y << " " << Z << endl;
                return 0;
            }
        }
    }

    if(cnt == 0) cout << "-1 -1 -1" << endl;

    return 0;
}

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

using namespace std;

int A, B, C, D;

int main()
{
	scanf("%d %d %d %d", &A, &B, &C, &D);
	int finalAns = min(A, B);
	finalAns += min(C, D);
	printf("%d\n", finalAns);
	
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A[][],B[][];
		A= new int [3][3];
		B= new int [3][3];
		for (int i=0;i<3;i++) {
			for (int j=0;j<3;j++) {
				A[i][j]= sc.nextInt();
				B[i][j]=0;
			}
		}
		int N ;
		N= sc.nextInt();
		for (int i=0;i<N;i++) {
			int c =sc.nextInt();
			for (int j=0;j<3;j++) {
				for (int k=0;k<3;k++) {
					if(A[j][k]==c) {
						B[j][k]=1;
					}
				}
			}
		}
		for (int i=0;i<3;i++) {
			if(B[i][0]==1&&B[i][1]==1&&B[i][2]==1) {
				System.out.println("Yes");
				return;
			}
		}
		for (int i=0;i<3;i++) {
			if(B[0][i]==1&&B[1][i]==1&&B[2][i]==1) {
				System.out.println("Yes");
				return;
			}
		}
		if(B[0][0]==1&&B[1][1]==1&&B[2][2]==1) {
			System.out.println("Yes");
			return;
		}
		if(B[2][0]==1&&B[1][1]==1&&B[0][2]==1) {
			System.out.println("Yes");
			return;
		}
		System.out.println("No");
	}
}

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

int main(){
    int n, m; cin >> n >> m;
    vector<int> num(n, -1);
    vector<int> s(m);
    vector<int> c(m);
    rep(i, m) {
        cin >> s.at(i) >> c.at(i);
        s[i]--;
    }

    rep(i, m) {
        if (num[s[i]] != -1 && num[s[i]] != c[i]) {
            cout << -1 << endl;
            return 0;
        }
        num[s[i]] = c[i];
    }

    if (n > 1) {
        if (num[0] == 0) {
            cout << -1 << endl;
            return 0;
        } else if (num[0] == -1) {
            num[0] = 1;
        }
        rep(i, n) {
            if (num[i] == -1) cout << 0;
            else cout << num[i];
        }
        cout << endl;
        return 0;
    } else { // N == 1
        if (num[0] == -1) num[0] = 0;
        cout << num[0] << endl;
        return 0; 
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits.h>
#include <string>
#include <string.h>
#include <sstream>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;

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

  if( a < b ){
    cout << "a < b" << endl;
  }else if( a > b ){
    cout << "a > b" << endl;
  }else{
    cout << "a == b" << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include<stdio.h>
#define N 100

int main(){
  int i,j,n,key,d;
  int A[N];

  scanf("%d",&n);
  for(i = 0; i < n; i++) scanf("%d",&A[i]);
  for(d = 0;d < n - 1; d++)  printf("%d ",A[d]);
  printf("%d",A[n - 1]);
  printf("\n"); 

  for(i = 1; i <= n - 1;i++){
    key = A[i];
    j = i - 1;
    while(j >= 0 && A[j] > key){
      A[j+1] = A[j];
      j--;
      A[j+1] = key;
    }
   for(d = 0;d < n-1; d++) printf("%d ",A[d]);
   printf("%d",A[n - 1]);
    printf("\n"); 
  }
  return 0;
}



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

int main(){
    int n;
    cin >> n;
    int ans = (n/500) * 1000 + (((n%500)/5)*5);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int n=1e6+456;
long long w[n + 2], v[n + 2], u[n +2 ], dp[n + 2];
int main()
{
	int N, W;
	long long ans = 0;
	cin >> N >> W;

	u[0] = 1;
	for(int i = 1; i <= N; i  ++)
	{
		cin >> w[i] >> v[i];
	}
	for(int i = 1; i <= N; i ++)
	{
		for(int j = W-w[i]; j >= 0; j --)
		{
			dp[j + w[i]] = max(dp[j] + v[i], dp[j + w[i]]);
			if(j + w[i] <= W)
			{
				ans = max(ans, dp[j + w[i]]);
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 7168
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();

		long[] array = new long[] { A, B, C };
		Arrays.sort(array);

		if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) {
			System.out.println(0);
		} else {
			System.out.println(array[0] * array[1]);
		}
	}
}


Measured memory_bytes: 9812
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,t,c=0;
    while(cin>>n>>t>>m)
    {
        vi a;
         rep(i,n)
         {
             vp(a,x);
         }
         s=c=0;
         c=INT_MAX;
        double cc=c*1.0;
         rep(i,n)
         {
             double d=t-(a[i]*0.006);
             double f=abs(d-(m*1.0));
             if(f<cc)
             {
                 cc=f;
                 s=i+1;
             }
         }
         cout<<s<<en;
    }
}



Measured memory_bytes: 256
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var a = 1L;
        var b = 0L;
        for (int i = 0; i < n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var q = int.Parse(line[0]);
            var x = int.Parse(line[1]);
            if (q == 1) { a *= x; b *= x; }
            else if (q == 2) { b += x; }
            else b -= x;
        }
        Console.WriteLine("{0} {1}", -b, a);
    }
}



Measured memory_bytes: 17952
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val h = sc.nextInt()
    val w = sc.nextInt()
    val a = Array(h) { Array(w) { 0 } }
    val b = Array(h) { Array(w) { 0 } }
    for (i in 0 until h) {
        for (j in 0 until w) {
            a[i][j] = sc.nextInt()
        }
    }
    for (i in 0 until h) {
        for (j in 0 until w) {
            b[i][j] = sc.nextInt()
        }
    }
    val c = Array(h) { Array(w) { 0 } }
    for (i in 0 until h) {
        for (j in 0 until w) {
            c[i][j] = Math.abs(a[i][j] - b[i][j])
        }
    }
    val size = 13000
    val dp = Array(h) { Array(w) { BitSet(size) } }
    dp[0][0][c[0][0]] = true
    for (i in 0 until h) {
        for (j in 0 until w) {
            for (k in 0 until size) {
                if ((i > 0 && dp[i - 1][j][k]) || (j > 0 && dp[i][j - 1][k])) {
                    val plus = k + c[i][j]
                    val minus = Math.abs(k - c[i][j])
                    if (plus in 0 until size) {
                        dp[i][j][plus] = true
                    }
                    if (minus in 0 until size) {
                        dp[i][j][minus] = true
                    }
                }
            }
        }
    }
    for (i in 0 until size) {
        if (dp[h - 1][w - 1][i]) {
            println(i)
            return
        }
    }
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 127812
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)
const ll mod = 1e9+7;

vector<string> s(2);
 
int main(){
  int n;
  cin >> n;
  cin >> s[0] >> s[1];
  ll res = 1LL;
  bool iscase = true;
  for (int i = 0; i < n;i++){
    if (s[0][i] == s[1][i]){  
      if (i == 0){
        res*=3;
        iscase = true;
        continue;
      }
      else {
        if (iscase) res*=2,res%=mod;
        else res *= 1,res%=mod; 
        iscase = true;
      }
    }
    else{
      i++;
      if (i == 1){
        res*= 6;
        iscase = false;
        continue;
      }
      else {
        if (iscase) res*= 2,res%=mod;
        else res*= 3;res%=mod;
        iscase = false;
      }
    }
  }
  cout << res << endl; 
  return 0; 
}



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

int main() {
	int n;
	cin >> n;
	int a[n+1][3];
	for(int i = 1 ; i <= n  ; i++){
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	int dp[n+1][3];
	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[0][2] = 0;
	for(int i = 1 ; i<=n; i++){
		dp[i][0] = std::max(a[i][0] + dp[i-1][1] , a[i][0] + dp[i-1][2]);
		dp[i][1] = std::max(a[i][1] + dp[i-1][2] , a[i][1] + dp[i-1][0]);
		dp[i][2] = std::max(a[i][2] + dp[i-1][1] , a[i][2] + dp[i-1][0]);
		
	}
	cout << std::max(std::max(dp[n][0] , dp[n][1]) , dp[n][2])<<endl;
	
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

ll S;

ll ans;

const ll T = 10000, mod = int(1e9) + 7;
ll Z(ll x){ return (x%mod+mod)%mod; }

ll Pow10[20];

ll Pow(ll a, ll b){
	ll ret=1;
	while(b){
		if(b&1) (ret*=a)%=mod;
		b>>=1; (a*=a)%=mod;
	}
	return ret;
}

ll make1(ll x){
	if(x<=10 && 9*Pow10[x-1] < S/x) return 0;
	return Z(9*Pow(10, x-1) - S/x + 1);
}

pll extgcd(ll a, ll b){
	if(!b) return {1, 0};
	pll tmp = extgcd(b, a%b);
	return {tmp.second, tmp.first-a/b*tmp.second};
}

ll gcd(ll a, ll b){ return b?gcd(b, a%b):a; }

ll make2(ll s, ll lv, ll rv){
	if(s < lv+rv || (lv<=10 && rv<=10 && 9*Pow10[lv-1]*lv + 9*Pow10[rv-1]*rv < s)) return 0;
	ll g = gcd(lv, rv);
	if(s%g) return 0;
	ll X, Y; tie(X, Y) = extgcd(lv, rv);
	if(X*lv+Y*rv<0) X=-X, Y=-Y;
	X *= (s/g); Y *= (s/g);
	
	ll dx=rv/g, dy=-lv/g;
	
	ll l = (1-X)/dx-3, r=(S/lv-X)/dx+2;
	
	ll sx, tx;
	
	while(l+1 < r){
		ll mid=((l+r)>>1);
		ll cx = X+mid*dx;
		ll cy = Y+mid*dy;
		if(1<=cx && (rv>=10 || cy<=9*Pow10[rv-1])) r=mid;
		else l=mid;
	}
	sx = X+dx*r;
	
	l = (1-X)/dx-3, r=(S/lv-X)/dx+2;
	
	while(l+1 < r){
		ll mid=((l+r)>>1);
		ll cx = X+mid*dx;
		ll cy = Y+mid*dy;
		if(1<=cy && (lv>=10 || cx<=9*Pow10[lv-1])) l=mid;
		else r=mid;
	}
	tx = X+dx*l;
	if(tx < sx) return 0;
	return (tx-sx)/dx + 1;
}

ll make3(ll b, ll c, ll r){
	if(r>=c) return 0;
	if(b<T) return 0;
	if((b>=10 || c-r <= 9*Pow10[b-1]) && ((b+1)>=10 || r <= 9*Pow10[b])){
		if(r) return 1;
		return make1(b);
	}
	return 0;
}

int main()
{
	Pow10[0] = 1;
	for(int i=1; i<=15; ++i) Pow10[i] = Pow10[i-1]*10;

	read(S);
	for(ll s=1; s<T; ++s){
		if(S%s == 0) (ans += make1(s))%=mod;
		ll cs = S;
		for(ll t=s+1; cs>0;++t){
			(ans += make2(cs, s, t))%=mod;
			if(t >= 10 || (cs -= t*9*Pow10[t-1]) <= 0) break;
		}
	}
	
	for(ll df=0; df<T; ++df){
		ll tg = S-df;
		if(tg <= 0) break;
		for(ll i=1; i*i<=tg; ++i) if(tg%i == 0){
			ans += make3(i, tg/i, df);
			if(i != tg/i)
				ans += make3(tg/i, i, df);
		}
	}
	
	ans %= mod;
	
	printf("%lld\n", ans);
	return 0;
}


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

typedef long long ll;
typedef pair<int, int> pii;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()

#define endl "\n"

void use_cio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto x : V) os << x << ", ";
  return os << "]";
}
//--------------------------------------------------//
const int MOD = 1000003;
inline ll mul(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
ll pow_mod(ll x, ll n) {
  ll ret = 1;
  for (; n; n >>= 1, x = mul(x, x))
    if (n & 1) ret = mul(ret, x);
  return ret;
}
inline ll inv_mod(ll x) { return pow_mod(x, MOD - 2); }
inline ll add(ll a, ll b) { return (a + b) % MOD; }

int cumprod[1000010];
void solve() {
  int x, d, n;
  cin >> x >> d >> n;
  if (d == 0) {
    cout << pow_mod(x, n) << endl;
    return;
  }
  ll dn = pow_mod(d, n);
  ll st = mul(x, inv_mod(d));
  ll ans = 1;
  if (st + n - 1 >= MOD) {
    cout << 0 << endl;
    return;
  }
  ans = mul(cumprod[st + n - 1], inv_mod(cumprod[st - 1]));
  cout << mul(ans, dn) << endl;
}
int main() {
  use_cio();
  cumprod[0] = 1;
  repp(i, 1, 1000010)
      cumprod[i] = mul(cumprod[i - 1], i);

  int q;
  cin >> q;
  while (q--) solve();
}


Measured memory_bytes: 4864
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
#include <utility>

constexpr int INF = 1000000000;

int n, d;
int dp[210][2]; // 0: max, 1: min
int data[210][2];
int temp[210];

int main() {
    std::cin >> d >> n;

    for(int i = 0; i < d; ++i) {
        std::cin >> temp[i];
    }

    for(int i = 0; i < d; ++i) {
        data[i][0] = -1;
        data[i][1] = INF;
    }

    int a, b, c;
    for(int i = 0; i < n; ++i) {
        std::cin >> a >> b >> c;

        for(int j = 0; j < d; ++j) {
            if(temp[j] >= a && temp[j] <= b) {
                data[j][0] = std::max(data[j][0], c);
                data[j][1] = std::min(data[j][1], c);
            }
        }
    }

    for(int i = 1; i < d; ++i) {
        dp[i][0] = std::max(
                        dp[i - 1][1] + std::abs(data[i - 1][1] - data[i][0]),
                        dp[i - 1][0] + std::abs(data[i - 1][0] - data[i][0])
                        );
        dp[i][1] = std::max(
                        dp[i - 1][1] + std::abs(data[i - 1][1] - data[i][1]),
                        dp[i - 1][0] + std::abs(data[i - 1][0] - data[i][1])
                        );
    }

    std::cout << std::max(dp[d - 1][0], dp[d - 1][1]) << std::endl;
}

Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n;
	int flag=1;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		if(a%2==0)
		{
			if(a%3!=0&&a%5!=0)
			{
				flag=0;
			}
		}
	}
	if(flag)
	{
		printf("APPROVED");
	}
	else
	{
		printf("DENIED");
	}
 } 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector <ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <vector<ll>> vv;
typedef vector <string> vs;
typedef vector <char> vc;
 
 
ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;
 
#define Endl endl
 
 
/*--------------------template--------------------*/
 
int main() {
    cin >> n >> m >> k;
 
    while (1) {
        if (cnt*m + (cnt + 1) * k == n) {
            cout << cnt << endl;
            return 0;
        } else if (cnt*m + (cnt + 1) * k > n) {
            break;
        } else {
            cnt++;
        }
    }
    while (1) {
        if (cnt*m + (cnt + 1) * k == n) {
            cout << cnt << endl;
            return 0;
        } else if (cnt*m + (cnt + 1) * k < n) {
            cout << cnt << endl;
            return 0;
        } else {
            cnt--;
        }
    }
    
}

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

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

    int ans = T.size();

    for (int start = 0; start <= S.size() - T.size(); start++) {
        int diff = 0;
        for (int i = 0; i < T.size(); i++) {
            if (S[start + i] != T[i]) {
                diff++;
            }
        }
        ans = min(ans, diff);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3580
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt64)
}

func readFloat() float64 {
	sc.Scan()
	r, _ := strconv.ParseFloat(sc.Text(), math.MaxInt64)
	return r
}

func main() {
	a, b, c := readFloat(), readFloat(), readFloat()
	k := readFloat()
	max := math.Max(math.Max(a, b), c)
	sum := max*math.Pow(2, k) + (a + b + c) - max
	fmt.Println(sum)
}


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

using namespace std;

typedef long long ll;

ll MOD = 1000000007;

int main(int, char**) {
        int a, b, c;
        cin >> a >> b >> c;
        string s;
        if (a==b&&b!=c){
                s = "Yes";
        } else if (a!=b&&b==c) {
                s = "Yes";
        } else if (a==c&&b!=c) {
                s = "Yes";
        } else {
                s = "No";
        }
        cout << s << endl;
        return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main()
{
    int n,a,b,c,i;
    scanf("%d",&n);
    b=0;c=0;
    for(i=1;i<=n;i++) {
        scanf("%d",&a);
        if(a%2==0) { b++;
        if(a%6==0 || a%10==0) { c++; }
        }
    }
    if(b==c) { printf("APPROVED\n"); }
    else { printf("DENIED\n"); }

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll                  long long
#define dl                 double
#define pb                push_back
#define F                  first
#define S                  second
#define endl              "\n"
#define rep(i,a,b)       for(i=a;i<b;i++)
#define all(v)             v.begin(),v.end()
#define allr(v)            v.rbegin(),v.rend()
#define mod              1000000007LL
#define CIN(V,s,n)      for(int i=s;i<n;i++){cin >> V[i];}
#define COUT(V,s,n)   {for(int i=s;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define CLEAR(V);      for(ll i=0;i<V.size();i++) V[i] = 0;
#define N                  1000005
#define tmod             998244353LL
using namespace std;

bool sBs(const pair<int,int> &a,const pair<int,int> &b)
{   return (a.second < b.second);   }

ll SUMD(ll n);
ll BS(vector<pair< ll ,ll > > &PS,ll s,ll e,ll ser);
ll MI(ll a, ll m);
//ll P[N+1];
void Sieve(int n=N);
ll Powb(ll b,ll n,ll m);

int BIT[N+5];

void UP(int ind,int v , int n )
{
    while(ind<=n)
    {
        BIT[ind] += v;
        ind += ind&(-ind);
    }
}

int Q(int ind)
{
    int ans = 0;
    while(ind>0)
    {
        ans += BIT[ind];
        ind -= ind&(-ind);
    }
    return ans;
}

int main()
{
fast;
ll q=1,t;
//cin >> q;
while(q--)
{
    ll i,j,n,m,k,l,r,a,b,c=0,d=0,e,g=0,p,v,w,x,y,flag=1; int u;
    //n=m=k=i=j=l=r=a=b=c=d=u=v=w=p=x=y=0;
    cin >> n;
    n = n%10;
    if(n==2 or n==4 or n==5 or n==7 or n==9) cout << "hon";
    else if(n==3) cout << "bon";
    else cout << "pon";
}
    return 0;
}

//*****************************************************************************************************************************************

ll Powb(ll b,ll n,ll m)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2,m);
    if(n%2==0){return (temp*temp)%m;}
    else{return (b*((temp*temp)%m))%m;}
}

ll SUMD(ll n)
{   ll sum=0;
    while(n>0){sum += n%10;n = n/10;}
    return sum;

}
ll BS(vector<pair<ll,ll> > &PS,ll s,ll e,ll ser)
{
    if(s>e)
        return s;
    ll mid = (s+e)/2;
    if(PS[mid].F==ser)
    {
        return mid;
    }
    else if(PS[mid].F > ser)
    {
        return BS(PS,s,mid-1,ser);
    }
    else
        return BS(PS,mid+1,e,ser);
}
ll MI(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
    if (m == 1)
      return 0;
    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
       x += m0;
    return x;
}

/*void Sieve(int n)
{
    //memset(P,true,sizeof(P));
    //P[0] = false;
    //P[1]= false;
    for(int i=1;i<=n;i++) P[i] = i;
    for(ll i=2;i*i<=n;i++)
    {
        if(P[i]==i)
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                if(P[j]==j)
                    P[j]=i;
            }
        }
    }

}

*/


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

int main()
{
    int n;
    cin >> n;
    while (n != 0) {
        if (n % 10 == 7) {
            cout << "Yes" << endl;
            return 0;
        }
        n /= 10;
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3636
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vs){
  for (const T& v : vs) os << v << " ";
  return os;
}

int main() {
  int N; cin >> N;
  vector<double> p(N); cin >> p;
  vector<vector<double>> dp(N + 1, vector<double>(N + 1, 0));

  dp[0][0] = 1.0;
  for (int i = 0; i < N; ++i) {
    dp[i + 1][0] = dp[i][0] * (1.0 - p[i]);
    for (int j = 1; j <= N; ++j) {
      dp[i + 1][j] = dp[i][j-1] * p[i] + dp[i][j] * (1.0-p[i]);
    }
  }

  double sum = 0;
  for (int i = (N + 1)/2; i <= N; ++i) sum += dp[N][i];
  printf("%.10f\n", sum);
}


Measured memory_bytes: 73784
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする
import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))


Measured memory_bytes: 12420
import javax.xml.crypto.Data;
import java.util.*;
import java.io.*;

public class Main {
    public static int SENTINEL = 100000007;
    public static int MAX = 10007;
    public static int NIL = -1;

    public static int[] dp = new int[100];


    public static void main(String[] args) throws IOException {

        //??\???

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");

        Scanner sc = new Scanner(System.in);

        Stack S = new Stack();
        int a, b;
        for(int i = 0; i < str.length; i++) {
            if(str[i].equals("+")) {
                a = S.pop();
                b = S.pop();
                S.push(a + b);
            }
            else if(str[i].equals("-")) {
                a = S.pop();
                b = S.pop();
                S.push(b - a);
            }
            else if(str[i].equals("*")) {
                a = S.pop();
                b = S.pop();
                S.push(a * b);
            }
            else {
                S.push(Integer.parseInt(str[i]));
            }
        }
        System.out.println(S.pop());
    }

}

class Stack {
    int top;
    int MAX = 10001;
    int[] S = new int[MAX];

    Stack() {
        top = 0;
    }
    boolean isEmpty() {
        return top == 0;
    }
    boolean isFull() {
        return top > MAX;
    }
    void push(int x) {
        if(isFull()) return;
        top++;
        S[top] = x;
    }
    int pop() {
        if(isEmpty()) return -1;
        top--;
        return S[top + 1];
    }
}

Measured memory_bytes: 26200
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n;
class tree{
	public:
	int id;
	int parent;
	int depth;
	vector<int> next;
}data[100000];

void decidedepth(int dep,int i){
	data[i].depth=dep;
	for(vector<int>::iterator j=data[i].next.begin();
								j!=data[i].next.end();j++){
		decidedepth(dep+1,*j);
	}
}

int main(){
	cin>>n;
	int no,k,c;
	for(int i=0;i<n;i++)	data[i].parent=-1;
	for(int i=0;i<n;i++){
		cin>>no>>k;
		data[no].id=no;
		for(int j=0;j<k;j++){
			cin>>c;
			data[no].next.push_back(c);
			data[c].parent=no;
		}
	}
	for(int i=0;i<n;i++){
		if(data[i].parent==-1){
			decidedepth(0,i);
			break;
		}
	}
	for(int i=0;i<n;i++){
		cout<<"node "<<data[i].id<<": parent = "<<data[i].parent;
		cout<<", depth = "<<data[i].depth<<", ";
		if(data[i].parent==-1)	cout<<"root, ";
		else if(data[i].next.empty())	cout<<"leaf, ";
		else 	cout<<"internal node, ";
		cout<<"[";
		for(int j=0;j<(int)data[i].next.size();j++){
			if(j) 	cout<<", ";
			cout<<data[i].next[j];
		}
		cout<<"]\n";
	}
	return 0;
}

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

using namespace std;
typedef long long ll;

int main()
{
 	ios_base::sync_with_stdio(0);
 	string s;
 	cin >> s;
 	if((s[0] == s[1] and s[1] == s[2]) or  (s[1]==s[2] and s[2]==s[3])) {
 		cout << "Yes";
 	}
 	else {
 		cout << "No";
 	}
}


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

const double EPS=1e-8;

int main()
{
  long long n,A;
  scanf("%lld%lld",&n,&A);
  vector<long long> DP[50];
  long long T=n;
  for(int t=2;t<=50;t++){
    long long a=(long long)(pow((double)n,(double)1./t)+EPS);
    int k=0;
    while(pow(a,t-k)*pow(a+1,k)<n-EPS){
      k++;
    }
    T=min(T,A*(t-1)+a*(t-k)+(a+1)*k);
  }
  printf("%lld\n",T);
  return 0;
}  


Measured memory_bytes: 512
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    
    root = 0
    q = []
    q.append(root)
    pre = [-1]*N
    visited = [False]*N
    while q:
        v = q.pop() 
        visited[v] = True
        for to in edge[v]:
            if visited[to]:
                continue
            pre[to] = v
            q.append(to)
    
    path = [] #パスに含まれる辺(根に向かう方で保存)
    constraint = []
    M=I()
    for i in range(M):
        a,b = MI_()
        constraint.append((a,b))

        
        root_path_a = 1<<a
        root_path_b = 1<<b
        
        while a!=root:
            root_path_a |= 1<<pre[a]
            a = pre[a]
        while b!=root:
            root_path_b |= 1<<pre[b]
            b = pre[b]
        path.append(root_path_a ^ root_path_b) #LCAまでのみ
        if not path[-1]>>a&1:
            path[-1] |= 1<<a
        if not path[-1]>>b&1:
            path[-1] |= 1<<b
    

    ans = 0
    for mask in range(1<<M):
        builtin_count = 0
        U = 0 #pathに含まれる辺
        for i in range(M):
            if mask>>i&1:
                builtin_count += 1
                U |= path[i]
        edge_cnt = max(0,bin(U).count("1")-1)
        if builtin_count&1:
            ans -= 1<<(N-1-edge_cnt)
        else:
            ans += 1<<(N-1-edge_cnt)
    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 68704
#include<cstdio>
#include<cstring>
using namespace std;

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

#define int long long

const int N = 4e5 + 5;

int seg[N], sum[N], a[N], n;

void add(int x)
{
	for (; x < N; x += x & -x)
		++seg[x];
}

int query(int x)
{
	int res = 0;
	for (; x; x -= x & -x)
		res += seg[x];
	return res;
}

bool check(int x)
{
	memset(seg, 0, sizeof(seg));
	sum[0] = 0;
	int res = 0;
	add(sum[0] + n + 1);
	
	for (int i = 1; i <= n; ++i) 
	{
		sum[i] = sum[i - 1] + (a[i] >= x ? 1 : -1);
		res += query(sum[i] + n + 1);
		add(sum[i] + n + 1);
	}
	
	if (res >= 1LL * n * (n + 1) / 2 - res) 
		return true;
	return false;
}

signed main()
{
	n = read();
	
	for (int i = 1; i <= n; ++i) a[i] = read();
	
	int l = 0, r = 1e9;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
			else r = mid - 1;
	}
	
	printf("%d\n", l);
	
	return 0;
}


Measured memory_bytes: 6272
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <numeric>



int main()
{
	long long a, b;

	std::cin >> a >> b;

	long long count = 0;

	while (a <= b) {
		count++;
		a *= 2;
	}

	std::cout << count << std::endl;

	return 0;
}


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

int main() {
  int x;
  cin >> x;
  
  bool bo = false;
  
  if (x == 2 || x == 3 || x == 5) {
    cout << x << endl;
  }
  else if (x == 4) {
    cout << 5 << endl;
  }
  else {
    for (int i = x; ; i++) {
      for (int j = 2; j < (i / 2); j++) {
        if (j * (i / j) == i) {
          break;
        }
        else if (j == (i / 2) - 1) {
          cout << i << endl;
          bo = true;
        }
      }
      if (bo) {
        break;
      }
    }
  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int n, i, sum;

  scanf("%d", &n);
  int value[n], cost[n];
  for(i=1;i<=n;i++){
    scanf("%d", &value[i]);
  }
  for(i=1;i<=n;i++){
    scanf("%d", &cost[i]);
  }
  sum=0;
  for(i=1;i<=n;i++){
    if(value[i]>cost[i]){
      sum+=value[i]-cost[i];
    }
  }
  printf("%d\n", sum);
  return 0;
}


Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include <stdio.h>

int main(){
	using namespace std;
	int a,b;
	scanf("%d %d",&a,&b);
		if(a<b)
			printf("a < b\n");
		else if(a>b)
			printf("a > b\n");
		else
			printf("a == b\n");
	return 0;
}

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

#define int long long

signed main(){
    int a;
    cin>>a;
    string s;
    cin>>s;
    if(a<3200){
        cout<<"red"<<endl;
    }
    else{
        cout<<s<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
from collections import deque

H, W = map(int, input().split())
meiro = []
INF = 10**9
meiro.append(["#"]*(W+2))
for _ in range(H):
    temp = list(input())
    temp.append("#")
    temp.insert(0,"#")
    meiro.append(temp)
meiro.append(["#"]*(W+2))

def bfs(i,j):
    INF = 10 ** 9
    dist = [[INF for i in range(W+2)] for j in range(H+2)]
    dist[i][j] = 0
    q = deque([[i,j]])
    while q:
        v = q.popleft()
        dv = dist[v[0]][v[1]]
        
        if meiro[v[0]-1][v[1]] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]-1][v[1]]:
                dist[v[0]-1][v[1]] = dist[v[0]][v[1]]+1
                q.append([v[0]-1,v[1]])
                
        if meiro[v[0]+1][v[1]] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]+1][v[1]]:
                dist[v[0]+1][v[1]] = dist[v[0]][v[1]]+1
                q.append([v[0]+1,v[1]])
        
        if meiro[v[0]][v[1]-1] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]][v[1]-1]:
                dist[v[0]][v[1]-1] = dist[v[0]][v[1]]+1
                q.append([v[0],v[1]-1])
        
        if meiro[v[0]][v[1]+1] != "#":
            if dist[v[0]][v[1]]+1 < dist[v[0]][v[1]+1]:
                dist[v[0]][v[1]+1] = dist[v[0]][v[1]]+1
                q.append([v[0],v[1]+1])
    
    dist = [[0 if x == INF else x for x in inner] for inner in dist]
    
    max_dist = 0
    for i in dist:
        max_dist = max(max_dist,max(i))
    return max_dist

ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if meiro[i][j] == ".":
            ans = max(ans,bfs(i,j))
print(ans)



Measured memory_bytes: 3304
n = int(input())
a = list(map(int,input().split()))

tmp = []
ttmp = []

list.sort(a,reverse=True)

for i in range(1,n+1):
    if i%2==1:
        tmp.append(a.pop(0))
    if i%2==0:
        ttmp.append(a.pop(0))
        # ttmp = a.pop(0)

print(sum(tmp)-sum(ttmp))

Measured memory_bytes: 3064
fun main() {
    val l = readLine()!!.split(' ').map { it.toInt() }
    val x = l[0]
    if (l[1] == 0) {
        println(x)
        return
    }
    val p = readLine()!!.split(' ').map { it.toInt() }.toHashSet()
    val q = (0..101)
    var def = 100
    var res = 0
    for (i in q) {
        if (!p.contains(i)) {
            var tmp = Math.max(x-i, i-x)
            if (def > tmp) {
                def = tmp
                res = i
            }
        }
    }
    println(res)
}


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


int main() {
    int n;cin>>n;
    string nn = to_string(n);
    if(nn.find('9') == string::npos){
        cout << "No"<<endl;
    }else{
        cout << "Yes" << endl;
    }

    return 0;
}

Measured memory_bytes: 256