akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

template<typename T>
struct Bit {
  int N; // 2のべき乗でなくてもOK
  vector<T> node;
  Bit(int N) : N(N), node(N + 1, 0) {}
  void add(int i, T w) // node[i] += w
  {
    for (int x = ++i; x <= N; x += x & -x) node[x] += w;
  }
  T sum(int i) // return sum [0, i)
  {
    T ans = 0;
    for (int x = i; x > 0; x -= x & -x) ans += node[x];
    return ans;
  }
  T sum(int i, int j) // return sum [i, j)
  {
    return sum(j) - sum(i);
  }
  vector<T> debug()
  {
    vector<T> a;
    for (int i = 0; i < N; i++) {
      a.push_back(sum(i, i + 1));
    }
    return a;
  }
};

void solve() {
  int n;
  cin >> n;
  vi a(n), b(n);
  rep(i, n) cin >> a[i];
  b = a;
  sort(b.begin(), b.end());
  ll total = (ll)(n + 1) * n / 2;
  dump(a, b, total);
  auto inv = [&](int x) { // 転倒数を求める
    const int base = n + 1;
    vi cum(n + 1);
    rep(i, n) cum[i + 1] = cum[i] + (a[i] < x ? -1 : 1);
    Bit<ll> bit(base + n + 1);
    ll cnt = 0;
    rep(i, n + 1) {
      cnt += bit.sum(base + cum[i] + 1);
      bit.add(base + cum[i], 1);
    }
    return cnt;
  };
  int left = 0;
  int right = n - 1;
  int ans = 0;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (total / 2 <= inv(b[mid])) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  cout << b[ans] << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 3044
#include<stdio.h>
#include<math.h>

int main(void)
{
	int i;
	double n,x[1000],y[1000],d[100],d1=0,d2=0,d3=0,max=0;

	scanf("%lf",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lf",&x[i]);
	}
	for(i=0;i<n;i++)
	{
		scanf("%lf",&y[i]);
	}
	for(i=0;i<n;i++)
	{
		d[i]=fabs(x[i]-y[i]);
		d1+=d[i];
	}
	printf("%f\n",d1);

	for(i=0;i<n;i++)
	{
		d2+=d[i]*d[i];
	}
	printf("%f\n",sqrt(d2));

	for(i=0;i<n;i++)
	{
		d3+=d[i]*d[i]*d[i];
	}
	printf("%f\n",pow(d3,1.0/3.0));

	for(i=0;i<n;i++)
	{
		if(d[i]>max)
		{
			max=d[i];
		}
	}
	printf("%f\n",max);

	return 0;
}


Measured memory_bytes: 696
/*
 * C.cpp
 *
 *  Created on: 2020/06/07
 *      Author: admin
 */


#include <iostream>


using namespace std;


int main(){
	long long A;
	long double B;
	cin >> A >> B;
	long long C = B*100+0.1;
	long long result;
	result = A*C/100;
	cout << result << endl;
}


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

int main(){
	int N; cin>>N;
	vector<int> A(N), rev(N);
	for(int i = 0; i < N; i++) cin >> A[i];

	// 桶排序
	for(int i = 0; i < N; i++)
		rev[A[i]-1] = i + 1;
	for(int i = 0; i < N; i++)
		cout << rev[i] << endl;
	return 0;
}

Measured memory_bytes: 1664
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(long long i=0;i<(long long)(n);i++)
#define N 201000


int main() {
	char a[N + 1];
	f(i, N + 1)a[i] = 0;
	long long ans;
	long long n;
	long long x, y, z;
	bool v;
	scanf("%s", a);
	n = strlen(a);
	ans = 0;
	x = 0;
	for (long long i = n-1; i >=0; i--) {
		if (a[i] == 'A') {
			y = i + 1;
			z = 0;
			while (true) {
				if (y >= n) {
					v = false;
					break;
				}
				if (a[y] == 'A') {
					v = true;
					break;
				}
				if (a[y] == 'C') {
					v = false;
					break;
				}

				if (y + 1 >= n)	{
					v = false;
					break;
				}
				if (a[y + 1] != 'C') {
					v = false;
					break;
				}
				y += 2;
				z++;
			}
			if (v)z += x;
			ans += z;
			x = z;
		}
	}
	printf("%lld\n", ans);

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int min=2147483647;
  for(int i=0;i<N;i++){
    int A;
    cin >> A;
    int time=0;
    
    for(int j=A;j%2==0;j/=2){
      time++;
    }
   
    if(time<=min){
      min=time;
    }
  }
  cout << min << endl;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;
typedef pair<int,int> ii;

#define MAX 200010
ll xs[MAX], ys[MAX];

struct Data1 {
  ll x,y;
  bool operator < ( const Data1 &d ) const {
    return x-y < d.x-d.y;
    //return llabs(x-y) < llabs(d.x-d.y);
  }
};

struct Data2 {
  ll x,y;
  bool operator < ( const Data2 &d ) const {
    return x+y < d.x+d.y;
  }
};

int n;


ll solve() {
  ll ret = 0;
  rep(i,n) {
    rep(j,n) {
      ll v = llabs(xs[i]-xs[j]) + llabs(ys[i]-ys[j]);
      ret = max(ret,v);
    }
  }
  return ret;
}

int main() {
  if( 0 ) {
    n = 100;
    cout << n << endl;
    srand((unsigned int)time(NULL));
    rep(i,n) {
      cout << rand() % 100 + 1 << " " << rand() % 100 + 1 << endl;
    }
    return 0;
  }
  
  cin >> n;
  rep(i,n) cin >> xs[i] >> ys[i];
  //cout << "Answer: " << solve() << endl;
  vector<Data1> vec1;
  vector<Data2> vec2;
  rep(i,n) {
    vec1.pb((Data1){xs[i],ys[i]});
    vec2.pb((Data2){xs[i],ys[i]});
  }
  sort(ALL(vec1));
  sort(ALL(vec2));
  Data1 L = vec1[0];
  Data1 R = vec1[n-1];
  ll ans = llabs( L.x - R.x ) + llabs( L.y - R.y );
  Data2 L2 = vec2[0];
  Data2 R2 = vec2[n-1];
  ans = max(ans, llabs( L2.x - R2.x ) + llabs( L2.y - R2.y ) );
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 12956
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int ans = 0;

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
//		int d = sc.nextInt();
//
		boolean f = true;
		int[] array = new int[n];
		int[] array2 = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
			if(array[i] != i+1) {
				f=false;
			}
		}

		if(f) {
			System.out.println("YES");
			sc.close();
			return;
		}
		f= true;

		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				f = true;
				System.arraycopy(array,0,array2,0,n);
				array2[j] = array[i];
				array2[i] = array[j];
				for(int k= 0;k<n;k++) {
					if(array2[k] != k+1) {
						f = false;
						break;
					}
				}
				if(f) {
				System.out.println("YES");
				sc.close();
				return;
				}

			}
		}
		System.out.println("NO");

		sc.close();
	}
}

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

int main(void) {
	int N;
	scanf("%d", &N);
	int A[200100];
	long ans = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		if (i != 0) {
			int add = max(0, A[i - 1] - A[i]);
			ans += add;
			A[i] += add;
		}
	}
	printf("%ld\n", ans);
	return 0;
}


Measured memory_bytes: 4592
a = list(map(int,input().split()))
H=a[0]
W=a[1]
S = [input().split() for l in range(H)]

for i in range(H):
    if 'snuke' in S[i]:
        raw=i+1
        try:
            column=S[i].index('snuke')+1
            num2alpha = lambda c: chr(c+64)
            column=num2alpha(column)
        except:
            continue

print(column+str(raw))



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

using namespace std;

int main(void) {
    int n;
    string s;
    cin >> n >> s;

    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') l++;
        else l = max(l - 1, 0);
    }
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == ')') r++;
        else r = max(r - 1, 0);
    }

    for (int i = 0; i < r; i++)
        cout << "(";
    cout << s;
    for (int i = 0; i < l; i++)
        cout << ")";
    cout << endl;

    return 0;
}

Measured memory_bytes: 384
import copy
 
n = int(input())
x = list(map(int, input().split(" ")))

y = copy.copy(x)
x.sort()
l = len(x)
m0 = x[int(l/2 - 1)]
m1 = x[int(l/2)]


for i in y:
    if i <= m0:
        print(m1)
    else:
        print(m0)

Measured memory_bytes: 27156
package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
func main() {
	fsc := NewFastScanner()
	S := fsc.Next()
	if S[0] == S[2] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}
 
//template
type FastScanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}
 
func NewFastScanner() *FastScanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1024)
	return &FastScanner{r: rdr}
}
func (s *FastScanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *FastScanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *FastScanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *FastScanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}
 
func (s *FastScanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *FastScanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}
 
//Max,Min
func IntMax(a, b int) int {
	if a < b {
		return b
	}
	return a
}
 
func Int64Max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}
func Float64Max(a, b float64) float64 {
	if a < b {
		return b
	}
	return a
}
 
func IntMin(a, b int) int {
	if a > b {
		return b
	}
	return a
}
 
func Int64Min(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}
func Float64Min(a, b float64) float64 {
	if a > b {
		return b
	}
	return a
}
 
//Gcd
func IntGcd(a, b int) int {
	if a < b {
		b, a = a, b
	}
	if b == 0 {
		return a
	}
	return IntGcd(b, a%b)
}
func Int64Gcd(a, b int64) int64 {
	if a < b {
		b, a = a, b
	}
	if b == 0 {
		return a
	}
	return Int64Gcd(b, a%b)
}
 
func IntAbs(a int) int {
	if a < 0 {
		a *= -1
	}
	return a
}
 
func Int64Abs(a int64) int64 {
	if a < 0 {
		a *= -1
	}
	return a
}


Measured memory_bytes: 640
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int main(void){
  int n,m;
  cin >> m >> n;
  int res = 0;
  for(int i = 0; i < m; i++){
    int t = 0;
    for(int j = 0; j < n; j++){
      int a;
      cin >> a;
      t += a;
    }
    res = max(res,t);
  }
  cout << res << endl;
}

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

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        int k,p;
        scanf("%d %d",&k,&p);
        int ans = k%p;
        if(ans == 0)ans = p;
        printf("%d\n",ans);
    }

    return 0;
}

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

int main(){
  int a,b;
  int n;

  scanf("%d",&n);

  if(n==1){
    printf("Hello World\n");
  }

  if(n==2){
    scanf("%d",&a);
    scanf("%d",&b);
    printf("%d\n",a+b);
  }

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
using namespace std;
 
int main() {
  int n;
  string s;
  cin >> n >> s;
  int x = 0, max = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == 'I') x = x+1;
    if(s[i] == 'D') x = x-1;
    if(max < x){max = x;}
  }
 cout << max << endl;
}

Measured memory_bytes: 384
//shara's here
//SPEEEEEEEEEED IS KEEEEEEEEEEY
//REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEAD
#include <bits/stdc++.h>
using namespace std;
typedef string s;
typedef long long ll;
typedef long double ld;
#if !defined(ONLINE_JUDGE)
#include "C:\debug.hpp"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define pb push_back
#define ins insert
#define vl vector<ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int main(){
    speed;
    ll n;
    cin>>n;
    vl v(n);
    for( ll i=1;i<n;i++){
        ll k; cin>>k;
        v[k-1]++;
    }
    for( ll i=0;i<n;i++)cout<<v[i]<<endl;

















return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/


Measured memory_bytes: 4776
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define Yes()           printf("Yes\n")
#define No()            printf("No\n")
#define YES()           printf("YES\n")
#define NO()            printf("NO\n")
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  int n, a, b; cin >> n >> a >> b;
  outl(min(n * a, b));
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<string>

using namespace std;

int main(void){
  string s;

  while(cin >> s){
    string ans="";
    for(int i=0;i<s.size();i++){
      if(s[i]=='A')ans+='X';
      else if(s[i]=='B')ans+='Y';
      else if(s[i]=='C')ans+='Z';
      else ans+=s[i]-3;
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
template<typename T> inline void add(T& a, T b) { a += b; if (a >= MOD) a -= MOD; }

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

  int N; cin >> N;
  vector<ll> A(N+1);
  A[0] = 0;
  map<ll,ll> T;
  T[0] = 1;
  rep1(i, N) {
    cin >> A[i];
    A[i] += A[i-1];
    T[A[i]]++;
  }

  ll ans = 0;
  for(auto t : T) {
    if(t.second >= 2) {
      ans += t.second * (t.second - 1) / 2;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 14336
n = int(input())
lst = [int(x) for x in input().split()]

func = lambda x : 1 if( x > 1) else 0 if( x == 0) else -1

signs = [func(x) for x in lst]
lst = [abs(x) for x in lst]

if(signs.count(-1)%2 == 1):
    m = min(lst)
    lst.remove(m)
    s = sum(lst) - m
    print(s)
else:
    print(sum(lst))

Measured memory_bytes: 14412
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int result = a + b;

			if (result < a - b) {
				result = a - b;
			}
			if (result < a * b) {
				result = a * b;
			}
			System.out.println(result);
		}
	}
}


Measured memory_bytes: 22228
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public static class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Program
{
    static int N, M;
    static int[] X;

    public static void Main(string[] args)
    {
        N = Input.NextInt();
        M = Input.NextInt();

        if (N >= M)
        {
            Console.WriteLine(0);
            return;
        }

        X = Input.LineInt();
        Array.Sort(X);

        var hasamerikazu = N - 1;
        var kankaku = new int[M - 1];

        for (int i = 0; i < kankaku.Length; i++)
            kankaku[i] = X[i + 1] - X[i];

        Array.Sort(kankaku);
        Array.Reverse(kankaku);

        int sum = 0;
        for (int i = hasamerikazu; i < kankaku.Length; i++)
        {
            sum = sum + kankaku[i];
        }

        Console.WriteLine(sum);
    }
}


Measured memory_bytes: 17504
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

var ans int

func main() {
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(stringLineScan())
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(stringLineScan())
		a[i] -= i + 1
	}
	sort.Ints(a)
	b := a[n/2]
	ans := 0
	for i := 0; i < n; i++ {
		ans += abs(b - a[i])
	}
	fmt.Println(ans)
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}


Measured memory_bytes: 5248
#include <iostream>
using namespace std;
int main()
{
  int n;
  cin >> n;
  while(n--){
    string str;
    int o = 0, p = 0, r=0;
    while(o < 3){
      cin >> str;
      if(str == "HIT"){
	if(r<3) r++;
	else p++;
      }else if(str == "HOMERUN"){
	p += r+1;
	r = 0;
      }else if(str == "OUT"){
	o++;
      }
    }
    cout << p << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;
// driver
int main() {
   // 11:34 - 
   int n;
   cin >> n;
   vector<int> a(n), dp(n, 0);
   for (int i=0; i<n; ++i) cin >> a[i];

   // dp[i] = min(dp[i-1] + abs(a[i]-a[i-1]), dp[i-2] + abs(a[i]-a[i-2]))

   for (int i=1; i<n; ++i) {
     int& val = dp[i];
     val = dp[i-1] + abs(a[i] - a[i-1]);
     if (i > 1)
       val = min(val, dp[i-2]+abs(a[i] - a[i-2]));
   }

   cout << dp.back() << endl;

   return 0;
}

Measured memory_bytes: 1024
N = int(input())
A = sorted(list(map(int,input().split())))
pre = [A[0]]
for i in range(1,N):
  pre.append(pre[i-1] + A[i])

can = [False for x in range(N-1)] + [True]
for i in range(N-2,-1,-1):
  if pre[i] >= A[i+1] / 2 and can[i+1]:
    can[i] = True
print(can.count(True))

Measured memory_bytes: 14320
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int  main(){
ll h;
cin >> h;
ll ans =0,che=0;
while(h!=1){
 h/=2;
 ans+=pow(2,che);
 che++;
}
ans += pow(2,che);
cout << ans << endl;
}





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

using namespace std;

#define fast_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define int long long
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define MOD 1000000007

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

int n, m, i;

signed main()
{
    fast_IO;
    int test = 1;
    // cin >> test;
    while(test--)
    {
        cin >> n;
        if(n >= 30)
            return cout << "Yes", 0;
        cout << "No";
    }
    return 0;
} 

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
string to_str(ll x){string res; while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return res;}
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; }
//template end



int main(){
    ll n,m,v,p; scanf("%lld%lld%lld%lld",&n,&m,&v,&p);
    vector<ll> a(n);
    rep(i,0,n)scanf("%lld",&a[i]);
    sort(ALL(a)); ll lb=-1,rb=n;
    while(rb-lb>1){
        ll mid=(lb+rb)/2;
        if(a[n-p]-a[mid]>m){lb=mid; continue;}
        ll cnt=0;
        rep(i,mid+1,n-p+1)cnt+=a[i]-a[mid];
        if(cnt>m*(n-v))lb=mid; else rb=mid;
    }
    printf("%lld\n",n-rb);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define fast_cin() ios_base::sync_with_stdio(0) 
typedef long long int ll;
using namespace std;
const int MOD=1e9+7;
const int size=1e5+5;

ll a[size],b[size];

int main()
{
	ll n;
	string s;
	cin >> s;
	string x="AC";
	for(int i=0;i<s.length()-1;i++)
	{
		string y=s.substr(i,2);
		//cout << x << " " << y << endl;
		if(x==y)
		{
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";

}


Measured memory_bytes: 256
#include<numeric>
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
	int a[5];
	for(int i=0;i<5;i++)	cin>>a[i];
	sort(a,a+5,greater<int>());
	for(int i=0;i<5;i++)	cout<<(i?" ":"")<<a[i];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 0
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a = sorted(a)
ans = a[Q-1] - a[0]

while True:
  d_temp = list()
  sub_temp = list()
  for sub in d:
    for c in sub:
      if c != a[0]:
        sub_temp.append(c)
      else:
        d_temp.append(sub_temp)
        sub_temp = list()
    d_temp.append(sub_temp)
    sub_temp = list()

  d = list()
  a = list()
  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub = sorted(sub)
      a.extend(sub[0:len(sub)-K+1])

  a = sorted(a)

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)


Measured memory_bytes: 3316
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ans = 0
tmp = 0
for i in a:
	ans += b[i-1]
	if i == tmp+1 and tmp != 0:
		ans += c[tmp-1]
	tmp = i

print(ans)

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

using namespace std;

int main()
{
  int N, M, A[1000];

  cin >> N >> M;
  for(int i = 0; i < N; i++) cin >> A[i];
  
  int now = 0, flag = false, sum = 0;
  vector< int > vs;
  while(!flag || now != 0) {
    int aa = 114514, bb = -114514;
    for(int i = 0; i < M; i++) {
      aa = min(aa, A[now]);
      bb = max(bb, A[now]);
      now = (now + 1) % N;
    }
    sum += bb - aa;
    flag = true;
  }
  cout << sum << endl;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define endl '\n'
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define pb push_back
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()

using namespace std;

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b){
    return (a*b)/gcd(a,b);
}
int ncr(int n, int k){
    int res = 1;
    if ( k > n - k )
        k = n - k;

    for (int i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

int fibonacci(int n){
    double phi = (1LL + sqrt(5))/(double)2;
    int nth_fib = round(pow(phi,n)/sqrt(5));
    return nth_fib;
}

signed main(){

    fastIO

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


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

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



Measured memory_bytes: 256
N,M = gets.split.map(&:to_i)

g = Array.new(N){Array.new(N)}

M.times do |i|
  
  a,b = gets.split.map(&:to_i).sort.reverse
  a -= 1
  b -= 1
  g[a][b] = g[b][a] = 1
end

# p g
 
pattern = [*1...N].permutation(N-1).to_a.map{ |k| [0] + k }

# p pattern.length

ans = 0
pattern.each do |p|
  
  f = true
  (1...N).each do |i|
    p [p[i-1], p[i]]
    if g[p[i-1]][p[i]].nil?
      f = false
      break
    end
  end
  ans += 1 if f
  # p p if f
end

puts ans

Measured memory_bytes: 3452
# https://atcoder.jp/contests/abc051/submissions/1055446

def main():
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

    N, M = map(int, input().split())

    dist = [[inf for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = 0

    es = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        es.append((a, b, c))
        dist[a][b] = dist[b][a] = c

    for k in range(N):
        for j in range(N):
            for i in range(j):
                d = dist[i][k] + dist[k][j]
                if dist[i][j] > d:
                    dist[i][j] = dist[j][i] = d

    ans = 0
    for a, b, c in es:
        if dist[a][b] == c: continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template <typename T1, typename T2> 
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, r;
  cin >> n >> r;
  if(n >= 10){
    cout << r << endl;
  }else{
    cout << r + 100 * (10 - n) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
r,s,p = map(int,input().split())
t = input()
t2 = []
for i in range(k):
  t2.append(t[i:n:k])
ans = 0
for i in t2:
  c = [0,0,0]
  nc = [0,0,0]
  for j in i:
    if j == "s":
      nc[0] = max(c[1],c[2]) + r
    else:
      nc[0] = max(c[1],c[2])
    if j == "p":
      nc[1] = max(c[0],c[2]) + s
    else:
      nc[1] = max(c[0],c[2])
    if j == "r":
      nc[2] = max(c[0],c[1]) + p
    else:
      nc[2] = max(c[0],c[1])
    c = nc.copy()
  ans += max(c)
print(ans)

Measured memory_bytes: 8828
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PI;
const double EPS = 1e-9;
#define rep(i,s,n) for(int i=(s); i < int(n); ++i)

const int N = 101;
const int V = 1e5 + 1;
int v[N], w[N];
int n, wlim;
int tv[N];

int dp[N][V];
const int INF = 0x2fffffff;
const int DEBUG = 0;

int solve(void) {
  dp[0][0] = 0;
  int total_v = 1;
  rep(i, 0, n) {
    total_v += v[i];
  }
  rep(j, 1, total_v) {
    dp[0][j] = INF;
  }
  rep(i, 1, n + 1) {
    rep(j, 0, total_v) {
      int res = dp[i-1][j];
      int val = v[i-1];
      int wei = w[i-1];
      if (val <= j) {
	res = min(res, dp[i - 1][j - val] + wei);
      } else {
	res = min(res, wei);
      }
      if(DEBUG) {
	cout << "dp[" << i << "][" << j << "] = " << res << endl;
      }
      dp[i][j] = res;
    }
  }
  int q = 0;
  rep(i,0,total_v) {
    if (dp[n][i] <= wlim) {
      q = i;
    }
  }
  if(DEBUG) {
    cout << "q = " << q << endl;
  }
  int rem = q;
  int sum = 0;
  for (int i = n; i > 0; --i) {
    int val = v[i-1];
    int wei = w[i-1];
    if (val <= rem && dp[i][rem] - wei == dp[i - 1][rem - val]) {
      // output (i - 1)
      sum += tv[i - 1];
      rem -= val;
    }
  }
  return sum;
}


int main(void) {
  cin >> n >> wlim;
  double max_v = 0.0;
  rep(i, 0, n) {
    cin >> tv[i] >> w[i];
    max_v = max(max_v, (double) tv[i]);
  }
  double k = 45;
  double scale = max(1.0, max_v / (k + 1) / n);
  rep(i, 0, n) {
    v[i] = (int) floor(tv[i] / scale);
  }
  cout << solve() << endl;
}

Measured memory_bytes: 40612
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);



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

	int N, M;
	cin >> N >> M;
	vector<int>A(M);
	rep(i, M)cin >> A[i];

	if (N <= 2) {
		rep(i, M) {
			if (i)cout << " ";
			cout << A[i];
		}
		cout << endl;
		cout << 1 << endl << N << endl;
		return 0;
	}
	if (M == 1) {
		cout << A[0] << endl << 2 << endl << A[0] - 1 << " " << 1 << endl;
		return 0;
	}
	if (M == 2) {
		sort(ALL(A));
		rep(i, M) {
			if (i)cout << " ";
			cout << A[i];
		}
		cout << endl;
		cout << 2 << endl << A[0] + 1 << " " << A[1] - 1 << endl;
		return 0;
	}

	vector<int>odd;
	rep(i, M)if (A[i] % 2 == 1)odd.push_back(A[i]);
	if (3 <= odd.size()) {
		cout << "Impossible" << endl;
		return 0;
	}
	sort(ALL(odd));
	vector<int>ansa;
	if (odd.size())ansa.push_back(odd[0]);
	rep(i, M)if (A[i] % 2 == 0)ansa.push_back(A[i]);
	if (odd.size() == 2)ansa.push_back(odd[1]);
	rep(i, M) {
		if (i)cout << " ";
		cout << ansa[i];
	}
	cout << endl;
	cout << (ansa[0] == 1 ? M - 1 : M) << endl;
	if (ansa[0] != 1)cout << ansa[0] - 1;
	REP(i, 1, M - 1)cout << " " << ansa[i];
	cout << " " << ansa[M - 1] + 1 << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 1LL << 60;
const long long MOD = 1000000007;

vector<long long> dijkstra(const vector<vector<pair<int,int>>>& g, int S){
	int n = g.size();
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> qu;
	qu.emplace(0, S);
	vector<long long> res(n, INF);
	res[S] = 0;
	while(!qu.empty()){
		auto p = qu.top(); qu.pop();
		const int pos = p.second;
		const long long dist = p.first;
		for(const auto& next : g[pos]){
			int nextPos = next.first;
			long long nextDist = res[pos] + next.second;
			if(nextDist < res[nextPos]){
				res[nextPos] = nextDist;
				qu.emplace(nextDist, nextPos);
			}
		}
	}
	return res;
}

vector<long long> calcPath(const vector<vector<pair<int,int>>>& g, const vector<long long>& dist, int S){
	vector<long long> res(g.size(), 0);
	vector<int> visit(g.size(), 0);
	res[S] = 1;
	priority_queue<pair<long long, int>> qu;
	qu.emplace(dist[S], S);
	while(!qu.empty()){
		auto p = qu.top(); qu.pop();
		int pos = p.second;
		if(visit[pos]) continue;
		visit[pos] = 1;
		for(auto& next : g[pos]){
			if(dist[next.first] + next.second == dist[pos]){
				res[next.first] = (res[next.first] + res[pos]) % MOD;
				qu.emplace(dist[next.first], next.first);
			}
		}
	}
	return res;
}

int main(){
	int N, M;
	while(cin >> N >> M){
		int S, T; cin >> S >> T;
		--S; --T;
		vector<vector<pair<int,int>>> g(N);
		for(int i=0;i<M;i++){
			int U, V, D; cin >> U >> V >> D;
			--U; --V;
			g[U].emplace_back(V, D);
			g[V].emplace_back(U, D);
		}
		vector<long long> distS = dijkstra(g, S);
		vector<long long> distT = dijkstra(g, T);
		vector<long long> pathNumS = calcPath(g, distT, S);
		vector<long long> pathNumT = calcPath(g, distS, T);
		long long res = pathNumS[T] * pathNumS[T] % MOD;
		for(int i=0;i<N;i++){
			if(distS[T]%2 == 0 && distS[i] == distS[T]/2){
				long long num = pathNumS[i] * pathNumT[i] % MOD;
				long long sub = num * num % MOD;
				res = (res + MOD - sub) % MOD;
			}
			if(2*distS[i] < distS[T]){
				for(const auto& p : g[i]){
					if(distS[i] + p.second == distS[p.first] && distS[T] < 2*distS[p.first]){
						long long num = pathNumS[i] * pathNumT[p.first] % MOD;
						long long sub = num * num % MOD;
						res = (res + MOD - sub) % MOD;
					}
				}
			}
		}
		cout << res << endl;
	}
}


Measured memory_bytes: 14036
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <map>
#include <cstdlib>
using namespace std;

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0])
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.*;
import java.math.*;
import java.util.HashMap;

public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		//int a = sc.nextInt();
		// スペース区切りの整数の入力
		//int b = sc.nextInt();
		//int c = sc.nextInt();
		// 文字列の入力
		//String s = sc.next();
		//1文字ずつ
		//s.atChar(i);
		// 出力
		//System.out.println("");
		//double countx=0;
		//int n=sc.nextInt();
		
		String s = sc.next();
		
		int yy=Integer.parseInt(s.substring(0,4));
		int mm=Integer.parseInt(s.substring(5,7));
		int dd=Integer.parseInt(s.substring(9,10));
		//System.out.print(mm);
		
		boolean x=false;//false=heisei
	
		
		if(yy==2019){
			if(mm>4){
				x=true;
				
			}
		}
		
		if(yy > 2019){
			x=true;
		}
		
		if(x){
			System.out.println("TBD");
		}else{

			System.out.println("Heisei");
		}
		
	}
		
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define SIZE 200005
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

char str[SIZE];
int dp[2];

int main()
{
	scanf("%s",&str);
	int n=strlen(str);
	ll ret=0;
	dp[0]=dp[1]=0;
	for(int i=0;i<n;i++)
	{
		if(str[i]=='0')
		{
			ret+=max(dp[0],dp[1]);
			int m=max(dp[0],dp[1]);
			dp[0]=dp[1]=m;
		}
		else if(str[i]=='1')
		{
			ret+=i/2+1;
			int o=max(dp[1],dp[0]+1);
			int z=max(dp[0],dp[1]);
			dp[0]=z,dp[1]=o;
		}
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 4008
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>


#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int x, y, a, b, c; cin >> x >> y >> a >> b >> c;
	vector<int64_t> ps(a); for (auto& p : ps) cin >> p;
	vector<int64_t> qs(b); for (auto& q : qs) cin >> q;
	vector<int64_t> rs(c); for (auto& r : rs) cin >> r;

	sort(ps.begin(), ps.end());
	sort(qs.begin(), qs.end());
	sort(rs.begin(), rs.end());

	int64_t okv = 0; int64_t ngv = 1000000001;
	while (okv + 1 < ngv) {
		int64_t m = (okv + ngv) / 2;

		int64_t cc = 0;
		{
			auto it = std::lower_bound(ps.begin(), ps.end(), m);
			cc += min((int)(ps.end() - it), x);
		}
		{
			auto it = std::lower_bound(qs.begin(), qs.end(), m);
			cc += min((int)(qs.end() - it), y);
		}
		{
			auto it = std::lower_bound(rs.begin(), rs.end(), m);
			cc += rs.end() - it;
		}

		if ((x + y) <= cc) {
			okv = m;
		}
		else {
			ngv = m;
		}
	}

	int64_t ans = 0;
	int64_t cc = 0;
	FOR_LT(i, 0, a) {
		if (x <= i) break;
		if (okv <= ps[a - i - 1]) {
			ans += ps[a - i - 1];
			cc++;
		}
		else {
			break;
		}
	}
	FOR_LT(i, 0, b) {
		if (y <= i) break;
		if (okv <= qs[b - i - 1]) {
			ans += qs[b - i - 1];
			cc++;
		}
		else {
			break;
		}
	}
	int64_t rc = (x + y) - cc;
	FOR_LT(i, 0, rc) {
		ans += rs[c - i - 1];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <unordered_map>
#include <algorithm>
#include <climits>

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int lcm(int a,int b){return a*b/gcd(a,b);}
typedef long long ll;
typedef std::vector<int> VI;
typedef std::pair<int, int> PII;

using namespace std;


int main()
{
  int N;
  cin >> N;
  vector<int> V(N,0);
  REP(i, N) {
    cin >> V[i];
  }
  sort(all(V));
  double ans = V[0];
  for (int i = 1; i < N; i++)
  {
    ans = ans + V[i];
    ans /= 2.0;
  }
  printf("%.8lf\n", ans);
}


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

int main(){
	int N, i, j, k;
	scanf("%d", &N);
	vector<int> S(1 << N);
	for(i = 0; i < (1 << N); i++){
		scanf("%d", &S[i]);
	}
	sort(S.begin(), S.end(), greater<int>());
	for(i = 0; i < N; i++){
//		printf("i = %d\n", i);
		sort(S.begin(), S.begin() + (1 << i), greater<int>());
		sort(S.begin() + (1 << i), S.end(), greater<int>());
/*		for(j = 0; j < (1 << N); j++){
			printf("%d ", S[j]);
		}
		printf("\n");
*/		for(j = 0, k = (1 << i); j < (1 << i); j++){
			while(k < (1 << N) && S[j] <= S[k]){
				k++;
				if(k == (1 << N)){
					printf("No\n");
					return 0;
				}
			}
//			printf("(j, k) = (%d, %d)\n", j, k);
/*			if(k == (1 << N)){
				printf("No\n");
				return 0;
			}
*/			swap(S[(1 << i) + j], S[k]);
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif


struct UnionFind {
  vector<ll> par, siz;
  UnionFind(ll n):par(n),siz(n,1) {
    for (ll i = 0; i < n; ++i) par[i] = i;
  }
  ll size() { return par.size(); };
  ll root(ll x) {
    assert(x < size());
    if (par[x] == x) return x;
    else return par[x] = root(par[x]);
  }
  void merge(ll x, ll y) {
    assert(x < size());
    assert(y < size());
    ll rx = root(x);
    ll ry = root(y);
    if (rx == ry) return;
    if (siz[rx] < siz[y]) std::swap(rx, ry);
    par[rx] = ry;
    siz[ry] += siz[rx];
  }
  bool same(ll x, ll y) { 
    assert(x < size());
    assert(y < size());
    return root(x) == root(y);
  }
  ll size(ll x) {
    assert(x < size());
    return siz[root(x)];
  }
};


int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n,m;
  cin >> n >> m;
  vector<int> p(n);
  rep(i,n) {
    cin >> p[i];
    p[i]--;
  }
  UnionFind tree(n);
  rep(i,m) {
    int x,y;
    cin >> x >> y;
    x--; y--;
    tree.merge(x,y);
  }

  vector<map<int,int> > maps(n);
  rep(i,n) {
    if (tree.size(i) > 1) {
      // debug(tree.root(i), maps[tree.root(i)].size());
      maps[tree.root(i)][i]++;  
    }
  }
  int ans = 0;
  rep(i,n) {
    if (tree.size(i) == 1) {
      if (i == p[i]) ans++;
    }
    else {
      if (maps[tree.root(i)].count(p[i]) > 0) ans++; //同じグループ内にp[i]と同じキーがあれば追加
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main()
{
  int n;
  cin >> n;
  int cnt = 0;
  while(n > 1){
    n = n/3 + (n%3 != 0);
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,y;
  cin >> n >> y;
  int res10000=-1,res5000=-1,res1000=-1;
  for(int i=0;i<=n;i++){
    for(int j=0;i+j<=n;j++){
      int k=n-i-j;
      int total=10000*i+5000*j+1000*k;
      if(total==y){
        res10000=i;
        res5000=j;
        res1000=k;
      }
    }
  }
  cout << res10000 << " " << res5000 << " " << res1000 << endl;
}


Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Balanced Path
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 80;
const int MAX_W = 80;
const int MAX_P = MAX_H + MAX_W + 1;
const int MAX_A = 80;
const int ORG = MAX_A * MAX_P;
const int MAX_D = ORG * 2 + 1;
const int INF = 1 << 30;

/* typedef */

/* global variables */

int as[MAX_H][MAX_W], bs[MAX_H][MAX_W], ds[MAX_H][MAX_W];
bool dp[MAX_H][MAX_W][MAX_D];

/* subroutines */

/* main */

int main() {
  int h, w;
  scanf("%d%d", &h, &w);

  for (int y = 0; y < h; y++)
    for (int x = 0; x <w; x++)
      scanf("%d", &as[y][x]);
  for (int y = 0; y < h; y++)
    for (int x = 0; x <w; x++) {
      scanf("%d", &bs[y][x]);
      ds[y][x] = abs(as[y][x] - bs[y][x]);
    }

  dp[0][0][ORG + ds[0][0]] = dp[0][0][ORG - ds[0][0]] = true;

  for (int y = 0; y < h; y++)
    for (int x = 0; x <w; x++)
      for (int d = 0; d < MAX_D; d++)
	if (dp[y][x][d]) {
	  if (y + 1 < h) {
	    int dy = ds[y + 1][x];
	    dp[y + 1][x][d + dy] = dp[y + 1][x][d - dy] = true;
	  }
	  if (x + 1 < w) {
	    int dx = ds[y][x + 1];
	    dp[y][x + 1][d + dx] = dp[y][x + 1][d - dx] = true;
	  }
	}

  int mind = INF;
  for (int d = 0; d < MAX_D; d++)
    if (dp[h - 1][w - 1][d]) {
      int ad = abs(d - ORG);
      if (mind > ad) mind = ad;
    }

  printf("%d\n", mind);
  return 0;
}


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

int main(){
    int n,k,x,y;
    cin >> n >> k >> x >> y;
    cout << x*min(k,n) + y*max(n-k,0) << endl;
    return 0;
}


Measured memory_bytes: 256