akhauriyash/Code-Regression huggingface dataset:
/*------U Have To DO It------*/
/* BY-> RicoProg */
/*        ___ 
           __|__|
          |  |___       */
#include <bits/stdc++.h>
using namespace std;
 
 
//---------------------------------------------------MACROS----------------------------------------------------------
#define ll long long
#define ld long double
#define beg(i ,n) for(ll i=0;i<n;i++)
#define beg1(i ,n) for(ll i=1;i<n;i++)
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back 
#define mp make_pair
#define nl "\n" 
#define vec(v , n) vector<ll> v(n)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define pll pair<ll , ll>
#define mii map<int , int>
#define mll map<ll , ll>
#define msi map<string , int>
#define mci map<char , int>
#define f1 first
#define f2 second
#define inf 1e18 + 10

//---------------------------------------------------GLOBAL----------------------------------------------------------
const ll MOD = 1e9 + 7 ;
const ll MAX = 1e5 + 7 ;

//---------------------------------------------------FUNCTIONS-------------------------------------------------------

const ll nax = 1e5+5 ;
ll dp[nax][2] , n ;
vector<ll> gr[nax] ;

void add_self(ll &a , ll b){
	a+=b ;
	if(a>=MOD) a-=MOD ;
}

ll mul(ll a , ll b){
	return (a*b) % MOD ;
}

void dfs(ll n , ll p){
	bool flag = false ;
	ll temp_w , temp_b , temp ;
	temp_w = 1, temp_b = 1 ;
	for(auto i : gr[n]){
		if(i != p){
			temp = 0 ;
			flag = true ;
			dfs(i , n) ;
			add_self(temp , dp[i][0]) ;
			add_self(temp , dp[i][1]) ;
			temp_w = mul(temp_w , temp) ;
			temp_b = mul(temp_b , dp[i][0]) ;
			//cout << i << " " << temp_b << " " << dp[i][1] << nl ; 
		}
	}
	add_self(dp[n][0] , temp_w) ;
	add_self(dp[n][1] , temp_b) ;
	if(!flag) dp[n][0] = dp[n][1] = 1 ;
	//cout << n << "  " << dp[n][0] << " " << dp[n][1] << nl ;
}

void solve(){
	scanf("%lld" , &n) ;
	ll root , a , b , ans=0 ;
	beg(i , n-1){
		scanf("%lld %lld" , &a , &b) ;
		gr[a].pb(b) ;
		gr[b].pb(a) ;
	}
	dfs(1 , 0) ;
	ans = (dp[1][0] + dp[1][1])%MOD ;
	//cout << dp[2][0] << " " << dp[2][1] << nl ;
	printf("%lld" , ans) ;
}

//---------------------------------------------------DRIVER----------------------------------------------------------
int main()
{
    fast ;
    int t=1 ;
    //scanf("%lld" , &t) ;
    while(t--){
        solve() ;
    }
    return 0;
}	

Measured memory_bytes: 14208
import java.util.*;

public class Main {
    public static void main(String[] args){
   
      Scanner sc = new Scanner(System.in);
    	int A1 = sc.nextInt();
      	int A2 = sc.nextInt();
      	int A3 = sc.nextInt();

      	int ans = A1 + A2 + A3;
 		if(ans >= 22){
        System.out.println("bust");
   		}else{
		System.out.println("win");
          }
}
}

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

int main(){
  int n;
  cin >>n;
  int color[8] = {0};
  int cnt = 0;
  rep(i,n){
    int a; cin >>a;
    if(a>=1 and a<=399) color[0]++;
    else if(a<=799) color[1]++;
    else if(a<=1199) color[2]++;
    else if(a<=1599) color[3]++;
    else if(a<=1999) color[4]++;
    else if(a<=2399) color[5]++;
    else if(a<=2799) color[6]++;
    else if(a<=3199) color[7]++;
    else if(a>=3200) cnt++;
  }
  int ans = 0;
  rep(i,8){
    if(color[i]>0) ans++;
  }
  if(ans==0) cout << 1 << " " << cnt << endl;
  else cout << ans << " " << ans+cnt << endl; 
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
using namespace std;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
#define pb push_back
template<class T> void print(const T& x){cout << x << endl;}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;

int main(){
    int t, x;
    cin >>t >> x;
    double ans = (double)t / x;
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3764
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <utility>
using namespace std;

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

#define MAX_M 1e5

map<string, int> id;

int N, M, num;
string S;
vector<pair<int, int>> town(MAX_M);
vector<pair<int, int>> town_sort(MAX_M);

int main() {

  cin >> N >> M;

  rep(i, M) {
    cin >> town[i].first >> town[i].second;
    town_sort[i].first = town[i].first;
    town_sort[i].second = town[i].second;
  }

  sort(town_sort.begin(), town_sort.begin()+M);


  for(int i=0; i<M; ++i) {
    if(i==0) {
      S = to_string(town_sort[i].first)+to_string(town_sort[i].second);
      id[S] = 1;
      num = 1;
      ++num;
    }else {
      if(town_sort[i].first!=town_sort[i-1].first) {
        num = 1;
      }
      S = to_string(town_sort[i].first)+to_string(town_sort[i].second);
      id[S] = num;
      ++num;
    }
  }

  rep(i, M) {
    S = to_string(town[i].first)+to_string(town[i].second);
    cout << setfill('0') << right << setw(6) << town[i].first;
    cout << setfill('0') << right << setw(6) << id[S] << endl;
  }

  return 0;
}


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

int main(){
    int N,a,b,c,d;
    cin>>N;
    a=N/1000;
    N=N-a*1000;
    b=N/100;
    N=N-b*100;
    c=N/10;
    N=N-10*c;
    d=N;
    if(((a==b)&&(b==c))||((b==c)&&(c==d)))cout<<"Yes"<<endl;
    else{cout<<"No"<<endl;}
    return 0;
}

Measured memory_bytes: 3624
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  N = readint()[1]
  A = readint()

  b = Array{int,2}(undef,32,N)
  oe = Vector{int}(undef,32)
  oe .= 0
  for i in 1:N
    for j in 1:32
      k = A[i]
      b[j,i] = k >> (j-1) &1
      if i > 2
        oe[j] += b[j,i]
      end
    end
  end

  r = Array{int,2}(undef,32,N)
  r .= 0

  for i in 1:32
    # odd or even 
    oe[i] = oe[i] %2

    if b[i,1]%2 == 0
      if b[i,2]%2 == 0
        if oe[i] == 1
          r[i,1] = 1
          r[i,2] = 1
        else
          r[i,1] = 0
          r[i,2] = 0
        end 
      else
        if oe[i] == 1
          r[i,1] = 0
          r[i,2] = 1
        else
          r[i,1] = 1
          r[i,2] = 0
        end
      end
    else
      if b[i,2]%2 == 0
        if oe[i] == 1
          r[i,1] = 1
          r[i,2] = 0
        else
          r[i,1] = 0
          r[i,2] = 1
        end 
      else
        if oe[i] == 1
          r[i,1] = 0
          r[i,2] = 0
        else
          r[i,1] = 1
          r[i,2] = 1
        end
      end
    end
  end

    for i in 2:N-1
      for j in 1:32
        if b[j,i] == b[j,i+1]
          r[j,i+1] = r[j,i]
        else
          if r[j,i]==0
            r[j,i+1] = 1
          else
            r[j,i+1] = 0
          end
        end
      end
    end

    for i in 1:N
      s = 0
      for j in 1:32
        s += r[j,i]*(2^(j-1))
      end
      println(s)
    end

  
  end


main()

Measured memory_bytes: 307624
package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)
	for i := 1; i <= b; i++ {
		if a*i%b == c {
			fmt.Print("YES")
			return
		}
	}
	fmt.Print("NO")
}


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

using namespace std;

int main() {
    int N;  cin >> N;
    int *A = new int[N];
    for (int i = 0; i < N; i++)
        cin >> A[i];

    int *d = new int[N], *u = new int[N];
    d[0] = abs(A[0]), u[N-1] = abs(A[N-1]);
    for (int i = 0; i < N-1; i++) {
        d[i+1] = d[i] + abs(A[i+1] - A[i]);
        u[N-2-i] = u[N-1-i] + abs(A[N-2-i] - A[N-1-i]);
    }

    cout << u[1] + abs(A[1]) << endl;

    for (int i = 1; i < N-1; i++) {
        cout << d[i-1] + u[i+1]  + abs(A[i-1] - A[i+1]) << endl;
    }

    cout << d[N-2] + abs(A[N-2]) << endl;

    return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 62;
constexpr double EPS = 1e-9;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
  }
} initializer;

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

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (it != vec.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pa) {
  return os << "(" << pa.first << ", " << pa.second << ")";
}

template<typename Tuple, size_t N>
struct TuplePrinter {
  static void print(const Tuple &t) {
    TuplePrinter<Tuple, N-1>::print(t);
    cout << ", " << get<N-1>(t);
  }
};

template<typename Tuple>
struct TuplePrinter<Tuple, 1> {
  static void print(const Tuple &t) {
    cout << get<0>(t);
  }
};

template<typename... T>
ostream &operator<<(ostream &os, const tuple<T...> &tup) {
  os << "(";
  TuplePrinter<decltype(tup), sizeof...(T)>::print(tup);
  return os << ")";
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &se) {
  os << "{";
  for (auto it = se.begin(); it != se.end(); ++it) {
    if (it != se.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &ma) {
  os << "{";
  for (auto it = ma.begin(); it != ma.end(); ++it) {
    if (it != ma.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  return os << "}";
}

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }
#define dump(...) cout<<#__VA_ARGS__<<": [L_"<<__LINE__<<"]"<<'\n'; print(__VA_ARGS__);cout<<'\n';

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

int main() {
  int n, m; cin>>n>>m;
  int ans = n+1;
  vector<int> a(n+2);
  rep(i, m) {
    int c, d; cin>>c>>d;
    REP(j, c, d) {
      a[j] += 2;
    }
  }
  int cnt = 0;
  rep(i, n+2) {
    if (a[i]>0) ++cnt;
    else {
      ans += cnt*2;
      cnt = 0;
    }
  }
  print(ans);

  return 0;
}


Measured memory_bytes: 3216
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] nums = new int[3];
		boolean isSuccessFlg = false;
		for (int i = 0; i < 3; i++) {
			nums[i] = sc.nextInt();
		}
		int k = sc.nextInt();
		int a = nums[0];
		for (int i = 0; i <= k; i++) {
			int b = (int) (nums[1] * Math.pow(2, i));
			int c = (int) (nums[2] * Math.pow(2, k - i));
			if (c > b && b > a) {
				isSuccessFlg = true;
				break;
			}
		}

		if (isSuccessFlg) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 35632
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  int N, M;
  scanf("%d",&N);
  scanf("%d",&M);
  std::vector<int > A(N);
  for (int i=0; i<N; i++){
    scanf("%d",&A[i]);
  }
  std::sort(A.begin(), A.end());
  std::vector<int > B(M);
  std::vector<long long> C(M);
  std::multimap<long long, int, std::greater<long long> > map;
  for (int i=0; i<M; i++){
    scanf("%d",&B[i]);
    scanf("%lld",&C[i]);
    map.insert(std::make_pair(C[i],B[i]));
  }
  auto itr_map = map.begin();
  int index_A = 0;
  int count = 0;
  while(A[index_A]<itr_map->first){
    A[index_A] = itr_map->first;
    index_A++;
    count++;
    if (count>=itr_map->second){
      itr_map++;
      count=0;
    }
    if (index_A>=A.size() || itr_map==map.end()){
      break;
    }
  }
  long long sum = 0;
  for (int i=0; i<N; i++){
    //printf("A[%d]=%lld\n",i,A[i]);
    sum += A[i];
  }
  printf("%lld\n",sum);
  return 0;
}


Measured memory_bytes: 8064
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;

int n;
int ans=0;

int l[20000],r[20000];
int len[20000];
char c;
char s[11000][15];

void init()
{
    cin>>n;
    for (int i=1; i<=n; ++i)
    {
        len[i]=0;
        while (1)
        {
            scanf("%c",&c);
            if (c=='\n')
            {
                if (len[i]==0) continue;
                else break;
            }
            s[i][len[i]]=c;
            len[i]++;
        }
    }
    for (int i=1; i<=n; ++i)
    {
        if (s[i][0] == 'A') l[i]=1;
        if (s[i][0] == 'B') l[i]=2;
        if (s[i][len[i]-1] == 'A') r[i]=1;
        if (s[i][len[i]-1] == 'B') r[i]=2;
    }
}

void solve()
{
    for (int i=1; i<=n; ++i)
        for (int j=0; j<len[i]-1-1; ++j)
            if (s[i][j]=='A' && s[i][j+1]=='B')
                ans++;
    int rA = 0, lB =0, rAlB=0;
    for (int i=1; i<=n; ++i)
    {
        if (r[i]==1 && l[i]==2) rAlB++;
        else if (r[i]==1) rA++;
        else if (l[i]==2) lB++;
    }
    if (rAlB==0)
    {
        ans+=min(rA,lB);
    }else
    {
        ans+=rAlB-1;
        if (rA>0)
        {
            rA--;
            ans++;
        }
        if (lB>0)
        {
            lB--;
            ans++;
        }
        ans+=min(rA,lB);
    }
    cout<<ans<<endl;
}

int main()
{
    init();
    solve();
    return 0;
}



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

#define N 16

int main()
{
  while(true){
    int n;
    cin >> n;
    if ( n == 0 ) break;
    int ice[N]={0,};
    for(int i = 0; i < n; ++i){
      int t;
      cin >> t;
      ice[t]++;
    }
    for(int i = 0; i < 10; ++i){
      if( ice[i] > 0 ){
	for(int j = 0; j < ice[i];  ++j){
	  cout << '*';
	}
	cout << endl;
      }else{
	cout << '-' << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

using ll = long long;

#define MOD 1000000007

#define FOR(i, m, n) for (ll i = m; i <= n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)

ll gcd(ll a, ll b) { if (a < b) { a ^= b; b ^= a; a ^= b; } return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

ll ANS[2010];

int main() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    
    FOR(i, 1, N - 1)
    FOR(j, i + 1, N) {
        if (i <= X && j <= X) ANS[j - i]++;
        else if (i >= Y && j >= Y) ANS[j - i]++;
        else {
            ll ii = max(i, X);
            ll jj = min(j, Y);
            ll Xi = max(X - i, 0LL);
            ll Yj = max(j - Y, 0LL);
            ll d  = min(jj - ii, ii - X + Y - jj + 1);
            ANS[d + Xi + Yj]++;
        }
    }

    FOR(i, 1, N - 1) cout << ANS[i] << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <cmath>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define pb push_back
#define fst first
#define snd second

typedef long long ll;
typedef pair<int,int> pii;
template<typename T> using min_queue=priority_queue<T,vector<T>,greater<T>>;

const ll MOD=1e9+7;

int N,M;
vector<int> c[100100];

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

  cin>>N>>M;
  int a,b;
  for(int i=0;i<N;i++) cin>>a>>b, c[a].pb(b);

  priority_queue<int> q;
  int res=0;
  for(int i=1;i<=M;i++) {
    for(int k:c[i]) q.push(k);
    if (!q.empty()) {
      res+=q.top();
      q.pop();
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 5632
import bisect

n = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0

for b_i in B:
  top_n = bisect.bisect_left(A, b_i)
  bottom_n = n-bisect.bisect_right(C, b_i)
  ans += top_n*bottom_n
  
print(ans)

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

int main(){
  int d, t, s;
  cin >> d >> t >> s;
  if(t*s>=d) cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 3592
import java.util.ArrayList;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<Integer>();
		while(sc.hasNext()){
			int tra = sc.nextInt();
			if(tra == 0){
				System.out.println(list.remove(list.size()-1));
			} else {
				list.add(tra);
			}
		}
	}

}

Measured memory_bytes: 17212
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
int color[8];
map<string,int> used;
set<int> S;
int t;

void rot1(){
  rep(i,3)swap(color[i],color[i+1]);
  rep(i,3)swap(color[i+4],color[i+5]);
}

void rot2(){
  swap(color[0],color[4]);  swap(color[1],color[5]);
  swap(color[4],color[7]);  swap(color[5],color[6]);
  swap(color[7],color[3]);  swap(color[6],color[2]);
}

bool check(){
  int s=0;
  rep(i,8)s=s*10+color[i];
  t=s;
  return S.count(t)!=0;
}

void solve(){
  S.clear();
  int num[8];
  int cp[8];
  rep(i,8)num[i]=i,cp[i]=color[i];
  do{
    rep(i,8)color[i]=cp[num[i]];
    bool f=false;
    rep(i,4){ rot1();
      rep(j,4){ rot2();
	rep(k,4){ rot1();
	  if(check())f=true;
	}
      }
    }
    if(!f)S.insert(t);
  }while(next_permutation(num,num+8));
  cout<<S.size()<<endl;
}

string in[8];
int main(){
  while(cin>>in[7]){
    rep(i,7)cin>>in[i];
    used.clear();
    int Num=1;
    rep(i,8){
      if(!used.count(in[i]))
	used[in[i]]=Num++;
      color[i]=used[in[i]];
    }
    solve();
  }
  return 0;
}

Measured memory_bytes: 3300
#include<iostream>
#include<cstdio>
using namespace std;
int a[4];
int main()
{
	int s1,s2,s=0,minn=100000000,minnn;
	for(int i=1;i<=3;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=3;i++)
	{
		if(a[i]<minn) 
		{
			minn=a[i];
			minnn=i;
		}
	}
	s=s+minn;
	minn=100000000;
	for(int i=1;i<=3;i++)
	{
		if(i!=minnn)
		{
			if(a[i]<minn) minn=a[i];
		}
	}
	s+=minn;
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
class SegmentTree
  def initialize(n)
    @sz=2**(Math.log(n)/Math.log(2)).ceil
    @seg=Array.new(2*@sz-1){0}
    @root=0
    @nil=-1
  end

  attr_accessor :seg

  def max(a, b, i=@root, l=0, r=@sz)
    if b<=l or r<=a
      @nil
    elsif a<=l and r<=b
      @seg[i]
    else
      m=(r+l)/2
      vl=max(a, b, 2*i+1, l, m)
      vr=max(a, b, 2*i+2, m, r)
      [vl, vr].max
    end
  end

  def update(i, data)
    i+=@sz-1
    @seg[i]=data
    while i.nonzero?
      i=(i-1)/2
      @seg[i]=[@seg[2*i+1], @seg[2*i+2]].max
    end
  end

  def answer
    @seg[@root]
  end
end


n=gets.to_i
a=[]
n.times do |i|
  e=gets.to_i
  a<< [e, -i]
end

b=a.sort_by do |_a|
  [_a[0], _a[1]]
end

st=SegmentTree.new(n)
b.each do |_b|
  i=-_b[1]
  st.update(i, st.max(0, i+1)+1)
end

puts st.answer

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

using i64 = int64_t;

constexpr i64 MOD = 1000000007;

i64 repeated_squaring(i64 x, i64 n) {
    i64 res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int main(){
    int n, c;
    cin >> n >> c;
    vector<int>a, b;
    for(int i=0;i<n;++i){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    for(int i=0;i<n;++i){
        int tmp;
        cin >> tmp;
        b.push_back(tmp);
    }
    //for(int i=0;i<n;++i)assert(a[i] == b[i]);
    vector<vector<i64>> sum_powers(n, vector<i64>(c+1));
    for(int i=0;i<n;++i){
        for(i64 j=0;j<=c;++j){
            for(i64 k=a[i];k<=b[i];++k){
                sum_powers[i][j] += repeated_squaring(k, j);
                sum_powers[i][j] %= MOD;
            }
        }
    }
    vector<vector<i64>> dp(n, vector<i64>(c+1));
    for(i64 k=0;k<=c;++k){
        dp[0][k] += sum_powers[0][k];
        dp[0][k] %= MOD;
    }
    for(int i=1;i<n;++i){
        for(int j=0;j<=c;++j){
            for(i64 k=0;k<=c-j;++k){
                dp[i][j+k] += dp[i-1][j] * sum_powers[i][k];
                dp[i][j+k] %= MOD;
            }
        }
    }

    cout << dp[n-1][c] << endl;

    return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)


void solve(long long A, long long B, long long C){
    cout << min(C, B/A) << "\n";
}

int main(){

    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int p[6000],flg[51000]={1,1},i,j,t;
	for(i=t=0;i<51000;i++)
		if(!flg[i])
		{
			p[t++]=i;
			for(j=2;j*i<51000;j++)
				flg[i*j]=1;
		}
	for(;~scanf("%d",&t);)
	{
		for(i=0;p[i]<t;i++);
		printf("%d %d\n",p[i-1],p[i]==t?p[i+1]:p[i]);
	}
	return 0;
}

Measured memory_bytes: 824
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<ll> >;

const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MX = 0; //最大値

#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define PB push_back
#define F first
#define S second

ll N, M;
Graph G;

void solve(){
    vector<int> dist(N, -1), prev(N, -1);
    queue<ll> que;
    que.push(0);
    dist[0] = 0;
    while(!que.empty()) {
        ll v = que.front();
        que.pop();
        for (auto nv : G[v]){
            if(dist[nv] == -1){
                dist[nv] = dist[v]+1;
                prev[nv] = v;
                que.push(nv);
            }
        }
    }
    cout << "Yes" << endl;
    for(int i = 1; i < N; i++) cout << prev[i] + 1 << endl;
}

int main(){
    cin >> N >> M;
    G.assign(N, vector<ll>());
    rep(i, M){
        ll a,b;
        cin >> a >> b;
        a--; b--;
        G[a].PB(b); G[b].PB(a);
    }
    solve();
    return 0;
}

Measured memory_bytes: 12916
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    DP = [[0 for j in range(K + 1)] for i in range(N)]
    for i in range(A[0] + 1): DP[0][i] = 1
    cum = [0] * (K + 2)
    for i in range(1, N):
        for j in range(1, K + 2): cum[j] = (cum[j-1] + DP[i-1][j-1]) % mod
        for j in range(K + 1): DP[i][j] = (cum[j + 1] - cum[max(0, j - A[i])]) % mod
    print(DP[N-1][K])

    return 0

if __name__ == "__main__":
    solve()

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

using namespace std;

const int mod = 1e9 + 7;

int s;
int dp[2010];

int f(int sum) {
    if(sum == s) return 1;

    int &ans = dp[sum];
    if(ans != -1) return ans;
    ans = 0;

    for (int i = 3; i <= 2000; ++i) {
        if(sum + i <= s) {
            ans += f(sum + i);
            ans %= mod;
        }
    }
    return ans;
}

int main() {
    memset(dp, -1, sizeof dp);
    cin >> s;
    cout << f(0) << "\n";
    return 0;
}


Measured memory_bytes: 3644
A=io.read("n")
B=io.read("n")
K=io.read("n")
if 2*K>=B-A+1 then
  for i=A,B do
    print(i)
  end
  else 
  for i=A,A+K-1 do
    print(i)
  end
  for i=B-K+1,B do
    print(i)
  end
end

Measured memory_bytes: 752
from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
prev = [-1] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def bfs(v):
    q = deque()
    prev[v] = -99999
    q.append(v)
    while q:
        v = q.popleft()
        for u in edges[v]:
            if prev[u] == -1:
                prev[u] = v
                q.append(u)

bfs(0)
print("Yes")
for i in range(1, n):
    print(prev[i] + 1)


Measured memory_bytes: 34100
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+10;
int n,top;
int a[N],b[N],c[N],pre[N],suf[N],stk[N];
long double ans;
void init(){
	int mx=0,ps=-1;
	for(int i=1;i<=n;i++) if(a[i]>mx) mx=a[i],ps=i;
	rotate(a+1,a+ps,a+n+1);
	rotate(b+1,b+ps,b+n+1);
	a[++n]=a[1],b[n]=b[1];
	for(int i=3;i<=n;i++) c[i]=2*(b[i-1]+c[i-1])-c[i-2],a[i]-=c[i];
}
long double slope(int tp1,int tp2){ 
	return 1.0*(a[tp2]-a[tp1])/(tp2-tp1); 
}
bool pd(int tp1,int tp2,int tp3){ 
	return slope(tp1,tp2)<=slope(tp2,tp3); 
}
void solve(){
	for(int i=1;i<=n;i++){
		while(top>1 && pd(stk[top-1],stk[top],i)) --top;
		stk[++top]=i;
	}
	stk[top+1]=n+1;
	for(int i=1;i<=top;i++) for(int j=stk[i];j<stk[i+1];j++) pre[j]=stk[i];
	for(int i=1;i<=top;i++) for(int j=stk[i-1]+1;j<=stk[i];j++) suf[j]=stk[i];
	for(int i=1;i<n;i++){
		if(pre[i]!=suf[i]) ans+=1.0*(a[suf[i]]*(i-pre[i])+a[pre[i]]*(suf[i]-i))/(suf[i]-pre[i]);
		else ans+=1.0*a[i];
	}
	for(int i=1;i<n;i++) ans+=c[i];
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	init();
	solve();
	printf("%.12Lf",1.0*ans/(n-1));
} 


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

int main() {
  long long A,B,C,D;
  cin >> A >> B >> C >> D;
  if(D<0 && B<0){
    cout << A*C << endl;
  }
  else if(A>0 && C>0){
    cout << B*D << endl;
  }
  else{
    cout << max(A*C,max(B*D,max(A*D,B*C))) << endl;
  }
}


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

#define         eps         10e-9
#define         pi          2*acos(0)
#define         P1          1e9+7
#define         P2          1e9+9
#define         lli         long long int

using namespace std;

///ISNNJB

/**int fx[]={+1,-1,+0,+0};
int fy[]={+0,+0,+1,-1};
int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};*/

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

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

    lli a,b,c,d,t,n,m,k,x,y,q,ctn,l1,l2,ara[1100],total=0;
    cin>>n>>k;
    for (int i=1; i<=n;  i++)
        cin>>ara[i];
    sort(ara+1, ara+n+1);

    for (int i=1; i<=k; i++)
        total+=ara[i];
    cout<<total<<endl;

    return 0;
}


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

int main(){
    int k,s,i,j,w;
    cin >> k >> s;
    int x,y,z,num=0;
    for (i=0;i<=k;i++){
        x = i;
        for (j=0;j<=k;j++){
            y = j;
            z = s - x - y;
            if (z >= 0 && z <= k){
                num++;
            }
        }
    }
    cout << num;
}


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

using namespace std;

#define PB push_back  
#define MP(A, B) make_pair(A, B)  
#define fi first  
#define se second  

#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define pii pair<int,int>
#define ll long long  
#define MAX 1000005  
#define MOD 998244353  
#define M 998244353  
#define INF 0x3f3f3f3f  
#define EXP 1e-8  
#define lowbit(x) (x&-x)  

long long qpow(long long a, long long n) {
    long long ret = 1;
    a = (a % M + M) % M;
    for (; n; n >>= 1) {
        if (n & 1) ret = (ret * a) % M;
        a = (a * a) % M;
    }
    return ret;
}
 
vector<int64_t> fact, seq_inv, fact_inv;
 
void create_fact_mod(int num){
    fact[0] = fact[1] = 1;
    for(int i=2; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
}
 
void create_seq_inv_mod(int num){
    seq_inv[0] = seq_inv[1] = 1;
    for(int i=2; i<=num; i++) seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
}
 
void create_fact_inv_mod(int num){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i=2; i<=num; i++) fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
}
 
void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}
 
int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}
 
int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}
 
int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}
 
int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}
 
int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 


long long n,m, k; 
long long dp[200005] = {0};
int main() {
    cin >> n >> m >> k;
    long long ans = 0;
    create_mod_tables(200005);
    for (int i = 0; i <= k; ++i) {
        dp[i] = (m * qpow(m-1, n-i-1) %MOD * comb_mod(n-1, i)) %MOD;
        ans = (ans + dp[i]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9528
using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Linq;

namespace ConsoleApp8
{
    class Program
    {
        static void Main(string[] args)
        {
            var Count = Console.ReadLine();
            string[] values = Count.Split(' ');
            int a = int.Parse(values[0]);
            int b = int.Parse(values[1]);
            int c = int.Parse(values[2]);
            int d = int.Parse(values[3]);
            int e = int.Parse(values[4]);

            if (a == 0)
                Console.WriteLine('1');
            else if(b == 0)
                Console.WriteLine('2');
            else if (c == 0)
                Console.WriteLine('3');
            else if (d == 0)
                Console.WriteLine('4');
            else
                Console.WriteLine('5');
        }
    }
}

Measured memory_bytes: 27368
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

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

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

int main(){
    int n, k; cin>>n>>k;
    vector<ll> h(n);
    ll sum=0, maxp=0;
    for(int i=0; i<n; i++){
        cin>>h[i];
    }
    sort(h.begin(), h.end());

    ll ans=INF;
    for(int i=0; i+k<=n; i++){
        chmin(ans, h[i+k-1]-h[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    R = iRaw()
    ans = R*2*math.pi         
    return ans

if __name__ == "__main__":
    print(main())


Measured memory_bytes: 67556
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
template<typename T>
int sz(const T &a){return (int)a.size();}
const int MAXN=1e5+1;
int height[MAXN];
bool ngood[MAXN];
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>height[i];
    }
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        if(height[a]<=height[b])ngood[a]=true;
        if(height[b]<=height[a])ngood[b]=true;
    }
    int am=0;
    for(int i=1;i<=n;i++){
        if(!ngood[i])am++;
    }
    printf("%d\n",am);
    return 0;
}

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

long long p[26];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s; cin >> s;
	for (int i = 0; i < s.length(); i++)
		p[s[i] - 'a']++;
	long long ans = s.length() * (s.length() + 1) / 2 + 1;
	for (int i = 0; i < 26; i++)
		ans -= p[i] * (p[i] + 1) / 2;
	cout << ans << '\n';
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define pf push_front
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ge(a, b) get<(b)>((a))
#define SZ(x) (x).size()
#define endl '\n'
#define FOR(a, b, c) for (auto(a) = (b); (a) < (c); ++(a))
#define ROF(a, b, c) for (auto(a) = (b); (a) > (c); --(a))
#define F0R(a, b) FOR ((a), 0, (b))
#define R0F(a, b) ROF ((a), (b), -1)
#define CEIL(a, b) ((a) + (b)-1) / (b)
#define CLR(a, b) memset((a), (b), sizeof((a)))
template <typename t> bool ckmin(t& a, const t& b) {return a > b ? a = b, true : false;}
template <typename t> bool ckmax(t& a, const t& b) {return a < b ? a = b, true : false;}

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

    ll n, k;
    cin >> n >> k;
    ll m = n;
    if(n > k) {
        n = n % k;
        ckmin(m, n);
    }
    while(n > abs(n - k)) {
        n = abs(n - k);
        ckmin(m, n);
    }
    cout << m << endl;


}




Measured memory_bytes: 256
#include<stdio.h>

const int N = 10;
int a[N][N];
bool isClick[N][N];

void Click(int x,int y)
{
	int dx[] = {0,1,-1,0, 0,};
	int dy[] = {0,0, 0,1,-1,};
	for(int i = 0;i < 5; ++i)
	{
		if(x+dx[i] >= 0 && x+dx[i] < N && y+dy[i] >= 0 && y+dy[i] < N)
			a[x+dx[i]][y+dy[i]] = !a[x+dx[i]][y+dy[i]];
	}
}

void AllDelete()
{
	int original[N][N];
	int i,j;
	for(i=0;i<N;++i)for(j=0;j<N;++j)original[i][j]=a[i][j];

	unsigned mask=0;
	for(;;)
	{
		for(i=0;i<N;++i)
			for(j=0;j<N;++j)
				a[i][j] = original[i][j],isClick[i][j] = false;
		for(j = 0;j < N;++j)
		{
			if(mask & (1<<j))
				Click(0,j), isClick[0][j] = true;
		}
		++mask;
		for(i = 1; i < N; ++i)
			for(j = 0; j < N; ++j)
			{
				if(a[i-1][j])
					Click(i,j), isClick[i][j] = true;
			}
		bool isEnd = true;
		for(j = 0; j < N; ++j)
		{
			if(a[N-1][j]) isEnd = false;
		}
		if(isEnd) return;
	}
}

int main(void)
{
	int n,i,j;
	scanf("%d",&n);
	while(n--)
	{
		for(i=0;i<N;++i)
			for(j=0;j<N;++j)
			{
				scanf("%d",&a[i][j]);
				isClick[i][j] = false;
			}

		AllDelete();
		for(i=0;i<N;++i)
		{
			for(j=0;j<N;++j)
				printf("%s%d%s",(j?" ":""),isClick[i][j],(N-j==1?"\n":""));
		}
	}
	return 0;
}

Measured memory_bytes: 0
N = int(input())
v_list= list(map(int, input().split()))
v_list_s = sorted(v_list, reverse=True)

while True:
    if len(v_list_s) <= 1:
        break
    temp_c = (v_list_s[-1] + v_list_s[-2])/2
    v_list_s.remove(v_list_s[-1])
    v_list_s.remove(v_list_s[-1])
    v_list_s.append(temp_c)

print(sorted(v_list_s)[0])


Measured memory_bytes: 2940
#include <iostream>
#include <string>
using namespace std;
int main()
{   
	string S;
	cin >> S;
	int cnt = 0;
	for(int i=0; i<3; i++)
	{
		if(S[i]=='o') cnt++;
	}
	cout << 700 + cnt * 100 << endl;

	return 0;
}

Measured memory_bytes: 256
import numpy

n,q = [int(x) for x in input().split()]
s = input()

li = [0]*(n+1)
for i in range(n-1):
    if (s[i]=="A" and s[i+1] == "C"):
        li[i+1] = 1
cum = numpy.cumsum(li)
for i in range(q):
    l,r = [int(x) for x in input().split()]
    print(cum[r-1]-cum[l-1])

Measured memory_bytes: 18596
from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=[[0,0]]
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        for z, dist in G[y]:
            if seen[z] == 0:
                di[z] = d + dist
                stack.append([z, d + dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)

Measured memory_bytes: 51576
#include <bits/stdc++.h>
using namespace std;
template<typename T = int, T mod = 1'000'000'007, typename U = long long>
struct umod{
        T val;
        umod(): val(0){}
        umod(U x){ x %= mod; if(x < 0) x += mod; val = x;}
        umod& operator += (umod oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
	umod& operator -= (umod oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
	umod& operator *= (umod oth){ val = ((U)val) * oth.val % mod; return *this; }
	umod& operator /= (umod oth){ return *this *= oth.inverse(); }
        umod& operator ^= (U oth){ return *this = pwr(*this, oth); }
	umod operator + (umod oth) const { return umod(*this) += oth; }
	umod operator - (umod oth) const { return umod(*this) -= oth; }
	umod operator * (umod oth) const { return umod(*this) *= oth; }
	umod operator / (umod oth) const { return umod(*this) /= oth; }
        umod operator ^ (long long oth) const { return umod(*this) ^= oth; }
	bool operator < (umod oth) const { return val < oth.val; }
	bool operator > (umod oth) const { return val > oth.val; }
	bool operator <= (umod oth) const { return val <= oth.val; }
	bool operator >= (umod oth) const { return val >= oth.val; }
	bool operator == (umod oth) const { return val == oth.val; }
	bool operator != (umod oth) const { return val != oth.val; }
        umod pwr(umod a, U b) const { umod r = 1; for(; b; a *= a, b >>= 1) if(b&1) r *= a; return r; }
        umod inverse() const {
		U a = val, b = mod, u = 1, v = 0;
		while(b){
			U t = a/b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		if(u < 0)
			u += mod;
		return u;
        }
};

template<typename U>
struct NCR {
        vector<U> fact, ifact;
        NCR(int size){
                fact.resize(size + 1); ifact.resize(size + 1);
                fact[0] = 1;
                for(int i = 1; i <= size; i++) fact[i] = fact[i - 1] * i;
                ifact[size] = fact[size].inverse();
                for(int i = size - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
        }
        U ncr(int n, int r){
                if(n < r) return 0;
                return fact[n] * ifact[r] * ifact[n - r];
        }
};

using U = umod<>;
using NC = NCR<U>;

const int maxn = 1'000'000;
int main(){
	NC kit(3 * maxn);
	int x, y; cin >> x >> y;
	U ans = 0;
	for(int i = 0; i <= x; i++){
		int mx = i, my = 2 * i;
		int px = x - mx, py = y - my;
		if(px == 2 * py){
			ans += kit.ncr(i + py, i);
		}
	}
	cout << ans.val << endl;
	return 0;
}


Measured memory_bytes: 23680
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

int n, m, k, maxn = 0;
vector<int>list;
bool flag[100005];
bool flag2[100005];

struct MyStruct
{
	//vector<int>list;
	vector<pair<int, int>>list;
};

vector<MyStruct>slist(100002);

int func(int no, bool iro) {

	for (int i = 0; i < slist[no].list.size(); i++) {
		if (flag[slist[no].list[i].first] == false) {

			flag[slist[no].list[i].first] = true;

			if (slist[no].list[i].second % 2 == 0) {
				flag2[slist[no].list[i].first] = iro;
				func(slist[no].list[i].first, iro);
			}
			else {
				flag2[slist[no].list[i].first] = (iro + 1) % 2;
				func(slist[no].list[i].first, (iro + 1 ) % 2 );
			}

		}
	}


	return 0;
}


signed main() {
	memset(flag, false, sizeof(flag));

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int v1, v2, w;
		cin >> v1 >> v2 >> w;

		slist[v1].list.push_back(make_pair(v2, w));
		slist[v2].list.push_back(make_pair(v1, w));		
	}

	for (int i = 1; i <= n; i++) {
		sort(slist[i].list.begin(), slist[i].list.end());
		slist[i].list.erase(std::unique(slist[i].list.begin(), slist[i].list.end()), slist[i].list.end());
	}

	func(1, 0);

	for (int i = 1; i <= n; i++) {
		cout << flag2[i] << endl;
	}




	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 8960
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define input freopen("1.txt","r",stdin);
#define output freopen("output.txt","w",stdout);
#define ll long long int
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define vi vector<int>
#define vii vector<vi>
#define vl vector<ll>
#define vll vector<vl>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define mp make_pair
#define vpi vector<pii>
#define vpl vector<pll> 
using namespace std;
 
const int p=1e9+7;
const int maxn=1e5+2;
int DP[3000][3000], choice[3000][3000];  // choice[i][j] = 1, 2, 3   if(0) => i-- if(1) => j-- if(2) => i-- && j--

void solve() {
    // int N; cin >> N;
    string s, t; cin >> s >> t;
    DP[0][0] = 0;
    choice[0][0] = 1;
    if(s[0] == t[0]) {
        DP[0][0] = 1;
        choice[0][0] = 3;
    }
    int n = s.length();
    int m = t.length();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            // not picking 
            if(i > 0) {
                DP[i][j] = DP[i-1][j];
                choice[i][j] = 1;
            }
            if(j > 0) {
                if(DP[i][j-1] > DP[i][j]) { // if DP[i][j] is not initialised above it contains zero due to global declaration
                    DP[i][j] = DP[i][j-1];
                    choice[i][j] = 2;
                }
            }

            // picking only when they characters are equal
            if(s[i] == t[j]) {
                int ans = 1;
                if(i > 0 && j > 0) {
                    ans = 1 + DP[i-1][j-1];
                }
                if(ans > DP[i][j]) {
                    DP[i][j] = ans;
                    choice[i][j] = 3;
                }
            }
        }
    }

    // cout << DP[n-1][m-1] <<"\n";       // optimal max length of common subsequence

    // choice 1 & 2  correspond to not getting picked
    int i = n-1, j = m-1;
    string ans = "";
    while(i >= 0 && j >= 0) {
        if(choice[i][j] == 1 || choice[i][j] == 0) {
            i--;
        }
        else if(choice[i][j] == 2) {
            j--;
        }
        else if(choice[i][j] == 3) {
            ans = s[i] + ans;
            i--; j--;
        }
    }
    cout << ans <<"\n";
}

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

Measured memory_bytes: 74056
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,x = LI()
if 500*k >= x:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38384
#include <cstdio>
#include <algorithm>

using namespace std;

int C[10][10];
int h, w;

int main() {
    scanf("%d%d", &h, &w);
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++) scanf("%d", &C[i][j]);
    for (int k = 0; k < 10; k++)
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
    int ans = 0;
    for (int i = 0, x; i < h; i++)
        for (int j = 0; j < w; j++) scanf("%d", &x), ans += (x==-1)?0:C[x][1];
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128