akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define N 1000009

vector<int> a, b;

int main()
{
    ll n , k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a.pb(x);
    }
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        b.pb(x);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    reverse(a.begin(), a.end());
    ll l = 0LL, r = 1000000000001LL, ans = 10000000000000000LL;
    while(l <= r)
    {
        ll md = (l + r) / 2;
        //cout << md << endl;
        ll cal1 = 0LL, cal2 = 0LL;
        for(int i = 0; i < a.size(); i++)
        {
            ll x = md / b[i];
            if(a[i] > x)
            {
                cal1 += (a[i] - x);
            }
        }
        if(cal1 <= k)
        {
            ans = min(ans, md);
            r = md - 1;
        }
        else l = md + 1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 2548
n=int(input())
s1=input()
s2=input()
mod=10**9+7
ans=3
for i in range(1,n):
  if i==1 or s1[i-1]==s2[i-1]:
    ans*=2
  elif not s1[i-1]==s1[i] and not s1[i]==s2[i]:
    ans*=3
print(ans%mod)

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

const int MAX = 500000;
int H, A[MAX+1];

void maxHeapify(int i) {
  int l = i * 2, r = i * 2 + 1, largest;
  if (l <= H && A[l] > A[i])
    largest = l;
  else
    largest = i;
  if (r <= H && A[r] > A[largest])
    largest = r;

  if (largest != i) {
    swap(A[i], A[largest]);
    maxHeapify(largest);
  }
}

void buildMaxHeap() {
  for (int i = H / 2; i >= 1; --i) {
    maxHeapify(i);
  }
}

int main() {
  cin >> H;
  for (int i = 1; i <= H; ++i) 
    cin >> A[i];
  buildMaxHeap();
  for (int i = 1; i <= H; ++i)
    cout << ' ' << A[i];
  cout << endl;
  return 0;
}


Measured memory_bytes: 5008
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()

cand1 = 0
for i, si in enumerate(s):
    if i % 2:
        if si == '0':
            cand1 += 1
            
    else:
        if si == '1':
            cand1 += 1
       
        
cand2 = 0
for i, si in enumerate(s):
    if i % 2:
        if si == '1':
            cand2 += 1
            
    else:
        if si == '0':
            cand2 += 1

print(min(cand1, cand2))

Measured memory_bytes: 3188
integer(16) N
integer(16),allocatable,dimension(:)::A,B
read*,N
allocate(A(N),B(N-1))
read*,B
do i=2,N-1
  A(i)=min(B(i),B(i-1))
end do
A(1)=B(1)
A(N)=B(N-1)
print"(i0)",sum(A)
end

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        int x = Integer.parseInt(sc.next());
        int ans = 0;
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                for (int k = 0; k <= c; k++) {
                    if (x == i * 500 + j * 100 + k * 50) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

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

using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    int h, w; cin >> h >> w;
    string arr[h];
    for (int i = 0; i < h; i++) cin >> arr[i];
    long long res[h][w];
    res[0][0] = 1LL;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (arr[i][j] == '#') {
                res[i][j] = 0;
                continue;
            }
            if (i == 0 && j == 0) continue;
            long long a = 0, b = 0;
            if (j >= 1) a = res[i][j - 1];
            if (i >= 1) b = res[i - 1][j];
            res[i][j] = (a + b) % MOD;
        }
    }
    cout << res[h - 1][w - 1];
}


Measured memory_bytes: 9088
/*
"Won't stop until I'm phenomenal."
- Phenomenal, Eminem
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define ff first
#define Shazam ios_base::sync_with_stdio(false);   cin.tie(NULL); cout.tie(NULL);
#define ss second
#define all(c) c.begin(),c.end()
#define endl "\n"
#define test() int t; cin>>t; while(t--)
#define fl(i,a,b) for(int i = a ; i <b ;i++)
#define get(a) fl(i,0,a.size())  cin>>a[i];
#define pra(a) fl(i,0,a.size()) cout<<a[i]<<" ";	cout<<endl;
#define pr(a,n) fl(i,0,n) cout<<a[i]<<" ";	cout<<endl;
const ll INF = 2e18;
const int inf = 2e9;
const int mod1 = 1e9 + 7;



int main(){
    Shazam;
    int n, m; cin>>n>>m;
    priority_queue<ll>  q;
    vector<vector<ll>> day(m+1);
    for(int i = 0 ; i < n; i++){
        ll a,b; cin>>a>>b;
        if(m-a+1>0)
            day[m-a+1].push_back(b);
    }
    ll ans = 0;
    for(int i = m ; i >0; i--){
        for(int p : day[i]) q.push(p);
        if(q.size()){
            ans+=q.top();
            q.pop();
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8360
import java.util.Scanner;

public class Main {
	private static Scanner sc=new Scanner(System.in);
	private static String s=sc.nextLine();
	private static String p=sc.nextLine();
	private static String str=s+s;
	private static boolean possible=false;
	public static void main(String[] args){
		for(int i=0;i<s.length();i++){
			String word=str.substring(i,i+p.length());
			if(word.equals(p)){
				possible=true;
			}
		}
		if(possible) System.out.println("Yes");
		else System.out.println("No");
	}
}

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

int gcd(int x,int y){
  return (y ? gcd(y,x%y) : x);
}

int main(){
  int x,y;
  cin >> x >> y;
  int ans=gcd(x,y);
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    int n,r,i;
    cin >> n >> r;
    if(n >= 10){
        cout << r << endl;
    }
    else{
        i = (10-n)*100 + r;
        cout << i << endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

//------------------------------------------------------

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

    int n;
    cin >> n;
    
    auto check = [](int x, int y, int z) {
        return x * x + y * y == z*z;
    };

    rep(i, n) {
        int a, b, c;
        cin >> a >> b >> c;
        YES(check(a, b, c) || check(b, c, a) || check(c, a, b));
    }
    return 0;
}




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

const int N = 3007;

ll mp[N][N], n, m, k, dp[N][N][5];

bool judge(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > m) {
        return true;
    }
    return false;
}

ll dfs(int x, int y, int c) {
    if (judge(x, y)) return 0;
    //cout << x << " " << y << endl;
    ll ans = 0;
    if (dp[x][y][c] != -1) return dp[x][y][c];
    if (mp[x][y]) {
      
        if (c < 3) {
            ans = max(ans, dfs(x + 1, y, 0) + mp[x][y]);
        }
        ans = max(ans, dfs(x + 1, y, 0));
    
    
        if (c < 3) {
            ans = max(ans, dfs(x, y + 1, c + 1) + mp[x][y]);
        }
        ans = max(ans, dfs(x, y + 1, c));
        
    } else {
     
        ans = max(ans, dfs(x + 1, y, c));
    
        ans = max(ans, dfs(x, y + 1, c));
        
    }
    return dp[x][y][c] = ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        mp[x][y] = w;
    }
    memset(dp, -1, sizeof(dp));
    ll ans = dfs(1, 1, 0);

    printf("%lld\n", ans);

}

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

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll n,a,b;

ll binpow(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}

ll inverse(ll x) {
	return binpow(x, mod - 2, mod);
}

int factmod(int n, int p) {
    int res = 1;
    while (n > 1) {
        res = (res * ((n/p) % 2 ?  p-1 : 1)) % p;
        for (int i = 2; i <= n%p; ++i)
            res = (res * i) % p;
        n /= p;
    }
    return res % p;
}

ll cc(ll a, ll b) {
	if(b>a) return 0;
    if(a==b) return 1;
    ll ans1=1,ans2=1;
    for(ll i=1;i<=b;i++){
        ans1=ans1*(a-i+1)%mod;
        ans2=ans2*i%mod;
    }
    return ans1*binpow(ans2,mod-2,mod)%mod;
}

int main()
{
	cin>>n>>a>>b;
	ll ans = (binpow(2,n,mod)-1-cc(n,a)%mod-cc(n,b)%mod) % mod;
	cout << (ans + mod) % mod;
	return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn.readLine
import scala.annotation.tailrec
object Main {
    def main(args: Array[String]) {
        val i = readLine.split(" ").map(_.toInt)
        println(gcd(i(0), i(1)))
    }
    @tailrec
    def gcd(a: Int, b: Int): Int = (a, b) match {
        case (x, y) if x % y == 0 => y
        case (x, y) => gcd(y, x % y)
    }
}


Measured memory_bytes: 43836
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ALL(a) (a).begin(), (a).end()
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
const ll mod = 1e9 + 7;

int main()
{
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    if (k % 2 == 0)
        cout << a - b << endl;
    else
        cout << b - a << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define MAX 200010
using namespace std;
int nums[MAX];
int main(){
	int k,n;
	scanf("%d %d",&k,&n);
	for(int i=0;i<n;i++){
		scanf("%d",&nums[i]);
	}
	int findMAX= nums[0]+k-nums[n-1];
	int start,end;
	for(int i=0;i<n-1;i++){
		if(nums[i+1]-nums[i] >findMAX){
			findMAX=nums[i+1]-nums[i];
			start=i;
			end=i+1;
		}
	}
	int res=k-findMAX;
	printf("%d",res);
	return 0;
}

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

int main()
{
    vector<int> height;
    int buff;
    for(int i=0; i< 10; i++)
    {
        std::cin >> buff;
        height.push_back(buff);
    }
    sort(height.begin(), height.end());
    cout << height[height.size() - 1] << endl;
    cout << height[height.size() - 2] << endl;
    cout << height[height.size() - 3] << endl;
    
    return 0;
}

Measured memory_bytes: 1216
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b // gcd(a,b)

a,b,c,d = map(int,input().split())

ans = b-a+1
ans = ans-(b//c-a//c)
ans = ans-(b//d-a//d)

temp = int(lcm(c,d))

ans = ans+(b//temp-a//temp)


if a%c == 0:
    ans -= 1
    
if a%d == 0:
    ans -= 1
    
if a%(c*d) == 0:
    ans += 1

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
string s;
int solve(string s) {
    if (s.size() == 0) return 0;
    string t;
    for (int i = 1; i < s.size(); i++) t += s[i];
    if (s[0] == '0') return (solve(t));
    else return max((int)(s[0] - '0') + solve(t), (int)(s[0] - '0' - 1) + 9 * ((int)s.size() - 1));
}
int main() {
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin >> s;
    cout << solve(s);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A[] = new int[N+1];
        int ans = 0;
        for (int i = 0; i < N ; i++) {
            A[i] = sc.nextInt();
            if (i==0){
                ans += Math.abs(A[i]);
            }else{
                ans += Math.abs(A[i - 1] - A[i]);
            }
        }
        ans += Math.abs(A[N-1]);
        for (int i = 0; i < N; i++) {
            int tmp = ans;
            if (i==0){
                tmp -= Math.abs(A[i]) + Math.abs(A[i+1]-A[i]) - Math.abs(A[i+1]);
            }else if (i == N-1){
                tmp -= Math.abs(A[i] -A[i-1]) + Math.abs(A[i]) - Math.abs(A[i-1]);
            }else{
                tmp -= Math.abs(A[i] -A[i-1]) + Math.abs(A[i+1]-A[i]) - Math.abs(A[i+1]- A[i-1]);
            }
            System.out.println(tmp);

        }
    }
}

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

def dfs(s):
    stack = [(s, -1, 1)]
    while(len(stack)):
        v, p, c = stack[-1]
        stack.pop()
        color[v] = c
        for e in graph[v]:
            if e[0] == p: continue
            stack.append((e[0], v, abs(c - e[1] % 2)))


n = int(input())
color = [-1] * n
graph = [[] for _ in range(n)]

for _ in range(n-1):
    u, v, w = [int(x) for x in input().split()]
    u, v = u-1, v-1
    graph[u].append((v, w))
    graph[v].append((u, w))

dfs(0)
for c in color: print(c)

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

signed main(){
	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> a(m);
	for(int i = 0; i < m; i++){
		scanf("%d", &a[i]);
	}
	sort(a.begin(), a.end(), greater<int>());
	vector<int> data = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
	vector<ll> dp(n + 1, -100000);
	dp[0] = 0;
	for(int i = 0; i < m; i++){
		for(int j = 0; j <= n; j++){
			int num = data[a[i]];
			if(j + num <= n) dp[j + num] = max(dp[j + num], dp[j] + 1);
		}
	}
	int keta = dp[n];
	string ans;
	for(int i = 0; i < keta; i++){
		for(int j = 0; j < m; j++){
			int num = data[a[j]];
			if(n - num >= 0 && dp[n - num] == dp[n] - 1){
				ans.push_back(a[j] + '0');
				n -= num;
				break;
			}
		}
	}
	cout << ans << endl;
}

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


int dp[100100][3];

int main() {
  int n; cin >> n;
  vector<int> a(n), b(n), c(n);
  rep(i,n) cin >> a[i] >> b[i] >> c[i];
  memset(dp, 0, sizeof(dp));
  rep(i,n) {
    rep(j,3) {
      if(j==0) dp[i+1][0] = max(dp[i][1],dp[i][2])+a[i];
      if(j==1) dp[i+1][1] = max(dp[i][0],dp[i][2])+b[i];
      if(j==2) dp[i+1][2] = max(dp[i][0],dp[i][1])+c[i];
    }
  }
  cout << max(dp[n][0],max(dp[n][1],dp[n][2])) << endl;
  return 0;
}


Measured memory_bytes: 5576
def get_result(A):
    res = 1
    total = 3 ** len(A)
    for i, ai in enumerate(A):
        res *= 2 if ai % 2 == 0 else 1
    return total - res
n = input()
A = [int(ai) for ai in input().split()]
print(get_result(A))

Measured memory_bytes: 2940
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#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 <ctime>
#include <string>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200003;
int main(){
  int n;
  cin>>n;
  ll a[maxn];
  a[0]=0LL;
  for(int i=0;i<n;i++){
    cin>>a[i+1];
    a[i+1]+=a[i];
  }
  ll res=0LL,res2=0LL;
  ll sum1=0LL,sum2=0LL;
  for(int i=1;i<n+1;i++){
    if( (i)%2LL==0LL and a[i]+sum1<=0LL){
      res+=abs(sum1+a[i])+1;
      sum1+=(abs(a[i]+sum1)+1);
    }
    else if( (i)%2LL==1LL and a[i]+sum1>=0LL){
      res+=abs(sum1+a[i])+1;
      sum1-=(abs(a[i]+sum1)+1);
    } 
  }
  for(int i=1;i<n+1;i++){
    if( (i)%2LL==1LL and a[i]+sum2<=0LL){
      res2+=abs(sum2+a[i])+1;
      sum2+=(abs(a[i]+sum2)+1);
    }
    else if( (i)%2LL==0LL and a[i]+sum2>=0LL) {
      res2+=abs(sum2+a[i])+1;
      sum2-=(abs(a[i]+sum2)+1);
    }
  }
  cout<<min(res,res2)<<endl;

  return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long num, i, n, max, min, sum;
        num = sc.nextInt();
        max = Integer.MIN_VALUE; min = Integer.MAX_VALUE; sum = 0;
        for (i = 0; i < num; i++) {
            n = sc.nextInt();
            if (n > max) max = n;
            if (n < min) min = n;
            sum += n;
        }
        System.out.println(min + " " + max + " " + sum);
    }
}



Measured memory_bytes: 42392
#include<stdio.h>

#define MAX 100001

int parent(int);
int left(int);
int right(int);


int main(){

  int num,i,a[MAX];


  scanf("%d",&num);
  for(i = 1; i <= num; i++){
    scanf("%d",&a[i]);
  }


  for(i = 1; i <= num; i++){
    printf("node %d: key = %d, ",i,a[i]);
    if(parent(i) >= 1)printf("parent key = %d, ",a[parent(i)]);
    if(left(i) <= num)printf("left key = %d, ",a[left(i)]);
    if(right(i) <= num)printf("right key = %d, ",a[right(i)]);
    printf("\n");
  }


  return 0;
}

int parent(int i){
  return i/2;
}

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i + 1;
}

Measured memory_bytes: 608
#include<stdio.h>
int main()
{
  int N,K;
  scanf("%d",&N);
  if(N % 1000 == 0){
    	printf("0\n");
    	return 0 ;
  }
  printf("%d\n",(N / 1000 + 1) * 1000 - N);
  return 0;
}

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

cum = [0] * (n + 1)

for i in range(1, n + 1):
    cum[i] = cum[i - 1] + a[i - 1]

ans = 1

for i in range(n, 0, -1):
    if cum[i - 1] * 3 >= cum[i]:
        ans += 1
    else:
        break

print(ans)


Measured memory_bytes: 14320
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long a[5];
  for(int i=0;i<5;i++)
    cin>>a[i];
  for(int i=0;i<5;i++)
    if(a[i]==0)
    {
      cout<<i+1;
      break;
    }
  
}

Measured memory_bytes: 3540
import Control.Applicative
import Control.Monad
import Data.List
import Data.Char
strToInt s = (read :: String -> Int) s

main :: IO ()
main = do
    -- スペース区切り整数の入力
    [_, a, b] <- map strToInt . words <$> getLine
    -- 出力
    putStrLn $ if odd (a - b) then "Borys" else "Alice"


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

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;

#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define rrep(i,a) for(ll i=a-1;i>=0;i--)
#define MOD 1000000007

//debug
#define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl;

int main(){
  ll N;
  cin >> N;
  ll X[N];
  rep(i, N) cin >> X[i];

  double mean = 0;
  rep(i, N) mean += X[i];
  mean /= N;

  ll c1 = mean;
  ll c2 = c1 + 1;
  ll P = mean - c1 < c2 - mean ? c1 : c2;
  ll ans = 0;
  rep(i, N) ans += (X[i] - P) * (X[i] - P);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#二つの長方形
#縦A、横B A*B
#縦C、横D C*D

a,b,c,d = map(int,input().split())

if a*b == c*d:
    print(a*b)
if a*b < c*d:
    print(c*d)
if a*b > c*d:
    print(a*b)







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

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int r;
    cin>>r;
    if(r<1200)  cout<<"ABC"<<endl;
    else if(r<2800) cout<<"ARC"<<endl;
    else cout<<"AGC"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
const int maxlongint=2147483647;
const int mo=1e9+7; 
const int N=100005;
using namespace std;
int n,m,ans,deep[N],a[N];
int tot,nt[N*2],lt[N*2],to[N*2];
bool bz[N];
void link(int x,int y)
{
    nt[++tot]=lt[x];
    lt[x]=tot;
    to[tot]=y;
}
int dg(int x,int fa)
{
    deep[x]=deep[fa]+1;
    int mx=deep[x];
    for(int i=lt[x];i;i=nt[i]) mx=max(dg(to[i],x),mx);
    if(x==1) return 0;
    if(fa!=1 && mx-deep[x]+1==m) ans++,mx=0;
    return mx;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i!=1) link(a[i],i);
    }
    if(a[1]!=1) ans++;
    deep[0]=-1;
    dg(1,0);
    printf("%d",ans);
}

Measured memory_bytes: 6912
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	N := getInt()
	d1 := make([]int, N)
	d2 := make([]int, N)
	for i := 0; i < N; i++ {
		d1[i], d2[i] = getInt(), getInt()
	}
	cnt := 0
	for i := 0; i < N; i++ {
		if d1[i] == d2[i] {
			cnt++
		} else {
			cnt = 0
		}
		if cnt == 3 {
			out("Yes")
			return
		}
	}
	out("No")

}


Measured memory_bytes: 1776
N, K = map(int, input().split())
S = input()
 
if S[K-1] == 'A': rep = 'a'
elif S[K-1] == 'B': rep = 'b'
else: rep = 'c'

# (K-1)文字目まで + K文字目 + K+1文字目から
print(S[:K-1] + rep + S[K:])

Measured memory_bytes: 8980
#include <stdio.h>
#include <stdlib.h>

int asc(const void *a, const void *b){
  return *(int *)a - *(int *)b;
}

int
main(int argc, char *argv[])
{
  int n, x[51], y[51];
  scanf("%d", &n);
  int k = 0; int ymin = 1000000000;
  for(int i = 0; i < n; i++){
    scanf("%d %d", &x[i], &y[i]);
  }

  int p, q; int used[50]; int z; int min = 100; int arr[50]; int cnt;

  if(n == 1) min = 1;

  for(int i = 0; i < n - 1; i++){
    for(int j = i + 1; j < n; j++){
      for(int r = 0; r < n; r++){
	used[r] = 0;
      }
      z = 0;
      p = x[i] - x[j];
      q = y[i] - y[j];
      if(p != 0){
	for(int k = 0; k < n; k++){
	  if(used[k] == 0){
	    cnt = 0;
	    for(int l = 0; l < n; l++){
	      if(used[l] == 0 && (x[k] - x[l]) % p == 0 && ((x[k] - x[l]) / p) * q == y[k] - y[l]){
		used[l] = 1;
		arr[cnt++] = (x[k] - x[l])/p;
	      }
	    }
	   
	    if(cnt == 1) z++;
	    else{
	      qsort(arr, cnt, sizeof(int), asc);
	     
	      z++;
	      for(int r = 1; r < cnt; r++){
	
		if(arr[r - 1] + 1 != arr[r]) z++;
	      }
	      
	    }
	  }
	}
      }
      else{
	for(int k = 0; k < n; k++){
	  if(used[k] == 0){
	    cnt = 0;
	    for(int l = 0; l < n; l++){
	      if(used[l] == 0 && (y[k] - y[l]) % q == 0 && ((y[k] - y[l]) / q) * p == x[k] - x[l]){
		used[l] = 1;
		arr[cnt++] = (y[k] - y[l])/q;
	      }
	    }
	    if(cnt == 1) z++;
	    else{
	      qsort(arr, cnt, sizeof(int), asc);
	     
	      z++;
	      for(int r = 1; r < cnt; r++){
		
		if(arr[r - 1] + 1 != arr[r]) z++;
	      }
	      
	    }
	  }
	}
      }
      if(min > z) min = z;
    }
  }

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

  return 0;
}
	    
	  


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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
int main()
{
    LL n,m;
    cin>>n>>m;
    LL ans=(n*(n-1)/2)+(m*(m-1)/2);
    cout<<ans;

}


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

int main() {
    int n; cin >> n;
    map<int, int> counts;
    for (int i = 0; i < n; i++) {
        int a_i; cin >> a_i;
        if (counts.count(a_i)) counts[a_i]++;
        else counts[a_i] = 1;
    }

    // if value equals to key or 0, then OK.
    int ans = 0;
    for (auto p : counts) {
        if (p.second > p.first) ans += p.second - p.first;
        else if (p.second < p.first) ans += p.second;
    }    

    cout << ans << endl;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define maxn 10
#define INF 0x3f3f3f3f
#define mod 1000000007
#define rep(i, a, n) for (int i=(a); i<(n); i++)
#define per(i, a, n) for (int i=(a); i>(n); i--)
typedef long long ll;
using namespace std;

char s[maxn];

void slove()
{
	
	cin >> s;
	if (s[1] == 'B') {
		cout << "ARC";
	}
	else  {
		cout << "ABC";
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef DEBUG
	freopen("C:\\Users\\Fish_Brother\\Desktop\\in", "r", stdin);
	//freopen("C:\\Users\\Fish_Brother\\Desktop\\out", "w", stdout);
#endif
	slove();

	return 0;
}

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

int main(){
char s[4];
scanf("%s",s);
    if((s[0]==s[1]) && (s[2]==s[3]) && (s[0]!=s[2])) printf("Yes\n");
    else if((s[0]==s[2]) && (s[1]==s[3]) && (s[0]!=s[1])) printf("Yes\n");
    else if((s[0]==s[3]) && (s[1]==s[2]) && (s[0]!=s[1])) printf("Yes\n");
    else printf("No\n");
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
	int h, w;
	int a[500][500];
	int count = 0;
	int ac[250000][4];
	cin >> h >> w;
	for(int i = 0;i < h;i++){
		for(int j = 0;j < w;j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0;i < h - 1;i++){
		for(int j = 0;j < w - 1;j++){
			if(a[i][j] % 2){
				a[i][j]--;
				a[i][j + 1]++;
				ac[count][0] = i + 1;
				ac[count][1] = j + 1;
				ac[count][2] = i + 1;
				ac[count][3] = j + 2;
				count++;
			}
		}
		if(a[i][w - 1] % 2){
			a[i][w - 1]--;
			a[i + 1][w - 1]++;
			ac[count][0] = i + 1;
			ac[count][1] = w;
			ac[count][2] = i + 2;
			ac[count][3] = w;
			count++;
		}
	}
	for(int j = 0;j < w - 1;j++){
		if(a[h - 1][j] % 2){
			a[h - 1][j]--;
			a[h - 1][j + 1]++;
			ac[count][0] = h;
			ac[count][1] = j + 1;
			ac[count][2] = h;
			ac[count][3] = j + 2;
			count++;
		}
	}
	cout << count << endl;
	for(int i = 0;i < count;i++){
		cout << ac[i][0] << " " << ac[i][1] << " " << ac[i][2] << " " << ac[i][3] << endl;
	}
}

Measured memory_bytes: 6272
from collections import defaultdict

n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
p = [defaultdict(int), defaultdict(int), defaultdict(int)]
for i in range(n):
    ci = list(map(int, input().split()))
    for j, cj in enumerate(ci):
        k = (i + j + 2) % 3
        p[k][cj] += 1
ans = []
for i in range(1, c + 1):
    x = 0
    for ci, ti in p[0].items():
        x += D[ci - 1][i - 1] * ti

    for j in range(1, c + 1):
        if j == i:
            continue
        y = 0
        for cj, tj in p[1].items():
            y += D[cj - 1][j - 1] * tj

        for k in range(1, c + 1):
            if k in [i, j]:
                continue
            z = 0
            for ck, tk in p[2].items():
                z += D[ck - 1][k - 1] * tk
            ans.append(x + y + z)

print(min(ans))


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

ope = sum(b) - sum(a)
var = 0

for i in range(n):
    if a[i] >= b[i]:
        var += a[i] - b[i]
    else:
        var += (b[i] - a[i])%2
if (ope-var)%2 == 0 and ope >= var:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 4596
def solve(M,K):
    if K>=2**M:
        return False
    if M==0:
        if K==0:
            return ["0","0"]
        else:
            return False
    elif M==1:
        if K==1:
            return False
        else:
            return ["0","0","1","1"]
    else:
        b=list(range(2**M))
        b.remove(K)
        import copy
        c=copy.deepcopy(b)
        c.reverse()
        return b+[K]+c+[K]

if __name__ == '__main__':
    M,K=list(map(int,input().split()))
    ans=solve(M,K)
    if ans is False:
        print(-1)
    else:
        for i in range(len(ans)):
            if i!=len(ans):
                print("{} ".format(ans[i]),end="")
            else:
                print(ans[i])

Measured memory_bytes: 85452
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
// clang-format on

const ll INF = LLONG_MAX / 3;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    const int L = 2 + n % 2;
    vector<vector<ll>> dp(n, vector<ll>(L, -INF));
    rep(i, L) dp[i][L - 1 - i] = a[i];
    rep(i, n - 1) rep(j, L) {
        if (dp[i][j] == -INF) continue;
        if (i + 2 < n) dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i + 2]);
        if (j > 0) dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j]);
    }
    cout << dp[n - 1][0] << "\n";
    return 0;
}


Measured memory_bytes: 15648
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){a %= mod;ll ans = 1;while(b){if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{bool operator()(const pii & a, const pii & b){return a.second > b.second;}};
int lb(int x){return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 2147483648;
const int maxn = 2e3 + 5;

int main()
{
    int n;
    scanf("%d",&n);
    int ans =0 ;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d",&x);
        if(i % 2 &&x % 2)
            ans ++ ;
    }
    cout<<ans<<endl;
}


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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int64_t>h(n);
	for (int i = 0; i < n; i++)cin >> h.at(i);
	sort(h.begin(), h.end());
	int64_t ans = 100000000000;
	for (int i = 0; i < n - k + 1; i++) {
		ans = min(ans, (h.at(i + k - 1) - h.at(i)));
	}
	cout << ans << endl;
}

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

#define OnlineJudge1

#define loop(a,n) for(int i = a;i<n;i++)
#define NumofDigits(n) ((int)log10(n)+1)
#define CountofNumber(array,n,x)  (upper_bound(array, array+n, x)-lower_bound(array, array+n, x))
#define readline(s) getline(cin,s)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define EPS 1e-7
#define modulo ll (1e9 + 7)


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

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
#ifdef OnlineJudge
    freopen("in.in","r",stdin);
    freopen("out.txt","w",stdout);
#endif
}

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

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

//    int powres[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912};

ll power(ll b, ll p){
    if(p == 0)return 1;
    ll res = power(b,p/2);
    res *= res;
    if(p & 1)res *= b;
    return res;
}

set<ll> factors;
set<ll> divisors;

void divide(ll n){
    for(ll i = 2;i * i <= n;i++){
        if(n % i == 0){
            divisors.insert(i);
            divisors.insert(n/i);

        }
    }
}

void factorize(ll n){
        for(ll i = 2;i * i <= n;i++){
        if(n % i == 0){
            factors.insert(i);
            while(n % i == 0)n /= i;
        }
    }
    if(n != 1)factors.insert(n);
}

int Max = 1e7 + 5;
int prime[(int)1e7+7];

void sieve(){
    prime[0] = prime[1] = 1;
    for(ll i = 1;i<=Max;i++){
        if(prime[i])
            continue;
        else{
            for(ll j = i*i;j<=Max;j+=i)
                prime[j] = 1;
        }
    }
}

int n,maxW;
ll dp[100][(int)1e5+5];
int value[100], weight[100];

ll solve(int i, int w){
    if(w > maxW)
        return -1e9;

    if(i == n)
        return 0;

    ll &res = dp[i][w];

    if(res != -1)
        return res;

    res = value[i] + solve(i + 1, weight[i] + w);

    res = max(res, solve(i + 1, w));

    return res;
}
int main(){
    init();

    cin >> n >> maxW;

    memset(dp, -1, sizeof dp);

    for(int i = 0;i < n;i++){
        cin >> weight[i] >> value[i];
    }

    cout << solve(0,0);

}


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

int number( int c[8], int parm )
{
        int sum = 0;
        for ( int i = 0 ; i < 8 ; i++ ) {
                // printf( "%d\n", c[(i+parm)%8] );
                sum += c[(i+parm)%8] * ( int ) pow( 10.0, 7.0 - (double) i );
        }
        return sum;
}

int main()
{
        int p[8];
        int c[8] = { 4, 1, 4, 1, 2, 1, 2, 1 };
        int rest[8];
        int cnt, minval, restnum, i, minnum;

        while ( scanf( "%d %d %d %d %d %d %d %d",
                                &p[0], &p[1], &p[2], &p[3], &p[4], &p[5], &p[6], &p[7] ) != EOF ) {

                cnt = 0;
                minnum = 70000;
                minval = 0;

                /* @hF,0LCV$r$:$i$7$J$,$iBT$A?M?t$,:G>.$N>l9g$r7W;;$9$k*/
                while ( cnt < 8 ) {
                        restnum = 0;

                        /* */
                        for ( i = 0 ; i < 8 ; i++ ) {
                                rest[i] = p[i] - c[(i+cnt)%8];
                                if ( rest[i] < 0 ) {
                                        rest[i] = 0;
                                }
                                restnum += rest[i];
                        }

                        if ( restnum < minnum ) {
                                minnum = restnum;
                                minval = cnt;
                        } else if ( restnum == minnum ) {
                                // printf( "%7d, %7d\n", number( c, minval ), number( c, cnt ) );
                                if ( number( c, minval ) > number( c, cnt ) ) {
                                        minval = cnt;
                                }
                        }
                        cnt++;
                }

                for ( i = 0 ; i < 8 ; i++ ) {
                        if ( i == 7 ) {
                                printf( "%d\n", c[(i+minval)%8] );
                        } else {
                                printf( "%d ", c[(i+minval)%8] );
                        }
                }
        }

        return 0;
}



Measured memory_bytes: 2100
use proconio::{input, fastout};
use std::cmp::min;

#[fastout]
fn main() {
    input! {
        s: String,
        t: String,
    };

    let mut ans = t.len();
    for i in 0..=s.len()-t.len() {
        ans = min(ans, t.len()-m(&s[i..i+t.len()], &t));
    }
    println!("{}", ans);
}

fn m(s: &str, t: &str) -> usize {
    let mut ans = 0;
    for (i, j) in s.to_string().chars().zip(t.to_string().chars()) {
        if i == j {
            ans += 1;
        }
    }
    ans
}


Measured memory_bytes: 2180
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define double long double
using namespace std;
const int mod = 998244353, N = 210000;

int n;
double a[N], b[N], u[N], v[N];
struct point {
	double x, y;
	point(double x = 0, double y = 0) : x(x), y(y) {}
	inline double cross(const point &a) const {
		return x * a.y - y * a.x;
	}
	inline point operator - (const point &a) const {
		return point(x - a.x, y - a.y);
	}
};
vector<point> stck;

inline int addMod(int a, int b) {
	return (a += b) >= mod ? a - mod : a;
}

inline ll quickpow(ll base, ll pw) {
	ll ret = 1;
	while (pw) {
		if (pw & 1) ret = ret * base % mod;
		base = base * base % mod, pw >>= 1;
	}
	return ret;
}

template <class T>
inline void read(T &x) {
	x = 0;
	char ch = getchar(), w = 0;
	while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x = w ? -x : x;
	return;
}

int main() {
	int maxP = 0;
	read(n);
	for (R int i = 1; i <= n; ++i) {
//		read(a[i]);
		cin >> a[i];
		if (a[i] > a[maxP]) maxP = i;
	}
	for (R int i = 1; i <= n; ++i)
		//read(b[i]);
		cin >> b[i];
	reverse(a + 1, a + 1 + n);
	reverse(a + 1, a + 1 + n - maxP);
	reverse(a + 1 + n - maxP, a + 1 + n);
	reverse(b + 1, b + 1 + n);
	reverse(b + 1, b + 1 + n - maxP);
	reverse(b + 1 + n - maxP, b + 1 + n);
	a[0] = a[n], b[0] = b[n];
	for (R int i = 1; i < n; ++i) {
		u[i] = 1 / (2 - u[i - 1]);
		v[i] = (v[i - 1] - 2 * b[i]) * u[i];
	}
	for (R int i = n - 1; i; --i)
		v[i] += u[i] * v[i + 1];
	stck.emplace_back(0, a[0]);
	for (R int i = 1; i <= n; ++i) {
		point now(i, a[i] - v[i]);
		while (stck.size() >= 2) {
			point &a = stck[stck.size() - 2], &b = stck.back();
			if ((b - a).cross(now - a) < 0) break;
			stck.pop_back();
		}
		stck.push_back(now);
	}
	double sum = 0;
	for (auto it = stck.begin(); next(it) != stck.end(); ++it) {
		int l = next(it)->x - it->x;
		for (R int i = it->x; i < next(it)->x; ++i)
			sum += (it->y * (next(it)->x - i) + next(it)->y * (i - it->x)) / l + v[i];
	}
//	printf("%.15lf\n", sum / n);
	printf("%.15Lf\n", sum / n);
	return 0;
}

Measured memory_bytes: 24004
#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <vector>
#include <map>
#include <set>
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;

int main() {
	string fronts, backs;
	bool isReverse = false;

	string s;
	cin >> s;
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			isReverse = !isReverse;
		} else if (t == 2) {
			int f;
			char c;
			cin >> f >> c;
			if (f == 1) {
				(isReverse ? backs : fronts).push_back(c);
			} else if (f == 2) {
				(isReverse ? fronts : backs).push_back(c);
			}
		}
	}

	if (isReverse) {
		reverse(s.begin(), s.end());
		reverse(backs.begin(), backs.end());
		cout << (backs + s + fronts) << endl;
	} else {
		reverse(fronts.begin(), fronts.end());
		cout << (fronts + s + backs) << endl;
	}

	return 0;
}


Measured memory_bytes: 1348
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
using ll = long long;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> sum(n+1);
    for (int i=1;i<n+1;i++){
        if(s.at(i-1)=='E')
            sum.at(i) = sum.at(i-1)+1;
        else
            sum.at(i) = sum.at(i-1);
    }
    int ans = INF;
    // (0)W(0)E(1)E(2)W(2)W(2)
    for (int i=0;i<n+1;i++){
        //左のWの数
        // cout << i-sum.at(i) << endl;
        // cout << sum.at(n)-sum.at(i);
        ans = min (ans,i+sum.at(n)-2*sum.at(i));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1796
#include <iostream>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
ll n,a,b;
main(){
	cin>>n>>a>>b;
	if(a>b)swap(a,b);
	if((a%2)==(b%2))cout<<((b-a)/2)<<endl;
	else cout<<min(a+(b-a-1)/2,n-b+1+(b-a-1)/2)<<endl;
	return 0;
}

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

// iterator
#define REP(i,from, to) for(lli i=from;i<to;i++)
#define REPE(i,from, to) for(lli i=from;i<=to;i++)
#define REP_R(i,from, to) for(lli i=from;i>to;i--)
#define REPE_R(i,from, to) for(lli i=from;i>=to;i--)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;
typedef vector<lli> vlli;

int main() {
    lli k;
    cin1(k);


    lli n = 50;
    cout << n << endl;
    lli p = k / n;
    lli q = k % n;
    vlli ans;
    // 初期値セット
    REP(i,0,n) {
        ans.push_back(i);
    }
    // n 回の処理ですべてに1がたされるので、それをやる
    REP(i,0,n) {
        ans[i] +=p;
    }
    // 端数処理
    REP(i,0,q) {
        REP(j,0,n) {
            if (j == i)
                ans[j] += n;
            else
                ans[j] -= 1;
        }
    }
    REP(i,0,n) {
    cout << ans[i] << ( i == n-1 ? "" : " ");
    }
    cout << endl;
}


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

using namespace std;

#define int long long
#define ll long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl


signed main(){

	int ai, ao, at, aj, al, as, az;
	cin >> ai >> ao >> at >> aj >> al >> as >> az;
	int ans = 0;
	ans += ao;
	// JJかLLかJILかII

	//JILが1個のとき
	if (ai > 0 && aj > 0 && al > 0){
		ans += 3;
		ans += ((ai - 1) / 2) * 2
			+ ((aj - 1) / 2) * 2
			+ ((al - 1) / 2) * 2;
	}

	// JILが0個のとき
	int ans2 = ao;
	// II
	ans2 += (ai / 2) * 2; ai %= 2;;
	// JJ
	ans2 += (aj / 2) * 2; aj %= 2;
	// LL
	ans2 += (al / 2) * 2; al %= 2;

	cout << max(ans, ans2) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, A[MX], ans;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>A[i];
    int l=1;
    while(l<=n){
        int pos=l;
        while(pos+1<=n && A[l]==A[pos+1]) pos++;
        if(pos==n){
            ans++;
            break;
        }
        if(A[pos]<A[pos+1]){
            while(pos+1<=n && A[pos]<=A[pos+1]) pos++;
            l=pos+1;
            ans++;
            continue;
        }
        if(A[pos]>A[pos+1]){
            while(pos+1<=n && A[pos]>=A[pos+1]) pos++;
            l=pos+1;
            ans++;
            continue;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(){
int n,i,a=0,p[20]={};
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&p[i]);
for(i=1;i<n-1;i++)if((p[i-1]<p[i]&&p[i]<p[i+1])||(p[i+1]<p[i]&&p[i]<p[i-1]))a++;
printf("%d\n",a);
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
using namespace std;

int main() {
	int A, B, K;
	cin >> A >> B >> K;
	vector<int> vec;

	for (int i = min(A, B); 0 < i; i--) {
		if (A % i == 0 && B % i == 0) {
			vec.push_back(i);
		}
		else {
			continue;
		}
	}
	cout << vec[K - 1] << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
void makeFib();
int F[10000000],n;

int main(){
  int i;
  scanf("%d",&n);
  makeFib();
  printf("%d\n",F[n]);
  return 0;
}

void makeFib(){
  int i;
  F[0] = 1;
  F[1] = 1;
  for(i=2;i<=n;i++) F[i] = F[i-2] + F[i-1];
}



Measured memory_bytes: 2104
n, m, k = (int(x) for x in input().split())

a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

K = k
ans = 0

i = 0
while i<n and K-a[i]>=0:
    K -= a[i]
    i += 1
    # if i==n:
    #     break
ans = i
# print(ans)
    
# K = k
l = 0
# if i==0:
#     while l<m and K-b[l]>=0:
#         K -= b[l]
#         l += 1
#     ans = max(ans, l)
# else:
for j in range(i, -1, -1):
    while l<m and K-b[l]>=0:
        K -= b[l]
        l += 1
    ans = max(ans, j+l)
    if j != 0:
        K += a[j-1]

# print(ans)
# print(b[l])
# print(K)
while l<m and K-b[l]>=0:
    K -= b[l]
    l += 1
    ans = max(ans, l)

print(ans)

Measured memory_bytes: 112032