akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long int
#define INF 100000000
#define INFLL 100000000000
#define MOD 998244353
#define PI 3.14159265359
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll, ll>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Edge {
  int to;     
  ll weight; 
  Edge(int t, ll w) : to(t), weight(w) { }
};

template<class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template<class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}


int N;
vector<int> v;
ll ans;

int main () {
  cin >> N;

  ans = 1;

  bool flg = false;

  rep(i, N) {
    int tmp;
    cin >> tmp;

    if (i == 1 && tmp != 0) {
      ans = 0;
      flg = true;
      break;
    }
    if (i != 1 && tmp == 0) {
      ans = 0;
      flg = true;
      break;
    }

    if (i != 1) {
      v.push_back(tmp);
    }
  }

  if (flg) {
    cout << 0 << "\n";
  } else {
    sort(All(v));

    int pos = 0;
    int pos_num_last = 1;
    int pos_num = 1;

    Rep(i, N-1) {
      int tmp = v[i];

      //cout << pos_num << "\n";
      //cout << pos_num_last << "\n";
      //cout << "\n";

      if ((tmp - pos) >= 2) {
        ans = 0;
        break;
      } else if ((tmp - pos) == 1) {
        Rep(k, pos_num) {
          ans *= pos_num_last;
          ans %= MOD;
        }
        pos++;
        pos_num_last = pos_num;
        pos_num = 1;
      } else {
        pos_num++;
      }
    }

    Rep(k, pos_num) {
      ans *= pos_num_last;
      ans %= MOD;
    }

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

Measured memory_bytes: 892
#!python3

from collections import deque

iim = lambda: map(int, input().rstrip().split())

def calc(dp):
    ans = 0
    dq = deque([[0, 0]])
    #print(dp)
    for i, hi in enumerate(dp):
        j = i
        while dq[-1][1] > hi:
            j, h1 = dq.pop()
            ans = max(ans, (i - j) * h1)

        if dq[-1][1] < hi:
            dq.append([j, hi])

    i = len(dp)
    for j, hi in dq:
        ans = max(ans, (i - j) * hi)
    #print(i, dq, ans)
    return ans

def resolve():
    N = int(input())
    H = list(iim())

    print(calc(H))

if __name__ == "__main__":
    resolve()



Measured memory_bytes: 21748
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int a[maxn];
int main(){
  long long ans=0;
  int n;scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",a+i);
  for(int i=1;i<=n;++i){
    if(a[i]&1){
      ans+=a[i]/2;a[i]=1;
    }else if(a[i]>=2){
      ans+=(a[i]-2)/2;a[i]=2;
    }
  }
  for(int i=1;i<n;++i){
    if(a[i]==2)ans++,a[i]=0;
    int tmp=min(a[i],a[i+1]);ans+=tmp;a[i]-=tmp;a[i+1]-=tmp;

  }
  if(a[n]==2)ans++;
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define fi first
#define se second

int main(){
  long n,x;
  cin>>n>>x;
  vector<long> vec(n);
  rep(i,n) scanf("%ld", &vec[i]);

  //各スライムを取ってくるのに最適な場所を探す
  vector<long> res(n,0); // res[i] i回までマジック使えるときの最小コスト
  rep(i,n){ // slime i
    long tmp=i; //現在の最小コストのidx
    res[0] += vec[i];
    repl(j,1,n){
      long idx = (i-j+n)%n;
      if(vec[tmp] > vec[idx]){
        tmp = idx;
      }
      res[j] += vec[tmp];
    }
  }

  long ans = res[0];
  rep(i,n) ans =min(ans, res[i] + (long)i*x);

  cout<< ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define pb push_back
#define f first
#define s second

using namespace std;
int main(){
	int n;
	cin >> n;
	ll t;
	long double ans = 1;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		if (ans != -1)
			ans *= t;
		if (ans > 1000000000000000000)
			ans = -1;
		if (t == 0)
			ans = 0;
	}
	cout << (ll)ans;
	return 0;

}

Measured memory_bytes: 3624
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad
import Control.Monad.Fix
import Data.Int
import Data.Foldable
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)
import Debug.Trace

solve :: Int -> VU.Vector (Int, Int) -> Int
solve !n !abn =
  foldl' (\(!acc) (!i, (_, !a, !b)) -> acc + (if even i then a else -b)) 0
    $ zip [0 ..]
    $ reverse
    $ sort
    $ VU.toList
    $ VU.map (\(!a, !b) -> (a + b, a, b)) abn

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  n   <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  abn <-
    VU.replicateM n
    $   (\vec -> (vec VU.! 0, vec VU.! 1))
    .   VU.unfoldrN 2 readInt
    <$> B.getLine
  print $ solve n abn


Measured memory_bytes: 36220
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    long long int a,b,c,d;

    cin >> a >> b >> c>>d;
    cout <<max(max(a*c,a*d),max(b*c,b*d)) << endl;
}

Measured memory_bytes: 3224
/*input
8
2 4 8 16 32 64
*/

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <utility>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define pb                push_back
#define pp                pop_back
#define nl                cout << "\n"
#define MIN(con)          (*min_element(ALL(con)))
#define MAX(con)          (*max_element(ALL(con)))
#define NX(cont)          next_permutation(ALL(cont))
#define PX(cont)          prev_permutation(ALL(cont))
#define prec(n)           cout << fixed << setprecision(n)
#define PI                3.14159265358979323846264338327951
#define all(c)            c.begin(),c.end()
#define rep(i,a,b)        for(ll i=a;i<b;i++)
#define sp                cout << " "
#define mod               1000000007    //9
#define ifalse            ios_base::sync_with_stdio(false),cin.tie(NULL)

using ll = long long;
using ld = long double;
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > T LCM(T a, T b)            { return (a * b) / GCD(a, b); }
template < typename T > string toString(T a)       { return to_string(a); }  // Convert int to string
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}  // Convert string to int

ll add(ll x, ll y) { x += y; if(x >= mod) x -= mod; return x; }
ll sub(ll x, ll y) { x -= y; if(x < 0) x += mod; return x; }
ll mul(ll x, ll y) { return ((x % mod) * (y % mod)) % mod; }

ll powr(ll a, ll b) {
    ll x = 1LL;
    while(b) {
        if(b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}

ll inv(ll a) { return powr(a, mod - 2); }
const int inv2 = (mod + 1) >> 1;
const ll INF =  1e18;
const int inf = 1e9;

bool check(ll n)
{
    if(n == 1) return 0;
    if(n == 2 or n == 3) return 1;
    if(n % 2 == 0 or n % 3 == 0) return 0;
    for(ll i = 5; i * i <= n; i += 6) if(n % i == 0 or n % (i + 2) == 0) return 0;
    return 1;
}

/*********************************************START**************************************************************/

int main()
{
    ifalse;
    int n;
    cin >> n;
    vector < ll > v;
    map < ll, ll > mp;
    rep(i, 0, n) {
        ll x;
        cin >> x;
        v.pb(x);
        mp[x] ++;
    }
    ll ans = 0;
    sort(all(v), greater < ll > ());
    for(int i = 0; i < n; i ++) {
        ll x = v[i];
        if(mp[x] <= 0) continue;
        ll d = 1;
        while(d <= x) d *= 2;
        mp[x] --;
        if(mp[d - x]) {
            ans ++;
            mp[d - x] --;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 26864
from collections import defaultdict as dd

N, K, L = list(map(int, input().split()))
PQ = [list(map(int, input().split())) for _ in range(K)]
RS = [list(map(int, input().split())) for _ in range(L)]

def uft_root(g, a):
	if g[a] < 0:
		return a
	g[a] = uft_root(g, g[a])
	return g[a]

def uft_size(g, a):
	return -g[uft_root(g, a)]

def uft_merge(g, a, b):
	a, b = uft_root(g, a), uft_root(g, b)
	if a == b:
		return
	size_a, size_b = uft_size(g, a), uft_size(g, b)
	if size_a < size_b:
		a, b = b, a
		size_a, size_b = size_b, size_a
	g[a] -= size_b
	g[b] = a

uft_pq = [-1] * N
uft_rs = [-1] * N

for p, q in PQ:
	p, q = p - 1, q - 1
	uft_merge(uft_pq, p, q)
for r, s in RS:
	r, s = r - 1, s - 1
	uft_merge(uft_rs, r, s)

group = dd(int)
for n in range(N):
	group[(uft_root(uft_pq, n), uft_root(uft_rs, n))] += 1

result = []
for n in range(N):
	result += [group[(uft_root(uft_pq, n), uft_root(uft_rs, n))]]
print(" ".join(map(str, result)))


Measured memory_bytes: 95004
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int a;
    string b;
    cin >> a >> b;
    int n = b.length();
    int sum = 0;
    for (int i=0;i<n;++i){
        if (b[i] == '.'){
            continue;
        }
        sum  = sum * 10 + (b[i]-'0');
    }
    cout << (a*sum)/100;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

int n;
int x[maxn];
int dp[maxn][22];
int L;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++) scanf("%d", x+i);
	scanf("%d", &L);
	vector<int> vec;
	for(int i = 1; i<= n; i++) vec.pb(x[i]);
	vec.pb(vec.back()+1);
	for(int i = 1; i<= n; i++)
	{
		dp[i][0] = upper_bound(vec.begin(), vec.end(), x[i]+L)-vec.begin();
	}
	dp[n+1][0] = n+1;
	// for(int i = 1; i<= n; i++) printf("%d ", dp[i][0]);
	// printf("\n");
	for(int j = 1; j<= 20; j++)
	{
		for(int i = 1; i<= n+1; i++)
		{
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}
	// for(int i = 1; i<= n; i++) printf("%d ", dp[i][1]);
	// printf("\n");
	// for(int i = 1; i<= n; i++) printf("%d ", dp[i][2]);
	// printf("\n");
	int q; scanf("%d", &q);
	while(q--)
	{
		int a, b; scanf("%d %d", &a, &b);
		if(a> b) swap(a, b);
		int ans = 0;
		for(int i = 20; i>= 0; i--)
		{
			int x = dp[a][i];
			// printf("x is %d\n", x);
			if(x>= b) continue;
			a = x;
			ans += (1<<i);
		}
		printf("%d\n", ans+1);
	}
}

Measured memory_bytes: 10360
import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    likes = [string_to_int(i) for i in inputs]
    everyone_likes = {n for n in range(1, M+1)}

    for l in likes:
        like_set = set()
        for i, f in enumerate(l):
            if i == 0:
                continue
            like_set.add(f)

        everyone_likes = everyone_likes & like_set
    return len(everyone_likes)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(N))
    print(ret)

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int gcd(int p, int q) {
	if (p > q) swap(p, q);
	if (p == 0) return q;
	else return gcd(q % p, p);
}

int main() {
	int N;
	cin >> N;
	int a, b;
	rep(i, N) {
		cin >> a;
		if (i == 0) {
			b = a;
			continue;
		}
		b = gcd(a, b);
		if (b == 1) break;
	}
	cout << b << endl;
}

Measured memory_bytes: 256
package main

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

var sc  = bufio.NewScanner(os.Stdin)

func Text() string {
	sc.Scan()
	text := sc.Text()
	return text
}

func main() {
	sc.Split(bufio.ScanWords)

	string := Text()
	m := map[int32]int{}
	for _, c := range string {
		_, ok := m[c]
		if ok == true {
			fmt.Println("no")
			return
		} else {
			m[c] = 1
		}
	}
	fmt.Println("yes")
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;

int m, a, b, p ,q, bestp, bestq;
bool isprime[100000];
vector<int> prime;

void init() {
  fill(isprime, isprime+100000, true);
  isprime[0] = isprime[1] = false;
  for (auto i=2; i<100000; i++) {
    if (isprime[i]) {
      prime.push_back(i);
      for (auto j=2; j<100000; j++) {
	int temp = i*j;
	if (temp >= 100000) break;
	isprime[temp] = false;
      }
    }
  }
}

bool check() {
  return (a * q <= b * p);
}

bool maximize() { // qが決まったら最大のpをpに入れる。そしてそれが適切か返す。
  for (auto i=0; i<prime.size(); i++) {
    if (!(prime[i] * q <= m && prime[i] <= q)) break;
    p = prime[i];
  }
  return check();
}

void best() {
  int res = 0;
  for (auto i=0; i<prime.size(); i++) {
    q = prime[i];
    int temp;
    if (maximize() && (temp = p * q) > res) {
      res = temp;
      bestp = p;
      bestq = q;
    }
  }
}

int main() {
  init();
  while(scanf("%d%d%d", &m, &a, &b) != EOF && m) {
    best();
    printf("%d %d\n", bestp, bestq);
  }
}

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

// #define int long long

signed main(void) {
  int num; // num
  // num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  num = numeric_limits<int>::max(); // min
  int N;
  int M;
  array<int, 1000000> A;
  // string S;
  // string T;

  cin >> N >> M;
  for (auto it = A.begin(); it < A.begin() + N; ++it) cin >> *it;

  for (int i = 0; i < N - M + 1; ++i) {
    int tmp = min(abs(A[i]) + abs(A[i] - A[i + M - 1]),
                  abs(A[i + M - 1]) + abs(A[i] - A[i + M - 1]));
    num = min(num, tmp);
  }
  cout << num << endl;
    
  // cin >> N;
  // for (auto it = A.begin(); it < A.begin() + N; ++it)
  //   cin >> *it;
  // for (auto it = A.begin(); it < A.begin() + N; ++it)
  //   if (*it % 2 == 0) ++num;
  // cout << num << endl;
  
  return 0;
}


Measured memory_bytes: 640
import sys

#+++++
		
def check_near_black(c,i,j):
	dd=[[1,0],[0,1],[-1,0],[0,-1]]
	for dx,dy in dd:
		if c[i+dy][j+dx] == '#':
			return True
	return False

def main():
	h,w = map(int, input().split())
	camp=[]
	ww=list('.'*(w+2))
	camp.append(ww)
	for i in range(h):
		s = '.'+input()+'.'
		camp.append(list(s))
	camp.append(ww)
	
	for i in range(1,1+h):
		for j in range(1,1+w):
			#print(camp[i][j])
			if camp[i][j]=='#' and not check_near_black(camp,i,j):
				return 'No'
				
				
	return 'Yes'
		
	
	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string s;
	cin>>n>>s;
	deque<char>ret;
	int b = 0;
	for(int i=0; s[i]; i++){
		if(s[i]=='(') b++;
		else b--;
		ret.push_back(s[i]);
		if(b<0){
			b*=-1;
			for(int j=0; j<b; j++) ret.push_front('(');
			b = 0;
		}
	}
	while(b--) ret.push_back(')');
	while(ret.size()){
		cout<<ret.front();
		ret.pop_front();
	}
}

Measured memory_bytes: 3508
D,G=map(int,input().split())
li=[list(map(int,input().split())) for _ in range(D)][::-1]
ans=float("inf")
for i in range(2**D):
  S=0
  cnt=0
  q="{:0>10b}".format(i)[::-1]
  ads=q.find("0")
  for j in range(D):
    if int(q[j])&1:
      S+=(D-j)*100*li[j][0]+li[j][1]
      cnt+=li[j][0]
  if S<G and (D-ads)*100*(li[ads][0]-1)>=G-S:
    for k in range(li[ads][0]):
      S+=(D-ads)*100
      cnt+=1
      if S>=G:
        break
  if S>=G:
    ans=min(ans,cnt)
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class B { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		var S = GetString().ToArray();
		var T = GetString().ToArray();

		long min = long.MaxValue;
		for(long i = 0; i < S.Length; i++)
		{
			if(i + T.Length > S.Length)
				break;

			long cnt = 0;
			for(long j = 0; j < T.Length; j++)
			{
				if(S[i + j] != T[j])
					cnt++;
			}
			chmin(ref min, cnt);
		}
		WriteLine(min);
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 26408
#include <stdio.h>
#include <inttypes.h>

int
main(void)
{
        int64_t man;
        int64_t capacity[5];

        scanf("%lld\n", &man);
        scanf("%lld\n", &capacity[0]);
        scanf("%lld\n", &capacity[1]);
        scanf("%lld\n", &capacity[2]);
        scanf("%lld\n", &capacity[3]);
        scanf("%lld", &capacity[4]);

        int64_t min = INT64_MAX;
        int64_t total = 0;
        for (int i = 0; i < 5; i++) {
                if (capacity[i] < min )
                        min = capacity[i];
        };

        total = (man + min - 1)/ min + 4;

        printf("%lld", total);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll          long long
#define ld          long double
#define mod         (1000000000+7)
#define ull         unsigned long long
#define pb          push_back
#define	endl		'\n'
#define pi          acos(-1)
#define pii         pair<ll int,ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define SIZE(X)     ((int)((X).size()))
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define fo(i,s,n)  for(int i=s;i<n;i++)
#define FORE(i,s,n) for(int i=s;i<=n;i++)
#define ERASE(x)    x.erase(unique(x.begin(),x.end()),x.end()) //removes repeated element;
#define Fast        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);

using namespace std;
const int N = 100010;
vector <ll> is_prime(N+1 , true);
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b){return (a.first > b.first);}
bool sortbysecdesc(const pair<int,int> &a,const pair<int,int> &b){return a.second>b.second;}
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) {return (a.second < b.second);}
ll int pow(ll int x, ll int y) { ll int res = 1; while (y > 0) { if (y & 1) res = ((res) * (x)); res %= N; y = y >> 1; x = ((x) * (x)); } return res; }
int powm(int x, int y, int p)  {  int res = 1; x = x % p; while (y > 0) {if (y & 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p;}   return res; }
ll int power(ll int a , ll int b) { if(b == 1) return a; if(b == 0) return 1; ll int m1 = power(a,b/2); if(b%2) return m1*m1*a; return m1*m1; }
void seive_of_eras(ll n) { is_prime[0] = 0; is_prime[1] = 0; for(ll i=2;i*i<=n;i++) { if(is_prime[i]) { for(ll j=i*i;j<=n;j+=i) { is_prime[j] = false; } } } }
bool isprime (ll a) { if(a<=1) return false; if(a==2||a==3) return true; if(a%2==0||a%3==0) return false; for(ll i=5;i*i<=a;i=i+6) { if(a%i==0||a%(i+2)==0) return false; } return true; }

void codeit()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll w=0,r=0;
    fo(i,0,n)
    {
        if(s[i]=='R')
            r++;
        else
        {
            w++;
        }

    }
    ll ans=min(r,w);
    ll pr=0,pw=0;
    fo(i,0,n)
    {
        if(s[i]=='W')
        {
            pw++;
            r--;
        }
        else
        {
            pr++;
            w--;
        }
        //if(pr-w>=0)
            ans=min(ans,pr+w);
            //ans=min(ans,pr)

    }
    ll hw=0,hr=0;
    int i=0,j=n-1;
    while(i<n&&j>=0&&i<j)
    {
        if(s[i]!='W')
        {
            i++;
        }
        if(s[j]!='R')
            j--;
        if(s[i]=='W'&&s[j]=='R')
        {
            i++;
            j--;
            hr++;
        }
    }
    ans=min(ans,hr);
    cout<<ans<<endl;
}

int main()
{
    //Fast
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ull tt; //cin>>tt;
    tt = 1;
    for(ull i=0;i<tt;i++)
        codeit();
}


Measured memory_bytes: 4392
#include <stdio.h>
 
int rot[24][7] = {
    { 0,1,2,3,4,5,6 },{ 0,1,3,5,2,4,6 },{ 0,1,4,2,5,3,6 },{ 0,1,5,4,3,2,6 },
    { 0,2,6,3,4,1,5 },{ 0,2,3,1,6,4,5 },{ 0,2,1,4,3,6,5 },{ 0,2,4,6,1,3,5 },
    { 0,3,1,2,5,6,4 },{ 0,3,2,6,1,5,4 },{ 0,3,5,1,6,2,4 },{ 0,3,6,5,2,1,4 },
    { 0,4,1,5,2,6,3 },{ 0,4,2,1,6,5,3 },{ 0,4,5,6,1,2,3 },{ 0,4,6,2,5,1,3 },
    { 0,5,1,3,4,6,2 },{ 0,5,3,6,1,4,2 },{ 0,5,4,1,6,3,2 },{ 0,5,6,4,3,1,2 },
    { 0,6,2,4,3,5,1 },{ 0,6,3,2,5,4,1 },{ 0,6,5,3,4,2,1 },{ 0,6,4,5,2,3,1 } };
int assign[7];
 
int main(void)
{
    int i, j;
    int a[7], b[7], dice[7];
 
    for (i = 1; i <= 6; i++) scanf("%d", assign+i);
    for (i = 1; i <= 6; i++) scanf("%d", a+i);
    for (j = 0; j < 24; j++) {
        for (i = 1; i <= 6; i++) dice[i] = rot[j][i];
        for (i = 1; i <= 6; i++) b[i] = assign[dice[i]];
        for (i = 1; ; i++) {
            if (i > 6) { puts("Yes"); return 0; }
            if (a[i] != b[i]) break;
        }
    }
    puts("No");
    return 0;
}


Measured memory_bytes: 2112
#include <iostream>
#include <vector>
#include <complex>
using namespace std;
 
#define X real()
#define Y imag()
#define EPS (1e-10)
 
typedef complex<double> P;
typedef P Vec;
 
double dot(Vec v1, Vec v2) {
  return (v1*conj(v2)).X;
}
 
double cross(Vec v1, Vec v2) {
  return (v1*conj(v2)).Y;
}
 
enum { COUNTER_CLOCKWISE, CLOCKWISE, ONLINE_FRONT, ONLINE_BACK, ON_SEGMENT };
 
int ccw(P p0, P p1, P p2) {
  Vec a = p1 - p0;
  Vec b = p2 - p0;
  if(cross(a, b) > EPS) return CLOCKWISE;
  if(cross(a, b) < -EPS) return COUNTER_CLOCKWISE;
  if(dot(a, b) < -EPS) return ONLINE_BACK;
  if(norm(a) < norm(b)) return ONLINE_FRONT;
  return ON_SEGMENT;
}

typedef vector<P> Polygon;

#define prev(G, i) ((G)[((i)-1+(G).size())%(G).size()])
#define curr(G, i) ((G)[(i)%(G).size()])
#define next(G, i) ((G)[((i)+1+(G).size())%(G).size()])

int main() {
  double x, y;
  Polygon g;
  
  int n;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> x >> y;
    g.push_back(P(x, y));
  }
  
  for(int i=0; i<n; i++) {
    if( ccw(prev(g, i), curr(g, i), next(g, i)) == CLOCKWISE ) {
      cout << 0 << endl;
      return 0;
    }
  }
  
  cout << 1 << endl;
  
  return 0;
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  string sa,sb,sc;
  cin >> sa >> sb >> sc;
  ll la=sa.size(),lb=sb.size(),lc=sc.size();
  char ch='a';
  ll a=0,b=0,c=0;
  while(1){
    if(ch=='a'&& a>=la){
       cout << 'A';
      break;
      return 0;
    }
    if(ch=='b'&& b>=lb){
       cout << 'B';
      break;
      return 0;
    }
    if(ch=='c'&& c>=lc){
       cout << 'C';
      break;
      return 0;
    }
    if(ch=='a'){
      ch=sa.at(a);
      a++;
    }else if(ch=='b'){
      ch=sb.at(b);
      b++;
    }else{
      ch=sc.at(c);
      c++;
    }
  }
}
    

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> m(n);
    for (int i = 0; i < n; ++i) cin >> m[i];
    int sum = accumulate(m.begin(), m.end(), 0);
    x -= sum;
    sort(m.begin(), m.end());
    int tmp = x / m[0];
    cout << tmp + n << endl;
    return 0;
}

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


int main(){
    string s;
    cin>>s;
    
    int n=(int)s.size();
    int ans=n;
    rep(i,n-1){
        if(s[i]!=s[i+1]){
            int tmp;
            tmp=max(i+1,n-i-1);
            ans=min(ans,tmp);
        }
    }
    
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int k,s;
    cin>>k>>s;
    int x,y,z;//x<=y<=z
    int cnt = 0;
    for(int x=0;x<=k;x++){
        for(int y=0;y<=k;y++){
            z = s-x-y;
            if(0<=z && z<=k){
                cnt++;
            }
        }
    }

    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5;
char s[N];
int n,a[N],b[N],ans;

signed main(){
	ans=read(n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) a[i]=a[i-1]+(s[i]=='.');
	for(int i=n;i;i--) b[i]=b[i+1]+(s[i]=='#');
	for(int i=0;i<=n;i++) ans=min(ans,i-a[i]+(n-i)-b[i+1]);
	write(ans);
}

Measured memory_bytes: 5512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		boolean inclued3 = false;

		for (int i = 1, a; i <= n; i++) {
			a = 1;
			while (i / a >= 1) {
				if (i % (a * 10) / a == 3) {
					inclued3 = true;
					break;
				} else {
					inclued3 = false;
				}
				a *= 10;
			}

			if (i % 3 == 0 || inclued3) {
				System.out.print(" " + i);
			}

		}
		System.out.println();
	}

}

Measured memory_bytes: 28736
s = input()

year = int(s[:4])
month = int(s[5:7])


if year < 2019:
	print("Heisei")
	quit()

if year >= 2020:
	print("TBD")
	quit()

if year==2019 and month >= 5:
	print("TBD")
	quit()
else:
	print("Heisei")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  string l[10] = {"pon", "pon", "hon", "bon", "hon",
                  "hon", "pon", "hon", "pon", "hon"};
  int n;cin >> n;
  cout << l[n%10] << endl;
  return 0;
}

Measured memory_bytes: 3580
n = $stdin.gets.chomp.to_i
arr = gets.chomp.split(' ').map(&:to_i)
kabe = 0;ans = 0
n.times do |k|
  if arr[k] >= kabe
    ans += 1
  end
  if arr[k] > kabe
    kabe = arr[k]
  end
end
puts ans

Measured memory_bytes: 14380
#define DBG 0 //submit 0
#define ll long long
#if DBG
    #include <algorithm>
    #include <array>
    #include <ctime>
    #include <cstdlib>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <iostream>
    #include <cmath>
    #include <queue>
    #include <numeric>
#else
    #include <bits/stdc++.h>
#endif
 
using namespace std;
 
 
int main(){
    int n,ans=0;
    ll a,down = 1000000001,up = 0;
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> a;
        down = min(a,down);
        up = max(a,up);
    }

    ans = up-down;

    //cout << (flag ? "Yes" : "No") << endl;
    cout << ans << endl;
}


Measured memory_bytes: 256
A = [1, 3, 5, 7, 8, 10, 12]
B = [4, 6, 9, 11]
C = [2]

x, y = [int(n) for n in input().split()]

if x in A and y in A:
    print('Yes')
elif x in B and y in B:
    print('Yes')
elif x in C and y in C:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
using namespace std;
//typedef __int64 LL;
typedef long long int LL;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef pair<int,int> P;
//typedef pair<LL,LL> PL;

const int MOD=1000000007;
int INF=100100100;
int main(){
	LL a,b,c;
	cin>>a>>b>>c;
	cout<<b+min(a+b+1,c)<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

int a,b,c,i,n;

scanf("%d",&n);

for(i=0;i<n;i++){
   scanf("%d %d %d",&a,&b,&c);

if((a*a+b*b==c*c) || (b*b+c*c==a*a) || (c*c+a*a==b*b)){
 printf("YES\n");
}else{
printf("NO\n");
}

}

return 0;
}

Measured memory_bytes: 1712
import java.util.Scanner;

	public class Main {

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			String S = sc.next();
			char[] s = S.toCharArray();
			int L = s.length;
			for(int i=1;i<=L;i++) {
				if((L-i)%2==0) {
					int eq=0;
					for(int j=0;j<(L-i)/2;j++) {
						if(s[j]==s[j+((L-i)/2)]) {
							eq++;
						}
					}
					if(eq==(L-i)/2) {
						System.out.println(L-i);
						return;
					}
				}
				
			}
			
		}	
	}

Measured memory_bytes: 22100
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
#define rep(i,a,b) for(ll i=a;i<b;i++)
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline constexpr int intpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans*(b&1?a:1);
}
inline constexpr int modpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans%MOD*(b&1?a:1)%MOD;
}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll LINF=0x1fffffffffffffff;

int main(){
    string s,t;
    cin>>s>>t;
    rep(i,0,s.size()){
        char ss=s[0];
        s.erase(s.begin(),s.begin()+1);
        s+=ss;
        if(s==t) {cout<<"Yes";return 0;}
    }
    cout<<"No";
}

Measured memory_bytes: 256
#define ll long long
#include <iostream>
using namespace std;
int main()
{
  	ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll answer=0,n,D,x,y;
    std::cin >> n>>D;
    for(ll i=0;i<n;i++){
        std::cin >> x>>y;
        if(x*x+y*y<=D*D)
            answer++;
    }
    std::cout << answer << std::endl;
    return 0;
}

Measured memory_bytes: 3184
my $n=<STDIN>;
my$line = int($n/15);
my $sum = 60*($line**2);
my $sur = $n%15;
my $remain;
if($sur==1) {$remain=1+15*$line;} elsif($sur==2 or $sur ==3){$remain=3+15*$line*2;}elsif($sur==4 or $sur==5
or $sur==6){$remain=7+15*$line*3;}
elsif($sur==7){$remain=14+15*$line*4;}elsif($sur==8 or $sur==9 or $sur==10){$remain=22+15*$line*5;} elsif($sur==11 or $sur ==12){$remain=33+15*$line*6;} elsif($sur==13){$remain=46+15*$line*7;}elsif($sur==14){$remain=60+15*$line*8;}
print $sum+$remain;

Measured memory_bytes: 4800
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 21
#define ll long long
#define lb(x) ((x) & (-(x)))
#define mod 1000000007

using namespace std;

int n, m, k;
int c[N][N];
ll f[2][1 << N];

int main(){
	scanf("%d%d%d",&n, &m, &k);--n;
	for(int i = 1; i <= k; ++i){
		int x, y, z;scanf("%d%d%d", &x, &y, &z);
		c[x][y - 1] = z + 1;
	}
	f[0][0] = 1;
	int lst = 1, cur = 0, all = (1 << n) - 1;
	for(int i = 1; i <= m; ++i)
		for(int j = 0; j < n; ++j){
			swap(lst, cur);
			int now = 1 << j, bar = all ^ ((now << 1) - 1);
			for(int s = 0; s <= all; ++s) f[cur][s] = 0;
			for(int s = 0; s <= all; ++s){
				if(!f[lst][s]) continue;
				if(c[i][j] != 2 && (!(now & s))) (f[cur][s] += f[lst][s]) %= mod;
				if(c[i][j] != 1){
					int x;
					if(now & s) x = s;
					else{
						if(!(bar & s)) x = s | now;
						else x = (s | now) ^ lb(bar & s);
					}
					(f[cur][x] += f[lst][s]) %= mod;
				}
			}
		}
	ll ans = 0;
	for(int i = 0; i <= all; ++i) (ans += f[cur][i]) %= mod;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12544
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {

	Scanner std = new Scanner(System.in);


	//List<Integer> list = new ArrayList<>();
	//int N = std.nextInt();

	//String S = std.next();
	long A = std.nextLong();
	long B = std.nextLong();
	long C = std.nextInt();
	long D = std.nextInt();

	long BBB = Takuma(B,C,D);
	long AAA = Takuma(A-1,C,D);

	long CCC = BBB-AAA;

	System.out.println(CCC);

	}


	public static long Takuma (long B,long C,long D) {

	long g;
	long bigC = B/C;
	long bigD = B/D;
	long CD = C*D;
	long copyC = C;

	//ユークリッドの互除法
	while((g = D%copyC) != 0) {
		D = copyC;
		copyC = g;
	}

	long l = CD/copyC;

	long bigL = B/l;



	long X = B - bigC - bigD + bigL; //B以下でCで割り切れるものとDで割り切れるものの数(重複は無視)

	//B以下でCで割れるものとDで割れるもの

	return X;

	}




	}




Measured memory_bytes: 21716
/*
时间:2020-7-31
书籍：算法和数据结构
内容：科赫曲线
页数：P116
*/
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>
using namespace std;
const double PI = 3.1415926535;
class Point
{
public:
	double x;
	double y;
	Point(double x=0, double y=0)
	{
		this->x = x; 
		this->y = y;
	}
};
void koch(int n, Point a, Point b)
{
	if (n == 0)
		return;
	Point s, t, u;
	double th =PI* 60.0 / 180.0;
	s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
	s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
	t.x = (2.0 * b.x + 1.0 * a.x) / 3.0;
	t.y = (2.0 * b.y + 1.0 * a.y) / 3.0;
	u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;           //通过旋转矩阵获得
	u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

	koch(n - 1, a, s);
	cout << s.x << " " << s.y << endl;
	koch(n - 1, s, u);
	cout << u.x << " " << u.y << endl;
	koch(n - 1, u, t);
	cout << t.x << " " << t.y << endl;
	koch(n - 1, t, b);
	 
}
int main()
{
	cout << setprecision(10);
	Point a(0, 0), b(100, 0);
	int n;
	cin >> n;
	cout << a.x << " " << a.y << endl;
	koch(n, a, b);
	cout << b.x << " " << b.y << endl;
	return 0;
}


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

using namespace std;

int main(){
    ios_base::sync_with_stdio (false);
    int n, a;
    cin >> n;
    set<int> s;
    for(int i=0; i<n; ++i){
        cin >> a;
        if(s.find(a) == s.end()){
            s.insert(a);
        }else{
            s.erase(a);
        }
    }
    cout << s.size();
    return 0;
}


Measured memory_bytes: 4992
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static void swap(int[] a,int idx1 , int idx2) {
		int t = a[idx1];	a[idx1]= a[idx2];	a[idx2] = t;
	}
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		int K = stdIn.nextInt();
		int[] H = new int[N];
		for(int i= 0; i<N ; i++) {
			H[i] = stdIn.nextInt();
		}
		Arrays.sort(H);
		
		long sum = 0;
		for(int i= N-1-K ; i>=0 ; i--) {
			sum += H[i];
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 91232
/*/-----


    Written By:- Sajal Agrawal
          (Have Patience)

/*/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ll long long int
#define f(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define rf(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
#define mod 1000000007
#define fi first
#define se second
#define pa pair <ll,ll>
#define mp make_pair
#define c(t) cout<<t<<"\n"
#define pb push_back
#define ln '\n'
#define forstl(i,v) for(auto &i: v)
#define PRI(x) cerr<<#x<<'='<<x<<endl;
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (for ints only diff for ll)
//https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html for other in built
#define all(con) con.begin(),con.end()
#define sz(x) ((long long)x.size())
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>

void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

ll dp[100010];
ll find(ll a[],ll i,ll n){

if(i==n-1){
    return 0;
}
if(dp[i]!=-1){
    return dp[i];
}
ll ans=INT_MAX;
if(i<n-1)ans=min(ans,abs(a[i]-a[i+1])+find(a,i+1,n));
if(i<n-2){
    ans=min(ans,abs(a[i]-a[i+2])+find(a,i+2,n));
}
return dp[i]=ans;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
ll n;
cin>>n;
ll a[n];
f(i,0,n+1){
    dp[i]=-1;
}
f(i,0,n){
    cin>>a[i];
}

cout<<find(a,0,n)<<endl;











}





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



int main(){
    
       int n,m;
       
       cin>>n>>m;
       if(n<m){
           for(int i=0;i<m;i++){
               cout<<n;
           }
       }else{
           for(int i=0;i<n;i++){
               cout<<m;
           }
       }
       cout<<endl;
   

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){
  int n;

  cin >> n;
  vector<int> l(n);

  rep(i,n){
    cin >> l[i];
  }

  int cnt = 0;

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

  rep(i,n-2){
    for(int j=i+1;j < n-1;j++){
      for(int k=j+1;k < n;k++){
        if(l[i] + l[j] <= l[k]) break;
        else{
          cnt++;
        }

      }
    }
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 384
class ModCombination():
    def __init__(self, n, mod=998244353):
        self.mod = mod
        self.N = n
        fact = [1, 1] # 元テーブル
        ifact = [1, 1] #逆元テーブル
        inverse = [0, 1] #逆元テーブル計算用テーブル

        for i in range( 2, n + 1 ):
            fact.append( ( fact[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            ifact.append( (ifact[-1] * inverse[-1]) % mod )
        
        self.fact = fact
        self.ifact = ifact
        self.inverse = inverse

    def nCr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.ifact[r] * self.ifact[n-r] % self.mod

    def nPr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.ifact[n-r] % self.mod


def main():
    S = int(input())
    MOD = 10**9 + 7
    mc = ModCombination(S, MOD)

    if S < 3:
        print(0)
        return

    ans = 0
    for i in range(1, 1+S//3):
        if i == 1:
            ans += 1
            continue

        rest = S - i * 3
        # print(i, rest)
        ans = (ans + mc.nCr(i+rest-1, rest)) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9320
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <queue>


using namespace std;
#define INF 0x3f3f3f3f3f
#define ll long long
#define pr(x) (cerr << #x << ' ' << x << ' ')
#define prln(x) (cerr << #x << ' ' << x << endl)


int main()
{
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif // LOCAL
    int n;
    scanf("%d", &n);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            int t = 0;
            for (int j = 1; j <= n; ++j) {
                if (i % j == 0) {
                    ++t;
                }
            }
            if (t == 8 && ((i & 1) == 1)) {
                // prln(i);
                ++cnt;
            }
        }
        printf("%d\n", cnt);
    return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void anss(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=0,res2=INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0;
  bool judge = true;
  ll a,b,c;cin>>a>>b>>c;
  for(i=1;i<=b;i++){
    if((i*a)%b==c)judge=false;
  }
  ans2(!judge);


  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String T = sc.next();

		if(S.substring(0,S.length()).equals(T.substring(0,S.length()))) {
			if(T.substring(T.length()) != "") {
				System.out.print("Yes");
			}
			else
				System.out.print("No");
		}
		else
			System.out.print("No");

    }
}


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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

#ifdef LOCAL
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else 
#define dump(x) true
#endif

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

using P = pair<ll, ll>;
const int maxn = 200010;
const ll INF = TEN(18);

ll dp[maxn][32];

int main() {
	int N, T; cin >> N >> T;

	V<P> vec;
	V<int> bs;

	rep(i, N) {
		int a, b;
		cin >> a >> b;
		if (a > 0) {
			vec.eb(a, b);
		} else {
			bs.pb(b);
		}
	}

	sort(ALL(vec), [](const P& a, const P& b) {
		return a.fi * (b.se + 1) > b.fi * (a.se + 1);
	});

	dump(vec);

	rep(i, maxn) {
		rep(j, 32) {
			dp[i][j] = INF;
		}
	}

	dp[0][0] = 0;
	N = vec.size();

	rep(i, N) {
		rep(j, 32) {
			if (dp[i][j] != INF) {
				chmin(dp[i+1][j], dp[i][j]);
				ll t = dp[i][j] + 1;
				ll nx = (1 + vec[i].fi) * t + vec[i].se;
				if (nx <= T) {
					chmin(dp[i+1][j+1], nx);
				}
			}
		}
	}

	int ans = 0;
	sort(ALL(bs));

	rep(j, 32) {
		if (dp[N][j] != INF) {
			int num = j;

			ll t = dp[N][j];
			ll u = 0;
			rep(i, bs.size()) {
				u += bs[i] + 1;
				if (u + t <= T) {
					num++;
				} else {
					break;
				}
			}

			chmax(ans, num);
		}
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 54380
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  ll r,d,x;
  cin>>r>>d>>x;
  rep(i,10){
    x=(ll)(x*r)-d;
    cout<<x<<endl;
  }

  return 0;
}





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

bool has_key(unordered_map<string, ll> &m, string s){
    if (m.find(s) == m.end()){
        return false;
    }
    else{
        return true;
    }
}


bool vector_find(std::vector<ll> vec, ll number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) {
    return true;
  }
  else {
    return false;
  }
}


void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
  if (rest == 0) {
    f(indexes);
  } else {
    if (s < 0) return;
    recursive_comb(indexes, s - 1, rest, f);
    indexes[rest - 1] = s;
    recursive_comb(indexes, s - 1, rest - 1, f);
  }
}


void foreach_comb(int n, int k, std::function<void(int *)> f) {
  int indexes[k];
  recursive_comb(indexes, n - 1, k, f);
}


int main() {

    long double A, B, H, M;
    
    cin >> A >> B >> H >> M;    

    long double ans;


    long double alpha = (H * 60 + M)/2;
    long double beta = M *6;

    long double gamma = abs(alpha - beta);

    long double pi = 3.14159265358979323846;

    ans = A*A + B*B - (A * B * cos((gamma/180)*pi))*2;

    ans = sqrt(ans);


    cout << std::setprecision(20) << ans << endl;

    return 0;
}

Measured memory_bytes: 4192
#include <bits/stdc++.h>
#define INF 2000000000000000000
#define ll long long
#define pb push_back
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string S;
  cin >> S;
  ll N;
  N = S.size();
  vector<vector<ll>> dp(N + 1, vector<ll>(2, INF));//index, 0 same, 1 big
  ll ans = INF;
  dp.at(0).at(0) = 0;
  dp.at(0).at(1) = 1;
  for (ll i = 0; i < N; ++i) {
    dp.at(i + 1).at(0) = min(dp.at(i).at(0) + (S.at(i) - '0'), dp.at(i).at(1) + (10 - (S.at(i) - '0')));
    dp.at(i + 1).at(1) = min(dp.at(i).at(0) + (S.at(i) - '0') + 1, dp.at(i).at(1) + (10 - (S.at(i) - '0')) - 1);
  }
  cout << dp.at(N).at(0) << "\n";
}


Measured memory_bytes: 58928