akhauriyash/Code-Regression huggingface dataset:
/* coordinate_compress_2D.cpp
    2Dの座標圧縮を行う

    verified: [AOJ] DSL_4_A Union of Rectangles
        http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_4_A&lang=ja
*/

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

/* compress
    (X1,Y1),(X2,Y2)という二点で表されるもの（長方形や直線など）について、行か列の片方（X1とX2 or Y1とY2）を座標圧縮する（副作用）
    返り値: ソートされ重複要素を除いた値
    計算量: O(n log n)
*/
template <typename T>
vector<T> compress(vector<T> &C1, vector<T> &C2) {
    vector<T> vals;
    int N = (int)C1.size();
    for (int i = 0; i < N; i++) {
        for (T d = 0; d <= 0; d++) {  // その位置と、一つ隣を確保(隣を確保しないと空白が埋まってしまうことがある)
            T tc1 = C1[i] + d;
            T tc2 = C2[i] + d;
            vals.push_back(tc1);
            vals.push_back(tc2);
        }
    }
    // ソート
    sort(vals.begin(), vals.end());
    // 隣り合う重複を削除(unique), 末端のゴミを削除(erase)
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 0; i < N; i++) {
        C1[i] = lower_bound(vals.begin(), vals.end(), C1[i]) - vals.begin();
        C2[i] = lower_bound(vals.begin(), vals.end(), C2[i]) - vals.begin();
    }
    return vals;
}

int main() {
    int N;
    cin >> N;
    vector<long long> X1(N), Y1(N), X2(N), Y2(N);
    for (int i = 0; i < N; i++) {
        cin >> X1.at(i) >> Y1.at(i) >> X2.at(i) >> Y2.at(i);
    }
    vector<long long> X = compress(X1, X2);
    vector<long long> Y = compress(Y1, Y2);

    int w = (int)X.size();
    int h = (int)Y.size();
    vector<vector<int>> G(w, vector<int>(h));
    // imos法で塗りつぶし
    for (int i = 0; i < N; i++) {
        G[X1[i]][Y1[i]]++;
        G[X2[i]][Y2[i]]++;
        G[X1[i]][Y2[i]]--;
        G[X2[i]][Y1[i]]--;
    }
    for (int x = 1; x < w; x++) {
        for (int y = 0; y < h; y++) {
            G[x][y] += G[x - 1][y];
        }
    }
    for (int x = 0; x < w; x++) {
        for (int y = 1; y < h; y++) {
            G[x][y] += G[x][y - 1];
        }
    }

    long long ans = 0;
    for (int x = 0; x < w - 1; x++) {
        for (int y = 0; y < h - 1; y++) {
            if (G[x][y]) {
                ans += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y]);
            }
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 65700
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

using namespace std;

int main() {
    int N, W, i, j;
    cin >> N >> W;
    int v[N];
    int w[N];
    rep(i, N) cin >> v[i] >> w[i];

    // dp[i][w_i]: i番目までの商品で総重量 w_i 以下となるときの最大価値
    // dp[i+1][w_i]: max(dp[i][W - w_i] + v[i+1], dp[i][w_i])
    int dp[N+1][W+1];
    rep(i, N+1) rep(j, W+1) dp[i][j] = 0;

    for(i = 1; i <= N; i++) {
        int v_i = v[i-1];
        int w_i = w[i-1];

        // cout << i << "th: val: " << v_i << " wei: " << w_i << endl;

        for (int weight = 1; weight <= W; weight++) {
            if (w_i > weight) {
                dp[i][weight] = dp[i-1][weight];
            } else {
                dp[i][weight] = max(dp[i-1][weight-w_i] + v_i, dp[i-1][weight]);
            }
        }
    }

    // rep(i, N+1) {
    //     cout << i << "th: ";
    //     rep(j, W+1) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << dp[N][W] << endl;

    return 0;
}



Measured memory_bytes: 7040
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
 
int main() {
    set<char> V = {'a', 'e', 'i', 'o', 'u'};
    char c;
    cin >> c;
    if(V.find(c) != V.end()) cout << "vowel";
    else cout << "consonant";
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n, sum=0;
  cin >> n;
  int a[n+1];
  for(int i=1;i<=n;i++)
  {
    	cin >> a[i];
    	sum+=a[i];
  }
  sort(a+1,a+n+1);
  sum-=a[n]/2;
  cout<<sum<<endl;
  return 0;
}


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

using namespace std;

int main(void){
    int h,w;
    while(true)
    {
        cin>>h>>w;
        if(h==0&&w==0)break;
        for(int i=0;i<h;i++)
        {
            for(int i=0;i<w;i++)
            {
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
    }
}



Measured memory_bytes: 3108
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

struct D {
	vector<int> v;
	int cost;

	D(vector<int> t, int c) {
		v.clear();
		copy(t.begin(),t.end(),back_inserter(v));
		cost = c;
	}

	bool operator < (const D &data) const {
		return cost < data.cost;
	}

	bool operator > (const D &data) const {
		return cost > data.cost;
	}
};

int n, cost[10][10];
map< vector<int> , int> m;

void dijkstra() {
	priority_queue<D ,vector<D>, greater<D> > que;

	vector<int> t(n);
	rep(i, n) t[i] = i;

	que.push(D(t, 0));
	m[t] = 0;

	while(que.size()) {
		D data = que.top();
		que.pop();

		vector<int> v = data.v;
		int c = data.cost;


		if(m[v] < c) continue;

		rep(i, v.size()) {
			REP(j, i+1, v.size()) {
				vector<int> t2(v.begin(), v.end());
				swap(t2[i], t2[j]);
				int nc = c + cost[i][j];

				if(m[t2] > nc) {
					m[t2] = nc;
					que.push(D(t2, nc));
				}
			}
		}
	}
}

int main() {
	cin >> n;

	memset(cost, 0, sizeof(cost));
	rep(i, n) {
		rep(j, n) cin >> cost[i][j];
	}

	vector<int> v(n);
	rep(i, n) v[i] = i;

	do {
		m[v] = INF;

	}while(next_permutation(v.begin(), v.end()));

	dijkstra();

	int ans = 0;
	map< vector<int>, int>::iterator ite;
	for(ite = m.begin(); ite != m.end(); ite++) {
		ans = max(ans, ite->second);
		// rep(i, ite->first.size()) cout << ite->first[i] << " ";
		// cout << " c:" << ite->second << endl;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 12148
#include <iostream>
#include <string>
bool is_prime(int x) {
    int divcnt = 0;
    for (int i = 1; i <= x; i += 2)
    {
        if(x%i == 0) {
            divcnt++;
        }
    }

    if(divcnt == 2) {
        return true;
    } else {
        return false;
    }
}

int main()
{
    int x;
    std::cin >> x;
    int ans;
    if(x%2 == 0 && x != 2) {
        x++;
    }

    while (1)
    {

        if(is_prime(x) || x == 2) {
            ans = x;
            break;
        }

        x += 2;
    }

        std::cout << ans << "\n";
}

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

using namespace std;

int main()
{
  long long int flag = 0;
  string q;
  cin >> q;
  while(1)
  {
    string w;
    cin >> w;
    if(w == "END_OF_TEXT")
    break;
    for(int i = 0;i < w.size();i++)
    {
      if(w[i] >= 'A'&&w[i] <= 'Z')
      {
        w[i] += 32;
      }
    }
    if(w == q)
    {
      flag++;
    }
  }
  cout << flag << endl;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

const long long INF = 1LL << 58;

// vector v において、x の前方と後方の index を求める
template<class T>
int former(const vector<T> &v, T x) {
    return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
}

template<class T>
int latter(const vector<T> &v, T x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

int main() {
    int A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A), t(B);
    rep(i, A) cin >> s[i];
    rep(i, B) cin >> t[i];
    s.push_back(INF), s.push_back(-INF), sort(s.begin(), s.end());
    t.push_back(INF), t.push_back(-INF), sort(t.begin(), t.end());

    rep(_, Q) {
        ll x;
        cin >> x;
        ll res = INF;

        // 最初に s (前方に行くか後方に行くか場合分け)
        rep(i, 2) {
            ll first = (i ? s[former(s, x)] : s[latter(s, x)]);
            // 次に t (現在地の前後を見る)
            rep(j, 2) {
                ll second = (j ? t[former(t, first)] : t[latter(t, first)]);
                chmin(res, abs(x - first) + abs(first - second));
            }
        }
        // 最初に t (前方に行くか後方に行くか場合分け)
        rep(i, 2) {
            ll first = (i ? t[former(t, x)] : t[latter(t, x)]);
            // 次に t (現在地の前後を見る)
            rep(j, 2) {
                ll second = (j ? s[former(s, first)] : s[latter(s, first)]);
                chmin(res, abs(x - first) + abs(first - second));
            }
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 2912
N,K,Q = map(int,input().split())
life = [K for i in range(N)]
damage = [0 for i in range(N)]

for i in range(Q):
    tmp = int(input())
    damage[tmp-1] += 1

sum_damage = sum(damage)

for j in range(N):
    if sum_damage - damage[j] >= K:
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 5500
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

#define nl     '\n'
#define F      first
#define S      second
#define pb     push_back
#define sz(x)  (int)x.size()
#define all(x) x.begin(), x.end()

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

const int N    = (int)1e3 + 23   ;
const int K    = (int)500        ;
const int maxn = (int)2e9        ;
const int mod  = (int)1e9 + 7    ;
const ll inf   = 1ll * 1e18 + 123;

int n;
int ans ;
void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int q; cin >> q;
        ans += (q - 1);
    }
    cout << ans;

}
int main(){

    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #ifdef LOCAL
       freopen("in.txt", "r", stdin);
    #endif

    int q = 1;
    //cin >> q;
    while(q--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
prev = -1
ans = []
for i, a in enumerate(A):
    if prev == a:
        ans.append(a)
        prev = -1
        if len(ans) == 2:
            break
    else:
        prev = a
if len(ans) == 2:
    print(ans[0] * ans[1])
else:
    print(0)


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

int main() {
  int n ;
  cin >> n;
  int64_t max_x = 0;
  int64_t min_x = 1000000000;
  for(int i = 0; i < n; i++){
    int64_t x;
    cin >> x;
    max_x = max(x, max_x);
    min_x = min(x, min_x);
  }
  cout << max_x - min_x << endl;
}


Measured memory_bytes: 256
from bisect import bisect_right

n = int(input())
s = input()

ans = 0

pos = [
    [] for _ in range(10)
]


def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    return None


for j in range(n):
    pos[int(s[j])].append(j)

for i in range(1000):
    t = '000' + str(i)
    t = t[-3:]
    a, b, c = map(int, tuple(t))

    p = -1
    p = find_gt(pos[a], p)
    if p is None:
        continue
    q = find_gt(pos[b], p)
    if q is None:
        continue
    r = find_gt(pos[c], q)
    if r is None:
        continue

    ans += 1

print(ans)


Measured memory_bytes: 4328
#include <stdio.h>

int main(void){

	int a,b ;
	char op;
while(1){
    scanf("%d %c %d", &a, &op, &b);

	if( op == '+'){
	printf("%d\n", a+b );
	}else if(op == '-'){
	printf("%d\n", a-b );
	}else if(op == '*'){
	printf("%d\n", a*b );
	}else if(op == '/'){
	printf("%d\n", a/b );
	}else if(op == '?') break;
    }
    return 0;
}

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	string s, t;
	cin >> s >> t;

	sort(all(s));
	sort(all(t));
	reverse(all(t));

	cout << (s < t ? "Yes" : "No") << endl;
	return 0;
}

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


#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define pii pair<int,int>
#define ll long long
#define el '\n'

using namespace std;

int n,m;
vector <int> v1,v2;

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

    v1.pb(-1);v2.pb(-1);
    cin >> n >> m;
    

    if (n>m){
        for (int i=0;i<n;i++){
            int tm;
            cin >> tm;
            v2.pb(tm);
        }

        for (int i=0;i<m;i++){
            int tm;
            cin >> tm;
            v1.pb(tm);
        }

        swap(n,m);
    } else {
        for (int i=0;i<n;i++){
            int tm;
            cin >> tm;
            v1.pb(tm);
        }

        for (int i=0;i<m;i++){
            int tm;
            cin >> tm;
            v2.pb(tm);
        }
    }

    ll dp[n+1][m+1];
    for (int i=0;i<n+1;i++){
        for (int j=0;j<m+1;j++){
            if (v1[i]==v2[j]) dp[i][j]=1;
            else dp[i][j]=0;
        }
    }

    ll ad[n+2][m+2],ton[m+2];
    for (int i=0;i<n+2;i++){
        for (int j=0;j<m+2;j++){
            ad[i][j]=0;
        }
    }
    for (int i=0;i<m+2;i++) ton[i]=0;


    for (int i=1;i<=n;i++){
        ll cur=0;
        for (int j=1;j<=m;j++){
            cur=(cur+ton[j])%MOD;
            if (dp[i][j]>0)
                dp[i][j]=(dp[i][j]+cur)%MOD;
        }
        for (int j=0;j<m;j++){
            ton[j+1]=(ton[j+1]+dp[i][j])%MOD;
        }
    }
    
    ll tot=0;
    for (int i=0;i<=n;i++){
        for (auto x : dp[i]) tot=(tot+x)%MOD;
    }

    cout << tot << el;

    return 0;
}

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

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n;
    string st;
    cin >> n >> st;
    int i=0,j=n-1,ans=0;
    while(1){
    	while(i<j and st[i]=='R')i++;
    	while(j>i and st[j]=='W')j--;
    	if(i>=j)break;
    	swap(st[i],st[j]);
    	ans++;
    }
    cout << ans;
}


Measured memory_bytes: 3692
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <climits>
using namespace std;

#define REPI(i,a,b) for (ll i=(a);i<(b);i++)
#define REP(i,n) REPI(i,0,n)

typedef long long int ll;

int SURP = 1000000007;

int ceil(int a,int b){
	return (a+b-1)/b;
}

int main(){
	ll N,M;
	cin >> N >> M;

	ll min = 1;
	REPI(i,1,(ll)sqrt(M)+1){
		if(M%i == 0){
			ll a1 = M/i;
			ll a2 = i;
			if(a1 > min && a1 <= M/N){
				min  = a1;
			}
			if(a2 > min && a2 <= M/N){
				min  = a2;
			}
		}
	}

	cout << min << endl;
	return 0;
}


Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * b.cc: 
 */

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

using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef long long ll;

/* global variables */

int as[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> as[i];

  ll cnt = (as[0] >> 1);
  as[0] &= 1;
  for (int i = 1; i < n; i++) {
    if (as[i - 1] > 0 && as[i] > 0) cnt++, as[i]--;
    cnt += (as[i] >> 1);
    as[i] &= 1;
  }

  printf("%lld\n", cnt);
  return 0;
}


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


int main(){
  int n;
  cin >> n;
  vector<pair<ll,ll>> st(n);
  for(int i=0;i<n;++i){
    ll s,t;
    cin >> s >> t;
    st[i]=make_pair(t,s);
  }
  sort(st.begin(),st.end());
  ll fi=st[0].first;
  //ll start=st[0].first;
  int ans=1;
  for(int i=1;i<n;++i){
    if(st[i].second>fi){
      ans++;
      fi=st[i].first;
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 4388
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
 size_t strlen(const char *s);
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::vector<int> graph[10050];//graph頂点数のsize
const int N=100010;
const int P=1000000007;
long long int compare_int(const void *a, const void *b)
{
    return *(long long int*)a - *(long long int*)b;//a-b昇順
}
//絶対値
int ze(int a, int b){
	if(a>b){
		return a-b;
	}else{
		return b-a;
	}
}
// a^n mod 
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod 
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

//mod掛け算
long long mt(long long a, long long b, long long mod){
	return (a*b)%mod;
}

//メモ
//	cout<<(n-2)*180<<endl;
//	string s="hoge";
//	cout<<ans<<endl;
//	int  n  ,a  ,b  ,c  ,d  ,e  ,f  ;
//	cin  >>n  >>a  >>b  >>c  >>d  >>e  >>f  ;

/*
	memset(b, '\0', sizeof(b));
初期化*/


/*
	len = strlen(s);
文字列長さ*/


/*
	string s;
	s.size()
*/


/*ソート
	qsort(b, 10, sizeof(int), compare_int);
*/


/*
	char s[N];
	strlen(s)
/*
	if(  <  )puts("Yes");
	else puts("No");
*/
/*文字列比較
if(strcmp(name[i],s)==0)
*/
/*
	graph[a].push_back(b);//graph[a][i番目に入れた]==b
	graph[j].size()	//forで回すときとか

*/


int main(){
	long long int n, ans=0;
	long long int x[N];
	cin>>n;
	rep(i,n){
		cin>>x[i];
	}
	long long int seki=1;
	rep(i,n-1){
		seki=mt(seki,i+1,P);
	}
	rep(i,n-1){
		ans=( ans+mt(mt( (x[n-1]-x[i]),seki,P ),modinv(i+1,P),P) )%P;
	}


	cout<<ans<<endl;

}

Measured memory_bytes: 1280
import sys


N,X=[int(i) for i in input().split(" ")]
x=[abs(int(i)-X) for i in input().split(" ")]
minimum=min(x)




yakusuu=[]
for i in range(1,minimum+1):
    if minimum%i==0:
        yakusuu.append(i)
        yakusuu.append(minimum//i)
    if (minimum/i)+1<i:
        break
yakusuu=sorted(yakusuu)[::-1]
for i in yakusuu:
    flag=True
    for j in x:
        if j%i!=0:
            flag=False
    if flag:
        print(i)
        sys.exit()


Measured memory_bytes: 14248
//****** @mdazmat9 **********
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define EB emplace_back
#define PB push_back
#define endl "\n"
#define MOD2 1000000007
#define MOD 998244353
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
typedef pair<int, int> pr;
typedef vector<int> VI;
typedef vector<pr> VP;
typedef vector<string> VS;
typedef vector<vector<int>> VV;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
int fast_pow(int x, int y, int p);
const int MAX_SIZE = 200001;
int n;VI a;
int dp[3001][3001];
int rec(int i,int j){
    if(i>j)return 0;
    int& ans=dp[i][j];
    if(ans!=-1)return ans;
    int op1=a[i]-rec(i+1,j);
    int op2=a[j]-rec(i,j-1);
    ans=max(op1,op2);
    return ans;
}
void solve() {
    cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        a.EB(x);
    }
    memset(dp,-1, sizeof(dp));
    cout<<rec(0,n-1);
}

int32_t main() {
    IOS;
    int test = 1;
//    cin >> test;
    for(int i=1;i<=test;i++){
//        cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}
int fast_pow(int x, int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}


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

#define ll long long
#define endl '\n'

const int maxn = 10005;
vector< int > v(maxn);

int find(int a){
	if(a == v[a]) return a;
	return v[a] = find(v[a]);
}

void merge(int a, int b){
	a = find(a), b = find(b);
	if(a == b) return;
	v[b] = a;
}

void solve(){
	int n, q; cin>>n>>q;
	for(int i = 1; i<=n; i++) v[i] = i;
	for(int i = 0; i<q; i++){
		int a, x, y; cin>>a>>x>>y;
		if(a){
			cout<<(find(x) == find(y))<<endl;
		}else{
			merge(x, y);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t1 = 1; //cin>>t1;
	while(t1--){
		solve();
	}
	return 0;
}



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

// iterator
#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

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

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

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

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

typedef long long int lli;
typedef pair<lli, lli> P;


lli t[200001];

int main() {
    lli n;
    cin1(n);
    lli a[n+1];
    REPE(i, 1, n) {
        cin >> a[i];
    }

    for (lli i = n; i >= 1; i--) {

        lli x = i / n;
        lli count = 0;
        for (lli j = i+i; j <= n; j += i) {
            count += t[j];
        }
        if (a[i] == 1) {
            if (count % 2 == 0)
                t[i] = 1;
        }
        else {
            if (count % 2 == 1)
                t[i] = 1;
        }
    }
    lli ans = 0;
    REPE(i, 1, n) {
        if (t[i] > 0)
            ans++;
    }
    cout << ans << endl;
    if (ans == 0)
        return 0;

    REPE(i, 1, n) {
        if (t[i] > 0)
            cout << i << " ";
    }
    cout << endl;
}




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

int main(){
    std::string S, T;
    std::cin >> S >> T;
    for(int i = 0; i < S.size(); i++){
        if(S[i] != T[i]){
            std::cout << "No" << std::endl;
            return 0;
        }
    }
    std::cout << "Yes" << std::endl;
    return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 10000000000000000
#define endl '\n'
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; }
using namespace std;

class LazyRMQ{
private:
    int n;
    vector<int> node,lazy;
    vector<bool> islazy;
    bool ismax;
    inline int pick(int x, int y){
        if(ismax)return max<int>(x,y);
        else return min<int>(x,y);
    }
    void update2(int a, int b, int v, int k, int l, int r){
        eval(k,l,r);
        if(a==l and b==r){
            islazy[k]=true;
            lazy[k]=v;
            eval(k,l,r);
            return;
        }
        int m=(l+r)/2;
        if(b<=m)update2(a,b,v,k*2+1,l,m);
        else if(a>=m)update2(a,b,v,k*2+2,m,r);
        else{update2(a,m,v,k*2+1,l,m); update2(m,b,v,k*2+2,m,r);}  
        node[k]=pick(node[k*2+1],node[k*2+2]);
    }
    int get2(int a, int b, int k, int l, int r){
        eval(k,l,r);
        if(a==l and r==b)return node[k];
        int m=(l+r)/2;
        if(b<=m)return get2(a,b,k*2+1,l,m);
        else if(a>=m)return get2(a,b,k*2+2,m,r);
        else return pick(get2(a,m,k+2+1,l,m),get2(m,b,k+2+2,m,r));
    }
public:
    LazyRMQ(vector<int> vec, bool is_max){
        ismax=is_max; int tmp_size=vec.size();
        n=1; while(n<tmp_size)n*=2;
        node.resize(n*2-1,-pick(-INF,INF));
        for(int i=0; i<tmp_size; i++)node[i+n-1]=vec[i];
        for(int i=n-2; i>=0; i--)node[i]=pick(node[i*2+1],node[i*2+2]);
        lazy.resize(n*2-1,-pick(-INF,INF));
        islazy.resize(n*2-1,false);
    }
    void eval(int k, int l, int r){
        if(islazy[k]){
            node[k]=pick(node[k],lazy[k]);
            if(r-l>1){
                lazy[k*2+2]=pick(lazy[k*2+2],lazy[k]);
                lazy[k*2+1]=pick(lazy[k*2+1],lazy[k]);
                islazy[k*2+2]=islazy[k*2+1]=true;
            }
            islazy[k]=false;
            if(ismax)lazy[k]=-INF;
            lazy[k]=-pick(-INF,INF);
        }
    }
    void update(int a, int b, int v){
        update2(a,b,v,0,0,n);
    }
    int get(int a, int b){
        return get2(a,b,0,0,n);
    }
};

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

    int n,q; cin>>n>>q;
    LazyRMQ sg(vector<int>(q,INF),false);
    vector<int> s(n),t(n),x(n),d(q);
 
    rep(i,n){
        cin>>s.at(i)>>t.at(i)>>x.at(i);
    }
    rep(i,q){
        cin>>d.at(i);
    }
 
    rep(i,n){
        int S=s.at(i),T=t.at(i),X=x.at(i);
        int lf=lower_bound(all(d),S-X)-d.begin();
        int ri=lower_bound(all(d),T-X)-d.begin();
        if(lf>=ri)continue;
        sg.update(lf,ri,X);
    }
 
    rep(i,q){
        int ans=sg.get(i,i+1);
        if(ans==INF)cout<<-1<<endl;
        else cout<<ans<<endl;
    }

}

Measured memory_bytes: 16484
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
// << fixed << setprecision
// --------------------------------------
int n;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;

  vector<int> v(n);
  vector<int> nv(n);
  vector<int> rv(n);

  REP(i, n) cin >> v[i];

  int s = 0, rs = 0;
  REP(i, n) {
    s = v[i] ^ s;
    rs = v[n - i - 1] ^ rs;
    nv[i] = s;
    rv[n - i - 1] = rs;
  }

  REP(i, n) {
    int l = 0, r = 0;
    if(i > 0) l = nv[i - 1];
    if(n - 1 > i) r = rv[i + 1];
    cout << (l ^ r) << " ";
  }
  cout << endl;
}


Measured memory_bytes: 5544
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=61
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef pair<int,int> pairii;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
int main() {
  int H,W;
  cin>>H>>W;
  int h,w;
  cin>>h>>w;
  cout<<H*W-h*W-H*w+h*w<<endl;
}

Measured memory_bytes: 256
// Created by Kshitij Anand NSIT
#include <bits/stdc++.h>


using namespace std;


#define int long long
#define pb push_back
#define P pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define vc vector<char>
#define vb vector<bool>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mp(a, b) make_pair(a, b)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define fill(arr,val) memset(arr,val,sizeof(arr))
#define db(x)  cout<<#x<<" : "<<x<<endl


const int N = 1000000007;

void solve(){

    int n,a,b,c, ans=0, count=0, sum=0;
    // cin>>n;
    int arr[5];
    for(int i=0;i<5;i++){
      cin>>arr[i];
      if(arr[i] == 0){
      	ans = i+1;
      }
    }

    cout<<ans<<endl; 
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    
  //  int t; cin>>t; while(t--)
    {     
      solve();
    }

  return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>

int main()
{
	int x = 0;
	int i;
	
	for(i = 1;;i++)
	{
		scanf("%d",&x);
		if(x == 0)
		{
			break;
		}
		printf("Case %d: %d\n",i,x);
	}
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
const double PI=3.14159265358979323846;
//#define int long long int
signed main(){
    int n,k;cin>>n>>k; 
    vector<int> v(n,0);
    int d;
    for(int i=0;i<k;i++){
        cin>>d;
        for(int j=0;j<d;j++){
            int a;
            cin>>a;
            v[a-1]++;
        }
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(v[i]==0)sum++;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3628
// Author : MohamedSameh
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<stack>
#include<deque>
#include <sstream>
#include <string.h>

typedef long long ll ;
// random in each run --> srand(time(NULL));

#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SZ(a) (int)a.size()
#define IN(n) scanf("%d" , &n )
#define debug(x) cout<<#x<<" = { "<<x<<" }\n"
void fo (){fflush(stdout);}
using namespace std;
int a ,b ;
int main ()
{
  int n , k ;
  scanf ("%d%d" , &n , &k );
  int mx = ((n-2) * (n-1)) / 2  ;
  if (k > mx )
  {
    printf ("-1\n");
    return 0 ;
  }
  vector <pair<int,int>> ans ;
  for (int i = 2; i<= n ; i++)ans.pb({1,i});
  int v = 2 ;
  while (k!=mx )
  {
    for (int i = v+1 ; k != mx && i <= n ; i++,mx--)
    {
      ans.pb({v,i});
    }
    v++;
  }
  printf ("%d\n" , SZ(ans));
  for (int i =0 ; i < SZ(ans) ;i++)
  {
    printf ("%d %d\n" , ans[i].f , ans[i].s );
  }
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const int MOD = 1e9+7;


#define REP(i, N) for (int i = 0; i < (N); i++)
#define REPP(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((int)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<int>>

using namespace std;

ll Euclid(ll A, ll B){
    if(B == 0) return A;
    return Euclid(B,A%B);
}



int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<ll> sos;
    sos.push_back(1);
    sos.push_back(2);

    
    ll A,B;
    cin >> A >> B;

    ll AB = Euclid(A,B);

    // ABの素因数の個数+1が今回求めたい答えとなる
    int step = 2;
    ll count = 0;
    bool already=false;
    while(AB != 1){
        if(AB % step == 0){
            if(!already){
                count++;
                already = true;
            }
            AB /= step;
        }else if(step > sqrt(AB)){
            count++;
            break;
        }
        else{
            step++;
            already = false;
        }

    }
    cout << count+1 << endl;

    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N = int(input())
S = [input().strip() for _ in range(N)]

d = {}
for s in S:
    d.setdefault(s, 0)
    d[s] += 1

dmax = max(d.values())

dmax_list = [k for k, v in d.items() if v == dmax]
for d in sorted(dmax_list):
    print(d)

Measured memory_bytes: 35216
def witness(a,n,t,u):
    x=pow(a,u,n)
    for _ in range(t):
        y=(x*x)%n
        if y==1 and x!=1 and x!=(n-1):
            return True
        x=y
    return y!=1

def is_probably_prime(n,witnesses):
    t=1
    u=n>>1
    while u&1==0:
        t+=1
        u>>=1
    assert(2**t*u==n-1)
    for a in witnesses:
        if a<n and witness(a,n,t,u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n&1)) and n!=2) or (n<2) or ((n%3==0) and (n!=3)):
        return False
    elif n<=3:
        return True
    else:
        return is_probably_prime(n,[2,7,61])

n=10**5
P=[0]*(n+1)
for i in range(n):
    if is_definitely_prime(i+1) and is_definitely_prime((i+2)//2):
        P[i+1]=P[i]+1
    else:
        P[i+1]=P[i]
q=int(input())
Q=[tuple(map(int,input().split())) for _ in range(q)]
for l,r in Q:
    ans=P[r]-P[l-1]
    print(ans)

Measured memory_bytes: 18120
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
constexpr i64 MOD = 998244353;

i64 modpow(i64 a, i64 n, i64 mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        i64 t = modpow(a, n / 2, mod);
        return t * t % mod;
    }
    return a * modpow(a, n - 1, mod) % mod;
}

struct Point {
    int x, y;
};

struct Line {
    int x, y;
    int dx, dy;

    bool operator==(const Line rhs) const {
        if (dx * rhs.dy != dy * rhs.dx) {
            return false;
        }
        return (x - rhs.x) * dy == (y - rhs.y) * dx;
    }
};

Line make_line(Point a, Point b) {
    return {a.x, a.y, b.x - a.x, b.y - a.y};
}

int main() {
    int n;
    cin >> n;
    i64 ans = modpow(2, n, MOD) - 1 - n - n * (n - 1) / 2;
    vector<Point> ps;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        ps.push_back({x, y});
    }

    vector<Line> ls;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int ok = 1;
            Line line = make_line(ps[i], ps[j]);
            for (Line& l: ls) {
                if (l == line) {
                    ok = 0;
                    break;
                }
            }
            if (ok) {
                int cnt = 0;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    if (line == make_line(ps[i], ps[k])) {
                        cnt++;
                    }
                }
                ls.emplace_back(line);
                // cout << cnt << endl;
                if (cnt > 0) {
                    cnt += 2;
                    ans -= modpow(2, cnt, MOD) - 1 - cnt - cnt * (cnt - 1) / 2; 
                    ans %= MOD;
                }
            }
        }
    }

    cout << (ans % MOD + MOD) % MOD << endl;
}

Measured memory_bytes: 896
import sys

n=input()
num = n.split()
a=int(num[0])
b=int(num[1])

def checkMultiNum(base, dst):
	num=0
	while True:
		if base >= dst:
			break;
		num+=1
		base = base * 2
		if base >= dst:
			break;
	return num

prob=1/a
res=0
if a >= b:
	res=prob*(a-(b-1))
for v in range(a):
	if v+1 >= b:
		break;
	num = checkMultiNum(v+1, b)
	tmp = prob * 0.5**num
	res += tmp

print(res)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using i64 = long long;

template <class T = long long int>
class Bit {
    private:
    int len;
    T *arr;
    T init;

    public:
    Bit(int length, T initialValue = 0) : len(length), init(initialValue) {
        arr = new T[length + 1];
        for (int i = 0; i <= length; i++) {
            arr[i] = initialValue;
        }
    }
    ~Bit() {
        delete[] arr;
    }
    void update(int a, T newval) {
        for (int x = a; x <= len; x += x & -x) arr[x] += newval;
    }
    T query(int a) const {
        T ret = init;
        for (int x = a; x > 0; x -= x & -x) ret += arr[x];
        return ret;
    }
};

int main() {
    constexpr i64 mod = 998244353;
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> a;
    std::vector<int> ys;
    std::vector<i64> ts(n + 1);
    ts[0] = 1;
    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        a.emplace_back(x, y);
        ys.push_back(y);
        ts[i + 1] = ts[i] * 2 % mod;
    }

    std::sort(a.begin(), a.end());
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
    for (auto &e : a) e.second = std::lower_bound(ys.begin(), ys.end(), e.second) - ys.begin() + 1;

    i64 ret = ts[n - 1] * n % mod;
    Bit<> bit(n + 10);

    for (int i = 0; i < n; i++) {
        i64 p = bit.query(a[i].second), c = i - p, b = a[i].second - 1 - p, q = n - 1 - i - b;
        bit.update(a[i].second, 1);
        ret = (ret + (ts[c] - 1) * (ts[b] - 1) % mod * ts[p] % mod * ts[q] % mod + (ts[p] - 1) * (ts[q] - 1) % mod * (ts[c] + ts[b] - 1) % mod) % mod;
    }

    std::cout << ret << std::endl;

    return 0;
}


Measured memory_bytes: 6768
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>

using namespace std;
int main() {
	int n, k;
	unsigned int r=1;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		r *= (i) ? k - 1 : k;
	}
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(void){
  int N;
  int M;
  cin >> N;
  string *s = new string[N];
  for(int i = 0;i < N;i++) cin >> s[i];
  cin >> M;
  string *t = new string[M];
  for(int i = 0;i < M;i++) cin >> t[i];
  
  int *counts = new int[N + 1];
  counts[N] = 0;
  for(int i = 0;i < N;i++){
    string cmp = s[i];
    int count = 0;
    for(int ii = 0; ii < N;ii++){
      if(s[ii] == cmp) count++;
    }
    for(int jj = 0; jj < M; jj++){
      if(t[jj] == cmp) count--;
    }
    counts[i] = count;
  }
  int max = 0;
  for(int i = 0;i < N;i++){
    if (max < counts[i]) max = counts[i];
  }
  
  cout << max << endl;
  
  delete[] s;
  delete[] t;
  return 0;
}

Measured memory_bytes: 256
//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define inf 20021225
#define N 100010
using namespace std;
int read()
{
	int s=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return f*s;
}
struct edge{int to,lt;}e[N];
int in[N],cnt,f[N],tmp[N];
void add(int x,int y)
{
	e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;
}
void dfs(int x)
{
	if(!in[x])	return; int t=0;
	for(int i=in[x];i;i=e[i].lt)	dfs(e[i].to);
	for(int i=in[x];i;i=e[i].lt)	tmp[++t]=f[e[i].to];
	sort(tmp+1,tmp+t+1);
	for(int i=2;i<=t;i++)	if(tmp[i]<=tmp[i-1])
		tmp[i]=tmp[i-1]+1;
	f[x]=tmp[t]+1;// printf("%d %d\n",x,f[x]);
}
int main()
{
	int n=read(),x;
	for(int i=2;i<=n;i++) x=read(),add(x,i);
	dfs(1); printf("%d\n",f[1]);
	return 0;
}

Measured memory_bytes: 6400
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n,k;
  cin >> n>>k;
  vector<double> vec(n);
  rep(i,n){
    cin >> vec.at(i);
  }
  vector<double> as(n);
  rep(i,n){
    as.at(i)=(vec.at(i)+1);
  }
  double ans=0,maxi=0;
  queue<int> que;
  rep(i,n){

    if(que.size()>k-1){
      maxi-=que.front();
      que.pop();
    }
    que.push(as.at(i));
    maxi+=as.at(i);
    ans=max(maxi,ans); 
  }
  ans/=2;
  printf("%.10lf",ans);
}


Measured memory_bytes: 4224
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll>A(N);
	ll sum = 0;
	for (ll i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
	}
	set<ll>dv;
	for (ll i = 1; i*i <= sum; i++) {
		if (sum % i == 0) {
			dv.insert(i);
			dv.insert(sum / i);
		}
	}

	ll ans = 1;
	fore(x, dv) {
		map<ll,ll>mp;
		ll modsum = 0;
		fore(y, A) {
			mp[y%x]++;
			modsum += y % x;
		}
		vector<ll>p;
		fore(x, mp) {
			for (int i = 0; i < x.second; i++)p.pb(x.first);
		}
		sort(all(p));
		reverse(all(p));
		ll tmp = 0;
		for (ll i = 0; i < modsum / x; i++) {
			tmp += x - p[i];
		}
		if (tmp <= K)ans = max(ans, x);
	}
	puts(ans);
	
	return 0;
}

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

using namespace std;
#define BUF (1000)
#define ll long long 

ll n;
int v[30];
int main(void){
	cin >> n;
	ll tmp = n;
	ll cnt=0;
	int ans = 0;
	while(tmp!= 0){
		v[cnt]=tmp%10;
		tmp=tmp/10;
		cnt++;
	}

	//1999とか29999とか
	int f = 0;
	for (int j = 0; j < cnt - 1; j++)
	{
		if (v[j] != 9)
			f = 1;
	}
	if (f == 0)
	{
		ans = v[cnt-1]+9*(cnt-1);		
		cout << ans << endl;
		//cout << n << endl;
		return 0;
	}
	int i;

	//find first 9
	for(i=cnt-1;i>=0;i--){
		if(v[i]!=9)break;
	}
	//first num is not 9
	if(cnt==i+1){
		ans = v[cnt-1]-1+9*(cnt-1);
		cout << ans << endl;
		//if(v[cnt-1]!=1) cout << v[cnt-1]-1;
		//for(int j=0;j<cnt-1;j++) cout << 9;
		return 0;
	}

	//find 99... k 
	ans = 9*(cnt)-1;
	cout << ans << endl;
//	for(int j=0;j<cnt;j++){
		
//		if(j==i+1) cout << 8;
//		else cout << 9;
	
	cout << endl;


	return 0;
}


Measured memory_bytes: 256
n = int(input())
l = [0]*4
for i in range(n):
  s = input()
  if s=="AC":
    l[0]=l[0]+1
  elif s=="WA":
    l[1]=l[1]+1
  elif s=="TLE":
    l[2]=l[2]+1
  else:
    l[3]=l[3]+1
print("AC x "+str(l[0]))
print("WA x "+str(l[1]))
print("TLE x "+str(l[2]))
print("RE x "+str(l[3]))

Measured memory_bytes: 9224
n=int(input())
l=list(map(int, input().split()))
cnt=0
for i in range(n):
    if n==1:
        break
    elif l[i]!=min(l[i:n]):
        num=l[i:n].index(min(l[i:n]))+i
        l[i],l[num]=l[num],l[i]
        cnt+=1
print(*l)
print(cnt)


Measured memory_bytes: 5612
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const int N = 205, X = 1e5+10, L = 17;

int n, x;
int s[N];
ll fac[N];
/*
int dp[N][N][X]; // dp[i][j] := value if cur = j, ind = i

ll solve(int pos, int above, int accum, int val) {
  if (pos >= n) return accum ? 0 : fac[above] * val % MOD;
  if (dp[pos][above][val] != -1) return dp[pos][above][val];
  if (val < s[pos]) {
    return dp[pos][above][val] = solve(pos+1, above+1, accum, val);
  } else {
    ll ans = solve(pos+1, above, accum+1, val);
    int nval = val % s[pos];
    for (int i = 0; i <= above; i++) {
      ans += solve(pos+1, above + accum - i, 0, nval) * fac[i];
    }
  }
}*/

int dp[N][X]; // dp[i][j] = # of ways to end with j, last mod i

void pre() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i-1] * i % MOD;
  }
}

void add(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  pre();
  cin >> n >> x;
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
  }
  sort(s + 1, s + n + 1, greater<int>());
  s[0] = x+1;
  dp[0][x] = 1;
  for (int i = 1; i <= n; i++) {
    // take self
    for (int j = 0; j <= x; j++) {
      add(dp[i][j%s[i]], dp[i-1][j]);
    }
    // don't take self
    for (int j = 0; j <= x; j++) {
      add(dp[i][j], (ll) dp[i-1][j] * (n - i) % MOD);
    }
    /*
    for (int j = 0; j <= x; j++) {
      dp[i][j] = dp[i-1][j];
      if (j < s[i]) {
        for (int k = j + s[i]; k <= x; k += s[i]) {
          add(dp[i][j], (ll) dp[i-1][k]);
        }
      }
    }*/
    //cerr << accumulate(dp[i], dp[i] + X, 0LL) << nl;
  }
  //cerr << accumulate(dp[n], dp[n] + X, 0LL) << nl;
  int ans = 0;
  for (int i = 0; i < s[n]; i++) {
    //cerr << i << " " << dp[n][i] << nl;
    add(ans, (ll) i * dp[n][i] % MOD);
  }
  cout << ans << nl;
  return 0;
}


Measured memory_bytes: 79744
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);
		int c=1;
		for(;;){
			int n=sc.nextInt();
			if(n==0) break;
			System.out.println("Case"+" "+c+": "+n);
			c++;
		}

	}

}

Measured memory_bytes: 41668
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  ll Q, H, S, D, N;
  cin >> Q >> H >> S >> D >> N;
  H = min(H, 2 * Q);
  S = min(S, 2 * H);
  if (2 * S <= D)
  {
    cout << N * S << endl;
  }
  else
  {
    cout << (N / 2) * D + (N % 2) * S << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    int N, K; cin >> N >> K;
    int ans = 0;
    while(N){
        N /= K;
        ans++;
    }
    Out(ans);

    return 0;
}


Measured memory_bytes: 256