akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

int main(){
	ll n;
	cin>>n;
	ll mod=1e9+7;
	ll a=1,b=1,c=1;
	for(int i=1;i<=n;i++){
		a*=10;
		a%=mod;
		b*=9;
		b%=mod;
		c*=8;
		c%=mod;
	}
	a+=c;
	a%=mod;
	a+=2*mod-2*b;
	a%=mod;
	cout<<a;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <utility>
#include <cmath>
 
using namespace std;
 
int main(void){
    int N;
    cin >> N;
 
    for(int i=0;i<N;i++){
        pair<double,double> p[2];
        double d,r[2];
 
        for(int j=0;j<2;j++){
            float x,y;
            cin >> x >> y >> r[j];
            p[j]=make_pair(x,y);
        }
        d=sqrt(pow(p[0].first-p[1].first,2)+pow(p[0].second-p[1].second,2));
 
        cout << (d<=r[0]+r[1]?d+r[1]>=r[0]?d+r[0]>=r[1]?1:-2:2:0) << endl;
    }
 
    return 0;
}

Measured memory_bytes: 3168
program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: cnt(4)=0
    integer(int32):: i,n
    character(3):: judge


    read*, n
    do i=1,n
        read*, judge
        if (judge(1:1) == 'A') then
            cnt(1)=cnt(1)+1
        else if (judge(1:1) == 'W') then
            cnt(2)=cnt(2)+1
        else if (judge(1:1) == 'T') then
            cnt(3)=cnt(3)+1
        else
            cnt(4)=cnt(4)+1
        end if
    end do
    
    print'("AC x ",i0)', cnt(1)
    print'("WA x ",i0)', cnt(2)
    print'("TLE x ",i0)', cnt(3)
    print'("RE x ",i0)', cnt(4)
end program main

Measured memory_bytes: 2908
import Data.List (sort)
import Data.Char (toLower)

readIntLine :: IO ([Int])
readIntLine = do
    x <- getLine
    return $ map (read :: String -> Int) $ words x

main :: IO ()
main = do
    s <- getLine
    putStrLn $ format s

format :: String -> String
format s =
    let p1 = (read :: String -> Int) $ take 2 s
        p2 = (read :: String -> Int) $ drop 2 s
      in if ok p1 then if ok p2 then "AMBIGUOUS"
                                else "MMYY"
                  else if ok p2 then "YYMM"
                                else "NA"

ok :: Int -> Bool
ok x = x > 0 && x < 13


Measured memory_bytes: 508
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <random>
#include <utility>
#include <map>
#include <vector>
#include <queue>
#include <bitset>
#define REP(i,x) for(int i=0; i<(x); i++)
typedef long long ll;

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int x[n],y[n];
    int t[n];
    REP(i, n){
        cin >> t[i] >> x[i] >> y[i];
    }
    int kyori = abs(x[0]) + abs(y[0]);
    if (kyori <= t[0]) {
        if ((kyori % 2) == (t[0]%2)) {
        } else {
            cout << "No" << endl;
            return 0;
        }
    } else {
        cout << "No" << endl;
        return 0;
    }
    REP(i, n-1){
        kyori = abs(x[i]-x[1+i]) + abs(y[i]-y[1+i]);
        if (kyori <= t[1+i]) {
            if ((kyori % 2) == ((t[1+i]-t[i])%2)) {
            } else {
                cout << "No" << endl;
                return 0;
            }
        } else {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 1408
/*
        Author: Prokash
                CSE48, JU

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int ara[2005];
int main()
{
    FAST;
    int n, x = 0, y = 0, t = 0;
    scanf("%d\n",&n);
    for (int i = 0; i < n; i++)
    {
        int time, a, b;
        scanf("%d %d %d\n", &time, &a, &b);
        for (; t < time; t++)
        {
            if (x < a)
            {
                x++;
            }
            else if (x > a)
            {
                x--;
            }
            else if (y < b)
            {
                y++;
            }
            else
            {
                y--;
            }
        }
        if (x != a || y != b)
        {
            cout<<"No"<<endl;
            return 0;
        }
    }

    cout<<"Yes"<<endl;
    return 0;
}

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

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		int[] l = new int[n];
		for (int i = 0; i < n; i++) {
			l[i] = scan.nextInt();
		}
		Arrays.sort(l);
		int ans = 0;
		int c = 0;
		for (int i = l.length-1; ; i--) {
			c++;
			ans = ans + l[i];
			if (c == k) {
				break;
			}
		}
		System.out.println(ans);
	}
}


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

int main(){
	int n; cin >> n;
	string s, t;
	cin >> s >> t;
	string ans = "";
	for(int i = 0; i < n; ++i){
		ans += s[i];
		ans += t[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <memory>
#include <queue>
#include <cassert>
#include <cmath>
#include <ctime>
#include <complex>
#include <bitset>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

#define ws ws_____________________
#define y1 y1_____________________
#define y0 y0_____________________
#define left left_________________
#define right right_______________
#define next next_________________
#define prev prev_________________
#define hash hash_________________

#define pb push_back
#define fst first
#define snd second
#define mp make_pair 
#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(C) begin(C), end(C)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
typedef complex<double> cd;

#define FILE_NAME "a"

const int MAXN = 1e5 + 10;

int n;
int a[MAXN];

bool read() {
	if  (scanf("%d", &n) < 1) {
		return 0;
	}
	forn(i, n) {
		scanf("%d", &a[i]);
	}
	return 1;
}

bool solve() {
	vi cnt(2, 0);
	forn(i, n) {
		++cnt[a[i] % 2];
	}

	while (cnt[1] >= 2) {
		++cnt[0];
		cnt[1] -= 2;
	}

	if  (cnt[1] == 1) {
		if  (!cnt[0]) {
			return 1;
		}
		return 0;
	}

	return 1;
}

int main() {
#ifdef LOCAL
	freopen(FILE_NAME ".in", "r", stdin);
	// freopen(FILE_NAME ".out", "w", stdout);
#endif

	while (read()) {
		puts(solve() ? "YES" : "NO");
	}

#ifdef LOCAL
	cerr.precision(5);
	cerr << "Time: " << fixed << (double) clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


Measured memory_bytes: 768
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ r, g, b, n ] <- readInts
	print $ length $ do
		x <- [ 0 .. n ]
		y <- [ 0 .. n - x * r ]
		let
			rest = n - x * r - y * g
		guard $  0 <= rest && rest `mod` b == 0
		return ()

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

int main () {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int n,Q;
    cin >> n >> Q;

    fenwick_tree<ll> fw(n);
    rep(i,n) {
        int a; cin >> a;
        fw.add(i,a);
    }

    while(Q--) {
        int type;
        cin >> type;
        if(type == 0) {
            int p,x;
            cin >> p >> x;
            fw.add(p,x);
        }
        if(type == 1) {
            int l,r;
            cin >> l >> r;
            cout << fw.sum(l,r) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 8228
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 16:32:55 2020

@author: tinku
"""
n=int(input())
arr=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]=(1.0-arr[i-1])*dp[i-1][j]
        else:
            dp[i][j]=arr[i-1]*dp[i-1][j-1]+(1.0-arr[i-1])*dp[i-1][j]
print(sum(dp[n][n//2+1:]))

Measured memory_bytes: 223820
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


int main() {
  string s;
  cin >> s;
  if (s[2] == s[3] and s[4] == s[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
h,w,c,max;
int D(x,y,c,n,M)int *M;{
	int r=1;
	M[x+(w+2)*y]=n;
	if(M[x-1+(w+2)*y]==c)r+=D(x-1,y,c,n,M);
	if(M[x+1+(w+2)*y]==c)r+=D(x+1,y,c,n,M);
	if(M[x+(w+2)*(y-1)]==c)r+=D(x,y-1,c,n,M);
	if(M[x+(w+2)*(y+1)]==c)r+=D(x,y+1,c,n,M);
	return r;
}
int E(d,M)int *M;{
	if(d==4){
		if(M[1+w+2]==c)return;
		int *m=malloc(400);
		memcpy(m,M,400);
		D(1,1,m[1+w+2],c,m);
		int k=D(1,1,m[1+w+2],-1,m);
		if(max<k)max=k;
		free(m);
		return;
	}
	int i=1,I,J;
	for(;i<7;i++){
		if(M[1+w+2]==i)continue;
		int *m=malloc(400);
		memcpy(m,M,400);
		D(1,1,m[1+w+2],i,m);
		E(d+1,m);
		free(m);
	}
}
a[100];
main(i,j){
	for(;scanf("%d%d%d",&h,&w,&c),c;printf("%d\n",max)){
		memset(a,0,400);
		for(j=1;j<h+1;j++)for(i=1;i<w+1;i++)scanf("%d",a+i+(w+2)*j);
		E(max=0,a);
	}
}

Measured memory_bytes: 604
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include<bitset>
#include <iomanip>

using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;



#define ll long long




/*
class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d, e, H, W, L;
long long A[200005] = {};
long long B[5005][5] = {};
long long C[205][205] = {};
long long D[200005] = {};
long long E[200005] = {};
bool f, ff;
string S[2];
set <long long>sll;
pl bufpl;
vector <long long>vl[3];
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}


bool otta[2005] = {};
bool ri[2005] = {};

ll nijou[65] = {};
ll high,width;

int main() {

	nijou[0] = 1;
	for (int i = 1; i < 65; i++) {
		nijou[i] = nijou[i - 1] * 2;
	}

	while (true) {

		cin >> N >> a >> b;

		if (N == 0 && a == 0 && b == 0) {
			break;
		}

		

		M = nijou[N];
		high = nijou[N]-a+1;

		d = N;

		while (M > 1) {
			if (high > M / 2) {
				otta[d] = true;
				c = high - (M / 2);
				high = (M / 2) - c + 1;//
			}
			else {
				otta[d] = false;
			}

			d--;
			M /= 2;

		}


		M = nijou[N];
		width = b;

		d = 1;

		while (M > 1) {

			if (otta[d] == true) {
				if (width <= M / 2) {
					ri[d] = false;
					c = (M / 2) - width;
					width = c + 1;//
				}
				else {
					ri[d] = true;
					c = M - width;
					width = c + 1;
				}


			}

			if (otta[d] == false) {
				if (width <= M / 2) {
					ri[d] = true;
				}
				else {
					ri[d] = false;
					width = width - (M / 2);
				}


			}



			d++;
			M /= 2;

		}

		for (int i = 1; i <= N; i++) {
			if (ri[i]) {
				cout << 'R';
			}
			else {
				cout << 'L';
			}
		}

		cout << endl;


	}

	return 0;

}



Measured memory_bytes: 3108
#include <iostream>
#include <map>
#define MAX(a,b) ((a>b)? a:b)
using namespace std;

int main(){
    int m,n,w,v,i,j,p,c;
    float s,t,r;
    
    while(1){
        map<int,float> hg;
        cin>>n>>w;
        if(!n && !w){break;}
        for(i=0;i<n;i++){
            cin>>v;
            auto itr=hg.find(v/w);
            if(itr!=hg.end()){
                hg[v/w]++;
            }
            else{
                hg[v/w]=1;
            }
        }
        m=0;c=0;
        r=0.0;
        for(auto itr=hg.begin();itr!=hg.end();itr++){
            m=MAX(m,itr->second);
            c=MAX(c,itr->first);
        }
        for(auto itr=hg.begin();itr!=hg.end();itr++){
            if(c!=0){
                s=(float)(c-itr->first)/c;
            }
            else{
                s=1;
            }
            t=itr->second/m;
            r+=s*t;
        }
        r+=0.01;
        cout<<r<<endl;
    }
    return 0;
}




Measured memory_bytes: 3244
#include <stdio.h>

int main()
{
  char a[11];
  scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3]);
  if (a[0] + a[1] > a[2] + a[3])
    printf("Left");
  else if (a[0] + a[1] < a[2] + a[3])
    printf("Right");
  else
    printf("Balanced");
}

Measured memory_bytes: 128
S=input()
 
if S=='SUN':
  print(7)
elif S=='MON':
  print(6)
elif S=='TUE':
  print(5)
elif S=='WED':
  print(4)
elif S=='THU':
  print(3)
elif S=='FRI':
  print(2)
else:
  print(1)

Measured memory_bytes: 2940
import java.util.*;
import java.math.*;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    long[] h = new long[n];

    for (int i = 0; i < n; i++) {
      h[i] = sc.nextInt();
    }

    Arrays.sort(h);

    long count = 0;

    for (int i = 0; i < n-k; i++) {
      count += h[i];
    }

    System.out.println(count);

  }

}


Measured memory_bytes: 87764
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,c=0;
  cin>>n;
  vector<ll> a(n),b(n);
  for(ll i=1;i<=n;i++){
    cin>>a[i-1];
    b[i-1]=a[i-1]-i;
  }
  sort(b.begin(),b.end());
  ll bb;
  if(n%2==1){
    bb=b[n/2];
  }else{
    bb=(b[n/2]+b[n/2-1])/2;
  }
  for(ll i=0;i<n;i++){
    c+=abs(b[i]-bb);
  }
  cout<<c;
}


Measured memory_bytes: 3328
x, y =map(int, input().split())
if x in {1,3,5,7,8,10,12}:
    x= 1
elif x in {4,6,9,11}:
    x =2
else:
    x = 3
if y in {1,3,5,7,8,10,12}:
    y= 1
elif y in {4,6,9,11}:
    y =2
else:
    y = 3
print("Yes" if x == y else "No")

Measured memory_bytes: 8884
N=int(input())
A=input()
A=A.rstrip().split(" ")
listA=[]
for i in range(N):
    listA.append(int(A[i]))
#print(listA)

B=1
for j in range(N):
    B=B*listA[j]
#print(B)

ans=0
for k in range(N):
    ans+=(B-1)%listA[k]
print(ans)

Measured memory_bytes: 3316
#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int mod = 1000000007;
int main() {
	int S;
	cin >> S;
	vector<int> dp(S + 1);
	dp[0] = 1;
	for (int i = 1; i <= S; ++i) {
		for (int j = 0; j <= i - 3; ++j) {
			dp[i] += dp[j];
			if (dp[i] >= mod) dp[i] -= mod;
		}
	}
	cout << dp[S] << endl;
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	ll mx;
	for (int i = 1; i <= n; i++) {
		if (i * (i - 1) / 2 < n && n <= (1 + i) * i / 2) {
			mx = i;
			break;
		}
	}
	ll wo = (mx + 1) * mx / 2 - n;
	for (int i = 1; i <= mx; i++) {
		if (i != wo)cout << i << endl;
	}
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
q = [(1,0)]
while q:
    x,parent = q.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        q.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)


Measured memory_bytes: 124240
// Problem : C - HonestOrUnkind2
// Contest : AtCoder - AtCoder Beginner Contest 147
// URL : https://atcoder.jp/contests/abc147/tasks/abc147_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

int n;
vii t[20];

void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int c; cin>>c;
        while(c--){
            int x,y; cin>>x>>y;
            x--;
            t[i].pb({x,y});
        }
    }
    int ans = 0;
    for(int m=0;m<(1<<n);m++){
        bool ok = true;
        for(int i=0;i<n;i++){
            if(((m>>i)&1) == 0) continue; 
            for(auto [x,y] : t[i]) ok &= (((m>>x)&1) == y);
        }
        if(ok) ans = max(ans,(ll)__builtin_popcountll(m));
    }
    cout<<ans;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3608
///   ***   ---   |||		 In the name of ALLAH		|||   ---   ***   ///



#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {			cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

ll gcd ( ll a, ll b ) { return __gcd ( a, b ); }
ll lcm ( ll a, ll b ) { return a * ( b / gcd ( a, b ) ); }


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

const int mx = 2e5+123;
ll a[mx];

int main()
{
	optimize();

	int n;
	cin >> n;

	for ( int i = 1; i <= n; i++ ) cin >> a[i];

	ll Mx = 0, ans = 0;
	for ( int i = 1; i <= n; i++ ) {
		if ( a[i] < Mx ) ans += abs ( a[i] - Mx );
		Mx = max ( Mx, a[i] );
	}

	cout << ans << endl;


	return 0;
}

















Measured memory_bytes: 5176
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n],b=1,c=1;
	for(int i=0;i<n;i++){
		cin>>a[i];
		c*=3;
		if(a[i]%2==0) b*=2;
	}
	cout<<c-b;
	return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("-O3")
/*
				C++
				encoding: UTF-8
				Last Modified: 28/Mar/20 05:31:16 PM
*/

#include <bits/stdc++.h>
#ifdef H4wk3ye
#	include <prettypr.hpp>
#endif

using namespace std;

// clang-format off

#define		int                    long long
#define		ve                     vector
#define		pb                     push_back
#define		endl                   "\n"
#define		ff                     first
#define		ss                     second
#define		pii                    pair<int, int>
#define		len(v)                 (int)v.size()
#define		all(v)                 v.begin(), v.end()
#define		reset(a, b)            memset(a, b, sizeof(a));
#define		fr(i, s, n)            for (int i = s ; i < n ; ++i)
#define		dfr(i, s, n)           for (int i = s ; i > n ; --i)

template < typename T > void pr (const T& t) {
    cout << t << "\n";
}

template < typename T, typename U, typename... ARGS >
void pr (const T& t, const U& u, const ARGS&... args) {
    cout << t << " ";
    pr (u, args...);
}

// clang-format on


signed main () {
	ios_base::sync_with_stdio (false), cin.tie (nullptr);
	string s;
	cin >> s;
	bool ans = (s[2] == s[3]) and (s[4] == s[5]);
	pr (ans ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const ll INF = 1e+18;


int main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<a*b/2<<endl;;
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
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<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }
template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

int a[200010];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    rep(i, N-1) {
        int A; cin >> A;
        a[A-1]++;
    }
    rep(i, N) cout << a[i] << endl;
    return 0;
}

Measured memory_bytes: 4380
#include<stdio.h>
int main(void)
{
	char a[1200];
	int b;
	for(b=0;a[b-1]!='\n';b++){
		scanf("%c",&a[b]);
		if(65<=a[b] && 90>=a[b]){
			a[b]+=32;
		}else{
			if(97<=b[a] && 122>=a[b]){
				a[b]-=32;
			}
		}
	}
	a[b-1]=0;
	printf("%s\n",a);
	return 0;
}

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

int main(){
	ll n,w;
  	cin>>n>>w;
	ll wt[n],val[n];
	for(int i=0;i<n;i++){
		cin>>wt[i]>>val[i];
	}
	ll dp[n+1][w+1];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=w;j++){
			if(wt[i-1]<=j)
			dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j]);
			else
			dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][w]<<endl;
	return 0;
}

Measured memory_bytes: 79104
#include<iostream>
#include<string>
using namespace std;
int main(){
  int h,w;
  cin>>h>>w;
  string board[50];
  for(int i=0;i<h;i++) cin>>board[i];
  
  const int dx[8]={1,0,-1,0,1,-1,-1,1};
  const int dy[8]={0,1,0,-1,1,1,-1,-1};
  
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(board[i][j]=='#') continue;
      
      int num=0;
      for(int d=0;d<8;d++){
        const int ni=i+dy[d];
        const int nj=j+dx[d];
        
        if(ni<0||h<=ni) continue;
        if(nj<0||w<=nj) continue;
        if(board[ni][nj]=='#') num++;
      }
      board[i][j]=char(num+'0');
    }
  }
  
  for(int i=0;i<h;i++) cout<<board[i]<<endl;
  return 0;
}
    


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int K, A, B; cin >> K >> A >> B;
    for (int i = K; i <= B; i+=K) {
        if (i >= A) {
            return cout << "OK", 0;
        }
    }
    cout << "NG";
}

Measured memory_bytes: 3608
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;





int main(void){
    ll n;
    cin>>n;
    vector<ll>a(n),dp;
    for(ll i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<n;i++){
        auto itr = upper_bound(dp.begin(),dp.end(),a[i],greater<ll>());
        if(itr==dp.end())dp.push_back(a[i]);
        else *itr=a[i];
    }
    cout<<dp.size()<<endl;
    return 0;
}

Measured memory_bytes: 2168
func readInts(separator: String.Element = " ") -> [Int] {
    return readLine()!.split(separator: separator).map { Int($0)! }
}

func readTwoInts(separator: String.Element = " ") -> (a: Int, b: Int) {
    let ints = readLine()!.split(separator: separator).map { Int($0)! }
    return (a: ints[0], b: ints[1])
}


struct Tower: Hashable {
    let index: Int
    let height: Int
    var adjucents: [Tower] = []
}

struct Load {
    var start: Tower
    var end: Tower
}

func mainC() {
    let (N, M) = readTwoInts()
    var towers = readInts().enumerated().map { (index, element) in Tower(index: index, height: element) }

    let loads = (0..<M).map { _ -> Load in
        let (start, end) = readTwoInts()

        return Load(start: towers[start - 1], end: towers[end - 1])
    }

    // 分類
    for load in loads {
        towers[load.start.index].adjucents.append(load.end)
        towers[load.end.index].adjucents.append(load.start)
    }

    // 調べる
    var count = 0
    for tower in towers {
        var isPeak = true

        let set = Set(tower.adjucents)
        for adjucent in set {
            if tower.height <= adjucent.height {
                isPeak = false
            }
        }

        if isPeak {
            count += 1
        }
    }

    print(count)
}
mainC()

Measured memory_bytes: 26476
using System;
using System.Collections.Generic;

public class WeLoveGolf{
    public static void Main(){
        
        var K = int.Parse(Console.ReadLine());
        var input = Console.ReadLine().Split(' ');
        var A = int.Parse(input[0]);
        var B = int.Parse(input[1]);
        var result = "NG";
        
        for (int i = A; i <= B; i++)
            {
                if (i % K == 0)
                {
                    result = "OK";
                    break;
                }
            }
 
            Console.WriteLine(result);
        }
}

Measured memory_bytes: 27500
#include <bits/stdc++.h>
            #include <ext/pb_ds/assoc_container.hpp>
            #include <ext/pb_ds/tree_policy.hpp>
            using namespace std;
            using namespace __gnu_pbds;
            #define rep(i, a , b) for (ll i =a ; i < b ; i++)
            #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            #define endl "\n"
            #define pb push_back
            #define F first
            #define S second
            #define print(a)       for(auto x : a) cout << x << " "; cout << endl
            #define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
            #define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
            #define mk(x,y)  make_pair(x,y)
            typedef long long int ll;
            const ll N =  1e6+5;
            const ll mod = 1e9+7;
            const ll inf = 1e18;
            ll   n  , k  , s , m  , l , r  , x  , w  , u , z , d  , q ,vis_x[N] , vis_y[N] ;
            pair <ll,ll> a[N];

    ll pow_mod_m(ll a , ll n)
    {
        if(!n)
            return 1;
        ll pt =  pow_mod_m(a,n/2) ;
        pt *= pt  ;
        if(n&1)
            pt *= a ;
        return pt;
    }


    int main()
    {
         IOS;
         int ts =1;
        /// cin >> ts ;
         while(ts--)
         {
            cin >> n >> m >> k;
            map <ll, vector < ll> > mp_x  , mp_y;
            set < pair <ll,ll> > s;
            rep(i,0,k)
            {
                cin >> a[i].F >> a[i].S;
                s.insert( { a[i].F , a[i].S } );
                mp_x[a[i].F].pb(i);
                mp_y[a[i].S].pb(i);
            }
            ll r = 0 ,c = 0 ;
            for(auto u : mp_x)
            {
                r = max((ll)u.S.size() , r);
            }
            for(auto u : mp_y)
            {
                c = max((ll)u.S.size() , c);
            }
            ll ans =  r + c;
            set <ll> row , col;
            for( auto u : mp_x )
            {
                if(r == u.S.size())
                row.insert(u.F);
            }
            for( auto u : mp_y )
            {
                if(c == u.S.size())
                col.insert(u.F);
            }
            ll present_at_intersection = 0 ;
            for(auto u : s)
            {
                if(row.find(u.F) != row.end() and col.find(u.S) != col.end())
                {
                    present_at_intersection ++;
                }
            }
            if(present_at_intersection == (ll)row.size() * (ll)col.size()) ans--;
            cout << ans << endl;
         }
    }


Measured memory_bytes: 120792
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string N;
  cin >> N;
  int n = N.size();
  if (N[n - 1] == '2' || N[n - 1] == '4' || N[n - 1] == '5' || N[n - 1] == '7' || N[n - 1] == '9')
    cout << "hon" << endl;
  else if (N[n - 1] == '0' || N[n - 1] == '1' || N[n - 1] == '6' || N[n - 1] == '8')
    cout << "pon" << endl;
  else
    cout << "bon" << endl;
  return 0;
}


Measured memory_bytes: 3628
object Main extends App {
	val pw = new java.io.PrintWriter(System.out)

	@scala.annotation.tailrec
	def loop(start: Int, end: Int)(f: Int => Unit): Unit =
		if (start < end) {
			f(start)
			loop(start + 1, end)(f)
		}

	pw.println(if (Scanner.nextInt == 1) 0 else 1)
	pw.flush()
}

object Scanner {
	private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0

	@inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
	@inline private def hasNextByte(): Boolean = if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else true
	@inline private def hasNext(): Boolean = {
		while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
		hasNextByte()
	}
	@inline private def readByte(): Byte = if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else -1

	def next(): String = {
		if(!hasNext()) ???
		val sb = new StringBuilder; var b = readByte()
		while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
		sb.toString
	}

	def nextInt(): Int = {
		val n = nextLong()
		if (n < Int.MinValue || Int.MaxValue < n) ???
		n.toInt
	}

	def nextLong(): Long = {
		if(!hasNext()) ???
		var minus = false; var b = readByte()
		if (b == '-') { minus = true; b = readByte() }

		@scala.annotation.tailrec
		def go (b: Byte, n: Long = 0): Long = if ('0' <= b && b <= '9') go(readByte(), n * 10 + b - '0') else if (minus) -n else n

		go(b)
	}

	def nextDouble(): Double = next().toDouble
}


Measured memory_bytes: 54620
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
A = [(l,i) for i,l in zip(range(1,N+1),A)]

A.sort()

print(*[i[1] for i in A])

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

long long solve(vector<long long> nums){
  long long ans = 0;
  int cnt = 0;
  for(int i = 0; i < nums.size()-2; i++){
    for(int j = i+1; j < nums.size()-1; j++){
      for(int k = j+1; k < nums.size(); k++){
        ans += nums[i]*nums[j]*nums[k];
        cnt ++;
      }
    }
  }
  cerr << cnt << endl;
  return ans;
}

int main(){
  int N;
  cin >>N;
  vector<long long> nums(5, 0);
  for(int i = 0; i < N; i++){
    string s;
    cin >> s;
    if(s[0] == 'M') nums[0]++;
    if(s[0] == 'A') nums[1]++;
    if(s[0] == 'R') nums[2]++;
    if(s[0] == 'C') nums[3]++;
    if(s[0] == 'H') nums[4]++;
  }
  
  long long ans;
  ans = solve(nums);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct tree {
	int node;
	int parent = -1;
	int depth = 0;
	vector<int> edge;
};

vector<struct tree> Tr(100001);

void ini_dep(int n) {
	for (int i = 0; i < Tr[n].edge.size(); i++) {
		int next = Tr[n].edge[i];
		Tr[next].depth = Tr[n].depth + 1;
		ini_dep(next);
	}
}

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
//	vector<struct tree> Tr(n);
	for (int i = 0; i < n;i++) {
		int id, k, c; cin >> id >> k;
		Tr[id].node = id;
		for (int j = 0; j < k;j++) {
			cin >> c;
			Tr[c].parent = id;
			//Tr[c].depth = Tr[id].depth + 1;
			Tr[id].edge.push_back(c);
		}
	}

	int root;
	for (int i = 0; i < n; i++) {
		if (Tr[i].parent == -1) { root = i; }
	}

	ini_dep(root);

	for (int i = 0; i < n;i++) {
		cout << "node " << i << ": parent = " << Tr[i].parent << ", depth = " << Tr[i].depth
			<< ", ";
		if (Tr[i].parent == -1) { cout << "root, ["; }
		else if (Tr[i].edge.size() != 0) { cout << "internal node, ["; }
		else { cout << "leaf, ["; }
		for (int j = 0; j < Tr[i].edge.size(); j++) {
			if (j != Tr[i].edge.size() - 1) {
				cout << Tr[i].edge[j] << ", ";
			}
			else {
				cout << Tr[i].edge[j];
			}
		}
		cout << "]" << endl;
	}
}

Measured memory_bytes: 7616
MOD = 10**9 + 7
n,k,*a=map(int,open(0).read().split())
a.sort()
comb = 1
ans = 0
for i in range(k,n+1):
    ans += (a[i-1] - a[-i]) *comb 
    comb = comb * i * pow(i-k+1,MOD-2,MOD) % MOD
    ans = ans%MOD
print(ans)

Measured memory_bytes: 14316
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  int M = sc.nextInt();
  String[] a = new String[N];
  String[] b = new String[M];
  boolean exist = false;
  for(int i = 0;i < N;i++)a[i] = sc.next();
  for(int i = 0;i < M;i++)b[i] = sc.next();
  out:
  for(int i = 0;i < N-M+1;i++) {
    for(int j = 0;j < N-M+1;j++) {
      for(int k = 0;k<M;k++) {
        if(!(a[j+k].substring(i,i+M).equals(b[k]))) break;
        if(k == M - 1) {
          exist = true;
          break out;
        }
      }
    }
  }
  if(exist) System.out.println("Yes");
  else System.out.println("No");
}}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

vector<vector<ll>>a(11);
ll ch[11],n,m,ans;
bool sw[11];
void cal(){
	bool now=true;
	for(ll i=0;i<m;i++){
		ll sum=0;
		for(ll j=0;j<a[i].size();j++){
			if(sw[a[i][j]]){
				sum++;
			}
		}
		if(sum%2!=ch[i]){
			now=false;
		}
	}
	if(now!=false){
		ans++;
	}
}
void dep(ll now){
	if(now==n){
		cal();
		return;
	}
	sw[now]=0;dep(now+1);
	sw[now]=1;dep(now+1);
}
int main() {
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		ll x;
		cin>>x;
		for(ll j=0;j<x;j++){
			ll y;
			cin>>y;
			y--;
			a[i].push_back(y);
		}
	}
	for(ll i=0;i<m;i++){
		cin>>ch[i];
	}
	dep(0);
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
import std.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.typecons;

struct R {
    int l, t, r, b;
}

void main() {
    int n;
    while (readf("%d\n", &n), n) {
        int[] ps;
        R[] Rs;
        foreach (i; 0 .. n) {
            int[] p = readln.chomp.split(" ").map!(to!int).array;
            ps ~= p;
            Rs ~= R(p[0], p[1], p[2], p[3]);
        }
        int[int] cmap;
        int[] v = [-1] ~ ps.sort.uniq.array ~ [1000002];
        //v.writeln;
        foreach (int i, x; v) {
            cmap[x] = i;
        }
        int ymax = cmap[1000002],
            xmax = cmap[1000002];
        foreach (ref r; Rs) {
            r.l = cmap[r.l];
            r.t = cmap[r.t];
            r.r = cmap[r.r];
            r.b = cmap[r.b];
        }

        long[][] F = new long[][](ymax, xmax);
        void fillR(in R r, long id) {
            foreach (i; r.b .. r.t) {
                foreach (j; r.l .. r.r) {
                    F[i][j] += id;
                }
            }
        }
        foreach (i, r; Rs) {
            fillR(r, (1L << i));
        }

        //foreach (ref _; F) _.writeln;

        bool[][] used = new bool[][](ymax, xmax);
        void dfs(int y, int x) {
            static const dy = [1, 0, -1, 0],
                         dx = [0, 1, 0, -1];
            used[y][x] = true;
            foreach (i; 0 .. 4) {
                int ny = y + dy[i],
                    nx = x + dx[i];
                if (ny < 0 || ny >= ymax) continue;
                if (nx < 0 || nx >= xmax) continue;
                if (used[ny][nx]) continue;
                if (F[ny][nx] != F[y][x]) continue;
                dfs(ny, nx);
            }
        }

        int c = 0;
        foreach (i; 0 .. ymax) {
            foreach (j; 0 .. xmax) {
                if (used[i][j]) continue;
                c++;
                dfs(i, j);
            }
        }

        c.writeln;
    }
}

Measured memory_bytes: 6512
ans=0
def f(cnt,div):
    global ans
    if cnt==0:
        ans+=eval(div)
    else:
        f(cnt-1,div[:cnt]+'+'+div[cnt:])
        f(cnt-1,div[:cnt]+div[cnt:])

n=input()
f(len(n)-1,n)
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
int main()
{
	int n,nc;
	int i=0,j;
	int tmp;
	int v[1000];
	double arr[1000];
	
	scanf("%d",&n);
	nc=n;
	for(;nc>0;nc--)
	{
		scanf("%d",&v[i]);
		i=i+1;
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(v[i]>v[j])
			{
				tmp=v[i];
				v[i]=v[j];
				v[j]=tmp;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		arr[i]=(double)v[i];
	}
	for(i=0;i<=n-2;i++)
	{
		arr[i+1]=(arr[i]+arr[i+1])/2;
	}
	printf("%lf",arr[n-1]);
	return 0;
}

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

typedef long long ll; // -9,223,372,036,854,775,808 から 9,223,372,036,854,775,807

template <class T> using vec = std::vector<T>;
template <class T> using vec2 = vec<vec<T>>;
template <class T> using vec3 = vec<vec<vec<T>>>;

#define DEBUG

void solve(long long N, std::vector<long long> P){
    vec<ll> lenArray(N+1);
    for(auto iter: P){
        lenArray.at(iter) = lenArray.at(iter-1) + 1;
    }

    ll maxLen = *max_element(lenArray.begin(), lenArray.end());

    cout << N - maxLen << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> P(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&P[i]);
    }
    solve(N, std::move(P));
    return 0;
}


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

void main_()
{
    string S;
    cin >> S;
    deque<char> d(begin(S), end(S));

    ll Q;
    cin >> Q;

    bool is_reverse = false;
    for (ll i = 0; i < Q; ++i) {
        int T;
        cin >> T;
        if (T == 1) {
            is_reverse = !is_reverse;
        } else { // T == 2
            int F;
            char C;
            cin >> F >> C;
            if ((F == 1 && is_reverse) || (F == 2 && !is_reverse)) {
                d.push_back(C);
            } else {
                d.push_front(C);
            }
        }
    }
    if (is_reverse) {
        reverse(begin(d), end(d));
    }
    copy(begin(d), end(d), ostreambuf_iterator<char>(cout));
    cout << "\n";
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


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

int main() {
  int N; cin >> N;
  vector<int> sum(N);
  rep(i,N) {
    int W; cin >> W;
    if(i==0) sum[i] = W;
    else sum[i] = sum[i-1] + W;
  }
  int diff=10e9;
  rep(i,N) {
    diff = min(diff, abs(sum[N-1] - sum[i] - sum[i]));
  }
  cout << diff << endl;
  return 0;
}


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

int main(void){
    int N, D, X;

    scanf("%d%d%d", &N, &D, &X);

    int i, A;
    int sum = 0;

    for(i = 0; i < N; i ++){
        scanf("%d", &A);

        sum += (D - 1) / A + 1;
    }
    printf("%d", sum + X);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define N 300005
const int INF=0x3f3f3f3f;
const int mod=1e9 + 7;
using namespace std;
ll a[N];
int main(){
	ll n;
	cin >> n;
	ll sum = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
	} 
	cout << sum - n << endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
using namespace std;
	long long as[200001],bs[200001],n,m,k,a[200001],b[200001],s;
int main(void)
{
	int i,j;
	int mx,mid,low,high;
	scanf("%lld %lld %lld",&n,&m,&k);
	for(i=1;i<=n;i++)	scanf("%lld",&a[i]);
	for(i=1;i<=m;i++)	scanf("%lld",&b[i]);
	as[0]=0;
	for(i=1;i<=n;i++)	as[i]=as[i-1]+a[i];
	bs[0]=0;
	for(i=1;i<=m;i++)	bs[i]=bs[i-1]+b[i];
	mx=0;
	for(i=0;i<=n;i++)	{
		s=k-as[i];
		if(s<0)	break;
		low=0;	high=m;
		while(low<=high)	{
			mid=(low+high)/2;
			if(bs[mid]==s)	{
				high=mid;
				break;
			}
			else if(bs[mid]<s)	{
				low=mid+1;
			}
			else high=mid-1;
		}
		mx=max(mx,high+i);
	}
	printf("%d\n",mx);
	return 0;
}

Measured memory_bytes: 7972
#include <iostream>
using namespace std;
int main(){
  string S;
  while(cin >> S, S != "#"){
    if(S.length() <= 2){
      cout << 0 << endl;
      continue;
    }
    int ans = 0;
    int f[2] = {S[0],S[1]}, m = 1;
    for(int i = 1; i < S.length(); ++i){
      if((m == 1 && (S[i]-'0'-1)%3 > (f[1-m]-1)%3)){
	++ans;
	f[1-m] = S[i] - '0';
      }else if((m == 0 && (S[i]-'0'-1)%3 < (f[1-m]-1)%3)){
	++ans;
	f[1-m] = S[i] - '0';
      }else{
	f[m] = S[i] - '0';
	m = 1-m;
      }
    }
    int t = 0;
    f[0] = S[1];
    f[1] = S[0];
    m = 0;
    for(int i = 1; i < S.length(); ++i){
      if((m == 1 && (S[i]-'0'-1)%3 > (f[1-m]-1)%3)){
	++t;
	f[1-m] = S[i] - '0';
      }else if((m == 0 && (S[i]-'0'-1)%3 < (f[1-m]-1)%3)){
	++t;
	f[1-m] = S[i] - '0';
      }else{
	f[m] = S[i] - '0';
	m = 1-m;
      }
    }
    //cout << ans << endl;
    //cout << t << endl;
    ans = min(ans,t);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3128
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <set>
#include <queue>
using namespace std;

int main(){
	int n, k; cin >> n >> k;
	if (n % k == 0) cout << "0" << endl;
	else cout << "1" << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef vector<pair<ll,ll> > vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
  string s;cin>>s;
  bool ok=true;
  rep(i,0,3){
    bool okok=false;
    rep(j,0,3){
      if(s[j]=='a'+i){okok=true;}
    }
    if(!okok){ok=false;break;}
  }
  if(ok){cout<<"Yes"<<endl;}
  else{cout<<"No"<<endl;}
}



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

using namespace std;

typedef long long ll;

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

    int k;  cin >> k;
    string s;   cin >> s;

    int n = s.size();

    string Ans;

    if(s.size() <= k)
    {
        Ans = s;
    }

    else
    {
        Ans = s.substr(0, k) + "...";
    }

    cout << Ans << endl;
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using llu = long long unsigned int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N,X,Y;
    Scd3(N,X,Y);
    X--,Y--;

    vector<vi> e(N);
    Rep(i,N-1) e[i].push_back(i+1), e[i+1].push_back(i);
    e[X].push_back(Y);
    e[Y].push_back(X);

    vector<vi> d(N,vi(N,INF));
    Rep(i,N)   d[i][i] = 0;

    vi ans(N,0);
    stack<int> s;
    Rep(i,N){
        s.push(i);
        while( s.size() ){
            int from = s.top();
            int di = d[i][from];
            s.pop();
            for( int to : e[from] ){
                if( d[i][to] > di+1 ){
                    d[i][to] = di+1;
                    s.push(to);
                }
            }
        }
    }

    Rep(i,N) Rep(j,N){
        ans[d[i][j]]++;
    }

    Repe(i,N,1){
        printf ("%d\n", ans[i]/2 );
    }

    return 0;

}




Measured memory_bytes: 16128