akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 105;
const int MAXM = 11005;

int s, t;
namespace Dinic{
	struct Edge{
		int u, v, c, f;
		Edge() {}
		Edge( int u, int v, int c, int f ) :
			u(u), v(v), c(c), f(f) {}
	} edge[MAXM<<1];
	int n, ecnt, head[MAXN], nxt[MAXM<<1];
	inline void init(){
		ecnt = 0;
		memset( head, -1, sizeof head );
	}
	inline void adde( int u, int v, int c ){
		edge[ecnt] = Edge( u, v, c, 0 );
		nxt[ecnt] = head[u]; head[u] = ecnt++;
		edge[ecnt] = Edge( v, u, 0, 0 );
		nxt[ecnt] = head[v]; head[v] = ecnt++;
	}
	int dis[MAXN], cur[MAXN];
	queue<int> bfsq;
	inline bool bfs(){
		for( int i = 0; i <= n; ++i ) dis[i] = 0;
		dis[s] = 1; bfsq.push(s);
		while( !bfsq.empty() ){
			int u = bfsq.front(); bfsq.pop();
			for( int i = head[u]; ~i; i = nxt[i] ){
				Edge &e = edge[i];
				if( e.c > e.f && !dis[e.v] ){
					dis[e.v] = dis[u] + 1;
					bfsq.push(e.v);
				}
			}
		}
		return dis[t];
	}
	ll dfs( int u, ll res ){
		if( u == t || !res ) return res;
		ll flow = 0;
		for( int &i = cur[u]; ~i; i = nxt[i] ){
			Edge &e = edge[i];
			if( e.c > e.f && dis[e.v] == dis[u] + 1 ){
				ll f = dfs( e.v, min( res, (ll)e.c-e.f ) );
				flow += f; res -= f;
				e.f += (int)f; edge[i^1].f -= (int)f;
				if( !res ) break;
			}
		}
		return flow;
	}
	inline ll mincut(){
		ll flow = 0;
		while( bfs() ){
			for( int i = 0; i <= n; ++i ) cur[i] = head[i];
			flow += dfs( s, LINF );
		}
		return flow;
	}
}

int n;
ll ans, tot;

int main(){
	scanf( "%d", &n );
	s = 0; t = n + 1; Dinic::n = n + 1;
	Dinic::init();
	for( int i = 1; i <= n; ++i )
		for( int j = i+i; j <= n; j += i )
			Dinic::adde( i, j, INF );
	for( int i = 1; i <= n; ++i ){
		int x; scanf( "%d", &x ); ans += x;
		x = -x;
		if( x > 0 ) Dinic::adde( s, i, x ), tot += x;
		else Dinic::adde( i, t, -x );
	}
	tot = -tot + Dinic::mincut();
	printf( "%lld\n", ans - tot );
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
int main()
{

	int len[200];
	int max = 0;
	for(int num = 0 ;num < 200 ; num++)
	{
		string str;
		string item;
		vector<string> list;
		getline(cin, str);
		if (str == "")
		{
			break;
		}

		stringstream ss(str);
		while (getline(ss, item, ' ') && !item.empty()) {
			list.push_back(item);
		}
		int sum = stoi(list[0].c_str()) + stoi(list[1].c_str());
		int count = 0;
		for (int i = 10; i <= 10000000; i = i * 10)
		{
			count++;
			if(sum < i)
			{
				len[num] = count;
				max++;
				break;
			}


		}
	}
	for (int num = 0; num < max; num++)
	{
		cout << len[num] << endl;

	}
	return 0;
}

Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
int a[10][10],m,n,flag;//a数组表示能不能选
char kk[10];//这个数组用来输入
void dfs(int x,int y){
    if(x==m-1&&y==n-1){//如果能走到最后一格
        for(int i=0;i<m;++i)for(int j=0;j<n;++j){
            if(a[i][j])return;//如果有个没走过
        }
        flag=1;//标记
        return;//返回
    }
    if(flag==1)return;//加快，优化
    if(a[x+1][y]){//如果可以向下走
        a[x+1][y]=0;//表示走过
        dfs(x+1,y);
        a[x+1][y]=1;//回溯
    }
    if(a[x][y+1]){//同上（懒）
        a[x][y+1]=0;
        dfs(x,y+1);
        a[x][y+1]=1;
    }
    if(!a[x][y+1]&&!a[x+1][y])return;
    //如果既不能向右又不能向下，就返回
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<=m;++i){
        gets(kk);//输入
        for(int j=0;j<n;++j)
        if(kk[j]=='#')a[i-1][j]=1;
        //如果是#，就说明可以从这里走
    }
    if(a[0][0]){
        a[0][0]=0;//肯定要走，先打上标记
        dfs(0,0);
    }
    if(flag)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int k,a,b;
	scanf("%d %d %d",&k,&a,&b);
  int i;
  int flag=0;
  for(i=a;i<b+1;i++){
    if(i%k==0){
      flag=1;
      break;
    }
  }
  if(flag==0){
    printf("NG");
  }
  else{
    printf("OK");
  }  
	return 0;
}

Measured memory_bytes: 2156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii  = pair<int,int>;
const int INF=1001001001;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define MOD 1000000007
#define EPS 10e-8
int gcd(int a,int b){return b?gcd(b,a%b):a;}    //最大公約数
int lcm(int a, int b) {return a * b / gcd(a, b);}   //最小公倍数

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    char c = s[0];
    int ans = 1;
    rep(i, n)
    {
        if(s[i]!=c)
            ans++;
        c = s[i];
    }
    cout << ans << endl;
}

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

int main() {
  int N,D;
  cin >> N >> D;

  int P;
  P = ((D + 1) * 2) - 1;
  cout << (N + (P - 1)) / P <<endl;
}

Measured memory_bytes: 256
s = int(input())
if s <= 10**9:
  print(0,0,s,1,0,1)
elif s == 10**18:
  print(0,0,10**9,0,0,10**9)
else:
  m = s//10**9+1
  a = 10**9-s%10**9
  print(0,0,m,1,a,10**9)

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, m;
int mat[MAX][MAX], c[MAX], d[MAX];

void dfs_init(){
	for(int i=0; i<n; i++) c[i]=WHITE;
	return;
}

void dfs_visit(int u, int cnt){
	c[u]=GRAY;
	d[u]=cnt;
	for(int v=0; v<n; v++){
		if(mat[u][v]==1 && c[v]==WHITE){
			dfs_visit(v, cnt);
		}
	}
	c[u]=BLACK;
	return;
}

int main(){
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			mat[i][j]=0;
		}
	}
	vector<pair<int,int>> e;
	for(int i=0; i<m; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		mat[a][b]=1;
		mat[b][a]=1;
		e.push_back(make_pair(a,b));
	}

	int ans=0;
	for(int i=0; i<e.size(); i++){
		dfs_init();
		mat[e[i].first][e[i].second]=0;
		mat[e[i].second][e[i].first]=0;
		int cnt=0;
		for(int j=0; j<n; j++){
			if(c[j]==WHITE){
				dfs_visit(j, cnt);
				cnt++;
			}
		}
		int a=d[0];
		for(int j=0; j<n; j++){
			if(d[j]!=a){
				ans++;
				break;
			}
		}
		mat[e[i].first][e[i].second]=1;
		mat[e[i].second][e[i].first]=1;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    int n, m;
    cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    sort(d.begin(), d.end());
    cin >> m;

    rep(i, m) {
        int t;
        cin >> t;
        auto iter = lower_bound(d.begin(), d.end(), t);
        if (t != *iter) {
            cout << "NO" << endl;
            return 0;
        } else
            d.erase(iter);
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 3956
n,m = map(int,input().split())
ann = [str(input()) for i in range(n)]
bmm = [str(input()) for i in range(m)]
for y in range (n-m+1):
    for x in range(n-m+1):
        
        flag = True
        for i in range(m):
            if bmm[i] != ann[y+i][x:x+m]:
                flag = False
        if flag == True:
            break
    if flag == True:
      break
if flag == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<functional>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef queue<P> Q;

int gcd(int a,int b){
    if(b==0){
        return a;
    }else{
        return gcd(b,a%b);
    }
}
int A[100010]={};
int main(){
    int N;
    cin >>N;
    int g;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(i==0){
            g=A[0];
        }else{
            g=gcd(g,A[i]);
        }
    }
    cout<<g;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s,t;cin >> s >> t;
  int a=s.size(),b=t.size();
  s=s+s;
  int nex[200005][26];
  for(int i=0;i<26;i++){
    nex[2*a][i]=2*a;
  }
  for(int i=2*a-1;i>=0;i--){
    for(int j=0;j<26;j++){
      nex[i][j]=nex[i+1][j];
    }
    nex[i][s[i]-'a']=i+1;
  }
  ll ans=0;
  for(int i=0;i<b;i++){
    int c=t[i]-'a';
    int x=ans%a;
    if(nex[x][c]==2*a){
      cout << -1 << endl;
      return 0;
    }
    ans+=nex[x][c]-x;
  }
  cout << ans << endl;
}

Measured memory_bytes: 21120
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <numeric>

using namespace std;

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

    cout << setprecision(15) << 3.141592 * 2 * R << endl;
    return 0;
}


Measured memory_bytes: 3760
#include <stdio.h>

int main(void){
  int x,n,i,j,min,flg;
  int a[100];
  scanf("%d %d", &x,&n);
  if(n == 0){
    printf("%d", x);
    return 0;
  }
  for(i=0;i<n;i++){
    scanf("%d", &a[i]);
  }
  for(i=0;i<n/2+2;i++){
    flg = 0;
    for(j=0;j<n;j++){
      if(x - i == a[j]){
        flg = 1;
        break;
      }
    }
    if(flg == 0){
      min = x - i;
      break;
    }
    flg = 0;
    for(j=0;j<n;j++){
      if(x + i == a[j]){
        flg = 1;
        break;
      }
    }
    if(flg == 0){
      min = x + i;
      break;
    }
  }
  printf("%d", min);
  return 0;
}

Measured memory_bytes: 1732
using System;

class C
{
	static void Main()
	{
		var words = new[] { "dream", "dreamer", "erase", "eraser" };
		var s = Console.ReadLine();

		while (s != "")
		{
			var ok = false;
			foreach (var w in words)
			{
				if (!s.EndsWith(w)) continue;
				s = s.Remove(s.Length - w.Length);
				ok = true;
				break;
			}
			if (ok) continue;
			Console.WriteLine("NO");
			return;
		}
		Console.WriteLine("YES");
	}
}


Measured memory_bytes: 38156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const double pi = 3.141592653589793238;
    double a, b, x;
    cin >> a >> b >> x;
    x /= a;
    double space = a * b - x;
    double ans;
    if (space > x) {
        double h = x * 2 / b;
        ans = atan2(b, h) * 180 / pi;
    }
    else {
        double h = space * 2 / a;
        ans = atan2(h, a) * 180 / pi;
    }
    printf("%.10f\n", ans);
    return 0;
}


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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
	int n, m;
	cin >> n >> m;
	int a[n], b[m];
	REP(i, n) cin >> a[i];
	REP(i, m) cin >> b[i];
	sort(a, a+n);
	sort(b, b+m);
	ll ans = 1, ca = n-1, cb = m-1;
	for(int i = n*m; i >= 1; i--){
		if(ca >= 0 && cb>=0 && a[ca] == i && b[cb] == i){
			ca--;
			cb--;
		}
		else if(ca >= 0 && a[ca] == i){
			ca--;
			(ans *= m-1-cb)%=INF;
		}
		else if(cb >= 0 && b[cb] == i){
			cb--;
			(ans *= n-1-ca)%=INF;
		}
		else (ans *= ((m-1-cb)*(n-1-ca)-(n*m-i))%INF)%=INF;
	}
	cout << ans << endl;
} 

Measured memory_bytes: 256
use std::io;
use std::io::BufRead;

fn main() {
    let stdin = io::stdin();
    let mut stdin = stdin.lock();

    let (r, d, mut x) = {
        let mut input = String::new();
        stdin.read_line(&mut input).unwrap();
        let mut input = input.trim().split_whitespace();
        (
            input.next().unwrap().parse::<i32>().unwrap(),
            input.next().unwrap().parse::<i32>().unwrap(),
            input.next().unwrap().parse::<i32>().unwrap(),
        )
    };

    for _ in 0..10 {
        x = r*x - d;
        println!("{}", x);
    }
}


Measured memory_bytes: 4352
package main

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

var scanner = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func main() {
	scanner.Split(bufio.ScanWords)

	nQueries := nextInt()
	for i := 0; i < nQueries; i++ {
		lengths := []int{nextInt(), nextInt(), nextInt()}
		sort.Slice(lengths, func(i, j int) bool { return lengths[i] > lengths[j] })
		if math.Pow(float64(lengths[0]), 2) == math.Pow(float64(lengths[1]), 2)+math.Pow(float64(lengths[2]), 2) {
			fmt.Println("YES")
		} else {
			fmt.Println("NO")
		}
	}
}



Measured memory_bytes: 1224
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int[] nums = new int[n];
        String[] line = scanner.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line[i]);
        }

        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = Math.abs(nums[1] - nums[0]);

        for (int i = 2; i < n; i++) {
            int choice1 = dp[i - 1] + Math.abs(nums[i] - nums[i - 1]);
            int choice2 = dp[i - 2] + Math.abs(nums[i] - nums[i - 2]);

            dp[i] = Math.min(choice1, choice2);
        }

        System.out.println(dp[n - 1]);
    }
}


Measured memory_bytes: 51012
A, B, C, D, E, F = map(int, input().split())
A *= 100
B *= 100
Smax = E * F // 100
S, W = [False for i in range(Smax+1)], [False for i in range(F+1)]
S[0], W[0] = True, True
for i in range(1, len(S)):
    if i - C >= 0:
        if S[i-C] == True:
            S[i] = True
    if i - D >= 0:
        if S[i-D] == True:
            S[i] = True
for i in range(1, F+1):
    if i - A >= 0:
        if W[i-A] == True:
            W[i] = True
    if i - B >= 0:
        if W[i-B] == True:
            W[i] = True

conc = 0
ans = [A, 0]
for i in reversed(range(len(S))):
    if S[i] == True:
        for j in range(1, F-i+1):
            if W[j] == True and 100 * i <= j * E:
                if 100 * i / (i+j) > conc:
                    conc = 100 * i / (i+j)
                    ans = [i+j, i]
                    break
print(" ".join(map(str, ans)))

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


 int main() {
 int n,k;
 cin>>n>>k;
 int a[n];
 for(int i=0;i<n;i++)
    cin>>a[i];
 int d[n];
 d[0]=0;
 d[1]=abs(a[0]-a[1]);
 for(int i=2;i<n;i++)
 {
   d[i]=INT_MAX;
   for(int j=max(0,i-k);j<i;j++)
   {
       d[i]=min(d[i],d[j]+abs(a[i]-a[j]));
   }

 }
 cout<<d[n-1]<<endl;

 }






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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main(void){

    string s1, s2;
    cin >> s1 >> s2;

    string s3 = s2.substr(0, s1.size());
    if(s1 == s3){
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define INOUT freopen(name".inp","r", stdin); freopen(name".out","w",stdout);
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define f0(i,n) for(i=0;i<n;i++)
#define f1(i,n) for(i=1;i<=n;i++)
#define fab(i,a,b) for(i=a;i<=b;i++)
#define f0r(i,n) for(i=n-1;i>=0;i--)
#define f1r(i,n) for(i=n;i>=1;i--)
#define fabr(i,a,b) for(i=b;i>=a;i--)
#define hi cout<<"hi\n";

#define ln "\n"

using namespace std;
const ld pi=acos(-1);
const ll mod=1e9+7;
const ll MAX=INT_MAX;
const ll MIN=INT_MIN;


int main()
{
    FAST;
    ll t,n,i,j,k,len,x,y,z,f,flag,p,q,mx,mn,l,r,sum,ans,tmp,it,pos;
    
    cin>>t;
    ll a[t],b[t],c[t];
    f0(i,t)
    cin>>a[i]>>b[i]>>c[i];
    
    
    f1(i,t-1)
    {
        a[i]+=max(b[i-1],c[i-1]);
        b[i]+=max(a[i-1],c[i-1]);
        c[i]+=max(b[i-1],a[i-1]);
    }
    t--;
    cout<<max(b[t],max(a[t],c[t]));
    
	return 0;
}


Measured memory_bytes: 2560
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class A
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		var A = GetInts(N);

		int ans = 0;
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N - 1; j++)
			{
				if(A[j] > A[j + 1])
				{
					swap(ref A[j], ref A[j + 1]);
					ans++;
				}
			}
		}

		WriteLine(string.Join(" ", A));
		WriteLine(ans);
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => Enumerable.Range(0, (int)N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(long N) => Enumerable.Range(0, (int)N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDouble()).ToArray();
	public static decimal[] GetDecimals(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDecimal()).ToArray();
	public static string[] GetStrings(long N) => Enumerable.Range(0, (int)N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}


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

typedef long long lnt;

#define lson st, (st + en) >> 1, rt << 1
#define rson ((st + en) >> 1) + 1, en, rt << 1 | 1

const int N = 3e5 + 10;
const int M = 3e5;

int x[N << 2];

void modify (int p, int v, int st, int en, int rt) {
	x[rt] = v; 
	if (st == en) return;
	if (p <= ((st + en) >> 1)) modify(p, v, lson);
	else modify(p, v, rson);
	x[rt] = max(x[rt << 1], x[rt << 1 | 1]);
}

int query (int l, int r, int st, int en, int rt) {
	if (l > en || r < st) return 0;
	if (l <= st && en <= r) return x[rt];
	return max(query(l, r, lson), query(l, r, rson));
}

int a[N];

int main (void) {
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i ++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i ++) {
		int val = query(max(0, a[i] - k), min(M, a[i] + k), 0, M, 1);
		modify(a[i], val + 1, 0, M, 1);
	}
	printf("%d\n", x[1]);
}

Measured memory_bytes: 9092
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Foz(i, a) For(i, 0, a)
#define Doz(i, a) Dor(i, 0, a)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (string& e) { return "\"" + e + "\""; }
string to_string (char e) { return "\'" + string(1, e) + "\'"; }
string to_string (bool e) { return e ? "true" : "false"; }
template <typename T> string to_string (T e) {
	string s = "[ ";
	for (auto& x : e) s += to_string(x) + " ";
	return s + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e) {
	return "(" + to_string(e.first) + ", " + to_string(e.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	string s;
	cin >> s;
	int a = 0, b = 0;
	Trav(x, s) if (x == '1') a++; else b++;
	cout << 2 * min(a, b) << '\n';
}



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

typedef struct {
  vector<int> neighbour;
} Node;

Node node[100];
bool visit[100];

void dfs(int i) {
  visit[i] = true;
  for(int n:node[i].neighbour) {
    if(!visit[n]) dfs(n);
  }
}

void reset() {
  rep(i, 100) {
    node[i].neighbour.clear();
    visit[i] = false;
  }
}

int main() {
  int N, E;
  cin >> N >> E;
  vector<int> a(E), b(E);
  rep(i, E) {
    cin >> a[i] >> b[i];
  }

  int ans = 0;
  rep(i, E) {
    reset();
    rep(j, E) {
      if(j != i) {
        node[a[j]].neighbour.push_back(b[j]);
        node[b[j]].neighbour.push_back(a[j]);
      }
    }
    dfs(1);
    for(int i=1; i<=N; ++i) {
      if(!visit[i]) {
        ++ans;
        break;
      }
    }
  }
  cout << ans << endl;
}

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B, N;
    cin >> A >> B >> N;
    // REP(i, 50) {
    // cout << i << " " << A * i / B << " " << A * (i / B) << endl;
    // }

    // 周期Bなので最大値となるxは、B-1 もしくは単調増加なのでN
    int x = min(B - 1, N);
    cout << A * x / B - A * (x / B) << endl;

    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<string>
#include<map>

using namespace std;

class Dice{
	int face[6] ;
	map<string,int> dir;
	
public:
	Dice(int sai[6]){
		for(int i=0 ; i<6 ; i++){
			face[i] = sai[i] ;
		}
		dir["top"]    = 1 ;
		dir["south"]  = 2 ;
		dir["east"]   = 3 ;
		dir["west"]   = 4 ;
		dir["north"]  = 5 ;
		dir["bottom"] = 6 ;
	}
	void show(string d){
		if(d == "all"){
			for(int i=0 ; i<6 ; i++){
				cout << face[i] << " " ;
			}
			cout << endl;
			return ;
		}else{
			cout << face[dir[d]-1] << endl;
		}
	}
	int get(string d){
		return face[dir[d]-1] ;
	}
	void move(const string str){//動かす
		for(int i=0 ; i<str.size() ; i++){
			turn(str[i]);//char
		}
	}
	void turn(char d){//回す//direction:方向
		map<char, int> mp;
		mp['S'] = 0 ;
		mp['E'] = 1 ;
		mp['W'] = 2 ;
		mp['N'] = 3 ;
		
		static const int index[4][6] ={
			{5,1,3,4,6,2},//south
			{4,2,1,6,5,3},//east
			{3,2,6,1,5,4},//west
			{2,6,3,4,1,5},//north
		};
		
		int copy[6] ;
		for(int i=0 ; i<6 ; i++){
			copy[i] = face[i] ;
		}
		//これは止めて、代入演算子＝をオーバーライドしてもいいかもしれない。しかして、それをやると実行時のメモリが微増するはずだ。
		
		for(int i=0 ; i<6 ; i++){//permutation:置換
			face[i] = copy[index[mp[d]][i]-1] ;
		}
		
		//show("all");//check
	}
	void rotate(void){//回転//SWNの操作で、上から見てCCW:counter clock wise：反時計回りでの90度回転。
		turn('S');
		turn('W');
		turn('N');
	}
	bool adjust(int top,int south){//位置合わせ
		for(int i=0;i<6;i++){
			if(get("top") == top){
				break;
			}
			//cout << "zigzag:" << i << endl ;//check
			turn(i%2==0 ? 'S' : 'E');//三項演算子
		}
		for(int i=0;i<4;i++){
			//cout << "rotate:" << i << endl ;//check
			rotate();
			if(get("south") == south){
				return true ;
			}
		}
		
		return false ;
	}
	bool operator == (Dice obj){
		for(int i=0 ; i<6 ; i++){
			for(int j=0 ; j<4 ; j++){
				bool flg = true ;
				for(int k=0 ; k<6 ; k++){
					if(this->face[k] == obj.face[k]){
						flg &= true ;
					}else{
						flg &= false ;
					}
				}
				if(flg){
					return true ;
				}
				this->rotate();
			}
			this->turn(i%2==0 ? 'S' : 'E');
		}
		return false ;
	}
	/*
	bool operator == (Dice obj){//演算子のオーバーライド
		if(obj.adjust(this->get("top"),this->get("south"))){
			for(int i=0 ; i<6 ; i++){
				if(this->face[i] != obj.face[i]){
					return false ;
				}
			}
			return true ;
		}
		
		return false ;
	}
	*/
};

int main(void){
	// ITP1_11_C　同一判定
	int sai[6] ;
	
	cin >> sai[0] >> sai[1] >> sai[2] >> sai[3] >> sai[4] >> sai[5] ;
	Dice d1(sai);
	
	cin >> sai[0] >> sai[1] >> sai[2] >> sai[3] >> sai[4] >> sai[5] ;
	Dice d2(sai);
	
	cout << (d1==d2 ? "Yes" : "No") << endl ;
}

Measured memory_bytes: 1216
n = int(input())
sp = [0] * n
for i in range(n):
    sp[i] = list(map(str,input().split()))
sp_sorted = sorted(sp, key=lambda x: int(x[1]), reverse=True)
sp_sorted_sorted = sorted(sp_sorted, key=lambda x: x[0])
for i in range(n):
    for j in range(n):
        if sp_sorted_sorted[i] == sp[j]:
            print(j+1)

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    string s;
    cin >> s;

    int ans = 0;
    rep(i,3){
        if (s[i] == 'R'){
            int sum = 1;
            if (i + 1 < 3 && s[i+1] == 'R') sum++;
            if (i + 2 < 3 && s[i+1] == 'R' && s[i+2] == 'R') sum++;
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define F first 
#define S second
#define PB push_back

using namespace std;

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

const int N = 110, M = 5, mod = 1e9 + 7;

int n;
int f[N][M][M][M];

int main()
{
	cin >> n;
	f[0][0][0][0] = 1;
	
	for (int i = 1; i <= n; i ++ )
		for (int a = 0; a <= 4; a ++ )
			for (int b = 0; b <= 4; b ++ )
				for (int c = 0; c <= 4; c ++ )
					for (int j = 1; j <= 4; j ++ )
					{
						if (b == 1 && c == 2 && j == 3) continue;
						if (b == 1 && c == 3 && j == 2) continue;
						if (b == 2 && c == 1 && j == 3) continue;
						if (a == 1 && b == 2 && j == 3) continue;
						if (a == 1 && c == 2 && j == 3) continue;
						f[i][b][c][j] = (f[i][b][c][j] + f[i - 1][a][b][c]) % mod;
					}
	
	int res = 0;
	for (int i = 1; i <= 4; i ++ )
		for (int j = 1; j <= 4; j ++ )
			for (int k = 1; k <= 4; k ++ )
				res = (res + f[n][i][j][k]) % mod;
	cout << res << endl;
    return 0;
}

Measured memory_bytes: 3632
def main():
    import collections
    import sys
    input = sys.stdin.readline
    n = int(input())
    d = list(map(int, input().split()))
    # 各距離の頂点数を求める
    c = collections.Counter(d)
    ans = 1
    tmp = -1
    # 頂点1のみが0である必要がある
    if d[0] != 0 or c[0] > 1:
        print(0)
        exit()
    # 個数の計算
    for i in range(2, n):
        if i - 1 in c.keys():
            ans *= c[i - 1] ** c[i]
            ans %= 998244353
        else:
            tmp = i
            break
    # 距離が連番になっていなければ到達不可能
    if tmp >= 0:
        for j in range(tmp, n):
            if j in c.keys():
                print(0)
                exit()
    print(ans)


if __name__ == "__main__":
    main()

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

int main() {
	int debt = 100000; int n; cin >> n;
	for (int i = 0; i < n; i++) {
		debt = debt * 1.05;
		debt = debt + (debt % 1000 != 0 ? 1000 - debt % 1000 : 0);
	}
	cout << debt << endl;
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  
  string title;
  string number;
  
  if(n <= 999){
    title = "ABC";
    number = to_string(n);
  }
  
  if(n > 999){
    title = "ABD";
    number = to_string(n-999);
  }
  cout << title << endl;
}

Measured memory_bytes: 256
# https://abc096.contest.atcoder.jp/tasks/abc096_c

neighbor_i = [-1, 0, 1, 0]
neighbor_j = [0, -1, 0, 1]

H, W = map(int, input().split())


def can_draw(l, target_i, target_j):
    for i, j in zip(neighbor_i, neighbor_j):
        if target_i + i < 0 or target_j < 0:
            continue
        if target_i + i >= H or target_j + j >= W:
            continue
        if l[target_i + i][target_j + j] == '#':
            return True

    return False


data = []
for i in range(H):
    raw = list(str(input()))
    data.append(raw)


# print(data)


ok = True
for i in range(H):
    for j in range(W):
        if data[i][j] == '#':
            if not can_draw(data, i, j):
                ok = False
                break
    if not ok:
        break

if ok:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define all(x) x.begin(),x.end()
#define gll greater<ll>()

vll z_algorithm(const string &s) {
  ll n=s.size();
  vll prefix(n);
   prefix[0]=n;
   ll i=1,j=0;
  while (i < n) {
  while (i+j < n && s[j] == s[i+j]) j++;
  prefix[i] = j;
  if (j == 0) { i++; 
          continue;
   }
  ll k = 1;
  while (i+k < n && k+prefix[k] < j) {
    prefix[i+k] = prefix[k];
    k++;
  }
  i += k;
  j -= k;
}
  return prefix;
}

void solve(){
  ll n;
 string s;
  cin >> n >> s;
  
 vvll a(n,vll(n,0)); 
 rep(i,0,n) {
  string t=s.substr(i,n-i);
   a[i].resize(t.size());
   a[i]=z_algorithm(t);
 }
   
 ll ans=0;
 rep(i,0,n){
  rep(j,0,a[i].size()){ 
   if(a[i][j]<=j) chmax(ans,a[i][j]);
  }
 }
  cout << ans << endl;
}
int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}  

Measured memory_bytes: 195840
#include <iostream>

using namespace std;

int main(int argc, char** argv){
    int H, W, N;
    cin >> H >> W >> N;
    int a[N];
    for (int i=0; i<N; i++) cin >> a[i];
    int c[H][W];
    int color = 0;
    for (int i=0; i<H; i++){
        for (int k=0; k<W; k++){
            int j = k;
            if (i % 2 == 1) j = W - 1 - k;
            while (a[color] == 0) color++;
            c[i][j] = color + 1;
            a[color]--;
        }
    }
    for (int i=0; i<H; i++)
        for (int j=0; j<W; j++)
            cout << c[i][j] << (j!=W-1 ? " " : "\n");
    return 0;
}


Measured memory_bytes: 384
M = 2147483647
a = [M for i in range(1000000)]

def j_min(x,y):
    if x < y:return x
    else: return y

def find(x,y,i,l,r):
    if r<=x or y<=l:return M
    if x<=l and r<=y: return a[i]
    return j_min(find(x,y,i*2,l,(l+r)/2),find(x,y,i*2+1,(l+r)/2,r))

if __name__=='__main__':
    n, m = (int(x) for x in input().split())
    t=1
    while t<n :t *= 2

    for i in range(m-1,-1,-1):
        com,x,y = (int(x) for x in input().split())
        if com :
            #continue
            print(find(x,y+1,1,0,t))
        else:
            x+=t
            a[x]=y
            while isinstance(x, int) or x >= 2:
               a[int(x/2)]=j_min(a[int(x)],a[int(x)^1])
               x/=2



Measured memory_bytes: 15072
#include"bits/stdc++.h"
using namespace std;

int main(){

	int answer;
	int p1,p2,p3,j1,j2;
	int P,J;

	cin >> p1 >> p2 >> p3 >> j1 >> j2;
	
	P = min( min(p1, p2), p3);
	J = min(j1, j2);

	cout << P + J - 50 << endl;


	/*
	int datanum = 0;
	for(int dataset = 0; dataset < 1; dataset++){
		if(input == 0) break;


		answer[dataset] = sum;

		datanum++;
	}

	for(int dataset = 0; dataset < datanum; dataset++){
		cout << answer[dataset] << endl;
	}
	*/

	

	return 0;
}


Measured memory_bytes: 3108
#include<stdio.h>
#include<string.h>
#include<stdbool.h>

#define YES "Yes"
#define NO "No"

int main()
{
    int a, b, c, k;
    bool result = false;

    scanf("%d %d %d", &a, &b, &c);
    scanf("%d", &k);

    for (int i = 0; i<k; i++)
    {
        if (a >= b)
        {
            b *= 2;
        } else if (b >= c) {
            c *= 2;
            if (b < c)
            {
                result = true;
                break;
            }

        } else {
            result = true;
            break;
        }
    }

    if (result == false)
        printf("%s", NO);
    else 
        printf("%s", YES);

    return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N,M;
  cin >> N >> M;
  vvi A(N,vi(M));
  rep(i,N) {
    rep(j,M) {
      cin >> A[i][j];
      A[i][j]--;
    }
  }
  int ans = INF;
  vi except(M,0);
  while(1) {
    vi cnt(M,0);
    rep(i,N) {
      int idx=0;
      while(idx < M && except[A[i][idx]]) idx++;
      if(idx==M) {
        cout << ans << endl;
        return 0;
      }
      cnt[A[i][idx]]++;
    }
    int n = 0;
    rep(i,M) {
      n = max(n,cnt[i]);
    }
    ans = min(ans,n);
    rep(i,M) {
      if(cnt[i]==n) {
        except[i]++;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

main(void)
{
	int a,b,d,r;
	double f;
	
	scanf("%d %d",&a,&b);
	
	d=a/b;
	r=a%b;
	f=(double)a/b;
	
	printf("%d %d %.5f\n",d,r,f);
	
	return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = pow(2, 57);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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; }




/* main */






signed main(){

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

    int n, len; cin >> n >> len;

    vi x, val;

    rep(i,0,n){
        x.push_back(input());
        val.push_back(input());
    }

    int plus = 0;
    vi left1;
    int s = 0;
    rep(i,0,n){
        s += val[i];
        chmax(plus, s - x[i]);
        left1.push_back(plus);
    }

    vi left2;
    plus = 0;
    s = 0;
    rep(i,0,n){
        s += val[i];
        chmax(plus, s - x[i] * 2);
        left2.push_back(plus);
    }


    s = 0;
    plus = 0;
    vi right1(n, 0);
    revrep(i,n - 1, -1){
        s += val[i];
        chmax(plus, s - (len - x[i]));
        right1[i] = plus;
    }

    vi right2(n, 0);
    plus = 0;
    s = 0;
    revrep(i,n - 1, -1){
        s += val[i];
        chmax(plus, s - (len - x[i]) * 2);
        right2[i] = plus;
    }

    int ans = 0;
    chmax(ans, *max_element(all(left1)));
    chmax(ans, *max_element(all(right1)));

    rep(i,0,n - 1){
        chmax(ans, left2[i] + right1[i + 1]);
    }

    revrep(i,n - 1, 0){
        chmax(ans, right2[i] + left1[i - 1]);
    }

    print(ans);





    


    


    





    
    






    



    





    


    

}



Measured memory_bytes: 5100
#include <bits/stdc++.h>
using namespace std;
 
main(){
  int n, m ;
  cin >> n >> m ;
  int a[n] ;
  int count = 0 ;
  int sum = 0 ;
  for(int i=0;i<n;i++){
    cin >> a[i] ;
    sum += a[i] ;
  }
  for(int i=0;i<n;i++){
    if(4*m*a[i] >= sum ) count ++ ;
  }
  if(count >= m) cout << "Yes" ;
  else cout << "No" ;
  return 0 ;
}

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

int main(){
	int t;
	cin>>t;
	int x = t/500;
	t = t%500;
	// cout<<t<<endl;
	int ans = x*1000;
	// cout<<ans<<endl;
	x = t/5;
	ans += x*5;
	cout<<ans;
	return 0;
}

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

namespace TYC
{
	typedef long long ll;
	const int N = 300005;

	int n, Len, ans, P[N], T[N], L[N], R[N];

	inline int read()
	{
		int x = 0, f = 0, ch = getchar();
		while (!isdigit(ch))
			f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))
			x = x * 10 + ch - '0', ch = getchar();
		return f ? -x : x;
	}

	void work()
	{
		n = read(), Len = read();
		for (int i = 1; i <= n; i++)
			P[i] = read();
		for (int i = 1; i <= n; i++)
		{
			T[i] = read();
			ans += (T[i] / (Len << 1)) * 2;
			T[i] %= Len << 1;
		}
		for (int i = 1; i <= n; i++)
			if (T[i])
			{
				L[i] = 2 * P[i] >= T[i] ? 1 : 3;
				R[i] = 2 * (Len - P[i]) >= T[i] ? 1 : 3;
			}
		ans += R[n];
		int lc = 0, rc = 0;
		for (int i = 1; i < n && P[i] <= Len / 2; i++)
			if (T[i])
			{
				if (L[i] != R[i])
				{
					if (lc)
						lc--, ans++;
					else
						ans += 2;
				}
				else if (L[i] == 1)
					lc++, ans++;
				else
					ans += 2;
			}
		for (int i = n - 1; i && P[i] > Len / 2; i--)
			if (T[i])
			{
				if (L[i] != R[i])
				{
					if (rc)
						rc--, ans++;
					else
						ans += 2;
				}
				else if (L[i] == 1)
					rc++, ans++;
				else
					ans += 2;
			}
		if ((lc + rc) & 1)
			ans++;
		printf("%lld\n", (ll)Len * (ans + 1 + (!R[n])));
	}
}

int main()
{
	TYC::work();
	return 0;
}

Measured memory_bytes: 4992
#include "bits/stdc++.h"
using namespace std;

int ufp[777777],ufr[777777];

void ufinit(int h, int w){
	int i,j;
	for(i=0; i<20*h; ++i){
		for(j=0; j<20*w; ++j){
			ufp[i*1000+j] = i*1000+j;
			ufr[i*1000+j] = 0;
		}
	}
	for(i=0; i<h; ++i){
		for(j=0; j<w; ++j){
			++ufr[i*1000+j];
		}
	}
}

int ufind(int x){
	if(ufp[x]!=x){
		ufp[x] = ufind(ufp[x]);
	}
	return ufp[x];
}

void unionf(int x, int y){
	x = ufind(x);
	y = ufind(y);
	if(x==y){
		return;
	}
	if(ufr[x] < ufr[y]){
		swap(x,y);
	}
	ufp[y] = x;
	ufr[x] += ufr[y];
}

int main(void){
	int n,m,t,p,i,j,k,xl,xr,yl,yr,d,c,ans=0;
	while(cin >> n >> m >> t >> p){
		if(!(n||m||t||p)){
			break;
		}
		ufinit(n,m); ans = 0;
		xl = 0; xr = n; yl = 0; yr = m;
		for(k=0; k<t; ++k){
			cin >> d >> c;
			if(d==1){
				for(i=0; i<c; ++i){
					for(j=yl; j<yr; ++j){
						unionf((xl+i)*1000+j,(xl+2*c-i-1)*1000+j);
					}
				}
				xl += c; xr = max(xr,xl+c);
			}else{
				for(i=xl; i<xr; ++i){
					for(j=0; j<c; ++j){
						unionf(i*1000+(yl+j),i*1000+(yl+2*c-j-1));
					}
				}
				yl += c; yr = max(yr,yl+c);
			}
		}
		for(k=0; k<p; ++k){
			cin >> i >> j;
			i += xl; j += yl;
			cout << ufr[ufind(i*1000+j)] << endl;
		}
	}
	return 0;
}


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

int main() {
  //数の代入
  int N;
  cin >> N;
  vector<int> numbers(N);
  for (int i = 0; i < N; i++) {
    cin >> numbers.at(i);
  }
  
  //AliceとBobの点数を作る
  int Alice = 0;
  int Bob = 0;
  
  //numbersをソート→リバースして，順番にAlice,Bobに入れていく
  sort(numbers.begin(),numbers.end());
  reverse(numbers.begin(),numbers.end());
  
  for (int i = 0; i < N; i++) {
    if ( i % 2 == 0) {
      Alice += numbers.at(i);
    }
    else {
      Bob += numbers.at(i);
    }
  }
  
  cout << Alice - Bob << endl;
}



Measured memory_bytes: 256
input = raw_input

nums = input().split(" ")

ds = [0, 0]
for i, num in enumerate(nums):
    if "." in num:
        d = num[::-1].index(".")
        ds[i] = d
        num = int(num.replace(".", ""))
    else:
        num = int(num)

    if i == 0:
        a = num
    else:
        b = num

out = a * b
sd = sum(ds)
out = out // (10 ** sd)

print(out)

Measured memory_bytes: 64272
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int count = 0;
    while(n > 0) {
      n /= k;
      count++;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 35696
n = int(input())
A = [int(i) for i in input().split()]

def f(x):
    ans = 0
    cnt = 0
    for i in range(n):
        if i % 2 == x:
            if cnt + A[i] < 0:
                cnt += A[i]
            else:
                ans += abs(cnt + A[i] - (-1))
                cnt = -1
        else:
            if cnt + A[i] > 0:
                cnt += A[i]
            else:
                ans += abs(cnt + A[i] - 1)
                cnt = 1
    return ans

print(min(f(0), f(1)))

Measured memory_bytes: 14332
N, K = gets.split.map(&:to_i)
M = 10**9 + 7

def mpow(x, n)
  ret = 1
  while n > 0
    if n.even?
      x = x * x % M
      n >>= 1
    else
      ret = ret * x % M
      n -= 1
    end
  end
  ret
end

@m = {}

def f(x)
  k = K/x
  @m[x] ||= mpow(k, N) - (2 .. k).inject(0){|s, y| s + f(x*y)}
end

puts (1 .. K).inject(0){|s, k| (s + f(k)*k) % M}

Measured memory_bytes: 19224
#include<bits/stdc++.h>
using namespace std;
long long Ceil(long long n,long long m){
    if(n%m!=0){
        return n/m+1;
    }
    else return n/m;
}
int main(){
  long long n,m,sum=0;
  cin>>n>>m;
  long long a[n];
  for(long long i=0;i<n;i++){
    cin>>a[i];
  	sum+=a[i];
  }
  sort(a,a+n);
  long long cnt=0;
  for(long long i=n-1;i>=n-m;i--){
     if(a[i]>=Ceil(sum,(4LL*m))){
      cnt++;
    }
  }
  if(cnt==m){
    cout<<"Yes";
  }
  else
    cout<<"No";

   return 0;
       }













Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if ((a+b)>(c+d))
        cout<<"Left";
    else if ((a+b)<(c+d))
        cout<<"Right";
    else if ((a+b)==(c+d))
        cout<<"Balanced";
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()

using ll = long long;
using P = pair<int,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;



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

    int n;
    cin >> n;

    n %= 10;

    if(n == 2 || n == 4 || n == 5 || n == 7 || n == 9){
        cout << "hon" << "\n";
    }
    if(n == 0 || n == 1 || n == 6 || n == 8){
        cout << "pon" << "\n";
    }
    if(n == 3){
        cout << "bon" << "\n";
    }


    return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int red = Integer.parseInt(sc.next());
        int green = Integer.parseInt(sc.next());
        int blue = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        String ans = "No";
        while (k > 0) {
            if (green <= red) {
                green *= 2;
                k--;
            } else if (blue <= green) {
                blue *= 2;
                k--;
            }
            if ((green > red) && (blue > green)) {
                ans = "Yes";
                break;
            }
        }

        System.out.println(ans);
        sc.close();
    }

}


Measured memory_bytes: 35548
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
for i in range(1, N):
    candy = A[i] + A[i - 1]

    # Kより少ないならそのまま
    if candy < K:
        continue

    # 右にあるやつをたべる
    r = min(A[i], candy - K)
    candy -= r
    A[i] -= r
    ans += r
    if candy < K:
        continue

    # 左にあるやつを食べる
    l = min(A[i - 1], candy - K)
    candy -= l
    A[i - 1] -= l
    ans += l
    if candy < K:
        continue

print(ans)


Measured memory_bytes: 14672
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll tmp1,tmp2,tmp3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}

ll maxi = 6400;
int main(){
  ll h,w;
  cin >> h >> w;
  vector<vector<ll>> a(80,vector<ll>(80)),b(80,vector<ll>(80)),c(80,vector<ll>(80));
  //ll ans[h][w][maxi];
  vector<vector<vector<ll>>> ans(h,vector<vector<ll>>(w,vector<ll>(maxi,0)));
  //memset(ans,sizeof(ans),0);
//  rep(i,h){
//    rep(j,w){
//      rep(k,maxi){
//        ans[i][j][k] = 0;
//      }
//    }
//  }
  rep(i,h){
    rep(j,w){
      cin >> a[i][j];
    }
  }
  rep(i,h){
    rep(j,w){
      cin >> b[i][j];
    }
  }
  rep(i,h){
    rep(j,w){
      c[i][j] = abs(a[i][j] - b[i][j]);
    }
  }
  ans[0][0][c[0][0]] = 1;
  for(ll i = 0;i < h;i++){
    for(ll j = 0;j < w;j++){
      rep(k,maxi){
        if(ans[i][j][k]){
          if(i != h-1){
            tmp1 = k + c[i+1][j];
            if(tmp1 < 6400){
              ans[i+1][j][tmp1] = 1;
            }
            tmp2 = abs(k - c[i+1][j]);
            if(tmp2 < 6400){
              ans[i+1][j][tmp2] = 1;
            }
          }

          if(j != w-1){
            tmp1 = k + c[i][j+1];
            if(tmp1 < 6400){
              ans[i][j+1][tmp1] = 1;
            }
            tmp2 = abs(k - c[i][j+1]);
            if(tmp2 < 6400){
              ans[i][j+1][tmp2] = 1;
            }
          }
        }
      }
    }
  }
  ll mini = INFLONG;
  rep(i,maxi){
    if(ans[h-1][w-1][i]){
      mini = i;
      break;
    }
  }
  cout << mini << endl;
}


Measured memory_bytes: 324736