akhauriyash/Code-Regression huggingface dataset:
#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...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(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;

const ll MOD = 1000000007;
//const ll MOD = 998244353;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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

    mint len_x = 0;

    ll prev;
    REP(i, n) {
        ll a; cin >> a;
        if (i > 0) {
            len_x += mint(a - prev) * i * (n - i);
        }
        prev = a;
    }

    mint len_y = 0;
    REP(i, m) {
        ll a; cin >> a;
        if (i > 0) {
            len_y += mint(a - prev) * i * (m - i);
        }
        prev = a;
    }

    print(len_x * len_y);
}


Measured memory_bytes: 3636
import java.util.*;
public class Main {
	public static void main(String[] args) {
		long H = new Scanner(System.in).nextLong(), ans = 1;
		for(int i = 0; i < (int) (Math.log(H) / Math.log(2)) + 1; i++)
			ans *= 2;
		System.out.println(ans-1);
	}
}


Measured memory_bytes: 23764
EPS = 1e-4

#外積
def OuterProduct(one, two):
	tmp = one.conjugate() * two
	return tmp.imag

#内積
def InnerProduct(one, two):
	tmp = one.conjugate() * two
	return tmp.real

def solve(a, b, c, d):
	if abs(OuterProduct(b-a, d-c)) <= EPS:
		return 2
	elif abs(InnerProduct(b-a, d-c)) <= EPS:
		return 1
	else:
		return 0

n = int(input())
for _ in range(n):
	pp = list(map(int, input().split()))
	p = [complex(pp[i], pp[i+1]) for i in range(0, 8, 2)]
	print(solve(p[0], p[1], p[2], p[3]))


Measured memory_bytes: 5648
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, cnt[2] = {0, 0};
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[x & 1]++;
    }
    if (cnt[1] % 2 == 0) {
        cout << "YES\n";
    } else if (cnt[0] + cnt[1] == 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}


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

int main()
{	
	int n,m,l,b;
	cin >> n >> m >>l;
	int A[100][100] = {{}};
	int B[100][100] = {{}};
	int C[100][100] = {{}};
	long long lo =0;
	for(int i=0; i<n;i++){
		for(int j=0 ; j<m ; j++){
			cin >>b;
			A[i][j] = b;
		}
	}

	for(int i=0; i<m;i++){
		for(int j=0 ; j<l ; j++){
			cin >>b;
			B[i][j] = b;
		}
	}

	for(int i=0; i<n;i++){
		for(int j=0 ; j<l ; j++){
			lo = 0;
			for(int k=0; k<m ;k++){
				lo += A[i][k]*B[k][j];
			}
			if(j ==0) cout << lo;
			else cout << " " << lo;
		}
		cout << endl;
	}



    return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;

void solve(){

    int a,b,c;
    cin >> a >> b >> c;
    string s="win";
    if(a+b+c>=22) s = "bust";
    cout << s << endl;

}

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


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc073/tasks/abc073_d

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))



# default import
from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

# ダイクストラか？
# 全点間の最小距離を取得
# rについてpermutationして。その通りに訪れたときの距離をシミュレーション
# 最小値を選ぶ

N, M, r = read_ints()
R = [x - 1 for x in read_ints()]
adj_mat = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c

# print(csr_matrix(adj_mat, dtype='int'))
D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)
# print(D)
# 全探索パート
ans = 2 ** 31


def get_kyori(p):
    ret = 0
    for ps, pt in zip(p[:-1], p[1:]):
        ret += D[ps, pt]
    return ret


for p in permutations(R):
    ans = min(ans, get_kyori(p))
print(int(ans))


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

typedef long long ll;
#define mod 1000000007

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

void solve(){
    int n, k;
    cin>>n>>k;
    vector<int> h(n), dp(n, INT_MAX);
    for(auto& e:h){
        cin>>e;
    }
    dp[0] = 0;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j <= i+k && j < n; j++){
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
        }
    }
    cout<<dp[n-1];

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

    return 0;
}

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

int main() {
	int n, a, q, m;
	cin >> n;

	bool dp[2001] = {true, false};
	for (int i=0; i<n; ++i) {
		cin >> a;
		for (int j=2000; j>=0; --j) {
			dp[j+a] |= (dp[j] && j+a<2001);
		}
	}

	cin >> q;
	for (int i=0; i<q; ++i) {
		cin >> m;
		cout << (dp[m] ? "yes" : "no") << endl;
	}
}

Measured memory_bytes: 1152
N=int(input())
t=[0]*N
r=set(range(N))
for _ in[0]*N:
 x,y,z=list(map(int,input().split()))
 t[x]=[y,z]+[0]*5
 r-={y,z}
def f(i,p,s,d):
 if i<0:return-1
 l,r=t[i][:2]
 t[i][2:]=[p,s,(l!=-1)+(r!=-1),d,max(f(l,i,r,d+1),f(r,i,l,d+1))+1]
 return t[i][-1]
f(r.pop(),-1,-1,0)
for i in range(N):
 print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i,*t[i][2:],'root'if not t[i][5]else'internal node'if t[i][4]else'leaf'))


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

void solve()
{
	ll n,d; cin>>n>>d;
	int count = 0;
	for(int i=0;i<n;i++){
		ll a,b;
		cin>>a>>b;
		double dist = 0;

		dist = sqrt((a*a)+(b*b));
		if(dist <= d ){
			count++;
		}
	}
	cout<<count<<'\n';
}

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

Measured memory_bytes: 3692
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)

def main():
    h,w = LI()
    a = [S() for _ in range(h)]
    t = set()
    for i in range(h):
        ai = a[i]
        for j in range(w):
            if ai[j] == '#':
                t.add(i*w+j)


    r = 0
    u = t | set()
    while 1:
        k = set()
        for ij in t:
            i = ij // w
            j = ij % w
            for di,dj in dd:
                ni = i + di
                nj = j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                nk = ni*w + nj
                if nk in u:
                    continue
                k.add(nk)
        if not k:
            break
        r += 1
        t = k
        u |= k

    return r


print(main())




Measured memory_bytes: 135784
import java.util.*;
import java.util.Scanner;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    
	    Scanner scanner = new Scanner(System.in);
	    int A = scanner.nextInt();
	    int P = scanner.nextInt();

        int numPiece = 3*A+P;
        int numPie = numPiece / 2;

	    System.out.println(String.valueOf(numPie));
	}
}


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

int main(){
	int n;
	cin >> n;
	int i = 1;
	while(1){
		if(i < n) i *= 2;
		else if(i == n) break;
		else{
			i /= 2;
			break;
		}
	}
	cout << i ;
	return 0;
}


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

string S;

int main(){
  cin >> S;
  if(S[5]=='0' && (S[6]=='1' ||S[6]=='2' ||S[6]=='3' ||S[6]=='4')){
    cout << "Heisei" << endl;
  }else{
    cout << "TBD" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int a, b, c, d;

int main() {
	cin >> a >> b >> c >> d;
	a = max(a, c);
	b = min(b, d);
	if (a < b) {
		cout << b - a << endl;
	}
	else {
		cout << 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,n) for(lli i=0;i<n;i++)
#define repb(i,n) for(lli i=n-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define bg() begin()
#define en() end()
#define ft first
#define sc second
#define vect_lli_it vector<lli>::iterator
#define set_lli_it set<lli>::iterator
#define inf 1e18
#define all(X) X.begin(),X.end()
#define iterate(X) for(it=X.begin();it!=X.end();it++)
lli combi(lli n,lli k)
{
    lli ans=1;
    k=k>n-k?n-k:k;
    lli j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
lli findlcm(vector <lli> arr, lli n)
{
    lli ans = arr[0];
    for (lli i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));

    return ans;
}
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,t;
    cin>>s>>t;
    if((lli)t.length()==(lli)s.length()+1){
    	lli check=0;
    	rep(i,s.length()){
    		if(s[i]!=t[i]){
    			check=1;
    			break;
			}
		}
		if(check==0)
		cout<<"Yes";
		else
		cout<<"No";
	}
	else
	cout<<"No";
    return 0;
}


Measured memory_bytes: 3660
N,K=map(int,input().split())
S=list(input())

if S[0]=="L":
    key="R"
    not_key="L"
else:
    key="L"
    not_key="R"

flag=False
count=0
for i in range(1,N):
    if count==K:
        break
    if S[i]==key:
        if flag==False:
            flag=True
            S[i]=not_key
        elif flag==True:
            S[i]=not_key
    elif S[i]==not_key:
        if flag==True:
            count+=1
            flag=False

L_flag=False
R_flag=False
count=0
for i in range(N):
    if S[i]=="L":
        if L_flag==False:
            L_flag=True
            R_flag=False
        elif L_flag==True:
            count+=1

    elif S[i]=="R":
        if R_flag==False:
            R_flag=True
            L_flag=False
        elif R_flag==True:
            count+=1

print(count)

Measured memory_bytes: 4084
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
 
signed main() {
    IOS;
    #ifdef LOCAL
        freopen("input.txt","r", stdin);
        freopen("output.txt","w",stdout);
    #endif
    int a, b;
    cin >> a >> b;
    if((a+b)&1)
        cout << "IMPOSSIBLE";
    else
        cout << ((a+b) >> 1);   
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
 int main(void){
 int a, b, c;
 
 scanf("%d%d%d", &a, &b, &c);
 
int ispoor = 0;
 if (a == b && b != c) ispoor = 1;
 if (b == c && c != a) ispoor = 1;
 if (c == a && a != b) ispoor = 1;
 
if (ispoor) {puts("Yes");
} else {
 puts("No");
}
 
 return 0;
 }

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


class Program {

	static long mod = 1000000007;
	//static long mod =998244353;
	static int[] ans;
	static void Main(string[] args) {

		char[] cs = new char[] { ' ' };
		//char[] cs = new char[] { ' ', ',' };

		//int n = int.Parse(Console.ReadLine());
		//int val = int.Parse(Console.ReadLine());
		//int[] vals = parseAry(Console.ReadLine().Split(cs));
		//string str = Console.ReadLine();
		//string[] strs = Console.ReadLine().Split(cs);

		//string res = "";
		double res = 0;



		int n = int.Parse(Console.ReadLine());

		res = 1.0 * ( (n / 2 )+1) / n;
		if ( n == 1 ) { res = 1; }
		if ( n % 2 == 0 ) { res = 0.5; }
		
				Console.WriteLine(res);

		return;

	}



	//	int配列をスペース区切りの文字列に変換
	static string stringBuilderArrayInt(int[] a) {
		StringBuilder sb = new StringBuilder();

		for ( int i = 0; i < a.Length; i++ ) {
			if ( a[i] == 1 ) { sb.Append(i + " "); }
		}
		if ( sb.Length > 1 ) {
			sb = sb.Remove(sb.Length - 1, 1);
		}
		return sb.ToString(); ;
	}


	//	文字列strをindex番目からdで上書き
	static string strOverWrite(string str, int i, string s) {
		return str.Remove(i, s.Length).Insert(i, s);
	}

	//　String[]  ----->  int[]
	static int[] parseAry(string[] str) {
		int[] nums = new int[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = int.Parse(str[i]); }
		return nums;
	}
	//　String[]  ----->  long[]
	static long[] parseAryL(string[] str) {
		long[] nums = new long[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = long.Parse(str[i]); }
		return nums;
	}

	//文字列を1文字ずつString[]に入れる
	static string[] strAry(String str) {
		string[] re = new string[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { re[i] = str[i].ToString(); }
		return re;
	}



}

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

vector<int64_t> memo;

int64_t greedy(const string& s, int64_t index, int64_t C) {
    if (index >= s.size()) {
        return 0;
    }
    if (memo[index] != -1) {
        return memo[index];
    }

    for (int64_t i = index; i < s.size(); i++) {
        if (s[i] == 'o') {
            return memo[index] = (1 + greedy(s, i + C + 1, C));
        }
    }

    return memo[index] = 0;
}

int main() {
    int64_t N, K, C;
    string S;

    cin >> N >> K >> C >> S;
    memo.resize(N + 1, -1);

    vector<int64_t> ans;
    for (int64_t i = 0; i < S.size(); i++) {
        if (S[i] == 'x') {
            continue;
        }

        //S[i] == 'o'
        //ここが必須かどうか
        //S[i] = 'x'として判定してみる
        //ダメなら必須
        int64_t num = greedy(S, i + 1, C);
        if (num < K) {
            ans.push_back(i + 1);
        }

        //ここをオフにしない場合、絶対に選ぶのが得
        K--;
        i += C;
    }

    for (int64_t value : ans) {
        cout << value << endl;
    }
}

Measured memory_bytes: 8052
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int N;
long *A;
long *B;

int main(int argc, char *argv[]) {
	int sr;
	int i;
	long sum=0;

	sr=scanf("%d", &N);

	A = (long *)malloc(sizeof(long)*(N+1));
	B = (long *)malloc(sizeof(long)*N);

	for (i=0; i<=N; i++) {
		sr=scanf("%ld", A+i);
	}
	for (i=0; i<N; i++) {
		sr=scanf("%ld", B+i);
	}

	for (i=0; i<N; i++) {
//printf("A[%d]=%ld A[%d]=%ld B[%d]=%ld\n", i, A[i], i+1, A[i+1], i, B[i]);
		if (B[i] >= A[i]) {
			sum += A[i];
//printf("s %d: %ld\n", i, sum);
			B[i] -= A[i];
			if (A[i+1] >= B[i]) {
				sum += B[i];
//printf("s %d: %ld\n", i, sum);
				A[i+1] -= B[i];
				continue;
			}
			sum += A[i+1];
//printf("s %d: %ld\n", i, sum);
			A[i+1] = 0;
			continue;
		}
		sum += B[i];
//printf("s %d: %ld\n", i, sum);
	}

	printf("%ld\n", sum);
	fflush(stdout);

	return 0;

}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const ll MOD = 1e9+7;
const int INF = 1001001001;
// const ll INF = 1000000000000000000LL;
  
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<ll> table(n+1);
    for(int i=1;i<=n;i++){
        table[i] = table[i-1]+a[i-1];
    }
    map<ll,ll> mp;
    rep(i,n+1)
        mp[table[i]]++;
    ll ans = 0;
    for(auto iter:mp){
        if(iter.second>1){
            ll cur = iter.second*
            (iter.second-1);
            cur/=2;
            ans+=cur;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 18764
package main

// Solution for https://atcoder.jp/contests/abc073/tasks/abc073_c

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

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var n int
	con.Scan(&n)
	a := make([]int, n+1)
	for i := 0; i < n; i++ {
		con.Scan(&a[i])
	}
	sort.Ints(a[:n])
	c, d, p := 0, 0, 0
	for i := 0; i <= n; i++ {
		if a[i] == p {
			c++
		} else {
			if c%2 == 1 {
				d++
			}
			c = 1
			p = a[i]
		}
	}
	con.Println(d)
	return nil
}


Measured memory_bytes: 4312
def c_many_formulas(S):
    import itertools
    ans = 0
    for operators in itertools.product(('', '+'), repeat=len(S) - 1):
        operator = list(operators) + ['']  # zip()に渡す文字列の長さを合わせる
        formula = ''.join([value + op for value, op in zip(S, operator)])
        ans += eval(formula)
    return ans

S = input()
print(c_many_formulas(S))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i ++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll MOD = 1e9 + 7;
const ll INF = 1e10;

int main() {
    int n; cin >> n;
    ll ans = 0;
    vector<vector<int>> dist;
    vector<vector<int>> edge;
    rep(i,n) {
        vector<int> a(n);
        rep(j,n) {
            cin >> a[j];
            if (i < j) {
                edge.push_back({a[j],i,j});
                ans += a[j];
            }
        }
        dist.push_back(a);
    }

    rep(k,n)rep(i,n)rep(j,n) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);

    for (vector<int> e: edge) {
        int c = e[0], a = e[1], b = e[2];
        if (c > dist[a][b]) {
            ans = -1;
            break;
        }
        rep(i,n) {
            if (i != a && i != b) {
                if (c == dist[a][i] + dist[i][b]) {
                    ans -= c;
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3124
H, W = map(int, input().split())
a = [list(input()) for i in range(H)]

for h in range(H):
    for w in range(W):
        if a[h][w] == ".":
            count = 0
            if h > 0:
                if w > 0:
                    if a[h - 1][w - 1] == "#":
                        count += 1
                if a[h - 1][w] == "#":
                    count += 1
                if w < W - 1:
                    if a[h - 1][w + 1] == "#":
                        count += 1
            if w > 0:
                if a[h][w - 1] == "#":
                    count += 1
            if w < W - 1:
                if a[h][w + 1] == "#":
                    count += 1
            if h < H - 1:
                if w > 0:
                    if a[h + 1][w - 1] == "#":
                        count += 1
                if a[h + 1][w] == "#":
                    count += 1
                if w < W - 1:
                    if a[h + 1][w + 1] == "#":
                        count += 1
            a[h][w] = str(count)
for h2 in range(H):
    print("".join(a[h2]))


Measured memory_bytes: 40172
#include <iostream>
#include <cstdio>

using namespace std;

void insertionSort(int *, int);
void printArray(int *, int);

int main(int argc, char const* argv[]) {
    int n;
    cin >> n;
    int A[100];
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    printArray(A, n);
    insertionSort(A, n);
    return 0;
}

void insertionSort(int *A, int n) {
    for (int i = 1; i < n; i++) {
        int tmp = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > tmp) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = tmp;
        printArray(A, n);
    }
}

void printArray(int *A, int n) {
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", A[i]);
    }
    printf("%d\n", A[n-1]);
}

Measured memory_bytes: 3188
#include <iostream>
#include<iomanip>
#include<math.h>
using namespace std;
int main() {
  int a,b,c;
  double s,l,h,pi=3.14159265358979;
  cin>>a>>b>>c;
  s=a*b*sin(c*pi/180)*1/2;
  l=sqrt(a*a+b*b-2*a*b*cos(c*pi/180))+a+b;
  h=b*sin(c*pi/180);
  cout<<fixed<<setprecision(6)<<s<<endl<<l<<endl<<h<<endl;
  return 0;
}

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

using namespace std;

using dijkstra_cost = double;
template<class V, class E>
struct Graph
{
	int sz;
	vector<V> v;
	vector<vector<E>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = V(args...);
	}
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Vertex_Cost
{
	T cost;
	Vertex_Cost(T v1) : cost(v1) {}
	Vertex_Cost() {}
	inline bool operator<(const Vertex_Cost r) const {
		return cost < r.cost;
	}
	inline bool operator>(const Vertex_Cost r) const {
		return r < *this;
	}
	inline bool operator>=(const Vertex_Cost r) const {
		return !(*this < r);
	}
	inline bool operator<=(const Vertex_Cost r) const {
		return !(r < *this);
	}
	inline bool operator==(const Vertex_Cost r) const {
		return !(r < *this) && !(*this < r);
	}
	inline bool operator!=(const Vertex_Cost r) const {
		return (r < *this) || (*this < r);
	}
};
using vertex = Vertex_Cost<dijkstra_cost>;

template<class T>
struct Edge_Cost
{
	int to;
	T cost;
	Edge_Cost(int t, T c) : to(t), cost(c) {}
	Edge_Cost() {}
	inline bool operator<(const Edge_Cost rhs) const {
		return cost < rhs.cost;
	}
	inline bool operator>(const Edge_Cost rhs) const {
		return rhs < *this;
	}
	inline bool operator>=(const Edge_Cost rhs) const {
		return !(*this < rhs);
	}
	inline bool operator<=(const Edge_Cost rhs) const {
		return !(*this > rhs);
	}
	inline bool operator==(const Edge_Cost rhs) const {
		return *this <= rhs && *this >= rhs;
	}
	inline bool operator!=(const Edge_Cost rhs) const {
		return !(*this == rhs);
	}
};
using edge = Edge_Cost<dijkstra_cost>;
using graph = Graph<vertex, edge>;

template<class T, class V, class E>
void Dijkstra(Graph<V, E>& G, int s, T INF_COST)
{
	auto &v = G.v;
	auto &e = G.e;
	for (auto& vv : v) vv.cost = INF_COST;
	priority_queue<E, vector<E>, greater<E>> q;
	q.emplace(s, 0);
	while (!q.empty()) {
		auto a = q.top();
		q.pop();
		if (a.cost >= v[a.to].cost) continue;
		v[a.to].cost = a.cost;
		for (auto& p : e[a.to]) {
			if (p.cost == INF_COST) continue;
			if (a.cost + p.cost < v[p.to].cost) q.emplace(p.to, a.cost + p.cost);
		}
	}
}

int main()
{
	int N;
	vector<long long> x, y, r;
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		x.push_back(a);
		y.push_back(b);
		r.push_back(0);
		x.push_back(c);
		y.push_back(d);
		r.push_back(0);
	}
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		x.push_back(a);
		y.push_back(b);
		r.push_back(c);
	}
	graph G(N+2);
	for (int i = 0; i < N + 2; i++) {
		for (int j = 0; j < N + 2; j++) {
			double dx = x[i] - x[j];
			double dy = y[i] - y[j];
			dx *= dx;
			dy *= dy;
			G.add_edge(i, j, max<double>(0, sqrt(dx + dy) - r[i] - r[j]));
		}
	}
	Dijkstra(G, 0, 1e18);
	cout << fixed << setprecision(12) << G.v[1].cost << endl;
}

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

int main(){
	int no;
	cin >> no;
	int s, n;
	char st;
	bool tr[4][13];
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 13; j++){
			tr[i][j] = false;
		}
	}
	for (int i = 0; i < no; i++){
		cin >> st >> n;
		switch (st){
		case 'S':
			s = 0;
			break;
		case 'H':
			s = 1;
			break;
		case 'C':
			s = 2;
			break;
		case 'D':
			s = 3;
			break;
		default:
			break;
		}
		tr[s][n-1] = true;
	}
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 13; j++){
			if (tr[i][j] == false){
				switch (i){
				case 0:
					st = 'S';
					break;
				case 1:
					st = 'H';
					break;
				case 2:
					st = 'C';
					break;
				case 3:
					st = 'D';
					break;
				}
				cout << st << " " << j+1 << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Cake {
    int w, d;
    Cake(int w, int d) : w(w) , d(d) {}
    Cake() { w = 0; d = 0; }
    void Push(int _w, int _d) { w = _w; d = _d; }
};

bool operator<(const Cake &a, const Cake &b) {
    return a.w * a.d < b.w * b.d;
}

int main()
{
    int n, w, d;

    while (cin >> n >> w >> d, n || w || d) {
        vector<Cake> cake(n + 1);
        int p, s;

        cake[0].Push(w, d);

        for (int i = 0; i < n; ++i) {
            cin >> p >> s;
            --p;

            w = cake[p].w, d = cake[p].d;
            int len = 2 * w + 2 * d;
            s = s % len;

            for (int j = p; j < i; ++j)
                swap(cake[j], cake[j + 1]);

            if ((0 < s && s < w) ||
                (w + d < s && s < 2 * w + d)) {
                // 縦に分割
                if (w + d < s && s < 2 * w + d)
                    s = s - w - d;

                if (s >= w - s) {
                    cake[i + 1].Push(s, d);
                    cake[i].w = w - s;
                }
                else {
                    cake[i + 1].Push(w - s, d);
                    cake[i].w = s;
                }
            }
            else if ((w < s && s < w + d)
                     || (2 * w + d < s)) {
                // 横に分割
                if (2 * w + d < s)
                    s = s - 2 * w - d;
                else
                    s = s - w;

                if (s >= d - s) {
                    cake[i + 1].Push(w, s);
                    cake[i].d = d - s;
                }
                else {
                    cake[i + 1].Push(w, d - s);
                    cake[i].d = s;
                }
            }
        }

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

        for (size_t i = 0; i < cake.size() - 1; ++i)
            cout << cake[i].w * cake[i].d << " ";
        cout << cake[cake.size() - 1].w * cake[cake.size() - 1].d << endl;
    }

    return 0;
}

Measured memory_bytes: 1200
#include<stdio.h>
#include<stdlib.h>
int main(void){
	int h,n;
	scanf("%d %d",&h,&n);
	int ans=0;
	int s;
	for(int m=0;m<n;m++){
		scanf("%d",&s);
		ans+=s;
	}
	if(h<=ans){
	printf("Yes");
	}else{
		printf("No");
	}

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define MOD 1000000007
#define ONLINE_JUDGE

using namespace std;
int dp[100005][4];
int vc[100005][4];
void ravi()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int vac(int n,int vc[][4],int day,int prev)
{

    // Base condition
    if(day > n)
        return 0;
    if (dp[day][prev] != -1)
        return dp[day][prev];
    int maxi = 0;
    if(day == 1)
    {
        maxi = max(maxi,(vc[day][1] + vac(n,vc,day+1,1)));
        maxi = max(maxi,(vc[day][2] + vac(n,vc,day+1,2))); 
        maxi = max(maxi,(vc[day][3] + vac(n,vc,day+1,3)));
    }
    else if(prev == 1)
    {
        maxi = max(maxi,vc[day][2] + vac(n,vc,day+1,2));
        maxi = max(maxi,vc[day][3] + vac(n,vc,day+1,3));
    }
    else if(prev == 2)
    {
        maxi = max(maxi,vc[day][1] + vac(n,vc,day+1,1));
        maxi = max(maxi,vc[day][3] + vac(n,vc,day+1,3));
    }
    else
    {
        maxi = max(maxi,vc[day][2] + vac(n,vc,day+1,2));
        maxi = max(maxi,vc[day][1] + vac(n,vc,day+1,1));
    }
    return dp[day][prev] = maxi;
}

int main()
{
    ravi();
    int n,temp1;
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=3;j++)
        {
            cin>>vc[i][j];
        }
    }
    cout<<vac(n,vc,1,0);
}

Measured memory_bytes: 11136
n = int(input())
s = list(input())
temp = s[1:].count('E')
res = temp
for i in range(len(s)-1):
    if s[i+1] == "E":
        temp-=1
    if s[i] == "W":
        temp+=1
    res = min(res,temp)
    
print(res)
        

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

bool solve(string S)
{
    auto n = S.find('N') != string::npos;
    auto e = S.find('E') != string::npos;
    auto s = S.find('S') != string::npos;
    auto w = S.find('W') != string::npos;
    return (n == s) && (e == w);
}

int main()
{
    string s; cin >> s;
    cout << (solve(s) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#define		_CRT_SECURE_NO_WARNINGS
#include	<cstdio>
#include	<cstdint>
#include	<iostream>

typedef		std::uint_least32_t		ULI;		//10^9
typedef		std::int_least32_t		SLI;
typedef		std::uint_least64_t		ULLI;
typedef		std::int_least64_t		SLLI;

using namespace std;

int main()
{
	ULI		x, y;

	cin >> x >> y;
	cin.clear();
	cin.ignore();

	for (;;)
	{
		if ((x == 0) || (y == 0))
		{
			if (x > y)
			{
				cout << x << "\n";
			}
			else
			{
				cout << y << "\n";
			}
			break;
		}

		if (x > y)
		{
			x = x % y;
		}
		else
		{
			y = y % x;
		}
	}

	return 0;
}

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

def main():
    s = input()[:-1]
    t = input()[:-1]
    
    ans = 0
    for i in range(len(s)-len(t)+1):
        sub = 0
        for j in range(len(t)):
            if s[i+j] == t[j]:
                sub += 1
        if ans < sub:
            ans = sub
        
    ans = len(t) - ans
    print(ans)
    
    
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9068
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<ld> A(n); rep(i, n) cin >> A[i];
  int mxi = max_element(all(A)) - begin(A);
  ld mx = A[mxi];
  int mni = min_element(all(A)) - begin(A);
  ld mn = A[mni];
  vector<pair<int, int>> ans;
  if(abs(mn) > mx) {
    rrep(i, n) {
      ans.push_back({mni, i});
      ans.push_back({mni, i});
      A[i] += mn*2;
      if(A[i] < mn) {
        mn = A[i];
        mni = i;
      }
    }
  } else {
    rep(i, n) {
      ans.push_back({mxi, i});
      ans.push_back({mxi, i});
      A[i] += mx*2;
      if(A[i] > mx) {
        mx = A[i];
        mxi = i;
      }
    }
  }
  cout << ans.size() << endk;
  for(auto a: ans) cout << a.first+1 << ' ' << a.second+1 << endk;
  return 0;
}


Measured memory_bytes: 3880
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>  
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<ll> v32;
typedef vector<vector<ll> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 1e9+7;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define vvv64 vector<vv32>
#define vvvv64 vector<vvv32>
void solve()
{
	ll n;
	cin>>n;
	if (n%2==1)
	{
		cout<<0<<endl;
		return;
	}
	ll a=0;
	for (int i=1; i<=60; i++)
	{
		ll val=1LL<<i;
		a+=n/val;
	}
	ll m=n/2;
	ll b=0;
	ll val=5;
	for (int i=1; i<=60; i++)
	{
		b+=m/val;
		if (val > n/5)
			break;
		val*=5;		
	}
	cout<<min(a,b)<<endl;
}   
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long int;
using ULL = unsigned long long;

int main() {
    int n; cin >> n;
    set<string> st;
    bool ok = true;
    string s1; cin >> s1;
    st.insert(s1);
    char last = s1.back();
    rep(i, n - 1) {
        string s; cin >> s;
        // debug(last);
        if (st.find(s) != st.end()) ok = false;
        if (s.front() != last) ok = false;
        st.insert(s);
        last = s.back();
    }

    if (ok) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 504
x1,y1,x2,y2 = map(int,input().split())

x3 = x2 + (y1 -y2)
y3 = y2 - (x1 -x2)
x4 = x3 + (y2 -y3)
y4 = y3 - (x2 -x3)

print(x3,y3,x4,y4)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=2100;
bool cmp(int a1,int b1)
{return a1>b1;}


int f(int a1,int a2,int a3)
{
    if((a1-a2+a1-a3)%2==0) return (a1-a2+a1-a3)/2;
    else return f(a1+1,a2,a3+1)+1;
}
int main()
{
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3,cmp);
    cout<<f(a[0],a[1],a[2]);
    return 0;
}


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

#define ll long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//const int MOD = 1e9 + 7;
//typedef unsigned long long u64;
//const double pi = 3.141592653589793238460;

const int MAX = 1e5 + 5;
int arr[MAX];

int main()
{
	IOS
	int t = 1;
	//cin >> t;
	while(t--)
	{
		for(int i = 1 ; i <= 5; i++)
			cin >> arr[i];
		int p = 0;
		for(int i = 1; i <= 5; i++)
		{
			if(arr[i] != i)
			{
				p = i;
				break;
			}
		}
		cout << p << endl;
	}
	return 0;
}


Measured memory_bytes: 3608
def main
    n = gets.to_i
    as = []
    bs = []
    n.times do
        ab = gets.split(" ").map(&:to_i)
        as.push ab[0]
        bs.push ab[1]
    end
    as.sort!
    bs.sort!
    min = (as.size % 2).zero? ? as[as.size/2 - 1, 2].inject(:+) / 2.0 : as[as.size/2]
    max = (bs.size % 2).zero? ? bs[bs.size/2 - 1, 2].inject(:+) / 2.0 : bs[bs.size/2]
    if n % 2 == 0
        puts (max * 2 - min * 2 + 1).to_i
    else
        puts (max - min + 1).to_i
    end
end

main


Measured memory_bytes: 20440
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;

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

int main(){
    string s; cin>>s;
    int n=s.size();
    cout << s[0];
    cout << n-2;
    cout << s[n-1] << endl;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
    private static FastScanner sc = new FastScanner();
    private static boolean DEBUG_FLG = false;

    public static void main(String[] args) {
    	char[] S = sc.next().toCharArray();
    	int N = S.length;
    	int mode = 0;
    	long ans = 0;
    	for(int i=N-1; i>=0; i--) {
    		if(mode%2 == 0) {
    			if(mode >= 2 && S[i] == 'A') {
    				ans += (long)mode / 2;
    			} else if(S[i] == 'B') {
    				mode = 0;
    			} else 	if(S[i] == 'C') {
    				mode++;
    			}
    		} else {
    			if(S[i] == 'A') {
    				mode = 0;
    			} else if(S[i] == 'B') {
    				mode++;
    			} else if(S[i] == 'C') {
    				mode = 1;
    			}
    		}
    	}
    	System.out.println(ans);
    }

    static void debug(long... args) {
    	if(!DEBUG_FLG) return;
    	boolean flg = false;
    	for(long s : args) {
    		if(flg) System.out.print(" ");
    		flg = true;
    		System.out.print(s);
    	}
    	System.out.println();
    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}


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

int main()
{
	int N, d[105] = {};
	int ans = 0;


	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> d[i];
	}

	int array_len = sizeof d / sizeof d[0];
	for (int i = 0; i < array_len; i++) {
		for (int j = i + 1; j < array_len; j++) {
			ans += d[i] * d[j];
		}
	}

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

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

public class Main {

	public static void main(String[] args) {

		//		new Main().dPA();
		//		new Main().dPA2();
		new Main().dPA3();

	}

	private void dPA() {
		Scanner scanner = null;
		int numFrog = 0;
		int numK = 0;

		try {
			scanner = new Scanner(System.in);
			numFrog = scanner.nextInt();
			numK = scanner.nextInt();
			int[] heightArray = new int[numFrog];

			for (int i = 0; i < numFrog; i++) {
				heightArray[i] = scanner.nextInt();
			}

			int[] koufukuArray = new int[numFrog];
			Arrays.fill(koufukuArray, Integer.MAX_VALUE);
			koufukuArray[0] = 0;
			koufukuArray[1] = Math.abs(heightArray[1] - heightArray[0]);
			for (int i = 0; i < heightArray.length; i++) {
				for (int j = 1; j <= numK; j++) {
					if (i + j >= heightArray.length) {
						break;
					}
					int val1 = Math.abs(heightArray[i + j] - heightArray[i]);
					koufukuArray[i + j] = Math.min(koufukuArray[i + j], val1 + koufukuArray[i]);
				}
			}
			System.out.println(koufukuArray[koufukuArray.length - 1]);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void dPA2() {
		Scanner scanner = null;
		int numAshiba = 0;
		int numK = 0;

		try {
			scanner = new Scanner(System.in);
			numAshiba = scanner.nextInt();
			numK = scanner.nextInt();
			int[] heightArray = new int[numAshiba];
			int[] koufukuArray = new int[numAshiba];
			Arrays.fill(koufukuArray, Integer.MAX_VALUE);

			for (int i = 0; i < numAshiba; i++) {
				heightArray[i] = scanner.nextInt();
			}
			koufukuArray[0] = 0;
			for (int i = 0; i < numAshiba; i++) {
				for (int j = 1; j <= numK; j++) {
					if (i + j >= numAshiba)
						continue;
					koufukuArray[i + j] = Math.min(koufukuArray[i] + Math.abs(heightArray[i] - heightArray[i + j]),
							koufukuArray[i + j]);
				}
			}

			System.out.println(koufukuArray[numAshiba - 1]);
		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void dPA3() {
		Scanner scanner = null;
		int n = 0;
		int k = 0;

		try {
			scanner = new Scanner(System.in);
			n = scanner.nextInt();
			k = scanner.nextInt();
			int[] heightArray = new int[n];
			int[] cost = new int[n];
			Arrays.fill(cost, Integer.MAX_VALUE);

			for (int i = 0; i < n; i++) {
				heightArray[i] = scanner.nextInt();
			}
			cost[0] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 1; j <= k; j++) {
					if (i + j < n) {
						cost[i + j] = Math.min(cost[i + j], Math.abs(heightArray[i + j] - heightArray[i]) + cost[i]);
					}
				}
			}

			System.out.println(cost[n - 1]);
		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
}

Measured memory_bytes: 50376
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    string a, b;
    bool flag = false;
    cin >> a >> b;
    rep(i, a.size() - b.size() + 1)
    {
        flag = false;
        rep(j, b.size())
        {
            //cout << b[j] << a[i + j] << endl;
            flag = true;
            if (b[j] == '_')
                continue;
            else if (b[j] == a[i + j])
                continue;
            else
            {
                flag = false;
                break;
            }
        }
        if (flag == true)
            break;
    }
    if (flag)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}



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

d = int(input())
C = tuple(map(int, input().split()))
S = tuple(tuple(map(int, input().split())) for _ in range(d))
ans = 0
R = [0]*26
for i in range(1, d+1):
  M = -float("inf")
  idx = -1
  for t in range(26):
    L = list(R)
    L[t] = i
    temp = S[i-1][t]
    for j, (c, l) in enumerate(zip(C, L)):
      temp -= c*(i-l)
    if M < temp:
      M = temp
      idx = t
  R[idx] = i
  print(idx+1)

Measured memory_bytes: 9392