akhauriyash/Code-Regression huggingface dataset:
// #define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::string s, t;
  std::cin >> n >> s >> t;

  std::string ans;
  rep(i,0,n) {
    ans.push_back(s.at(i));
    ans.push_back(t.at(i));
  }
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <vector>
#include <queue>
#include <unordered_map> 
#include <iomanip>
#include <random>
#include <future>
#include <thread>
#include <utility>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF (INT_MAX/3)
#define INF_L (LLONG_MAX/3)
#define PSB push_back
#define PN 1000000007
typedef long long LL;
#define int long long


// booooooooooooost
// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// namespace mp = boost::multiprecision;	//多倍長整数(mp::cpp_int), 多倍長小数(mp::cpp_dec_float_100)


signed main() {

	int N, M;
	struct edge { int from, to, cost; };
	vector<edge> es;
	vector<int> d;

	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		es.push_back(edge{ a - 1, b - 1, -c });
	}
	d.assign(N, INF_L);
	d[0] = 0;

	for (int v = 0; v < N; ++v) {
		/* // 負閉路検出
		if (v == N - 1) {
			d[N - 1] = -INF_L;
			break;
		} */

		bool update = false;
		for (int i = 0; i < M; ++i) {
			edge e = es[i];
			if (d[e.from] != INF_L && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}

		if (!update) break;
	}

	bool negative[1000];
	for (int i = 0; i < N; ++i) {
		negative[i] = false;
	}
	for (int loop = 0; loop < N; ++loop) {
		for (int i = 0; i < M; ++i) {
			edge e = es[i];
			if (d[e.from] != INF_L && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				negative[e.to] = true;
			}
			if (negative[e.from] == true) {
				negative[e.to] = true;
			}
		}
	}



	cout << (negative[N - 1] ? "inf" : to_string(-d[N - 1])) << endl;




	return 0;
}

Measured memory_bytes: 384
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

ld f(ld a) {
    ld ans = (1 + a) / 2;
    return ans; 
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<ld> data(N);
    for (int i = 0; i < N; i++) {
        ld a;
        cin >> a;
        data[i] = f(a);
    }
    ld ans = 0;
    for (int i = 0; i < K; i++) {
        ans += data[i];
    }
    ld ansa = ans;
    for (int i = 0; i < N - K; i++) {
        ansa -= data[i];
        ansa += data[K + i];
        ans = max(ans, ansa);
    }
    cout << fixed << setprecision(12);
    cout << ans << endl;
}


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

typedef long long ll;
const int MAX_N = 200000;
const ll INF = (ll) 2e+18;

int main() {
	int N;
	static ll sum[MAX_N] = {};

	std::cin >> N;
	ll s = 0;
	for(int i = 0; i < N; ++i) {
		ll a;
		std::cin >> a;
		s += a;
		sum[i] = s;
	}

	ll ans = INF;
	for(int i = 0; i < N - 1; ++i) {
		ans = std::min(ans, std::abs(sum[N - 1] - 2 * sum[i]));
	}

	std::cout << ans << std::endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstdio>
#include <stack>
#include <functional>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

#define _SI(arr) (sizeof(arr)/sizeof(arr[0])

int main() {
	ll a,b,c;
	cin >> a >> b >> c;
	ll n = 0;


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

}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vv = vector<vector<int>>;
using P = pair<int,int>;

int main(){
  ull n,a,b;
  cin >> n >> a >> b;
  ull cnt = n/(a+b);
  
  n -= cnt*(a+b);
  ull ans;
  if( n >= a ){
    ans = cnt*a + a;
  }else{
    ans = cnt*a + n;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <cmath>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define pb push_back
#define fst first
#define snd second

typedef long long ll;
typedef pair<int,int> pii;
template<typename T> using min_queue=priority_queue<T,vector<T>,greater<T>>;

const ll MOD=1e9+7;

int N;
ll s[200100];

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

  cin>>N;
  for(int i=1;i<=N;i++) cin>>s[i], s[i]+=s[i-1];

  int i=2,j=3,k=4;
  ll res = 1e18;
  while (j<=N-1) {
    while (s[j-1]-s[i-1] > s[i-1]) i++;
    ll a = max(s[i-2], s[j-1]-s[i-1]);
    ll b = s[j-1]-a;

    while (s[N]-s[k-1] > s[k-1]-s[j-1]) k++;
    ll c = max(s[k-2]-s[j-1], s[N]-s[k-1]);
    ll d = s[N]-s[j-1]-c;

    res = min(res, max(max(a,b),max(c,d))-min(min(a,b),min(c,d)));

    j++;
  }

  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

int main() {
  int N;
  double T, A;
  int ans = 0;
  double mind = 100000.0;

  cin >> N;
  cin >> T >> A;

  vector<double> H(N);
  for(int i = 0; i < N; i++){
    cin >> H[i];
  }
  for(int i = 0; i < N; i++){
    if(mind > abs((T-0.006*H[i]) - A)){
      mind = abs((T-0.006*H[i]) - A);
      ans = i+1;
    }
  }

  cout << ans <<endl;
}


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

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

    int n, d, a;
    cin >> n >> d >> a;
    priority_queue<P, vector<P>, greater<P>> Q;
    P p;
    rep(i, n)
    {
        cin >> p.first >> p.second;
        p.second = (p.second + a - 1) / a;
        Q.push(p);
    }
    ll ans = 0;
    ll sum = 0;
    while (Q.size())
    {
        int x = Q.top().first;
        int h = Q.top().second;
        Q.pop();
        if (h > 0)
        {
            if (sum >= h) continue;
            ans += h - sum;
            Q.push(P(x + 2 * d + 1, -(h - sum)));
            sum = h;
        }
        else
        {
            sum += h;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 6000
/**
*    author:  yuya1234
*    created: 27.06.2020 20:57:02
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

#define ALL(x) x.begin(),x.end()
#define SORT(x) sort(x.begin(),x.end())
#define SORTD(x) sort(x.rbegin(),x.rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define SZ(x) ll(x.size())

#define MEMSET(v, h) memset((v), h, sizeof(v))

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

  string s,t;
  cin>>s>>t;

  int cnt=0;

  REP(i,SZ(s))
  {
    if(s[i]!=t[i])
    {
      cnt++;
    }
  }

  cout<<cnt<<endl;

  return 0;
}

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

int main() {
	int h, w;
	while (cin >> h >> w && h != 0 || w != 0) {
		for (int i = 0; i < h; ++i) {
			for (int i2 = 0; i2 < w; ++i2) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 3088
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        a: i64, b: i64,
    }
    puts!("{}\n", max(0, a - 2 * b));
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
{-# LANGUAGE FlexibleContexts, BangPatterns #-}

module Main where

import Data.Char
import Data.List
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Applicative
import Text.Printf


readInt :: IO Int
readInt = read <$> (input `seq` input)
    where input = do
            !c <- getChar
            if isDigit c || c == '-'
                then (c :) <$> input
                else return []

prints :: Show a => [a] -> IO ()
prints as = putStrLn $ concat $ intersperse " " $ map show as

shuffle h t = drop h t ++ take h t

main = do
    t <- getLine
    when (t /= "-") $ do
        m <- readInt
        hs <- replicateM m readInt
        putStrLn $ foldr shuffle t $ reverse hs
        main



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

using namespace std;

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

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

	int n, m;
	cin >> n >> m;

	vector<ll> a(m);
	vector<ll> c(m, 0);
	rep(i, m){
		int b;
		cin >> a[i] >> b;

		rep(j, b){
			int x;
			cin >> x;
			c[i] += 1 << (x - 1);
		}
	}

	// rep(i, m) cout << a[i] << (i == m - 1 ? "\n" : " ");
	// rep(i, m) cout << c[i] << (i == m - 1 ? "\n" : " ");

	ll INF = 1e11;
	vector<vector<ll>> dp(m+1, vector<ll>((1 << n), INF));
	dp[0][0] = 0;

	for(int i = 0; i < m; i++){
		for(int j = 0; j < (1 << n); j++){
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
			dp[i+1][j | c[i]] = min(dp[i+1][j | c[i]], dp[i][j] + a[i]);
		}
	}

	cout << (dp[m][(1 << n) - 1] == INF ? -1 : dp[m][(1 << n) - 1]) << endl;
}


Measured memory_bytes: 32384
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int MOD = 1e9 + 7;

int main()
{
    int n, cnt=0,ans=0;
    cin >> n;
    for(int i=1; i<n; i++)
    {
        if(n%i == 0)
            ans += (n/i) - 1;
        else
            ans += (n/i);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>

int main(){
  
  int l, r, ll, rr, minn;
  
  scanf("%d%d", &l, &r);

  ll = l % 2019;
  rr = r % 2019;
  
  minn = 2019;
  if(r - l > 2019) rr += 2019;

  for (int i=ll;i<rr;i++){
      for (int j=ll+i-ll+1;j<rr+1;j++){
          if(minn > i * j % 2019){
              minn = i * j % 2019;
          }
      }
  }
  printf("%d\n", minn);
  return 0;
}


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



int main() {
    int a,b; cin >> a >> b;

    if((a*b)%2 == 0) cout << "Even" << endl;
    else cout << "Odd" << endl;

    return 0;
}

Measured memory_bytes: 3456
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  string s; cin >> s;
  rep(i,s.size()) {
    if(s[i] == '?') s[i] = 'D';
  }
  cout << s << "\n";
  return 0;
}


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

int main(){
  int N;
  
  while(cin>>N){
    if(N==0){
      return 0;
    }
    int dp[N];
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    if(N<4){
      cout<<1<<endl;
      continue;
    }
    for (int i=4;i<N+1;i++){
      dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
    cout<<dp[N]/3650+1<<endl;
  }
  return 0;
}

    


Measured memory_bytes: 3000
s = input()
t = input()

l = []
for i in range(len(s)-len(t)+1):
    f = 0
    u = s[i:len(t)+i]
    for j in range(len(t)):
        if u[j] != t[j] and u[j] != "?":
            f = 1
    if f == 0:
        l.append((s[:i]+t+s[len(t)+i:]).replace("?","a"))
if l:
    print(sorted(l)[0])
else:
    print("UNRESTORABLE")

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

int main() {
    int N; cin >> N;
    int num[2];
    num[0] = num[1] = 0;

    // num[0] は 4 の倍数の数, num[1] は奇数の数
    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        if (a%4 == 0) num[0]++;
        else if (a%2 == 1) num[1]++;
    }

    if (N%2 == 1 && num[0] + 1 < num[1]) cout << "No" << endl;
    else if (N%2 == 0 && num[0] < num[1]) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

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

int main() {
  int n, a, b, ma, mi, p, q;
  vector<int> nums;
  cin >> n;
  p = q = 0;
  for (int i = 1; i <= n; i++){
    nums.push_back(i);
  } 
  for (int i = n; 0 < i; i--){
    int num;
    cin >> num;
    p += pow(10, i-1)*num;
  }
  for (int i = n; 0 < i; i--){
    int num;
    cin >> num;
    q += pow(10, i-1)*num;
  }
  int cnt = 1;
  do {
    int val = 0;
    for (int i = 0; i < nums.size(); i++){
      val += pow(10, n-i-1)*nums[i];
    }
    if (p == val) a = cnt;
    if (q == val) b = cnt;
    cnt++;
  } while (next_permutation(nums.begin(), nums.end()));
  cout << abs(a-b) << endl;
}

Measured memory_bytes: 3956
n,m =map(int,input().split())

H=[]
H=list(map(int,input().split()))
C=[]
for i in range(n):
    C.append(1)

for i in range(m):
    a,b = map(int,input().split())
    if H[a-1]==H[b-1] :
        C[a-1] = 0
        C[b-1] = 0
    elif H[a-1]<H[b-1] :
        C[a-1] = 0
    else:
        C[b-1] = 0

print( C.count(1))        


Measured memory_bytes: 20052
#include<stdio.h>
int main(void){
  int i, n, k, sum, max, a[100000];
  while(scanf("%d %d", &n, &k), n){
    sum = max = 0;
    for(i = 0; i < n; i++){
      scanf("%d", &a[i]);
      if(i < k)
	sum+=a[i];
    }
    max = sum;
    for(i = k; i < n; i++){
      sum -= a[i - k];
      sum += a[i];
      if(sum > max)
	max = sum;
    }
    printf("%d\n", max);
  }
  return 0;
}

Measured memory_bytes: 988
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[30];
signed main() {
	string w;
	cin>>w;
	for(int i=0;i<w.size();i++){
		a[w[i]-'a']++;
	}
	for(int i=0;i<26;i++){
		if(a[i]%2==1){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい
// https://github.com/atcoder/live_library
// cppdbg: test.exeのterminalに標準入力を打てる

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
#define ub(a,x) (upper_bound(ALL(a),x)-a.begin())
#define lb(a,x) (lower_bound(ALL(a),x)-a.begin())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<ll, vector<ll>, greater<ll> > gpq; //逆順priority_queue
typedef priority_queue<ll> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    int M;cin>>M;
    cout<<48-M<<endl;
}

Measured memory_bytes: 3596
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int calc(long x, long y) {
    long p = x;
    int ans = 1;
    while (p * 2 <= y) {
        p *= 2;
        ans++;
    }
    return ans;
}

void main() {
    auto xy = reads!long;
    long x = xy[0], y = xy[1];
    writeln(calc(x, y));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<static_cast<int>(n);++i)
#define per(i, n) for(int i=static_cast<int>(n)-1;i>=0;--i)
#define eee(a) (cerr<<(#a)<<": "<<(a)<<'\n');
#define ppp(a) (cout<<(a)<<'\n'); 
#define cop(a) for(auto x:(a)){cerr<<(x)<<'\n';}
using ll = long long;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
constexpr ll MOD = 1e9+7;
constexpr ll Mod = 998244353;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
constexpr double phi = (1+sqrt(5))/2;
constexpr double pi = 3.14159265358979323846264338327950288;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll inverse(ll n,ll m=MOD){ll a=n,b=m,x=1,y=0;while(b){ll t=a/b;a-=t*b;swap(a,b);x-=t*y;swap(x,y);}return (a%m+m)%m;}
inline void Yes(){puts("Yes");}
inline void No(){puts("No");}
inline void Judge(bool b){b?Yes():No();}
inline void YES(){puts("YES");}
inline void NO(){puts("NO");}
inline void JUDGE(bool b){b?YES():NO();}
inline ll powmod(ll b, ll e, ll m=MOD){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
inline double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
inline double d2r(double d){return d*pi/180;}
inline double r2d(double r){return r*180/pi;}
template<class T>inline bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}
template<typename T1,typename T2>ostream& operator<<(ostream& s,const pair<T1, T2>& p){return s <<"("<<p.first<<", "<<p.second<<")";}
template<typename T> ostream& operator<<(ostream& s,const vector<T>& v){s<<'[';for(size_t i=0;i<v.size();++i){s<<v[i];if(i<v.size()-1)s<<", ";}s<<']';return s;}


int dp[100010][3];


int main(){
    cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
    
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for(int i = 0; i < n; ++i){
        int a, b, c; cin >> a >> b >> c;
        dp[i+1][0] = max(dp[i][1], dp[i][2]) + a;
        dp[i+1][1] = max(dp[i][0], dp[i][2]) + b;
        dp[i+1][2] = max(dp[i][0], dp[i][1]) + c;
    }
    cout << accumulate(dp[n], dp[n]+3, 3, [](int acc, int x) {return max(acc, x);}) << '\n';
    
    return 0;
}


Measured memory_bytes: 2560
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef int_fast64_t LL;
const int MAXN = 2e5+7;
LL n,k,A[MAXN],sum[MAXN];
map<LL,int> msk;
int main(){
    ____();
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> A[i];
    partial_sum(A+1,A+1+n,sum+1);
    for(int i = 1; i <= n; i++) sum[i] = (sum[i]-i)%k;
    LL tot = 0;
    msk[0]++;
    for(int i = 1; i <= n; i++){
        if(i>=k) msk[sum[i-k]]--;
        tot+=msk[sum[i]];
        msk[sum[i]]++;
    }
    cout << tot << endl;
    return 0;
}

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(ll i=0;i<(n);i++)

using namespace std;



int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    vector<ll> c(n);
    rep(i, n)   cin >> a[i];
    rep(i, n)   cin >> b[i];
    rep(i, n)   cin >> c[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    vector<ll> memob(n, 0);
    ll ia = 0;
    rep(ib, n){
        for(; ia < n; ia++){
            if(a[ia] < b[ib])   continue;
            else                break;
        }
        memob[ib] = ia;
    }

    rep(ib, n-1){
        memob[ib+1] += memob[ib];
    }

    vector<ll> memoc(n, 0);
    ll ib = 0;
    rep(ic, n){
        for(; ib < n; ib++){
            if(b[ib] < c[ic])   continue;
            else                break;
        }
        if(ib == 0) memoc[ic] = 0;
        else        memoc[ic] = memob[ib-1];
    }

    ll sum = 0;
    rep(ic, n)  sum += memoc[ic];

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 4224
K, S = map(int, input().split())

def f():
  if K * 3 >= S:
    for x in range(min(K, S), -1, -1):
      if K * 2 >= S - x:
        for y in range(min(K, S - x), -1, -1):
          if K >= S - x - y:
            yield 1

print(sum(list(f())))


Measured memory_bytes: 39716
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

int D[31][31];
const ll INF=1e9+7;

int main(){
  int n,c;
  cin>>n>>c;
  
  map<int,int> m1,m2,m0;
  for(int i=1;i<=c;i++){
    for(int j=1;j<=c;j++) cin>>D[i][j];
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      int x;
      cin>>x;
      if((i+j)%3==1) m1[x]++;
      else if((i+j)%3==2) m2[x]++;
      else m0[x]++;
    }
  }
  
  int ans=INF;
  for(int i=1;i<=c;i++){
    for(int j=1;j<=c;j++){
      if(j==i) continue;
      for(int k=1;k<=c;k++){
        if(k==i || k==j) continue;
        int sum=0;
        for(auto x:m1) sum+=D[x.first][i]*x.second;
        for(auto x:m2) sum+=D[x.first][j]*x.second;
        for(auto x:m0) sum+=D[x.first][k]*x.second;
        ans=min(ans,sum);
      }
    }
  }
  cout<<ans<<endl;
    
  return 0;
}

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

const long mod = 1000000007L;

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

    ll a[n+10];
    ll sum = 0;
    rep (i, n) {
        cin >> a[i];
        sum += a[i];
        sum %= mod;
    }

    ll ans = 0;

    for (int i = 0; i < n; i++) {
        sum -= a[i];
        sum %= mod;
        ans += a[i] * sum;
        ans %= mod;
    }
    
    if (ans < 0) cout << ans + mod << endl;
    else cout << ans % mod << endl;
    return 0;
    
    
}

Measured memory_bytes: 5124
import sys

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


def main():
    N, K = map(int, readline().split())

    if N % K == 0:
        print(0)
    else:
        print(1)


if __name__ == '__main__':
    main()


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

int main()
{
  int f = 0;
  string a;
  
  cin >> a;
  
  for(int i = 0; i <= a.size() - 1; i++){
    if(a[i] == a[i + 1]){
      f = 1;
    }
  }
  if(f == 1){
    cout<<"Bad"<<endl;
  }else{
    cout<<"Good"<<endl;
  }
}






Measured memory_bytes: 256
#include<stdio.h>

void PrintRectangle(int H,int W){
	int i,j;
	for(i=1; i<= H; i++){
		for(j=1; j<=W; j++){
			printf("#");
		}
		printf("\n");
	}
	printf("\n");
}

int main (void)
{
	int H;
	int W;
	int i,j;
		
	while(1 ){
		scanf("%d %d", &H, &W);
		if(H == 0 && W == 0) break;
		PrintRectangle(H, W);
	
	}
	return 0;
}

Measured memory_bytes: 572
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int s,w;
    cin>>s>>w;
  	if(w>=s)
    cout<<"unsafe";
    else
    cout<<"safe";
    return 0;
}
 

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

int main() {
  string tenki;
  cin >> tenki;
  if(tenki == "RSS" || tenki == "SRS" || tenki == "SSR" || tenki == "RSR")
    cout << 1 << endl;
  if(tenki == "RRS" || tenki == "SRR")
    cout << 2 << endl;
  if(tenki == "RRR")
    cout << 3 << endl;
  if(tenki == "SSS")
    cout << 0 <<endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#define REP(i,n) for (int i=0;i<(n);++i)
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr int INF = 1 << 30;

ll h, w;

ll n, k, s;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> k >> s;
  ll tmp = max(n, k);
  cout << (s + tmp - 1) / tmp;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF LLONG_MAX/10
#define rep(i,n) for(int i=0;i<n;i++)
#define krep(i,k,n,m) for(int i=k;i<n;i+=m)
#define erep(i,k,n) for(int i=k;i<n;i++)
#define mod 1000000007
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
    int n;
    cin>>n;
    int a,b;
    cin>>a>>b;
    if(abs(a-b)%2==0){
        cout<<abs(a-b)/2<<endl;
    }
    else{
        if(a<b){
            if(b-1+a-1<n-a+n-b){
                cout<<(b+a-1)/2<<endl;
            }
            else{
                cout<<(n*2-a-b+1)/2<<endl;
            }
        }
        
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define INT_MAX 999999999
#define ll long long int
using namespace std;
int main()
{
    string s, t;
    cin>>s>>t;
    int n = s.length(), m =  t.length();
    int  dp[n+1][m+1];
    for(int i =0; i<=m; i++)
        dp[0][i] = 0;
    for(int i =0; i<= n; i++)
        dp[i][0] = 0;
    for(int i =1; i<=n;i++)
    {
        for(int j = 1; j<=m; j++)
        {
            if(s[i-1]==t[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else
            {
                dp[i][j]  = max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1]));
            }
        }
    }
    string  r ="";
    int i = n, j =m;
    while(i>0&&j>0)
    {
        if(s[i-1]==t[j-1])
        {
            r+=s[i-1];
            i--;
            j--;
        }
        else if(dp[i-1][j] > dp[i][j-1])
        {
            i--;
        }
        else
            j--;
    }
    reverse(r.begin(), r.end());
    cout<<r<<endl;

}

Measured memory_bytes: 35456
def resolve():
    N = int(input())
    d = list(map(int, input().split()))
    
    d.sort()
    if d[int(N/2-1)] < d[int(N/2)]:
        ans = len(range(d[int(N/2-1)], d[int(N/2)]))
    else:
        ans = 0
    print(ans)
resolve()

Measured memory_bytes: 14556
W, H, N = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(N)]
left_bottom = (0, 0)
right_top = (W, H)
for x, y, a in points:
    if a == 1: left_bottom = (max(x, left_bottom[0]), left_bottom[1])
    elif a == 2: right_top = (min(x, right_top[0]), right_top[1])
    elif a == 3: left_bottom = (left_bottom[0], max(y, left_bottom[1]))
    else: right_top = (right_top[0], min(y, right_top[1]))
width = max(right_top[0] - left_bottom[0], 0)
height = max(right_top[1] - left_bottom[1], 0)
print(width*height)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define inlld(x) scanf("%lld", &x)
#define ind(x) scanf("%d", &x)
#define inlld2(x, y) scanf("%lld%lld", &x, &y)
#define inlld3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z)
#define ind2(x, y) scanf("%d%d", &x, &y)
#define ind3(x, y, z) scanf("%d%d%d", &x, &y, &z)

const int N=2e5+5;
const int MOD=1e9+7;

typedef long long ll;
typedef long double ld;

using namespace std;

ll n, d, A, right_most[N];
pair<ll, ll>arr[N];
ll segt[4*N], lazy[4*N];

inline ll lt(ll x){return 2*x;}
inline ll rt(ll x){return 2*x+1;}

void push(ll nd, ll s, ll e)
{
    segt[nd]+=(e-s+1)*lazy[nd];
    if(s!=e)
    {
        lazy[lt(nd)]+=lazy[nd];
        lazy[rt(nd)]+=lazy[nd];
    }
    lazy[nd]=0;
}

void upd(ll nd, ll s, ll e, ll l, ll r, ll val)
{
    if(lazy[nd])
        push(nd, s, e);
    if(s>r || e<l)
        return;
    if(s>=l && e<=r)
    {
        segt[nd]+=(e-s+1)*val;
        if(s!=e)
        {
            lazy[lt(nd)]+=val;
            lazy[rt(nd)]+=val;
        }
        return;
    }
    ll m=(s+e)/2;
    upd(lt(nd), s, m, l, r, val);
    upd(rt(nd), m+1, e, l, r, val);
    segt[nd]=segt[rt(nd)]+segt[lt(nd)];
}

ll query(ll nd, ll s, ll e, ll idx)
{
    if(lazy[nd])
        push(nd, s, e);
    if(s>idx || e<idx)
        return 0;
    if(s==e)
        return segt[nd];
    ll m=(s+e)/2;
    return query(lt(nd), s, m, idx) + query(rt(nd), m+1, e, idx);
}

int main()
{
    inlld3(n, d, A);
    for(ll a=1; a<=n; a++)
        inlld2(arr[a].f, arr[a].s);
    sort(arr+1, arr+n+1);
    ll ptr=n;
    for(ll a=n; a>=1; a--)
    {
        while(arr[ptr].f-arr[a].f>2*d)
            ptr--;
        right_most[a]=ptr;
    }
    ll ans=0;
    for(ll a=1; a<=n; a++)
    {
        ll decr=query(1, 1, n, a);
        arr[a].s-=decr*A;
        if(arr[a].s<=0)
            continue;
        ans+=(arr[a].s+A-1)/A;
        upd(1, 1, n, a, right_most[a], (arr[a].s+A-1)/A);
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 17408
#include <stdio.h>
#include <string.h>

int main(void) {
  int i, f, l;
  char s[200010];
  scanf("%s", s);
  for(i = 0; ; ++i) if(s[i] == 'A') {
    f = i; break;
  }
  for(i = strlen(s); ; --i) if(s[i] == 'Z') {
    l = i; break;
  }
  printf("%d", l - f + 1);
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <functional>
#include <string>
#include <sstream>
#include <cctype>
using namespace std;


int main(){
  string A, B, C; cin >> A >> B >> C;
  string ans = "";
  ans.push_back(toupper(A.front()));
  ans.push_back(toupper(B.front()));
  ans.push_back(toupper(C.front()));
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cfloat>
#include<functional>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<bitset>
#include<list>
#include<numeric>
#include<complex>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<long long, long long> ll_ll;
typedef pair<double, double> d_d;
typedef vector<int> Vint;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define rep2d(i, j, n) for(i = 0;i < n;++i)for(j = i + 1;j < n;++j)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << x << "\n"
#define pri2(x, y) cout << x << " " << y << "\n"
#define pri3(x, y, z) cout << x << " " << y << " " << z << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << x << "\n"
#define debug2(x, y) cout << " --- " << x << " " << y << "\n"
#define debug3(x, y, z) cout << " --- " << x << " " << y << " " << z << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)


signed main(void){
  int i, j, k;
  for(int testcase = 0;testcase >= 0;testcase++){
    int2(n, m);
    int a[n], cnt[n];
    scn(n, a);
    rep(i, n)cnt[i] = 0;

    rep(i, m){
      int(b);
      rep(j, n)if(b >= a[j]){
        cnt[j]++; break;
      }
    }

    int ma = 0;
    rep1(i, n)if(cnt[ma] < cnt[i])ma = i;
    pri(ma + 1);


/*/

//*/ break;
  }
  return 0;
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
using namespace std;
// {{{
namespace unolight {
#define SZ(x) ((int)(x).size())
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP1(i,a,b) for (int i = a; i <= (int)(b); i++)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP make_pair
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template <class T, class F = less<T>>
void sort_uniq(vector<T> &v, F f = F()) {
    sort(begin(v), end(v), f);
    v.resize(unique(begin(v), end(v)) - begin(v));
}

const int MOD=1000000007;
int n;
LL dp[201][201]; // before i, j items not matched
void main() {
    cin >> n;
    vector<char> s(n);
    REP(i,n) cin >> s[i];
    dp[0][0]=1;
    REP(i,n) REP(j,i+1) {
        if ( s[i]=='-' ) { // i match i
            dp[i+1][j]+=dp[i][j];
            dp[i+1][j]%=MOD;
        } else if ( s[i]=='U' ) { // left i not match
            // right i match with left j (j<i)
            dp[i+1][j]+=dp[i][j]*j%MOD;
            dp[i+1][j+1]%=MOD;
            // right not match
            dp[i+1][j+1]+=dp[i][j];
            dp[i+1][j+1]%=MOD;
        } else { // left i match
            // right i match with left j (j<i)
            dp[i+1][j-1]+=dp[i][j]*j%MOD*j%MOD;
            dp[i+1][j-1]%=MOD;
            // right not match
            dp[i+1][j]+=dp[i][j]*j%MOD;
            dp[i+1][j]%=MOD;
        }
    }
    cout << dp[n][0] << '\n';
}
// }}}
} int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    unolight::main(); return 0;
} 



Measured memory_bytes: 3488
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){ 
	string n;
	cin>>n;
	if(n[0]==n[2]){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	
	}
}

Measured memory_bytes: 256
#include<stdio.h>
long long n,srx[101];//同各位大佬的说法
int i;
long long lgx(long long n)//递推递归函数
{
    if(srx[n])
    return srx[n];//记忆
    if(n>0)
    srx[n]=lgx(n-1)*2+2;//递推递归式
}
int main()
{
    scanf("%d",&n);
    srx[0]=2;
    lgx(n);
    printf("%lld\n",srx[n]);
}

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

const int MOD = 924844033;
const int N = 2007;
long long f[N][N][3];
long long fact[N];

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int k; cin >> k;
    f[0][0][0] = 1;
    int cnt = 0;
    for (int st = 0; st < 2 * k; ++st) {
        for (int i = st; i < n; i += 2 * k) {
            ++cnt;
            for (int err = 0; err <= cnt; ++err) {
                f[cnt][err][0] = (f[cnt - 1][err][0] + f[cnt - 1][err][1] + f[cnt - 1][err][2]) % MOD;
                if (err > 0 && i - k >= 0) f[cnt][err][1] = (f[cnt - 1][err - 1][0] + f[cnt - 1][err - 1][1] + (i == st ? f[cnt - 1][err - 1][2] : 0)) % MOD;
                if (err > 0 && i + k < n) f[cnt][err][2] = (f[cnt - 1][err - 1][0] + f[cnt - 1][err - 1][1] + f[cnt - 1][err - 1][2]) % MOD;
            }
        }
    }
    fact[0] = 1;
    for (int i = 1; i < N; ++i) fact[i] = i * fact[i - 1] % MOD;
    long long res = 0;
    for (int i = 0; i <= n; ++i) {
        res += (i % 2 == 0 ? 1 : -1) * (f[n][i][0] + f[n][i][1] + f[n][i][2]) * fact[n - i] % MOD;
    }
    cout << (res % MOD + MOD) % MOD  << endl;
    return 0;
}


Measured memory_bytes: 54912
#include<stdio.h>
int main(){
	int a,b;
	char st[20];
	bool valid = true;
	
	scanf("%d %d",&a,&b);
	scanf("%s",st);
	
	if(st[a] != '-'){
		valid = false;
	}
	for(int i=0; st[i] !='\0';i++){
		if(i != a){
			if(st[i] < '0' || st[i] > '9'){
				valid = false;
				break;
			}
		}
	}
	(valid) ? puts("Yes") : puts("No");
}


Measured memory_bytes: 1660
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
ll n, m;
ll gap[200010];
int main()
{
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &gap[i]);
	ll dap = 0;
	ll fi = m + gap[1] - 1;
	for (int i = 2; i <= n; i++)
	{
		dap += (min(fi, gap[i]-1) - gap[i - 1]+1);
		fi = m + gap[i] - 1;
	}
	dap += (fi - gap[n] + 1);
	printf("%lld", dap);
}

Measured memory_bytes: 1664
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long 
#define REP(i, a, b) for (ll i = a; i < b; i++)
#define REPI(i, a, b) for (ll i = b - 1; i >= a; i--)
#define i_os ios::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
#define INF (ll)1e18 + 100
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
/*SOME BITMASK KNOWLEDGE
1)x & (x - 1):sets the last one bit of x to zero
power of two exactly when x & (x − 1) = 0.
2)x & -x:sets all the one bits to zero, except last one bit
3)x | (x - 1):inverts all the bits after the last one bit*/
#define o_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define o_setll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
typedef tree<pair<ll, ll>,null_type,less<pair<ll, ll>>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set1;
typedef tree<string,null_type,less<string>,rb_tree_tag,tree_order_statistics_node_update> indexed_set2;
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

int main()
{   
    i_os;
    ll n;
    cin>>n;
    pair<ll,ll> arr[n];
    REP(i,0,n){
        cin>>arr[i].first>>arr[i].second;
    }
    REP(i,0,n){
        ll x = arr[i].first;
        ll y = arr[i].second;
        arr[i].first = x+y;
        arr[i].second = y-x;
    }
    ll maxx = arr[0].first,minx = arr[0].first;
    ll maxy = arr[0].second,miny = arr[0].second;
    REP(i,0,n){
        maxx = max(maxx,arr[i].first);
        minx = min(minx,arr[i].first);
        maxy = max(maxy,arr[i].second);
        miny = min(miny,arr[i].second);
    }
    ll ans = 0;
    REP(i,0,n){
        ans = max({ans,abs(maxx-arr[i].first),abs(minx-arr[i].first),abs(maxy-arr[i].second),abs(miny-arr[i].second)});
    }
    cout<<ans<<endl;
    return 0;
}   
    

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

int main(void){
    int H,W,K,ans=0;
    cin >>H>>W>>K;
    char c[H+1][W+1];
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cin >> c[i][j];
        }
    }
    for(int i=0;i<(1<<(H+W+1));i++){
        int count=0;
        for(int j=1;j<=H;j++){
            for(int k=1;k<=W;k++){
                if(!(i&(1<<j))&&!(i&(1<<(H+k)))&&c[j][k]=='#') count++;
            }
        }
        if(K==count) ans++;
    }
    cout << ans/2;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
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; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int n,k,q; cin >> n >> k >> q;
  int a[q]; REP(i,q) {cin >> a[i]; a[i]--; }

  vector<int> p(n,0);
  REP(i,q) p[a[i]]++;
  REP(i,n) Yes(k - (q-p[i]) > 0);
  return 0;
}

Measured memory_bytes: 1408
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())
S1 = readline().rstrip()
S2 = readline().rstrip()

if S1[0] == S2[0]:
    passflag = 0
    bef = 1
    ans = 3
else:
    passflag = 1
    bef = 0
    ans = 6

for i in range(1,N):
    if passflag:
        passflag = 0
        continue
    if bef:
        if S1[i] == S2[i]:
            ans = ans*2%mod
            passflag = 0
            bef = 1
        else:
            ans = ans*2%mod
            passflag = 1
            bef = 0
    else:
        if S1[i] == S2[i]:
            passflag = 0
            bef = 1
        else:
            ans = ans*3%mod
            passflag = 1
            bef = 0
print(ans)



Measured memory_bytes: 9320
#include<stdio.h>
int main(){
  char s[4];
  scanf("%s",s);
  if(s[2]=='\0'){
    printf("%s",s);
  }else{
    int i;
    for(i=2;i>=0;i--){
      printf("%c",s[i]);
    }
  }
  return 0;
}

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

int main(){
int x,y,z;
while(1){
 cin >> x >> y;
 if (x==0 && y==0) break;
 if(y>x){
  z=x;
  x=y;
  y=z;
  }
 cout << y << " "<< x << endl;
 }
return 0;
}

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 n;
    cin >> n, n++;
    i64 s = (i64) log10(n);
    cout << 9 * s + n / (i64) pow(10, s) - 1 << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 512
/**
*    author:  Dooloper
*    created: 02.05.2020 20:53:40
**/

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>


using namespace std;
typedef unsigned long long ll;

int main() {
    cin.tie(0);
    ll X;cin>>X;
    ll money = 100;
    ll cnt;
    for(int i = 0; ;i++){
        money *= 1.01;
        if(X<=money){
            cnt = i +1;
            break;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

const int N = 100100;

int n,a[N][3],dp[N][3];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=3;j++)
            scanf("%d",&a[i][j]);

    for(int i=n;i>=1;i--)
        for(int last=1;last<=3;last++)
            for(int j=1;j<=3;j++)
                if( j != last )
                    dp[i][last] = max( dp[i][last] , dp[i+1][j] + a[i][j] );

    printf("%d\n",max( { dp[1][1] , dp[1][2] , dp[1][3] } ) );
}


Measured memory_bytes: 6100
def p_a():
    S = int(input())
    max_v = 10 ** 9

    if S > max_v:
        x2 = (S + max_v - 1) // max_v
        x3 = max_v * x2 - S
        print("0 0 " + str(x2) + " 1 " + str(x3) + " " + str(max_v))
    else:
        print("0 0 1 0 0 " + str(S))


if __name__ == '__main__':
    p_a()


Measured memory_bytes: 2940
import sys
N = int(input())
H = list(map(int,input().split()))
for i in range(N) :
    if i == 0 :
        H[i] -= 1
    else :
        if H[i-1] == H[i] :
            pass
        elif H[i-1] <= H[i] - 1  :
            H[i] -= 1
        elif H[i-1] > H[i] :
            print('No')
            sys.exit()
print('Yes')


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


int main()
{
    ll a, b;
    cin >> a >> b;
    if (a == b) {
        cout << 2 * a << endl;
        return 0;
    }
    ll bigger = max(a, b);
    cout << bigger + (bigger - 1) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	//a,b,cは入力値
	int a, b, c;

	//scanf関数でデータを取得
	scanf("%d %d %d",&a, &b, &c);

	//(a < b) かつ (b < c) を満たせば、a < b < c となる
	if((a < b) && (b < c)){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 1928