akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>

using namespace std;

int P(int a, int b) {
	int ret = 1;
	for (int i = 0; i<b; i++) {
		ret = ret * a;
	}
	return ret;
}

int C(int N, int set) {
	//printf("C(%d, %d) is called\n", N, set);

	int ret;
	int num[3];
	int G, cN, M, count;
	ret = 0;
	num[0] = 3, num[1] = 5; num[2] = 7;
	count = 0;
	for (int i = 0; i<3; i++) {
		if ((set >> i) % 2 == 1) {
			count++;
		}
	}
	if (N<10) {
		for (int i = 0; i<3; i++) {
			if ((set >> i) % 2 == 1) {
				if (num[i] <= N) {
					ret++;
				}
			}
		}
	}
	else {
		M = 0;
		cN = N;
		while (cN >= 10) {
			cN = cN / 10;
			M++;
		}
		G = cN;
		//printf("N = %d, M = %d, G = %d\n", N, M, G);
		for (int i = 0; i<3; i++) {
			if ((set >> i) % 2 == 1) {
				if (G > num[i]) {
					ret = ret + P(count, M);
				}
				else if(G==num[i]) {
					ret = ret + C(N - G * P(10, M), set);
				}
			}
		}


	}
	//printf("C(%d, %d) is finished\n", N, set);
	return ret;
}
int r_ans(int N) {
	return C(N, 7) - C(N, 6) - C(N, 5) - C(N, 3) + C(N, 4) + C(N, 2) + C(N, 1);

}

int main(void) {
	int N, ans;
	scanf("%d", &N);

	int M = 0;
	int cN = N;
	while (cN >= 10) {
		cN = cN / 10;
		M++;
	}
	int pow;
	pow = P(10, M) - 1;
	ans = r_ans(N);

	while (pow > 0) {
		ans += r_ans(pow);
		pow = pow / 10;
	}

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


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

using namespace std;

int main() {
  int e;
  while ((cin >> e) && e != 0) {
    int m = e;
    for (int z=0,zzz=0; zzz<=e; z++,zzz=z*z*z){
      for (int y=0,yy=0; (yy+zzz)<=e; y++,yy=y*y){
        int x = e - (yy+zzz);
        m = min(m, x+y+z);
      }
    }
    cout << m << endl;
  }
  return 0;
}

Measured memory_bytes: 3072
import sys

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    N = len(S)

    for i in range(N):
        s0 = S[i]
        if i <= N-2 and s0 == S[i+1]:
            return '{} {}'.format(i+1, i+2)

        if i <= N-3 and s0 == S[i+2]:
            return '{} {}'.format(i+1, i+3)

    return '-1 -1'


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3188
n, k = map(int, input().split())
X = list(map(int, input().split()))
ans = 10 ** 9
for i in range(n - k + 1):
  if X[i] * X[i + k - 1] < 0:
    dup = min(abs(X[i]), abs(X[i + k - 1])) * 2
    sgl = max(abs(X[i]), abs(X[i + k - 1]))
    dist = dup + sgl
  else:
    dist = max(abs(X[i]), abs(X[i + k - 1]))
  ans = min(ans, dist)
print(ans)

Measured memory_bytes: 14536
from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(e.keys(), reverse=True):
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz)%M
  return ret

N = int(input())
edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Measured memory_bytes: 115288
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=200005,INF=1<<30;

int par[MAX],size[MAX];
vector<pair<int,ll>> G[MAX];

void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
        if(i<100000) size[i]=1;
        else size[i]=0;
    }
}

int root(int a){
    if(par[a]==a) return a;
    else return par[a]=root(par[a]);
}

void unite(int a,int b){
    if(root(a)!=root(b)){
        if(root(a)<root(b)) swap(a,b);
        size[root(a)]+=size[root(b)];
        par[root(b)]=root(a);
    }
}

bool check(int a,int b){
    return root(a)==root(b);
}

struct edge{
    int from;
    int to;
    ll dis;
};

ll sum=0;
ll ans[MAX];

void DFS(int u,int p){
    ans[u]=sum;
    
    for(pair<int,ll> to:G[u]){
        if(to.first==p) continue;
        
        sum+=to.second;
        DFS(to.first,u);
        sum-=to.second;
    }
}


int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    init(200001);
    vector<edge> S(N-1);
    for(int i=0;i<N-1;i++){
        int a,b;ll c;cin>>a>>b>>c;
        a--;b--;
        S[i]={a,b,c};
    }
    
    sort(all(S),[](edge a,edge b){
        return a.dis>b.dis;
    });
    
    for(int i=0;i<N-1;i++){
        int a=size[root(S[i].from)],b=size[root(S[i].to)];
        
        G[100000+i].push_back({root(S[i].from),S[i].dis*b});
        G[100000+i].push_back({root(S[i].to),S[i].dis*a});
        
        unite(S[i].from,100000+i);
        unite(S[i].to,100000+i);
        
    }
    
    DFS(100000+N-2,-1);
    
    for(int i=0;i<N;i++){
        cout<<ans[i]<<endl;
    }
}


Measured memory_bytes: 22528
// AUTHOR : Kishan Srivastav
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main() {
	ios
#ifndef ONLINE_JUDGE
	in;
	out;
#endif
	int a,b;
	cin>>a>>b;
	int ans = 0;
	ans = max(ans , a- 2*b);
	cout<<ans<<endl;

}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main(){
  int k,a,b;
  cin>>k>>a>>b;
  bool ans = false;
  for(int i=a;i<=b;i++){
    if(i%k==0){
   cout<<"OK";
      return 0;
    }
  }
  
     cout<<"NG";
    return 0;
  
}
  
  
  
  
  


Measured memory_bytes: 3596
#include <stdio.h>
#include <string.h>

int main(void){

	char s[200020];
	char t[200020];
	int count;
	int len;

	scanf("%s", s);
	scanf("%s", t);

	count = 0;
	len = strlen(s);
	for (int i = 0; i < len; ++i)
	{
		if (s[i] != t[i])
		{
			count += 1;
		}
	}

	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 2088
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

struct S{
	int y1, x1, y2, x2;
};

int main(){
	int h, w; scanf("%d %d", &h, &w);
	int a[500][500];
	for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){
		scanf("%d", &a[i][j]);
		a[i][j] %= 2;
	}
	vector<S> s;
	for(int i = 0; i < h; i++){
		int n = count(a[i], a[i] + w, 1);
		while(n > 1){
			int* p = find(a[i], a[i] + w, 1);
			int* q = find(p + 1, a[i] + w, 1);
			for(int j = p - a[i]; j < q - a[i]; j++) s.push_back({i, j, i, j + 1});
			*p = *q = 0;
			n -= 2;
		}
		if(n == 1){
			int* p = find(a[i], a[i] + w, 1);
			for(int j = p - a[i]; j < w - 1; j++) s.push_back({i, j, i, j + 1});
			a[i][w - 1] = 1;
		}
	}
	int b[500];
	for(int i = 0; i < h; i++) b[i] = a[i][w - 1];
	int n = count(b, b + h, 1);
	while(n > 1){
		int* p = find(b, b + h, 1);
		int* q = find(p + 1, b + h, 1);
		for(int i = p - b; i < q - b; i++) s.push_back({i, w - 1, i + 1, w - 1});
		*p = *q = 0;
		n -= 2;
	}
	printf("%d\n", s.size());
	for(int i = 0; i < s.size(); i++) printf("%d %d %d %d\n", s[i].y1 + 1, s[i].x1 + 1, s[i].y2 + 1, s[i].x2 + 1);
	return 0;
}

Measured memory_bytes: 5104
<?php
// Your code here!
    fscanf(STDIN,"%d %d",$num1,$num2);

    $vec =array();
   
    for($i=0;$i<$num1;$i++){
        $vec[$i] = array_map('intval',explode(" ",trim(fgets(STDIN))));

    }
    
    for($n=0;$n<$num2;$n++){
        $b_vec[$n] = intval(trim(fgets(STDIN)));
    }
    $old=0;
    
    for($i=0;$i<$num1;$i++){
        for($j=0;$j<$num2;$j++){
            $c_vec = $vec[$i][$j] * $b_vec[$j];
            $c_vec_sum[$i] = $c_vec + $old;
            $old = $c_vec_sum[$i];
        }
        $old=0;
    }
    for($i=0;$i<$num1;$i++){
        echo $c_vec_sum[$i];
        echo "\n";
    }
?>


Measured memory_bytes: 10700
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007ll 
#define pb push_back
#define vl vector<ll>
#define pll pair<ll,ll>
#define mp make_pair
using namespace std;
#define pi (long double)3.14159265358979323846 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 struct sch{
  ll s,e,t;
};
bool sortinrev(const struct sch &a, const struct sch &b) 
{ 
    return (a.s < b.s); 
}
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
}
ll lcm(ll a,ll b)
{
  return a*b/gcd(a,b);
}
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1; 
    x = x % p;  
    while (y > 0) 
    {
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; // y = y/2 
        x = (x*x) % p; 
    } 
    return res; 
}
int main()
{
    ll x;
    cin>>x;
    if(x%2==0)
    {
        cout<<-1<<endl;
        return 0;
    }
    ll ans = 0;
    ll rem = 0;
    while(1)
    {
        rem *= 10;
        rem += 7;
        ans++;
        if(rem%x==0)
            break;
        rem = rem%x;
        if(ans>1000000)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
S = int(input())
mod = 10**9 + 7
q, r = divmod(S, 3)

factorial = [1]
inverse = [1]

for i in range(1, S + 1):
    factorial.append(factorial[i - 1] * i % mod)
    inverse.append(pow(factorial[i], mod - 2, mod))


def C(n, r):
    if n < r:
        return 0
    return (factorial[n] * inverse[r] * inverse[n - r]) % mod


ans = 0
X = S
for i in range(q):
    X -= 3
    ans += C(X + i, i)
    ans %= mod
print(ans)

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

string grid[409];
ll h, w, vis[409][409], black, white;
void func1(ll i, ll j);
void func2(ll i, ll j);

void func2(ll i, ll j)
{
    if(i >= h || i < 0 || j >= w || j < 0 || grid[i][j] != '.' || vis[i][j])
        return;

    white++;
    vis[i][j] = 1;

    if(!vis[i+1][j])
        func1(i+1, j);
    if(!vis[i-1][j])
        func1(i-1, j);
    if(!vis[i][j+1])
        func1(i, j+1);
    if(!vis[i][j-1])
        func1(i, j-1);
}

void func1(ll i, ll j)
{
    if(i >= h || i < 0 || j >= w || j < 0 || grid[i][j] != '#' || vis[i][j])
        return;

    black++;
    vis[i][j] = 1;

    if(!vis[i+1][j])
        func2(i+1, j);
    if(!vis[i-1][j])
        func2(i-1, j);
    if(!vis[i][j+1])
        func2(i, j+1);
    if(!vis[i][j-1])
        func2(i, j-1);

}

int main()
{
    ll i, j, ans = 0;
    scanf("%lld %lld", &h, &w);
    for(i = 0; i < h; i++)
        cin >> grid[i];

    for(i = 0; i < h; i++)
    {
        for(j = 0; j < w; j++)
        {
            if(grid[i][j] == '#' && !vis[i][j])
            {
                black = 0;
                white = 0;
                func1(i, j);
                ans += black*white;
            }
        }
    }

    printf("%lld", ans);
}


Measured memory_bytes: 6784
using System;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] In = Console.ReadLine().Split(' ');
            int[] B = new int[n - 1];
            for(int i=0; i < n - 1; i++)
            {
                B[i] = int.Parse(In[i]);
            }
            long sum = B[0];
            for(int i=0; i < n - 2; i++)
            {
                sum += (int)Math.Min(B[i], B[i + 1]);
            }
            sum += B[n - 2];
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 27556
import math

def main():
    N, M = tuple(map(int, input().split(' ')))
    man_list = []
    point_list = []
    for i in range(N):
        man_list.append(tuple(map(int, input().split(' '))))
    for i in range(M):
        point_list.append(tuple(map(int, input().split(' '))))

    result = []
    for i, man in enumerate(man_list):
        a, b = man
        min_ = float('inf')
        for j, point in enumerate(point_list):
            c, d = point
            v = abs(a-c)+ abs(b-d)
            if len(result) < i+1:
                min_ = v
                result.append(j+1)
                continue
            if v < min_:
                result[i] = j+1
                min_ = v


    for r in result:
        print('{}'.format(r))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <string>
#include <iostream>

using namespace std;

int main() {
    string search; cin >> search;
    int n; cin >> n;
    string rings[n];
    for (int i = 0; i < n; i++) {
        string ring;
        cin >> ring;
        rings[i] = ring + ring;
    }

    int c = 0;
    for (int i = 0; i < n; i++) {
        string ring = rings[i];
        if (ring.find(search) != string::npos) {
            c++;
        }
    }

    cout << c << endl;
    return 0;
}

Measured memory_bytes: 0
func readIntPair() -> (Int, Int) {
    let line = readLine()!.split(separator: " ").map({Int($0)!})
    return (line[0], line[1])
}

func readIntArray() -> [Int] {
    readLine()!.split(separator: " ").map({Int($0)!})
}


let (X, N) = readIntPair()
if N == 0 {
    print(X)
} else {
    let p = readIntArray()
    if !p.contains(X) {
        print(X)
    } else {
        var ans = 101
        (0...101).forEach({
            if !p.contains($0) {
                let temp = max(ans, X) - min(ans, X)
                let dist = max($0, X) - min($0, X)
                if dist < temp {
                    ans = $0
                } else if dist == temp {
                    ans = min(ans, $0)
                }
            }
        })
        print(ans)
    }
}


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

using pii = pair<int, int>;

int main() {
    int n, k; cin >> n >> k;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }

    vector<tuple<short, short, short>> v;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            int dx = x[j] - x[i], dy = y[j] - y[i];
            if(dx == 0) {
                v.emplace_back(x[i] + 20000, 0, 0);
                continue;
            }
            if(dy == 0) {
                v.emplace_back(0, y[i], 0);
                continue;
            }
            if(dx < 0) dx *= -1, dy *= -1;
            const int g = __gcd(dx, abs(dy));
            dx /= g, dy /= g;
            int b = 0;
            if(x[i] < 0) {
                b = y[i] - (x[i] - dx + 1) / dx * dy;
            } else {
                b = y[i] - (x[i] / dx) * dy;
            }
            v.emplace_back(dx, dy, b);
        }
    }
    sort(begin(v), end(v));

    const int sz = v.size();
    bool ans = 0;
    int cnt = 1;
    for(int i = 0; i + 1 < sz; ++i) {
        if(v[i] == v[i + 1]) {
            cnt += 1;
        } else {
            ans |= cnt >= k * (k - 1) / 2;
            cnt = 1;
        }
    }
    ans |= cnt >= k * (k - 1) / 2;

    cout << ans << endl;
}



Measured memory_bytes: 52068
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    string S;
    cin >> N >> S;
    int A = 0;
    for (int i = 0; i < N-2; i++) {
        if (S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C') {
            A++;
        }
    }
    cout << A << endl;
}


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

#define w cout
#define e '\n'
#define int long long
#define sz(x) (int)x.size()
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

const int N = 1e6;

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n ; cin >> n;
	int a , b; cin >> a >> b;
	if(a == 0) return  w << 0 , 0;
	w << 1ll*(n / (a + b))*a + 1ll*min(a , n % (a + b));
}


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


int main() {
   // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    
    long long n, k;
    cin >> n >> k;

    long long r = n % k;
    long long res = min(k - r, r);
    cout << res;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int B[201010];
int W[201010];

int b(int l, int r){
    return B[r] - B[l-1];
}
int w(int l, int r){
    return W[r] - W[l-1];
}

int main(){

    int N;
    cin >> N;
    int ans = N;
    for(int i = 2; i <= N + 1; i++){
        char c;
        cin >> c;
        B[i] = B[i - 1];
        W[i] = W[i - 1];
        if(c == '#')B[i]++;
        else W[i]++;
    }
    B[N + 2] = B[N + 1];
    W[N + 2] = W[N + 1];
    for(int i = 1; i <= N + 1; i++){
        int tmp = b(1, i) + w(i + 1, N + 2);
        ans = min(ans, tmp);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll MAX=71;
const ll MOD=2100000000;
ll a,b,fin=0,n;
ll div2(ll x,ll y,ll u){
    if(y-x==1ll) return x;
    ll p=(x+y)/2ll;
    if((p-p/2ll)*(p/2ll)<u) return div2(p,y,u);
    return div2(x,p,u);
}
int main(){
    ll t;
    scanf(" %lld",&n);
    for(int i=0;i<n;i++){
    scanf(" %lld %lld",&a,&b);
    if(a>b) swap(a,b);
    fin+=(a-1ll)*2ll;
    t=div2(1ll,MOD,a*b);
    fin+=max(t-2*a,0ll);
    printf("%lld\n",fin);
    fin=0;
    }
}

/*
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll MAX=71;
const ll MOD=1300000007;
ll a,b,fin=0,n;
ll div2(ll x,ll y,ll u){
    if(y-x==1ll) return x;
    ll p=(x+y)/2ll;
    if((p-p/2ll)*(p/2ll)<u) return div2(p,y,u);
    return div2(x,p,u);
}
int main(){
    ll t;
    scanf(" %lld",&n);
    for(ll i=0;i<n;i++){
        scanf(" %lld %lld",&a,&b);
        if(a>b) swap(a,b);
        fin+=(a-1ll);
        if(a==b) t=div2(0,MOD,a*b);
        t=div2(1ll,MOD,a*b);
        fin+=max(t-2*a,0ll);
        printf("%lld\n",fin);
        fin=0;
    }
}
*/


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
 
using namespace std;
 
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-10;

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

int t, d, ta, tb, da, db;

double calc(int va, int vb){
	return (double)(ta*va+tb*vb)/(va+vb);
}

int main(){
	cin>>t>>d>>ta>>tb>>da>>db;
	double ans = 1e9;
	for(int i = 0; i <= d; i+=da){
		for(int j = 0; i + j <= d; j+=db){
			if(i+j==0) continue;
			ans = min(ans, abs(t-calc(i, j)));
		}
	}
	printf("%.15lf\n", ans);

}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#define ll long long
#define endl '\n'
using namespace std;
int N, M;

vector<int> adj[9];
bool visited[9];

bool ok()
{
    for(int i = 1; i <= N; i++)
        if(!visited[i]) return false;
    return true;
}

int dfs(int cur)
{
    visited[cur] = true;
    int ret = 0;
    if(ok())
        ret = 1;
    
    for(int i = 0; i < adj[cur].size(); i++)
    {
        auto next = adj[cur][i];
        if(visited[next]) continue;
        ret += dfs(next);
    }
    
    visited[cur] = false;
    return ret;
}

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    cin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    cout << dfs(1) << endl;
    return 0;
}


Measured memory_bytes: 888
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C - management
 */

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

/* constant */

const int MAX_N = 200000;

/* typedef */

/* global variables */

int cs[MAX_N];

/* subroutines */

/* main */

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

  for (int i = 1; i < n; i++) {
    int ai;
    scanf("%d", &ai);
    ai--;
    cs[ai]++;
  }

  for (int i = 0; i < n; i++) printf("%d\n", cs[i]);
  return 0;
}


Measured memory_bytes: 3976
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define STRINGIFY(n) #n
#define TOSTRING(n) STRINGIFY(n)
#define PREFIX "#" TOSTRING(__LINE__) "| "
#define debug(x) \
{ \
  std::cout << PREFIX << #x << " = " << x << std::endl; \
}

std::ostream& output_indent(std::ostream& os, int ind) {
  for(int i = 0; i < ind; i++) os << " ";
  return os;
}

template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p);
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);

template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) {
  return (os << "(" << p.first << ", " << p.second << ")");
}
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "[";
  for(int i = 0;i < v.size();i++) os << v[i] << ", ";
  return (os << "]");
}

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) { return std::vector<T>(n, std::forward<T>(val)); }
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}
template<class Cond> struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  template<class T> bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; }
};
template<class Cond> chain<Cond> make_chain(Cond cond) { return chain<Cond>(cond); }

int main() {
  i64 N;
  cin >> N;
  string S;
  cin >> S;
  vector<i64> R(N + 1);
  vector<i64> W(N + 1);
  rep(i,0,N) {
    R[i + 1] += R[i];
    W[i + 1] += W[i];
    if(S[i] == 'R') R[i + 1]++;
    else W[i + 1]++;
  }
  i64 ans = N;
  rep(i,0,N + 1) {
    i64 left = W[i];
    i64 right = R[N] - R[i];
    ans = std::min(ans, std::max(left, right));
  }
  cout << ans << endl;
}


Measured memory_bytes: 6808
N = int(input())
dp = [[0 for i in range(3)] for j in range(N + 1)]
for i in range(1, N + 1):
    a, b, c = map(int, input().split())
    dp[i][0] = max(dp[i][0], dp[i - 1][1] + a)
    dp[i][0] = max(dp[i][0], dp[i - 1][2] + a)
    dp[i][1] = max(dp[i][1], dp[i - 1][0] + b)
    dp[i][1] = max(dp[i][1], dp[i - 1][2] + b)
    dp[i][2] = max(dp[i][2], dp[i - 1][0] + c)
    dp[i][2] = max(dp[i][2], dp[i - 1][1] + c)

ans = max(dp[N])
print(ans)


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

int main(){
  int num;
  int cnt = 0;
  int tmpCnt = 0;
  
  cin >> num;
  
  vector<int> vec(num);
  for(int i = 0; i < num; i++) cin >> vec.at(i);
  
  for(int i = 0; i < num-1; i++){
    if(vec.at(i) >= vec.at(i+1)) tmpCnt++;
    
    if(tmpCnt > cnt) cnt = tmpCnt;
    if(vec.at(i) < vec.at(i+1)) tmpCnt = 0;
  }
  
  cout << cnt;
}

Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;

int main()
{
	int n;
	cin>>n;
	int *A = new int[n];
	int *B = new int[n];
	for(int i = 0; i < n; i++){
		cin>>A[i];
		B[i] = A[i];
	}
	sort(B,B+n,greater<int>());
	int max = B[0];
	int secondMax = B[1];
	for(int i = 0; i < n; i++){
		if( A[i] == max){
			cout<<secondMax<<endl;
		}else{
			cout<<max<<endl;
		}
	}
	return 0;
}



Measured memory_bytes: 3200
fun main(args: Array<String>) {
    val s = readLine()!!
    val t = readLine()!!

    val s1 = s.length
    val t1 = t.length

    var best = 1000000
    (0 .. (s1 - t1)).forEach {skip ->
        val diff = s.drop(skip).zip(t).count { it.first != it.second }
        best = Math.min(best, diff)
    }
    println(best)
}


Measured memory_bytes: 45284
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_set>
#include<vector>
#include<utility>
#include<cstring>
#define pb(a)             push_back(a)
#define mp(a,b)           make_pair(a,b)
#define pf printf
#define ff first
#define ss second
#define sef second.first
#define ses second.second
#define ms(a,b)            memset(a, b, sizeof(a))
#define loop(i,a)          for(int i=1;i<=a;i++)
#define pii                pair <int,int>
#define sl(a)              scanf("%I64d",&a)
#define sll(a,b)           scanf("%I64d %I64d",&a,&b)
#define si(a)              scanf("%d",&a)
#define sii(a,b)           scanf("%d %d",&a,&b)
using namespace std ;
const int maxx = 8e4+10;
//typedef pair < int , pii > node ;
//node tree[4*maxx],lazy[4*maxx];
int tree[4*maxx],lazy[4*maxx] ;
int main()
{
     int n,f=0;
     cin >> n ;
     while(n>9)
     {
         int x = n%10;
         if(x==7){f=1;}
         n=n/10;
     }
     if(n==7){f=1;}
     if(f==1){cout << "Yes" << endl;}
     else{cout << "No" << endl;}
  return 0 ;
}


Measured memory_bytes: 3624
"""
map(int,input().split())

X = input().split()
x = []
for i in range(0,len(X)):
    x.append(X[i])

"""

N = int(input())
S = input()
K = int(input())-1

sls = []

for w in S:
    sls.append(w)

getW = S[K]
out = ""

for i in range(0,N):
    if sls[i] != getW:
        sls[i] = "*"
    out += sls[i]


print(out)

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

ll solve() {
    ll N;
    cin >> N;
    string S;
    cin >> S;
    ll c = 0;
    for ( int i = 0; i < N-2; i++ ) {
        if ( S.substr(i,3) == "ABC" ) c++;
    }
    
    return c;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
n = int(stdin.readline())
a = []
for _ in xrange(n):
    s = stdin.readline().strip()
    di = {}
    for i in s:
        di[i] = di.get(i,0) + 1
    a.append(di)       
ans = ''
b = 'abcdefghijklmnopqrstuvwxyz'
for i in b:
    x = 10**5
    for yy in a:
        x = min(x, yy.get(i,0))
    ans += x*i
print ans    

Measured memory_bytes: 2692
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
      
n = int(input())
la = list(map(int, input().split()))
import sys
if my_index(la, 0) > 0:
  print(0)
  sys.exit()

ans = 1
for i in la:
  ans *= i
  if ans > 10**18:
    print(-1)
    sys.exit()
print(ans)

Measured memory_bytes: 21656
#include <bits/stdc++.h>
#include<stdio.h>
#define ll  long long
#define ull unsigned long long  
using namespace std;
#define  inf 1e9+18
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define  f1(i,n) for(i=1;i<=n;i++)
#define f0(i,n)  for(i=0;i<n;i++)
#define w(x)   while(x--)
const int maxn=105;
#define  pq priority_queue
#define  ff first
#define  ss second 
#define pb  push_back
#define lb lower_bound
#define ub upper_bound
#define pie 3.14159265359
#define mod 1000000007
double dp[3005][3005];
double possible_ways(int h,int t,int n,double a[],int cnt)
{
 // cout<<cnt<<" "<<h<<" "<<t<<"\n";
  if(cnt==n&&h>t)
    return 1.0;
  else if(cnt==n)
    return 0;
  if(dp[h][t]>-0.9)
    return dp[h][t];
  double ans=a[cnt]*possible_ways(h+1,t,n,a,cnt+1)+(1.0-a[cnt])*possible_ways(h,t+1,n,a,cnt+1);
  dp[h][t]=ans;
  return ans;

}
int main()
{
  
 int n,m,i,j;;
 cin>>n;
  double a[n];
 f0(i,n)
    cin>>a[i];
    memset(dp,-1,sizeof(dp));
cout<<fixed<<setprecision(9)<<possible_ways(0,0,n,a,0);
}

Measured memory_bytes: 71040
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
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;
}
//

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

  lint n;
  cin >> n;
  n--;
  cout << n * (n + 1) / 2 << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
//[int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

/*--------------------template--------------------*/

int main()
{
	int n;
	while (cin >> n, n)
	{
		map<pii, int> mp;
		vector<vector<pii>> v;
		REP(i, n)
		{
			int x, y; char c;
			cin >> x >> y >> c;
			auto l = pii(x, y);
			if (c == 'x') x++;
			else y++;
			auto r = pii(x, y);
			mp[l] = i;
			mp[r] = i;
			v.emplace_back(vector<pii>{l, r});
		}
		vector<bool> vis(n);
		map<pii, bool> con;
		bool ans = true;
		REP(i, n)
		{
			if (vis[i]) continue;
			vis[i] = true;
			queue<pii> que;
			REP(j, 2)
			{
				que.push(v[i][j]);
				con[v[i][j]] = j;
			}
			while (que.size())
			{
				int tx = que.front().first, ty = que.front().second;
				pii tmp = que.front();
				que.pop();
				REP(j, 4)
				{
					int nx = tx + dx[j], ny = ty + dy[j];
					pii t(nx, ny);
					if (mp.find(t) == mp.end()) continue;
					int futon = mp[t];
					pii oth;
					if (v[futon][0] == t) oth = v[futon][1];
					else oth = v[futon][0];
					if (oth == tmp) continue;

					if (con.find(t) == con.end())
					{
						con[t] = con[tmp];
						con[oth] = 1 - con[tmp];
						que.push(t); que.push(oth);
						vis[futon] = true;
					}
					else
					{
						if (con[t] != con[tmp]) 
							ans = false;
					}
				}
			}
		}
		puts(ans ? "Yes" : "No");
	}
	return 0;
}

Measured memory_bytes: 8700
#include"bits/stdc++.h"
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

int main() {
	int n, a,pos=0,index=0;
	ll k;
	cin >> n >> k;
	set<int>cycle;
	vi city,tere;
	rep(i, n) {
		cin >> a;
		city.push_back(--a);
	}
	while(!cycle.count(pos)) {	//サイクル検出するまで繰り返し
		cycle.insert(pos);
		tere.push_back(pos);
		pos = city[pos];
	}
	for (int s : tere) {	//サイクルにたどり着くまでのワープ回数
		if (s == pos) break;
		else index++;
	}
	if (k <= index) cout << tere[k] + 1 << endl;	//サイクル以前で王が満足
	else {
		k -= index;
		cout << tere[index + (k % (tere.size() - index))] + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 13840
#include<iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;
int main()
{
	int N, D, X;
	int A[100];
	int add = 0;
	int Ans = 0;

	cin >> N >> D >> X;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (int n = 0; n < N; n++) {
		for (int d = 0; d < D; d++) {
			if ((d*A[n] + 1)<=D) {
				add++;
			}
		}
	}

	Ans = add + X;

	cout << Ans;

	return 0;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(int argc, char const *argv[])
{
	VI ret;
	int n;
	while(true){
		cin >> n;
		if(n == 0) break;
		VI a(n);
		REP(i, n)
			cin >> a[i];
		SORT(a);
		a.erase(a.begin());
		a.pop_back();
		int size = a.size();
		int sum = 0, ave = 0;
		REP(i, size)
			sum += a[i];
		ave = sum / size;
		ret.PB(ave);
	}

	REP(j, ret.size())
		cout << ret[j] << endl;

	return 0;
}

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

vector<vector<int>> to;
vector<bool> visited;
vector<int> topologicalsort;

void tsort(int v){
  // v以下の要素を全部列挙
  if( visited[v]){ return ;}
  visited[v] = true;
  
  if( !to[v].empty()){
   for(auto u : to[v]){
     
     if(visited[u]){ continue;}
     
     tsort(u);
   }
  }
  
  topologicalsort.push_back(v);
}
    

int main(){
  int n,m; cin >> n >> m;
  
  to.resize(n); visited = vector<bool>(n,false); //falseは未到達
  
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b; a--; b--;
    to[a].push_back(b);
  }
  
  for(int i = 0; i < n; i++){
    sort(to[i].begin(),to[i].end());
    tsort(i);
  }
  
  reverse(topologicalsort.begin(),topologicalsort.end());
  
  for(auto ne : topologicalsort){cout << ne+1 << endl; 
                               }
  
  for(int i = 0; i < n-1; i++){
    
    int res1 = topologicalsort[i];
    int res2 = topologicalsort[i+1];
    if( !binary_search(to[res1].begin(),to[res1].end(),res2)){
      cout << 1 << endl; return 0;
    }
  }
  
  cout << 0 << endl; return 0;
  
}
    


Measured memory_bytes: 3792
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
using namespace std;

int main() {
	int x, a, b;
	cin >> x >> a >> b;
	if (b - a <= 0) {
		cout << "delicious" << endl;
	}
	else {
		if (x >= b - a) {
			cout << "safe" << endl;
		}
		else {
			cout << "dangerous" << endl;
		}
	}
}

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

int main() {
	int n,k;
	cin>>n>>k;
	double ans = 0.0;
	for(int i=1;i<=n;++i) {
		if(i>=k) {
			ans += (1.000000000/n);
		} else {
			double j = log2(k)-log2(i);
			ans += (1.000000000/n)*(pow((0.500000000),ceil(j)));
		}
	}
	printf("%.9f", ans);
	return 0;
}

Measured memory_bytes: 384
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
using namespace std;
#define U(v) \
cerr << #v << ": " << (v) << endl

int main() {
    int H, W, N;
    cin >> H >> W >> N;
    map<pair<int, int>, int> mp;
    for (int i = 0; i < N; ++i) {
        int y, x;
        cin >> y >> x;
        --x;
        --y;
        for (int dy = -2; dy <= 0; ++dy) {
            for (int dx = -2; dx <= 0; ++dx) {
                if (x + dx < 0 || y + dy < 0 || x + dx + 2 >= W || y + dy + 2 >= H) continue;
                ++mp[{ x + dx, y + dy }];
            }
        }
    }
    vector<int> ct(10, 0);
    for (auto& p : mp)
        ++ct[p.second];
    long long sm = (long long)(W - 2) * (H - 2);
    for (int i : ct)
        sm -= i;
    cout << sm << endl;
    for (int i = 1; i < 10; ++i)
        cout << ct[i] << endl;
    return 0;
}


Measured memory_bytes: 56448
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
#define ll long long
const int mod = 998244353, maxn = 1e5+10;
int N, M, K;
int dp[3030][3030], path[3030][3030][2];
char s[3030], t[3030];

int main()
{
    scanf("%s %s", s, t);
    int ls = strlen(s), lt = strlen(t);
    for(int i = 1; i <= ls; i++)
        for(int j = 1; j <= lt; j++)
        {
            if(dp[i][j-1] > dp[i-1][j])
                path[i][j][0] = path[i][j-1][0], path[i][j][1] = path[i][j-1][1];
            else
                path[i][j][0] = path[i-1][j][0], path[i][j][1] = path[i-1][j][1];
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            if(dp[i-1][j-1]+(s[i-1]==t[j-1]) > dp[i][j])
            {
                dp[i][j] = dp[i-1][j-1]+(s[i-1]==t[j-1]);
                path[i][j][0] = i-1, path[i][j][1] = j-1;
            }
        }
//    printf("%d\n", dp[ls][lt]);
    int cnt = dp[ls][lt], px = path[ls][lt][0], py = path[ls][lt][1];
    stack<char> sta;
    while(cnt--) {
        sta.push(s[px]);
        ls = px, lt = py;
        px = path[ls][lt][0], py = path[ls][lt][1];
    }
    while(!sta.empty()) {
        printf("%c", sta.top());
        sta.pop();
    }
    return 0;
}


Measured memory_bytes: 109568
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n,k = MAP()

p = LIST()
#
# i=0
# j = k-1

mx = 0

for i in range(k):
    mx+=(p[i]+1)/2
    # print(mx)
gndMax = mx
i = 1
j=k
# print(mx)
while(j<n):
    mx = mx + (p[j] + 1) / 2 - (p[i - 1] + 1) / 2
    gndMax=max(gndMax, mx)
    i+=1
    j+=1
    # print(mx, gndMax)
print(gndMax)


Measured memory_bytes: 102628
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <set>
#define MAXX 111
#define ll long long
using namespace std;

// 01, 32
// 00, 22



int main() {
    int a,b;
    cin>>a>>b;
    cout << a-1+(b>=a) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, s, n) for (int i = s; i < (n); i++)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
ll INF = 1e15;
struct edge
{
    int to;
    int cost;
};
vector<edge> v[100010];
ll fl[100010];
int n, m;
bool dfs(int n)
{
    bool ans = true;
    rep(i, v[n].size())
    {
        if (fl[v[n][i].to] != INF)
        {
            if (fl[v[n][i].to] != fl[n] + v[n][i].cost)
            {
                ans = false;
            }
        }
        else
        {
            fl[v[n][i].to] = fl[n] + v[n][i].cost;
            ans &= dfs(v[n][i].to);
        }
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    rep(i, m)
    {
        int l, r, d;
        cin >> l >> r >> d;
        edge e;
        e.to = r;
        e.cost = d;
        v[l].push_back(e);
        e.to = l;
        e.cost = -d;
        v[r].push_back(e);
    }
    rep(i, n + 1)
    {
        fl[i] = INF;
    }
    bool ans = true;
    rep(i, n + 1)
    {
        if (fl[i] == INF)
        {
            fl[i] = 0;
            ans &= dfs(i);
        }
    }
    if (ans)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 12416
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("3 1 2");
            WillReturn.Add("6 1 1");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("2 100 100");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("5 1 1");
            WillReturn.Add("100 1 1");
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        int PrevT = 0;
        int PrevX = 0, PrevY = 0;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int CurrT = wkArr[0];
            int CurrX = wkArr[1];
            int CurrY = wkArr[2];

            int DiffT = CurrT - PrevT;
            int DiffX = Math.Abs(CurrX - PrevX);
            int DiffY = Math.Abs(CurrY - PrevY);

            if (DiffT < DiffX + DiffY) {
                Console.WriteLine("No");
                return;
            }
            if ((DiffT - DiffX - DiffY) % 2 == 1) {
                Console.WriteLine("No");
                return;
            }
            PrevT = CurrT;
            PrevX = CurrX;
            PrevY = CurrY;
        }
        Console.WriteLine("Yes");
    }
}


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

int main()
{
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    int white_cnt = 0;
    for (int i = 0; i < h; i++)
    {
        cin >> s[i];
        for (int j = 0; j < w; j++)
        {
            if(s[i][j] == '.')white_cnt++;
        }
    }

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

    vector<vector<int>> seen(h, vector<int>(w, -1));
    queue<pair<int, int>> que;

    seen[0][0] = 0;
    que.push(make_pair(0, 0));

    while (!que.empty())
    {
        pair<int ,int> pos = que.front();
        int x = pos.first, y = pos.second;
        que.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            
            if(nx < 0 || nx >= h || ny < 0 || ny >= w)continue;
            if(s[nx][ny] == '#')continue;

            if(seen[nx][ny] == -1)
            {
                que.push(make_pair(nx, ny));
                seen[nx][ny] = seen[x][y] + 1;
            }
        }
    }

    if(seen[h - 1][w - 1] == -1)cout << -1 << endl;
    else cout << white_cnt - seen[h - 1][w - 1] - 1 << endl;
}

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

int main() {
    int n, m, x;

    cin >> n >> m >> x;

    int a[m];

    for(int i = 0; i < m; i++) {
        cin >> a[i];
    }

    int res_go = 0;
    int res_back = 0;

    for(int i = x; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[j] == i) {
                res_go++;
            }
        }
    }

    for(int i = x; i > 0; i--) {
        for(int j = 0; j < m; j++) {
            if(a[j] == i) {
                res_back++;
            }
        }
    }

    if(res_go > res_back) {
        cout << res_back << endl;
    }
    else {
        cout << res_go << endl;
    }


}

Measured memory_bytes: 256