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

using ll = long long;
using P = pair<int, int>;

int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<int> a(n+1);
        for(int i=1; i<=n; ++i) {
            cin >> a[i];
            a[i] %= m;
            (a[i] += a[i-1]) %= m;
        }
        int res = 0;
        set<int> s;
        s.insert(0);
        for(int i=1; i<=n; ++i) {
            auto it = s.upper_bound(a[i]);
            res = max(res, a[i]);
            if(it != s.end()) {
                res = max(res, (a[i] - *it + m) % m);
            }
            s.insert(a[i]);
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 4100
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, a, b) for(int i=(a); i<(int)(b); i++)

typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int to, cost; };
struct Node { int from, to, cost; };

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

int gcd(int a, int b){ return a % b == 0 ? b : gcd(b, a%b); }
int lcm(int a, int b){ return a * b/ gcd(a, b); }
int extgcd(int a, int b, int& x, int& y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}

int dp[101][4][4][4];

int main(void){
	int n; cin >> n;
	dp[0][3][3][3] = 1;
	rep(len, n){
		rep(i, 4){
			rep(j, 4){
				rep(k, 4){
					rep(a, 4){
						if(a == 2 && i == 1 && j == 0) continue;
						if(a == 2 && i == 0 && j == 1) continue;
						if(a == 1 && i == 2 && j == 0) continue;
						if(a == 2 && i == 1 && k == 0) continue;
						if(a == 2 && j == 1 && k == 0) continue;
					
						dp[len+1][a][i][j] += dp[len][i][j][k];
						dp[len+1][a][i][j] %= MOD;
					}
				}
			}
		}
	}

	int ans = 0;
	rep(i, 4){
		rep(j, 4){
			rep(k, 4){
				ans += dp[n][i][j][k];
				ans %= MOD;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.*;

class Main {
	public static void main(String[] arg)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] alp = new int[26];
		String str;
		while(( str = br.readLine())!=null){
			str = str.toLowerCase();
			for(int i=0;i<str.length();i++){
				char alp_num = str.charAt(i);
				if('a'<= alp_num && alp_num <= 'z'){
					alp[alp_num - 'a']++;
				}
			}
		}
		for(int i=0;i <26;i++){
			System.out.println((char)('a' + i)+" : "+alp[i]);
		}
	}
}
	

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

template<class T> T euclidean_gcd(T a, T b)
{
    if(a < b) return euclidean_gcd(b, a);
    T r;
    while(r=a%b)
    {
        a = b;
        b = r;
    }
    return b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll A, B;
    cin >> A >> B;
    ll C = euclidean_gcd(A, B);

    vector<ll> yakusu;
    for(ll i=1; i*i<=C; i++)
    {
        if(C%i==0)
        {
            yakusu.push_back(i);
            if(i*i != C) yakusu.push_back(C/i);
        }
    }

    sort(yakusu.begin(), yakusu.end());
    // cout << yakusu.size() << endl;
    vector<ll> ans;
    for(int i=0; i<yakusu.size(); i++)
    {
        bool is_add = true;
        for(int j=0; j<ans.size(); j++)
        {
            if(euclidean_gcd(yakusu[i], ans[j]) != 1) is_add = false;
        }
        if(is_add) ans.push_back(yakusu[i]);
    }
    cout << ans.size() << endl;

    return 0;
}

Measured memory_bytes: 384
import sys
n = int(input())
le = 0
ri = n
print(0)
sys.stdout.flush()
s = input()
if s == "Male":
    ls = "Male"
elif s == "Female":
    ls = "Female"
else:
    exit()

while ri > le + 1:
    m = (ri+le)//2
    print(m)
    sys.stdout.flush()
    s = input()
    if s == "Vacant":
        exit()
    if (m-le)%2:
        if s == ls:
            ri = m
        else:
            le = m
            ls = s
    else:
        if s == ls:
            le = m
            ls = s
        else:
            ri = m
print(le)
sys.stdout.flush()
exit()


Measured memory_bytes: 9184
//Low Elements
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i=0; i<n; i++){
        cin >> p[i];
    }
    int a=p[0];
    int ans=1;
    for(int i=1; i<n; i++){
        a=min(a, p[i]);
        if(a==p[i]){
            ans+=1;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define N 3005

int mod;

int inv[N];

struct poly {
    vector <int> A;
    poly(int n=1,int m=0) {
		resize(n);
		fill(A.begin(),A.end(),m);
	}
	int size() {return A.size();}
	void resize(int n) {A.resize(n);}
	int & operator [](int i) {return A[i];}
    void trim() {
        while (!A.empty() && A.back() == 0) A.pop_back();
        if (A.empty()) A.push_back(0);
    }
    poly operator * (poly &B) {
        int sz = A.size() + B.size() - 1;
        poly C(sz, 0);
        for (int i = 0; i < A.size(); i ++) {
            for (int j = 0; j < B.size(); j ++) {
				C[i+j] = (C[i+j] + 1ll * A[i] * B[j]) % mod;
            }
        }
        C.trim();
        return C;
    }
    poly operator - (poly B) {
        int sz = max((int)A.size(), B.size());
        poly C(sz, 0);
        for (int i = 0; i < sz; i ++) {
            if (i < A.size()) {
                C[i] += A[i];
                if (C[i] >= mod) C[i] -= mod;
            }
            if (i < B.size()) {
                C[i] -= B[i];
                if (C[i] < 0) C[i] += mod;
            }
        }
        C.trim();
        return C;
	}
    poly operator / (poly &B) {
        int n = A.size() - 1, m = B.size() - 1;
        if (n < m) return poly(1, 0);
        int sz = n - m + 1;
        poly C(sz, 0);
        poly tmp; tmp.A = A;
        int coe = inv[B[m]];
        for (int i = n; i >= m; i --) {
            int k = 1ll * tmp[i] * coe % mod;
            C[i-m] = k;
            for (int j = m; j >= 0; j --) {
                tmp[i-m+j] = (tmp[i-m+j] - 1ll * B[j] * k) % mod;
                if (tmp[i-m+j] < 0) tmp[i-m+j] += mod;
            }
        }
        C.trim();
        return C;
    }
    void print() {
		for (int i = 0; i < A.size(); i ++) printf("%d ", A[i]);
		puts("");
    }
} A(1, 1), B(1, 1);

poly extended_euclid(poly a, poly b, poly &x, poly &y) {
    if (b.size() == 1 && b[0] == 0) {
        x = poly(1, 1), y = poly(1, 0);
        return a;
    }
    poly D = a / b;
    poly rlt = extended_euclid(b, a - D * b, y, x);
    y = y - D * x;
    return rlt;
}

int a[N];

int main() {
//	freopen("1.in", "r", stdin);
	int p;
    scanf("%d", &p);
    inv[1] = 1;
    for (int i = 2; i < p; i ++) inv[i] = 1ll * (p / i) * (p - inv[p%i]) % p;
    mod = p;
    for (int i = 0; i < p; i ++) {
		scanf("%d", &a[i]);
        if (a[i] == 0) {
            poly tmp(2, 0);
            tmp[0] = (p - i) % p;
            tmp[1] = 1;
            A = A * tmp;
        }
        else {
            poly tmp(2, 0);
            tmp[0] = (p - i) % p;
            tmp[1] = 1;
            B = B * tmp;
        }
    }
    poly X, Y;
    poly C = extended_euclid(A, B, X, Y);
    A = A * X;
    int d = inv[C[0]];
    for (int i = 0; i < A.size(); i ++) printf("%d ", A[i] * d % mod);
    for (int i = A.size(); i < p; i ++) printf("0 ");
    puts("");
    return 0;
}


Measured memory_bytes: 14208
n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
mod=10**9+7
broken=[False for _ in range(n+1)]
for _ in range(m):
    broken[int(input())]=True
    
for i in range(1,n+1):
    if broken[i]:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%mod

print(dp[n])

Measured memory_bytes: 7832
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll H, W, K;
  cin >> H >> W >> K;
  vector<vector<char>> cake(H, vector<char>(W));
  for (ll i = 0; i < H; ++i) {
    for (ll j = 0; j < W; ++j) {
      cin >> cake.at(i).at(j);
    }
  }

  vector<vector<ll>> ans(H, vector<ll>(W));
  vector<ll> before(W, 1);
  vector<ll> no(W, -1);
  ll cnt = 1;
  for (ll i = 0; i < H; ++i) {
    ll straw = 0;
    for (ll j = 0; j < W; ++j) {
      if (cake.at(i).at(j) == '#') {
        straw += 1;
      }
    }
    if (straw == 1) {
      for (ll j = 0; j < W; ++j) {
        ans.at(i).at(j) = cnt;
      }
      cnt += 1;
    }
    else if (straw == 0) {
      ans.at(i) = no;
    }
    else {
      ll temp = 0;
      for (ll j = 0; j < W; ++j) {
        ans.at(i).at(j) = cnt;
        if (cake.at(i).at(j) == '#') {
          temp += 1;
          if (temp != straw) {
            cnt += 1;
          }
        }
      }
      cnt += 1;
    }
  }
  for (ll i = 0; i < H - 1; ++i) {
    if (ans.at(i + 1) == no) {
      ans.at(i + 1) = ans.at(i);
    }
  }
  for (ll i = H - 1; i > 0; --i) {
    if (ans.at(i - 1) == no) {
      ans.at(i - 1) = ans.at(i);
    }
  }
  for (ll i = 0; i < H; ++i) {
    for (ll j = 0; j < W; ++j) {
      cout << ans.at(i).at(j) << " ";
    }
    cout << "\n";
  }
}

// 3 3 3
// ###
// ...
// ...


Measured memory_bytes: 1536
#!/usr/bin/env python3
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
from heapq import heapify, heappush, heappop # heapify(L) changes list in-place in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(nlgk)=O(n).
from itertools import accumulate             # accumulate(iter[, f])
from functools import reduce                 # reduce(f, iter[, init])
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from fractions import gcd                    # for Python3.4.3


def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    d, n = mi()
    print(100 ** d * (n + 1)) if n == 100 else print(100 ** d * n)

if __name__ == "__main__":
    main()

Measured memory_bytes: 5124
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

    int n, k;
    cin >> n >> k;
    auto h = make_vec<int>(n);
    REP(i, n) { cin >> h.at(i); }
    sort(ALL(h));

    int ans = INF;
    REP(i, n - k + 1) { ans = min(ans, (h[i + k - 1] - h[i])); }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

int main() {
  int d,n;
  cin>>d>>n;
  int q=1;
  if(d==1) q=100;
  if(d==2) q=10000;
  if(n!=100) cout<<q*n<<endl;
  else cout<<(n+1)*q<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

/**
 * 問題A<BR>
 * 起床時刻と就寝時刻及び学習時間が与えられる。
 * 学習可能な時間を求めて出力してください。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 起床時刻
        int sh = sc.nextInt();
        int sm = sc.nextInt();
        // 就寝時刻
        int eh = sc.nextInt();
        int em = sc.nextInt();
        // 学習時間
        int k  = sc.nextInt();

        int study = (eh * 60 + em) - (sh * 60 + sm) - k;
        if (study < 0) {
            study = 0;
        }
        System.out.println(study);
    }
}

Measured memory_bytes: 27088
#include<iostream>
#include<map>
#include<numeric>
using namespace std;

#define inRange(x,a,b) (a <= x && x <= b)

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

typedef long long ll;

int main(){
    int h, w, n;
    cin >> h >> w >> n;

    int a, b;
    map<int,map<int,int>> m;

    for(int i = 0; i < n; i++){
        cin >> a >> b;
        for(int k = 0; k < 9; k++){
            int na = a + dx[k], nb = b + dy[k];
            m[na][nb]++;
        }
    }

    ll cnt[10] = {};
    for(auto p : m){
        if(!inRange(p.first, 2, h-1))   continue;
        for(auto q : p.second){
            if(!inRange(q.first, 2, w-1))   continue;
            cnt[q.second]++;
        }
    }

    cnt[0] = (ll)(h-2)*(w-2) - accumulate(cnt, cnt+10, 0ll);
    for(int i = 0; i < 10; i++) cout << cnt[i] << endl;

    return 0;
}

Measured memory_bytes: 70528
#include<stdio.h>
 
long long n,m,x[100000],y[100000];
 
int main(void){
    scanf("%lld%lld",&n,&m);
    for(int i = 0;i < n;i++)
        scanf("%lld",&x[i]);
    for(int i = 0;i < m;i++)
        scanf("%lld",&y[i]);
 
    long long n2,m2;
 
    n2 = (-1) * n;m2 = m * (-1);n2++;m2++;
 
    long long xx = 0,yy = 0;
 
    for(int i = 0;i < n;i++){
        xx += n2 * x[i] % 1000000007;
        xx %= 1000000007;
        n2 += 2;
    }
    for(int i = 0;i < m;i++){
        yy += m2 * y[i] % 1000000007;
        yy %= 1000000007;
        m2 += 2;
    }
    printf("%lld\n",xx * yy % 1000000007);
    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a),i##Len_=(b);i<i##Len_;i++)
const char* LF = "\n";
namespace{struct _{_(){
    cin.tie(0);
    ios::sync_with_stdio(false);
}}a;}

signed main() {
    string S;
    cin >> S;

    stack<char> st;
    ll ans = 0;

    REP(i, S.size()) {
        if (st.empty()) {
            st.push(S[i]);
            continue;
        }

        if (st.top() != S[i]) {
            st.pop();
            ans += 2;
        }
        else {
            st.push(S[i]);
        }
    }

    cout << ans << LF;

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll x;
    cin >> x;
    set<ll> st;
    st.insert(0);
    ll a = 1, lm;
    while(true){
        st.insert(pow(a, 5));
        if(pow(a+1, 5) - pow(a, 5) > 1e12){
            lm = a+1;
            break;
        }
        a++;
    }
    for(ll a = -1; a > -lm; a--){
        st.insert(pow(a, 5));
    }
    //cerr << st.size() << endl;
    bool f = false;
    for(auto s : st){
        ll b = s - x;
        //cerr << b << endl;
        if(st.count(b) > 0){
            ll ans1, ans2;
            rep(i, -lm, lm){
                if(pow(i, 5) == s) ans1 = i;
                if(pow(i, 5) == b) ans2 = i;
            } 
            cout << ans1 << " " << ans2 << endl;
            f = true;
            break;
        }
    }
    if(!f) cerr << "err" << endl;
    
    return 0;
}

Measured memory_bytes: 4172
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while(t>0){
        int n;
        cin >> n;
        int mu = 0,md = 0;
        int h[101] = {0};
        for(int i = 0; i < n; i++){
            cin >> h[i];
        }
        for(int i = 0; i < n-1; i++){
            if(h[i] <= h[i+1]) mu = max(mu,h[i+1]-h[i]);
            else md = max(md,h[i]-h[i+1]);
        }
        cout << mu << " " << md << endl;
        t--;
	}
	return 0;
}

Measured memory_bytes: 1160
typedef long unsigned int size_t;
extern int printf (const char *__restrict __format, ...);
extern int scanf (const char *__restrict __format, ...) ;
extern int getchar (void);
extern int putchar (int __c);
int nextInt(){int f=0;char s=0;char c=getchar();while((c<48)||(57<c)){if(c==45){s=1;c=getchar();break;}c=getchar();}while((48<=c)&&(c<=57)){f=f*10+(c-48);c=getchar();}return s?-f:f;}
short int nextShort(){short f=0;char s=0;char c=getchar();while((c<48)||(57<c)){if(c==45){s=1;c=getchar();break;}c=getchar();}while((48<=c)&&(c<=57)){f=f*10+(c-48);c=getchar();}return s?-f:f;}
long long int nextLong(){long long int f=0;char s=0;char c=getchar();while((c<48)||(57<c)){if(c==45){s=1;c=getchar();break;}c=getchar();}while((48<=c)&&(c<=57)){f=f*10+(c-48);c=getchar();}return s?-f:f;}
void print(char *f){while(*f){putchar(*f);f++;}}
void printInt(int f){char c[10];if(!f){putchar(48);return;}if(f<0){f=-f;putchar(45);}char i=0;while(f){c[++i]=(f%10)+48;f/=10;}while(i){putchar(c[i--]);}}
void printLong(long long int f){char c[19];if(!f){putchar(48);return;}if(f<0){f=-f;putchar(45);}char i=0;while(f){c[++i]=(f%10)+48;f/=10;}while(i){putchar(c[i--]);}}
int lower_bound(void *base, size_t num, size_t size){
 void *l = base;
 void *r = base + num*size;
}
int H, W, h, w;
int main(){
 scanf("%d%d%d%d", &H, &W, &h, &w);
 printf("%d\n", (H-h)*(W-w));
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define LLI long long int
LLI n,m,sum,ans,pp,j;
using namespace std;
string  str;

int main(){

    while(1){
    cin >> n;
    if(n==0)break;
    cin >> m >> str;
    pp=m-(n*2);
    for(int i=0;i<=pp;i++){
            if(str[i]=='I'){
                    j=1;
                    while(1){
        if(str[i+j]=='O'&&str[j+i+1]=='I')sum++;
        else break;
                j+=2;
                    }

                    i+=sum*2;
                    if(sum-n+1>0)ans+=sum-n+1;
                    sum=0;
            }
        }

        cout << ans << endl;
        ans=0;
    }


return 0;
}

Measured memory_bytes: 2100
import sys


def I(): return int(sys.stdin.readline().rstrip())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def S(): return sys.stdin.readline().rstrip()


def LS(): return list(sys.stdin.readline().rstrip().split())


ans = 0
a, b, c = LI()
for i in range(a, b+1):
    if c % i == 0:
        ans += 1
print(ans)



Measured memory_bytes: 5604
#include<stdio.h>

int cnt, h, c;
int g[1000000];

void insertionSort(int a[], int n, int g)
{
	int i, v, j;

	for(i = g; i < n; i++)
	{
		v = a[i];
		j = i - g;
		while(j >= 0 && a[j] > v)
		{
			a[j+ g] = a[j];
			j = j - g;
			cnt++;
		}
		a[j + g] = v;
	}
}

void shellSort(int a[], int n)
{
	int i;
	
	for(h = 1;;)
	{
		if(h > n){
			break;
		}
		h = 3 * h + 1;
		c++;
	}
	
	g[0] = 1;
	
	for(i = 1; i < c; i++)
	{
		g[i] = 3 * g[i - 1] + 1;
	}
	
	
	for(i = c - 1; i >= 0; i--)
	{
		insertionSort(a, n, g[i]);
	}
}

int main(void)
{
	int n, i;
	
	scanf("%d", &n);
	
	int a[n];
	
	for(i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	cnt = 0;
	c = 0;
	
	shellSort(a,n);
	
	
	printf("%d\n", c);
	
	for(i = c - 1; i >= 0; i--)
	{
		if(i != 0)
		{
			printf("%d ", g[i]);
		}
		else
		{
			printf("%d\n", g[i]);
		}
	}
	
	printf("%d\n", cnt);
	for(i = 0; i < n; i++)
	{
		printf("%d\n", a[i]);
	}
	
	return 0;
}


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

int main(){
    int n;cin >> n;
    n %= 10;
    if(n == 3){
        cout << "bon" << endl;
    }else if(n == 0 || n== 1 || n==6 || n == 8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())

ll arr[3005];

ll dp[3005][3005][2];

ll fu(int init,int end,int val){
    if(init>end) return 0;
    if(init==end){ 
        dp[init][init][val]=arr[init];
        if(val==0) return arr[init];
        else return 0;
       
    
    }

    ll tar=0;
    ll x=dp[init][end][val];
    if(x>=0){
        return x;

    }
    if(val==1){
        
        tar=min(fu(init+1,end,0),fu(init,end-1,0));
        dp[init][end][1]=tar;
        return tar;
    }
    if(val==0){
        tar=max(arr[init]+fu(init+1,end,val^1),arr[end]+fu(init,end-1,val^1));
        dp[init][end][0]=tar;
        return tar;
    }
    
}

int main(){
    IOS
    int n;
    cin>>n;
    fo(i,n) cin>>arr[i];
    fo(i,n+1){
        fo(j,n+1){
            dp[i][j][0]=-1;
            dp[i][j][1]=-1;
        }
    }
    ll ans=fu(0,n-1,0);
    ll suum=0;
    fo(i,n) suum+=arr[i];
    cout<<2*ans-suum<<endl;




}

Measured memory_bytes: 141312
s = (input())
fr = int(s[0:2])
fb = int(s[2:])
if(0<fr<13 and 0<fb<13):
  print("AMBIGUOUS")
elif((fb<1 or fb>12) and (fr>12 or fr<1)):
  print("NA")
elif((fr<1 or fr>12)):
  print("YYMM")
else:
  print("MMYY")
 


Measured memory_bytes: 3060
from sys import stdin
from collections import deque

N = int(stdin.readline())
A = sorted([int(stdin.readline()) for i in range(N)])
ans1 = deque([A[N-1]])
ans2 = deque([A[0]])

f = 0
f2 = 1
b = N - 2
b2 = N - 1
s = True
while f <= b:
    if s:
        ans1.append(A[f])
        f += 1
        if f <= b:
            ans1.appendleft(A[f])
            f += 1
        ans2.append(A[b2])
        b2 -= 1
        if f2 <= b2:
            ans2.appendleft(A[b2])
            b2 -= 1
    else:
        ans1.append(A[b])
        b -= 1
        if f <= b:
            ans1.appendleft(A[b])
            b -= 1
        ans2.append(A[f2])
        f2 += 1
        if f2 <= b2:
            ans2.appendleft(A[f2])
            f2 += 1
    s = not s

a1 = a2 = 0
ans1 = list(ans1)
ans2 = list(ans2)
for i in range(N-1):
    a1 += abs(ans1[i] - ans1[i+1])
    a2 += abs(ans2[i] - ans2[i+1])

print(max(a1, a2))

Measured memory_bytes: 10504
#include <iostream>

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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

ll dp[105][100005];

int main() {
  int n, w;
  cin >> n >> w;
  P a[n];
  rep(i, n) cin >> a[i + 1].first >> a[i + 1].second;

  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= w; ++j) {
      dp[i][j] = dp[i - 1][j];
      if (j >= a[i].first)
        dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].first] + a[i].second);
    }
  }

  cout << dp[n][w] << endl;
  return 0;
}


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

int main(void) {
  long long N, M;
  long long K[30];
  long long A;
  unsigned long int chose[30];
  cin >> N >> M;

  for (int i = 0; i < N; i++) {
    cin >> K[i];
    chose[i] = 0x00;
    for (int j = 0; j < K[i]; j++) {
      cin >> A;
      chose[i] |= (0x01 << A);
    }
  }
  
  int all_chose = 0;
  for (int i = 0; i < N; i++) {
    if (i == 0) 
      all_chose = chose[i];
    else
      all_chose &= chose[i];
  }

  int counter = 0;

  for (int i = 1; i <= M; i++) {
    if (((all_chose >> i) & 0x01) == 0x01) {
      counter ++;
    }
  }
  cout << counter << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int max_rect(VI a){
    int n = a.size();
    VI l(n), r(n);

    stack<int> st;
    REP(i,n){
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        l[i] = (st.empty() ? 0 : st.top() + 1);
        st.push(i);
    }

    while (!st.empty()) st.pop();
    FORR(i,n-1,0){
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        r[i] = (st.empty() ? n : st.top());
        st.push(i);
    }

    int ret = 0;
    REP(i,n){
        ret = max(ret, a[i] * (r[i] - l[i] + 1));
    }
    return ret;
}

int main(){
    int h, w;
    cin >> h >> w;

    vector<string> s(h);
    REP(i,h) cin >> s[i];

    VVI a(h, VI(w-1));
    REP(i,h-1) REP(j,w-1){
        a[i+1][j] = ((s[i][j] == '.') + (s[i+1][j] == '.') + (s[i][j+1] == '.') + (s[i+1][j+1] == '.')) % 2;
    }

    VVI b(h, VI(w-1, 1));
    REP(j,w-1){
        REP(i,h){
            if (a[i][j] == 0){
                b[i][j] = (i == 0 ? 1 : b[i-1][j] + 1);
            }
        }
    }

    // REP(i,h){
    //     REP(j,w-1) cout << b[i][j];
    //     cout << endl;
    // }

    int ans = max(h, w);
    REP(i,h) ans = max(ans, max_rect(b[i]));
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 35840
#include<iostream>
#include<string>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define ceil(a,b) (((a)+(b)-1)/(b))
#define dist(a,b) max((a)-(b),(b)-(a))
#define yn(i) print((i)?"Yes":"No")
#define rep(i,n) for(int i=0;i<(n);i++)

#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << " ";
    cout << *(itr++);
  }
  return os;
}



int main(){
  li a; cin >>a;
  li x=2,ans=1;
  while(x*x<=a){
    if(a%x==0) ans=x;
    x++;
  }
  print(a/ans+ans-2);
}





Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    long int n,k,q;
      cin>>n>>k>>q;
      long int i,j,a[q],b[n]; 
      for(i=0;i<q;i++)
      {
          cin>>a[i];
          
      }
      for(i=0;i<n;i++)
      {
          b[i]=k;
      }
      for(i=0;i<q;i++)
      {
          b[a[i]-1]+=1;
          
      }
      for(i=0;i<n;i++)
      {
          b[i]-=q;
          //cout<<b[i]<<endl;
      }
      for(i=0;i<n;i++)
      {
          if(b[i]<=0)
          {
              cout<<"No"<<endl;
          }
          else
          {
              cout<<"Yes"<<endl;
          }
      }
}


Measured memory_bytes: 5128
local function gcd(a,b)
    if b>0 then
        return gcd(b,a%b)
    else
        return a
    end
end

local n=io.read("*n")
local a={}
for i=1,n do
    a[i]=io.read("*n")
end
for i=1,n-1 do
    a[i+1]=gcd(a[i],a[i+1])
end
print(a[n])

Measured memory_bytes: 2424
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        if (N < 105) {
            System.out.println(0);
        } else if (N < 135) {
            System.out.println(1);
        } else if (N < 165) {
            System.out.println(2);
        } else if (N < 189) {
            System.out.println(3);
        } else if (N < 195) {
            System.out.println(4);
        } else {
            System.out.println(5);
        }
    }
}

Measured memory_bytes: 21332
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;



int main(){
  int a, b;
  cin >> a >> b;
  if (a%3 == 0 || b%3 == 0 || (a+b)%3 == 0) cout << "Possible\n";
  else cout << "Impossible\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
int d,e;
string S;
e = 0;
cin >> S;
d = S.size();
for (int i = 0; i < d; i++) {
for (int j = i+1; j < d; j++) {
if (S[i] == S[j]) {
e = 1;
break;
}
}
}
if (e == 0) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}

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

int main() {
    int N, p, pmax = 0, ans = 0;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> p;
        pmax = max(pmax, p);
        ans += p;
    }
    ans -= pmax / 2;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL; 

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string str;
	getline(cin, str);
	
	for(size_t i = 0; i < str.size(); ++i){
		if('a' <= str[i] && str[i] <= 'z'){
			str[i] += 'A' - 'a';
		}
	}
	
	cout << str << endl;
	
	return 0;
}

Measured memory_bytes: 1172
($n,$d)=glob<>;
@x=<>;
for$i(0..$n-1){
	for$j($i+1..$n-1){
		@a=glob$x[$i];
		@b=glob$x[$j];
		$s=0;
		for(0..$d-1){
			$s+=($a[$_]-$b[$_])**2;
		}
		$ans++ if(int($s**0.5)**2==$s);
	}
}
print $ans||0;

Measured memory_bytes: 5600
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
long long int gcm(long long int a,long long int b){
    long long int r = a % b;
while(r!=0){
    a = b;
    b = r;
    r = a % b;
    }
    return b;
}

long long int lcm(long long int a,long long int b){
    return a*b/gcm(a,b);
}

int main(void){
    long long  int A,B;
    long long int C,D;
    scanf("%lld %lld %lld %lld",&A,&B,&C,&D);
    if(C<D){
        long long int temp = C;
        C=D;
        D = temp;
    }
    A--;
    long long int s1 = B-(B/C+B/D-B/(lcm(C,D)));
    long long int s2 = A-(A/C+A/D-A/(lcm(C,D)));
    printf("%lld",s1-s2);
    return 0;
}

Measured memory_bytes: 128
n=int(input())
A=list(map(int,input().split()))
q=int(input())
B=list(map(int,input().split()))
M=2000
table=[0 for _ in range(M+1)]

def solve(i,m):
    if i==n:
        table[m]=1
        return 
    solve(i+1,m)
    if m+A[i]<=M:
        solve(i+1,m+A[i])

solve(0,0)

for i in range(q):
    m=B[i]
    if table[m]:
        print('yes')
    else:
        print('no')


Measured memory_bytes: 5640
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
using Graph = vector<vector<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; }
//#define int long long

template<typename T>
struct SegmentTree{
private:
    int n;
    T E;
    vector<T> node;
    inline void updatef(T& x,T& y){
        x = y;
        //x += y;
        //x = max(x,y);
        //x = min(x,y);
    }
    inline T queryf(T& x,T& y){
        //return min(x,y);
        //return x+y;
        return max(x,y);
    }

public:
    SegmentTree(int sz,T E_):E(E_){
        n=1;
        while(n<sz)n<<=1;
        node.resize(2*n-1,E);
    }

    SegmentTree(vector<T>& A,T E_):E(E_){
        int sz=A.size();
        n=1;
        while(n<sz)n<<=1;
        node.resize(2*n-1,E);
        rep(i,sz)node[i+n-1]=A[i];
        for(int i=n-2;i>=0;--i){
            node[i]=queryf(node[2*i+1], node[2*i+2]);
        }
    }
    void update(int k,T x){
        k+=n-1;
        updatef(node[k],x);
        while(k>0){
            k=(k-1)/2;
            node[k]=queryf(node[2*k+1], node[2*k+2]);
        }
    }
       //[a,b)での値を返す
    T get(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l)return E;
        if(a<=l&&r<=b)return node[k];
        T xl=get(a,b,2*k+1,l,(l+r)/2);
        T xr=get(a,b,2*k+2,(l+r)/2,r);
        return queryf(xl, xr);
    }
};

void solve() {
	int n; cin >> n;
    vector<int> h(n);
    rep(i, n) {
        cin >> h[i];
    }
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    SegmentTree<ll> sg(n + 5, 0);
    rep(i, n) {
        ll tmp = sg.get(0, h[i]);
        sg.update(h[i], tmp + a[i]);//更新は各々1回だけ
    }
    cout << sg.get(0, n + 1) << endl;//範囲に注意
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 6656
#include<iostream>
#include <vector>
#include<algorithm>
#include <queue>
#include<climits>
#define rep(i, a) for(int i=0; i<(int)(a); i++)
using namespace std;
long long int d[100][100];int v, n, c, e,u;
const long long int INF = (1LL<<32);
void warshall_floyd(int n) { // nは頂点数
    rep(k,n) {  // 経由する頂点
        rep(i,n) { 
            if (d[i][k] == INF) continue;// 開始頂点
            rep(j,n) {// 終端
                if (d[k][j] == INF) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}
int main()
{
    cin >> n >> e;
    rep(i, n) {
        rep(j, n) {
            d[i][j] = ((i == j) ? 0 : INF);
        }
    }
    rep(i, e) {
        cin >> u >> v >> c;
        d[u][v] = c;
    }
    warshall_floyd(n);
    bool ne = false;
    rep(i, n) if (d[i][i] < 0) ne = true;
    if (ne)cout << "NEGATIVE CYCLE" << endl;
    else {
        rep(i, n) {
            rep(j, n) {
                if (j) cout << " ";
                if (d[i][j] == INF) cout << "INF";
                else cout << d[i][j];
            }
            cout << endl;
            }
        }
    }


Measured memory_bytes: 3176
import java.util.*;
public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String ss,t;
        ss = sc.next();
        StringBuffer p = new StringBuffer(ss);
        p = p.reverse();
        t = sc.next();
        StringBuffer q = new StringBuffer(t);
        q = q.reverse();
        boolean f = true;
        int head = 0;
        for(int i=0;i<p.length();i++){
            if(p.charAt(i)==q.charAt(0) || p.charAt(i)=='?'){
                head = i;
                for(int j=0;j<q.length();j++){
                    if(i+j>=p.length()){
                        f = false;
                        break;
                    }
                    if(p.charAt(i+j)==q.charAt(j) || p.charAt(i+j)=='?'){

                        f = true;
                    } else {
                        f = false;
                        break;
                    }
                }
            if(f==true) break;
            }else{
                f = false;
            }

        }

        if(f==false){
            System.out.println("UNRESTORABLE");
        } else {
            String sr = "";
            for(int i=0;i<head;i++){

                if(p.charAt(i)!='?'){
                    sr = sr + p.charAt(i);
                }else {
                    sr = sr + 'a';
                }
            }
            sr = sr + q;
            for(int i= head + q.length();i<p.length();i++){
                if(p.charAt(i)!='?'){
                    sr = sr + p.charAt(i);
                }else {
                    sr = sr+'a';
                }
            }

            StringBuffer s = new StringBuffer(sr);
            System.out.println(s.reverse());
        }


    }


}


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

bool d[10];
bool takbir(int n){
    while(n){
        if(d[n%10]) return true;
        n /= 10;
    }
    return false;
}

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

    //good luck kittu!
    int n, k, x; cin>>n>>k;
    for(int i = 0; i<k; i++){
        cin>>x;
        d[x] = 1;
    }

    while(takbir(n)) n++;
    cout<<n<<"\n";
    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++)
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>P;


int main(){
  ll N;
  cin>>N;
  vector<ll>A(N);
  rep(i,N){cin>>A[i];}
  ll ans=1;
  long double g=1;
  int flag=0;
  rep(i,N){
    ans*=A[i];
    g*=A[i];
  }
  if(g>(long double)1000000000000000000){flag=1;}
  if(flag==1){cout<<-1;}
  else{cout<<ans;}
}


Measured memory_bytes: 4044
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<vector>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N;
vector<P> aVec[20];
int main(){
    cin>>N;
    for(ll i=0;i<N;i++){
      ll a;cin>>a;
      for(ll j=0;j<a;j++){
        ll x,y;
        cin>>x>>y;
        x--;
        aVec[i].push_back(P(x,y));
      }
    }
    ll ans=0;
    for(ll state=0;state<(1<<N);state++){
      bool able=true;
      ll cnt=0;
      for(ll i=0;i<N;i++){
        if(state&(1<<i))cnt++;
        for(auto p:aVec[i]){
          if(state & (1<<i)){
            if( (state&(1<<p.first)) ^ (p.second<<p.first) ){
              able=false;
            }
          }
        }
      }
      if(able){
        ans=max(ans,cnt);
      }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define swap(type,x,y) do{type t=x;x=y;y=t;}while(0)

using namespace std;

void quick(vector<int> a, int left, int right) {
	int pl = left;
	int pr = right;
	int x = a[(pl + pr) / 2];

	do {
		while (a[pl] < x)pl++;
		while (a[pr] > x)pr--;
		if (pl <= pr) {
			swap(int, a[pl], a[pr]);
			pl++;
			pr--;
		}
	} while (pl <= pr);
	if (left < pr) quick(a, left, pr);
	if (pl < right) quick(a, pl, right);
}

int main() {
	int n, m, i, j, k, s;
	int *x;

	cin >> n >> m;

	x = new int[n];

	for (i = 0; i < n; i++)
		x[i] = 0;

	for (i = 0; i < m; i++) {
		cin >> j >> k;
		if (j == 1)
			x[k - 1]++;
		else if (k == n)
			x[j - 1]++;
	}
	for (i = 0; i < n; i++) {
		if (x[i] == 2) {
			cout << "POSSIBLE";
			return 0;
		}
	}
	cout << "IMPOSSIBLE";
	
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
//#include "testlib.h"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define int long long
#define ll long long
#define M 1000000007
#define MM 998244353
#define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define mii  map<ll ,ll >
#define sz(a) (int)a.size()
#define msi  map<string,ll >
#define rep(a,b)    for(ll i=a;i<b;i++)
#define rep0(n)    for(ll i=0;i<n;i++)
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define vi vector<ll>
#define vs vector<string>
#define ppb pop_back
#define endl '\n'
#define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define r0 return 0;
#define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
#define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define Set(a, s) (a, s, sizeof (a))
#define FOR repi
#define pii pair<int,int>
#define REVERSE(v) reverse(all(v))
#define trav(a, x) for(auto& a : x)
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl
#define debug cerr<<"bhau"<<endl
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
template<typename T, typename U> static inline void amin(T &x, U y) 
{ 
    if (y < x) 
        x = y; 
}
template<typename T, typename U> static inline void amax(T &x, U y) 
{ 
    if (x < y) 
        x = y; 
}
 
ll max(ll a, ll b) { return (a > b)? a : b;}
int min(int a, int b) { return (a < b)? a : b;} 
 
 
int solve(){
	int n,k;cin>>n>>k;
	vector<double> d(n);
	for(int i=0;i<n;i++) cin>>d[i];
	// sort(all(d),greater<double>());
	double ans=0;
	for(int i=0;i<k;i++){
		ans+=(double(d[i]+1)/2);
	}
	double nans=ans;
	for(int i=0,last=k;last<n;i++,last++){
		ans-=(double(d[i]+1)/2);
		ans+=(double(d[last]+1)/2);
		nans=max(ans,nans);
	}

	// double arr[n+1];
	// memset()
	cout<<fixed<<setprecision(10)<<nans<<endl;
 
 
    return 0;
}
signed main(){
    asdf
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
int main ()
{
	int N,L;
	scanf ("%d %d",&N,&L);
	int a[N],i,min,ans,count=0;
	for (i=0;i<N;i++)
	{
		a[i]=L+i;
	}
	min=a[0];
	if (N==1)
		ans = L;
	else{

	if (a[0]>=0){
	for (i=0;i<N;i++)
	{
		if (a[i]<min&&a[i]>=0)
			min=a[i];
		
	}
	}
	else
	{
		for (i=0;i<N;i++)
		{
			if(i!=N-1)
			{
			if (a[i]>min&&a[i]>=0&&a[i+1]>a[i])
			{
				min=a[i];
				break;
			}
			}
			else
				min=a[i];

		}
	}
	for (i=0;i<N;i++)
	{
		count=count+a[i];
	}
	ans=count-min;
	}
	printf ("%d\n",ans);
	return 0;
	}



Measured memory_bytes: 128
N,a,b=map(int,input().split())
Num=0
Num_sum=0

for number in range(1,N+1):
    for num in str(number):
        num=int(num)
        Num+=num

    if Num>=a and Num<=b:
        Num_sum+=number
    Num=0
print(Num_sum)

Measured memory_bytes: 3060
n = gets.to_i
points = []
total = 0
divident = 0

n.times do
  x, y = gets.split.map(&:to_i)
  points.push([x,y])
end

points.permutation(n).to_a.each do |array|
  divident += 1
  (0..n-2).each do |i|
    total += Math.sqrt((array[i][0] - array[i+1][0])**2 + (array[i][1] - array[i+1][1])**2)
  end
end

puts total.to_f / divident


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

using namespace std;

pair<long long, int> p[5];
long long n;

int main() {
  for (int i = 0; i < 4; i++) {
    long long a;
    cin >> a;
    p[i] = {a, 1 << i};
  }
  sort(p, p + 4);
  cin >> n;
  n *= 4;
  
  long long ans = 1e18;
  do {
    long long cur = n;
    long long cost = 0;
    for (int i = 0; i < 4; i++) {
      long long nums = cur / p[i].second;
      cur -= nums * p[i].second;
      cost += nums * p[i].first;
    }
    ans = min(ans, cost);
  } while (next_permutation(p, p + 4));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
	int a[9999], i;
	i = 0;
	while (1) {
		i = i + 1;
		scanf("%d",&a[i]);
		if (a[i] == 0) {
			break;
		}
	}
	i = 0;
	while (1) {
		i = i + 1;
		if (a[i] == 0) {
			break;
		}
		printf("Case %d: %d\n", i, a[i]);
	}
	return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,q,opt,l,r,ans;
int sum[N<<2][26];
char str[N];

void build(int k,int l,int r)
{
	if (l==r)
	{
		sum[k][str[l]-'a']=1;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	for (register int i=0; i<26; ++i) sum[k][i]=sum[k<<1][i]+sum[k<<1|1][i];
}

void change(int k,int l,int r,int pos,int x)
{
	if (l==pos && pos==r) 
	{
		for (register int i=0; i<26; ++i) sum[k][i]=0;
		sum[k][x]=1;
		return;
	}
	int mid=l+r>>1;
	if (pos<=mid) change(k<<1,l,mid,pos,x);
	else change(k<<1|1,mid+1,r,pos,x);
	for (register int i=0; i<26; ++i) sum[k][i]=sum[k<<1][i]+sum[k<<1|1][i];
}

int query(int k,int l,int r,int qx,int qy,int x)
{
	if (qx<=l && r<=qy) return sum[k][x];
	int mid=l+r>>1;
	int ans=0;
	if (qx<=mid) ans=query(k<<1,l,mid,qx,qy,x);
	if (mid<qy) ans+=query(k<<1|1,mid+1,r,qx,qy,x);
	return ans;
}

inline char readchar()
{
	char ch=getchar();
	while (ch<'a' || ch>'z') ch=getchar();
	return ch;
}

int main(){
	scanf("%d",&n);
	scanf("%s",str+1);
	build(1,1,n);
	scanf("%d",&q);
	while (q--)
	{
		scanf("%d",&opt);
		if (opt==1)
		{
			scanf("%d",&l);
			char ch=readchar();
			change(1,1,n,l,ch-'a');
		}
		else
		{
			ans=0;
			scanf("%d%d",&l,&r);
			for (register int i=0; i<26; ++i) if (query(1,1,n,l,r,i)) ans++;
			printf("%d\n",ans);	
		}
	}
return 0;
}

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

int main(){
  int i, j, x, min=10000;
  int p[3],d[2];

  cin >> p[0] >> p[1] >> p[2] >> d[0] >> d[1];

  for (i=0; i<3; i++){
    for (j=0; j<2; j++){
      x=p[i]+d[j]-50;
      if (x<min) min=x;
    }
  }

  cout << min << endl;

  return 0;
}

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
typedef vector<vector<int>> Graph;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1L);

vi operation;
vi dp;

int rec(int n) {
    if (n == 0)
        return 0;

    if (dp[n] == INF) {
        int res = INF;
        for (auto op : operation) {
            if (n - op >= 0) {
                res = min(res, rec(n - op) + 1);
            }
        }
        dp[n] = res;
    }

    return dp[n];
}

int main() {
    int n;
    cin >> n;
    operation.push_back(1);
    for (int i = 6; i <= n; i *= 6) {
        operation.push_back(i);
    }
    for (int i = 9; i <= n; i *= 9) {
        operation.push_back(i);
    }

    dp = vi(n + 1, INF);
    rec(n);
    out(dp[n]);
}


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

int main(){
    int N,D,X;
    int A;
    long ans=0;

    cin >> N;
    cin >> D >> X;
    ans = X+N;

    for(int i=0;i<N;i++){
        cin >> A;
        ans += (D-1)/A;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int a;
	cin >> a;
	cout << 3* (a* a) << endl;
	return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#include <iostream>
#define fastinput ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


LL POW(LL x,LL y)
{
    LL ans=1;
    LL base=x;
    while(y)
    {
        if(y&1)
        {
            ans*=base;
        }
        base=base*base;
        y=y>>1;
    }
    return ans;
}


int main()
{    
    fastinput;
    LL n,i,j,k,t,temp;
    cin>>i>>j>>k;
    if(i==j && j!=k)
    {
        cout<<"Yes\n";
    }
    else if(j==k && i!=j)
    {
                cout<<"Yes\n";

    }
    else if(i==k && i!=j)
    {
                cout<<"Yes\n";

    }
    else
    {
        cout<<"No\n";
    }
    

    


    
    return 0;
}

Measured memory_bytes: 256