akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = [int(v) for v in input().split()]
B = [int(v) for v in input().split()]

cnt = 0
for i in range(N + 1):
    if i > 0:
        if B[i - 1] > 0:
            v = min(A[i], B[i - 1])
            A[i] -= v
            cnt += v

    if i < N:
        v = min(A[i], B[i])
        A[i] -= v
        cnt += v
        B[i] -= v
print(cnt)


Measured memory_bytes: 19648
#include <stdio.h>

int main(){
	int W, H, x, y, r;
	
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	
	if(x >= r && x+r <= H && y >= r && y + r <= H){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second 
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define rep(i,a,b) for( ll i = a ; i < b ; i+=1 )
#define pp pair<ll,ll> 
#define sz(v) int(v.size())
#define hell (ll)1000000007
#define hell1 (ll)100000009
#define hell2 (ll)998244353
ll t = 1 ;
void solve()
{
    ll n ;
    map<string,ll> mapa ;
    cin >> n ;
    rep( i , 0 , n ){
        string s ;
        cin >> s ;
        sort(all(s));
        mapa[s]++;
    }
    ll ans = 0 ;
    for( auto u : mapa ){
        ans += (u.se*(u.se-1))/2 ;
    }
    cout << ans << "\n" ;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cin>>t ;
    while(t--){
        solve();
    }
    return 0 ;
}


Measured memory_bytes: 11264
import math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
N = int(input())
if N == 1:
  print(0)
  exit()
cnt = 0
insulist = factorization(N)
for i in range(len(insulist)):
  for j in range(1, insulist[i][1] + 1):
    if N % (insulist[i][0] ** j) == 0:
      N //= insulist[i][0] ** j
      cnt += 1
print(cnt)
    


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

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);   cout.tie(nullptr);
    if (ifstream("test.inp"))
    {
        freopen("test.inp", "r", stdin);
        #ifdef CHECKING
            freopen(taskname".out", "w", stdout);
        #else
            freopen("test.out", "w", stdout);
        #endif //CHECKING
    }
    else if (ifstream(taskname".inp"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }

    int n, D;   cin >> n >> D;
    vector<int> d(n), a(n), b(n + 1);
    for (int &i : d) cin >> i;

    if (d[0] / 2 >= D) a[0] = D;
    else a[0] = abs(D - d[0]);
    for (int i = 1; i < n; ++i)
        if (abs(a[i - 1] - d[i]) < a[i - 1]) a[i] = abs(a[i - 1] - d[i]);
        else a[i] = a[i - 1];

    b[n] = 1;
    for (int i = n - 1; i >= 0; --i)
        if (d[i] / 2 >= b[i + 1]) b[i] = b[i + 1];
        else b[i] = b[i + 1] + d[i];

    int Q;  cin >> Q;
    while (Q--)
    {
        int q;  cin >> q;
        if (q == 1)
        {
            if (D >= b[--q + 1]) cout << "YES\n";
            else cout << "NO\n";
            continue;
        }
        if (a[--q - 1] >= b[q + 1]) cout << "YES\n";
        else cout << "NO\n";
    }
}


Measured memory_bytes: 13696
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
c1, c2 = Counter(v[::2]), Counter(v[1::2])
mc1, mc2 = c1.most_common(2), c2.most_common(2)
mc1.append((0, 0))
mc2.append((0, 0))

print(n - (max(mc1[0][1] + mc2[1][1], mc1[1][1] + mc2[0][1]) if mc1[0][0] == mc2[0][0] else mc1[0][1] + mc2[0][1]))


Measured memory_bytes: 18656
#define _USE_MATH_DEFINES
#define llint long long
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n, c;
int d[32][32];
int cost[3][31];
int ans = 2000000000;

int main() {
    cin >> n >> c;
    for (int i = 1; i <= c; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> d[i][j];
        }
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= c; j++) {
            cost[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int co;
            cin >> co;
            for (int k = 1; k <= c; k++) {
                cost[(i + j) % 3][k] += d[co][k];
            }
        }
    }

    for (int i = 1; i <= c; i++) {
        for (int j = 1; j <= c; j++) {
            if (i == j) continue;
            for (int k = 1; k <= c; k++) {
                if (i == k || j == k) continue;
                ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main(){
    int n; cin >> n;
    int MX, ans;
    MX = ans = 0;
    for(int i = 0; i < n; i++){
        int curr;cin >> curr;
        MX = max(MX,curr);
        ans += (MX <= curr);
    }
    cout << ans << "\n";
    return 0;
}

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

using namespace std;

void __start__() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef MY
    freopen("/home/ainur/CLionProjects/wow/input.txt", "r", stdin);
    freopen("/home/ainur/CLionProjects/wow/output.txt", "w", stdout);
#else
    //freopen("search.in", "r", stdin);
   // freopen("search.out", "w", stdout);
#endif
}

#define sz(x) (int)x.size()
#define yes cout<<"Yes\n"
#define  no cout << "No\n"
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ft first
#define sd second
#define read(a) for(auto &qwqw:a)cin >> qwqw;
#define print(a) for(auto qwqw:a)cout<<qwqw<<' ';
#define print_plus(a) for(auto qwqw:a)cout<<qwqw+1<<' ';
//#define FOR(i, b, n) for(int i=b;i<n;i++) #define FOR(i, n) FOR(i, 0, n) #define FOR(n) FOR(i, 0, n)
mt19937_64 rnd(time(0));
#define int long long
using ll = long long;
using vi = vector<int>;
using ld = long double;
using vb = vector<bool>;
using pii = pair<int, int>;
using vd = vector<long double>;


int log2(int q) {
    int c = 0;
    while (q) {
        q >>= 1;
        c++;
    }
    return c;
}

void test_case() {
    int n, ans = 0;
    cin >> n;
    vi a(n);
    int u[1000001] = {};
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        u[a[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        bool ok = 1;
        for (int j = 1; j < sqrt(a[i]) + 2; ++j) {
            if (a[i] % j == 0) {
                if (u[j] > 1 || (u[j] == 1 && j != a[i])) {
                    ok = 0;
                    break;
                }
                if (u[a[i] / j] > 1 || (u[a[i] / j] == 1 && j != 1)) {
                    ok = 0;
                    break;
                }
            }
        }
        ans += ok;
    }
    cout << ans;

}

signed main() {
    __start__();
    int Q = 1;
    //cin >> Q;
    while (Q--) {
        test_case();
    }
}





Measured memory_bytes: 12708
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
  int n , c , k; 
  cin>>n>>c>>k;
  int a[n]; 
  for (int i = 0; i < n; i++) 
  {
    cin>>a[i];
  }
  sort(a, a + n);
  int x = 0 , y = 0;
  for ( int i = 0; i < n; i++) 
  {
    if ( a[x] + k < a[i]|| i - x + 1 > c ) 
    {
      x = i;
      y++;
    } 
  }
  cout<<y+1<<endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <math.h>
using namespace std;

#define MAX 1000000000

int manhattan(int *stx, int *sty, int *cpx, int *cpy);

int main(void){

    int n, m;
    scanf("%d%d", &n, &m);
    int stx[n],sty[n];
    int cpx[m], cpy[m];
    int i, j;
    int ans, min, dis;

    for (i = 0; i < n;i++){
        scanf("%d%d", &stx[i], &sty[i]);
    }
    for (i = 0; i < m; i++){
        scanf("%d%d", &cpx[i], &cpy[i]);
    }
    for (i = 0; i < n;i++){
        min = MAX;
        for (j = 0; j < m;j++){
            dis = manhattan(&stx[i], &sty[i], &cpx[j], &cpy[j]);
            if(min > dis){
                min = dis;
                ans = j + 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

int manhattan(int *stx, int *sty, int *cpx, int *cpy){
    int dis;
    dis = abs(*stx - *cpx) + abs(*sty - *cpy);
    return dis;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#include <iomanip>
#include <queue>
#include <string.h>
#include <bitset>

#define ll long long int
#define ld long double
#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 << endl
#define cosp(x) cout << x << " "
#define all(x) x.begin(),x.end()
#define allr(x) x.begin(),x.end(),greater<int>()
#define P pair<ll,ll>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1ll << 60
#define PI 3.14159265359

using namespace std;

int main(){

	ll n,a,b;
	cin >> n >> a >> b;

	ll ans = 0;

	ans = a*(n/(a+b));

	ans += min(n%(a+b),a);

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        s: chars,
    };
    println!("{}", s.iter().filter(|&&c| c == '1').count());
}


Measured memory_bytes: 4352
/*
[abc165] B - 1%
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
#define ALL(c) (c).begin(), (c).end()

ll X;

ll solve() {
    ll ans = 0;
    for (ll a = 100; a < X; a += a / 100) {
        ans++;
    }

    return ans;
}

int main() {
    cin >> X;

    cout << solve() << endl;

    return 0;
}


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

namespace ConsoleApp11
{
    class Class38
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            Dictionary<string, int> Table = new Dictionary<string, int>();
            for(int i = 1; i <= N; i++)
            {
                string[] read = Console.ReadLine().Split();
                Table.Add(read[0], int.Parse(read[1]));
            }
            string X = Console.ReadLine();
            int ans = 0;
            bool check = false;
            foreach(string s in Table.Keys)
            {
                if (s == X)
                {
                    check = true;

                }
                else if (check)
                    ans += Table[s];
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13152
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
map<int,int64_t> p;
//O(√n)
//素因数分解
void fl(int64_t n){
    if(n==1){
        return ;
    }
    int tmp = n;
    while(tmp%2==0 ){
        tmp /= 2;
        p[2]++;
    }
    for(int i=3;i*i<=tmp;i++){
        while(tmp % i ==0){
            tmp /= i;
            p[i]++;
        }
    }
    if(tmp!=1){//まだ割り切れてない場合、√Nまでは見てるから
        p[tmp]++;
    }
}
int main(){
    int n;
    cin>>n;
    if(n<=9){
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        fl(i);
    }
    int s=p.size();
    int p75,p3,p25,p5,p15;
    p75=0;
    p3=0;
    p25=0;
    p5=0;
    p15=0;
    for(auto c:p){
        //cout<<c.first<<" "<<c.second<<endl;
        int sh = c.second;//肩
        if(sh>=74){
            p75++;
        }
        if(sh>=24){
            p25++;
        }
        if(sh>=14){
            p15++;
        }
        if(sh>=4){
            p5++;
        }
        if(sh>=2){
            p3++;
        }
    }
    //cout<<p75<<" "<<p25<<" "<<p15<<" "<<p5<<" "<<p3<<endl;
    cout<<p75+p25*(p3-1)+(p5-1)*p15+(p3-2)*p5*(p5-1)/2<<endl;
    //約数75個 => x^74,x^24*y^2, x^4*y^14, x^2*y^4*z^4の場合 
}

Measured memory_bytes: 256
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  cout << (d2 == 1ll) << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3648
#[derive(Debug)]
struct ParseStdinError;
impl std::error::Error for ParseStdinError {}
impl std::fmt::Display for ParseStdinError {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(formatter, "parse stdin error")
    }
}

macro_rules! input {
    () => {{
        use std::io::*;
        let mut buffer = String::new();
        stdin().lock().read_to_string(&mut buffer)?;
        buffer
    }
    .lines()
    .next()
    .ok_or(ParseStdinError)?
    .split(' ')
    .next()
    .ok_or(ParseStdinError)?};
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut f = 0;
    let input = input!().parse::<i64>()?;
    for v in 1..=input {
        if v % 3 != 0 && v % 5 != 0 {
            f += v
        }
    }
    println!("{}", f);
    Ok(())
}


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

int main()
{
    int N,M; cin>>N>>M;
    vector<vector<int>> v(100005);
    for(int i=0;i<N;i++){
        int a,b; cin>>a>>b;
        v[a].push_back(b);
    }

    int ans=0;
    priority_queue<int> Q;
    for(int i=1;i<=M;i++){
        for(int x:v[i]) Q.push(x);
        if(!Q.empty()){
            ans+=Q.top(); Q.pop();
        }
    }
    cout<<ans<<endl;

    return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    string s;
    cin >> s;

    int cnt = 0;
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] == '0') ++cnt;
    }
    cout << min(cnt, int(s.size()) - cnt) * 2 << endl;

    return 0;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int n,m,temp,sum=0;
int main()
{
	cin>>n>>m;
  	for(int i=0;i<m;i++)
    {
      cin>>temp;
      sum+=temp;
    }
  	if(sum>n)
      cout<<"-1";
  	else
      cout<<n-sum;
}


Measured memory_bytes: 3636
package main

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

func main() {
	sc := NewScanner()
	_ = sc.NextInt()
	A, B := sc.NextInt(), sc.NextInt()
	P := sc.NextIntArray()
	box1 := 0
	box2 := 0
	box3 := 0

	for _, v := range P {
		if v <= A {
			box1++
		} else if A < v && v <= B {
			box2++
		} else {
			box3++
		}
	}
	fmt.Println(minA(box1, box2, box3))
}
func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func minA(arg ...int) int {
	var s = arg[0]
	for _, v := range arg {
		s = min(s, v)
	}
	return s
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>
#include <stack>
#include <deque>
#define pb push_back
#define make make_pair
#define kaku(a) cout << a << endl
#define isort(a) sort(a.begin(),a.end())
 
using namespace std;
 
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define PI 3.14159265359
long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}
long long lcm(long long a,long long b){ return a/gcd(a,b)*b;}
 
typedef pair<ll,ll> Pair;
const ll inf =1000000007;

void solve(){
    ll n,m;
    cin >> n >>m;
    ll ans=0;
    ans+=(n-2)*(m-2);
  if(ans<0) ans=0;
    if(n==1 || m==1){
        ans+=max(n-2,m-2);
    }
    if(n==1 && m==1) ans=1;
    kaku(ans);
}

int main(){
    solve();
}




//




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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, T;
long long dp[3010][3010];

int main() {
    cin >> N >> T;
    vector<pair<int, int>> ab;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        ab.push_back({a, b});
    }
    sort(ab.begin(), ab.end());
    for (int i = 0; i < N; ++i) {
        int a = ab[i].first;
        int b = ab[i].second;
        for (int j = 0; j < T; ++j) {
            chmax(dp[i + 1][j], dp[i][j]);
            if (j + a <= T) {
              chmax(dp[i + 1][j + a], dp[i][j] + b);
            }
        }
    }

    long long res = 0;
    for (int i = 1; i <= N; ++i) {
        long long value = dp[i - 1][T - 1] + ab[i - 1].second;
        if (value > res) res = value;
    }
    cout << res << endl;
}

Measured memory_bytes: 70912
#include<stdio.h>

int data[1023];

int query(int a,int b,int k,int l,int r){
	if(r<=a || l>=b)return 0;
	if(a<=l && r<=b)return data[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2,r);
		return vl+vr;
	}
}

int main(){
	int N,M,Q;
	int i;
	scanf("%d %d %d",&N,&M,&Q);
	int L[M+Q],R[M+Q],q[M+Q],ans[Q];
	for(i=0;i<M;i++){
		scanf("%d %d",&L[i],&R[i]);
		R[i]++;
		q[i]=0;
	}
	for(;i<M+Q;i++){
		scanf("%d %d",&L[i],&R[i]);
		R[i]++;
		q[i]=i-M+1;
	}
	
	//sort
	int h=M+Q;
	int swapped=0;
	while(h>1 || swapped==1){
		if(h>1)h=(h*10)/13;
		swapped=0;
		for(int j=0;j<M+Q-h;j++){
			if(R[j]>R[j+h] || (R[j]==R[j+h] && q[j]>q[j+h])){
				int temp=R[j];
				R[j]=R[j+h];
				R[j+h]=temp;
				temp=L[j];
				L[j]=L[j+h];
				L[j+h]=temp;
				temp=q[j];
				q[j]=q[j+h];
				q[j+h]=temp;
				swapped=1;
			}
		}
	}
	
	for(i=0;i<M+Q;i++){
		if(q[i]==0){
			int l=511+L[i];
			while(1){
				data[l]++;
				if(l==0)break;
				l=(l-1)/2;
			}
		}
		else{
			ans[q[i]-1]=query(L[i],R[i],0,0,512);
		}
	}
	
	for(i=0;i<Q;i++)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 4736
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=(a);i<=(b);++i)
#define rep(i,n) rep2(i,0,n)

using namespace std;

ll int a[2100]={};
ll int dp[2100][2];
int n;
void go(){
    int i=1;
    while(i<=n){
        ll int max=-1,min=1e9+1;
        rep2(j,1,i-1){
            if(max<dp[j][0]) max=dp[j][0];
            if(min>dp[j][1]) min=dp[j][1];
        }
        if(max<abs(a[i]-a[0])) max=abs(a[i]-a[0]);
        if(min>abs(a[i]-a[0])) min=abs(a[i]-a[0]);
        dp[i][1]=max;
        dp[i][0]=min;
        i++;
    }
    
}

main(){
    ll int z,w;
    cin>>n>>z>>w;
    rep(i,n) cin>>a[n-1-i];
    a[n]=w;
    go();
    cout<<dp[n][1];
    return 0;
}

Measured memory_bytes: 256
import           Control.Monad
import qualified Control.Monad.ST            as ST
import qualified Data.ByteString.Char8       as BS
import           Data.List
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
getInt = readInt <$> BS.getLine

primes n = ST.runST $ do
  v <- VM.new (n+1)
  VM.write v 0 0
  VM.write v 1 0
  forM_ [2..n] $ \i -> VM.write v i i
  let sqrtN = ceiling $ sqrt $ fromIntegral n
  forM_ [2..sqrtN] $ \i -> do
    x <- VM.read v i
    when (x > 0) (forM_ [2..(n`div`i)] $ \j -> VM.write v (i*j) 0)
  v' <- V.freeze v
  return $ V.filter (> 0) v'

main = do
  x <- getInt
  print $ V.head $ V.dropWhile (< x) $ primes 100003

Measured memory_bytes: 2172
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	char b;
	cin >> b;
	if (b == 'A')cout << 'T' << endl;
	else if (b == 'T')cout << 'A' << endl;
	else if (b == 'G')cout << 'C' << endl;
	else cout << 'G' << endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.*;

public class Main {


    public void solve() throws IOException {
        int n = nextInt();
        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        int res = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || a[i] == a[i - 1]) cnt++;
            else {
                res += cnt / 2;
                cnt = 1;
            }
        }
        out.print(res + cnt / 2);
    }

    BufferedReader br;
    StringTokenizer sc;
    PrintWriter out;

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        new Main().run();
    }

    public void run() throws IOException {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    public String nextToken() throws IOException {
        while (sc == null || !sc.hasMoreTokens()) {
            try {
                sc = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return sc.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
}

Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5+7;

ll p(ll x){
    return (x*(x-1)/2);
}

int main(){
    ll n, m;
    cin >> n >>m;
    cout << p(n) + p(m);
}
/*
100 100

*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const long long INF=1e18,MOD=1e9+7;
#define MAX_V 100010
int main(){
	ll r,d,x;
	cin>>r>>d>>x;
	for(int i=0;i<10;i++){
		x=r*x-d;
		cout<<x<<endl;
	}

}

Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())
x3 = x2 + y1 - y2
y3 = y2 + x2 - x1
x4 = x1 + y1 - y2
y4 = y1 + x2 - x1
print(x3, y3, x4, y4)

Measured memory_bytes: 2940
#include <stdio.h>

int tillnextyear(int year, int month, int day)	{
	
	int res = 0;
	
	if (year % 3 == 0)	{
		
		res += 21 - day;
		month ++;
		
		for (; month <= 10; month++)	{
			res += 20;
		}
		
		return res;
	} else	{
	  
	  if (month % 2 == 0) {
	    res += 20 - day;
	    month++;
	  } else  {
	    res += 21 - day;
	    month++;
	  }
	  
	  for(; month <= 10; month++) {
	    
	    if (month % 2 == 0) {
	      res += 19;
	    } else  {
	      res += 20;
	    }
	  }
	  
	  return res;
	}
}
		
int main(void)	{
	
  int n, y, m, d, res;
  
  scanf("%d", &n);
  
  for (int i = 1; i <= n; i++)  {
    
    res = 0;
    
    scanf("%d %d %d", &y, &m, &d);
    
    res += tillnextyear(y, m, d);
    y++;
    
    for (; y <= 999; y++) {
      
      if (y % 3 == 0) {
        res += 200;
      } else  {
        res += 195;
      }
    }
    
    printf("%d\n", res);
  }
    
	return 0;
}


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

int main() {
    int n,m;
    cin>>n>>m;
    int a[m],sum=0;
    for(int i=0;i<m;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum>n){
        cout<<"-1"<<endl;
    }
    else cout <<n-sum<<endl;
    return 0;

}

Measured memory_bytes: 3632
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int w = sc.nextInt();
		int h = sc.nextInt();
		long[] p = new long[w];
		long[] q = new long[h];
		long[] psum = new long[w];
		long ans = 0;
		for(int i=0; i<w; i++){
			p[i] = sc.nextLong();
			ans += p[i];
		}
		for(int i=0; i<h; i++){
			q[i] = sc.nextLong();
			ans += q[i];
		}
		sc.close();
		
		Arrays.sort(p);
		long sum = 0;
		for(int i=0; i<w; i++){
			sum += p[i];
			psum[i] = sum;
		}
		
		for(int i=0; i<h; i++){
			int result = Arrays.binarySearch(p, q[i]) + 1;
			int pos = (result >= 0) ? result : -result;
			ans += (w-pos) * q[i];
			if(pos != 0){
				ans += psum[pos-1];
			}
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 76760
#include <iostream>

#define int long long

using namespace std;

const int N = 2e5 + 10;

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    
    string s;
    cin >> s;
    if (s == "ABC") cout << "ARC";
    else cout << "ABC";
    return 0;
}


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

int main()
{
	int i;
	unsigned long takahasi, aoki, a, b, k;
	scanf("%lu%lu%lu", &takahasi, &aoki, &k);
	a = takahasi;
	b = aoki;
	if (k <= a) {
		takahasi = a-k;
		aoki = aoki;
	}
	else if (k <= a+b) {
		takahasi = 0;
		aoki = b-(k-a);
	}
	else {
		takahasi = 0;
		aoki = 0;
	}
	printf("%lu %lu", takahasi, aoki);
	return 0;
}

Measured memory_bytes: 128
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int count=0;
  int N;
  cin >> N;
  vector<int> p(N);
  REP(i,N) cin >> p[i];
  REP(i,N) if(p[i]!=i+1) ++count;
  if(count==0||count==2) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed_=(b);i<=_ed_;++i)
#define DREP(i,a,b) for(int i=(a),_ed_=(b);i>=_ed_;--i)
#define pb push_back
#define mp make_pair
#define sz(x) (int)((x).size())
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int P=1000000007;
void inc(int& x,int y){x=x+y<P?x+y:x+y-P;}

int h,n,p[600005],ans;

int tr[600005];
void insert(int x,int w){while(x)w=1ll*w*x%P,inc(tr[x],w),x>>=1;}
void del(int x){while(x)tr[x]=0,x>>=1;}
int query(int x,int w){
    int res=0,ans=0;
    while(x){
	int t=(P+tr[x]-1ll*res*x%P)%P;
	inc(ans,1ll*t*w%P);
	res=tr[x],w=1ll*w*x%P,x>>=1;
    }
    return ans;
}

vector<pii> dfs(int u){
    vector<pii> L,R;
    if(u>n+n-1)return L;
    L=dfs(u<<1),R=dfs(u<<1|1);
    for(pii nw:L)insert(p[nw.first],1ll*nw.second*u%P);
    for(pii nw:R)inc(ans,query(p[nw.first],nw.second));
    for(pii nw:L)del(p[nw.first]);
    L.insert(L.end(),R.begin(),R.end());
    REP(i,0,sz(L)-1)L[i].second=1ll*L[i].second*u%P;
    if(!sz(L))L.pb(mp(u,u));
    return L;
}

int main(){
    //freopen("in.in","r",stdin);
    h=read();n=1<<(h-1);
    REP(i,n,n+n-1)p[i]=n+read()-1;
    dfs(1);
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 6780
#include<bits/stdc++.h>
#include <chrono>
using namespace std::chrono;
using namespace std;
#define fr(x,i,n) for(int x = i; x < n; ++x)
#define fb(x,i,n) for(int x = i; x >= n; --x)
#define pr pair<int,int>
#define ll long long int
const int mod=1e9+7;
/*    auto start = high_resolution_clock::now();
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "\nduration="<<duration.cnt()/1e6 << endl;
*/
long double pi= (long double)6.28318530717958623200;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    int a[m],sum=0;
    fr(i,0,m){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum>n)
    cout<<-1;
    else
    cout<<n-sum;
}


Measured memory_bytes: 3696
N = int(input())
T,A = map(int, input().split())
H_list = map(int, input().split())

H_list1 = []
for i,h in enumerate(H_list):
    H_list1 = H_list1 + [abs(A-(T - h*0.006)),]
print(H_list1.index(min(H_list1))+1)

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

#define PB push_back
#define LL long long
#define vi vector<int>
#define pii pair<int,int>
#define MP make_pair
#define pll pair<LL,LL>
using namespace std;

const int Maxn=110;
const int Maxv=1110;
int g[Maxn][Maxn],n,m,l;
int vis[Maxv],match[Maxv];
int head[Maxv],tot;
const int Inf=1e9+7;
struct Edge{
    int to,next;
}edge[Maxv*Maxv*2];

void init()
{
    memset(head,-1,sizeof(head));
    for(int i=0;i<Maxn;i++)
        for(int j=0;j<Maxn;j++)
            g[i][j]=i==j?0:Inf;
    tot=0;
}

void add_edge(int u,int v)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

void Floyed()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
}

bool dfs(int u,int tar)
{
    for(int i=head[u];~i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==tar)
            continue;
        vis[v]=tar;
        if(match[v]==-1||dfs(match[v],tar))
        {
            match[v]=u;
            return true;
        }
    }
    return false;
}

int hungary()
{
    int ret=0;
    memset(match,-1,sizeof(match));
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<l;i++)
    {
        ret+=dfs(i,i);
    }
    return ret;
}

pii op[Maxv];

bool cmp(pii a,pii b)
{
    return a.second<b.second;
}

int main()
{
    while(scanf("%d %d %d",&n,&m,&l),n||m||l)
    {
        init();
        while(m--)
        {
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            g[u][v]=g[v][u]=min(g[u][v],w);
        }
        Floyed();
        for(int i=0;i<l;i++)
        {
            int p,t;
            scanf("%d %d",&p,&t);
            op[i]=MP(p,t);
        }
        for(int i=0;i<l;i++)
        {
            for(int j=0;j<l;j++)
            {
                int p1=op[i].first,p2=op[j].first;
                int d=g[p1][p2];
                if(i==j)
                    continue;
                if(d==0&&op[i].second==op[j].second)
                    continue;
                if(op[i].second+d<=op[j].second)
                    add_edge(i,j);
            }
        }
        printf("%d\n",l-hungary());
    }
    return 0;
}

Measured memory_bytes: 5356
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int P = 1e9+7;
#define fr(i,low,up,st) for(register int i = low;i <= up;i += st)
#define nfr(i,low,up,st) for(register int i = low;i >= up;i -= st)
#define clr(a) memset(a,0,sizeof a)
#define SZ(a) (a.size())

int n,m,k;
char ch[N];
int a[N];
int cnt;
int ans = 1;
int bc = 0,wc = 0;
int main(){
   scanf("%d",&n);
   scanf("%s",ch+1);
   fr(i,1,2*n,1){
      if(i%2 == 1 && ch[i] == 'B')a[i] = 1,++bc;
      else if(i%2 == 0 && ch[i] == 'W')a[i] = 1,++wc;
      else if(i%2 == 0 && ch[i] == 'B')a[i] = -1,--bc;
      else a[i] = -1,--wc;
      if(bc < 0 || wc < 0){
         puts("0");
         return 0;
      }
   }
   if(bc || wc){
      puts("0");
      return 0;
   }
   fr(i,1,2*n,1){
      cnt += a[i];
      if(cnt < 0){
         puts("0"); return 0;
      }
      if(a[i] == -1)ans = 1LL*ans*(cnt+1)%P;
   }
   if(cnt != 0)puts("0");
   fr(i,1,n,1){
      ans = 1LL*ans*i%P;
   }
   printf("%d\n",ans);
   return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define cs ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
int main(){
    cs;
    int a=0,b=0;
    string s;
    cin>>s;
    rep(i,s.size()) {
        if(i&1){
            if(s[i]-'0') a++;
            else b++;
        }
        else {
            if(s[i]-'0') b++;
            else a++;
        }
    }
    //a=10101010... b=01010101...
    cout<<min(a,b);
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n;
	int ret=0;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		if(i%2 && x%2){
			ret++;
		}
	}
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using  namespace std;
int main()
{
    int a;
    cin>>a;
    int arr[a];
    for(int i=0;i<a;i++)
    {
        cin>>arr[i];
    }
    int sum=0;
    for(int i=0;i<a;i++)
    {
        for(int j=i+1;j<a;j++)
        {
            sum=sum+arr[i]*arr[j];
        }
    }
    cout<<sum<<endl;
}

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

int main(){
  int N, A, i;
  
  cin >> N;
  for (i = 0; i < N; i++) {
    cin >> A;
    if (A % 2 == 0 && A % 3 != 0 && A % 5 != 0) {
      cout << "DENIED" << endl;
      return 0;
    }
  }
  
  cout << "APPROVED" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <climits>
#include <sstream>
#include <array>
#include <tuple>
#include <set>
#include <iterator>
#include <cstdio>
#include <string>
#include <stack>
#include <valarray>
#include <utility>
#include <iomanip>
#include <list>
#include <numeric>
#include <regex>
#include <map>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll          long long
#define PI          3.1415926535
#define pb          push_back
#define ins         insert
#define INF         LLONG_MAX
#define mk          make_pair
#define lb(v,x)     lower_bound(all(v),x)
#define ub(v,x)     upper_bound(all(v),x)
#define ff          first
#define ss          second
#define rev         reverse
#define uset        unordered_set
#define umap        unordered_map
#define endl        "\n"
#define max3(x,y,z)  max(x,max(y,z))
#define min3(x,y,z)  min(x,min(y,z))
#define sz(a)       (ll)a.size()
#define double      long double
#define minpq       priority_queue <ll,vector<ll>,greater<ll> > 
#define fill(x,y)   memset(x,y,sizeof(x))
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define MOD         1000000007 //1e9+7
#define bp(n)       __builtin_popcountll(n)
#define mxt(a)      *(max_element(a.begin(),a.end()))
#define mnt(a)      *(min_element(a.begin(),a.end())
#define unique_sort(c) (sort(all(c)), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define rep(i, a, b) for(ll i = (a); i<= (b); ++i)
#define trav(a, x) 	 for(auto &a : x)
#define re(i,n)      for(ll i = 0; i < n; ++i) 
const ll N = 4e5 + 7;
typedef pair<ll,ll>   pii;
typedef vector<pii>   vpii;
typedef vector<ll>    vll;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
ll power(ll x,ll y){ll res=1;x=x;while(y>0){if(y&1)res=(res*x);y=y>>1;x=(x*x);}return res;}
template<typename T> T gcd(T a,T b){ if(a==0) return b; return gcd(b%a,a); }
template<typename T> T powm(T a,T b, ll m){T cnt=1; while(b>0){ if(b%2==1) cnt=(cnt*a)%m; b/=2; a=(a*a)%m; }return cnt%m;}
ll ncr(ll n,ll r){ll res=1;if(r>n)return 0;if(r>n-r)r=n-r;for(ll i=0;i<r;i++){res*=(n-i);res/=(i+1);}return res;}
ll sqr(ll x) { return x * x;}
// always use 1ll*ans to avoid signed integer overflow; 
void prec(){

}

void solve(){
	ll int n,k;cin>>n>>k;
	ll int h[n+10],dp[n+10];
	rep(i,1,n) cin>>h[i];
	rep(i,1,n) dp[i]=INF;
	dp[0]=0,dp[1]=0;
	rep(i,1,n){
		for(ll j=i+1; j<=i+k; ++j) if(j<=n) dp[j]=min(dp[j],abs(h[j]-h[i])+dp[i]);
	}
	cout<<dp[n]<<endl;
}

int main()
{
    ios;
    int tc=1;
    //cin>>tc;
    prec();
    while(tc--)
    	solve();
    return 0; 
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;
int sum[401][401];
long long value[401][401];

int main(){

    int N, C;
    cin >> N >> C;
    vector<int> A(N);
    vector<int> B(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int j = 0; j < N; j++){
        cin >> B[j];
    }

    for(int i = 0; i <= 400; i++){
        sum[i][0] = 0;
        for(int j = 1; j <= 400; j++){
            long long temp = 1;
            for(int k = 0; k < i; k++){
                temp = (temp * j) % MOD;
            }
            sum[i][j] = (sum[i][j - 1] + temp) % MOD;
        }
    }

    value[0][0] = 1;
    for(int i = 1; i <= C; i++){
        value[0][i] = 0;
    }

    for(int i = 1; i <= N; i++){
        int a = A[i - 1];
        int b = B[i - 1];
        for(int j = 0; j <= C; j++){
            long long plus = 0;
            for(int k = 0; k <= j; k++){
                int diff = j - k;
                long long plusValue = (sum[diff][b] - sum[diff][a - 1] + MOD) % MOD;
                long long tempPlus = (value[i - 1][k] * plusValue) % MOD;
                plus = (plus + tempPlus) % MOD;
            }
            value[i][j] = plus;
        }
    }

    cout << value[N][C] << endl;

    return 0;
}

Measured memory_bytes: 2176
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


class point_t {
public:
  bool operator<(const point_t& p) const {
    if (x == p.x)
      return y < p.y;

    return x < p.x;
  };
                                          
public:
  int x;
  int y;
};


class bipartite_matching_fn_t {
public:
  bipartite_matching_fn_t(int N) : N_(N), G_(N) {
    match_ = new int [N_];
    used_ =  new bool[N_];
  };

  ~bipartite_matching_fn_t() {
    delete[] match_;
    delete[] used_;
  };

public:
  void add_edge(int u, int v) {
    G_[u].push_back(v);
    G_[v].push_back(u);
  };

private:
  bool dfs(int v) {
    used_[v] = true;

    for (int i = 0, size = G_[v].size(); i < size; i ++) {
      int u = G_[v][i], w = match_[u];

      if (w < 0 || (! used_[w] && dfs(w))) {
        match_[v] = u;
        match_[u] = v;

        return true;
      }
    }

    return false;
  };

public:
  int match() {
    int c = 0;

    memset(match_, -1, sizeof(int) * N_);

    for (int v = 0; v < N_; v ++) {
      if (match_[v] < 0) {
        memset(used_, 0, sizeof(bool) * N_);

        if (dfs(v))
          c ++;
      }
    }
    
    return c;
  };

private:
  int N_;
  
  std::vector<std::vector<int>> G_;

  int* match_;

  bool* used_;
};


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int N, c = 0;

  std::cin >> N;

  std::vector<point_t> reds(N), blues(N);

  for (auto& p : reds)
    std::cin >> p.x >> p.y;

  for (auto& p : blues)
    std::cin >> p.x >> p.y;

  std::sort(ALL(reds));
  std::sort(ALL(blues));

  bipartite_matching_fn_t fn(N + N);

  for (int i = 0; i < N; i ++) {
    const auto& p = reds[i];
    
    for (int j = 0; j < N; j ++) {
      const auto& q = blues[j];

      if (p.x < q.x && p.y < q.y)
        fn.add_edge(i, j + N);
    }
  }

  std::cout << fn.match() << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 10020;
int a[MAX];
int x[12] = {0,1,0,2,1,2,0,3,1,3,2,3};
int y[12] = {1,0,2,0,2,1,3,0,3,1,3,2};
long pow(int n){
  if(n <= 0)
    return 1;
  else
    return 10 * pow(n-1);
}
int digit(int a){
  int cnt = 0;
  while(a > 0){
    a /= 10;
    cnt++;
  }
  return cnt;
}
long stick(int a, int b){
  return a * pow(digit(b)) + b;
}
void solve(int n){
  sort(a,a+n);
  long min1,min2,ans;
  min1 = stick(a[x[0]],a[y[0]]);
  min2 = stick(a[x[1]],a[y[1]]);
  ans = stick(a[x[2]],a[y[2]]);
  if(min1 > min2){
    long tmp = min1;
    min1 = min2;
    min2 = tmp;
  }
  if(ans < min1){
    long tmp = min1;
    min1 = ans;
    ans = min2;
    min2 = tmp;
  }
  else if(ans < min2){
    long tmp = ans;
    ans = min2;
    min2 = tmp;
  }
  if(n == 3){
    for(int i = 3 ; i < 6 ; i++){
      long z = stick(a[x[i]],a[y[i]]);
      if(z < min1){
        ans = min2;
        min2 = min1;
        min1 = z;
      }
      else if(z < min2){
        ans = min2;
        min2 = z;
      }
      else if(z < ans){
        ans = z;
      }
    }
  }
  else{
    for(int i = 3 ; i < 12 ; i++){
      long z = stick(a[x[i]],a[y[i]]);
      if(z < min1){
        ans = min2;
        min2 = min1;
        min1 = z;
      }
      else if(z < min2){
        ans = min2;
        min2 = z;
      }
      else if(z < ans){
        ans = z;
      }
    }
  }
  printf("%ld\n",ans);
}
int main(){
  int n;
  scanf("%d",&n);
  for(int i = 0 ; i < n ; i++)
    scanf("%d",a+i);
  solve(n);
}



Measured memory_bytes: 2836
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    ll a,b,count=1,x=0;
    cin >> a >> b;
    ll c = __gcd(a,b);
    ll d = c;
    while(d>1){
        for(ll i=2;i<sqrt(d)+3;i++){
            if(d%i==0){
                while(d%i==0)d/=i;
                count++;
                break;
            }
            int y = sqrt(d);
          	if(i==y+2){
              x=1;
              break;
        }
      }
      if(x==1){
        count++;
        break;
      }
    }
    cout << count << endl;
}

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

int main() {
    string S, T; cin >> S >> T;
    int A, B; cin >> A >> B;
    string U; cin >> U;
    if (U == S) {
        cout << A-1 << ' ' << B << endl;
    } else {
        cout << A << ' ' << B-1 << endl;
    }
}


Measured memory_bytes: 256