akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

template <class T> class SegmentTree {
public:
  SegmentTree(const int n, const T id, function<T(T, T)> op,
              function<T(T, T)> updateOp);
  void update(const int index, const T value);
  T find(const int l, const int r);

private:
  int leftChildIndex(const int parent);
  int rightChildIndex(const int parent);
  int parent(const int child);
  int leaf(const int index);
  T query(const int l, const int r, const int node, const int al, const int ar);

private:
  vector<T> data;
  int leafNum;
  T id;
  function<T(T, T)> op;
  function<T(T, T)> updateOp;
};

template <class T>
SegmentTree<T>::SegmentTree(const int n, const T id, function<T(T, T)> op,
                            function<T(T, T)> updateOp)
    : id(id), op(op), updateOp(updateOp) {
  leafNum = 1;
  while (leafNum < n)
    leafNum *= 2;
  data = vector<T>(2 * leafNum - 1, id);
}

template <class T> int SegmentTree<T>::leftChildIndex(const int parent) {
  return parent * 2 + 1;
}

template <class T> int SegmentTree<T>::rightChildIndex(const int parent) {
  return parent * 2 + 2;
}

template <class T> int SegmentTree<T>::parent(const int child) {
  return (child - 1) / 2;
}

template <class T> int SegmentTree<T>::leaf(const int index) {
  return index + leafNum - 1;
}

template <class T> T SegmentTree<T>::find(const int l, const int r) {
  return query(l, r, 0, 0, leafNum);
}

template <class T>
T SegmentTree<T>::query(const int l, const int r, const int node, const int al,
                        const int ar) {
  if (r <= al || ar <= l)
    return id;
  if (l <= al && ar <= r)
    return data[node];
  int mid = (al + ar) / 2;
  T leftValue = query(l, r, leftChildIndex(node), al, mid);
  T rightValue = query(l, r, rightChildIndex(node), mid, ar);
  return op(leftValue, rightValue);
}

template <class T> void SegmentTree<T>::update(const int index, const T value) {
  int i = leaf(index);
  data[i] = updateOp(data[i], value);
  while (i > 0) {
    i = parent(i);
    data[i] = op(data[rightChildIndex(i)], data[leftChildIndex(i)]);
  }
}

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

  vector<int> h(n), a(n);
  REP(i, n) { cin >> h[i]; }
  REP(i, n) { cin >> a[i]; }

  auto op = [](ll a, ll b) -> ll { return max(a, b); };
  SegmentTree<ll> seg(200001, 0, op, op);

  ll ans = 0;
  REP(i, n) {
    ll m = seg.find(0, h[i]);
    seg.update(h[i], m + a[i]);
    ans = max(ans, m + a[i]);
  }

  cout << ans << endl;
}


Measured memory_bytes: 5888
#include <bits/stdc++.h>
#define SIZE 10
#define PI 3.141592653589793

using namespace std;
typedef long long ll;

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

	int N;
	double R;
	int i,j;
	int tmp;
	int answer=0;
	int counter=0;
	vector<int> given;

	cin >> R;

	
	cout << std::fixed << std::setprecision(15) << R*2*PI << endl;

	return 0;
}



Measured memory_bytes: 3812
N, K = map(int, input().split())

height_list = [0] * N

for n in range(N):
    height_list[n] = int(input())
height_list = sorted(height_list, reverse=True)

diff_list = [0] * (N - K + 1)

for i in range(N - K + 1):
    diff_list[i] = height_list[i] - height_list[i + K - 1]
print(min(diff_list))

Measured memory_bytes: 10852
#include <iostream>
using namespace std;
template <class Type>
class BIT {
private:
	int size_; Type *v;
	Type sum(int r) { Type ret = 0; while (r > 0) ret += v[r], r -= r & -r; return ret; }
public:
	BIT() {};
	BIT(int size__) {
		for (size_ = 1; size_ < size__;) size_ <<= 1;
		v = (Type *)malloc(sizeof(Type) * (size_ + 1));
		for (int i = 0; i <= size_; i++) v[i] = 0;
	}
	void add(int i, Type x) { i++; while (i <= size_) v[i] += x, i += i & -i; }
	Type sum(int l, int r) { return sum(r) - sum(l); }
};
int n, q, c, x, y;
int main() {
	cin >> n >> q;
	BIT<int> b(n);
	for (int i = 0; i < q; i++) {
		cin >> c >> x >> y;
		if (!c) b.add(x - 1, y);
		else cout << b.sum(x - 1, y) << endl;
	}
	return 0;
}

Measured memory_bytes: 3604
mylist = []
for i in range(0, 2):
    val = input()
    if ' ' in val:
        mylist.append(val)
a = list((map (int,mylist[0].split(' '))))

cnt = 0
while True:
    map (int,a)
    if all(map(lambda x: x % 2 == 0, a)) == False:
        break
    a = list(map(lambda x:x//2,a))
    cnt +=1
print (cnt)

Measured memory_bytes: 3064
#include <stdio.h>
#define IMAX 100000

int main()
{
  int x,y;
  scanf("%d %d",&x,&y);
  if (!(x%y)) {
    printf("-1\n");
    return 0;
  }
  for(int i=1;i<IMAX;i++){
    int k=x*i;
    if(k%y!=0){
      printf("%d\n",k); break;
    }

  }
  return 0;
}


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

int main() {
	string s;
	cin >> s;
	if (s[1] == s[2]) {
		if (s[1] == s[0] || s[1] == s[3]) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int N;
    cin >> N; 
    int ans = N;
    for(int i = 0; i <= N; i++) {
        int cnt = 0;
        int X = i; 
        int Y = N-i;
        while(X != 0) {
            cnt+=X%6;
            X/=6;
        }
        while(Y != 0) {
            cnt+=Y%9;
            Y/=9;
        }
        ans = min(ans,cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
string s;
int n,num,m=0,i;
int max(int a,int b){
	if(a>b){
		return a;
	}
	if(a<b){
		return b;
	}
	if(a=b){
		return a;
	}
}
int main()
{
    cin>>n>>s;
    for(i=0;i<n;i++){
        if(s[i]=='I'){
        	num++;
		}
        if(s[i]=='D'){
        	num--;
		}
        m=max(m,num);
    }
    cout<<m<<endl;
    return 0;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC() ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL);


int main()
{
    int i = 0, j = 0, cs = 0, in;
    ll n; cin>>n;
    ll x = 26;
    vll v; v.pb(26);
    vll sum; sum.pb(26);
    ll para = 26;
    for(i = 0; i < 11; i++){
        para *= 26;
        v.pb(para);
    }
    for(i = 1; i < v.size(); i++) sum.pb(sum.back() + v[i]);
    int d;
    para = 0;
    for(i = 0; i < v.size(); i++){
        para += v[i];
        if(para >= n){
            d = i+1;
            break;
        }
    }
    string s;
    if(d>1) n-=sum[d-2];
    for(i = d; i > 1; i--){
        ll x = v[i-2];
        int cnt = 1;
        while(x * cnt < n) cnt++;
        s.pb(96+cnt);
        n-=(x*(cnt-1));
    }
    s.pb(96+n);
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3652
// g++ -O3 -fmax-errors=1 -fsanitize=undefined -fsanitize=address -sanitize=leak 
#include <bits/stdc++.h>

using namespace std;

struct KnuthMorrisPratt {
  const int m;
  const vector<int64_t> p;
  vector<int> fail;
  KnuthMorrisPratt(vector<int64_t> p) : m(p.size()), p(p) {
    fail.resize(m+1, -1);
    for (int i = 1, j = -1; i <= m; ++i) {
      while (j >= 0 && p[j] != p[i-1]) j = fail[j];
      fail[i] = ++j;
    }
  }
  template <class F>
  void match(vector<int64_t> s, F f) {
    int n = s.size(), k = 0;
    for (int i = 0; i < n; ++i) {
      while (k == m || (k >= 0 && s[i] != p[k])) k = fail[k];
      if (++k == m) f(i-m+1, i+1); // p[0,m) matches to s[i-m+1,i+1)
    }
  }
};


int main() {
  int n;
  cin >> n;
  vector<int64_t> a(n), b(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];

  vector<int64_t> da(n), db(n);
  da[0] = a[n-1] ^ a[0];
  db[0] = b[n-1] ^ b[0];
  for (int i = 1; i < n; ++i) {
    da[i] = a[i-1] ^ a[i];
    db[i] = b[i-1] ^ b[i];
  }
  vector<int64_t> da2 = da;
  for (int i = 0; i < n-1; ++i) da2.emplace_back(da[i]);

  vector<int> candidate;
  KnuthMorrisPratt kmp(db);
  kmp.match(da2, [&](int i, int j) {
    candidate.emplace_back(i);
  });
  // a[i, i+n) == b[0,n)
  for (int k: candidate) {
    int64_t x = a[0+k] ^ b[0];
    printf("%d %ld\n", k, x);
  }
}


Measured memory_bytes: 17580
#include <stdio.h>
#define BUILDINGS 4
#define FLOORS 3
#define ROOMS 10

void
priHouse(const int [BUILDINGS][FLOORS][ROOMS]);

int
main(void)
{
    int house[BUILDINGS][FLOORS][ROOMS] = {};
    int n, building, floor, room, people;
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d %d %d", &building, &floor, &room, &people);
        house[building - 1][floor - 1][room - 1] += people;
    }
    priHouse(house);
    return 0;
}

void
priHouse(const int house[BUILDINGS][FLOORS][ROOMS])
{
    int i, j, k;
    for (i = 0; i < BUILDINGS; i++) {
        for (j = 0; j < FLOORS; j++) {
            for (k = 0; k < ROOMS; k++)
                printf(" %d", house[i][j][k]);
            putchar('\n');
        }
        if (i < BUILDINGS - 1)
            puts("####################");
    }
}


Measured memory_bytes: 2044
//om namah shivaaay//
#include <bits/stdc++.h>
#define Om_namah_Shivaay ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
 using namespace std;
 int main()
 {
    Om_namah_Shivaay;
    string s;
    cin>>s;
    if(s.at(2)==s.at(3) && s.at(4)==s.at(5))
    {
		cout<<"Yes";
		
		}
		else{	cout<<"No";}}
    
    


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <map>
using namespace std;

typedef unsigned long ul;
typedef array<ul, 6> dice;

bool f(int n)
{
    static const array<dice, 6> tbl = {
            0,1,2,3,4,5, 1,5,2,3,0,4, 2,1,5,0,4,3,
            3,1,0,5,4,2, 4,0,2,3,5,1, 5,1,3,2,4,0};
    dice d;
    map<ul, bool> db;
    array<ul, 24> r;

    while (n--) {
        for (ul &a: d)
            cin >> a;
        int i = 0;
        for (dice t: tbl) {
            for (int j = 0; j < 4; j++) {
                ul u = 0;
                for (int k = 0; k < 6; k++)
                    u += (d[t[k]] + 1) << k * 10;
                if (db.count(u))
                    return true;
                r[i * 4 + j] = u;
                ul x = t[1]; t[1] = t[2]; t[2] = t[4]; t[4] = t[3]; t[3] = x;
            }
            i++;
        }
        for (ul x : r)
            db[x] = true;
    }
    return false;
}

int main()
{
    int n;
    cin >> n;
    cout << (f(n) ? "No" : "Yes") << endl;
}


Measured memory_bytes: 3144
import java.util.*;

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

        String s, ans = "";

        s = scan.nextLine();
        for(int i = 0; i < s.length(); i++) {
            String a = s.substring(i, i + 1);
            char[] c = a.toCharArray();
            if(Character.isUpperCase(c[0])) {
                ans += a.toLowerCase();
            } else if(Character.isLowerCase(c[0])) {
                ans += a.toUpperCase();
            } else {
                ans += a;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 31704
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new java.util.Scanner(System.in);
		int count,Judg,taroP=0,hanakoP=0;
		String taroC,hanakoC;
		count= sc.nextInt();

		for(int i =0; i<count; i++) {
			taroC = sc.next();
			hanakoC = sc.next();
			Judg = taroC.compareTo(hanakoC);
			if(Judg==0) {
				taroP++;
				hanakoP++;
			}else if(Judg<0) {
				hanakoP +=3;
			}else if(Judg>0) {
				taroP +=3;
			}
		}
		System.out.println(taroP+" "+hanakoP);
	}
}



Measured memory_bytes: 30684
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(const void *a, const void *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(const void* left, const void* right) {return strcmp((char *)left,(char *)right);}
int downchar(const void* left, const void* right) {return strcmp((char *)right,(char *)left);}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1){
            res *= a; if(mod>=1) res %= mod;
        }
        a *= a; if(mod>=1) a %= mod;
        n >>= 1;
    }
    return res;
}
void initialize(){
    
}
ll x[LIMIT2]={0},h[LIMIT1]={0};
int c[LIMIT1]={0};
int tmp(cv *p,cv *q){
  return x[*(int *)p]-x[*(int *)q];
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0,d,a,l,r;
  char s[LIMIT1];
  ll sum[LIMIT1]={0};//累積和(攻撃回数)
  ll total=0;
  
  scanf("%lld %lld %lld",&n,&d,&a);
  rep(i,n){
    scanf("%lld %lld",&x[i],&h[i]);
    h[i] = (ll)ceill((ld)h[i]/a);//hp->攻撃数
    c[i]=(int)i;
  }
  qsort(c,n,sizeof(int),tmp);
  l=0;
  r=0;
  rep(l,n){
    total+=sum[l];
    //printf("%lld\n",(ll)h[c[l]]-total);
    if(h[c[l]]<=total){
      continue;//already fainted
    }
    while(r<n && x[c[r]]<=x[c[l]]+2*d){
      r++;
    }
    //printf("%lld %lld\n",l,r);
    sum[l]+=h[c[l]]-total;
    if(r<n){
      sum[r]-=h[c[l]]-total;
    }
    result+=h[c[l]]-total;
    total+=h[c[l]]-total;
    //printf("%d %d\n",(x[c[l]])+(int)d,h[c[l]]-total);
    if(l==r) r++;
    else{
    }
  }
  printf("%lld\n",result);
  return 0;
}



Measured memory_bytes: 6652
# inputを高速化する。
import sys
input = sys.stdin.readline

n = int(input())

count  = [[0] * 3 for i in range(n)]

for i in range(n):
    a, b, c = map(int, input().split())

    if i == 0:
        count[i][0] = a
        count[i][1] = b
        count[i][2] = c

    else:
        count[i][0] = a + max(count[i-1][1],count[i-1][2])
        count[i][1] = b + max(count[i-1][0],count[i-1][2])
        count[i][2] = c + max(count[i-1][0],count[i-1][1])
        

print(max(count[-1][0],count[-1][1],count[-1][2]))

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

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  
  int rgb = r*100 + g*10 + b;  
  if ( rgb % 4 == 0 ) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var z = 0;
            for (int i = 0; i < s.Length; i++)
            {
                z += int.Parse(s[i].ToString());
            }
            if (long.Parse(s) % z == 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <iomanip>
#include <cmath>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N,K;cin>>N>>K;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    sort(A.begin(),A.end());
    int ans = 0;
    REP(i,N-1){
        if(K>=A[i]){
            ++ans;
            K -= A[i];
        }
    }
    if(K==A[N-1]) ++ans;
    cout << ans << '\n';
    return 0;
}

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

int main() {
    unsigned int a, b;
    cin >> a >> b;
    a -= 2;
    b -= 2;
    if (a == b) {
        cout << "Draw" << endl;
    } else if (a < b) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>

#define LOT_NUMBER 30


void cross_num(int lot_num[LOT_NUMBER], char *r, char *l);


main()
{
	int line_lot, bridge;
	char *bridge_num;
	bridge_num = (char*)malloc( sizeof( char) * 4 );
	int i, j;
	scanf("%d", &line_lot);
	int lot_number[line_lot];
	for(i = 0; i < line_lot; i++)
	{
		lot_number[i] = i + 1;
	}
	scanf("%d", &bridge);
	
	for(i = 0; i < bridge; i++)
	{
		scanf("\n");
		gets(bridge_num);
		char *r = strtok(bridge_num, ",");
		char *l = strtok(NULL, ",");
		cross_num(lot_number, r, l);
	}
	
	for(j = 0; j < line_lot; j++)
	{
		printf("%d\n", lot_number[j]);
	}
	return 0;
}

void cross_num(int lot_num[LOT_NUMBER], char *r, char *l)
{
	int right = atoi(r) - 1;
	int left = atoi(l) - 1;
	int temp = lot_num[right];
	lot_num[right] = lot_num[left];
	lot_num[left] = temp;
}

Measured memory_bytes: 596
package main

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

func main() {
	n := nextInt()
	k := nextInt()

	initFact(n * 2)
	if n < k {
		fmt.Println(dupcomb(n, n))
		return
	}

	ans := mint(0) // 移動なし

	for i := 0; i <= k; i++ {
		a := comb(n, i).mul(comb(n-1, i)) // i人いる部屋の位置 * 残り(n-i)人が(n-1)部屋に移動
		ans = ans.add(a)
	}

	fmt.Println(ans)
}

var facts []mint  // facts[i] = i!
var ifacts []mint // ifacts[i] = i!の逆元

// nの階乗までを初期化します
func initFact(n int) {
	facts = make([]mint, n+1)
	ifacts = make([]mint, n+1)
	facts[0] = mint(1)
	ifacts[0] = mint(1)
	m := mint(n)
	for i := mint(0); i < m; i++ {
		facts[i+1] = facts[i].mul(i.add(1))
		ifacts[i+1] = ifacts[i].mul(i.add(1).pow(mod - 2))
	}
}

// perm はnPkを返します
func perm(n, k int) mint {
	if n < k {
		return 0
	}
	return ifacts[n-k].mul(facts[n])
}

// comb はnCkを返します
func comb(n, k int) mint {
	if n == 0 && k == 0 {
		return mint(1)
	} else if n < k || n < 0 {
		return mint(0)
	}
	return facts[n].mul(ifacts[n-k]).mul(ifacts[k])
}

// dupcomb はnHkを返します
func dupcomb(n, k int) mint {
	if n == 0 && k == 0 {
		return mint(1)
	} else if n < 0 || k == 0 {
		return mint(0)
	}
	return facts[n+k-1].mul(ifacts[n-1]).mul(ifacts[k])
}

type mint int64

var mod = mint(1e9 + 7)

// add は a + bを返します
func (a mint) add(b mint) mint {
	return (a + b) % mod
}

// sub は a - bを返します
func (a mint) sub(b mint) mint {
	return (a - b + mod) % mod
}

// mul は a * bを返します
func (a mint) mul(b mint) mint {
	return (a * (b % mod)) % mod
}

// div は a/bを返します
func (a mint) div(b mint) mint {
	return a.mul(b.inv())
}

// inv は aの逆元を返します
func (a mint) inv() mint {
	// 拡張ユークリッドの互除法
	b := mod
	u := mint(1)
	v := mint(0)
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	return (u + mod) % mod
}

// pow は a ^ bを返します
func (a mint) pow(b mint) mint {
	ans := mint(1)

	for b != 0 {
		if b&1 == 1 {
			ans = ans.mul(a)
		}
		a = a.mul(a)
		b = b >> 1
	}
	return ans
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 7552
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}



int main(void) {
    FAST_IO;
    
    int k, n;
    cin >> n >> k;
    vector<double> v;
    for (int i = 0; i < n; i++) {
        double x;
        cin >> x;
        v.push_back((1 + x) * x / 2 / x);
    }
    vector<double> sum(n + 10);
    double ans = 0, temp = 0;;
    for (int i = 0; i < k; i++) {
        temp += v[i];
    }
    ans = temp;
    for (int i = k, j = 0; i < n; i++, j++) {
        temp = temp - v[j];
        temp = temp + v[i];
        ans = max(temp, ans);
    }
    cout << fixed << setprecision(12) << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3568
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def lucas(n, k):
    return (n&k) == k

N = INT()
A = [a-1 for a in list(map(int, input()))]

def check(A):
    mod2 = 0
    for i, a in enumerate(A):
        if a == 1:
            mod2 += lucas(N-1, i)
            mod2 %= 2
    return mod2

res = check(A)
if res == 1:
    print(1)
    exit()

if A.count(1):
    print(0)
    exit()

A = [a//2 for a in A]
res = check(A)
if res == 1:
    print(2)
else:
    print(0)


Measured memory_bytes: 26720
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <cstring>
#include <iomanip>
#include<queue>
#include<set>
#include<stack>
#include<fstream>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1844674407370955161
typedef long long int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007


int main()
{
	int X,Y;
	cin>>X>>Y;
	if(Y%2!=0){
		cout<<"No"<<endl;
		return 0;
	}
	if((Y-2*X)<0||(4*X-Y)<0){
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
	return 0;
	
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
            dp[i] = Integer.MAX_VALUE;
        }

        dp[0] = 0;
        for (int i = 0; i < n-1; i++) {
            dp[i + 1] = Math.min(dp[i + 1], dp[i] + Math.abs(h[i] - h[i + 1]));
            if (i + 2 < n) {
                dp[i + 2] = Math.min(dp[i + 2], dp[i] + Math.abs(h[i] - h[i + 2]));
            }
        }
        System.out.println(dp[n-1]);

    }
}


Measured memory_bytes: 60252
def c_walking_takahashi():
    X, K, D = [int(i) for i in input().split()]
    x = abs(X)
    need_move, r = divmod(x, D)  # 位置 r に到達するには need_move 回の移動が必要
    if need_move >= K:
        return x - K * D  # r には到達できない。動ける限り動いた結果がこれ
    can_move = K - need_move
    # 動ける回数が偶数回だと位置 r で、奇数回だと abs(r-D)=D-r で終了する
    if can_move % 2 == 0:
        return r
    return D - r

print(c_walking_takahashi())

Measured memory_bytes: 9176
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define iin(x) scanf("%d", &x)
#define lin(x) scanf("%lld", &x)
#define fin(x) scanf("%lf", &x)

#define iout(x) printf("%d", x)
#define lout(x) printf("%lld", x)
#define fout(x) printf("%.10f", x)
#define _ putchar(' ')
#define endl puts("")

#define reps(i, x, n) for(i = (x); i < (n); i++)
#define rep(i, n) reps(i, 0, n)

int n;
int r[101], c[101], R[101];
int dp[101][101];

int min(int a, int b) {
  return a < b ? a : b;
}

int main() {
  int i, j, k;
  iin(n);
  rep(i, n) iin(r[i]), iin(c[i]);
  R[0] = r[0];
  reps(i, 1, n+1) R[i] = c[i-1];
  rep(i, 101) {
    rep(j, 101) dp[i][j] = 1<<25;
    dp[i][i] = 0;
  }
  reps(i, 1, n+1) {
    rep(j, n-i) {
      reps(k, j+1, i+j+1) {
	dp[j][i+j] = min(dp[j][i+j], dp[j][k-1] + dp[k][i+j] + R[j]*R[k]*R[i+j+1]);
      }
    }
  }

  iout(dp[0][n-1]),endl;

  return 0;
}

Measured memory_bytes: 648
from fractions import gcd
N = int(input())
a = list(map(int, input().split()))
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0+1)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        if data[2*k+1] == INF:
            data[k] = data[2*k+2]
        elif data[2*k+2] == INF:
            data[k] = data[2*k+1]
        else:
            data[k] = gcd(data[2*k+1], data[2*k+2])

for i in range(N):
    update(i, a[i])

ans = 0
for i in range(N):
    update(i, INF)
    ans = max(ans, data[0])
    update(i, a[i])

print(ans)


Measured memory_bytes: 90496
import java.io.*;
import java.util.*;

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

    String[] values = in.readLine().split(" ");
    int N = Integer.parseInt(values[0]);
    int M = Integer.parseInt(values[1]);

    int[] A = new int[M], B = new int[M];
    for (int i = 0; i < M; ++i) {
      values = in.readLine().split(" ");
      A[i] = Integer.parseInt(values[0]);
      B[i] = Integer.parseInt(values[1]);
    }

    System.out.println(solve(N, M, A, B));

    in.close();
  }

  private static int solve(int N, int M, int[] A, int[] B) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (int i = 0; i < M; ++i) {
      addEdge(graph, A[i], B[i]);
      addEdge(graph, B[i], A[i]);
    }

    int numGroups = 0;
    Integer[] nodeGroupMap = new Integer[N + 1];
    for (int i = 1; i <= N; ++i) {
      if (nodeGroupMap[i] == null) {
        nodeGroupMap[i] = numGroups;
        groupNodes(graph, i, nodeGroupMap, numGroups++);
      }
    }

    int maxGroupSize = 0;
    int[] groupSizes = new int[numGroups];
    for (int i = 1; i <= N; ++i) {
      groupSizes[nodeGroupMap[i]]++;
      maxGroupSize = Math.max(maxGroupSize, groupSizes[nodeGroupMap[i]]);
    }

    return maxGroupSize;
  }

  private static void addEdge(Map<Integer, Set<Integer>> graph, int from, int to) {
    Set<Integer> adjacents = graph.getOrDefault(from, new HashSet<>());
    adjacents.add(to);
    graph.put(from, adjacents);
  }

  private static void groupNodes(Map<Integer, Set<Integer>> graph, int node, Integer[] nodeGroupMap, int group) {
    if (graph.containsKey(node)) {
      for (int next : graph.get(node)) {
        if (nodeGroupMap[next] == null) {
          nodeGroupMap[next] = group;
          groupNodes(graph, next, nodeGroupMap, group);
        }
      }
    }
  }
}

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

lint n, a, x[52], dp[52][52][52*52];

int main(){
    cin >> n >> a;
    for(int i=0;i<n;i++) cin >> x[i];

    for(int i=0;i<n;i++) dp[i][0][0]++;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=2500;k++){
                dp[i][j][k] = dp[i-1][j][k];
                if(x[i-1]<=k) dp[i][j][k] += dp[i-1][j-1][k-x[i-1]];
            }
        }
    }

    lint ans = 0;
    for(int i=1;i<=n;i++) ans += dp[n][i][a*i];

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 55168
import java.util.*;
import java.math.*;
public class Main{
        public static void main(String args[])
        {

            
            Scanner sc = new Scanner(System.in);
           int a = sc.nextInt();
           int b = sc.nextInt();
         if((a<=9 && a>=1) && (b<=9 && b>=1))
            System.out.println(a*b);
            else
            System.out.println("-1");
        }
}


Measured memory_bytes: 21716
fun main(args: Array<String>) {
  val sc = if (args.size > 1) java.util.Scanner(java.io.File(args[1])) else java.util.Scanner(System.`in`)
  solve(sc)
}

fun solve(sc: java.util.Scanner) {
  val A = IntArray(sc.nextInt()) { sc.nextInt() }
  val a = mutableSetOf<Int>()
  A.forEach {
    if (a.contains(it)) {
      a.remove(it)
    } else {
      a.add(it)
    }
  }
  println(a.count())
}


Measured memory_bytes: 59364
// https://atcoder.jp/contests/abc164/tasks/abc164_a
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int S, W;
    cin >> S >> W;
    if (W >= S) {
        cout << "unsafe\n";
    } else {
        cout << "safe\n";
    }

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int main(){
    int A,B,C; cin>>A>>B>>C;

    int m=A%B;
    int _m=m;
    set<int> s;
    while(s.count(C)==0 && s.count(_m)==0){
        s.insert(_m);
        _m=(_m+m)%B;
    }

    string ans="YES";
    if(s.count(C)==0) ans="NO";
    cout<<ans<<endl;
}

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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    if(s[k-1] == 'A'){
        s[k-1] = 'a';
    }else if(s[k-1] == 'B'){
        s[k-1] = 'b';
    }else{
        s[k-1] = 'c';
    }
    cout << s << endl;
}

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

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<string>> s(N, vector<string>());
    for (int i = 0; i < M; i ++) {
        int p;
        string t;
        cin >> p >> t;
        p--;
        s[p].push_back(t);
    }
    int ac = 0;
    int pena = 0;
    for (auto& v: s) {
        int pena_tmp = 0;
        bool is_ac = false;
        for (auto& u: v) {
            if (u == "AC") {
                is_ac = true;
                break;
            } else {
                pena_tmp ++;
            }
        }
        if (is_ac) {
            ac++;
            pena += pena_tmp;
        }
    }
    cout << ac << " " << pena << endl;

    return 0;
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int maxV = 90010;
const int maxN = 3e5+10;
const int inf = 0x3f3f3f3f;
const ll MOD = 1e9+7;
const ll INF = 1000000000000000010LL;
#define X first
#define Y second

ll a[maxN];
ll power(ll x,ll p)
{
	if(p==0)
	{
		return 1;
	}
	ll t = power(x,p/2);
	t = t*t % MOD;
	if(p % 2 == 1)
	{
		t = t*x %MOD;
	}
	return t;
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	ll ans = 0;
	for(int k=0;k<60;k++)
	{
		ll cnt = 0;
		for(int i=1;i<=n;i++)
		{
			if(a[i] & (1ll<<k))
			{
				cnt++;
			}
		}
		ll sum = 2* cnt * (n-cnt)%MOD;
		ans += sum * power(2,k) % MOD;
		ans %= MOD;
	} 
	ans = ans * power(2,MOD-2) % MOD;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define ref(i,n) for(long long i=0;i<n;i++)
using namespace std;
#define mo 1000000007

typedef pair<long long,long long> P;
set<P> v;
map<P,long long> mp;

long long gcd(long long m,long long n){
    if(m==0) return n;
    if(n==0) return m;
    if(n>m) return gcd(m,n%m);
    else return gcd(n,m%n);

    }

int main()
{
    int n;
    cin>>n;
    long long a0=0,aa=0,a1=0,yy;

    ref(i,n){
        long long x,y;
        cin>>x>>y;
        if(!x&&!y){aa++;continue;}
        if(y==0) {a0++;continue;}
        if(x==0) {a1++;continue;}
        if(x<0){ x=-x;y=-y;}

        if(y>0) yy=y; else yy=-y;

        P p=P(x/gcd(x,yy),y/gcd(x,yy));

        if(v.find(p)!=v.end()) mp[p]++;
        else {mp[p]=1;v.insert(p);}
    }
    long long ans=1;


    auto j=v.begin();

    ref(i,v.size()){

        P t=*j,p;
        if(t.second<0) {
            p=P(-t.second,t.first);
        }
        else p=P(t.second,-t.first);

        if(v.find(p)!=v.end()){

            long long y1=1,y2=1;

            ref(k,mp[t]) y1=y1*2%mo;
            ref(k,mp[p]) y2=y2*2%mo;

            long long yy=(y1+y2-1)%mo;

            ans=ans*yy%mo;
            mp[t]=0;mp[p]=0;

        }
    j++;
    }


    auto i=mp.begin();

    ref(k,mp.size()){
        long long xx=1;
        ref(k,i->second) xx=xx*2%mo;
        ans=ans*xx%mo;
        i++;
    }



        long long y1=1,y2=1;

        ref(k,a0) y1=y1*2%mo;
        ref(k,a1) y2=y2*2%mo;

        long long ye=(y1+y2-1)%mo;

        ans=ans*ye%mo;



    ans+=aa;
    ans%=mo;
    if(ans==0) ans+=mo;
    cout<<ans-1;
    return 0;

}


Measured memory_bytes: 28636
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (n); i++)
 
int main(){
    int M1,D1,M2,D2;
    cin >> M1 >> D1 >> M2 >> D2;
    if(D1 == 31 || D2 == 1){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }
 
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string>
#include <cstring>
using namespace std;

typedef long long ll;

void solve()
{
    int x, y;
    cin >> x >> y;
    int b = y / 2 - x;
    if ((y - 2 * x) % 2 == 0 && b >= 0 && b <= x)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
int main()
{
    solve();
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ZERO(a) memset(a,0,sizeof(a))

const int M = 55;
int w,h;
int f[M][M];
int dx[] = {1,1,1,0,0,-1,-1,-1};
int dy[] = {0,1,-1,1,-1,0,1,-1};

void dfs(int x, int y) {
    if(x == w || y == h) return ;
    f[y][x] = 0;
    rep(i,8) {
        int nx = x+dx[i], ny = y+dy[i];
        if(f[ny][nx] == 1)
            dfs(nx, ny);
    }
}

int main() {
    while(cin>>w>>h && w) {
        ZERO(f);
        rep(i,h) rep(j,w) cin >> f[i][j];

        int ans = 0;
        rep(i,h) rep(j,w) {
            if(f[i][j] == 0) continue;
            dfs(j,i);
            ans++;
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 1252
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;


int main() {
	int i, n, x;
	cin >> n >> x;
	vector<ll>a(n), mn(n);
	for (i = 0; i < n; i++) cin >> a[i];
	mn = a;
	ll ans = INF * INF;
	for (int rotate = 0; rotate < n; rotate++) {
		ll tmp = (ll)rotate * x;
		for (i = 0; i < n; i++) mn[i] = min(mn[i], a[(i - rotate + n)%n]);
		for (i = 0; i < n; i++)tmp += mn[i];
		ans = min(ans, tmp);
	}
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
const ll mod = 7 * 17 * (1 << 23) + 1;
const ll inf = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() { //DINIC ORZ
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n, s;
	vi a;
	cin >> n >> s;
	a.resize(n);
	for(auto &i : a) cin >> i;
	sort(all(a));
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		if(s>=a[i]) s-=a[i], ans++;
		else break;
	}
	if(ans==n&&s) ans--;
	cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int k;
    string s;
    cin>>k>>s;
    if(s.size()<=k) cout<<s<<endl;
    else{
        for(int i=0;i<k;i++){
            cout<<s.at(i);
        }
        cout<<"..."<<endl;
    }
}

Measured memory_bytes: 3628
integer N
integer(8) MARCH(5)
character FirstCharacter
integer(8) ans
integer i,j,k
read*,N

MARCH=0
do i=1,N
  read*,FirstCharacter
  if(FirstCharacter=="M")MARCH(1)=MARCH(1)+1
  if(FirstCharacter=="A")MARCH(2)=MARCH(2)+1
  if(FirstCharacter=="R")MARCH(3)=MARCH(3)+1
  if(FirstCharacter=="C")MARCH(4)=MARCH(4)+1
  if(FirstCharacter=="H")MARCH(5)=MARCH(5)+1
end do

ans=0
do i=1,3
  do j=i+1,4
    do k=j+1,5
      ans=ans+MARCH(i)*MARCH(j)*MARCH(k)
    end do
  end do
end do

print"(I0)",ans
end

Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <ctime>
#include <cassert>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define eps 1e-9

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

const int INF = 0x7fffffff;
const int maxn = 2e5 + 10;
int T, n;
int a[maxn];

int main() {
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif // __AiR_H
    scanf("%d %d", &n, &T); ll ans = 0; int t;
    REP(i, n) { scanf("%d", &a[i]); } ans = a[0] + T; t = a[0] + T;
    for (int i = 1; i < n; ++i) {
        if (a[i] == 0) { continue; }
        if (t < a[i]) { ans += T; t = a[i] + T; continue; }
        ans += a[i] + T - t; t = a[i] + T;
    }
    cout << ans << endl;
#ifdef __AiR_H
    printf("Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC);
#endif // __AiR_H
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
 
typedef long long int ll;

const int MOD = 1e9 + 7;
const int INV2 = MOD/2 + 1;
const int N = 5050;

int n,m,pot[N],ipot[N];
int dp[N][N], cum[N];

void add(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;

    pot[0] = ipot[0] = 1;
    forsn(n,1,N) {
        pot[n] = 2 * pot[n-1] % MOD;
        ipot[n] = ll(INV2) * ipot[n-1] % MOD;
    }

    for (int j = 1; j <= m; j++) dp[0][j] = 1;
    for (int i = 1; i <= n; i++) {
        forn(j,m+1) {
            cum[j+1] = cum[j];
            add(cum[j+1], (ll) ipot[j] * j % MOD * dp[i-1][j] % MOD);
        }
        forsn(j,1,m+1) {
            dp[i][j] = ll(j+1)*dp[i-1][j]%MOD;
            add(dp[i][j], (ll) pot[j-1] * cum[j] % MOD);
        }
    }
    cout << dp[n][m];

    return 0;
}


Measured memory_bytes: 102272
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],n,ans;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=1,j=1;i<=n;i=j){
		while (j<=n&&a[i]==a[j])j++;
		ans+=(j-i)/2;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

man = 0
k = 0
for i in a:
  man += b[i-1]
  if i == k:
    man += c[i-2]
  k = i + 1

print(man)

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

int main() {
  int a, b;
  cin >> a >> b;
  if (a+b>=24) {
    cout << a+b-24 << endl;
  } else {
    cout << a+b << endl;
  }
  return 0;
}

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

int n, h[111];

int func(int l, int r){
	int mi = 1e9;
	for(int i=l; i<=r; ++i) mi = min(mi, h[i]);
	int res = mi;
	for(int i=l; i<=r; ++i) h[i] -= mi;
	for(int i=l; i<=r; ++i){
		if(h[i] > 0){
			int j = i;
			while(j+1 <= r && h[j+1] > 0) ++j;
			res += func(i, j);
		}
	}
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1; i<=n; ++i) cin >> h[i];
	cout << func(1, n) << "\n";
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
int main(void){
    int N,T;
    int t[200010];
    cin >> N >> T;
    REP(i,N){cin >> t[i];}
    long long int count=0;
    REP(i,N-1){
        if(t[i+1]-t[i]>=T){
            count += T;
        }else{
            count +=t[i+1]-t[i];
        }
    }
    cout << count + T;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll a,b,n; cin >> a >> b >> n;
    ll x = min(n,b-1);
    cout << a*x/b - a * (x/b);
    return 0;
}


Measured memory_bytes: 3616
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VRSORT(v) sort(v.rbegin(), v.rend());//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
  ll a,b,c;
  cin >> a >> b >> c;
  ll ans =0;
  while(1){
    if(b>0 && c>0){
      c--;
      b--;
      ans+=2;
      continue;
    }
    else if(a>0 && c>0){
      c--;
      a--;
      ans++;
      continue;
    }
    else break;
    
  }
  if(c>0) ans++;
  if(b>0) ans += b;
  cout << ans << endl;
}

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

using namespace std;

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

  int n, x, y;
  cin >> n;
  vector<pair<int,int>> p(n);
  vector<int> pos(n);
  for (int i = 0; i < n; ++i) {
    cin >> x >> y;
    p[i] = {x, y};
    pos[i] = i;
  }
  double total;
  int cnt = 0;
  do {
    ++cnt;
    for (int i = 1; i < n; ++i) {
      int x1 = p[pos[i]].first;
      int y1 = p[pos[i]].second;
      int x2 = p[pos[i-1]].first;
      int y2 = p[pos[i-1]].second;
      total += sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
  } while (next_permutation(pos.begin(), pos.end()));

  cout << total / cnt <<endl;

  return 0;
}



Measured memory_bytes: 256
def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P) :
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:] :
        phU.append(p)
        while(True) :
            if isCLKWISE(phU) : break
            else :
                del phU[-2]
                if len(phU) == 2 : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1] :
        phL.append(p)
        while(True) :
            if isCLKWISE(phL) : break
            else :
                del phL[-2]
                if len(phL) == 2 : break
    ph = phU + phL[1:-1]
    return ph
  
n = range(int(input()))
P = [[int(x) for x in input().split()] for _ in n]
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
R = Q[idx:] + Q[:idx]
for r in R : print(r[0],r[1])

Measured memory_bytes: 33776
import math
a,b,h,m=map(int,input().split())
theta_1=(h+(m/60))*(math.pi/6)
theta_2=m*(math.pi/30)
theta_1=2*math.pi-(theta_1-math.pi/2)
theta_2=2*math.pi-(theta_2-math.pi/2)

y1=a*math.sin(theta_1)
x1=a*math.cos(theta_1)

y2=b*math.sin(theta_2)
x2=b*math.cos(theta_2)

print(math.sqrt((x1-x2)**2+(y1-y2)**2))

Measured memory_bytes: 9592
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int k,a,b,pass=0;
     cin>>k;
cin>>a>>b;
 for(int i=a;i<=b;i++)
{
     if(i%k==0)
    {
         pass=1;
     }
}
if(pass)
{
  cout<<"OK"<<endl;
}
else
{
cout<<"NG"<<endl;
}
	return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>
int main(){
  int n,i,r=100000;
  scanf("%d",&n);
  if(n<=100){
  for(i=0;i<n;i++){
    r=r*1.05;
  if(r%1000>=1 && r%100<=999){
    r=r+(1000-r%1000);
  }
  }
  printf("%d\n",r);
  }
  return 0;
}

Measured memory_bytes: 0
/**
class cfmaster {
 public:
  struct code {
  	see the details down there !
  };
};
**/
#include <bits/stdc++.h>

using namespace std;

const int MAX = (int) 1e5;
const long long inf = (long long) 9e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, W;
  cin >> n >> W;
  vector<long long> w(n), v(n);
  for (int i = 0; i < n; i++) {
  	cin >> w[i] >> v[i];
	}
	vector<long long> dp(MAX + 1, inf);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		vector<long long> new_dp = dp;
		for (int j = 0; j <= MAX; j++) {
			if (dp[j] != inf) {
				new_dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i]);
			}
		}
		dp = new_dp;
	}
	int ans = 0;
	for (int i = 0; i <= MAX; i++) {
		if (dp[i] <= W) {
			ans = max(ans, i);
		}
	}
	cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
    char input[15];
    int m, f, r;
    while (1){
        fgets(input, sizeof(input), stdin);
        m = atoi(strtok(input, " "));
        f = atoi(strtok(NULL, " "));
        r = atoi(strtok(NULL, " "));

        if (m + f + r == -3){
            return 0;
        }else if (m == -1 || f == -1){
           printf("F");
        }else if (m + f < 30){
           printf("F");
        }else if (m + f < 50 && r < 50){
           printf("D");
        }else if (m + f < 65 || r >= 50){
           printf("C");
        }else if (m + f < 80){
           printf("B");
        }else{
           printf("A");
        }
    printf("\n");
    }
}

Measured memory_bytes: 524