akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
class matrix{
public:
    int n;
    vector<vi> val;
    matrix(int n=2);
    matrix operator+(const matrix&) const;
    matrix operator-(const matrix&) const;
    matrix operator*(const matrix&) const;
    matrix& operator=(const matrix& b){
        val=b.val;
        n=b.n;
        return *this;
    }
    void set(int x){
        rep(i,0,n){
            rep(j,0,n){
                val[i][j]=x;
            }
        }
    }
    void print(){
        rep(i,0,n){
            rep(j,0,n){
                cout<<val[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    matrix mul(int a){
        matrix ans(this->n);
        rep(i,0,this->n){
            rep(j,0,this->n){
                ans.val[i][j]=a*this->val[i][j];
            }
        }
        return ans;
    }
};
matrix::matrix(int x){
    n=x;
    val.resize(x);
    rep(i,0,x){
        val[i].resize(x);
    }
}
matrix matrix::operator+(const matrix& b) const{
    matrix ans(b.n);
    rep(i,0,b.n){
        rep(j,0,b.n){
            ans.val[i][j]=this->val[i][j]+b.val[i][j];
        }
    }
    return ans;
}
matrix matrix::operator-(const matrix& b) const{
    matrix ans(b.n);
    rep(i,0,b.n){
        rep(j,0,b.n){
            ans.val[i][j]=this->val[i][j]-b.val[i][j];
        }
    }
    return ans;
}
matrix matrix::operator*(const matrix& b) const{
    matrix ans(b.n);
    rep(i,0,b.n){
        rep(j,0,b.n){
            rep(k,0,b.n){
                ans.val[i][j]=(ans.val[i][j]+1LL*this->val[i][k]*b.val[k][j])%hell;
            }
        }
    }
    return ans;            
}
matrix identity(int N=2){
    matrix ans(N);
    rep(i,0,N){
        ans.val[i][i]=1;
    }
    return ans;
}
matrix matexpo(matrix a, int n){
    if(n==0){
        return identity(a.n);
    }
    if(n==1) return a;
    matrix x=matexpo(a,n/2);
    matrix r=x*x;
    if(n&1) r=r*a;
    return r;
}
void solve(){
    int n,k;
    cin>>n>>k;
    matrix mat(n);
    rep(i,0,n){
        rep(j,0,n){
            cin>>mat.val[i][j];
        }
    }
    int ans=0;
    mat=matexpo(mat,k);
    rep(i,0,n){
        rep(j,0,n){
            ans=(ans+mat.val[i][j])%hell;
        }
    }
    cout<<ans<<endl;
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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

int INF=pow(10,9);
int n,A,B,C;

int dfs(int i, int a, int b, int c, vector<int> &l){
    if(i == n){
        int calc;
        if(a>0 && b>0 && c>0){
            calc = abs(A-a) + abs(B-b) + abs(C-c) - 30;
            return calc;
        }
        else{
            return INF;
        }
    }
    else{
        int p,q,r,s;
        p = dfs(i+1, a+l.at(i), b, c, l)+10;
        q = dfs(i+1, a, b+l.at(i), c, l)+10;
        r = dfs(i+1, a, b, c+l.at(i), l)+10;
        s = dfs(i+1, a, b, c, l);
        return min(min(p,q), min(r,s));
    }
}

int main(){
    cin >> n >> A>> B >> C;
    vector<int> l(n);
    for(int i=0; i<n; i++){
        int k;
        cin >> k;
        l.at(i) = k;
    }
    int ans;
    ans = dfs(0, 0, 0, 0, l);
    cout << ans << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int MAX  = 1e7 + 5;
long long int f[MAX]={0};
int main() {

    jaldi

    int n;
    cin>>n;

    for(int i=1;i<MAX;i++) {
        for(int j=i;j<MAX;j+=i){
            f[j]++;
        }
    }
    long long int ans =0;
    for(int i=1;i<=n;i++) {
        long long int temp = i*f[i];
        ans+=temp;
    }
    cout<<ans<<'\n';
}


Measured memory_bytes: 81728
// failed to generate code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

int main(){	
	ll N, D;
	cin >> N >> D;
	ll X[N][D];
	rep(i, N) {
		rep(j, D) {
			cin >> X[i][j];
		}
	}
	ll cnt = 0;
	rep(i, N) {
		for (ll j = i+1; j < N; j++) {
			ll d = 0;
			rep(k, D) {
				d += (X[i][k] - X[j][k])*(X[i][k] - X[j][k]);
			}
			rep(k, 200) {
				if (d == k*k) {
					cnt++;
					break;
				}
			}
		}	
	}
	cout << cnt << endl;
}


Measured memory_bytes: 256
object Main extends App {
  import java.util.Scanner
  val sc = new Scanner(System.in)

  val a = sc.nextInt()
  val b = sc.nextInt()
  val c = sc.nextInt()
  val k = sc.nextInt()

  val result = if (k <= a) {
    k
  } else if (k <= (a + b)) {
    a
  } else {
    a - (k - a - b)
  }
  println(result)
}


Measured memory_bytes: 55380
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef vector<pair<ll,ll> > vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
  ll n;string s;
  cin>>n>>s;
  vvll dp(2,vll(n+1,0));
  rep(i,0,n){
    if(s[i]=='E'){
      dp[0][i+1]=dp[0][i]+1;
      dp[1][i+1]=dp[1][i];
    }
    else{
      dp[0][i+1]=dp[0][i];
      dp[1][i+1]=dp[1][i]+1;
    }
  }
  ll ans=300001;
  rep(i,0,n){
    ll tmp=dp[1][i]+(dp[0][n]-dp[0][i+1]);
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 7684
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

ll solve(){
    string s;
    cin >> s;
    s = "R" + s;
    for(ll i = 1; i < s.size(); i += 2)if(s[i] == 'L')return 0;
    for(ll i = 2; i < s.size(); i += 2)if(s[i] == 'R')return 0;
    return 1;
}

int main(){

    if(solve())cout << "Yes" << endl;
    else cout << "No" << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string s, t;
set<string> S;

void Work()
{
    int lens = s.size();
    int lent = t.size();
    for(int i = 0; i < lens; i++)
    {
        if(s[i] == '?' || s[i] == t[0])//如果字符相等
        {
            string tmp = s;              //构造判断子串之前的字符
            for(int j = 0; j < i; j++)
                if(tmp[j] == '?')
                    tmp[j] ='a';
            bool can = false;
            for(int j = 0; j < lent; j++)    //判断是否为子串
            {

                if(tmp[i+j]!= '?' && tmp[i+j] != t[j])  //字符匹配
                    break;
                tmp[i+j] = t[j];
                if(j == lent - 1) can = true;
            }
            if(can)
            {
                for(int j = i + lent; j < lens; j++) if(tmp[j] == '?') tmp[j] = 'a';//处理匹配后的字符
                S.insert(tmp);  //
            }
        }
    }
    if(S.size() == 0) cout << "UNRESTORABLE" << endl;
    else cout << *S.begin() << endl;
}
int main()
{
    cin >> s >> t;
    Work();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ff first
#define ss second
// #define mp make_pair
#define pb push_back
// #define pop pop_back
#define all(a) a.begin(), a.end()

const int N = 2e5 + 7;
const ll INF = 1e17;

const ll mod = (ll)1e9 + 7;

void solve()
{   
    ll n, w; cin >> n >> w;
    ll wts[n+1], val[n+1]; ll dp[n + 1][w + 1];
    for(int i = 1; i <= n; i++)
        cin >> wts[i] >> val[i];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            if(j < wts[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wts[i]] + val[i]);
        }
    }
    cout << dp[n][w];
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // int t; cin>>t; 
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 82516
#include<stdio.h>
 
int main(void)
{
  int i,j,cnt;
  int t_num, tmp;
  int mochi_info[100];
  int mochi_reslt[100];
  
  scanf("%d",&t_num);
  
  //データ入力
  for(i=0;i<t_num;i++)
  {
    scanf("%d",&mochi_info[i]);
  }
  
  //並べ替え
  for(i=0;i<t_num;i++)
  {
    for(j=0;j<t_num;j++)
    {
      if(mochi_info[i] < mochi_info[j])
      {
        tmp = mochi_info[i];
        mochi_info[i] = mochi_info[j];
        mochi_info[j] = tmp;
      }
    }
  }
  
  //重複削除
  j = 0;
  for(i=0;i<t_num;i++)
  {
    cnt = 0;
    for(j=i+1;j<t_num;j++){
	   if(mochi_info[i] == mochi_info[j])
       {
         mochi_reslt[i] = -1;
         cnt++;
         break;
       }
    }
    if(cnt == 0)
    {
      mochi_reslt[i] = mochi_info[i];
    } 
  }
  
  //合算
  cnt = 0;
  for(i=0;i<t_num;i++)
  {
    if(mochi_reslt[i] > 0)
    {
      cnt++;
    }
  }
  
  printf("%d\n",cnt);
  return 0;
  
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int N, M, Q;
int a[100], b[100], c[100], d[100], A[16];

int dfs(int index, int val){
  if(val>M) return 0;
  if(index==N){
    int ans = 0;
    for(int i=0; i<Q; ++i){
      if(A[b[i]]-A[a[i]]==c[i]) ans += d[i];
    }
    return ans;
  }
  A[index] = val;
  return max(dfs(index, val+1), dfs(index+1, val));
}

int main(){
  cin >> N >> M >> Q;
  for(int i=0; i<Q; ++i){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--; b[i]--;
  }
  A[0] = 1;
  cout << dfs(1,1) << endl;
  return 0;
}

Measured memory_bytes: 3636
import math

def rotate(x, y, theta):
    return (round(x*math.cos(theta) -1*y*math.sin(theta), 5), round(x*math.sin(theta) + y*math.cos(theta), 5))

def koch(p1, p2, n):
    s = (round((2*p1[0] + p2[0])/3, 5), round((2*p1[1] + p2[1])/3, 5))
    t = (round((p1[0] + 2*p2[0])/3, 5), round((p1[1] + 2*p2[1])/3, 5))
    rotated = rotate(t[0]-s[0], t[1]-s[1], math.pi/3)
    u = (s[0] + rotated[0], s[1] + rotated[1])

    if n == 0:
        print(round(p1[0], 5), round(p1[1], 5))
    elif n == -1:
        return None

    koch(p1, s, n-1)
    koch(s, u, n-1)
    koch(u, t, n-1)
    koch(t, p2, n-1)

n = int(input())
koch((0.0, 0.0), (100, 0.0), n)
print(100, 0.0)


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

const int max_n = 1e6;
ll a[max_n];
int main(){
  ll n;  cin >> n;
  ll cnt4 = 0;
  ll cnt2 = 0;
  ll clu = 0;
  for(int i=0 ; i<n ; i++){
    cin >> a[i];
    if(a[i]%4==0 ) cnt4++;
    else if(a[i]%2==0) cnt2++;
    else clu++;
  }
  string s = "";
  if(clu+cnt2 %2-1 <= cnt4){
    s += "Yes";
  }else{
    s += "No";
  }
  cout << s << endl;
  return 0;
}


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

long long minll(long long n,long long m){
  if(n<m){
    return n;
  }
  else{
    return m;
  }
}

int main() {
  int N;
  cin >> N;
  long long dp[110000];
  long long h[110000];
  int K;
  cin >> K;
  for(int i=0;i<110000;i++){
    dp[i]=pow(10,10);
    cin >> h[i];
  }
  for(int i=0;i<K+1;i++){
    dp[i]=abs(h[i]-h[0]);
  }
  for(int i=K+1;i<N;i++){
    long long k=pow(10,10);
    for(int j=1;j<K+1;j++){
      dp[i]=minll(k,dp[i-j]+abs(h[i]-h[i-j]));
      k=dp[i];
    }
  }
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repm(i, m, n) for (int i = (m); i < (int)(n); i++)
#define repr(i, n) for (int i = (n); i > 0; i--)
#define all(vec) vec.begin(), vec.end()
using namespace std;

int main(){
  int a, b, c, d;
  //string a, b;
  cin >> a;
  
  int ans = 0;
  //string ans = "Hello World";
  ans = a * a * a;

  cout << ans << endl;
}


Measured memory_bytes: 3104
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

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

    int r;
    cin >> r;
    string ret = "AGC";
    if(r < 1200){
        ret = "ABC";
    }else if(r < 2800){
        ret = "ARC";
    }
    cout << ret << 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++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

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

const int mod = 1000000007;
struct mint {
ll x; // typedef long long ll;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
}
mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
}
mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
mint operator+(const mint a) const { return mint(*this) += a;}
mint operator-(const mint a) const { return mint(*this) -= a;}
mint operator*(const mint a) const { return mint(*this) *= a;}
mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
}
// for prime mod
mint inv() const { return pow(mod-2);}
mint& operator/=(const mint a) { return *this *= a.inv();}
mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint choose(int n, int r){
    if (n < r) return mint(0);
    mint x = 1, y = 1;
    for(int i = 0; i < r; i++){
        x *= n-i;
        y *= i+1;
    }
    return x / y;
}

int main(){
    int n, k;
    cin >> n >> k;
    mint ans = 0;
    for(int i = 1; i <= k; i++){
        ans = choose(k-1, i-1) * choose(n-k+1, i);
        printf("%lld\n", ans.x);
    }
    return 0;
}

Measured memory_bytes: 3724
n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
c=0
b=[]
for i in range(n-1):
    c+=a[i]
    b.append(c)
mi=abs(s-2*b[0])
for i in range(n-1):
    mi=min(mi,abs(s-2*b[i]))
print(mi)


Measured memory_bytes: 24936
// atcoder/abc175/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;

const int N = 5000 + 5;
const lli inf = 1LL << 60;

int p[N];
lli c[N];

int n;
lli k;

lli vis[N];
lli cycle_size[N];
lli cycle_score[N];

void rec1(int curr, int depth, lli& S, lli& C)
{
  if (vis[curr] != -1) {
    C = depth - vis[curr];
    return ;
  }
  vis[curr] = depth;
  S += c[p[curr]];
  rec1(p[curr], depth + 1, S, C);
  cycle_size[curr] = C;
  cycle_score[curr] = S;
  return ;
}

lli rec2(int curr, int depth, lli S)
{
  if (k < depth) return -inf;
  if (vis[curr]) {
    return -inf;
  }
  vis[curr] = true;

  S += c[curr];
  lli mx = -inf;
  lli z = ((k - depth) / cycle_size[curr]) * cycle_score[curr];

  // cout << curr+1 << ' ' << S << ' ' << z << endl;

  setmax(mx, S);
  setmax(mx, S + z);
  setmax(mx, rec2(p[curr], depth + 1, S));

  vis[curr] = false;
  return mx;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  while (cin >> n >> k) {
    for (int i = 0; i < n; ++i) {
      cin >> p[i];
      --p[i];
    }
    for (int i = 0; i < n; ++i) {
      cin >> c[i];
    }

    fill(vis, vis + N, -1);
    fill(cycle_size, cycle_size + N, -1);
    for (int i = 0; i < n; ++i) {
      if (cycle_size[i] == -1) {
        lli S = 0;
        lli C = 0;
        rec1(i, 0, S, C);
      }
    }

    lli mx = *max_element(c, c + n);
    fill(vis, vis + N, false);
    for (int i = 0; i < n; ++i) {
      setmax(mx, rec2(p[i], 1, 0));
    }
    cout << mx << endl;
  }

  return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

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

int main(){
    int n,m;cin>>n>>m;
    vi x(m),y(m);
    vector<pair<int,bool>>a(n);
    rep(i,n){
        a[i].F=1;
        a[i].S=false;
    }
    a[0].S=true;
    rep(i,m){
        cin>>x[i]>>y[i];
        a[x[i]-1].F--;
        a[y[i]-1].F++;
        if(a[x[i]-1].S)a[y[i]-1].S=true;
        if(a[x[i]-1].F==0)a[x[i]-1].S=false;
    }
    int cnt=0;
    rep(i,n){
        if(a[i].S)cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 1792
/*
 © 2020-08-15 21:07:12 Franco1010 All Rights Reserved
*/

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
#define deb(x) cout << #x": " << (x) << endl;

int main(){ _
  lli n; cin >> n;
  vector<lli> v(n);
  fore(i, 0, n){
    cin >> v[i];
  }
  sort(all(v));
  // for(auto i : v) cout << i << ' '; cout << ENDL;
  lli res = 0;
  fore(i, 0, n){
    fore(j, i + 1, n){
      if(v[j] != v[i])
      fore(k, j + 1, n){
        if(v[i] != v[k] and v[j] != v[k])
        if(v[i] + v[j] > v[k]){
          // cout << v[i] << ' ' << v[j] << ' ' << v[k] << ENDL;
          res ++;
        }
      }
    }
  }
  cout << res << ENDL;
  return 0;
}


Measured memory_bytes: 3640
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define vi vector<int>
#define all(a) a.begin(),a.end()
typedef pair<int,int> P;
const long long mod=1000000007;
const long long inf=1ll<<61;
int a[85];
signed main(){
    int n;cin>>n;
    rep(i,n)cin>>a[i];
    int nm=1000,nk=0;
    int mode=0;
    rep(i,n){
        if(mode==0){
           if(a[i]<a[i+1]){
               mode=1;
               nk+=nm/a[i];
               nm%=a[i];
           }
        }
        else{
            if(a[i]>a[i+1]){
                mode=0;
                nm+=nk*a[i];
                nk=0;
            }
        }
    }
    cout<<nm<<endl;
}

Measured memory_bytes: 3620
#include <stdio.h>

int main(void)
{
    int h, w, i, j;
    
    scanf("%d %d", &h, &w);
    
    while((h != 0) && (w != 0)) {
        for (i=0; i < h; i++) {
            for (j=0; j<w; j++) {
                printf("#");
            }   
            printf("\n");
        }   
        scanf("%d %d", &h, &w);
        printf("\n");
    }   
    
    return 0;
}   

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

typedef pair<long,int> P;

int par[100010];
int rankd[100010];

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rankd[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }
  else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  
  if(rankd[x] < rankd[y]){
    par[x] = y;
  }
  else{
    par[y] = x;
    if(rankd[x] == rankd[y]) rankd[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}

struct edge{int u,v;long cost;};

bool comp(const edge& e1,const edge& e2){
  return e1.cost < e2.cost;
}

edge es[200020];
int n;

long kruskal(){
  sort(es,es+2*(n-1),comp);
  init(n);
  long res = 0;
  for(int i = 0;i < 2*(n-1);i++){
    edge e = es[i];
    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res += e.cost;
    }
  }
  return res;
}

int main(){
  cin >> n;
  vector<P> x,y;
  for(int i = 0;i < n;i++){
    long a,b;
    cin >> a >> b;
    x.push_back({a,i});
    y.push_back({b,i});  
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  for(int i = 0;i < n-1;i++){
    edge e;
    e.u = x.at(i).second;
    e.v = x.at(i+1).second;
    e.cost = abs(x.at(i).first - x.at(i+1).first);
    es[i] = e;
    e.u = y.at(i).second;
    e.v = y.at(i+1).second;
    e.cost = abs(y.at(i).first - y.at(i+1).first);
    es[i+n-1] = e;
  }
  long ans;
  ans = kruskal();
  cout << ans << endl;
}

Measured memory_bytes: 8036
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
const int MOD = 1e9+7;
#define PI 3.14159265359
typedef long long ll;
using namespace std;



int main(){
	int a, b, c;
	cin >> a >> b >> c;
	int maxi = max(a, max(b, c));
	if (maxi%2 == (a+b+c)%2) cout << (3*maxi - a - b - c)/2 << endl;
	else cout << (3*(maxi+1) - a - b - c)/2 << endl;
	return  0;
}

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

using namespace std ;

#define ll long long

ll a , b [ 3001 ] , c , d , e , cnt ;

int main ()
{
    cin >> a ;
    for ( int i = 1 ; i <= a ; ++ i ){
        cin >> b [ i ] ;
        cnt += b [ i ] ;
    }
    cout << cnt - a ;
    return 0 ;
}
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;

#define Endl endl

/*--------------------template--------------------*/


void ppp(string a,string b,string c)
{
	cout << a << Endl;
	cout << b << Endl;
	cout << c << endl;
	cout << endl;
}


int main()
{
	string a, b, c;
	cin >> a >> b >> c;
	reverse(begin(a), end(a));
	reverse(begin(b), end(b));
	reverse(begin(c), end(c));
	ll flag = 1;
	while (1) {
		if (flag == 1) {
			if (a.size() == 0) {
				s = 'A';
				break;
			}
			flag = a.back() - 'a' + 1;
			a.pop_back();
		} else if (flag == 2) {
			if (b.size() == 0) {
				s = 'B';
				break;
			}
			flag = b.back() - 'a' + 1;
			b.pop_back();
		} else {
			if (c.size() == 0) {
				s = 'C';
				break;
			}
			flag = c.back() - 'a' + 1;
			c.pop_back();
		}
		
	}
	cout << s << Endl;
}

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

int main() {
    ll X, Y;
    cin >> X >> Y;

    ll res = 0;
    while(X<=Y) {
        X *= 2;
        res ++;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(a+b+c>21){
			System.out.println("bust");
		}else{
			System.out.println("win");
		}
	}
}


Measured memory_bytes: 23764
#include <stdio.h>


int main()
{
	int h, m, s;
	int S;

	scanf("%d", &S);
	h = S / 3600;
	S = S % 3600;
	m = S / 60;
	S = S % 60;
	s = S;

	printf("%d:%d:%d\n",h,m,s);
    return 0;
}






Measured memory_bytes: 2108
import java.util.*;

public class Main {

    long INF = Long.MAX_VALUE;
    long[][] dp;

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double[] A = new double[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextDouble();
        }
        double ans =0;
        for (int i = 0; i < N; i++) {
            ans += 1/A[i];
        }
        System.out.println(1/ans);
    }

}


Measured memory_bytes: 23252
#include<stdio.h>
#include<math.h>
int main()
{
int n,i,digit=1,sum=0,save_n;
scanf("%d",&n);
save_n=n;
for(i=0;n/10;i++)
{		
	n=n/10;
	digit++;
}


n=save_n;
for(i=1;i<digit;i=i+2)
{
	sum=sum+9*pow(10,(i-1));
}
if(digit%2==1)
{
	digit=digit-1;
	
	sum=sum+n-pow(10,digit)+1;
}

printf("%d",sum);
return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>

int64_t table[50][5000];

int main()
{
    int n, a;
    std::cin >> n >> a;

    std::vector<int> values;
    values.reserve(n);
    for (int i = 0; i < n; ++i)
    {
        int tmp;
        std::cin >> tmp;
        values.push_back(tmp - a);
    }

    for (int i = 0; i < n; ++i)
    {
        if (i == 0)
        {
            table[i][2500] = 1;
            // value[i]が0の場合がある
            table[i][values[i] + 2500] += 1;
        }
        else
        {
            for (int j = 0; j < 5000; ++j)
            {
                if (j - values[i] < 0 || j - values[i] >= 5000)
                {
                    table[i][j] = table[i - 1][j];
                }
                else
                {
                    table[i][j] = table[i - 1][j] + table[i - 1][j - values[i]];
                }
            }
        }
    }

    std::cout << table[n - 1][2500] - 1 << std::endl;
    return 0;
}


Measured memory_bytes: 2176
package main

import (
	"fmt"
	"math"
)

var N, M int

func main() {
	fmt.Scan(&N, &M)
	x := make(map[int]int)

	for i := 0; i < M; i++ {
		var t1, t2 int
		fmt.Scan(&t1, &t2)
		x[t1]++
		x[t2]++
	}

	for i := 1; i <= N; i++ {
		fmt.Println(x[i])
	}
}

/*  ----------------------------------------  */

func combination(x, y int) int {
	return permutation(x, y) / permutation(y, y)
}

func permutation(x, y int) int {
	var ans int = 1
	for i := x - y; 0 < i; i-- {
		ans *= i
	}
	return ans
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }

type XY struct {
	x int
	y int
}
type SortBy []XY

func (a SortBy) Len() int      { return len(a) }
func (a SortBy) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool {
	if a[i].x == a[j].x {
		return a[i].y > a[j].y
	}
	return a[i].x > a[j].x
}


Measured memory_bytes: 512
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();

		int a = sc.nextInt();
		int b = sc.nextInt();

		Map<String,Integer> map = new HashMap<>();
		map.put(s, a);
		map.put(t, b);

		String u = sc.next();
		map.put(u,map.get(u)-1);

		System.out.println(map.get(s)+ " " + map.get(t));
	}
}

Measured memory_bytes: 23764
#include<iostream>
using namespace std;
int main(){
  int road[55]={0}; //[1]~[n]
  int n,m; cin >> n >> m;
  for(int i=0;i<m;i++){
    int a,b; cin >> a >> b;
    road[a]++;
    road[b]++;
  }
  for(int i=1;i<=n;i++){
    cout << road[i] << endl;
  }
  return 0;
}

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

int n, m, ans, vc;
int G[10][10];
bool used[10];

void dfs(int now){
    used[now] = true;
    vc++;
    if(vc == n){
        ans++;
    }
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
    used[now] = false;
    vc--;
    return;
}

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

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a][b] = true;
        G[b][a] = true;
    }

    dfs(0);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVL vector<vector<ll>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
constexpr ll MOD = 1000000007;
using std::cout;
using std::endl;
using std::cin;
using std::sort;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::multiset;


// ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
// ll pow(ll a, ll b) { ll ans = 1; while (b > 0) { if (b % 2 == 1) { ans *= a; ans %= MOD; }b /= 2; a *= a; a %= MOD; }return ans; }
// ll comb(ll n, ll r) { if (n - r < r) { return comb(n, n - r); }static VVL memo = {{1}}; if (memo.size() < n + 1) { memo.reserve(n + 1); FOR(i, memo.size(), n + 1) { memo.emplace_back(i + 1, 0); REP(j, i + 1) { memo[i][j] = 0;	if (j < i) { memo[i][j] += memo[i - 1][j]; }if (j > 0) { memo[i][j] += memo[i - 1][j - 1]; }memo[i][j] %= MOD; } } }return memo[n][r]; }
// ll comb_L(ll a, ll b) { if (a - b < b) { return comb(a, a - b); }static unordered_map<ll, ll> memo; ll c = 1; FOR(i, a - b + 1, a + 1) { c *= i; c %= MOD; }if (memo.find(b) == memo.end()) { ll k = 1; FOR(i, 2, b + 1) { k *= i;	k %= MOD; }memo[b] = pow(k, MOD - 2); }	c *= memo[b]; return c % MOD; }
// multiset<ll> prime_decomposition(ll n) { ll i = 2; multiset<ll> table{}; while (i * i <= n) { while (n % i == 0) { n /= i;	table.emplace(i); }++i; }if (n > 1) { table.emplace(n); return table; }return table; }
//-- bit -- REP(i, (1 << n)) {REP(j, n) {cout << (1 & (i >> j));}cout << endl;}

//==============================================================================================



int main() {
	ll n, m;
	cin >> n >> m;
	unordered_map<ll, list<ll>> graph;
	unordered_set<ll> from;
	REP(i,m){
		ll a, b;
		cin >> a >> b;
		graph[a].emplace_back(b);
		if (b == n) {
			from.emplace(a);
		}
	}

	REPC(x, graph[1]) {
		if (from.find(x) != from.end()) {
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 16328
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x)
#define rmax(r, x) r = max(r, x)
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 2e5 + 10;
const int maxq = 2e5 + 10;

int n, q;
int a[maxn], b[maxn];

int main(void) {
    fastio;
    cin >> n >> q;
    ll ans = 1LL * (n - 2) * (n - 2);
    int l = n, r = n;
    memset(a, -1, sizeof(a));
    memset(b, -1, sizeof(b));
    while(q--) {
        int t, x;   cin >> t >> x;
        if(t == 1) {
            for(int i = x; i <= n && a[i] == -1; ++i)   a[i] = l - 2;
            ans -= a[x];
            rmin(r, x);
        }
        else {
            for(int i = x; i <= n && b[i] == -1; ++i)   b[i] = r - 2;
            ans -= b[x];
            rmin(l, x);
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 5220
#include<stdio.h>
 
int main(void)
{
int c[51]={0},a,b,n,m,i;

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

for(i=1; i<=m; i++){
scanf("%d %d",&a,&b);
c[a]+=1;
c[b]+=1;
}
for(i=1; i<=n; i++){
printf("%d\n",c[i]);
}

return 0;
}

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

int value(int n){
  if(n < 0)
    n *= -1;
  return n;
}
int main(void){
  int x, a, b;
  int delta_a, delta_b;
  cin >> x >> a >> b;
  delta_a = value(x - a);
  delta_b = value(x - b);
  if(delta_a < delta_b)
    cout << "A" << "\n";
  else
    cout << "B" << "\n";
  return 0;
}


Measured memory_bytes: 3624
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const ll mod = 998244353;
const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int kazu[100001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();

	//解けなかった...ｶﾅｼｲ...
	if (getint() != 0) {
		printf("0");
		return 0;
	}

	int saidai = 0;;
	rep(i, N - 1) {
		int d = getint();
		if (!d) {
			printf("0");
			return 0;
		}
		kazu[d]++;
		chmax(saidai, d);
	}

	ll kotae = 1;
	int mae = 1;
	rep1(i, saidai) {
		rep(j, kazu[i]) kotae = kotae * mae % mod;
		mae = kazu[i];
	}

	printf("%d", kotae);

	Would you please return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple

using namespace std;

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

const int N = 1e5 + 10;

vector<int> G[N];


int main(){	
	int n, m;
	cin >> n >> m;
	string s;
	rep(i, n){
		char c;
		cin >> c;
		s += c;
	}
	rep(i, m){
		int s, t;
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}

	rep(i, n){
		if (s[i] != '?') continue;
		set<char> st;
		for (auto v : G[i]){
			st.insert(s[v]);
		}
		rep(j, 26){
			if (st.count('a' + j)) continue;
			s[i] = 'a' + j;
			break;
		}
	}
	cout << s << endl;

	return 0;
}


Measured memory_bytes: 8096
#include<bits/stdc++.h>
    using namespace std;
    #define maxl 3010
    typedef vector<int> vi;
    vector<vi> pos;
    string s,t,sol;
    int32_t memo[maxl][maxl];
    int td(int i, int j){
      if(i>=s.size() || j>=t.size()) return 0;
      if(memo[i][j]!=-1) return memo[i][j];
      if(pos[(int)s[i]].empty()) return memo[i][j]=td(i+1,j);
      if(lower_bound(pos[(int)s[i]].begin(),pos[(int)s[i]].end(),j)==pos[(int)s[i]].end()) return memo[i][j]=td(i+1,j);
      int k=*lower_bound(pos[(int)s[i]].begin(),pos[(int)s[i]].end(),j);
      if(k!=t.size()) return memo[i][j]=max(td(i+1,j),1+td(i+1,k+1));
      return memo[i][j]=td(i+1,j);
    }
    void backtrack(int i, int j){
      if(i>=s.size() || j>=t.size()) return;
      if(pos[(int)s[i]].empty() || lower_bound(pos[(int)s[i]].begin(),pos[(int)s[i]].end(),j)==pos[(int)s[i]].end()) {
        backtrack(i+1,j);
        return;}
      int k=*lower_bound(pos[(int)s[i]].begin(),pos[(int)s[i]].end(),j);
      if(k!=t.size()) {
        if(memo[i+1][j]>1+memo[i+1][k+1])
          backtrack(i+1,j);
        else{
          sol+=s[i];
          backtrack(i+1,k+1);
        }
        return;
      }
      backtrack(i+1,j);
      return;
    }
    int main(){
      //cout<<(int)'a'<<endl;
      pos.assign(130,vi());
      cin>>s>>t;
      for (size_t i = 0; i < t.size(); i++) {
        pos[(int)t[i]].push_back(i);
      }
      for (size_t i = 0; i <= s.size(); i++) {
        for (size_t j = 0; j <= t.size(); j++) {
          memo[i][j]=-1;
        }
      }
      td(0,0);
      backtrack(0,0);
      cout<<sol<<'\n';
      return 0;
    }

Measured memory_bytes: 39108
fn main() {
	let mut s = String::new();
	std::io::stdin().read_line(&mut s).unwrap();
	let s = s.trim();
	let x: i64 = s.parse().unwrap();
	let mut l = 1;
	let mut r = 1e16 as i64;
	while r - l > 1 {
		let m = l + (r - l) / 2;
		if cnt(m) > x {
			r = m;
		} else {
			l = m;
		}
	}
	println!("{}", l);
}

fn cnt(n: i64) -> i64 {
	let mut r = 0;
	let mut n = n;
	while n > 2 {
		n = (n - 1) / 2;
		r += 1;
	}
	r
}


Measured memory_bytes: 2140
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

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

	vector<string> a(n);

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


	LL cnta = 0;
	LL cntb = 0;
	LL cntc = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < a[i].size()-1; j++) {
			if (a[i][j] == 'A' && a[i][j + 1] == 'B')ans++;
		}

		if (a[i][a[i].size() - 1] == 'A' && a[i][0] == 'B')cntc++;
		else if (a[i][a[i].size() - 1] == 'A')cnta++;
		else if (a[i][0] == 'B')cntb++;
	}

	if (cntc >= 2) {
		ans = ans + (cntc - 1);
	}

	if (cntc > 0) {
		if (cnta > 0) {
			ans++;
			cnta--;
		}

		if (cntb > 0) {
			ans++;
			cntb--;
		}
	}

	ans += min(cnta, cntb);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 768
#include<stdio.h>

double hirei(double x1,double y1,double x2,double y2);

main(){
  int n,i;

  scanf("%d",&n);

  for(i=0;i<n;i++){
  double x1,x2,x3,x4,y1,y2,y3,y4;
  double g1,g2;


    scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);

    g1=hirei(x1,y1,x2,y2);
    g2=hirei(x3,y3,x4,y4);

    if(g1==g2){
      printf("YES");
    }
    else{
      printf("NO");
    }
    puts("");
  }

  return 0;
}

double hirei(double x1,double y1,double x2,double y2){
  double a;

  a=(y1-y2)/(x1-x2);

  return(a);
}

Measured memory_bytes: 0
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
double r[601];
double dist[601];
int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lf",&r[i]);
	}
	dist[0]=r[0];
	for(int i=1;i<n;i++){
		dist[i]=r[i];
		for(int j=0;j<i;j++){
			dist[i]=max(dist[i],dist[j]+sqrt(4.0*r[i]*r[j]));
		}
	}
	double res=0;
	for(int i=0;i<n;i++){
		res=max(res,dist[i]+r[i]);
	}
	printf("%.10f\n",res);
	return 0;
}

Measured memory_bytes: 2756
#require 'prime'
MOD=10**9+7;  cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.chomp.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def ar2(s1,s2,de=nil) Array.new(s1){Array.new(s2,de)} end
def ar3(s1,s2,s3,de=nil) Array.new(s1){Array.new(s2){Array.new(s3,de)}} end

def desc(ar) ar.sort!{|x,y| y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end
def ceil(a,b) (a.to_f/b).ceil end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end
def rui(ar) s=[0]; ar.size.times{|i| s<<s[-1]+ar[i]}; s end
def rev_rui(ar) s=[0]; ar.size.times.reverse_each{|i| s<<s[-1]+ar[i]}; s end

def puts_yesno(b) puts(b ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def pu(h) begin; require './../nemi_lib/debug.rb'; puts_val(h); rescue LoadError; end; end
########### ( ˘ω˘ )ｽﾔｧ… ###########
s=gs
n=s.length
s2=s[0..((n-1)/2-1)]
s3=s[((n+3)/2-1)..(n-1)]
b= s==s.reverse&&s2==s2.reverse&&s3==s3.reverse
puts_yesno(b)

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{   
    fast;
    lli n;
    cin>>n;
    lli sum=0;
    int count=1;
    vector<char> v;
    while(n!=0)
    {
        if(n%26==0)
        {
            v.push_back('z');
            n=n-1;
        }
        else
        {
            v.push_back((char)(96+n%26));
        }
        n=n/26;
    }
    reverse(v.begin(),v.end());
    for(auto x:v)
    {
        cout<<x;
    }
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// #define int long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = (((1<<30)-1)<<1)+1;
const int nINF = 1<<31;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

/////////////////////////////////////////////////////////////////////

const int N = 3010;
int n, a[N];
ll dp[N][N]; //dp[i][j] - best value of X-Y for segments i..j

ll rec(int l, int r) {return l > r ? 0 : (dp[l][r] != -1 ? dp[l][r] : dp[l][r] = max(a[l]-rec(l+1, r), a[r]-rec(l, r-1)));}

signed main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    memset(dp, -1, sizeof(dp));
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    cout << rec(1, n) << endl;

    return 0;
}

// Easy things to check:
// - LONG LONGS (WA)
// - const int N is correct (WA, RTE)
// - .size()-k underflow (WA, RTE, TLE)
// - small n edge cases (WA)

// Rare mistakes made in the past:
// - division by 0 (WA)
// - integer division (WA)
// - setprecision (WA)
// - INF not big enough using ll (WA)
// - setting min to 0 instead of -INF (WA)
// - outputting debug (WA)
// - allocating too much memory (locRTE, MLE)
// - stack size (locRTE)


Measured memory_bytes: 71296
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int rectangle = 0;
		int lozenge = 0;
		while(sc.hasNext()) {
			String[] sarr = sc.next().split(",");
			int[] x = new int[3];
			for(int i=0;i<3;i++) {
				x[i] = Integer.valueOf(sarr[i]);
			}
			if (x[0] * x[0] + x[1] * x[1] == x[2] * x[2]) {
				rectangle++;
			}
			if (x[0] == x[1]) {
				lozenge++;
			}
		}
		System.out.println(rectangle);
		System.out.println(lozenge);
	}
	
}

Measured memory_bytes: 17132