akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

struct Edge {
    int from, to;
    long long cost;
    Edge(int _to, long long _cost) :
        from(-1), to(_to), cost(_cost) {}
    Edge(int _from, int _to, long long _cost) :
        from(_from), to(_to), cost(_cost) {}
};

template<class T>
vector<T> Bell(const vector<Edge> &edges, int N, int s, T def) {
    vector<T> dist(N, def);
    vector<bool> negative(N);
    dist[s] = 0;
    for(int loop = 0; loop < 2 * N - 1; ++loop) {
        for(auto &e : edges) {
            if(dist[e.from] == INF) continue;
            if(dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                if(loop > N - 1) negative[e.to] = true;
            }
            if(loop > N - 1 && negative[e.from]) negative[e.to] = true;
        }
    }
    for(int i = 0; i < N; ++i) {
        if(negative[i]) dist[i] = -INF;
    }
    return dist;
}

void solve() {
    int N, M, P;
    cin >> N >> M >> P;
    vector<Edge> edges;
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        edges.emplace_back(a, b, P - c);
    }
    auto dist = Bell(edges, N, 0, INF);
    long long ans = -dist[N - 1];
    if(ans == INF) cout << -1 << '\n';
    else if(ans < 0) cout << 0 << '\n';
    else cout << ans << '\n';
}

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


Measured memory_bytes: 512
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int MAXN = 220000;

int n;
int a[MAXN], b[MAXN];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	int fl = 0;
	int mn = int(2e9);
	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		if (a[i] != b[i])
			fl = 1;
		sum += a[i];
		if (a[i] > b[i]) {
			mn = min(mn, b[i]);
		}
	}
	if (!fl) {
		cout << 0 << "\n";
	}
	else {
		cout << sum - mn << "\n";
	}
	return 0;
}



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

void eratosthenes(int n, std::vector<bool> &isPrime){
    isPrime.assign(std::max(n + 1, 2), true);
    isPrime[0] = false;
    isPrime[1] = false;

    for(int i = 4 ; i <= n ; i += 2){
        isPrime[i] = false;
    }
    for(int i = 9 ; i <= n ; i += 6){
        isPrime[i] = false;
    }

    int s = 4;
    for(int i = 5 ; i * i <= n ; i += s){
        if(isPrime[i]){
            for(int j = i * i ; j <= n ; j += i){
                isPrime[j] = false;
            }
        }
        s ^= 6;
    }

    return;
}

#include<iostream>
using namespace std;

int main(){
    vector<bool> isPrime;
    eratosthenes(100000, isPrime);

    vector<int> sum(100001, 0);
    for(int i = 1 ; i <= 100000 ; i += 2){
        if(isPrime[i] && isPrime[(i + 1) / 2]){
            sum[i] = 1;
        }
    }
    for(int i = 1 ; i <= 100000 ; ++i){
        sum[i] += sum[i - 1];
    }

    int q;
    cin >> q;

    vector<int> ans;
    while(q--){
        int l, r;
        cin >> l >> r;
        ans.emplace_back(sum[r] - sum[l - 1]);
    }

    for(auto x : ans){
        cout << x << endl;
    }

    return 0;
}

Measured memory_bytes: 1532
import java.util.*;

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

        for (int i = 0; i < N; i++) {
            P[i] = sc.nextInt();
        }

        int ans = 0;
        int min = 9999999;

        for (int i = 0; i < N; i++) {
            if(min > P[i]){
                min = P[i];
                ans++;
            }
        }

        System.out.println(ans);

    }
}



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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    string S; cin >> S;
    int N = S.length();
    vector<ll> dp(N, 0); //dp[i]: S[i]以降の部分列"BC"の数
    vector<ll> cnt_C(N, 0); //cnt_C[i]: S[i+1]~S[N-1]で'C'が出現する回数
    vector<ll> cnt_Q(N, 0);
    if(S[N-1] == 'C') cnt_C[N-2] = 1;
    else if(S[N-1] == '?') cnt_Q[N-2] = 1;
    for(int i = N-2; i >= 1; i--){
        if(S[i] == 'C'){
            cnt_C[i-1] = cnt_C[i] + 1;
            cnt_Q[i-1] = cnt_Q[i];
        }
        else if(S[i] == '?'){
            cnt_C[i-1] = cnt_C[i];
            cnt_Q[i-1] = cnt_Q[i] + 1;
        }
        else{
            cnt_C[i-1] = cnt_C[i];
            cnt_Q[i-1] = cnt_Q[i];
        }
    }

    ll ans = 0;
    ll fac3[100001];
    fac3[0] = 1;
    for(int i = 1; i <= 100000; i++) fac3[i] = (fac3[i-1]*3) % mod;

    dp[N-1] = 0;
    for(int i = N-2; i >= 0; i--){
        if(S[i] == 'A' || S[i] == 'C') dp[i] = dp[i+1];
        else if(S[i] == 'B'){
            dp[i] = (dp[i+1] + cnt_C[i]*fac3[cnt_Q[i]] + cnt_Q[i]*fac3[cnt_Q[i]-1]) % mod;
        }
        else{
            dp[i] = (dp[i+1]*3 + cnt_C[i]*fac3[cnt_Q[i]] + cnt_Q[i]*fac3[cnt_Q[i]-1]) % mod;
        }
    }
    //S[i-1]までに出てくる'?'の数を知らないときつい
    vector<ll> Q_head(N+1, 0); //Q_head[i]: S[0]が?ならQ_head[1] = 1
    for(int i = 1; i <= N; i++){
        if(S[i-1] == '?') Q_head[i] = Q_head[i-1] + 1;
        else Q_head[i] = Q_head[i-1];
    }
    for(int i = 0; i < N-2; i++) if(S[i] == 'A' || S[i] == '?') ans = (ans + (fac3[Q_head[i]]*dp[i+1] % mod)) % mod;
    cout << ans << endl;
    //rep(i, N) cout << dp[i] << " "; cout << endl;
    return 0;
}

Measured memory_bytes: 4352
import java.util.*;

class Main{
  static Scanner sc = new Scanner(System.in);
  public static void main(String args[]){
    int n = sc.nextInt();
    int b[] = new int[n+1];
    b[0] = Integer.MAX_VALUE;
    b[n] = Integer.MAX_VALUE;
    for(int i=1;i<n;i++){
      b[i]=sc.nextInt();
    };
    int a=0;
    for(int i=0;i<n;i++){
      a+=Integer.min(b[i],b[i+1]);
    }
    System.out.println(a);
  }
}

Measured memory_bytes: 23764
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace D
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int K = int.Parse(input[1]);
            if(N <= K)
            {
                ReadLine();
                WriteLine(N);
                return;
            }

            var s = ReadLine();

            List<int> index = new List<int>();
            index.Add(0);
            int start = int.Parse(s[0].ToString());
            for(int i = 1; i < N; i++)
            {
                if(s[i] != s[i - 1])
                {
                    index.Add(i);
                }
            }
            index.Add(s.Length);
            List<int> num = new List<int>();
            for(int i=0; i < index.Count; i++)
            {
                num.Add(index[Math.Min((i + (2 * K) + ((i + start) % 2)),index.Count - 1)] - index[i]);
            }

            WriteLine(num.Max());
        }
    }
}


Measured memory_bytes: 13536
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using ll = long long;

constexpr static ll MOD = 1000000007ll;
constexpr static int INF = 1 << 28; // for x <= 10^9
constexpr static ll INFL = 1ll << 60; // for x <= 10^19

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

    int len = s.length();
    vector<string> tmp;
    for (int i = 0; i < len; i++) {
        int a = min(k, len - i);
        for (int j = 1; j <= a; j++) {
            tmp.push_back(s.substr(i, j));
        }
    }
    sort(tmp.begin(), tmp.end());
    unique(tmp.begin(), tmp.end());

    cout << tmp[k - 1] << endl;
}


Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

void debug_out() { std::cout << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n)-1); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

template <class T>
inline bool chmin(T &a, T b){
    if (a > b){
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmax(T &a, T b){
    if (a < b){
        a = b;
        return true;
    }
    return false;
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

bool isPalindrome(string s){
    string t = s;
    reverse(all(t));
    return s==t;
}

constexpr ll INF = 1e9+7;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

std::vector<int> Eratosthenes( const int N )
{
    std::vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x,y,z,k; cin >> x >> y >> z >> k;
    vector<ll> a(x),b(y),c(z);
    Rep(i,0,x) cin >> a[i];
    Rep(i,0,y) cin >> b[i];
    Rep(i,0,z) cin >> c[i];
    vector<ll> e;
    Rep(i,0,x){
        Rep(j,0,y){
            e.emplace_back(a[i]+b[j]);
        }
    }
    sort(rall(e));
    vector<ll> ans;
    Rep(i,0,min(k,x*y)){
        Rep(j,0,min(k,z)){
            ans.emplace_back(e[i]+c[j]);
        }
    }
    sort(rall(ans));
    Rep(i,0,k){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 43240
R, G, B, N = map(int,input().split())
count = 0
i_range = N//R+1
j_range = N//G+1

for i in range (N//R+1):
    for j in range (N//G+1):
        if (N - i*R - j*G)%B == 0 and (N - i*R - j*G)>=0:
            count += 1
print(count)

Measured memory_bytes: 40940
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N,s=1;
  cin>>N;
  for(;s*(s+1)/2<N;s++);
  int ans=s*(s+1)/2-N;
  vector<bool> A(s,true);
  for(int i=s;i>0;i--){
    if(ans>=i){
      ans-=i;
      A[i-1]=false;
    }
  }
  for(int i=0;i<s;i++)
    if(A[i])
      cout<<i+1<<endl;
}

Measured memory_bytes: 3628
def bit_fullsearch(target):
    n = len(target)
    ret = []
    for i in range(2**n):
        tmp = []
        for j in range(n):
            if (i>>j)&1:
                tmp.append(target[j])
        ret.append(tmp)
    return ret

h,w,k = map(int,input().split())
C = [list(input()) for _ in range(h)]

col = [i for i in range(h)]
row = [j for j in range(w)]

col = bit_fullsearch(col)
row = bit_fullsearch(row)

now = 0
ans = 0
for i in range(h):
    for j in range(w):
        if C[i][j]=='#':
            now += 1
for y in col:
    for x in row:
        tmp = 0
        for i in range(h):
            for j in range(w):
                flg = False
                if i in y:
                    flg = True
                if j in x:
                    flg = True
                if flg and C[i][j]=='#':
                    tmp += 1
        if now - tmp == k:
            ans += 1
print(ans)

Measured memory_bytes: 71324
//============================================================================
// Name        : hoba.cpp :)
// Author      : (O_O Diab) (Why_not) (el 3AQ)
// Version     :
// Copyright   : please, Don't touch me :(
// Description : problem in C++
// MAIN IDEA   :
//============================================================================
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cerr<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace __gnu_pbds;
using namespace std;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int N = 50 + 5, mod = (int) 1e9 + 7, INF = 0x3f3f3f3f;
int n, A, B;
ll dp[N][N] = { }, x;
vl v;
vector<pair<ld, int>> vv;
ll solve(int idx, int len) {
	if (!len || (idx >= (int) v.size()))
		return 0;
	ll &ret = dp[idx][len];
	if (~ret)
		return ret;
	ret = 0;
	ret = max(ret, solve(idx + 1, len));
	ret = max(ret, solve(idx + 1, len - 1) + v[idx]);
	return ret;
}
ll dp2[N][N] = { };
ll out(int idx, int len) {
	if (!len || idx >= n)
		return 1;
	ll &rf = dp2[idx][len];
	if (~rf)
		return rf;
	rf = 0;
	ll &ret = dp[idx][len];
	if (ret == solve(idx + 1, len))
		rf += out(idx + 1, len);
	if (ret == (solve(idx + 1, len - 1) + v[idx]))
		rf += out(idx + 1, len - 1);
	return rf;
}
int main() {
#ifdef ONLINE_JUDGE
	   FAST;
#endif
	cin >> n >> A >> B;
	lp(i,1,n)
	{
		cin >> x;
		v.pb(x);
	}
	clr(dp, -1);
	clr(dp2, -1);
	lp(i,A,B)
	{
		ll ans = solve(0, i);
		ld d = (ld) ans / (ld) i;
		vv.pb( { d, i });
	}
	sort(all(vv));
	cout << fixed << setprecision(6) << vv.back().F << "\n";
	ll ans = 0;
	for (auto u : vv)
		if (vv.back().F == u.F)
			ans += out(0, u.S);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>

using std::cin;using std::cout;using std::cerr;using std::endl;

#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)

const int mmax = 2e5;
int n,k;
int a[mmax + 10],l = 1e9,r = 0,ans;

bool check(int x){
	int num = 0,t;
	rep(i,1,n){
		t = a[i] / x;
		if(t * x == a[i]) num += t - 1;
		else num += t;
	}
	return (num <= k?1:0);
}

int main(){

	std::ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>n>>k;

	rep(i,1,n){
		cin>>a[i];
		r = std::max(r,a[i]);
	}
	l = 1;
	ans = r;

	while(r - l >=1){
		int m = (l + r) / 2;
		if(check(m)){
			ans = m;
			r = m;
		}
		else{
			l = m + 1;
		}
	}

	cout<<ans;

	return 0;
}

Measured memory_bytes: 4372
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

signed main(){IOS;
	string s,t;cin>>s>>t;
	int a,b; cin>>a>>b;
	string u; cin>>u;
	if(u==s) a--;
	if(u==t) b--;
	cout<<max(a,0ll)<<' '<<max(b,0ll)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int main(void){
    int num_T,num_A;
    int try;
    scanf("%d %d %d",&num_T,&num_A,&try);
    int i;
    for(i=0;i<try;i++){
        if(i%2==0){
            if(num_T%2!=0){
                num_T--;
                num_A+=num_T/2;
                num_T=num_T/2;
            }
            else if(num_T%2==0){
                num_A+=num_T/2;
                num_T=num_T/2;
            }
        }
        else if(i%2!=0){
             if(num_A%2!=0){
                num_A--;
                num_T+=num_A/2;
                num_A/=2;
            }
            else if(num_A%2==0){
                num_T+=num_A/2;
                num_A/=2;
            }
        }
    }
    printf("%d %d",num_T,num_A);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define LIMIT(d_in, d_min, d_max) max(d_min, min(d_max, d_in))
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

struct UnionFind
{
	vector<int> data;
	vector<int> size;

	UnionFind(int n)
	{
		size = vector<int>(n, 1);
		for (int i = 0; i < n; i++)
		{
			data.push_back(i);
		}
	}

	int Root(int n)
	{
		if (data[n] == n)
			return n;

		return Root(data[n]);
	}

	bool Union(int n, int m)
	{
		n = Root(n);
		m = Root(m);

		if (Check(n, m))
			return false;

		if (size[n] < size[m])
			swap(n, m);

		size[n] += size[m];
		data[m] = n;

		return true;
	}

	bool Check(int n, int m)
	{
		return Root(n) == Root(m);
	}

	int Size(int n)
	{
		return size[Root(n)];
	}
};

void execute()
{
	lint N, M;

	cin >> N >> M;
	vector<pair<int, int>> edge(M);
	stack<lint> ans;
	UnionFind tree(N);
	lint full = N * (N - 1) / 2;
	lint connect = 0;

	for (int i = 0; i < M; i++)
	{
		cin >> edge[i].first >> edge[i].second;
		edge[i].first--;
		edge[i].second--;
	}

	for (int i = M - 1; 0 <= i; i--)
	{
		ans.push(full - connect);
		int size_a = tree.Size(edge[i].first);
		int size_b = tree.Size(edge[i].second);

		if (tree.Union(edge[i].first, edge[i].second))
		{
			connect += size_a * size_b;
		}
	}

	for (; !ans.empty();)
	{
		cout << ans.top() << endl;
		ans.pop();
	}

	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 3832
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int N;
vector<int> G[MAX];
int color[MAX];
void dfs(int R, int C) {
	stack<int> S;
	S.push(R);
	color[R] = C;
	while (!S.empty()) {
		int U = S.top(); S.pop();
		for (int i = 0; i < G[U].size(); i++) {
			int V = G[U][i];
			if (color[V] == NIL) {
				color[V] = C;
				S.push(V);
			}
		}
	}
}
void assignColor() {
	int id = 1;
	for (int i = 0; i < N; i++) color[i] = NIL;
	for (int u = 0; u < N; u++) {
		if (color[u] == NIL) dfs(u, id++);
	}
}
int main() {
	int S, T, M, Q;

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> S >> T;
		G[S].push_back(T);
		G[T].push_back(S);
	}
	
	assignColor();
	cin >> Q;

	for (int i = 0; i < Q; i++) {
		cin >> S >> T;
		if (color[S] == color[T]) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}
}


Measured memory_bytes: 9012
#include <stdio.h>
int main(){
    char S[10];
    scanf("%s",S);
    for(int i=0;i<8;i=i+2){
        if((S[i]=='h')&&(S[i+1]=='i')){
            if(S[i+2]=='\0'){
                break;
            }
            continue;
        }
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.util.stream.IntStream;

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

        IntStream NStream = IntStream.range(1, sc.nextInt() + 1);
        System.out.println(NStream.filter(Main::isDigitOdd).count());

    }

    static boolean isDigitOdd(int n) {
        return ((int) Math.log10((double) n) + 1) % 2 != 0;
    }
}

Measured memory_bytes: 26836
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Mod 1000000007
using namespace std;
int n;
int f[5010][5010];
int siz[5010];
int g[5010];
struct Edge{
	int v,nxt;
}e[10010];int tot;
int first[5010];
void build(int u,int v)
{
	e[++tot]=(Edge){v,first[u]};
	first[u]=tot;
	return ;
}
int tmp[5010];
void dfs(int u,int lst)
{
	f[u][1]=1;
	siz[u]=1;
	for(int i=first[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==lst)continue;
		dfs(v,u);
		for(int j=1;j<=siz[u];j++)
			for(int k=1;k<=siz[v];k++)
			{
				tmp[j]=(tmp[j]-(long long)f[v][k]*g[k]%Mod*f[u][j]%Mod+Mod)%Mod;
				tmp[j+k]=(tmp[j+k]+(long long)f[v][k]*f[u][j])%Mod;
			}
		siz[u]+=siz[v];
		for(int j=1;j<=siz[u];j++)
		{
			f[u][j]=tmp[j];
			tmp[j]=0;
		}
	}
	return ;
}
int main()
{
	scanf("%d",&n);
	g[0]=1;
	for(int i=2;i<=n;i++)
		g[i]=(long long)g[i-2]*(i-1)%Mod;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		build(u,v);
		build(v,u);
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=(ans+(long long)f[1][i]*g[i])%Mod;
	printf("%d\n",ans);
	return 0;
}//???

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

lli gcd(lli x, lli y)
{
       if(x<y)swap(x,y);
        if (y == 0) {
                return x;
        } else {
                return gcd(y, x % y);
        }
}

lli lcm(lli a,lli b)
{
   return a*b/gcd(a,b);
}

void func(long long N, long long M, std::vector<long long> a){
    sort(a.begin(),a.end());
    REP(i,0,N)a[i]/=2;
    lli GCD = a[0];
    REP(i,1,N){
        GCD = lcm(GCD,a[i]);
        if(GCD>M){
            cout<<0<<endl;
            return ;
        }
    }
    
    REP(i,0,N){if( (GCD/a[i])%2==0){
        cout<<0<<endl;
        return ;
    }}

    cout<<(M+GCD)/(2*GCD)<<endl;

}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    func(N, M, std::move(a));
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#pragma warning(disable:4996)
#ifdef _MSC_VER
#  define __builtin_popcount __builtin_popcountll
#  define __builtin_popcountll __popcnt
#endif
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
inline void my_io() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout << fixed << setprecision(10);
}
signed main() {
	my_io();
	int k, a, b;
	int ans = 1;
	cin >> k >> a >> b;
	if (a+2>=b) {//すべての回でポケットをたたく
		ans = k + 1;
	}
	else if (k == 1) {
		ans = 2;
	}
	else if (a == 1) {
		int kaisuu_sousa = k / 2;
		ans += (b - a)*kaisuu_sousa;
		if (k % 2 == 1) {
			ans++;
		}
	}
	
	else {//a=1のときも考える
		int ori_k = k;
		k -= (a - 1);
		if (k <= 1) {
			ans = ori_k + 1;
		}
		else {
			k--;
			k--;
			ans = b;
			
			
			int kaisuu_sousa = k / 2;
			ans += kaisuu_sousa * (b - a);
			if (k % 2 == 1) {
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}
/*

3 3 100
*/



Measured memory_bytes: 256
/******************
*  Author: BD747  *
******************/
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n,x;
ll pat[55],tot[55];

ll dfs(ll lev,ll eat){//burger level and level to eat
	if(lev==0 && eat==1)return 1;
	if(lev==0 && eat==0)return 0;
	ll res=0;
	eat--;//B
	if(eat==0)return res;
	if(eat>=tot[lev-1]){
		res+=pat[lev-1];
		eat-=tot[lev-1];
	}else{
		res+=dfs(lev-1,eat);
		return res;
	}//level n-1
	if(eat>=1){
		eat--;
		res++;
	}
	if(eat==0){
		return res;
	}//P
	if(eat>=tot[lev-1]){
		res+=pat[lev-1];
		eat-=tot[lev-1];
	}else{
		res+=dfs(lev-1,eat);
		return res;
	}//level n-1
	eat--;//B
	if(eat>0)cout<<"WHATTHEF**K"<<endl;
	return res;
}

int main(){

	cin>>n>>x;
	pat[0]=1;
	tot[0]=1;
	for(int i=1;i<=50;i++){
		pat[i]=pat[i-1]*2+1;
		tot[i]=tot[i-1]*2+3;
	}
	cout<<dfs(n,x);

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}

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

int main(void) {
  int n;
  vector<ll> v;
  vector<int> h;
  cin>>n;
  for(int i=0; i<n; i++) {
    ll x;
    cin>>x;
    v.push_back(x);
    h.push_back(0);
  }
  int i, j;
  for(i=0; i<n-1; i++) {
    for(j=i+1; j<n; j++) {
      if(v[j]<=v[j-1]) {
	h[i]++;
      } else {
	break;
      }
    }
    i = j-1;
  }
  int m=-1;
  for(int i=0; i<n; i++) {
    m = max(m, h[i]);
  }
  std::cout << m << std::endl;


  return 0;
}



Measured memory_bytes: 1908
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    const S = next()
    const T = next()
    let cnt = 0
    for(let i = 0; i<S.length;i ++){
        if(S[i] !== T[i]) cnt++
    }
    console.log(cnt)

}
Main()


Measured memory_bytes: 33016
import java.io.IOException;
import java.util.Scanner;


public class Main{
	public static void main(String args[]) throws IOException{
		Scanner bf = new Scanner(System.in);
		while(true){
			int N = Integer.parseInt(bf.nextLine());
			if(N==0) break;
			int use = 0;
			int useMax = 0;
			int nonuseMax = 0;
			int max = Integer.MIN_VALUE;
			for(int i=0; i<N; i++){
				int tmp = Integer.parseInt(bf.nextLine());
				max = Math.max(tmp,max);
				use = Math.max(0, use + tmp);
				nonuseMax = Math.max(nonuseMax, useMax);
				useMax = Math.max(use, useMax);
			}
			int ans = Math.max(useMax, nonuseMax);
			if(ans <= 0) ans = max;
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 32476
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define ll long long
#define P pair<int, int>

using namespace std;
int mod = 1000000007;

int K, S;

int main() {
  cin >> K >> S;
  int ans = 0;
  for(int i=0; i<=K; i++) {
    for(int j=0; j<=K; j++) {
      int sum = i+j;
      if (i+j+K >= S && i+j<=S) {
        ans++;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
number = int(input())

AC = 0
TLE = 0
WA = 0
RE = 0
chara = []
for i in range(0,number):
    a = input()
    if(a == 'AC'):
        AC = AC + 1
    elif(a == 'TLE'):
        TLE = TLE + 1
    elif (a == 'WA'):
        WA = WA + 1
    elif (a == 'RE'):
        RE = RE + 1

print('AC x',AC)
print('WA x',WA)
print('TLE x',TLE)
print('RE x',RE)

Measured memory_bytes: 9236
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
const int mx = 200005;
int n, a[mx], l, r = mx;

int main(){
    scanf("%d", &n);
    rep(i,n) scanf("%d", a+i);
    while(l+1 < r){
        int mid = (l+r) / 2, hight = 0;
        bool ok = true;
        map<int, int> mp;
        rep(i,n){
            if(hight < a[i]) hight = a[i];
            else{
                if(mid == 1){
                    ok = false; break;
                }
                hight = a[i];
                while(++mp[hight] >= mid && hight > 0) hight--;
                if(hight == 0){
                    ok = false;
                    break;
                }
            }
            mp.erase(mp.upper_bound(hight), mp.end());
        }
        (ok ? r : l) = mid;
    }
    printf("%d\n", r);
}

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

int main(){
  long N;
  scanf("%ld",&N);
  long ans=0;
  for(long j=1;j<=N;j++){
    long X=N/j;
    ans+=(X*(X+1)/2)*j;
  }
  printf("%ld\n",ans);
}


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

#define ll long long
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main() {
    string S;
    cin >> S;
    int a[26]={0};
    
    for(char i='a';i<='z';i++){
        int cnt =0;
        for(int j=0;j<S.size();j++){
        if(S.at(j) == i) cnt++;
        }
        if(cnt != 0 && i == 'z') {
        cout << "None" <<endl;
        break;
        }
        if(cnt == 0){
            cout << i <<endl;
            break;
        }
    }
}

Measured memory_bytes: 512
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
    let (mut n, k) = read_touple::<usize>();
    let mut ans = 0;
    while n > 0 {
      ans += 1;
      n /= k;
    }

    println!("{}", ans);
}


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

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

using namespace std;

typedef pair<int,int> ii;
struct Data { short h,w,index; };

short H,W,n,b[20],k[20],s[20][20],ans[20][20],buf[20][20];
vector<Data> edge[20][20];
short found;

bool isValid(int x,int y){ return 0 <= x && x < W && 0 <= y && y < H; }

inline void makeEdge(){
  rep(y,H) rep(x,W) {
    rep(i,n){
      for(int hy=1;hy<=k[i];hy++){ 
        if( k[i] % hy ) continue;
        int hx = k[i] / hy;
        bool failed = false, check = false;          
        for(int cy=y;cy<y+hy;cy++)for(int cx=x;cx<x+hx;cx++){
            if( !isValid(cx,cy) ) {
              failed = true;
              goto Skip;
            }
            if( !( s[cy][cx] == 0 || s[cy][cx] == b[i] ) ) {
              failed = true;
              goto Skip;
            }
            if( s[cy][cx] == b[i] ) check = true;
          }
        if( check ) { edge[y][x].push_back((Data){hy,hx,b[i]}); }
      Skip:;
        
      }
    }
  }
  /*
  rep(y,H) rep(x,W) {
    cout << "(" << x  << "," << y << ") ---- " << endl;
    rep(i,(int)edge[y][x].size()){
      cout << "(" << edge[y][x][i].w << "," << edge[y][x][i].h << "," << edge[y][x][i].index << ") ";
      cout << endl;
    }
      cout << endl;
      cout << endl;
  }
  */
}

bool BackTracking(int cx,int cy){
  /*
  cout << cx << "," << cy << endl;
  rep(i,H) {
    rep(j,W) cout << ans[i][j] << " ";
    cout << endl;
  }
    cout << endl;
  */
  if( cx == W-1 && cy == H-1 && ans[cy][cx] != 0 ) {
    ++found;
    if( found == 1 ) rep(i,H) rep(j,W) buf[i][j] = ans[i][j];
    return found >= 2;
  }

  rep(i,(int)edge[cy][cx].size()){
    int h = edge[cy][cx][i].h, w = edge[cy][cx][i].w, index = edge[cy][cx][i].index;
    ii next = ii(-1,-1);
    ii memo = ii(-1,-1);
    rep(y,h) rep(x,w) {
      if( ans[y+cy][x+cx] != 0 ){
        memo = ii(x,y);
        goto Skip2;
      }
      ans[cy+y][cx+x] = index;
    }
    next = ii(-1,-1);
    rep(y,H) rep(x,W){
      if( ans[y][x] == 0 ) {
        next = ii(x,y);
        goto Skip2;
      }
      if( x == W-1 && y == H-1 ) next = ii(W-1,H-1);
    }
  Skip2:;

    if( next != ii(-1,-1) && BackTracking(next.first,next.second) ) return true;
    rep(y,h) rep(x,w) {
      if( x == memo.first && y == memo.second ) goto Skip3;
      ans[cy+y][cx+x] = 0;
    }
  Skip3:;
  }
  return false;
}

inline void compute(){
  makeEdge();
  rep(i,H) rep(j,W) ans[i][j] = 0;
  found = 0;
  if( !BackTracking(0,0) && found == 1 ) {
    rep(i,H) { 
      rep(j,W) {
        if( j ) cout << " ";
        cout << buf[i][j]; 
      } 
      cout << endl; 
    }
  } else puts("NA");
  rep(i,H) rep(j,W) edge[i][j].clear();
}

int main(){
  while( cin >> W >> H >> n, W|H|n ){
    int sum = 0;
    rep(i,n) {
      cin >> b[i] >> k[i];
      sum += k[i];
    }
    rep(i,H) rep(j,W) cin >> s[i][j];
    if( sum != H*W ) { puts("NA"); continue; }
    compute();
  }
  return 0;
}

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

int main(){
  string S;
  int N;
  int count=0;
  cin >>N >>S;
  for(int i=0; i<(N-2); i++){
    if(S.at(i)=='A'){
      if(S.at(i+1)=='B'){
        if(S.at(i+2)=='C'){
          count++;
    }
    }
    }
  }
  cout <<count;
}

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

#define pb push_back
#define pob pop_back
#define st first
#define nd second
#define test cout<<"test"<<endl;
#define mp make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

ll INF = 1e9;
ll mod = 1e9+7;

ll n,m,k,l,r,ans;

ll min(ll a, ll b) {
	return (a<b)? a:b;
}
ll max(ll a, ll b) {
	return a+b-min(a,b);
}

ll a,b,c;
int main() {
	cin>>a>>b>>c>>k;
	if(k%2 == 1) {
		cout<<b-a<<endl;
	}
	else {
		cout<<a-b<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  if((abs(A-B)<=D&&abs(B-C)<=D)||abs(A-C)<=D){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

    int x = 0;
    int ans = 0;
    rep(i, n)
    {
        if (s[i] == 'D')
        {
            x--;
        }
        else
        {
            x++;
        }
        ans = max(ans, x);
    }

    cout << ans << endl;
    return 0;
}


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

constexpr int maxn = 1e7 + 1;

uint32_t a[maxn];

int main() {
  for (int i = 1; i < maxn; ++i) {
    for (int j = i; j < maxn; j += i) {
      a[j] += 1;
    }
  }
  ios::sync_with_stdio(false);
  uint32_t n;
  cin >> n;
  uint64_t ans = 0;
  for (uint32_t i = 1; i <= n; ++i) {
    ans += 1ULL * i * a[i];
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 42712
#include<bits/stdc++.h>
typedef long long int ll;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define p push
#define p1 pop
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair<ll,ll>
#define e 1000000007
using namespace std;
int main()
{
    ll n,m;cin>>n>>m;
    char dp[n][m];
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            cin>>dp[i][j];
    }
    ll ans[n][m];
    ans[0][0]=1;
    for(int i=1;i<m;++i)
    {
        if(dp[0][i]=='.')
            ans[0][i]=ans[0][i-1];
        else
            ans[0][i]=0;
    }
    for(int i=1;i<n;++i)
    {
        if(dp[i][0]=='.')
            ans[i][0]=ans[i-1][0];
        else
            ans[i][0]=0;
    }
    for(int i=1;i<n;++i)
    {
        for(int j=1;j<m;++j)
        {
            if(dp[i][j]=='#')
                ans[i][j]=0;
            else
                ans[i][j]=((ans[i-1][j]%e)+(ans[i][j-1]%e))%e;
        }
    }
    cout<<ans[n-1][m-1];
}

Measured memory_bytes: 9088
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int n,m;
vector<int> p;
vector<Int> two;

int main() {
	while(cin>>n>>m,n){
		p.clear();
		two.clear();
		int i;
		for(i=0;i<n;i++){
			p.push_back(in());
		}
		int j;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				two.push_back(p[i]+p[j]);
			}
			two.push_back(p[i]);
		}
		two.push_back(0);
		sort(two.begin(),two.end());
		Int res=0;
		for(i=0,j=two.size()-1;i<two.size()&&j>=0;){
			if(two[i]+two[j]<=m){
				chmax(res,two[i]+two[j]);
				i++;
			}else{
				j--;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

struct mint {
    long long x;
    mint(long long x=0):x(x % MOD + (0 <= x ? 0 : MOD)) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint& a) { if ((x += a.x) >= MOD) x -= MOD; return *this; }
    mint& operator-=(const mint& a) { if ((x -= a.x) < 0) x += MOD; return *this; }
    mint& operator*=(const mint& a) { (x *= a.x) %= MOD; return *this; }
    mint operator+(const mint& a) const { return mint(x) += a; }
    mint operator-(const mint& a) const { return mint(x) -= a; }
    mint operator*(const mint& a) const { return mint(x) *= a; }

    // for prime mod
    mint inv() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return mint(u);
    }
    mint& operator/=(const mint& a) { return *this *= a.inv(); }
    mint operator/(const mint& a) const { return mint(x) /= a; }
};
istream& operator>>(istream& is, const mint& a){ return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a){ return os << a.x; }

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

    vector<ll> x(N), y(M);
    for (auto &i : x) cin >> i, i += 1e9;
    for (auto &i : y) cin >> i, i += 1e9;

    mint resx = 0;
    for (int j = 1; j < N; ++j) resx += j * x[j];
    for (int i = 0; i < N-1; ++i) resx -= (N - 1 - i) * x[i];

    mint resy = 0;
    for (int j = 1; j < M; ++j) resy += j * y[j];
    for (int i = 0; i < M-1; ++i) resy -= (M - 1 - i) * y[i];

    mint ans = resx * resy;
    cout << ans << endl;
}

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

using namespace std;

const int MAX_W_SIZE = 600, M = 1e9 + 5;
int W[MAX_W_SIZE];
bool dp[M];


int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> W[i];

    for (int stone = 0; stone <= k; stone++) {
        for (int state = 0; state < n; state++) {
            if ((stone - W[state] >= 0) && (!dp[stone - W[state]])) {
                dp[stone] = true;
            }
        }
    }

    dp[k] ? cout << "First" : cout << "Second";

    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n ;
  vector<int> p(n);
  for (int i = 0; i < n; i++ ){
    cin >> p.at(i) ;
  }
  sort(p.begin(),p.end());
  
  int ans = p.at(n/2)-p.at(n/2-1);
  printf("%d\n",ans);
  
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>

using namespace std;

int mem[223][223][22][3];

int neighbors[][3]={
  {5,4,1},
  {6,0,2},
  {7,1,3},
  {8,2,4},
  {9,3,0},
  {0,11,10},
  {1,12,11},
  {2,13,12},
  {3,14,13},
  {4,10,14},
  {15,9,5},
  {16,5,6},
  {17,6,7},
  {18,7,8},
  {19,8,9},
  {10,16,19},
  {11,17,15},
  {12,18,16},
  {13,19,17},
  {14,15,18},
};

int main(){
  fill(***begin(mem),***end(mem),1e9);
  vector<tuple<int,int,int,int> > vs[123];
  vs[0].emplace_back(0,0,0,0);
  for(int i=0;i<=100;i++){
    //    cout<<"vs = "<<vs[i].size()<<endl;
    while(!vs[i].empty()){
      int y,x,f,d;
      tie(y,x,f,d)=vs[i].back();
      vs[i].pop_back();
      if(mem[y+100][x+100][f][d]<1e8){
	//	cout<<i<<endl;
	continue;
      }
      //      cout<<i<<' '<<x<<' '<<y<<' '<<f<<' '<<d<<endl;
      mem[y+100][x+100][f][d]=i;
      int n[3];
      for(int j=0;j<3;j++){
	n[j]=neighbors[f][(d+j)%3];
      }
      for(int j=0;j<3;j++){
	static int dy[][3]={{1,0,0},{0,-1,0}};
	static int dx[][3]={{0,-1,1},{-1,0,1}};
	static int l[][3]={{1,2,0},{2,0,1}};
	int b=(abs(y)+abs(x))%2;
	vs[i+1].emplace_back(y+dy[b][j],x+dx[b][j],n[j],(find(begin(neighbors[n[j]]),end(neighbors[n[j]]),f)-begin(neighbors[n[j]])-l[b][j]+3)%3);
	{
	  int ny=y+dy[b][j],nx=x+dx[b][j],nf=n[j],nd=(find(begin(neighbors[n[j]]),end(neighbors[n[j]]),f)-begin(neighbors[n[j]])-l[b][j]+3)%3;
	  int n[3];
	  for(int j=0;j<3;j++){
	    n[j]=neighbors[nf][(nd+j)%3];
	  }
	  bool flag=false;
	  for(int j=0;j<3;j++){
	    static int dy[][3]={{1,0,0},{0,-1,0}};
	    static int dx[][3]={{0,-1,1},{-1,0,1}};
	    static int l[][3]={{1,2,0},{2,0,1}};
	    int b=(abs(ny)+abs(nx))%2;
	    flag|=y==ny+dy[b][j]&&x==nx+dx[b][j]&&f==n[j]&&d==(find(begin(neighbors[n[j]]),end(neighbors[n[j]]),nf)-begin(neighbors[n[j]])-l[b][j]+3)%3;
	  }
	  if(!flag){
	    cout<<"a"<<' '<<x<<' '<<y<<' '<<f<<' '<<d<<endl;
	  }
	}
      }
    }
  }
  int x=13,y=-13,f=2,d=0;
  for(int i=28;i>0;i--){
      int n[3];
      for(int j=0;j<3;j++){
	n[j]=neighbors[f][(d+j)%3];
      }
    for(int j=0;j<3;j++){
      static int dy[][3]={{1,0,0},{0,-1,0}};
      static int dx[][3]={{0,-1,1},{-1,0,1}};
      static int l[][3]={{1,2,0},{2,0,1}};
      int b=(abs(y)+abs(x))%2;
      int ny=y+dy[b][j],nx=x+dx[b][j],nf=n[j],nd=(find(begin(neighbors[n[j]]),end(neighbors[n[j]]),f)-begin(neighbors[n[j]])-l[b][j]+3)%3;
      if(mem[ny+100][nx+100][nf][nd]==i-1){
	y=ny;
	x=nx;
	f=nf;
	d=nd;
	cout<<i<<' '<<y<<' '<<x<<' '<<f<<' '<<d<<endl;
	break;
      }
    }
  }
    
    
  
  for(int x,y,n;cin>>x>>y>>n,x|y|n;){
    // for(int i=0;i<3;i++){
    //   cout<<mem[y+100][x+100][n][i]<<' ';
    // }
    // cout<<endl;
    cout<<*min_element(begin(mem[y+100][x+100][n]),end(mem[y+100][x+100][n]))<<endl;
  }
}

Measured memory_bytes: 57088
N, Y = map(int, input().split())

flg = False
for i in range(0, N + 1) :
    for j in range(0, N + 1 - i) :
        if i * 10000 + j * 5000 + (N - i - j) * 1000 == Y :
            print(i, j, N - i - j)
            flg = True
            break
            
    if flg == True :
        break
if flg == False :
    print(-1, -1, -1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
//#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define all1(i) begin(i),end(i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false

int main(void){
    
    ll X,K,D;
    cin >> X >> K >> D;
    X = abs(X);
    
    ll Ans;
    if(K%2==0){
        Ans=X;
    }else{
        Ans = min(abs(X-D),abs(X+D));
    }
    
    ll B = X/D;
    B = min(B,K);
    for(ll i = B-3;i<=B+3;i++){
        if(i%2==K%2 && i<=K){
            Ans=min(Ans,abs(X-i*D));
        }
    }
    cout << Ans << endl;
    return 0;
}



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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= n; i--)
#define ll long long
#define pb push_back
#define popb pop_back
#define debug(i) cout << i << endl
using namespace std;
int sz;
string s,s1,s2;
void make(int a){
    REP(i, a){
        if(i % 2 == 0){
            s1.pb('0');
            s2.pb('1');
        }else{
            s1.pb('1');
            s2.pb('0');
        }
    }
}

int main(){
    cin >> s;
    int ans1=0, ans2=0;
    sz = s.size();
    make(sz);

    REP(i,sz){
        if(s[i] != s1[i]) ans1++;
        if(s[i] != s2[i]) ans2++;
    }
    
    cout << min(ans1,ans2) << endl;
    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <utility>
#include <set>
#include <vector>
#include <functional>
#include <map>
#include <queue>
using namespace std;
int main()
{
  long long A,B,C,K;
  cin>>A>>B>>C>>K;
  if (K%2) cout<<B-A<<endl;
  else cout<<A-B<<endl;
  //system("pause");
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;++i)
int main(){
    int n,x;
    while(cin >> n >> x,n){
        int ans = 0;
        FOR(i,1,n+1)FOR(j,i+1,n+1)FOR(k,j+1,n+1){
            if(i+j+k==x) ++ans;
        }
        cout << ans << endl;
    }
}


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

int INF = 1001001001;

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> key;
    rep(i,m){
        int a, b;
        cin >> a >> b;
        int s = 0;
        rep(j,b){
            int c;
            cin >> c;
            --c;
            s |= 1<<c;
        }
        key.emplace_back(s,a);
    }

    vector<int> dp(1<<n, INF);
    dp[0] = 0;
    rep(s,1<<n){
        rep(i,m){
            int t = s | key[i].first;
            int cost = dp[s] + key[i].second;
            dp[t] = min(dp[t], cost);
        }
    }
    int ans = dp.back();
    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def in_rectangle(w, h, x, y, r)
  return (((x-r)>= 0) && ((x+r) <= w) && ((y-r)>= 0) && ((y+r)<=h))
end

values = gets.split(" ").map{ |s| s.to_i}
w = values[0]
h = values[1]
x = values[2]
y = values[3]
r = values[4]

inside = in_rectangle(w, h, x, y, r)
if inside
  print "Yes\n"
else
  print "No\n"
end

Measured memory_bytes: 8692