akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,w;
double histogram[11];

double calc(double bar){
  double hightest=0;
  for(int i=0;i<bar;i++){
    hightest=max(hightest,histogram[i]);
  }
  double res=0;
  for(int i=0;i<bar-1;i++){
    res+=(histogram[i]/hightest) * ((bar-1-i)/(bar-1));
  }
  return res;
}

int main(){
  while(cin>>n>>w,n){
    memset(histogram,0,sizeof(histogram));
    int data[n];
    for(int i=0;i<n;i++)cin>>data[i];
    for(int i=0;i<n;i++){
      histogram[data[i]/w]++;
    }
    int bar;
    for(int i=10;i>=0;i--){
      if(histogram[i]>0){
	bar=i+1;
	break;
      }
    }
    // cout << "bar:" << bar << endl;
    // for(int i=0;i<=bar;i++){
    //   cout << "histgram[" << i << "]:" << histogram[i] << endl;
    // }
    double ans=calc(bar);
    ans+=0.01;
    printf("%.10f\n",ans);
  }
  return 0;
}

Measured memory_bytes: 1188
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<iso646.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>

#define FOR(counter,initial_value,condition) for(int counter = initial_value; counter < condition;counter++)

int main()
{
	int a, b, c;
	std::cin >> a >> b >> c;
	if (a == b + c or b==c+a or c==a+b) std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string mozi;
    cin >> mozi;
    if(mozi.at(2)==mozi.at(3)&&mozi.at(4)==mozi.at(5)){
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

    Scanner sc = new Scanner(System.in);

    String c = sc.next();
      if (c.equals("a") || c.equals("i") || c.equals("u") || c.equals("e") || c.equals("o")){
        System.out.println("vowel");
      }
      else {
        System.out.println("consonant");
      }
  }
}


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

int n;
vector<int> graph[200010];

int mod3[200010];
int cnt[3], c[3];
int ans[200010];

void DFS(int node, int m){
    mod3[node] = m; ++cnt[m];
    for(auto next : graph[node]){
        if(mod3[next]) continue;
        DFS(next, 3-m);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<n; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    DFS(1, 1);
    if(cnt[1] < cnt[2]){
        for(int i=1; i<=n; ++i) mod3[i] = 3-mod3[i];
        swap(cnt[1], cnt[2]);
    }
    //for(int i=1; i<=n; ++i) printf("%d ", mod3[i]);
    //printf("\n");
    c[0] = n/3;
    c[1] = (n+2)/3;
    c[2] = (n+1)/3;
    if(cnt[2] <= c[0]){
        // all 2 -> 0
        for(int i=1; i<=n; ++i){
            if(mod3[i] != 2) continue;
            --cnt[2];
            mod3[i] = 0;
            ++cnt[0];
        }
        // 1->2 or 1->0
        for(int i=1; i<=n; ++i){
            if(mod3[i] != 1) continue;
            if(cnt[0] < c[0]){
                --cnt[1];
                mod3[i] = 0;
                ++cnt[0];
            }
            else if(cnt[2] < c[2]){
                --cnt[1];
                mod3[i] = 2;
                ++cnt[2];
            }
        }
    }
    else{
        for(int i=1; i<=n; ++i){
            if(cnt[mod3[i]] > c[mod3[i]]){
                --cnt[mod3[i]];
                mod3[i] = 0;
                ++cnt[0];
            }
        }
    }
    //for(int i=1; i<=n; ++i) printf("%d ", mod3[i]);
    //printf("\n");
    int num[3] = {3, 1, 2};
    for(int i=1; i<=n; ++i){
        printf("%d ", num[mod3[i]]);
        num[mod3[i]] += 3;
    }
    printf("\n");
}

Measured memory_bytes: 16000
import sys
import collections
N = int(input())
strs = []
for _ in range(N):
  s = input()
  strs.append(s)
#print('strs', strs)
c = collections.Counter(strs)
maxv = -1
ans = []
for k , v in c.most_common():
  if v != maxv and maxv != -1:
    break
  ans.append(k)
  maxv = v
for a in sorted(ans):
  print(a)

Measured memory_bytes: 45040
from math import gcd
def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)

N, = map(int, input().split())
d = dict()
X = []
cc = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b==0:
        cc += 1
        continue
    f = to_standard_form(a, b)
    if f not in d:
        d[f] = 0
    d[f] += 1
    X.append(f)

vs = dict()
for a, b in X:
    f1 = (a, b)
    f2 = to_standard_form(-b, a)
    if f2 not in d:
        d[f2] = 0
    if f1 in vs or f2 in vs:
        continue
    vs[f1] = (d[f1], d[f2])

mod = 10**9+7
r = 1
for k in vs:
    a, b = vs[k]
    r = r * (pow(2, a, mod) + pow(2, b, mod)-1) % mod
print((r-1+cc)%mod)


Measured memory_bytes: 195256
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc =  new Scanner(System.in);
    String[] S = sc.nextLine().split(" ");
    int N = Integer.parseInt(S[0]);
    int M = Integer.parseInt(S[1]);
    Map<Integer, Integer> map = new TreeMap<>();
    int[][] val = new int[N][2];
    for(int i = 0; i < N; i++){
      String[] T = sc.nextLine().split(" ");
      int a = Integer.parseInt(T[0]);
      int b = Integer.parseInt(T[1]);
      map.put(a, b);
      val[i][0] = a;
      val[i][1] = b;
    }
    Arrays.sort(val, (a, b) -> Integer.compare(a[0], b[0]));
    long ans = 0;
    for(int i = 0; M > 0; i++){
      long a = val[i][0];
      long b = val[i][1];
      if(val[i][1] < M){        
        ans += a * b;
        M -= b;
      }else{
        ans += a * M;
        M = 0;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 133456
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
long long int a[1000007];
int main()
{
	int m;
	scanf("%d",&m);
	int i;
	for(i=0;i<m;i++)
		scanf("%lld",a+i);
	sort(a,a+m);
	long long int ans=a[m-1]-a[0];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int i=0;
	int a=0;
	int b=0;
	int s[5];
	int n[4]={6000,4000,3000,2000};
	for(i=0;i<4;i++){
		cin>>a>>b;
		a--;
		s[i]=n[a]*b;
	}
	for(i=0;i<4;i++){
		cout<<s[i]<<endl;
	}
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;

int main(){

    for(int i = 1;;i++){
        int x;
        cin >> x;
        if(x == 0){
            return 0;
        }else{
            cout << "Case " << i << ": " << x << endl;
        }
    }

}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll H, W;
    cin >> H >> W;
    vector<string> a(H);
    REP(i,0,H) cin >> a[i];

    REP(i,0,W+2) cout << '#';
    cout << endl;
    REP(i,0,H) {
        cout << '#' << a[i] << '#' << endl;
    }
    REP(i,0,W+2) cout << '#';
    cout << endl;

    return 0;
}

/*



*/

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define FIND(c, e) ((c).find(e) != (c).end())
#define NFIND(c, e) ((c).find(e) == (c).end())
#define ALL(t) (t).begin(), (t).end()
#define ALLR(t) (t).rbegin(), (t).rend()
#define MP make_pair
template<class T> inline T max(T a,T b,T c){return max(max(a,b),c);}
template<class T> inline T min(T a,T b,T c){return min(min(a,b),c);}
const int  MOD = int( 1e9 ) + 7;
const int    N = int( 1e5 ) + 42;
const int LOGN = ceil(log(N) / log(2));
const double EPS = 1e-6;


void __answer()
{
    int n;
    cin >> n;
    if(n >= 30) cout << "Yes";
    else cout << "No";
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cout << setprecision(11) << fixed;
    #ifdef LOCAL
        freopen("TEST.txt", "r", stdin);
    #endif
    __answer();
    return 0;
}


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

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

using ll = long long;

int dp[100005];

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> v(N);
  for(int i = 0; i < N; i++) {
    cin >> v[i];
  }
  for(int i = 0; i < v.at(0); i++) {
    dp[i] = 1;
  }
  for(int i = v.at(0); i <= K; i++) {
    int cnt = 0;
    for(int j = 0; j < N; j++) {
      if (v.at(j) > i) break;
      cnt += dp[i-v.at(j)];
    }
    if(cnt == 0) dp[i] = 1;
    else dp[i] = 0;
  }
  string ans;
  if(dp[K] == 0) ans = "First";
  if(dp[K] == 1) ans = "Second";
  cout << ans << endl;
}

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

typedef long long LL;
typedef unsigned long long ULL;
const int MAXN=1248576;
const int mod=1000000007;
const LL INF=1e18+10;
const double EPS=1e-8;

LL n,m;
int x[MAXN];

int main(){
    cin>>n>>m;
    if (m%2==1){
        ULL ans=0;
        for(int i=1;i<=n;i++){
            if (m*i<=n) ans++;
            else break;
        }
        ans=ans*ans*ans;
        cout<<ans<<endl;
    }
    else{
        ULL ans=0;
        ULL a=0;
        for(int i=0;i<=n;i++){
            if (m*(2*i+1)/2<=n) a++,x[m*(2*i+1)/2]=1;
            else break;
        }
        ULL b=0;
        for(int i=1;i<=n;i++){
            if (m*i<=n){
                if (x[m*i]==0){
                    b++;
                    //cout<<m*i<<endl;
                }
            }
            else break;
        }
        ans=a*a*a+b*b*b;
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 1024
import heapq

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
pq=p[:x]+q[:y]
heapq.heapify(pq)

for i in range(c):
    a=heapq.heappop(pq)
    if a<r[i]:
        heapq.heappush(pq,r[i])
    else:
        heapq.heappush(pq,a)
        break

print(sum(pq))

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

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N; cin >> N;
    int Q; cin >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

Measured memory_bytes: 21732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f;
const double pi=3.1415926535897932384626;
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
ll n,ans,tmp;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		tmp=n/i;
		ans+=((tmp+1)*tmp*i)>>1;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3772
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"io/ioutil"
	"math"
	"os"
	"path/filepath"
	"runtime"
	"strings"
)

func main() {
	b, _ := ioutil.ReadAll(os.Stdin)
	if len(b) == 0 {
		test()
	} else {
		solve(bytes.NewReader(b), os.Stdout)
	}
}

func solve(r io.Reader, w io.Writer) {
	var n, a int
	fmt.Fscanln(r, &n, &a)
	time := n
	// k-1: count of eating cookies.
	// k <= log2(n) because
	//   - shortest eating interval is 2
	for k := 1; k <= int(math.Ceil(math.Log2(float64(n)))); k++ {
		// s: average number of eating interval
		s := int(math.Ceil(math.Pow(float64(n), 1/float64(k))))
		assert(pow(s, k) >= n)
		c := 0              // the number of "s" interval
		for ; c <= k; c++ { // TODO: binary search should be better
			if n <= pow((s-1), (k-c))*pow(s, c) {
				break
			}
		}
		if t := (k-1)*a + s*c + (s-1)*(k-c); t < time {
			// fmt.Println(strings.Join(procedure(s, k, c), ""))
			time = t
		}
	}
	fmt.Fprintln(w, time)
}

func procedure(s, k, c int) []string {
	ps := make([]string, 0, (s-1)*(k-c)+s*c+(k-1))
	for i := 0; i < k-c; i++ {
		if i != 0 {
			ps = append(ps, "E")
		}
		for j := 0; j < s-1; j++ {
			ps = append(ps, "B")
		}
	}
	for i := 0; i < c; i++ {
		if len(ps) > 0 {
			ps = append(ps, "E")
		}
		for j := 0; j < s; j++ {
			ps = append(ps, "B")
		}
	}
	return ps
}

func test() {
	tests := []struct {
		in   string
		want string
	}{
		{in: `8 1`, want: `7`},
		{in: `1000000000000 1000000000000`, want: `1000000000000`},
	}
	for i, tt := range tests {
		fmt.Printf("=== TEST %d\n", i)
		buf := new(bytes.Buffer)
		solve(strings.NewReader(chomp(tt.in)), buf)
		if got, want := chomp(buf.String()), chomp(tt.want); got != want {
			fmt.Printf("%d: got %v, want %v\n", i, got, want)
		}
	}
}

func chomp(s string) string {
	return strings.Trim(s, "\n")
}

func assert(b bool) {
	if !b {
		_, file, line, ok := runtime.Caller(1)
		if ok {
			f, _ := os.Open(file)
			defer f.Close()
			s := bufio.NewScanner(f)
			lnum := 0
			for s.Scan() {
				lnum++
				if lnum == line {
					wd, _ := os.Getwd()
					fname, _ := filepath.Rel(wd, file)
					fmt.Printf("assertion fails: %s:%d: %v\n", fname, line, s.Text())
					break
				}
			}
		}
	}
}

func pow(a, b int) int {
	r := 1
	for i := 0; i < b; i++ {
		r *= a
	}
	return r
}


Measured memory_bytes: 640
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    int x[] = new int[n];
    int y[] = new int[n];

    for(int i=0; i<n; i++){
      x[i] = Integer.parseInt(sc.next());
      y[i] = Integer.parseInt(sc.next());
    }
    
    double sum = 0;
    
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        //if(i>=j){
        //  continue;
        //}
        sum += Math.sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
      }
    }
    
    double ans = sum * (n-1) / n / (n-1);
    
    System.out.println(ans);

  }
}


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

int main() {
  string s; cin>>s;
  int n=s.size();
  vector<bool> ok(26, false);
  rep(i, 0, n) {
    int tmp=(int)(s[i])-97;
    ok[tmp]=true;
  }
  bool frag=false;
  rep(i, 0, 26) if (!ok[i]) frag=true;
  if (frag) {
    cout<<s;
    rep(i, 0, 26) {
      if (!ok[i]) {
        cout<<(char)(i+97)<<endl;
        break;
      }
    }
  }
  else if (s=="zyxwvutsrqponmlkjihgfedcba") cout<<-1<<endl;
  else {
    int tmp=0;
    for (int i=n-1; i>0; i--) {
      if ((int)s[i]>(int)s[i-1]) {
        tmp=i-1;
        break;
      }
    }
    rep(i, tmp+1, n) {
      if ((int)(s[tmp])<(int)(s[i])) ok[(int)(s[i])-97]=false;
    }
    rep(i, 0, tmp) cout<<s[i];
    rep(i, 0, 26) {
      if (!ok[i]) {
        cout<<(char)(i+97)<<endl;
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 256
public class
Main
{
  private static final int N = 100;

  private static int
  c2d (
    final char ch
    )
  {
    return ( Character.isLowerCase ( ch ) ? ch - 'a' : 26 + ch - 'A' );
  }

  private static char
  d2c (
    int d
    )
  {
    return ( d < 26 ? (char)( d + 'a' ) : (char)( d - 26 + 'A' ) );
  }

  public void
  run (
    final java.util.Scanner sc,
    final java.io.PrintStream out
    )
  {
    int[ ] k = new int[ N ];
    int i; 

    for ( ; ; )
    {
      String s;
      int n;

      n = sc.nextInt ( );
      if ( n == 0 ) break ;
      for ( i = 0; i < n; ++i )
        k[ i ] = sc.nextInt ( );
      s = sc.next ( );

      for ( i = 0; i < s.length ( ); ++i )
        out.print ( d2c ( ( c2d ( s.charAt ( i ) ) + 52 - k[ i % n ] ) % 52 ) );
      out.println ( );
    }
  }

  public static void
  main (
    final String[ ] args
    )
  {
    ( new Main ( ) ).run ( new java.util.Scanner ( System.in ), System.out );
  }
}

Measured memory_bytes: 24392
#include <stdio.h>
int main(void){
    int a,b,c,x,ans=0;
    scanf("%d %d %d",&a,&b,&c);
    for (int x = a; x <= b; x++){
        if(c%x==0) ans++;
    }
    printf("%d\n",ans);

    return 0;
}


Measured memory_bytes: 2124
//go:generate echo "https://atcoder.jp/contests/dp/tasks/dp_a"
package main

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

type scanner struct{ *bufio.Scanner }

func newScanner(r io.Reader) *scanner {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	s.Buffer(nil, 100000000)
	return &scanner{s}
}

func (s *scanner) Int() int {
	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	return n
}

func (s *scanner) IntSlice(l int) []int {
	if l == 0 {
		return []int{}
	}
	sl := make([]int, l, l)
	for i := range sl {
		sl[i] = s.Int()
	}
	return sl
}

func iabs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func solve(n int, heights []int) int {
	t := make([]int, n+1, n+1)
	for i := range t {
		t[i] = math.MaxInt64
	}

	t[0] = 0
	for i := 1; i < n; i++ {
		if v := t[i-1] + iabs(heights[i]-heights[i-1]); v < t[i] {
			t[i] = v
		}
		if 1 < i {
			if v := t[i-2] + iabs(heights[i]-heights[i-2]); v < t[i] {
				t[i] = v
			}
		}
	}

	return t[n-1]
}

func main() {
	sc := newScanner(os.Stdin)
	n := sc.Int()
	heights := sc.IntSlice(n)
	ans := solve(n, heights)
	fmt.Println(ans)
}


Measured memory_bytes: 3788
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
        k: usize,
    }

    let mut d = std::cmp::min(a, b) + 1;
    let mut i = 0;
    while i != k {
        d -= 1;
        if a % d == 0 && b % d == 0 {
            i += 1;
        }
    }
    println!("{}", d);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll INFl = 1e18;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	ll n; cin >> n;
	ll x = 100;
	int cnt = 0;
	while (x < n) {
		cnt ++;
		x += (x / 100);
	}
	cout << cnt << '\n';
	return 0;
}


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

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);

int n;

int main() {
	
	FAST;
	
	cin >> n;
	vector <int> l(n + 1);
	for (int i = 1; i <= n; i ++) cin >> l[i];
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = i + 1; j <= n; j ++) {
			for (int k = j + 1; k <= n; k ++) {
				if (l[i] != l[j] && l[j] != l[k] && l[i] != l[k]) {
					int sum = l[i] + l[j] + l[k];
					int sumi = sum - l[i];
					int sumj = sum - l[j];
					int sumk = sum - l[k];
					if (sumi > l[i] && sumj > l[j] && sumk > l[k]) ans ++;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3604
N,Z,W=map(int,input().split())
alist=list(map(int,input().split()))

if N==1:
  print(abs(alist[-1]-W))
else:
  ans1=abs(alist[-2]-alist[-1])
  ans2=abs(alist[-1]-W)
  print(max(ans1,ans2))

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(void){
    // Your code here!
    string str;
    stack<char> st;
    cin>>str;
    for(auto i:str){
        if(st.empty()){
            st.push(i);
        }else{
            if(st.top()=='S'&&i=='T'){
                st.pop();
            }else{
                st.push(i);
            }
        }
    }
    cout<<st.size()<<endl;
}


Measured memory_bytes: 644
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;


int main(){
    
    string s;
    cin>>s;
    if(s == "ABC")
        cout<<"ARC";
    else
        cout<<"ABC";
    
    return 0;
}

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


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string S;
	cin >> S;
	int ans = 0;
	string t  = "", p = "";
	rep(i, S.size()) {
		t += S.at(i);
		if (t == p) continue;
		p = t;
		ans++;
		t = "";
	}
	cout << ans << endl;
}

Measured memory_bytes: 720
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input;
		int a=0, b=0, o=0, ab=0;
		while((input = br.readLine()) != null) {
			if(input.isEmpty()) break;
			String[] split = input.split(",");
			if(split[1].equals("A")) a++;
			else if(split[1].equals("B")) b++;
			else if(split[1].equals("O")) o++;
			else if(split[1].equals("AB")) ab++;
		}
		System.out.println(a);
		System.out.println(b);
		System.out.println(ab);
		System.out.println(o);
	}
}

Measured memory_bytes: 16928
#include<stdio.h>
int main(void){
	int n,k,d,temp,count=0;
	int sunuke[100]={0};
	scanf("%d %d",&n,&k);
	for(int i=0;i<k;i++){
		scanf("%d",&d);
		for(int j=0;j<d;j++){
			scanf("%d",&temp);
			sunuke[temp-1]++;
		}
	}
	for(int i=0;i<n;i++){
		if(sunuke[i]==0){
			count++;
		}
	}
	printf("%d",count);
}

Measured memory_bytes: 1688
#include<stdio.h>


int main() {
    int n;
    scanf("%d\n", &n);
    int a[n];
    int cw = 0;
    for(int i = 0; i < n; i++) {
        char c;
        scanf("%c", &c);
        if(c == 'W') {
            a[i] = 1;
            cw++;
        }
        else {
            a[i] = 0;
        }
    }
    int count = 0;
    for(int i = 0; i < n - cw; i++) {
        if(a[i] == 1) {
            count++;
        }
    }
    printf("%d\n", count);
}

Measured memory_bytes: 2512
#include<bits/stdc++.h>
const int MAX = 1e5;
using namespace std;

bool isPrime(int);
void outputV(vector<int>);
void outputV(vector<vector<int>>);

int main(){
  vector<int> ruiseki(MAX+1,0);
  for(int i=3;i<MAX;i+=2){
    if(isPrime(i)&&isPrime((i+1)/2)){
      ruiseki[i]++;
    }
    ruiseki[i+1]+=ruiseki[i];
    ruiseki[i+2]+=ruiseki[i];
  }
  //outputV(ruiseki);

  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    cout<<ruiseki[r]-ruiseki[l-1]<<endl;
  }
  return 0;
}

bool isPrime(int x){
  if(x<2){
    return false;
  }
  for(int i=2;i*i<=x;i++){
    if(x%i==0){
      return false;
    }
  }
  return true;
}

void outputV(vector<int> v) {
  for (int i = 0; i < v.size(); i++) {
    if (i) {
      cout << ' ';
    }
    cout << v[i];
  }
  cout << endl;
}

void outputV(vector<vector<int>> v) {
  for (int i = 0; i < v.size(); i++) {
    for (int j = 0; j < v[i].size(); j++) {
      if (j) {
        cout << ' ';
      }
      cout << v[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 3684
<?php

function input() {
    return trim(fgets(STDIN));
}
function input_array() {
    return explode(' ', input());
}

input();
$A = array_map(function($numeric_string) {
    return (int)$numeric_string;
}, input_array());

list($A, $swap_count) = bubble_sort($A);

echo implode(' ', $A) . "\n";
echo $swap_count . "\n";

function bubble_sort($A) {
    $swap_count = 0;
    for ($i = 0, $count = count($A); $i <= $count - 1; $i++) {
        for ($j = $count - 1; $j >= $i + 1; $j--) {
            if ($A[$j] < $A[$j - 1]) {
                swap($A[$j], $A[$j - 1]);
                $swap_count++;
            }
        }
    }
    return [$A, $swap_count];
}

function swap(&$a, &$b) {
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}


Measured memory_bytes: 9360
#include "bits/stdc++.h"

using namespace std;

void Main() {
    int A, B;
    cin >> A >> B;
    int ans = 0;
    for (int i = A; i <= B; ++i) {
        string s = to_string(i);
        if (s[0] == s[4] && s[1] == s[3]) {
            ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define repe1(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define count(v, t) count(v.begin(), v.end(), t)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a * b / gcd(a, b);}

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if (a+b>=c) {
    cout << b+c << "\n";
    return 0;
  } else {
    cout << a+b*2+1 << "\n";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int A, B, C, X, Y, Cost;
	cin >> A >> B >> C >> X >> Y;
	Cost = A * X + B * Y;
	for (int i = 1; i <= max(X, Y); i++) {
		if (A * max((X-i),0) + B * max((Y-i),0) + 2*C*i < Cost){
			Cost=A * max((X-i),0) + B * max((Y-i),0) + 2*C*i;
		}
		
	}
	cout <<Cost << endl;
  return 0;
}

 

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

int main(){
  int n;
  vector<int> a(9);
  rep(i,9) cin >> a[i];
  vector<int> b(n);
  cin >> n;
  rep(i,n) cin >> b[i];
  bitset<9> a2;
  rep(i,n)rep(j,9)if(b[i]==a[j])a2.set(8-j,1);
  bool y=0;
  if(a2.test(0)&&a2.test(1)&&a2.test(2)||a2.test(3)&&a2.test(4)&&a2.test(5)||a2.test(6)&&a2.test(7)&&a2.test(8)) y=1;
  if(a2.test(2)&&a2.test(5)&&a2.test(8)||a2.test(1)&&a2.test(4)&&a2.test(7)||a2.test(0)&&a2.test(3)&&a2.test(6)) y=1;
  if(a2.test(0)&&a2.test(4)&&a2.test(8)||a2.test(2)&&a2.test(4)&&a2.test(6)) y=1;
  
  if(y) cout << "Yes" << endl;
  else cout << "No" << endl;
  if(a[1]==1234)cout << a2;
  return 0;
}

Measured memory_bytes: 3736
#include <iostream>

using namespace std;

int main(void){
	while(1){
		int n, m; cin >> n >> m;
		if(!n && !m) break;
		pair<int, int> p[101];
		for(int i=0; i<n; i++){
			cin >> p[i].first >> p[i].second;
		}
		int sum = 0;
		int top[101]={0};

		for(int i=0; i<n; i++){
			if(top[p[i].first] < p[i].second){
				sum += p[i].second;
				sum -= top[p[i].first];
				top[p[i].first] = p[i].second;
			}
		}
	
		cout << sum << endl;
	}
}


Measured memory_bytes: 3064
#include <stdio.h>

int sqrt(int n)
{
    int lb = 1;
    int ub = n + 1;
    long long m = 0;
    while (ub - lb > 1) {
	m = (lb + ub) / 2;
	if (m * m <= n) lb = m;
	else ub = m;
    }
    return lb;
}

int main()
{
    int n;
    int i;
    scanf("%d", &n);
    printf("%d:", n);
    while (n > 1) {
	for (i = 2; i <= sqrt(n); i++) {
	    if (n % i == 0) {
		printf(" %d", i);
		break;
	    }
	}
	if (i > sqrt(n)) break;
	n /= i;
    }
    if (n != 1) printf(" %d", n);
    printf("\n");
    return 0;
}



Measured memory_bytes: 2716
#include <bits/stdc++.h>
#define COUT(x) cout << #x << " = " << (x) << ", "
typedef long long ll;
using namespace std;
static const ll MOD = 1000000007;

int main(){
  int N; cin >> N;
  vector<ll> A(N);
  vector<ll> res(N+1);
  for(int i = 0; i < N; i++){
    cin >> A[i];
    res[A[i]]++;
  }
  vector<ll> Com(N+1);
  ll sum = 0;  
  for(int i = 1; i <= N; i++){
    Com[i] = res[i] * (res[i] - 1) / 2;
    sum += Com[i];
  }
  for(int i = 0; i < N; i++){
    ll tmp = Com[A[i]];
    ll com = (res[A[i]] - 1) * (res[A[i]] - 2) / 2;
    ll res = sum - tmp + com;
    cout << res << endl;
  }
}


Measured memory_bytes: 7296
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>

#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

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

int main() {
    int N;
    string S;
    cin >> N >> S;

    int numW = 0;
    int numR = 0;
    rep(i, N) {
        if(S[i] == 'W') {
            numW++;
        } else {
            numR++;
        }
    }
    if(numW == 0 || numR == 0) {
        cout << 0 << endl;
        return 0;
    }

    int ret = 0;
    rep(i, N) {
        if(S[i] == 'W') {
            numR--;
            numW--;
            ret++;
        } else {
            numR--;
        }
        if(numR == 0 || numW == 0) {
            break;
        }
    }
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 3752
#include<iostream>
using namespace std;
int main(){
	int L,N,x,w,sum=0;
	cin>>L>>N;
	for(int i=0;i<N;i++){
		cin>>x>>w;
		sum+=x*w;
	}
	if(sum==0) cout<<0<<endl;
	else if(sum>0) cout<<1<<endl<<-1<<' '<<sum<<endl;
	else cout<<1<<endl<<1<<' '<<-sum<<endl;
	return 0;
}

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

#define MOD 1000000007
typedef unsigned long long ull;

string s = "";

int main() {
  cin >> s;

  int n = s.length();

  ull sum = 0;
  for (int tmp = 0; tmp < (1 << n - 1); tmp++) {
    // cout << endl << tmp << endl;
    string num = "";

    for (int i = 0; i < n - 1; i++) {
      // cout << s.at(i);
      num += s.at(i);
      if (tmp & (1 << i)) {
        // cout << "+";
        sum += stoull(num);
        num = "";
      }
    }
    num += s.at(n - 1);
    sum += stoull(num);
    // cout << s.at(n - 1);
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323846
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
int WRITER_DOUBLE_DIGIT = 15;
inline int writerDigit_double(){
  return WRITER_DOUBLE_DIGIT;
}
inline void writerDigit_double(int d){
  WRITER_DOUBLE_DIGIT = d;
}
inline void wt_L(double x){
  const int d = WRITER_DOUBLE_DIGIT;
  int k;
  int r;
  double v;
  if(x!=x || (x==x+1 && x==2*x)){
    my_putchar_unlocked('E');
    my_putchar_unlocked('r');
    my_putchar_unlocked('r');
    return;
  }
  if(x < 0){
    my_putchar_unlocked('-');
    x = -x;
  }
  x += 0.5 * pow(0.1, d);
  r = 0;
  v = 1;
  while(x >= 10*v){
    v *= 10;
    r++;
  }
  while(r >= 0){
    r--;
    k = floor(x / v);
    if(k >= 10){
      k = 9;
    }
    if(k <= -1){
      k = 0;
    }
    x -= k * v;
    v *= 0.1;
    my_putchar_unlocked(k + '0');
  }
  if(d > 0){
    my_putchar_unlocked('.');
    v = 1;
    for(r=(0);r<(d);r++){
      v *= 0.1;
      k = floor(x / v);
      if(k >= 10){
        k = 9;
      }
      if(k <= -1){
        k = 0;
      }
      x -= k * v;
      my_putchar_unlocked(k + '0');
    }
  }
}
template<class T> inline T pow2_L(T a){
  return a*a;
}
int A;
int B;
int H;
int M;
int main(){
  double x1;
  double y1;
  double x2;
  double y2;
  double res;
  rd(A);
  rd(B);
  rd(H);
  rd(M);
  x1 = A * cos(2*PI * (H*60+M) / (12*60));
  y1 = A * sin(2*PI * (H*60+M) / (12*60));
  x2 = B * cos(2*PI * M / 60);
  y2 = B * sin(2*PI * M / 60);
  res = sqrt((pow2_L((x1-x2)))+(pow2_L((y1-y2))));
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// int A, B, H, M;
// {
//   double x1, y1, x2, y2, res;
//   rd(A,B,H,M);
// 
//   x1 = A * cos(2*PI * (H*60+M) / (12*60));
//   y1 = A * sin(2*PI * (H*60+M) / (12*60));
//   x2 = B * cos(2*PI * M / 60);
//   y2 = B * sin(2*PI * M / 60);
//   res = sqrt( (x1-x2)**2 + (y1-y2)**2 );
//   wt(res);
// }


Measured memory_bytes: 4016
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: u64 = itr.next().unwrap().parse().unwrap();
    let k: u64 = itr.next().unwrap().parse().unwrap();
    let mut ans = 0u64;
    for b in k + 1..n + 1 {
        ans += n / b * (b - k);
        if n % b >= k {
            ans += n % b - k + 1;
        }
    }
    if k == 0 {
        ans -= n;
    }
    println!("{}", ans);
}


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

int main() {
  while(true){
    string s;
    cin >> s;
    if(s == "-") return 0;
    int n;
    cin >> n;
    for(int i =0 ;i < n;i++){
      int m;
      cin >> m;
      s += s.substr(0,m);
      s = s.substr(m);
    }
    cout << s << endl;
  }
}



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

int main(){
    int N;
    string S;
    cin >> N >> S;
    int count = 0; 
    rep (i,N-1){
        if (S.at(i) == S.at(i+1)){
            count += 1;
        }
    }
    cout << N - count << endl;
    return 0;
}

Measured memory_bytes: 512
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  a[i], b[i] = map(int,input().split())

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  x,y = max(x,y),min(x,y)
  if x == y:
    ans.append(c)
    continue
  c -= len(g[x])*len(g[y])
  ans.append(c)
  for i in g[y]:
    d[i] = x
  g[x] += g[y]
for t in ans[::-1]:
  print(t)
  

Measured memory_bytes: 39924
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1[100],s2[100];
string t;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++)
        cin >> s1[i];
    for(int j=0;j<m;j++)
        cin >> s2[j];
        
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            t+=s1[i][j];
        
    for(int i=0;i<t.size();i++){
        int g=0,cnt=0;
        for(int k=i;k<t.size();k+=n){
            string r = t.substr(k,m);
            if(r==s2[g]){
                cnt++; g++;
            }
            if(cnt==m){
                cout << "Yes";
                return 0;
            }
        }
        
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repd(i,a,b) for (int i = (a); i < (b); i++)
typedef long long ll;
int main(void)
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    int count = 0;
    rep(i, N)
    {
        while(S[i] == S[i+1])
        {
            i++;
        }
        count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
#include <math.h>
#define lop(i, n) for(i=0; i<=n; i++)

int main()
{
	int k, x, min, i;
	
	scanf("%d %d", &k, &x);
	
	min=x-k+1;
	
	lop(i,2*(k-1)){
		printf("%d ", min + i );
	}
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define ld long double
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<ll>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
#define INF 1e+9
#define MAX_N 200000

int dp[MAX_N];
int n;
vector<int> a;

int lis() {
    fill(dp, dp+n, INF);
    for (int i=0; i<n; ++i) {
        *upper_bound(dp, dp+n, a[i]) = a[i];
    }
    return lower_bound(dp, dp+n, INF) - dp;
}


int main(){
  cin >> n;
  a.resize(n);
  rep(i,n)cin >> a[n-i-1];
  int u=a[0];
  int o=0;
  rep(i,n-1)if(u!=a[i+1])o++;
  if(o==0){
    cout << n << endl;
    return 0;
  }
  
  cout << lis() << endl;
}


Measured memory_bytes: 1024
/******************************************
* AUTHOR : SOMU KUMAR *
* INSTITUTION : IIT BHUBANESWAR *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//code here...............//
int n;
cin>>n;
if(n%1000==0)cout<<0<<endl;
else cout<<(1000-(n%1000))<<endl;
return 0;
}

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

using namespace std;
typedef long long ll ;
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define pb push_back

ll p=1e9+7 ;

int main()
{
	int T=1;
	// cin >> T ;

	while(T--)
	{
		int n ;
		cin>>n ;
		double p[n] ,a,b,ans=0;
		rep(i,0,n) cin>>p[i] ;
		double dp[n][n] ;
		memset(dp,0,sizeof(dp)) ;

		rep(i,0,n)
		{
			rep(j,0,i+1)
			{
				if(i>0) a=dp[i-1][j] ;
				else a=0 ;
				if(i>0 && j>0) b=dp[i-1][j-1];
				else b=1 ;

				dp[i][j]=a*(1-p[i]) + b*p[i] ;
			}
		}
		// rep(i,0,n)
		// {
		// 	rep(j,0,n)
		// 	{
		// 		cout<<dp[i][j]<<" " ;
		// 	}
		// 	cout<<endl ;
		// }
		// rep(i,n/2,n)
		// {
		// 	ans += dp[n-1][i] ;
		// }
		printf("%.9lf\n",dp[n-1][n/2]) ;
	}	
	return 0;
}

Measured memory_bytes: 74000
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
//const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    string s; cin >> s;
    int n = s.size();
    int c = 0;
    int a = 0;
    int b = 0;
    rep(i,n){
        string t = to_string(c);
        if (s.substr(i,1) != t) a++;
        c = 1 - c;
    }
    c = 1;
    rep(i,n){
        string t = to_string(c);
        if (s.substr(i,1) != t) b++;
        c = 1 - c;
    }
    cout << min(a,b) << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 5000+10;
const ll mod =   1e9+7;

int main()
{  fast
int x,z;
cin>>x>>z;
for(int i=0;i<=x;i++){
	int y=x-i;
	int sum=y*4+i*2;
	if(sum==z){

	cout<<"Yes\n";return 0;}
}
cout<<"No";


}

Measured memory_bytes: 3644
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Linq.Enumerable;
using static System.Math;

class Program
{
    static void Main()
    {
        var ABC = ReadLine().Split(' ').Select(int.Parse).ToArray();

        var (s, m, l) = ABC.OrderBy(x => x).ToArray();

        var ans = l - m + (m - s + 1) / 2 + (m - s) % 2;

        WriteLine(ans);
    }
}

static class ArrayDeconstructExtensions
{
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2) => (i1, i2) = (a[0], a[1]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3) => (i1, i2, i3) = (a[0], a[1], a[2]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4) => (i1, i2, i3, i4) = (a[0], a[1], a[2], a[3]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4, out T i5) => (i1, i2, i3, i4, i5) = (a[0], a[1], a[2], a[3], a[4]);
}


Measured memory_bytes: 28276
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int h, w;   cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++)
        cin >> s[i];

    vector<vector<int> > a(h, vector<int>(w, 0)), b(h, vector<int>(w, 0)), c(h, vector<int>(w, 0)), d(h, vector<int>(w, 0));
    
    for (int i = 0; i < h; i++) {
        for (int j = 1; j < w; j++) {
            if (s[i][j-1] == '.')
                a[i][j] = a[i][j-1]+1;
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = w-2; j >= 0; j--) {
            if (s[i][j+1] == '.')
                b[i][j] = b[i][j+1] + 1;
        }
    }

    for (int i = 1; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i-1][j] == '.')
                c[i][j] = c[i-1][j] + 1;
        }
    }
    for (int i = h-2; i >= 0; i--) {
        for (int j = 0; j < w; j++) {
            if (s[i+1][j] == '.')
                d[i][j] = d[i+1][j] + 1;
        }
    }

    long long ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '.')
                ans = max(ans, (long long)(a[i][j]+b[i][j]+c[i][j]+d[i][j]+1));
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 73660
#include<stdio.h>
#define N 100

int main(){
  int n, flag=0, i, j;
  int A[N+1];
  int key;
  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);

  for(j=2; j<=n; j++){
    key = A[j];
    i = j-1;

    while(i>0 && A[i]>key){
      A[i+1] = A[i];
      i = i-1;
      A[i+1] = key;
      flag++;
    }
  }

  for(i=1; i<=n; i++){
    if(i>1) printf(" ");
    printf("%d",A[i]);
  }

  printf("\n%d\n",flag);

  return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

int R, C;

string s[1001];

int memo[1001][1001];

struct State {
  int first, second, cost;
};

int main2() {
  R = nextLong();
  C = nextLong();

  int sr = nextLong()-1;
  int sc = nextLong()-1;
  int gr = nextLong()-1;
  int gc = nextLong()-1;

  REP(i, R) {
    cin >> s[i];
  }

  const int INF = 1001001001;
  REP(i, 1001) REP(j, 1001) memo[i][j] = INF;

  deque<State> q;
  q.push_front((State){sr, sc, 0});
  memo[sr][sc] = 0;

  while (!q.empty()) {
    auto cur = q.front(); q.pop_front();

    if (memo[cur.first][cur.second] != cur.cost) continue;

    for (int dr = -2; dr <= 2; dr++) {
      for (int dc = -2; dc <= 2; dc++) {
        int nr = cur.first + dr;
        int nc = cur.second + dc;
        if (!(0 <= nr && nr < R && 0 <= nc && nc < C)) continue;
        if (s[nr][nc] != '.') continue;

        if (abs(dr) + abs(dc) == 1) {
          if (memo[nr][nc] > cur.cost + 0) {
            memo[nr][nc] = cur.cost + 0;
            q.push_front({nr, nc, memo[nr][nc]});
          }
        } else {
          if (memo[nr][nc] > cur.cost + 1) {
            memo[nr][nc] = cur.cost + 1;
            q.push_back({nr, nc, memo[nr][nc]});
          }
        }
      }
    }
  }
  ll ans = memo[gr][gc];
  if (ans == INF) {
    ans = -1;
  }
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 9612