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

int main(){
  int n;
  cin>>n;

  vector<double> v(n);
  int i;
  for(i=0;i<n;i++)
  cin>>v[i];

  sort(v.begin(),v.end());
  double ans=(v[0]+v[1])/2;
  for(i=2;i<n;i++){
    ans=(ans+v[i])/2;
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

const int mod = 998244353;

int N, M;
ll F[3000010], IF[3000010];

ll pw(ll x, ll y = mod - 2) {
	ll res = 1;
	while(y) {
		if(y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

ll nCr(int n, int r) {
	if(r < 0 || r > n) return 0;
	return F[n] * IF[r] % mod * IF[n-r] % mod;
}

int main() {
	F[0] = 1; for(int i=1;i<3000010;i++) F[i] = i * F[i-1] % mod;
	IF[3000009] = pw(F[3000009]);
	for(int i=3000008;i>=0;i--) IF[i] = (i+1) * IF[i+1] % mod;
	scanf("%d%d", &N, &M);
	ll ans = 0;
	for(int t=0;t<=N && t<=M;t++) {
		if((3*M-t) % 2 != 0) continue;
		
		int sum = (3 * M - t) / 2;
		ll C1 = nCr(N, t) * nCr(N + sum - 1, sum) % mod;
		
		ans = (ans + C1) % mod;
		if(sum >= M) {
			int sum2 = sum - M;
			ll C2 = nCr(N, t) * nCr(N + sum2 - 1, sum2) % mod * t % mod;
			ans = (ans - C2 + mod) % mod;
		}
		if(sum >= M+1) {
			int sum2 = sum - M - 1;
			ll C2 = nCr(N, t) * nCr(N + sum2 - 1, sum2) % mod * (N-t) % mod;
			ans = (ans - C2 + mod) % mod;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 47104
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int c=0,t,p=0,a=0;
  string s;
  cin>>s;
  reverse(s.begin(),s.end());
  r(b,12)if(s[b]=='?')r(i,10){
      s[b]='0'+i;
      for(int j=11;j>0;j--){
	if(j>=7)a+=(j-5)*(s[j]-'0');
	else a+=(j+1)*(s[j]-'0');
	//cout<<j<<' '<<j-5<<endl;
      }
      if(a%11<=1)a=0;
      else a=11-a%11;
      if(a==s[0]-'0'){c++;t=i;}
      a=0;
    }
  if(c==1)cout<<t<<endl;//cout<<c;
  else cout<<"MULTIPLE"<<endl;
}

Measured memory_bytes: 3216
#include<stdio.h>
#define ll long long int
int main(){
	ll a,b,m;
	scanf("%lld%lld%lld",&a,&b,&m);
	ll i;
	ll A[a],B[b],M[3][m];
	ll mina,minb,sum;
	ll la,lb;
	for(i=0;i<a;i++){
		scanf("%lld",&A[i]);
		if(i==0){
			mina=A[i];
			la=0;
		}
		else{
			if(A[i]<mina){
				mina=A[i];
				la=i;
			}
		}

	}
	for(i=0;i<b;i++){
		scanf("%lld",&B[i]);
		if(i==0){
			minb=B[i];
			lb=0;
		}
		else{
			if(B[i]<minb){
				minb=B[i];
				lb=i;
			}
		}
	}
	sum=mina+minb;
	for(i=0;i<m;i++){
		scanf("%lld%lld%lld",&M[0][i],&M[1][i],&M[2][i]);
		}

	for(i=0;i<m;i++){
		if(A[M[0][i]-1]+B[M[1][i]-1]-M[2][i]<sum){
			sum=A[M[0][i]-1]+B[M[1][i]-1]-M[2][i];

		}
	}
	printf("%lld",sum);
}


Measured memory_bytes: 4096
n = int(input())
n_ac = 0
n_wa = 0
n_tle = 0
n_re = 0
for i in range(n):
    temp = input()
    if temp == "AC":
        n_ac += 1
    elif temp == "WA":
        n_wa += 1
    elif temp == "TLE":
        n_tle += 1
    else :
        n_re += 1
print("AC x "+str(n_ac))
print("WA x "+str(n_wa))
print("TLE x "+str(n_tle))
print("RE x "+str(n_re))

Measured memory_bytes: 9208
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n, m; cin >> n >> m;
    int Min = pow(10,n-1);
    if (n == 1) Min = 0;
    int Max = pow(10,n)-1;
    vector<int> s(m);
    vector<char> c(m);
    rep(i,m) {
        cin >> s[i] >> c[i];
    }
    for (int i = Min; i <= Max; i++) {
        string str = to_string(i);
        bool ok = true;
        rep(j,m) {
            // char比較
            if (str[s[j]-1] != c[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

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

int main() {
    int N, Alice = 0, Bob = 0;
    bool trun = true;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A.at(i);
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    
    for(int x : A) {
        if (trun) Alice += x;
        else Bob += x;
        trun = !trun;
    }

    cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#define ll long long
#define fr(i,k,N) for(decltype(N+k) i=k; i<N;i++)
#define rep(i,N) for(decltype(N) i=0; i<N;i++)
#define ALL(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}}
template <class X> void prrr(X test){int f=0;for(auto it:test){cout<<(f++!=0?" ":"")<<it;}cout<<endl;}
template<typename X>
istream&operator>>(istream&i,vector<X>&v){for(X&x:v)i>>x;return i;}

class UF { // union find from https://github.com/kartikkukreja/blog-codes (MIT)
    // [usage]
    // auto uf = new UF(n);
    // uf->merge(l, r); // 0 <= l, r <= n-1
    // ...
public:
    int *id; // inner id
    int cnt; // number of all vartices
    int *sz; // sz[i] means size of i's set
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF() {
        delete [] id;
        delete [] sz;
    }
    int find(int p) {
        int root = p;
        while (root != id[root]) root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    int count() {
        return cnt;
    }
};

// return 約数unordered_set 1 <= x <= n
auto divv = [](auto n) {
  unordered_set<decltype(n)> v;
  for(decltype(n) i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      v.insert(i);
      if(i*i != n) v.insert(n/i);
    }
  }
  return v;
};

// check prime (and n>=2) or not
auto isPrime = [](auto n){
  if(n <= 1) return false;
  for(decltype(n) i = 2; i <= sqrt(n); ++i) {
      if(n % i == 0) {
          return false;
      }
  }
  return true;
};



int main() {
    ll a;
    cin>>a;
    string s;
    cin>>s;
    
    unordered_set<string> u;
    unordered_set<string> ans;
    
    for(const auto& itt:s){
        auto it = string(1, itt);
        auto uu = u;
        for(const auto& jt:u){
            auto tmp = jt + it;
            if(tmp.size()>=3) {
                ans.emplace(tmp);
            }else{
                uu.emplace(tmp);
            }
        }
        swap(u, uu);
        u.emplace(it);
    }
    
    pr(ans.size());
}


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

int main(void){
	int a,b,c;
	char temp;
	int hisi = 0, cho = 0;
	while(!cin.eof()){
		cin >> a >> temp >> b >> temp >> c;
		if(a*a + b*b == c*c)
			cho++;
		if(a == b)
			hisi++;
	}
	cout << cho << endl << hisi << endl;
}

Measured memory_bytes: 1160
def main():
    K, A, B = map(int, input().split())
    ans = 1
    if A > 1:
        K -= A - 1
        ans += A - 1
    if K % 2 != 0:
        ans += 1
        K -= 1
    if B - A > 1:
        print((B - A) * (K // 2) + ans)
    else:
        print(ans + K)


main()


Measured memory_bytes: 2940
function main(input) {
  // 入力値（文字列）を改行で区切る
  const inputList = input.split(/\n/);
  const numList = inputList[1].split(/\s/).map(ip => formatNum(ip));
  const half = Math.floor(numList.length / 2);
  numList.sort(compareFunc);
  const result = numList[half] - numList[half - 1];
  console.log(result);
};

// 文字列を数値に変換
function formatNum(str) {
  return Number(str);
};

function compareFunc(a, b) {
  return a - b;
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 27832
#!/usr/bin/env python3


def solv(l, r):
    # 2019 = 673 * 3
    if r - l >= 672:
        return 0

    if l == 0:
        return 0

    ans = 2018
    for i in range(l, r+1):
        for j in range(i+1, r+1):
            a = (i * j) % 2019
            if a < ans:
                ans = a
    return ans

if __name__ == '__main__':

    l, r = map(int, input().split())

    ans = solv(l, r)
    print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100000+5;
int a[N];

int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	long long m=1;
	int s=0;
	sort(a,a+n);
	for(int i=n-1;i>0;i--){
		if(a[i]==a[i-1]){
			m*=a[i];
			s++;
			if(s==2)
				break;
			i--;
		}
	}
	if(s<2)
		m=0;
	cout<<m<<endl;
	return 0;
}

Measured memory_bytes: 768
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int[]list = new int[11];
	static int weight;
	public static void main(String[] args) {
		makeList();
		while(read()){
			solve();
		}
	}
	static void makeList(){
		list[0] = 1;
		for(int i = 1; i < 11; i++){
			list[i] = list[i-1]*2;
		}
		Arrays.sort(list);
	}
	static boolean read(){
		if(!sc.hasNext())
			return false;
		weight = sc.nextInt();
		return true;
	}
	static void solve(){
		ArrayList<Integer>ans = new ArrayList<Integer>();
		int index = 0;
		while(weight != 0){
			if(weight > list[index]){
				index++;
			}else if(weight < list[index]){
				weight = weight - list[index-1];
				ans.add(list[index-1]);
				index = 0;
			}else{
				weight = weight - list[index];
				ans.add(list[index]);
				index = 0;
			}
		}
		Collections.sort(ans);
		for(int i = 0; i < ans.size() - 1; i++){
			System.out.print(ans.get(i) + " ");
		}
		System.out.println(ans.get(ans.size()-1));
	}
}

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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  
  if (A >= K) {
    cout << K << endl;
  }
  
  else if (A + B >= K) {
    cout << A << endl;
  }
  
  else {
    cout << A * 2 - K + B << endl;
  }
  
    
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    rep(i,n){
        int x;
        cin>>x;
        x--;
        v[x]++;
    }
    sort(v.begin(),v.end());
    int cnt = 0;
    int ans = 0;
    int size = 0;
    //cout<<endl;
    //rep(i,n) cout<<v[i]<<" ";
    //cout<<endl;
    rep(i,n) if(v[i]>0) size++;
    //cout<<size<<endl;
    for(int i=0;i<n;i++){
        if(v[i]>0){
            //cout<<i<<" is minus "<<v[i]<<endl;
            cnt++;
            ans+=v[i];
        }
        if(cnt>=size-k) break;
    }
    //cout<<n-k<<endl;
    cout<<ans<<endl;
    return 0;
}

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

int H;	

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

void swap(int *x, int *y){
	int trader;
	trader = *x;
	*x = *y;
	*y = trader;
}//trading x y

void maxHeapify(int *A, int i){
	int l, r, largest;
	l = left(i);
	r = right(i);
	
	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(A, largest);
   }
	}
	
	void buildMaxHeap(int *A){
		int i;
		
    for(i = H/2; i > 0; i--){
        maxHeapify(A, i);
			}
	}
	
int main(){
	int i;
	int *A;
	
	scanf("%d", &H);
	A = malloc(sizeof(int) * (H + 1));	
	for(i = 1; i <= H; i++){
		scanf("%d", &A[i]);
	}
	
	buildMaxHeap(A);
	
	for(i = 1; i <= H; i++){
	printf(" %d", A[i]);
}

printf("\n");
return 0;
}

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

const int N=800005;
int n,m;
int v[N],nxt[N],head[N];
long long s[N],w[N],tag[N];

void pushdown(int x,int l,int r)
{
	int mid=(l+r)>>1;
	s[x<<1]+=tag[x],s[x<<1|1]+=tag[x];
	tag[x<<1]+=tag[x],tag[x<<1|1]+=tag[x];
	tag[x]=0;
}

void modify(int x,int l,int r,int L,int R,long long val)
{
	if(l>=L&&R>=r)
	{
		s[x]+=val,tag[x]+=val;
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if(L<=mid) modify(x<<1,l,mid,L,R,val);
	if(R>mid) modify(x<<1|1,mid+1,r,L,R,val);
	s[x]=max(s[x<<1],s[x<<1|1]);
}

long long query(int x,int l,int r,int L,int R)
{
	if(l>=L&&R>=r) return s[x];
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	long long res=-0x3f3f3f3f3f3f3f3f;
	if(L<=mid) res=max(res,query(x<<1,l,mid,L,R));
	if(R>mid) res=max(res,query(x<<1|1,mid+1,r,L,R));
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		long long z;
		scanf("%d%d%lld",&y,&x,&z);
		v[i]=y,w[i]=z;
		nxt[i]=head[x],head[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		modify(1,1,n,i,i,query(1,1,n,1,i));
		for(int j=head[i];j>0;j=nxt[j])
		{
			modify(1,1,n,v[j],i,w[j]);
		}
	}
//	cout<<query(1,1,n,1,n)<<endl;
	printf("%lld\n",max(s[1],0ll));
}

Measured memory_bytes: 22784
#include<iostream>

using namespace std;

int A, B, C, K,ans;

int main() {

	cin >> A >> B >> C >> K;
	if (A < K) {
		ans += A;
		K -=  A;
	}
	else {
		ans = K;
		K = 0;
	}

	if (B < K && K>0) {
		K -=   B;
	}
	else if (K > 0) {
		K = 0;
	}

	if (C < K && K > 0) {
		ans += -C;
		K -=  C;
	}
	else if (K != 0) {
		ans += -K;
		K = 0;
	}

	cout << ans << endl;
}


Measured memory_bytes: 3632
//file_name:ABC47_B.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


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


    ll ans = 0;

    int l = 0;
    int r = w;
    int t = h;
    int u = 0;

    rep(i,n){
        int x,y,a;
        cin >> x >> y >> a;
        if(a==2){
            r = min(r,x);
        }
        if(a==1){
            l = max(l,x);
        }
        if(a==4){
            t = min(t,y);
        }
        if(a==3){
            u = max(u,y);
        }
    }
    ans = max(0,r-l)*max(0,t-u);

    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
#define eb emplace_back
#define rep(i,n) for(int i=0; i<(n); ++i)
#define outl(x) cout<< (x) << '\n'
#define outl2(x,y) cout<< (x) << ' ' << (y) << '\n'
#define show(x) clog << #x << " \t = " << (x) << '\n'
using pii = pair<int,int>;
using ll = long long;
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
static constexpr int INF = 0x3f3f3f3f;

vector<int> G[10];
int N, M;
int dp[10][1 << 9];

int _(int u, int bit)
{
    if (bit == (1 << N)-1) {
        return 1;
    }
    if (~dp[u][bit]) return dp[u][bit];

    int ret = 0;

    for (int nxt : G[u]) {
        if ((bit >> nxt) & 1) continue;
        ret += _(nxt, bit | (1 << nxt));
    }

    return dp[u][bit] = ret;
}

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

    cin>> N >> M ;
    rep(i, M) {
        int a,b;
        cin >> a >> b;
        --a, --b;
        G[a].eb(b);
        G[b].eb(a);
    }

    memset(dp, -1, sizeof(dp));

    outl(_(0,1));

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2　//1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int,int>;
typedef vector<int> vit;

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

  int n, k;
  cin >> n >> k;
  int x[n + 5];
  reps(i, n){
    cin >> x[i];
  }
  lol ans = LINF, nasu;
  reps(i, n - k + 1){
    nasu = x[i] - x[i + k - 1];
    ans = min({ans, max(-x[i], x[i]) + max(nasu, -nasu), max(-x[i + k - 1], x[i + k - 1]) + max(nasu, -nasu)});
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 640
n=int(input())
from collections import deque
q =deque(input())

ans = 0
while q:
    while q and q[0] == 'R' and q:
        q.popleft()
    while q and q[-1] == 'W' and q:
        q.pop()
    if not q:break
    ans += 1
    q.popleft()
    q.pop()
print(ans)

Measured memory_bytes: 81576
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long x = sc.nextLong();
		long[]a = new long[N];
		for(int i = 0; i < N; i++) {
			a[i] = sc.nextLong();
		}
		sc.close();
		long cnt = 0;
		for(int i = 1; i < N; i++) {
			long t = a[i] + a[i - 1];
			if(t > x) {
				long res = t - x;
				cnt += res;
				if(a[i] >= res) {
					a[i] -= res;
				}else {
					a[i - 1] -= res - a[i];
					a[i] = 0;
				}
			}
		}
		System.out.println(cnt);
	}
}

Measured memory_bytes: 50760
//MISHON69
//DATE:6/24/2020
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long

int main(){
  int a;
  cin>>a;
  cout<<a+a*a+a*a*a<<endl;   
}

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

//gcdやり直す

void swap (int *x, int *y) {
  int temp;    

  temp = *x;
  *x = *y;
  *y = temp;
}




/***
* pivotを決め、
* 全データをpivotを境目に振り分け、
* pivotの添え字を返す
***/
int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;   // 先頭要素をpivotとする

  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    // pivotより小さいものを左へ、大きいものを右へ
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);   //pivotを更新

  return j;
}

/* クイックソート */
void quick_sort (int array[], int left, int right) {
  int pivot;

  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
    quick_sort(array, pivot+1, right);
  }
}




/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

int main(void){
  int n;
  scanf("%d",&n);
  int ans=0;
  for(int i=3;i<=n;i++){
    int div=1;
    int now=i;
    for(int j=2;j*j<=i;j++){
      int count=1;
      while(now%j==0){
        count++;
        now/=j;
      }

      div*=count;
    }

    if(now!=1){
      div*=2;
    }

    if(div==8 && i%2==1){
      ans++;
    }
  }

  printf("%d\n",ans);
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define int ll

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

  int N;
  cin>>N;
  vector<int>A(N),B(N);
  for(int i=0;i<N;i++)cin>>A[i];
  for(int i=0;i<N;i++)cin>>B[i];
  priority_queue<pii>q;
  for(int i=0;i<N;i++)q.push({B[i],i});
  int ans=0;
  while(q.size()){
    int num=q.top().first;
    int now=q.top().second;
    q.pop();
    int sum=0;
    if(B[now]==A[now])continue;
    if(now==0)sum=B[1]+B[N-1];
    else if(now==N-1)sum=B[0]+B[N-2];
    else sum=B[now-1]+B[now+1];
    if(B[now]-sum<A[now]){
      cout<<-1<<endl;
      return 0;
    }
    int time=(B[now]-A[now])/sum;
    ans+=time;
    B[now]-=time*sum;
    if(A[now]!=B[now])q.push({B[now],now});
  }
  bool ok=true;
  for(int i=0;i<N;i++)if(A[i]!=B[i])ok=false;
  if(ok)cout<<ans<<endl;
  else cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 5620
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    cnt = Counter(a)
    comb = 0
    for v in cnt.values():
        if v >= 2:
            comb += v * (v - 1) // 2
    for k in range(n):
        if cnt[a[k]] >= 2:
            print(comb - (cnt[a[k]] - 1))
        else:
            print(comb)


if __name__ == "__main__":
    main()


Measured memory_bytes: 29748
#include<bits/stdc++.h>
using namespace std;
int a[300001],b[300001]={0},c[300001]={0};
int u=0;
int n;
int k;
int judge(int q,int k)
{
	int l=1,r=n,mid,ans;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(b[mid]<q&&(mid==n||b[mid+1]>=q))
		{
			ans=mid;
			break;
		}
		else if(b[mid]<q) l=mid+1;
		else r=mid-1;
	}
	if((n-ans)*q+c[ans]>=k*q) return 1;
	else return 0;
}
int main(){
	cin>>n;
	int m=-1;
	for(int i=1;i<=n;++i)
	{
		int x;
		cin>>x;
		b[x]++;
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;++i)
	{
		c[i]=c[i-1]+b[i];
	}
	int q=n;
	for(int i=1;i<=n;++i)
	{
		while(!judge(q,i))
		{
			q--;
		}
		cout<<q<<endl;
	}
	return 0;
}

Measured memory_bytes: 3200
#include<iostream>
	#include<vector>
	#include<algorithm>
	#include<bits/stdc++.h>
	using namespace std;
	#define pb push_back
	#define ll long long int
	# define pll pair<ll,ll>
		
	int main()
	{
		int n;
		cin>>n;
		if(n==1)
		{
			cout<<0<<"\n";
			return 0;
		}
		vector<ll> a(n);
		for(int i=0;i<n;i++)
		cin>>a[i];
		sort(a.begin(),a.end());
		reverse(a.begin(),a.end());			
		ll ans=0;
		ans+=a[0];
		for(int i=2;i<n;i++)
		{
			ans+=a[i/2];
		}
		cout<<ans<<'\n';
		return 0;
	}

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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = LLONG_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;
}

signed main() {
	ll n;
	string s;

	cin >> n >> s;

	vector<ll> v1(n, 0);
	vector<ll> v2(n, 0);
	
	REP(i, n - 1) {
		if (s[i] == 'W') {
			v1[i + 1] = v1[i] + 1;
		}
		else {
			v1[i + 1] = v1[i];
		}
	}
	
	RFOR(i, 1, n) {
		if (s[i] == 'E') {
			v2[i - 1] = v2[i] + 1;
		}
		else {
			v2[i - 1] = v2[i];
		}
	}
	
	ll ans = INF;

	REP(i, n) {
		ans = min(ans, v1[i] + v2[i]);
	}

	cout << ans << endl;
}

Measured memory_bytes: 5380
n = int(input())
a = list(map(int,input().split()))
 
s = sum(a)
 
left = 0
right = s
res = s
for i in range(n-1):
    left += a[i]
    right -= a[i]
    res = min(res,abs(left-right))
    if res == 0:
        break
    
print(res)



Measured memory_bytes: 88016
#include <stdio.h>

int main() {
	int a, b;
	scanf("%d", &a);
	
	b = a / 2;
	
	if(a % 2 == 1) {
		printf("%d", b + 1);
	} else {
		printf("%d", b);
	}
	
	return 0;
}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 5e5 + 123;
const int M = 1e6 + 123;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int a[N];

ll dp[N][3];

void relax(ll &a, ll b){
    a = max(a, b);
}

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    memset(dp, -0x3f, sizeof dp);
    dp[1][0] = a[1];
    for (int i = 2; i <= n; i++){
        relax(dp[i][0], dp[i-2][0] + a[i]);
        relax(dp[i][1], dp[i-2][1] + a[i]);
        relax(dp[i][2], dp[i-2][2] + a[i]);

        relax(dp[i][1], dp[i-1][0] + a[i]-a[i-1]);
        relax(dp[i][2], dp[i-1][1] + a[i]-a[i-1]);
    }
    if (n%2 == 0){
        cout << max(dp[n][1], dp[n-1][0]);
    }
    else{
        cout << max({dp[n][2], dp[n-1][1], dp[n-2][0]});
    }
}

int main(){
    #ifdef KAZAKH
        freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++){
        //cout << "case #" << i << ": ";
        solve();
    }
    return 0;
}


Measured memory_bytes: 16096
N = int(input())
As = [int(s) - 1 for s in input().split()]

Cs = [0 for _ in range(N)]
for A in As:
    Cs[A] += 1

a = [C * (C - 1) // 2 for C in Cs]
b = [(C - 1) * (C - 2) // 2 for C in Cs]

S = sum(a)

for A in As:
    print(S - a[A] + b[A])


Measured memory_bytes: 25644
package main

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

// input scanner
var sc = bufio.NewScanner(os.Stdin)

const (
	initialBufSize = 10e4
	maxBufSize     = 10e6
)

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

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

// util
func max(l []int) (int, int) {
	idx := 0
	ans := l[idx]
	for i, n := range l {
		if n > ans {
			idx = i
			ans = n
		}
	}
	return idx, ans
}

func min(l []int) (int, int) {
	idx := 0
	ans := l[idx]
	for i, n := range l {
		if n < ans {
			idx = i
			ans = n
		}
	}
	return idx, ans
}

// main
func main() {
	buf := make([]byte, initialBufSize)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	a := nextInt()
	b := nextInt()
	m := nextInt()
	ai := nextInts(a)
	bi := nextInts(b)
	var ans int
	_, minA := min(ai)
	_, minB := min(bi)
	ans = minA + minB
	for i := 0; i < m; i++ {
		x := nextInt()
		y := nextInt()
		c := nextInt()
		s := ai[x-1] + bi[y-1] - c
		if s < ans {
			ans = s
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {
	void solve() {
		Scanner scan = new Scanner(System.in);
		int r = scan.nextInt();
		if(r < 1200) {
			System.out.println("ABC");
		} else if(r < 2800) {
			System.out.println("ARC");
		} else {
			System.out.println("AGC");
		}
		scan.close();
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}


Measured memory_bytes: 35604
from collections import defaultdict
from bisect import bisect_right

S = input()
dS = defaultdict(list)
T = input()
for i in range(len(S)):
    dS[S[i]].append(i+1)
if not dS[T[0]]:
    print(-1)
    exit()
now = min(dS[T[0]])
ans = now
for i in range(1, len(T)):
    t = T[i]
    if not dS[t]:
        print(-1)
        exit()
    b = bisect_right(dS[t], now)
    if b == len(dS[t]):
        ans += len(S) - now
        now = min(dS[t])
        ans += now
    else:
        ans += dS[t][b] - now
        now = dS[t][b]
print(ans)

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

int main()
{
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);

    if(abs(a - c) <= d) {
        printf("Yes\n");
    } else if(abs(a - b) <= d && abs(b - c) <= d) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
//using namespace __gnu_pbds;
using namespace std;
typedef long long  L;

#define max_(x, y) (((x) > (y)) ? (x) : (y))
#define min_(x, y) (((x) < (y)) ? (x) : (y))
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Mx 2000001
#define inf 1e15
const L MOD = 1e9+7;
const double pi = 2 * acos (0.0);

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/


//typedef tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

L a1,a2,a3,b1,b2,b3,c,c1,c2,c3,d,d1,d2,d3,d4,d5,e1,e2,e3,f,h,k,l,m,n,m1,m2,n1,n2,o,p,p1,p2,p3,p4,
q,q1,q2,q3,q4,r,s,t,u,v,x,y,z,sum,mx=-inf,mn=inf,flg,flg1,flg2,id1,id2,id3,id4,lim;

L A[Mx],D[Mx],B[Mx];

void solve(){
  d=((x*x)+(y*y));
  if(d<= (m*m)){
    c++;
  }
}
int main()
{
    c=0;
    scanf("%lld%lld",&n,&m);
    for(L i=0;i<n;i++){
      scanf("%lld%lld",&x,&y);
      solve();
    }
    printf("%lld\n",c);
    return 0;
}
/// empty() lld I64d push_back() top() pop() insert() upper_bound() lower_bound() memset() max() min() scanf continue


Measured memory_bytes: 3780
// 解き直し.
// ABC 140解説.
// https://img.atcoder.jp/abc140/editorial.pdf
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報取得.
    int N, K;
    scanf("%d %d", &N, &K);
    char c[111111];
    scanf("%s", c);
    
    // 2. 解説通り.
    // 赤印: r0, r, rn
    int r0 = (c[0] == 'L') ? 1 : 0;     // c[0]     が 'L' の 場合は, r0 = 1 を 設定.
    int rn = (c[N - 1] == 'R') ? 1 : 0; // c[N - 1] が 'R' の 場合は, rn = 1 を 設定.
    int r = 0, ans = 0;
    for(int i = 1; i < N; i++){
        if(c[i - 1] == 'R' && c[i] == 'L') r++;   // 赤印加算.
        if(c[i - 1] == c[i])               ans++; // 'LL' or 'RR' の 場合.
    }
    // printf("r0=%d r=%d rn=%d ans=%d\n", r0, r, rn, ans);
    
    // 3. 幸福の最大人数を計算.
    // 操作K回で, 幸福である人を増加.
    while(1){
        if(K > 0 && r > 0)            ans += 2,  r--, K--;
        if(K > 0 && r == 0 && r0 > 0) ans++,    r0--, K--;
        if(K > 0 && r == 0 && rn > 0) ans++,    rn--, K--;
        // testcase_01等 の TLE対応.
        if(K == 0)                       break;
        if(r == 0 && r0 == 0 && rn == 0) break;
        if(ans >= N - 1)                 break;
    }
    
    // 4. 出力 ～ 後処理.
    // 幸福の最大人数は, N - 1人 の はず.
    ans = min(ans, N - 1);
    printf("%d\n", ans);
    return 0;
    
}

Measured memory_bytes: 384
/* 
 * Project: AtCoder Beginners Contest 154 B - I miss you...
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/06/30
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <cstring>
using namespace std;

char s[100];

void solve() {

    for (int i=0;i<strlen(s);i++) {
        printf("x");
    }
    printf("\n");
}

int main() {

    scanf("%s", s);

    solve();

}

Measured memory_bytes: 3172
s = gets.chomp
len = s.length
map = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
arr = Array.new(26,0)
26.times do |i|
  d = 0
  max = 0
  len.times do |j|
    if s[j] == map[i]
      max = d if max < d
      d = 0
    else
      d += 1
    end
  end
  max = d if max < d
  arr[i] = max
end
puts [arr.min,len/2].min

Measured memory_bytes: 14288
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

ll Largest_Rectangle_inHistogram(const vector<ll> &A){
    ll mx=0;
    stack<pll> s;
    for(ll i=0;i<A.size();i++){
        ll mi=i;
        while(!s.empty() && s.top().F>A[i]){
            pll w=s.top(); s.pop();
            mx=max(mx,w.F*(i-w.S));
            mi=w.S;
        }
        s.push({A[i],mi});
    }
    while(!s.empty()){
        pll w=s.top(); s.pop();
        mx=max(mx,w.F*((ll)A.size()-w.S));
    }
    return mx;
}


ll Largest_Rectangle(const vector<vector<bool>> &A){
    vector<vector<ll>> a(A.size(),vector<ll>(A[0].size(),0));
    ll count;
    for(int i=0;i<A[0].size();i++){
        count=0;
        for(ll h=0;h<A.size();h++){
            if(A[h][i]){count++;}
            else{count=0;}
            a[h][i]=count;
        }
    }
    ll mx=0;
    stack<pll> s;
    for(int i=0;i<A.size();i++){
        for(int t=0;t<A[0].size();t++){
            ll mi=t;
            while(!s.empty() && s.top().F>a[i][t]){
                pll w=s.top(); s.pop();
                mx=max(mx,w.F*(t-w.S));
                mi=w.S;
            }
            s.push({a[i][t],mi});
        }
        while(!s.empty()){
            pll w=s.top(); s.pop();
            mx=max(mx,w.F*((ll)A[0].size()-w.S));
        }
    }
    return mx;
}

ll Largest_Square(const vector<vector<bool>> &A){
    vector<vector<ll>> a(A.size(),vector<ll>(A[0].size(),0));
    ll count;
    for(int i=0;i<A[0].size();i++){
        count=0;
        for(ll h=0;h<A.size();h++){
            if(A[h][i]){count++;}
            else{count=0;}
            a[h][i]=count;
        }
    }
    ll mx=0;
    stack<pll> s;
    for(int i=0;i<A.size();i++){
        for(int t=0;t<A[0].size();t++){
            ll mi=t;
            while(!s.empty() && s.top().F>a[i][t]){
                pll w=s.top(); s.pop();
                ll x=min(w.F,t-w.S);
                mx=max(mx,x*x);
                mi=w.S;
            }
            s.push({a[i][t],mi});
        }
        while(!s.empty()){
            pll w=s.top(); s.pop();
            ll x=min(w.F,(ll)A[0].size()-w.S);
            mx=max(mx,x*x);
        }
    }
    return mx;
}


int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++){cin>>a[i];}
    cout<<Largest_Rectangle_inHistogram(a)<<endl;
    
    return 0;
}



Measured memory_bytes: 5344
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

vector<pair<int, int>> adj[100005];

static const int MAX = 100005;
static const int INFTY = (1 << 28);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int s, t;
int n;

int dist[MAX];

void dijkstra() {
	priority_queue<pair<int, int>> PQ;
	int color[MAX];
	
	REP(i, n) {
		dist[i+1] = INFTY;
		color[i+1] = WHITE;
	}

	dist[s] = 0;
	PQ.push(make_pair(0, s));
	color[s] = GRAY;

	while (!PQ.empty()) {
		pair<int, int> f = PQ.top(); PQ.pop();
		int u = f.second;
		color[u] = BLACK;

		//????°???????????????????????????????????????§???????????°??????
		if (dist[u] < f.first*(-1)) continue;

		REP(j, adj[u].size()) {
			int v = adj[u][j].first;
			if (color[v] == BLACK) continue;
			if (dist[v] > dist[u] + adj[u][j].second) {
				dist[v] = dist[u] + adj[u][j].second;
				PQ.push(make_pair(dist[v] * (-1), v));
				color[v] = GRAY;
			}
		}
	}

	/*
	REP(i, n) {
		cout << i+1 << " " << (dist[i+1] == INFTY ? -1 : dist[i+1]) << endl;
	}
	*/
}

int main() {
	int M;
	cin >> n >> M >> s >>t;

	int dam[100005];
	REP(i, n) {
		cin >> dam[i + 1];//1-indexed
	}

	REP(i, n) {
		if (i == 0) continue;
		adj[i+1].push_back(make_pair(i, 0));//1-indexed
	}
	int a, b;
	REP(i, M) {
		cin >> a >> b;
		adj[a].push_back(make_pair(b, dam[b]));
	}

	/*
	REP(i, n) {
		for (auto u : adj[i + 1]) {
			cout << u.first << ":" << u.second << " ";
		}
		cout << endl;
	}
	*/

	dijkstra();

	cout << dist[t] << endl;
	return 0;
}

Measured memory_bytes: 11696
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int w,a,b;
	cin>>w>>a>>b;
	if(a<b)
	{
		a+=w;
		if(a>b)
		{
			cout<<0;
		}
		else
		{
			cout<<abs(a-b);
		}
	}
	else
	{
		b+=w;
		if(b>a)
		{
			cout<<0;
		}
		else
		{
			cout<<abs(a-b);
		}
	}
	return 0;
}


Measured memory_bytes: 256
/**
 * @File   : atcoder.cpp
 * @Author : pasnger 
 * @Date   : 29/8/2020, 2:59:47 pm 
 */

#include<bits/stdc++.h>
using namespace std;
#define INF 1e17
#define int long long
#define f(i, a, b) for(int i=a; i<b; i++)
#define rf(i, a, b) for(int i=a; i>b; i--)
const int mod = 1e9+7;

#define deb(...) cerr << "[" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__) 
void DBG() {
  cerr << "]\n";
}
template<typename T, typename ...Args> void DBG(T first, Args... args) {
  cerr << first; if (sizeof...(args))cerr<<", "; DBG(args...);
}

int mul(int x,int y){
    int res = x*y;
    if(res >= mod)res%=mod;
    return res;
}

int add(int x, int y){
    int res = x+y;
    if(res >= mod)res-=mod;
    return res;
}
int sub(int x, int y){
    int res = x-y;
    if(res<0)res+=mod;
    return res;
}

/////////////////////////// GLOBAL ///////////////////////////
const int N = 2e5+10;
vector<int> adj[N];
int cnt = 0;
int m;
int visited[N];
/////////////////////////// GLOBAL ///////////////////////////
void dfs(int root, int parent){
  if(!adj[root].empty()){
    // deb(root, visited[root], cnt);
    for(auto ele: adj[root]){
      if(parent != ele && visited[ele]==0){
        cnt++;
        visited[ele] = 1;
        dfs(ele, root);
      }
    }
  }
}

void solve() {
  int n, m;
  cin>>n>>m;
  int a, b;
  f(i, 0, m){
    cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  fill(visited, visited+N, 0);
  m = 0;
  f(i, 1, n+1){
    cnt = 1;
    visited[i] = 1;
    dfs(i, -1);
    m = max(m, cnt);
    // deb(m, cnt);
  }
  cout<<m<<"\n";

}


int32_t main() {
  #ifndef ONLINE_JUDGE
  clock_t tStart = clock();
  freopen("in.txt", "r", stdin);
  //freopen("output.txt","w",stdout);
  #endif 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t=1;
  // cin >> t;
  for (int tt=1;tt<=t;tt++) {
    //cout << "Case #"<<tt<<": ";
    solve();
  }
  #ifndef ONLINE_JUDGE
    cerr << "\nRun Time -> "<<(double)(clock()-tStart)/CLOCKS_PER_SEC <<" sec\n";
  #endif
}


Measured memory_bytes: 25420
def main():
    n = int(input()) % 10
    hon = [2, 4, 5, 7, 9]
    pon = [0, 1, 6, 8]
    bon = [3]

    if n in hon:
        print("hon")
    elif n in pon:
        print("pon")
    elif n in bon:
        print("bon")


if __name__ == '__main__':
    main()


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

using namespace std;

#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container), element) != container.end())
#define INF 0x3f3f3f3f
#define f1(i, n) for (int i = 0; i < n; ++i)
#define f2(i, n) for (int i = 1; i < n; ++i)
#define f3(i, start, end) for (int i = start; i < end; ++i)
#define ll long long
typedef pair<int, int> iPair;
const double epsilon = 1e-7;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int x;
  cin >> x;
  int res;
  if (x < 600)
    res = 8;
  else if (x < 800)
    res = 7;
  else if (x < 1000)
    res = 6;
  else if (x < 1200)
    res = 5;
  else if (x < 1400)
    res = 4;
  else if (x < 1600)
    res = 3;
  else if (x < 1800)
    res = 2;
  else res = 1;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include <vector>
#include<queue>
#include<map>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<bitset>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define vsort(v) sort(v.begin(), v.end())
#define rv(v) reverse(v.begin(), v.end())
#define ll long long
using vll = vector<ll>;
using Graph = vii;
const ll MOD = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	string ans = "No";
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (i * j == n) {
				ans = "Yes";
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <iomanip>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
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; }
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

#define MAX_N 10
int n;
int p[MAX_N], q[MAX_N];

void input() {
  cin >> n;
  rep(i, 0, n) cin >> p[i];
  rep(i, 0, n) cin >> q[i];
}

string to_str(int a[]) {
  string rsl = "";
  rep(i, 0, n) rsl += to_string(a[i]);
  return rsl;
}

void solve() {
  string P = to_str(p);
  string Q = to_str(q);
  int array[n];
  rep(i, 0, n) array[i] = i + 1;
  vector<string> vs;
  do {
    string s = "";
    rep(i, 0, n) {
      s += to_string(array[i]);
    }
    vs.push_back(s);
  }while(next_permutation(array, array + n));

  vsort(vs);
  int a = 0, b = 0;
  rep(i, 0, vs.size()) {
    if(vs[i] == P) a = i;
    if(vs[i] == Q) b = i;
  }
  cout << abs(a - b) << endl;
}

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

  input();
  solve();
}



Measured memory_bytes: 2424
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

M,D = IL()

cnt = 0
for m in range(1,M+1):
  d2 = 0
  for d in range(20,D+1):
    d1 = str(d)[-1]
    d10 = str(d)[-2]
    if (int(d1) >= 2) and (int(d10) >= 2) and (int(d1)*int(d10) == m):
      cnt += 1

print(cnt)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 int main(){
   int a1,a2,a3;
   cin>>a1>>a2>>a3;
   if(a1+a2+a3>=22){
     cout<<"bust"<<endl;
   }else{
     cout<<"win"<<endl;
   }
 }

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

int main() {
    string ans = "Yes";
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    int count = 0;
    while(A >= B) {
        B *= 2;
        count++;
    }
    while(B >= C) {
        C *= 2;
        count++;
    }
    if(K < count)
        ans = "No";

    cout << ans << endl;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <cctype>
#include<math.h>
#include <iomanip>  
using namespace std;
int main() {
	int n, m, p[100000], wa = 0, ac = 0, pw[100000];
	bool pa[100000];
	string  s[100000];
	cin >> n >> m;
	for (int i = 0; i < m; ++i)cin >> p[i] >> s[i];
	for (int i = 0; i < 100000; ++i)pw[i] = 0;
	for (int i = 0; i < 100000; ++i)pa[i] = false;
	for (int i = 0; i < m; ++i) {
		if (s[i] == "WA") {
			pw[p[i] - 1]++;
		}

		else if (pa[p[i] - 1] == false){
			pa[p[i] - 1] = true;
			ac++;
			wa += pw[p[i] - 1];
		}
	}
	
	//cout << pw[0] << pw[1] << pw[2] << pa[0] << pa[1] << pa[2] << endl;
	cout << ac << ' ' << wa << endl;

}

Measured memory_bytes: 6656
o = list(input())
rev = [ 0 for i in range(len(o)) ]

for i in range(1, len(o)+1):
  rev[i-1] = o[i * -1]
  if i == len(o)+1:
    rev[-1] = o[0]

ans = 0
for j in range(len(o)):
  if str(o) == str(rev):
    break

  if o[j] != rev[j]:
    o[j] = rev[j]
    rev[(j+1) * -1] = rev[j]
    ans += 1


print(ans)

Measured memory_bytes: 3064