akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  ll x;
  cin >> N >> x;
  
  vector<ll> a(N);
  REP(i,N) cin >> a[i];
  int ans=0;
  VSORT(a);
  
  for(int i=0;i<N;i++){
      x -= a[i];
      if(x>=0) ans++;
  }
  if(x>0) ans--;
  cout << ans << endl;
}

Measured memory_bytes: 256
import math

a, b, C = [int(n) for n in input().split()]
c = (a**2+b**2-2*a*b*math.cos(math.radians(C)))**0.5
A = (360-2*C)/2
print(0.5*a*b*math.sin(math.radians(C)))
print(a+b+c)
print(b*math.sin(math.radians(C)))


Measured memory_bytes: 5732
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////
int N;
ll K;

vector<ll> color;
bool seen[100005];

void dfs(vector<vector<int>> &G,int v,int pv) {
  ll count = 1;
  if (pv != -1) count++;
  seen[v] = true;
  for (auto nv : G[v]) {
    if (color[nv] != INF) continue;
    color[nv] = count;
    count++;
  }
  for (auto nv : G[v]) {
    if (seen[nv]) continue;
    dfs(G,nv,v);
  }
  return;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); //入出力高速化
  cin >> N >> K;
  vector<vector<int>> G(N);

  rep(i,N-1) {
    int a,b;
    cin >> a >> b;
    a--; b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  
  color.resize(N,INF); 
  color[0] = 0;
  dfs(G,0,-1);
  ll ans = 1;
  rep(i,N) {
    ans *= (K - color[i]);
    ans %= MOD;
  }

  cout << ans << endl;
}

Measured memory_bytes: 8704
#include<bits/stdc++.h>
using namespace std;
//#define debug 1

int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n;
	cin>>n;
	int a[n],b[n];
	//a[i] = xi + xi+1
	//b[i] = xi - xi+2
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	b[n-1]=a[n-1]-a[0];
	for(int i=0;i<=n-2;i++)
		b[i]=a[i]-a[i+1];
	
	int x0_x1=b[0];
	for(int i=2;i<n;i+=2)
		x0_x1+=b[i];
	
	int x[n];
	x[0]=(x0_x1 + a[0])/2;
	for(int i=1;i<n;i++)
		x[i]=a[i-1]-x[i-1];
#ifdef debug
cout<<"a:"<<endl;
for(int i=0;i<n;i++)
	cout<<a[i]<<" ";
cout<<endl<<"b:"<<endl;
for(int i=0;i<n;i++)
	cout<<b[i]<<" ";
cout<<endl<<"x:"<<endl;
for(int i=0;i<n;i++)
	cout<<x[i]<<" ";
#endif
	for(int i=0;i<n;i++)
		cout<<x[i]*2<<" ";
	cout<<endl;
	return 0;
}
/*
x0+x1=a0
x1+x2=a1
x2+x3=a2
x3+x4=a3
x4+x5=a4
......
xm-1 + x0 = am-1

=>
x0-x2
x1-x3
x2-x4
x3-x5
x4-x5
......
xm-1 - x1
*/


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

constexpr int MAX = 100'000;
int N;
int c[2][100100];

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

    std::cin >> N;

    for(int i=0;i<N;++i){
        int v;
        std::cin >> v;

        c[i & 1][v] += 1;
    }

    int n = N / 2, m = N - n;
    int mx_i0 = std::max_element(c[0], c[0] + MAX + 1) - c[0],
        mx_i1 = std::max_element(c[1], c[1] + MAX + 1) - c[1];
    int mn;

    if(mx_i0 != mx_i1){
        mn = (n - c[0][mx_i0]) + (m - c[1][mx_i1]);
    }else if(std::max(std::count(c[0], c[0] + MAX + 1, c[0][mx_i0]), std::count(c[1], c[1] + MAX + 1, c[1][mx_i1])) >= 2){
        mn = (n - c[0][mx_i0]) + (m - c[1][mx_i1]);
    }else{
        int s0 = 0, s1 = 0;
        for(int i=1;i<=MAX;++i){
            if(i != mx_i0){
                s0 = std::max(s0, c[0][i]);
                s1 = std::max(s1, c[1][i]);
            }
        }

        mn = std::min((n - c[0][mx_i0]) + (m - s1),
                      (n - s0) + (m - c[1][mx_i1]));
    }

    std::cout << mn << std::endl;
}


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

using namespace std;

typedef long long ll;

ll n, ans;

int main() {
	cin >> n;
	for (ll i = 1; i*i <= n; i++) {
		if (n % i != 0) continue;
		ll j = n / i;
		//cout << i << ' ' << j << '\n';
		if (i-1 && n % (i-1) == n / (i-1)) ans += i-1;
		if (j-1 && n % (j-1) == n / (j-1)) ans += j-1;
	}
	cout << ans << '\n';
	return 0;
}



Measured memory_bytes: 256
n = gets.to_i
T = gets.split.map &:to_i
V = gets.split.map &:to_i
V << 0

dp = Array.new(n+1) {|i|[-10**18]*(i < n ? V[i]+1 : 1)}
dp[0][0] = 0
(0..n-1).each{|i|
  (0..V[i]).each{|p|
    (0..V[i+1]).each{|q|
      next unless p-T[i] <= q && q <= [p+T[i], V[i]].min
      b = (T[i]+p+q)/2.0
      if b < V[i]
        d = (2*b**2 - p**2 - q**2)/2.0
      else
        d = (2*V[i]**2 - p**2 - q**2)/2.0 + V[i]*(T[i]-(2*V[i]-p-q))
      end
      nd = dp[i][p] + d
      dp[i+1][q] = nd if dp[i+1][q] < nd
    }
  }
}
puts "%.10f" % dp[n][0]


Measured memory_bytes: 3836
n, m, c = [int(x) for x in input().split()]
bb = [int(x) for x in input().split()]
a = [list(map(int, input().split())) for _ in range(n)]

result = 0
for ae in a:
  tmp = sum([a*b for a, b in zip(ae, bb)]) + c
  if tmp > 0:
    result += 1

print(result)

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

int main(){
  int N;
  cin >> N;
  int x = 0;
   for (int i = 0; i < N; i++){
     string S;
     cin >> S;
     	if (S == "Y"){
      	x++;
     	}
      	      
   }
  
  if (x>0){
   cout << "Four" <<endl;
  }
  else{
   cout << "Three" <<endl;
  }
}


Measured memory_bytes: 256
H, W = map(int, input().split())

grid = [['.' for i in range(0, W+2)] for i in range(0, H+2)]
temp = []

for i in range(1, H+1):
    temp.append(list(input()))
    grid[i][1:1+W] = temp[i-1][::]
    
ans = 'Yes'
    
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] == '#':
            if grid[i+1][j] == '#' or grid[i-1][j] == '#':
                pass
            elif grid[i][j+1] == '#' or grid[i][j-1] == '#':
                pass
            else:
                ans = 'No'

print(ans)


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

int main(){
    string S;
    cin >> S;
    ll total=0,count=0;
    
    for(ll i=0;i<S.length();i++){
        if(S[i]=='>'){
            count++;
        }else{
            total+=(count+1)*count/2;
            count=0;
        }
    }
    
    
    
    total+=(count+1)*count/2;
    count=0;
    
    
    for(ll i=0;i<S.length();i++){
        if(S[i]=='<'){
            count++;
        }else{
            total+=count*(count-1)/2;
            count=0;
        }
    }
    
    total+=(count+1)*count/2;
    count=0;
    
    ll a=0,b=0,c=0;
    
    for(ll i=0;i<S.length();i++){
        if(S[i]=='<'){
            if(i!=0){
                if(S[i-1]==S[i]){
                    a++;
                }else{
                    if(a-b>0) total+=a-b;
                    a=0;
                    b=0;
                    a++;
                }
            }else{
                a++;
            }
            c=1;
        }else{
            if(c) b++;
        }
    }
    
    if(a-b>0&&S[S.length()]=='>') total+=a-b;
    
    
    
    cout << total << endl;
    

    return 0;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define PI (3.141592653589793)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

int N,W;
int w[110],v[110];
int dp[110][100100];

signed main(){
    cin>>N>>W;
    rep(i,N)cin>>w[i]>>v[i];
    rep(i,110)rep(j,100100)dp[i][j]=INF;
    dp[0][0]=0;
    rep(i,N){
        rep(sum_v,100100){
            if(sum_v-v[i]>=0)chmin(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i]);
            chmin(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }
    int ans=0;
    rep(i,100100){
        if(dp[N][i]<=W)chmax(ans,i);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 86272
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

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

		ArrayList<Integer> lstInt = new ArrayList<Integer>();
		String line = "";
		String[] strArray;
		int result = 0;
		int cnt = 0;

		while (cnt < 200 && (line = br.readLine()) != null)
		{
			strArray = line.split(" ", 0);
			result = Integer.parseInt(strArray[0]) + Integer.parseInt(strArray[1]);
			lstInt.add(Integer.toString(result).length());
			++cnt;
		}

		for (int digit : lstInt)
		{
			System.out.println(digit);
		}

	}
}

Measured memory_bytes: 24308
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081
//????§£?????????
//?????????????????????

#include<iostream>
#include<complex>
#include<cstdio>
using namespace std;

typedef complex<double> xy_t;
double x[3], y[3];
double pro(xy_t a, xy_t b) {
    return (conj(a)*b).real();
}
int main()
{
    xy_t p[3], a, b, c, d;
    char n;
    while (cin >> x[0] >> n >> y[0] >> n >> x[1] >> n >> y[1] 
        >> n >> x[2] >> n >> y[2])
    {
        p[0] = xy_t(x[0], y[0]);
        p[1] = xy_t(x[1], y[1]);
        p[2] = xy_t(x[2], y[2]);
        a = p[2] - p[0];
        b = p[1] - p[0];
        c = b*pro(a, b) / norm(b) + p[0];
        d = c + c - p[2];
        printf("%.6f %.6f\n", real(d), imag(d));
    }
    return 0;
}

Measured memory_bytes: 1264
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Mod=1000000007;
int n;
#define Maxn 5005
int head[Maxn],v[Maxn<<1],nxt[Maxn<<1],tot=0;
inline void add_edge(int s,int e){
	tot++;v[tot]=e;nxt[tot]=head[s];head[s]=tot;
	tot++;v[tot]=s;nxt[tot]=head[e];head[e]=tot;
}
int dp[Maxn][Maxn];
int siz[Maxn],way[Maxn],tmp[Maxn];

void dfs(int u,int f){
	dp[u][1]=1;siz[u]=1;
	for(int i=head[u];i;i=nxt[i])
		if(v[i]^f){
			dfs(v[i],u);
			for(int j=1;j<=siz[u]+siz[v[i]];++j)tmp[j]=0;
			for(int j=1;j<=siz[u];++j)
				for(int k=1;k<=siz[v[i]];++k){
					tmp[j+k]=(tmp[j+k]+1ll*dp[u][j]*dp[v[i]][k])%Mod;
					tmp[j]=(tmp[j]+1ll*(Mod-dp[v[i]][k])*way[k]%Mod*dp[u][j])%Mod;
				}
			for(int j=1;j<=siz[u]+siz[v[i]];++j)dp[u][j]=tmp[j];
			siz[u]+=siz[v[i]];
		}
}

inline void rd(int &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
}

int main(){
	rd(n);
	way[0]=1;
	for(int i=2;i<=n;i+=2)way[i]=1ll*way[i-2]*(i-1)%Mod;
	int s,e;
	for(int i=1;i<n;++i){
		rd(s);rd(e);
		add_edge(s,e);
	}
	dfs(1,0);
	int Ans=0;
	for(int i=1;i<=n;++i)Ans=(Ans+1ll*way[i]*dp[1][i])%Mod;
	printf("%d\n",Ans);
}

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

typedef long long int ll;

int main(){
 ll N;
 cin >> N;
 ll ans = 10000000000000000;
 for(ll i = 1;i < pow(N,0.5) + 1;i++){
     if(N % i == 0){
         ans = min(ans,i + N / i);
     }
 }
 cout << ans - 2 << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0)
//#define MULTI_TEST
//#define GOOGLE
#ifdef LOCAL
#include "debugger.h"
#else
#define db(...)
#endif
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
const ll MOD = 1e9 + 7;
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }

bool overlap(ll l1, ll r1, ll l2, ll r2)
{
	if (r1 < l2 || r2 < l1)
		return false;
	return true;
}
void solve(int tc)
{
	ll a, b;
	cin >> a >> b;
	int highest_bit = 60;
	while (highest_bit >= 0)
	{
		ll res1 = a & (1ll << highest_bit);
		ll res2 = b & (1ll << highest_bit);
		if (res1 == res2)
		{
			if (a & (1ll << highest_bit))
				a = a ^ (1ll << highest_bit);
			if (b & (1ll << highest_bit))
				b = b ^ (1ll << highest_bit);
			highest_bit--;
			continue;
		}
		else
			break;
	}
	db(highest_bit);
	if (highest_bit < 0)
	{
		cout << 1 << ln;
		return;
	}
	ll T = (1ll << highest_bit);
	ll l1 = a, r1 = T - 1;
	ll l2 = T, r2;
	int k = 0;
	while (T + (1ll << k) <= b)
		k++;
	k--;
	r2 = T + (1ll << (k + 1)) - 1;
	ll l3 = T + a, r3 = 2 * T - 1;
	db(l1, r1, l2, r2, l3, r3, k);
	ll ans = (r1 - l1 + 1);
	if (overlap(l2, r2, l3, r3))
	{
		l2 = min(l2, l3);
		r2 = max(r2, r3);
		ans += (r2 - l2 + 1);
	}
	else
	{
		ans += (r2 - l2 + 1);
		ans += (r3 - l3 + 1);
	}
	cout << ans << ln;
	return;
}

int main()
{
#ifndef LOCAL
	FASTIO;
#endif
	int t = 1;
#ifdef LOCAL
	clock_t start, stop;
	start = clock();
#endif
#ifdef MULTI_TEST
	cin >> t;
#endif
	for (int tc = 1; tc < t + 1; tc++)
	{
#ifdef GOOGLE
		cout << "Case #" << tc << ": ";
#endif
		solve(tc);
	}
#ifdef LOCAL
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

int main() {
  int n;
  S(n);
  while(n) {
    int r = n % 10;
    n /= 10;
    if(r == 9) {
      printf("Yes\n");
      return 0;
    }
  }
  printf("No\n");
  return 0;
}

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

#define ll long long
#define pb push_back
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fr freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define mp make_pair
#define F first
#define S second

using namespace std;

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

string a;
int main ()
{
	speed;
	cin>>a;
	string s="";
	for (int i=0;i<a.size();i++){
		if (a[i]=='B'){
			if (s.empty()){
				continue;
			}
			else {
				s.pop_back();
			}
		}
		else {
			s+=a[i];
		}
	}
	cout<<s;
}



Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d", $n);
$a_number = explode(' ', trim(fgets(STDIN)));

for($i = 0; $i < $n; ++$i){
	if($a_number[$i] % 2){
		continue;
	}
	if(!($a_number[$i] % 3) || !($a_number[$i] %5)){
		continue;
	}
	echo 'DENIED';
	exit;
}
echo "APPROVED";
?>

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

int ans[365],c[26],s[365][26],last[26],csum,nowscore,newscore;
const int INF=1e9,d=365,starttemp=4000,endtemp=100;
double temperature,prob;
const double TIMELIMIT=1.97*CLOCKS_PER_SEC;

#define REP(i,n) for(int i=0;i<n;i++)

void FIN(bool a){
  if(a){
    ofstream fout("output.txt");
    REP(i,d)fout<<ans[i]+1<<"\n";
    fout.close();
    return;
  }
  REP(i,d)cout<<ans[i]+1<<"\n";
  return;
}
/*
int score(){
  int res=0;
  memset(last,-1,sizeof(last));
  REP(day,d){
    res+=s[day][ans[day]];
    last[ans[day]]=day;
    REP(i,26)res-=c[i]*(day-last[i]);
  }
  return res;
}
*/
int score(){//上のがO(26*365)、こっちがO(365)のスコア計算
  int res=0,minus=csum;
  memset(last,-1,sizeof(last));
  REP(day,d){
    res+=s[day][ans[day]];
    minus-=c[ans[day]]*(day-last[ans[day]]);
    last[ans[day]]=day;
    res-=minus;
    minus+=csum;
  }
  return res;
}
void swap(){
  int RAND=rand();
  int day=RAND%(d-1);
  RAND^=newscore;
  int diff=RAND%min(d-day-1,10)+1;
  swap(ans[day],ans[day+diff]);
  newscore=score();
  prob=exp((newscore-nowscore)/temperature);
  if(prob>(rand()%INF)/(double)INF)nowscore=newscore;
  else swap(ans[day],ans[day+diff]);
}
void onechange(){
  int day=rand()%365;
  REP(i,26){
    int tmp=ans[day];
    ans[day]=i;
    newscore=score();
    prob=exp((newscore-nowscore)/temperature);
    if(prob>(rand()%INF)/(double)INF)nowscore=newscore;
    else ans[day]=tmp;
  }
}

int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  clock_t start=clock();
  memset(last,-1,sizeof(last));
  cin>>c[0];
  REP(i,26){cin>>c[i];csum+=c[i];}
  REP(i,d)REP(j,26)cin>>s[i][j];
  REP(day,d){
    int idx,mx=-INF;
    REP(i,26){
      int A=c[i]*(day-last[i])+s[day][i];
      if(mx<A)mx=A,idx=i;
    }
    ans[day]=idx,last[idx]=day;
  }
  nowscore=score();
  while(true){
    clock_t nowt=clock();
    const double Time=static_cast<double>(nowt-start);
    if(Time>TIMELIMIT)break;
    temperature=starttemp+(double)(endtemp-starttemp)*Time/TIMELIMIT;
    REP(_,50)
      if((_^newscore)&1)swap();
      else onechange();
  }
  FIN(0);
}


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

#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int lli;
typedef pair<int, int> P;

int main() {
    string s;
    cin >> s;
    int size = (int)s.length();
    int first_0 = 0, first_1 = 0;

    bool is_0 = false;
    for (int i = 0; i < size; i++) {
        if (is_0) {
            if (s[i] != '0')
                first_0++;
            //cout << "a" << endl;
            //cout << s[i] << endl;
            //cout << i << endl;
        }
        else {
            if (s[i] != '1')
                first_0++;
            //cout << "b" << endl;
            //cout << s[i] << endl;
            //cout << i << endl;
        }
        is_0 = !is_0;
    }

    is_0 = true;
    for (int i = 0; i < size; i++) {
        if (is_0) {
            if (s[i] != '0')
                first_1++;
            //cout << "c" << endl;
            //cout << s[i] << endl;
            //cout << i << endl;
        }
        else {
            if (s[i] != '1')
                first_1++;
            //cout << "d" << endl;
            //cout << s[i] << endl;
            //cout << i << endl;
        }
        is_0 = !is_0;
    }
    //cout << first_0 << endl;
    //cout << first_1 << endl;

    cout << min(first_0, first_1) << endl;
}


Measured memory_bytes: 512
from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

import sys
input=sys.stdin.readline
n,m,s,t=map(int,input().split())



en=Graph()
snu=Graph()

for i in range(m):
    u,v,a,b=map(int,input().split())
    en.add_edge(u,v,a)
    en.add_edge(v,u,a)
    snu.add_edge(u,v,b)
    snu.add_edge(v,u,b)

enen=Dijkstra(en,s)
snusnu=Dijkstra(snu,t)
ans=[enen.shortest_distance(n)+snusnu.shortest_distance(n)]

for i in range(n-1,0,-1):
    d1=enen.shortest_distance(i)
    d2=snusnu.shortest_distance(i)
    ans.append(min(ans[-1],d1+d2))


for i in range(1,n+1):
    print(10**15-ans[-i])


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


int main(){
  ll n;
  cin >> n;
  vector<ll> re;
  ll ans=0;
  for(ll i=1;i*i<=n;++i){
    if(n%i==0){
      re.push_back(i);
      //ans+=(i-1);
      if(i*i!=n){
        re.push_back(n/i);
        //ans+=(n/i-1);
      }
    }
  }
  sort(re.begin(),re.end());
  for(int i=1;i<re.size();++i){
    if(re[i]==2)continue;
    if((n/(re[i]-1))==n%(re[i]-1)){
      ans+=re[i]-1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
package main

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

var (
	sc = bufio.NewScanner(os.Stdin)
)

func init() {
	sc.Split(bufio.ScanWords)
}

func readInts(n int) []int {
	a := make([]int, n)
	for i := range a {
		sc.Scan()
		a[i], _ = strconv.Atoi(sc.Text())
	}
	return a
}

func main() {
	var n int
	fmt.Scan(&n)
	a := readInts(n)
	d := make([]int, 0, n)
	for _, e := range a {
		i := sort.Search(len(d), func(i int) bool { return d[i] < e })
		if i == len(d) {
			d = append(d, e)
		} else {
			d[i] = e
		}
	}
	fmt.Println(len(d))
}


Measured memory_bytes: 3840
import bisect as bi

# input
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

count = 0

for b in B:
    i = bi.bisect_left(A, b) # A[0],...,A[i - 1] < b
    k = bi.bisect_right(C, b) # b < C[k],...C[N-1]
    count += i * (N - k)

print(count)

Measured memory_bytes: 23092
#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 = 1e9;

int main() {
  string sa, sb, sc, ans;
  cin >> sa >> sb >> sc;

  char ch = sa[0];
  int a = 1, b = 0, c = 0;

  while (true) {
    if (ch == 'a') {
      if (a == sa.length()) ans = "A";
      ch = sa[a];
      a++;
    }
    if (ch == 'b') {
      if (b == sb.length()) ans = "B";
      ch = sb[b];
      b++;
    }
    if (ch == 'c') {
      if (c == sc.length()) ans = "C";
      ch = sc[c];
      c++;
    }
    if (ans != "") break;
  }

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


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

int main()
{
	// Variable declaration
	unsigned int n, b, f, r = 0;
	int v, temp;
	unsigned int resident[4][3][10];

	string inptn;
	int innum;

	// Initializ resident.
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 10; k++)
			{
				resident[i][j][k] = 0;
			}
		}
	}

	// Input n
	cin >> n;

	// Input
	// n times loop
	for (int cnt = 0; cnt < n; cnt++)
	{
		// Input b, f, r, v
		cin >> b >> f >> r >> v;

		// Out of range
		if (b < 1 || b > 4 ||
			f < 1 || f > 3 ||
			r < 1 || r > 10)
		{
			cnt--;
			continue;
		}

		// Copy the resident before updating.
		temp = resident[b - 1][f - 1][r - 1];

		// Update resident
		resident[b - 1][f - 1][r - 1] += v;

		// Out of range
		if (resident[b - 1][f - 1][r - 1] < 0 || resident[b - 1][f - 1][r - 1] > 9)
		{
			// Back to the value before the update.
			resident[b - 1][f - 1][r - 1] = temp;
			cnt--;
			continue;
		}
	}

	// Output
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 10; k++)
			{
				cout << " " << resident[i][j][k];
			}
			cout << endl;
		}
		if (i < 3)
		{
			cout << "####################" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1164
X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

alist = []
ans = 0

for i in range(X):
    alist.append(p[i])
    
for j in range(Y):
    alist.append(q[j])
    
for k in range(C):
    alist.append(r[k])
    
alist.sort(reverse=True)
    
for k in range(X+Y):
    ans += alist[k]

print(ans)

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

int n;
string s[50];
int t[50];
string x;

int main()
{
	ios::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
		cin >> t[i];
	}
	cin >> x;
	int idx;

	for (int j = 0; j < n; j++)
	{
		if (s[j] == x)
		{
			idx = j;
			break;
		}
	}
	int ans(0);

	for (int i = idx + 1; i < n; i++)
	{
		ans += t[i];
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int res=1,last,cnt;
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    last=a[0];
    cnt=1;
    for(int i=1;i<n;i++)
    {
        if(a[i]>last) cnt=1;
        else ++cnt;
        last=a[i];
        res=max(res,cnt);
    }
    cout<<res-1;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cstdio>
#include <typeinfo>
#include <vector>

using namespace std;

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
    string s;
    int val;
    cin >> s;
    vector<int> v;
    int sum = 0;

    val = stoi(s);

    for(int i = 0; i < s.length(); i++){
        v.push_back(ctoi(s[i]));
    }
    
    for(auto itr = v.begin(); itr != v.end(); itr++){
        sum += *itr;
    }

    if( val % sum == 0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

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


int main() {
  int n, l;
  cin >> n >> l;
  vector<int> a(n);
  int sum = 0, num=100100, m;
  rep(i,n) {
    a[i]=l+i;
    sum += a[i];
    if(num>abs(a[i])) {
      num = abs(a[i]);
      m = i;
    }
  }
  cout << sum - a[m] << endl;
  return 0;
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
    public static void main(String[]args) {
        final Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        int count = 0;
        for (int i = 0; i < s.toCharArray().length; i++) {
            if (s.toCharArray()[i] == t.toCharArray()[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 24916
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int n;
  cin >> n;
  if(n==1){
    cout << "Hello World" << endl;
  }else{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
  }
}


Measured memory_bytes: 256
let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]
let M = input[1]
let H = readLine()!.split(separator: " ").map { Int($0)! }

var observatories = Array(repeating: true, count: N)
for _ in 0 ..< M {
    let root = readLine()!.split(separator: " ").map { Int($0)! }
    let A = root[0]
    let B = root[1]

    if H[A - 1] > H[B - 1] {
        observatories[B - 1] = false
    } else if H[B - 1] > H[A - 1] {
        observatories[A - 1] = false
    } else {
        observatories[A - 1] = false
        observatories[B - 1] = false
    }
}

print(observatories.filter { $0 }.count)


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

/* Union-Find-Tree */
/* 必ず要素数をコンストラクタに入れること */
template <class T = long long>
class Union_Find {
  using size_type = std::size_t;
  using _Tp = T;
public:

  vector<_Tp> par;
  vector<_Tp> rnk;

  // 親の根を返す。値の変更は認めない。
  const _Tp & operator[] (size_type child) {
    find(child);
    return par[child];
  }

  Union_Find (size_type n) {
    par.resize(n), rnk.resize(n);
    for (int i = 0; i < n; ++i) {
      par[i] = i;
      rnk[i] = 0;
    }
  }

  // 木の根を求める
  _Tp find(_Tp x) {
    if (par[x] == x)
      return x;
    else
      return par[x] = find(par[x]);
  }

  // xとyの属する集合を併合
  void merge(_Tp x, _Tp y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (rnk[x] < rnk[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if (rnk[x] == rnk[y]) rnk[x]++;
    }
  }

  // xとyが同じ集合に属するか否か
  bool same(_Tp x, _Tp y) {
    return find(x) == find(y);
  }
};

int main() {
  int n,q;
  cin >> n >> q;
  Union_Find<int> uf(n);

  int com, x, y;
  for (int i = 0; i < q; ++i) {
    cin >> com >> x >> y;
    if (com) {
      cout << (uf.same(x, y) ? 1 : 0) << endl;
    } else {
      uf.merge(x, y);
    }
  }
}


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

#define ll long long int

int N,M;
vector<int> vec;
vector<int> p(10);
vector<int> k(10);
vector<vector<int>> s(10,vector<int>(10));
int kazu=0;

void denki(int number,int i){
  if(i<N){
        denki(10*number,i+1);
    denki(10*number+1,i+1);
  }
  else{
    //cout<<number<<endl;
    int hantei = 1;
    for(int a=0;a<M;a++){//電球ぶん回す
      int pika =0;
      int c = number;
      for(int b=N;b>0;b--){
        int amari = c%10; //スイッチbを示す。
        c/=10;
        if(amari==0)
          continue;
        for(int d=0;d<k.at(a);d++){
          if(s.at(a).at(d)==b){
            pika++;
            break;
          }
        }
      }
      //cout<<" "<<pika<<endl;
      if(pika%2!=p.at(a))
        hantei=0;
    }
    if(hantei==1)
      kazu++;
  }
}
int main(){
  cin>>N>>M;

  for(int i=0;i<M;i++){
    cin>>k.at(i);
    for(int j=0;j<k.at(i);j++){
      cin>>s.at(i).at(j);
    }
  }
  for(int i=0;i<M;i++)
    cin>>p.at(i);

  denki(0,1);
    denki(1,1);
    cout<<kazu<<endl;
}

Measured memory_bytes: 256
s=  input()
W = 'W'
B = 'B'
Bi = []
Wi = []

BC = s.count(B)
WC = len(s) - BC

for i in range(len(s)):
  if s[i] == B:
    Bi.append(i)
  else:
    Wi.append(i)
    
W_dist = sum(Wi) - int((0 + WC-1)* (WC)/2)
#print('W',str(W_dist))

B_dist = int((len(s)-1 + WC) * BC /2) - sum(Bi)
#print('B',str(B_dist))

print(int((W_dist + B_dist)/2))

Measured memory_bytes: 11368
n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

if x < a[0]:
    print(0)

else:
    cnt = 0
    for i in range(n-1):
        if x - a[i] < 0:
          break
        cnt += 1
        x -= a[i]
    print(cnt+1 if x == a[-1] else cnt)
    
    


Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  int N, H, ans{}, c{}, L{};
  cin >> N;
  while (cin >> H) {
    if (H <= L)
      ++c;
    else
      c = 0;
    L = H;
    ans = max(c, ans);
  }
  cout << ans << endl;
}


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

int main(){
  int h1, h2, k1, k2;
  int a, b, c, d;
  cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;

  int hResult = 0, kResult = 0;

  for(int i = 1; i <= h1; i++){
    hResult += a;
    if((i % 10) == 0){hResult += c;}
  }
  for(int i = 1; i <= h2; i++){
    hResult += b;
    if((i % 20) == 0){hResult += d;}
  }

  for(int i = 1; i <= k1; i++){
    kResult += a;
    if((i % 10) == 0){kResult += c;}
  }
  for(int i = 1; i <= k2; i++){
    kResult += b;
    if((i % 20) == 0){kResult += d;}
  }
  
  if(hResult > kResult){
    cout << "hiroshi" << endl;
  }else if(hResult < kResult){
    cout << "kenjiro" << endl;
  }else if(hResult == kResult){
    cout << "even" << endl;
  }
}


Measured memory_bytes: 3104
#include<string>
#include <sstream>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

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

    pair<int, ll> q;
    pair<pair<int, ll>, int> p[m];
    for(int i = 0; i < m; i++){
        cin >> p[i].first.first >> p[i].first.second;
        p[i].second = i;
    }

    sort(p, p + m);

    string ans[m];
    ll cou = 0;
    ll now_number = 0;
    string now; 
    string zero;

    for(int i = 0; i < m; i++){
        if(i != 0 && now_number != p[i].first.first){
            cou = 0;
        }

        now = to_string(p[i].first.first);
        zero = "";
        //cout << "now_1 " << now << endl;
        if(now.length() <= 6){
            for(int i = 0; i < 6 - now.length(); i++){
                zero += "0";
            }
            now = zero + now;
        }
        //cout << "now_2 " << now << endl;
        cou += 1;
        now_number = p[i].first.first;
        if(cou <= 100000){
            zero = to_string(cou);
            int len = zero.length();
            for(int i = 0; i < 6 - len; i++){
                zero = "0" + zero;
            }
            now += zero;
        }

        ans[p[i].second] = now;
    }

    for(int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }


    /*for(int i = 0; i < m; i++){
        cout << p[i].first.first << " " << p[i].first.second << " " << p[i].second << endl;
    }*/
}

Measured memory_bytes: 9344
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define PB push


#define MOD 1000000007LL
#define EPS 1e-10

int main()
{
    char c;
    cin >> c;
    if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
    {
        cout << "vowel" << endl;
    }
    else
    {
        cout << "consonant" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b_1 = []
b_2 = []
b = []
for i in reversed(range(len(a))):
	if i % 2 != 0:
		b_1.append(a[i])
	else:
		b_2.append(a[i])
if len(a) % 2 == 0:
	b_2.reverse()
	b.extend(b_1)
	b.extend(b_2)
else:
	b_1.reverse()
	b.extend(b_2)
	b.extend(b_1)
for b_num in b:
	print(b_num, end = ' ')

Measured memory_bytes: 26180
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//難しすぎて何が何だかわからない・・・

//なんで通ったんだ
const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	int pn = 1;
	if (ci - cn + 16 > cm) {
		if ((ct = getcha()) == '-') { pn = -1; ct = getcha(); }
		A = ct - '0';
		while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';;
		return pn * A;
	}
	else {
		if ((ct = *ci++) == '-') { pn = -1; ct = *ci++; }
		A = ct - '0';
		while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';;
		return pn * A;
	}
}

ll XD[400000], tmp[400000];
void pakuri_sort(int N, ll A[]) {
	const int b = 9;
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint();
	int k = 0;
	const ll are = 1ll << 40;
	ll kazu = 0;
	rep(i, N) {
		ll x = getint() + 1000000000, d = getint();
		XD[k++] = kazu + x * 2 + 1;
		kazu += are;
		XD[k++] = kazu + (x + d) * 2;
		kazu += are;
	}

	pakuri_sort(N + N, XD);
	auto tmpN = tmp + N;
	k = 0;
	rep(i, N + N) {
		int j = XD[i] >> 41;
		if (XD[i] & 1) tmp[k++] = j;
		else tmpN[j] = k;
	}
	auto XDN = XD + N;
	XD[0] = (ll(N + 1) << 32) + N + 1;
	const ll ma = (1ll << 32) - 1;
	k = 0;
	for (int i = N - 1; i >= 0; i--) {
		int j = tmpN[tmp[i]];
		int mae = k;
		while ((XD[k] >> 32) <= j) k--;
		int kari = (mae == k ? j : max(int(XD[k + 1] & ma), j));
		XD[++k] = kari + (ll(i + 1) << 32);
		XDN[i] = kari;
	}

	const int mod = 998244353;
	rep(i, N + 1) tmp[i] = 0;
	tmp[0] = 1;
	rep(i, N) {
		tmp[i + 1] += tmp[i];
		tmp[XDN[i]] = (tmp[XDN[i]] + tmp[i]) % mod;
	}

	printf("%lld", tmp[N] % mod);

	Would you please return 0;
}

Measured memory_bytes: 6528
using System;
using System.Linq;

namespace ABC139
{
    class Program
    {
        static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            var H = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            var max = 0;
            var now = 0;
            for (int i = n - 1; i >= 1; i--)
            {
                if (H[i - 1] >= H[i]) now++;
                else now = 0;

                if (now > max) max = now;
            }
            Console.WriteLine(max);
        }
    }
}


Measured memory_bytes: 28124
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main(){
	
	LL n,k;
	cin >> n >> k;
	LL a[n];
	
	for( LL i = 0; i < n; i++)
		cin>>a[i];
	
	LL dp[n];
	dp[0] = 0;
	dp[1] = abs(a[1]-a[0]);
	
	for( LL i = 2; i < n; i++){
		dp[i] = INT_MAX;
		
		for(LL j = i-1 ; j >= (i-k) && j>=0; j--){
			dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));	
		}
		
	}
	cout<<dp[n-1]<<endl;
	return 0;
	
}

Measured memory_bytes: 1792
//		HYSO SERIOUS? WHY SO SERIOUS                            RIOUS? WHY SO SERIOUS? WHYSO SERIO
//		 ERIOUS? WHY SO SERIOUS ? WHY                          WHY SO SERIOUS? WHY SOSERIOUSWHYS
//		       OSERIOUS? WHY SO SERIOU         SERIOUS        ERIOUS? WHY SO SERIOUS? WHYS
//		          WHY SO SERIOUS? WHY SOSERIOUS? WHYSOSERIOUS? WHY SO SERIOUS?WHY SO SE
//		           ERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SOSERIO
//		           WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WH
//		            SERIOUS?WHYSO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHYSO SE
//		              ?WHYSOSERIOUS?WHY SO SERIOUS? WHY SO SERIOUS?WHYSO SERIOUS?
//		                           OSERIOUS? WHY SO SERIOUS?WHYSOSER
//		                                 HYSOSERIOUS?WHYSOSERI
//		                                     SOSERIOUS?W
//		                                         SER
//		                                          W


#include 	<ext/pb_ds/assoc_container.hpp> 
#include 	<ext/pb_ds/tree_policy.hpp> 
#include 	<iostream>
#include 	<queue>
#include 	<tuple>
#include 	<vector>
#include	<bits/stdc++.h>
#include	<algorithm>
#include 	<cmath>
#include 	<map>
#include 	<string>
#include 	<iomanip> 
using 		namespace __gnu_pbds; 
using 		namespace std;
#define 	ll  long long int
#define		read(a) long long int a; cin>>a;
#define 	readstr(s) string s; cin>>s;
#define 	readc(c) char c; cin>>c;
#define 	readarr(a,l) long long int a[l]={0}; for(ll i=0;i<l;i++) cin>>a[i];
#define 	loop(i,a,b) for(ll i=a;i<b;i++)
#define 	rloop(i,a,b) for(ll i=a;i>b;i--)
#define 	loopitr(vec) for(auto itr=vec.begin();itr!=vec.end();itr++)
#define 	ff first
#define 	ss second
#define 	readmtrx(i,j,a,b) ll arr[a][b]={0};for(ll i=0;i<a;i++)for(ll j=0;j<b;j++) cin>>arr[i][j];
#define 	v(pi) vector<ll>pi
#define 	all(a) a.begin(), a.end()
#define 	yes cout <<"YES"<<endl;
#define 	no cout <<"NO"<<endl;
#define 	sc(x) cout << (#x) << " is " << (x) << endl;
#define 	vp(pi) vector<pair<ll,ll>>pi
#define 	fast ios_base::sync_with_stdio(false);cin.tie(0);
#define 	pb(p) push_back(p)
#define 	mp make_pair
#define 	mi(lol) map<ll,ll>lol
#define 	fsort(vec) sort(vec.begin(),vec.end())
#define 	rsort(vec) sort(vec.begin(),vec.end(),compare)
#define 	Endl endl
#include 	<ctype.h>
#define 	ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define 	roundoff std::cout << std::setprecision(15)
#define 	inf 9223372036854775807
#define 	infn -9223372036854775807
#define 	pi 3.14159265358979323846
const 		int mod = 1e9+7; 
#define 	REVERSE(vec) reverse(vec.begin(),vec.end())
#define  	mx 1e9+5

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

//code start from here 

int main() {
	fast;
	read(a)
	read(b)
	vector<ll>dp(a,1e9+5);
	readarr(arr,a)
	dp[0]=0;
	loop(i,0,a){
		for(ll j=i+1;j<=i+b;j++){
			dp[j]=min(dp[j],dp[i]+abs(arr[i]-arr[j]));
		}
	}
	cout<<dp[a-1]<<endl;
	return 0;
}

//ends here s

Measured memory_bytes: 1792
n=int(input())
s=list(map(int,input().split()))
q=int(input())
t=list(map(int,input().split()))

counter=0
for x in t:
    low=0
    high=n-1
    while low<=high :
        mid=(low+high)//2 
        if x==s[mid]:
            counter+=1
            break
        if x<s[mid]:
            high=mid-1
        else :
            low=mid+1

print(counter)


Measured memory_bytes: 16708
#![allow(unused_imports)]
#![allow(non_snake_case, unused)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;

// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254

macro_rules! eprint {
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = write!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! eprintln {
	() => { eprintln!(""); };
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = writeln!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! dbg {
	($v:expr) => {{
		let val = $v;
		eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
		val
	}}
}

macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

macro_rules! ok {
	($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
		$a$([$i])*.$f($($t),*)
	};
	($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
		let t = $e;
		ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
	} };
}

pub fn readln() -> String {
	let mut line = String::new();
	::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
	line
}

macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

pub fn main() {
	let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

const MOD: usize = 1_000_000_007;
const INF: i64 = std::i64::MAX/2;

fn solve() {
    let (n,m) = read!(usize,usize);
    let h = read!([i64]);
    let ab = read!(usize,usize;m);
    let mut seen = vec![true;n];
    for (a,b) in ab {
        if h[a-1]<=h[b-1] {
            seen[a-1] = false;
        }
        if h[a-1]>=h[b-1] {
            seen[b-1] = false;
        }
    }
    println!("{}", seen.into_iter().filter(|&x| x).collect::<Vec<bool>>().len());
}

fn run() {
    solve();
}


Measured memory_bytes: 3960
import java.util.*;

public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        long div = n / (a + b);
        long mod = n % (a + b);
        System.out.println(div * a + Math.min(mod, a));
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 23764
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>

using namespace std;


int main(){

    long long n=0, k=0;
    string s;

    cin >> n >> s >> k;

    for(int i=0;i<n;i++){
        if(s[i] != s[k-1])s[i] = '*';
    }



    cout << s << endl;
/*    if(){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
*/
}


Measured memory_bytes: 256
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val vs = Seq.fill(n)(sc.nextInt).sorted

  val res = vs.sorted.tail.foldLeft(vs.sorted.head.toDouble){case (tmp, acc) =>
    (tmp + acc) / 2
  }



  println(res)


}


Measured memory_bytes: 27192
import heapq
def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = list(map(lambda x: x*(-1), a))

    heapq.heapify(a)
    cnt = 0
    while cnt < m:
        x = heapq.heappop(a)
        heapq.heappush(a, -(-x//2))
        cnt += 1
        if x == 0: break

    return sum(a)*(-1)

print(solve())

Measured memory_bytes: 20016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    vector<int> a(3);
    rep(i, 3)
    {
        cin >> a[i];
    }
    sort(ALL(a));

    cout << a[0] + a[1] << endl;
}

Measured memory_bytes: 256