akhauriyash/Code-Regression huggingface dataset:
//https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b
//B - K個のケーキ / K Cakes
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
    ll K, T; cin>>K>>T;
    vector<pair<ll,ll>> at(T+1); //数,index
    FOR(i,1,T+1){
        cin>>at.at(i).first;
        at.at(i).second=i;
    }
    priority_queue<pair<ll,ll>> que;
    FOR(i,1,T+1){
        que.push(at.at(i));
    }

    ll ans=0;
    ll prev=-1;
    REP(i,K){
        auto a=que.top();
        que.pop();
        if(prev!=a.second){
            a.first-=1;
            prev=a.second;
            ++ans;
        }else{
            if(!que.empty()){
                auto b=que.top();
                que.pop();
                if(prev!=b.second){
                    b.first-=1;
                    prev=b.second;
                    ++ans;
                }
                if(b.first>0)que.push(b);
            }
        }
        if(a.first>0)que.push(a);
    }
    cout<<K-ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18+1;
const ll DIV = 1000000007;
//#define TEST
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long N;
    cin >> N;
    vector<ll> a(N);
    bool times = true;
    ll times4=0;
    ll times2=0;
    ll other=0;
    for(size_t i=0;i<N; i++)
    {
        cin >> a[i];
        if(a[i] % 4 == 0) times4++;
        else if(a[i] % 2 == 0) times2++;
        else other++;
    }
    //cerr << times4 << ":" << times2 << ":" << other << endl;
    if(other>0)
    {
        if(other+times2%2 <= times4+1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else cout << "Yes" << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

Measured memory_bytes: 3968
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int n,m;
vector<int>g[N];
int dis[N],pre[N];
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n>>m;
	rep(i,1,m){
		int a,b;
		cin>>a>>b;
		g[a].pb(b);g[b].pb(a);
	}
	queue<int>q;
	q.push(1);
	rep(i,1,n) dis[i]=inf;
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int x:g[u]){
			int cost=dis[u]+1;
			if(cost<dis[x]){
				dis[x]=cost;
				pre[x]=u;
				q.push(x);
			}
		}
	}
	for(int i=2;i<=n;i++) if(dis[i]==inf){
		puts("No");
		return 0;
	}
	puts("Yes");
	rep(i,2,n) cout<<pre[i]<<endl;
	return 0;
}

Measured memory_bytes: 10812
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 505;
ll A[MAX_N];
vector<ll> d;

int main()
{
	ll N,K;
	cin >> N >> K;
	ll sum = 0;
	rep(i,N)
	{
		cin >> A[i];
		sum += A[i];
	}
	for (int i = 1; i*i <= sum; ++i)
	{
		if (sum % i == 0)
		{
			d.push_back(i);
			d.push_back(sum/i);
		}
	}
	sort(d.begin(), d.end());
	reverse(d.begin(), d.end());
	rep(i,d.size())
	{
		ll D = d[i];
		vector<ll> B;
		ll sum2 = 0;
		rep(j,N)
		{
			B.push_back(A[j] % D);
			sum2 += A[j] % D;
		}
		sort(B.begin(), B.end());
		reverse(B.begin(), B.end());
		ll res = 0;
		for (int j = sum2 / D; j < N; ++j)
		{
			res += B[j];
		}
		if (res <= K)
		{
			cout << D << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;


map<vector<int>,int> dp;
//状態を渡すとそこから遷移する状態を作成して返す
vector<vector<int> > next(vector<int> pre) {
    vector<vector<int> > res;
    int zero = pre[0];
    if (zero != 1 && zero!= 5) {
        vector<int> tmp = pre;
        swap(tmp[zero],tmp[zero-1]);
        tmp[0] = zero - 1;
        res.push_back(tmp);
    }
    if(zero!=4&&zero!=8) {
        vector<int> tmp = pre;
        swap(tmp[zero],tmp[zero+1]);
        tmp[0] = zero+1;
        res.push_back(tmp);
    }
    if (zero > 4) {
        vector<int> tmp = pre;
        swap(tmp[zero],tmp[zero-4]);
        tmp[0] = zero - 4;
        res.push_back(tmp);
    } else {
        vector<int> tmp = pre;
        swap(tmp[zero],tmp[zero+4]);
        tmp[0] = zero+4;
        res.push_back(tmp);
    }
    return res;
}

void init() {
    vector<int> s = {1,0,1,2,3,4,5,6,7};
    queue<vector<int> > q;
    dp.clear();
    dp[s] = 0;
    q.push(s);
    while(!q.empty()) {
        vector<int> tmp = q.front(); q.pop();
        vector<vector<int> > n = next(tmp);
        for (int i = 0; i < n.size(); i++) {
            if (dp.count(n[i]) == 0) {
                dp[n[i]] = dp[tmp] + 1;
                q.push(n[i]);
            }
        }
    }
}

int main() {
    init();
    vector<int> in(9);
    //各クエリに対する応答
    while(cin>>in[1]>>in[2]>>in[3]>>in[4]>>in[5]>>in[6]>>in[7]>>in[8]) {
        for (int i = 1; i < in.size(); i++) {
            if (in[i] == 0) {
                in[0] = i;
            }
        }
        cout << dp[in] << endl;
        in.clear();
        in.resize(9);
    }
}


Measured memory_bytes: 5544
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        s[i] = 'A' + (s[i] - 'A' + n) % 26;
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.algorithm, std.range, std.conv;

void main(){
    while(true){
        auto input = readln.split;
        int n = input[0].to!int, k = input[1].to!int;

        if(n == 0 && k == 0) break;
        auto G = new int[][](n + 1, n + 1);
        foreach(ref g; G){
            g[] = int.max;
        }

        foreach(Unused; 0..k){
            input = readln.split;
            int op = input[0].to!int;
            if(op == 1){
                int a = input[1].to!int, b = input[2].to!int, cost = input[3].to!int;
                if(cost < G[a][b]){
                    G[a][b] = cost;
                    G[b][a] = cost;
                }
            }else if(op == 0){
                int start = input[1].to!int, end = input[2].to!int;
                auto d = new int[](n + 1);
                auto MST = new bool[](n + 1);
                d[] = int.max;
                d[start] = 0;
                while(true){
                    int min = int.max;
                    int u;
                    foreach(i; 1..n + 1){
                        if(!MST[i] && min > d[i]){
                            min = d[i];
                            u = i;
                        }
                    }
                    if(u == 0) break;
                    MST[u] = true;
                    foreach(v; 1..n + 1){
                        if(!MST[v] && G[u][v] != int.max && G[u][v] + d[u] < d[v]){
                            d[v] = G[u][v] + d[u];
                        }
                    }
                }
                if(d[end] == int.max) (-1).writeln;
                else d[end].writeln;
            }
        }
    }
}

Measured memory_bytes: 1804
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int a, b; cin >> a >> b;
  cout << (a <= 8 && b <= 8? "Yay!" : ":(") << '\n';
  return 0;
}


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

int main(){
  int N;
  cin >> N;
  vector<int> x(N), y(N), h(N);
  rep(i, N) cin >> x.at(i) >> y.at(i) >> h.at(i);
  int x0, y0, h0, i;
  h0 = 0, i = 0;
  while(h0 == 0){
    if(h.at(i)){
      x0 = x.at(i);
      y0 = y.at(i);
      h0 = h.at(i);
      break;
    }
    i++;
  }
  
  int ans_x, ans_y, ans_h;
  for(int cx = 0; cx <= 100; cx++){
    bool check = false;
    for(int cy = 0; cy <= 100; cy++){
      int dis = abs(x0 - cx) + abs(y0 - cy);
      int ch = h0 + dis;
      bool flag = true;
      for(int j = 0; j < N; j++){
        if( h.at(j) != max(ch - abs(x.at(j) - cx) - abs(y.at(j) - cy), 0)){
          flag = false;
          break;
        }
      }
      if(flag){
        ans_x = cx; ans_y = cy; ans_h = ch;
        check = true;
        break;
      }
    }
    if(check) break;
  }
  
  cout << ans_x << ' ' << ans_y << ' ' << ans_h << endl;
}

Measured memory_bytes: 256
words = []
n = gets.to_i
blues = []
n.times do
  s = gets.strip
  blues << s
  words << s
end

m = gets.to_i
reds = []
m.times do
  t = gets.strip
  reds << t
  words << t
end

mx = -10000000
words.sort.uniq.each do |w|
  plus = blues.count w
  minus = reds.count w
  mx = [mx, plus - minus].max
end

puts [mx, 0].max


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

namespace AtCoder2020Ned
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(' ');
            var numberOfMonsters = int.Parse(inputs[0]);
            var numberOfFennecUltimate = int.Parse(inputs[1]);

            var secondInputs = Console.ReadLine().Split(' ');
            var monstersHp = new int[secondInputs.Length];

            foreach (var item in secondInputs.Select((hp, index) => (new { Hp = hp, Index = index })))
            {
                monstersHp[item.Index] = int.Parse(item.Hp);
            }

            Array.Sort(monstersHp, (x, y) => (y - x));

            if (numberOfFennecUltimate > monstersHp.Length)
            {
                numberOfFennecUltimate = monstersHp.Length;
            }

            for (int i = 0; i < numberOfFennecUltimate; i++)
            {
                monstersHp[i] = 0;
            }

            ulong battleCount = 0;

            foreach (var item in monstersHp)
            {
                battleCount += (ulong)item;
            }

            Console.WriteLine(battleCount);
            Console.Read();
        }
    }
}


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

int main()
{
    int n;
    int i,j,k;
    cin >> n;
    vector<long long> t(n);
    vector<long long> a(n);
    for(i = 0;i < n;++i){
        cin >> t.at(i) >> a.at(i);
    }
    long long ans = t.at(0)+a.at(0);
    long long tempt = t.at(0),tempa = a.at(0);
    long long temp;
    for(i = 1;i < n;++i){
        temp = max((tempt-1)/t.at(i)+1,(tempa-1)/a.at(i)+1);
        ans = temp*(t.at(i)+a.at(i));
        tempt = temp*t.at(i);
        tempa = temp*a.at(i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e12);
const ll mod = ll(1e9+7);
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")

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

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

ll factorial(ll n){
    ll ans = 1;
    rep1(i, n){
        ans *= i;
        ans %= mod;
    }
    return ans;
}

ll power(ll a, ll b){
    ll ans = 1;
    a %= mod;
    while(b) {
        if(b & 1LL) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

vector<ll> FactorialInv, Factorial;

void init_combination(ll MAX){
    Factorial.resize(MAX + 1);
    FactorialInv.resize(MAX + 1);
    Factorial[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = power(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
}

ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    if(b < 0) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

//modの値の確認をすること
int main(){
    string s;
    cin >> s;
    vector<ll> ans(s.size());
    ll cnt = 1;
    rep0(i, s.size()){
        if(s[i] == s[i + 1] && s[i] == 'R'){
            ans[i] = 0;
            ++cnt;
        }else if(s[i] == 'R'){
            ans[i] = cnt;
            cnt = 1;
        }
    }
    rrep0(i, s.size()){
        if(s[i] == s[i - 1] && s[i] == 'L'){
            ans[i] = 0;
            ++cnt;
        }else if(s[i] == 'L'){
            ans[i] = cnt;
            cnt = 1;
        }
    }
    rep0(i, ans.size()){
        if(ans[i] != 0 && ans[i + 1] != 0){
            ll cnt = 0;
            nfor(j, -ans[i] + 1, ans[i + 1] + 1)if(j % 2 == 0)++cnt;
            ans[i + 1] = ans[i] + ans[i + 1] - cnt;
            ans[i] = cnt;
            ++i;
        }
    }
    rep0(i, ans.size() - 1)cout << ans[i] << " ";
    pf(ans[ans.size() - 1]);
    return 0;
}


Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String st = sc.next();
		String[] s = st.split("");
		int count01 = 0; int  count10 = 0; boolean sw = true;
		for(String a: s) {
			if(sw) {
				if(a.equals("0"))count01++;
				if(a.equals("1"))count10++;
			}else {
				if(a.equals("1"))count01++;
				if(a.equals("0"))count10++;
			}
			sw = !sw;
		}
		System.out.println(Math.min(count01,count10));

		sc.close();
	}
}

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

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

    int N;
    cin >> N;
    int T[N];
    int sum = 0;
    for(int i = 0; i < N; ++i){
        cin >> T[i];
        sum += T[i];
    }
    
    int M;
    cin >> M;
    int res[M];

    for (int i = 0; i < M; ++i){
        int X, P;
        cin >> X >> P;

        res[i] = sum - (T[X - 1] - P);
    }

    for (int i = 0; i < M; ++i) cout << res[i] << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long min = sc.nextInt();
		long max = min;
		for(int i = 0; i < N-1; i++) {
			long A = sc.nextInt();
			min = Math.min(min,A);
			max = Math.max(max, A);
		}
		System.out.println(max-min);
	}
}


Measured memory_bytes: 21844
Sp = list(input())
T = list(input())

len_Sp = len(Sp)
len_T = len(T)
restorable = False
max_i = 0
if len_Sp >= len_T:
    for i in range(len_Sp - len_T, -1, -1):
        for j in range(len_T):
            if Sp[i + j] != '?' and Sp[i + j] != T[j]:
                break
        else:
            #Sp[i : i + len_T] = T
            max_i = max(max_i, i)
            restorable = True
if restorable:
    Sp[max_i : max_i + len_T] = T
    print(''.join(Sp).replace('?', 'a'))
else:
    print('UNRESTORABLE')
#print(''.join(Sp).replace('?', 'a') if restorable else 'UNRESTORABLE')


Measured memory_bytes: 3064
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)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $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! {
    n: usize,
    c: [usize; 5]
    }
    let m = c.iter().min().unwrap();
    let ans: usize = 5 + n / m - if n % m == 0 {1} else {0};
    println!("{}", ans);
}



Measured memory_bytes: 2152
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	ll A, v, B, w, t;
 	cin >> A >> v >> B >> w >> t;
 	if (abs(A - B) <= t * (v - w)) cout << "YES\n";
 	else cout << "NO\n";
 	return 0;
}

Measured memory_bytes: 3652
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Console;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static StreamWriter sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
        static void Main(string[] args)
        {
            try
            {
                SetOut(sw);
                Solve.Answer();
                Out.Flush();
            }
            catch (Exception ex)
            {
                WriteLine(ex.ToString());
            }
        }
    }

    public class Solve
    {
        public static void Answer()
        {
            var NK = IO.RSInt;
            var x = IO.RSInt;

            var N = NK[0];
            var K = NK[1];

            var ans = long.MaxValue;
            for (int i = 0; i < N - K + 1; i++)
            {
                long d = Abs(x[i + K - 1] - x[i]);
                long c = Min(Abs(x[i + K - 1]), Abs(x[i]));

                ans = Min(ans, d + c);
            }

            WriteLine(ans);

        }
    }

    public class IO
    {
        #region Input
        public static int RInt => int.Parse(ReadLine());
        public static long RLong => long.Parse(ReadLine());
        public static double RDouble => double.Parse(ReadLine());

        public static string[] RSString => ReadLine().Split();
        public static int[] RSInt => ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        public static long[] RSLong => ReadLine().Split().Select(s => long.Parse(s)).ToArray();
        public static double[] RSDouble => ReadLine().Split().Select(s => double.Parse(s)).ToArray();
        #endregion

        #region Output
        public static void OutJoinSpace<T>(IEnumerable<T> list) => WriteLine(string.Join(" ", list));
        public static void WriteLineYes_or_No(bool flag) => WriteLine(flag ? "Yes" : "No");
        public static void WriteLineYES_or_NO(bool flag) => WriteLine(flag ? "YES" : "NO");
        #endregion
    }

    public class Mod
    {
        #region
        private readonly static long M = 1000000007;

        public static long Add(long a, long b) => (a * b) % M;
        public static long Sub(long a, long b) => (a - b) % M >= 0 ? (a - b) % M : (a - b) % M + M;
        public static long Multi(long a, long b) => (a * b) % M;
        #endregion
    }
}

Measured memory_bytes: 28804
#include <bits/stdc++.h>
#if 1
#define int long long
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define stoi stoll
#else
#define MAX INT_MAX
#define MIN INT_MIN
#endif
#define ALL(obj) (obj).begin(), (obj).end()
#define fi first
#define se second
const int NIL = -1;
const int MOD = 1000000007;
#define REP(i,n) for (int i=0; i < (n); ++i)
#define FOR(i,a,b) for (int i=(a); i < (b); ++i)
using namespace std;

int get_gcd(int a, int b){while(1){if (a < b) swap(a, b); if (b == 0) return a; a %= b;}}
int get_lcm(int a, int b){return a * b / get_gcd(a, b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//-------------------------テンプレここまで-------------------------//

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

  string s, s_org;
  cin >> s;
  int n = s.size() - 1;
  s_org = s;

  int sum = 0;
  // bit全探索
  for (int bit = 0; bit < (1<<n); bit++) {
    s = s_org;
    for (int i = 0; i < n; i++) {
      if (bit & (1<<i)) {
        string ss = s.substr(n-i);
        sum += stoi(ss);
        s = s.substr(0, n-i);
      }
    }
    sum += stoi(s);
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
template <class T> inline void dump(T &v){irep(i, v){cout<<(*i)<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-11;



int main() {
    
    string s;
    cin>>s;
    if(s=="RRR")fin(3);
    else if(s.substr(0,2)=="RR"||s.substr(1,2)=="RR")fin(2);
    else if(s=="SSS")fin(0);
    else fin(1);
}

Measured memory_bytes: 3628
#include<iostream>
#include<bitset>
#define plus 8000
using namespace std;

int main(){
  string s;
  cin>>s;
  int n= s.size();
  int a[10000]={};
  int j=0;

  for(int i=0;i<n;i++){
    if(s[i]=='F') a[j]++;
    else j++;
  }

  bitset<16001> dpx,dpy;
  dpx=1;
  dpy=1;
  dpx=dpx<<plus;
  dpy=dpy<<plus;
  dpx=dpx<<a[0];
  int i = 1;

  while(i<plus){
    dpy = (dpy<<a[i])|(dpy>>a[i]);
    i++;
    dpx = (dpx<<a[i])|(dpx>>a[i]);
    i++;
  }

  int x,y;
  cin>>x>>y;
  if(dpx[x+plus]&&dpy[y+plus])
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int t[100005],x[100005],y[100005];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i]>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(int(fabs(t[i]-t[i-1]))<int(fabs(x[i]-x[i-1])+fabs(y[i]-y[i-1])))
		{
			cout<<"No";
			return 0;
		}
		if(int(fabs(t[i]-t[i-1]))%2!=int(fabs(x[i]-x[i-1])+fabs(y[i]-y[i-1]))%2)
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

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

int main()
{
    int n;
    cin>>n;
    vector<tuple<string,int,int>> res(103);
    for(int i=0;i<n;i++)
    {
        string name;int score;int num=i;
        cin>>name>>score;
        res[i] = make_tuple(name,score,i);
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>0;j--)
        {
            if(get<0>(res[j]) < get<0>(res[j-1]))
            {
                tuple<string,int,int> temp = res[j-1];
                res[j-1] = res[j];
                res[j] = temp;
            }
            if(get<0>(res[j]) == get<0>(res[j-1]))
            {
                if(get<1>(res[j]) > get<1>(res[j-1]))
                {
                    tuple<string,int,int> tmp = res[j-1];
                    res[j-1] = res[j];
                    res[j] = tmp;
                }
            }
        }
    }
    
    for(int i=0;i<n;i++)
    {
        cout<<get<2>(res[i])+1<<endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int H, W, i,j;
	while (1)
	{
		cin >> H >> W;
		if (H == 0 && W == 0)break;
		for (i = 0; i < H; i++)
		{for (j = 0; j < W; j++)
			
				cout << "#";
				cout << endl;
			}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector<int> > G(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			int v_j;
			cin >> v_j;
			G[u - 1][v_j - 1] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << G[i][j] << (j == n - 1 ? "\n" : " ");
		}
	}
}

Measured memory_bytes: 1256
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 305
#define inf 1e18
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

ll dp[maxn][maxn],a[maxn],n,k;

int main()
{
	n=read(); k=read(); rep(i,1,n) a [i]=read();
	rep(i,1,n) rep(j,1,n) dp[i][j]=inf;
	rep(i,1,n) dp[i][1]=a[i];
	rep(i,2,n)
	{
		rep(j,2,i)
		{
			ll tmp=inf;
			for(int k=1;k<=i-1;k++)
			{
				ll p=dp[k][j-1]; if(p==inf) continue;
				if(a[i]>a[k]) p+=(a[i]-a[k]);
				tmp=min(tmp,p);
			}
			dp[i][j]=tmp;
		}
	}
	ll ans=inf;
	for(int i=n;i>=n-k;i--) ans=min(ans,dp[i][n-k]); cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
K=int(input())
S=input()
N=len(S)
mod=10**9+7

fact=[1]*(K+N)
for i in range(2,K+N):
    fact[i]=fact[i-1]*i%mod

inv=[1]*(K+N)
inv[K+N-1]=pow(fact[K+N-1],mod-2,mod)
for i in range(K+N-2,0,-1):
    inv[i]=inv[i+1]*(i+1)%mod
    
def comb(n,r):
    ret=fact[n]*inv[r]*inv[n-r]%mod
    return ret

ans=0
for i in range(K+1):
    ans+=pow(26,i,mod)*pow(25,K-i,mod)*comb(K+N-1-i,N-1)
    ans%=mod

print(ans)

Measured memory_bytes: 117360
#include <bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
using G=vector<vector<int>>;
using ll=long long;

int main(){
    string s;
    cin>>s;
    int n=s.length();
    int p=2019;
    
    if(p==2||p==5){
        ll ans=0;
        for(int i=0;i<n;i++){
            if((s[i]-'0')%p==0LL){
                ans +=i+1;
            }
            
        }
        cout<<ans<<endl;
    }
    else{
        vector<ll>U(n+1,0);
        map<int,int>mods;//各mod pに何個値があるか
        mods[0]=1;
        ll ans=0;
        int pw[n+1];
        pw[0]=1;
        //この処理をしないと値が大きくなりすぎる
        for(int i=1;i<=n;i++) pw[i]=10*pw[i-1] %p;

        for(int i=n-1;i>=0;i--){
            //各Uを求める
            U[i]=(U[i+1]+(s[i]-'0')*pw[n-i-1])%p;
            ans+=mods[U[i]];
            mods[U[i]]++;
        }

        cout<<ans<<endl;
    }
}

Measured memory_bytes: 5920
import math
import copy

neko = 0
n,m = map(int,input().split())
b = [0] * m
for i in range(n):
    a = [int(x) for x in input().split()]
    for j in range(1,len(a)):
        b[a[j]-1] += 1
for i in range(m):
    neko = (neko+1 if b[i]==n else neko)
print(neko)

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	n=n%10;
	
	switch(n)
	{
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:cout<<"hon"<<endl; break;
		
		case 0:
		case 1:
		case 6:
		case 8:cout<<"pon"<<endl; break;
		
		case 3:cout<<"bon"<<endl; break;	
	}
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define fi first
#define se second
 
const ll MOD = 1000000007;

int main() {
   char temp[100000]; scanf("%s", &temp); string s(temp);
   vector<int> run; run.pb(-1);
   for (int i = 0; i < s.size() - 1; ++i) {
      if (s[i] != s[i + 1])
         run.pb(i);
   }
   run.pb(s.size() - 1);
   vector<int> ans(s.size());
   for (int i = 1; i < run.size(); i += 2) {
      int left = run[i] - run[i - 1];
      int right = run[i + 1] - run[i];
      ans[run[i]] = (left + 1) / 2 + right / 2;
      ans[run[i] + 1] = left / 2 + (right + 1) / 2;
   }
   for (int i : ans)
      printf("%d ", i);
   return 0;
}

Measured memory_bytes: 1528
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

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

    ll n, m;
    cin >> n >> m;

    cout << n*(n-1)/2 + m*(m-1)/2 << endl;

    return 0;
}

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

using namespace std;

int main() 
{
#ifdef DK
    freopen("in", "r", stdin);
#endif
    int n;
    cin >> n;
    int ans = 0;
    while (n) {
        ans += ((int) to_string(n).size() % 2 == 1);
        n--;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.replace(/\n$/,"")).split("\n");
var n=Arr.shift()-0;
for(var i=0;i<n;i++){
var arr=Arr[i].split(" ").map(Number);
var s=arr[0];
var g=arr[1];
var ans=[s];
var plus=1;
if(s<g){do{s++;ans.push(s);}while(s!=g);}
else if(s>g && s<=5){do{s--;ans.push(s);}while(s!=g);}
else if(s>g && s>=6){do{s+=plus;if(s==10){s=5;plus=-1;};if(s==0){plus=1;};ans.push(s);}while(s!=g);}
console.log(ans.join(" "));
}

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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define what_is(x) cerr << #x << " is " << x << endl;

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	string s;
	ll k;
	cin >> s >> k;
	int n = s.length();
	int first;
	for (first = 0; first < n; first++) {
		if (s[first] != '1') break;
	}

	if (first == n || first >= k)
		puts("1");
	else
		printf("%c\n", s[first]);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

#include <complex>

typedef complex<double> C;
const double PI=acos(-1.0);

vector<C> FFT(vector<C> a,bool inverse=false){
    int n=a.size();
    int high=0;
    for(int i=0;(1<<i)<n;i++) high++;

    for(int i=0;i<n;i++){
        int mask=0;
        for(int k=0;k<high;k++){
            if(i>>k&1) mask|=(1<<(high-1-k));
        }
        if(i<mask) swap(a[i],a[mask]);
    }

    for(int b=1;b<n;b*=2){
        for(int j=0;j<b;j++){
            C w=polar(1.0,2*PI*j*(inverse?-1.0:1.0)/(2*b));
            for(int k=0;k<n;k+=2*b){
                C s=a[k+j];
                C t=a[k+j+b]*w;

                a[k+j]=s+t;
                a[k+j+b]=s-t;
            }
        }
    }

    if(inverse){
        for(int i=0;i<n;i++) a[i]/=n;
    }
    return a;
}

vector<double> convolute(const vector<double> &a,const vector<double> &b){
    int size=a.size()+b.size()-1;
    int n=1;
    while(n<size) n*=2;

    vector<C> A(n,C(0,0)),B(n,C(0,0));
    for(int i=0;i<a.size();i++) A[i]=C(a[i],0);
    for(int i=0;i<b.size();i++) B[i]=C(b[i],0);

    A=FFT(A);
    B=FFT(B);

    for(int i=0;i<n;i++) A[i]*=B[i];
    A=FFT(A,true);

    vector<double> res(size);
    for(int i=0;i<size;i++) res[i]=A[i].real();
    return res;
}

int N,M,K,L;
vector<string> P;
string S;

int main(){
  cin>>N>>M>>K>>L;
  P.resize(N);
  rep(i,N) cin>>P[i];
  cin>>S;

  vector<double> A(M*M,0),B(M*M,0);
  for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
          if(P[i][j]=='X') A[i*M+j]=1;
      }
  }

  int x=0,y=0;
  for(int i=0;i<L;i++){
      if(S[i]=='U') x--;
      else if(S[i]=='D') x++;
      else if(S[i]=='L') y--;
      else y++;

      B[x*M+y]+=1;
  }

  vector<double> c=convolute(A,B);
  int ans=0;
  for(int i=0;i<M*M;i++){
      int res=(int)(c[i]+0.5);
      if(res>=K) ans++;
  }
  cout<<ans<<endl;

  return 0;
}



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

int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<char>>m(h,vector<char>(w));
    vector<vector<bool>>tf(h,vector<bool>(w,true));
    rep(i,h){
        int count=0;
        rep(j,w){
            char c;
            cin>>c;
            m[i][j]=c;
            if(c=='.') count++;
        }
        if(count==w){
            rep(j,w) tf[i][j]=false;
        }
    }

    rep(j,w){
        int count=0;
        rep(i,h){
            if(m[i][j]=='.') count++;
        }
        if(count==h){
            rep(i,h) tf[i][j]=false;
        }
    }


    rep(i,h){
        int x=0;
        rep(j,w){
            if(tf[i][j]==true) {
                cout << m[i][j];
                x++;
            }
        }
        if(x>0)cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <string>
#include <algorithm>
#include <vector> 
#include <math.h>
#include <iostream>
using namespace std;
long long mod = 1000000000 + 7;

struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

int main()
{
	int n ,m;
	cin >> n >>m;
	
	vector<vector<int>> a(m);
	bool flag = true;
	
	for (int i = 0; i < m; i++) {
		int a1, a2, a3;
		cin >> a1 >> a2 >> a3;
		a[i].push_back(a1);
		a[i].push_back(a2);
		a[i].push_back(a3);
		
	}

	
	int island = 0;
	UnionFind tree(n); 

	for (int i = 0; i < m; i++) {
		if (tree.same(a[i][0] - 1, a[i][1] - 1)) {
			island++;
		}
		tree.unite(a[i][0] - 1, a[i][1] -1 );
	}
	int ans = n - m + island;
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    vector<int> a(2e5,0);
    int x;
    cin >> x;
    rep(i,2e5){
        if (i<2) continue;
        if (a[i]==0){
            for(int k=i*2;k<2e5;k+=i){
                a[k]=1;
            }
        }
    }
    while(true){
        if (a[x]==0) break;
        x++;
    }
    cout << x << endl;
}


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

typedef long long ll;

using namespace std;

int main() {
	int n; cin >> n;
	int seq[n];
	vector<ll> count(n, 0);
	for(int i = 0; i < n; i++) {
		cin >> seq[i];
		count[seq[i]-1]++;
	}
	ll sum = 0;
	for(int i = 0; i < n; i++) {
		sum += (count[i] * (count[i]-1)) / 2;
	}
	for(int i = 0; i < n; i++) {
		ll summ = sum;
		summ -= count[seq[i] - 1] - 1;
		cout << summ << endl;
	}
}





Measured memory_bytes: 4992
/*input
5 2
..
#.
..
.#
..

*/



#include<bits/stdc++.h>
using namespace std;
int mod = 1e9 +7;
int main()
{
	int h,w;
	cin>>h>>w;
	vector<string> vec;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			string s;
			cin>>s;
			vec.push_back(s);
		}
	}
	int dp[h+1][w+1];
	int flag=0;
	for(int j=0;j<w;j++)
	{
		if(vec[0][j]=='#')
		flag=1;
		if(flag)
			dp[0][j]= 0;
		else dp[0][j]=1;
	}
	 flag=0;
	for(int j=0;j<h;j++)
	{
		if(vec[j][0]=='#'){
		flag=1;	
	}

		if(flag)
			dp[j][0]= 0;
		else dp[j][0]=1;
	}

	for(int i=1;i<h;i++)
	{
		for(int j=1;j<w;j++)
		{
			if(vec[i][j]=='#')
				dp[i][j]=0;
			else
			{
				dp[i][j] = (dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
			}
		}
	}
	cout<<dp[h-1][w-1]<<endl;
}

Measured memory_bytes: 13160
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
print("\n".join(list(map(lambda x:str(len(x)), edge))))

Measured memory_bytes: 9200
// Created by Kshitij Anand NSIT
#include <bits/stdc++.h>


using namespace std;


#define int long long
#define pb push_back
#define P pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define vc vector<char>
#define vb vector<bool>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mp(a, b) make_pair(a, b)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fill(arr,val) memset(arr,val,sizeof(arr))
#define db(x)  cout<<#x<<" : "<<x<<endl


const int N = 1000000007;

int func(int arr[] ,  int n , int k){

	int dp[n];

	for(int i=0; i<n; i++) {
		dp[i] = INT_MAX;
	}
	dp[0] = 0;

	dp[1] = abs(arr[1] - arr[0]);


	for(int i=2; i<n; i++) {

		for(int j=1; j<=k; j++) {

			if(i-j >=0){
				dp[i] = min(dp[i] , dp[i-j] + abs(arr[i] - arr[i-j]));

			}
		}


		// dp[i] = min(dp[i] , dp[i-1] + abs(arr[i] - arr[i-1]));
	}

	return dp[n-1];

}

void solve(){

    int n,k,b,c, ans=0, count=0, sum=0;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++){
      cin>>arr[i];
    }

    ans = func(arr , n , k);

    cout<<ans<<endl; 
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    
  //  int t; cin>>t; while(t--)
    {     
      solve();
    }

  return 0;
}


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

int main(){
	int a,b;
	string c,d;
	char ans;
	cin >> c;
	cin >> d;
	ans=c[0];
	c[0]=c[2];
	c[2]=ans;
	if(c==d)
		cout<<"YES";
	else
		cout <<"NO";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ms memset
#define MOD 1000000007
#define MOD2 1000000009
#define sp fixed<<setprecision
#define sz(x) (int)(x).size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
ll fpow(ll x,ll y,ll p=MOD){x=x%p;ll sum=1;while(y){if(y&1)sum=sum*x;sum%=p;y=y>>1;x=x*x;x%=p;}return sum;}
ll inv(ll a,ll m=MOD){ll c=m;ll y=0,x=1;if(m==1)return 0;while(a>1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=c;return x;}
ll add(ll a, ll b) {if(a<0)a+=MOD; if(b<0)b+=MOD; return (a%MOD + b%MOD + MOD)%MOD;}
ll sub(ll a, ll b) {if(a<0)a+=MOD; if(b<0)b+=MOD; return (a%MOD - b%MOD + MOD)%MOD;}
ll mul(ll a, ll b) {if(a<0)a+=MOD; if(b<0)b+=MOD; return ((a%MOD)*(b%MOD) + MOD)%MOD;}
void setIO(string name = "") {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (sz(name)) {
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}
ll dp[2001];
ll foo(ll x){
  if(x==0)
    return 1;
  else if(x<3)
    return 0;
  else if(dp[x]!=0)
    return dp[x];
  ll sum = 0;
  for(int i=3;i<=x;i++){
    sum+=foo(x-i);
    sum%=MOD;
  }
  return dp[x]=sum;

}
int main(){
    setIO();
    ll n;
    cin>>n;
    cout<<foo(n);
}


Measured memory_bytes: 3672
void main()
{
    long n, k;
    rdVals(n, k);
    long[] h = n.rdCol;

    h.sort!"a < b";
    long[] total = new long[n];
    foreach (i; 1 .. n)
    {
        total[i] = total[i-1] + h[i] - h[i-1];
    }

    long result = inf;
    foreach (i; k-1 .. n)
    {
        result = min(result, total[i]-total[i-k+1]);
    }

    result.writeln;
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 4732
N,M,Q = map(int,input().split())
q = []
for i in range(Q):
	a,b,c,d = map(int,input().split())
	q.append((a-1,b-1,c,d))

def score(ary):
	ret = 0
	for x in q:
		if ary[x[1]] - ary[x[0]] == x[2]:
			ret += x[3]
	return ret

def f(n,mi,ary):
	if n == 0:
		return score(ary)
	return max([f(n-1, i, ary + [i]) for i in range(mi, M+1)])

print(f(N-1, 1, [1]))

Measured memory_bytes: 9228
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <ctime>
#include <iterator>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;



int main()
{
    int N;
    cin>>N;
    vector<int> A(N+1);
    for(int c=1;c<=N;c++)
    {
        cin>>A[c];
    }
    for(int j=2;j<=N;j++)
    {
        for(int c2=1;c2<=N;c2++) cout<<A[c2]<<(c2 < N ? " " : "");
        cout<<endl;
        int key = A[j];
        int i = j - 1;
        while( i > 0 && A[i] > key)
        {
            A[i+1] = A[i];
            i--;
        }
        A[i+1] = key;
    }
    for(int c2=1;c2<=N;c2++) cout<<A[c2]<<(c2 < N ? " " : "");
    cout<<endl;
}

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

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

    int idx = -1;
    bool can = false;
    rep(i, s.size() - t.size() + 1) {
        bool flg = true;
        rep(j, t.size()) {
            if(s[i + j] == t[j] || s[i + j] == '?') continue;
            flg = false;
        }
        if(flg) can = true, idx = i;
    }
    if(!can) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    
    rep(i, t.size()) {
        if(s[i + idx] == '?') s[i + idx] = t[i];
    }
    rep(i, s.size()) {
        if(s[i] == '?') s[i] = 'a';
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define vb __int128
#define ll long long
#define ld long double
#define full(a) a.begin(),a.end()
#define stoink stack<ll>
#define vec vector <ll>
#define vg vector<vector<ll> >
#define vgw vector<vector<pair<ll,ll> >
#define pa pair<ll,ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define prec 0.00000000000000000001
#define inf 1000000000000
#define mod (ll)(1e9 + 7)
ll n;
vec arr;
vec pre;
ll dp[101][100001];
int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll k;
	cin >> n >> k;
	arr.resize(n+1);
	ll i,j;
	for(i = 1 ; i <= n ; i++) {
		cin >> arr[i];
	}
	dp[0][0] = 1;
	for(i = 1 ; i <= n ; i++) {
		vec pre(k+1);
		for(j = 0 ; j <= k ; j++) {
			if(j == 0) 
				pre[j] = dp[i-1][j];
			else
				pre[j] = dp[i-1][j] + pre[j-1]; 
		}
		for(j = 0; j <= k ; j++) {
			ll val;
			if(j <= arr[i])
				val = 0;
			else
				val = pre[j - arr[i] - 1];
			dp[i][j] = (pre[j] - val) % mod;
		}	

	}
	cout << dp[n][k] << endl;
	return 0;
}

Measured memory_bytes: 82516
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll n,k,ans=0,s;
  cin>>n>>k;
  for(int i=k;i<n+2;i++){
    s=(n+1-i)*i+1;
    ans+=s;
  }
  cout<<ans%1000000007<<endl;
}

Measured memory_bytes: 3628