akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define fs first
#define sc second
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<tuple<ll,ll>> vtl;
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

void solve(){
    //abc120c
    string s;
    cin>>s;
    ll k;
    cin>>k;
    ll n=min((ll)s.size(),k);
    rep(i,n){
      if(s[i]!='1'){
        cout<<s[i];
        return;
      }
    }
  cout<<1<<endl;
}

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

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int mod = 1000000007;
        long sum = (2 * pow(9, n, mod)) % mod;
        long part = sum - pow(8, n, mod);
        if (part < 0) part += mod;
        long ans = pow(10, n, mod) - part;
        System.out.println(ans < 0 ? ans + mod : ans);
    }

    static long pow(int x, int y, long mod) {
        if (y == 0) return 1L;
        long res = pow(x, y / 2, mod);
        if (y % 2 == 1) {
            return (((res * res) % mod) * x) % mod;
        }
        return (res * res) % mod;
    }
}

Measured memory_bytes: 35640
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long N, K, Q, ANS = 1000000000;
	cin >> N >> K >> Q;
	vector<long long> A(N);
	vector<pair<long long, long long> > B(N);
	vector<bool> C(N, true);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i] = { A[i], i };
	}
	sort(B.begin(), B.end());
	for (int i = 0; i < N; i++) {
		vector<vector<long long> > V;
		V.clear();
		V.push_back(vector<long long>(0));
		for (int j = 0; j < N; j++) {
			if (C[j]) V[V.size() - 1].push_back(A[j]);
			else V.push_back(vector<long long>(0));
		}
		vector<long long> W;
		for (int j = 0; j < V.size(); j++) {
			if (V[j].size() < K) continue;
			sort(V[j].begin(), V[j].end());
			for (int k = 0; k < V[j].size() - K + 1; k++) {
				W.push_back(V[j][k]);
			}
		}
		sort(W.begin(), W.end());
		if (W.size() < Q) {
			break;
		}
		ANS = min(ANS, W[Q - 1] - W[0]);
		C[B[i].second] = false;
	}
	cout << ANS << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll x,y,z;
  cin >> x >> y >> z;
  pr(x*y/2);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons;

alias A = Tuple!(int, "i", int, "j");

A[300*300+1] AS;
long[300*300+1] DS;

void main()
{
    auto hwd = readln.split.to!(int[]);
    auto H = hwd[0];
    auto W = hwd[1];
    auto D = hwd[2];

    foreach (j; 0..H) 
        foreach(i, e; readln.split.to!(int[]))
            AS[e] = A(i.to!int, j);
    
    foreach (i; 1..D+1) {
        long d;
        DS[i] = d;
        while (i <= H*W-D) {
            auto a = AS[i];
            i += D;
            auto ad = AS[i];
            d += abs(a.i - ad.i) + abs(a.j - ad.j);
            DS[i] = d;
        }
    }

    auto Q = readln.chomp.to!int;
    foreach (_; 0..Q) {
        auto lr = readln.split.to!(int[]);
        auto L = lr[0];
        auto R = lr[1];

        writeln(DS[R] - DS[L]);
    }
}

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

namespace AtCoder {
    class Program {
        
        static void Main(string[] args) {

            var input = Console.ReadLine().Split(' ');

            var X = int.Parse(input[2]);
            var Y = int.Parse(input[3]);

            var x = Console.ReadLine().Split(' ').Select(e => int.Parse(e)).Max();
            var y = Console.ReadLine().Split(' ').Select(e => int.Parse(e)).Min();

            var war = true;

            var xflag = false;
            var yflag = false;
            for (int Z = X + 1; Z <= Y; Z++) {

                xflag = false;
                yflag = false;
                if(x < Z) {
                    xflag = true;
                }
                if(y >= Z) {
                    yflag = true;
                }
                if(xflag && yflag) {

                    war = false;
                    break;
                }
            }
            Console.WriteLine(war ? "War" : "No War");
        }
    }
}

Measured memory_bytes: 13268
import sys
n, k = map(int, input().split())
lines = sys.stdin.readlines()
trees = [None] * n
for i in range(n):
    trees[i] = int(lines[i])

trees.sort()

#print(trees)
min_h = sys.maxsize
k_1 = k - 1
for i in range(n-k+1):
    height_diff = trees[i + k_1] - trees[i]
    if height_diff < min_h:
        min_h = height_diff


print(min_h)

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

int main() {
  int N, x;
  cin >> N >> x;
  int a[110];
  for (int i=0;i<N;++i) {
    cin >> a[i];
  }
  sort(a, a + N);
  int count = 0;
  for (int i=0;i<N;++i) {
    x -= a[i];
    if (x < 0) {
      break;
    } else {
      ++count;
    }
  }
  if (x > 0) {
    cout << count - 1 << endl;
  } else {
    cout << count << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);

    int n = scan.nextInt();
    String str = scan.next();
    int cnt = 0;

    for (int i = 0; i < n - 2; i++) {
      if (str.substring(i, i + 3).equals("ABC")) {
        cnt++;
      }
    }

    System.out.println(cnt);
  }

}

Measured memory_bytes: 25172
#include <iostream>
 
using namespace std;
int main() {
  string s;
  cin >> s;
  if (s[0] == s[1] && s[1] == s[2] || s[1] == s[2] && s[2] == s[3])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();

    let mut ans = n - 1;
    for i in 1..1_000_001 {
        if n % i == 0 {
            ans = std::cmp::min(ans, i + n / i - 2);
        }
    }

    format!("{}\n", ans)
}
#[test]
fn test_solve() {
   assert_eq!(solve("10\n"), "5\n");
   assert_eq!(solve("50\n"), "13\n");
   assert_eq!(solve("10000000019\n"), "10000000018\n");
}
fn main() {
    let mut buf = String::new();
    use std::io::Read;
    std::io::stdin().read_to_string(&mut buf).unwrap();
    use std::io::Write;
    std::io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}
struct Scanner<I> {
    src: I,
}
impl<'a> Scanner<std::str::SplitWhitespace<'a>> {
    fn from_str(src: &'a str) -> Self {
        Scanner {
            src: src.split_whitespace(),
        }
    }
}
#[allow(dead_code)]
impl<'a, I> Scanner<I>
where
    I: std::iter::Iterator<Item = &'a str>,
{
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.src.next().unwrap().parse().ok().expect("Parse error")
    }
    fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    fn chars(&mut self) -> Vec<char> {
        self.src.next().unwrap().chars().collect()
    }
}

Measured memory_bytes: 4352
#include <stdio.h>

int main(void)
{
	char pattern[10][10];
	char buf[10][10];
	int x, y, i, j;
	
	for (i = 0; i < 8; i++){
		scanf("%s", pattern[i]);
	}
	
	
	/*pattern[y][x]*/
	for (i = 0; i < 3; i++){
		switch (i){
		  case 0:
		  	printf("90\n");
			break;
			
		  case 1:
		  	printf("180\n");
			break;
			
		  case 2:
		  	printf("270\n");
			break;
		}
		
		/*90度回転*/
		for (y = 0; y < 8; y++){
			for (x = 0; x < 8; x++){
				buf[y][x] = pattern[7 - x][y];
			}
			buf[y][8] = '\0';
		}
		
		for (y = 0; y < 8; y++){
			for (x = 0; x < 8; x++){
				pattern[y][x] = buf[y][x];
			}
			pattern[y][8] = '\0';
		}
		
		for (j = 0; j < 8; j++){
			printf("%s\n", pattern[j]);
		}
	}
	
	return (0);
}

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

a_even = a[0::2]
a_odd  = a[1::2] 

# even
if (n - 1) % 2 == 0: # 0-(n-1)の実施なので(n-1)の偶奇を判定
    b = a_even.copy()
    b.reverse()
    b = b + a_odd
# odd
else:
    b = a_odd.copy()
    b.reverse()
    b = b + a_even

b = list(map(str, b))
print(' '.join(b))

Measured memory_bytes: 37164
N, x = gets.split.map &:to_i
A = gets.split.map &:to_i
A.concat([0])

ans = 0
N.times do |i|
  a, b = A[i], A[i+1]
  #p a:a, b:b
  if a+b > x
    d = (a+b)-x
    db = [d, b].min
    da = [d-b, 0].max
    ans += d
    A[i+1] -= db
  end
end
p ans


Measured memory_bytes: 11148
#include <stdio.h>

int min(int a,int b){
	if (a>b){
		return b;
	}
	return a;
}

int main(void){
	int D,G,p[11],c[11];
	scanf("%d %d",&D,&G);
	int i;
	for(i=0;i<D;i++){
		scanf("%d %d",&p[i],&c[i]);
	}
	int ans = 1e9;
	for(int mask=0;mask<(1<<D);++mask){	// 1<<Dはより2^D回繰り返すってワケ。
		int s=0,num=0,rest_max=1;
		for(i=0;i<D;++i){		//問題の個数分このループを回す。
			if(mask>>i & 1){	//論理積をとっている。これは全ての問題を解くやつを選んでいる。
				s += 100* (i+1) * p[i] + c[i];//sは獲得した点数。
				num += p[i];	//numは解いた問題の数、解いた問題の数を加算している。
			}else{
				rest_max = i;	//iは解いていない中で最も配点の高い問題？
			}
		}
		if(s<G){//もしも点数が上で足りていない場合以下を実行する。
			int s1 = 100*(rest_max + 1);//s1というのは解いていない中で最も配点が高い問題を解いた時の点数(ボーナスは含めない)
			int need = (G-s+s1-1)/s1;//needは必要な数？どれだけ解けばいいのか？
			if(need >= p[rest_max]){//問題数が足りず届かない場合は
				continue;//次のforループに向かう。
			}
			num += need;
		}
		ans = min(ans,num);
	}
	printf("%d",ans);
	return 0;
}

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

if N % 2 == 0:
    count = (N - 2) * N // 2
    print(count)
    for i in range(1, N + 1, 1):
        for j in range(i + 1, N + 1, 1):
            if i + j == N + 1:
                continue
            else:
                print(i, j)
else:
    count = ((N - 2) * (N - 1) + (N - 1)) // 2
    print(count)
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1, 1):
            if i + j == N:
                continue
            else:
                print(i, j)



Measured memory_bytes: 3736
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# エントリーポイント
def main():
    N, M = input(int, int)
    ABC = input([[int, 3], M])

    # Nから到達できる辺のみ抽出する
    g = nlist([N + 1], [])
    for a, b, c in ABC:
        g[b] += [(a, c)]

    que, rch = [N], {N}
    while que:
        cur = que.pop()
        for nxt, _ in g[cur]:
            if nxt in rch: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    # ベルマンフォード法で負の最短経路(スコアの最大値)を導出する
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -c
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        # 負の閉路を除外する
        print("inf")
        return
    print(-g[N])
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    char s[213121];
    char t[123213];
    Scs(s);
    Scs(t);

    int N = strlen(s);
    bool ans = true;
    Rep(i,N) ans = ans && s[i] == t[i];

    YesNo(ans);

    return 0;
}



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

int64_t from_zero(int64_t n)
{
    if (n % 4 == 0)
    {
        return n;
    }
    else if (n % 4 == 1)
    {
        return 1;
    }
    else if (n % 4 == 2)
    {
        return n ^ 1;
    }
    else
    {
        return 0;
    }
}

int main()
{
    int64_t a, b;
    cin >> a >> b;
    int64_t res;
    if (a == 0)
    {
        res = from_zero(b);
    }
    else
    {
        res = from_zero(a - 1) ^ from_zero(b);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main(){
    var a, b int
    fmt.Scan(&a)
    fmt.Scan(&b)
    if a < b {
        fmt.Println("a < b")
    }else if a > b{
        fmt.Println("a > b")
    }else{
        fmt.Println("a == b")
    }
}


Measured memory_bytes: 1156
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    int n;
    int ans = 0;
    cin >> n;
    map<ll,int> mli;
    rep(i,n){
        ll x;
        cin >> x;
        mli[x]++;
    }
    for(auto u : mli){
        if(u.first != u.second){
            if(u.first < u.second) ans += u.second - u.first;
            else ans += u.second;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6272
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "tmp.cpp"

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

  int n;
  cin >> n;
  vl a(n);
  REP(i, n) { cin >> a[i]; }

  ll ans = 0;
  ll res = 0;
  REP(i, n) {
    if (a[i] == 0) {
      res = 0;
      continue;
    }
    ans += (a[i] + res) / 2;
    res = (a[i] + res) % 2;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
 
int main(void){
    char ch;
    int alpha[26]={0},i;
    while(scanf("%c",&ch)!=EOF){
        if('A'<=ch && ch<= 'Z'){
            alpha[ch-'A']++;
        }
        else if('a'<=ch && ch<= 'z'){
            alpha[ch-'a']++;
        }
    }
    for(i=0;i<26;i++){
        printf("%c : %d\n",'a'+i,alpha[i]);
    }
    return 0;
}


Measured memory_bytes: 2108
X = int(input())

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n ** 0.5) + 1):
        if n % k == 0:
            return False

    return True

while True:
    if is_prime(X) == 1:
        print(X)
        break
    X += 1

Measured memory_bytes: 3060
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
H = defaultdict(lambda: 0)
N = int(input())
dot = [()]*N
mod = 998244353
for i in range(N):
    x, y = inpl()
    dot[i] = (x, y)
for i in range(N):
    for j in range(i+1,N):
        x1, y1 = dot[i]
        x2, y2 = dot[j]
        A = y1 - y2
        B = x2 - x1
        C = y1*x2 - x1*y2
        if A < 0:
            A *= -1
            B *= -1
            C *= -1
        gcdabc = gcd(gcd(A,B), C)
        A //= gcdabc
        B //= gcdabc
        C //= gcdabc
        H[(A, B, C)] += 1
ans = (2**N - N - 1 )%mod
for i in H.values():
    i = int((1+(1+8*i)**(1/2))/2)
    ans -= (2**i - i - 1)%mod
print(ans%mod)

Measured memory_bytes: 7464
N,A,B = map(int,input().split())
ans=0

for i in range(0,N+1):
  keta_sum = 0
  i = str(i)
  for j in range(len(str(i))):
    keta_sum += int(i[j])
  if A <= keta_sum <= B:
    ans += int(i)

print(ans)

Measured memory_bytes: 9000
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef pair< int , int > P;
typedef pair< pair< int , P > , bool > PP;
//コスト,座標,次どっちの足？(true:左,false:右)
#define fr first
#define sc second
#define MAX_W 30
#define MAX_H 60
#define mp(a,b) make_pair(a,b)

const int dx[]={1,1,1,1,1,2,2,2,3},dy[]={2,1,0,-1,-2,1,0,-1,0};
int w,h;
char mas[MAX_H][MAX_W];

bool over(int nx,int ny){
  return nx < 0 || nx >= w || ny < 0 || ny >= h;
}

int bfs(vector<P>& st){
  bool used[MAX_H][MAX_W][2] = {};
  priority_queue< PP , vector<PP> , greater<PP> > que;
  for(int i = 0 ; i < st.size() ; i++ ){
    que.push(PP(mp(0,st[i]),false));
    que.push(PP(mp(0,st[i]),true));
  }
  while(!que.empty()){
    PP p = que.top();
    que.pop();
    if(used[p.fr.sc.fr][p.fr.sc.sc][p.sc]++) continue;
    if(mas[p.fr.sc.fr][p.fr.sc.sc] == '0') return p.fr.fr;
    for(int i = 0 ; i < 9 ; i++ ){
      int ny = p.fr.sc.fr + dy[i] , nx = p.fr.sc.sc + (p.sc ? dx[i] : -dx[i]);
      if(over(nx,ny) || mas[ny][nx] == 'X') continue;
      que.push(PP(mp(p.fr.fr+(mas[ny][nx]-'0'),P(ny,nx)),!p.sc));
    }
  }
  return -1;
}

int main(){
  while(cin >> w >> h , w){
    vector<P> st;
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
        if(mas[i][j] == 'S') st.push_back(P(i,j));
        if(mas[i][j] == 'T') mas[i][j] = '0';
      }
    }
    cout << bfs(st) << endl;
  }
}

Measured memory_bytes: 1308
<?php

ini_set('memory_limit', '1024M');

$sc = new Scanner();

$N = $sc->nextInt();
$K = $sc->nextInt();
$h = [];

for($i = 0; $i < $N; $i++) {
    $h[] = $sc->nextInt();
}

$dp = [];

for($i = 1; $i < $N; $i++) {
    $dp[$i] = pow(10,10);
    for($j = $i - 1; $j >= $i - $K && $j >= 0; $j--) {
        $dp[$i] = min($dp[$i], $dp[$j] + abs($h[$i] - $h[$j]));
    }
}

echo $dp[$N-1] . PHP_EOL;

class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}


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

const int N = 1000;

int main() {
	int M[N][N];
	int n, u, k, v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			M[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
				cin >> v;
				v--;
				M[u][v] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j) cout << " ";
			cout << M[i][j];
		}
		cout << endl;
	}
	return 0;
}



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

using namespace std;

int main() {
    long N, M, K;
    cin >> N >> M >> K;
    vector<long> A(N), B(M);
    for (long a_index = 0; a_index < N; ++a_index) {
        cin >> A[a_index];
    }
    for (long b_index = 0; b_index < M; ++b_index) {
        cin >> B[b_index];
    }

    vector<long> accumulation_a(N+1), accumulation_b(M+1);
    accumulation_a[0] = 0;
    accumulation_b[0] = 0;
    for (long a_index = 1; a_index < N+1; ++a_index) {
        accumulation_a[a_index] = A[a_index-1] + accumulation_a[a_index-1];
    }
    for (long b_index = 1; b_index < M+1; ++b_index) {
        accumulation_b[b_index] = B[b_index-1] + accumulation_b[b_index-1];
    }


    long ans = 0;
    long best_b_index = M;

    for (long a_index = 0; a_index < N+1; ++a_index) {
        long rest = K - accumulation_a[a_index];
        if (rest < 0) continue;
        if (rest == 0) {
            long cand_ans = a_index;
            if (cand_ans > ans) {
                ans = cand_ans;
            }
            continue;
        }
        for (long b_index = best_b_index; b_index >= 0; --b_index) {
            if (rest >= accumulation_b[b_index]) {
                best_b_index = b_index;
                long cand_ans = a_index + b_index;
                if (cand_ans > ans) {
                    ans = cand_ans;
                }
                break;
            }
        }
    }

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 9588
N,M=map(int,input().split())
X=[int(i) for i in input().split()]
Y=[int(i) for i in input().split()]
mod=pow(10,9)+7
a=0
b=0
for i in range(N):
    a=(a+(-N+2*i+1)*X[i])%mod
for i in range(M):
    b=(b+(-M+2*i+1)*Y[i])%mod
print((a*b)%mod)

Measured memory_bytes: 83172
#include <iostream>
#include <vector>
#define MOD 1000000007
#define ll long long
using namespace std;

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	ll sum = 1;
	vector<int> A(N + 1,0);
	for (int i = 1; i <= N; i++) {
		int a; cin >> a;
		if (N % 2 == 0 && a == 0) { cout << 0 << endl; return 0; }
		A[a]++;
		if (A[a] > 2) { cout << 0 << endl; return 0; }
		if (A[a] == 2 && a == 0) { cout << 0 << endl; return 0; }
		if (A[a] == 2) { sum = (sum * 2) % MOD;}
	}
	cout << sum << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int b[100010];
int c[100010];
int dp[100010][5];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][1] = max(dp[i-1][2]+b[i],dp[i-1][3]+c[i]);
        dp[i][2] = max(dp[i-1][1]+a[i],dp[i-1][3]+c[i]);
        dp[i][3] = max(dp[i-1][1]+a[i],dp[i-1][2]+b[i]);
    }
    int ans = max(dp[n][1],max(dp[n][2],dp[n][3]));
    printf("%d\n",ans);
}


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

#define ll long long
#define endl '\n'
#define REP(i, a, n) for(int i=a; i<n; ++i)
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const double PI = 3.141592653589793238460;
const ll mod = 1e9 + 7;

void FAST(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}

int main(){
  FAST();

  int n;
  string s;
  cin >> n >> s;

  string t(s.begin(), s.begin() + n/2);
  t += t;
  if(t == s)
    cout << "Yes\n";
  else
    cout << "No\n";

  return 0;
}


Measured memory_bytes: 256
N = int(input())
def solve(n):
	if n == 0:
		return "0"
	out = []
	while n != 0:
		n, rem = divmod(n, -2)
		if rem < 0:
			n += 1
			rem -= -2
		out.append(rem)
	return "".join(map(str, out[::-1]))
print(solve(N))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define vi vector<int>
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;

typedef pair<int,int> P1;
typedef pair<int,P1> P2;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

#define MAX_N 100002

int dp[MAX_N];
vector<int> G[MAX_N];
bool d[MAX_N]={};
queue<P1> que;


int main() {
	int n;
	cin>>n;
	rep(i,MAX_N)dp[i]=-inf;
	rep(i,n-1){
		int a1,b1;
		cin>>a1>>b1;
		G[a1].push_back(b1);
		G[b1].push_back(a1);
	}

	int k;
	cin>>k;
	rep(i,k){
		int v1;
		int p1;
		cin>>v1>>p1;
		dp[v1]=p1;
		d[v1]=true;
		for(auto it:G[v1]){
			que.push(P1(p1-1,it));
		}
	}
	while(!que.empty()){
		P1 pp1=que.front();que.pop();
		int cost=pp1.first;
		int to=pp1.second;
		if(dp[to]==cost||dp[to]>cost+1)continue;
		if(d[to]||dp[to]==cost+1){
			cout<<"No"<<endl;
			return 0;
		}
		dp[to]=cost;
		for(auto it:G[to]){
			que.push(P1(cost-1,it));
		}
	}
	cout<<"Yes"<<endl;
	rep(i,n)cout<<dp[i+1]<<endl;
	return 0;
}


Measured memory_bytes: 9336
//---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    use std::str::SplitWhitespace;
    use std::io::Read;
    use std;
    pub struct Scanner<'a> {
        it: SplitWhitespace<'a>
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace()
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            match self.it.next().unwrap().parse::<T>() {
                Ok(v) => v,
                _ => panic!("Scanner error")
            }
        }
        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect::<Vec<T>>()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }
    }
    pub fn read_string() -> String {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }
}
//---------- end scannner ----------

use std::io::Write;

fn main() {
    let sc = scanner::read_string();
    let sc = scanner::Scanner::new(&sc);
    let out = std::io::stdout();
    let out = std::io::BufWriter::new(out.lock());
    run(sc, out);
}

fn run(mut sc: scanner::Scanner, mut out: std::io::BufWriter<std::io::StdoutLock>) {
    let a: u32 = sc.next();
    let b: u32 = sc.next();
    let ans = if a >= 13 {
        b
    } else if a >= 6 {
        b / 2
    } else {
        0
    };
    writeln!(out, "{}", ans).unwrap();
}


Measured memory_bytes: 4352
while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        dlist=[]
        for i in range(n):
            [d,p]=[int(x) for x in raw_input().split()]
            dlist.append([d,p])
        dlist.sort(key=lambda x:x[1])
        P=0
        while(m>0 and len(dlist)>0):
            mostdanger=dlist.pop()
            if m>=mostdanger[0]:
                m=m-mostdanger[0]
            else:
                P=(mostdanger[0]-m)*mostdanger[1]
                m=0
        if len(dlist)==0:
            print P
        else:
            for sec in dlist:
                P=P+sec[0]*sec[1]
            print P

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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {
    int N, T, A;
    cin >> N >> T >> A;
    vector<int> h(N);
    REP(i, N) cin >> h[i];

    int ans = -1;
    double maxD = 1e9;
    REP(i, N) {
        double tmp = (double)T - (double)h[i] * 0.006;
        double a = abs(tmp - A);
        if (a < maxD) {
            maxD = a;
            ans = i;
        }
    }
    print(ans + 1);
}

signed main() {
    solve();
}


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

using namespace std;

int main() {
    string s;
    cin>>s;
    char a=s[0];
    char b=s[1];
    char c=s[2];
    char d=s[3];
    if(a==b||b==c||c==d)
    cout<<"Bad";
    else
    cout<<"Good";
    
    
    
     
    return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	if n < 10 || n%2 == 1 {
		fmt.Println(0)
		return
	}

	tcnt := 0 //ka
	for div := 10; div <= n; div *= 5 {
		tcnt += n / div
	}

	fmt.Println(tcnt)

}
func d(s string, i int) int {
	return int(s[i] - '0')
}
func pow(a, b int) int {
	var ret int = 1
	for b > 0 {
		if (b & 1) == 1 {
			ret *= a
		}
		a *= a
		b >>= 1
	}
	return ret
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
#include <iostream>
#include <string>
#include <limits.h>
#include <math.h>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(void){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), b(n);
    vector<pair<ll, ll>> x(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        x[i] = make_pair(a[i], b[i]);
    }
    
    sort(x.begin(), x.end());
    
    ll f = 0; 
    for (int i = 0; i < n; i++) {
        f += x[i].second;
        if (f >= k) {
            cout << x[i].first << endl;
            return 0;
        }
    }
    
}


Measured memory_bytes: 3328
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <vector>
using f32 = float;
using f64 = double;
using i8 = int_fast8_t;
using u8 = uint_fast8_t;
using i16 = int_fast16_t;
using u16 = uint_fast16_t;
using i32 = int_fast32_t;
using u32 = uint_fast32_t;
using i64 = int_fast64_t;
using u64 = uint_fast64_t;
void resolver();
inline void fast_io() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}
template <class T>
inline std::vector<T> read_vector() {
    size_t n;
    std::cin >> n;
    std::vector<T> ret(n);
    for (T &i : ret) {
        std::cin >> i;
    }
    return ret;
}
void t_case() {
    i64 t;
    std::cin >> t;
    while (t--) {
        resolver();
    }
}
void single_case() { resolver(); }

int main(int argc, char *argv[]) {
    fast_io();
    // t_case();
    single_case();
}

void resolver() {
    using namespace std;

    i32 k;
    cin >> k;
    vector<i32> all = read_vector<i32>();
    sort(all.begin(), all.end());
    i32 len = all.size();
    all.push_back(all[0]);
    i32 max_value = 0;
    for (i32 i = 0; i < len; i++) {
        i32 dist = abs(all[i] - all[i + 1]);
        if (i == len - 1) {
            dist = k - all[i] + all[0];
        }
        if (max_value < dist) {
            max_value = dist;
        }
    }
    cout << k - max_value;
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9  + 5;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	for(int i = 0;i<n;++i) {
		cin >> h[i];
	}	
	vector<int> dp(n, INF);
	dp[0] = 0;
	for(int i = 0;i<n;++i) {
		for(int j = i+1;j <= i+k;++j) {
			if(j<n)
				dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
		}
	}	
	cout << dp[n-1] << '\n';
} 


Measured memory_bytes: 3968
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
 
#define X first
#define Y second
#define N 302
#define M 11
 
typedef long long ll;
const int Mod = 1000000007;
const int INF = 1 << 30;
 
const double eps = 1e-10;

vector< pair<int, int> > lim[N];
int dp[N][N][N];

bool Invalid(int a, int b, int c)
{
	int r = max(a, max(b, c));
	for (int i = 0; i < lim[r].size(); ++i)
	{
		int cnt = 0;
		if (a >= lim[r][i].X) cnt++;
		if (b >= lim[r][i].X) cnt++;
		if (c >= lim[r][i].X) cnt++;
		if (cnt != lim[r][i].Y) return true;
	}
	
	return false;
}

int main()
{
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    
    int n, m;
    scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= m; ++i)
	{
		int l, r, x;
		scanf("%d %d %d", &l, &r, &x);
		lim[r].push_back(make_pair(l, x));
	}
		
	
	dp[1][0][0] = 1;
	dp[0][1][0] = 1;
	dp[0][0][1] = 1;
	
	int res = 0;
	for (int k = 1; k <= n; ++k)
	{
		for (int i = 0; i <= k; ++i)
		{
			for (int j = 0; j <= k; ++j)
			{
				if (i == j && i > 0) continue;
				if (Invalid(k, i, j)) dp[k][i][j] = 0;
				if (Invalid(i, k, j)) dp[i][k][j] = 0;
				if (Invalid(i, j, k)) dp[i][j][k] = 0;
				
				//cout << k <<  " " << i <<" " << j <<" " << dp[k][i][j] <<" " << dp[i][k][j] << " " << dp[i][j][k] << endl;
				if (k == n) 
				{
					res = (res + dp[k][i][j]) % Mod;
					res = (res + dp[i][k][j]) % Mod;
					res = (res + dp[i][j][k]) % Mod;
					continue;
				}
				
				(dp[k + 1][i][j] += dp[k][i][j]) %= Mod;
				(dp[k][k + 1][j] += dp[k][i][j]) %= Mod;
				(dp[k][i][k + 1] += dp[k][i][j]) %= Mod;
				
				(dp[k + 1][k][j] += dp[i][k][j]) %= Mod;
				(dp[i][k + 1][j] += dp[i][k][j]) %= Mod;
				(dp[i][k][k + 1] += dp[i][k][j]) %= Mod;
				
				
				(dp[k + 1][j][k] += dp[i][j][k]) %= Mod;
				(dp[i][k + 1][k] += dp[i][j][k]) %= Mod;
				(dp[i][j][k + 1] += dp[i][j][k]) %= Mod;
			}
		}
	}
	
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 107520
/* 
 * Author: aps
 * Time: 19-06-2019 22:52:44
**/
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int,int> pii;

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

inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x;}
inline ll sub(ll x, ll y) { x -= y; if (x < 0) x += mod; return x;}
inline ll mul(ll x, ll y) { return ((x % mod) * (y % mod)) % mod;}
inline ll power(ll a, ll b) {
    ll x = 1;
    while (b) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline ll inv(ll a) { return power(a, mod - 2);}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    int n,k; cin >> n >> k;
    
    int a[n];
    for(int i=0;i<n;i++) cin >> a[i];

    int ans = 0;
    priority_queue<int, vi, greater<int> > pq;
    for(int i=-1;i<n;i++){
        for(int j=n;j>i;j--){
            int sum = 0, y = 0;
            while(!pq.empty()) pq.pop();
            for(int p=0;p<=i;p++) {
                sum += a[p]; y++;
                pq.push(a[p]);
            }
            for(int p=n-1;p>=j;p--) {
                sum += a[p]; y++;
                pq.push(a[p]);
            }
            if(y > k) break;
            ans = max(ans,sum);
            for(int x=1;x<=y;x++){
                if((x+y) > k) break;
                sum -= pq.top();
                pq.pop();
                ans = max(ans,sum);
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) cin >> L[i] >> R[i];
    sort(rbegin(L), rend(L));
    sort(begin(R), end(R));
    Int ans = 0, tmp = 0;
    for (int i = 0; i < N; i++) {
        tmp += L[i]; ans = max(ans, tmp);
        tmp -= R[i]; ans = max(ans, tmp);
    }
    tmp = 0;
    for (int i = 0; i < N; i++) {
        tmp -= R[i]; ans = max(ans, tmp);
        tmp += L[i]; ans = max(ans, tmp);
    }
    cout << ans * 2 << '\n';
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main() {

	int n;

	while(cin >> n) {
		if(!n) {
			break;
		}
		int t=0;
		n=1000-n;
		while(n>=500) {
			n-=500;
			t++;
		}
		while(n>=100) {
			n-=100;
			t++;
		}
		while(n>=50) {
			n-=50;
			t++;
		}
		while(n>=10) {
			n-=10;
			t++;
		}
		while(n>=5) {
			n-=5;
			t++;
		}
		while(n>=1) {
			n-=1;
			t++;
		}

		cout << t << endl;
	}

	return 0;

}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=100005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

string s; int n, A[MAXN];
void fail(){
	cout<<-1;
	exit(0);
}
void edge(int x, int y){
	cout<<x<<" "<<y<<"\n";
}
main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>s;
	n = s.length();
	FOR(i,1,n) A[i] = (int) s[i-1] - '0';
	if (!A[1]) fail();
	if (A[n]) fail();
	FOR(i,1,n) if (A[i] != A[n-i]) fail();
	
	int prev = 1;
	int sz = 1;
	FOR(i,2,n){
		if (!A[i]) continue;
		edge(prev, sz+1);
		FOR(j, sz+2, i){
			edge(sz+1, j);
		}
		prev = sz+1;
		sz=i;
	}
	edge(prev, n);
}


Measured memory_bytes: 2000
import itertools

N = int(input())
L = list(map(int, input().split()))
count = 0

for p in itertools.combinations(L, 3):
  if len(set(p)) != 3:
    continue
  else:
    if p[0] < p[1] + p[2] and p[1] < p[0] + p[2] and p[2] < p[0] + p[1]:
      count += 1
print(count)
    

Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
#define nl '\n' 
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pii pair <int,int>
ll mod=1000000007;
int dp[1001][1001];
int main()
{
	string s;cin>>s;
	cout<<s;
	if(s[s.length()-1]=='s')
		cout<<"es";
	else
		cout<<"s";
}

Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main() {
	int n;
	string s;
	cin >> n >> s;
	int ans = 0;
	for (int i = 0; i <= n - 3; i++) {
		if (s[i] == 'A'&&s[i + 1] == 'B'&&s[i+2] == 'C') ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

int a[2010];

int main () {
  int N, Z, W;
  cin >> N >> Z >> W;
  for (auto i = 0; i < N; ++i) {
    cin >> a[i];
  }
  int kaname = a[N-1];
  for (auto i = 0; i < N; ++i) {
    a[i] = abs(a[i] - a[N-1]);
  }
  reverse(a, a+N);
  int mini[2010];
  int maxi[2010];
  int tmin, tmax;
  mini[1] = a[1];
  maxi[1] = a[1];
  tmin = a[1];
  tmax = a[1];
  for (auto i = 2; i < N; ++i) {
    if (a[i] < tmin) {
      mini[i] = a[i];
      tmin = a[i];
    } else {
      mini[i] = mini[i-1];      
    }
    if (a[i] > tmax) {
      maxi[i] = a[i];
      tmax = a[i];
    } else {
      maxi[i] = maxi[i-1];      
    }
  }
  int ans = abs(W - kaname);
  for (auto i = 1; i < N; ++i) {
    ans = max(mini[i], ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)


int main(int argc, char *argv[]) {
  i64 N, S, i, j;
  cin >> N >> S;
  vi A(N);
  REP(0, N, i) {
    cin >> A[i];
  }

  i64 NUM = 998244353LL;

  vvi G(N, vi(S+1, 0));
  G[0][0] = 1;
  if(A[0] <= S) {
    G[0][A[0]] = 1;
  }
  REP(1, N, i) {
    G[i][0] += 1;
    if(A[i] <= S) {
      G[i][A[i]] += 1;
    }
    REP(0, S+1, j) {
      G[i][j] += G[i-1][j] * 2;
      G[i][j] %= NUM;
      
      if(j - A[i] >= 0) {
	G[i][j] += G[i-1][j-A[i]];
	G[i][j] %= NUM;
      }
    }
  }

  /*
  REP(0, N, i) {
    REP(0, S+1, j) {
      cout << G[i][j] << " ";
    }
    cout << endl;
  }
  */
  
  cout << G[N-1][S] % NUM << endl;

  return 0;
}


Measured memory_bytes: 73692
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 998244353
#define ordered_set tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update>
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
ll dp[3005][3005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    dp[a][b] = 1ll;
    for(ll i=a;i<=c;i++)
    {
    	for(ll j=b;j<=d;j++)
    	{
    		if(i > a)
    			dp[i][j] = (dp[i][j] + (dp[i-1][j]*j)%mod)%mod;
    		if(j > b)
    			dp[i][j] = (dp[i][j] + (dp[i][j-1]*i)%mod)%mod;
    		if(i>a && j>b)
    			dp[i][j] = (dp[i][j] - (dp[i-1][j-1]*((i-1)*(j-1))%mod)%mod + mod)%mod;
    	}
    }
    cout << dp[c][d] << nl;
    return 0;
}

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


void solve(){
    ll n,i;
    cin>>n;
    vector<ll>a(n+1);
    for(int x=1;x<=100;x++)
    {
     for(int y=1;y<=100;y++)
     {
      for(int z=1;z<=100;z++)
      {
         ll cal=x*x+y*y+z*z+x*y+x*z+y*z;
          if(cal>n)break;
              a[cal]++;
      }
       if((x*x+y*y)>n)break;
     }
    }
    for(i=1;i<=n;i++)
        cout<<a[i]<<endl;
    
}


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

Measured memory_bytes: 3656
#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=2e5+5;
int a[maxn];

int main()
{
    int n=read();
    REP(i,1,n) a[i]=read();
    LL ans=0;
    REP(i,2,n) if(a[i]<a[i-1]) ans+=a[i-1]-a[i],a[i]=a[i-1];
    cout<<ans;

    return 0;
}


Measured memory_bytes: 4372
#include<bits/stdc++.h>
using namespace std;
long long a,b;
int main(){
    cin>>a>>b;
    if(a>0)cout<<"Positive";
    else if(a==0||(a<0&&b>0))cout<<"Zero";
    else if((abs(b)-abs(a))%2!=0)cout<<"Positive";
    else cout<<"Negative";
    return 0;
}

Measured memory_bytes: 256
import sys
from collections import deque
#import numpy as np
import math
#sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    lent = len(t)
    lens = len(s)
    ans = lent
    for i in range(lens-lent+1):
        tmp = 0
        for j in range(lent):
            if t[j] != s[j+i]:
                tmp += 1
        ans = min(ans,tmp)
    print(ans)
    return

if __name__=='__main__':
    s = S()
    t = S()
    solve()

Measured memory_bytes: 9296