akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;


int main() {
    long double a,b,v,w,t;
    cin >> a >> v >> b >> w >> t;
    if(v <= w) {
        puts("NO");
        return 0;
    }
    long double dist = abs(a - b);
    long double ti = dist / (v - w);
    if(ti <= t) {
        puts("YES");
    } else {
        puts("NO");
    }
    return 0;
}

Measured memory_bytes: 3788
def p_c():
    n, m = map(int, input().split())
    s = [list(map(int, input().split()))[1:] for _ in range(m)]
    *p, = map(int, input().split())
    b = []
    for _s in s:
        bit = 0
        for i in _s:
            bit += (1 << (i - 1))
        b.append(bit)
    ans = 0
    for i in range(1 << n):
        for j, k in enumerate(b):
            if bin(i & k).count("1") & 1 != p[j]:
                break
        else:
            ans += 1
    print(ans)
    
p_c()

Measured memory_bytes: 3064
#![allow(unused_imports)]
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,
    }
    let n = s.len();
    for _ in 0..n{
        print!("x")
    }
}


Measured memory_bytes: 4352
using System;

class Program
{
    static void Main()
    {
        long N = long.Parse(Console.ReadLine());
        string[] a = Console.ReadLine().Split(' ');

        long cnt = 0;
        long preNum = 0;

        for(int i = 0; i < a.Length; i++)
        {
            long num = long.Parse(a[i]);

            if(preNum + 1 == num)
            {
                cnt++;
                preNum++;
            }
        }
        if(preNum == 0)
        {
            Console.WriteLine("-1");
        }
        else
        {
            Console.WriteLine((a.Length - cnt).ToString());
        }
    }
}


Measured memory_bytes: 30724
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).end(),greater<>()
#define Pi 3.1415926535
#define MOD 1000000007;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}
void yes(){cout << "Yes" << endl;}
void no(){cout << "No" << endl;}

int solve(){
    double a,b; cin >> a;


    cout << a*2*Pi << endl;

    return 0;
}

int main(){
    cin.tie(0);
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 3808
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int ans = 0;
        String A[] = new String[H];
        String mine[][] = new String[H][W];
        for (int z = 0; H > z; z++) {
            A[z] = sc.next();
        }
        for (int i = 0; H > i; i++) {
            for (int j = 0; W > j; j++) {
                char tmp = A[i].charAt(j);
                mine[i][j] = String.valueOf(tmp);
            }
        }
        for (int s = 0; H > s; s++) {
            for (int e = 0; W > e; e++) {
                ans = 0;
                if (!"#".equals(mine[s][e])) {
                    if (s - 1 >= 0 && e - 1 >= 0) {
                        if ("#".equals(mine[s - 1][e - 1])) {
                            ans++;
                        }
                    }
                    if (s - 1 >= 0) {
                        if ("#".equals(mine[s - 1][e])) {
                            ans++;
                        }
                    }
                    if (s - 1 >= 0 && e + 1 < W) {
                        if ("#".equals(mine[s - 1][e + 1])) {
                            ans++;
                        }
                    }
                    if (e - 1 >= 0) {
                        if ("#".equals(mine[s][e - 1])) {
                            ans++;
                        }
                    }
                    if (e + 1 < W) {
                        if ("#".equals(mine[s][e + 1])) {
                            ans++;
                        }
                    }
                    if (s + 1 < H && e - 1 >= 0) {
                        if ("#".equals(mine[s + 1][e - 1])) {
                            ans++;
                        }
                    }
                    if (s + 1 < H) {
                        if ("#".equals(mine[s + 1][e])) {
                            ans++;
                        }
                    }
                    if (s + 1 < H && e + 1 < W) {
                        if ("#".equals(mine[s + 1][e + 1])) {
                            ans++;
                        }
                    }
                    System.out.print(ans);
                } else {
                    System.out.print(mine[s][e]);
                }
            }
            System.out.println("");
        }
    }
}


Measured memory_bytes: 22356
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(D)]
last = [-1]*26
ans = 0
for i in range(D):
  TEMP = -float('inf')
  T = -1
  for t in range(26):
    temp = 0
    temp += s[i][t]
    tempo = last[t]
    last[t] = i
    temp -= sum([c[j]*(i-last[j]) for j in range(26)])
    #print(temp)
    if temp > TEMP:
      T = t
      TEMP = temp
    last[t] = tempo
  print(T+1)
  last[T] = i
  ans += TEMP
  #print(ans)


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

int a[100000];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N, S, W, Q;
	while(cin >> N >> S >> W >> Q, N){
		int g = S;
		for(int i = 0; i < N; i++){
			a[i] = (g / 7) % 10;
			if(g % 2 == 0){ g = (g / 2); }
			else{ g = (g / 2) ^ W; }
		}

		if(Q == 2 || Q == 5){
			ll nonzero = 0, ans = 0;
			for(int i = 0; i < N; i++){
				if(Q == 2 && a[i] % 2 == 0){
					ans += nonzero;
					if(a[i] != 0) ans++;
				}
				if(Q == 5 && (a[i] == 0 || a[i] == 5)){
					ans += nonzero;
					if(a[i] == 5) ans++;
				}
				if(a[i] != 0) nonzero++;
			}
			cout << ans << endl;
		}
		else{
			map<int, ll> m;
			ll mod = 0, ans = 0, pow = 1;
			for(int i = N - 1; i >= 0; i--){
				mod = (a[i] * pow + mod) % Q;
				if(a[i] != 0 && m.count(mod)){
					ans += m[mod];
				}
				if(a[i] != 0 && mod == 0) ans++;
				m[mod]++;
				pow *= 10;
				pow %= Q;
			}
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 9148
#include<iostream>
using namespace std;
const double eps=1e-9;
double p,q,a;
int n;
int ans=0;
void dfs(double pq,int s,int depth,int seki){
  if(pq>=-eps&&pq<=eps){
    ans++;
    return;
  }
  for(int i=s;i<=a;i++){
    if(seki*i>a)
      break;
    if((pq-(1.0/i))>=-eps&&depth+1<=n){
      dfs((pq-(1.0/i)),i,depth+1,seki*i);
    }
  }
}
int main(){
  while(cin>>p>>q>>a>>n,p+q+a+n){
    ans=0;
    for(int i=1;i<=a;i++){
      if((p/q)-(1.0/i)>=-eps)
	dfs((p/q)-(1.0/i),i,1,i);
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3208
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<bitset>
#include<complex>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')	f=-1;c=getchar();}
    while(isdigit(c))	{x=x*10+c-'0';c=getchar();}
    x*=f;
}
int n;
int a[200005];
int b[200005];
int main()
{
	read(n);
	for(int i=0;i<n;i++)
	{
		read(a[i]);
		b[i]=a[i];
	}
	sort(b,b+n);
	for(int i=0;i<n;i++)
	{
		if(a[i]<=b[n/2-1])
			printf("%d\n",b[n/2]);
		else
			printf("%d\n",b[n/2-1]);
	}
	return 0;
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T>
T SUM(V<T> v, T init_val=0){return accumulate(ALL(v),T(init_val));}

int main(){
    int n;
    cin>>n;
    Vi a(n),b(n);
    REP(i,n) cin>>a[i];

    REPD(i,n-1){
        int cnt=0;
        int j = i+1;
        while(j<=n){
            if((j)%(i+1)!=0) continue;
            if(b[j-1]==1) cnt++;
            j += i+1; 
        }
        if(a[i]==1 && cnt%2==0 ) b[i] = 1;
        else if(a[i]==0 && cnt%2==1 ) b[i] = 1;
    }

    int m = SUM(b);
    cout<<m<<endl;
    REP(i,n){
        if(b[i] ==0 ) continue;
        cout<<i+1<<" ";
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 2560
def main():
    from sys import stdin
    import math
    n,m = map(int,stdin.readline().rstrip().split())
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,stdin.readline().rstrip().split())
        way[a].append(b)
        way[b].append(a)
    
    mark = [0]*(n+1)
    flag = True
    check = [1]

    while flag:
        flag = False
        check_bf = [i for i in check]
        check = []

        for i in check_bf:
            for j in way[i]:
                if mark[j] == 0:
                    mark[j] = i
                    check.append(j)
                    flag = True
    
    if 0 in mark[2:]:
        print("No")
    else:
        print("Yes")
        for i in mark[2:]:
            print(i)
main()

Measured memory_bytes: 34632
#include <bits/stdc++.h>
using namespace std;
 
namespace TYC
{
	const int N = 2e5 + 5;
 
	int n, tot, C[N], Fa[N], M[N], R[N], Q[N][2];
	vector<int> E[N];
	struct node {  int ls, rs, v; } tr[N * 150];
 
	int add(const int p, const int x, const int w, const int l = 1, const int r = n)
	{
		int o = ++tot;
		tr[o] = tr[p];
		if (l == r)
			return tr[o].v += w, o;
		int mid = (l + r) >> 1;
		if (x <= mid)
			tr[o].ls = add(tr[p].ls, x, w, l, mid);
		else
			tr[o].rs = add(tr[p].rs, x, w, mid + 1, r);
		tr[o].v = tr[tr[o].ls].v + tr[tr[o].rs].v;
		return o;
	}
 
	int merge(const int x, const int y, const int l = 1, const int r = n)
	{
		if (!x || !y)
			return x + y;
		int o = ++tot;
		if (l != r)
		{
			int mid = (l + r) >> 1;
			tr[o].ls = merge(tr[x].ls, tr[y].ls, l, mid);
			tr[o].rs = merge(tr[x].rs, tr[y].rs, mid + 1, r);
		}
		tr[o].v = tr[x].v + tr[y].v;
		return o;
	}
 
	int del(const int p, const int v, const int l = 1, const int r = n)
	{
		if (r <= v)
			return 0;
		if (l == r)
			return p;
		int o = ++tot, mid = (l + r) >> 1;
		if (v <= mid)
		{
			tr[o].ls = del(tr[p].ls, v, l, mid);
			tr[o].rs = tr[p].rs;
		}
		else
		{
			tr[o].ls = 0;
			tr[o].rs = del(tr[p].rs, v, mid + 1, r);
		}
		tr[o].v = tr[tr[o].ls].v + tr[tr[o].rs].v;
		return o;
	}
 
	int query(const int o, const int x, const int l = 1, const int r = n)
	{
		if (!o) 
			return 0;
		if (l == r)
			return tr[o].v;
		int mid = (l + r) >> 1;
		if (x <= mid)
			return query(tr[o].ls, x, l, mid);
		else
			return tr[tr[o].ls].v + query(tr[o].rs, x, mid + 1, r);
	}
 
	void dfs(const int u, const int f)
	{
		Fa[u] = f;
		M[u] = max(M[f], f);
		for (int v : E[u])
			if (v != f)
			{
				dfs(v, u);
				R[u] = merge(R[u], R[v]);
			}
		Q[u][0] = query(R[u], M[u]) + 1;
		Q[u][1] = query(R[u], M[f]) + 1;
		int t = query(R[u], u) + 1;
		R[u] = del(R[u], u);
		R[u] = add(R[u], u, t);
	}
 
	void dfs(const int u)
	{
		if (u != 1)
			C[u] = C[Fa[u]] + Q[u][0] - (u < M[u] && u < M[Fa[u]] ? Q[u][1] : 0);
		for (int v : E[u])
			if (v != Fa[u])
				dfs(v);
	}
 
	void work()
	{
		scanf("%d", &n);
		for (int i = 1, u, v; i < n; i++)
		{
			scanf("%d%d", &u, &v);
			E[u].push_back(v);
			E[v].push_back(u);
		}
		for (int i = 1; i <= n; i++)
			sort(E[i].begin(), E[i].end());
		dfs(1, 0);
		dfs(1);
		for (int i = 2; i <= n; i++)
			printf("%d ", C[i]);
	}
}
 
int main()
{
	TYC::work();
	return 0;
}

Measured memory_bytes: 141300
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;

int main(){
     int h;
     cin >> h;
     int a[h+1];
     for(int i = 0; i < h; i++){
          cin >> a[i+1];
     }
     for(int i = 1; i<=h; i++){
          cout << "node " << i << ": ";
          cout << "key = " << a[i] << ", ";
          if(i != 1){
               int parent = i / 2;
               cout << "parent key = " << a[parent] << ", ";
          }
          if(2 * i <= h) cout << "left key = " << a[2 * i] << ", ";
          if(2 * i + 1 <= h) cout << "right key = " << a[2 * i + 1] << ", ";
          cout << endl;
     }
     return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

void ABC131B()
{
	int N, L;
	cin >> N >> L;
	vector<int> A(N);
	for (int i = 0; i < N; ++i)
	{
		A[i] = L + i;
	}
	auto p = lower_bound(A.begin(), A.end(), 0);
	if (p == A.cend())
	{
		cout << accumulate(A.begin(), (--A.end()), 0) << endl;
		return;
	}
	if (p == A.cbegin())
	{
		cout << accumulate(A.begin() + 1, A.end(), 0) << endl;
		return;
	}

	if (abs(*p) < abs(*p-1))
	{
		cout << accumulate(A.begin(), A.end(), 0) - *p << endl;
	}
	else
	{
		cout << accumulate(A.begin(), A.end(), 0) - *(p-1) << endl;
	}
}
int main()
{
	ABC131B();
	return 0;
}

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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  string S; cin >> S;
  ll x = 0;
  for (ll i = 0; i < (ll)S.size(); i++) {
    if (S.at(i) == '+') x++;
    else x--;
  }
  cout << x << endl;

  return 0;
}



Measured memory_bytes: 256
/*
                                                                                                                                               
8b        d8                           888888888888                                             88b           d88                  ad88888ba   
 Y8,    ,8P                                 88                                        ,d        888b         d888                 d8"     "8b  
  Y8,  ,8P                                  88                                        88        88`8b       d8'88                 ""      a8P  
   "8aa8"  ,adPPYba,   88       88          88  8b,dPPYba,  88       88  ,adPPYba,  MM88MMM     88 `8b     d8' 88   ,adPPYba,          ,a8P"   
    `88'  a8"     "8a  88       88          88  88P'   "Y8  88       88  I8[    ""    88        88  `8b   d8'  88  a8P_____88         d8"      
     88   8b       d8  88       88          88  88          88       88   `"Y8ba,     88        88   `8b d8'   88  8PP"""""""         ""       
     88   "8a,   ,a8"  "8a,   ,a88          88  88          "8a,   ,a88  aa    ]8I    88,       88    `888'    88  "8b,   ,aa         aa       
     88    `"YbbdP"'    `"YbbdP'Y8          88  88           `"YbbdP'Y8  `"YbbdP"'    "Y888     88     `8'     88   `"Ybbd8"'         88       
                                                                                                                                               
*/
#include <bits/stdc++.h>
using namespace std;

int n;
long long a[404], dp[404][404];

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

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}

	for (int len = 2; len <= n; len++) {
		for (int i = 1; i <= n - len + 1; i++) {
			int j = i + len - 1;

			dp[i][j] = 1e18;
			for (int k = i; k < j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (a[k] - a[i - 1]) + (a[j] - a[k]));
			}
		}
	}

	cout << dp[1][n] << '\n';

	return 0;
} 

Measured memory_bytes: 1536
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

const int N = 1000 + 10;

int n;
long long w;

int convert(char *x)
{
	if (x[0] == 'S') {
		if (x[1] == 'u') return 0;
		return 6;
	} else if (x[0] == 'T') {
		if (x[1] == 'u') return 2;
		return 4;
	} else if (x[0] == 'M') {
		return 1;
	} else if (x[0] == 'W') {
		return 3;
	}
	return 5;
	assert(0);
}

void read(long long &x)
{
	char ch;
	for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar())
		x = x * 10 + ch - '0';
}

int id[N];
long long a[N];
int s[N];

void solve()
{
	int cnt;
	char buf[10];
	for(int i = 0; i < n; ++ i) {
		read(a[i]);
		scanf("%d", &cnt);
		s[i] = 0;

		for( ; cnt --; ) {
			scanf("%s", buf);
			int x = convert(buf);
			s[i] |= (1 << x);
		}
	}
	int flag = true;
	for(int t = 0; t < (1 << 7); ++ t) {
		long long tmp = 0;
		for(int i = 0; i < n; ++ i) {
			if ((s[i] | t) == t) {
				tmp += a[i];
			}
		}
		int x = 0;
		for(int tmp = t; tmp; tmp -= tmp & -tmp)
			++ x;
		if (tmp > x * w) {
			flag = false;
			break;
		}
	}
	cout << (flag ? "Yes" : "No") << endl;
}

int main()
{
	for( ; cin >> n >> w && (n || w); ) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 1256
def solution(x,y):
    ans = ''
    nowx, nowy = 0,0
    preX = [0]*31
    preY = [0]*31
    for i in range(31):
        if nowx < x:
            nowx += 2**(30-i)
            preX[i] = 1
        else:
            nowx -= 2**(30-i)
            preX[i] = -1
        if nowy < y:
            nowy += 2**(30-i)
            preY[i] = 1
        else:
            nowy -= 2**(30-i)
            preY[i] = -1
    for i in range(31):
        if preX[i] == -1 and preY[i] == -1:
            ans += 'L'
        elif preX[i] == 1 and preY[i] == 1:
            ans += 'R'
        elif preX[i] == -1 and preY[i] == 1:
            ans += 'D'
        else:
            ans += 'U'
    return ans
N = int( input())
X = [0]*N
Y = [0]*N
x, y = map( int, input().split())
X[0] = x
Y[0] = y
evod = (x+y)%2
Flag = True
for i in range(1,N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
    if (x+y)%2 != evod:
        Flag = False

if Flag:
    D = [2**i for i in range(30,-1,-1)]
    if evod == 1:
        print(31)
        print(' '.join(map(str,D)))
        for i in range(N):
            print( solution(X[i]+Y[i],X[i]-Y[i]))
    else:
        print(32)
        D.append(1)
        print(' '.join(map(str,D)))
        for i in range(N):
            print( solution(X[i]+Y[i]-1,X[i]-1-Y[i]) + 'R')
else:
    print(-1)

Measured memory_bytes: 3192
h,w,k=map(int,input().split())
c=[0]*h
for i in range(h):
  c[i]=list(str(input()))
l=h+w
ans=0
M = 2#bit探査をしたい時はM=2
def dfs(A):
    global ans
    # 終端条件 --- l 重ループまで回したら処理して打ち切り
    if len(A) == l:
        b=0
        for i in range(h):
          if A[i]==0:
            continue
          else:
            for j in range(w):
              if A[h:l][j]==1 and c[i][j]=='#':
                b+=1
        if b==k:
          ans+=1
        return
    for v in range(M):
        A.append(v)
        dfs(A)
        A.pop() # これが結構ポイント
dfs([])
print(ans)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
	ll a , b ,q;
	scanf("%lld%lld%lld",&a,&b,&q);
	
	vector <ll > s,t;
	//~ for(ll & x  : s)
		//~ scanf("%lld",&x);
	//~ for(ll &x : t)
		//~ scanf("%lld",&x);
	
	for(ll temp, i = 0 ; i < a ; i++)
		scanf("%lld",&temp),s.push_back(temp);
	for(ll temp, i = 0 ; i < b ; i++)
		scanf("%lld",&temp),t.push_back(temp);
		
	//~ for(auto x : s)
		//~ cout << x <<" ";
	//~ puts("");
	//~ for(auto x : t)
		//~ cout << x << " ";
	//~ puts("");
	//~ /*
	while(q--){
		ll x ;
		scanf("%lld",&x);
		ll fl = lower_bound(s.begin(),s.end(),x)-s.begin();
		
		ll tl = lower_bound(t.begin(),t.end(),x)-t.begin();
		//~ cerr << fl << " " << tl << endl;
		ll ans = 0;
		//~ if(s[fl]==t[tl] && x==s[fl])
			//~ ans = 0;
		
		//~ else if(s[fl]==x){
			//~ if(tl){
				//~ ans = min(abs(x-t[tl]),abs(x-t[tl-1]));
			//~ }
			//~ else{
				//~ ans = abs(x-t[tl]);
			//~ }
		//~ }
		//~ else if(t[tl]==x){
			
			//~ if(fl){
				//~ ans = min(abs(x-s[fl]),abs(x-s[fl-1]));
			//~ }
			//~ else{
				//~ ans = abs(x-s[fl]);
			//~ }
			
		//~ }
		//~ else{
		{
			ans = 1e18+90 ;
			if(tl >= b)
				tl--;
			if(fl >= a)
				fl--;
			ll fa= fl , ta = tl;
			
			if(fa)
				fa--;
			if(ta)
				ta--;
				
			
			//~ cout << s[fa] << " " << s[fl] << " " << t[ta] <<" " << t[tl] << endl;
				
			for(auto j : {fa,fl}){
				for(auto y : {ta,tl}){
					ans= min( ans, abs(x-s[j])+abs(s[j]-t[y]));
					ans= min( ans, abs(x-t[y])+abs(t[y]-s[j]));
					//~ cout << ans << endl;
				}
			}
			printf("%lld\n",ans);
			
		}
	}
	//~ */
	return 0;
}


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_N (2000L)
#define MAX_M (2000L)
#define NUM_MOD (1000000007L)

using namespace std;

long mod(long n, long k) { return n % k >= 0 ? n % k : n % k + k; }

long dpss[MAX_N + 1][MAX_M + 1] = {}, acc_dpss[MAX_N + 1][MAX_M + 1] = {};

int main(int argc, char *argv[]) {
  // read inputs
  long N, M, as[MAX_N], bs[MAX_M];
  scanf("%ld %ld", &N, &M);
  for (long i = 0; i < N; i++) {
    scanf("%ld", &as[i]);
  }
  for (long j = 0; j < M; j++) {
    scanf("%ld", &bs[j]);
  }

  // solve dp
  // initialize
  dpss[N][M] = 1;
  acc_dpss[N][M] = 1;
  for (long i = N - 1; i >= 0; i--) {
    acc_dpss[i][M] = acc_dpss[i + 1][M];
  }
  for (long j = M - 1; j >= 0; j--) {
    acc_dpss[N][j] = acc_dpss[N][j + 1];
  }
  // update
  for (long i = N - 1; i >= 0; i--) {
    for (long j = M - 1; j >= 0; j--) {
      if (as[i] == bs[j]) {
        dpss[i][j] = acc_dpss[i + 1][j + 1];
      }
      acc_dpss[i][j] = mod(dpss[i][j] + acc_dpss[i][j + 1] +
                               acc_dpss[i + 1][j] - acc_dpss[i + 1][j + 1],
                           NUM_MOD);
    }
  }
  // printf("dpss:\n");
  // for (long i = 0; i <= N; i++) {
  //   for (long j = 0; j <= M; j++) {
  //     printf("%ld ", dpss[i][j]);
  //   }
  //   printf("\n");
  // }
  // printf("acc_dpss:\n");
  // for (long i = 0; i <= N; i++) {
  //   for (long j = 0; j <= M; j++) {
  //     printf("%ld ", acc_dpss[i][j]);
  //   }
  //   printf("\n");
  // }

  // print ans
  printf("%ld\n", acc_dpss[0][0]);

  return 0;
}


Measured memory_bytes: 62592
#include <stdio.h>

int main(void) {
    int n, count, breakFlg;
    int a[200];
    int i, ret;

    ret = scanf("%d", &n);
    
    for(i = 0; i < n; i++) {
    	ret = scanf("%d", &a[i]);
    }
    
    breakFlg = 0;
    count = 0;
    while(1) {
	    for(i = 0; i < n; i++) {
	    	if(a[i] % 2 != 0) {
	    		breakFlg = 1;
	    		break;
	    	}
	    	a[i] = a[i] / 2;
	    }
	    if(breakFlg) {
	    	break;
	    }
    	
    	// みんな偶数だったので、2で割れた。カウント更新
    	count++;
    }

    printf("%d\n", count);
	
    return 0;
}

Measured memory_bytes: 128
package main

import (
	"fmt"
	"math"
)

func main() {
	// Code for B - Contests
	var N int
	fmt.Scanf("%d", &N)

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

	var P int
	var count1, count2, count3 int
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &P)
		if P <= A {
			count1++
		} else if A < P && P <= B {
			count2++
		} else {
			count3++
		}
	}
	ans := math.Min(float64(count1), math.Min(float64(count2), float64(count3)))
	fmt.Println(ans)

}


Measured memory_bytes: 1836
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n; cin >> n;
	ll s = 0;
	for(ll i = sqrt(n);i >= 1;i--){
		ll j = n / i;
		if(i * j == n){
			s = i + j - 2;
			break;
		}
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    

    long double t,x;
    cin >> t >> x;
    cout << fixed;
    cout << setprecision(10);
    cout << t/ x << endl;
}


Measured memory_bytes: 256
// practice with kaiboy, coached by rainboy
import java.io.*;
import java.util.*;

public class Main extends PrintWriter {
	Main() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		Main o = new Main(); o.main(); o.flush();
	}

	void main() {
		int n = sc.nextInt();
		int[] aa = new int[n];
		int[] bb = new int[n];
		for (int i = 0; i < n; i++) {
			aa[i] = sc.nextInt();
			bb[i] = sc.nextInt();
		}
		aa = Arrays.stream(aa).boxed().sorted().mapToInt($->$).toArray();
		bb = Arrays.stream(bb).boxed().sorted().mapToInt($->$).toArray();
		int a, b;
		if (n % 2 == 1) {
			a = aa[n / 2];
			b = bb[n / 2];
		} else {
			a = aa[n / 2 - 1] + aa[n / 2];
			b = bb[n / 2 - 1] + bb[n / 2];
		}
		println(b - a + 1);
	}
}


Measured memory_bytes: 67140
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()

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

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

void chmin(int &a, int b) { if (a > b) a = b; }

int GCD(int a, int b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }


int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    vector<int> L(N);
    vector<int> R(N);
    
    rep(i, N-1) L[i + 1] = GCD(L[i], A[i]);
    for (int i=(N-1);i>=1;--i) R[i - 1] = GCD(R[i], A[i]);
    int ans = 1;

    rep(i, N) ans = max(ans, GCD(L[i], R[i]));
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>
#include<numeric>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,x,y) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define SUM(a) accumulate(all(a),0LL)
#define scan(x) scanf("%lld",&x)
#define print(x) printf("%lld ",x)
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;

ll n = 0, m = 0, ans = 0, cnt = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok, flag;
ll dx[5] = { 1,-1,0,0,0 }, dy[5] = { 0,0,1,-1,0 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111



int main(void) {
  cin >> n >> m;
  tmp = n / m;
  ll b = tmp;
  b *= tmp;
  b *= tmp;
  ans = b;
  if (m % 2 == 0) {
	ll cnt = 0;
	FOR(i, 1, n + 1) {
	  if (i%m == m / 2) cnt++;
	}
	ll a = cnt;
	a *= cnt;
	a *= cnt;
	ans += a;
  }
  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
INF = float("inf")

start = []
end = []
weight = []
node_cost = [-INF] * N
for _ in range(M):
    a, b, c = map(int, input().split())
    start.append(a - 1)
    end.append(b - 1)
    weight.append(c)

node_cost[0] = 0
for _ in range(N - 1):
    for i in range(M):
        new_cost = node_cost[start[i]] + weight[i]
        if new_cost > node_cost[end[i]]:
            node_cost[end[i]] = new_cost
ans = node_cost[N-1]
cycle = [False] * N
for _ in range(N):
    for i in range(M):
        if cycle[start[i]]:
            cycle[end[i]] = True
        new_cost = node_cost[start[i]] + weight[i]
        if new_cost > node_cost[end[i]]:
            cycle[end[i]] = True
if cycle[N-1]:
    ans = "inf"
print(ans)

Measured memory_bytes: 9452
#include <bits/stdc++.h>
#include <ctime>
#include <sstream>
#define weewoo ios::sync_with_stdio(false);cin.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define ll long long
#define se second
#define fi first
#define ctoi(x) (x-'0')
#define pi (acos(-1))
#define llputin(a,n) for(int i=0;i<n;i++){ll x;cin >> x;a.push_back(x);}
#define iputin(a,n) for(int i=0;i<n;i++){int x;cin >> x;a.push_back(x);}

#define MOD ((ll) 1e9 + (ll) 7)
using namespace std;

ll pw(ll x,ll a){
    if(a==0)
        return 1;
    ll t = pw(x,a/2);
    if(a%2==0)
        return (t*t);
    else
        return (t*t*x);
}

bool prime(int x)
{
    if(x < 2) return false;
        for(int i=2; i<= sqrt(x); i++) {
            if ((x%i) == 0) return false;
        }
    return true;
}

bool cmp(const pair<int , int> &a , const pair<int , int> &b){
    return (a.first < b.first);
}


ll lcm(ll a,ll b){
    return ( a*b/__gcd(a,b));
}

int a[100010][4];
ll dp[100010][4];

int n;
ll solve(int i,int ch){
    if(i==n){
        return 0;
    }
    ll &cur = dp[i][ch];
    if(cur+1)
        return cur;
    cur = 0;
    if(ch!=1){
        cur = max(cur,a[i][1]+solve(i+1,1));
    }
    if(ch!=2){
        cur = max(cur,a[i][2]+solve(i+1,2));
    }
    if(ch!=3){
        cur = max(cur,a[i][3]+solve(i+1,3));
    }
    return cur;
}



int main()
{
    weewoo;
    cin >> n;
    for(int i=0;i<n;i++){
        for(int j=1;j<4;j++){
            cin >> a[i][j];
        }
    }
    memset(dp,-1,sizeof dp);
    cout << solve(0,0) << endl;
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
#define repi(n) for (long long i = 0; i < (n); ++i)
#define repj(n) for (long long j = 0; j < (n); ++j)
#define repk(n) for (long long k = 0; k < (n); ++k)
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(itr) for (auto&& v : (itr))
#define updatemax(t, v) (t = std::max(t, (v)))
#define updatemin(t, v) (t = std::min(t, (v)))

int main() {
  string s;
  cin >> s;
  int n = 0;
  itr(s) n = (n + (v - '0')) % 9;
  cout << (n == 0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3720
import sys
def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

N, X = InputToInt()
A = InputToInt()

P = 0
for i in range(N):
    P += A[i]
    if P > X:
        print(i+1)
        sys.exit()
print(N+1)


Measured memory_bytes: 3060
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n,ans=1e9;
void work(int x,int y)
{
	int s=0;
	while(x)
	{
		s+=x%10;
		x/=10;
	}
	while(y)
	{
		s+=y%10;
		y/=10;
	}
	ans=min(ans,s);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		work(i,n-i);
	}
	cout<<ans;
	return 0;
}

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

using namespace std;

set<int> f(int x) {
  set<int> s;
  if (x == 0) s.insert(0);
  while (x > 0) {
    s.insert(x % 10);
    x /= 10;
  }
  return s;
}

bool has_common(const set<int> &a, const set<int> &b) {
  auto ai = a.begin(), bi = b.begin();
  while (ai != a.end() && bi != b.end()) {
    if (*ai < *bi) ai++;
    else if (*ai > *bi) bi++;
    else return true;
  }
  return false;
}

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

  set<int> D;
  for (int i = 0; i < K; ++i) {
    int d;
    cin >> d;
    D.insert(d);
  }

  while (has_common(D, f(N))) N++;

  cout << N << endl;
}


Measured memory_bytes: 3596
#include <math.h>

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;

ll solve(int n, const vector<int> &a) {
  int itr = 1;
  rep(i, n) if (a[i] == itr)++ itr;

  if (itr == 1)
    return -1;
  else
    return n - (itr - 1);
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);

  cout << solve(n, a) << endl;

  return 0;
}

Measured memory_bytes: 1024
// 何文字ズラすか分からない(1文字ずつズラして"the"が出るまで確認する)シーザー暗号の問題
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0017&lang=jp
#include <iostream>
#include <string>
using namespace std;
int main()
{
	string s;
	while (getline(cin, s))
	{
		// "the"も"this"も"that"も見つからない, 限りループし続ける
		while (s.find("the") == string::npos
			&& s.find("this") == string::npos
			&& s.find("that") == string::npos)
		{
			for (int i=0; i<s.size(); i++)
			{
				if (s[i] == 'z') // zの場合はaにリセット
					s[i] = 'a';
				else if (s[i] >= 'a' && s[i] <= 'z') // アルファベットは1文字ズラす
					s[i]++;
			}
		}
		cout << s << endl;
	}
}

Measured memory_bytes: 1176
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,m,x,l):
    cost = 2**31-1
    f = False
    for i in range(2**n):
        isOK,val = getcost(i,x,l,m)
        if isOK : 
            f = True
            cost = min(cost, val)
    return cost if f else -1
        
def getcost(p,x,l,m):
    flag = 1
    cost = 0
    res = [0]*m
    for i in range(len(l)):
        if (p >> i) & 1:
            cost += l[i][0]
            for j in range(len(res)):
                res[j] += l[i][j+1]
    for i in res:
        if i < x:flag = 0
    return [flag, cost if flag==1 else -1]

n,m,x = mi()
l = mix(n)
print(main(n,m,x,l))

Measured memory_bytes: 9276
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_3_D&lang=jp
# Lexicographical Comparison

from functools import reduce
from collections import deque
import sys
input = sys.stdin.readline


def main():
    n1 = int(input())
    l1  = "".join(map(str,input().split()))
    n2 = int(input())
    l2  = "".join(map(str,input().split()))
    if (l1 >= l2):
        print (0)
    else:
        print(1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 6276
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int p[] = new int[n];
    int count = 0;
    for(int i=0 ; i<n ; i++){
      p[i] = sc.nextInt();
    }
    for(int i=1 ; i<n-1 ; i++){
      if(p[i-1]<p[i] && p[i]<p[i+1]){
        count++;
      }else if(p[i-1]>p[i] && p[i]>p[i+1]){
        count++;
      }
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 21844
(defun func ()
	(let (a b c)
		(setq a (read))
		(setq b (read))
		(setq c (read))
		(cond ((= (mod a 2) 0) 0)
			  ((= (mod b 2) 0) 0)
			  ((= (mod c 2) 0) 0)
		  	  (t (min (* a b) (min (* b c) (* c a)))))))
		  
(princ (func))
(fresh-line)

Measured memory_bytes: 7656
#include<stdio.h>
#include<math.h>
int main(void)
{
    int x,y,num,swap;
    scanf("%d %d",&x,&y);
    if(x<y){
        swap=x;
        x=y;
        y=swap;
    }
    while(1){
        num=x%y;
        if(num==0){
            break;
        }
        x=y;
        y=num;
    }
    printf("%d\n",y);
    return 0;
}


Measured memory_bytes: 2144
N = gets.chomp.to_i
strings = []
N.times { strings.push(gets.chomp) }

strings.map! { |s| s.chars.sort.join("") }
strings.sort!

ans = 0
count = 0
s = ""
strings.each do |str|
  if str == s
    count += 1
    next
  end

  s = str
  ans += count * (count - 1) / 2 if count >= 2
  count = 1
end

ans += count * (count - 1) / 2 if count >= 2
puts ans


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

const int MOD = 1e9+7;

vector<int> combinations;

typedef long long lli;

int power(lli base, int num) {
   lli result = 1;
   while(num) {
       if (num&1)
           (result *= base) %= MOD;
       (base *= base) %= MOD;
       num >>= 1;
   }
   return result;
}

int inverse(int num) {
    return power(num, MOD-2);
}

void cal(int N, int K) {
   
    combinations = vector<int>(N+1, 0);
    combinations[K] = 1;
    for (int i = K+1; i <= N; i++) {
        lli result;
        (result = ((lli)i)*combinations[i-1]) %= MOD;
   //   cout << result << endl;
        (result *= inverse(i-K)) %= MOD;
     //   cout << result << endl;
        combinations[i] = result;
    
   // cout << "C " << i << "," << K << "=" << combinations[i] << endl;
    }
}


int main(){
    int N, K;
    cin >> N >> K;
   
    cal(N, K);

    vector<int> nums(N);
    for (int i = 0; i < N; i++)
        cin >> nums[i];

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

    lli result = 0;
    for (int i = 0; i < N-1; i++) {
        int diff = nums[i+1]-nums[i];

        lli ways = (combinations[N] - combinations[i+1] - combinations[N-i-1]) % MOD;
        (result += (diff*ways) % MOD) %= MOD;
    }

    if (result < 0)
        result += MOD;

    cout << result << endl;

    return 0;
}


Measured memory_bytes: 1024
/*
ID: jerrywcy
TASK: AtCoder Beginner Contest 106 Problem A
LINK: https://abc106.contest.atcoder.jp/tasks/abc106_a
LANG: C++
*/
#include<bits/stdc++.h>

using namespace std;

int a,b;

int main() {
	cin>>a>>b;
	cout<<(a-1)*(b-1)<<endl;
	
}

Measured memory_bytes: 256
/*input
2 100
10 10
*/
#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int fast_ex(int a,int n,int m){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= fast_ex(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

const int N = 1e5+1;
int h[N];
int dp[N];
int n,k;

void solve(){
	 cin >> n >> k;
	 RE(i,n)cin >> h[i];
	 dp[0] = h[0] = dp[1] = 0;
	 dp[2] = abs(h[2]-h[1]);
	 int z = 1;
     for(int i = 3;i <=n;i++){
     	 dp[i] = INF;
         for(int j = max(z,i-k);j < i;j++){
     	 dp[i] = min(dp[j]+abs(h[i]-h[j]),dp[i]);
     	}
     }
     cout << dp[n];
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;//cin >> t;
  WL(t)solve();
  return 0;
}

Measured memory_bytes: 1792
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
        
    ios_base::sync_with_stdio(0);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int x,y;
    cin>>x>>y;
    cout<<x+(y/2)<<endl;
    return 0;
}



Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;


class Program {
    

    internal static void Main(string[] args)
    {
        int[] inp = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        int N = inp[0];
        int M = inp[1];
        int X = inp[2];
        int[] A = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        WriteLine(Math.Min(A.Where(i => i < X).Count(),
                           A.Where(i => i > X).Count()));
    }
}

Measured memory_bytes: 13396
/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#ifdef LOCAL
#include "debug.h"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(x...)
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using ordered_set= tree<T, null_type, 
		less<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
template<class T> 		
using ordered_mset= tree<T, null_type, 
		less_equal<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
		
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	

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

ll ara[mx],dp[mx];	

void solve()
{
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++) cin>>ara[i];
	
	for(int i=1;i<=n;i++) dp[i]=(dp[i-1]+ara[i])%mod;
	
	auto mul=[&](ll a,ll b)
	{
		a%=mod;
		b+=mod;
		b%=mod;
		
		ll ans=a*b;
		ans%=mod;
		
		return ans;
		
	};
	
	ll ans=0;
	
	for(int i=1;i<=n;i++)
	{
		ans+=mul(ara[i],dp[n]-dp[i]);
		ans%=mod;
	}
	
	cout<<ans;
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int testcase=1;
	//cin>>testcase;
	
	for(int i=1;i<=testcase;i++)
	{
		//cout<<"Case "<<i<<": ";
		solve();
	}
	
	#ifdef LOCAL
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	#endif
	
	
	return 0;
}


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

#define FOR(idx, begin, end) for(int idx = (lint)(begin); idx < (lint)(end); ++idx)

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

using namespace std;
typedef long long lint;

const int MOD = 1000000007, INF = 1111111111;
const double EPS = 1e-9;

struct itm { lint w;  lint val; };
bool operator<(itm &lhs, itm &rhs) { return lhs.w < rhs.w; };
bool valcomp(itm &lhs, itm &rhs) { return lhs.val > rhs.val; };

int main() {

	cin.tie(0);

	int N, W;
	cin >> N >> W;

	vector<itm> item(N);
	FOR(i, 0, N) cin >> item[i].w >> item[i].val;
	lint w0 = item[0].w;
	sort(item.begin(), item.end());

	vector<vector<itm>> numw(4);
	for (const auto &ele : item) {
		
		FOR(i, 0, 4) if (ele.w == w0 + i) numw[i].emplace_back(ele);
	}
	itm zero;
	zero.w = 0; zero.val = 0;
	FOR(i, 0, 4) numw[i].emplace_back(zero);
	FOR(i, 0, 4) sort(numw[i].begin(), numw[i].end(),valcomp);

	DMP(numw[0].size());

	lint ans = 0, tmp = 0;
	FOR(i0, 0, numw[0].size())FOR(i1, 0, numw[1].size())FOR(i2, 0, numw[2].size())FOR(i3, 0, numw[3].size()) {
		
		tmp = 0;
		DMP((i0 + i1 + i2 + i3)*w0 + i1 + 2 * i2 + 3 * i3);
		if ((lint)((i0 + i1 + i2 + i3)*w0 + i1 + 2 * i2 + 3 * i3) <= W) {
			FOR(ii0, 0, i0) tmp += numw[0][ii0].val;
			FOR(ii1, 0, i1) tmp += numw[1][ii1].val;
			FOR(ii2, 0, i2) tmp += numw[2][ii2].val;
			FOR(ii3, 0, i3) tmp += numw[3][ii3].val;
			ans = ans < tmp ? tmp : ans;
		}
	}

	cout << ans;
	return 0;
}

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

typedef long long ll;
 
int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int l = a + b;
  int r = c + d;
  string ans;
  if(l<r) ans = "Right";
  if(l==r) ans = "Balanced";
  if(l>r) ans = "Left";
  cout << ans << endl;
  return 0;
}


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

#define ll long long
#define repeat(i, x) for (register ll i = 0; i < x; i++)

int main()
{
  int K;
  cin >> K;
  for (int i = 0; i < K; i++)
  {
    cout << "ACL";
  }
}

Measured memory_bytes: 3584
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    int n, T;
    cin >> n >> T;
    int min_cost = numeric_limits<int>::max();

    for (int i = 0; i < n; i++)
    {
        int c, t;
        cin >> c >> t;
        if (t <= T)
        {
            min_cost = min(min_cost, c);
        }
    }
    if (min_cost == numeric_limits<int>::max())
    {
        cout << "TLE" << endl;
    }
    else
    {
        cout << min_cost << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
int main() {
    int n, s[1000];
    for (std::cin >> n; n != 0; std::cin >> n) {
        double m = 0., d = 0.;
        for (int i = 0; i < n; ++i) {
            std::cin >> s[i];
            m += s[i];
        }
        m /= n;
        for (int i = 0; i < n; ++i) {
            d += (s[i] - m) * (s[i] - m);
        }
        d /= n;
        std::cout << std::fixed << std::setprecision(6)
            << std::sqrt(d) << std::endl;
    }
}



Measured memory_bytes: 3280
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define endl '\n'
#define ll long long
#define P pair<int,int>

const int INF = 1e9;
const int N = 110;
int h,w;

char board[N][N];
int dp[N][N];

signed main() {
    cin >> h >> w;
    rep(i,h) rep(j,w) cin >> board[i][j];
    rep(i,N) rep(j,N) dp[i][j] = INF;

    if(board[0][0] == '#') dp[0][0] = 1;
    else dp[0][0] = 0;

    queue<P> que;
    que.push({0,0});

    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        if(x == h - 1 && y == w - 1) break;

        int add = 0;
        if(x + 1 < h) {
            if(board[x][y] == '.' && board[x + 1][y] == '#') add = 1;
            else add = 0;
            if(dp[x + 1][y] <= dp[x][y] + add);
            else {
                que.push({x + 1, y});
                dp[x + 1][y] = min(dp[x + 1][y], dp[x][y] + add);
            }
        }
        if(y + 1 < w) {
            if(board[x][y] == '.' && board[x][y + 1] == '#') add = 1;
            else add = 0;
            if(dp[x][y + 1] <= dp[x][y] + add);
            else {
                que.push({x, y + 1});
                dp[x][y + 1] = min(dp[x][y + 1], dp[x][y] + add);
            }
        }
    }

    cout << dp[h - 1][w - 1] << endl;
}

Measured memory_bytes: 256