akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define PI 3.141592653589793
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> P(N);
    vector<ll> Q(N);
    for(int i = 0; i < N; i++){
        cin >> P[i];
    }
    for(int i = 0; i < N; i++){
        cin >> Q[i];
    }


    vector<ll> N_list;
    if(N==2){
        N_list.push_back(1);
        N_list.push_back(2);
    }else if(N==3){
        N_list.push_back(1);
        N_list.push_back(2);
        N_list.push_back(3);
    }else if(N==4){
        N_list.push_back(1);
        N_list.push_back(2);
        N_list.push_back(3);
        N_list.push_back(4);
    }else if(N==5){
        N_list.push_back(1);
        N_list.push_back(2);
        N_list.push_back(3);
        N_list.push_back(4);
        N_list.push_back(5);
    }else if(N==6){
        N_list.push_back(1);
        N_list.push_back(2);
        N_list.push_back(3);
        N_list.push_back(4);
        N_list.push_back(5);
        N_list.push_back(6);
    }else if(N==7){
        N_list.push_back(1);
        N_list.push_back(2);
        N_list.push_back(3);
        N_list.push_back(4);
        N_list.push_back(5);
        N_list.push_back(6);
        N_list.push_back(7);
    }else{
        //N_list = {1, 2, 3, 4, 5, 6, 7, 8};
        N_list.push_back(1);
        N_list.push_back(2);
        N_list.push_back(3);
        N_list.push_back(4);
        N_list.push_back(5);
        N_list.push_back(6);
        N_list.push_back(7);
        N_list.push_back(8);
    }

    ll cnt=1;
    ll pcnt=1;
    ll qcnt=1;
    do{
        if(N_list==P) pcnt=cnt;
        if(N_list==Q) qcnt=cnt;
        cnt++;
    }while(std::next_permutation(N_list.begin(), N_list.end()));

    cout << abs(pcnt - qcnt) << endl;

}

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

int main(){
  int n;
  cin >> n;
  
  vector<long long> a(n);
  cin >> a.at(0);
  
  for(int i=1;i<n;i++){
    long long x;
    cin >> x;
    a.at(i)=x+a.at(i-1);
  }
  
  long long x=a.at(n-1);
  long long ans=x;
  
  for(int i=0;i<n-1;i++){
    ans=min(ans,max(x-2*a.at(i),2*a.at(i)-x));
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
#define ll long long 
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define REP(i,n) for (int i=0; i<(n); i++)
#define RREP(i,n) for (int i=(n-1); i>=0; i--)
#define ALL(x) x.begin(),x.end()
#define SZ(x) x.size()
#define SQ(x) (x)*(x)
#define MNTO(a,b) a = min(a,(__typeof__(a))(b))
#define MXTO(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define debug(x) cerr<<#x<<" is "<<x<<endl
using namespace std;

// #define int ll

const int maxn = 1e5+5;
const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"No\n"; exit(0);}

ll pow(ll a, ll n){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mod;
        a = a*a %mod;
        n>>=1;
    }
    return re;
}

ll inv (ll b){
    if (b==1) return b;
    return (mod-mod/b) * inv(mod%b) % mod;
}

int n; 

int id (int x){
    if (x>n) return x-n;
    return x;
}

main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>n;
    if (1<<((int)log2(n))==n) {
        GG();
    }
    cout<<"Yes\n";
    cout<<1+n<<' '<<2+n<<'\n';
    for (int i = 2; i<=n-1; i+=2){
        cout<<i<<' '<<1<<'\n';
        cout<<i+1<<' '<<1<<'\n';
        cout<<i+1+n<<' '<<i<<'\n';
        cout<<i+n<<' '<<i+1<<'\n';
    }
    if (n%2==0){
        int lb = n&(-n);
        int cp = n-lb;
        cout<<n<<' '<<lb+1<<'\n';
        cout<<n+n<<' '<<cp<<'\n';
    }
}

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

int c[505]={0}, s[505]={0}, f[505]={0};

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n-1;++i){
        cin >> c[i] >> s[i] >> f[i];
    }
    for(int i=0;i<n;++i){
        int ans = (i == n-1 ? 0 : s[i] + c[i]);
        for(int j=i+1;j<n-1;++j){
            ans = max(s[j] + c[j], ((ans + f[j] - 1) / f[j]) * f[j] + c[j]);
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    ll a[n];
    ll ma=0;
    ll index;
    for(int i=0;i<n;i++){
    	cin>>a[i];
    }
    for(int i=1;i<n;i++){
    	if(a[i-1]+a[i]>ma){
    		ma=a[i-1]+a[i];
    		index=i;
    	}
    }
    if(ma<k){
    	cout << "Impossible"<<endl;
    }else{
    	cout << "Possible"<<endl;
    	for(int i=n-1;i>index;i--){
    		cout << i<<endl;
    	}
    	for(int i=1;i<=index;i++){
    		cout << i<<endl;
    	}
    }
    return 0;
}


Measured memory_bytes: 1664
n = int(input())
a = [0] + list(map(int,input().split()))

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(2,n//(n-i) + 1):
        count += info[(n-i)*j]
    if count % 2 != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(" ".join(map(str,ans)))

Measured memory_bytes: 81896
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String abc = "abcdefghijklmnopqrstuvwxyz";

        int[][] alphcnt = new int[ n ][ 26 ];
        for(int i = 0 ; i < n ; i ++){
            String S = sc.next();
            for (int j = 0; j < S.length(); j++) {
                alphcnt[i][abc.indexOf(String.valueOf(S.charAt(j)))]++;
            }
        }

        int[] alphMin = {50,50,50,50,50,50,50,50,50,50,
                         50,50,50,50,50,50,50,50,50,50,
                         50,50,50,50,50,50,} ;
        for (int j = 0; j < 26 ; j++) {
            for (int i = 0; i < n; i++) {
                if (alphcnt[ i ][ j ] < alphMin[ j ]) {
                    alphMin[j] = alphcnt[i][j];

                }
            }
        }
        StringBuilder result = new StringBuilder();
        for(int j = 0 ; j < 26 ; j ++){
            for (int k = 0; k < alphMin[j]; k++) {
                result.append(String.valueOf(abc.charAt(j)));
            }
        }
        System.out.println(result);

    }
}


Measured memory_bytes: 21844
#include<cstdio>
int n,m,a,b;
int main(){
	scanf("%d%d%d%d",&n,&m,&a,&b);
	for(int i=1;i<=b;i++){
		for(int j=1;j<=a;j++)putchar('1');
		for(int j=a+1;j<=m;j++)putchar('0');
		puts("");
	}
	for(int i=b+1;i<=n;i++){
		for(int j=1;j<=a;j++)putchar('0');
		for(int j=a+1;j<=m;j++)putchar('1');
		puts("");
	}
}

Measured memory_bytes: 1152
#include <cstdio>
#include <iterator>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <string>
#include <set>
#include <numeric>
#include <bitset>
#include <cmath>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <numeric>
#include <vector>
#include <cassert>
#include <ctime>

using namespace std;
 
#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
 
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;
using pii=pair<int, int>;
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto& p: c) os << p << " ";
	return os<<']';
}
 
void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}
 
 
template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}
 
 
constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;
constexpr int maxn=1001;
constexpr int pro=2000;

ll q, h, s,d;
ll n;

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

	while(cin>> q>>h>>s>>d) {
		cin>> n;
		vl pr;
		if(q*2 < h) pr.push_back(q*2);
		else pr.push_back(h);
		if(pr[0]*2 < s) pr[0]*=2;
		else pr[0] = s;
		if(pr[0]*2 > d) pr.push_back(d);
			else pr.push_back(pr[0]*2);
		ll ret  = pr[1] * (n/2) + pr[0] * (n%2);
		cout << ret << endl;
	}
	return 0;
}


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

int main() {
  int A,B,M,ans=0;
  cin >> A >> B >> M;
  vector<int> a(A);
  for (int i=0;i<A;i++){
  cin >> a.at(i);
  } 
  vector<int> b(B);
  for (int i=0;i<B;i++){
  cin >> b.at(i);
  }
  
  vector<vector<int>> c(M,vector<int>(3));
  vector<int> d(M);
  for (int i = 0; i <M; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> c.at(i).at(j);
    }
      d.at(i) = a.at(c.at(i).at(0)-1)+b.at(c.at(i).at(1)-1)-c.at(i).at(2);
  }
  
  sort(d.begin(),d.end());
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  ans=min(d.at(0),a.at(0)+b.at(0));

  cout << ans << endl;
  
}

Measured memory_bytes: 6912
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
#include<ctype.h>

using namespace std;

double sum(double a,double b){ return a+b; }
double dif(double a,double b){ return a-b; }
double mul(double a,double b){ return a*b; }
double div(double a,double b){ return a/b; }
double (*ops[])(double,double)={sum,dif,mul,div};

int main(){
  int i;
  char in[256],*ind,op[]={'+','-','*','/'};
  stack<double> st;
  double p1,p2;

  while(fgets(in,256,stdin)!=NULL){
    for(ind=strtok(in," ");ind!=NULL;ind=strtok(NULL," ")){
      for(i=0;i<4;i++)
	if(op[i]==ind[0]&&!isdigit(ind[1])){
	  p1=st.top();
	  st.pop();
	  p2=st.top();
	  st.pop();
	  st.push(ops[i](p2,p1));
	  goto jump;
	}
      st.push(atof(ind));
    jump:;
    }
    printf("%.6lf\n",st.top());
    st.pop();
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <array>

using namespace std;

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

    string buf = "";
    for(int i = 0; i < 100; i++) buf += i < 50 ? '.' : '#';

    array<string, 100> ans;
    fill(ans.begin(), ans.end(), buf);

    int i = 1, j = 51;
    for(; a > 1; a--) {
        ans[i][j] = '.';
        j += 2;
        if(j > 98) {
          i += 2;
          j = 51;
        }
    }

    i = 1; j = 1;
    for(; b > 1; b--) {
        ans[i][j] = '#';
        j += 2;
        if(j > 48) {
          i += 2;
          j = 1;
        }
    }

    cout << "100 100" << endl;
    for_each(ans.begin(), ans.end(), [](auto x) {cout << x << endl;});
}

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

#define F first
#define S second
#define nl '\n'
#define gcd __gcd
#define nset __builtin_popcount
#define pb push_back
#define btoe(x) x.begin(), x.end()
#define trim_chains(x) (x).resize(unique(btoe(x)) - (x).begin())
#define remove_dups(x) sort(btoe(x)); trim_chains(x);
#define rep(i, a, b)  for (int i = int(a); i <= int(b); i++)
#define nrep(i, a, b) for (int i = int(a); i >= int(b); i--)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using ll  = long long;
using ull = unsigned long long;
using vi  = vector<int>;
using vl  = vector<long>;
using vll = vector<ll>;
using vb  = vector<bool>;
using vvb = vector<vb>;
using vvi = vector<vector<int> >;
using ii  = pair<int, int>;
using vii = vector<ii>;
using vs  = vector<string>;
using msi = map<string, int>;
using iss = istringstream;

int main()
{
    FASTIO;
    int n; cin >> n;
    vll dcnt(n+1, 0);

    for(ll i = 1; i <= n; i++) {
        for(int j = i; j <= n; j += i) {
            dcnt[j]++;
        }
    }

    ll ans = 0;
    for(ll i = 1; i <= n; i++) {
        ans += i * dcnt[i];
    }

    cout << ans << nl;
    return 0;
}


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

int main(){
	int N;
	cin >> N;
	int max = N,count = 0;
	for(int i=0;i < N;i++){
		int P;
		cin >> P;
		
		if(max >= P){
			max = P;
			count ++;
		}
	}
	cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

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

ll gcd(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    while (m != n)
    {
        if (m > n)
            m = m - n;
        else
            n = n - m;
    }
    return m;
}

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

int ctoi(const char c)
{
    if ('0' <= c && c <= '9')
        return (c - '0');
    return -1;
}

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

    vector<int> D(K);
    cin >> D;

    FOR(i,N,10*N){
        bool flag = true;
        int res = i;
        while(res){
            int dig = res % 10;
            REP(j,D.size()){
                if(dig==D[j]){
                    flag = false;
                }
            }
            res = res / 10;
        }
        if(flag){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}



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

int main() {
    string S;
    cin >> S;
    int count_a = 0;
    int count_b = 0;
    int count_c = 0;
    for (int i = 0; i < 3; i++) {
        if (S.at(i) == 'a') {
            count_a += 1;
        }
        if (S.at(i) == 'b') {
            count_b += 1;
        }
        if (S.at(i) == 'c') {
            count_c += 1;
        }
    }
    string ans;
    if (count_a * count_b * count_c == 1) {
        ans = "Yes";
    }
    else {
        ans = "No";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	if ((n & (n - 1)) == 0) {
		printf("No\n");
		return 0;
	}
	vector<pair<int, int>> ans;
	ans.emplace_back(n + 2, n + 1);
	for (int i = 2; i + 1 <= n; i += 2) {
		ans.emplace_back(1, i);
		ans.emplace_back(1, i + 1);
		ans.emplace_back(i, n + i + 1);
		ans.emplace_back(i + 1, n + i);
	}
	if (n % 2 == 0) {
		int x = 1 << (31 - __builtin_clz(n));
		int y = n - x + 1;
		ans.emplace_back(n, x);
		ans.emplace_back(n + n, y);
	}
	assert(ans.size() == 2 * n - 1);
	printf("Yes\n");
	for (auto& a : ans) printf("%d %d\n", a.first, a.second);
}


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

map<ll, ll> mp0, mp1;
ll mod = 1e9+7;

ll rec(ll N, int up) {
    if (up == 0) {
        if (mp0.find(N) != mp0.end()) return mp0[N];
        if (N == 1) return 2;
        if (N == 0) return 1;
        ll res = 0;
        res += rec(N/2, 0);
        res += rec((N-1)/2, 0);
        res += rec(N/2, 1);
        return mp0[N] = res%mod;
    }
    if (up == 1) {
        if (mp1.find(N) != mp1.end()) return mp1[N];
        if (N == 1) return 1;
        if (N == 0) return 0;
        ll res = 0;
        res += rec((N-1)/2, 0);
        res += rec(N/2, 1);
        res += rec((N-1)/2, 1);
        return mp1[N] = res%mod;
    }
    return 0;
}

int main() {
    ll N;
    cin >> N;
    cout << rec(N, 0) << endl;
    return 0;
}

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

//C++14 (GCC 5.4.1)

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)

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

template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }

#define dbg_v1(i,V) do{cout<<"-v1----\n";rep(i,V.size())cout<<" "<<i<<"\t:"<<V[i]<<endl;cout<<endl;}while(0)
#define dbg_v2(i,k,V) do{cout<<"-v2----\n";rep(i,V.size()){rep(k,V[0].size())cout<<" "<<V[i][k];cout<<endl;}}while(0)
#define lower_bound_idx(V,c) distance(V.begin(),lower_bound(V.begin(),V.end(),c))

int main() {
    ios::sync_with_stdio(false);//stdoutとcoutの同期解除
    cin.tie(nullptr);//cinとcoutの同期解除
    
    int N;
    cin >>N;

    vector<int> a(N),b(N),c(N);
    rep(i,N) cin >> a[i]>>b[i]>>c[i];
    vector<int> DA(N,0),DB(N,0),DC(N,0);
    DA[0]=a[0];
    DB[0]=b[0];
    DC[0]=c[0];
    repd(i,1,N){
        chmax(DA[i],DB[i-1]+a[i]);
        chmax(DA[i],DC[i-1]+a[i]);
        chmax(DB[i],DA[i-1]+b[i]);
        chmax(DB[i],DC[i-1]+b[i]);
        chmax(DC[i],DB[i-1]+c[i]);
        chmax(DC[i],DA[i-1]+c[i]);
    }
    cout << max({DA[N-1],DB[N-1],DC[N-1]}) <<endl;
    return (0);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N,R; //Nは参加回数Rは表示レ
    cin >> N >> R;
    if (N >= 10){
        cout << R << endl;
    }
    else{
        cout <<  R + 1000 - 100 * N  << endl;
    }
    
}

Measured memory_bytes: 256
//#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
char s[N], t[N];
vector<int> occ[30];

int main() {
 //   freopen("in.txt", "rt", stdin);
    scanf("%s %s", s, t);
    for (int i = 0; s[i]; ++i) {
        occ[s[i] - 'a'].push_back(i);
    }
    for (int i = 0; t[i]; ++i) {
        if (occ[t[i] - 'a'].empty()) {
            puts("-1");
            return 0;
        }
    }
    int idx = 0, v = 0;
    for (int i = 0; t[i]; ++i) {
        int id = t[i] - 'a';
        auto it = lower_bound(occ[id].begin(), occ[id].end(), idx);
        if (it == occ[id].end()) {
            idx = 0;
            v++;
            --i;
            continue;
        } else {
            idx = (*it) + 1;
        }
    }
    int l = strlen(s);
    printf("%lld", idx + (1ll * v * l));
}

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


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define w(x)  int x; cin>>x; while(x--)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define watch4(x,y,z,q) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<" and "<<(#q)<<" is "<<(q)<<"\n"
#define MOD 1000000007
#define INF 1000000007;
#define F first
#define S second
#define pb(x) push_back(x);


#define ll  long long
#define all(c) (c).begin(),(c).end()
#define endl "\n"

typedef vector<int> vl;
typedef vector< vl > vvl;
typedef pair< int, int> pll;
typedef map< int, int> mll;


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif





void c_p_c()
{
#ifndef ONLINE_JUDGE
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void parray(int a[],int n){
    for(int i=0;i<n;i++){
    cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main() {
    int i,n,m,k,c=0,sum=0;
    c_p_c();
    int a,b;
    cin>>n>>a>>b;
    if(b>a){
    	// watch2(a+n,b);
    	// cout<<(a+n<=b)?0:(b-(a+n));
    	if(a+n>=b)
    		cout<<0<<endl;
    	else 
    		cout<<b-(a+n)<<endl;
    }else if (a>b){
    	if(b+n>=a)
    		cout<<0<<endl;
    	else 
    		cout<<a-(b+n)<<endl;

    }else
     cout<<0<<endl;
 	return 0;

   }

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

const int MAX = 1000000;
const int INF = 1<<29;

int main() {
    vector<int> dp(MAX, INF), odddp(MAX, INF);
    dp[0] = odddp[0] = 0;
    for (int i = 1;; ++i) {
        int num = i * (i+1) * (i+2) / 6;
        if (num >= MAX) break;
        for (int j = num; j < MAX; ++j) {
            dp[j] = min(dp[j], dp[j-num]+1);
            if (num & 1) odddp[j] = min(odddp[j], odddp[j-num]+1);
        }
    }
    int n;
    while (cin >> n) {
        if (n == 0) break;
        cout << dp[n] << " " << odddp[n] << endl;
    }
}


Measured memory_bytes: 10528
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Iterator;

class Graph {
	private int totalVertex;
	//adjMatrix[u][v] = 1 if there is an edge from u to v, otherwise 0
	private int[][] adjMatrix;
	//adjWeight[u][v] -- the weight of the edge from u to v if there is one
	private int[][] adjWeight;
	//if a node is settled (e.g., processed in the Dijkstra's algorithm)
	private Boolean[] ifSettled;
	public Graph() { totalVertex = 0; }
	public int getTotalVertex() { return totalVertex; }
	//load graph from standard input
	public void loadAdjMatrix() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjMatrix = new int[totalVertex][totalVertex];
		adjWeight = new int[totalVertex][totalVertex];
		ifSettled = new Boolean[totalVertex];
		int i, j;
		for(i = 0; i < totalVertex; i ++) {
			ifSettled[i] = false;
			for(j = 0; j < totalVertex; j ++) {
				adjMatrix[i][j] = adjWeight[i][j] = 0;
			}
		}
		int u, v;
		for(i = 0; i < totalVertex; i ++) {
			u = in.nextInt();
			int degree = in.nextInt();
			for(j = 0; j < degree; j ++) {
				v = in.nextInt(); 
				adjMatrix[u][v] = 1;
				adjWeight[u][v] = in.nextInt();
			}	
		}
		in.close();
	}
	//return weight of the edge from u to v if there is one
	public int getWeight(int u, int v) {
		return adjWeight[u][v];
	}
	//return neighbors of u as a LinkedList
	public LinkedList<Integer> getNeighbors(int u) {
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for(int v = 0; v < totalVertex; v ++) {
			if(adjMatrix[u][v] == 1) tmp.add(v);
		}
		return tmp;
	}
	//return unsettled neighbors of u as a LinkedList
	public LinkedList<Integer> getUnsettledNeighbors(int u) {
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for(int v = 0; v < totalVertex; v ++) {
			if((adjMatrix[u][v] == 1) && (ifSettled[v] == false)) tmp.add(v);
		}
		return tmp;
	}
	//return the unsettled node that has the smallest dist
	public int getUnsettledNearest(int[] dist) {
		int md = Integer.MAX_VALUE;
		int mv = -1;
		int v;
		for(v = 0; v < totalVertex; v ++) {
			if((ifSettled[v] == false) && (dist[v] < md)) {
				md = dist[v];
				mv = v;
			}
		}
		return mv;
	}
	//implement the following	
	public int[] Dijkstra(int s) {
		int[] dist = new int[totalVertex];
		dist[s] = 0;
		for (int i = 1; i < totalVertex; i++) {
			dist[i] = Integer.MAX_VALUE;;
		}
		for (int i = 0; i < totalVertex; i++) { 
			int v = getUnsettledNearest(dist);
			ifSettled[v] = true;
			for (int x = 0; x < totalVertex; x++) {
				if (!ifSettled[x] && adjMatrix[v][x] != 0) {
					dist[x] = Math.min(dist[v] + getWeight(v, x), dist[x]);
				}
			}
		}
		
		return dist;
	}
}

public class Main {
	public static void main(String[] argv) {
		Graph g = new Graph();
		g.loadAdjMatrix();
		int[] dist = g.Dijkstra(0);
		for(int i = 0; i < g.getTotalVertex(); i ++) {
			System.out.println(i + " " + dist[i]);
		}
	}
}


Measured memory_bytes: 39996
#include <stdio.h>

int main(int argc, char *argv[])
{
        int a, b, c;
        int i, d = 0;

        scanf("%d %d %d", &a, &b, &c);

        for (i = a; i <= b; i++) {
                if (c % i == 0) d++;
        }

        printf("%d\n", d);

        return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define ll long long
#define lli long long int
#define li long int
#define ld long double
#define vi vector<int>
#define vlli vector<lli>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define mp(a, b) make_pair(a, b)
#define all(arr) arr.begin(), arr.end()
using namespace std;
const lli mod = 1e9 + 7;
const lli mod_ = 998244353;
const int INF = 1000000000;
const lli INF64 = (lli)1E18;
const int MAX = 1e5 + 5;

int dp[3005][3005];

int main() {
	// ifstream cin("input.in");
	// ofstream cout("output.out");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s, t, res;
	cin >> s >> t;
	int slen = s.length(), tlen = t.length();
	s = " " + s;
	t = " " + t;
	for(int si = 1; si <= slen; si++) {
		for(int ti = 1; ti <= tlen; ti++) {
			if(s[si] == t[ti]) {
				dp[si][ti] = 1 + dp[si-1][ti-1];
			} else {
				dp[si][ti] = max(dp[si-1][ti], dp[si][ti-1]);
			}
		}
	}

	int si = slen, ti = tlen;
	while(si > 0 && ti > 0) {
		if(s[si] == t[ti]) {
			res += s[si];
			si--; ti--;
		} else {
			if(dp[si-1][ti] > dp[si][ti-1]) {
				si--;
			} else {
				ti--;
			}
		}
	}
	reverse(all(res));
	cout << res;
	return 0;
}

Measured memory_bytes: 35456
x,y = map(int,input().split())
m = 10**9+7
n = (x+y)//3
c = 0
if x*0.5 <= y <= 2*x and (x+y)%3 == 0:
    r = x - n
    c = 1
    for i in range(1,r+1):
        c *= (n-i+1) % m
        c *= pow(i,m-2,m)
        c = c % m
else:
    ans = 0
print(c)

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

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  for(int i = 0; i < h; i++) cin >> s.at(i);
  
  vector<int> dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
  vector<vector<int>> check(h, vector<int>(w, -1));
  check.at(0).at(0) = 1;
  queue<pair<int, int>> bfs;
  bfs.push({0, 0});
  while(bfs.size() > 0){
    queue<pair<int, int>> next;
    while(bfs.size() > 0){
      next.push(bfs.front());
      bfs.pop();
    }
    
    while(next.size() > 0){
      auto now = next.front();
      next.pop();
      int k = check.at(now.second).at(now.first) + 1;
      for(int i = 0; i < 4; i++){
        int x = now.first + dx.at(i), y = now.second + dy.at(i);
        if(x < 0 || x >= w || y < 0 || y >= h) continue;
        if(s.at(y).at(x) == '#') continue;
        if(check.at(y).at(x) > 0) continue;
        check.at(y).at(x) = k;
        bfs.push({x, y});
      }
    }
  }
  
  int cnt = 0;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(s.at(i).at(j) == '.') cnt++;
    }
  }
  
  if(check.at(h-1).at(w-1) < 0) cout << -1 << endl;
  else cout << cnt - check.at(h-1).at(w-1) << endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int N,M;
vector<int> g[100010];
int p[100010];
vector<int> ds;
int c0,c1;
int dp[100010];
ll sum=0;

bool dfs(int v,int pari){
  p[v]=pari;
  if(pari==0)c0++;
  else c1++;
  bool ok=true;
  for(int nv : g[v]){
    if(p[v]==p[nv])ok=false;
    else{
      if(p[nv]==-1&&!dfs(nv,1-pari))ok=false;
    }
  }
  return ok;
}

int main(){
  cin>>N>>M;
  rep(i,M){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  memset(p,-1,sizeof(p));
  rep(i,N){
    if(p[i]!=-1)continue;
    c0=0;
    c1=0;
    if(!dfs(i,0)){
      cout<<-1<<endl;
      return 0;
    }
    ds.push_back(abs(c0-c1));
    sum+=abs(c0-c1);
  }
  sort(all(ds));
  vector<int> a,m;
  rep(i,ds.size()){
    int j=i;
    a.push_back(ds[i]);
    int cnt=0;
    while(j<ds.size()&&ds[j]==ds[i]){
      j++; cnt++;
    }
    m.push_back(cnt);
    i=j-1;
  }

  memset(dp,-1,sizeof(dp));
  dp[0]=0;
  rep(i,a.size()){
    rep(j,N+1){
      if(dp[j]>=0)dp[j]=m[i];
      else if(j<a[i]||dp[j-a[i]]<=0)dp[j]=-1;
      else dp[j]=dp[j-a[i]]-1;
    }
  }

  ll res=-INF;
  rep(j,N+1){
    if(dp[j]<0)continue;
    ll d=abs(sum-2*j);
    ll x=(N+d)/2,y=(N-d)/2;
    assert(x+y==N);
    maxch(res,x*y-M);
  }
  cout<<res<<endl;
  return 0;
}



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

int main()
{
    char S;
    cin >> S;

    if(S=='A')
        cout << "T" << endl;
    if (S == 'T')
        cout << "A" << endl;
    if (S == 'G')
        cout << "C" << endl;
    if (S == 'C')
        cout << "G" << endl;
}

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

#define mod 1000000007
#define ll long long

ll bow(ll x, ll y) {
  ll res = 1;
  for (ll i = 1; i <= y; ++i) {
    res = res * x % mod;
  }
  return res;
}

void solve() {
  ll n;
  cin >> n;
  ll ans = bow(10, n) - bow(9, n) - bow(9, n) + bow(8, n);
  ans %= mod;
  ans = (ans + mod) % mod;
  cout << ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

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

using namespace std;


vector<int> m = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

string getMax(string a, string b)
{
    if(a.length() > b.length())
    {
        return a;
    }
    else if(a.length() < b.length())
    {
        return b;
    }
    else  //如果长度相等，返回字典序较大的字符串
    {
        return a > b ? a : b;
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(M, 0);
    for(int i = 0; i < M; i++)
    {
        cin >> A[i];
    }

    sort(A.begin(), A.end(), greater<int>());

    vector<string> dp(max(N+1,10), "");

    for(int i = 0; i < M; i++)
    {
        dp[m[A[i]]] = getMax(dp[m[A[i]]], to_string(A[i]));
    }

    for(int j = 0; j <= N; j++)
    {
        for(int i = 0; i < M; i++)
        {
            if(j - m[A[i]] >= 0 && dp[j-m[A[i]]] != "")
            {
                dp[j] = getMax(dp[j], dp[j-m[A[i]]] + to_string(A[i]));
            }
        }
    }

    cout << dp[N] << endl;

    return 0;
}

Measured memory_bytes: 32896
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
int a[100100],b[100100],c[100100];
int dp_a[100100],dp_b[100100],dp_c[100100];

int main(){
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }

    dp_a[0]=0;
    dp_b[0]=0;
    dp_c[0]=0;

    for(int i=1;i<=n;i++){
        dp_a[i]=max(b[i-1]+dp_b[i-1],c[i-1]+dp_c[i-1]);
        dp_b[i]=max(a[i-1]+dp_a[i-1],c[i-1]+dp_c[i-1]);
        dp_c[i]=max(a[i-1]+dp_a[i-1],b[i-1]+dp_b[i-1]); 
    }
    /*
    cout<<dp_a[n]<<" ";
    cout<<dp_b[n]<<" ";
    cout<<dp_c[n];

    cout<<endl;
    */
    int dpa =dp_a[n-1]+a[n-1];
    int dpb =dp_b[n-1]+b[n-1];
    int dpc =dp_c[n-1]+c[n-1];
    /*
    cout<<dpa<<" ";
    cout<<dpb<<" ";
    cout<<dpc;
    */
    int maiorPath=max(dpa,dpb);
    maiorPath=max(maiorPath,dpc);
    cout<<maiorPath;

}


Measured memory_bytes: 5960
using System;
namespace ConsoleApplication1{
    class Program{
        static void Main(string[] args){
            while(true){
                int n=int.Parse(Console.ReadLine());
                if(n==0){
                    break;
                }
                int max=int.MinValue;
                int[] a=new int[n];
                for(int i=0;i<n;i++){
                    a[i]=int.Parse(Console.ReadLine());
                    if(max<a[i]){
                        max=a[i];
                    }
                }
                for(int i=0;i<n-1;i++){
                    int sum=a[i];
                    for(int j=i;j<n-1;j++){
                        sum=sum+a[j+1];
                        if(max<sum){
                            max=sum;
                        }
                    }
                }
                Console.WriteLine(max);
            }
        }
    }
}

Measured memory_bytes: 5704
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

int main() {
  int n;
  cin>>n;
  
  vector<int> A(n+1,0);
  rep(i,n) cin>>A[i];
  
  int cnt=0;
  for(int i=0;i<n;i++){
    if(A[i]==0) continue;
    while(A[i]>0){
      cnt++;
      A[i]--;
      for(int j=i+1;j<=n;j++){
        if(A[j]!=0) A[j]--;
        else break;
      }
    }
  }
  
  cout<<cnt<<endl;
  
  return 0;
}

Measured memory_bytes: 3588
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;

using namespace std;
int main() {
	int a, p;
	cin >> a >> p;
	cout << (3 * a + p) / 2 << endl;
	return 0;
}


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

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

  int x = 0;
  int maxi = 0;
  
  rep(i, n){
    if(s.at(i) == 'I'){
      x++;
    }
    else{
      x--;
    }
    maxi = max(maxi, x);
  }
  cout << maxi << endl;
}

Measured memory_bytes: 256
n=gets.to_i
m=gets.to_i

array=Array.new(n)
  n.times{|t|
  array[t]=Array.new(n, 100000000)
}
m.times{
  a,b,c,d=gets.split(",").map{|e|e.to_i}
  array[a-1][b-1]=c
  array[b-1][a-1]=d
}

#k,i,j=0,0,0
for k in 0..n-1 do
  for i in 0..n-1 do
    for j in 0..n-1 do 
      array[i][j]=array[i][k]+array[k][j] if array[i][j]>array[i][k]+array[k][j]
      j+=1
    end
    i+=1
  end
  k+=1
end
x1,x2,y1,y2=gets.split(",").map{|e|e.to_i}

#array.each{|e|p e}

p y1-y2-array[x1-1][x2-1]-array[x2-1][x1-1]

Measured memory_bytes: 6120
import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))

money = 1000
min_price = float("inf")
for i in range(N):
    if min_price > A[i]:
        min_price = A[i]
    elif min_price < A[i]:
        num = money // min_price
        money = money - min_price * num + A[i] * num
        min_price = A[i]

print(money)

Measured memory_bytes: 9144
n = int(input())
H = list(map(int,input().split()))
X = 0
x = 0
for i in range(n-1):
    if H[i]>=H[i+1]:
        x +=1
    else:
        if x > X:
            X = x
        x = 0
if x > X:
    X = x
print(X)

Measured memory_bytes: 14284
//templates
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <sstream>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define sort_key(struct_name,key_name) [](const struct_name &x, const struct_name &y){return x.key_name < y.key_name;}
#define pb(x) push_back(x)
typedef long long ll;
const long long MOD = 1e9 + 7;
using namespace std;

//main
int main(){
    int N; cin >> N;
    vector<int> B(N-1);
    rep(i,N-1) cin >> B[i];
    int ans = B[0]+B[N-2];
    rep(i,N-2){
        ans += min(B[i],B[i+1]);
    }
    cout << ans << endl;
}



Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int i,j;
	if(a>b){
		i=b;
	}else{
		i=a;
	}
	if(c>d){
		j=d;
	}else{
		j=c;
	}
	cout<<i+j<<endl; 
} 

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

int main() {

ll n,x,t; cin>>n>>x>>t;
  ll a=n/x; 
  if(n%x!=0){a++;}
  cout<<a*t<<endl;
  
  
  
  
  
  
}


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

#define int             long long int
#define ld              long double
#define ff              first
#define ss              second
#define mp              make_pair
#define pb              push_back
#define endl            "\n"

#define si              set <int>
#define vi              vector <int>
#define pii             pair <int, int>
#define vpii            vector <pii>
#define mii             map <int, int>
#define que_max         priority_queue <int>
#define que_min         priority_queue <int, vi, greater<int>>

#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))


#define M               1000000007
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl

const int inf = INT_MAX;
const long long INF = LLONG_MAX;

inline int power(int a, int b)
{
	int x = 1;
	while (b)
	{
		if (b & 1) x *= a;
		a *= a;
		b >>= 1;
	}
	return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 3e5 + 7;
vector <vi > adj(N);

bool vis[N];
//0-->white
int dp[100005][2];
int n;
/* In tree vale questions no need to keep the visited array as each node can be visited
only once as each node has exactly one parent except the root node which has no parent. 
while doing dfs of a tree we only need to keep track of the parent node.*/
int dfs(int id, int p, int pc)
{

	int &ans = dp[id][pc];
	if ( ans != -1 ) return ans;

	int a1 = 1;
	for (auto i : adj[id])
	{
		if ( i != p )
		{

			a1 *= dfs(i, id, 0);
			a1 %= M;
		}
	}
	int a2 = 0;

	if (pc != 1)
	{
		a2 = 1;
		for (auto i : adj[id])
		{
			if ( i != p )
			{
				a2 *= dfs(i, id, 1);
				a2 %= M;
			}
		}
	}

	return ans = (a1 + a2) % M;

}
void solve()
{
	cin >> n;
	adj.resize(n + 1);
	mset(dp, -1);
	loop(i, 0, n - 1)
	{
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	cout << dfs(1, 0, 3) << endl;


}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


	cout << setprecision(9) << fixed;

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


	return 0;
}


Measured memory_bytes: 18944
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;
    string ans = "";
    rep(i, N) {
        ans += S[i];
        ans += T[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;

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

typedef tree<double,null_type,less<double>,rb_tree_tag,tree_order_statistics_node_update> Tree;

#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}


int n;
pair<pi,int> ps[40005];


typedef pair<double,double> pd;
pd event[40005];
lint count(double X){
  REP(i,n){
    double y=(ps[i].sc-(ps[i].fr.fr*X))/ps[i].fr.sc;
    double ang=-ps[i].fr.fr/(double)ps[i].fr.sc;
    event[i]={y,ang};
  }
  Tree T;
  sort(event,event+n);
  lint res=0;
  REP(i,n){
    T.insert(event[i].sc);
    res+=T.order_of_key(event[i].sc);
  }
  return res;
}
double solve(){
  const double MX=1e9;
  double lb=-MX,ub=MX;

  lint all=n*(lint)(n-1)/2;
  lint half=(all+1)/2;
  REP(hoge,80){
    double md=(lb+ub)/2;
    if(count(md)<half) lb=md;
    else ub=md;
  }
  return lb;
}
int main(){
#ifdef LOCAL_REDIR
  freopen("/home/hog/Dropbox/pg/working/in.txt","r",stdin);
#endif
  cin>>n;
  REP(i,n){
    cin>>ps[i].fr.fr>>ps[i].fr.sc>>ps[i].sc;
  }
  double X=solve();
  REP(i,n) swap(ps[i].fr.fr,ps[i].fr.sc);
  double Y=solve();

  printf("%.15f %.15f\n",X,Y);

  return 0;
}






Measured memory_bytes: 3968
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1010;
int a[maxn],b[maxn],n;
void insertionSort(int a[],int len)
{
	for(int i=2;i<=len;i++)//每次把当前这个元素往前面已经排好的里面插入 
	{
		for(int j=1;j<i;j++)
		{
			if(a[i]<a[j]){  //如果当前的比前面的小，则替换  由于前面的是有序的，所以替换后还是有序的 
				int temp=a[i];//交换元素 
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
	
}
void merge(int a[],int l,int mid,int r)//区间合并函数 
{
	int i=l,j=mid+1,cnt=l;//i，j是two pointer，cnt表示处理好的元素位置 
	while(i<=mid&&j<=r)		//有序表的合并 
	{
		if(a[i]<a[j]){
			b[cnt++]=a[i++];
		}else{
			b[cnt++]=a[j++];
		}		
	}
	while(i<=mid)b[cnt++]=a[i++]; //处理左区间还没有处理的元素 
	while(j<=r)b[cnt++]=a[j++];   //右区间 
	
	for(int i=l;i<=r;i++)         //信息转移 
		a[i]=b[i];
}
void mergeSort(int a[],int l,int r)
{
	if(l==r)return;        //只有一个元素  无需分治 
	int mid=(l+r)>>1;
	mergeSort(a,l,mid);    //处理左区间 
	mergeSort(a,mid+1,r);  //处理右区间 
	merge(a,l,mid,r);      //合并区间 
}
int main(){
	ll a,b,c,ans=0;
	while(cin>>a>>b>>c)
	{
		ans=b+min(a+b,c);
		if(c>a+b)ans++; 
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N;
  cin>>N;
vector<ll> A(N+1);
  ll sum=0;
  for(ll i=0;i<N+1;i++) {
cin>>A[i];
    sum+=A[i];
  }
  
  vector<ll> B(N);
  for(ll i=0;i<N;i++) {
    cin>>B[i];
  }
  
  for(ll i=0;i<N;i++) {
if(A[i]>=B[i]) {
A[i]-=B[i];
continue;
}
    else {
    B[i]-=A[i];
      A[i]=0;
      
      if(B[i]>A[i+1]) {
A[i+1]=0;
        continue;
      }
      else {
A[i+1]-=B[i];
        continue;
      }
    }
  }
  
  ll ans=0;
  for(ll i=0;i<N+1;i++) {
    ans+=A[i];
  }
  
  cout<<sum-ans<<endl;
}


  
  
  
  


Measured memory_bytes: 4740
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const long long mod = 1000000007LL;

ll check[1000005];

int main() {
  ll n;
  cin >> n;
  vll a(n);
  rep(i,n) cin >> a[i];
  sort(a.begin(),a.end());
  rep(i,n) {
    for(int j = 1; a[i]*j<=a[n-1]; j++) check[a[i]*j]++;
  }
  ll ans = 0LL;
  rep(i,n) if(check[a[i]]==1) ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 12764
using System;

namespace oasobi
{
    static class MainClass
    {
        public static void Main()
        {
            int A = int.Parse(Console.ReadLine());
            int B = int.Parse(Console.ReadLine());
            int C = int.Parse(Console.ReadLine());
            int X = int.Parse(Console.ReadLine());

            int counter = 0;

            for(int i = 0; i <= A; ++i)
            {
                for(int j = 0; j <= B; ++j)
                {
                    for(int k = 0; k <= C; ++k)
                    {
                        int total = (500 * i) + (100 * j) + (50 * k);
                        if (total == X)
                        {
                            ++counter;
                        }
                    }
                }
            }

            Console.WriteLine(counter);
        }
    }
}

Measured memory_bytes: 13140
#include<stdio.h>
int main()
{
	int a, b, c, x, i, k, j,count=0;
	scanf("%d %d %d %d", &a, &b, &c, &x);
	for (i = 0; i <= a; i++)
		for (j = 0; j <= b; j++)
			for (k = 0; k <= c; k++)
				if (i * 500 + j * 100 + k * 50 == x)
					count++;
	printf("%d\n", count);
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

void solve(){
    int N, T;
    cin >> N >> T;

    int ans=100000;
    for (int i = 0; i < N; i++) {
        int c, t;
        cin >> c >> t;
        if (t <= T) {
            ans = min(ans, c);
        }
    }
    if (ans == 100000) {
        cout << "TLE" << endl;
    }else{
        cout << ans << endl;
    }

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256