akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll INF = 1LL << 60;

ll N, W;
vector<ll> w, v;

// i: 何個目
// j: 重さ
// = 価値
ll dp[110][(int)1e5 + 10];  

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

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            // 選ばない
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);

            if (j + w[i] > W) continue;
            // 選ぶ
            dp[i + 1][j + w[i]] = max(dp[i][j + w[i]], dp[i][j] + v[i]);
            // cout << i << " from: " << j << " to: " << j + w[i] << " " << dp[j + w[i]] << endl;
        }
    }

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

Measured memory_bytes: 81676
#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, p: "List[int]"):
    sorted_list = [i for i in range(1, N + 1)]
    if p == sorted_list:
        print("YES")
    elif N - sum(np.array(p) == sorted_list) == 2:
        print("YES")
    else:
        print("NO")


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, p)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14424
def inpl(): return input().split()
n = int(input())
a = list(map(int, inpl()))

ans = float('inf')
for sgn in [1, -1]:
    s = 0
    cnt = 0
    for i in range(n):
        s += a[i]
        if s * sgn > 0:
            pass
        else:
            #s <= 0 and sgn = 1
            #s >= 0 and sgn = -1
            cnt += abs(sgn - s)
            s = sgn
        sgn *= (-1)
    ans = min(ans, cnt)
print(ans)

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

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

#define NL '\n'
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sii(x, y) scanf("%d%d",&x, &y)
#define sll(x, y) scanf("%lld%lld",&x, &y)

#define xx first
#define yy second
#define ins insert
#define mp make_pair
#define pb push_back
#define mdx ((l+r)>>1)
#define ldx ((idx<<1))
#define rdx ((idx<<1)|1)
#define sz(x) x.size()
#define pi 2.0*acos(0.0)
#define sqr(x)  ((x) * 1ll * (x))
#define all(x) (x).begin(),(x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define file_in(); freopen("input.txt", "r", stdin);
#define file_out(); freopen("output.txt", "w", stdout);
#define file_err(); freopen("serr.txt", "w", stderr);
#define rep(ii,aa,bb) for(ll (ii)=ll(aa);(ii)<(ll)(bb);++(ii))
#define _fastIO() ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define _runtime() cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

template<class T> T setbit(T n, T pos){n=n|(1<<pos); return n;}
template<class T> T checkbit(T n, T pos){n=n&(1<<pos); return n;}
template<class T> T gcd(T a, T b ) {return b<=0?a:gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return ((a / gcd(a,b) ) * b);}





const int mxx = 1e5+9;
int n, k, a[mxx], dp[mxx];

int main(){
	_fastIO();
	rep(i, 0, mxx) dp[i] = INT_MAX;
	dp[0] = 0;
	cin >> n >> k; 
	rep(i, 0, n) cin >> a[i];
	rep(i, 1, n){
		rep(j, 0, k+1){
			if(i - j >= 0) dp[i] = min(dp[i], abs(a[i-j]-a[i]) + dp[i-j]);
		}
	}
	cout << dp[n-1] << NL;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

typedef long long ll;

using namespace std;

int main(int argc, const char * argv[]) {
  ll N;
  cin >> N;
  vector<float> v(N);
  ll i;
  for(i=0;i<N;i++){
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  for(i=1;i<N;i++){
    v[i] = (v[i] + v[i-1])/2.0;
  }
  cout << v[N-1];
}


Measured memory_bytes: 256
import sys
from collections import Counter
S = list(input())
N = len(S)
S = Counter(S)
if len(S) == 1:
    if N == 1:
        print("YES")
        sys.exit()
    else:
        print("NO")
        sys.exit()
if len(S) == 2:
    if N == 2:
        print("YES")
        sys.exit()
    else:
        print("NO")
        sys.exit()

a = S["a"]
b = S["b"]
c = S["c"]
M = max(a, b, c)
m = min(a, b, c)

if (M-m) <= 1:
    print("YES")
else:
    print("NO")


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

int main(){
  int X;
  cin >> X;
  int ans = 1;
  int Y = X;
  
  while(Y%360 != 0){
   Y = (Y+X) % 360;
    ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3608
import java.util.Scanner;
public class Main{

	public static void main(String[] args){

		Scanner sc= new Scanner(System.in);

		while(true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H == 0 && W == 0) {
				break;
			}else {
				for(int i = 0;i < H;i++) {
					for(int j = 0;j < W;j++) {
						System.out.print("#");
					}
					System.out.println("");
				}
			}
			System.out.println("");
		}

	}
}


Measured memory_bytes: 33412
//Daniel Grzegorzewski
#include <bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

string s;
int n, k;

int main()
{
    init_ios();
    cin >> s >> k;
    n = s.size();
    for (int i = 0; i < n; ++i) {
    	if (s[i] == 'a')
    		continue;
    	int ile = (int)('z'-s[i]+1);
    	if (ile <= k) {
    		k -= ile;
    		s[i] = 'a';
    	}
    }
    k %= 26;
    while (k--) {
    	if (s.back() == 'z')
    		s.back() = 'a';
    	else
    		++s.back();
    }
    cout<<s<<"\n";
}

Measured memory_bytes: 592
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;

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

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

	int N,x;
	int a[110];
	cin >> N >> x;

	REP(i, N) cin >> a[i];
	sort(a, a + N);
	int ans = 0;
	int sum = 0;
	for (int i=0;i<N;i++) {
		sum += a[i];
		if (sum > x) {
			ans = i;
			break;
		}
	}
	if (ans == 0) {
		if (sum == x) {
			ans = N;
		}
		else if(sum < x) {
			ans = N-1;
		}
	}

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <limits>

using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){

    ll a, b, x;
    cin >> a >> b >> x;

    if(x >= a * a * b * 0.5){
        ll limit = a * a * b - x;
        cout << setprecision(10) << atan2(limit, 0.5 * a * a * a) * 180.0 / M_PI << endl;
    }
    else{
        double theta = atan2((double)x, 0.5 * a * b * b) * 180.0 / M_PI;
        cout << setprecision(10) << (90.000000 - theta) << endl;
    }


}

Measured memory_bytes: 384
a, b, c, x, y = map(int, input().split())
c2 = min(c * 2, a + b)
a = min(a, c * 2)
b = min(b, c * 2)
ans = 0

#buy set of A,B
nab = min(x, y)
ans += nab*c2
x -= nab
y -= nab


#buy remainder
ans += x * a
ans += y * b
print(ans)

Measured memory_bytes: 3064
S = str(input())
x = len(S)
if '0' in S:
  y0 = S.count('0')
else:
  y0 = 0
if '1' in S:
  y1 = S.count('1')
else:
  y1 = 0
  
d = abs(y0 - y1)
print(x - d)


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

int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin >> v.at(i);
  vector<int> c(n);
  for(int i=0;i<n;i++)
    cin >> c.at(i);
  
  int k=0;
  
  for(int i=0;i<n;i++){
    if(v.at(i)-c.at(i)>0)
      k+=v.at(i)-c.at(i);
  }
  cout << k << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B,C,X,Y,ans;
int main(){
	cin >> A >> B >> C >> X >> Y ;
	ans = C * (max(X, Y) * 2);
	if (X <= Y){
		swap(A,B);swap(X,Y);
	}
	for(int i = 0; i <= Y; i++) 
    ans = min(ans, (i * B) + (A * (i+(X-Y))) + C*2*(Y-i));
    cout << ans;
    return 0;
}

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

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

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

signed main() {
    int N;
    cin >> N;

    cout << setprecision(10) << ceil((double) N / 2) / (double)N << endl;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define rep0(i, n) for (i = 0; i < n; i++)
#define rep(s, i, n) for (i = s; i < n; i++)
using namespace std;

long long N;
string ans;

int main()
{
    string c;
    cin >> N;

    while(N>0)
    {
       c=(N-1)%26+'a';
       ans.insert(0,c);
       N=(N-1)/26;
    }

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

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

int n;
typedef pair<int, int> P;
vector<P> v;
long long ans = 1, mod = 1e9+7;
int a[2];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0; i<n; ++i){
		int t;
		cin >> t;
		v.push_back(P(t, 0));
	}
	for(int i=0; i<n; ++i){
		int t;
		cin >> t;
		v.push_back(P(t, 1));
	}
	sort(v.begin(), v.end());
	for(int i=0; i<2*n; ++i){
		if(a[1-v[i].second] > 0){
			ans = ans * a[1-v[i].second] % mod;
			--a[1-v[i].second];
		}else{
			++a[v[i].second];
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 2420
#
# File    : C.rb
# Author  : Kazune Takahashi
# Created : 12/8/2018, 9:13:23 PM
# Powered by Visual Studio Code
#

n, k = gets.chomp.split(" ").map{|i| i.to_i}
h = []
n.times{
  h << gets.to_i
}
h.sort!
ans = h[k - 1] - h[0]
for i in 0..n - k
  ans = [ans, h[k - 1 + i] - h[i]].min
end
puts ans


Measured memory_bytes: 4016
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define vv(T) std::vector<std::vector<T>>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

// 0 < A < 10^4
// 小数分の桁数は9以下 -> 計13桁
// xxxx000000000になるかどうか
// 2と5が共に18個以上あれば当てはまる

int main()
{
	int n;
	cin >> n;
	vv(ll) D(20, vector<ll>(20)); // 20 ? 
	vector<pair<ll, ll>> TF(n, {0, 0});
	for (int i = 0; i < n; ++i)
	{
		string S;
		cin >> S;
		ll n = 0, j = 0, d = 100;
		while (S[j] && d--)
		{
			if (S[j] == '.')
			{
				d = 9;
				++j;
				continue;
			}
			n = n * 10 + (S[j++] - '0');
		}
		d = min(d, 9LL);
		while (d--)
			n *= 10;
		ll two = 0, five = 0;
		while (n % 2 == 0)
		{
			++two;
			n /= 2;
		}
		while (n % 5 == 0)
		{
			++five;
			n /= 5;
		}
		two = min(two, 18LL);
		five = min(five, 18LL); 
		D[two][five]++;
		TF[i] = {two, five};
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i)
	{
		ll t = TF[i].first;
		ll f = TF[i].second;
		for (ll j = 18-t; j <= 18; ++j)
			for (ll k =18-f; k <= 18; ++k)
				ans += D[j][k];
		if (t >= 9 && f >= 9)
			--ans;
	}
	ans /= 2;
	cout << ans << endl;
}


Measured memory_bytes: 6344
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????


		Scanner scan = new Scanner(System.in);
		ArrayList<Integer[]> list = new ArrayList<Integer[]>();

		Integer[] ary;

		while(scan.hasNext()){

			ary = new Integer[2];
			//???H
			ary[0] = scan.nextInt();
			//?¨?W
			ary[1] = scan.nextInt();

			if(ary[0] != 0 && ary[1] != 0){

				list.add(ary);
			}else{
				scan.close();
				break;
			}

		}

		for(int i = 0; i < list.size(); i++){

			ary = list.get(i);
			//???
			for(int j = 0; j < ary[0]; j++){

				//?¨?
				for(int k = 0; k < ary[1]; k++){

					System.out.print("#");
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}

Measured memory_bytes: 25752
//mod
#include <iostream>
using namespace std;

// return gcd(a,b)
// obtain x,y s.t. ax+by=gcd(a,b)
long long extgcd(long long a, long long b, long long &x, long long &y)
{
    if(b==0){
        x = 1;
        y = 0;
        return a;
    }
    long long d = extgcd(b, a%b, y, x);
    y  -= a/b * x;
    return d;
}

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

//return a^-1 mod p (p is a prime number)
long long fermat(long long a, long long p)
{  
    if(p==2) return 0; 
    return modpow(a,p-2,p);
}

//require len(factorials)==len(invs)==n+1
void prepareCOM(long long n, long long p, long long* factorials, long long* invs)
{
    long long f = 1;
    factorials[0] = 1;
    for (long long i = 1; i <= n; i++)
    {
        f = (f*i) % p;
        factorials[i] = f;
    }

    //obtain n!^-1
    long long inv = fermat(factorials[n],p);
    //obtain n!-1~1!^-1
    invs[n] = inv;
    for (long long i = n; i > 0 ; i--)
    {
        inv = (inv*i)%p;
        invs[i-1] = inv;
    }
}

//return nCa mod p
long long COM(long long n, long long a, long long p)
{
    //obtain f=n!
    long long fna = n%p;
    long long fa = 1;
    for (long long i = n-1; i > n-a; i--)
    {
        fna = (fna*i)%p;
    }
    for (long long i = 2; i <= a; i++)
    {
        fa = (fa*i)%p;
    }

    long long inv_a  = fermat(fa,p);

    return (fna*inv_a)%p;
}

int main(){
    long long n;
    long long a,b;

    cin >> n >> a >> b;
    long long p = 1e9+7;

    long long totalComb = (modpow(2,n,p)-1)%p;
    
    //prepare 
    long long nCa = COM(n,a,p);
    long long nCb = COM(n,b,p);

    cout << ((totalComb-nCa-nCb)%p+p)%p;//avoiding being minus

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void merg(int arr[2], int v){
  if(v >= arr[1])
    arr[0] = arr[1], arr[1] = v;
  else if(v >= arr[0])
    arr[0] = v;
}
int main(){
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  int n;
  cin >> n;
  int len = 1 << n;
  int a[len];
  for(int i = 0;i < len;i++)
    scanf("%d", a + i);
  int two[len][2];
  for(int i = 1;i < len;i++){
    two[i][0] = -1;
    two[i][1] = a[0];
    for(int j = i;j > 0;j = (j - 1) & i)
      merg(two[i], a[j]);
  }
  int res[len];
  res[1] = two[1][0] + two[1][1];
  printf("%d\n", res[1]);
  for(int i = 2;i < len;i++){
    res[i] = max(res[i - 1], two[i][0] + two[i][1]);
    printf("%d\n", res[i]);
  }
  return 0;
}


Measured memory_bytes: 7168
from collections import*
n,*h=map(int,open(0).read().split())
dp=defaultdict(int)

for i in range(1,n+1):
    dp[i]=float("inf")
dp[0]=0
for i in range(n):
    for j in range(1,3):
        if i+j<n:
            dp[i+j]=min(abs(h[i]-h[i+j])+dp[i],dp[i+j])
        else:
            break
print(dp[n-1])


Measured memory_bytes: 63248
#include <iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  while(n % 10 == 0){
    n /= 10;
  }
  int ans = 0;
  if(n == 1){
    cout << 10 << endl;
  }else{
    while(n > 0){
      ans += n % 10;
      n /= 10;
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main(){
    int x, y;
    cin >> x >> y;
    bool flag = false;
    if(x == 2){
        if(y == 2){
            flag = true;
        }
    }else if(x == 4 || x == 6 || x == 9 || x == 11){
        if(y == 4 || y == 6 || y == 9 || y == 11){
            flag = true;
        }
    }else{
        if(y == 1 || y == 3 || y == 5 || y == 7 || y == 8 || y == 10 || y == 12){
            flag = true;
        }
    }
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;

int main() {
  ll a;
  string b;
  cin >> a >> b;
  ll b100 = (b[0] - '0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');
  
  cout << (a * b100) / 100 << endl;
  
}
  


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

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

  int n;
  cin >> n;

  vector<string> s(n);
  vector<int> t(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i] >> t[i];
  }

  string x;
  cin >> x;

  ll ans = 0;
  bool ok = true;
  for (int i = 0; i < n; i++) {
    if (!ok) {
      ans += t[i];
    }

    if (s[i] == x) {
      ok = false;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>

#define llong long long
#define rep(i,l,n) for(llong (i)=(l);(i)<(n);(i++))
#define _min(a,b) ((a)<(b)?(a):(b))
#define _max(a,b) ((a)>(b)?(a):(b))
#define _abs(a) ((a)>0?(a):(-(a)))

using namespace std;

int main(){
	llong N,X,M;
	cin >> N >> X >> M;
	int first[M];
	llong first_sum[M];
	rep(i,0,M){
		first[i] = -1;
		first_sum[i] = 0;
	}
	
	llong ans=0;
	if( M < N ){
		int roop;
		llong roop_ans;
		rep(i,0,N){
			if( first[X]>=0 ){
				roop = i-first[X];
				roop_ans = ans-first_sum[X];
				break;
			}else{
				first[X] = i;
				first_sum[X] = ans;
				ans += X;
			}
			X = (X*X)%M;
		}
		ans += roop_ans*((N-first[X])/roop - 1);
		N = (N-first[X])%roop;
	}
	rep(i,0,N){
		ans += X;
		X = (X*X)%M;
	}
	cout << ans;
}


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

typedef pair<int,int> pint;

int main(){
    int n,m,p,q,r;
    while(cin>>n,n){
        cin>>m>>p>>q>>r;
        vector<pint> cards;
        cards.push_back(pint(1,n));
        int x,y;        
        while(m--){
            cin>>x>>y;
            vector<pint> a,b;
            int count=0;
            for(int i=0;i<cards.size();++i){
                count += cards[i].second - cards[i].first +1;
                if(count>=x){
                    a.insert(a.begin(),cards.begin(),cards.begin()+i+1);
                    a[i].second -= count - x;
                    if(count>x){
                        cards[i].first =a[i].second+1;--i;
                    }
                    cards.erase(cards.begin(),cards.begin()+i+1);
                    break;
                }
            }
            count=x;
            for(int i=0;i<cards.size();++i){
                count += cards[i].second - cards[i].first +1;
                if(count>=y){
                    b.insert(b.end(),cards.begin(),cards.begin()+i+1);
                    b[i].second -= count - y;
                    if(count>y){
                        cards[i].first = b[i].second +1;
                        --i;
                    }
                    cards.erase(cards.begin(),cards.begin()+i+1);
                    break;
                }
            }
            cards.insert(cards.end(),b.begin(),b.end());
            cards.insert(cards.end(),a.begin(),a.end());
        }
        int count = 0,ans=0;
        for(int i=0;i<cards.size();++i){
            count += cards[i].second - cards[i].first +1;
            if(count>=p){
                cards[i].first = cards[i].second -count +p;
                cards.erase(cards.begin(),cards.begin()+i);
                break;
            }
        }
        count=p-1;
        for(int i=0;i<cards.size();++i){
            count += cards[i].second - cards[i].first +1;
            if(count>=q){
                cards[i].second += -count+q;              
                cards.erase(cards.begin()+i+1,cards.end());
                break;
            }
        }
        for(int i=0;i<cards.size();++i){
            ans += max(0,min(r-cards[i].first+1,cards[i].second-cards[i].first+1));
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int

const int maxr = 2e5 + 5;

int arr[maxr];
int32_t main()
{
	GO;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n, greater<int>());
	int count = 1;
	int ans = arr[0];
	for (int i = 1; i < n && count < n - 1; i++) {
		ans += arr[i];
		count++;
		if (count == n - 1)
			break;
		ans += arr[i];
		count++;
	}
	cout << ans << endl;
	return 0;
}

//!

Measured memory_bytes: 5212
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
#define EPS 1e-10
using namespace std;
typedef long long llong;
int main() {
	string s, t;
	while (cin >> s >> t, t != "0") {
		int hit = 0, blow = 0;
		
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (i == j) {
					if (s[i] == t[j])hit++;
				}
				else {
					if (s[i] == t[j])blow++;
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d[i];
  }
  int ret = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      ret += d[i] * d[j];
    }
  }
  cout << ret << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<57;
const double pi=acos(-1);
const double eps=1e-6;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,1,1,1,0},DY[8]={1,0,-1,-1,-1,0,1,1};

class Graph{
	private:
	int V;
	vvp List;
	int Diametarfunc(int s,int& d){
		int ansv;
		vb used(V);
		used[s]=1;
		queue<P> que;
		que.push(P(s,0));
		while(!que.empty()){
			P v=que.front();
			que.pop();
			if(v.second>d){
				ansv=v.first;
				d=v.second;
			}
			for(int i=0;i<List[v.first].size();i++){
				P u=List[v.first][i];
				if(!used[u.first]){
					used[u.first]=1;
					que.push(P(u.first,v.second+u.second));
				}
			}
		}
		return ansv;
	}
	int Diametar(){
		int d=-1,ansl,ansr;
		ansl=Diametarfunc(0,d);
		d=-1;
		ansr=Diametarfunc(ansl,d);
		return d;
	}
	void change_edge(int s){
		List[s][0].second++;
		int t=List[s][0].first;
		for(int i=0;i<List[t].size();i++) if(List[t][i].first==s) List[t][i].second++;
	}
	public:
	Graph(int v){
		V=v;
		List=vvp(v);
	}
	void add_edge(int s,int t,int c){
		List[s].push_back({t,c});
		List[t].push_back({s,c});
	}
	int solve(){
		int num=0;
		for(int i=0;i<V;i++){
			int S=List[i].size();
			if(S==1) num++;
			if(S==2) change_edge(i);
		}
		return num+Diametar();
	}
};

int n;

int main(){
	cin>>n;
	Graph g(n);
	for(int i=1;i<n;i++){
		int s,t;
		cin>>s>>t;
		g.add_edge(s-1,t-1,0);
	}
	cout<<g.solve()<<endl;
}

Measured memory_bytes: 6272
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef long double ld;
typedef vector<ll>VI;
typedef pair<ll,ll>P;
#define VV(T) vector<vector<T>>
#define sz(x) int(x.size())
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
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 vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX6 1001001//6
#define MAX7 10010010//7
#define SENTINEL 2000000000//9
const int MOD = 1000000007;
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define CLR(mat) memset(mat, 0, sizeof(mat))
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}
using Edge=pair<int,ll>;
using Graph=vector<vector<ll> >;//ll or Edge
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// sort_reverse -> greater<long long>()
// vector型から重複を削除 list.erase(unique(ALL(list)),list.end());
// g++ -o a a.cpp -Wall -lm -std=c++17
//push_back -> emplace_back

int main(){
   string S;cin>>S;
   stack<char>st;
   int ans=0;
   rep(i,sz(S)){
      if(S[i]=='S')st.push(S[i]);
      else{
         if(st.size())st.pop();
         else ans++;
      }
   }
   ans+=st.size();
   cout<<ans<<endl;
}

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

int main() {
	int n, u, k, v;
	cin >> n;
	vector<vector<bool>> am(n, vector<bool>(n));
	for (int i = 0; i < n; ++i) {
		cin >> u >> k;
		for (int j = 0; j < k; ++j) {
			cin >> v;
			am[u - 1][v - 1] = true;
		}
	}
	for (vector<bool>& i : am) {
		cout << i[0];
		for (int j = 1; j < n; ++j) cout << ' ' << i[j];
		cout << endl;
	}
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;

#define F first
#define S second
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define sz size()
#define all(A)    A.begin(), A.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define f0(i,b)   for(int i=0;i<(b);i++)
#define f1(i,b)   for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define mod 1000000007

#define forr(i,n)    for(i=0; i<n; i++)
#define whilee(i,t)  while(i!=t)
#define  sl(a)  scanf("%lld",&a)
#define  pl(a)  printf("%lld",a)

//for(auto it =A.begin(); it!=A.end(); it++)
//sort(A.begin(),A.end());
//binary_search(A.begin(),A.end(),x);
//reverse(A.begin(), A.end());
//cout << *max_element(A.begin(), A.end());
//cout << *min_element(A.begin(), A.end());
//count(A.begin(), A.end(), X); //counts the occurrences of X
//distance(A.begin(),A.end());  //distance between first to last element
//accumulate(A.begin(), A.end(), 0); //add
//next_permutation(A.begin(), A.end());
//prev_permutation(A.begin(), A.end());
//swap(S[0], T[0]);
//scanf("%d",&x);
//printf("%d\n",x);

//vector <int> A;
//deque <int> A;
//queue <int> A;
//stack <int> A;
//set <int> A;
//map <int,int> A;
//pair <int,int> A ;
//vector <pair <int,int>> A ;
//char ch;
//string S, T, U;
ll i, j, k, a, b, c, d, f, g, h, l, m, n, p, q, r, s, t, w, x, y, z,maxx=INT_MIN, minn=INT_MAX, ans=0;

int main()
{
    while(true)
    {
        scanf("%d",&n);
        if(n == 0)
        {
            break;
        }
        int A[n];
        forr(i,n)
        {
            scanf("%d",&A[i]);
        }
        int sum=0;
        int best=A[0];
        forr(i,n)
        {
            sum=max(A[i],sum+A[i]);
            best=max(best,sum);
        }
        printf("%d\n",best);
    }
     return 0;
}



Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, q, tmp;
  cin >> n;
  long long sum = 0;
  vector<int> a(100001);
  fill(a.begin(), a.end(), 0);
  for(int i = 0; i < n; i++){
    cin >> tmp;
    a[tmp]++;
    sum += tmp;
  }
  cin >> q;
  for(int i = 0; i < q; i++){
    int b, c;
    cin >> b >> c;
    if(a[b] > 0){
      int dif = c - b;
      sum += dif * a[b];
      a[c] += a[b];
      a[b] = 0;
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 3756
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MAX 100000
typedef long long ll;
typedef pair<int,ll> P;
typedef pair< pair<int,ll>, int> p; 
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/

vector<P> V[510];
P d[510][510];
ll L;



//s…始点
void dijkstra(int s){
  // greater<P>を指定することでfirstが小さい順に取り出せる
  priority_queue<p,vector<p>,greater<p>> que;
  
  que.push(p(P(0,0),s));
  for(int i=0;i<510;i++){
      d[s][i].first=310;
  }
  d[s][s]=P(0,0);

  while(!que.empty()){
    p x=que.top(); que.pop();
    int v=x.second;
    //cout<<s<<" "<<v<<endl;
    if(d[s][v]<x.first) continue;

    for(int i=0;i<(int)V[v].size();i++){
        P e=V[v][i];
        int sum1;
        ll sum2;
        if(e.second>L) continue;
        if(d[s][v].second+e.second>L){
            sum1=d[s][v].first+1;
            sum2=e.second;
        }else{
            sum1=d[s][v].first;
            sum2=e.second+d[s][v].second;
        }
        if(d[s][e.first]>P(sum1,sum2)){
            d[s][e.first]=P(sum1,sum2);
            que.push(p(d[s][e.first],e.first));
        }
    }
    //if(d[v]<p.first) continue;
  }
}


int main(){
    int N,M,a,b;
    ll c;
    cin>>N>>M>>L;
    for(int i=0;i<M;i++){
        cin>>a>>b>>c;
        a--; b--;
        V[a].push_back(P(b,c));
        V[b].push_back(P(a,c));
    }
    for(int i=0;i<N;i++){
        dijkstra(i);
    }
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++){
        int s,t;
        cin>>s>>t;
        s--; t--;
        if(d[s][t].first==310) cout<<-1<<endl;
        else cout<<d[s][t].first<<endl;
    }
}

Measured memory_bytes: 5376
// File Name: D.cpp
// Author: YangYue
// Created Time: Thu Oct 10 12:41:57 2013
//headers 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<LL, LL>PLL;
typedef pair<LL,int>PLI;

#define lch(n) ((n<<1))
#define rch(n) ((n<<1)+1)
#define lowbit(i) (i&-i)
#define sqr(x) ((x)*(x))
#define fi first
#define se second
#define MP make_pair
#define PB push_back

const int MaxN = 2005;
const double eps = 1e-8;
const double DINF = 1e100;
const int INF = 1000000006;
const LL LINF = 1000000000000000005ll;

int dcmp(double x) { return x < -eps ? -1 : x > eps; }
struct Point {
	double x, y;
	Point (){}
	Point(double x, double y) : x(x), y(y) {}
	Point operator - (const Point &b) { return Point(x - b.x, y - b.y); }
	Point operator + (const Point &b) { return Point(x + b.x, y + b.y); }
	Point operator * (const double &b) { return Point(x * b, y * b); }
	Point operator / (const double &b) { return Point(x / b, y / b); }
	Point rot90(int t) { return Point(-y, x) * t; }
	double operator * (const Point &b) { return x * b.y - y * b.x; }
	double operator % (const Point &b) { return x * b.x + y * b.y; }
	double len2() { return x * x + y * y; }
	double len() { return sqrt(x * x + y * y); }
	bool operator < (const Point &b) const {
		if (dcmp(x - b.x) != 0) return dcmp(x - b.x) < 0;
		return dcmp(y - b.y) < 0;
	}
	void init() {
		scanf("%lf%lf", &x, &y); 
	}
} p[MaxN];
bool on_line(Point p, Point p1, Point p2) {
	return dcmp((p - p1) * (p - p2)) == 0;
}
pair<Point, int> keys[MaxN];
bool yes[2][2];
bool check(Point s, Point e, int n, int m) {
	int keysize = 0;
	for (int i = 0; i < n; ++i) {
		if (on_line(p[i], s, e)) keys[keysize++] = make_pair(p[i], i < m ? 0 : 1);
	}
	sort(keys, keys + keysize);
	int i = 0, j = 0;
	for (; i < keysize && keys[i].second == keys[0].second; ++i);
	for (j = i; j < keysize && keys[i].second == keys[j].second; ++j);
	if (j < keysize) return 0;
	memset(yes, 0, sizeof yes);
	for (int i = 0; i < n; ++i) {
		if ((e - s) * (p[i] - s) > eps) {
			int t = i < m ? 0 : 1;
			yes[0][t] = 1;
		}
	}
	for (int i = 0; i < n; ++i) {
		if ((e - s) * (p[i] - s) < -eps) {
			int t = i < m ? 0 : 1;
			yes[1][t] = 1;
		}
	}
	if (yes[0][0] && yes[0][1]) return 0;
	if (yes[1][0] && yes[1][1]) return 0;
	if (yes[0][1] && yes[1][1]) return 0;
	if (yes[0][0] && yes[1][0]) return 0;
	return 1;
}
int main()
{
	//freopen("in","r",stdin);

	int n, m;
	while (1) {
		scanf("%d%d", &n,&m); if (n == 0 && m == 0) break;
		for (int i = 0; i < n + m; ++i) p[i].init();
		bool yes = 0;
		for (int i = 0; i < n + m; ++i) {
			for (int j = i + 1; j < n + m; ++j) {
				if (check(p[i], p[j], n + m, n)) {
					yes = 1;
					break;
				}
			}
			if (yes) break;
		}
		if (yes) puts("YES");
		else puts("NO");
	}

	return 0;
}

// hehe ~

Measured memory_bytes: 1252
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
int main(){
    ll n,k,ans;
    cin>>n>>k;
    ans=k;
    rep(i,1,n)ans*=k-1;
    cout<<ans;
}


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

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define endl '\n'

int const N = 10000001;
int f[N];

void sieve(int n){
    for (int p=1; p<=n; p++){
        f[p]++;
        for (int i=p*2; i<=n; i+=p) f[i]++;
    }
}

void solvetask(){
    int n; cin >> n;
    sieve(n);
    long long ans = 0;
    for (long long i = 1; i <= n; i++) ans += i * (long long) f[i];
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;// cin >> t;
    while(t--) solvetask();
}

Measured memory_bytes: 42668
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;
LL x[N];
LL dp[N];
int main() {
    LL n,a,b;
    scanf("%lld%lld%lld",&n,&a,&b);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i]);

    dp[1]=0;
    for(int i=2;i<=n;i++){
        LL walk=dp[i-1]+(x[i]-x[i-1])*a;
        LL teleport=dp[i-1]+b;
        dp[i]=min(walk,teleport);
    }
    printf("%lld\n",dp[n]);

    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
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<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

ll mod = 1e9 + 7;

int main() {
    ll n, k;
    cin >> n >> k;
    VI a(n);
    REP(i,n) a[i] = in();
    ll ans = 0;
    REP(i,n) FOR(j,i+1,n-1){
        if (a[i] > a[j]) ans = (ans + k) % mod;
        if (a[i] != a[j]) ans = (ans + k * (k - 1) / 2) % mod;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
    int x,a,b;
    scanf("%d%d%d",&x,&a,&b);
    int ans = x-a;
    int i;
    for(i = 0; i < 100; i++){
        if(ans-i*b<0){
            printf("%d",ans-(i-1)*b);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

template <class Abel>
class BIT
{
public:
  using F=function<Abel(Abel,Abel)>;
  F f;
  int l;
  vector<Abel> bit;
  Abel m0;
  BIT(int maxidx,F fu,Abel m0):f(fu),l(maxidx),m0(m0)
  {
    bit.assign(l+1,m0);
  }
  void update(int idx,Abel val)
  {
    idx++;
    while(idx<=l)
    {
      bit[idx]=f(bit[idx],val);
      idx+=idx & -idx;
    }
  }
  Abel query(int idx)
  {
    Abel res=m0;
    while(idx>0)
    {
      res=f(bit[idx],res);
      idx-=idx& -idx;
    }
    return res;
  }
};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  vector<ll>h(n),b(n);
  BIT<ll> bit(n+1,[](ll a,ll b){return max(a,b);},0);
  rep(i,n)
  {
    cin>>h[i];
  }
  rep(i,n)
  {
    cin>>b[i];
  }
  rep(i,n)
  {
    bit.update(h[i],bit.query(h[i])+b[i]);
  }
  cout<<bit.query(n+1)<<endl;
  return 0;

}


Measured memory_bytes: 4992
#include <stdio.h>
 
char a[10];
char b[10];
int count;
 
int main(void)
{
	scanf("%s", a);
	scanf("%s", b);
	for(int i = 0 ; i < 3 ; i++)
	{
		if(a[i] == b[i])
			count++;
	}
	printf("%d", count);
	return 0;
}


Measured memory_bytes: 128
//auto 関数名 = [(&:ラムダ外の引数をとる時))](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 }; //inside main() define function. take care of };
// for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
//   bitset<ビット数> s(tmp);
//   // (ビット列sに対する処理)
// }
// sort(配列変数.begin(), 配列変数.end());
// do {
//   // 順列に対する処理
// } while (next_permutation(配列変数.begin(), 配列変数.end()));
//const double PI = acos(-1); M_PI
// cout << fixed << setprecision(10);
#include <bits/stdc++.h>
#include <regex>
using namespace std;
#define _GLIBCXX_DEBUG 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end() //sort(all(vec)); ,reverse(all(vec));etc
int main(){
  int n,k;
  cin>>n>>k;
  double sum=0;
  vector<int>vec(n);
  rep(i,n){
    cin>>vec.at(i);
  }
  double ans=0;
  for(int i =0;i<n-k+1;i++){
    if(i==0){
    for(int j=0;j<k;j++){
      sum+=double((vec.at(i+j)+1))/double(2);
    }
    ans=sum;
    }else{
    sum=sum-(double((vec.at(i-1)+1))/double(2))+(double((vec.at(i+k-1)+1))/double(2));
    if(sum>ans){
      ans=sum;
    }
    }
    //cout<<sum<<endl;
    }
cout<<fixed<<setprecision(20);
cout<<ans<<endl;
}

  

Measured memory_bytes: 4048
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)
def d(y):
    t=[]
    while y>=2:
        p=x[y]
        t.append(p)
        y=y//p
    t=list(set(t))
    for i in range(len(t)):
        z[t[i]]+=1
    return
g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        d(a[i])
    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")


Measured memory_bytes: 189380
import std.stdio;
import std.string; // chomp????????????????????????(?????????????????????)
import std.conv; // to????????????????????????
import std.array; // split?????????????????????

void main() {
    auto input = readln.split;
    auto a = input[0].to!int;
    auto b = input[1].to!int;
    writeln(a * b, " ", 2 * (a + b));
}

Measured memory_bytes: 2400
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

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

void solve() {
  int n;
  cin >> n;
  bool zero = false;
  ll ret = 0;
  ll minAbs = 2e9;
  int neg = 0;
  while(n--) {
    ll t;
    cin >> t;
    if(t < 0) neg++;
    else if(t == 0) zero = true;
    ret += abs(t);
    minAbs = min(minAbs, abs(t));
  }
  if(!zero && neg%2) ret -= 2*minAbs;
  cout << ret << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
  solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
typedef pair<int, int> P;
ll comb(ll n, ll r)
{
	if (r * 2 > n)
		r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (unsigned int i = 1; i <= r; ++i)
	{
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
int main()
{
	int n;
	cin >> n;
	bool ok = false;
	int row=0;
	FOR(i,1,1000){
		if(i*(i-1)==2*n){
			ok=true;
			row=i;
			break;
		}
	}
	if(ok){
		cout<<"Yes"<<endl;
		deque<int>tmp(n*2);
		vector<vector<int>>ans(row);
		cout<<row<<endl;
		rep(i,n){
			tmp[i]=i+1;
			tmp[i+n]=i+1;
		}
		rep(i,row){
			FOR(j,i+1,row){
				ans[i].push_back(tmp.front());
				ans[j].push_back(tmp.front());
				tmp.pop_front();
			}
		}
		
		rep(i,row){
			cout<<row-1<<" ";
			rep(j,ans[i].size()){
				cout<<ans[i][j];
				if(j!=row-2){
					cout<<" ";
				}else{
					cout<<endl;
				}
			}
		}
	}else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 2816
function main(input) {
  input=input.trim();
  var s=input
  var ans=[]
  for(var i=0; i<Math.floor(s.length/2)+Math.floor(s.length%2); i++){
    ans.push(s.substr(i*2,1))
  }
  console.log(ans.join(""));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 13236
#include <iostream>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <sstream>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
template < typename T > std::string to_string( const T& n ){
        std::ostringstream stm ;
        stm << n ;
        return stm.str() ;
}


void dfs(int &cnt, ll tmp,int n, bool a, bool b, bool c){
    if(tmp>n)return;

    if(a==true){
        if(b==true){
            if(c==true){
                cnt++;
            }
        }
    }


    dfs(cnt, tmp*10+3, n, true, b, c);
    dfs(cnt, tmp*10+5, n, a, true, c);
    dfs(cnt, tmp*10+7, n, a, b, true);
}


int main() {
    int n;cin>>n;
    ll tmp=0;
    int cnt=0;
    bool a=false,b=false,c=false;
    dfs(cnt, tmp, n, a, b, c);

    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int n,m;
int d[11];
int p[11];
int main(){
    cin>>n>>m;
    int ki,si;
    rep(i,m){
        cin>>ki;
        rep(j,ki){
            cin>>si;
            --si;
            d[i]|=(1<<si);
        }
    }
    rep(i,m) cin>>p[i];
    int ans=0;
    rep(i,1<<n){
        bool ok=true;
        rep(j,m){
            int cnt=__builtin_popcount(i&d[j]);
            if((cnt&1)!=p[j]){
                ok=false;
                break;
            }
        }
        if(ok) ++ans;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}



template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WG = vector< Edges< T > >;
using UG = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
struct LowLink {
  const WG<T> &g;
  vector< int > used, ord, low;
  vector< int > articulation;
  vector< pair< int, int > > bridge;

  LowLink(const WG<T> &g) : g(g) {}

  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    for(auto &e : g[idx]) {
      if(!used[e.to]) {
        ++cnt;
        k = dfs(e.to, k, idx);
        low[idx] = min(low[idx], low[e.to]);
        is_articulation |= ~par && low[e.to] >= ord[idx];
        if(ord[idx] < low[e.to]) bridge.emplace_back(minmax(idx, (int) e.to));
      } else if(e.to != par) {
        low[idx] = min(low[idx], ord[e.to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }

  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int n,m;
  cin>>n>>m;
  WG<int> es(n);
  rep(i,m){
    int x,y;
    cin>>x>>y;
    es[x].PB(edge<int>(y,1));
    es[y].PB(edge<int>(x,1));
  }

  LowLink<int> lowlink(es);
  lowlink.build();
  sort(all(lowlink.articulation));
  for(int x:lowlink.articulation){
    cout<<x<<endl;
  }


}


Measured memory_bytes: 7672