akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <assert.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, k, a[101], dp[101][100001], ps[100001];
void init_ps(int i) {
	ps[0] = dp[i][0];
	for (int j = 1; j <= k; j++) {
		ps[j] = (ps[j - 1] + dp[i][j]) % MOD;
	}
}
int get_sum(int l, int r) {
	return (ps[r] - ((l > 0) ? ps[l - 1] : 0) + MOD) % MOD;
}
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		init_ps(i - 1);
		for (int j = 0; j <= k; j++) {
			dp[i][j] = get_sum(max(j - a[i], 0), j);
		}
	}
	printf("%d\n", dp[n][k]);
	return 0;
}

Measured memory_bytes: 40064
N = int(input())
lists = list(map(int, input().split()))

dic = {}
for i in lists:
    if i in dic.keys():
        dic[i] += 1
    else:
        dic[i] = 1

for i in range(1, N+1):
    if i in dic.keys():
        print(dic[i])
    else:
        print(0)

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

int main()
{
	int a[4][13];
	for (int i = 0; i <= 3; i++)
	{
		for (int j = 0; j <= 12; j++)
		{
			a[i][j] = j + 1;
		}
	}
	char x;
	int n, y;
	cin >> n;
	for (int k = 1; k <= n; k++)
	{
		cin >> x >> y;
		if (x == 'S') a[0][y - 1] = 0;
		if (x == 'H') a[1][y - 1] = 0;
		if (x == 'C') a[2][y - 1] = 0;
		if (x == 'D') a[3][y - 1] = 0;
	}
	for (int i = 0; i <= 3; i++)
	{
		for (int j = 0; j <= 12; j++)
		{
			if (a[i][j] != 0)
			{
				if (i == 0) cout << 'S' << " " << j + 1 << endl;
				if (i == 1) cout << 'H' << " " << j + 1 << endl;
				if (i == 2) cout << 'C' << " " << j + 1 << endl;
				if (i == 3) cout << 'D' << " " << j + 1 << endl;
			}
		}
	}
}



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

const int mxN = 3010;
int N, a[mxN];
ll dp[mxN][mxN][2];
bool vis[mxN][mxN][2];

ll recursion(int l, int r, int t) {
	if (l > r)
		return 0;
	if (vis[l][r][t]) {
		return dp[l][r][t];
	}
	vis[l][r][t] = true;
	if (t == 0) {
		dp[l][r][t] = max(a[l] + recursion(l + 1, r, 1), a[r] + recursion(l, r - 1, 1));
	} else {
		dp[l][r][t] = min(-a[l] + recursion(l + 1, r, 0), -a[r] + recursion(l, r - 1, 0));
	}
	return dp[l][r][t];
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> a[i];
	ll answer = recursion(0, N - 1, 0);
	cout << answer;

	return 0;
}

Measured memory_bytes: 102364
(let* ((lst (concatenate 'list (read-line)))
       (a (car lst))
       (b (caddr lst)))

  (format t "~A~%"
          (cond ((and (char= a #\H) (char= b #\H)) #\H)
                ((and (char= a #\D) (char= b #\H)) #\D)
                ((and (char= a #\H) (char= b #\D)) #\D)
                ((and (char= a #\D) (char= b #\D)) #\H))))


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

int main(){
    int n;  cin >> n;
    vector<int> r(n);
    for(int i=0; i<n; i++) cin >> r.at(i);
    int cnt=0;
    for(int i=0; i<n; i++){
        int ix = r.at(i)-1;
        if(i == r.at(ix)-1) cnt += 1;
    }
    cout << cnt/2 << endl;
}




Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<queue>
#include<string>
#include<stack>
using namespace std;
typedef long long int llint;
int main(){
	llint N;
	cin >> N;
	vector<char> S(N+1);
	for(llint i=0;i<N;i++){
		cin >> S[i];
	}
	sort(S.begin(),S.end());
	
	llint ans = 0;
	for(llint i=0;i<N-1;i++){
		if(S[i]!=S[i+1]){
			ans++;
		}
	}
	
	if(ans == 3){
		cout << "Three" << endl;
	}else{
		cout << "Four" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)

#define endl "\n"
#define pb push_back
#define elif else if
#define coutdb fixed

#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};

typedef long long ll;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

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

	string s;
	int k;
	set<string> st;

	cin >> s >> k;

	REP(i, s.size()){
		REP(j, k+1){
			string t = s.substr(i, j);
			st.insert(t);
		}
	}

	auto itr = st.begin();
	while(k != 0){
		itr++;
		k--;
	}
	cout << *itr << endl;

	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

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

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

const int MAX_N = 5010;
int a[MAX_N][MAX_N];

int getSum(int r1, int c1, int r2, int c2) {
    return a[r1][c1] - a[r1][c2] - a[r2][c1] + a[r2][c2];
}

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

    int n, m;
    cin >> n >> m;
    vector<Pii> p(n);
    map<int, int> mpx;
    map<int, int> mpy;
    rep(i, n) {
        cin >> p[i].first >> p[i].second;
        mpx[p[i].first] = 0;
        mpy[p[i].second] = 0;
    }

    V vx;
    V vy;
    int idx = 0;
    for (auto&& q : mpx) {
        vx.emplace_back(q.first);
        q.second = idx++;
    }
    int idy = 0;
    for (auto&& q : mpy) {
        vy.emplace_back(q.first);
        q.second = idy++;
    }

    rep(i, n) {
        a[mpx[p[i].first]][mpy[p[i].second]]++;
    }

    rrep(i, n) {
        rrep(j, n) {
            a[i][j] += a[i][j + 1];
        }
    }

    rrep(j, n) {
        rrep(i, n) {
            a[i][j] += a[i + 1][j];
        }
    }

    rep(i, m) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int r1, c1, r2, c2;
        r1 = lower_bound(all(vx), x1) - vx.begin();
        c1 = lower_bound(all(vy), y1) - vy.begin();
        r2 = upper_bound(all(vx), x2) - vx.begin();
        c2 = upper_bound(all(vy), y2) - vy.begin();
        cout << getSum(r1, c1, r2, c2) << endl;
    }


}

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

int main() {
  long long a, b, c;
  cin >> a >> b >> c;
  
  long long k = c - a - b;
  if(k <= 0) cout << "No" << endl;
  else if(k*k > 4*a*b) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a,b;
  cin >> a>>b;
  cout << a*b/2 << endl;
}

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

using namespace std;

using ll = long long;

bool Check(const int i, const int j, const int h, const int w,
           const vector<string> &a) {

    bool is_delete = true;
    for (int k = 0; k < w; ++k)
        if (a[i][0] != a[i][k]) is_delete = false;

    if (is_delete) return false;
    is_delete = true;
    for (int k = 0; k < h; ++k)
        if (a[0][j] != a[k][j]) is_delete = false;

    return !is_delete;
}

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

    int h, w;

    cin >> h >> w;
    vector<string> a(h);
    for (int i = 0; i < h; ++i) cin >> a[i];

    for (int i = 0; i < h; ++i) {
        bool is_delete = true;
        for (int j = 0; j < w; ++j) {
            if (a[i][j] == '#' || Check(i, j, h, w, a)) {
                cout << a[i][j];
                is_delete = false;
            }
        }
        if (!is_delete) cout << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int i, n, a, max = 0, min = 0;
    long sum = 0;
    
    scanf("%d", &n);
    
    for (i = 0; n > i; i++) {
        scanf("%d", &a);
        
        if (i == 0) {
            max = a;
            min = a;
            sum = a;
        } else {
            if (max < a) {
                max = a;
            }
            if (min > a) {
                min = a;
            }
            sum = sum + a;
        }
    }
    
    printf("%d %d %ld\n", min, max, sum);
    
    return 0;
}

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

int main(){
	long long int test=1;
	//cin>>test;
	while(test--){
	    int n;
	    cin>>n;
	    set<string> s;
	    for(int i=0;i<n;i++){
	        string ss;
	        cin>>ss;
	        s.insert(ss);
	    }
	    cout<<s.size()<<endl;
	}
	return 0;
}

Measured memory_bytes: 19104
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,x,m=map(int,input().split())
    l=[]
    ans=0
    cnt=0
    while (x not in l)and(cnt<=n):
      l.append(x)
      ans+=x
      cnt+=1
      x=(x**2)%m
    for i in range(len(l)):
      if x==l[i]:
        break
    lc=l[i:].copy()
    lc_cnt=(n-cnt)//len(lc)
    ans+=lc_cnt*sum(lc)+sum(lc[:(n-cnt)-lc_cnt*len(lc)])
    print(ans)

if __name__ == '__main__':
    resolve()

Measured memory_bytes: 68604
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<queue>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int main() {
	string S;
	cin >> S;
	if (S.size() >= 4 && S.substr(0, 4) == "YAKI") cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(), m = scanner.nextInt();
		int[][] a = new int[n][m];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				a[i][j] = scanner.nextInt();
			}
		}
		int[] b = new int[m];
		for (int i = 0; i < m; ++i) {
			b[i] = scanner.nextInt();
		}
		int result[] = new int[n];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				result[i] += a[i][j] * b[j];
			}
		}
		for (int i : result) {
			System.out.printf("%d\n", i);
		}
	}
}



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

using P = pair<int, int>;

vector<P> next(int y, int x) {return {{y-1, x-1}, {y-1, x}, {y-1, x+1}, {y, x-1}, {y, x+1}, {y+1, x-1}, {y+1, x}, {y+1, x+1}};}

int main() {
  int H, W;
  cin >> H >> W;

  auto valid = [&](auto y, auto x) {return 0 <= y && y < H && 0 <= x && x < W;};

  vector<vector<int>> hp(H, vector<int>(W)), flat(H, vector<int>(W));

  for(auto i = 0; i < H; ++i) for(auto j = 0; j < W; ++j) {
    char c;
    cin >> c;
    hp[i][j] = (c == '.') ? 0 : (c - '0');
  }

  queue<P> cur, nex;
  for(auto i = 0; i < H; ++i) for(auto j = 0; j < W; ++j) if(hp[i][j] <= flat[i][j]) cur.emplace(i, j);
  for(auto step = 0; ; ++step) {
    if(cur.empty()) {cout << step - 1 << endl; break;}
    while(!cur.empty()) {
      int y, x;
      tie(y, x) = cur.front();
      cur.pop();
      for(auto p: next(y, x)) if(valid(p.first, p.second)) if(++flat[p.first][p.second] == hp[p.first][p.second]) nex.emplace(p);
    }
    swap(cur, nex);
  }
}

Measured memory_bytes: 10824
#coding:utf-8

n = int(input().rstrip())
tatemono=[
[[0 for i in range(10)],[0 for i in range(10)],[0 for i in range(10)]],
[[0 for i in range(10)],[0 for i in range(10)],[0 for i in range(10)]],
[[0 for i in range(10)],[0 for i in range(10)],[0 for i in range(10)]],
[[0 for i in range(10)],[0 for i in range(10)],[0 for i in range(10)]]]

for i in range(n):
    b,f,r,v = [int(i) for i in input().rstrip().split(" ")]
    tatemono[b-1][f-1][r-1] += v

for i in range(3):
    for j in range(3):
        print(" " + " ".join(list(map(str, tatemono[i][j]))))

    print("####################")

for i in range(3):
    print(" " + " ".join(list(map(str, tatemono[3][i]))))

Measured memory_bytes: 7744
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> vec(n, make_pair(0, 0));
    REP(i, m) {
        int index;
        string judge;
        cin >> index >> judge;
        if (vec[index-1].first == 1) continue;
        if (judge == "AC") vec[index-1].first = 1;
        else vec[index-1].second++;
    }

    int cor_count = 0, penalty = 0;
    for (auto elem : vec) {
        cor_count += elem.first;
        penalty += elem.second * elem.first;
    }

    cout << cor_count << " " << penalty << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) for(auto x:obj)cout<<x<<' ';cout<<endl;
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int a,b;
	cin>>a>>b;
	// if(a*b<=0){cout<<"Zero"<<endl; return 0;}
	// if(a>0){cout<<"Positive"<<endl; return 0;}
	// if(a==b){cout<<"Positive"<<endl; return 0;}
	// if(!((b-a+1)%2))cout<<"Positive"<<endl;
	// else cout<<"Negative"<<endl;

	if(0<a && a<=b){cout<<"Positive"<<endl; return 0;}
	if(b<0){
		if((b-a+1)%2){cout<<"Negative"<<endl;}
		else {cout<<"Positive"<<endl;}
		return 0;
	}
	cout<<"Zero"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;
string s;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> s;
  for(int i=0; i<sz(s); i+=2) cout << s[i];
  cout << endl;
}

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

int d[110];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> d[i];
    sort(d, d+n, greater<int>());

    int counter = 1;
    for (int i=0; i<n; i++) {
        if (i>0) {
            if (d[i]!=d[i-1]) {
                counter++;
            }
        }
    }
    cout << counter << endl;
}



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

// 0-indexed
template <typename T>
struct BinaryIndexedTree {
    int n;
    vector<T> data;

    BinaryIndexedTree(int _n) : n(_n) { data.assign(n + 1, 0); }

    inline void add(int k, T x) {
        assert(0 <= k && k < n);
        for (int i = k + 1; i <= n; i += i & -i) data[i] += x;
    }
    // [0, k)
    inline T sum(int k) {
        assert(0 <= k && k <= n);
        T s = 0;
        for (int i = k; i > 0; i -= i & -i) s += data[i];
        return s;
    }
};

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

    vector<BinaryIndexedTree<int>> bits(26, BinaryIndexedTree<int>(n));
    for (int i = 0; i < n; i++) {
        bits[s[i] - 'a'].add(i, 1);
    }
    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i;
            char c;
            cin >> i >> c, i--;
            bits[s[i] - 'a'].add(i, -1);
            s[i] = c;
            bits[s[i] - 'a'].add(i, 1);
        } else {
            int l, r;
            cin >> l >> r, l--, r--;
            int sum = 0;
            for (int i = 0; i < 26; i++) {
                sum += (bits[i].sum(r + 1) - bits[i].sum(l) > 0);
            }
            cout << sum << endl;
        }
    }
}

Measured memory_bytes: 53636
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()

    for i in range(3):
        if s[i] == s[i+1]:
            print("Bad")
            sys.exit()
    else:
        print("Good")



if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
#include<stdio.h>

// iwana{a c } yamame{ b d }

//  hiroshi、健次郎が勝ちなら kenjiro 、引き分けなら even と１行に出力する。


int main( void )
{
	int Aiwasi ,Biwasi ;
	int Ayamame ,Byamame ;

	scanf( "%d %d %d %d" ,&Aiwasi ,&Ayamame ,&Biwasi ,&Byamame ) ;

	int a ,b ,c ,d ;
	scanf( "%d %d %d %d" ,&a ,&b ,&c ,&d ) ;

	int A = (Aiwasi * a + (Aiwasi / 10) * c) + (Ayamame * b + (Ayamame / 20 ) * d) ;
	int B = (Biwasi * a + (Biwasi / 10) * c) + (Byamame * b + (Byamame / 20 ) * d) ;

	if( A == B )
	{	puts( "even" ) ;	}

	else if( A < B )
	{	puts( "kenjiro" ) ;	}

	else
	{	puts( "hiroshi" ) ;	}

	return 0 ;
}


Measured memory_bytes: 2696
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

ll dp[3003][3003];
int n;
vector<int> a;

ll dfs(int l, int r, int key) { // 数列の [l, r], どっちがとる
  if (dp[l][r] != -1) return dp[l][r];
  if (l == r) return dp[l][r] = (key == 0 ? a[l] : -a[l]);

  ll ret;
  ret = dfs(l + 1, r, key ^ 1) + (key == 0 ? a[l] : -a[l]);
  if (key == 0) {
    chmax(ret, dfs(l, r - 1, key ^ 1) + a[r]);
  } else {
    chmin(ret, dfs(l, r - 1, key ^ 1) - a[r]);
  }

  return dp[l][r] = ret;
}

void solve() {
  cin >> n;
  a.resize(n);
  rep(i, n) cin >> a[i];
  // 後退解析
  fill_n(*dp, 3003 * 3003, -1);
  cout << dfs(0, n - 1, 0) << endl;
  // rep(i, n) { rep(j, n) cout << dp[i][j] << " "; cout << endl; }
}


Measured memory_bytes: 70912
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long 
int a[N],b[N],c[N];
ll sizb[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);
	int p1=1;
	for(int i=1;i<=n;i++){
		while(c[p1]<=b[i]&&p1<=n) p1++;
		sizb[i]=n-p1+1;
	}
	for(int i=n;i>=1;i--) sizb[i]+=sizb[i+1];
	p1=1;
	ll ans=0;
	for(int i=1;i<=n;i++){
		while(b[p1]<=a[i]&&p1<=n) p1++;
		ans+=sizb[p1];
	}
	cout<<ans;
	return 0;
}

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

int main(){
	int a[4];
	scanf("%d%d%d%d",a,a+1,a+2,a+3);
	std::sort(a,a+4);
	puts(a[0]==a[1]&&a[2]==a[3] ? "yes" : "no");
}

Measured memory_bytes: 2580
#include <bits/stdc++.h>
using namespace std;
// types
typedef long long ll; 
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
// IO
#define fo(i, n) for (int i = 0; i < n; i++)
#define fo1(i, n) for (int i = 1; i <= n; i++)
#define sc(n) scanf("%d", &n) 
#define sca(a, n) fo(i, n) sc(a[i])
#define pd(a) printf("%d ", a)
#define pld(a) printf("%d\n", a)
#define pda(a, n) fo(i, n) pd(a[i])
#define pl printf("\n")
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b) 
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
// math
const ll mod = 1e9+7;
template<typename T> T gcf(T a, T b) {return (b == 0) ? a : gcf(b, a%b);} 
template<typename T> T lcm(T a, T b) {return (a*b)/gcf(a, b);}
template<typename T> T sumTo(T x) {return x * (x+1) / 2;}
template<typename T> T sumSquaresTo(T x) {return x * (x+1) * (2*x+1) / 6;}
template<typename T> T ceilDiv(T n, T d) {return (n+d-1)/d;}

void solve() {
    int a, b;
    cin >> a >> b;
    pd(ceilDiv(b-1, a-1));
}

int main() {
    int t = 1;
    //scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
char a[55][55], b[55][55];
int cont;
int main(){
	while(~scanf("%d %d", &n, &m)){
		cont = 0;
		bool flag = false;
		for(int i = 1; i <= n; i++)
			scanf("%s", a[i] + 1);
		for(int i = 1; i <= m; i++)
			scanf("%s", b[i] + 1);
		for(int i = 1; i <= n - m + 1; i++){
			for(int j = 1; j <= n - m + 1; j++){
				cont = 0;
				for(int k = 1; k <= m; k++)
					for(int l = 1; l <= m; l++)
						if(a[i + k - 1][j + l - 1] == b[k][l]) cont++;
				if(cont == m * m) flag = true;
			}
		}
		if(flag) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    ll x, y; cin >> x >> y;
    int ans = 0;

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

    cout << ans << endl;
}

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

int main() {
    int n, k, ans = 0;  cin >> n >> k;
    int h[n];
    rep(i,n)  cin >> h[i];

    rep(i,n) {
        if (h[i] >= k)  ans++;
    }

    cout << ans << endl;
}

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

using namespace std;
#define forn(i,a,n) for(i=a;i<n;i++)

int getvalue(vector<int>&a,vector<int>&b,vector<int>&c,int n)
{
	vector<vector<int>>dp(n,vector<int>(3,0));
	dp[0][0]=a[0];dp[0][1]=b[0];dp[0][2]=c[0];
	int i;
	forn(i,1,n)
	{
		dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
		dp[i][1]=max(dp[i-1][2]+b[i],dp[i-1][0]+b[i]);
		dp[i][2]=max(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
	}
	return max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}

int32_t main(void)
{
	int n,i,j;
	cin>>n;
	vector<int>a(n),b(n),c(n);
	int ans=0;
	forn(i,0,n)cin>>a[i]>>b[i]>>c[i];
	ans=getvalue(a,b,c,n);
	cout<<ans<<endl;
}

Measured memory_bytes: 9808
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();  
        String s = r.s();
        String t = r.s();
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        Arrays.sort(sc);
        Arrays.sort(tc);
        char[] temp = new char[tc.length];
        for(int i = 0; i < tc.length; i++)
            temp[i] = tc[tc.length-1-i];
        tc = temp;
        s = new String(sc);
        t = new String(tc);
        println(s.compareTo(t) < 0 ? "Yes" : "No");
    }
    static class EdgeList{
        int id;
        ArrayList<int[]> list = new ArrayList<>();
        int d;
        EdgeList(int n){
            id = n;
        }
        void add(int[] a){
            list.add(a);
        }
        int size(){
            return list.size();
        }
        void setD(int d){
            this.d = d;
        }
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}


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

int main()
{
  int N;
  int len = 0;
  int maxlen = 0;
  
  cin >> N;
  vector<long> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H.at(i);
  }
  for (int i = 0; i < H.size(); i+=len+1) {
    len = 0;
    for (int j = i; j < H.size() - 1; j++) {
      if (H.at(j) < H.at(j+1)) {
        break;
      }
      len++;
    }
    maxlen = max(maxlen, len);
  }
  cout << maxlen << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long n; cin>>n;
    long long a,b,c,d,e; cin>>a>>b>>c>>d>>e;
    long long minn=min({a,b,c,d,e});
    cout<<((n+minn-1)/minn)+4<<endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a) for (ll i = 0; i < (a); ++i)
#define pb push_back
#define all(v) v.begin(),v.end()
#define sort_1(v) sort(v.begin(),v.end())
#define sort_2(v) sort(v.begin(),v.end(),greater<ll>())
#define reverse(v) reverse(v.begin(),v.end())
typedef long long ll;
typedef long double la;
using namespace std;
 
int main(){
  int n;
  cin >> n;
  vector<pair<int, int>> p;
  for(int i=1;i<n+1;i++){
    int a;
    cin >> a;
    p.emplace_back(a,i);
  }
  sort_1(p);
  rep(i,p.size()){
    cout << p[i].second << " ";
  }
  cout << endl;
}

Measured memory_bytes: 1780
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
RL = [[0, 0] for _ in range(N)]
for i in range(N):
    left = XL[i][0] - XL[i][1]
    right = XL[i][0] + XL[i][1]
    RL[i][0] = left
    RL[i][1] = right
 
RL.sort(key=lambda x: x[1])
now_right = RL[0][1]
cnt = 0
for i in range(1, N):
    if now_right <= RL[i][0]:
        now_right = RL[i][1]
    else:
        cnt += 1
print(N - cnt)

Measured memory_bytes: 44496
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  long long X;
  scanf("%lld", &X);
  ll t = 100;
  for (ll i = 1; i < 10000; ++i)
  {
    t *= 1.01;
    if (t >= X)
    {
      cout << i << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 3256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,flag=0;cin>>n;
  ll a[n]; for(int i=0;i<n;i++){cin>>a[i]; if(!a[i]){flag=1;}}
  if(flag){cout<<0<<endl; return 0;}
  ll val=(ll)1e18,product=1,rem;
  for(int i=0;i<n;i++){
    rem=val/product;
    if(a[i]>rem){ product=-1;break;}
    else{product*=a[i];}
  }
  cout<<product<<endl;
  return 0;
}

Measured memory_bytes: 4388
N, K = map(int,input().split())
# aの桁数
a = len(bin(K))-2
c = 0
# print(a)
# 引いたときにK-1以下である確率
prob1 = min(1,(K-1)/N)
prob2 = 1-prob1

cnt = 0
ans = 0
while (K-1)//(2**cnt) > 0:
    #そこに収まる数(maxがN)
    n = min(N, (K-1)//(2**cnt)) - (K-1)//(2**(cnt+1))
    if n > 0:
       ans += n*1.00/(N*2**(cnt+1))
    #    print(cnt+1,n,ans)
    cnt+=1
    
print(ans+prob2)

Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc := NewScanner(os.Stdin)

	n := sc.ReadLine().Int()
	switch n % 10 {
	case 3:
		fmt.Println("bon")
	case 2, 4, 5, 7, 9:
		fmt.Println("hon")
	default:
		fmt.Println("pon")
	}
}

type Scanner struct {
	*bufio.Scanner
}

func NewScanner(r io.Reader) *Scanner {
	return &Scanner{
		bufio.NewScanner(r),
	}
}

func (sc *Scanner) ReadLine() Value {
	if sc.Scan() {
		return Value(sc.Text())
	}
	panic("read line error")
}

func (sc *Scanner) ReadLines(n int) Values {
	values := make(Values, n)
	for i := range values {
		values[i] = sc.ReadLine()
	}
	return values
}

type Value string

func (v Value) String() string {
	return string(v)
}

func (v Value) Int() int {
	n, err := strconv.Atoi(v.String())
	if err != nil {
		panic(err)
	}
	return n
}

func (v Value) Int64() int64 {
	n, err := strconv.ParseInt(v.String(), 10, 64)
	if err != nil {
		panic(err)
	}
	return n
}

func (v Value) Float64() float64 {
	f, err := strconv.ParseFloat(v.String(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func (v Value) Strings() []string {
	return strings.Split(v.String(), " ")
}

func (v Value) Ints() []int {
	strings := v.Strings()
	ints := make([]int, len(strings))
	for i, s := range strings {
		n, err := strconv.Atoi(s)
		if err != nil {
			panic(err)
		}
		ints[i] = n
	}
	return ints
}

func (v Value) Int64s() []int64 {
	strings := v.Strings()
	ints := make([]int64, len(strings))
	for i, s := range strings {
		n, err := strconv.ParseInt(s, 10, 64)
		if err != nil {
			panic(err)
		}
		ints[i] = n
	}
	return ints
}

func (v Value) Float64s() []float64 {
	strings := v.Strings()
	float64s := make([]float64, len(strings))
	for i, s := range strings {
		f, err := strconv.ParseFloat(s, 64)
		if err != nil {
			panic(err)
		}
		float64s[i] = f
	}
	return float64s
}

type Values []Value

func (v Values) Strings() [][]string {
	strings := make([][]string, len(v))
	for i, value := range v {
		strings[i] = value.Strings()
	}
	return strings
}

func (v Values) Ints() [][]int {
	ints := make([][]int, len(v))
	for i, value := range v {
		ints[i] = value.Ints()
	}
	return ints
}

func (v Values) Int64s() [][]int64 {
	int64s := make([][]int64, len(v))
	for i, value := range v {
		int64s[i] = value.Int64s()
	}
	return int64s
}

func (v Values) Float64s() [][]float64 {
	float64s := make([][]float64, len(v))
	for i, value := range v {
		float64s[i] = value.Float64s()
	}
	return float64s
}


Measured memory_bytes: 1760
#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);
  }
  
  int cnt=0;
  int minimum = 1e9;
  for(int i=0;i<n;i++){
    minimum = min(minimum,p[i]);
    if(minimum == p[i]) cnt++;
  }
  
  cout << cnt << endl;
  
  return(0);
}

Measured memory_bytes: 4060
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	YOKO,
	TATE,
};


int H,W;
int ans,limit;

bool check(Type type,int row,int col,int table[20][20]){ //新しく角が寄った点だけ調べる

	int start_row,end_row,start_col,end_col;
	if(type == YOKO){
		start_col = max(1,col);
		end_col = min(W-1,col+2);
		start_row = max(1,row);
		end_row = min(H-1,row+1);

	}else{ //type == TATE

		start_col = max(1,col);
		end_col = min(W-1,col+1);
		start_row = max(1,row);
		end_row = min(H-1,row+2);
	}

	for(int row = start_row; row <= end_row; row++){
		for(int col = start_col; col <= end_col; col++){
			if(table[row-1][col-1] == 0 || table[row-1][col] == 0 || table[row][col-1] == 0 || table[row][col] == 0)continue;

			if(table[row-1][col-1] != table[row-1][col] && table[row-1][col-1] != table[row][col-1] && table[row-1][col-1] != table[row][col] &&
				table[row-1][col] != table[row][col-1] && table[row-1][col] != table[row][col] && table[row][col-1] != table[row][col])return false;

		}
	}
	return true;
}

void recursive(int count,int row,int col,int table[20][20]){ //重複計上を防ぐため、行ごとに畳を並べる
	if(row == H){
		if(count == limit+1)ans++;
		return;
	}
	if(col == W){ //次の行へ
		recursive(count,row+1,0,table);
		return;
	}

	if(table[row][col] != 0){ //既に畳が敷いてある(縦)
		if(col <= W-2){
			recursive(count,row,col+1,table);
		}else{ //col == W-1
			recursive(count,row+1,0,table); //次の行へ
		}
		return;
	}

	if(col <= W-2 && table[row][col+1] == 0){ //右に敷ける場合
		int next_table[20][20];
		for(int a = 0; a < H; a++){
			for(int b = 0; b < W; b++)next_table[a][b] = table[a][b];
		}
		next_table[row][col] = count;
		next_table[row][col+1] = count;

		if(check(YOKO,row,col,next_table)){
			recursive(count+1,row,col+2,next_table);
		}
	}
	if(row <= H-2 && table[row+1][col] == 0){ //縦に敷ける場合
		int next_table[20][20];
		for(int a = 0; a < H; a++){
			for(int b = 0; b < W; b++)next_table[a][b] = table[a][b];
		}
		next_table[row][col] = count;
		next_table[row+1][col] = count;

		if(check(TATE,row,col,next_table)){
			recursive(count+1,row,col+1,next_table);
		}

	}

}


int main(){

	int first_table[20][20];

	while(true){
		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0)break;

		if((H*W)%2 == 1){
			printf("0\n");
			continue;
		}

		ans = 0;
		limit = (H*W)/2; //limit枚の畳が敷けるはず

		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				first_table[row][col] = 0;
			}
		}
		recursive(1,0,0,first_table);

		printf("%d\n",ans);
	}

	return 0;
}



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

using int64=long long;
using uchar=unsigned char;

constexpr int maxn(200000);
constexpr int64 inf(1e17);

template<class _Tp>
	inline bool bchkMin(_Tp&x,const _Tp&y)
		{return(x>y)&&(x=y,1);}

namespace IOManager{
	constexpr int FILESZ(131072);
	char buf[FILESZ];
	const char*ibuf=buf,*tbuf=buf;

	struct IOManager{
		inline char gc()
			{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

		template<class _Tp>
			inline operator _Tp(){
				_Tp s=0u;char c=gc();
				for(;c<48;c=gc());
				for(;c>47;c=gc())
					s=(_Tp)(s*10u+c-48u);
				return s;
			}
	};
}IOManager::IOManager io;

int sz[maxn+1];
int64 szl[maxn+1],szr[maxn+1];

struct Edge{
	int s,t;int64 w;

	inline void init(const int&is,const int&it,const int64&iw)
		{s=is;t=it;w=iw;}

	inline bool operator<(const Edge&rhs)
		const{return w<rhs.w;}
}e[maxn*30],*cur=e;

void calc(const int&l,const int&r){
	if(l==r)
		return;
	const int m=(l+r)>>1;

	int lmp,rmp;
	int64 lmv=inf,rmv=inf;

	for(int i=l;i<=m;++i)
		if(bchkMin(lmv,szl[i]))
			lmp=i;
	for(int i=m+1;i<=r;++i)
		if(bchkMin(rmv,szr[i]))
			rmp=i;

	for(int i=l;i<=m;++i)
		(++cur)->init(i,rmp,szl[i]+rmv);
	for(int i=m+1;i<=r;++i)
		(++cur)->init(lmp,i,lmv+szr[i]);

	calc(l,m);calc(m+1,r);
}

int ufs[maxn+1];

inline int anc(const int&v)
	{return v==ufs[v]?v:ufs[v]=anc(ufs[v]);}

int main(){
	const int n=io,D=io;
	int64 t=0;
	for(int i=1;i<=n;++i,t+=D)
		ufs[i]=i,
		sz[i]=io,
		szl[i]=sz[i]-t,
		szr[i]=sz[i]+t;

	calc(1,n);
	std::sort(e+1,cur+1);
	int64 ans=0;
	for(Edge*i=e+1;i<=cur;++i)
		if(anc(i->s)!=anc(i->t))
			ans+=i->w,ufs[ufs[i->s]]=ufs[i->t];
	printf("%lld",ans);

	return 0;
}


Measured memory_bytes: 62208
// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████   
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████  
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
const double EPS = 1e-9;
#define INF (1LL<<60)
#define fs first
#define sc second
#define pb push_back
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<vector<P> > Graph;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n;
  cin >> n;

  vec a(n);
  REP(i,n) cin >> a[i];

  int ans = 0;
  REP(i,n){
    bool f = true;
    REP(j,i) if(a[i] < a[j]) f = false;
    if(f) ans++;
  }

  cout << ans << endl;

  return 0;
}

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

int N,M,Q,a[50],b[50],c[50],d[50],res;

void dfs(vector<int>v){
	if(v.size()==N){
		int t=0;
		for(int i=0;i<Q;i++){
			if(v[b[i]]-v[a[i]]==c[i]){
				t+=d[i];
			}
		}
		res=max(res,t);
	}
	else{
		if(v.empty())v.push_back(1);
		else v.push_back(v.back());
		for(int i=v.back();i<=M;i++){
			v.back()=i;
			dfs(v);
		}
	}
}

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


Measured memory_bytes: 3628
import sys
input = sys.stdin.readline

s = int(input())
l = []
l.append(s)
L = 1
for i in range(1000000):

    if s % 2 == 0:
        s = s // 2
    else:
        s = 3*s + 1

    l.append(s)

    if L == len(set(l)):
        print(i+2)
        exit()
    else:
        L = len(set(l))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[1111][1<<12];
signed main(){
  int hi,hm;
  while(cin>>hi>>hm,hi||hm){
    int r,c;
    cin>>r>>c;
    string a[r];
    for(int i=0;i<r;i++) cin>>a[i];
    int t;
    cin>>t;
    char b[t];
    int d[t];
    for(int i=0;i<t;i++) cin>>b[i]>>d[i];
    int s;
    cin>>s;
    char e[s];
    int n[s];
    for(int i=0;i<s;i++) cin>>e[i]>>n[i];
    int q;
    cin>>q;
    int p[q];
    for(int i=0;i<q;i++) cin>>p[i];
    //puts("OK");
    map<char,int> dm;
    for(int i=0;i<t;i++) dm[b[i]]=d[i];
    string udlr="UDLR";
    map<char,int> rd;
    for(int i=0;i<(int)udlr.size();i++) rd[udlr[i]]=i;
    memset(dp,0,sizeof(dp));
    dp[0][0]=hi;
    int z=0;
    int ax[]={0,0,-1,1};
    int ay[]={-1,1,0,0};
    int px=0,py=0;
    for(int x=0;x<s;x++){
      for(int y=0;y<n[x];y++){
	int k=rd[e[x]];
	px+=ax[k];
	py+=ay[k];
	for(int i=0;i<(1<<q);i++){
	  if(!dp[z][i]) continue;
	  for(int l=0;l<q;l++){
	    if((i>>l)&1) continue;
	    int j=i+(1<<l);
	    int tmp=min(hm,dp[z][i]+p[l]);
	    dp[z][j]=max(dp[z][j],tmp);
	    tmp-=dm[a[py][px]];
	    dp[z+1][j]=max(dp[z+1][j],tmp);
	  }
	  dp[z+1][i]=max(dp[z+1][i],dp[z][i]-dm[a[py][px]]);
	}      
	z++;
      }
    }
    bool f=0;
    for(int i=0;i<(1<<q);i++) f|=dp[z][i];
    cout<<(f?"YES":"NO")<<endl;
  }
  return 0;
}

Measured memory_bytes: 38580
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (a : b : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    a' = 100 * a
    b' = 100 * b
    cs = filter p [1..1000]
      where
        p :: Int -> Bool
        p k = a' <= 8 * k && 8 * k < a' + 100 && b' <= 10 * k && 10 * k < b' + 100
  print $ if null cs then -1 else head cs

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
#include <iostream>
#include <algorithm>
#include <cmath>
#define max 100000
#define MAX 1000000000
using namespace std;
int n;
long long num[max];
long long sum[max];

int main()
{
	cin >> n;
	long long t=0;
	int r;
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&num[i]);
		if(t<num[i])
		{
			t=num[i];
			r=i;
		}
	}
	long long s=t/2;
	long long int a=MAX,b;
	for(int i=0;i<n;i++)
	{
		if(i==r)continue;
		sum[i]=abs(num[i]-s);
		if(a>sum[i])
		{
			a=sum[i];
			b=num[i];
		}
	}
	cout << t << ' ' << b;
	
	
	return 0;
}

Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 1e16;

#define rep(i, N) for(ll i=0; i<N; ++i)

ll max(ll a, ll b) {return a < b ? b : a; }
ll min(ll a, ll b) {return a > b ? b : a; }
double maxf(double a, double b) { return a < b ? b : a; }

int main() {
  int n;
  cin>>n;
  int ans = 0;

  ans = n/500*1000;
  n = n % 500;

  int tmp = 0;
  tmp = n / 5 * 5;

  ans += tmp;

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N=0;
    cin>>N;

    string num=to_string(N);

    for(int i=0;i<3;++i){
        if(num[i]=='1'){
            num[i]='9';
        }else{
            num[i]='1';
        }
    }

    cout<<num<<endl;

            

}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define FOR(i,a,n) for(i=a;i<n;i++)
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
void fill(int a[],int b,int c){
	int i;
	FOR(i,0,b) a[i]=c;
	return;
}
int main(void)
{
	int a,b,c,t1,t2,cnt=0;
	scanf("%d%d%d",&a,&b,&c);
	while(!(a%2)&&!(b%2)&&!(c%2)){
		if(a==b&&b==c){
			puts("-1");
			return 0;
		}
		cnt++;
		t1=a,t2=b;
		a=(b+c)/2;
		b=(t1+c)/2;
		c=(t1+t2)/2;
	}
	printf("%d\n",cnt);
	return 0;
}
    
    


Measured memory_bytes: 128