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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N;
    cin >> N;
    vector<P> items(N);
    rep(i, N) cin >> items[i].first >> items[i].second;
    vector<int> V(N), W(N);
    rep(i, N) {
        V[i] = items[i].first;
        W[i] = items[i].second;
    }
    ll Q;
    cin >> Q;

    vector<vector<ll>> dp(min(N + 1, (ll)(1 << 10) + 1), vector<ll>(100001, 0));
    rep2(i, 1, min(N + 1, (ll)(1 << 10) + 1)) {
        rep(j, 100001) {
            ll par = i / 2;
            dp[i][j] = dp[par][j];
            if (j - items[i - 1].second >= 0) {
                dp[i][j] = max(dp[i][j], dp[par][j - items[i - 1].second] + items[i - 1].first);
            }
        }
    }
    vector<ll> ans(Q);
    vector<P> query(Q);
    rep(q, Q) cin >> query[q].first >> query[q].second;
    rep(q, Q) {
        int v = query[q].first;
        int L = query[q].second;
        vector<int> use;
        v--;
        int u = v;
        use.push_back(u);
        while (u != 0) {
            u = (u - 1) / 2;
            use.push_back(u);
        }
        if (v < (1 << 10)) {
            ans[q] = dp[v + 1][L];
            continue;
        }
        sort(use.begin(), use.end());
        int n = use.size();
        vector<int> use_p;
        int last = -1;
        rep(i, n) {
            if (use[i] >= (1 << 10)) {
                use_p.push_back(use[i]);
            } else {
                last = max(last, use[i]);
            }
        }
        ll a = 0;
        rep(i, 1 << (int) use_p.size()) {
            int value = 0;
            int weight = 0;
            rep(j, use_p.size()) {
                if (i & (1 << j)) {
                    value += V[use_p[j]];
                    weight += W[use_p[j]];
                    if (weight > L) break;
                }
            }
            if (L - weight < 0) continue;
            a = max(a, dp[last + 1][L - weight] + value);
        }
        ans[q] = a;
    }
    rep(q, Q) {
        cout << ans[q] << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,x;
    cin>>n>>x;
    ll a[n];

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

    sort(a,a+n);
    cout << n+x/a[0]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

int a, b;

int main(){
	//IO("input.txt", "output.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> a >> b;
	if(a >= 13) cout << b << "\n";
	else if(a >= 6) cout << b / 2 << "\n";
	else cout << "0\n";
	return 0;
}

Measured memory_bytes: 256
#include <array>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <unordered_map>
using namespace std;

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

enum FACE { TOP, BOTTOM, NORTH, SOUTH, WEST, EAST, NUM };

struct dice {
	array<int, NUM> num;
	dice():num({{1, 6, 2, 5, 3, 4}}) {}

	int operator[](FACE f) { return num[f]; }

	void roll(FACE a, FACE b, FACE c, FACE d) {
		const int t = num[a];
		num[a] = num[b];
		num[b] = num[c];
		num[c] = num[d];
		num[d] = t;
	}
};

void north(dice &die) { die.roll(TOP, SOUTH, BOTTOM, NORTH); }
void south(dice &die) { die.roll(TOP, NORTH, BOTTOM, SOUTH); }
void west (dice &die) { die.roll(TOP,  EAST, BOTTOM,  WEST); }
void east (dice &die) { die.roll(TOP,  WEST, BOTTOM,  EAST); }

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

	const unordered_map<string, function<void(dice&)>> operate{
		{"north", &north},
		{"south", &south},
		{"west" , &west},
		{"east" , &east}
	};

	for(int n; cin >> n && n;) {
		dice die;
		rep(i, n) {
			string s;
			cin >> s;
			operate.at(s)(die);
		}
		cout << die[TOP] << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T> ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int N;
  cin>>N;
  double sum=0;
  REP(i,0,N){
    double a;
    cin>>a;
    sum+=1.0/a;
  }
  printf("%lf\n", 1.0/sum);

  return 0;
}


Measured memory_bytes: 256
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):x,d,n=map(int,input().split());t=x*p(d,M-2,M)%M;print([p(x,n,M),M//(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Measured memory_bytes: 94188
a,b,c,d = map(int, input().split())

s1 = a*c
s2 = a*d
s3 = b*c
s4 = b*d

score = [s1,s2,s3,s4]
max_score = max(score)
if a<=0<=b and c<=0<=d and max_score<0:
    print(0)
else:
  print(max_score)

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

#ifdef _LOCAL_DEBUG
#include "templates/debug.h"
#else
#define debug(...)
#endif

int r, c, n;
vector<vector<ll>> a;
vector<vector<array<ll, 4>>> dp;

void maxi(ll& x, ll y) {
    x = max(x, y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> r >> c >> n;
    a.resize(r, vector<ll>(c));
    dp.resize(r, vector<array<ll, 4>>(c));
    for (int x = 0; x < n; x++) {
        int i, j, v;
        cin >> i >> j >> v;
        a[i - 1][j - 1] = v;
    }
    dp[0][0][1] = a[0][0];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            for (int k = 0; k <= 3; k++) {
                if (i + 1 < r) {
                    maxi(dp[i + 1][j][0], dp[i][j][k]);
                    if (a[i + 1][j] != 0)
                        maxi(dp[i + 1][j][1], dp[i][j][k] + a[i + 1][j]);
                }
                if (j + 1 < c) {
                    maxi(dp[i][j + 1][k], dp[i][j][k]);
                    if (k < 3 && a[i][j + 1] != 0)
                        maxi(dp[i][j + 1][k + 1], dp[i][j][k] + a[i][j + 1]);
                }
            }
        }
    }
    cout << *max_element(dp[r - 1][c - 1].begin(), dp[r - 1][c - 1].end());
    return 0;
}

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

using namespace std;
using ll = long long int;


int main() {
		int n;
		cin>>n;
		ll arr[n];
		for(int i = 0; i < n; i++) cin>>arr[i];
		ll dp[n][n];
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < n; i++) {
			dp[i][i] = arr[i];
		}
		for(int len = 2; len <= n; len++) {
			for(int i = 0; i < n && i + len-1 < n ; i++) {
				int j = i + len-1;
				dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1]);
			}
		}
		cout<<dp[0][n-1]<<"\n";
}


Measured memory_bytes: 70528
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<tuple>
#include<stdio.h>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Q;
ll longinf=1ll<<60;
int inf=1<<29;
int dh[]={1,-1,0,0};
int dw[]={0,0,1,-1};
//mleしなければぜんぶllでかく。

ll keta(ll n){
      ll pos=0;
      while(n>0){
            n/=2;
            pos++;
      }
      return pos;
}
int main(){
      cin.tie(0);
      ios::sync_with_stdio(false);
      ll n,k;
      cin>>n>>k;
      ll b[n];
      rep0(i,n) cin>>b[i];
      ll a[n];
      rep0(i,n) a[i]=b[i];
      ll keta_k=keta(k);
      ll cnt0[keta_k];
      fill(cnt0,cnt0+keta_k,0);
      ll cnt1[keta_k];
      fill(cnt1,cnt1+keta_k,0);
      rep0(i,n){
            rep0(j,keta_k){
                  if(a[i]&1) cnt1[j]++;
                  else cnt0[j]++;
                  a[i]>>=1;
            }
      }
      ll max_k[keta_k];
      rep0(j,keta_k){
            if(j==0){
                  if(cnt1[j]<cnt0[j]) max_k[j]=1;
                  else max_k[j]=0;
            }
            else{
                  if(cnt1[j]<cnt0[j]) max_k[j]=(1ll<<j)+max_k[j-1];
                  else max_k[j]=max_k[j-1];
            }
      }
      ll ans_k=0;
      rep0(j,keta_k){
            ll checker=(1ll<<(keta_k-1-j))+ans_k;
            ll check_sum=0;
            ll now_sum=0;
            if(checker>k) continue;
            rep0(i,n){
                  check_sum+=(b[i]^checker);
                  now_sum+=(b[i]^ans_k);
            }
            if(check_sum>=now_sum) ans_k=checker;
      }
      ll ans=0;
      rep0(i,n){
            ans+=(ans_k^b[i]);
      }
      cout<<ans<<endl;


      return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define ind(a) scanf("%lf", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a));
//def   puts(a) printf("%s\n", a) 文字はこっち
//your code here!


int main(void){
    ll N, L;
    in(N); in(L);
    if(L>=0) put(L*(N-1)+(N-1)*N/2);
    else if(L+N-1<=0) put(L*(N-1)+(N-2)*(N-1)/2);
    else put(L*N+N*(N-1)/2);
    return 0;
}


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

using namespace std;

#define pb push_back
#define ull unsigned long long
#define ll long long

// LETS KEEP IT SIMPLE AND ROBUST

int solve() {

	return 0;
}


int main() {
	int s, w;
	cin>>s>>w;
	if (w>=s) {
		printf("unsafe\n");
	} else {
		printf("safe\n");
	}
}









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

const ll L = 1000000007;

ll fnc(int x) {
    ll ret = 1;
    for (int i=1; i<=x; i++) {
        ret *= i;
        ret %= L;
    }
    return ret;
}

int main() {
    int m, n;
    cin >> m >> n;
    if (abs(m-n) > 1) cout << 0 << endl;
    else if (m == n) cout << (2*fnc(m)*fnc(n))%L << endl;
    else cout << (fnc(m)*fnc(n))%L << 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 all(a) (a).begin(),(a).end()
typedef long long ll;

int main(void){
    string s;
    cin >> s;
    reverse(all(s));
    int n = s.size();
    ll res = 0;
    ll bc = 0;
    rep(i,n){
        if (s[i] == 'A') {
            res += bc;
            continue;
        }
        if (i == n-1) {
            continue;
        }
        if (s[i] == 'C' && s[i+1] == 'B') {
            bc++;
            i++;
            continue;
        }
        bc = 0;
    }
    cout << res << endl;
    return 0;
}


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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int ans=0;
    for (int i=1;i<=n-1;i++){
        int temp=n-i;
        for (int j=1;j<=sqrt(temp);j++){
            if(temp%j==0){
                ans++;
                if(temp/j!=j) ans++;
            }
        }
    }
    cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 3716
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const long long INF=200000000000000;
double pi=3.141592653589793;

const int MOD = 1000000007;

long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	return gcd(a%b,b);
}

long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
long myPow(long long x, long long n, long long m=MOD){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout<<fixed;
	string s;
	cin>>s;
	if(s=="SUN")cout<<7<<endl;
	if(s=="MON")cout<<6<<endl;
	if(s=="TUE")cout<<5<<endl;
	if(s=="WED")cout<<4<<endl;
	if(s=="THU")cout<<3<<endl;
	if(s=="FRI")cout<<2<<endl;
	if(s=="SAT")cout<<1<<endl;
}



Measured memory_bytes: 764
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VV(T, a, b, c) vector<vector<T>>(a, vector<T>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define VVV(T, a, b, c, d)                                                     \
  vector<vector<vector<T>>>(a, vector<vector<T>>(b, vector<T>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N, R;
  cin >> N >> R;
  if (N >= 10) {
    cout << R << endl;
  } else {
    cout << R + (100 * (10 - N)) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    double ans = 0;
    int n,m,d;
    cin >> n >> m >> d;
    if(d == 0){
        ans = 1.0/n;
    }else{
        ans = 2.0*(n-d)/n/n;
    }
    ans *= (m-1);
    printf("%.10lf\n", ans);
}

Measured memory_bytes: 256
# デバッグ用
GBN_DEBUG = False
def dprn(s, i):
    if GBN_DEBUG: print(", " + s + " = " + str(i), end = "")
def dprns(s):
    if GBN_DEBUG: print(", " + s, end = "")
def dprni(i):
    if GBN_DEBUG: print(i, end=" ")
def endl(): 
    if GBN_DEBUG: print('')
def puts(s): print(s)

#本体ここから

#S = input()
#N = int(input())
#S, T = input().split()
A, B, C = map(int, input().split())
#W = [input() for _ in range(N)]
#A = list(map(int, input().split()))

#GBN_DEBUG = True

cup1_remain = A - B
print(max(0, C - cup1_remain))


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

int main(void) {
    int n, k;
    string s;
    cin >> n;
    cin >> s;
    cin >> k;
    char c = s[k - 1];
    for (int i = 0; i < n; i++) {
        if (s[i] != c) {
            s[i] = '*';
        }
    }
    cout << s << endl;
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val n = sc.nextLong()

  val map = mutableMapOf<Long, Int>()

  for (x in 1L..100L) {
    for (y in 1L..100L) {
      for (z in 1L..100L) {

        val tmp = x * x + y * y + z * z + x * y + y * z + z * x
        val value = map.getOrElse(tmp) { 0 }
        map.put(tmp, value+1)
      }
    }
  }

  for (i in 1L..n) {
    val value = map.getOrElse(i) { 0 }
    println(value)
  }

}


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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>; 

#define INF 100000000
#define MOD 10007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

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

  int N,M,C;
  cin>>N>>M>>C;
  vector<int>B(M);
  for(int i=0;i<M;i++)cin>>B[i];
  vector<vector<int> >A(M,vector<int>(N));
  for(int y=0;y<N;y++){
    for(int x=0;x<M;x++){
      cin>>A[x][y];
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    int sum=0;
    for(int j=0;j<M;j++){
      sum+=A[j][i]*B[j];
    }
    sum+=C;
    if(sum>0)ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

const int maxk = 102;
const int mo = 1e9 + 7;

int k, n;

int main() {

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

	cin >> n >> k;

	int lim = floor(sqrt(n));
	vector<vector<int> > f(k+1, vector<int>(lim+1)),
						 g(k+1, vector<int>(lim+1));

	vector<long long> buckets(lim+1);

	for (int j = 1; j <= lim; ++j) {
		f[1][j] = 1;
		if (j == n / j)
			g[1][j] = buckets[j] = 0;
		else
			g[1][j] = buckets[j] = n / j - n / (j+1);
	}

	for (int i = 2; i <= k; ++i) {
		long long sumf = 0;
		for (int j = 1; j <= lim; ++j) {
			sumf = (sumf + f[i-1][j]) % mo;
			if (j == n / j)
				g[i][j] = 0;
			else
				g[i][j] = buckets[j] * sumf % mo;
		}

		long long sumg = 0;
		for (int j = lim; j >= 1; --j) {
			sumg = (sumg + g[i-1][j]) % mo;
			f[i][j] = (sumf + sumg) % mo;
		}
	}

	long long ans = 0;
	for (int j = 1; j <= lim; ++j)
		ans = (ans + f[k][j] + g[k][j]) % mo;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 25600
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define VI vector<int>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
ll n;
bool f(ll d){
	if(d == 1) return 0;
	ll x = n;
	while(x % d == 0) x /= d;
	return x%d == 1;
}
int main(){
	scanf("%lld", &n);
	int tot = 0;
	for(ll i = 1; i * i <= n; i++){
		if(n%i == 0){
			tot += f(i);
			if(i != n/i) tot += f(n/i);
		}
	}
	n--;
	for(ll i = 1; i * i <= n; i++){
		if(n%i == 0){
			if(i != 1) tot++;
			if(n/i != i) tot++;
		}
	}
	printf("%d\n", tot);
	return 0;
}

Measured memory_bytes: 256
// Author: πα

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

#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define long int64_t

const int N = 1e5 + 5;
long dp[N];

int main()
{
    FastIO;
    int n, i, j, m, v, w;
    cin >> n >> m;
    for(i = 0; i < n; ++i)
    {
        cin >> w >> v;
        for(j = m-w; j >= 0; --j)
            dp[j+w] = max(dp[j+w], dp[j]+v);   
    }
    cout << dp[m] << endl;
    return 0;
}

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

int main() {
	int a, b, c, lop;
	while (cin >> a >> b) {
		c = 10;
		for (lop = 1; c<=a+b; lop++) {
			c *= 10;
		}
		cout << lop << endl;

	}
	return 0;
}


Measured memory_bytes: 3008
d=input().split()
v=list(input())

def roll(Dice,Vector):
    if Vector == "N":
        c=Dice[0]
        Dice[0]=Dice[1]
        Dice[1]=Dice[5]
        Dice[5]=Dice[4]
        Dice[4]=c
    elif Vector == "W":
        c=Dice[0]
        Dice[0]=Dice[2]
        Dice[2]=Dice[5]
        Dice[5]=Dice[3]
        Dice[3]=c
    elif Vector == "E":
        c=Dice[0]
        Dice[0]=Dice[3]
        Dice[3]=Dice[5]
        Dice[5]=Dice[2]
        Dice[2]=c
    elif Vector == "S":
        c=Dice[0]
        Dice[0]=Dice[4]
        Dice[4]=Dice[5]
        Dice[5]=Dice[1]
        Dice[1]=c

for item in v:
    roll(d,item)
print(d[0])


Measured memory_bytes: 5568
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;

ll power(ll x, ll n){
    if(n==0){
        return 1;
    }
    
    ll temp = power(x,n/2);
    if(n%2==1){
        return (temp*temp%MOD)*x%MOD;
    }else{
        return temp*temp%MOD;
    }
}

string L;
int main(){
    ll ans = 0;
    
    cin >> L;
    
    int n=L.length();
    ll bi=1;
    for(int i=0; i<n; i++){
        if(L[i]=='1'){
            ans+=(power(3,n-1-i)*bi)%MOD;
            bi*=2;
            bi%=MOD;
        }
    }
    ans += bi;
    ans%=MOD;
    
    cout<<ans<<endl;
    return 0;
}






Measured memory_bytes: 512
class BinaryTreeNode():
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

class BinarySearchTree():
    def __init__(self):
        self.root = None

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < x.val:
                x = x.left
            else:
                x = x.right
        node = BinaryTreeNode(val=val)

        if y == None:
            self.root = node
        elif node.val < y.val:
            y.left = node
        else:
            y.right = node

    def find(self, val):
        x = self.root
        while x != None:
            if x.val == val:
                return True
            elif x.val < val:
                x = x.right
            else:
                x = x.left
        return False

    def preorder(self):
        self.preorder_list = []
        self.preorder_bfs(self.root)
        return self.preorder_list

    def preorder_bfs(self, u):
        if u == None: return
        self.preorder_list.append(u.val)
        self.preorder_bfs(u.left)
        self.preorder_bfs(u.right)

    def inorder(self):
        self.inorder_list = []
        self.inorder_dfs(self.root)
        return self.inorder_list

    def inorder_dfs(self, u):
        if u == None: return
        self.inorder_dfs(u.left)
        self.inorder_list.append(u.val)
        self.inorder_dfs(u.right)

def print_elements(arr):
    print(' ' + ' '.join([str(item) for item in arr]))

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
        continue

    ope, num = op.split(' ')
    num = int(num)
    if ope == 'insert':
        bst.insert(num)
    elif ope == 'find':
        if bst.find(num):
            print('yes')
        else:
            print('no')



Measured memory_bytes: 121500
"""
覚えておきたい
"""

n,*a=map(int,open(0).read().split())
ans=1
tmp=0
for i in range(1,n):
  if (a[i]-a[i-1])*tmp<0:
    ans+=1
    tmp=0
  elif not a[i]-a[i-1]==0:
    tmp=a[i]-a[i-1]
print(ans)

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(a) int((a).size())
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ini(a, i) memset(a, i, sizeof(a))
#define inin(a, n, i) memset(a, i, sizeof(a[0])*(n))
#define contains(c, i) ((c).find(i) != (c).end())
#define present(i, c) (find(all(c), i) != (c).end())

#define trav(x, c) for(auto& x : c)
#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, b, e) for(int i = (b)-((b)>(e)); i != (e)-((b)>(e)); i += 1-2*((b)>(e)))
	
template<class T> bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }
template<class T> bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template<class A, class B> A cvt(B x) { stringstream s; s << x; A r; s >> r; return r; }

void read() {}
void print() {}
template<class T, class... Args> void read(T& a, Args&... args) { cin >> a; read(args...); }
template<class T, class... Args> void print(T a, Args... args) { cout << a << ' '; print(args...); }
template<class... Args> void println(Args... args) { print(args...); cout << '\n'; }

#define debug(args...) { string s_(#args); replace(all(s_), ',', ' '); stringstream ss_(s_); istream_iterator<string> it_(ss_); cerr_(it_, args); }
void cerr_(istream_iterator<string> it) { (void) it; }
template<class T, class... Args> void cerr_(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; cerr_(++it, args...); }

template<class T, class S>  ostream& operator<<(ostream& os, const pair<T, S>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<class T> ostream& operator<<(ostream &os, const set<T> &s) { os << '{'; string sep; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<class T, class S> ostream& operator<<(ostream &os, const map<T, S> &m) { os << '{'; string sep; for (const auto &x : m) os << sep << x, sep = ", "; return os << '}'; }
template<class T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }

const int INF = 0x3F3F3F3F;
const int MAXN = (int) 1e6;
const int MOD = (int) 1e9+7;

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

void run_test() {
	int k; read(k);
	rep(i, k) cout << "ACL";
	println();
}

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//int t_ = 1, t__; cin >> t__; while(t_ <= t__) { cout << "Case #" << t_++ << ": "; run_test(); }
	// int t_; cin >> t_; while(t_--) run_test();
	run_test();
	return 0;	
}


Measured memory_bytes: 3524
S = int(input())
n = S // 3
p = 1000000000 + 7
N = 2000
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def MOD_binom(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

answer = 0

for i in range(1, n + 1):
    answer += MOD_binom(S - 2*i - 1, i-1, p)
print(answer % p)


Measured memory_bytes: 9388
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
string u="abcdefghijklmnopqrstuvwxyz";

int main(){
    int N;
    cin >> N;
    LL u=0,v=0;
    for(int i=0;i<N;i++){
        LL t,a;
        cin >> t >> a;
        if(i==0){
            u=t;
            v=a;
            continue;
        }
        LL p,q;
        if(u%t==0) q=u/t;
        else q=u/t+1;
        if(v%a==0) p=v/a;
        else p=v/a+1;
        LL g;
        g=max(q,p);
        u=g*t;
        v=g*a;
    }
    cout << u+v << endl;
    return 0;
}

Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B: Find Symmetries
 */

#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;

/* constant */

const int MAX_N = 300;

/* typedef */

/* global variables */

char s[512];
int as[MAX_N][MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%s", s);
    for (int j = 0; j < n; j++) as[i][j] = s[j] - 'a';
  }

  int cnt = 0;
  for (int k = 0; k < n; k++) {
    bool ok = true;
    for (int i = 0; ok && i < n; i++) {
      int ik = (i + k) % n;
      for (int j = i + 1; ok && j < n; j++) {
	int jk = (j + k) % n;
	ok = (as[i][jk] == as[j][ik]);
      }
    }
    if (ok) cnt++;
  }

  printf("%d\n", cnt * n);
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
//F6編譯，右上三角形執行，ctrl+c強制停止執行  F5開啟exe
#define ll long long
#define maxn 100005
#define mod 1000000007
using namespace std;

typedef pair<int, int> P;

char s[105];

int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int ans = 0;
    for (int i = 1; i <= n / 2; i++)
        if (s[i] != s[n + 1 - i])
            ans++;
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n][3];
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>a[i][j];
		}
	}
	int dp[n][3];
	dp[0][0]=a[0][0];
	dp[0][1]=a[0][1];
	dp[0][2]=a[0][2];
	
	for(int i=1;i<n;i++){
		dp[i][1]=((dp[i-1][0]>dp[i-1][2])?dp[i-1][0]:dp[i-1][2])+a[i][1];
		dp[i][0]=((dp[i-1][1]>dp[i-1][2])?dp[i-1][1]:dp[i-1][2])+a[i][0];
		dp[i][2]=((dp[i-1][0]>dp[i-1][1])?dp[i-1][0]:dp[i-1][1])+a[i][2];
		
	}
	sort(dp[n-1],dp[n-1]+3);
	cout<<dp[n-1][2]<<endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
const int MAX_N = 100010;

int ball[MAX_N];
bool red[MAX_N];
int main(){
    int N,M;
    cin >> N >> M;
    fill(ball, ball+N, 1);
    red[0] = true;
    REP(i,M){
        int x,y;
        cin >> x >> y;
        x--, y--;
        ball[y]++;
        ball[x]--;
        if(red[x]){
            red[y] = true;
            if(ball[x] == 0){
                red[x] = false;
            }
        }
    }

    int ans = 0;
    REP(i,N){
        if(red[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 768
r,c=map(int,input().split())
a=[[0 for i in range(c+1)] for j in range(r+1)]
lst=[[int(a) for a in input().split()] for x in range(r)]

for k in range(r):
    for l in range(c):
        a[k][l]=lst[k][l]
        
for n in range(r+1):
    for m in range(c,c+1):
        a[n][m]=sum(a[n])
        
for n in range(c):
    s=0
    for m in range(r):
        s+=a[m][n]
    a[r][n]=s
a[r][c]=sum(a[r])
for n in range(r+1):
    print(*a[n])


Measured memory_bytes: 6256
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, M, P = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

to = [[] for _ in range(N + 1)]
ot = [[] for _ in range(N + 1)]
edges = [[] for _ in range(N + 1)]

for a, b, c in X:
    edges[a].append((b, c - P))
    to[a].append(b)
    ot[b].append(a)

ok_1 = [False] * (N + 1)
ok_n = [False] * (N + 1)

def dfs_1(u):
    if ok_1[u]:
        return
    
    ok_1[u] = True
    for v in to[u]:
        dfs_1(v)
        
def dfs_n(u):
    if ok_n[u]:
        return
    
    ok_n[u] = True
    for v in ot[u]:
        dfs_n(v)

dfs_1(1)
dfs_n(N)

INF = 10 ** 9 + 7
d = [INF] * (N + 1)
d[1] = 0
updated = True
cnt = 0
while updated and cnt <= N:
    updated = False
    cnt += 1
    for u in range(1, N + 1):
        if not ok_1[u] or not ok_n[u]:
            continue
            
        for v, c in edges[u]:
            if not ok_1[v] or not ok_n[v]:
                continue
                
            if d[v] > d[u] - c:
                d[v] = d[u] - c
                updated = True

if cnt > N:
    print(-1)
else:
    print(max(0, -d[-1]))


Measured memory_bytes: 87988
#include <iostream>
#include <string>
#include <algorithm>
#include <array>
#include <vector>

using namespace std;


int main(){
  int i,a,b;
  cin>>a>>b;
  vector<int>v(b);

  for(int i=0; i<b;i++){
     v[i]=a;
  }
  
   vector<int>v2(a);

  for(int i=0; i<a;i++){
     v2[i]=b;
  }
 
  if(v<v2){
    
  for(int i=0; i<b;i++){
     v[i]=a;
        cout<<v[i];
   
  }
     
  }else if(v2<v){
     
      for(int i=0; i<a;i++){
    
          v2[i]=b;
    cout<<v2[i];
  }
  }else if(v==v2){
          for(int i=0; i<a;i++){
    
          v2[i]=b;
    cout<<v2[i];
  }
  }
  


  return 0;
}



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

bool cmp(int m1,int d1,int m2,int d2){
  if(m1>m2){
      return true;
  }
  if(m1==m2){
      if(d1>=d2){
          return true;
      }
  }
  return false;
}
int main(){
 int y1,y2;
 int m1,m2;
 int d1,d2;
 cin>>y1>>m1>>d1;
 cin>>y2>>m2>>d2;
 int ans=abs(y1-y2)+1;
 if(y1==y2){
    if(m1==m2&&d1==d2)ans--;  //!!!!!!
 }
 if(y1<y2){
     if(cmp(m1,d1,m2,d2)){
         ans--;
     }
 }
 if(y1>y2){
     if(cmp(m2,d2,m1,d1)){
         ans--;
     }
 }
 cout<<ans<<endl;
 return 0;
}


Measured memory_bytes: 3120
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N (1<<17)
#define G 2147483647
class RUQ{
private:
    #define D 20
    ll dat[2*N],laz[2*N];
    ll eval(int k){
	if(laz[k]!=G){
	    dat[k]=laz[k];
	    if(k<N){
		laz[k*2]=laz[k];
		laz[k*2+1]=laz[k];
	    }
	}
	laz[k]=G;
	return dat[k];
    }
public:
    void Init(){
	lol(i,2*N)dat[i]=laz[i]=G;
    }
    void Upd(int l,int r,ll x){
	l+=N,r+=N+1;
	for(int i=D;i>=0;i--){
	    eval(l>>i);eval(r>>i);
	}
	for(int a=l,b=r;a<b;a>>=1,b>>=1){
	    if(a&1)laz[a++]=x;
	    if(b&1)laz[--b]=x;
	}
	for(int a=l,b=r;a;a>>=1,b>>=1){
	    dat[a/2]=min(eval(a),eval(a^1));
	    dat[b/2]=min(eval(b),eval(b^1));
	}
    }
    ll Min(int l,int r){
	l+=N,r+=N+1;
	for(int i=D;i>=0;i--){
	    eval(l>>i);eval(r>>i);
	}
	ll res=(ll)mod*(ll)mod;
	for(int a=l,b=r;a<b;a>>=1,b>>=1){
	    if(a&1)res=min(res,eval(a++));
	    if(b&1)res=min(res,eval(--b));
	}
	return res;
    }
};
int main(){
    int n,q;cin>>n>>q;
    RUQ seg;seg.Init();
    while(q--){
	ll a,b,c;cin>>a;
	if(a==0){
	    cin>>a>>b>>c;
	    seg.Upd(a,b,c);
	}
	else{
	    cin>>a>>b;
	    cout<<seg.Min(a,b)<<endl;
	}
    }
    return 0;
}



Measured memory_bytes: 7184
#include <iostream>
#include <cstdlib>
#include <climits>
#include <algorithm>

using namespace std;
const static int N_MAX =  110;
const static int H_MAX = 1010;


int main() {

  while( 1 ) {
    int amida[ H_MAX ][ N_MAX ] = { 0 };
    int n, m, a;
    int hMax = INT_MIN;
    cin >> n >> m >> a;
    if( !n && !m && !a ) { return EXIT_SUCCESS; }

    for( int i = 0; i < m; i++ ) {
      int h, p, q;
      cin >> h >> p >> q;
      amida[ h ][ p ] = q;
      amida[ h ][ q ] = p;
      hMax = max( hMax, h ); 
    }
    
    for( int h = hMax; h > 0; h-- ) {
      a = amida[ h ][ a ] ? amida[ h ][ a ] : a;  
    }

    cout << a << endl;
  }


}

Measured memory_bytes: 1600
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>

#define ll long long
#define LINF LLONG_MAX

using namespace std;

int main() {
  ll N, K, S;
  cin >> N >> K >> S;
  ll T = 0;
  if (S >= 500000000) {
    T = -1;
  } else {
    T = 1;
  }
  for (int i = 0; i < N; i++) {
    if (K > 0) {
      cout << S << " ";
      K--;
    } else {
      cout << abs(1000000000 - (S + T)) << " ";
    }
  }
  cout << endl;
}

Measured memory_bytes: 1280
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    n = II()
    if n < 1000:
        print("ABC")
    else:
        print("ABD")
    return

#B
def B():
    a, b = LI()
    x = b - a - 1
    print((1 + x) * x // 2 - a)
    return

#C
def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])
    return

#D
def D():
    n, c = LI()
    D = LIR(c)
    C = LIR_(n)
    CL = list(itertools.permutations(range(c), 3))
    ans = inf
    amari0 = [0 for i in range(30)]
    amari1 = amari0[::1]
    amari2 = amari0[::1]
    for y in range(n):
        for x in range(n):
            amari = (x + y) % 3
            if amari == 0:
                amari0[C[y][x]] += 1
            if amari == 1:
                amari1[C[y][x]] += 1
            if amari == 2:
                amari2[C[y][x]] += 1
    for c0, c1, c2 in CL:
        ansb = 0
        for i in range(c):
            ansb += D[i][c0] * amari0[i]
            ansb += D[i][c1] * amari1[i]
            ansb += D[i][c2] * amari2[i]
        ans = min(ans, ansb)
    print(ans)
    return

#Solve
if __name__ == '__main__':
    B()


Measured memory_bytes: 39920
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define pb(a) push_back(a)
#define int long long
using namespace std;
typedef long long LL;
const int INF = 999999999;

signed main(){
    int n,a[3];
    cin >> n;
    rep(i, 3) cin >> a[i];
    vector<int> l(n);
    rep(i, n) cin >> l[i];

    vector<vector<int> > mp(3, vector<int>(300, INF));
    rep(k, 3){
    rep(mask, 256){
        if(mask == 0) continue;
        int tmp = mask;
        int res = -10, now = 0;
        rep(i, n){
            if(tmp & 1){
                now += l[i];
                res += 10;
            }
            tmp >>= 1;
        }
        mp[k][mask] = abs(now - a[k])+res;
    }
    }
    LL ans = INF;
    int lim = 1;
    rep(i, n) lim *= 2;
    rep(i, lim)rep(j, lim)rep(k, lim){
        if((i&j) == 0 && (j&k) == 0 && (k&i) == 0){
            ans = min(ans, (LL)mp[0][i]+mp[1][j]+mp[2][k]);
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
from collections import deque

K = int(input())
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9,])

cnt = 0
while cnt < K-1:
    n = q.popleft()
    d = int(str(n)[-1])
    cnt += 1
    for i in [d-1, d, d+1]:
        if(i < 0 or 10 <= i):
            continue
        q.append(10*n+i)
print(q.popleft())

Measured memory_bytes: 19452
import sys
sys.setrecursionlimit(1000000)
def II(): return int(input())
def MI(): return map(int, input().split())
N=II()
edge=[[] for i in range(N)]
a=[0]*N
b=[0]*N
for i in range(N-1):
  a[i],b[i]=MI()
  a[i]-=1
  b[i]-=1
  edge[a[i]].append(b[i])
  edge[b[i]].append(a[i])
k=0
color_dict={}
def dfs(to,fm=-1,ban_color=-1):
  global k
  color=1
  for nxt in edge[to]:
    if nxt==fm:
      continue
    if color==ban_color:
      color+=1
    color_dict[(to,nxt)]=color
    dfs(nxt,to,color)
    color+=1
  k=max(k,color-1)
dfs(0)
print(k)
for i in range(N-1):
  print(color_dict[(a[i],b[i])])

Measured memory_bytes: 92568
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let k = read::<usize>();
    let mut humans = vec![0; n];
    for i in 0..n {
        humans[i] = read::<i64>();
    }
    humans.sort();
    let mut foods = vec![0; n];
    for i in 0..n {
        foods[i] = read::<i64>();
    }
    foods.sort();
    foods.reverse();
    let mut l = -1;
    let mut r = 1 << 60;
    while r - l > 1 {
        let m = (r + l) / 2;
        let mut sum = 0;
        for i in 0..n {
            let t = m / foods[i];
            sum += std::cmp::max(0, humans[i] - t);
        }
        if sum <= k as i64 {
            r = m;
        } else {
            l = m;
        }
    }
    println!("{}", r);
}


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

using namespace std ;

const int N=2e5+10 ;

int tr[N<<1] , Siz ;
inline void build ( int n ) { for ( Siz=1 ; Siz<=n ; Siz<<=1 ); }
inline void update ( int x , int d )
{
    x+=Siz,tr[x]=max(tr[x],d);
    while ( x>1 ) x>>=1,tr[x]=max(tr[x<<1],tr[x<<1|1]);
}
inline int query ( int l , int r )
{
    int res=0 ;
    for ( l+=Siz-1,r+=Siz+1 ; l^r^1 ; l>>=1,r>>=1 )
    {
        if ( ~l&1 ) res=max(res,tr[l^1]);
        if ( r&1 ) res=max(res,tr[r^1]);
    }
    return res ;
}

int a[N] , b[N] , f[N] ;
int n , m ;
int main ()
{
    int i , T=0 ;
    scanf("%d",&n);
    for ( i=1 ; i<=n ; i++ ) scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
    for ( i=1 ; i<=n ; i++ ) a[i]=lower_bound(b+1,b+m+1,a[i])-b,T=max(T,a[i]);
    build(T);
    int res=0 ;
    for ( i=1 ; i<=n ; i++ ) f[i]=query(a[i],T)+1,update(a[i],f[i]),res=max(res,f[i]);
    printf("%d\n",res);
    return 0 ;
}

Measured memory_bytes: 2176
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long y = sc.nextLong();

		int ans = 0;
		while (x <= y) {
			x *= 2;
			ans++;
		}

		System.out.println(ans);

		sc.close();

	}

}

Measured memory_bytes: 35796
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
x=int(input())
if 400<=x<=599:
    print(8)
elif 600<=x<=799:
    print(7)
elif 800<=x<=999:
    print(6)
elif 1000<=x<=1199:
    print(5)
elif 1200<=x<=1399:
    print(4)
elif 1400<=x<=1599:
    print(3)
elif 1600<=x<=1799:
    print(2)
else:
    print(1)

Measured memory_bytes: 72812
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MN = 200005;
const int Inf = 0x3f3f3f3f;

int N;
char s[MN];
int f[MN], g[MN];

int main() {
	scanf("%s", s + 1), N = strlen(s + 1);
	f[0] = g[0] = g[1] = -Inf;
	f[1] = 1;
	for (int i = 2; i <= N; ++i) {
		f[i] = g[i - 1] + 1, g[i] = i == 2 ? 1 : f[i - 2] + 1;
		if (f[i - 1] > 0 && s[i - 1] != s[i]) f[i] = std::max(f[i], f[i - 1] + 1);
		if (g[i - 2] > 0 && (s[i - 3] != s[i - 1] || s[i - 2] != s[i])) g[i] = std::max(g[i], g[i - 2] + 1);
	}
	printf("%d\n", std::max(f[N], g[N]));
	return 0;
}

Measured memory_bytes: 1920