akhauriyash/Code-Regression huggingface dataset:
let split str delim =
  let rec doit s acc =
    match
      try Some (String.index s delim)
      with _ -> None
    with
    | None -> s :: acc
    | Some i ->
        let s1 = String.sub s 0 i in
        let s2 = String.sub s (i + 1) (String.length s - String.length s1 - 1) in
        doit s2 (s1 :: acc)
  in
  List.rev (doit str [])

let lowercase c =
  if c >= 'A' && c <= 'Z' then Char.chr ((Char.code c) - (Char.code 'A') + (Char.code 'a'))
  else c

let lowercase_ascii str =
  Bytes.map (fun c -> lowercase c) str

let count_words w t =
  List.length (List.filter (fun s -> s = w) (split t ' '))

let () =
  try
    let w = read_line () in
    let rec doit cnt =
      match read_line () with
      | "END_OF_TEXT" -> Printf.printf "%d\n" cnt
      | t -> doit (cnt + count_words (lowercase_ascii w) (lowercase_ascii t))
    in
    doit 0
  with End_of_file -> ()

Measured memory_bytes: 2264
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int N,M;
  cin >>N>>M;
  int A[M];
  int B[N];
  int sum[N];
  for(int i=0 ; i < N ; i++)sum[i]=0;
  for(int i=0 ; i < M ; i++)cin >>A[i];
  for(int i=0 ; i < M ; i++){
    for(int j=0 ; j < N ; j++)cin >>B[j];
    for(int j=0 ; j < N ; j++){
      if(A[i] == B[j]){
	sum[j]++;
      }else{
	sum[A[i]-1]++;
      }
    }
  }
  for(int i=0 ; i < N ; i++)cout <<sum[i]<<endl;
  
  return 0;
}

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;
constexpr int MOD = 1e9 + 7;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //cout << fixed << setprecision(6);
    int n; cin >> n;
    vll a(n), cum(n + 1, 0);
    for (int i = 1; i < n+1; i++) {
        cin >> a[i-1];
        cum[i] = cum[i-1] + a[i-1];
    }

    ll dif = INFLL;
    int ans;
    for (int i = 0; i < n+1; i++) {
        ll tmp = abs(cum.back()-cum[i]*2);
        if (dif > tmp) {
            dif = tmp;
        }
    }

    cout << dif << endl;
    return 0;
}

Measured memory_bytes: 6336
s = input()
if len(s) % 2 == 0:
  s1 = "10" * int(len(s) / 2)
  s2 = "01" * int(len(s) / 2)
else:
  s1 = "10" * int(len(s) / 2) + "1"
  s2 = "01" * int(len(s) / 2) + "0"
a1 = int(s) + int(s1)
a2 = int(s) + int(s2)
a1 = str(a1).count("1")
a2 = str(a2).count("1")
print(min(a1,a2))

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> sz(n, 1);
  vector<bool> c(n);
  c[0] = true;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    c[y] = (c[y] | c[x]);
    sz[x]--;
    sz[y]++;
    if (sz[x] == 0) {
      c[x] = false;
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans += c[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int m,n,aa[110000][10],k,cnt=0,a,b;
pair<int,int> p[220000];
string s,ss[220000],x;
char c;
signed main(){
    cin>>n>>a>>b;
    cnt+=n/(a+b)*a;
    cnt+=min(n-n/(a+b)*(a+b),a);
    cout<<cnt;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
#include <iomanip>
#include <typeinfo>
#define ll              long long
#define pb              push_back
#define ppb             pop_back
#define endl            '\n'
#define mii             map<ll int,ll int>
#define pii             pair<ll int,ll int>
#define vi              vector<ll int>
#define vs              vector<string>
#define all(a)          (a).begin(),(a).end()
#define F               first
#define S               second
#define sz(x)           (ll int)x.size()
#define hell            1000000007
#define PI              3.14159265358979323844
#define rep(i,a,b)      for (long long int i=a;i<b;i++)
#define repr(i,a,b)     for (long long int i=a-1;i>=b;i--)
#define lbnd            lower_bound
#define ubnd            upper_bound
#define bs              binary_search
#define mp              make_pair
#define ios             ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={0+,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/
 
//primes for hashing 937,991,1013,1409,1741
ll n,arr[100005],dp[100005];

ll find(ll ind){
	if (dp[ind]!=-1)return dp[ind];
	if (ind==n-1)return 0;
	if (ind>n-1)return hell;
	dp[ind]=min(find(ind+1)+abs(arr[ind]-arr[ind+1]),find(ind+2)+abs(arr[ind]-arr[ind+2]));
	return dp[ind];
}

void solve() {
    cin>>n;
    rep(i,0,n){
    	cin>>arr[i];
    }
    memset(dp,-1,sizeof dp);
    cout<<find(0);
}

signed main() {
    ios
    ll test=1;
    //cin>>test;
    while (test--) solve();
    return 0;
}

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

constexpr int INF = (1LL << 31) - 1;

template <typename T>
class SegmentTree {
private:
  int n;
  T init;
  vector<T> seg;

  int size (int N) {
    int ret;
    for (ret = 1; ret < N; ret <<= 1);
    return ret;
  }

  T query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return init; // maxver
    if (a <= l and r <= b) return seg[k];

    T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }

public:
  SegmentTree (int N, T i = 0) : n(size(N)), seg(size(N) * 2, i), init(i) {}

  void update (int k, T val) {
    k += n - 1;
    seg[k] = val;
    while (k > 0) {
      k = (k - 1) / 2;
      // ???????????´
      seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }

  // [l, r) ???????????§???????????¨?????¨???!!! ... [l, r]??????find(l, r + 1)
  T find(int l, int r) {
    return query(l, r, 0, 0, n);
  }
};


int main() {
    int n, q, command, x, y;

    cin >> n >> q;

    SegmentTree<int> st(n, INF);

    for (int i = 0; i < q; ++i) {
        cin >> command >> x >> y;
        if (command == 0) {
            st.update(x, y);
        }
        else {
            cout << st.find(x, y + 1) << endl;
        }
    }
}

Measured memory_bytes: 3840
#include <stdio.h>
#include <string>
#include <iostream>

int Answer(int N, int M, int* s, int* c, int* Number);

int main(void) {
  
  int N = 0;
  int M = 0;
  
  scanf("%d %d", &N, &M);
  
  int *s = NULL;
  int *c = NULL;
  
  s = (int*)malloc(sizeof(int)*M);
  c = (int*)malloc(sizeof(int)*M);
  
  for(int ii = 0; ii < M; ii++) {
    scanf("%d %d", &s[ii], &c[ii] );
  }
  
  std::string str;
  int *Number = NULL;
  Number = (int*)malloc(sizeof(int)*N);
  for( int ii = 0; ii < N; ii++) {
    Number[ii] = -1;
  }
  
  if( M != 0 ) {
    int AnswerStatus = Answer(N, M, s, c, Number);
    if ( AnswerStatus != 0 ) {
      std::cout << "-1";
    }
    else {
      for( int ii = 0; ii < N; ii++ ) {
        std::string tmpStr;
        tmpStr = std::to_string( Number[ii] );
        str = str + tmpStr;
      }
      std::cout << str;

    }
  }
  else{
    if( N == 1 ) {
      std::cout << "0";
    }
    else {
      str = str + "1";
      for( int ii = 1; ii < N; ii++ ) {
        std::string tmpStr;
        tmpStr = "0";
        str = str + tmpStr;
      }
      std::cout << str;
    }
  }
  
  if( Number != NULL ) {
    free(Number);
  }
  
  if( c != NULL ) {
    free(c);
  }
  
   if( s != NULL ) {
    free(s);
  }
  
  return 0;
}

int Answer(int N, int M, int* s, int* c, int* Number) {
  
  int rc = 0;
  
  //入力引数チェック
  if( N <= 0 ) {
    rc = -1;
    return rc;
  }
  
   if( M <= 0 ) {
    rc = -1;
    return rc;
  }
  
   if( s == NULL ) {
    rc = -1;
    return rc;
  }
  
    if( c == NULL ) {
    rc = -1;
    return rc;
  }
  
  for( int ii = 0; ii < M; ii++ ) {
    
    int keta = 0;
    keta = s[ii];
    
    //情報が重複していたらエラーとする
    if( (Number[keta-1] != -1) && (Number[keta-1] != c[ii]) ) {
      rc = -1;
      return rc;
    }
    else {
      if( (Number[keta-1] == -1) || ( Number[keta-1] > c[ii] ) ) {
        Number[keta-1] = c[ii];
      }
    }
    
  }
  
  //情報がない桁については0を入れる（1桁目には1を入れる)
  for( int ii = 0; ii < N; ii++ ) {
    if( Number[ii] == -1 ) {
      if( (ii == 0) && (N != 1) ) {
        Number[ii] = 1;
      }
      else {
        Number[ii] = 0;
      }
    }
  }
  
  //1桁目が0はエラー
  if( (Number[0] == 0) && ( N != 1 ) ) {
    rc = -1;
  }
  
  return rc;
}

Measured memory_bytes: 256
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	k, a, b := nextInt(), nextInt(), nextInt()

	for i := 1; k*i <= b; i++ {
		if k*i >= a {
			puts("OK")
			return
		}
	}
	puts("NG")
}


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

int main()
{
	int h, w;

	while (true)
	{
		cin >> h >> w;
		if ((h == 0) && (w == 0)) break;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if ((i == 0) || (i == (h - 1))) {
					cout << "#";
				}
				else
				{
					if ((j == 0) || (j == (w - 1))) {
						cout << "#";
					}
					else
					{
						cout << ".";
					}
				}
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 3084
#include<cstdio>
#include<vector>
#include<utility>

using namespace std;

int h, w, k;
char s[11][1003];
int sum[11][1003];

int find_sum(int x1, int y1, int x2, int y2) {
  return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}

bool valid(vector<pair<int, int>>& v1, vector<pair<int, int>>& v2) {
  for (auto p2: v2) {
    if (p2.first > p2.second) {
      return false;
    }
    for (auto p1: v1) {
      if (find_sum(p1.first, p2.first, p1.second, p2.second) > k) {
        return false;
      }
    }
  }
  return true;
}

int min(int x, int y) {
  return x < y ? x : y;
}

int main() {
  scanf("%d %d %d", &h, &w, &k);
  for (int i = 1; i <= h; i++) {
    scanf("%s", s[i]+1);
  }
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      sum[i][j] = sum[i][j - 1] + (s[i][j] == '1' ? 1 : 0);
    }
  }
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      sum[i][j] += sum[i - 1][j];
    }
  }
  int res = 100000;
  for (int i = 0; i < (1 << (h - 1)); i++) {
    vector<pair<int, int>> v;
    int pre = 0;
    for (int j = 0; j < h; j++) {
      if (i & (1 << j) || j == h - 1) {
        v.push_back({pre + 1, j + 1});
        pre = j + 1;
      }
    }
    vector<pair<int, int>> v2;
    int pre2 = 1;
    for (int j = 1; j <= w; j++) {
      for (auto p: v) {
        if (find_sum(p.first, pre2, p.second, j) > k) {
          v2.push_back({pre2, j - 1});
          pre2 = j;
          break;
        }
      }
    }
    v2.push_back({pre2, w});
    if (valid(v, v2)) {
      res = min(res, v.size() + v2.size() - 2);
    }
  }
  printf("%d\n", res);
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<i64>();
    let (x, y, z) = (v[0], v[1], v[2]);
    let ans = (x - z) / (y + z);
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
fun main() {
    val (a, b, c, d) = readLine()!!.trim().split(' ').map(String::toInt)
    var takahashiR = a
    var aokiR = c
    while (takahashiR > 0 && aokiR > 0) {
        aokiR -= b
        if (aokiR <= 0) break
        takahashiR -= d
    }
    println(
        if (takahashiR > 0) "Yes" else "No"
    )
}


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

#define int long long
signed main(){
    int n,k0;
    cin >> n >> k0;
    int k;
    int a[n+1];
    int t;
    a[0]=0;
    for(int i =0;i<n;i++){
        cin >> k;
        a[i+1]= a[i]+k;

    }
    int c[(n*(n+1))/2];
    int j = n;
    k =0 ;
 
    for(int i =0;i<(n*(n+1))/2;i++){
        c[i]= a[j]-a[i-k];
        if(i-k == j-1){
            k+= j ;
            j--; 
        }
       
    }
    t =0;
    int y;
  
    for(int i =40;i>=0;i--){
        y=0;
        k = pow(2,i);
        for(int u =0;u<(n*(n+1))/2;u++){
            if((c[u]&(t+k))==t+k)y++;
        }
        if(y>=k0) t +=k;
    }
    cout << t;
    return 0;
    
}

Measured memory_bytes: 4224
fun main(args: Array<String>) {

    val (n, a, b) = readLine()!!.split(" ").map{ it.toLong() }

    var ans = modPow(2, n) - 1 + mod
    val minus = modAdd(nCr(n,a), nCr(n,b))

    ans = modSub(ans, minus)
    if (ans < 0L) ans += mod
    println(ans)

}

const val mod = 1000000007L
fun modAdd(a: Long, b:Long):Long = (a + b) % mod
fun modSub(a: Long, b:Long):Long = (a - b) % mod
fun modMul(a: Long, b:Long):Long = (a % mod) * (b % mod) % mod
fun modDiv(a: Long, b:Long):Long = modMul(a, modPow(b, mod - 2))
fun modPow(a: Long, b:Long):Long =
    when {
        b == 0L -> 1L
        b == 1L -> a
        b % 2L == 0L -> modPow(a, b / 2L).let { (it * it) % mod }
        else -> (a * modPow(a, b - 1)) % mod
    }
val factList = mutableListOf<Long>()
val factInvList = mutableListOf<Long>()
fun modFactInit(n: Long, a:Long, b:Long) {
    val limit = Math.max(Math.min(a, n-a), Math.min(b, n-b))
    var tmp = 1L
    var tmpInv = 1L
    for(i in 0 until limit) {
        tmp = modMul(tmp, n-i)
        tmpInv = modMul(tmpInv, i+1)
        factList.add(tmp)
        factInvList.add(tmpInv)
    }
}
fun nCr(n: Long, r: Long):Long {
    var ans = 1L
    var bunbo = 1L
    val limit = Math.min(r, n-r)
    for (i in 0 until limit) {
        ans = modMul(ans, n-i)
        bunbo = modMul(bunbo, i + 1)
    }
    return modDiv(ans, bunbo)
}


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

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N;
int a[20][20];
int dp[1<<16]; // dp[i]: iの立っているビットを使用したときの組み合わせの数
int USE[1<<16]; // USE[i]: iで立ってるビットを同じグループとしたときのスコア

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%lld", &a[i][j]);
    }
  }

  // 使用したビットに対応するスコアをあらかじめ計算しておく
  for (int use = 0; use < (1 << N); use++) {
    int score = 0;
    for (int i = 0; i < N; i++) {
      for (int j = i; j < N; j++) {
        if (((use >> i)&1) and ((use >> j)&1)) {
          score += a[i][j];
        }
      }
    }
    USE[use] = score;
  }

  // DP
  for (int used = 0; used < (1 << N); used++) { // 使用済みのビット
    int unused = used ^ ((1 << N) - 1); // 未使用のビット
    for (int use = unused; use > 0; use=(use-1)&unused) { // unusedの部分集合を列挙
      if (!(use > used)) continue;
      chmax(dp[use | used], dp[used] + USE[use]);
    }
  }

  cout << dp[(1<<N)-1] << endl;

  return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<string>
#include<cstdlib>
#include<cctype>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;
}
// ----------------------------------------------------------------------------

int main(){
  int A,B;
  cin >> A >> B;
  int N;
  cin >> N;
  if(A > B){
    swap(A,B);
  }
  int cnt=0;
  for(int i=0; i<A; i++){
    cnt++;
    N -= B;
    if(N <= 0){
      cout << cnt << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())

a = list(map(int, input().split()))

ans = 'APPROVED'

for num in a:
  if num % 2 == 0:
    if num % 3 != 0 and num % 5 != 0:
      ans = 'DENIED'
      
print(ans)
    

Measured memory_bytes: 2940
def CountingSort(A, B, k):
    C = [0 for i in range(k+1)]
    
    for j in range(n):
        C[A[j]] += 1
     
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    
    for j in range(n-1,-1,-1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
        
n = int(input())
A = list(map(int,input().split()))
B = [0 for i in range(len(A))]
k = 10000
CountingSort(A, B, k)
print(*B)


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

int main() {
  int a,b;
  cin>>a>>b;
  int count=0;
  string x,y;
  for(int i=a;i<=b;i++){
    x=to_string(i);
    reverse(x.begin(),x.end());
    y=to_string(i);
    if(x==y)count++;
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef		 long long int     ll;
typedef		vector<ll>      vll;
#define     fi              first
#define     se              second
#define		pb              push_back
#define		nn              "\n"
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		ss              ' '
#define     pii             pair<ll,ll>
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
const double eps = 1e-8;







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

    ll n;
    cin>>n;
    ll ans=n;
    ans+=(n*n);
    ans+=(n*n*n);
    cout<<ans<<nn;





}


/* Final check before submit :

1. array size or integer overflow.

2. Think twice,code once.check all possible counter test case.

3. Be careful about corner case! n=1?k=1? something about 0?

4. avoid stupid mistake!complexity(t/m)?precision error?submit same code twice?

5. if got WA than remember that you are missing something common.
   *** Be confident!!! who knows? may be your one step back to AC ***

*/



Measured memory_bytes: 3484
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <list>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <limits>

      /*########  IN THE NAME OF ALLAH   ##########*/

using namespace std;
#define ll long long
#define MAX 999999999999999999
#define nl printf("\n")
#define  r0 return 0
#define  r1 return 1
#define sf1(x)  scanf("%lld",&x)
#define sf2(x,y)  scanf("%lld %lld",&x,&y)
#define sf3(x,y,z)  scanf("%lld %lld %lld",&x,&y,&z)
#define pf1(x)  printf("%lld\n",x)
#define pf2(x,y)  printf("%lld %lld\n",x,y)
#define pf3(x,y,z)  printf("%lld %lld %lld\n",x,y,z)
#define yes  printf("YES\n")
#define no  printf("NO\n")
#define pc(x)  printf("Case %lld :",x)
#define pb push_back
#define mp make_pair
#define pa pair<ll,ll>
#define mem(a,b) memset(a,b,sizeof(a))
#define MIN  -99999999999999999
#define READ(f) freopen(f,"r",stdin)
#define WRITE(f) freopen(f,"w",stdout)
#define pi 2.0*acos(0.0)
#define sp printf(" ")
#define vs(v) (v.begin(),v.end())

ll max(ll a,ll b) {if(a>b) return a; else return b;} ll min(ll a,ll b) {if(a<b) return a; else return b;}
ll power(ll B,ll P){ if(P==0) return 1; ll X=power(B,P/2); if(P%2==0) return X*X; else return B*X*X;}
ll fx[]={1,-1,0,0}; ll fy[]={0,0,1,-1};

ll A[3000005],B[3000005],C[3000005],visited[3000005],level[3000005];
char CH[1000][1000];
vector<ll>V,G;

int main()
{
  ll T,N,E,u,Q,v,i,j,k,sum=0,ck=0,x,y,cs=0;
  ll a,b,c;
  ll ans;
  cin>>a>>b>>c;
  ll d=4*a*b;
  ll d1=c-(a+b);
  if(d1<=0) {cout<<"No"<<endl;r0;}
  ck=d1*d1;
  if(d<ck) {cout<<"Yes"<<endl;}
  else cout<<"No"<<endl;





 /************ALEYA YOUSUF ************/


 /************ALLAH IS ALMIGHTY ************/
return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    // Write Your Code Below
    int p, q, r;cin >> p >> q >> r;
    int a = max(r, max(p, q));
    int ans = p+q+r-a;
    cout << ans << endl;

}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    static Scanner sc;

    private static void nextArr(int[] h) {
        for(int i = 0; i < h.length; i++) h[i] = sc.nextInt();
    }

    private static int nextInt() {
        return sc.nextInt();
    }

    private static void print(Object... vals) {
        for(int i = 0; i < vals.length; i++) {
            if (i != vals.length - 1) {
                System.out.print(vals[i] + ",");
            } else {
                System.out.print(vals[i]);
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[] p = new double[n];
        for(int i = 0; i < n; i++) p[i] = sc.nextDouble();

        double[][] dp = new double[n + 1][n + 1];
        dp[1][0] = (1 - p[0]);
        dp[1][1] = p[0];
        for(int i = 2; i <= n; i++) dp[1][i] = 0;
        for(int i = 2; i <= n; i++) dp[i][0] = dp[i - 1][0] * (1 - p[i - 1]);
                
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j<= n; j++) {
                dp[i][j] = p[i - 1] * dp[i - 1][j - 1] + (1 - p[i - 1]) * dp[i - 1][j];
            }
        }

        double ans = 0;
        for(int i = (n + 1) / 2; i <= n; i++) {
            ans += dp[n][i];
        }
        print(ans);
    }
}


Measured memory_bytes: 123352
#include<string>
#include<iostream>
 
using namespace std;
 
int main()
{
    string s;   getline(cin,s);
 
    for(int i=0;i<s.length();i++){
        if     (s.substr(i,5)=="apple")   s.replace(i,5,"peach");
        else if(s.substr(i,5)=="peach")   s.replace(i,5,"apple");
    }
 
    cout<<s<<endl;
 
    return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  int b;
  int c;
  cin >> a >> b >> c;
  int d = c-b; 
  vector<int> s(a);
  if(b == c){
    for(int i = 1;i < a;i++){
      s.at(i) = a-i;}}
 else{ for(int i = 1;i < a;i++){
     for(int j = i+1;j < a+1;j++){
       if(i <= b && j <= b){
         s.at(j-i)++;}
       else if(i <= b && j > b && j <= c)
       {s.at(min(j-i,b-i+1+c-j))++;}
       else if(i <= b){
         s.at(b-i+j-c+1)++;}
       else if(i < c && c < j){
         s.at(min(j-i,i-b+1+j-c))++;}
       else if(i < c){
         s.at(min(j-i,d+1-j+i))++;}
       else{s.at(j-i)++;}
     }
  }
     }
  for(int i = 1;i < a;i++){
    cout << s.at(i) << endl;}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) begin(c), end(c)
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6+6;


int main(){
	//freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
	
	ll x;
	
	cin>>x;
	
	ll a = 100;
	
	for(int k=1;;++k){
		a = a + a/100;
		if(a>=x){
			cout<<k<<endl;
			break;
		}
	}
	
	
	return 0;
}


Measured memory_bytes: 3648
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>

using namespace std;

int h, w;
char s[12][13];
string ss[12];
int a[12];
int b[12];

void dfs1(int x, bool f) {
    if (x == w) {
        puts("YES");
        exit(0);
    } else if (b[x] != -1) {
        dfs1(x + 1, f);
    } else {
        int i, j;
        
        for (i = x + 1; i < w; i++) {
            if (b[i] != -1) continue;
            
            for (j = 0; j < h; j++) {
                if (s[j][x] != s[a[j]][i]) break;
            }
            
            if (j == h) {
                b[x] = i;
                b[i] = x;
                
                dfs1(x + 1, f);
                
                b[x] = b[i] = -1;
            }
        }
        
        if (!f) {
            for (j = 0; j < h; j++) {
                if (s[j][x] != s[a[j]][x]) break;
            }
            
            if (j == h) {
                b[x] = x;
                
                dfs1(x + 1, true);
                
                b[x] = -1;
            }
        }
    }
}

void dfs2(int x, bool f) {
    if (x == h) {
        dfs1(0, w % 2 == 0);
    } else if (a[x] != -1) {
        dfs2(x + 1, f);
    } else {
        int i;
        
        for (i = x + 1; i < h; i++) {
            if (a[i] != -1) continue;
            if (ss[x] != ss[i]) continue;
            
            a[x] = i;
            a[i] = x;
            
            dfs2(x + 1, f);
            
            a[x] = a[i] = -1;
        }
        
        if (!f) {
            a[x] = x;
            
            dfs2(x + 1, true);
            
            a[x] = -1;
        }
    }
}

int main() {
    int i;
    
    scanf("%d %d", &h, &w);
    
    for (i = 0; i < h; i++) scanf("%s", s[i]);
    
    for (i = 0; i < h; i++) {
        ss[i] = s[i];
        sort(ss[i].begin(), ss[i].end());
    }
    
    for (i = 0; i < h; i++) a[i] = -1;
    for (i = 0; i < w; i++) b[i] = -1;
    
    dfs2(0, h % 2 == 0);
    
    puts("NO");
    
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)){
			int N = Integer.parseInt(sc.next());
			int x=0;
			int maxX=0;
			String S = sc.next();
			for(char c:S.toCharArray()){
				if(c=='I'){
					x++;
					maxX=Math.max(maxX, x);
				}else{
					x--;
				}
			}
			System.out.println(maxX);
		}
	}
}


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

int main () {
  int N;
  cin >> N;
  vector<long long>A(N);
  vector<long long>B(N);
  long long sumA = 0;
  long long sumB = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    sumA += A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> B.at(i);
    sumB += B.at(i);
  }
  
  if (sumA < sumB){
    cout << -1 << endl;
    return 0;
  }
  
  long long dis = 0;
  long long add = 0;
  long long count = 0;
  vector<long long>plus(N,0);
  for (int i = 0; i < N; i++) {
    if (A.at(i) > B.at(i)){
      plus.at(i) = A.at(i) - B.at(i);
    }
    else if (A.at(i) < B.at(i)){
      dis += B.at(i) - A.at(i);
      count++;
    }
  }
  
  if (count == 0){
    cout << 0 << endl;
    return 0;
  }
  
  sort(plus.begin(), plus.end());
  reverse(plus.begin(), plus.end());
  
  for (int i = 0; i < N; i++) {
    add += plus.at(i);
    if (dis <= add){
      cout << count + i + 1 << endl;
      return 0;
    }
  }
}
    
    
    
  
  
  
  
   

Measured memory_bytes: 5512
import sys
import math
import functools
from collections import deque
sin = sys.stdin

n = int(sin.readline())
stones = [int(i) for i in sin.readline().split()]
minCost = [float('inf') for i in range(n)]
minCost[0] = 0
minCost[1] = abs(stones[0] - stones[1])

for i in range(2, len(stones)):
    minCost[i] = min(minCost[i-1] + abs(stones[i-1] - stones[i]),
                     minCost[i-2] + abs(stones[i-2] - stones[i]))

print(minCost[n-1])


Measured memory_bytes: 14108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

pii p[maxn];

pair<pii,int> v[maxn];

vector<pair<int,pii>> edge;

int DJS[maxn];
int sz[maxn];

int find(int u){
    if(DJS[u]==u) return u;
    return DJS[u]=find(DJS[u]);
}

int mrg(int u,int v){
    u=find(u);v=find(v);
    if(u==v) return -1;
    if(sz[u]>sz[v]) swap(u,v);
    DJS[u]=v;
    sz[v]+=sz[u];
    return sz[v];
}

int main()
{
	IOS;
    int n;
    cin>>n;
    REP(i,n) DJS[i]=i;
    REP(i,n) sz[i]=1;
    REP(i,n) cin>>p[i].F>>p[i].S;
    sort(p,p+n);
    REP(i,n-1) edge.pb(MP(p[i+1].F-p[i].F,MP(i,i+1)));
    //for(auto i:edge) cout<<i<<'\n';
    REP(i,n) v[i]=MP(MP(p[i].S,p[i].F),i);
    sort(v,v+n);
    REP(i,n-1){
        edge.pb(MP(v[i+1].F.F-v[i].F.F,MP(v[i+1].S,v[i].S)));
    }
    sort(ALL(edge));
    
    ll ans=0;
    for(auto i:edge){
        //cout<<i.F<<' '<<i.S<<'\n';
        int tmp=mrg(i.S.F,i.S.S);
        if(tmp==-1);
        else ans+=i.F;
        if(tmp==n){
            cout<<ans<<'\n';
            return 0;
        }
    }
	return 0;
}


Measured memory_bytes: 11892
import sys
input = sys.stdin.readline

a, b, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)

for i in range(m):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)
print(ans)

Measured memory_bytes: 64800
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N, K, C;
    cin >> N >> K >> C;

    string S; cin >> S;

    vector<int> R(K), L(K);

    int x = 0;
    REP(i, N) {
        if (S[i] == 'o') {
            R[x++] = i;
            if (x == K) break;
            i += C;
        }
    }

    reverse(ALL(S));
    REP(i, N) {
        if (S[i] == 'o') {
            L[--x] = N - i - 1;
            if (x == 0) break;
            i += C;
        }
    }

    REP(i, K) {
        if (R[i] == L[i]) cout << R[i] + 1 << endl;
    }
}


Measured memory_bytes: 3348
n, m = [int(_) for _ in input().split()]
w = {}
seen = {}
d = {}
for i in range(n):
    w[i+1] = []
    seen[i+1] = 0
    d[i+1] = -1
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    w[a].append(b)
    w[b].append(a)

# print(w)
# print(seen)
# print(d)

que = [1]
n_que = []

seen[1] = 1

while len(que) != 0:
    for i in range(len(que)):
        p = que.pop()
        for u in w[p]:
            if seen[u] == 0:
                d[u] = p
                seen[u] = 1
                n_que.append(u)
            else:
                continue
    que = n_que
    n_que = []

# print(seen)
# print(d)

flag = 1
for i in range(n):
    if seen[i+1] == 0:
        flag = 0

if flag == 0:
    print('No')
else:
    print('Yes')
    for i in range(1, n):
        # print('n', n)
        # print('i', i)
        print(d[i+1])


Measured memory_bytes: 114668
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9;
int main(){
    ll s;
    cin>>s;
    ll y2=ceil((1.0*s)/(1.0*INF));
    ll x2=y2*INF-s;
    cout<<"0 0 1000000000 1"<<" "<<x2<<" "<<y2;
}


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

int main()
{
  string x;
  cin >> x;
  stack<char> t;
  for(int i=0; i<x.size(); i++){
    if(x[i]=='S') t.push(x[i]);
    else if(x[i]=='T'){
      if(!t.empty()&&t.top()=='S') t.pop();
      else t.push(x[i]);
    }
  }
  cout << t.size() << endl;
}

Measured memory_bytes: 644
N = int(input())

if(N > 111 and N <= 222):
    print('222')
if(N > 222 and N <= 333):
    print('333')
if(N > 333 and N <= 444):
    print('444')
if(N > 444 and N <= 555):
    print('555')
if(N > 555 and N <= 666):
    print('666')
if(N > 666 and N <= 777):
    print('777')
if(N > 777 and N <= 888):
    print('888')
if(N > 888 and N <= 999):
    print('999')
if N <= 111:
    print('111')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
// (setq-default c-basic-offset 2)

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

  if (n >= 10) {
    cout << r << endl;
  } else {
    // r = inner - 100 * (10 - n)
    int inner = r + 100 * (10 - n);
    cout << inner << endl;
  }

  return 0;
}


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

int main() {
  int n;
  cin>>n;
  int a[5565];
  bool ans=true;
  int count=0;
  for(int i=1;i<5556;i++){
    ans=true;
    int k=10*i+1;
    for(int j=2;j<k;j++){
      if(k%j==0){
        ans=false;
        break;
      }
    }
    if(ans){
      a[count]=k;
      count++;
    }
  }
  for(int i=0;i<n-1;i++){
    cout<<a[i]<<' ';
  }
  cout<<a[n-1]<<endl;
}


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

using namespace std;

int main()
{
    long long int a,res;
    double b;
    scanf("%lld%lf",&a,&b);

    res = (long long int)((b*100)+0.5);
    res *= a;
    res /= 100;


    printf("%lld",res);


    return 0;
}


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

using namespace std;
#define _for(i,j,N) for(int i = (j); i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
typedef long long LL;
int get_int(){int x;scanf("%d",&x);return x;}
int get_ll(){LL x;scanf("%lld",&x);return x;}

void tests(){
    ;
}

int main()
{
    int N = get_int();
    int res = 0;
    int h = -1;
    _for(i,0,N){
        int num = get_int();
        if(num >= h) res++;
        h = max(num,h);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int main(){
	cin>>n>>a>>b;
	for(int i=a;i<=b;i++)
	if(i%n==0)
	{
	cout<<"OK";
	return 0;
	}
	
	cout<<"NG";
	return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cctype>
#include<cmath>
#include<vector>
#include<climits>
#include<queue>

using namespace std;


int d,g,q,ans=INT_MAX;
int score,p[12],c[12];
bool qa[12];

int cnt(int a)
{
    long long tmp=0;
    int count=0;
    do
    {
        tmp+=100*(a+1);
        count++;
        if (count==p[a])
        {
            tmp+=c[a];
        }
    }
    while(score+tmp<g && count<p[a]);

    if (score+tmp>=g)
    {
        if (ans>q+count)
        {
            ans=q+count;
        }
    }
    else
    {
        qa[a]=true;
        q+=count;
        score+=tmp;
        for (int i=0; i<d; i++)
        {
            if (qa[i]==false)
            {
                cnt(i);
                qa[i]=false;
            }
        }
        score-=tmp;
        q-=count;
    }
    return 0;
}

int main(void)
{
    scanf("%d%d",&d,&g);
    for (int i=0; i<d; i++)
    {
        scanf("%d%d",&p[i],&c[i]);
        qa[i]=false;
    }
    for (int i=0; i<d; i++)
    {
        cnt(i);
        qa[i]=false;
    }
    printf("%d\n",ans);
    return 0 ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 234567;
long long f[5][maxn];
long long a[maxn];
int main(){
	int n; cin >> n;
	for(int j = 0; j < 5; j++) f[j][0] = 1ll<<50;
	f[0][0] = 0;
	f[1][0] = 0;
	f[2][0] = 0;
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		f[0][i + 1] = f[0][i] + x;
		f[1][i + 1] = min(f[1][i], f[0][i]) + (x%2) + (x == 0 ? 2 : 0);
		f[2][i + 1] = min(min(f[2][i], f[1][i]), f[0][i]) + 1 - (x%2);
		f[3][i + 1] = min(min(f[1][i], f[0][i]), min(f[2][i], f[3][i])) + (x%2) + (x == 0 ? 2 : 0);
		f[4][i + 1] = min(min(f[4][i], f[3][i]), min(f[2][i], min(f[1][i], f[0][i]))) + x;
	}
	cout << min(f[3][n], min(f[4][n], f[2][n])) << endl;
	return 0;
}


Measured memory_bytes: 9088
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b == c || b + c == a || c + a == b) {
		cout << "Yes";
		return 0;
	}
	cout << "No";
	return 0;
}

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

typedef long long ll;

/* メモリ食い過ぎ注意 */
#define int ll
#define ALL(v) v.begin(), v.end()
#define _REP(i, n) for (int i = 0; i < n; i++)
#define REP(n) _REP(i, n)

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    int n, k;
    int h[100001] = {};
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    h[0] = h[1];

    int dp[n + 1];
    for (int i = 0; i <= n; i++)
        dp[i] = INF;

    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int kk = 1; kk <= k; kk++)
        {
            if (i - kk < 0)
            {
                break;
            }
            dp[i] = min(dp[i], dp[i - kk] + abs(h[i] - h[i - kk]));
        }
    }
    // for (int i = 0; i <= n; i++)
    //     cout << dp[i] << " ";
    // cout << endl;
    cout << dp[n] << endl;
}

Measured memory_bytes: 1792
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s = input()
n = len(s)
a,b,c = 0,0,0
if s == s[::-1]:a=1
if s[:n//2] == s[:n//2][::-1]:b = 1
if s[n//2+1:] == s[n//2+1:][::-1]: c = 1
if a and b and c:
  print("Yes")
else:
  print("No")

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

int main()
{
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i=0; i<n; i++)
    cin >> s.at(i);
  int m;
  cin >> m;
  vector<string> t(m);
  for (int i=0; i<m; i++)
    cin >> t.at(i);
  
  int tmp, max = 0;
  
  for (int i=0; i<n; i++) { //比べるやつ
    tmp = 0;
    for (int j=0; j<n; j++) { //比べられるやつ
		if (s.at(i) == s.at(j))
          tmp++;
    }
    for (int j=0; j<m; j++) { //比べられるやつ
		if (s.at(i) == t.at(j))
          tmp--;
    }
    if (tmp > max) max = tmp;
  }
  for (int i=0; i<m; i++) { //比べるやつ
    tmp = 0;
    for (int j=0; j<m; j++) { //比べられるやつ
		if (t.at(i) == t.at(j))
          tmp--;
    }
    for (int j=0; j<n; j++) { //比べられるやつ
		if (t.at(i) == s.at(j))
          tmp++;
    }
    if (tmp > max) max = tmp;
  }
  
  cout << max << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {

    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean ok = true;
        String s = sc.next();
        int[] cnt = new int[27];
        for(int i=0;i<s.length();i++){
            cnt[s.charAt(i)-'a']++;
        }
        for(int i=0;i<27;i++){
            if(cnt[i]%2!=0)ok=false;
        }
        System.out.println(ok?"Yes":"No");
    }
}


Measured memory_bytes: 23124
package main

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

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 100000000)

	n, k := scanInt(), scanInt()
	s := scanText()

	c := 0

	for i := 0; i < n; i++ {
		if s[i] == 'L' {
			if i != 0 && s[i] == s[i-1] {
				c++
			}
		} else {
			if i != n-1 && s[i] == s[i+1] {
				c++
			}
		}
	}
	
	fmt.Println(min(2*k+c, n-1))
}

func min(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res > a[i] {
			res = a[i]
		}
	}
	return res
}

func max(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res < a[i] {
			res = a[i]
		}
	}
	return res
}



Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define EPS (1e-7)
#define INF (1e9 + 10)
#define PI (acos(-1))
#define MOD (1000000007)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<x<<endl
template<class T>string watch(T &v){string res="";for(auto f:v)res+=(to_string(f)+" ");return res;}
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; }
#define int long long

main() {
    int N,x;cin >> N >> x;
    VI a(N, 0);
    REP(i, N) {
        cin >> a[i];
    }
    int ans = 0;
    REP(i, N-1) {
        int d = a[i] + a[i+1] - x;
        if (d>0){
            if (a[i+1] - d >= 0){
                a[i+1] -= d;
            } else {
                a[i] -= (d - a[i+1]);
                a[i+1] = 0;
            }
            ans += d;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
using System;
namespace AtCoder
{

    class Program
    {
        static void Main(string[] args)
        //static void dummy()
        {
            // 入力データパース
            string szRate = Console.ReadLine();
            int rate = int.Parse(szRate);

            string szRet = null;
            if( rate < 1200)
            {
                szRet = "ABC";
            }
            else
            {
                szRet = "ARC";
            }
            Console.WriteLine(szRet);
        }
    }
}


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

int main(void){
  int i, cmp, times, taro=0, hanako=0;
  char t[100], h[100];
  scanf("%d", &times);
  for(i=0;i<times;i++){
    scanf("%s %s", t, h);
    if((cmp = strcmp(t,h)) > 0) taro += 3;
    else if(cmp < 0) hanako += 3;
    else{
      taro++;
      hanako++;
    }
  }
  printf("%d %d\n", taro, hanako);
  return 0;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_c() {
	ll n, m, r;

	cin >> n >> m;

	ll ans;

	ans = 100 * (n - m) + 1900 * m;
	ans *= pow(2, m);

	cout << ans << "\n";
}

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

	solve_abc_c();

	return 0;
}

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

int n,m,flag=0,pos;
char s[55],pre[55];

int main()
{
	string s1,s2;
	cin>>s1>>s2;
	n=s1.size(),m=s2.size();
	for (int i=1;i<=n;i++)  s[i]=s1[i-1];
	for (int i=1;i<=m;i++)  pre[i]=s2[i-1];
	
	for (int i=n-m+1;i>=1;i--)
	{
		bool dog=1; 
		for (int j=i;j<=i+m-1;j++)
		{
			if (s[j]!=pre[j-i+1]&&s[j]!='?')
			{
				dog=0;
				break;
			}
		}
		if (dog==1)
		{
			flag=1;
			pos=i;
			break;
		}
	}
	if (flag==0)
	{
		cout<<"UNRESTORABLE"<<endl;
		return 0;
	}
	for (int i=pos;i<=pos+m-1;i++)  s[i]=pre[i-pos+1];
	for (int i=1;i<=n;i++)
	{
		if (s[i]=='?')  s[i]='a';
	}
	for (int i=1;i<=n;i++)  cout<<s[i];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

const int mx = 510;
vector<int> c(mx),s(mx),f(mx);
int time(int now,int pos){
	int ret,st = s[pos];
	while(st < now){
		st += f[pos];
	}
	ret = st-now+c[pos];
	return ret;
}

int main(){
	int n;
	cin >> n;
	
	for(int i = 0; i < n-1; i++) cin >> c[i] >> s[i] >> f[i];
	vector<int> ans(n,0);

	for(int i = 0; i < n-1; i++){
		ans[i] += s[i];
		for(int j = i; j < n-1; j++){
			ans[i] += time(ans[i],j);
		}
	}

	for(int i = 0; i < n; i++){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  long long N,K;cin>>N>>K;
  
  while(true){
    N=N%K-K;
    if(N<=0){
      if(0-N<N+K){
        cout<<0-N<<endl;
        break;
      }
      else{
        cout<<N+K<<endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 3608