akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static long solve1(int h, int n, int[][] l) {
        int maxa = 0;
        for (int i = 0; i < n; ++i) {
            maxa = Math.max(maxa, l[i][0]);
        }

        int maxh = h + maxa + 1;
        long[][] f = new long[n][maxh + 1];

        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], Long.MAX_VALUE);
            f[i][0] = 0;
        }

        for (int j = 1; j <= (int)(1.0 * maxh / l[0][0]); ++j) {
            f[0][l[0][0] * j] = l[0][1] * j;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < maxh; ++j) {
                if (j - l[i][0] >= 0 && f[i][j - l[i][0]] != Long.MAX_VALUE) {
                    f[i][j] = f[i][j - l[i][0]] + l[i][1];
                }

                if (f[i - 1][j] != Long.MAX_VALUE) {
                    f[i][j] = f[i][j] == 0 ? f[i - 1][j] : Math.min(f[i][j], f[i - 1][j]);
                }
            }
        }

//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < maxh; ++j) {
//                System.out.print((f[i][j] == Long.MAX_VALUE ? "INF" : f[i][j]) + " ");
//            }
//            System.out.println();
//        }

        long minf = Long.MAX_VALUE;
        for (int i = h; i < maxh; ++i) {
            if (f[n - 1][i] != Long.MAX_VALUE) minf = Math.min(minf, f[n - 1][i]);
        }

        return minf;
    }

    public static void solve() {
        int h = 0;
        int n = 0;
        int[][] l = null;
        Scanner s = new Scanner(System.in);
        h = s.nextInt();
        n = s.nextInt();
        l = new int[n][2];
        for (int i = 0; i < n; ++i) {
            l[i][0] = s.nextInt();
            l[i][1] = s.nextInt();
        }

        System.out.println(solve1(h, n, l));
    }

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


Measured memory_bytes: 129968
from collections import *
N = int(input())
C = Counter(map(int,input().split()))
A = [0,0]
B = [0]

for k,v in C.items():
  if 2<=v:
    A+=[k]
  if 4<=v:
    B+=[k]

A.sort()
B.sort()
print(max(A[-1]*A[-2],B[-1]**2))

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

#define si(n) scanf("%d",&n)

const int MAX=(int)4e6+7;

bitset<MAX>a;

int main()
{
    int n,i,j,sum=0;
    si(n);
    a.set(0);
    for(i=0;i<n;i++){
        si(j);
        sum+=j;
        a|=(a<<j);
    }
    sum=(sum+1)/2;
    for(;;sum++){
        if(a[sum]){
            printf("%d\n",sum);
            return 0;
        }
    }
}


Measured memory_bytes: 1664
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    ret = 0
    X = defaultdict(int)
    for i, a in enumerate(A):
        X[a+i] += 1

        if 0 <= i-a:
            ret += X[i-a]

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 42996
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main(void) {
  int n,m;
  string chkword;
  vector<string> words;
  
  cin >> n;
  string s[n];
  rep(i,n){cin >> s[i];words.push_back(s[i]);}
  
  cin >> m;
  string t[m];
  rep(i,m){cin >> t[i];words.push_back(t[i]);}

  int ans=0;
  sort(words.begin(),words.end());
  rep(i,n+m){
    int sum=0,sums=0,sumt=0;
    if(i==0||chkword!=words[i]){chkword = words[i];}
    else if(chkword==words[i]){continue;}
    rep(j,n){if(chkword==s[j]){sums++;}}
    rep(k,m){if(chkword==t[k]){sumt++;}}
    sum = sums - sumt;
    if(sum>ans){ans=sum;}
  }

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

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template<int Modulo = MOD> struct Mint {
	Int val;
	constexpr Mint(Int v = 0) noexcept : val(v% Modulo) {
		if (val < 0) v += Modulo;
	}
	constexpr int getmod() { return Modulo; }
	constexpr Mint operator - () const noexcept { return val ? Modulo - val : 0; }
	constexpr Mint operator + (const Mint& r) const noexcept { return Mint(*this) += r; }
	constexpr Mint operator - (const Mint& r) const noexcept { return Mint(*this) -= r; }
	constexpr Mint operator * (const Mint& r) const noexcept { return Mint(*this) *= r; }
	constexpr Mint operator / (const Mint& r) const noexcept { return Mint(*this) /= r; }
	constexpr Mint& operator += (const Mint& r) noexcept {
		val += r.val;
		if (val >= Modulo) val -= Modulo;
		return *this;
	}
	constexpr Mint& operator -= (const Mint& r) noexcept {
		val -= r.val;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr Mint& operator *= (const Mint& r) noexcept {
		val = val * r.val % Modulo;
		return *this;
	}
	constexpr Mint& operator /= (const Mint& r) noexcept {
		Int a = r.val, b = Modulo, u = 1, v = 0;
		while (b) {
			Int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % Modulo;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr bool operator == (const Mint& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const Mint& r) const noexcept {
		return this->val != r.val;
	}
	friend ostream& operator << (ostream& os, const Mint<Modulo>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream& is, Mint<Modulo>& x) noexcept {
		Int tmp; is >> tmp;
		x = Mint<Modulo>(tmp);
		return is;
	}
	friend constexpr Mint<Modulo> modpow(const Mint<Modulo>& a, Int n) noexcept {
		Mint res(1), tmp = a;
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};

using mint = Mint<>;

int main() {

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

	Int N;
	cin >> N;

	vector<Int> A(N);
	for (Int i = 0; i < N; i++) {
		cin >> A[i];
	}

	sort(A.begin(), A.end());

	Int temp = A[0];
	Int cnt = 0;
	Int num = 0;
	vector<Int> card(N);
	for (Int i = 0; i < N; i++) {
		if (A[i] == temp) {
			cnt++;
		}
		if(A[i]!=temp){
			card[num] = cnt;
			temp = A[i];
			num++;
			cnt = 1;
		}
		if (i == N - 1) {
			card[num] = cnt;
		}
	}

	Int diff = 0;
	for (Int i = 0; i < num; i++) {
		diff += card[i] - 1;
	}

	Int ans;
	if (diff % 2) {
		if (card[num] % 2) {
			ans = num;
		}
		else {
			ans = num + 1;
		}
	}
	else {
		if (card[num] % 2) {
			ans = num + 1;
		}
		else {
			ans = num;
		}
	}

	cout << ans << "\n";

}

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


int main() {
    int n;cin>>n;
    vector<ll> by(0);
    vector<ll> a(n);
    vector<bool> ch(n,true);
    for(ll i=1;i<=20000000000;i*=2) by.push_back(i);
    rep(i,n)cin>>a[i];
    sort(a.begin(),a.end());
    int ans=0;
    
    for(int i=n-1;i>=0;i--){
        if(!ch[i]) continue;
        ll k=a[i];
        ll l=*upper_bound(by.begin(),by.end(),k); 
        ch[i]=false;   
        auto its=lower_bound(a.begin(),a.end(),l-k);
        if(*its==l-k&&ch[its-a.begin()]){
            ans++;
            ch[its-a.begin()]=false;
            (*its)--;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#define N 200000 
int main(){
  int a[N],n,fx,i,tmin;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    if(a[i]-tmin>fx){
      fx = a[i]-tmin;
    }
    if( i==0 ){
      tmin=a[i];
      fx=-a[i];
    }
    if(a[i]<tmin){
      tmin = a[i];
    }


  }

  printf("%d\n",fx);

  return 0;
}

Measured memory_bytes: 1376
#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
  int n,i;

  cin >> n;

  for(i=1;i<=n;i++){
    if(i%3==0){
        cout << " " << i;
        continue;
    }

    for(int x=i;x>0;x/=10){
        if( x % 10 == 3 ){
            cout << " " << i;
            break;
        }
    }
  }
  cout << endl;

  return 0;
}



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

using namespace std;

#define ll long long int
#define get(a) ll a; cin >> a;
#define show(a) cout << a << endl;
#define full(p) p.begin(), p.end()
#define sz(a) (ll)(a.size())
#define pb push_back

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout<<fixed;
	////////////////////////////////
	string s;
	cin >> s;

	int a = (s[5]-'0')*10 + s[6]-'0';

	if( a > 4)
	cout << "TBD" << endl;
	else
	cout << "Heisei" << endl;	

	return 0;
}

Measured memory_bytes: 3608
# ABC132
def main():
    n = int(input())
    p = list(map(int, input().rstrip().split()))
    ans = 0
    for i, j, k in zip(p, p[1:], p[2:]):
        if i < j < k or k < j < i:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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

int main(void) {
  int arr[3];
  for (int i = 0; i < 3; i++) {
    cin >> arr[i];
  }
  int n;
  cin >> n;
  sort(arr, arr+3);
  for (int i = 0; i < n; i++) {
    arr[2] = arr[2] * 2;
  }
  cout << arr[2] + arr[1] + arr[0] << endl;
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"math/bits"
	"os"
	// "strconv"
	// "strings"
)

//  長い入力を読む
func ReadLongLines(times int) ([]string, error) {
	result := make([]string, times)
	reader := bufio.NewReader(os.Stdin)
	buffer := bytes.NewBuffer(make([]byte, 0))
	readBytes := int64(2)
	for i := 0; i < times; i++ {
		for {
			readBuf, isPrefix, err := reader.ReadLine()
			// fmt.Printf("Reader.Read: %d\n", len(readBuf))
			readBytes += int64(len(readBuf) + 1)
			if err != nil {
				if err == io.EOF {
					fmt.Println("EOF")
					break
				} else {
					return result, err
				}
			}
			_, err = buffer.Write(readBuf)
			if err != nil {
				return result, err
			}
			// end of line
			if !isPrefix {
				result[i] = buffer.String()
				buffer.Reset()
				// reader = bufio.NewReader(os.Stdin)
				break
			}
		}
	}
	// 先読みしてしまうようなので、戻しておく
	os.Stdin.Seek(-int64(reader.Buffered()), os.SEEK_CUR)
	return result, nil
}

// 出力 for 競プロ
type Console struct {
	writer *bufio.Writer
}

func NewConsole() Console {
	return Console{bufio.NewWriter(os.Stdout)}
}
func (this *Console) Printf(format string, a ...interface{}) {
	fmt.Fprintf(this.writer, format, a...)
}
func (this *Console) Println(s string) {
	fmt.Fprintln(this.writer, s)
}
func (this *Console) Close() {
	this.Flush()
}
func (this Console) Flush() {
	this.writer.Flush()
}

func PrintList(list []int) {
	con := NewConsole()
	defer con.Flush()
	for i := range list {
		if i == 0 {
			con.Printf("%d", list[i])
		} else {
			con.Printf(" %d", list[i])
		}
	}
	con.Println("")
}

func main() {
	con := NewConsole()
	defer con.Flush()

	var n int
	fmt.Scanf("%d", &n)

	
	// 部分集合
	fmt.Scanf("%d", &n)
	t := uint32(0)
	for i := 0; i < n; i++ {
		x := 0
		fmt.Scanf("%d", &x)
		t = t + (1 << uint32(x))
	}


	for i := uint32(0); i <= t; i++ {
		if i & t != i {
			continue
		}
		con.Printf("%d:", i)
		begin := bits.TrailingZeros32(i)
		end := bits.LeadingZeros32(i)
		for j := begin; j < 32-end; j++ {
			//fmt.Printf("%d & 1<<%d (%d)\n",i, j, (i & (1 << uint32(j))))
			if 0 < (i & (1 << uint32(j))) {
				con.Printf(" %d", j)
			}
		}
		con.Println("")
	}

}



Measured memory_bytes: 6172
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#define ll long long
using namespace std;



int main(){
  ll K,X;
  cin>>K>>X;
  if(K*500>=X) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍


int main(){
	ll n;cin>>n;
    map<string,ll> m;
    string w;cin>>w;
    char c = w[w.size()-1];
    m[w] = 1;
    rep(i,1,n){
        cin>>w;
        if(m[w] == 1 || w[0] != c){
            cout << "No" << endl;
            return 0;
        }else{
            c = w[w.size()-1];
          	m[w] = 1;
        }
    }
    cout << "Yes" << ednl;

}


Measured memory_bytes: 256
#include<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline int GCD(int a,int b){return !b?a:GCD(b,a%b);}
const int Primes[168]=
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
 97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,
 227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,
 367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,
 509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
 661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,
 829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
const char common[]="not coprime",disjoint[]="pairwise coprime",several[]="setwise coprime";
char esc[1000000];
static inline int Divide(int x)
{
  if(!x){return 0;}
  rep(i,168)
  {
    if(Primes[i]*Primes[i]>x)break;
    if(x%Primes[i])continue;
    if(esc[Primes[i]-1])return 0;
    esc[Primes[i]-1]=1;
    while(x%Primes[i]==0&&x)x/=Primes[i];
  }
  if(x>1){if(esc[x-1])return 0;esc[x-1]=1;}
  return 1;
}
int main(void)
{
  int N=IN(),A=0,f=0,g=0,temp=0,penultimate=0;
  rep(i,N)
  {
    A=IN();g=GCD(g,A);if(i&&g!=1){f=1;}if(!f&&penultimate&&GCD(penultimate,A)!=1){f=1;}
    penultimate=temp;temp=A;if(f)continue;else{if(!Divide(A))f=1;}
  }
  if(g>1)return puts(common),0;else{if(f)return puts(several),0;else return puts(disjoint),0;}
}

Measured memory_bytes: 2504
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <random>

#define FOR(idx, begin, end) for(int idx = (int)(begin); idx < (int)(end); ++idx)
#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif
#define INF  1000000000

using namespace std;
typedef long long lint;
const int MOD = 1000000007;
random_device rnd;

int dp[45][410][410];

int main() {

	cin.tie(0);
	
	int N, M_a, M_b, ans = INF;
	cin >> N >> M_a >> M_b;
	DMP(N);
	vector<int> a(N), b(N), c(N);
	FOR(i, 0, N) cin >> a[i] >> b[i] >> c[i];

	FOR(i, 0, 45)FOR(j, 0, 410)FOR(k, 0, 410) {
	
		dp[i][j][k] = INF;
	}

	dp[0][0][0] = 0;

	FOR(i, 0, N) {
		FOR(j, 0, 400) {
			FOR(k, 0, 400) {

				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				dp[i + 1][j + a[i]][k + b[i]] = min(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k] + c[i]);
			}
		}
	}

	for (int i = 1; i * max(M_a, M_b) < 410; i++) ans = ans > dp[N][i*M_a][i*M_b] ? dp[N][i*M_a][i*M_b] : ans;
	if (ans == INF) cout << "-1";
	else cout << ans;

	return 0;
}

Measured memory_bytes: 29824
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
b = [None] * n
for i, c in enumerate(a):
    b[i] = [None] * n
    b[i][0] = a[i]
    for j in range(1, n): b[i][j] = min(b[i][j - 1], a[(i - j) % n])
d = None
for i in range(n):
    c = i * x
    for j in range(n): c += b[j][i]
    if d is None or c < d: d = c
print(d)


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

bool is_prime(int N){
    if(N == 1) return false;
    if(N == 2) return true;

    for(int i=2; i*i<=N; i++){
        if(N % i == 0) return false;
    }
    return true;
}

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

    vector<int> sum(100010, 0);
    for(int i=0; i<50000; i++){
        int c = 2*i+1, n = 2*(i+1)+1;
        sum[n] = sum[c];
        if(is_prime(n) && is_prime((n+1)/2)) sum[n] += 1;
    }

    for(int q=0; q<Q; q++){
        int l, r; cin >> l >> r;
        cout << sum[r] - sum[max(0,l-2)] << endl;
    }
}

Measured memory_bytes: 1024
def ipt(N=0,switch=0):
    if N == 0:
        return list(map(int,input().split()))
    else:
        if switch==0:
            return [list(map(int,input().split())) for _ in range(N)]
        else:
            return [int(input()) for _ in range(N)]

N,M=ipt()
a=ipt(M)

for i in range(1,N+1):
    ans_list=[]
    for j in range(M):
        if a[j][0] == i:
            ans_list.append(a[j][1])
        if a[j][1] == i:
            ans_list.append(a[j][0])
    print(len(ans_list))

Measured memory_bytes: 3064
N, K = map(int, input().split())
p = list(map(int, input().split()))

expectedList = [(1 + s) /  2 for s in p]
cumsum = sum(expectedList[:K])
confirm_cumsum = cumsum

for i in range(K, N):
    cumsum += expectedList[i]
    cumsum -= expectedList[i - K]
    if cumsum > confirm_cumsum:
        confirm_cumsum = cumsum

print(confirm_cumsum)

Measured memory_bytes: 25060
import java.util.*;
 
 
class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        long N = sc.nextLong();
        long min = Integer.MAX_VALUE;

        for(long a=1; a<=Math.sqrt((double)N);a++){
            if(N%a==0){
                long b = N/a; 
                int f = Math.max(String.valueOf(a).length(),String.valueOf(b).length());
                if(f<min) min = f;
            }
            
        }
        System.out.println(min);

    }
}

Measured memory_bytes: 25300
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;

int N, K;
ll x[100001];

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

	ll ans = 1e18;
	for (int i = 0; i + K <= N; i++) {
		if (x[i] < 0 && x[i + K - 1] > 0) {
			if (abs(x[i]) > abs(x[i + K - 1])) {
				ans = min(ans, abs(x[i]) + abs(x[i + K - 1] * 2));
			}
			else {
				ans = min(ans, abs(x[i]) * 2 + abs(x[i + K - 1]));
			}
		}
		else if (x[i] > 0 && x[i + K - 1] > 0) {
			ans = min(ans, x[i + K - 1]);
		}
		else {
			ans = min(ans, -x[i]);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
)
 
func run() {

	var N int;
    N = nextInt();
    var X int;
    X = nextInt();
    L := make([]int,N);
    for i := 0 ; i < int(N) ; i++ {
        L[i] = nextInt();
    }
	solve(N, X, L);

}

func solve(N int, X int, L []int){
	sum := 0
	count := 0
	for i := 0; i < int(N); i++ {
		sum += L[i]
		if sum <= X {
			count++
		}
	}

	Println(count+1)
}


// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int {
	a, err := strconv.Atoi(next())
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}


type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

/////数字と文字
// 基本クラス
type NS struct {
    Num int
    Str string
}

//////　数字と数字
// 基本クラス
type NN struct {
    Num1 int
    Num2 int
}

 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}



Measured memory_bytes: 2816
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define pb push_back
#define READ(FILE) freopen(FILE,"r",stdin)
#define WRITE(FILE) freopen(FILE,"w",stdout)
#define loop(i,s,e) for(int i=s;i<e;i++)
#define mego fast();
using namespace std;
void fast()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

ll lcm(ll x, ll y)
{
    return (x*y)/__gcd(x,y);
}
int sum(string s)
{
    int x=0,sz=s.size();
    loop(i,0,sz)x+=(s[i]-'0');
    return x;
}
/*
struct node
{
int data;
node *link;
};
typedef node* nodeptr;
void head_insert(nodeptr& head,int x)
{
    nodeptr tmp;
    tmp=new node;
    tmp->data=x;
    tmp->link=head;
    head=tmp;
}
nodeptr search(nodeptr head,int x)
{
    nodeptr cur=head;
    if(cur ==  nullptr)return cur;
    while(cur->data!=x&&cur->link!=nullptr)
    {
        cur=cur->link;
    }
    if(cur->data==x)return cur;
    else return nullptr;
}
void show(nodeptr head)
{
    nodeptr cur=head;
    if(cur==nullptr)return;
   // cout<<head->data<<" ";
    while(cur->link!=nullptr){
        cout<<cur->data<<" ";
        cur=cur->link;
    }
    cout<<endl;
}
*/

int main()
{
    mego
    int n,a=0,b=0,c=0,d=0;
    string s;
    cin>>n;
    loop(i,0,n)
    {
        cin>>s;
        if(s=="AC")
            a++;
        else if(s=="WA")
            b++;
        else if(s=="TLE")
            c++;
        else
            d++;

    }
    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<b<<endl;
    cout<<"TLE x "<<c<<endl;
    cout<<"RE x "<<d;
    return 0;
}


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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)

#define BR "\n"
#define fcout cout << fixed << setprecision(18)

int main() {
  int n; cin >> n;
  double x[n], y[n];
  rep0(i, n) cin >> x[i];
  rep0(i, n) cin >> y[i];
  
  double d1 = 0, d2 = 0, d3 = 0, d0 = 0;
  rep0(i, n) {
    double d, dd, ddd;
    d = abs(x[i] - y[i]);
    dd = d * d;
    ddd = dd * d;

    d1 += d;
    d2 += dd;
    d3 += ddd;
    d0 = max(d0, d);
  }
  fcout << d1 << BR;
  fcout << sqrt(d2) << BR;
  fcout << pow(d3, 0.3333333333) << BR;
  fcout << d0 << BR;

  return 0;
}


Measured memory_bytes: 3452
package main

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

func main () {
  // fmt.Println("Input: ")
  sc := bufio.NewScanner(os.Stdin)
  sc.Split(bufio.ScanWords)

  var count int8
  var a int
  var b int
  var c int

  if sc.Scan() { a, _ = strconv.Atoi(sc.Text()) }
  if sc.Scan() { b, _ = strconv.Atoi(sc.Text()) }
  if sc.Scan() { c, _ = strconv.Atoi(sc.Text()) }

  for i := a; i <= b; i++ {
    if c % i == 0 { count++ }
  }

  fmt.Printf("%d\n", count)
 }



Measured memory_bytes: 1104
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef pair<int, int>P;

int main(){
    for(int n; cin>>n,n;){
        int mx = 0;
        vector<int>p(n);
        for(int i=0;i<n;i++){
            cin>>p[i];
        }
        map<P, int>dp[2];
        dp[0][P(0, 0)] = 0;
        for(int i=0;i<n;i++){
            map<P, int>::iterator it = dp[i%2].begin();
            for(;it!=dp[i%2].end();it++){
                int earn = (*it).first.first;
                int satsu = (*it).first.second;
                int pay = (*it).second;
                int zeni = satsu * 1000 - pay - earn * 500;

                //pass
                if(dp[(i+1)%2].find(P(earn, satsu)) == dp[(i+1)%2].end()){
                    dp[(i+1)%2][P(earn, satsu)] = pay;
                }
                else{
                    dp[(i+1)%2][P(earn, satsu)] = min(dp[(i+1)%2][P(earn, satsu)], pay);
                }

                //1000円だけで払う
                int turi = 1000 - p[i] % 1000, get500 = 0;
                if(turi == 1000)turi = 0;
                if(turi >= 500){
                    turi -= 500;
                    get500 = 1;
                }
                int nxtEarn = earn + get500;
                int nxtPay = pay + p[i];
                int nxtSatsu = satsu + p[i] / 1000 + (p[i] % 1000 == 0?0:1);
                if(dp[(i+1)%2].find(P(nxtEarn, nxtSatsu)) == dp[(i+1)%2].end()){
                    dp[(i+1)%2][P(nxtEarn, nxtSatsu)] = nxtPay;
                }
                else{
                    dp[(i+1)%2][P(nxtEarn, nxtSatsu)] = min(dp[(i+1)%2][P(nxtEarn, nxtSatsu)], nxtPay);
                }
                
                //500円もらえるように払う
                int need = abs((p[i] % 1000) - 500);
                if(zeni < need)continue;
                nxtEarn = earn + 1;
                nxtPay = pay + p[i];
                if(dp[(i+1)%2].find(P(nxtEarn, nxtSatsu)) == dp[(i+1)%2].end()){
                    dp[(i+1)%2][P(nxtEarn, nxtSatsu)] = nxtPay;
                }
                else{
                    dp[(i+1)%2][P(nxtEarn, nxtSatsu)] = min(dp[(i+1)%2][P(nxtEarn, nxtSatsu)], nxtPay);
                }

            }
            dp[i%2].clear();
        }
        int c = 0, s = 0;
        for(map<P, int>::iterator it = dp[n%2].begin(); it != dp[n%2].end(); it++){
            int earn = (*it).first.first;
            int satsu = (*it).first.second;
            int pay = (*it).second;
            int zeni = satsu * 1000 - pay - earn * 500;
            if(earn > c){
                c = earn;
                s = pay;
            }
            else if(earn == c && pay < s){
                c = earn;
                s = pay;
            }

        }
        cout<<c<<" "<<s<<endl;
    }

    return 0;
}


Measured memory_bytes: 5184
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int n,m,pre[100100],ok[100100];
string s;
int main()
{
    go;
    cin>>n>>m>>s;
    s='0'+s;
    for(int i=1;i<n;i++)
    {
        if(s[i]=='A'&&s[i+1]=='C')
            pre[i]=pre[i-1]+1,ok[i]=1;
        else
            pre[i]=pre[i-1];
    }
    pre[n]=pre[n-1];
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        if(ok[y]==1)
            cout<<max(0,pre[y-1]-pre[x-1])<<endl;
        else
            cout<<max(0,pre[y]-pre[x-1])<<endl;
    }
    return 0;
}


Measured memory_bytes: 1772
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int main()
{
	#define int long long
	int l,r;
	cin >> l >> r;
	int s = l%2019;
	if(s == 0)
	{
		cout << "0" << "\n";
	}
	else if(((l+2019)-s) <= r)
	{
		cout << "0" << "\n";
	}
	else
	{
		int mod = 2019,ans = 7000;
		for(int i = l; i <= r; i++)
		{
			for(int j = i+1; j <= r; j++)
			{
				int temp = ((i%mod)*(j%mod))%mod;
				ans = min(ans,temp);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 256
/// 23-01-2018
/// MD:NUR ALAM
/// Eastern University of Bangladesh

#include "bits/stdc++.h"

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, N) for (int i = 0; i < (N); ++i)
#define repp(i, a, b) for (int i = (a); i < (b); ++i)
#define fo(i, a, b) for (int i = (a); i <(b); ++i)
#define fors(i, s) for (int i = 0; s[i]; ++i)
#define rs(x) scanf("%s", (x))
#define mp make_pair
#define pb push_back
#define mso(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)

using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef long double lu;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<pii> vpll;
typedef pair<ll,ll> Pll;
typedef map<string,int>msi;
typedef set<ll>se;

template<class t> void _r(t &x) { cin >> x; }
void _r(int &x) { scanf("%d", &x); }
void _r(int64_t &x) { scanf("%lld", &x); }
void _r(double &x) { scanf("%lf", &x); }
void _r(char &x) { scanf(" %c", &x); }
void _r(char *x) { scanf("%s", x); }
void r() {}
template<class t, class... u> void r(t &head, u &... tail) { _r(head); r(tail...); }
template<class t> void _w(const t &x) { cout << x; }
void _w(const int &x) { printf("%d", x); }
void _w(const int64_t &x) { printf("%lld", x); }
void _w(const double &x) { printf("%.16f", x); }
void _w(const char &x) { putchar(x); }
void _w(const char *x) { printf("%s", x); }
template<class t,class u> void _w(const pair<t,u> &x) {_w(x.f); putchar(' '); _w(x.s);}
void w() {}
template<class t, class... u> void w(const t &head, const u &... tail) { _w(head); putchar(sizeof...(tail) ? ' ' : '\n'); w(tail...); }
template<class t, class... u> void debug(const t &head, const u &... tail) {
#ifdef HOME
#endif
}

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

int main(){

    string s;
    r(s);
    s[3]='8';
    w(s);
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#define mod 1000000007
#define mod2 998244353
#define int long long
#define endl "\n"
#define p_b push_back
#define fastIO ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
template <class T> 
using _ost = tree<
		T, 
		null_type, 
		less<T>, 
		rb_tree_tag, 
        tree_order_statistics_node_update>;
// char alphabet[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'};
void swap(int* a,int* b){
    int temp = *a;
    *a=*b;
    *b=temp;
}
/* prime factors */
vector<int> primeFactors(int n)  
{  
    // Print the number of 2s that divide n  
    std::vector<int> pf;
    if(n%2==0){
    	
    	pf.push_back(2);
    	while (n % 2 == 0)  
	        n=n/2; 
    }   
    // n must be odd at this point. So we can skip  
    // one element (Note i = i +2)  
    for (int i = 3; i <= sqrt(n); i = i + 2)  
    {  
        // While i divides n, print i and divide n  
        if(n%i==0){
        	pf.push_back(i);
	        while (n % i == 0)	      
	            n = n/i;  	       
    	}
    }   
    // This condition is to handle the case when n  
    // is a prime number greater than 2  
    if (n > 2)  
        pf.push_back(n);
    return pf;
}
/* all divisors excluding 1 */
vector<int> allDivisors(int n) 
{ 
    // Vector to store half of the divisors 
    vector<int> all; 
    for (int i=1; i<=sqrt(n); i++) 
    { 
        if (n%i==0) 
        { 
            if (n/i == i) // check if divisors are equal 
                all.p_b(i); 
            else
            { 
                all.p_b(i); 
  
                // push the second divisor in the vector 
                all.push_back(n/i); 
            } 
        } 
    } 
  
    // The vector will be printed in reverse 
    return all;
}
int32_t main(){
 	fastIO;
 	int n;cin>>n;
 	if(n==2)cout<<1<<endl;
 	else{
 		vector<int> pf=allDivisors(n);
 		vector<int> ad=allDivisors(n-1);
 		int ans=(int)ad.size()-1;
 		for(int i=1;i<pf.size();i++){
 			int num=n;
 			while(num%pf[i]==0)num/=pf[i];
 			if(num==1)ans++;
 			else if(num>=3){
 				if((num-1)%pf[i]==0)ans++;
 			}
 		}
 		cout<<ans<<endl;
 	}	
} 	

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int MOD = 1e9 + 7;

ll N,M,K,H,W;

ll r,s,p;

ll points(char me, char mach){
	if(me == 's' and mach == 'p') {return s;}
	if(me == 'p' and mach == 'r') {return p;}
	if(me == 'r' and mach == 's') {return r;}
	return 0;
}

ll dynamo(vector<char> hand){
	vector<vector<ll>> dp(3, vector<ll> (hand.size(), 0));
	// 0 == rock , 1 == sic, 2 == paper
	dp[0][0] = points('r', hand[0]);
	dp[1][0] = points('s', hand[0]);
	dp[2][0] = points('p', hand[0]);
	for(int i = 1; i < hand.size(); ++i){
		dp[0][i] = max( dp[1][i-1] , dp[2][i-1] ) + points('r', hand[i]);
		dp[1][i] = max( dp[0][i-1] , dp[2][i-1] ) + points('s', hand[i]);
		dp[2][i] = max( dp[1][i-1] , dp[0][i-1] ) + points('p', hand[i]);
	}
	return max(dp[0][hand.size()-1], max(dp[1][hand.size()-1], dp[2][ hand.size()-1] ));
}

int main(){
	cin >> N >> K;
	
	cin >> r >> s >> p;
	vector<vector<char>> hands(K);
	char c;
	REP(i, N){
		cin >> c;
		hands[i%K].push_back(c);
	}
	ll ans = 0;
	REP(i,K){
		ans += dynamo(hands[i]);
	}
	cout << ans;
	return 0;
}




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

int main(){
	int n,k,q; cin >>n>>k>>q;
	vector<int> p(n,k-q); 
	for(int i=0; i<q; i++){
		int a; cin>>a;
		p.at(--a)++;
	}
	for(auto i:p) cout <<(i>0?"Yes":"No") << endl;
}

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

const ll INF = 1ll << 60;
ll MOD = 998244353;

int main()
{

    ll w, h, x, y;
    cin >> w >> h >> x >> y;

    double want = (double)w * h / 2;
    int ans = 0;

    if (w * y == want)
        ans++;
    if (h * x == want)
        ans++;

    printf("%lf %d", want, ans == 2 ? 1 : 0);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <array>

using std::cin;

int main()
{
    std::array<int, 4> a, b;
    while (cin >> a.at(0)) {
        for (auto i = 1; i < 4; i++) {
            cin >> a.at(i);
        }
        for (auto i = 0; i < 4; i++) {
            cin >> b.at(i);
        }

        int hit = 0, blow = 0;
        for (auto i = 0; i < 4; i++) {
            for (auto j = 0; j < 4; j++) {
                if (a.at(i) == b.at(j)) {
                    if (i == j) {
                        hit++;
                    } else {
                        blow++;
                    }
                }
            }
        }

        std::cout << hit << " " << blow << std::endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <deque>
#define ll long long

using namespace std;

int N; 
vector<ll>BIT;
void add(int a, ll w) {
	for (int x = a; x <= N; x += x & -x) BIT[x] += w;
}
ll sum(int a) {
	ll ret = 0;
	for (int x = a; x > 0; x -= x & -x) ret += BIT[x];
	return ret;
}

vector<int>sortedA;


int main() {
	cin >> N;
	vector<int>a(N);
	BIT.assign(N + 1, 0);
	sortedA.assign(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		sortedA[i] = a[i];
	}
	sort(sortedA.begin(), sortedA.end());
	ll cnt = 0;
	for (int i = 0; i < N; i++) {
		int tar = a[i];
		int left = 0, right = N;
		while (left + 1 < right) {
			int mid = (left + right) / 2;
			if (sortedA[mid] == tar) {
				left = mid; right = mid + 1;
			}
			else if (sortedA[mid] < tar)
				left = mid + 1;
			else right = mid;
		}
		cnt += i - sum(left + 1);
		add(left + 1, 1);
	}

	cout << cnt << endl;







	return 0;
}





Measured memory_bytes: 6008
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>

using namespace std;

using ll = long long;

int main() {
    ll n, k;
    cin >> n >> k;
    
    vector<ll> a(n);
    vector<ll> b;
   
 
    for (int i = 0; i < n; i++) {
        ll t, d;
        cin >> t >> d;
        
        t--;
       
        if (a[t] == 0) {
            a[t] = d;
        } else if (a[t] < d) {
            b.push_back(a[t]);
            a[t] = d;
        } else {
            b.push_back(d);   
        }
    }
    
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    
    ll ans = 0;
    ll sum = 0;
    
    if (b.size() > k) {
        b.resize(k);
    }
    
    sum = accumulate(b.begin(), b.end(), ll(0));
    
    for (ll i = 0; i < k; i++) {
        if (a[i] == 0) {
            break;
        }
        
        if (b.size() + i + 1 > k) {
            sum -= b.back();
            b.pop_back();
        }
        
        sum += a[i];
        
        ans = max(ans, sum + (i + 1) * (i + 1));
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 2168
use proconio::input;

// use std::f64::consts::PI;
// use std::cmp::*;
// use std::collections::*;
// use proconio::marker::Chars;
// const MOD: u64 = 1000000007;
// const INF_I64: i64 = 92233720368547758;
// const INF_USIZE: usize = 18446744073709551;

macro_rules! echo {
    ($($a:expr),*) => {
          $(println!("{}",$a))*
      }
}

fn main() {
    input! {
        m:u32,
        k:u32
    }
    if m <= 1 {
        if k == 0 {
            if m == 1 {
                println!("0 0 1 1");
            }
            if m == 0 {
                println!("0 0");
            }
        } else {
            println!("-1")
        }
        return;
    }

    if k >= 2u32.pow(m) {
        println!("-1");
        return;
    }
    // let mut ans = vec![k];
    print!("{}", k);
    let tmp = 2u32.pow(m);

    for j in 0..2 {
        for i in 0..tmp {
            let x = if j == 1 { tmp - i - 1 } else { i };
            if x != k {
                // ans.push(i);
                print!(" {}", x);
            }
        }
        if j == 0 {
            print!(" {}", k);
        }
    }
    println!();
}


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

typedef long double ld;                                   // XD
#define int long long   
#define PB push_back 
#define all(x) (x).begin(),(x).end()
#define ii pair <int,int>
#define mii map <int,int>
#define vi vector<int> 
#define vii vector< ii >
#define F first
#define S second 
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a; i>=b; --i)
#define sz(x) (int)((x).size())
const double pi=2*acos(0.0);
inline void io(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);         
#endif
}

const int mod = 1e18+7;
const int maxn = 2e5+5;

void solve(){
	int x; cin>>x;
    if(x >= 30) cout<<"Yes"; else cout<<"No";
}
signed main() 
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //io();
    cout<<setprecision(16);
    
    int tc=1;// cin>>tc; 
    while(tc--){
        solve();cout<<'\n';
    }
    return 0;
}



Measured memory_bytes: 3648
def solve(string):
    n, *fp = string.split()
    n = int(n)
    f = fp[:10 * n]
    p = list(map(int, fp[10 * n:]))
    ans = -n * 10**7
    int_f = [int("".join(f[10 * i:10 * (i + 1)]), 2) for i in range(n)]
    for o in range(1, 2**10):
        tmp = [sum(map(int, "{:b}".format(o & _f))) for _f in int_f]
        ans = max(ans, sum([p[11 * i + t] for i, t in enumerate(tmp)]))
    return str(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(2 * n)])))


Measured memory_bytes: 3188
import sys
def input():
    return sys.stdin.readline()
n = int(input())
xd = [[int(i) for i in input().split()] for _ in range(n)]
xd.sort()


num_max = 2**(n-1).bit_length()
seg_max = [0] * (2 * num_max)
ide_ele_max = -1


def init_max(init_max_val):
    # set_val
    for i in range(n):
        seg_max[i+num_max-1] = init_max_val[i]
    # built
    for i in range(num_max-2, -1, -1):
        seg_max[i] = max(seg_max[2*i+1], seg_max[2*i+2])


def update_max(k, x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1], seg_max[k*2+2])


def query_max(p, q):
    if q <= p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res = ide_ele_max
    while q-p > 1:
        if p & 1 == 0:
            res = max(res, seg_max[p])
        if q & 1 == 1:
            res = max(res, seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res, seg_max[p])
    else:
        res = max(max(res, seg_max[p]), seg_max[q])
    return res


y = [0] * n
j = n-1
for x, d in reversed(xd):
    if x + d > xd[-1][0]:
        y[j] = n
    else:
        mi = 0
        ma = n - 1
        while mi != ma:
            m = (mi + ma) // 2 + 1
            if xd[m][0] < x + d:
                mi = m
            else:
                ma = m - 1
        if mi == j:
            y[j] = mi+1
        else:
            y[j] = query_max(j+1, mi+1)
    update_max(j, y[j])
    j -= 1
dp = [0] * (n + 1)
dp[-1] = 1
j = n-1
for i in y:
    if j == y[j]:
        dp[j] = dp[j+1]
    dp[j] = (dp[j + 1] + dp[y[j]]) % 998244353
    j -= 1
print(dp[0])


Measured memory_bytes: 96092
import java.util.Scanner;

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

        int N = in.nextInt();
        int[] a = new int[N+2];
        int sum = 0;
        for (int i = 1; i <= N; i++) {
            a[i] = in.nextInt();
            sum += Math.abs(a[i] - a[i-1]);
        }
        sum += Math.abs(a[N+1] - a[N]);
        for (int i = 1; i <= N; i++) {
            System.out.println(sum + Math.abs(a[i+1] - a[i-1]) - Math.abs(a[i] - a[i-1]) - Math.abs(a[i+1] - a[i]));
        }
    }
}


Measured memory_bytes: 68080
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a, b;
    cin>>a>>b;
    string n1, n2;
    ll t1 = a, t2 = b;
    while(t2) {
    	n1.pb(a + '0');
    	t2--;
    }
    while(t1) {
    	n2.pb(b + '0');
    	t1--;
    }
    cout<<min(n1, n2)<<"\n";
}

Measured memory_bytes: 256
<?php
$n = intval(fgets(STDIN));
if($n == 1){
  echo 1;
  exit;
}
for($i = 0; $i < $n; $i++){
  fscanf(STDIN, "%d%d", $x[], $y[]);
}
$maxHit = 0;
for($i = 1; $i < $n; $i++){
  for($h = 0; $h < $i; $h++){
    $dx = $x[$i] - $x[$h];
    $dy = $y[$i] - $y[$h];
    $hit = 0;
    for($j = 0; $j < $n; $j++){
      for($k = 0; $k < $j; $k++){
        if($x[$k] - $x[$j] ==  $dx && $y[$k] - $y[$j] ==  $dy || 
           $x[$k] - $x[$j] == -$dx && $y[$k] - $y[$j] == -$dy){
          $hit ++;
        }
      }
    }
    $maxHit = max($maxHit, $hit);
  }
}
echo $n - $maxHit;



Measured memory_bytes: 4728
#include <stdio.h>

int main(void)
{
	int A, B, C, D;
	scanf("%d %d %d %d", &A, &B, &C, &D);
	while(1) {
		C = C - B;
		if (C <= 0) {
			printf("Yes\n");
			break;
		}
		A = A - D;
		if (A <= 0) {
			printf("No\n");
			break;
		}
	}
	return 0;
}

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

int main(){
  double x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  double a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  double x3,y3,x4,y4,X3,Y3,X4,Y4;
  double costheta=(x2-x1)/a;
  double sintheta=(y2-y1)/a;
  X3=a;
  Y3=a;
  X4=0;
  Y4=a;
  x3=X3*costheta-Y3*sintheta+x1;
  y3=X3*sintheta+Y3*costheta+y1;
  x4=X4*costheta-Y4*sintheta+x1;
  y4=X4*sintheta+Y4*costheta+y1;
  cout<<x3<<' '<<y3<<' '<<x4<<' '<<y4<<endl;
}

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

#define MOD 1000000007
#define MODSET(d) if ((d) >= MOD) d %= MOD;

using namespace std;

int arr[205];

int main()
{
    #ifdef VSP4
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

	int n, i, j, ans = 1e9, curr;
	string str;
	
	cin >> str;
	
	for (i = 0; i + 1 < str.size(); i++)
	{
		if ((str[i] == str[i+1]))
		{
			cout << i+1 << " " << i+2 << "\n";
			return 0;
		}
	}
	
	for (i = 0; i + 2 < str.size(); i++)
	{
		if ((str[i] == str[i+1]) || (str[i+1] == str[i+2]) || (str[i] == str[i+2]))
		{
			cout << i+1 << " " << i+3 << "\n";
			return 0;
		}
	}
	
	cout << "-1 -1\n";
		
    return 0;
}


Measured memory_bytes: 512
n = int(input())
*v, = map(int, input().split())
*c, = map(int, input().split())

dp = [[0]*(n+1) for _ in range(n+1)]

for i in range(n+1):
    for j in range(n):
        dp[i][j+1] = dp[i][j]
        dp[i][j+1] = max(dp[i][j], dp[i][j]+v[j]-c[j])

print(dp[n][n])


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

void calc_burger(int x, ll *height, ll *patty) {
  if (x == 0) {
    height[x] = 1;
    patty[x] = 1;
    return;
  }
  calc_burger(x - 1, height, patty);
  height[x] = 3 + height[x - 1] * 2;
  patty[x] = 1 + patty[x - 1] * 2;
}

ll calc_patty(ll x, int layer, ll *height, ll *patty) {
  if (x >= height[layer]) return patty[layer];
  if (x <= 1) return 0;

  ll num = 0;
  num += calc_patty(x - 1, layer - 1, height, patty);
  if (x > 1 + height[layer - 1]) num++;
  num += calc_patty(x - 2 - height[layer - 1], layer - 1, height, patty);

  return num;
}

int main() {
  ll n, x;
  cin >> n >> x;

  ll height[51] = {}, patty[51] = {};

  calc_burger(n, height, patty);
  cout << calc_patty(x, n, height, patty) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for (int i=(a); i>=(b); --i)
#define REP(i,b) for (int i=0; i<(b); ++i)
#define endl '\n'
#define sz(x) (int) x.size()
#define mod %
#define fillchar(x,y,z) memset(x,z,y)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef long long int64;
typedef unsigned long long qword;
using namespace std;
const int base=1e9+7;
const int maxn=105;
int n,k;
int a[maxn];
int f[maxn][100005];
void Input()
{
    cin >> n >> k;
    FOR(i,1,n)
        cin >> a[i];
}
void Solve()
{
    f[0][0]=1;
    FOR(i,1,n) {
        FOR(j,0,k)
            f[i][j]=f[i-1][j]-(j-min(j,a[i])==0?0:f[i-1][j-min(j,a[i])-1]);
        FOR(j,1,k) {
            f[i][j]+=f[i][j-1];
            if (f[i][j]<0) f[i][j]+=base;
            if (f[i][j]>=base) f[i][j]-=base;
        }
    }
    cout << f[n][k];
}
int main()
{
    #ifdef meomeomeooooo
        freopen("input.txt","r",stdin);
        //freopen(".out","w",stdout);
    #endif // meomeomeooooo
    iostream::sync_with_stdio(false);
    cin.tie(0);
    Input();
    Solve();
    return 0;
}


Measured memory_bytes: 40832