akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define ll long long

const ll INF= 1LL << 60;
const int N_MAX=110;
const int V_MAX=100100;//100*1000

//入力
ll N;
ll W;
ll w[N_MAX];
ll v[N_MAX];
//dp
ll dp[N_MAX][V_MAX];

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

  for(int i=0;i<N;i++){
    cin >> w[i] >> v[i];
  }
  for(int i=0;i<N_MAX;i++)
    for(int j=0;j<V_MAX;j++)
      dp[i][j]=INF;
  
  dp[0][0]=0;
  
  for(int i=0;i<N;i++){
    for(int j=0;j<=V_MAX;j++){
      if(j-v[i]>=0) chmin(dp[i+1][j],dp[i][j-v[i]]+w[i]);
      chmin(dp[i+1][j],dp[i][j]);
    }
  }
  ll v_max=0;
  for(int i=0;i<V_MAX;i++){
    if(dp[N][i]<=W) v_max=i;
  }
  
  cout << v_max << endl;
}

Measured memory_bytes: 86400
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void solve() {
    ll N;
    cin >> N;
    vector<pair<ll,ll>> v(N);
    REP(i,N) {
        ll A,B;
        cin >> A >> B;
        v[i] = make_pair(A,B);
    }

    reverse(ALL(v));

    cerr << "3%5=" << 3%5 << endl;
    ll push = 0;
    REP(i,N) {
        cerr << push << endl;
        ll val = push + v[i].first;
        push += (v[i].second - (val%v[i].second)) % v[i].second;
    }

    cout << push << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 1920
#include <cstdio>
#include <algorithm>
using namespace std;

#define N 200005
#define int long long

int n,c[N],num[N],ans[N],C[N];
int tot,head[2*N],than[2*N],to[2*N]; 

inline int read(){
	int s=0,t=1;
	char c=getchar();
	while((c<'0'||c>'9')&&c!='-')c=getchar(),t=-1;
	if(c=='-')c=getchar(),t=-1;
	while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*t;
}

void add(int x,int y){
	tot++;
	to[tot]=y;
	than[tot]=head[x];
	head[x]=tot;
}

void dfs(int now,int p=-1){
	int tmp=C[c[now]];
	for(int i=head[now];i;i=than[i]){
		int t=to[i];
		if(t==p)continue;
		C[c[now]]=0;
		dfs(t,now);
		num[now]+=num[t];
		ans[c[now]]-=(num[t]-C[c[now]])*(num[t]-C[c[now]]+1)/2; 
	}
	C[c[now]]=tmp+num[now];
}

signed main(void){
	n=read();
	for(int i=0;i<n;i++)
	c[i]=read(),c[i]--,num[i]=1;
	for(int i=1;i<n;i++){
		int x,y;
		x=read()-1;
		y=read()-1;
		add(x,y);
		add(y,x);
	}
	dfs(0);
	for(int i=0;i<n;i++){
		int f=n*(n+1)/2;
		int f1=(n-C[i])*(n-C[i]+1)/2;
		printf("%lld\n",ans[i]+f-f1);
	}
//	for(int i=0;i<n;i++)
//	printf("%d ",ans[i]); 
} 

Measured memory_bytes: 31596
#include<bits/stdc++.h>
using namespace std;
int dp[100002][13];
const int mod = 1e9+7;
int main(){
    string s;
    cin>>s;
    int n = s.size();
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<13;j++){
            if(s[i-1]!='?'){
                int tmp = s[i-1]-'0';
                dp[i][(10*j+tmp)%13] += dp[i-1][j];
                dp[i][(10*j+tmp)%13] %= mod;
            }else{
                for(int t=0;t<10;t++){
                    dp[i][(10*j+t)%13] += dp[i-1][j];
                    dp[i][(10*j+t)%13] %= mod;
                }
            }
        }
    }
    cout<<dp[n][5]<<endl;
    return 0;
}

Measured memory_bytes: 5504
#include<stdio.h>

int main(void){
  int i;
  int k,cnum,c,csum;

  for(;;){
    scanf("%d",&k);
    if(k==0)
      break;

    cnum=k*(k-1)/2;

    csum=0;
    for(i=0;i<cnum;i++){
      scanf("%d",&c);
      csum+=c;
    }

    csum/=k-1;

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

  return 0;
}

Measured memory_bytes: 0
// https://atcoder.jp/contests/abc132/tasks/abc132_a
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
// clang-format on
int main()
{
    string S;
    cin >> S;
    set<char> C;
    REP(i, (int)S.size())
    {
        C.emplace(S[i]);
    }
    cout << (C.size() == 2 ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {

    

    class ClassMain {



        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                int n = int.Parse(line);
                if (n == 0) { break; }
                int a = 0;
                bool flg = true;
                for (int i = 0; i < n; i++) {
                    string[] strs = Console.ReadLine().Split(' ');
                    int n2 = int.Parse(strs[1]);
                    char ch = strs[0].ToCharArray()[0];
                    if (ch == '(') { a += n2; }
                    else { a -= n2; }
                    if (a < 0) { flg = false; break; }
                }
                if (a > 0) { flg = false; }
                if(flg){
                Console.WriteLine("YES");
                }else{
                    Console.WriteLine("NO");
                }
                break;
            }
        }

    }

    
}

Measured memory_bytes: 19660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2100000000
#define MOD 1000000007

bool dbgflag = false; //debug

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll x;
  cin >> x;
  int year = 0;
  ll m = 100;
  while (x > m) {
    year++;
    m *= 1.01;
  }

  cout << year << endl;

}


Measured memory_bytes: 3648
from math import sqrt
n,d = map(int, input().split())
X = [list(map(int, input().split())) for i in range(n)]

ans = 0
for i in range(n):
    for j in range(i,n):
        if i == j: continue
        tem = 0
        for k in range(d):
            tem += (X[i][k] - X[j][k])**2
        #print(int(sqrt(tem))**2)
        if int(sqrt(tem))**2 == tem:
            #print(i,j,tem)
            ans += 1
print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		int secret_num = 0;
		for(; scanner.hasNext();)
		{
			String input = scanner.next();
			
			for(int i=0; i<input.length(); i++)
			{
				char c = input.charAt(i);
				int num = 0;
				for(;'0'<=c && c<='9';)
				{
					num = 10*num + Integer.parseInt(input.substring(i, i+1));
					
					if(++i < input.length())
					{
						c = input.charAt(i);
					}
					else
					{
						break;
					}
					
				}				
				secret_num += num;
			}
		}
		
		System.out.println(secret_num);
	}
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairInt;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[])
{
  int N, D;

  scanf("%d%d", &N, &D);

  ll ans = 0;
  int floor = 1;
  int person = 0;
  int time = 0;
  int i = 0;
  bool flag = true;
  while (i < N) {
    int t, f;
    scanf("%d%d", &t, &f);
    if (t - time >= floor + f - 2) {
      ans += (ll)person * (floor - 1);
      floor = f;
      person = 1;
      time = t;
    } else if (t - time >= abs(f - floor) && person < D) {
      ans += (ll)person * (t - time);
      floor = f;
      person++;
      time = t;
    } else {
      flag = false;
      break;
    }
    i++;
  }

  if (flag == true) {
    ans += (ll)person * (floor - 1);
    printf("%lld\n", ans);
  } else {
    printf("-1\n");
  }
  
  return 0;
}

Measured memory_bytes: 3172
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=10010,mo=1e9+7;
int fa[N],n,m;
struct edge{int x,y,z;}w[N];
ll sum,X,ans,ans1,ans2;
int c1,c2;
bool comp(edge a,edge b){
	return a.z<b.z;
}
int gf(int x){
	return (fa[x]==x?x:fa[x]=gf(fa[x]));
}
ll power(ll a,ll b){
	ll ans=1;
	while (b){
		if (b&1)ans=ans*a%mo;
		a=a*a%mo;
		b>>=1;
	}return ans;
}
int main(){
	cin>>n>>m>>X;
	for (int i=1;i<=m;i++)
		scanf("%d%d%d",&w[i].x,&w[i].y,&w[i].z);
	ans1=ans2=m;
	ll m1=1e12,m2=1e12;
	sort(w+1,w+m+1,comp);
	for (int d=1;d<=m;d++){
		for (int i=1;i<=n;i++)fa[i]=i;
		sum=w[d].z;
		fa[w[d].x]=w[d].y;
		for (int i=1;i<=m;i++){
			int x=w[i].x,y=w[i].y;
			if (gf(x)!=gf(y)){
				sum+=w[i].z;
				fa[gf(x)]=gf(y);
			}
		}
		c1+=sum>=X;
		c2+=sum>X;
	}
	if (c1==c2){
		cout<<0<<endl;
		return 0;
	}
	if (c2==0){
		cout<<(power(2,min(m,c1+1))-2+mo)%mo<<endl;
		return 0;
	}
	cout<<(power(2,(min(m,c1+1)))-power(2,min(m,c2+1))+mo)%mo<<endl;
}

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

struct edge {
    int to;
    int cost;
};
using P = pair<int, int>;
vector<vector<edge>> G;
vector<int> d;
void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P>> que;
    fill(d.begin(), d.end(), INF);
    d[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first)
            continue;
        rep(i, G[v].size()) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    G.resize(N);
    d.resize(N);

    rep(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        if(a==0&&b==N-1)
            continue;

        G[a].push_back({b, 1});
    }

    dijkstra(0);

    if(d[N-1]==2)
        cout << "POSSIBLE";
    else
        cout << "IMPOSSIBLE";
    cout << endl;

    return 0;
}

Measured memory_bytes: 11124
console.log(function(args){
  const [[N],...tmp] = args.trim().split('\n').map( r=>r.split(' ').map(v=>v|0) );
  const tree = Array.from({length:N},_=>[]);
  for ( let i = 0; i < N-1; i++ ) {
    const [u,v,w] = tmp[i];
    tree[u-1].push([v-1,w&1]);
    tree[v-1].push([u-1,w&1]);
  }
  const color = Array.from({length:N},_=>NaN);
  color[0] = 0;
  const stack = [0];
  while ( stack.length ) {
    const u = stack.pop();
    for ( const [v,w] of tree[u] ) {
      if ( isFinite(color[v]) ) continue;
      stack.push(v);
      if ( w ) color[v] = ~color[u]&1;
      else color[v] = color[u];
    }
  }
  return color.join('\n');
}(require('fs').readFileSync('/dev/stdin', 'utf8')));


Measured memory_bytes: 104276
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int, int> P;
 
int main(){
  int n, m;
  cin >> n >> m;
  
  vector<int> s(m);
  vector<int> c(m);
  rep(i, m){
    cin >> s.at(i) >> c.at(i);
  }

  vector<int> t(n);
  rep(i, n) t[i]=-1;
  
  rep(j, m){
    if(t[s[j]-1]==-1) t[s[j]-1] = c[j];
    else if(t[s[j]-1]!=c[j]){
      cout << -1 << endl; return 0;
    }
  }
  
  if(n==1) t[0]=max(t[0], 0);
  else if(t[0]!=0) t[0]=max(t[0], 1);
  else{
    cout << -1 << endl; return 0;
  }
  for(int i=1; i<n; i++){
    if(t[i]==-1) t[i]=0;
  }
  
  int ans=0;
  int v;
  
  for(int i=0; i<n; i++){
    v = (int)pow(10,n-i-1);
    ans += t[i]*v;
//    cout << t[i] << " " << v << endl;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())
a = [A, B, C]
a.sort()
A, B, C = a[0], a[1], a[2]

ans = 0

def countEven(a, b, c):
    n = 0
    if a % 2 == 0:
        n += 1
    if b % 2 == 0:
        n += 1
    if c % 2 == 0:
        n += 1
    return n

if countEven(A, B, C) == 3 or countEven(A, B, C) == 0:
    ans += (C * 2 - (B + A)) / 2
elif countEven(A, B, C) == 1:
    ans += 1
    for i in range(3):
        if a[i] % 2 == 1:
            a[i] += 1
    ans += (a[2] * 2 - (a[1] + a[0])) / 2
elif countEven(A, B, C) == 2:
    ans += 1
    for i in  range(3):
        if a[i] % 2 == 0:
            a[i] += 1
    ans += (a[2] * 2 - (a[1] + a[0])) / 2

print(int(ans))


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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	int n, k; cin >> n >> k;
	vector<int> v(n);
	rep(i, 0, n) cin >> v[i];
	sort(all(v));
	int ans = 1000000000;
	rep(i, 0, n) if (i + k - 1 < n) {
		ans = min(ans, v[i + k - 1] - v[i]);
	}
	cout << ans << endl;
}



Measured memory_bytes: 640
fun main(args: Array<String>) {
    abc097c()
}

fun abc097c() {
    val s = readLine()!!
    val k = readLine()!!.toInt()
    val set = mutableSetOf<String>()
    for (i in s.indices) {
        var count = 0
        for (j in i + 1..s.length) {
            if (count >= 5) break
            set.add(s.substring(i, j))
            count++
        }
    }

    println(set.sorted()[k - 1])
}


Measured memory_bytes: 42384
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int a[310][310];
int b[310][310];

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    rep(i, N) rep(j, N) cin >> a[i][j];
    rep(i, N) rep(j, N) b[i][j] = a[i][j];
    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                b[i][j] = min(b[i][j], b[i][k] + b[k][j]);
            }
        }
    }
    int ans = 0;
    rep(i, N) {
        rep(j, N) {
            if (a[i][j] != b[i][j]) {
                cout << -1 << endl;
                return 0;
            }
            ans += a[i][j];
        }
    }
    rep(i, N) {
        rep(j, N) { 
            rep(k, N) {
                if (i == k || j == k || i == j) continue;
                if (a[i][k] + a[k][j] == a[i][j]) {  
                    ans -= a[i][j];
                    break;
                }
            }
        }
    }

    cout << ans/2 << endl;

    return 0;
}


Measured memory_bytes: 1664
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char s[64];
    
    scanf("%s", s);
    
    if (s[0] == 'x' && s[strlen(s) - 1] == 'x') printf("x\n");
    else printf("o\n");
    
    return (0);
}

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

using namespace std;

int main(int argc, const char * argv[])
{
    string stmp;
    cin >> stmp;
    
    vector<int> vcount(200);
    for(int i = 0; i < 200; i++)
    {
        vcount[i] = 0;
    }
    
    for(int i = 0; i < stmp.size(); i++)
    {
        char stgt = stmp[i];
        vcount[stgt]++;
    }
    
    for(int i = 0; i < 200; i++)
    {
        if(vcount[i] % 2 != 0)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}

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

using namespace std;

#define int long long
#define ff first
#define ss second
#define pii pair<int, int>
#define pb emplace_back
#define pf emplace_front
#define mp make_pair
#define ld long double

const int MAXN = 1000;
vector<int> g[MAXN];
int n;
int c[MAXN];
bool used[MAXN];
int dist[MAXN];
int inf = 1e9;

bool check(int v, int t)
{
    c[v] = t;
    used[v] = 1;
    for (int to : g[v])
    {
        if (used[to] && c[to] == t)
            return false;
        if (!used[to] && !check(to, 1 - t))
            return false;
    }
    return true;
}

int bfs(int v)
{
    for (int i = 0; i < n; i++)
    {
        dist[i] = inf;
        used[i] = false;
    }
    dist[v] = 0;
    used[v] = 1;
    queue<int> q;
    q.push(v);
    int y = v;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int to : g[u])
        {
            if (!used[to])
            {
                used[to] = 1;
                dist[to] = dist[u] + 1;
                q.push(to);
            }
        }
        y = u;
    }
    return dist[y] + 1;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int e = 0; e < n; e++)
        {
            if (s[e] == '1')
                g[i].pb(e);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i] && !check(i, 0))
        {
            cout << -1;
            return 0;
        }
    }
    int ma = 0;
    for (int i = 0; i < n; i++)
        ma = max(ma, bfs(i));
    cout << ma;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1000000000000000000

using namespace std;

int main(void){
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  /*
  ll sum = 0;
  ll ssum = 0;
  for (int i = 0; i < n; i++){
    sum = (sum + a[i]) % MOD;
    ssum = (ssum + a[i]*a[i]) % MOD;
  }

  ll ans = ((sum*sum - ssum) / 2 + MOD) % MOD;
  */

  vector<ll> sum(n + 1, 0);
  for (int i = 0; i < n; i++){
    sum[i+1] = (sum[i] + a[n-i-1]) % MOD;
  }
  ll ans = 0;
  for (int i = 0; i < n-1; i++){
    ans = (ans + a[i] * sum[n-i-1]) % MOD;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6424
s = raw_input().split()
[N, K] = s
N = int(N)
K = int(K)
#print N, K

s = raw_input().split()
#print s
h = [0]*N

for i in range(N):
    h[i] = int(s[i])
    #print h[i]

h.sort(reverse=True)
#print h

for i in range(N):
    if (h[i] >= K):
        continue
    else:
        print i
        exit()

print N


Measured memory_bytes: 12408
#include <cstdio>
#include <algorithm>
using namespace std ;
typedef int Read ; // Here to change reading type
inline Read Readin() {
	register Read K = 0 , F = 1 ; register char C = getchar() ;
	while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
	while( C >= '0' and C <= '9' ) K = ( K << 3 ) + ( K << 1 ) + C - '0' , C = getchar() ;
	return F * K ;
}
inline Read Min( Read A , Read B ) { return A < B ? A : B ; }
inline Read Max( Read A , Read B ) { return A > B ? A : B ; }
inline Read Abs( Read A ) { return A < 0 ? -A : A ; }
#define I(X) freopen(#X".in","r",stdin)
#define O(X) freopen(#X".out","w",stdout)
#define CLO fclose(stdin),fclose(stdout)
const int MaxN = 200 + 5 ;
int N , L[MaxN] ;
int main() {
	N = Readin() ; N <<= 1 ; 
	for(register int i = 0 ; ++i <= N ; L[i] = Readin() ) ;
	sort( L + 1 , L + 1 + N ) ;
	for(register int i = 0 ; i <= N ; ++i )
		L[0] += L[i<<1|1] ;
	printf( "%d\n" , L[0] ) ;
	return 0 ;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int A, B;
  int i;
  int error;
  char S[12];

  // 入力
  scanf("%d %d", &A, &B);
  scanf("%s", &S);
  
  error = 0;
  for(i = 0; i < A; i++){
    if(S[i] < '0' || S[i] > '9'){
      error = 1;
    }
  }
  if(S[i] != '-'){
    error = 1;
  }
  for(i = 0; i < B; i++){
    if(S[i+A+1] < '0' || S[i+A+1] > '9'){
      error = 1;
    }
  }
  
  // 出力
  if(error == 0){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


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

#define rep(i, N) for (int i = 0; i < N; i++)
#define rep1(i, N) for (int i = 1; i <= N; i++)
const int intinf = numeric_limits<int>::max();

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

#define MOD 1000000007

void solve()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N)
    {
        cin >> A[i];
        A[i]--;
    }

    vector<int> aton(N, 0);
    rep(i, N)
    {
        aton[A[i]]++;
    }

    ll nway = 0;
    rep(i, N)
    {
        nway += (ll)aton[i] * (aton[i] - 1) / 2;
    }

    rep(k, N)
    {
        ll nway_k = nway;
        int a = A[k];
        nway_k -= (ll)aton[a] * (aton[a] - 1) / 2;
        if (aton[a] > 0)
            nway_k += (ll)(aton[a] - 1) * (aton[a] - 2) / 2;
        cout << nway_k << endl;
    }
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 4096
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

vector<int> c[1 << 15];
int sum[1<<15];
int d[15][15];
void init(int n) {
	int x = (1 << n) - 1;
	rep(i, (1 << n)) {
		int r = i ^ x;
		vector<int> v;
		rep(j, n) {
			if (r&(1 << j))v.push_back(j);
		}
		int len = v.size();
		rep(j, (1 << len)) {
			int s = 0;
			rep(k, len) {
				if (j&(1 << k)) {
					s += (1 << v[k]);
				}
			}
			if (s == 0)continue;
			c[i].push_back(s);
		}
	}
	rep(i, (1 << n)) {
		vector<int> v;
		rep(j, n) {
			if (i&(1 << j))v.push_back(j);
		}
		rep(j, v.size()) {
			Rep(k, j + 1, v.size()) {
				sum[i] += d[v[j]][v[k]];
			}
		}
	}
}
int dp[1 << 15][15];
void solve() {
	int n, m; cin >> n >> m;
	int ssum = 0;
	rep(i, m) {
		int a, b, c; cin >> a >> b >> c; a--; b--;
		d[a][b] = d[b][a] = c; ssum += c;
	}
	init(n);
	rep(i, (1 << n)) {
		rep(j, n) {
			dp[i][j] = -mod;
		}
	}
	for (int i = 1; i < (1 << n); i += 2) {
		dp[i][0] = sum[i];
	}
	rep1(i, (1 << n)-1) {
		rep(j, n) {
			if (dp[i][j] < 0)continue;
			rep(k, c[i].size()) {
				int nex = c[i][k];
				int ni = i ^ nex;
				rep(l, n) {
					if (nex&(1 << l)) {
						if (d[j][l] == 0)continue;
						dp[ni][l] = max(dp[ni][l], dp[i][j] + sum[nex] + d[j][l]);
					}
				}
			}
		}
	}
	cout << ssum - dp[(1 << n) - 1][n - 1] << endl;
}
int main() {
	solve();
	//stop
	return 0;
}


Measured memory_bytes: 61696
n=int(input())
a=list(map(int, input().split()))
a.insert(0,0)
a.insert(n+1,0)
total=0
for i in range(n+1):
    total+=abs(a[i]-a[i+1])
for i in range(1,n+1):
    print(total-(abs(a[i-1]-a[i])+abs(a[i]-a[i+1]))+abs(a[i+1]-a[i-1]))

Measured memory_bytes: 13920
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = float('inf')

N = int(input())
As = list(map(int, input().split()))
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    adjL[u].append(v)
    adjL[v].append(u)

dp = [-INF]
anss = [0] * N
def dfs(vNow, vPar):
    A = As[vNow]
    if dp[-1] < A:
        dp.append(A)
        tp = 0
    else:
        i = bisect_left(dp, A)
        tp = 1
        iOld, AOld, = i, dp[i]
        dp[i] = A
    anss[vNow] = len(dp)-1

    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)

    if tp == 0:
        dp.pop()
    else:
        dp[iOld] = AOld

dfs(0, -1)

print('\n'.join(map(str, anss)))


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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true; } return false; }

// const int INF = 1001001001;
// long long max => LLONG_MAX

ll gcd_euclid(ll a, ll b){
    return b==0 ? a : gcd_euclid(b, a%b);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll a, b;
    cin >>a >> b;

    ll c= gcd_euclid(a,b);
    cout << a * b /c << endl;


    return 0;
}


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

using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;

    if(a<b)
    {
        for(int i=0 ; i<b; i++)
        {
            cout<<a;
        }
    }
    else
    {
        for(int i=0 ; i<a; i++)
        {
            cout<<b;
        }
    }
    return 0;
}


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

signed main()
{
    int n; cin >> n;
    set<string> s;
    while(n--)
    {
        string str; cin >> str;
        s.insert(str);
    }
    cout << (int) s.size() << "\n";
    
}

Measured memory_bytes: 19148
#include <stdio.h>
#include <stdlib.h>
int d_cnt;
long int X, K, D, a, b, c;
int main(void) {

	scanf("%ld %ld %ld", &X, &K, &D);
	if(X < 0){
		d_cnt = 1;
		X = labs(X);
	}
	a = X % D;
	if(a < 0){
		a = a + D;
	}
	b = (X - a) / D;
	if(K > b){
	X = X - D * b;

	if((K-b) >= 2){
			if(((K - b) % 2) == 0){
				printf("%ld", X);
			}else{
				printf("%ld", labs(X-D));
			}
		}else if((K-b) == 1){
			printf("%ld", labs(X-D));
		}else if((K-b) == 0){
			printf("%ld", X);
		}
	}else{
		printf("%ld", (X-K*D));
	}
	return 0;
}

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

int main() {
    
    int a, b;
    cin >> a >> b;
    int arr[a], sum=0;
    for(int i=0; i<a; i++){
        cin >> arr[i];
    }
    sort(arr, arr+a);
    for(int j=0; j<b; j++){
        sum= sum+arr[j];
    }
    cout << sum << endl;
    
    
    
    
    
	return 0;
}

Measured memory_bytes: 3640
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
int main(){
  int n;
  cin>>n;
  int ans=INT_MAX;
  for(int i=1;i<=(n+1)/2;i++){
    int l=i,r=n-i,res=0;
    while(l){
      res+=l%10;
      l/=10;
    }
    while(r){
      res+=r%10;
      r/=10;
    }
    chmin(ans,res);
  }
  cout<<ans<<"\n";
}

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

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
// #include <map>
// #include <string>
// #include <algorithm>
// #include <numeric>
// #include <limits>

using namespace std;

void measure(int n, vector<int> x, vector<int> y) {
	double d1 = 0, d2 = 0, d3 = 0, di = 0;
	int d;
	for (int i = 0; i < n; i++) {
		if (x[i] < y[i]) {
			d = y[i] - x[i];
		} else {
			d = x[i] - y[i];
		}
		d1 += d;
		d2 += pow(d, 2);
		d3 += pow(d, 3);
		if (di < d) {
			di = d;
		}
	}
	cout << fixed << setprecision(6);
	cout << d1 << endl;
	cout << pow(d2, double(1)/2) << endl;
	cout << pow(d3, double(1)/3) << endl;
	cout << di << endl;
}

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

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

	measure(n, x, y);
	// std::cout << "\e[38;5;0m\e[48;5;40m --- end ---  \e[m" << std::endl; // debug
	return 0;
}



Measured memory_bytes: 3440
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a + b <= 23) cout << a + b << endl;
	else cout << a + b - 24 << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n,q= map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) + [i] for i in range(q)]
for i in range(q):
    C[i][0] -= 1
    C[i][1] -= 1
for i in range(n):
    A[i] -= 1

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

B = Bit(n+1)
ANS = [-1] * q
C.sort(key=lambda x:x[1])
G = [-1] * (max(A)+1)
ind = 0
for i in range(n):
    a = A[i]
    if G[a] != -1:
        # print("ADD", G[a]+1, -1)
        B.add(G[a]+1, -1)
    G[a] = i
    # print("ADD", G[a]+1, 1)
    B.add(G[a]+1, 1)
    while ind < q and C[ind][1] == i:
        # print("SUM", C[ind][1]+1, C[ind][0]+1-1)
        ANS[C[ind][2]] = B.sum(C[ind][1]+1) - B.sum(C[ind][0]+1-1)
        ind += 1

for i in range(q):
    print(ANS[i])

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);

  put((N + 1) / 2 - 1);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


Measured memory_bytes: 256
/***"In the name of Allah(swt), the most gracious, most merciful. Allah(swt) blesses with knowledge whom he wants."***/
/*** "ALHAMDULILLAH for Everything..." ***/
#include<bits/stdc++.h>
using namespace std;
#define  fastt       ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define  ll         long long
#define  debug      printf("Come here!")
#define  inf        1000000000000000000
#define  pb         push_back
#define  mp         make_pair
#define  sz(a)      a.size()
#define  mem(a,b)   memset(a,b,sizeof(a))
#define  clr(x)     x.clear()
#define  ff         first
#define  ss         second
#define  case(x)    cout << "Case " << x <<": "

#define  md         1000000007
#define  pi         acos(-1.0)
#define  cos(a)     cos(a*pi/180)
#define  sin(a)     sin(a*pi/180)
#define  tan(a)     tan(a*pi/180)
#define  cosi(a)    acos(a)/(pi/180)
#define  sini(a)    asin(a)/(pi/180)
#define  tani(a)    atan(a)/(pi/180)

#define  vl         vector <ll>
#define  vs         vector <string>
#define  vc         vector <char>
#define  vpll       vector < pair <ll, ll> >
#define  vpsl       vector < pair <string, ll> >
#define  vpls       vector < pair <ll, string> >
#define  pql        priority_queue<ll>
#define  minpql     priority_queue<ll,vector<ll>,greater<ll> >

#define  setbits(x)     __builtin_popcountll(x)
#define  zerobits(x)    __builtin_ctzll(x)

#define toll(a) atoll(a.c_str())
string tostr(ll a) {stringstream rr;rr<<a;return rr.str();}
ll pow(ll c,ll d){return d==0?:c*pow(c,d-1);}
ll gcd(ll a,ll b) {return b==0? a:gcd(b,a%b);}
ll lcm(ll a,ll b) {return ((a*b)/gcd(a,b));}

/* mpp.max_load_factor(0.25); mpp.reserve(1024); */
/* cout << fixed << setprecision(12);*/

int main()
{
    ll n, i, j, x, y, p=0, h, f=0;
    string s, k, m="", a="dream", b="dreamer", c="erase", d="eraser";
    cin>>s;
    if(s.size()<5){
        cout<<"No"<<endl;
        return 0;
    }
    for(i=0; i<s.size()-4; i++){

        k=s.substr(i, 5);
        if(k==a){
            if(i+6<s.size() && s[i+5]=='e' && s[i+6]=='r'){
                if(i+7<s.size() && s[i+7]=='a'){
                    i+=4;
                }
                else{
                    i+=6;
                }
            }
            else{
                i+=4;

            }
        }
        else if(k==c){
            if(i+5<s.size() && s[i+5]=='r'){
                i+=5;
            }
            else{
                i+=4;
            }
        }
        else{
            f=1;
            break;
        }

    }
    i++;
    if(i<s.size())f=1;
    if(f==1)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;

    return 0;
}



Measured memory_bytes: 3716
#include <bits/stdc++.h>
#include<unordered_map>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 50
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
ll ans = 0;

int main() {
	string S;
	cin >> S;
	for (int i = 0; i < S.size(); i++)ans = S[i] == '+' ? ++ans : --ans;
	cout << ans << endl;
}


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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    ends = {}
    for i in range(M):
        s, e = L[i], R[i]
        if not e in ends:
            ends[e] = {}
        if not s in ends[e]:
            ends[e][s] = 0
        ends[e][s] += 1

    counts = [[0]]
    for i in range(1, N + 1):
        tmp = [v for v in counts[i - 1]]
        tmp.append(0)
        if i in ends:
            for s, cnt in ends[i].items():
                tmp[s] += cnt
        counts.append(tmp)
    #print(counts)

    for s, e in zip(p, q):
        ret = 0
        for j in range(s, e + 1):
            ret += counts[e][j]
        print(ret)
    return

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
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()


Measured memory_bytes: 64604
#include <stdio.h>
#include <stdlib.h>
#define N 3000000
#define INF 1000000

int parent_key(int);
int left_key(int);
int right_key(int);
void BuildMaxHeap();
void maxHeapify(int);
void insert(int);
void HeapIncreaseKey(int,int);
int HeapExtractMax();

int n,A[N+1];
int main()
{
  int key;
  char length[10];
  while(1)
    {
      scanf("%s",length);
      if(length[0]=='e'&&length[1]=='n') break;
      if(length[0]=='i')
	{
	  scanf("%d",&key);
	  insert(key);
	}
      else printf("%d\n",HeapExtractMax());
    }
  return 0;
}

void maxHeapify(int x)
{
  int l=0,r=0,largest=0;
  int es_largest=0; //??\???????????????????????¨???
  l=left_key(x);
  r=right_key(x);
  
  if(l<=n&&A[l]>A[x]) largest=l;
  else largest=x;
  
  if(r<=n&&A[r]>A[largest]) largest=r;
  
  if(largest!=x)
    {
      es_largest=A[largest];
      A[largest]=A[x];
      A[x]=es_largest;
      maxHeapify(largest);
    }
}

int parent_key(int x)
{
  return x/2;
}

int left_key(int x)
{
  return 2*x;
}
int right_key(int x)
{
  return 2*x+1;
}

void insert(int x)
{
  n++;
  A[n]=-INF;
  HeapIncreaseKey(n,x);
}

void HeapIncreaseKey(int x,int y)
{
  int escape=0;
  if(y<A[x]) exit(8);
  A[x]=y;
  while(x>1&&A[parent_key(x)]<A[x])
    {
      escape=A[parent_key(x)];
      A[parent_key(x)]=A[x];
      A[x]=escape;
      x=parent_key(x);
    }
}

int HeapExtractMax()
{
  int max=0;
  if(n<1) exit(8);
  max=A[1];
  A[1]=A[n];
  n--;
  maxHeapify(1);
  return max;
}

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

#define M   1050000
#define NIL (-1)
#define L   14

char H[M][L];

int getChar(char ch) {
  switch (ch) {
  case 'A': return 1;
  case 'C': return 2;
  case 'G': return 3;
  case 'T': return 4;
  default : return 0;
  }
}

long long getKey(char str[]){
  long long sum = 0, p = 1;
  for ( int i = 0; i < strlen(str); i++ ) {
    sum += p * (getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key) { return key % M; }
int h2(int key) { return 1 + (key % (M - 1)); }

int find(char str[]) {
  long long key, h;
  key = getKey(str);
  for ( int i = 0; ; i++ ) {
    h = (h1(key) + i * h2(key)) % M;
    if ( strcmp(H[h], str) == 0 ) return 1;
    else if ( strlen(H[h]) == 0 ) return 0;
  }
  return 0;
}

int insert(char str[]) {
  long long key, h;
  key = getKey(str);
  for ( int i = 0;  ; i++ ) {
    h = (h1(key) + i * h2(key)) % M;
    if ( strcmp(H[h], str) == 0 ) return 1;
    else if ( strlen(H[h]) == 0 ) {
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}

int main() {
  int n, h;
  char str[L], com[9];
  for ( int i = 0; i < M; i++ ) H[i][0] = '\0';
  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    cin >> com >> str;

    if ( com[0] == 'i' ) {
      insert(str);
    } else {
      if ( find(str) ) {
        cout << "yes" << endl;
      } else {
        cout << "no" << endl;
      }
    }
  }
  return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
#define int ll

void read() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (auto &i : p)
        cin >> i;
    ll ans = k;
    for (int i = 0; i < k; i++) {
        ans += p[i];
    }
    ll fans = ans;
    for (int i = k; i < n; i++) {
        fans += p[i];
        fans -= p[i - k];
        chkmax(ans, fans);
    }
    cout << ans / 2;
    if (ans % 2) {
        cout << ".5";
    } 
} 

void run() {

}

void write() {

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    run();
    write();
    return 0;
}

Measured memory_bytes: 1792
N = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
min = 1000; max = -1
N.times do |i|
  if a[i] < min
    min = a[i]
  end
  if a[i] > max
    max = a[i]
  end
end
puts max - min


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

ll m;
vec mul(vec &dp, mat &mt) {
  vec ret(m);
  for(ll i=0;i<m;i++) {
    for(ll j=0;j<m;j++) {
      ret[i]=(ret[i]+mt[i][j]*dp[j])%mod;
    }
  }
  return ret;
}

mat matmul(mat &a, mat &b) {
  mat res(m,vec(m,0));
  for(ll i=0;i<m;i++) {
    for(ll j=0;j<m;j++) {
      for(ll k=0;k<m;k++) {
        (res[i][j]+=a[i][k]*b[k][j])%=mod;
      }
    }
  }
  return res;
}

mat update(mat &mt) {
  mat ret(m,vec(m));
  for(ll i=0;i<m;i++) {
    for(ll j=0;j<m;j++) {
      for(ll k=0;k<m;k++) {
        ret[i][j]=(ret[i][j]+mt[i][k]*mt[k][j])%mod;
      }
    }
  }
  return ret;
}

void vmpow(vec &dp,mat &mt, ll k) {
  ll m=dp.size();
  while(k)  {
    if(k&1) dp=mul(dp,mt);
    mt=update(mt);
    k/=2;
  }
}

mat matpow(mat a, ll k) {
  mat res(m,vec(m,0));
  for(ll i=0;i<m;i++) {
    res[i][i]=1;
  }
  while(k>0) {
    if(k&1) res=matmul(res,a);
    a=matmul(a,a);
    k>>=1;
  }
  return res;
}

int main() {
  ll k;
  cin >> m >> k;
  mat mt(m,vec(m));
  for(ll i=0;i<m;i++) for(ll j=0;j<m;j++) cin >> mt[i][j];
  mt=matpow(mt,k);
  ll res=0;
  for(ll i=0;i<m;i++) {
    for(ll j=0;j<m;j++) {
      (res+=mt[i][j])%=mod;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  string s3;
  string s4;
  string s1 = to_string(a); 
    string s2 = to_string(b);
  for(int i=0;i<b;i++){
    s3=s3+s1;
  }
  for(int i=0;i<a;i++){
    s4+=s2;
  }
   if( lexicographical_compare(s3.begin(), s3.end(), s4.begin(),s4.end())){
       for(int i=0;i<s3.length();i++) cout << s3[i]; 
       } 
        
    else{
         for(int i=0;i<s4.length();i++) cout << s4[i]; 
        }
        
    return 0;      
   
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[10005],b;
int main()
{
	for (int i=1;i<=3;i++)
	  scanf("%d",&a[i]);
	sort(a+1,a+3+1);
	printf("%d\n",a[1]+a[2]);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#pragma GCC optimize("O2")
#define rep(i,N) for(int i=0;i<(int)N;i++)
const int MOD=1e9+7;
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline int asc(const int*a,const int*b){return *a-*b;}
int main()
{
  int A[200000],N=IN(),K=IN(),l,m=0,r,accum=1,sign=1;long x,y;
  rep(i,N)A[i]=IN(),m+=A[i]<0?1:0;
  qsort(A,N,sizeof(int),(int(*)(const void*,const void*))asc);
  if(K&1)accum=A[N-1],sign=(A[N-1]<0?-1:1),N--,K--;
  l=0,r=N-1;
  while(K)
  {
    x=1l*A[l]*A[l+1],y=1l*A[r]*A[r-1];
    if(x*sign>y*sign)x%=MOD,accum=1l*accum*x%MOD,l+=2;
    else y%=MOD,accum=1l*accum*y%MOD,r-=2;
    K-=2;
  }
  return printf("%ld\n",(1l*accum%MOD+MOD)%MOD),0;
}

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

typedef long long ll;
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define fork(i, n) for (ll i = 0; i < (n); i++)
#define forn for (ll i = 0; i < (n); i++)
#define fori(i, k, n) for (ll i = k; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define en '\n'
#define FILL(x, v) memset(x, v, sizeof(x))
#define pb push_back
#define fast                     \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(NULL);

template <typename A, typename B>
inline void chmin(A &a, B b)
{
	if (a > b)
		a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b)
{
	if (a < b)
		a = b;
}
template <typename T>
void print(vector<T> &a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
template <typename T>
void print(deque<T> &a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
template <typename T>
void print(vector<vector<T>> &a)
{
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[i].size(); j++)
			cout << a[i][j] << ' ';
		cout << en;
	}
}

const int mod = 1e9 + 7;

ll pw(ll b, ll e)
{
	ll res = 1;
	while (e)
	{
		if (e % 2)
			res = (res * b);
		b = (b * b);
		e >>= 1; // e/=2;
	}
	return res;
}

ll fact[200005], inv[200005];
ll C(ll n, ll k)
{
	return (((fact[n] * inv[k]) % mod) * inv[n - k]) % mod;
}

int main()
{
	fast;
	ll n;
	cin >> n;
	cout << n + pw(n, 2) + pw(n, 3) << en;
}

Measured memory_bytes: 3648
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>

#define P 1000000007

int comp(const void *a, const void *b){return *(int*)a-*(int*)b;}

int main(void){
	int n, i;
	scanf("%d", &n);
	int T=0, X=0, Y=0;
	for(i=0; i<n; i++){
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		int d = (x>X?x-X:X-x) + (y>Y?y-Y:Y-y);
		int dt = t-T;
		if(d>dt || (dt-d)%2!=0){
			puts("No");
			return 0;
		}
		T=t, X=x, Y=y;
	}
	puts("Yes");
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int bingo[3][3];
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            cin >> bingo[i][j];
        }
    }
    int N; cin >> N;
    bool check[3][3];
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            check[i][j] = false;
        }
    }
    for (int b = 0; b < N; ++b)
    {
        int bi; cin >> bi;
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                if (bingo[i][j] == bi)
                {
                    check[i][j] = true;
                }
            }
        }
    }
    bool isBingo = false;
    for (int i = 0; i < 3; ++i)
    {
        if (check[i][0] && check[i][1] && check[i][2]) isBingo = true;
    }
    for (int i = 0; i < 3; ++i)
    {
        if (check[0][i] && check[1][i] && check[2][i]) isBingo = true;
    }
    if (check[0][0] && check[1][1] && check[2][2]) isBingo = true;
    if (check[0][2] && check[1][1] && check[2][0]) isBingo = true;
    if (isBingo) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int n,x,ans;
multiset <int> st;
multiset <int>::iterator pos;

int main()
{
	cin>>n;
	rep(i,n)
	{
		cin>>x;
		pos=st.lower_bound(-x+1);
		if(pos==st.end()) ans++;
		else st.erase(pos);
		st.insert(-x);
	}
	cout<<ans<<endl;
	return 0;
}

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

int main()
{
    int n,i,c=0,f,x;
    scanf("%d",&n);
    int a[n];
    for(i=0; i<n; i++)  scanf("%d",&a[i]);
    sort(a,a+n);
    for(i=0; i<n; i++)
    {
        f = 0;
        x = a[i];
        while(1)
        {
            if(i>=n)    break;
            else if(a[i]!=x)
            {
                i--;
                break;
            }
            i++;
            f++;
        }
        if(f<x)    c += f;
        else if(f>x)    c += (f-x);
    }
    printf("%d\n",c);
    return  0;
}


Measured memory_bytes: 640