akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i, MAT.size()){
    REP(j, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

template <typename CLASS1, typename CLASS2>
class HOGE{
  public:
    CLASS1 key;
    CLASS2 value;
    HOGE(void){
      return;
    };
    HOGE(CLASS1 key, CLASS2 value){
      this->key = key;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "key : " << key << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  cin >> N;
  ll ans = 0;
  vll V(N), C(N);
  REP(i, N) cin >> V[i];
  REP(i, N) cin >> C[i];
  REP(i, N){
    ans += max(V[i]-C[i], (ll)0);
  }

  cout << ans << "\n";

  return 0;
}

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

int main() {
  cin.tie()->sync_with_stdio(0);
  
  int n;
  cin >> n;
  
  int sq = 0;
  int s = 0;
  
  for(int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    s += x;
    sq += x*x;
  }
  
  int best = INT_MAX;
  for(int i = 1; i <= 100; ++i) {
    best = min(best, - 2 * s * i + i * i * n);
  }
  cout << best + sq;
}


Measured memory_bytes: 256
import sys
import math
import bisect

def pow_mod(x, n, m):
    if n == 0:
        return 1
    ans = pow_mod(x, n // 2, m) ** 2 % m
    if n % 2 == 1:
        ans = ans * x % m
    return ans

def query_popcount(n):
    ans = 0
    while n:
        ans += n % 2
        n >>= 1
    return ans

def query_value(n):
    if n == 0:
        return 0
    m = query_popcount(n)
    return 1 + query_value(n % m)


def main():
    n = int(input())
    s = input()
    m = 0
    d = {}
    for c in s:
        if c == '1':
            m += 1
    # print('m: %d' % (m))
    if m - 1 != 0:
        val = 0
        for c in s:
            val = val * 2 + ord(c) - ord('0')
            if val >= (m - 1):
                val -= (m - 1)
        d[m-1] = val
    if m + 1 != 0:
        val = 0
        for c in s:
            val = val * 2 + ord(c) - ord('0')
            if val >= (m + 1):
                val -= (m + 1)
        d[m+1] = val
    # print('d: %s' % str(d))
    ans = []
    for i in range(n):
        if s[i] == '0':
            r = (d[m+1] + pow_mod(2, n - 1 - i, m + 1)) % (m+1)
            val = 1 + query_value(r)
            ans.append(val)
        elif s[i] == '1':
            if m - 1 == 0:
                ans.append(0)
            else:
                r = (d[m-1] + (m-1) - pow_mod(2, n - 1 - i, m - 1)) % (m-1)
                val = 1 + query_value(r)
                ans.append(val)

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()


Measured memory_bytes: 11284
#include<bits/stdc++.h>
#define int long long
#define M 1000000007
#define deb(x) cout<<#x<<'='<<x<<endl
using namespace std;
const int N=1e6;
signed main()
{
	int n;
	cin>>n;
	int tot=(n*(n+1))/2;
	int p1=n/3;
	int t1=(p1*(p1+1)*3)/2;
	int p2=n/5;
	int t2=(p2*(p2+1)*5)/2;
	int p3=n/15;
	int t3=(p3*(p3+1)*15)/2;
	int ans=tot-t1-t2+t3;
	cout<<ans<<endl;
}

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

int main()
{
    long int n[3];
    cin >> n[0] >> n[1] >> n[2];
    if(n[0]%2==0 || n[1]%2==0 || n[2]%2==0) cout << 0 << endl;
    else {
        sort(n, n+3);
        cout << n[0] * n[1] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int h, w, n;
int r[3010], c[3010];

ll dp[3010];

ll mod_pow(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return res;
}

ll mod_inverse(ll x) {
    return mod_pow(x, mod-2);
}

const int max_n = 1000000;
ll fact[max_n];
ll fact_inv[max_n];
void calc_fact() {
    fact[0] = 1;
    for (ll i = 1; i < max_n; i++)
        fact[i] = (fact[i-1] * i) % mod;
    fact_inv[max_n-1] = mod_inverse(fact[max_n-1]);
    for (ll i = max_n-2; i >= 0; i--)
        fact_inv[i] = (fact_inv[i+1] * (i+1)) % mod;
}
ll mod_comb(ll n, ll k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return (fact[n] * fact_inv[k] % mod) * fact_inv[n-k] % mod;
}

ll solve() {
    vector<P> vec(n+1);
    for (int i = 0; i < n; i++) vec[i] = make_pair(r[i]-1, c[i]-1);
    vec[n] = make_pair(h-1, w-1);
    sort(ALL(vec));

    calc_fact();
    for (int i = 0; i <= n; i++) {
        P p = vec[i];
        ll num = mod_comb(p.first+p.second, p.first);
        ll sub = 0;
        for (int j = 0; j < i; j++) {
            P q = vec[j];
            if (p.first >= q.first && p.second >= q.second) {
                sub += dp[j] * mod_comb(p.first-q.first+p.second-q.second, p.first-q.first);
                sub %= mod;
            }
        }
        num += mod - sub;
        num %= mod;
        dp[i] = num;
    }
    
    return dp[n];
}

void input() {
    cin >> h >> w >> n;
    for (int i = 0; i < n; i++) cin >> r[i] >> c[i];
}

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

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 19224
H, W = map(int, input().split())
F = [input() for _ in range(H)]

row = []
for i in range(H):
    if '#' not in F[i]:
        row.append(i)

column = []
for j in range(W):
    if all([F[i][j] == '.' for i in range(H)]):
        column.append(j)

ans = ''
for i in range(H):
    ret = False
    for j in range(W):
        if i not in row and j not in column:
            ans += F[i][j]
            ret = True
    if ret:
        ans += '\n'
print(ans)

Measured memory_bytes: 3064
from operator import itemgetter
N, K = map(int, input().split())
l = []
for i in range(N):
    a, b = map(int, input().split())
    l.append([a, b])
l.sort(key = itemgetter(0))
c = 0
for e in l:
    add = e[1]
    c += add
    if c >= K:
        print(e[0])
        break


Measured memory_bytes: 21288
import sys
input = sys.stdin.readline
#-------------------------------------

n = int(input())
a = list(map(int,input().split()))
b = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split())) + [0]*50

total = 0
last = -1
for aa in a:
    total += b[aa]
    if aa == last+1:
        total += c[last]
    last = aa


print(total)

Measured memory_bytes: 38612
using System;
using System.Linq;

public class Test
{
	public static void Main()
	{
		// your code goes here
		
		var b = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();	
		int a = b[0];
		int p = b[1];
		
		int q = a*3 + p;
		
		Console.WriteLine(q/2);
		
	}
}

Measured memory_bytes: 13268
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<bitset>
#include<iomanip>
#include<cctype>
using namespace std;
const int inf = 1001001000;

void print(vector<vector<int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

vector<int> bfs(vector<vector<int>> &graph, int start){
	queue<int> todo;
	vector<int> dist(graph.size(),-1);
	dist[start] = 1;
	todo.push(start);
	while(!todo.empty()){
		int now = todo.front();
		todo.pop();
		for (int i=0;i<graph[now].size();i++){
			int nxt = graph[now][i];
			if (dist[nxt] != -1) continue;
			dist[nxt] = dist[now] + 1;
			todo.push(nxt);
		}
	}
	return dist;
}

int main(){
    while (true){
        int w, h; cin >> w >> h;
        string gomi; getline(cin,gomi);
        if (w == 0 && h == 0) break;
        vector<string> map(2*h+1,string(2*w+1,'1'));
        for(int i = 1; i < 2*h; i++){
            string s;
            getline(cin,s);
            if (i % 2 == 1) s = s + ' ';
            for (int j = 0; j < s.size();j++){
                map[i][j+1] = s[j];
            }
        }
        vector<vector<int>> graph;
        for (int i = 0; i < map.size(); i++){
            for (int j = 0; j < map[i].size(); j++){
                vector<int> a;
                if (i % 2 == 1){
                    if (map[i][j] == ' '){
                        if (map[i][j-1] == '0') a.push_back(i*map[i].size()+j-2);
                        if (map[i][j+1] == '0') a.push_back(i*map[i].size()+j+2);
                        if (map[i-1][j] == '0') a.push_back((i-2)*map[i].size()+j);
                        if (map[i+1][j] == '0') a.push_back((i+2)*map[i].size()+j);
                    }
                }
                graph.push_back(a);
            }
        }
        vector<int> dist = bfs(graph,map[1].size()+1);
        cout << (dist[(map.size()-2)*map[0].size()+map[0].size()-2] != -1 ? dist[(map.size()-2)*map[0].size()+map[0].size()-2] : 0) << endl;
    }

    return 0;
}


Measured memory_bytes: 3248
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main(){
    long long n,k; cin>>n>>k;
    long long a=n%k;
    long long ans=min(a,k-a);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 998244353;

class SegmentTree{
public:
    ll N, unit; 
    vector<ll> data, tree;
    SegmentTree(vector<ll> v, ll u){
        unit = u;
        data = v;
        ll n = data.size();
        N = 1;
        while(N<n)N*=2;
        tree = vector<ll>(N*2,u);
        build();
    }
    void build(){rep(i,N)update(i,data[i]);}
    void update(ll i, ll x){
        i += N-1;
        tree[i]=merge(tree[i],x);
        while(i){
            i = (i-1)/2;
            tree[i]=merge(tree[i*2+1],tree[i*2+2]);
        }
    }
    ll query(ll start, ll end){return query(start, end, 0, 0, N);}
private:
    ll query(ll a, ll b, ll k, ll l, ll r){
        if(r<=a||b<=l)return unit;
        if(a<=l&&r<=b)return tree[k];
        else{
            ll lv = query(a,b,2*k+1,l,(l+r)/2);
            ll rb = query(a,b,2*k+2,(l+r)/2,r);
            return merge(lv,rb);
        }
    }
    ll merge(ll l, ll r){
        return max(l,r);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin>>n;
    vector<P> xd(n);
    rep(i,n){
        ll x,d;cin>>x>>d;
        xd[i]={x,d};
    }
    sort(xd.begin(), xd.end());
    vector<ll> cpx(n);rep(i,n)cpx[i]=xd[i].first;
    vector<ll> ri(n);
    rep(i,n){
        ri[i]=lower_bound(cpx.begin(), cpx.end(), xd[i].first+xd[i].second)-cpx.begin();
    }
    
    vector<ll> ini(n);rep(i,n)ini[i]=i;
    SegmentTree st(ini,0LL);
    vector<ll> dp(n+1,0);
    dp[n]=1;
    for(int i=n-1; i>=0; i--){
        //ri[i]=ri[ri[i]];
        ll q = st.query(i,ri[i]);
        st.update(i,q);
        dp[i]=(dp[q+1]+dp[i+1])%MOD;
        
    }
    cout<<dp[0]<<endl;
    return 0;
}

Measured memory_bytes: 15360
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
bool check(ll a,ll b,ll c){
    if(a==0)return (b%2&&c%2);
    if(b==0)return (a%2&&c%2);
    if(c==0)return (a%2&&b%2);
    return false;
}
int main(){
  V<ll> a(7);
  for(int i=0;i<7;i++)cin>>a[i];
  ll ans=a[1];
  ll d=min({a[0],a[3],a[4]});
      ans+=d*3;
      a[0]-=d;
      a[3]-=d;
      a[4]-=d;
      if(d&&check(a[0],a[3],a[4])){
          ans-=3;
          if(a[0]==0){
              a[3]++;
              a[4]++;
          }
          if(a[3]==0){
              a[0]++;
              a[4]++;
          }
          if(a[4]==0){
              a[0]++;
              a[3]++;
          }
      }
     ans+=a[0]/2*2+a[3]/2*2+a[4]/2*2;
     cout<<ans<<"\n";
}


Measured memory_bytes: 3632
#include <stdio.h>

int main(){
  int N;
  scanf("%d",&N);
  int d[102];
  int S=0;
  for(int i=1;i<=N;i++){
    scanf("%d",d+i);
    S+=d[i];
  }
  int ans=0;
  for(int i=1;i<=N;i++){
    ans+=d[i]*(S-d[i]);
  }
  printf("%d\n",ans/2);
  return 0;
}

Measured memory_bytes: 1724
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int N, K;
    cin >> N >> K;
    int M = 0, g;
    rep(i, N){
        int A; cin >> A;
        if(i == 0) g = A;
        else g = gcd(g, A);
        chmax(M, A);
    }
    cout << ((K%g == 0 && K <= M)? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int ans, i;
string s;
int main() {
	cin >> s;
	for (i = 0, ans = 700; i < s.size(); i++) ans += (s[i] == 'o' ? 100 : 0);
	cout << ans;
	return 0;
}

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

using namespace std;

typedef long long LL;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LC k<<1
#define RC k<<1|1

const int N=110000;
const int M=1100000;
const LL mod=1e9+7;

int flag;
int a,b;
int main()
{
	scanf("%d %d",&a,&b);
	for (int i=1;i<=2000;i++)
	{
		if ((int)(i*0.08)==a&&(int)(i*0.1)==b)
		{
			flag=1;
			printf("%d\n",i);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

//Finding the Top RPS Player
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		for(int T=1;;T++){
			int N = sc.nextInt(), M = sc.nextInt();
			if((N|M)==0)break;
			int[][] c = new int[2][M+1];
			c[0][0] = N;
			for(int x=1,t=1;;t++,x=1-x){
				Arrays.fill(c[x], 0);
				for(int i=0;i<M;i++){
					c[x][i+1]+=c[1-x][i]/2;
					c[x][0]+=c[1-x][i]/2;
					c[x][i]+=c[1-x][i]-c[1-x][i]/2*2;
				}
				if(c[x][M]!=0){
					System.out.println("Case "+T+": "+t); break;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
n = int(input())

for k in range(1, int(n ** 0.5) + 1):
    while n % k == 0:
        i = k
        j = n // k
        break
if j < 1:
    i = 1
    j = n

ans = max((i - 1), 0) + max((j - 1), 0)
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
int a, b, c;
int main(){
  scanf("%d%d%d", &a, &b, &c);
  if(a>c){a^=c; c^=a; a^=c;}
  if(b>c){b^=c; c^=b; b^=c;}
  if(a==5 && b==5 && c==7){
    printf("YES\n");
  }else{
    printf("NO\n");
  }
}


Measured memory_bytes: 128
import numpy as np

H,W = map(int,input().split())
# 周りに壁を、0,1化、壁をTrueで持つ
grid = np.ones((H+2,W+2),dtype=np.bool)
grid[1:-1,1:-1] = (np.array([list(input()) for _ in range(H)]) == '#')

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = x.T
  x = np.ravel(x) # to 1D array
  
  zero_idx = np.nonzero(x)[0]
  zero_span = np.diff(zero_idx) - 1 # 次の0までにある1の個数
  
  y = np.zeros(x.shape[0],dtype=np.int32)
  y[1:][zero_idx[:-1]] = zero_span # 1の個数の加算の起点
  y[zero_idx[1:]] -= zero_span # 1の個数の反映をやめる
  y = y.cumsum()
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)

answer = (F(True) + F(False)).max() - 1
print(answer)

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

void check(string *s, int i, int j, int h, int w){
    int cou = 0;
    for(int k = -1; k < 2; k++){
        for(int l = -1; l < 2; l++){
            int nx = j + l;
            int ny = i + k;
            if(nx >= 0 && nx < w && ny >= 0 && ny < h){
                if(s[ny][nx] ==  '#'){
                    cou++;
                }
            }
        }
    }

    string m = to_string(cou);

    s[i][j] = m[0];
    return ;
}

int main(){
    int h, w;
    cin >> h >> w;

    string s[h];
    for(int i = 0; i < h; i++){
        cin >> s[i];
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] == '.'){
                check(s, i, j, h, w);
            }
        }
    }

    for(int i = 0; i < h; i++){
        cout << s[i] << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int a, b, c, mx;
int main()
{
	cin >> a >> b >> c;
	mx = max(max(a, b), c);
	if((a + b + c - mx) == mx){
		cout << "Yes";
	}else {
		cout << "No";
	}
    return 0;
}


Measured memory_bytes: 256
import sys

N, Y = [int(c) for c in input().split()]
result = (-1, -1, -1)

for a in range(N+1):
    for b in range(N+1-a):
        if 10000 * a + 5000 * b + (N -  a - b) * 1000 == Y:
            print(a, b, (N -  a - b))
            sys.exit()

print(-1, -1, -1)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;


int main()
{
	string s;
	cin>>s;
	int sum=0;
	for(int i=0;i<s.size();i++)
	{
		sum+=s[i]-'0';
	}
	if(sum%9==0)printf("Yes");
	else printf("No");
}

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

using namespace std;
int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	int d[n];
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
	
	int ans = 0;
	for (int x = 0; x < n; x++) {
		for (int y = x + 1; y < n; y++) {
			ans += d[x] * d[y];
		}
	}
	
	cout << ans << endl;
}

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

int main() {
  int a, b, c, d, e, f, g, h, i;
  cin >> a >> b >> c;
  
  d = abs(a-b) + abs(c-b);
  e = abs(a-c) + abs(c-b);
  f = abs(b-a) + abs(a-c);
  g = abs(b-c) + abs(c-a);
  h = abs(c-a) + abs(a-b);
  i = abs(c-b) + abs(b-a);
   
  cout << min(min(min(min(min(d,e),f),g),h),i) << endl;
  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long int ll;
ll max(ll a,ll b)
{
	return a>b?a:b;
}
int main()
{
	ios;
	ll a,b,c,d,ed;
	cin>>a>>b>>c>>d;
	ed=a*c;
	ed=max(ed,a*d);
	ed=max(ed,b*d);
	ed=max(ed,b*c);
	cout<<ed<<'\n';
}

Measured memory_bytes: 3644
A,B,C = [int(i) for i in input().split()]
# a = A % B
# if (C % a == 0) :
#     print("YES")
# else :
#     print("NO")

msg = "NO"
for a in range(1,100) :
    if ((a*A) % B ==C ):
        msg = "YES"
        break

print(msg)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String x = sc.next();
        String a = sc.next();
        String b = sc.next();
       
        if((Math.abs(Integer.parseInt(x) - Integer.parseInt(a)))< (Math.abs(Integer.parseInt(x) - Integer.parseInt(b))))
            System.out.println("A");
        else if((Math.abs(Integer.parseInt(x) - Integer.parseInt(a))) > (Math.abs(Integer.parseInt(x) - Integer.parseInt(b))))
            System.out.println("B");            
        else
            System.out.println("Draw");
    }
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cout <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cout <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
#define jeb() fflush(stdout);

using namespace std;

char s[105];
int n;

VI dupa() {
	VI ans;
	int cur = 1;
	char c = s[0];
	FOR(i,1,n) {
		if (s[i] == c) {
			cur++;
		} else {
			ans.pb(cur);
			cur = 1;
			c = s[i];
		}
	}
	ans.pb(cur);
	return ans;
}

int main() {
	scanf("%s", s);
	make(k);
	n = strlen(s);
	VI v = dupa();
	lint ans = 0;
	if (s[0] != s[n-1]) {
		FOR(i,0,v.size()) ans += v[i]/2;
		ans = (ans * 1LL * k);
	} else {
		if (v.size() == 1) {
			ans = (k * 1LL * v[0])/2;
		} else {
			FOR(i,1,v.size() - 1) ans += v[i]/2;
			ans = ans * 1LL * k;
			ans = (ans + (k-1)*1LL*((v[0]+v.back())/2) + (v[0]/2) + (v.back()/2));
		}
	}
		printf("%lld\n", ans);
}






Measured memory_bytes: 256
def solve():
    N = int(input())
    n = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        if i % 2:
            for j in range(i, N + 1, i):
                n[j] += 1
    print(n.count(8))


if __name__ == "__main__":
    solve()


Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

ld a, b, c, d;

ld f(ld x){
    return a*pow(x, 3)+b*pow(x, 2)+c*x+d;
}

ld binary_search(ld s, ld t, bool rev = false){
    ld l = s, r = t;
    while(r-l > EPS){
        ld m = (l+r)/2;
        bool tmp = f(m) > 0;
        if(tmp^rev) r = m;
        else l = m;
    }
    return l;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> a >> b >> c >> d;
        if(a < 0) a = -a, b = -b, c = -c, d = -d;
        ll D = b*b-3*a*c;
        vector<ld> ans;
        if(D < -EPS){
            ans.pb(binary_search(-200, 200));
        }
        elif(abs(D) < EPS){
            ll x = -b/(3*a);
            if(abs(f(x)) < EPS){
                rep(i, 2) ans.pb(x);
            }
            ans.pb(binary_search(-200, 200));
        }
        else{
            ld s = (-b-sqrt(D))/(3*a), t = (-b+sqrt(D))/(3*a);
            if(f(s) > -EPS){
                ans.pb(binary_search(-200, s));
            }
            if(f(s) > -EPS && f(t) < EPS){
                ans.pb(binary_search(s, t, true));
            }
            if(f(t) < EPS){
                ans.pb(binary_search(t, 200));
            }
        }
        int p = 0, n = 0;
        for(auto &e: ans){
            if(e > 1e-3) p++;
            if(e < -1e-3) n++;
        }
        cout << p << ' ' << n << endl;
    }
}


Measured memory_bytes: 3448
#include <iostream>
using namespace std;
typedef long long ll;

int main(void){
  ll h,w;
  cin >> h >> w;
  if(h == 1 || w == 1){
    cout << 1 << endl;
  }
  else{
    cout << (h*w+1)/2 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int n;

int main(){
	cin>>n;
	ll g=0;
	for(int i=0;i<n;i++){
		int x,k;
		cin>>x>>k;
		if(k<100000){
			while(x%k!=0) x-=(x/k+1);
		}
		else{
			while(x%k!=0){
				int d=x/k+1,t=x/k*k;
				x-=(x-t+d-1)/d*d;
			}
		}
		g^=x/k;
	}
	cout<<(g?"Takahashi":"Aoki")<<endl;
}

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


/*高速化*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


/* define */
#define ALL(V) (V).begine(),(V).end()
#define SORT(V) sort(ALL(V))
#define REV(V) reverse(ALL(V))
#define RSORT(V) SORT(V);REV(V)
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i = 0;i < (int)(n);++i)
#define Rep(i,n) for(int i = 1;i <= (int)(n);++i)
#define Mod(n) n % 1000000007


/* 最大値と最小値に置き換える */
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;}


/* 型定義 */
typedef vector<int> vi;
typedef long long ll;
using Graph = vector<vi>;


/* 定数 */
const double PI = 3.141592;
const double e = 2.6;
const long long Inf = 1LL << 60;
const long long mInf = -Inf;


void calc()
{
    int S,W;
    cin >> S >> W;
    if(S <= W){cout << "unsafe\n";}else{cout << "safe\n";}
}


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

Measured memory_bytes: 3604
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <iostream> 
#include <iomanip>  
#include <string>
#include <sstream>  
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <cstring>
#include <cmath>
#include <cassert>


#define INF              (int)1000000007
#define EPS              1e-9
#define pb               push_back
#define mp               make_pair
#define all(c)           c.begin(), c.end()
#define forall(i,a,b)    for(int i=a;i<(b);++i)
#define trav(a,x)        for(auto & a: x)
#define in(a,b)          ((b).find(a) != (b).end())
#define sz(c)            (int)(c).size()
#define input(a)         for(auto & x : a) cin >> x;

using namespace std;

typedef vector<int>      vi;
typedef pair<int,int>    ii;
typedef vector<vi>       vvi;
typedef vector<ii>       vii;
typedef long long        ll;

#ifdef DEBUG
#define trace(...)       __f(#__VA_ARGS__, __VA_ARGS__)
#define debug(args...)   {dbg,args; clog<<endl;}
#define print_( a )      for( auto & x : a ) clog << x << ' '; clog << '\n';
#define printPair_( a )  for( auto & x : a ) clog << '(' << x.first << ',' << x.second << ')' << ' '; clog << '\n';
#else
#define trace(...)       
#define debug(args...)            
#define print_( a )               
#define printPair_( a )           
#endif

struct debugger {
  template<typename T> debugger& operator , (const T& x) {    
    clog << x << " ";    return *this;    
  }
}dbg;

template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " | ";
    __f(comma + 1, args...);
}

auto ____ =[]() { std::ios::sync_with_stdio(0); cin.tie(0); return nullptr; }();

int main( int argc, char * argv[] ){
  int n; cin >> n; 
  vector<double> v(n);
  input(v);
  print_(v);
  vector<double> p(6005,0), q(6005,0);
  p[3005] = 1; 
  forall(i,0,n){
    forall(j,0,6005){
      if( p[j] < 1e-12 ) continue;
      q[j-1] += p[j]*v[i];
      q[j+1] += p[j]*(1-v[i]);
      trace(i,j, v[i], q[j-1], q[j+1]);
      p[j] = 0;
    }
    swap(p,q);
  }
  cout << setprecision(12) << accumulate(p.begin(), p.begin()+3005, 0.0L) << endl;


  return 0;
}


Measured memory_bytes: 384
def height(a, b, x, y, h):
	return h + abs(a - x) + abs(b - y)

n = int(input())
P = []
for i in range(n):
	x, y, h = map(int, input().split())
	P.append([x, y, h])

# sort by h
P.sort(key=lambda x: x[2], reverse=True)

for i in range(101):
	for j in range(101):
		H = height(i, j, P[0][0], P[0][1], P[0][2])
		for k in range(1, n):
			if max(H - abs(P[k][0] - i) - abs(P[k][1] - j), 0) != P[k][2]:
				break
		else:
			print(i, j, H)
			exit()

Measured memory_bytes: 41200
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

k = ii()
a,b = iim()
flag = False
for i in range(a,b+1):
    if i%k == 0:
        flag = True
        break
print('OK' if flag else 'NG')

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

struct pt
{
	int r,c;
	int dist;
	pt(int r, int c, int dist) : r(r), c(c), dist(dist) { }
};

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

	int h, w; cin >> h >> w;
	vector<vector<bool>> grid(h);
	queue<pt> points;
	for (int r = 0; r < h; ++r)
	{
		grid[r].resize(w);
		for (int c = 0; c < w; ++c)
		{
			char in; cin >> in;
			switch (in)
			{
				case '#':
					grid[r][c] = false;
					points.push(pt(r,c,0));
					break;
				default:
					grid[r][c] = false;
			};
		}
	}
	int mx = 0;
	while (!points.empty())
	{
		pt p = points.front(); points.pop();
		if (grid[p.r][p.c])
			continue;
		mx = max(mx,p.dist);
		grid[p.r][p.c] = true;
		if (p.r > 0)
			points.push(pt(p.r-1,p.c,p.dist+1));
		if (p.c > 0)
			points.push(pt(p.r,p.c-1,p.dist+1));
		if (p.c < w-1)
			points.push(pt(p.r,p.c+1,p.dist+1));
		if (p.r < h-1)
			points.push(pt(p.r+1,p.c,p.dist+1));
	}
	cout << mx << '\n';
}


Measured memory_bytes: 48712
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    string S; cin >> S;
    int cnt = 1;
	FOR(i, 1, N) {
		if (S[i] != S[i-1]) ++cnt;
	}
	cout << cnt << nl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 3748
#include <iostream>
#include <vector>
#include <algorithm>

const int maxn = 52;

int n, k;
int v[maxn], pre[maxn], shu[maxn];

int gao(int l, int r, int d) {
	std::vector<int> x;
	for (int i = 1; i <= l; i++) {
		x.push_back(v[i]);
	}
	for (int i = 0; i < r; i++) {
		x.push_back(v[n-i]);
	}
	std::sort(x.begin(), x.end());
	int res = 0;
	for (int i = 0; i < d; i++) {
		res += x[i];
	}
	return res;
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	std::cin >> n >> k;
	pre[0] = 0;
	for (int i = 1; i <= n; i++) {
		std::cin >> v[i];
		pre[i] = pre[i-1] + v[i];
	}
	shu[n+1] = 0;
	for (int i = n; i >= 1; i--) {
		shu[i] = shu[i+1] + v[i];
	}
	int ans = 0;
	for (int l = 0; l <= n && l <= k; l++) {
		for (int r = 0; l+r <= n && l+r <= k; r++) {
			for (int d = 0; d <= l+r && d+l+r <= k; d++) {
				ans = std::max(ans, pre[l]+shu[n+1-r]-gao(l, r, d));
			}
		}
	}
	std::cout << ans << '\n';
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#include <queue> 
using namespace std;
int N, A[52], B[52]; 
vector<pair<int, int>> E[52]; // make_pair(行き先, log2(コスト))
bool possible(int a, int b, long long int K){
	if(a == b) return true; 
	if(a < b) return false; 
	bool visited[52] = {}; 
	queue<int> que; 
	que.push(a); visited[a] = true; 
	while(que.size()){
		int c = que.front(); que.pop(); 
		for(int i = 0; i < E[c].size(); i++){
			if(!((K >> E[c].at(i).second) & 1)) continue; 
			if(visited[E[c].at(i).first]) continue; 
			visited[E[c].at(i).first] = true; 
			que.push(E[c].at(i).first); 
		}
	}
	return visited[b]; 
}
bool ok(long long int K){
	bool tmp = true; 
	for(int i = 0; i < N; i++){
		tmp &= possible(A[i], B[i], K); 
	}
	return tmp; 
}
int main(){
  cin >> N; 
	for(int i = 1; i <= 50; i++){
		for(int j = 1; j <= i; j++){
			E[i].push_back(make_pair(i % j, j)); 
		}
	}
	for(int i = 0; i < N; i++) cin >> A[i]; 
	for(int i = 0; i < N; i++) cin >> B[i];
	long long int ans = (1LL << 51) - 2;
	if(!ok(ans)){
		cout << -1 << endl; return 0; 
	}
	for(int d = 50; d >= 1; d--){
		long long int tmp = ans - (1LL << d); 
		if(ok(tmp)) ans = tmp; 
	}
 	cout << ans << endl; 
}

Measured memory_bytes: 256
n = int(input())
c = [0]*5
for _ in range(n):
  s = input()
  if s[0]=="M":
    c[0]+=1
  elif s[0]=="A":
    c[1]+=1
  elif s[0]=="R":
    c[2]+=1
  elif s[0]=="C":
    c[3]+=1
  elif s[0]=="H":
    c[4]+=1
    
ans = 0
for i in range(5):
  for j in range(i+1, 5):
    for k in range(j+1, 5):
      ans+=c[i]*c[j]*c[k]
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
#define MAXN 100000

vector <int> sequence;
int n, ldslen;
multiset<int> decrease;

void find_lds()
{
	for (int i = 0; i<n; i++)
	{
		auto it = decrease.lower_bound(sequence[i]);
		if (it == decrease.begin())
			decrease.insert(sequence[i]);
		else
		{
			--it;
			decrease.erase(it);
			decrease.insert(sequence[i]);
		}
	}
	ldslen = decrease.size();
}

int main()
{
	usecppio
	cin >> n;
	sequence.resize(n);
	for (int i = 0; i<n ;i++)
		cin >> sequence[i];
	find_lds();
	cout << ldslen;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;

struct RBQ{
  int n=(1<<18),data[(1<<19)];
  RBQ(){
    memset(data,0,sizeof(data));
  }
  void update(int k,int x){
    k+=n-1;
    data[k]=x;
    while(k>0){
      k=(k-1)/2;
      data[k]=max(data[k*2+1],data[k*2+2]);
    }
  }
  int find(int a,int b,int k=0,int l=0,int r=(1<<18)){
    if(r<=a || b<=l)return 0;
    if(a<=l && r<=b)return data[k];
    int v1=find(a,b,k*2+1,l,(l+r)/2);
    int v2=find(a,b,k*2+2,(l+r)/2,r);
    return max(v1,v2);
  }
};

struct RLQ{
  int n=(1<<18),data[(1<<19)];
  RLQ(){
    fill(data,data+(1<<19),INT_MAX);
  }
  void update(int k,int x){
    k+=n-1;
    data[k]=x;
    while(k>0){
      k=(k-1)/2;
      data[k]=min(data[k*2+1],data[k*2+2]);
    }
  }
  int find(int a,int b,int k=0,int l=0,int r=(1<<18)){
    if(r<=a || b<=l)return INT_MAX;
    if(a<=l && r<=b)return data[k];
    int v1=find(a,b,k*2+1,l,(l+r)/2);
    int v2=find(a,b,k*2+2,(l+r)/2,r);
    return min(v1,v2);
  }
};

signed main(){
  int n,D;
  cin>>n>>D;
  RBQ X,Y;
  RLQ x,y;
  vector<P2>v;
  r(i,n){
    int x,y,z;
    cin>>x>>y>>z;
    v.push_back(P2(z,P(x,y)));
  }
  sort(v.begin(),v.end());
  int l=0,ans=0;
  r(r,n){
    int d=v[r].first;
    int nx=v[r].second.first;
    int ny=v[r].second.second;
    x.update(r,nx);
    X.update(r,nx);
    y.update(r,ny);
    Y.update(r,ny);
    while(d-v[l].first>D)l++;
    int min_x=x.find(l,r+1);
    int max_x=X.find(l,r+1);
    int min_y=y.find(l,r+1);
    int max_y=Y.find(l,r+1);
    ans=max(ans,(max_x-min_x)*(max_y-min_y));
  }
  cout<<ans<<endl;
}


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

int main(){
	int a[100],n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	
	for(int i=0;i<n;i++){
		int v=a[i];
		int j=i-1;
		while(j>=0&&a[j]>v){
			swap(a[j+1],a[j]);
			j--;
		}
		for(int k=0;k<n;k++){
			cout<<a[k];
			if(k==n-1)cout<<endl;
			else cout<<" ";
		}
	}
	return 0;
}

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

//上無限
const long long Inf = 1LL << 60;

//下無限
const long long MInf = -(Inf);


//2要素比較して小さいほうを第一引数に代入
template <class T> inline bool chmin(T&a,T b);
//2要素比較して大きいほうを第一引数に代入
template <class T> inline bool chmax(T&a,T b);

int main()
{
    int N,K;cin >> N >> K;
    long long dp[110000],list[110000];
    for(int i = 0; i < N; i++)
    {
        cin >> list[i];
        dp[i] = Inf;
    }

    dp[0] = 0;
 
    for(int i = 0;i < N;i++)
    {
        for(int j = 1;j <= K;j++)
        {
            chmin(dp[i + j],dp[i] + abs(list[i] - list[i + j]));
        }
    }
    std::cout << dp[N - 1] << endl;
}



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

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	cin >> n;
	vector<int> a(n), cnt(n);
	rep(i, n) {
		cin >> a[i];
		a[i]--;
		cnt[a[i]]++;
	}
	int sum = 0;
	rep(i, n) sum += cnt[i] * (cnt[i] - 1) / 2;
	rep(i, n) cout << sum - cnt[a[i]] + 1 << endl;
}

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

long long x;

int main(){
	cin>>x;
	for(int i=0; i<=120; i++){
		for(int j=0; j<=i; j++){
			if(i*i*i*i*i-j*j*j*j*j==x){
				cout<<i<<" "<<j<<endl;
				break;
			}
			if(i*i*i*i*i+j*j*j*j*j==x){
				cout<<i<<" "<<-j<<endl;
				break;
			}
		}
	}
}


Measured memory_bytes: 3640
#include <stdio.h>

int main()
{
long long int n,sum=0,i;
scanf("%lld",&n);
if(n>0)
{
    i=0;
    while(sum<n)
    {
    i++;
    sum+=i;
    
    }
    printf("%lld",i);
}else{
    i=0;
    while(sum>n)
    {
         i--;
        sum-=i;
       
    }
    printf("%lld",(-1)*i);
}

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
double C(int x,int y){
  double res=1;
  for(int i=0;i<y;i++) res*=x-i;
  for(int i=1;i<=y;i++) res/=i;
  return res;
}
int main(){
  int n,m;
  double l;
  cin >> n >> m >> l;
  int i,j,k,a;
  double p[n],t[n],v[n];
  double b[n][m+1];
  for(i=0;i<n;i++) {
    cin >> p[i] >> t[i] >> v[i];
    for(j=0;j<=m;j++){
      b[i][j]=C(m,j)*pow(p[i]/100,j)*pow(1.0-p[i]/100,m-j);
      //cout << i << "/" << j << ":" << b[i][j] <<"_" << l/v[i]+t[i]*j << endl;
    }
  }
  double ans,x,y;
  for(i=0;i<n;i++){
    ans=0;
    for(j=0;j<=m;j++){
      x=b[i][j];
      for(k=0;k<n;k++){
	if(i==k) continue;
	y=0;
	for(a=m;a>=0;a--){
	  if(l/v[k]+t[k]*a>l/v[i]+t[i]*j) y+=b[k][a];
	  else break;
	}
	//cout << "y:" << y << endl;
	x*=y;
      }
      //cout << "x:" << x << endl;
      ans+=x;
    }
    printf("%.8f\n",ans);
  }
  return 0;
}

Measured memory_bytes: 1284
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

//Code Short
#define REP(i,n) for(int i = 0;i < n;++i)
#define PB(s) push_back(s)
#define DSORT(n) sort(n.begin(),n.end())
#define QECHO(n) cout << n
#define QECHOS(n) cout << n << " "

//Define Math
const double EPS = 1e-10;
const double PI  = acos(-1.0);

using namespace std;
typedef long long ll;
/* prototype */
int EDSum(ll);//各桁の和
vector<int> SOE(int,int);//素数 (Min,Max)
int MinCM(int,int);//最小公倍数(num1,num2)
int MaxCD(int,int);//最大公約数(num1,num2)
vector<int> igets(int);//cin * N
ll nPr(ll,ll); //(n,r)
ll nE(ll); //(n)
ll nCr(ll,ll); //(n,r)

void solve(){
  int A,B,C,X,ans=0;
  cin >> A >> B >> C >> X;
  REP(i,A+1)
    REP(j,B+1)
      REP(k,C+1)
        if(i*500+j*100+k*50==X)
          ++ans;

  cout << ans << endl;
}



int main(void){cin.tie(0);ios::sync_with_stdio(false);solve();}
int EDSum(ll number) {
  int ans = 0;
  while (1) {
    ans += number % 10;
    number /= 10;
    if (number == 0) break;
  }
  return ans;
}

vector < int > SOE(int min, int max) {
  if (min < 2) min = 2;
  vector < int > int_array;
  for (int i = min; i <= max; i++) int_array.push_back(i);
  vector < int > sosu;
  double stop = sqrt(max);
  while (true) {
    sosu.push_back(int_array.front());
    int_array.erase(int_array.begin());
    if (stop < (double)(sosu.back())) break;
    for (int i = 0; i < (int) int_array.size(); i++) {
      if (int_array[i] % sosu.back() == 0)
        int_array.erase(int_array.begin() + i);
    }
  }
  sosu.insert(sosu.end(), int_array.begin(), int_array.end());
  return sosu;
}

int MinCM(int a, int b) {
  int c = a * b;
  if (a < b)
    swap(a, b);
  int r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return c / b;
}

int MaxCD(int a, int b) {
  if (a < b)
    swap(a, b);
  int r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
vector < int > igets(int N) {
  vector < int > A;
  int temp;
  for (int i = 0; i < N; ++i) {
    cin >> temp;
    A.push_back(temp);
  }
  return A;
}

ll nPr(ll n, ll r) {
  ll ans = 1;
  r = n - r;
  while (n != r) {
    ans *= n;
    --n;
  }
  return ans;
}

ll nE(ll n) {
  return nPr(n, n);
}

ll nCr(ll n, ll r) {
  if (r == 0) return -1;
  else {
    if (0 != n - r && n - r < r) r = n - r;
    return nPr(n, r) / nE(r);
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int gcd(int x, int y) {
  if(y>x)    return gcd( y, x );
  if(x%y==0) return y;
  else       return gcd( y, x%y );
}
int main() {
  int N; cin>>N;
  vector<int> A(N); for(auto& x:A) cin>>x;
  int x=A.front();
  for(int i=1; i<N; ++i) x=gcd(x,A[i]);
  cout<< x <<endl;
}

Measured memory_bytes: 640
fun main(args: Array<String>) {
    val (n, K) = listOfLong()
    val N = n.toInt()
    val A = listOfLong()
    var x = 0L
    val DIGIT = 40
    for (i in DIGIT - 1 downTo 0) {
        var count = 0
        for (j in 0 until N) count += 1 and (A[j] shr i).toInt()
        if (count <= N / 2) if ((x or (1L shl i)) <= K) x = x or (1L shl i)
    }
    var sum = 0L
    for (i in 0 until N) sum += x xor A[i]
    println(sum)
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfLong() = listOfString().map(String::toLong)

Measured memory_bytes: 74156