akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * Created by darshan on 5/30/19.
 */
public class Main {
    private static long[] sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] seq = new int[n];
        for (int i = 0; i < n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + seq[i];
        }
        long ans = Long.MAX_VALUE;
        for (int i = 2; i < n - 1; i++) {
            long[][] leftPartitions = partition(0, i);
            long[][] rightPartitions = partition(i, n);
            for (long[] left : leftPartitions) {
                for (long[] right : rightPartitions) {
                    long max = Math.max(Math.max(left[0], left[1]), Math.max(right[0], right[1]));
                    long min = Math.min(Math.min(left[0], left[1]), Math.min(right[0], right[1]));
                    ans = Math.min(ans, max - min);
                }
            }
        }
        System.out.println(ans);
    }

    private static long[][] partition(int exclusiveStart, int inclusiveEnd) {
        if (inclusiveEnd - exclusiveStart < 2) {
            throw new RuntimeException("inclusiveEnd - exclusiveStart must be >= 2");
        }
        int partitionLeft = exclusiveStart;
        // Exclude rightmost element to ensure at least one partition will always exist
        int partitionRight = inclusiveEnd - 1;
        while (partitionRight - partitionLeft > 1) {
            int mid = (partitionLeft + partitionRight) / 2;
            long sumLeft = sum[mid] - sum[exclusiveStart];
            long sumRight = sum[inclusiveEnd] - sum[mid];
            if (sumLeft >= sumRight) {
                partitionRight = mid;
            } else {
                partitionLeft = mid;
            }
        }
        if (partitionRight > exclusiveStart + 1) {
            return new long[][] {
                    { sum[partitionRight] - sum[exclusiveStart], sum[inclusiveEnd] - sum[partitionRight] },
                    { sum[partitionRight - 1] - sum[exclusiveStart], sum[inclusiveEnd] - sum[partitionRight - 1] }
            };
        } else {
            return new long[][]{
                    { sum[partitionRight] - sum[exclusiveStart], sum[inclusiveEnd] - sum[partitionRight] }
            };
        }
    }
}


Measured memory_bytes: 56764
#include <bits/stdc++.h>
using namespace std;
int main (){
  int N,x;
  cin >> N >> x;
  vector<int> X(N);
  for (int i=0; i<N ; i++)
    cin >> X.at(i);
  sort(X.begin(),X.end()); //小さい順に下から引いていく
  
  int i ;
  for (i=0; i<N ; i++){
   if (x<0)
     break;
    else
      x -= X.at(i);//０より大きい限り引く
  }
  if (x != 0) 
    i--;
  cout << i <<endl;
}

Measured memory_bytes: 256
n,x,y=map(int,input().split())
x-=1
y-=1
ans=[0]*(n-1)
for i in range(n-1):
	for j in range(i+1,n):
		a=j-i
		b=abs(y-j)+abs(i-x)+1
		ans[min(a,b)-1]+=1
for x in ans:
	print(x)



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

using namespace std;

#define int 		long long
#define ll			long long
#define endl 		"\n"
#define mod			1000000007
#define inf			1e12
#define IOS			ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

void findCycle(int i, vector<int>& cycle, vector<bool>& vis, vector<int>& p, vector<int>& c) {
	int sum = 0;

	int start = i;

	while (!vis[start]) {
		vis[start] = true;
		start = p[start];
		sum += c[start];
		cycle.push_back(sum);
	}
}

int32_t main() {

	IOS;

	int n, k;
	cin >> n >> k;

	vector<int> p(n), c(n);

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

	for (int i = 0; i < n; i++)
		cin >> c[i];

	int mx = -inf;

	for (int i = 0; i < n; i++) {
		vector<int> cycle;
		vector<bool> vis(n);

		findCycle(i, cycle, vis, p, c);

		int len = cycle.size();
		int ans = -inf;

		if (k >= len && cycle.back() > 0) {
			int repeat = k / len;
			int max1 = -inf, max2 = -inf, left = k % len;

			for (int i = 0; i < len; i++)
				max1 = max(max1, cycle[i]);

			for (int i = 0; i < left; i++)
				max2 = max(max2, cycle[i]);

			ans = max(repeat * cycle.back() + max2, (repeat - 1) * cycle.back() + max1);

		}
		else {
			int left = min(len, k);

			for (int i = 0; i < left; i++)
				ans = max(ans, cycle[i]);
		}

		mx = max(mx, ans);
	}

	cout << mx;

	return 0;
}

Measured memory_bytes: 3848
def sum_a(x):
    t = 0
    for i in range(x):
        t += i
    return t

N = int(input())
dic = {}

for i in range(N):
    s = input()
    s = ''.join(sorted(s))
    # print(s)
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

total = 0
for i in dic.values():
    if i > 1:
        total += sum_a(i)

print(total)

Measured memory_bytes: 17808
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
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; }

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
int a, b;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    while(true){
        int n, x;
        cin >> n >> x;
        int ans = 0;
        if(n == 0 && x == 0)return 0;
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n;j++){
                for(int k = j+1; k <= n;k++){
                    if(i + j + k == x)ans++;
                }
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  if(a > b)
  	cout << a * 2 - 1 << endl;
  else if(a < b)
  	cout << b * 2 - 1 << endl;
  else
  	cout << a * 2 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<ll> vec;



void solve() {
	int m; cin >> m;
	int n; cin >> n;
	vector<int> a(n);
	int ans = 0;
	rep(i, n) {
		cin >> a[i];
	}
	if (m > 2) {
		rep1(i, n - 1) {
			if (a[i] == a[i - 1]) {
				ans++;
				i++;
			}
		}
	}
	else {
		int s1 = 0, s2 = 0;
		rep(i, n) {
			if (i % 2) {
				if (a[i] == 1)s1++;
				else s2++;
			}
			else {
				if (a[i] == 2)s1++;
				else s2++;
			}
		}
		ans = min(s1, s2);
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(4);
	//init();
	solve();
	stop
		return 0;
}



Measured memory_bytes: 3356
N, M = gets.split.map(&:to_i)
A = []
N.times do
  A << gets.chomp
end

B = []
M.times do
  B << gets.chomp
end

(N-M+1).times do |i|
  (N-M+1).times do |j|
    tmp = []
    M.times do |k|
      tmp << A[i+k][j..(j+M-1)]
    end
    if tmp == B
      puts 'Yes'
      exit
    end
  end
end
puts 'No'

Measured memory_bytes: 1916
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n, m;
        cin >> n >> m;
        if(n == 0)
            return 0;

        list<int> a;
        for(int i=1; i<=n; ++i)
            a.push_back(i);

        list<int>::iterator it = a.begin();

        for(int i=0; i<n-1; ++i){
            for(int i=0; i<m-1; ++i){
                ++ it;
                if(it == a.end())
                    it = a.begin();
            }
            it = a.erase(it);
            if(it == a.end())
                it = a.begin();
        }

        cout << *it << endl;
    }
}

Measured memory_bytes: 0
N = int(input())
ans = 0
if N < 105:
    ans = 0
else:
    for i in range(105, N+1):
        if i % 2 == 1:
            count = 0
            for j in range(1, i+1):
                if i % j == 0:
                    count += 1

            if count == 8:
                ans += 1

print(ans)


Measured memory_bytes: 2940
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
	public static void main(String[] args)throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader reader = new BufferedReader(isr);
		String str;
		
		x : while(!(str = reader.readLine()).equals(".")){
			char c[] = str.toCharArray();
			
			Stack<Integer> s = new Stack<Integer>(); s.push(3);
			for(char var : c){
				if(var == '('){
					s.push(1);
				}
				else if(var == '['){
					s.push(0);
				}
				else if(var == ')' && s.peek() == 1){
					s.pop();
				}
				else if(var == ']' && s.peek() == 0){
					s.pop();
				}
				else if(var == ')' && s.peek() != 1){
					System.out.println("no");
					continue x;
				}
				else if(var == ']' && s.peek() != 0){
					System.out.println("no");
					continue x;
				}
			}
			if(s.size() == 1){
				System.out.println("yes");
			}else{
				System.out.println("no");
			}
		}
		reader.close();
	}
}

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

int main() {
int n,k;
cin >>n >>k;
vector<int>che(n,0);
for(int i=0;i<n;i++){
    int z;
    cin >>z;
    che.at(z-1)++;
}
int ans =0;
for(int i=0;i<n;i++){
    if(che.at(i)>=1)ans++;
}
sort(che.begin(),che.end());

    int  anss=0;
        for(int i=0;i<n;i++){ 
            if(ans<=k)break;
            if(che.at(i)>=1){
                anss+=che.at(i);
                che.at(i)=0;
                ans--;
            }
           
        }
    cout <<anss<<endl;
}



Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rnr(i,a,b) for(int i=int(a);i>=int(b);i--)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

int main() {
    int N, M, X; cin >> N >> M >> X;
    int A[M]; rep(i, M) cin >> A[i];
    int ansL = 0, ansR = 0, j = 0;

    rep(i, M) {
        if(A[i] < X) {
            ansL += 1;
        }else {
            ansR += 1;
        }
    }
    cout << min(ansL, ansR) << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    rep(i,n)cin>>v[i];
    
    int maxi = *max_element(all(v));
    int mini = *min_element(all(v));
    
    if(maxi==mini){
        if(maxi==n-1 || 2*maxi<=n)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }else if(maxi-mini==1){
        int p=0, q=0;
        rep(i,n){
            if(v[i]==mini)p++;
            else q++;
        }
        if(2*(maxi-p)<=q && maxi>p)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <string>

using namespace std;

int main()
{
  string S;
  cin >> S;

  int n = 1 << ( S.length() - 1 );

  long ans = 0;
  for( int bits = 0; bits < n; ++bits )
  {
    long sum = 0;
    long cur = S[ 0 ] - '0';
    for( int i = 0; i < S.length() - 1; ++i )
    {
      if( ( bits & ( 1 << i ) ) != 0 )
      {
        sum += cur;
        cur = 0;
      }
      else
      {
        cur *= 10;
      }

      cur += S[ i + 1 ] - '0';
    }
    sum += cur;
    ans += sum;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

struct Path{
  int a;
  int b;
  int d;

  bool operator<(const Path &another) const{
    return d<another.d;
  }
}typedef path;

int main(void){
  int n;
  int m;
  int a,b,d;
  vector<path> p;
  int lantern;
  while(1){
    cin>>n;
    if(n==0)break;
    cin>>m;
    for(int i=0;i<m;i++){
      scanf("%d,%d,%d",&a,&b,&d);
      path _p;
      _p.a=a;
      _p.b=b;
      _p.d=d;
      p.push_back(_p);
    }
    int group[n];
    for(int i=0;i<n;i++){
      group[i]=i;
    }
    lantern=0;
    sort(p.begin(),p.end());
    for(int i=0;i<m;i++){
      if(group[p[i].a]!=group[p[i].b]){
        lantern+=p[i].d/100-1;
        int g=group[p[i].a];
        for(int j=0;j<n;j++){
          if(group[j]==g){
            group[j]=group[p[i].b];
          }
        }
      }

    }
    cout<<lantern<<endl;
    p.clear();
  }
  return 0;
}



Measured memory_bytes: 3356
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static final int ALF = 26;

    Main() {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int D = sc.nextInt();
        int T = sc.nextInt();
        int S = sc.nextInt();
        System.out.println(T*S>=D?"Yes":"No");
    }

    public static void main(String[] args) {
        new Main();
    }
}


Measured memory_bytes: 35740
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m,map[16][16];
ll in[1<<16],f[1<<16][16];
int main(){
	scanf("%d%d",&n,&m);int x,y;
	for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),x--,y--,scanf("%d",&map[x][y]),map[y][x]=map[x][y];
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<n;j++)if(i&(1<<j))
			for(int k=j+1;k<n;k++)if(i&(1<<k))in[i]+=map[j][k];memset(f,-0x3f,sizeof(f));f[1][0]=0;
	for(int i=1;i<(1<<n);i++)
		for(int j=0;j<n;j++)if(i&(1<<j)){
			int x=i^(1<<j);
			for(int k=0;k<n;k++)if(i&(1<<k)&&map[k][j])f[i][j]=max(f[i][j],f[x][k]+map[k][j]);
			for(int k=x;k;k=(k-1)&x)f[i][j]=max(f[i][j],f[i^k][j]+in[1<<j^k]);
		}printf("%lld\n",in[(1<<n)-1]-f[(1<<n)-1][n-1]);
}


Measured memory_bytes: 8576
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
typedef long long ll;

int main()
{
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;
	if (N <= K) cout << X * N << endl;
	else cout << X * K + Y * (N - K) << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<memory.h>

using namespace std;
int main(){
	int dp[31][31];
	int n;
	while (1){
		cin >> n;
		if (n == 0)break;
		memset(dp, 0, sizeof(dp));
		dp[1][1] = 1;
		dp[1][2] = 1;
		dp[1][3] = 1;
		for (int i = 1; i <= 30; i++){
			for (int i2 = 1; i2 <= 30; i2++){
				if(i2+1<=30)dp[i + 1][i2 + 1] += dp[i][i2];
				if(i2+2<=30)dp[i + 1][i2 + 2] += dp[i][i2];
				if(i2+3<=30)dp[i + 1][i2 + 3] += dp[i][i2];
			}
		}
		int sum = 0;

		for (int i = 0; i < 30; i++){
			sum += dp[i][n];
		}
		cout << sum / 10 / 365 + 1 << endl;
	}
}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

int dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};

// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, m, x, y, q;
string s, t;

// <------------- Implement Functions Here ----------> //

vll cnt(12,0);

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n >> m ;
	cout<< n*n - m;
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b) { //最小公倍数
  return a * b / gcd(a, b);
}

ll digit_sum(ll a){ //10進桁和
  ll ans=0;
  while(a>0){
    ans+=a%10;
    a/=10;
  }
  return ans;
}



int main()
{
  ll n,m,ans=0LL;
  map<string,ll> mp;
  string s[110],t[110];

  cin>>n;
  rep(i,n){
    cin>>s[i];
    mp[s[i]]++;
  }
  cin>>m;
  rep(i,m){
    cin>>t[i];
    mp[t[i]]--;
  }

  rep(i,n){
    ans=max(ans,mp[s[i]]);
  }



  cout<<max(ans,0LL)<<endl;
  return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long n,total=1,l,s=1,k;
    cin>>n;
    while(n>1)
    {
        n/=2;
        k=2*s;
        total+=k; 
        s=k;
    }
    cout<<total<<endl;
    return 0;   
}

Measured memory_bytes: 3628
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int allNum=scan.nextInt();
        HashMap<Long,Long> bigger=new HashMap<>();
        HashMap<Long,Long> smaller=new HashMap<>();
        for (long i = 1; i <=allNum ; i++) {
            long A=scan.nextLong();
            if (bigger.containsKey(i+A)){
                bigger.put(i+A,bigger.get(i+A)+1);
            }else{
                bigger.put(i+A,1L);
            }
            if (smaller.containsKey(i-A)){
                smaller.put(i-A,smaller.get(i-A)+1);
            }else{
                smaller.put(i-A,1L);
            }
        }
        long count=0;
        for(Long i:bigger.keySet()){
            if (smaller.containsKey(i)){
                count+=bigger.get(i)*smaller.get(i);
            }
        }
        System.out.println(count);
    }
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, a[101010];
int cnt[101010];
void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]++;
	}
	
	for(int i = 0; i < n; i++){
		cnt[a[i]+1]++;
		cnt[a[i]-1]++;
		cnt[a[i]]++;
	}
	int ma = 0;
	for(int i = 0; i < 101010; i++){
		chmax(ma, cnt[i]);
	}
	cout << ma << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 1024
// はじめstring word と priority_queueのコード順を反対にしてたところQに何も入らなかった
// 順番を反対にしたらちゃんと値がQに入っていた理由がわからないです
// また、int num をwhileの外に書いていた時はエラーコードで再帰が深すぎるみたいな警告が出てきた時も結局理由がよくわからなかった
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_ C&lang=jp
// 教壇から見て右×奥

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main(){

  priority_queue<int> Q;
  string word;
  int num;
  while(cin >> word){
    if(word=="insert"){

      cin >> num;
      Q.push(num);
    }
    else if(word == "extract"){
      int n = Q.top();
      Q.pop();
      cout << n <<endl;
    }
    else if(word == "end"){
      break;
    }
  }
}


Measured memory_bytes: 6940
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(int i=0; i<n; i++)
#define reps(i, s, e) for(int i=s; i<e; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define reprs(i, s, e) for(int i=e-1; i>=s; i--)

int main(){

    int h, w; cin >> h >> w;
    int a, b; cin >> a >> b;

    int ans[h][w];
    rep(i, h){
        if(i < b){
            rep(j, w){
                if(j < a){
                    ans[i][j] = 1;
                }
                else{
                    ans[i][j] = 0;
                }
            }
        }
        else{
            rep(j, w){
                if(j < a){
                    ans[i][j] = 0;
                }
                else{
                    ans[i][j] = 1;
                }
            }
        }
    }

    rep(i, h){
        rep(j, w){
            cout << ans[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'
int main()
{
    Hello
    int n;
    cin >> n;
    while(n){
        if(n % 10 == 7)
            return cout << "Yes", 0;
        n /= 10;
    }
    cout <<"No";
    return 0;
}

Measured memory_bytes: 3668
#include<iostream>
using namespace std;
int C[12],A[12][12];
int main() {
  int N,M,X; cin>>N>>M>>X;
	for (int i=0; i<N; i++) {
		cin>>C[i];
		for (int j=0; j<M; j++) cin>>A[i][j];
	}
	int ans=1e8;
	for (int i=0; i<1<<N; i++) {
		int now[12]={};
		int sum=0;
		for (int j=0; j<N; j++) {
      if (i>>j&1) {
			  sum+=C[j];
			  for (int k=0; k<M; k++) now[k] += A[j][k];
		  }
    }
		bool flag=true;
		for (int j=0; j<M; j++) if (now[j]<X) flag=false;
		if (flag&&ans > sum) ans=sum;
	}
	cout<<(ans>1e7?-1:ans)<<endl;
  return 0;
}

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

int a[25], b[25], c[25];

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

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

    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }

    for (int i = 1; i <= n-1; ++i) {
        cin >> c[i];
    }

    ll content = 0;
    for (int i = 1; i <= n; ++i) {
        content += b[a[i]];
    }

    for (int i = 2; i <= n; ++i) {
        if (a[i] - a[i-1] == 1) {
            content += c[a[i-1]];
        }
    }

    cout << content << endl;

    return 0;
}

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

int main(){
  int N, T;
  cin >> N >> T;
  vector<int> inte(N);
  int minn=1000000001;
  for(int i=0; i<N; i++){
    int A;
    cin >> A;
    minn=min(minn, A);
    inte.at(i)=A-minn;
  }
  sort(inte.begin(), inte.end());
  reverse(inte.begin(), inte.end());
  //for(int i=0; i<N; i++) cout << inte.at(i) << ' ';
  int ans=0;
  while(inte.at(ans)==inte.at(ans+1)){
    ans++;
  }
  ans++;
  cout << ans << endl;
}


Measured memory_bytes: 640
# python3だとTLE,pypy3だとAC

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(0, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 272136
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static final int MOD = (int)Math.pow(10, 9);
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int[] nums = new int[n];
		int[] newNums = new int[n];
		
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}
		
		int pos = 0;
		
		for (int i = (n - 1); i >=0; i = i - 2) {
			newNums[pos] = nums[i];
			pos++;
		}
		
		for (int i = (n%2) ; i < n; i = i + 2) {
			newNums[pos] = nums[i];
			pos++;
		}
		
		for (int i = 0; i < n; i++) {
			if (i == n - 1) {
				System.out.println(newNums[i]);
			} else {
				System.out.print(newNums[i] + " ");
			}
		}
	}
	
    static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}


Measured memory_bytes: 61416
import java.util.*;

class Main {
    public static void main(String args[]) {
        
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int a = s.nextInt();
        int b = s.nextInt();
        if((int)(Math.abs(b-a))%2 == 0)
        System.out.println("Alice");
        else
        System.out.println("Borys");
        
        
        
        
        
    }
}


Measured memory_bytes: 23892
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
	public static void main(String[] args) throws java.io.IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while (n != 0) {
			n--;
			char[] snake = sc.next().toCharArray();
			String ans = isSnakeA(snake) ? "A" : isSnakeB(snake) ? "B" : "NA";
			System.out.println(ans);
		}
	}

	private static boolean isSnakeA(char[] snake) {
		String sa = "^>'(=+)#\\1~$";
		Pattern pa = Pattern.compile(sa);
		Matcher ma = pa.matcher(String.valueOf(snake));
		return ma.find();
	}

	private static boolean isSnakeB(char[] snake) {
		String sb = "^>\\^(Q=)+~~$";
		Pattern pb = Pattern.compile(sb);
		Matcher mb = pb.matcher(String.valueOf(snake));
		return mb.find();
	}
}

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

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

const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const int int_inf = 100000000;
const double eps = 1e-9;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll a, b, n;
    cin >> a >> b >> n;
    cout << a * min(b-1, n) / b << endl;

    return 0;
}



Measured memory_bytes: 3576
rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

def solve(A, B):
    for price in xrange(1, 1000000):
        tax1 =int(price * 0.08)
        tax2 = int(price* 0.10)
        if tax1 == A and tax2==B:
            return price
    return -1


print solve(*rrm())


Measured memory_bytes: 29164
#include <stdio.h>

#define W 10
#define H 10

int map[W][H];

void inc( int x, int y ){
	if( x>=0 && x<W && y>=0 && y<H )
		map[x][y]++;
}

void drop_ink( int x, int y, int size){
	int vh  = size/2 + size%2;
	int dia = size/2;
	int i;
	
	for( i=-vh; i<=vh; i++ ){
		if( i==0 )continue; //avoid duplication
		inc( x+i,  y  );
		inc(  x , y+i );
	}
	for( i=-dia; i<=dia; i++ ){
		if( i==0 )continue;//avoid duplication
		inc( x+i, y+i );
		inc( x-i, y+i );
	}
	inc( x, y );
}

int main(){
	int i, j;
	int x, y, size;
	int zero_num=0, max_dens=0;

	while( scanf("%d,%d,%d", &x, &y, &size) != EOF ){
		drop_ink( x, y, size );
	}

	for( i=0; i<H; i++ ){
		for( j=0; j<W; j++ ){
			if( map[i][j] == 0 )
				zero_num++;
			if( map[i][j] > max_dens )
				max_dens = map[i][j];
		}
	}

	printf("%d\n%d\n", zero_num, max_dens );

	return 0;
}

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

int main() {
  long long L, R;
  cin >> L >> R;

  long long ans = 2019;
  for (long long i = L; i <= min(R - 1, L + 2019LL); i++) {
    for (long long j = i + 1; j <= min(R, L + 2020LL); j++) {
      ans = min(ans, ((i * j) % 2019LL));
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sstream>

using namespace std;

int main(){
    int n, temp, minV, maxP;
    cin >> n;
    minV = 2000000000;
    maxP = -2000000001;
    for(int i = 0; i < n; ++i){
        cin >> temp;
        maxP = max(maxP, (temp - minV));
        minV = min(minV, temp);
    }

    cout << maxP << endl;

    return 0;
}


Measured memory_bytes: 3112
import java.util.Scanner;

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

		int n = scan.nextInt();
		int k = scan.nextInt();
		int sum = k;

		if(n == 1){
			System.out.println(sum);
			return;
		}


		for(int i = 0; i < n-1; i++){
			sum = sum * (k-1);
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[4]={0,1,0,-1},mdy[4]={-1,0,1,0};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n,m;
vector<int> prime;
vector<int> h_m_p;
ll mod_pow(ll x,ll n,ll mod){
	ll res=1;
	while(n>0){
		if(n&1)res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}

ll g(ll t){
	return mod_pow(t,MOD-2,MOD);
}
int main(){
	cin>>n>>m;
	if(m==1){
		cout<<1<<endl;
		return 0;
	}
	for(ll i=2;i<=sqrt(m);i++){
		while(m%i==0){
			prime.push_back(i);
			m/=i;
		}
		if(m==1)break;
	}
	if(m!=1)prime.push_back(m);
	int t=1;
	//cout<<prime.size()<<endl;
	for(int i=1;i<prime.size();i++){
		if(prime[i-1]==prime[i]){
			t++;
		}else{
			h_m_p.push_back(t);
			t=1;
		}
	}
	h_m_p.push_back(t);
	ll ans=1;
	//cout<<h_m_p.size()<<endl;
	for(ll j=0;j<h_m_p.size();j++){
		for(ll i=1;i<=h_m_p[j]+n-1;i++){
			ans*=i;
			ans%=MOD;
		}
		for(ll i=1;i<=h_m_p[j];i++){
			ans*=g(i);
			ans%=MOD;
		}
		for(ll i=1;i<=n-1;i++){
			ans*=g(i);
			ans%=MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

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

using namespace std;

void execute()
{
	int N, C;
	cin >> N >> C;

	vector<vector<int>> used(C, vector<int>(1000001, 0));
	for (int i = 0; i < N; i++)
	{
		int l, r, c;
		cin >> l >> r >> c;
		c--;
		used[c][l * 2]++;
		used[c][r * 2]--;
	}

	for (int i = 0; i < C; i++)
	{
		int current = 0;
		for (int j = 0; j < 1000000; j++)
		{
			if (used[i][j + 1] == 1)
			{
				current = 1;
			}
			if (used[i][j] == -1)
			{
				current = 0;
			}
			used[i][j] = current;
		}
	}

	int ans = 0;
	for (int i = 0; i < 1000000; i++)
	{
		int count = 0;
		for (int j = 0; j < C; j++)
		{
			count += used[j][i];
		}
		ans = max(ans, count);
	}
	cout << ans << endl;
	return;
}

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

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 121472
n, m = map(int, input().split())
students = [list(map(int, input().split())) for _ in range(n)]
points = [list(map(int, input().split())) for _ in range(m)]

for student in students:
  a, b = student
  ans = None
  dist = 10**10
  for i in range(len(points)):
    c, d = points[i]
    tmp = abs(a-c) + abs(b-d)
    if tmp < dist:
      ans = i+1
      dist = tmp
      
  print(ans)

Measured memory_bytes: 3064
while true
  # 中間試験の点数、期末試験の点数、再試験の点数
  m, f, r = $stdin.readline.split(" ").map {|s| s.to_i }

  if m == -1 && f == -1 && r == -1
    break
  end

  if m == -1 || f == -1
    puts "F"
    next
  elsif m + f >= 80
    puts "A"
    next
  elsif m + f >= 65
    puts "B"
    next
  elsif m + f >= 50
    puts "C"
    next
  elsif m + f >= 30
    if r >= 50
      puts "C"
    else
      puts "D"
    end
    next
  else
    puts "F"
  end
end



Measured memory_bytes: 6872
package main

import "fmt"

func main() {
	var tapPlugCount, requiredCount, tapCount int
	fmt.Scanf("%d", &tapPlugCount)
	fmt.Scanf("%d", &requiredCount)

	currentAvailableCount := 1
	for currentAvailableCount < requiredCount {
		currentAvailableCount += tapPlugCount - 1
		tapCount++
	}

	fmt.Println(tapCount)
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, a, n) for(ll i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    ll sum = 0;
    rep(i, 1, n+1){
        if(i % 3 == 0 || i % 5 == 0){
            continue;
        }
        else sum += i;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define MN 300000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[MN+5];
int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        if((a[i]+2*n-i)&1) return 0*puts("No");
    }
    for(int i=1,mx=0,j=0;i<=n;i=j+1)
    {
        while(mx=max(mx,a[++j]),mx!=j);
        int len=j-i+1;
        if(len%2==0) return 0*puts("No");
        if(len==1) continue;
        for(int k=i+1;k<j;k+=2) if(a[k]!=k) return 0*puts("No");
        int left=0,right=0;
        for(int k=i;k<=j;k+=2)
        {
            if(a[k]==k) return 0*puts("No");
            if(a[k]<k){if(a[k]<right)return 0*puts("No"); else right=a[k];}
            if(a[k]>k){if(a[k]<left )return 0*puts("No"); else left=a[k]; }
        }
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp15
{
    class Class312
    {
        static void Main()
        {
            int a = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            Console.WriteLine(a>=3200?s:"red");
        }
    }
}


Measured memory_bytes: 13140
#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 all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i,N){
        cin>>A[i];
    }
    map<int,int> cnt;
    rep(i,N){
        if(cnt.count(A[i])){
            cnt[A[i]]++;
        }else{
            cnt[A[i]]=1;
        }
    }

    int oc=0;
    int tc=0;
    rep(i,100001){
    //同じカードが3枚以上なら2ずつ減らせる
        if(cnt[i]==0){
            continue;
        }else{
            if(cnt[i]>=3){
                cnt[i]= (cnt[i]%2==0) ? 2 : 1;
            }
            if(cnt[i]==1){
                oc++;
            }else{
                tc++;
            }
        }
    }
    //2の数は偶数個1にできる
    int ans=0;
    // cout <<cnt[4]<<endl;
    ans=(tc%2==0)?oc+tc:oc+tc-1;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5376
#include <iostream>
using namespace std;
char a[55][55];
int main(){
	int H, W;
	cin >> H >> W;

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++)
			cin >> a[i][j];
    }
			
	for(int i=0; i<H; i++)
		for(int j=0; j<W ;j++){
			if(a[i][j] == '#'){
				if(i != 0){
                    if(a[i-1][j] == '#') continue;
                }
				if(i != H-1){
                    if(a[i+1][j] == '#') continue;
                }
				if(j != 0){
                    if(a[i][j-1] == '#') continue;
                }
				if(j != W-1){
                    if(a[i][j+1] == '#') continue;
                }
				cout << "No" << endl;
                return 0;
			}
		}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=m-1;i>=n;--i)
#define ALL(v) v.begin(),v.end()
#define INF 1000000001
#define MOD 1000000007

using namespace std;

int gcd(int a, int b) {
	if (a%b == 0) return b;
	else return gcd(b, a%b);
}


int main() {
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << endl;;
	return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/math/tools/minima.hpp>

const int MOD = 1e9+7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

namespace adaptor = boost::adaptors;
using namespace std;
using boost::math::tools::brent_find_minima;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::split;
using boost::algorithm::replace_all;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	int	n;
	ll	t;
	cin >> n >> t;
	vector<int>	V(n);
	rep(i, n)
		cin >> V.at(i);
	ll sum;
	sum = t;
	for (int i = 1; i < n; i++)
	{
		ll	d;
		d = V.at(i) - V.at(i - 1);
		if (d < t)
			sum += d;
		else
			sum += t;
	}
	cout << sum << endl;
}
// END

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


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

/*
 1 1/1
 2 3/2
 3 6/3
 4 10/4
 5 15/5
 6 21/6
 */


int main(){
    int n,k;
    std::cin >> n >> k;
    std::vector<double> p(n);
    std::vector<double> q(n);
    for(int i=0;i<n;++i){
        std::cin >> p[i];
    }
    
    for(int i=0;i<k;++i){
        q[0]+=(p[i]+1)/2;
    }
    
    for(int i=0;i<n-k;i++){
        q[i+1]=q[i]-(p[i]-p[i+k])/2;
    }
    std::sort(q.begin(),q.begin()+n-k+1,std::greater<double>());
    
    std::cout << std::fixed << std::setprecision(12) << q[0] << std::endl;
    return 0;
}

Measured memory_bytes: 3328
// code.begin();
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back 
#define what_is(x) cerr<<#x<<" is "<<x<<endl;
#define print(v) for(auto i:v) cout<<i<<" ";cout<<endl;
#define my_time ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long 
#define endl "\n"
#define MOD 1000000007
const long long int INF=1e18;
#define mod 1000000007
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    ordered_set; 
//find_by_order(x)
//order_of_key(x)  


int power(int x,unsigned int y)
{
    int res=1;
    
    while(y>0)
    {
        // if y is odd multiply with result
        if(y&1)
        res=res*x;
        
        y=y>>1; // y=y/2;
        x=x*x;
        
    }
    return res;
}

int gcd(int a,int b)
{
    if(b==0)
    return a;
    
    return gcd(b,a%b);
}

ll  max3(ll  a, ll  b, ll c)
{
    return max(c, max(a, b));
}
int min3(int a, int  b, int  c)
{
    return min(a, min(b, c));
}

int  powermod(int  x, int  y, int p )
{
    int res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res % p;
}
int logg(int  a)
{
    int  x = 0;
    while (a > 1)
    {
        x++;
        a /= 2;
    }
    return x;
}


int modinv(int x)
{
    return powermod(x, mod - 2, mod);
}



int  main(){
	my_time;

int t;
t=1;
//cin>>t;int test=0;
while(t--)
{
   int n;
   int w;
   cin>>n>>w;
   int weight[n+1];
   int value[n+1];
   
   for(int i=1;i<=n;i++)
   {
       cin>>weight[i]>>value[i];
   }
   
   
   
   ll dp[n+1][w+1];
   memset(dp,0,sizeof dp);
   for(int i=0;i<n+1;i++)
   {
     for(int j=0;j<=w;j++)
     {
         if(j==0 || i==0)
         {
             dp[i][j]=0;
             continue;
         }
         
         if(weight[i]<=j)
         {
             dp[i][j]=max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]]);
         }
         else
         dp[i][j]=dp[i-1][j];
         
     }
   }
   
   cout<<dp[n][w]<<endl;
   
   
   
}
    return 0;
}


//code.end();





Measured memory_bytes: 82456
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}

int main(){
  	vi a(3);
	int t;
  cin>>a[0]>>a[1]>>a[2]>>t;
  sort(all(a));
  cout<<(a[2]*(1<<t))+a[0]+a[1]<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    char ara[5];
    while(scanf("%s",ara)==1)
    {
        if(ara[0]==ara[1]&&ara[1]==ara[2]&&ara[2]==ara[3])printf("Yes\n");
        else if(ara[0]==ara[1]&&ara[1]==ara[2])printf("Yes\n");
        else if(ara[1]==ara[2]&&ara[2]==ara[3])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main()
{
    double x, xx;
    int    y, z;
    int i;

    scanf("%lf", &x);
    while (x >= 0) {

        xx = x * 16;
        y = (int)(xx);
        z = (int)x;
        if (z > 256 || xx - (double)y != 0) {
            printf("NA\n");
        } else {
            for (i = 0; i < 8; i++) {
                printf("%d", y >> 11);
                y = y << 1 & 0x00000fff;
            }
            putchar('.');
            for (i = 0; i < 4; i++) {
                printf("%d", y >> 11);
                y = y << 1 & 0x00000fff;
            }
            putchar('\n');

        }

        scanf("%lf", &x);
    }

    return 0;
}



Measured memory_bytes: 2656