akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(long long i=0;i<n;i++)
#define REP1(i,n) for(long long i=1;i<=n;i++)
#define PER(i,n) for(long long i=((n)-1);i>=0;i--)
#define PER1(i,n) for(long long i=(n);i>0;i--)
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define FORE(i,a,b) for(long long i=(a);i<=(b);i++)
#define ITE(arr) for(auto ite=(arr).begin();ite!=(arr).end();ite++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define YNPRT(b) cout<<((b)?"Yes":"No")<<endl
#define REV(arr) reverse(ALL(arr))
#define PRT(a) cout<<a<<endl;
#define PRTLST(arr,num) REP(_i,num) cout<<_i<<" - "<<arr[_i]<<endl;
#define PRTLST2(arr2,d1,d2) REP(_i,d1) REP(_j,d2) cout<<_i<<","<<_j<<" : "<<arr2[_i][_j]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
const ull INF_ULL = 18446744073709551615Ull;
const ll P = 92540646808111039LL;
const int Move[4][2] = {-1,0,1,0,0,1,0,-1};
const int Move_[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};

//---------------------
#define MAXN 100000
//---------------------

bool tieflag=true;
ll max1,max2;
ll a[27];
ll tickit[105];
int main(){
    REP(i,1500){
        ll n;
        cin>>n;
        if(n==0) break;
        ZERO(a);
        ZERO(tickit);
        tieflag=true;
        max1=0;
        max2=27;
        REP(j,n){
            char curchar;
            cin>>curchar;
            tickit[j]=curchar-'A';
        }
        REP(j,n){
            ll curid=tickit[j];
            a[curid]++;
            if(a[max1]<=a[curid] && curid!=max1){
                max2=max1;
                max1=curid;
            }else if(a[max2]<a[curid] && curid!= max2 && curid!=max1){
                max2=curid;
            }
            if(a[max1]>(a[max2]+n-j-1)){
                cout<<char('A'+max1)<<" "<<j+1<<endl;
                tieflag=false;
                break;
            }

        }
        if(tieflag && a[max1]==a[max2]) cout<<"TIE"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3080
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define ALL(a) (a).begin(),(a).end()
#define ifnot(a) if(not a)
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
bool test = 0;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
#define MAX (int)1e6 + 5

int main() {
	ll i, j, k, l;
	string s;
	vector<char> ans;
	cin >> s;
	rep(i, s.size()) {
		if (s[i] == '0') ans.push_back('0');
		if (s[i] == '1') ans.push_back('1');
		if (s[i] == 'B' && ans.size() > 0) {
			ans.pop_back();
		}
	}
	rep(i, ans.size()) {
		cout << ans[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
//-------------
//include
//-------------
#include <map>
#include <list>
#include <cmath>
#include <vector>
#include <string>
#include <cctype>
#include <random>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
//-------------
//typedef
//-------------
typedef long long LL;
typedef  vector<int> VI;
typedef  pair<int, int> PII;
typedef  vector<int, int> VII;
typedef  map<string, int> MSI;
//-------------
//utillty
//-------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MK make_pair
#define PB push_back
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define COUT(a) cout<<a<<endl
//-------------
//repetition
//-------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//-------------
//debug
//-------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumpl(c) REP(i,SZ(c))cerr<<#c<<i<<"="<<(c[i])<<endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const int MOD = 1000000007;
int main()
{
	int a , b , c;
	cin >> a >> b >> c;
	VI num = {a+b,b+c,a+c};
	SORT(num);
	cout <<*num.begin()<< endl;
#ifdef _DEBUG
	while(1);
#endif // _DEBUG

	return 0;
}

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

start = (0,0)
goal = (H-1, W-1)

def bfs():
    global H,W,maze,goal,start
    
    count = 0
    visited = [[False for _ in range(W)] for _ in range(H)]
    queue = [start]
    
    visited[start[0]][start[1]] = True
    while len(queue) > 0:
        next_queue = []
        for q in queue:
            if q == goal:
                return count
            x,y = q
            for nx,ny in [(x-1,y), (x+1,y),(x,y-1),(x,y+1)]:
                if 0<=nx<H and 0<=ny<W and not visited[nx][ny] and maze[nx][ny] == '.':
                    next_queue.append((nx, ny))
                    visited[nx][ny] = True
            
        queue = next_queue
        count+=1

    return -1

min_step = bfs()

if min_step == -1:
    print(-1)
else:
    count = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                count += 1
    answer = count - 1 - min_step
    print(answer)

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

int getDight(long long n){
    return (int)(log10(n) + 1);
}

void calculate(){
    long long A,B,AB,AN,BN;
    cin >> A >> B >> AB >> AN >> BN;
    long long SAB = A * AN + B * BN;
    long long SoAB = AB * max(AN,BN) * 2;
    long long SABaO = AB * min(AN,BN) * 2 + abs(AN - BN) * (AN > BN ? A : B);
    cout << min({SAB,SoAB,SABaO}) << '\n';
}

int main(int, char**) {
    calculate();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D,a,b;
  cin >>A >>B >>C >>D;
  a=A+B,b=C+D;
  if (a > b) {
    cout << "Left" << endl;
  }
  if (a == b) {
    cout << "Balanced" << endl;
  }
  if (a < b){
    cout <<  "Right" << 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(){
    string s,t;
    int n;
    cin>>n;
    cin>>s>>t;
    int ans = INF;
    for(int i=0;i<=n;i++){
        bool f = true;
        for(int j=i;j<n;j++){
            if( s[j]!=t[j-i] )f = false;
        }
        if(f)ans = min(ans,i*2+(n-i));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
s = input()
ans = True
for i in range(len(s)):
    if i % 2 == 0 and s[i] != 'R' and s[i] != 'U' and s[i] != 'D':
        ans = False
        break
    elif i % 2 == 1 and s[i] != 'L' and s[i] != 'U' and s[i] != 'D':
        ans = False
        break

if ans == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	int last = 'A', answer = 0;
	for(const char c : s){
		if(c <= last){ ++answer; }
		last = c;
	}
	cout << answer << endl;
	return 0;
}




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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

int N;
vector<int> L;

signed main()
{
    cin >> N;
    L.resize(N);
    int sum_l = 0;
    REP(i, N) {
        cin >> L[i];
        sum_l += L[i];
    }
    SORT(L);
    int max_l = L[L.size()-1];
    sum_l -= max_l;
    if(max_l < sum_l) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 256
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.IO;

namespace AtCoder
{
    class Program
    {

        const int BiggestMod = 1000000007;
        public static void Main()
        {

            Console.WriteLine(Console.ReadLine().ToArray().Select(x => (x == 'P' ? 'P' : 'D')).ToArray());

        }

    }

}

Measured memory_bytes: 28432
#include <iostream>
#include <math.h>
using namespace std;
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
int main()
{
	//debug;
	int N,M;
	int arr[10];
	int ifarr[10];
	for(int i=0;i<10;ifarr[i++]=0);
	for(int i=0;i<10;arr[i++]=10);
	cin>>N>>M;
	for(int i=1;i<=M;i++)
	{
		int a,b;
		cin>>a>>b;
		if(arr[a]!=b)
		{
			arr[a]=b;
			ifarr[a]++;
		}
	}
	//for(int i=1;i<=M;i++)
	//	cout<<arr[i]<<" ";
	//cout<<endl;
	for(int i=1;i<=N;i++)
	{
		if(ifarr[i]>1)
		{
			cout<<"-1";
			return 0;
		}
	}
	if(arr[1]==0&&N!=1)
	{
		cout<<"-1";
		return 0;
	}
	if(N==1)
	{
		if(arr[1]==10)
			cout<<"0";
		else
			cout<<arr[1];
		return 0;
	}
	for(int i=1;i<=N;i++)
	{
		if(arr[i]==10&&i==1)
			cout<<"1";
		else if(arr[i]==10)
			cout<<"0";
		else
			cout<<arr[i];
	}
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	private static int S;
	private static int N;
	private static int cnt;

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] arrays;

		while ((line = br.readLine()) != null) {
			cnt = 0;
			arrays = line.split(" ");
			N = Integer.parseInt(arrays[0]);
			S = Integer.parseInt(arrays[1]);

			comb(0, 1, new boolean[10]);
			
			System.out.println(cnt);

		}
	}

	private static void comb(int sum, int n, boolean[] c) {
		
		// ｎ件目は残りをnで割り切れるかどうかのチェックをする
		if (n == N) {
			if ((S - sum) % n == 0) {
				int a = (S - sum) / n;
				if (a < 10
						&& !c[a]) {
					cnt++;
				}
			}
			return;
		}

		// 1〜n-1件目は全探索
		for (int i = 0; i <= 9; i++) {
			if (c[i]) {
				continue;
			} else if (sum + i * n <= S && n < N) {
				c[i] = true;
				comb(sum + i * n, n + 1, c);
				c[i] = false;
			} else if (sum + i * n > S) {
				break;
			}
		}
	}
}

Measured memory_bytes: 19120
#include<stdio.h>

int main(void)
{
	int H, W,i,j;
	
	while(1){
		scanf("%d %d",&H, &W);
		
		if (H == 0 && W == 0)break;
		
		for(i = 0; i < H; i++){
			for(j = 0; j < W; j++){
			if(i % 2 == j % 2)
				printf("#");
			else
				printf(".");
			}
				printf("\n");
		}
	printf("\n");
	}

	
	return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9
#define f first
#define s second

typedef long long ll;

using namespace std;

const int N = 1e5;
int a[N+5];

int main()

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

    int a, b, c;

    cin >> a >> b >> c;

    cout << min(c, b/a);

    return 0;
}



Measured memory_bytes: 256
#ifdef ConanYu
#include "E:\yuzining\code\local.hpp"
#else
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) do { } while(false)
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie();
  Main();
  return 0;
}
#endif

void Main() {
  int k; cin >> k;
  int ans = 0;
  for(int i = 1; i <= k; i++) {
    for(int j = 1; j <= k; j++) {
      for(int q = 1; q <= k; q++) {
        ans += __gcd(__gcd(i, j), q);
      }
    }
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3608
Q,H,S,D = map(int, input().split())
N = int(input())
Q *= 4
H *= 2
min_cost = min(Q,H,S)
res = 0
if N%2:
    N -= 1
    res += min_cost
if N != 0:
    res += N//2*min(2*min_cost,D)
print(res)

Measured memory_bytes: 38256
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N;
    cin >> N;
    bool pink = false;
    bool white = false;
    bool green = false;
    bool yellow = false;
    char s;
    for(int i=0;i<N;i++){
        cin >> s;
        if(s == 'P') pink = true;
        if(s == 'W') white = true;
        if(s == 'G') green = true;
        if(s == 'Y') yellow = true;
    }
    if(pink && white && green && yellow){
        cout << "Four" << endl;
    }else{
        cout << "Three" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
from collections import Counter

n = int(input())
s = list(input())

c = Counter(s)
ans = c["R"]*c["G"]*c["B"]

for i in range(n-1):
    for j in range(i+1, (n-i-1)//2+i+1):
        if s[i] != s[j] and s[j] != s[2*j-i] and s[2*j-i] != s[i] :
            ans -= 1

print(ans)

Measured memory_bytes: 9484
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N, M; cin >> N >> M;
    pair<bool, int> S[N];
    repp(i,0,N) S[i] = make_pair(false,0);

    repp(i,0,M) {
        int p; cin >> p;
        string s; cin >> s;

        if (s == "AC") {
            S[p-1].first = true;
        } else if (! S[p-1].first) S[p-1].second += 1;
    }
    int countAC = 0;
    int countWA = 0;

    repp(i,0,N) {
        if (S[i].first) {
            ++countAC;
            countWA += S[i].second;
        }
    }
    cout << countAC << " " << countWA << endl;

}


Measured memory_bytes: 1024
package main

import (
	"bufio"
	_ "container/heap"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	defer wtr.Flush()
	h := sc.nextInt()
	a := sc.nextInt()
	if h <= a {
		fmt.Fprintln(wtr, 1)
		return
	}
	c := h / a
	if h%a != 0 {
		c++
	}

	fmt.Fprintln(wtr, c)
}

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	
	if(a+b>c+d){
		printf("Left\n");
	}else if(a+b<c+d){
		printf("Right\n");
	}else{
		printf("Balanced\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



int main(){
    ll N,x;
    cin>>N>>x;
    if(x==1 || x==2*N-1){cout<<"No"<<endl;}
    else{
        N--;
        cout<<"Yes"<<endl;
        set<ll> S;
        for(int i=1;i<=2*N+1;i++){S.insert(i);}
        vector<ll> ans(2*N+1,-1);
        if(N==1){cout<<1<<" "<<2<<" "<<3<<endl; return 0;}
        ans[N]=x;
        ans[N-1]=1;
        ans[N+1]=2*N+1;
        S.erase(x);
        S.erase(1);
        S.erase(2*N+1);
        if(x!=2*N){
            ans[N-2]=2*N;
            S.erase(2*N);
        }
        else{
            ans[N+2]=2;
            S.erase(2);
        }
        for(int i=0;i<2*N+1;i++){
            if(ans[i]==-1){ans[i]=*S.begin(); S.erase(S.begin());}
        }
        for(auto &I:ans){cout<<I<<endl;}
    }
    
    
    return 0;
}


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
#define MOD 1000000007

int main()
{
  int m,n;cin>>m>>n;
  int left=n;
  ll ans=1;
  ll ks=m;
  while(left>0)
  {
    if(left%2==1)
    {
      ans=(ans*ks)%MOD;
    }
    ks=(ks*ks)%MOD;
    left/=2;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 3100
#include<iostream>
using namespace std;
struct point
{
    int x,y,h;
    point(int xx=0,int yy=0,int hh=0) {x=xx;y=yy;h=hh;}
}p[105];
int manhatun(point a,point b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}
int mins=999999999;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].h);
        if(p[i].h==0)
            n--,i--;
        else
        mins=min(mins,p[i].h);
    }
    if(n==1){
       printf("%d %d %d",p[0].x,p[0].y,p[0].h);
        return 0;
    }
    int k;
    for(int i=0;i<=100;i++)
        for(int j=0;j<=100;j++){
            for(k=0;k<n;k++){
                int t;
                if(k==0)
                    t=manhatun(point(i,j),p[k]);
                else if(manhatun(point(i,j),p[k])-t!=p[0].h-p[k].h)
                    break;
            }
            if(k==n){
                printf("%d %d %lld\n",i,j,(long long)manhatun(point(i,j),p[0])+p[0].h);
                return 0;
            }
        }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

struct Edge {
	int from;
	int to;
	int id;
	long long int cost;
};

int main() {
	while (true) {
		int N;cin>>N;
		if(!N)break;
		long long int ans=1e18;
		for (int x = 1; x < N; ++x) {
			for (int y = 1; y < N; ++y) {
				long long int x3 = x*x*x;
				long long int y3 = y*y*y;
				if (x3 + y3 <= N*N*N) {
					ans=min(ans,N*N*N-x3-y3);
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 3076
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

template <typename T>
T mypow(T a, T b)
{
    if (b == 0)
        return 1;
    T tmp = mypow(a, b / 2);
    if (b % 2)
        return (((tmp * tmp) % MOD) * a) % MOD;
    else
        return (tmp * tmp) % MOD;
}

vector<ll> fact(200020, 1), inv(200020, 1);

ll comb(int n, int k)
{
    if (k < 0 || n < k)
        return 0;
    ll ret = fact[n] * inv[k] % MOD;
    return ret * inv[n - k] % MOD;
}

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

    int n, k;
    cin >> n >> k;
    if (k > (n - 1) * (n - 2) / 2)
    {
        cout << -1 << endl;
        return 0;
    }
    vector<P> ret;
    for (int i = 2; i <= n; i++)
    {
        ret.emplace_back(1, i);
    }
    int cnt = (n - 1) * (n - 2) / 2 - k;
    for (int i = 2; i < n; i++)
    {
        if (cnt == 0)
            break;
        for (int j = i + 1; j <= n; j++)
        {
            if (cnt == 0)
                break;
            ret.emplace_back(i, j);
            cnt--;
        }
    }
    cout << ret.size() << endl;
    for (auto p : ret)
        cout << p.first << " " << p.second << endl;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
#define int long long
main(){
  int n,a,b,c;
  ios_base::sync_with_stdio(false);

  cin >> n;
  int s=0,st=0;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    if(a >= st){
      st = a;
      s = b;
    }
  }

  cout << st+s << endl;

  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define bFor(i,a,b) for(i=a;i>=b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

vec eratosthenes(ll N){
  ll i;
  vec ch(N+1,1),p;
  ch[0]=ch[1]=0;
  rep(i,N+1){
    if(ch[i]){
      p.push_back(i);
      for(ll j=2;i*j<=N;j++){
        ch[i*j]=0;
      }
    }
  }
  return ch;
}
int main(){
  ll i,j,N,a,b,c,ans;
  cin>>N;
  vector<tdata> v(N-1);
  rep(i,N-1){
    cin>>a>>b>>c;
    v[i]=tdata(a,datas(b,c));
  }
  rep(i,N){
    ans=0;
    For(j,i,N-1){
      ans=max(ans,v[j].second.first);
      c=v[j].second.second;
      ans+=(c-ans%c)%c+v[j].first;
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int mark[100005];
int poss[100005];

int main(){
    int N, M;
    int res=0;
    scanf("%d%d", &N, &M);
    for(int i=1; i<=N; i++) mark[i] = 1;
    poss[1] = 1;
    for(int i=0; i<M; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        mark[b]++;
        if(poss[a]) poss[b] = 1;
        mark[a]--;
        if(mark[a] == 0) poss[a] = 0;
    }
    for(int i=1; i<=N; i++) if(poss[i]) res++;
    printf("%d", res);
    return 0;
}

Measured memory_bytes: 896
#include <stdio.h>
int main (){
	int a,b,c,angka = 0;
	scanf ("%d %d %d", &a,&b,&c);
	for (int i = a; i<=b;i++){
		if(i%c==0){
			angka++;
		}
	}
	printf("%d", angka);
	return 0;
}

Measured memory_bytes: 1664
read n

(( n > 10000 )) && M=16384 || M=32768

while read t1 x1 y1; do
    (( RANDOM < M )) &&
    (( d = (t1 - t2) - (x1>x2 ? x1-x2 : x2-x1) - (y1>y2 ? y1-y2 : y2-y1),
       d < 0 || d % 2 )) && echo No && exit
    read t2 x2 y2 || break
    (( RANDOM < M )) &&
    (( d = (t2 - t1) - (x1>x2 ? x1-x2 : x2-x1) - (y1>y2 ? y1-y2 : y2-y1),
       d < 0 || d % 2 )) && echo No && exit
done
echo Yes

Measured memory_bytes: 376
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
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; }
ll mod= 1e9 + 7;

ll f(ll x){
  int d=__builtin_popcount(x);
  return x%d;
}

int main(){
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll count=0; 
  int ans[n]={};
  rep(i,n)if(s[i]=='1')count++;

  ll upq=0;
  ll g=1;
  for(ll i=n-1;i>=0;i--){
    if(i!=n-1)g=g*2%(count+1);
    if(s[i]=='1')upq=(upq+g)%(count+1);
  }

  ll downq=0;
  g=1;
  for(ll i=n-1;i>=0;i--){
    if(count==1)break;
    if(i!=n-1)g=g*2%(count-1);   
    if(s[i]=='1')downq=(downq+g)%(count-1);
  }



  g=1;
  ll g2=1;
  ll p;
  for(ll i=n-1;i>=0;i--){
    if(s[i]=='0'){p=(upq+g)%(count+1); ans[i]++;
      while(p!=0){p=f(p);ans[i]++;}
    }else{
      if(count==1){ans==0;}else{
      p=(downq-g2+count-1)%(count-1); ans[i]++;
      while(p!=0){p=f(p);ans[i]++;}}
    }
    g=g*2%(count+1);
    if(count!=1)g2=g2*2%(count-1);
  }

  rep(i,n){
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 4464
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
  L() {}
};
typedef vector<P> G;
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]


int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}
P crosspoint(const L &l, const L &m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return m[0] + B / A * (m[1] - m[0]);
}

G convex_cut(const G& g, const L& l) {
  G Q;
  REP(i, g.size()) {
    P A = curr(g, i), B = next(g, i);
    if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
    if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0)
      Q.push_back(crosspoint(L(A, B), l));
  }
  return Q;
}
// 垂直二等分線
L bisector(const P &a, const P &b) {
  P A = (a+b)*P(0.5,0);
  return L(A, A+(b-a)*P(0, PI/2));
}
// ボロノイ領域
G voronoi_cell(G g, const vector<P> &v, int s) {
  REP(i, v.size())
    if (i!=s)
      g = convex_cut(g, bisector(v[s], v[i]));
  return g;
}
double area(const G& g) {
  double A = 0;
  for (int i = 0; i < g.size(); ++i) {
    A += cross(g[i], next(g, i));
  }
  return A/2;
}

int main() {
  int n,m;
  while(cin>>n>>m) {
    G g;
    REP(i,n) {
      P p;
      cin >> p.real() >> p.imag();
      g.push_back(p);
    }
    vector<P> v;
    REP(i,m) {
      P p;
      cin >> p.real() >> p.imag();
      v.push_back(p);
    }
    REP(i,m) {
      double ans = area(voronoi_cell(g, v, i));
      printf("%.6f\n", ans);
    }
  }
}

Measured memory_bytes: 0
#import<cstdio>
#define r(a) for(int i=0;i<a;i++)
#define s(a) scanf("%d",&a);
#define c(a,b) a=a<b?a:b
int w,n,m,d[999],p[999];main(){s(n)s(m)r(n)s(d[i])r(n)p[i]=1e9;r(m){s(w)r(n)c(p[i],p[i+1]+w*d[n-i-1]);}printf("%d\n",p[0]);}

Measured memory_bytes: 1032
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
int MOD=1000000007;
signed main(){
    int n,k;cin>>n>>k;
    vector<int> a(n+1);
    rep1(i,n)cin>>a[i];
    vector<int> sum(n+1,0);
    rep1(i,n)sum[i]=sum[i-1]+a[i];
    rep1(i,n){
        sum[i]-=i;
        sum[i]+=k*MOD;
        sum[i]%=k;
    }
    int res=0;
    map<int,int> memo;
    //sort(sum.begin(),sum.end());
    int cur=1;int last=0;
    sum.push_back(MOD*10000000);
    if(k>n+1)k=n+1;
    rep(i,k){
        auto iter=memo.find(sum[i]);
        if (iter != end(memo) ) {
        iter->second++;
    } else {
        memo[sum[i]]=1;
    }
    }
    res+=memo[sum[0]]-1;
    rep1(i,n){
        //printf("sum[%lld]=%lld\n",i,sum[i]);
    }
    for(int i=1;i<n;i++){
        if(i+k-1<n+1){
        auto iter=memo.find(sum[i+k-1]);
        if ( iter != end(memo) ) {
        iter->second++;
    } else {
        memo[sum[i+k-1]]=1;
    }}
    memo[sum[i-1]]--;
        if(false)cur++;
        else{
            cur=memo[sum[i]];
            //last=sum[i];
            res+=cur-1;
            //cout<<res<<endl;
        }
        //printf("sum[%lld]=%lld\n",i,sum[i]);
    }
    //if(a[n]%k==1)res++;
    std::cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 16740
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define all(x) x.begin(),x.end()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
 
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

//
int main(void) {
    string s;
    cin >> s;
    vector<int> a(10);
    rep(i,10){
        int cnt=0;
        for(int j=i;j<10;j++){
            if(s[j]=='A'||s[j]=='C'||s[j]=='G'||s[j]=='T') cnt++;
            else break;
        }
        a.at(i) = cnt;
    }
    sort(all(a),greater<int>());
    cout << a.at(0) << endl;
    return 0;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    cout << n - k + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int A, B;
	cin >> A >> B;
	int ans = 0;
	if(A > B)
	{
		ans += A + (A - 1);
	}
	else if(A < B)
	{
		ans += B + (B - 1);
	}
	else
	{
		ans += A + B;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  fspcnt = 0;
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}*/


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/
vector<int64_t> par(200000);
vector<int64_t> fsiz(200000);
void init(int64_t n){
  rep(i,n){
    par[i] = i;
    fsiz[i] = 1;
  }
}

int64_t root(int64_t x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = root(par[x]);
  }
}

bool same(int64_t x,int64_t y){
  return root(x) == root(y);
}

void unite(int64_t x,int64_t y){
  x = root(x);
  y = root(y);
  if(x == y) return;
  fsiz[y] = fsiz[x] + fsiz[y];
  //fsiz[y] = fsiz[x];
  par[x] = y;
}

int64_t count(int64_t x){
  return fsiz[root(x)];
}
  

int main(){
  int64_t n,m;
  cin >> n >> m;
  vector<int64_t> a(m),b(m);
  rep(i,m){
    cin >> a[i] >> b[i];
  }
  reverse(a.begin(),a.end());
  reverse(b.begin(),b.end());
  vector<int64_t> conv;
  
  conv.push_back((n*(n-1))/2);
  //cout << conv.back() << endl;
  init(n);
  rep(i,m-1){
    //printf("%ld %ld\n",count(a[i]-1),count(b[i]-1));
    if(same(a[i]-1,b[i]-1)){
      conv.push_back(conv.back());
      //cout << "#" << endl;
    }else{
      conv.push_back(conv.back() - (count(a[i]-1)*count(b[i]-1)));
    }
    //cout << conv.back() << endl;
    unite(a[i]-1,b[i]-1);
    //printf("*%ld %ld\n",count(a[i]-1),count(b[i]-1));
    /*rep(i,n){
      cout << fsiz[i];
    }
    cout << endl;*/
  }
  reverse(conv.begin(),conv.end());
  rep(i,conv.size()){
    cout << conv[i] << endl;
  }
    
    
  
}

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

#define F first 
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 100010, M = 2 * N;

int n, x, y;
int h[N], e[M], ne[M], idx;
int dist1[N], dist2[N], q[M];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int u, int dist[])
{
    for (int i = 1; i <= n; i ++ ) dist[i] = -1;

    int hh = 0, tt = -1;
    q[ ++ tt] = u;
    dist[u] = 0;
    
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] != -1) continue;

            dist[j] = dist[t] + 1;
            q[ ++ tt] = j;
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d%d", &n, &x, &y);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs(x, dist1), bfs(y, dist2);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (dist1[i] < dist2[i])
            res = max(res, dist2[i]);

    printf("%d\n", res - 1);
    return 0;
}


Measured memory_bytes: 6884
def d_Iroha_and_a_Grid(H, W, A, B):
    # フェルマーの小定理でnCrを定義
    n = H + W - 2
    M = 10**9 + 7
    factrial = [1] * (n + 2)
    for k in range(1, n + 2):
        factrial[k] = (factrial[k - 1] * k) % M

    fact_inv = [1] * (n + 2)
    fact_inv[n + 1] = pow(factrial[n + 1], M - 2, M)
    for k in range(n, -1, -1):
        fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % M

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n - r]) % M

    ans = 0
    # 左上のマスの座標を(0,0)としたとき、B<=i<=W-1を満たすiについて、
    # (0,0)→(H-A-1,i)への行き方 * (H-A-1,i)→(H-A,i)への行き方(1通り) *
    # (H-A,i)→(H-1,W-1)への行き方 の値の総和を取る(10**9+7で剰余を取る)
    for i in range(B, W):
        ans = (ans + nCr(H - A - 1 + i, H - A - 1, M) *
               nCr(A - 1 + W - 1 - i, A - 1, M)) % M
    return ans

H,W,A,B = [int(i) for i in input().split()]
print(d_Iroha_and_a_Grid(H, W, A, B))

Measured memory_bytes: 18804
L, R = map(int, input().split())

mini = (L * R) % 2019

if R - L >= 2019:
    print(0)
    exit()

for i in range(L % 2019, R % 2019):
    for j in range(i + 1, R % 2019 + 1):
        mini = min(mini, (i * j) % 2019)



print(mini)

Measured memory_bytes: 3060
N,K = map(int,input().split())
P_List = list(map(lambda x: (int(x)+1)/2 ,input().split()))

List2=[0]*(N-K+1)
for i in range(K):
    List2[0] += P_List[i] 

ans = List2[0]

for i in range(1,N-K+1):
    List2[i]=List2[i-1]+P_List[i+K-1]-P_List[i-1]
    if ans < List2[i]:
        ans = List2[i]

print(ans)

Measured memory_bytes: 23140
/*-- ILSH  --*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < ll >
#define vll vector < ll > 
#define dt cout<<"HERE\n";
#define pii pair < ll , ll >
#define pll pair < ll , ll >
#define vpi vector < pii >
#define vpl vector < pll >
#define fi first
#define se second 
#define sz size 
#define len length 
const ll inf=1e18+1e17;
const ll mod =1e9+7;
using cd= complex < double > ;
//const ll mod = 998244353;
ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=	(a*a)%mod;b>>=1;}return (res%mod);}
const ll N = 2e5 +5;


int dp[N][2],arr[N][2];
//,dpi[N][2],dpj[N][2];
void solve(){/*
	int n,q,a,b;
	cin>>n>>q>>a>>b;
	dp[0][0]=0;dp[0][1]=0;
	dpi[0][0]=a;dpi[0][1]=b;
	dpj[0][0]=a;dpj[0][1]=b;
	for ( int i=1;i<=q;i++){
		int pp;
		cin>>pp;
		if ( i==1){
			dp[i][0]=abs( a-pp);
			dp[i][1]=abs( b-pp);
			dpi[i][0]=pp;
			dpi[i][1]=b;
			dpj[i][0]=a;
			dpj[i][1]=pp;
			continue;
		}
		if ( dp[i-1][0]+abs( dpi[i-1][0]-pp)<dp[i-1][1]+abs(dpj[i-1][0]-pp)){
			dp[i][0]=dp[i-1][0]+abs( dpi[i-1][0]-pp);
			dpi[i][0]=pp;
			dpi[i][1]=dpi[i-1][1];
		}
		else
		{
			dp[i][0]=dp[i-1][1]+abs( dpj[i-1][0]-pp);
			dpi[i][0]=pp;
			dpi[i][1]=dpj[i-1][1];
		}
		if ( dp[i-1][1]+abs( dpi[i-1][1]-pp)<dp[i-1][0]+abs(dpi[i-1][1]-pp)){
			dp[i][1]=dp[i-1][1]+abs( dpi[i-1][1]-pp);
			dpj[i][0]=dpj[i-1][0];
			dpj[i][1]=pp;
		}
		else
		{
			dp[i][1]=dp[i-1][0]+abs(dpi[i-1][1]-pp);
			dpj[i][0]=dpi[i-1][0];
			dpj[i][1]=pp;
		}
	}
	for ( int i=0;i<=q;i++)
		cout<<dp[i][0]<<' '<<dp[i][1]<<'\n';
	cout<<min( dp[q][0],dp[q][1])<<'\n';*/
	ll n,t;
	cin>>n>>t;
	ll tot=0;
	ll x=0;
	for ( int i=0;i<n;i++){
		ll aa;
		cin>>aa;
		if ( x>aa){
			tot=tot-(x-aa);
		}
		x=aa+t;
		tot+=t;
	}
	cout<<tot<<'\n';

}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie( NULL);
	cout.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen ("INPUT.txt" , "r" , stdin);
		freopen ("OUTPUT.txt", "w" , stdout);
	#endif
	ll t=1;

//	cin>>t;
	for ( ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
    	solve();
    }
}


Measured memory_bytes: 3636
from itertools import count, combinations

def solve(p,q, limit, balls):
    cost = 0
    while balls:
        cost += 1
        if cost >= limit:
            return limit

        x,y = next(iter(balls))
        balls.discard((x,y))
        try:
            for n in count(1):
                balls.remove((x-n*p, y-n*q))
        except KeyError:
            pass

        try:
            for n in count(1):
                balls.remove((x+n*p, y+n*q))
        except KeyError:
            pass
    return cost


N = int(input())

balls = set(tuple(map(int,input().split())) for _ in range(N))

cost = len(balls)
for (a,b),(c,d) in combinations(sorted(balls), 2):
    cost = solve(a-c, b-d, cost, balls.copy())
print(cost)



Measured memory_bytes: 3064
#line 2 "header.hpp"

//%snippet.set('header')%
//%snippet.fold()%
#ifndef HEADER_H
#define HEADER_H

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

// varibable settings
const long long INF = 1e18;
template <class T> constexpr T inf = numeric_limits<T>::max() / 2.1;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (ll i = (ll)((b)-1); i >= (ll)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T> inline void chmax(T &a, const T &b) { if ((a) < (b)) (a) = (b); }
template <class T> inline void chmin(T &a, const T &b) { if ((a) > (b)) (a) = (b); }
template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector<decltype(cont)>(x, cont); }

#define divceil(a, b) ((a) + (b)-1) / (b)
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x) sort(all(x)); x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef long double ld;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
void check_input() { assert(cin.eof() == 0); int tmp; cin >> tmp; assert(cin.eof() == 1); }

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H */
//%snippet.end()%
#line 2 "solve.cpp"
template<class T=ll> using vec = vector<T>;
struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast;


int solve() {
    string s;cin>>s;
    sort(all(s));
    if (s[0]==s[1] && s[2]==s[3] && s[1]!=s[2]){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0; 
}


int main(){/*{{{*/
    solve();
    check_input();
    return 0;
}/*}}}*/


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

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

#define p(a, b) make_pair(a, b)

/*================================================
	Dijkstra
================================================*/
typedef int COST_TYPE;
#define NMAX (100001 * 3)
#define INF (100000000)
vector<pair<COST_TYPE, int> > G[NMAX];
COST_TYPE cost[NMAX];
bool done[NMAX] = { false };

void dijkstra(int root)
{
	priority_queue<pair<COST_TYPE, int>, vector<pair<COST_TYPE, int> >, greater<pair<COST_TYPE, int> > > PQ;
	pair<COST_TYPE, int> current;	/* first: cost, second: index */
	COST_TYPE next_cost;
	int current_index, next_index, size;

	rep(i, NMAX) {
		done[i] = false;
		cost[i] = INF;
	}

	cost[root] = 0;
	PQ.push(make_pair(0, root));

	while (!PQ.empty()) {
		current = PQ.top();
		PQ.pop();

		current_index = current.second;

		if (done[current_index]) continue;
		done[current_index] = true;

		size = (int)G[current_index].size();
		rep(i, size) {
			next_index = G[current_index][i].second;
			next_cost = G[current_index][i].first;

			if ((!done[next_index])
				&& (cost[next_index] > cost[current_index] + (COST_TYPE)next_cost)) {
				cost[next_index] = cost[current_index] + (COST_TYPE)next_cost;
				PQ.push(make_pair(cost[next_index], next_index));
			}
		}
	}
}

#define id0(n) (3 * (n) - 2)
#define id1(n) (3 * (n) - 1)
#define id2(n) (3 * (n))

int main()
{
	int N, S, T;
	ll M, ans = 0;

	cin >> N >> M;
	rep(i, M) {
		int u, v;
		cin >> u >> v;
		G[id0(u)].push_back(p(1, id1(v)));
		G[id1(u)].push_back(p(1, id2(v)));
		G[id2(u)].push_back(p(1, id0(v)));
	}
	cin >> S >> T;

	dijkstra(id0(S));

	if (cost[id0(T)] >= INF) ans = -1;
	else ans = cost[id0(T)] / 3;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
bool found = false;
string S,T;
int start;
 
int main(){
  cin >> S >> T;
  int N = S.size();
  int M = T.size();
  for (int i = 0;i < N - M + 1;i++){
    if (S[i] == T[0] || S[i] == '?'){
      bool foud = true;
      for (int j = 1;j < M;j++){
        if (S[i+j] != T[j] && S[i+j] != '?'){
          foud = false;
        }
      }
      if (foud){
        start = i;
        found = true;
      }
    }
  }
  for(int i = 0;i<start;i++){
    if (S[i] == '?'){
      S[i] = 'a';
    }
  }
  for(int i = 0;i<M;i++){
    S[i+start] = T[i];
  }
  for(int i = start + M;i<N;i++){
    if (S[i] == '?'){
      S[i] = 'a';
    }
  }
  if (found == false){
    S = "UNRESTORABLE";
  }
  cout << S << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"

int dx8[8] = { -1,-1,-1, 0, 1, 1, 1, 0 };
int dy8[8] = { -1, 0, 1, 1, 1, 0,-1,-1 };

struct aaa {
	int nx;
	int ny;
	int cost;
};

int main() {
	int W, H, K; cin >> W >> H >> K;
	set<pair<int, int>>obset;
	for (int i = 0; i < K; ++i) {
		int a, b; cin >> a >> b;
		obset.emplace(a, b);
	}
	map<pair<int, int>, int>mp;
	deque<aaa>que;
	for (int x = 0; x < W; ++x) {
		mp[make_pair(x, -1)] = 0;
		que.push_back(aaa{ x,-1,0 });
	}
	for (int y = 0; y < H; ++y) {
		mp[make_pair(W,y)] = 0;
		que.push_back(aaa{ W,y,0 });
	}
	int ans = 2;
	while (!que.empty()) {
		auto aa(que.front());
		que.pop_front();
		if (aa.nx == 0 && aa.ny >0) {
			ans = aa.cost;
			break;
		}
		else if (aa.nx < W - 1 && aa.ny ==H-1) {
			ans = aa.cost;
			break;
		}
		for (int way = 0; way < 8; ++way) {
			int nextx = aa.nx + dx8[way];
			int nexty = aa.ny + dy8[way];
			if (nextx >= 0 && nextx < W&&nexty >= 0 && nexty < H) {
				if (nextx == 0 && nexty == 0)continue;
				if (nextx == W - 1 && nexty == H - 1)continue;
				int nextcost = aa.cost;
				bool flag = false;
				if (obset.find(make_pair(nextx, nexty)) == obset.end()) {
					nextcost++;
					flag = true;
				}
				if (nextcost >= 2)continue;
				if (mp.find(make_pair(nextx, nexty)) == mp.end()) {
					mp[make_pair(nextx, nexty)] = 3;
				}
				if (mp[make_pair(nextx, nexty)] > nextcost) {
					mp[make_pair(nextx, nexty)] = nextcost;
					if (flag) {
						que.push_back(aaa{ nextx,nexty,nextcost });
					}
					else {
						que.push_front(aaa{ nextx,nexty,nextcost });
					}
				}
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 71140
#include <cstdio>
#include <cstdlib>

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int x[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&x[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(x[i] >= abs(x[i] - k)){
            ans += abs(x[i] - k);
        }else{
            ans += x[i];
        }
    }
    printf("%d\n",ans * 2);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;
const int N = 20;
int main(int argc, char *argv[])
{
  for(;;) {
    int n, k, s;
    cin >> n >> k >> s;
    if(n == 0 && k == 0 && s == 0) break;
    int cnt = 0;
    for(int i = 0; i < 1<<n; i++) {
      int c = 0, ss = 0;
      for(int j = 0; j < n; j++) {
        if(i & (1<<j)) { c++; ss+=(j+1); }
      }
      if(c == k && s == ss) cnt++;
    }
    cout << cnt << endl;
  }
  return 0;
}



Measured memory_bytes: 3052