akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
const double EPS = 1e-10;
const ll mod=1000000007;
//const ll mod=998244353;

int main(void){
    ll a,b;
    cin>>a>>b;
    ll n=b-a-1;
    cout<<n*(n+1)/2-a<<endl;
}

Measured memory_bytes: 3624
#include<stdio.h>

void initialize(int array[], int n);
void process(int input[], int copy[], int *result, int n);
void copying(int input[], int copy[], int n);
void output(int array[], int n, int result);

main()
{
	int i = 0, n = 0, result = 0;
	while(scanf("%d", &n), n > 0)
	{
		int input[n];
		int copy[n];
		initialize(input, n);
		initialize(copy, n);
		for(i = 0; i < n; i++)
		{
			scanf("%d", &input[i]);
		}
		process(input, copy, &result, n);
		output(copy, n, result);
		result = 0;
	}
	return 0;
}
void initialize(int array[], int n)
{
	int i= 0;
	for(i = 0; i < n; i++)
	{
		array[i] = 0;
	}
}
void process(int input[], int copy[], int *result, int n)
{
	*result += 1;
	int i = 0, j = 0, count = 0, flag = 0;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(input[i] == input[j])
			{
				count++;
			}
		}
		copy[i] = count;
		count = 0;
	}
	for(i = 0; i < n; i++)
	{
		if(input[i] == copy[i])
		{
			flag++;
		}
		else
		{
			continue;
		}
	}
	/*
	printf("result = %d\ninput = ", *result);
	for(i = 0; i < n; i++)
	{
		printf("%d ", input[i]);
	}
	printf("\ncopy = ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", copy[i]);
	}
	printf("\n");
	*/
	if(flag == n)
	{
		*result -= 1;
		return;
	}
	else
	{
		copying(input, copy, n);
		process(input, copy, result, n);
	}
}
void copying(int input[], int copy[], int n)
{
	int i = 0;
	for(i = 0; i < n; i++)
	{
		input[i] = copy[i];
		copy[i] = 0;
	}
}
void output(int array[], int n, int result)
{
	int i = 0;
	printf("%d\n", result);
	for(i = 0; i < n; i++)
	{
		if(i < n - 1)
		{
			printf("%d ", array[i]);
		}
		else
		{
			printf("%d\n", array[i]);
		}
	}
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scannerS = new Scanner(System.in);

		int D = scannerS.nextInt();
		int T = scannerS.nextInt();
		int S = scannerS.nextInt();

		float t;
		t = (float)D /(float)S;

		if (t <= T) {

			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 27092
n = list(map(int, list(input())))
k = int(input())

dp0 = [[0]*3]*len(n)
dp1 = [[0]*3]*len(n)
dp0[0][0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    if n[i]==0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = [0]+dp0[i-1][:2]

    dp1[i] = [
        dp1[i-1][0]+dp0[i-1][0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[i-1][1]*(n[i]!=0)+dp0[i-1][0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[i-1][2]*(n[i]!=0)+dp0[i-1][1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]

print(dp0[-1][k-1]+dp1[-1][k-1])

Measured memory_bytes: 9060
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		
		int n500 = num/500;
		int n005 = 0;
		if(n500 > 0) {
			n005 = (num%500)/5;
		}else {
			n005 = num/5;
		}
		
		System.out.println(n500*1000 + n005*5);
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define cl clear() ;
#define vl vector<ll>
#define sz size()
#define len length()
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define en end()
#define ro return 0
#define br break
#define eb emplace_back
#define con continue
#define ms(x) memset(x , 0, so x)
#define all(x) (x).be , (x).en
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;

int main()
{
    ios;
    ll a , b , x;
    cin >> a >> b >> x;
    ll rem = a %  x ;
    ll fn = -1;
    if(rem == 0 ){
        fn = a;
    }
    else {
        ll aa = a - rem ;
        fn = aa + x ;
    }
    if(fn == -1) throw ;
    ll ln = -1 ;
    rem = b % x ;
    if(rem == 0 ){
        ln = b;
    }
    else {
        ll bb = b - rem ;
        ln = bb ;
    }
    if(fn > ln ) {
       cout << 0 << el ;
       ro ;
    }
    if(fn > b or ln < a) {
        cout << 0 << el ;
        ro ;
    }
    if(fn < a or ln > b ){
        cout << 0 << el ;
        ro ;
    }
    else{
        ll diff = ln - fn ;
        ll res = diff / x;
        ++res;
        cout << res << el ;
        ro ;
    }
}
































Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int R = Integer.parseInt(sc.next());
      String result = R < 1200 ? "ABC" : R < 2800 ? "ARC" : "AGC";
      System.out.println(result);
    }
  }
}


Measured memory_bytes: 23764
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int t1,t2,t3,N;

int main() {

	cin >>t1 >> t2>> t3>>N;



	cout << (N==1) << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;

int rig[2020][2020];
int lef[2020][2020];
int up[2020][2020];
int dw[2020][2020];

int H,W;
string C[2020];

int main(){
  cin>>H>>W;
  for(int i=0;i<H;i++) cin>>C[i];

  int now=0;
  for(int i=0;i<H;i++){
    now=0;
    for(int j=0;j<W;j++){
      if(C[i][j]=='#') now=0;
      else{
        lef[i][j]=now;
        now++;
      }
    }
  }
  now=0;
  for(int i=0;i<H;i++){
    now=0;
    for(int j=W-1;j>=0;j--){
      if(C[i][j]=='#') now=0;
      else{
        rig[i][j]=now;
        now++;
      }
    }
  }
  now=0;
  for(int j=0;j<W;j++){
    now=0;
    for(int i=0;i<H;i++){
      if(C[i][j]=='#') now=0;
      else{
        up[i][j]=now;
        now++;
      }
    }
  }
  now=0;
  for(int j=0;j<W;j++){
    now=0;
    for(int i=H-1;i>=0;i--){
      if(C[i][j]=='#') now=0;
      else{
        dw[i][j]=now;
        now++;
      }
    }
  }

  int ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(C[i][j]=='#') continue;
      int num=lef[i][j]+rig[i][j]+up[i][j]+dw[i][j];
      ans=max(ans,num+1);
    }
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 67968
#include <iostream>
using namespace std;
 
int main(void){
 int n,m;
 cin >> n >> m;
 int a[100][100],b[100],c[100]={0};
 int i,j;
 for (i = 0; i < n; i++){
     for (j = 0; j < m; j++){
         cin >> a[i][j];
     }
 }
 for(i = 0; i < m; i++){
     cin >> b[i];
 }    
 for (i = 0; i < n; i++){
     c[i] = 0;
     for (j = 0; j < m; j++){
         c[i] += b[j] * a[i][j];
     }
 }
 for (i = 0; i < n; i++){
 cout << c[i] << endl;
 }
}


Measured memory_bytes: 3136
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

//----------------------------------------------------------------

int main()
{
    ll n;
    cin >> n;
    ll ans = infll;
    ll rootn = sqrt(n);
    for (ll i = 1; i <= rootn; i++)
    {
        if (n % i == 0)
        {
            chmin(ans, i + n / i - 2);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    if(a > b){
        cout << a - 1 << endl;
    }else{
        cout << a << endl;
    }
}

Measured memory_bytes: 256
n = int(input())
L = list(map(int,input().split()))
L = [0] +L

num = 0
min1 = 0
for i in range(n):
    
    if L[i] <= L[i+1]:
        num += L[i+1]-L[i]
    else:
        min1 = L[i+1]

print(num)

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n, a, b;
    cin >> n >> a >> b;
    if (a % 2 == b % 2) {
        cout << (b - a) / 2 << '\n';
    }   
    else {
        cout << min(a + (b - a - 1) / 2, (n - b + 1) + (b - a - 1) / 2) << '\n';
    }   


}   

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

int main(){
	char huruf;
	scanf("%c\n", &huruf);
	
	if(huruf >= 'A' && huruf <= 'Z'){
		puts("A");
	}
	else{
		puts("a");
	}	
	
	return 0;
}

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

namespace ABC114 {
	class ABC114_B {
		private static int numLength = 3;
		private static int targetVal = 753;
		static void Main(string[] args) {
			var line = Console.ReadLine();
			Console.WriteLine(Get753Diff(line));
		}

		private static int Get753Diff(string line) {
			int num;
			int min = int.MaxValue;
			for (int i = 0; i <= line.Length - numLength; i++) {
				if (int.TryParse(line.Substring(i, numLength), out num))
					min = Math.Min(min, Math.Abs(targetVal- num));
			}
			return min;
		}
	}
}


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

typedef long long ll;

ll dp[100005][3][2];
ll dpx[100005][2];
ll a[200005];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	if( n % 2 == 0 )
	{
		for (int i = 0; i < n / 2; i++)
		{
			int t1 = a[i*2];
			int t2 = a[i*2+1];
			if( i == 0 )
			{
				dpx[i][0] = t1;
				dpx[i][1] = t2;
			}else
			{
				dpx[i][0] = dpx[i-1][0] + t1;
				dpx[i][1] = max(dpx[i-1][0],dpx[i-1][1]) + t2;
			}
		}
		cout << max(dpx[n/2-1][0],dpx[n/2-1][1]) << '\n';
		return 0;
	} 
	for (int i = 0; i < n / 2; i++)
	{
		int t1 = a[i*2];
		int t2 = a[i*2+1];
		if( i == 0 )
		{
			dp[i][0][0] = t1;
			dp[i][0][1] = t2;
			dp[i][1][0] = max(t1,t2);
			dp[i][1][1] = a[i*2+2];
			dp[i][2][0] = -1e18;
			dp[i][2][1] = -1e18;
		}else
		{
			dp[i][0][0] = dp[i-1][0][0] + t1;
			dp[i][0][1] = max(dp[i-1][0][0],dp[i-1][0][1]) + t2;
			int t3 = a[i*2+2];
			dp[i][1][0] = max(dp[i-1][0][0] + max(t1,t2),dp[i-1][0][1] + t2);
			dp[i][1][1] = max(dp[i-1][0][0],dp[i-1][0][1]) + t3;
			int x1 = a[i*2+1];
			int x2 = a[i*2+2];
			dp[i][2][0] = max(dp[i-1][1][0],dp[i-1][2][0]) + x1;
			dp[i][2][1] = max(max(dp[i-1][1][0],dp[i-1][1][1]),max(dp[i-1][2][0],dp[i-1][2][1])) + x2;
		}
	}
	cout << max(max(dp[n/2-1][1][0],dp[n/2-1][1][1]),max(dp[n/2-1][2][0],dp[n/2-1][2][1])) << '\n';
	return 0;
}


Measured memory_bytes: 9904
//2014年5月14日

#include<stdio.h>
#define rep(i,n) for(i = 0;i < n;i++)
#define DB(x) 						//デバッグ用

char flag[1002][1002] = {0};	//調べたくないところはJ,O,I以外の文字にする。
char monsyo[2][3];				//紋章
char hash[4] = "JOI";			//'0'がつくので4byte確保

//紋章の左上と旗の(x,y)とを合わせたとき、紋章が旗に含まれるか ( 含まれる:1,含まれない:0 )
//要するに一致判定
int Check( int x,int y )
{
	/*間違い
	int i,j;
	rep(i,2){
		rep(j,2){
			if( monsyo[i][j] != flag[x+i][y+i] ){
				DB( printf("Check内 i = %d j = %d\n",i,j); )
				break;
			}
		}
	}
	if(i == 2 && j == 2)
		return 1;*/
	if( monsyo[0][0] == flag[x][y] && monsyo[0][1] == flag[x][y+1] && monsyo[1][0] == flag[x+1][y] && monsyo[1][1] == flag[x+1][y+1] )
		return 1;
	return 0;
}

int main(){
	int i,j,k;		//ループ用
	char c;			//1文字保存用
	int U = 0;		//初期状態でのJOI紋章の数
	int u1,u2;		//3*3マスにおけるJOI紋章の数 u1は初期状態,u2は1文字代えた後
	int K = 0;		//u2-u1の最大値
	int H,W;		//JOI旗の行数,列数

	scanf("%d%d",&H,&W);
	rep(i,H){
		scanf("%s",flag[i+1]+1);
	}
	rep(i,2){
		scanf("%s",monsyo[i]);
	}
	
	DB(
		//Check関数のデバッグ
		rep(i,H+1){
			rep(j,W+1){
				printf("Check(%d,%d) == %d\n",i,j,Check(i,j) );
			}
		}
	)

	//3*3の真ん中が(i,j) ⇔ flag[i][j]を変更
	rep(i,H+1){
		if(i == 0)
			continue;
		rep(j,W+1){
			if(j == 0)
				continue;
			//u1を求める
			u1 = Check( i-1,j-1 ) + Check( i-1,j ) + Check( i,j-1 ) + Check( i,j );
			//Uを更新
			U += Check( i,j );	//U += u1ではない
			rep(k,3){
				c = flag[i][j];
				flag[i][j] = hash[k];
				//u2を求める
				u2 = Check( i-1,j-1 ) + Check( i-1,j ) + Check( i,j-1 ) + Check( i,j );
				//Kを更新
				if( K < u2-u1 )
					K = u2-u1;
				flag[i][j] = c;
			}
		}
	}
	printf("%d\n", U+K );
	return 0;
}

Measured memory_bytes: 2012
#include <cstdio>
#include <map>

std::map < long long, int > mp;

int main() {
    int n;
    scanf("%d", &n);

    mp[0] = 1;
    long long ans = 0;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        sum += x;

        int &a = mp[sum];
        ans += a;
        a++;
    }

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 12800
import math

def binarySearch(key, nums, left=0, right=None):
    if right == None:
        right = len(nums)-1

    if right < left:
        return 0

    mid = math.floor((right - left)/2)+left

    if key == nums[mid]:
        return 1

    if key < nums[mid]:
        return binarySearch(key, nums, left ,mid-1)
    else:
        return binarySearch(key, nums, mid+1 ,right)

def main():
    input()
    ss = [int(x) for x in input().split()]

    input()
    ts = [int(x) for x in input().split()]

    nums = {}
    cnt = 0

    for t in ts:
        if t in nums:
            continue;

        nums[t] = binarySearch(t, ss)
        cnt += nums[t]

    print(cnt)

if __name__ == '__main__':
    main()



Measured memory_bytes: 17120
n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
def isOk(x):
	cost = 0
	for a, f in zip(A,F):
		eatable = x//f
		if eatable >= a:
			continue
		cost += a - eatable
	if cost <= k:
		return True
	return False
left = -1
right = A[-1] * F[0]
while left+1 < right:
	# mid = int(left + (right-left)//2)
	mid = (left+right)//2
	if isOk(mid):
		right = mid
	else:
		left = mid
print(right)

Measured memory_bytes: 33940
// {{{ include
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
// }}}
#include <sstream>

using namespace std;

typedef long long ll;
inline int in(){int x;scanf("%d",&x);return x;}

ll sumd(ll v){
  v--;

  ll ten = 1;
  int lgt = 0;
  while (ten * 10 <= v){
    ten *= 10;
    lgt++;
  }
  ll sum = 0;
  while (v){
    sum += (v - ten + 1) * (lgt + 1);
    v = ten - 1;
    ten /= 10;
    lgt--;
  }
  return sum;
}

bool is_ok(ll v, ll n){
  return sumd(v) < n;
}

int main()
{
  ll N;
  int K;
  while (N = in(), K = in()){
    ll l = 1;
    ll r = N + 1;
    while (r - l > 1){
      ll m = l + r >> 1;
      if (is_ok(m, N)) l = m;
      else r = m;
    }
    ll offset = N - sumd(l);
    stringstream ss;
    for (int i = 0; i < K; i++){
      ss << l + i;
    }
    string S = ss.str();
    cout << S.substr(offset - 1, K) << endl;
  }
  return 0;
}

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

using namespace std;

#define ll long long
#define PI 3.14159265358979323846264338327950L

int n,m,x,cc,aa;
int a[12][12];
int c[12];
int tmp[12];

void solve(){

    cin >> n >> m >> x;

    for (int i = 0; i < n; i++)
    {
        cin >> cc;
        c[i] = cc;
        for (int j = 0; j < m; j++)
        {
            cin >> aa;

            a[i][j] = aa;

        }
        
    }
    
    ll ans = 0;
    for (int i = 0; i < m; i++)
    {
        ans = 0;
        for (int j = 0; j < n; j++)
        {
            ans += a[j][i];
        }
        
        if(ans < x){
            cout << -1 << endl;
            return;
        }
    }
    
    ans = 1000000000000;
    ll tans = 0;
    for (ll i = 0; i < (1<<n); i++)
    {
        tans = 0;
        bool flag = true;
        for (int h = 0; h < m; h++) tmp[h] = 0;
        

        for (int j = 0; j < n; j++)
        {
            if(i & (1<<j)){
                tans +=c[j];
                for (int h = 0; h < m; h++) tmp[h] += a[j][h];                
            }
        }
        
        for (int h = 0; h < m; h++){
            if(tmp[h] < x){
                flag = false;
            }
        }    
        if(flag) ans = min(ans, tans);
    }
    
    cout << ans << endl;
}





int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Measured memory_bytes: 3644
while 0<n=gets.to_i
c=Hash[(1..n).map{gets.split}]
r={};gets.to_i.times{a,_,*b=gets.split;r[a]=b}
m=Hash.new{|h,k|h[k]=[c[k].to_i,r[k]?r[k].inject(0){|s,i|s+m[i]}:1e7].min}
p m[gets.chop]
end

Measured memory_bytes: 6132
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,A,B;
  cin>>N>>A>>B;
  vector<int> vec(N);
  int i=0;
  int h;
  int t;
  int th;
  int ans=0;
  int sum=0;
  while(i<N){
    vec.at(i)=i+1;
    i++;
  }
  for(int j=0;j<N;j++){
    h=0;
    t=0;
    th=0;
    int v=vec.at(j);
    while(v>999){
      v=v-1000;
      th++;
    }
    while(v>99){
      v=v-100;
      h++;
    }
    while(v>9){
      v=v-10;
      t++;
    }
    ans=v+t+h+th;
    if(vec.at(j)==10000)
      ans=1;
    if(ans>=A&&ans<=B)
      sum+=vec.at(j);
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
//============================
// ABC136c Build Stairs
//
// 2019/08/13
//============================

#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

#define NUM 100000

int main(int argc, char* argv[])
{
  int N;
  long H[NUM];

  cin >> N;
  for(int i=0; i<N; i++)
  {
    cin >> H[i];
  }

  string judge="Yes";
  for(int i=N-1; i>0; i--)
  {
    if(H[i-1] -1 == H[i])
    {
      H[i-1] -= 1;
    }
    else if(H[i-1] > H[i])
    {
      judge = "No";
      break;
    }
  }

  cout << judge << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
int main() {
    int n;
    cin >> n;
    if(n%10 == 3){
        cout << "bon" << endl;
    }
    else if(n%10 == 0 || n%10 == 1 || n%10 == 6 || n%10 == 8){
        cout << "pon" << endl;
    }
    else cout << "hon" << endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long n;
   cin>>n;
   if(n%1000==0){
    cout<<0<<endl;
   }
   else{
    long long vag=n/1000;
    vag ++;
    cout<<(1000*vag)-n<<endl;
   }
}


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

const Int MOD = 1e9+7;

int main(){
    Int N, K; cin >> N >> K;

    Int ans = 0;
    for(Int i=K; i<=N+1; i++){
        Int L = i * (i-1) / 2;
        Int R = i * (2*N-i+1) / 2;
        //cout << R << " " << L << endl;
        ans = (ans + (R-L+1+MOD)%MOD) % MOD;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3636
#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int A = 0;
    int B = 0;
    int result = 0;
    
    scanf("%d",&A);
    scanf("%d",&B);
    
    for (int i=0; i<2; i++) {
        if (A<B) {
            result = result + B;
            B--;
        }else{
            result = result + A;
            A--;
        }
    }
    
    printf("%d",result);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
int64_t INF = 1000000007;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t h,w;
    cin >> h >> w;
    if(h== 1|| w ==1){
        cout << 1 << endl;
    }else{
        cout << setprecision(100) << ceil(w * h / 2.0) << endl;
    }
}

Measured memory_bytes: 512
N=int(input())
L=list(map(int,input().split()))

L.sort()

ans=0

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i]+L[j]>L[k] and L[i]!=L[j]!=L[k]:
        ans+=1
        #print("{}{}{}".format(i,j,k))
        
print(ans)
#print(L)

Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N, K;
    cin >> N >> K;

    int E = (N - 1) * (N - 2) / 2;
    vector<P> ans;
    if (K > E) {
        cout << -1 << endl;
        return 0;
    }
    else {
        repd(i, 2, N + 1) ans.push_back(P(1, i));
        int cnt = E - K;
        repd(i, 2, N) {
            repd(j, i + 1, N + 1) {
                if (cnt == 0) break;
                ans.push_back(P(i, j));
                cnt--;
            }
            if (cnt == 0) break;
        }
    }

    cout << (int)ans.size() << endl;
    rep(i, ans.size()) cout << ans[i].first << " " << ans[i].second << endl;
    return 0;
}

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

using namespace std;
const int maxn=200050;
int a[maxn];
int next[maxn],last[maxn];
int main()
{
	int n,m;
	int x;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
	 next[i]=i+1;
	 last[i]=i-1;
    }
    last[n]=n-1;
    int head=1;
    int num=1;
	for(int i=1;i<=m;i++){
		scanf("%d",&x);//num;
		if(last[x]==0)
		continue;
		if(next[x]==0){
		   next[last[x]]=next[x];
		   next[x]=head;
		last[head]=x;
		last[x]=0;
		head=x;
		continue;
		}
		next[last[x]]=next[x];
		last[next[x]]=last[x];
		next[x]=head;
		last[head]=x;
		last[x]=0;
		head=x;
	}
	//for(int i=1;i<=n;i++)cout<<next[i]<<endl;
	for(int i=head;i;i=next[i])
	printf("%d\n",i);
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<string>s(N);
    for (int i = 0; i < N; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < N; ++i) {
        sort(s[i].begin(), s[i].end());
    }
    sort(s.begin(), s.end());

    ll ans = 0;
    ll streak = 1;
    for (int i = 1; i < N; ++i) {
        if(s[i] == s[i-1]) {
            streak++;
            if(i == N-1){
                ans = ans + (streak * (streak - 1) / 2);
            }
        } else{
            ans = ans + (streak * (streak - 1) / 2);
            streak = 1;
        }
    }
    cout << ans;
    return 0;
}

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

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    const int INF = INT_MAX / 4;

    const int MAX_H = 50;
    const int MAX_W = 50;

    int H, W;
    vector<string> F;
    bool input() {
        cin >> H >> W;
        if (H == 0 && W == 0) return false;
        F.clear(); F.resize(H); cin >> F;
        return true;
    }

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

    int G[MAX_H][MAX_W][MAX_H][MAX_W];
    bool R[MAX_H][MAX_W][MAX_H][MAX_W];

    void dfs(int sy, int sx, int y, int x) {
        R[sy][sx][y][x] = true;
        for (int i = 0; i < 2; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= H) continue;
            if (nx < 0 || nx >= W) continue;
            if (F[ny][nx] == '#') continue;
            if (R[sy][sx][ny][nx]) continue;
            dfs(sy, sx, ny, nx);
        }
    }

    int f(int sy, int sx, int ty, int tx) {
        if (sy < 0 || sy >= H || sx < 0 || sx >= W) return -INF;
        if (ty < 0 || ty >= H || tx < 0 || tx >= W) return -INF;
        if (not R[sy][sx][ty][tx]) return -INF;
        int& cache = G[sy][sx][ty][tx];
        if (cache >= 0) return cache;

        if (abs(sy - ty) + abs(sx - tx) == 1) return islower(F[sy][sx]) && toupper(F[sy][sx]) == F[ty][tx];

        int r = 0;
        r = max(r, f(sy, sx + 1, ty, tx));
        r = max(r, f(sy + 1, sx, ty, tx));

        if (not islower(F[sy][sx])) {
            return cache = r;
        }

        for (int y = sy; y <= ty; y++) {
            for (int x = sx; x <= tx; x++) {
                if (y == ty && x == tx) continue;
                r = max(r, f(sy, sx, y, x) + max(f(y + 1, x, ty, tx), f(y, x + 1, ty, tx)));
            }
        }

        int d = toupper(F[sy][sx]) == F[ty][tx];
        r = max(r, f(sy + 1, sx, ty - 1, tx) + d);
        r = max(r, f(sy + 1, sx, ty, tx - 1) + d);
        r = max(r, f(sy, sx + 1, ty - 1, tx) + d);
        r = max(r, f(sy, sx + 1, ty, tx - 1) + d);
        return cache = r;
    }

    void solve() {
        memset(G, -1, sizeof(G));
        memset(R, false, sizeof(R));

        for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) 
            if (F[i][j] != '#') dfs(i, j, i, j);

        if (not R[0][0][H - 1][W - 1]) {
            cout << -1 << endl;
            return;
        }

        cout << f(0, 0, H - 1, W - 1) << endl;
    }
}

int main() {
    while (input()) solve();
    return 0;
}

Measured memory_bytes: 33528
#include<bits/stdc++.h>
#define fi                first
#define se                 second
#define ll               long long
#define mod              1000000007
#define endl              "\n"
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb                push_back
#define all(v)             v.begin(),v.end()
#define inp(V,n)      for(int i=0;i<n;i++){cin >> V[i];}
#define oup(V,n)     {for(int i=0;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define pll              pair<long long,long long>
using namespace std;
ll factorial(ll n)
{
    return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
}
ll gcd(ll a, ll b)
{
    if (a == 0)
      return b;
    return gcd(b % a, a);
}
ll lcm(ll a, ll b)
{
   return (a*b)/gcd(a, b);
}
bool sortByVal(const pair<double,double> &a,
              const pair<double,double> &b)
{
    if(a.fi==b.fi)
    {
    return (a.se >b.se);
    }
    else
        return (a.fi<b.fi);
}
ll Powb(ll b,ll n)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2);
    if(n%2==0){return (temp*temp)%mod;}
    else{return (b*((temp*temp)%mod))%mod;}
}
int main()
{
 fast;
     int t=1;
     //cin>>t;
     while(t--)
     {
       ll k,n,i=0,j=0,c=0,d=0,e=0,f=0,g=0,h=0,maxi=0,sum=0;
         cin>>n>>k;
         double x;
         while(n--)
         {
             cin>>c>>d;
             c*=c;
             d*=d;
             c+=d;
             x=sqrt(c);
             if(x<=k)
                sum++;
         }
           cout<<sum<<endl;
     }
}


Measured memory_bytes: 3692
import java.util.*;

public class Main {
    
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
       
        while (true) {
            int month = scanner.nextInt();
            int day = scanner.nextInt();
            
            if (month == 0 || day ==0) {
                break;
            }

            Calendar calendar = new GregorianCalendar(2004, month-1, day);
            switch (calendar.get(Calendar.DAY_OF_WEEK)) {
                case Calendar.MONDAY :
                    System.out.println("Monday");
                    break;
                case Calendar.TUESDAY :
                    System.out.println("Tuesday");
                    break;
                case Calendar.WEDNESDAY :
                    System.out.println("Wednesday");
                    break;
                case Calendar.THURSDAY :
                    System.out.println("Thursday");
                    break;
                case Calendar.FRIDAY :
                    System.out.println("Friday");
                    break;
                case Calendar.SATURDAY :
                    System.out.println("Saturday");
                    break;
                case Calendar.SUNDAY :
                    System.out.println("Sunday");
                    break;
            }
        }            
    }        
}

Measured memory_bytes: 17312
#input
N = int(input())
L = list(map(int, input().split()))

#output
import heapq
import bisect

L = [-l for l in L]
heapq.heapify(L)

sum = 0
while len(L) > 2:
    largest = heapq.heappop(L)
    L.sort()
    for i in range(len(L)-1):
        p = bisect.bisect_left(L, largest-L[i])
        if p-(i+1) >0:
            sum += p-(i+1)
        
print(sum)

Measured memory_bytes: 46940
n = int(input())
s = {}

for _ in range(n):
    ss = input()
    ss = [i for i in ss]
    ss.sort()
    ss = tuple(ss)
    if ss in s:
        s[ss] +=1
    else:
        s[ss] = 1

ans = 0
for i in s:
    ans += (s[i] - 1) * s[i] // 2
print(ans)


Measured memory_bytes: 130136
open Batteries
let () =
  let w,h,n = Scanf.scanf "%d %d %d " (fun a b c -> a,b,c) in
  let pair_l = Array.to_list @@ Array.init n (fun _ -> Scanf.scanf "%d %d %d " (fun a b c-> a,b,c)) in

  let x1 = let l = List.filter (fun (x,y,a) -> a=1) pair_l |> List.map (fun (x,y,a) -> x) in
           try List.max l with _ -> 0
  in
  let x2 = let l = List.filter (fun (x,y,a) -> a=2) pair_l |> List.map (fun (x,y,a) -> x) in
           try List.min l with _ -> w
  in
  let y1 = let l = List.filter (fun (x,y,a) -> a=3) pair_l |> List.map (fun (x,y,a) -> y) in
           try List.max l with _ -> 0
  in
  let y2 = let l = List.filter (fun (x,y,a) -> a=4) pair_l |> List.map (fun (x,y,a) -> y) in
           try List.min l with _ -> h
  in

  let x = x2 - x1 in
  let x = if x < 0 then 0 else x in
  let y = y2 - y1 in
  let y = if y < 0 then 0 else y in

  Printf.printf "%d\n" @@ x*y


Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
	//入力
	string S;
	cin >> S;
	
	//処理
	string T = "ATCG";
	
	int ans = 0;//ATCG文字列の最大長
	int now = 0; //今見えている文字を末とするATCG文字列の最大長
	for(int i=0; i<S.size(); ++i){
		bool isATCG = false;
		for(int j=0; j<T.size(); ++j){
			if(S[i] == T[j]) isATCG = true;	
		}
		if(!isATCG){
			//違う場合は０にする
			now = 0;
		}else{
			//ATCG文字の場合は、前の文字列に人る文字を足します。
			now++;
			ans = max(now, ans);
			//if(now > ans) ans = now;も同じ
		}
		
	}
	
	cout << ans;
	
	
}

Measured memory_bytes: 256
n = int(input())
s = input()
index = 0
cnt = 0
for i in range(0, 1000):
    if i < 10:
        value = '00' + str(i)
    elif i < 100:
        value = '0' + str(i)
    else:
        value = str(i)

    for j in s:
        if value[index] == j:
            index += 1

        if index == 3:
            cnt += 1
            index = 0
            break
    index = 0

print(cnt)


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

const int _A = 100000;
int L[100009], A[100009];
long long ans[100009], F1[100009], F2[100009];
vector<int> S;

void upd(long long F[], int x, int y) {
	for(int i=x; i<=_A; i+=(i&-i)) F[i] += y;
}

long long get(long long F[], int x) {
	long long ret = 0;
	for(int i=x; i>=1; i-=(i&-i)) ret += F[i];
	return ret;
}

int getx(int x) {
	return lower_bound(S.begin(), S.end(), x) - S.begin() + 1;
}

int main() {
	int N; scanf("%d",&N);
	for(int i=1, m=0; i<=N; i++) {
		scanf("%d",&A[i]);
		S.push_back(A[i]);
		if(m < A[i]) L[i] = A[i] - m, m = A[i];
	}
	sort(S.begin(), S.end());
	S.resize(unique(S.begin(), S.end()) - S.begin());
	long long s = 0;
	for(int i=N; i>=1; i--) {
		int j = getx(A[i]), k = getx(A[i] - L[i] + 1);
		upd(F1, j, +1); upd(F2, j, A[i]);
		
		if(L[i]) {
			long long cnt = get(F1, _A) - get(F1, k - 1);
			long long sum = get(F2, _A) - get(F2, k - 1);
			ans[i] = sum - cnt * (A[i] - L[i]) - s;
			s += sum - cnt * (A[i] - L[i]) - s;
		}
	}
	for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
	return 0;
}

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

int main() {
    long a, b, c, d;
    cin >> a >> b >> c >> d;

    bool zero = false;
    if(a == 0 && b == 0 && c == 0 && d == 0) {
        cout << 0 << endl;
        zero = true;
    }

    if(!zero) {
        if(a == 0) a = 1;
        if(b == 0) b = 1;
        if(c == 0) c = 1;
        if(d == 0) d = 1;
        long long ac = a * c;
        long long ad = a * d;
        long long bc = b * c;
        long long bd = b * d;
        long long ans = max(max(ac, ad), max(bc, bd));
        cout << ans << endl;
    }
}

Measured memory_bytes: 3632
#include <iostream>
#include <array>
#include <map>
int main() {
    std::array<std::array<bool, 14>, 4> cards;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 14; ++j) {
            cards[i][j] = false;
        }
    }
    std::map<std::string, int> suit = { { "S", 0 }, { "H", 1 }, { "C", 2 }, { "D", 3 } };
    std::array<std::string, 4> rev = { "S", "H", "C", "D" };
    int n;
    std::cin >> n; // skip
    std::string s;
    while (std::cin >> s >> n) {
        cards[suit[s]][n] = true;
    }
    for (int i = 0; i < 4; ++i) {
        for (int j = 1; j < 14; ++j) {
            if (cards[i][j]) {
                continue;
            }
            std::cout << rev[i] << ' ' << j << std::endl;
        }
    }
}



Measured memory_bytes: 3128
import java.io.*;

class Main{
	public static void main(String args[]) throws IOException{
		BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
		String str;
		String str1,str2;
		int m=0;
		int h=0;

		while(true){
			str = buf.readLine();
			if(str.equals("-"))
				break;
			m = Integer.parseInt(buf.readLine());
			for(int i=0; i<m; i++){
				h = Integer.parseInt(buf.readLine());
				str1 = str.substring(0,h);
				str2 = str.substring(h);
				str = str2.concat(str1);
			}
			System.out.println(str);
		}	
		
		
		
	}
}

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

#define ll long long
int main() {
    
    ll n,k,q;
    cin>>n>>k>>q;
    vector<ll> v(n+1,0);
    for(ll i=0;i<q;i++)
    {
        ll x;cin>>x;
        v[x-1]++;
    }
    
    for(ll i=0;i<n;i++)
    {
        v[i]=v[i]+(k-q);
        if(v[i]>0)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    
    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int N;
    cin>>N;
    vector<long> A(N);
    vector<long> B(N);
    vector<long> C(N);
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    for(int i=0;i<N;++i){
        cin>>B[i];
    }
    for(int i=0;i<N;++i){
        cin>>C[i];
    }
    sort(A.begin(), A.end());
    sort(C.begin(), C.end());
    long ans = 0;
    long a, c;
    for(int i=0;i<N;++i){
        a = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
        c = C.end() - upper_bound(C.begin(), C.end(), B[i]);
        ans += a*c;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
typedef long long i64;
int main(){
    string s;
    cin >> s;
    bool b[26]={false};
    rep(i,s.size()) b[s[i]-'a']=true;
    rep(i,26){
        if(!b[i]){
            cout << (char)('a'+i) << endl;
            break;
        }else if(i==25) cout << "None" << endl;
    }

    return 0;
}


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

typedef long long ll;
#define pii pair<int , int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 1005

ll n , d , x , y;
ll ans;

int main()
{
    _FastIO;
    cin >> n >> d;
    ll k = d * d;
    for(ll i = 0; i < n; i++){
        cin >> x >> y;
        if((x * x + y * y) <= k)
            ans++;
    }
    cout << ans << endl;
    return 0;
}


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

#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define sz(a) (int)a.size()
#define fi first
#define se second

using namespace std;

const int N = 100000;
const int inf = (int)1e9 + 1;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int P = 239;
const ld eps = 1e-6;
const ld pi = atan2(0, -1);

void print(vector<int> &a)
{
    for (int i : a)
        cout << i << " ";
    cout << endl;
}

const int B = 16;
int pref[(1 << B) + 1];

void sort_n(vector<int> &a)
{
    int n = a.size(), x = (1 << B) - 1;
    vector<int> a1(n);
    fill(pref, pref + (1 << B) + 1, 0);
    for (int i : a)
        pref[(i & x) + 1]++;
    for (int i = 1; i <= (1 << B); i++)
        pref[i] += pref[i - 1];
    for (int i : a)
        a1[pref[(i & x)]++] = i;
    fill(pref, pref + (1 << B) + 1, 0);
    for (int i : a1)
        pref[(i >> B) + 1]++;
    for (int i = 1; i <= (1 << B); i++)
        pref[i] += pref[i - 1];
    for (int i : a1)
        a[pref[(i >> B)]++] = i;
}

int main()
{
    //freopen("in.in", "r", stdin);
    //freopen("archer.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    ll n, x;
    cin >> n >> x;
    ll ans = 0, curr = 0;
    rep(i, 0, n)
    {
        int a;
        cin >> a;
        ans += max(0LL, curr + a - x);
        curr = a - max(0LL, curr + a - x);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
fun main(args:Array<String>?): Unit {
    val (h, _) = readLine()!!.trim().split(' ').map(String::toInt)
    val info = Array(h){ readLine()!!.trim().toCharArray().map{it - '0'}.toIntArray()}
    for (y in info.indices.reversed())
        for (x in info[y].indices.reversed())
            info[y][x] += listOfNotNull(if (x + 1 in info[y].indices) info[y][x + 1] else null, if (y + 1 in info.indices) info[y + 1][x] else null).min() ?: 0
    println(info.first().first())
}


Measured memory_bytes: 34984
#include <stdio.h>

int main(void) {
	int n;
	while(scanf("%d",&n)==1 && n>0) {
		int start=0;
		int count=0;
		int feet=0;
		char input[16];
		int i;
		int cur_foot;
		for(i=0;i<n;i++) {
			if(scanf("%s",input)!=1)return 1;
			if(input[0]=='l') {
				cur_foot=1;
			} else {
				cur_foot=2;
			}
			if(input[1]=='u') {
				feet|=cur_foot;
				if(start==0 && feet==3) {
					count++;
					start=1;
				}
			} else {
				feet&=~cur_foot;
				if(start==1 && feet==0) {
					count++;
					start=0;
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    double l; cin>>l;
    double tt, yk ,tk;
    tt = yk = tk = l/3;
    cout << fixed << setprecision(10);
    cout << tt*yk*tk << '\n';
    return 0;
}

Measured memory_bytes: 256
p = [11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381,1451,1471,1481,1511,1531,1571,1601,1621,1721,1741,1801,1811,1831,1861,1871,1901,1931,1951,2011,2081,2111,2131,2141,2161,2221,2251,2281,2311,2341,2351,2371,2381,2411,2441,2521,2531,2551,2591,2621,2671,2711,2731,2741,2791,2801,2851,2861,2971,3001,3011,3041,3061,3121,3181,3191,3221,3251,3271,3301,3331,3361,3371,3391,3461,3491,3511,3541,3571,3581,3631,3671,3691,3701,3761,3821,3851,3881,3911,3931,4001,4021,4051,4091,4111,4201,4211,4231,4241,4261,4271,4391,4421,4441,4451,4481,4561,4591,4621,4651,4691,4721,4751,4801,4831,4861,4871,4931,4951,5011,5021,5051,5081,5101,5171,5231,5261,5281,5351,5381,5431,5441,5471,5501,5521,5531,5581,5591,5641,5651,5701,5711,5741,5791,5801,5821,5851,5861,5881,5981,6011,6091,6101,6121,6131,6151,6211,6221,6271,6301,6311,6361,6421,6451,6481,6491,6521,6551,6571,6581,6661,6691,6701,6761,6781,6791,6841,6871,6911,6961,6971,6991,7001,7121,7151,7211,7321,7331,7351,7411,7451,7481,7541,7561,7591,7621,7681,7691,7741,7841,7901,7951,8011,8081,8101,8111,8161,8171,8191,8221,8231,8291,8311,8431,8461,8501,8521,8581,8641,8681,8731,8741,8761,8821,8831,8861,8941,8951,8971,9001,9011,9041,9091,9151,9161,9181,9221,9241,9281,9311,9341,9371,9391,9421,9431,9461,9491,9511,9521,9551,9601,9631,9661,9721,9781,9791,9811,9851,9871,9901,9931,9941,10061,10091,10111,10141,10151,10181,10211,10271,10301,10321,10331,10391,10501,10531,10601,10631,10651,10691,10711,10771,10781,10831,10861,10891,11071,11131,11161,11171,11251,11261,11311,11321,11351,11411,11471,11491,11551,11621,11681,11701,11731,11801,11821,11831,11941,11971,11981,12011,12041,12071,12101,12161,12211,12241,12251,12281,12301,12391,12401,12421,12451,12491,12511,12541,12601,12611,12641,12671,12721,12781,12791,12821,12841,12911,12941,13001,13121,13151,13171,13241,13291,13331,13381,13411,13421,13441,13451,13591,13681,13691,13711,13721,13751,13781,13831,13841,13901,13921,13931,14011,14051,14071,14081,14221,14251,14281,14321,14341,14401,14411,14431,14461,14551,14561,14591]
print(' '.join(map(str,p[:int(input())])))

Measured memory_bytes: 3320
n=int(input())
H=[int(i) for i in input().split()]
ans=True
prev=0
for i in range(n):
  if H[i]<prev:
    ans=False
  if H[i]>prev:
    prev=H[i]-1
  else:
    prev=H[i]
print("Yes" if ans==True else "No")

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

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

ll n,h,a[MAXN],b[MAXN];
vector<pii> kn;
int main(){
  	cin>>n>>h;
  	REP(i,n) cin>>a[i]>>b[i];
  	REP(i,n){
  		kn.push_back(pii(a[i],0));
  		kn.push_back(pii(b[i],1));
  	}
  	sort(ALL(kn));
  	REV(kn);
  	ll ret=0;
  	ll id=0;
  	//PRTLST(kn,n*2);
  	while(h>0){
  		pii curkn=kn[id];
  		if(curkn.second){
  			h-=curkn.first;
  			ret++;
  		}
  		else{
  		  	if(!(h%curkn.first)) ret+=h/curkn.first;
	  		else ret+=h/curkn.first+1;
  			h=-1;
  		}
  		id++;
  	}
  	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 3956