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

using namespace std;
vector<long long> factors;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
ll maxs = 200000+10;
vector<ll> a(maxs);
vector<ll> t(maxs*4);
ll build(ll v,ll vl,ll vr){
	if(vl == vr){
		t[v] = a[vl];
		return t[v];
	}
	else{
		ll m = vl + (vr - vl)/2;
		t[v] = max(build(v*2 + 1,vl,m) ,build(v*2 + 2,m+1,vr));
		return t[v];
	}
}

ll que(ll v, ll vl,ll vr,ll l, ll r){
	if(l<=vl && vr <= r){
		return t[v];
	}else if(r < vl || vr < l){
		return -1;
	}
	ll m = vl + (vr - vl)/2;
	return max(que(2*v + 1,vl,m,l,r),que(2*v + 2,m + 1,vr,l,r));
}

void mod(ll v,ll vl,ll vr,ll val,ll point){
	ll m = vl + (vr - vl)/2;
	if(vl == vr){
		t[v] = val;
	}
	else if(point <= m){
		mod(2*v+1,vl,m,val,point);
		t[v] = max(t[2*v+1],t[2*v+ 2]);
	} else{
		mod(2*v+2,m+1,vr,val,point);
		t[v] = max(t[2*v+1],t[2*v+ 2]);
	}
}


int main()
{
	IOS
	ll n;
	cin >> n;
	vector<pll > flowers(n);
	for (ll i = 0; i < n; ++i)
		cin >> flowers[i].first;
	for (ll i = 0; i < n; ++i)
	{
		cin >> flowers[i].second;
	}
	for(ll i = 0;i < maxs; ++i){
		a[i] = 0;
	}
	build(0,0,n +1);
	for(ll i = 0; i < n;++i){
		ll temp = que(0,0,n,0,flowers[i].first);
		mod(0,0,n,flowers[i].second + temp,flowers[i].first);
	}
	cout << que(0,0,n,0,n);
	return 0;
}


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

int main(){
  int N;
  cin>>N;
  vector<int> num(N);
  for(int i=0;i<N;i++){
    cin>>num.at(i);
  }
  for (int i=1;i<=N;i++){
     for (int x=0;x<N;x++){
      if(x==N-1){
        cout<<num[N-1]<<endl;
        break;
      }
      cout<<num[x]<<" ";
    }
    int v =num[i];
    int j= i-1;
    while(j>=0 && num[j]>v){
      num[j+1] = num[j];
      j--;
    }
    num[j+1]=v;
  }
}


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

int main(){
  int n;
  cin >> n;
  
  vector<int> vec(n);
  
  for(int i=0; i<n; i++){
    cin >> vec.at(i);
  }
  
  for(int i=1; i<n; i++){
    int v = vec.at(i);
    int j = i-1;
    while(j >= 0 && vec.at(j) > v){
      vec.at(j+1) = vec.at(j);
      j--;
    }
    vec.at(j+1) = v;
  }
  
  int count = 0;
  for(int i=0; i<n; i++){
    if(i == 0){
      count += 1;
    }else if(vec.at(i) > vec.at(i-1)){
      count += 1;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i <(n); i++)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using p = pair<int,int>;

int main(){
  int data[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin >> n;
  cout << data[n-1] << endl;
  return 0;
}

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

Measured memory_bytes: 256
if __name__ == '__main__':
    d, g = map(int, input().split())
    p = []
    c = []
    for _ in range(d):
        p_i, c_i = map(int, input().split())
        p.append(p_i)
        c.append(c_i)

    # d = 2
    # g = 700
    # p = [3, 5]
    # c = [500, 800]

    # d = 5
    # g = 25000
    # p = [20, 40, 50, 30, 1]
    # c = [1000, 1000, 1000, 1000, 1000]

    ans = 10 * 100
    for bit in range(1 << d):
        sum_score = 0
        n_solved = 0
        # 1つも全完しないケースもこのfor文に含まれる
        for i in range(d):
            if bit & (1 << i) != 0:
                sum_score += c[i] + 100 * p[i] * (i + 1)
                n_solved += p[i]

        if g <= sum_score:
            ans = min(ans, n_solved)
            continue

        for i in range(d - 1, -1, -1):
            # already solved
            if bit & (1 << i) != 0:
                continue

            for j in range(p[i]):
                if g <= sum_score:
                    break
                sum_score += 100 * (i + 1)
                n_solved += 1

        ans = min(ans, n_solved)

    print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>

using namespace std;

int main()
{
    int a,b,c;
    int x,y;
    cin >> a >> b >> c >> x >> y;
    long long ans = a*x + b*y;
    
    for (int i = 2;i <= 2*max(x,y);i+=2){
        long long m;
        if (i/2 <= x && i/2 <= y){
            m = i*c + (x - i/2)*a + (y-i/2)*b;
        }
        else if (i/2 <= x && i/2 > y){
            m = i*c + (x-i/2)*a;
        }
        else if (i/2 > x && i/2 <= y){
            m = i*c + (y-i/2)*b;
        }
        else {
            m = i*c;
        }
        ans = min(ans,m);
    }
    
    cout << ans << endl;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,ans=0;cin>>n;vector<double> a(n,0.0);
  double ave=0.0;
  rep(i,n) {cin>>a[i];ave+=a[i];}
  ave/=n;
  rep(i,n) a[i]=abs(a[i]-ave);
  ans=min_element(a.begin(),a.end())-a.begin();
  print(ans); 
  return 0;
}


Measured memory_bytes: 256
/*
 * Author       : YangDavid
 * Created Time : 2019年11月23日 星期六 20时14分20秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 333;
int h, w, k, belong[maxn][maxn], row[maxn];
char s[maxn][maxn];
int main() {
	int cnt = 0;
	scanf("%d%d%d", &h, &w, &k);
	rep(i, h) {
		scanf("%s", s[i] + 1);
		rep(j, w) if(s[i][j] == '#')
			belong[i][j] = ++cnt;
	}
	for(int r = h-1; r > 0; --r) {
		for(int c = 1; c <= w; ++c) {
			if(!belong[r][c]) 
				belong[r][c] = belong[r+1][c];
		}
	}
	for(int r = 2; r <= h; ++r) {
		for(int c = 1; c <= w; ++c) {
			if(!belong[r][c]) 
				belong[r][c] = belong[r-1][c];
		}
	}
	for(int c = 2; c <= w; ++c)
		for(int r = 1; r <= h; ++r)
			if(!belong[r][c])
				belong[r][c] = belong[r][c-1];
	for(int c = w-1; c > 0; --c)
		for(int r = 1; r <= h; ++r)
			if(!belong[r][c])
				belong[r][c] = belong[r][c+1];
	rep(i, h) rep(j, w) printf("%d%c", belong[i][j], " \n"[j == w]);

    return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    int n;
    cin >> n;
    vector<int> a(100001, 0);

    rep(i, n)
    {
        int c;
        cin >> c;
        if (c == 0 || c == 1e5)
            a[c]++;
        else
        {
            a[c]++;
            a[c + 1]++;
            a[c - 1]++;
        }
    }
    OP(*max_element(ALL(a)));
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007

using namespace std;
long long H, W;

int main(){
	cin >> H >> W;
	int posx;
	int posy;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			string tmp;
			cin >> tmp;
			if(tmp == "snuke"){
				posx = j;
				posy = i;
			}
		}
	}
	cout << (char)('A'+posx) << posy+1 << endl;




}

Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;
using edge= struct{int to;ll cost;};


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
using Graph =vector<vector<int>>;
//xor ^
int main(){
  int N;cin>>N;
  ll ans=0;
   REP(i,N){
     ll tmp;
     cin>>tmp;
     ans ^=tmp;
   }
   if(!ans){
     cout<<"Yes"<<endl;
   }else{
     cout<<"No"<<endl;
   }
}

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

int main() {
  float n;
  float count=0;
  float ans;

  cin >> n ;

  for (int i=1;i<=n;i++){
    if(i%2!=0) count++;
  }
  ans=count/n;

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>

int main()
{
   int nHat;
   std::cin >> nHat;
   std::map<long long, int> num;
   long long tmp;
   for (int iHat = 0; iHat < nHat; iHat++) {
      std::cin >> tmp;
      num[tmp]++;
   }

   bool isSuccessful;
   if (num.size() > 3) {
      isSuccessful = false;
   } else if (num.size() == 1) {
      auto itr = num.begin();
      if (!itr->first) {
         isSuccessful = true;
      } else {
         isSuccessful = false;
      }
   } else if (nHat%3) {
      isSuccessful = false;
   } else if (num.size() == 2) {
      auto itr = num.begin();
      long long key1 = itr->first;
      itr++;
      long long key2 = itr->first;
      if (!key1 && 2 * num[key1] == num[key2]) {
         isSuccessful = true;
      } else {
         isSuccessful = false;
      }
   } else {
      auto itr = num.begin();
      long long key[3];
      for (int iKey = 0; iKey < 3; iKey++) {
         key[iKey] = itr->first;
         itr++;
      }
      if ((num[key[0]] == num[key[1]]) && num[key[1]] == num[key[2]]) {
         if ((key[0] ^ key[1]) == key[2]) {
            isSuccessful = true;
         }
      } else {
         isSuccessful = false;
      }
   }

   std::cout << (isSuccessful ? "Yes" : "No") << std::endl;
}


Measured memory_bytes: 5120
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

template <typename T>//	Tはintかll
T gcd(T a, T b) {//	最大公約数
	if (a < 0) { a = -a; }
	if (b < 0) { b = -b; }
	if (a == 0) { return b; }
	if (b == 0) { return a; }
	if (a < b) {
		return gcd(a, b % a);
	}
	return gcd(b, a % b);
}

int main() {
	ll N, M; cin >> N >> M;
	vector<ll> v;
	for (int i = 0; i < N; i++) {
		ll x; cin >> x; v.push_back(x / 2);
	}
	ll L = 1;
	for (int i = 0; i < N; i++) {
		ll g = gcd(L, v[i]);
		if (L * v[i] > M * g) {
			cout << 0 << endl;
			return 0;
		}
		L *= v[i] / g;
	}
	for (int i = 0; i < N; i++) {
		if ((L / v[i]) % 2 == 0) {
			cout << 0 << endl;
			return 0;
		}
	}
	cout << ((ll)(M / L)+1)/2 << endl;
	return 0;
}

Measured memory_bytes: 1400
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int l;
vector<p> G[20];
void add_edge(int u, int v, ll c)
{
    G[u].push_back(make_pair(v, c));
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> l;
    int dight;
    ll sum = 0;
    ll sub;
    ll pow1[21];
    for (int i = 0; i <= 20; i++)
    {
        ll c = pow(2, i);
        pow1[i] = c;
    }
    int n;
    for (int i = 0; i <= 20; i++)
    {
        if (l - 1 >= 2 * pow1[i] - 1)
        {
            add_edge(i, i + 1, pow1[i]);
            add_edge(i, i + 1, 0);
        }
        else
        {
            dight = i - 1;
            n = i;
            break;
        }
    }

    while (dight >= 0)
    {
        if (dight == 0)
        {
            {
                if (l - 1 > 2 * pow1[n - 1] - 1)
                    add_edge(dight, n, l - 1);
            }
        }
        else if (l - 1 - 2 * pow1[dight - 1] + 1 > 2 * pow1[n - 1] - 1)
        {
            add_edge(dight, n, l - 2 * pow1[dight - 1]);
            l -= 2 * pow1[dight - 1];
        }
        dight--;
    }
    ll sizeg = 0;
    for (int i = 0; i < n; i++)
    {
        sizeg += G[i].size();
    }
    cout << n + 1 << " " << sizeg << "\n";
    for (int i = 0; i < n; i++)
    {
        for (auto pa : G[i])
        {
            cout << i + 1 << " " << pa.first + 1 << " "
                 << pa.second << "\n";
        }
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    s+=" ";
    int m=0,cnt=0;
    for(int i=0;i<(int)s.size();i++)
    {
        if(s[i]=='A'||s[i]=='T'||s[i]=='C'||s[i]=='G') cnt++;
        else
        {
            m=max(m,cnt);
            cnt=0;
        }
    }
    cout << m << endl;
    return 0;
}


Measured memory_bytes: 256
require 'set'

def article_point(n)
  $timer = 1

  dfs(0)

  # puts "prenum: #{$prenum}, lowest: #{$lowest}, parent: #{$parent}"

  ap = Set.new
  root_num = 0
  n.times do |i|
    p = $parent[i]
    if p == -1
      next
    end
    # puts "i: #{i}, p: #{p}, $prenum[p]: #{$prenum[p]}, $lowest[i]: #{$lowest[i]}"
    if p.zero?
      root_num += 1
    elsif $prenum[p] <= $lowest[i]
      ap << p
    end
  end
  if root_num > 1
    ap << 0
  end
  ap = ap.sort
  ap.each do |i|
    puts i
  end

  
end

# stack level too deep (SystemStackError)
# def dfs(current, prev)
#   $visits[current] = true
#   $prenum[current] = $timer
#   $lowest[current] = $timer
#   $timer += 1
#   # puts "current : #{current}, prev : #{prev}, prenum: #{$prenum}, lowest: #{$lowest}"

#   for next_node in $g[current]
#     # puts "next : #{next_node}, visited? : #{$visits[next_node]}"
#     if !$visits[next_node]
#       $parent[next_node] = current
#       dfs(next_node, current)
#       $lowest[current] = [$lowest[current], $lowest[next_node]].min
#     elsif next_node != prev
#       $lowest[current] = [$lowest[current], $prenum[next_node]].min
#     end
#   end
# end

def dfs(current)
  $visits[current] = true
  $prenum[current] = $timer
  $lowest[current] = $timer
  $timer += 1
  # puts "current : #{current}, prev : #{prev}, prenum: #{$prenum}, lowest: #{$lowest}"

  stack = []
  stack << current

  while !stack.empty? do
    n = stack[-1]
    found = false

    # puts "n: #{n}, prenum: #{$prenum}, lowest: #{$lowest}, parent: #{$parent}"

    for next_node in $g[n]
      # puts "next : #{next_node}, visited? : #{$visits[next_node]}"
      if !$visits[next_node]
        $parent[next_node] = n
        
        # dfs(next_node, current)
        $visits[next_node] = true
        $prenum[next_node] = $timer
        $lowest[next_node] = $timer
        $timer += 1

        stack << next_node

        $lowest[n] = [$lowest[n], $lowest[next_node]].min
        found = true
        break
      elsif next_node != $parent[n]
        $lowest[n] = [$lowest[n], $prenum[next_node]].min
      end
    end
    unless found
      stack.pop
      for next_node in $g[n]
        if next_node == stack[-1]
          next
        end
        # puts "n: #{n}, next: #{next_node}, $lowest[n]: #{$lowest[n]}, $lowest[next]: #{$lowest[next_node]}"
        $lowest[n] = [$lowest[n], $lowest[next_node]].min
      end
    end
  end
end

v, e = gets.split.map(&:to_i)
$g = Array.new(v) {[]}
e.times do
  s, t = gets.split.map(&:to_i)
  $g[s] << t
  $g[t] << s
end
# puts 
# v.times do |i|
#   puts "NO.#{i}"
#   puts $g[i].join(' ')
# end
$prenum = Array.new(v)
$lowest = Array.new(v)
$parent = Array.new(v, -1)
$visits = Array.new(v, false)
article_point(v)


Measured memory_bytes: 9504
#include <bits/stdc++.h>
using namespace std;
int main() {
 
double a,b,c,d,e;
   cin >> a >>b;
 e =0;
 for(int i=1;i<=a;i++){
    c = i,d = 1/a;
   for(int j=0;j<20;j++){
     
   if(c>=b){
      e += d;
     break;
   }
    d /= 2;
    c *= 2;
   }
 }
   printf("%.10lf\n", e);
}

Measured memory_bytes: 256
from itertools import accumulate
from collections import defaultdict

N = int(input())
A = [0] + list(map(int, input().split()))
cum = list(accumulate(A))
count = defaultdict(int)
ans = 0
for i in range(N+1):
    ans += count[cum[i]]
    count[cum[i]] += 1
print(ans)


Measured memory_bytes: 113284
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>
#include <random>
#include <time.h>
#include <stack>
using namespace std;
const int N = 2e3 + 10;
const int inf = 1e18 + 5;
const int mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(false)
int n;
int dp1[N], dp2[N];
int val[N];
int cur = 0;
int main(){
    cin >> n >> val[0] >> val[1];
    for(int i = 2; i <= n + 1; ++i){
        cin >> val[i];
    }
    cur = val[n + 1];
    for(int i = n; i >= 1; --i){
        dp1[i] = dp2[i] = abs(cur - val[i]);
        for(int j = i + 1; j <= n; ++j){
            dp1[i] = min(dp2[j], dp1[i]);
            dp2[i] = max(dp1[j], dp2[i]);
        }
    }
    cout << dp2[1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;


int main(){
    string s1,s2,s3; cin >> s1 >> s2 >> s3;
    vector<int> index(3, 0);
    int s = 0;
    while(1){
        if(index[0] > s1.length()){
            cout << 'A' << endl;
            return 0;
        }else if(index[1] > s2.length()){
            cout << 'B' << endl;
            return 0;
        }else if(index[2] > s3.length()){
            cout << 'C' << endl;
            return 0;
        }
        if(s == 0){
            s = s1[index[0]] -'a';
            index[0]++;
        }else if(s == 1){
            s= s2[index[1]] - 'a';
            index[1]++;
        }else{
            s = s3[index[2]] - 'a';
            index[2]++;
        }
        
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
int main() {
	int n, a[100010], ans = 1;
	cin >> n >> a[0];
	for (int i = 1; i < n; i++)cin >> a[i];
	int f = 1;
	if (a[0] < a[1])f = 2;
	if (a[0] > a[1])f = 0;
	for (int i = 1; i < n - 1; i++) {
		if (f==2&&a[i] > a[i + 1]) {
			ans++;
			f = 1;
			i++;
		}
		else if (f==0&&a[i] < a[i + 1]) {
			ans++;
			f = 1;
			i++;
		}
		if (a[i] < a[i + 1])f = 2;
		if (a[i] > a[i + 1])f = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
int inf=1000001000;
ll INF=100000000000000000;

int par[200000];
int rrank[200000];
void init(int n){
for (int i=0;i<n;i++){
par[i]=i;
rrank[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 (rrank[x]<rrank[y]) par[x]=y;
else {par[y]=x;
if (rrank[x]==rrank[y]) rrank[x]++;}}
bool same(int x,int y){
return find(x)==find(y);}

int main() {
  int n,m;
  cin >> n >> m;
  if (m%2==1){
      cout << -1 << endl;
      return 0;
  }
  init(n+1);
  vector<vector<int>> e(n+1,vector<int>(0));
  vector<int> p(n+1,0),y(n+1,0);
  vector<pp> w;
  rep(i,m){
      int f,g;
      cin >> f >> g;
      if (same(f,g)) {
          w.push_back(mk(f,g));
          p[f]++;
          continue;
      }
      unite(f,g);
      y[f]++;
      y[g]++;
      e[f].push_back(g);
      e[g].push_back(f);
  }
  queue<int> q;
  rep(i,n){
      if(y[i+1]==1) q.push(i+1);
  }
  while(!q.empty()){
      int f=q.front();
      q.pop();
      y[f]--;
      rep(i,e[f].size()){
          int g=e[f][i];
          if (y[g]!=0){
              if (p[f]%2==0){
                  w.push_back(mk(g,f));
                  p[g]++;
              }
              else w.push_back(mk(f,g));
              y[g]--;
              if (y[g]==1) q.push(g);
          }
      }
  }
  rep(i,m){
      cout << w[i].first << " " << w[i].second << endl;
  }
}


Measured memory_bytes: 9592
a,b,c,x = 4.times.map{gets.to_i}

def coin_count(a,b,c,x)
    count = 0
    (0..a).each do |i|
        (0..b).each do |j|
            (0..c).each do |k|
                count += 1 if i * 500 + j * 100 + k * 50 == x
            end
        end
    end
    count
end

print coin_count(a,b,c,x)

Measured memory_bytes: 1916
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

vector<int> sft;
int digit;

void dfs(int s, int count) {
  if (count > digit) return;
  int cpy = s;
  sft.pb(cpy);
  dfs(cpy + pow(10,count) * 3, count+1);
  dfs(cpy + pow(10,count) * 5, count+1);
  dfs(cpy + pow(10,count) * 7, count+1);
  return;
}

int main() {
  int n,cpy,res = 0; cin >> n;
  cpy = n;
  while (cpy > 0) {
    digit++;
    cpy /= 10;
  }

  dfs(3,1);
  dfs(5,1);
  dfs(7,1);

  sorti(sft);
  for (auto itr : sft) {
    bool s,f,t; s = f = t = false;
    if (itr > n) break;
    int cpy = itr;
    while (cpy > 0) {
      int dig = cpy % 10;
      if (dig == 3) t = true;
      if (dig == 5) f = true;
      if (dig == 7) s = true;
      cpy /= 10;
    }
    if (s and t and f) res++;
  }

  cout << res << endl;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int length = scanner.nextInt();
		length = Math.max(length, scanner.nextInt());
		int N = scanner.nextInt();
		scanner.close();
		System.out.println((N - 1) / length + 1);

	}

}


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

int main(){
  int mn,o[101][101],d[101],f[101]={},i,j,n,k,a,b,e;
  while(1){   
    cin>>n>>k;
    if(n==0&&k==0)break;
    bool s;
    for(i=0;i<=n;i++)
      for(j=0;j<=n;j++)o[i][j]=1000000000;
    for(i=0;i<k;i++){
      cin>>s;
     
      if(s==0){
	for(j=0;j<=n;j++){
	  d[j]=1000000000;
	  f[j]=0;
	}
	cin>>a>>b;
	d[a]=0;	
	f[a]=1;
	while(1){
	  for(j=1;j<=n;j++){
	    d[j]=min(o[a][j]+d[a],d[j]);
	  }
	  if(a==b)break;
	  f[a]=1;
	  mn=1000000000;
	  for(j=1;j<=n;j++){
	    if(d[j]<mn&&f[j]==0){
	      mn=d[j];
	      a=j;
	    }
	  }
	  if(mn==1000000000)break;
	 
	}
	if(mn==1000000000)cout<<-1<<endl;
	else cout<<d[b]<<endl;
      }
      
      else{
	cin>>a>>b>>e;
	if(o[a][b]>e){
	o[a][b]=e;
	o[b][a]=e;
	}
      }
    }
  }
  return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

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

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    ll mi = (1ll << 60);
    REP(x, N){
        ll m = A[x];
        vector<ll> tmp;
        REP(i, N){
            priority_queue<ll, vector<ll>, greater<ll>> qu;
            if(A[i] < m) continue;
            int j = i;
            while(A[j] >= m && j < N){
                qu.push(A[j]);
                j++;
            }
            if(j-i >= K){
                REP(k, j-i-K+1){
                    ll val = qu.top();
                    qu.pop();
                    tmp.push_back(val);
                }
            }
            i = j-1;
        }
        sort(tmp.begin(), tmp.end());
        if(tmp.size() >= Q){
            mi = min(mi, tmp[Q-1]-m);
        }
    }
    cout << mi << endl;
    return 0;
}

Measured memory_bytes: 384
require 'set'; require 'prime'; require 'pp'
INF=Float::INFINITY; MOD=10**9+7
n,k = gets.chomp.split.map(&:to_i)
a = gets.chomp.split.map(&:to_i)


k.times do |i|
  imos = Array.new(n, 0)
  n.times do |j|
    aj = a[j]
    l = [j - aj, 0].max
    r = [j + aj + 1, n].min
    imos[l] += 1
    imos[r] -= 1 if r < n
  end

  current = 0
  n.times do |j|
    current += imos[j]
    a[j] = current
  end

  break if a[0] == n && a[-1] == n && a.all?{|e| e == n}
end

puts a.join(' ')



Measured memory_bytes: 77816
# -*- coding: utf-8 -*-

N = input()
K = int(len(N))
A = 0

if K % 2 == 0:
	for i in range(0,K,2):
		A += 9 * 10 ** i
elif K == 1:
	A = N
else:
	for i in range(0,K - 1,2):
		A += 9 * 10 ** i

if K % 2 != 0 and K != 1:
	A += int(N) - 10**(K - 1) + 1

print(A)

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

//vector <long long> v;

stack <char> s;

long long int  x[1000000], y, pot[30], czy=0, w, n, m;
//char s;

int main()
{
    long long int a, b, c, d, k, i, j, q, t, p;

//    q=1;
//    scanf("%lld", &q);
//    for(t=0; t<q; t++)
    {
        scanf("%lld", &n);

        w=0;

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

        scanf("%lld", &n);

        for(i=0; i<n; i++)
        {
            scanf("%lld%lld", &a, &b);
            w=w-a*x[a]+b*x[a];
            x[b]+=x[a];
            x[a]=0;
            printf("%lld\n", w);
        }
    }

    return(0);
}


Measured memory_bytes: 4540
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
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;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






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


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n , a, b ;
  cin >> n >> a >> b ;
  if((b-a)%2==0){
    cout <<(b-a)/2 <<endl ;
  }
  else{
    cout << min(a-1,n-b) + 1 + (b-a-1)/2 <<endl ;
  }
  
  
  
  
  return 0 ;
}



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

using namespace std;

#define F first
#define S second
#define modulo ll (1e9 + 7)

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

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}

const int N = 2e5 + 9, M = 1e6, OO = 0x3f3f3f3f;
const ll llOO = 0x3f3f3f3f3f3f3f3f;

int n;

struct DSU{
    int parent[N], sz[N];
    int components, mxcomponent;
    DSU(){
        iota(parent, parent + n, 0);
        fill(sz, sz + n, 1);
        components = n;
        mxcomponent = 1;
    }

    int find(int u){
        return (parent[u] == u) ? u : parent[u] = find(parent[u]);
    }

    void join(int u, int v){
        u = find(u);
        v = find(v);

        if(u == v)  return;

        if(sz[u] > sz[v])   swap(u ,v);

        parent[u] = v;
        sz[v] += sz[u];

        components--;
        mxcomponent = max(mxcomponent, sz[v]);
    }


    bool isInSameGroup(int u, int v){
        return find(u) == find(v);
    }

    int getSize(int u){
        return sz[find(u)];
    }
};

int k, l, u, v;

int main(){
    init();

    cin >> n >> k >> l;

    DSU roads, railways;
    for(int i = 0;i < k;i++){
        cin >> u >> v;  u--, v--;
        roads.join(u, v);
    }

    for(int i = 0;i < l;i++){
        cin >> u >> v; u--, v--;
        railways.join(u, v);
    }

    map<pii, int> roots;
    for(int i = 0;i < n;i++){
        int u = roads.find(i);
        int v = railways.find(i);
        roots[{u, v}]++;
    }

    for(int i = 0;i < n;i++){
        int u = roads.find(i);
        int v = railways.find(i);
        cout << roots[{u, v}] << " ";
    }

}


Measured memory_bytes: 15104
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	Int N, K;
	cin >> N >> K;
	vector<int> A(N);
	vector<vector<int>> Ax(200010);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		Ax[A[i]].emplace_back(i);
	}

	vector<int> nxt(N);
	for (int i = 0; i < N; ++i) {
		auto V = Ax[A[i]];
		int idx = upper_bound(V.begin(), V.end(), i) - V.begin();
		nxt[i] = (idx == V.size() ? V[0] : V[idx]);
	}

	Int cnt = 1;
	int now = 0;
	while (nxt[now] != N - 1) {
		if (now >= nxt[now]) { ++cnt; }
		now = nxt[now] + 1;
	}
	if (now == N - 1) { ++cnt; }

	K %= cnt;
	now = 0;
	while (K > 1) {
		if (now >= nxt[now]) { --K; }
		now = (nxt[now] + 1) % N;
	}

	vector<int> ans;
	while (now < N) {
		if (now < nxt[now]) {
			now = nxt[now] + 1;
		} else {
			ans.emplace_back(A[now]);
			now += 1;
		}
	}
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << (i < ans.size() - 1 ? " " : "\n");
	}

	return 0;
}


Measured memory_bytes: 16744
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>


using namespace std;
const int MOD = 1000000009; // check!!!
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)

const int MAX_H = 10;
const int MAX_W = 10;

int n;
int a[MAX_H][MAX_W];
struct P{
	int w,h,c;
	P(){}
	P(int w,int h,int c) : w(w),h(h),c(c) {}
};

P ans[12];
vector<int> dw[3],dh[3];
int dw_min[] = {-1,0,-2};
int dw_max[] = {1,2,2};
int dw_md[] = {0,1,0};
int dh_min[] = {0,0,0};
int dh_max[] = {2,2,4};
int dh_md[] = {1,1,2};

void init(){
	static int dx1[] = {0,-1,0,1,0};
	static int dy1[] = {0,1,1,1,2};
	static int dx2[] = {0,1,2,0,1,2,0,1,2};
	static int dy2[] = {0,0,0,1,1,1,2,2,2};
	static int dx3[] = {0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
	static int dy3[] = {0,1,1,1,2,2,2,2,2,3,3,3,4};

	FOR(i,5) dw[0].push_back(dx1[i]), dh[0].push_back(dy1[i]);
	FOR(i,9) dw[1].push_back(dx2[i]), dh[1].push_back(dy2[i]);
	FOR(i,13) dw[2].push_back(dx3[i]), dh[2].push_back(dy3[i]);
}

bool vaild(int x,int h,int w){
	if(0 <= w + dw_min[x] && w + dw_max[x] < MAX_W &&
	   0 <= h + dh_min[x] && h + dh_max[x] < MAX_H){
		FOR(i,sz(dw[x])){
			if(a[h + dh[x][i]][w + dw[x][i]] == 0)
				return false;
		}
		return true;
	} else {
		return false;
	}
}

void erase(int x,int h,int w){
	FOR(i,sz(dw[x])) a[h + dh[x][i]][w + dw[x][i]]--;
}

void redraw(int x,int h,int w){
	FOR(i,sz(dw[x])) a[h + dh[x][i]][w + dw[x][i]]++;
}

inline void hw_next(int &h,int &w){
	while(h < MAX_H){
		while(w < MAX_W){
			if(a[h][w] != 0) return;
			w++;
		}
		h++,w = 0;
	}
}

bool dfs(int h,int w,int sn,int sm){
	if(sn == n || sm == 0){
		return sm == 0 && sn == n;
	}

	if(a[h][w] != 0){
		FOR(i,3) if(sn < n && sm - sz(dw[i]) >= 0 && vaild(i,h,w)) {
			erase(i,h,w);
			ans[sn] = P(w + dw_md[i],h + dh_md[i],i+1);
			bool ret = dfs(h,w,sn + 1,sm - sz(dw[i]));
			redraw(i,h,w);
			if(ret) return true;
		}
	} else {
		hw_next(h,w);
		bool ret = dfs(h,w,sn,sm);
		if(ret) return true;
	}

	return false;
}

int main(){
	init();
	cin>>n;
	FOR(i,MAX_H) FOR(j,MAX_W) cin>>a[i][j];
	int sm = 0; 
	FOR(i,MAX_H) FOR(j,MAX_W) sm += a[i][j];

	dfs(0,0,0,sm);

	FOR(i,n){
		printf("%d %d %d\n",ans[i].w,ans[i].h,ans[i].c);
	}

	return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
int n,w[105],num1,num2,ans=1e5;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++)
	{
		num1=0,num2=0;
		for(int j=1;j<=n;j++)
		{
			if(j<=i) num1+=w[j];
			else num2+=w[j];
		}
		ans=min(ans,abs(num1-num2));
	}
	cout<<ans;
	return 0;
}

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


typedef long long ll;
string s;
//-----------------------------------------------------------------
int main() {
	cin >> s;

	vector<int> buf;
	int pre = 0;
	char pc = s[0];
	rep(i, 1, s.length()) {
		if (pc != s[i]) {
			buf.push_back(i - pre);
			pc = s[i];
			pre = i;
		}
	}
	buf.push_back(s.length() - pre);

	cout << buf.size() - 1 << endl;
}

Measured memory_bytes: 1020
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  sort(a.begin(), a.end());

#if 0
  for (int i = 0; i < n; i++) {
    cout << a[i] << ", ";
  }
  cout << endl;
#endif

  int max_count = 0;
//   for (int i = 0; i < n; i++) {
//     int count = 0;
//     int j = i;
//     while (a[j] - a[i] <= 2 && j < n) {
//       count++;
//       j++;
//     }
//     if (count > max_count) {
//       max_count = count;
//     }
//   }

  vector<int> same_num_count(a[n - 1] + 1);
  for (int i = 0; i < n; i++) {
    same_num_count[a[i]]++;
  }

#if 0
  for (int i = 0; i < same_num_count.size(); i++) {
    cout << same_num_count[i] << ", ";
  }
  cout << endl;
#endif  

  if (same_num_count.size() == 1) {
    max_count = same_num_count[0];
  } else if (same_num_count.size() == 2) {
    max_count = same_num_count[0] + same_num_count[1];
  } else {
    for (int i = 0; i < same_num_count.size() - 2; i++) {
      int count = same_num_count[i] + same_num_count[i + 1] + same_num_count[i + 2];
      if (count > max_count) {
	max_count = count;
      }
    }
  }

  cout << max_count << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
using namespace std;
#define mod 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%mod) % mod)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<int, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };

i64 D[114514];
i64 Powmod(i64 a, i64 b, i64 p)
{
	if (b == 0) return 1;
	if (b % 2 == 0)
	{
		i64 d = Powmod(a, b / 2, p);
		return d * d % p;
	}
	else
	{
		return a * Powmod(a, b - 1, p) % p;
	}
}
int main()
{
	memset(D, -1, sizeof(D));
	int N;
	scanf("%d", &N);
	int A[114514];
	for (int i = 0; i <= N; i++)
	{
		scanf("%d", &A[i]);
	}
	int C[114514];
	//memset(C, -1, sizeof(C));
	i64 K[114514];
	K[0] = 1;
	C[0] = -1;
	for (int i = 1; i <= N + 1; i++)
	{
		K[i] = (K[i - 1] * i) % mod;
		C[i] = -1;
	}
	int l = -1, r = -1;
	for (int i = 0; i <= N; i++)
	{
		int x = A[i];
		if (C[x] == -1)
		{
			C[x] = i;
		}
		else
		{
			l = C[x];
			r = i;
			break;
		}

	}
	//printf("%d %d\n",l,r);
	int W = l + N - r;

	printf("%d\n", N);
	for (int i = 2; i <= N; i++)
	{
		i64 p;

		if (D[i] != -1)p = D[i];
		else
		{
			D[i] = Powmod(K[i], mod - 2, mod);
			p = D[i];
		}
		i64 d = K[N + 1] * p % mod;

		if (D[N + 1 - i] != -1)p = D[N + 1 - i];
		else
		{
			D[N + 1 - i] = Powmod(K[N + 1 - i], mod - 2, mod);
			p = D[N + 1 - i];
		}
		d = d * p % mod;

		if (i == 2)
		{
			d -= l;
			d -= N - r;
		}
		else
		{
			if (i - 1 <= W)
			{
				if (D[i - 1] != -1)p = D[i - 1];
				else
				{
					D[i - 1] = Powmod(K[i - 1], mod - 2, mod);
					p = D[i - 1];
				}
				i64 e = K[W] * p % mod;

				if (D[W - i + 1] != -1)p = D[W - i + 1];
				else
				{
					D[W - i + 1] = Powmod(K[W - i + 1], mod - 2, mod);
					p = D[W - i + 1];
				}
				e = e * p % mod;

				d -= e;
			}
		}
		while (d< 0)
		{
			d += mod;
		}
		d %= mod;
		printf("%lld\n", d);

	}
	printf("1\n");
	return 0;
}


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

typedef long long ll;
typedef long double ld;
using namespace std;
//mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 mrand(42);
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define al(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define asdd cout<<"okok"<<endl;
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define pr(v) for(auto i:v) cout<<i<<" ";cout<<endl;
#define prt(a, l, r) for(auto i=l;i<=r;++i) cout<<a[i]<<" ";cout<<endl;
#define pc(x) __builtin_popcount(x)
#define pb push_back
#define PS string qqwwee;cin>>qqwwee;
typedef pair<int,int> pii;


ll cnt[44][21][10];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    int inte = 0;
    for(int i=1;i<=n;++i) {
        string s;
        cin >> s;
        int zero = 0;
        if(s.find('.') != string::npos) {
            zero = s.size() - s.find('.') - 1;
            s.erase(s.find('.'), 1);
        }
        ll x = stoll(s);
//        cout << x << endl;
        int two = 0, five = 0;
        while(x % 2 == 0) x /= 2, two++;
        while(x % 5 == 0) x /= 5, five++;
        if(min(two, five) >= zero) ++inte;
        cnt[two][five][zero]++;
    }
    ll ans = 0;
    for(int i=0;i<=43;++i) {
        for(int j=0;j<=20;++j) {
            for(int k=0;k<=9;++k) {
                if(!cnt[i][j][k]) continue;
                for(int i2=0;i2<=43;++i2) {
                    for(int j2=0;j2<=20;++j2) {
                        for(int k2=0;k2<=9;++k2) {
                            if(cnt[i2][j2][k2] && min(i+i2,j+j2)>=k+k2) ans+=1ll*cnt[i][j][k]*cnt[i2][j2][k2];
                        }
                    }
                }
            }
        }
    }
//    cout << ans << endl;
    ans = (ans - inte) / 2;
    cout << ans << endl;
}

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

using namespace std;

int main(){
	int n,k;
	cin >> n >> k;
	vector<int> a(n);
	vector<bool> dp(k+1);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i <= k; i++){
		bool flag = false;
		for(int j = 0; j < n; j++){
			if(a[j]<=i) flag |= !dp[i-a[j]];
		}
		dp[i] = flag;
	}
	cout << (dp[k]?"First":"Second") << endl;
	return 0;
}


Measured memory_bytes: 256
import numpy as np

N = int(input())

H = [int(i) for i in input().split()]

count =0

for i in range(N):
    if i ==0:
        count+=1
        H_max_so_far = H[i]
    else:
        if H[i] >= H_max_so_far:
            count+=1
            H_max_so_far = H[i]
            
print(count)

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

union Segments {
    struct {
        unsigned int g: 1;
        unsigned int f: 1;
        unsigned int e: 1;
        unsigned int d: 1;
        unsigned int c: 1;
        unsigned int b: 1;
        unsigned int a: 1;
    } bit;
    unsigned int row;
};


ostream& operator<<(ostream& out, const Segments& s) {
    out << s.bit.g << s.bit.f << s.bit.e << s.bit.d << s.bit.c << s.bit.b << s.bit.a;
    return out;
}

Segments d[] = {
    {0,1,1,1,1,1,1},
    {0,0,0,0,1,1,0},
    {1,0,1,1,0,1,1},
    {1,0,0,1,1,1,1},
    {1,1,0,0,1,1,0},
    {1,1,0,1,1,0,1},
    {1,1,1,1,1,0,1},
    {0,1,0,0,1,1,1},
    {1,1,1,1,1,1,1},
    {1,1,0,1,1,1,1}
};

int main() {
    int n, x;
    Segments display, sig;

    while (cin >> n, n != -1) {
        display.row = 0;
        while (n--) {
            cin >> x;
            sig.row = display.row ^ d[x].row;
            cout << sig << endl;
            display = d[x];
        }
    }
    return 0;
}

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

#define ll long long int

#define endl "\n"

int main(){

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

    int t=1;
    // cin>>t;

    while(t--){
        ll n;
        cin>>n;
        ll ans=0;
        for(ll i=1;i<n;i++){
            for(ll j=i;j*i<n;j++){
                ans+=2;
                if(j==i)
                    ans--;
            }
        }        
        cout<<ans<<endl;
    }


    return 0;
}

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

#define scd second
#define fst first
#define pb push_back
#define mkp make_pair
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
typedef vector<ll> vlong;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vint> vvint;
typedef vector<vlong> vvlong;
typedef list<int> lint;
typedef list<ll> llong;
typedef list<pii> lpii;
typedef list<pll> lpll;
typedef list<lint> llint;
typedef list<llong> lllong;

ll const LINF=numeric_limits<long long int>::max();
int const INF=numeric_limits<int>::max();

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

ll pow_mod(ll a, ll e, ll m){
	ll res=1;
	while(e){
		if(e&1) res=res*a%m;
		a=a*a%m;
		e>>=1;
	}
	return res;
}

ll inv_mod(ll b, ll m){
	b%=m;
	ll x=0, y=1, r, q, a=m;
	while(b){
		q=a/b;
		r=a%b;
		a=b;
		b=r;
		r=x;
		x=y;
		y=r-q*y;
	}
	x+=m;
	return x%m;
}

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

	vint pc={100,101,102,103,104,105};
	int s=0;
	while(true){
		int e=pc.size();
		for(int i=s; i<e; i++){
			pc.pb(pc[i]+100);
		}
		for(int i=101; i<=105; i++){
			pc.pb(pc[e-1]+i);
		}
		s=e;
		if(pc.back()>=1e5) break;
	}

	// for(int i=0; i<100; i++) cout<<pc[i]<<endl;

	int x;
	cin>>x;
	int ans=0;
	for(auto y : pc){
		if(y==x){
			ans=1;
			break;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 14572
def max(a,b)
    return a < b ? b : a
end
def min(a,b) 
    return a = a > b ? b : a
end
N = gets.to_i
dp = Array.new(N+1,123123123)
dp[0] = 0
N.times do |i|
    b = 1
    while(b<=i+1)
        dp[i+1] = min(dp[i+1],dp[i+1-b]+1)
        b*=6
    end
    b = 1
    while(b<=i+1)
        dp[i+1] = min(dp[i+1],dp[i+1-b]+1)
        b*=9
    end
end
p dp[N]

Measured memory_bytes: 2556
#include <cstdio>
#include <algorithm>
#define LL long long
const int maxn = 1e5 + 5; 
using namespace std;
LL a[maxn], k[maxn], res[maxn]; int n, Q, cnt;
void work(LL x, LL v){
	if (x <= a[1]){
		res[1] += v;
		res[x + 1] -= v;
		return;
	}
	int t = upper_bound(a + 1, a + cnt + 1, x) - a;
	k[t - 1] += v * (x / a[t - 1]);
	work(x % a[t - 1], v);
}
int main(){
	scanf("%d%d", &n, &Q);
	a[cnt = 1] = n;
	for (int i = 1; i <= Q; i++){
		LL x; scanf("%lld", &x);
		while (cnt > 0 && a[cnt] >= x) cnt--;
		a[++cnt] = x;
	}
	k[cnt] = 1;
	for (int i = cnt; i >= 2; i--){
		k[i - 1] += k[i] * (a[i] / a[i - 1]);
		work(a[i] % a[i - 1], k[i]);
	}
	res[0] = k[1];
	res[a[1] + 1] -= k[1];
	for (int i = 1; i <= n; i++){
		res[i] += res[i - 1];
		printf("%lld ", res[i]);
	}
	return 0;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
    詰まった時に、別の分野の問題として考え直す（これdpでは？、グラフとしてみればいいのでは？）
    多くの問題はパターンマッチだが、パターンに落とし込むまでが難しく、そのための訓練としてわからない問題をあれこれ色々な角度から考察してみるのではないか
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */


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

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

    vector<ll> A(n+1, 0), B(n+1, 0);
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    ll sum=0;

    rep(i, n){
        pq.push(a[i]);
        sum += a[i];
    }
    repr(i, n, 2*n+1){
        A[i-n] = sum;
        sum += a[i];
        pq.push(a[i]);
        sum -= pq.top();
        pq.pop();
    }

    priority_queue<ll> pq2;
    sum=0;
    reprrev(i, 2*n+1, 3*n){
        pq2.push(a[i]);
        sum += a[i];
    }
    reprrev(i, n, 2*n+1){
        sum+=a[i];
        pq2.push(a[i]);
        if(i!=2*n) { sum-=pq2.top(); pq2.pop(); }
        B[i-n]=sum;
    }

    ll ans=-(1LL<<60);
    rep(i, n+1) chmax(ans, A[i]-B[i]);
    cout << ans << endl;

    // rep(i, n+1) cout << A[i] << ' ';
    // cout << endl;
    // rep(i, n+1) cout << B[i] << ' ';
    
    return 0;
}


Measured memory_bytes: 6652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  int n;
  cin >> n;
  if(n==0) cout << 0 << endl;
  else{
  vector<int> bin;
  while(n!=0){
    if(n%2 == 0){
      bin.push_back(0);
      n /= -2;
    }else{
      bin.push_back(1);
      if(n>0) n = -n/2;
      else n = (-n+1)/2;
    }
    //cout << n << endl;
  }
  reverse(bin.begin(),bin.end());
  rep(i,bin.size()) cout << bin.at(i) ;
  cout << endl;
  }
  return 0;
}



Measured memory_bytes: 256