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

vector<int> Z_Algorithm(vector<int> &s) {
    vector<int> ret(s.size());
    for (int i = 1, j = 0; i < s.size(); i++) {
        if (i + ret[i-j] < j + ret[j]) {
            ret[i] = ret[i-j];
        } else {
            int k = max(0, j + ret[j] - i);
            while (i+k < s.size() && s[k] == s[i+k]) k++;   
            ret[i] = k; j = i;
        }
    }
    ret[0] = s.size();
    return ret;
}


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> a(n), b(n), c(3*n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) {
        c[i] = b[i] ^ b[(i+1) % n];
        c[i+n] = c[i+n*2] = a[i] ^ a[(i+1) % n];
    }
    auto ret = Z_Algorithm(c);
    for (int k = 0; k < n; k++) {
        if (ret[n+k] >= n) {
            cout << k << " " << (b[0] ^ a[k]) << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 9728
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
	    long[] V = new long[N];
	    for (int i = 0; i < N; ++i)
	    	V[i] = sc.nextLong();

	    long res = 0;
	    for (int p = 0; p <= Math.min(K, N); ++p) {
	        for (int q = 0; p + q <= Math.min(K, N); ++q) {
	            List<Long> v = new ArrayList<>();
                long cur = 0;
	            for (int i = 0; i < p; ++i) { v.add(V[i]); cur += V[i];}
	            for (int i = 0; i < q; ++i) { v.add(V[N-1-i]) ; cur += V[N-1-i];}
	               
	            Collections.sort(v);
	            for (int i = 0; i < Math.min(K - p - q, (int)v.size()); ++i) {
	                if (v.get(i) < 0) cur -= v.get(i);
	            }
	            res = Math.max(res, cur);
	        }
	    }
	    out.println(res);
		
		out.close();
	}



static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}
}



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

int n;
ll b[100001];

ll find(int s) {
	ll res = 0;
	for (int i = s; i > 0; i = i & (i - 1))
		res = max(res, b[i]);
	return res;
}

void update(int s, ll val) {
	for (int i = s; i <= n; i += (i & -i))
		b[i] = max(b[i], val);
}

int main()
{
	cin.sync_with_stdio(false);
	cin >> n;
	ll sum = 0;
	for (int i = 0, x; i < n; i++) {
		cin >> x;
		sum += x;
		update(x, find(x - 1) + x);
	}
	printf("%lld\n", sum - find(n));
	return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	int mx = (n - 1) * (n - 2) / 2;
	if (mx < k) {
		cout << -1 << endl;
		return 0;
	}
	vector<P> ans;
	rep(i, n - 1) ans.push_back(P(i + 1, n));
	int add = mx - k;
	vector<P> edge;
	rep(i, n - 1)rep(j, i) edge.push_back(P(i + 1, j + 1));
	rep(i, add) ans.push_back(edge[i]);
	cout << ans.size() << endl;
	rep(i, ans.size()) {
		cout << ans[i].first << ' ' << ans[i].second << endl;
	}
	return 0;
}


Measured memory_bytes: 384
// +build ignore
package main

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

func solve(sc *scanner, wr *bufio.Writer) int {
	N := sc.i()

	switch N % 10 {
	case 2, 4, 5, 7, 9:
		fmt.Println("hon")
	case 0, 1, 6, 8:
		fmt.Println("pon")
	default:
		fmt.Println("bon")
	}

	return 0
}

func main() {
	sc := newScanner(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	ret := solve(sc, wr)
	wr.Flush()
	os.Exit(ret)
}

// I/O
type scanner struct {
	sc *bufio.Scanner
}

func newScanner(input io.Reader) *scanner {
	sc := bufio.NewScanner(input)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &scanner{sc}
}

func (s *scanner) s() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *scanner) i() int {
	i, e := strconv.Atoi(s.s())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *scanner) f() float64 {
	f, e := strconv.ParseFloat(s.s(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *scanner) bs() []byte {
	return []byte(s.s())
}

func (s *scanner) is(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.i()
	}
	return res
}

func (s *scanner) fs(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.f()
	}
	return res
}


Measured memory_bytes: 1756
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    string s[3] = {"Sunny","Cloudy","Rainy"};
    string t;
    cin>>t;
    int a = -1;
    for(int i=0;i<3;i++) if(s[i]==t)a = i;
    cout<<s[(a+1)%3]<<endl;
    return 0;
}


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

#define deb(x)        cerr << #x << " = " << x << "\n";
#define deb2(x, y)    cerr << #x << " = " << x << ", " << #y << " = " << y << "\n";
#define deb3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << "\n";

#define pb push_back
#define mp make_pair
#define F  first
#define S  second

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;  
const ll MOD = 1e9 + 7;

void solve() {
    ll n;
    cin >> n;
    vector<int> dp(n+1);
    dp[0] = 1;
    for (int i = 3; i <= n; ++i) {
        for (int j = 0; j <= i-3; ++j) {
            dp[i] += dp[j];
            dp[i] %= MOD;
        }
    }
    cout << dp[n];
}

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

    ll tc = 1;
    //cin >> tc;

    while(tc--) {
        solve();
        cout << '\n';
    }

    return 0;
}


Measured memory_bytes: 3588
main :: IO()
main = do
    a <- readLn
    b <- readLn
    c <- readLn
    x <- readLn
    print $ gohyakuen a b c x



--500円玉の枚数を１つずつマッチさせて、hyakuenを呼ぶ
gohyakuen :: Int -> Int -> Int -> Int -> Int
gohyakuen maisuu500 maisuu100 maisuu50 coinSum
    | maisuu500 == 0				= hyakuen maisuu100 maisuu50 coinSum
    | coinSum < 500					= hyakuen maisuu100 maisuu50 coinSum
    | otherwise						= hyakuen maisuu100 maisuu50 coinSum+ gohyakuen (maisuu500 - 1) maisuu100 maisuu50 (coinSum - 500)


--100円玉の枚数を一つずつマッチさせて、gojuuennを呼ぶ。
hyakuen :: Int -> Int -> Int -> Int
hyakuen maisuu100 maisuu50 coinSum
    | maisuu100 == 0			= gojuuen maisuu50 coinSum
    | coinSum < 100				= gojuuen maisuu50 coinSum
    | otherwise					= gojuuen maisuu50 coinSum + hyakuen (maisuu100 - 1) maisuu50 (coinSum - 100)


--50円玉の枚数と残り残高　表現できるなら1,表現できないなら0を返す。
gojuuen :: Int -> Int -> Int
gojuuen maisuu coinSum = if (a && b) then 1 else 0
    where a = (mod coinSum 50 == 0)
          b = (50 * maisuu >= coinSum)





Measured memory_bytes: 508
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

typedef long long int ll;

int main () {
    ll x; cin >> x;
    ll ans = 0;
    ll a = x / 500;
    x -= (a * 500);
    ans += (a * 1000);
    ll b = x / 5;
    ans += (b * 5);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[100100];
	int n;
	cin>>n;
	int i=1;
	while(n--){
		cin>>a[i];
		i++;
	}
	int m;
	cin>>m;
	while(m--){
		int p,x;
		cin>>p>>x;
		int c; 
		c=a[p];
		a[p]=x;
		int sum=0;
		for(int j=1;j<i;j++){
			sum+=a[j];
		}
		cout<<sum<<endl;
		a[p]=c;
	}
}

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

long long asd[100005];
long long dp[100005];
int z,x;

long long rekur(int a)
{
	if(a==z)return 0;
	if(dp[a]!=-1)return dp[a];
	dp[a]=INT_MAX;
	long long temp;
	for(int q=1;q<=x;q++)
	{
		if(a+q<=z)
		{
			temp=asd[a+q]-asd[a];
			if(temp<0)temp=-temp;
			dp[a]=min(dp[a],temp+rekur(a+q));
		}
	}
	return dp[a];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	memset(dp,-1,sizeof(dp));
	cin>>z>>x;
	for(int q=1;q<=z;q++)
	cin>>asd[q];
	long long ans=rekur(1);
	cout<<ans<<endl;
}

Measured memory_bytes: 6528
#include<stdio.h>

char inp[128][128];

int main (void) {
	int h, w, i;
	scanf (" %d %d", &h, &w);
	for (i = 0; i < h; i++) {
		scanf (" %s", &inp[i]);
	}
	for (i = 0; i < h; i++) {
		printf ("%s\n%s\n", inp[i], inp[i]);
	}
	return 0;
}

Measured memory_bytes: 128
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    int m = Integer.parseInt(sc.next());
    int[] k = new int[m];
    int[][] s = new int[m][];
    int[] p = new int[m];
    for(int i=0;i<m;i++){
      k[i] = Integer.parseInt(sc.next());
      s[i] = new int[k[i]];
      for(int j=0;j<k[i];j++){
        s[i][j] = Integer.parseInt(sc.next())-1;
      }
    }
    for(int i=0;i<m;i++){
      p[i] = Integer.parseInt(sc.next());
    }
    int res = 0;
    outer:for(int i=0;i<(1<<n);i++){
      for(int j=0;j<m;j++){
        int count = 0;
        for(int l=0;l<k[j];l++){
          if(((i>>s[j][l]) & 1)==1){
            count++;
          }
        }
        if(count%2!=p[j]){
          continue outer;
        }
      }
      res++;
    }
    System.out.println(res);
    
  }
}


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

int ct, n, s;

void sum(int m, int i, int n){
  if (n == 0 && m == s){
    ct++;
    return;
  }
  if (n == 0 || i == 10)  return;
  sum(m, i + 1, n);
  sum(m + i, i + 1, n - 1);
}

int main()
{
  while (cin >> n >> s, n){
    ct = 0;
    sum(0, 0, n);
    cout << ct << endl;
  }
  return (0);
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
int main(){
  std::string ans = "CODEFESTIVAL2016";
  std::string input;
  std::cin >> input;
  int cont=0;
  for(int i=0;i<ans.size();i++){
    if(ans[i] != input[i]){
      cont++;
    }
  }
  std::cout << cont << std::endl;
  return 0;
}


Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


const ll MOD = 998244353;
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}


int n;
const int N = 1e7 + 10;

ll fc[N];
ll bfc[N];

ll cnk(int n, int k) {
    return fc[n] * bfc[k] % MOD * bfc[n - k] % MOD;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
    fc[0] = 1;
    for (int i = 1; i < N; ++i) {
        fc[i] = (fc[i - 1] * i) % MOD;
    }
    bfc[N - 1] = pw(fc[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i) {
        bfc[i] = (bfc[i + 1] * (i + 1)) % MOD;
    }

    cin >> n;
    ll ans = pw(3, n);
    for (int i = n / 2 + 1; i <= n; ++i) {
        ans = (ans - cnk(n, i) * pw(2, 1 + n - i) % MOD + 2 * MOD) % MOD;
    }
    cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 156544
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{   
    int N,T,A; cin>>N>>T>>A;
    vector<double> h(N);
    REP(i,N){
        cin>>h[i];
        h[i]=T-h[i]*0.006;
    }

    int ans=-1;
    double min=1e9;

    REP(i,N){
        double diff=abs(h[i]-A);
        if(diff<min){
            ans=i+1;
            min=diff;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)

int C[20];

// i番目の値をjにする時の誤差のmin
int dp[20001][256];

inline int round(int x){
    int res = x;
    res = min(res, 255);
    res = max(res, 0);
    return res;
}

int main(){
    int n, m;
    int const inf = 1 << 28;
    while (cin >> n >> m && n | m){
        rep(i, m)cin >> C[i];
        rep(i, 20001)rep(j, 256)dp[i][j] = inf;
        dp[0][128] = 0;
        rep(i, n){
            int x; cin >> x;
            rep(j, 256){
                rep(k, m){
                    int next = round(j + C[k]);
                    int diff = x - next;
                    dp[i + 1][next] = min(dp[i + 1][next], dp[i][j] + diff*diff);
                }
            }
        }
        int res = inf;
        rep(i, 256){
            res = min(res, dp[n][i]);
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 21160
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define COUT(x) cout<<(x)<<"\n"

int main(){
    int n;
    cin >> n;
    int ans = 0;
    int count = 0;
    while(1){
        ans += n;
        count++;
        if(ans%360==0){
            break;
        }
    }
    COUT(count);
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    double a = (N-1+2)/2 / double(N);
    cout.precision(7);
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b;
  char op;
  int c;
while(1){
  scanf("%d %s %d",&a,&op,&b);
  if(op=='?')break;
 if(op=='+'){
    c=a+b;
    printf("%d\n",c);
  }
else if(op=='-'){
    c=a-b;
     printf("%d\n",c);
  }
else if(op=='/'){
    c=a/b;
     printf("%d\n",c);
  }
else if(op=='*'){
    c=a*b;
     printf("%d\n",c);
  }

 }
 
return 0;
}

Measured memory_bytes: 600
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

int a[10][10];
signed main(void)
{
	REP(i, 10) REP(j, 10) cin >> a[i][j];

	int ret = 0;
	REP(i1, 10) REP(i2, 10) REP(i3, 10) REP(i4, 10) {
		int tmp = a[a[a[a[0][i1]][i2]][i3]][i4];
		int num[] = {(int)i1, (int)i2, (int)i3, (int)i4, tmp};
		bool flag = false;
		//1??????????????´???
		REP(j1, 5) REP(j2, 10) {
			if(num[j1] == j2) continue;
			int b = 0;
			REP(k, 5) {
				if(j1 == k) b = a[b][j2];
				else b = a[b][num[k]];
			}
			if(!b) flag = true;
		}
		//??\??????????????´???
		REP(j, 4) {
			int n[5];
			REP(k, 5) n[k] = num[k];
			if(n[j] == n[j+1]) continue;
			swap(n[j], n[j+1]);
			int b = 0;
			REP(k, 5) b = a[b][n[k]];
			if(!b) flag = true;
		}
		if(flag) ret++;
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 3100
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn main() {
  input! {
    n: usize, k: usize,
    av: [[usize]; k]
  };

  let mut set = HashSet::new();
  for a in av {
    for b in a {
      set.insert(b);
    }
  }
  let res = n - set.len();
  println!("{}", res);
}


Measured memory_bytes: 2200
H, W, K = [int(x) for x in input().split(' ')]
tab = []
for i in range(H):
    tab.append(input())

have_st = []

def find_pos(row):
    arr = []
    for idx, ch in enumerate(row):
        if ch == '#':
            arr.append(idx)

    return arr

for i in range(H):
    if '#' in tab[i]:
        have_st.append(i)

prev_len = 0
rec_grid = []
st_c = 0
st_r = 0
for idx, row_idx in enumerate(have_st):
    row = tab[row_idx]
    pos = find_pos(row)
    if len(have_st) == 1:
        for c, i in enumerate(pos):
            if c == len(pos) - 1:
                ed_r = row_idx
                ed_c = W-1
                rec_grid.append(((0,st_c), (H-1, ed_c)))
            else:
                ed_r = row_idx
                ed_c = i
                rec_grid.append(((0,st_c), (H-1, ed_c)))
                st_c = i + 1
        break
    if idx != len(have_st) - 1:
        for c, i in enumerate(pos):
            if c == len(pos) - 1:
                ed_r = row_idx
                ed_c = W-1
                rec_grid.append(((st_r,st_c), (ed_r, ed_c)))
            else:
                ed_r = row_idx
                ed_c = i
                rec_grid.append(((st_r,st_c), (ed_r, ed_c)))
                st_c = i + 1

        pass
    else:
        for c, i in enumerate(pos):
            if c == len(pos) - 1:
                ed_r = H-1
                ed_c = W-1
                rec_grid.append(((st_r,st_c), (ed_r, ed_c)))
            else:
                ed_r = H-1
                ed_c = i
                rec_grid.append(((st_r,st_c), (ed_r, ed_c)))
                st_c = i + 1


    st_r = row_idx + 1
    st_c = 0

out_arr = [[None for _ in range(W)] for __ in range(H)]
# print(rec_grid)
for idx, grids in enumerate(rec_grid):
    (st_r, st_c), (ed_r, ed_c) = grids
    for i in range(st_r, ed_r+1):
        for j in range(st_c, ed_c+1):
            out_arr[i][j] = str(idx + 1)

for row in out_arr:
    print((' ').join(row))


Measured memory_bytes: 28092
#include <iostream>
#include <string>

using namespace std;

int main()
{
	string x;

	x.reserve(200000);
	cin >> x;

	int32_t Scount{0}, count{ 0 };
	for (auto i{ 0 }; i < x.size(); ++i) {
		if (x[i] == 'S') {
			++Scount;
		}	
		else {
			if (Scount > 0)
				++count, Scount--;
		}
	}

	cout << x.size() - 2 * count << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
  long n,k;
  cin >> n >> k;
  long sum = 0;
  sum += (n/k)*(n/k)*(n/k);
  if(k%2==0) sum += ((n+k/2)/k)*((n+k/2)/k)*((n+k/2)/k);
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
mod = 10**9 + 7
n = int(input())
a = list(map(int,input().split()))
prefix = list()
sum = 0
for i in a:
	sum += i
	prefix.append(sum)

res = 0
for i in range(0,n):
	t = (a[i] * (prefix[n - 1] - prefix[i])) % mod
	res = (t + res) % mod

print(res)

Measured memory_bytes: 31392
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int ne[N],tot,fi[N],zz[N],Stack[N],cnt,vis[N],a[N],mex[N],x,n,flag[N];
void jb(int x,int y){
	ne[++tot]=fi[x];
	fi[x]=tot;
	zz[tot]=y;
}
void dfs1(int x){
	flag[x]=1;Stack[++cnt]=x;
	for (int i=fi[x];i;i=ne[i])
		if (!flag[zz[i]])dfs1(zz[i]);
		else if (flag[zz[i]]==1){
			tot=cnt;
			for (int i=1;i<=cnt;i++)a[i]=Stack[i],vis[a[i]]=1;
		}
	flag[x]=2;
	cnt--;
}
void dfs2(int x){
	for (int i=fi[x];i;i=ne[i])
		if (!vis[zz[i]])dfs2(zz[i]);
	for (int i=fi[x];i;i=ne[i])
		if (!vis[zz[i]])flag[mex[zz[i]]]=x;
	while (flag[mex[x]]==x)mex[x]++;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		jb(x,i);
	}
	tot=0;
	for (int i=1;i<=n;i++)
		if (!flag[i])dfs1(i);
	if (tot%2==0){
		puts("POSSIBLE");
		return 0;
	}
	memset(flag,0,sizeof flag);
	for (int i=1;i<=tot;i++)dfs2(a[i]);
	for (int i=2;i<=tot;i++)
		if (mex[a[i]]!=mex[a[1]]){
			puts("POSSIBLE");
			return 0;
		}
	puts("IMPOSSIBLE");
}


Measured memory_bytes: 10880
from collections import Counter
n=int(input())
v=list(map(int,input().split()))
v_odd=Counter(v[0::2]).most_common()
v_even=Counter(v[1::2]).most_common()
v_odd.append([0,0])
v_even.append([0,0])
if v_odd[0][0]!=v_even[0][0]:
    print(n-v_odd[0][1]-v_even[0][1])
else:
    print(min((n-v_odd[0][1]-v_even[1][1]),n-v_odd[1][1]-v_even[0][1]))


Measured memory_bytes: 20700
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int dfs(int p, int q, int a, int n, int cur_pro, int prev_d){
		if(n < 0){
			return 0;
		}
		
		if(p == 0 && cur_pro <= a){
			return 1;
		}else if(n == 0){
			return 0;
		}
		
		int sum = 0;
		
		int divide = /* a */ a / cur_pro + 1;
		while(p * divide >= q){
			//System.out.println("[" + n +"]" + " 1 / " + divide);
			if(divide * cur_pro > a){
				divide--;
				continue;
			}else if(n * q < p * divide){
				divide--;
				continue;
			}else if(divide < prev_d){
				break;
			}
			
			final int upper = p * divide - q;
			final int downer = q * divide;
			
			sum += dfs(upper, downer, a, n - 1, cur_pro * divide, divide);
			
			divide--;
		}
		
		return sum;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true){
			StringTokenizer tok = new StringTokenizer(br.readLine());
			final int p = Integer.parseInt(tok.nextToken());
			final int q = Integer.parseInt(tok.nextToken());
			final int a = Integer.parseInt(tok.nextToken());
			final int n = Integer.parseInt(tok.nextToken());
			
			if(p == 0 && q == 0 && a == 0 && n == 0){
				break;
			}
			
			int sum = dfs(p, q, a, n, 1, 0);
			
			System.out.println(sum);
		}
		
	}

}

Measured memory_bytes: 21416
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
int main(){
  ll n;
  cin>>n;
  vector<ll> p(n);
  rep(i,n) cin>>p[i];
  ll min=200001;
  ll ans=0;
  rep(i,n){
    if(p[i]<min){
      min=p[i];
      ans++;
    }
  }
  cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 1792
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;


#define INF (1ll<<60)

int main(int argc, char const *argv[]) {
	int n,x;cin>>n>>x;
	if(x==1||x==2*n-1){
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
	vector<int> res(2*n-1);
	if(n==2){
		cout<<1<<endl;
		cout<<2<<endl;
		cout<<3<<endl;
		return 0;
	}
	if(x==2){
		for(int i=0;i<2*n-1;i++){
			res[(i+n-2)%(2*n-1)]=i+1;
		}
	}
	else{
		res[n-1]=x;
		res[n-2]=x+1;
		res[n-3]=1;
		res[n]=2;
		int p=0;
		for(int i=3;i<x;++i){
			while(res[p]!=0)p++;
			res[p]=i;
		}
		for(int i=x+2;i<2*n;++i){
			while(res[p]!=0)p++;
			res[p]=i;
		}
	}
	for(int i:res)cout<<i<<endl;
	return 0;
}


Measured memory_bytes: 2304
N = int(input())
S = input()

ans = 0
for i in range(1,N):
    cnt = 0
    zenhan = list(set(S[:i]))
    kouhan = list(set(S[i:]))
    for j in zenhan:
        if kouhan.count(j) == 1:
            cnt += 1
    else:
        ans = max(ans,cnt)
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var n = Console.ReadLine().ToInt();
		if(n == 5 || n == 7 || n == 3)
		{
			Console.WriteLine("YES");
		}
		else
		{
			Console.WriteLine("NO");
		
		}
	}

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}


Measured memory_bytes: 13140
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, x = map(int, input().split())
A = list(map(int, input().split()))

total = 0
goal = x * (N - 1)
for i in range(N):
    if i == 0 or i == N - 1:
        total += A[i]
    else:
        total += 2 * A[i]

if total <= goal:
    print(0)
    exit()

ans = 0
if A[0] > x:
    diff = A[0] - x
    ans += diff
    A[0] -= diff
# if A[N - 1] > x:
#     diff = A[N - 1] - x
#     ans += diff
#     A[N - 1] -= diff

for i in range(1, N):
    if A[i - 1] + A[i] > x:
        diff = (A[i - 1] + A[i]) - x
        A[i] -= diff
        ans += diff
print(ans)





Measured memory_bytes: 20360
from math import ceil
from fractions import Fraction
n = int(input())
TA = [list(map(int, input().split())) for _ in range(n)]
tka, aok = 1, 1

for ta in TA:
    t, a = ta
    time = int(ceil(max((Fraction(tka, t), Fraction(aok, a)))))
    tka, aok = time * t, time * a
print(tka+aok)


Measured memory_bytes: 67820
#include <stdio.h>
#include <math.h>

int min_of_common(int a0, int a1, int b0, int b1) {
  if (a0 > a1) return -1;
  if (b0 > b1) return -1;
  if (a0 >= b0 && a0 <= b1) return a0;
  if (b0 >= a0 && b0 <= a1) return b0;
  return -1;
}

int modify(int current, int target, double tax) {
  int testee = current * tax;
  while ((int)(current * tax) < target) current++;
  while ((int)(current * tax) > target) current--;
  return current;
}

int main() {
  int A, B;
  const double tax_a = 0.08, tax_b = 0.1;
  scanf("%d %d", &A, &B);
  const double 
    A0 = (double)A / tax_a,
    A1 = (double)(A + 1) / tax_a,
    B0 = (double)B / tax_b,
    B1 = (double)(B + 1) / tax_b;
  const int
    iA0 = modify(ceil(A0), A, tax_a),
    iA1 = modify(ceil(A1), A, tax_a),
    iB0 = modify(ceil(B0), B, tax_b),
    iB1 = modify(ceil(B1), B, tax_b);
  printf("%d\n", min_of_common(iA0, iA1, iB0, iB1));
  return 0;
}


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

using namespace std;

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

typedef long long ll;
typedef pair<ll,ll> p;


int main()
{
  int n;
  cin >> n;
  vector<p> v(n, {0, 0});
  for(int i = 0; i < n; i++)
  {
    cin >> v[i].first;
  }

  int res = 0;
  for(int i = 0; i < n;)
  {
    if(i == 1) {
      cout << res << endl;
      return 0;
    }
    else
    {
      if(v[i].second == 1)
      {
        cout << -1 << endl;
        return 0;
      }
      v[i].second = 1;
      res++;
      i = v[i].first - 1;
    }
  }
}

Measured memory_bytes: 1920
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		
		ans += (b - a + 1);
	}
	
	cout << ans << endl;
	return 0;
}

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

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

  // int型の2次元配列(n×2要素の)の宣言
  vector<vector<int>> data(n, vector<int>(2));

  // 入力 
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> data.at(i).at(j);
    }
  }
  int count = 0;
  
  for (int i = 0; i < n; i++) {

      if (sqrt(pow(data.at(i).at(0),2)+pow(data.at(i).at(1),2)) <= d) {
        count++;
      }

    }
  cout << count << endl;

}


Measured memory_bytes: 14332
#include <bits/stdc++.h>
using namespace std;
#include<vector>
 int main()
   {
    int AC=0,WA=0,TLE=0,RE=0;
    int n;
    cin>>n;
    string s;
    while(n--)
      {
        cin>>s;
       if(s=="AC"){AC++;}
       if(s=="WA"){WA++;}
       if(s=="TLE"){TLE++;}
       if(s=="RE"){RE++;}
      }
      cout<<"AC x " <<AC<<endl ;
      cout<<"WA x " <<WA<<endl ;
      cout<<"TLE x " <<TLE<<endl ;
      cout<<"RE x " <<RE<<endl ;
   }

Measured memory_bytes: 3624
#include<forward_list>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<iterator> 
#include<sstream>
#include<fstream>
#include<istream>
#include<utility>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<list>
#include<map> 
#include<set>
#define NinjaTurtle ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define infile freopen(".txt", "r", stdin);
#define outfile freopen(".txt", "w", stdout);
#define all(v) v.begin(),v.end()
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define ll long long 
#define endl "\n"
using namespace std;
int frq[10];
int main()
{
	NinjaTurtle
		int s, w;
	cin >> s >> w;
	if (w >= s)cout << "unsafe";
	else cout << "safe" << endl;

}

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

bool FIND(string S, string T){
	if(S.find(T) == string::npos){
		return false;
	} else {
		return true;
	}
}

int main(){
    int N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--; B--; C--; D--;
    
    bool ans = true;
    for(int i = A; i < max(C, D); i++){
        if(S.substr(i, 2) == "##"){
           ans = false;
           break;
        }
    }
    if(ans && C > D){
        string s = S.substr(B - 1, abs(D - B) + 3);
        if(FIND(s, "...")){
            ans = true;
        }else{
            ans = false;
        }
    }
    cout << ((ans) ? "Yes" : "No") << endl;
}

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

int main(void) {
  int n;
  cin >> n;
  long long int sum = 0;
  for (int i = 1; i <= n; i++)
    if ((i % 3) != 0 && (i % 5) != 0)
      sum += i;

  cout << sum << endl;
}


Measured memory_bytes: 3192
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <queue>
#include <sstream>
#include <cmath>
#include <functional>
#include <climits>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(s,i,n) for(int i=s;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define skip(i,n,p) for(int i=0;i<n;i+=p)
#define all(a)  (a).begin(),(a).end()
#define int64 long long
#define debug cerr << __FILE__ << ":" << __LINE__ << endl;
#define INF 2147483647

struct Init {
    Init() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
        cout << fixed;
        // setw(6) << setfill('0')
    }
} init;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {
    for(int i = 0; i < (int) v.size(); i++) {
        ostr << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return ostr;
}

template <typename _K, typename _V>
ostream& operator << (ostream& ostr, const map<_K, _V>& v) {
    ostr << "{";
    for (auto iter = v.begin(); iter != v.end(); ++iter) {
        ostr << (*iter).first << ": " << (*iter).second << ", ";
    }
    ostr << "}";
    return ostr;
}

template <typename _K>
ostream& operator << (ostream& ostr, const set<_K>& v) {
    for (auto iter = v.begin(); iter != v.end(); ++iter) {
        ostr << *iter << (iter != v.end() ? " " : "");
    }
    return ostr;
}

template <typename _K, typename _V>
ostream& operator << (ostream& ostr, const pair<_K, _V>& v) {
    ostr << "(" << v.first << ", " << v.second << ")";
    return ostr;
}

vector<string> split(const string &s, char delim) {
    vector<string> result;
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
        if (!item.empty()) {
            result.push_back(item);
        }
    }
    return result;
}

int main() {
    int n, k; cin >> n >> k;
    vector<int> L(n); rep(i, n) cin >> L[i];

    int ans = 0;
    rep(i, n) if (L[i] >= k) ans++;

    cout << ans << endl;
}


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

int ans[100010],N,a;

int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		cin>>a;
		ans[a] = i;
	}
	for(int i=1;i<=N;i++) cout<<ans[i]<<" ";
	return 0;
} 

Measured memory_bytes: 1152
#include <bits/stdc++.h>
//#include <math>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
// #define fore(i,a) for(auto &i:a)
// #define all(x) (x).begin(),(x).end()
// #pragma GCC optimize ("-O3")
// using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
// typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
// template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
// template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
 
using namespace std;
 
int main(void)
{
  int k,s;
  cin>>k>>s;
  
  int count=0;
  
  rep(x,0,k+1){
    rep(y,0,k+1){
      if((s-(x+y))>=0 && (s-(x+y))<=k) count++;
    }
  }
  
  cout<<count<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ll long long 
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define ff first
#define ss second
#define vi vector<ll>
#define vii vector<vector<ll>>
#define vpi vector<pii>
#define mod 1000000007
#define MOD 1000000007
#define full(a) a.begin(),a.end()
#define inf INT_MAX
#define minf INT_MIN
#define dd double
#define fori(x,n) for(ll i=x;i<n;i++)
#define modd 998244353
#define umap unordered_map<ll,ll>
#define mmap map<ll,ll>
#define mm 100000000


int32_t main() 
{ 
  
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif


    
    ll t;
    t=1;
    // cin>>t;
    while(t--){
      ll n;
      cin>>n;
      ll a=0,b=0,c=0,d=0;

      while(n--){
        string s;
        cin>>s;
        if(s=="AC")a++;
        else if(s=="WA")b++;
        else if(s=="TLE")c++;
        else d++;
      }

      cout<<"AC"<<" x "<<a<<"\n";
      cout<<"WA"<<" x "<<b<<"\n";
      cout<<"TLE"<<" x "<<c<<"\n";
      cout<<"RE"<<" x "<<d<<"\n";








      

       




     

    






      
  
    }





return 0;
}     



Measured memory_bytes: 3668
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    long long  l,r,m=1000000000;
    cin >>l>> r;
    
    for (long long  i = l; i <r ; i++) {
        for (long long  j = l+1; j <=r ; j++) {
            long long  a=(i*j)%2019;
            m=min(a,m);
            if (a == 0) {
                cout << m << endl;
                return 0;
            }
        }
    }
    cout << m << endl;
}


Measured memory_bytes: 256
//============================================================================
// Name        : abc056_A.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	char a, b;

	cin >> a >> b;

	if (a == 'H' && b == 'H') {
		cout << 'H';
	} else if (a == 'H' && b == 'D') {
		cout << 'D';
	} else if (a == 'D' && b == 'D') {
		cout << 'H';
	} else if(a == 'D' && b == 'H') {
		cout << 'D';
	}

	return 0;
}


Measured memory_bytes: 256
import Data.List

main :: IO ()
main = do
  n <- readLn
  vs <- map read . words <$> getLine
  print $ solve n vs

solve :: Int -> [Int] -> Int
solve n vs = solve' n (count as) (count bs)
  where
    (as, bs) = deal vs

deal :: [Int] -> ([Int], [Int])
deal [] = ([], [])
deal (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = deal zs

solve' :: Int -> [(Int, Int)] -> [(Int, Int)] -> Int
solve' n [a0] [b0]
  | ka0 == kb0 = n - va0
  | ka0 /= kb0 = n - va0 - vb0
  where
    (ka0, va0) = a0
    (kb0, vb0) = b0
solve' n [a0] (b0:b1:bs)
  | ka0 == kb0 = n - va0 - vb1
  | ka0 /= kb0 = n - va0 - vb0
  where
    (ka0, va0) = a0
    (kb0, vb0) = b0
    (kb1, vb1) = b1
solve' n (a0:a1:as) [b0]
  | ka0 == kb0 = n - va1 - vb0
  | ka0 /= kb0 = n - va0 - vb0
  where
    (ka0, va0) = a0
    (kb0, vb0) = b0
    (ka1, va1) = a1
solve' n (a0:a1:as) (b0:b1:bs)
  | ka0 /= kb0             = n - va0 - vb0
  | va0 + vb1 >= va1 + vb0 = n - va0 - vb1
  | va0 + vb1 <  va1 + vb0 = n - va1 - vb0
  where
    (ka0, va0) = a0
    (kb0, vb0) = b0
    (ka1, va1) = a1
    (kb1, vb1) = b1

count :: [Int] -> [(Int, Int)]
count = reverse . sortOn snd . map (\xs -> (head xs, length xs)) . group . sort

Measured memory_bytes: 45436
/**
 *    author: apurba_debnath
**/
#include <bits/stdc++.h>


#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;


using namespace std;

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

    string r, b, u;
    int x, y;
    cin >> r >> b >> x >> y >> u;
    if (u == r)
        cout << x-1 << " " << y;
    else
        cout << x << " " << y-1;

    return 0;
}


Measured memory_bytes: 3616
#include <stdio.h>
#include <string.h>
int main(void)
{
    int h,w;
    scanf("%d%d", &h,&w);
    for(int i=0; i<h; i++)
    {
        char c[w+1];
        scanf("%s", c);
        for(int j=0; j<w; j++) printf("%c", c[j]);
        printf("\n");
        for(int j=0; j<w; j++) printf("%c", c[j]);
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String[] a = sc.next().split(",");
			int s = Integer.parseInt(a[0]);
			double w = Double.parseDouble(a[1]);
			double h = Double.parseDouble(a[2]);

			if(w/h/h >= 25){
				System.out.println(s);
			}
		}
	}
}

Measured memory_bytes: 25748
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define pb push_back
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
#define umap unordered_map
#define all(x) x.begin(), x.end()
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
lli M = 1e9 + 7;
lli power(lli x, lli y){
    lli res = 1;
    x = x%M;
    while (y > 0) {
        if (y & 1)
            res = (res*x)%M ;
        y = y>>1;
        x = (x*x)%M ;
    }
    return res%M;
}
lli solve(){
    lli n, k;
    cin>>n>>k;
    vll h(n);
    loop(i, 0, n)
        cin>>h[i];
    vll dp(n, 1e16);
    dp[0] = 0;
    loop(i, 1, n){
        loop(j, max(0ll, i-k), i)
            dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
    }
    cout<<dp[n-1]<<"\n";
    return 0;
}
int main(){
    fastio;
    lli t;
	// cin>>t;
    t = 1;
    while(t>0){ 
        t--;
        solve();
    }
}

Measured memory_bytes: 4776
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e5+10,mod=1e9+7,inf=0x3f3f3f3f;
int n,m,k,t;
int a[maxn],b[maxn];
vector<pii>q;
multiset<pii>p;
int main()
{
    int i,j;
  	//freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]),
        q.push_back({a[i],i}),
        q.push_back({b[i],i});
    sort(q.begin(),q.end());
    ll now=0;
    for(i=0;i<n-2;i++)
        p.insert({q[i].second,q[i].first}),
        now+=q[i].first;
    ll ret=min(accumulate(a+1,a+n+1,0LL),accumulate(b+1,b+n+1,0LL));
    for(i=1;i<=n;i++)
    {
        int cur=n-3,f=0,g=0,h=0;
        if(p.count({i,a[i]}))
            p.erase(p.lower_bound({i,a[i]})),
            ++cur,
            p.insert({q[cur].second,q[cur].first}),
            now+=q[cur].first-a[i],f=1;
        if(p.count({i,b[i]}))
            p.erase(p.lower_bound({i,b[i]})),
            ++cur,
            p.insert({q[cur].second,q[cur].first}),
            now+=q[cur].first-b[i],g=1;
        if(p.count({i,a[i]}))
            p.erase(p.lower_bound({i,a[i]})),
            ++cur,
            p.insert({q[cur].second,q[cur].first}),
            now+=q[cur].first-a[i],h=1;
        ret=min(ret,now+a[i]+b[i]);
        if(h)
            p.erase(p.lower_bound({q[cur].second,q[cur].first})),
            p.insert({i,a[i]}),
            now+=a[i]-q[cur].first,cur--;
        if(g)
            p.erase(p.lower_bound({q[cur].second,q[cur].first})),
            p.insert({i,b[i]}),
            now+=b[i]-q[cur].first,cur--;
        if(f)
            p.erase(p.lower_bound({q[cur].second,q[cur].first})),
            p.insert({i,a[i]}),
            now+=a[i]-q[cur].first,cur--;
    }
    printf("%lld\n",ret);
  	return 0;
}


Measured memory_bytes: 7280
#include <cstdio>
#include <algorithm>
using namespace std;
int a[3000], b[3000];
int dp[5000];
int main() {
    int n, t, s; scanf("%d%d%d",&n,&t,&s);
    for (int i=0; i<n; i++) scanf("%d%d",&a[i],&b[i]);
    int res=0;
    for (int i=0; i<n; i++) {
        for (int j=t-b[i]; j>=0; j--) {
            if (j<s&&s<j+b[i]) continue;
            dp[j+b[i]]=max(dp[j+b[i]], dp[j]+a[i]);
            res=max(res,dp[j+b[i]]);
        }
    }
    printf("%d\n",res);
}

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

typedef pair<int, int> ii;

int A[25];
int B[25];

int perm[25];

const int INF = 1012345678;

long long nxs(long long r){
    long long ls1 = r&(-r);
    long long rest = r+ls1;
    return rest|(((rest^r)/ls1) >> 2);
}

int main(){
    int N;
    scanf("%d", &N);

    for(int i = 0; i < N; i ++){
        scanf("%d", &A[i]);
    }

    for(int i = 0; i < N; i ++){
        scanf("%d", &B[i]);
    }

    int ans = INF;
    int noBits = (N+1)>>1;
    vector<ii> set1 = vector<ii>();
    vector<ii> set2 = vector<ii>();
    for(int i = (1<<noBits)-1; i < (1<<N); i = nxs(i)){
        //printf("i=%d\n", i);
        set1.clear();
        set2.clear();
        for(int j = 0; j < N; j ++){
            if(i&(1<<j)){
                // Place in first set, parity is even (0-indexed)
                if((j&1) == 0){
                    set1.push_back(ii(A[j], j));
                }else{
                    set1.push_back(ii(B[j], j));
                }
            }else{
                // Place in second set, parity is odd
                if((j&1) == 0){
                    set2.push_back(ii(B[j], j));
                }else{
                    set2.push_back(ii(A[j], j));
                }
            }
        }

        sort(set1.begin(), set1.end());
        sort(set2.begin(), set2.end());

        bool boleh = true;
        for(int j = 0; j < (int)set2.size(); j ++){
            //printf("set1[%d]=ii(%d, %d), set2[%d]=ii(%d, %d)\n", j, set1[j].first, set1[j].second, j, set2[j].first, set2[j].second);
            if(set1[j].first > set2[j].first){
                boleh = false;
                break;
            }

            if( ((N&1) == 0) && j == (int)set2.size()-1 ){
                break;
            }

            if(set1[j+1].first < set2[j].first){
                boleh = false;
                break;
            }
        }

        if(boleh){
            for(int j = 0; j < (int)set2.size(); j ++){
                perm[j<<1] = set1[j].second;
                perm[(j<<1)|1] = set2[j].second;
            }
            if(N&1){
                perm[N-1] = set1[set2.size()].second;
            }

            int inv = 0;
            for(int j = 0; j < N; j ++){
                for(int k = j+1; k < N; k ++){
                    if(perm[j] > perm[k]){
                        inv ++;
                    }
                }
            }

            ans = min(ans, inv);
        }
    }

    if(ans == INF){ans = -1;}
    printf("%d", ans);
    return 0;
}


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

namespace ConsoleApp7
{
	class Program
	{
		static void Main(string[] args)
		{
			var dice = Console.ReadLine().Split(' '); //1~6面の数字
			int num = int.Parse(Console.ReadLine()); 
			string top = dice[0]; //開始位置,上
			string front = dice[1];
			string right = dice[2];
			string left = dice[3];
			string back = dice[4];
			string bottom = dice[5];

			for (int i = 0; i < num; i++)
			{
				var tf = Console.ReadLine().Split(' ');
				var t = tf[0]; //上面
				var f = tf[1]; //正面
				string r = "";

				if(t == top)
				{
					if(f == front)
					{
						r = right;
					}
					else if(f == right)
					{
						r = back;
					}
					else if(f == back)
					{
						r = left;
					}
					else if(f == left)
					{
						r = front;
					}
				}

				if (t == front)
				{
					if (f == bottom)
					{
						r = right;
					}
					else if (f == right)
					{
						r = top;
					}
					else if (f == top)
					{
						r = left;
					}
					else if (f == left)
					{
						r = bottom;
					}
				}

				if (t == right)
				{
					if (f == top)
					{
						r = front;
					}
					else if (f == front)
					{
						r = bottom;
					}
					else if (f == bottom)
					{
						r = back;
					}
					else if (f == back)
					{
						r = top;
					}
				}

				if (t == left)
				{
					if (f == top)
					{
						r = back;
					}
					else if (f == back)
					{
						r = bottom;
					}
					else if (f == bottom)
					{
						r = front;
					}
					else if (f == front)
					{
						r = top;
					}
				}

				if (t == back)
				{
					if (f == top)
					{
						r = right;
					}
					else if (f == right)
					{
						r = bottom;
					}
					else if (f == bottom)
					{
						r = left;
					}
					else if (f == left)
					{
						r = top;
					}
				}

				if (t == bottom)
				{
					if (f == front)
					{
						r = left;
					}
					else if (f == left)
					{
						r = back;
					}
					else if (f == back)
					{
						r = right;
					}
					else if (f == right)
					{
						r = front;
					}
				}

				Console.WriteLine(r);
			}
		}
	}
}



Measured memory_bytes: 15732