akhauriyash/Code-Regression huggingface dataset:
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s, n, node):
    # 頂点が探索済みかどうかのチェック配列
    check = [False for _ in range(n)]
    check[s] = True
    # 次見る頂点を格納するキュー
    queue = deque([s])
    visited_num = 1

    # 問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color = [-1 for _ in range(n)]
    color[s] = 0

    while visited_num < n:
        # グラフが全連結ではない場合
        if len(queue) == 0:
            # 空配列を返す
            # 現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex = queue.popleft()
        # インデックスがない場合は
        for next_vertex in node[now_vertex]:

            if check[next_vertex] == True:
                continue

            queue.append(next_vertex)
            check[next_vertex] = True

            # 問題固有の計算
            color[next_vertex] = color[now_vertex]+1
            visited_num += 1

    return color


mod = 10**9+7
# n=int(input())
# n,m=list(map(int,input().split()))
# a=list(map(int,input().split()))
def ceil(x, y): return (x+y-1)//y
def input_list(): return list(map(int, input().split()))


def buy(buy_cost, sell_cost, money):
    return money % buy_cost+(money//buy_cost)*sell_cost


n = int(input())
a = input_list()

mon = 1000
i = 0
while i < n:
    # print(i)
    for j in range(i+1, n):
        if a[j] > a[i]:
            mon = buy(a[i], a[j], mon)
            #print(i, ":", j, "->", mon)
            i = j-1
            break
        if a[j] <= a[i]:
            break
    i += 1


print(mon)


Measured memory_bytes: 9584
n = int(input())
a = list(map(int, input().split()))

a2 = []
for i in range(n):
    a2.append((a[i], i))
a2.sort(reverse=True)

dp = [[-1] * n for _ in range(n)]
for i2 in range(n-1, -1, -1):
    a, i = a2[i2]

    for s in range(i2+1):
        if i2 == n-1:
            dp[i2][s] = a * abs(s-i)
        else:
            dp[i2][s] = max(dp[i2+1][s+1] + a * abs(s - i),
                            dp[i2+1][s] + a * abs(n-1-i2+s - i))

print(dp[0][0])

Measured memory_bytes: 100304
n=int(input())

l=[[0 for i in range(10)] for j in range(10)]

for i in range(n+1):
  i=str(i)
  l[int(i[0])][int(i[-1:])]+=1

ans=0

for i in range(1,10):
  for j in range(1,10):
    ans+=l[i][j]*l[j][i]
print(ans)
  

Measured memory_bytes: 9172
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin>>n;
  vector<tuple<int,int>> vp, vp2;
  REP(i,n) {
    int l,r;
    cin>>l>>r;
    vp.emplace_back(l,r);
    vp2.emplace_back(r,l);
  }
  sort(ALL(vp));
  sort(ALL(vp2));
  auto itr = begin(vp);
  auto itr2 = begin(vp2);
  ll ans = 0;
  FOR(i,-100000,100000) {
    for (; itr != end(vp); ++itr) {
      int l,r;
      tie(l,r) = *itr;
      if (l > i) break;
    }
    for (; itr2 != end(vp2); ++itr2) {
      int l,r;
      tie(r,l) = *itr2;
      if (r > i) break;
    }
    ll right = end(vp) - itr;
    ll left = itr2 - begin(vp2);
    if (i < 0) {
      ++right;
    } else {
      ++left;
    }
    ans += 2*min(left, right);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 2036
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if ((a * b) % 2 == 0) {
			System.out.println("Even");
		} else {
			System.out.println("Odd");
		}
	}

}


Measured memory_bytes: 22868
#include <iostream>
using ll = long long;
using namespace std;

/* initialize */

/* main */
int main() {
    int N;
    cin >> N;
    int u = 0, i = 0;
    for(;;i++) {
        if (i * (i + 1) > 2 * N){ u = i; break;}
    }
    int v = (u*(u+1))/2 - N;
    for (i= 1; i <= v-1; ++i) {
        cout << i << "\n";
    }
    for (i = v+1; i <= u; i++){
        cout << i << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- "
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long  
#define p(x)               cout << x << "\n" ; 
#define MOD                100000007
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"
#define mi                 map <int,int> 
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             (x).begin(),(x).end() 
/* 
  date | time : 3/22/2020 9:57:02 AM 
*/    
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set ; 
const int N = 2e5+7;  
int tests(){ 

	int i,n,m ;
	const int M = 1e9+7 ; 
	cin >> n >> m ;
	int x; 
	vector <bool> mask(n+1,false); 
	vector <int> dp(n+1,0);
	dp[0] = 1 ; 
	while(m--){
		cin >> x ; 
		mask[x] = true ;
	}
	forn(i,0,n+1)
	if(!mask[i])
	{ 
		if(i+1 <= n )
		    dp[i+1] = (dp[i+1]+dp[i])%M;
		if(i+2 <= n )
	    dp[i+2] = (dp[i+2]+dp[i])%M ;
	}
	else
		dp[i] = 0 ; 
	cout << dp[n]  << '\n' ; 
	return 0; 
} 
int main(){
    I__O ;          
    int cases = 1 ; 
    // cin >> cases ; 
    for(int i = 1 ; i <= cases ; i++ ){
      // cout << "Case #" << i << ": " ;  	
      tests(); 
    }
    return 0 ; 
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}
main()
{
    int x;
    cin>>x;
    for(int i=-1000; i<=1000; i++)
    {
        for(int j=-1000; j<=1000; j++)
        {
            int v=power(i,5)-power(j,5);

            if(v==x)
            {
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
}



Measured memory_bytes: 3636
/*
Author: Xjrjyy
LANG: C++
PROG: abc177_c.cpp
Mail: admin@xjrjyy.com
Blog: https://blog.xjrjyy.cn/
*/

#include <cstdio>
#include <cctype>
#include <vector>
#include <iostream>

#define Mod 1000000007
#define MAXN ()

int n, a;
long long sum, ans;

int main()
{
    scanf("%d", &n);
    while (n--)
    {
    	scanf("%d", &a);
    	ans = (ans + a * sum % Mod) % Mod;
    	sum = (sum + a) % Mod;
    }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 3816
fun main() {
    fun gcd(a: Int, b: Int): Int {
        if (a < b) return gcd(b, a)
        if (b == 0) return a
        return gcd(b, a % b)
    }

    val n = readLine()!!.toInt()
    var result = 0
    for (i in 1..n) {
        for (j in 1..n) {
            for (k in 1..n) {
                result += gcd(i, gcd(j, k))
            }
        }
    }

    println(result)
}

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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(std::vector<long long> H, std::vector<long long> M, long long K){
    cout << 60 * H[1] + M[1] - 60 * H[0] - M[0] - K << endl;
}

struct IoSetup {
    IoSetup() {
        // cin.tie(nullptr);
        // ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    std::vector<long long> H(2);
    std::vector<long long> M(2);
    for(int i = 0 ; i < 2 ; i++){
        scanf("%lld",&H[i]);
        scanf("%lld",&M[i]);
    }
    long long K;
    scanf("%lld",&K);
    solve(std::move(H), std::move(M), K);
    return 0;
}


Measured memory_bytes: 3696
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		for(int i = 1; i <= 9; i++){
			for(int j = 1; j <= 9; j++){
				System.out.printf("%dx%d=%d\n", i, j, i * j);
			}
		}
	}
}

Measured memory_bytes: 26220
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n, vl;
vector<P> ans;
bool a, b;
int main() {
	cin >> n;
	vector<ll> s(n);
	REP(i, n)cin >> s[i];
	sort(ALL(s));
	REP(i, n) {
		if (s[i] < 0)b = true;
		else if (s[i] > 0)a = true;
	}
	if (a and b) {
		REPO(i, s.size() - 2) {
			if (s[i] < 0) {
				ans.push_back(P(s[s.size() - 1], s[i]));
				s[s.size() - 1] -= s[i];
			}
			else {
				ans.push_back(P(s[0], s[i]));
				s[0] -= s[i];
			}
			
		}ans.push_back(P(s[s.size() - 1], s[0]));
			s[s.size() - 1] -= s[0];
		vl = s[s.size() - 1];
	}
	else if (a) {
		REPO(i, s.size() - 2) {
			ans.push_back(P(s[0], s[i]));
			s[0] -= s[i];
		}
		ans.push_back(P(s[s.size() - 1], s[0]));
		s[s.size() - 1] -= s[0];
		vl = s[s.size() - 1];
	}
	else {
		REP(i, s.size() - 1) {
			ans.push_back(P(s[s.size() - 1], s[i]));
			s[s.size() - 1] -= s[i];
		}
		vl = s[s.size() - 1];
	}
	cout << vl << endl;
	REP(i, ans.size()) {
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}


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

int main(int argc, char *argv[]) {
	int num_of_training = 0;
	std::cin >> num_of_training;

	uint64_t power = 1;
	const uint64_t divisor = static_cast<uint64_t>(std::pow(10, 9) + 7);  // 10^9 + 7
	uint64_t mod = 1;
	for (int i = 1; i <= num_of_training; i++) {
		//
		//  掛け算した結果の剰余は、もとの数の剰余同士を掛け算した結果に合同である
		//	例: 2^5 === 13 (mod 19)
		//      2^5 * 2 === 13 * 2 (mod 19)
		//
		//  つまり、剰余にpowerを掛け、その余りを求め続ければ良い
		//
		mod = (mod * i) % divisor;
	}

	std::cout << mod << std::endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String a = sc.next();
		String b = sc.next();
		if (a.equals("H")) {
			System.out.println(b);
		}
		if (a.equals("D")) {
			if (b.equals("D")) {
				System.out.println("H");
			} else if (b.equals("H")) {
				System.out.println("D");
			}
		}
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5;
int main(){
	string s;
	cin>>s;
	bool sign=false;
	for(int i=0;i<s.length()-1;i++){
		if(s[i]==s[i+1]){
			cout<<"Bad";
			sign=true;
			break;
		}
	}
	if(!sign){
		cout<<"Good";
	}
	return 0;
}

Measured memory_bytes: 256
function Main(input){
  line = input.split('\n');
  N = parseInt(line[0].trim());
  W = line[1].trim().split(' ').map(n => parseInt(n));
  min = Math.abs(sum(W, 0, 1) - sum(W, 1, N));
  for (T = 2; T < N; T++) {
    diff = Math.abs(sum(W, 0, T) - sum(W, T, N));
    min = diff < min ? diff : min;
  }
  console.log(min);
}

function sum(A, B, C) {
  total = 0;
  for (i = B; i < C; i++) {
    total += A[i];
  }
  return total;
}
 
Main(require("fs").readFileSync("/dev/stdin","utf-8"));


Measured memory_bytes: 7372
a, b, c, x, y = map(int, input().split())
min = 999999999999999999999999999999999999
for i in range(100001):
    price = max(0, x - i) * a + max(0, y - i) * b + (i * 2 * c)
    if price < min:
        min = price
print(min)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define read(x) scanf("%d",&x)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=2e5+7;
const int M=1e9+7;
const int INF=0x3f3f3f3f;

int n,m;

void solve(){
	string s;
	cin>>s;
	if (s[1]=='R') s[1]='B';
	else s[1]='R';
	cout<<s;
}

int main(){
//	ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
//	int T;read(T);
//	for(int i=1;i<=T;i++)
		solve();
}


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

double amax,amin,pp=0,p,t,k;

double night(int lev,double r,double l){
    double h=(l+r)/2;
    if(lev==k){
        if(h>=amin&&h<=amax)return 1;
        else return 0;
    }
    if(l<amin||r>amax)return 0;
    else{
        return (h>=t)?(1-p)*night(lev+1,r,h)+p*night(lev+1,h,l):(1-p)*night(lev+1,h,l)+p*night(lev+1,r,h);
    }
}

void solve(int _k,int r,int l,double _p,double e,double _t){
    p=_p;
    k=_k;
    t=_t;
    amin=t-e;
    amax=t+e;
    pp=night(0,(double)r,(double)l);
    printf("%.6lf",pp);
    
}

int main (){
    int a,b,c;
    double d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    solve(a,b,c,d,e,f);
}

Measured memory_bytes: 3276
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cout << "Hello world"<<"\n";
    const int m = 1000000007;
    int n;
    long long int x;
    cin >> n;
    vector<long long int> inp;
    vector<long long int> sumv;
    long long int sum = 0;
    for(int i = 0;i<n;i++)
    {
        cin >> x;
        inp.push_back(x);
        sum = (sum%m+x%m)%m;
        sumv.push_back(sum);
    }

    long long int ans = 0;
    for(int i = 1;i<n;i++)
    {
        ans = (ans%m + (inp[i]%m*sumv[i-1]%m)%m)%m;
    }
    cout << ans << endl;


    /*
    for(auto i : sumv)
        cout << i <<endl;
    */
}


Measured memory_bytes: 6692
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=55;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll dp[N][N*N];
int main()
{
    std::ios::sync_with_stdio(false);
    int n,a;
    ll x;
    cin>>n>>a;
    dp[0][0]=1;
    for(int i=1; i<=n; i++)
    {
        cin>>x;
        for(int j=i-1; j>=0; j--)
        {
            for(int w=0;w<N*N;w++)
            {
                dp[j+1][w+x]+=dp[j][w];
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=dp[i][i*a];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1408
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main(){
    sc.Split(bufio.ScanWords)
	var n, x int
	var l []int
	n = nextInt()
	x = nextInt()
	for i := 0; i < n; i++ {
		l = append(l, nextInt())
	}
	sum := 0
	ans := 1
	for _,val := range l {
		sum += val
		if sum > x {
			fmt.Print(ans)
			return
		} else {
			ans++
		}
	}
  	fmt.Print(ans)
	return
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,l=1,r=3;
ll ans=1e15,a[N],s[N];
ll calc(int l,int r){return s[r]-s[l-1];}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	for(int i=2;i<=n;i++){
		while(l+2<=i&&abs(calc(1,l)-calc(l+1,i))>abs(calc(1,l+1)-calc(l+2,i)))l++;
		while(r+2<=n&&abs(calc(i+1,r)-calc(r+1,n))>abs(calc(i+1,r+1)-calc(r+2,n)))r++;
		ll a=calc(1,l),b=calc(l+1,i),c=calc(i+1,r),d=calc(r+1,n);
		ans=min(ans,max(max(a,b),max(c,d))-min(min(a,b),min(c,d)));
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 6880
a, b = map(int, input().split())

if a > 0 and b > 0:
    print("Positive")
elif a < 0 and b > 0:
    print("Zero")
else:
    if (b - a + 1) % 2 == 0:
        print("Positive")
    else:
        print("Negative")


Measured memory_bytes: 9000
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repp(i,a,b) for(int i=a;i<=b;i++)
#define endl '\n'
#define mod 1000000007
#define pi 3.14159265358979323
 
bool sorttt(const pair<int, pair<char, int> > &a, 
              const pair<int, pair<char, int> > &b) 
{ 
    return (a.first > b.first); 
}
 
int power(int x,int n){
    int res=1;
    while(n>0){
        if(n&1)
            res=res*x;
        x*=x;
        n>>=1;
    }
    return res;
}

int bin(int x,int n){
    int res=1;
    while(n){
        if(n&1) res=(res*x)%mod;
        x=(x*x)%mod;
        n>>=1;
    }
    return res;
}
bool prime(int n){
    if(n==3)return 1;
    repp(i,2,sqrt(n)){
        if(n%i==0)return 0;
    }
    return 1;
}
int chk(int n){
    int mi=100, ma=-1;
    while(n){
        mi=min(mi,n%10);
        ma=max(ma,n%10);
        n/=10;
    }
    return ma*mi;
}
 
signed main()
{
    fast
    int n; cin>>n;
    if(n%10==3)cout<<"bon";
    else if(n%10==0 or n%10==1 or n%10==6 or n%10==8)cout<<"pon";
    else cout<<"hon";
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct edge {
  ll to, cost;
};

int main() {
  int N; cin >> N;
  vector<int> a(N); REP(i, N) cin >> a[i];
  vector<int> ans(N + 1, 0);
  for(int i = N - 1; i >= 0; --i) {
    int tmp = i + 1; int res = 0;
    for(int k = tmp; k <= N; k += tmp) {
      // cout << res << endl;
      res += ans[k];
    }
    if(res % 2 != a[i]) ans[tmp] = 1;
  }

  int b = 0;
  REP(i, N + 1) {
    if(i == 0) continue;
    if(ans[i] > 0) b++;
  }
  cout << b << endl;
  for(int i = 1; i <= N; ++i) {
    if(ans[i] == 1) cout << i << " ";
  }
  cout << endl;
}

Measured memory_bytes: 4824
import java.util.*;
import java.lang.*;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Set<Integer> set = new TreeSet<>();
		for (int i = 0; i < 4; i++) {
			set.add(sc.nextInt());
		}
		if (set.contains(1) && set.contains(9) && set.contains(7) && set.contains(4)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
#include <iomanip>
#include <limits>
using namespace std;


int main()
{
	double w, h, x, y;
	cin >> w >> h >> x >> y;

	cout << fixed << setprecision(9) << w*h/2 << " ";

	if(x == w/2 && y == h/2){
		cout << 1 << endl;
	}else{
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp=[0]+[1000000000]*(n-1)

for i in range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[-1])


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,K;
int A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	for(i=K;i<N;i++) {
		if(A[i-K]<A[i]) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 4400
fun main(array: Array<String>) {
    val n = readLine()!!.toInt()
    var max = 0
    var ans = 0

    if(n == 1) {
        print(1)
        return
    }

    for(i in 2 until n+1) {
        var a = i
        var cnt = 0
        while (a % 2 != 1) {
            a /= 2
            cnt++
        }
        if(max <= cnt) {
            max = cnt
            ans = i
        }
    }
    print(ans)
}

Measured memory_bytes: 33460
import numpy

N = int(input().strip())

grid = []
for i in range(N):
    grid.append(input().strip())

count_array = [0,0,0,0]
for i in grid:
    if i == "AC":
        count_array[0] += 1
    elif i == "WA":
        count_array[1] += 1
    elif i == "TLE":
        count_array[2] += 1
    else:
        count_array[3] += 1

print("AC x", count_array[0])
print("WA x", count_array[1])
print("TLE x", count_array[2])
print("RE x", count_array[3])

Measured memory_bytes: 34252
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
	string a;
	cin >> a;
	cout << "2018/" <<a[5]<< a[6] << a[7] << a[8] << a[9]  << endl;
}
/*
死のマウス
.　　あり許せん！
　　　∧＿＿∧
　|| （＃｀Д´ ） ||
　|| ( |　 　| | |||
　从| |　 　| |从从
￣) ⊂ノ￣￣!_つ￣て
　フヘ(　　　　ヽヘ(＼

*/


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int Min(int a, int b, int c) {
	if (a <= b) { return std::min(a, c); }
	else return std::min(b, c);
}
int Max(int a, int b, int c) {
	if (a >= b) { return std::max(a, c); }
	else return std::max(b, c);
}
int main(void) {
	int a, b, c; cin >> a >> b >> c;
	int s = abs(a - b), t = abs(b - c), d = abs(c - a);
	int res = s + t + d - Max(s, t, d);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,j,n) for(int i=j;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)

int main() {
  int h,n;
  cin >> h>>n;
  int a[n];
  int b[n];
  ll ans = 1000000000000;
  fr(i,n){
    cin >> a[i];
    cin >> b[i];
  }
  ll dp[h];
  fr(i,h){
    dp[i]=100000000000;
  }
  dp[0]=0;
  fr(i,h){
    if(dp[i]!=0||i==0){
      fr(j,n){
        if(i+a[j]>=h){
          if(ans>dp[i]+b[j])ans=dp[i]+b[j];
        }
        else if(dp[i+a[j]]>dp[i]+b[j])dp[i+a[j]]=dp[i]+b[j];
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
import java.io.PrintStream;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
	final static PrintStream so = System.out;
	final static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int[] digits = sc.next().chars().map(i -> i-'0').toArray(); // 125 -> {1, 2, 5}

		int pattern = (int) Math.pow(2, digits.length-1);

		so.println(IntStream.range(0, pattern).mapToLong(i -> calc(digits, i)).sum());
	}

	static long calc(int[] nums, int bits) {
		long sum = 0;
		long buf = nums[0];

		for (int i=1; i<nums.length; i++) {
			if ((bits >> i-1 & 1) == 1) {
				sum += buf;
				buf = nums[i];

			} else {
				buf = buf*10 + nums[i];
			}
		}
		sum += buf;
		return sum;
	}
}

Measured memory_bytes: 27092
S=input()
N=len(S)
S1=S[:(N-1)//2]
S2=S[(N+3)//2-1:]
flag=0
if S==S[::-1]:
    flag+=1
if S1==S1[::-1]:
    flag+=1
if S2==S2[::-1]:
    flag+=1
if flag==3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n,m;    cin>>n>>m;
    int a[n][m],b[m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        a[i][0]*=b[0];
    }
    for(int i=1;i<m;i++){
        for(int j=0;j<n;j++){
            a[j][i]=(a[j][i]*b[i])+a[j][i-1];
        }
    }
    for(int i=0;i<n;i++){
        cout<<a[i][m-1]<<endl;
    }
    return 0;
}

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

int main()
{
    int n , ans;
    cin>>n;
    ans=n%10;
    
    if (ans==2 || ans ==4 || ans ==5|| ans==7 ||ans==9)
    cout<<"hon";
    if(ans==0 || ans ==1 || ans ==6|| ans==8)
    cout<<"pon";
    if(ans==3)
    cout<<"bon";
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
Apparently, the tree supports the same operations as the set 
(at least I haven't any problems with them before), but also there are two new features — 
find_by_order() — The first returns an iterator to the k-th largest element (counting from zero)
order_of_key() — the number of items in a set that are strictly smaller than our item. 
https://codeforces.com/blog/entry/11080
using namespace __gnu_pbds; */
using namespace std;
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define int long long
#define MOD 1000000007
#define pb push_back 
#define ins insert
#define fast(); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ld long double
#define endl '\n'
int m(int a) {
    return ((a%MOD)+MOD)%MOD;
}
int p(int a, int b) {
    int res = 1;
    while(b > 0){
        if(b&1) res = m(m(res)*m(a));
        a = m(m(a)*m(a));
        b >>= 1;
    }
    return res;
}
int inv(int n){
    return p(n, MOD-2);
}
vector<int> fac;
int nCr(int n, int r){   
    if(r == 0)  return 1; 
    return m(m(m(fac[n])*m(inv(fac[r])))*m(inv(fac[n-r]))); 
}
signed main(){
    fast();
    string s;
    int k;
    cin >> k;
    cin >> s;
    int n = k+s.length();
    fac.resize(n+1);
    fac[0] = 1; 
    for (int i=1; i<=n; i++)   fac[i] = m(m(fac[i-1])*m(i));
    int z = 26;
    int ans = p(z,n), f = 0;
    for(int i=0; i<s.length(); i++){
        f = m(m(nCr(n, i))*m(p(z-1, n-i)));
        ans = m(m(ans)-m(f));
    }
    // cout << f << endl;
    cout << ans << endl;
    cerr << "\nTime elapsed : " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Measured memory_bytes: 19780
str = gets.split
N,K = str[0].to_i, str[1].to_i
a = Array.new(N)
f = Array.new(N)
v = 0
str = gets.split
for i in 0...N do
    a[i] = str[i].to_i
    v += a[i]
end
a.sort!
str = gets.split
for i in 0...N do
    f[i] = str[i].to_i
end
f.sort!.reverse!

t = v - K
if t <= 0
    puts 0
    exit
end

l = 1
r = 10**12
while l != r
    c = (l+r)/2
    s = 0
    for i in 0...N do
        s += c > a[i] * f[i] ? a[i] : c / f[i] 
    end
    if s >= t
        r = c
    else
        l = c+1
    end
end
puts l

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

using namespace std;

#define endl '\n'

const int N = 1e6;

vector <int> g[N];

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

	int n, m;
	cin >> n >> m;
	for(int i=0; i<m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int p[n+1];
	int seen[n+1];
	memset(seen, 0, sizeof seen);
	queue <int> q; q.push(1); seen[1] = 1;
	while(q.size()) {
		int u = q.front(); q.pop();
		for(int v : g[u]) {
			if(!seen[v]) {
				seen[v] = 1;
				p[v] = u;
				q.push(v);
			}
		}
	}
	int sum = 0;
	for(int i=1; i<=n; i++) sum += seen[i];
	if(sum == n) {
		cout << "Yes" << endl;
		for(int i=2; i<=n; i++) cout << p[i] << endl;
	}
	else cout << "No" << endl;/**/

	return 0;
}

Measured memory_bytes: 32004
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using ll = long long;

int main(){
    ll N;
    bool P=false;
    cin >> N;
    char str[N];
    for(int i=0;i<N;i++){
        cin >> str[i];
    }
    for(int i=0;i<N;i++){
        if(str[i]=='Y'){
            P = true;
        }
    }
    if(P == true){
        cout << "Four" << endl;
    }else{
        cout << "Three" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {
    int A = 0;
    int B = 0;
    int T = 0;

    cin >> A >> B >> T;

    int biscuit = 0;

    for (int i=A; i<T+0.5; i+=A) {
        biscuit += B;
    }

    cout << biscuit;

    return 0;
}


Measured memory_bytes: 256
s=gets.chomp
p (?a..?z).map{|c|
    t=s.chars
    n=t.size
    while t.uniq.size>1
        (t.size-1).times{|i| t[i]=t[i+1] if t[i+1]==c }
        t.pop
    end
    n-t.size
}.min


Measured memory_bytes: 1788
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

int n;
int a[300050];
bool good[300050];
int psum[300050];

bool check(int amt)
{
    for (int i = 0; i <= n + 1; i++) good[i] = false;
    int cur_min = 2000000000;
    for (int i = 0; i <= n + 1; i += 2) {
        if (i == 0 || psum[i-1] - psum[i-2] >= cur_min) {
            good[i] = true;
            cur_min = min(cur_min, amt - psum[n-1] - psum[i] + (i < 1 ? 0 : psum[i-1]));
        }
    }
    return good[n + 1];
}

int main()
{
    scanf("%d", &n);
    int total = 0;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        total += a[i];
        psum[i] = a[i] + (i < 2 ? 0 : psum[i-2]);
    }
    if (n % 2 == 0) {
        int odd = 0, even = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 2) odd += a[i];
            else even += a[i];
        }
        printf("%d %d", max(odd, even), min(odd, even));
        return 0;
    }
    int l = 0;
    int r = 300000000;
    while (l < r) {
        int mid = (l + r) / 2 + 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    printf("%d %d", l, total - l);
    return 0;
}


Measured memory_bytes: 5812
S = input()
x, y = map(int, input().split())
M = S.count("F")
F = list(map(len, S.split("T")))
F1 = F[::2]
B1 = 1 << sum(F1)
X = B1
X = X << x if x > 0 else X >> -x
B1 = B1 << F1[0]
for f in F1[1:]:
    B1 = (B1 << f) | (B1 >> f)
b1 = B1 & X
F2 = F[1::2]
B2 = 1 << sum(F2)
Y = B2
Y = Y << y if y > 0 else Y >> -y
for f in F2:
    B2 = (B2 << f) | (B2 >> f)
b2 = B2 & Y
print("YNeos"[not(b1 and b2)::2])

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define RREP(i,n) for(int i=int(n)-1; i>=0; i--)
#define FOR(i,f,t) for(int i=int(f); i<=int(t); i++)
#define RFOR(i,f,t) for(int i=int(f); i>=int(t); i--)
#define ALL(vec) (vec).begin(),(vec).end()
#define ASORT(vec) sort(ALL(vec))
#define DSORT(vec) sort(ALL(vec), greater<int>());
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define YES(ans) if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define Yes(ans) if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define yes(ans) if(ans) cout<<"yes"<<endl; else cout<<"no"<<endl;
#define INF 1000000000000
#define NOD 1000000007
#define PI 3.141592653589793238462643

int main() {
    int n, s=0;
    cin >> n;
    vector<int> data(n);
    REP(i, n) cin >> data.at(i);
    ASORT(data);
    REP(i, n-1) {
        if(data.at(i) == data.at(i+1)) {
            data.at(i) = 0;
            data.at(i+1) = 0;
        }
    }
    REP(i, n) {
        if(data.at(i) != 0) s++;
    }
    cout << s << endl;
}


Measured memory_bytes: 640
#include <stdio.h>

int *bubbleSort(int *N, int len)
{
    int i, j, temp;

    for (i = 0; i < len; i++)
    {
        for (j = len - 1; j > i; j--)
        {
            if (N[j] < N[j - 1])
            {
                temp = N[j];
                N[j] = N[j - 1];
                N[j - 1] = temp;
            }
        }
    }

    return N;
}

int *reverse(int *N, int len)
{
int temp;

for(int i=0;i<len/2;i++){
    temp=N[i];
    N[i]=N[len-i-1];
    N[len-i-1]=temp;
}

    return N;
}

int main(void)
{
    int s[105], t[105];
    int ls, lt, len;
    int i, temp;

    ls = 0;
    while ((temp = getchar()) != '\n')
    {   //s
        //printf("%c",temp);
        s[ls] = temp;
        ls++;
    }
    bubbleSort(s, ls);
    //printf("%d\n",ls);

    lt = 0;
    while ((temp = getchar()) != '\n')
    {   //t
        // printf("%c",temp);
        t[lt] = temp;
        lt++;
    }
    bubbleSort(t, lt);
    reverse(t,lt);
    //printf("%d\n",lt);
    //printf("%d %d\n",s[0],s[1]);

    if (ls > lt)
        len = lt;
    else
        len = ls;
    //printf("%d %d %d\n",ls,lt,len);
    for (i = 0; i < len; i++)
    {
        //printf("%d %d\n", s[i], t[i]);
        if (s[i] < t[i])
        {
            printf("Yes");
            return (0);
        }
        else if (s[i] > t[i])
        {
            printf("No");
            return (0);
        }
    }
    if (ls < lt)
        printf("Yes");
    else
        printf("No");

    return (0);
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main()
{
    int n, m, q, x, y;
    cin >> n >> m >> q;
    int count[501][501] = {0};
    for(int i  = 0; i < m; i++)
    {
        cin >> x >> y;
        count[x][y]++;
    }
    for(int i  =0; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            count[i][j] += count[i][j - 1];
        }
    }
    for(int i  = 0; i <= n; i++)
    {
        for(int j = n - 1; j >= 0; j--)
        {
            count[j][i] += count[j + 1][i];
        }
    }
    for(int i = 0; i < q; i++)
    {
        cin >> x >> y;
        cout << count[x][y] << endl;
    }

    return 0;
}


Measured memory_bytes: 4572
from collections import Counter
from itertools import accumulate


def prime_factorize(n):
    """素因数分解し，ユニークな素因数のsetを返す。"""
    ans = []
    ans_add = ans.append
    while n % 2 == 0:
        ans_add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ans_add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ans_add(n)
    return ans


def main():
    n = int(input())
    primes = prime_factorize(n)
    acc = tuple(accumulate(range(1, 42)))
    counted = Counter(primes)
    countcount = Counter(counted.values())
    ans = 0
    for c, cc in countcount.items():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp * cc
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9472
def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [None] * len(A)
    X[0] = sum(A) - 2 * sum([A[i] for i in range(1, len(A), 2)])
    for i in range(len(A)-1):
        X[i+1] = 2 * A[i] - X[i]
    
    print(' '.join(list(map(str, X))))
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 19140
#include "bits/stdc++.h"
using namespace std;
#define REP(a,b) for(long long a = 0;a < b;++a)
int main(){
#define int long long
	int n,k;
	cin >> n >> k;
	int ans = k;
	REP(i,n-1){
		ans *= k-1;
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
    int H, W;
    while (1){
        cin >> H >> W;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if ((i+j)%2==0) cout << "#";
                if ((i+j)%2==1) cout << ".";    
            }
            cout << endl;
        }
    if (H==0 && W==0) break;
    cout << endl;
    }
}


Measured memory_bytes: 3084
n = int(input())
restaurants = []

for i in range(n):
  tmp = input().split()
  tmp[1] = int(tmp[1])
  tmp.append(i+1)
  restaurants.append(tmp)

from operator import itemgetter

restaurants.sort(key=itemgetter(1),reverse=True)
restaurants.sort(key=itemgetter(0))

for j in restaurants:
    print(j[2])

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int main(void)
{
    int n, m;

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

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        StringJoiner ans = new StringJoiner(" ");
        int i = n - 1;
        while (i >= 0) {
            ans.add(String.valueOf(a[i]));
            i -= 2;
        }
        i = (n % 2 == 0) ? 0 : 1;
        while (i < n) {
            ans.add(String.valueOf(a[i]));
            i += 2;
        }
        System.out.println(ans.toString());
    }

}


Measured memory_bytes: 95208
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var S = ReadLine();
            var N = S.Length;
            var children = new long[N];
            var num = new long[] { 0, 0 };
            for (var i = N - 1; 0 <= i; --i)
            {
                if (S[i] == 'L')
                    ++num[i % 2];
                else
                {
                    children[i] += num[i % 2];
                    children[i + 1] += num[(i + 1) % 2];
                    num[0] = num[1] = 0;
                }
            }
            num[0] = num[1] = 0;
            for (var i = 0; i < N; ++i)
            {
                if (S[i] == 'R')
                    ++num[i % 2];
                else
                {
                    children[i] += num[i % 2];
                    children[i - 1] += num[(i - 1) % 2];
                    num[0] = num[1] = 0;
                }
            }
            WriteLine(string.Join(" ", children));
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13536
#include <bits/stdc++.h>
#include <atcoder/all>


using namespace std;
using namespace atcoder;

using mint = modint998244353;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef string str;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef dsu uf;
typedef fenwick_tree<ll> fw;

const ll mod=1e9+7;
const ll inf=1e18;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define pb(x) pop_back(x)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pc(x) __builtin_popcount(x)
#define gll greater<ll>()

void solve(){
  ll n,m;
  cin >> n >> m;
  vector<mint> a(n),b(m);
  rep(i,0,n) {
   ll x;
    cin >> x;
    a[i]=x;
  }
  rep(i,0,m){
   ll x;
    cin >> x;
    
   b[i]=x;
    
  }
  auto c=convolution(a,b);
  rep(i,0,n+m-2) cout << c[i].val()<< " ";
  cout << c[n+m-2].val() << endl;

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

Measured memory_bytes: 19064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
 
int a,b,c;
map<int,int> mp;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
  	cin>>a;
  	mp[a]++;
  	cin>>b;
  	mp[b]++;
  	cin>>c;
  	mp[c]++;
  	if(mp[5]==2 && mp[7]==1){
  		cout<<"YES"<<endl;
  	}
  	else cout<<"NO"<<endl;

    return 0;
}

Measured memory_bytes: 3604
n, q = map(int, input().split())
s = input()
keep = [0]*(n)

for i in range(1, n):
    keep[i] = keep[i-1]
    l, r = i-1, i+1
    if s[l:r] == "AC":
        keep[i] += 1

for j in range(q):
    l, r = map(int, input().split())
    print(keep[r-1]-keep[l-1])


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

namespace ConsoleApp8
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var sortedinputs = input.OrderByDescending(x=> x).ToArray();

            if (sortedinputs[2] + sortedinputs[1] == sortedinputs[0])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    n -= k;
    int ans = 1;
    while(n > 0){
        n -= (k-1);
        ans++;
    }
    cout << ans << endl;

}



Measured memory_bytes: 640
import math
size = 3
bingo = []
for i in range(size):
    line = [int(i) for i in input().split(' ')]
    bingo.append(line)
n = int(input())
bs = []
for i in range(n):
    b = int(input())
    bs.append(b)

flag = False
cnt1 = 0
cnt2 = 0
for i in range(size):
    if bingo[i][i] in bs:
        for j in range(size):
            if bingo[i][j] in bs:
                continue
            else:
                break
        else:
            flag = True
        for j in range(size):
            if bingo[j][i] in bs:
                continue
            else:
                break
        else:
            flag = True
        cnt1 += 1
    if bingo[i][size-i-1] in bs:
        cnt2 += 1
if (cnt1 == size) or (cnt2 == size):
    flag = True

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) ll aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) string aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007


int main() {
	
	int N;
	cin>>N;
	ll dp[N+1];
  ll dp2[220000];
	map<int,int> num;
	fx(N+1){
		dp[x]=0;
	}
  fx(220000){
		dp2[x]=0;
	}
	int pre=-1;
	fx(N){
		int c;
		cin>>c;
            dp[x+1]+=dp[x];
		if(c==pre){continue;}
		dp[x+1]+=num[c];
		dp[x+1]%=MOD;
		num[c]++;
			dp[x+1]+=dp2[c];
			dp[x+1]%=MOD;
		dp2[c]+=dp[x];
      dp2[c]%=MOD;
       pre=c;
      
	}
ce(dp[N]+1)
}

Measured memory_bytes: 12928
from sys import stdin, setrecursionlimit
from bisect import bisect_right


def main():
    input = stdin.buffer.readline
    n = int(input())
    v = list(map(int, input().split()))
    c = list(map(int, input().split()))

    d = [v[i] - c[i] for i in range(n)]
    d.sort()
    idx = bisect_right(d, 0)
    print(sum(d[idx:]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


Measured memory_bytes: 38256
//Name: Cup
//Level: 4
//Category: シミュレーション,数論
//Note:

/*
 * Aに積まれたN個のカップをCに移すときの手順は
 * ・AのN-1個のカップをCに移す
 * ・Aに残ったカップをBに移す
 * ・CのN-1個のカップをAに移す
 * ・Bに残っているカップをCに移す
 * ・AのN-1個のカップをCに移す
 * となるから，3^N-1手かかる．
 * それぞれのカップはトレイA-Cのどこにでも置けるから，可能な状態数は3^N．
 * したがって，普通に解けば全状態を網羅することになるので，当然初期状態もこの中に含まれる．
 * あとは解く手順をシミュレーションしながら初期状態が出現した手数を覚えておき，逆順に動かしたときも考えて小さいほうを手数として採用すればよい．
 */
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int pow_(int a, int x) {
    int val = 1;
    for(int i = 0; i < x; ++i) val *= a;
    return val;
}

int main() {
    while(true) {
        int N, M;
        cin >> N >> M;
        if(!N && !M) break;

        vector<vector<int> > goal(3);
        for(int i = 0; i < 3; ++i) {
            int n;
            cin >> n;
            while(n--) {
                int idx;
                cin >> idx;
                goal[i].push_back(idx-1);
            }
        }

        vector<vector<int> > field(3);
        for(int i = 0; i < N; ++i) {
            field[0].push_back(i);
        }

        int turn = 0;
        int prev_from = -1;
        int prev_to = -1;
        while(true) {
            if(field == goal) {
                break;
            }
            ++turn;
            for(int from = 0; from < 3; ++from) {
                if(field[from].size() == 0) continue;
                const int glass = field[from].back();
                const int to_1 = from-1;
                const int to_2 = from+1;
                if(!(from == prev_to && to_1 == prev_from) && to_1 >= 0 && (field[to_1].size() == 0 || field[to_1].back() < glass)) {
                    field[to_1].push_back(glass);
                    field[from].pop_back();
                    prev_from = from;
                    prev_to = to_1;
                    break;
                }
                else if(!(from == prev_to && to_2 == prev_from) && to_2 < 3 && (field[to_2].size() == 0 || field[to_2].back() < glass)) {
                    field[to_2].push_back(glass);
                    field[from].pop_back();
                    prev_from = from;
                    prev_to = to_2;
                    break;
                }
                else {
                }
            }
        }
        const int MAXTURN = pow_(3, N) - 1;
        turn = min(turn, MAXTURN-turn);
        if(turn > M) turn = -1;
        cout << turn << endl;
    }
    return 0;
}

Measured memory_bytes: 908