akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

vector<int> cache(1 << 11, -1);

bool check(ll g, const vector<ll>& p, const vector<ll>& c, ll k,
           unsigned int state){
    if(g <= 0){ return true; }
    if(k <= 0){ return false; }
    if(cache.at(state) != -1){ return cache.at(state); }

    for(int i = 0; i < p.size(); ++i){
        if(state & (1 << i)){ continue; }
        if(k >= p.at(i)){
            ll g2 = g - c.at(i) - 100 * (i + 1) * p.at(i);
            if(check(g2, p, c, k - p.at(i), state | (1 << i))){
                cache.at(state) = 1;
                return true;
            }
        }else if(g <= 100 * (i + 1) * k){
            cache.at(state) = 1;
            return true;
        }
    }
    cache.at(state) = 0;
    return false;
}

int main(){
    ll d, g;
    cin >> d >> g;
    vector<ll> p(d);
    vector<ll> c(d);
    for(int i = 0; i < d; ++i){
        cin >> p.at(i);
        cin >> c.at(i);
    }

    ll lo = 1, hi = 1000;
    while(lo < hi){
        ll test = (lo + hi) / 2;
        fill(cache.begin(), cache.end(), -1);
        if(check(g, p, c, test, 0)){
            hi = test;
        }else{
            lo = test + 1;
        }
    }
    cout << lo << endl;
    return 0;
}


Measured memory_bytes: 256
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ll n,k,ans;
    cin>>n>>k;
    ans=min(abs(n%k),abs((n%k)-k));
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=2005;
struct edge{
	int to,next;
}e[N*2];
int q[N],fa[N],px[N],py[N];
int n,m,x[N][N],y[N][N];
int head[N],tot,ans;
int ojbk[N],vis[N],D[N];
void add(int x,int y){
	e[++tot]=(edge){y,head[x]};
	head[x]=tot;
}
void bfs(){
	int h=0,t=1;
	q[1]=fa[1]=1;
	while (h!=t){
		int x=q[++h];
		for (int i=head[x];i;i=e[i].next)
			if (!fa[e[i].to]){
				D[e[i].to]=D[x]+1;
				fa[e[i].to]=x;
				q[++t]=e[i].to;
			}
	}
}
int chainmerge(int x,int y,int z){
	//printf("%d %d %d\n",x,y,z);
	memset(vis,0,sizeof(vis));
	for (int X=x,Y=y;X!=Y;++vis[X],X=fa[X])
		if (D[X]<D[Y]) swap(X,Y);
	for (int X=x,Y=z;X!=Y;++vis[X],X=fa[X])
		if (D[X]<D[Y]) swap(X,Y);
	For(i,1,n) if (vis[i]==2&&!ojbk[i])
		ojbk[i]=1,ans+=2;
}
int main(){
	scanf("%d%d",&n,&m);
	For(i,1,n-1){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	For(i,1,m)
		scanf("%d%d",&x[n][i],&y[n][i]);
	bfs();
	Rep(i,n,2){
		memcpy(x[i-1],x[i],sizeof(x[i]));
		memcpy(y[i-1],y[i],sizeof(y[i]));
		if (ojbk[q[i]]) px[i]=py[i]=1;
		For(j,1,m){
			if (x[i-1][j]==y[i-1][j])
				x[i-1][j]=y[i-1][j]=-1;
			if (x[i-1][j]==-1) continue;
			if (y[i-1][j]==q[i])
				swap(x[i-1][j],y[i-1][j]);
			if (x[i-1][j]==q[i]){
				if (!px[i]) px[i]=j,++ans;
				else if (!py[i]) py[i]=j,++ans;
				else x[i-1][j]=fa[q[i]];
			}
		}
		if (ojbk[q[i]]) px[i]=py[i]=0;
		if (px[i]&&!py[i]){
			int j=px[i];
			x[i-1][j]=fa[q[i]];
			px[i]=0;
		}
		if (px[i]&&py[i]){
			int j=px[i],k=py[i];
			ojbk[q[i]]=-1;
			chainmerge(x[i-1][j],y[i-1][j],y[i-1][k]);
			x[i-1][j]=y[i-1][k];
			x[i-1][k]=y[i-1][k]=-1;
		}
		//printf("ZYKniubi %d %d %d %d\n",fa[q[i]],q[i],i,ans);
		//For(j,1,m) printf("%d %d\n",x[i-1][j],y[i-1][j]);
	}
	For(i,2,n){
		For(j,1,m)
			if (x[i][j]!=y[i][j]&&j!=px[i]&&j!=py[i]){
				if (x[i][j]==q[i]||y[i][j]==q[i])
					if (x[i-1][j]==fa[q[i]])
						x[i-1][j]=q[i];
					else y[i-1][j]=q[i];
				if (x[i-1][j]==y[i][j])
					swap(x[i][j],y[i][j]);
				assert(x[i][j]==x[i-1][j]);
				assert(y[i][j]==y[i-1][j]);
			}
		if (px[i]&&py[i]){
			int j=px[i],k=py[i];
			if (x[i][j]==q[i]) swap(x[i][j],y[i][j]);
			if (y[i][k]==q[i]) swap(x[i][k],y[i][k]);
			if (x[i-1][j]==y[i][k]){
				swap(x[i][j],y[i][j]);
				swap(x[i][k],y[i][k]);
			}
		}
		//printf("ZYKniubi %d %d %d %d\n",fa[q[i]],q[i],i,ans);
		//For(j,1,m) printf("%d %d\n",x[i][j],y[i][j]);
	}
	printf("%d\n",ans);
	For(i,1,m) printf("%d %d\n",x[n][i],y[n][i]);
}

Measured memory_bytes: 31744
n = int(input())

c = [[0 for i in range(10)] for i in range(10)]
      
for i in range(1, n+1):
    
    tail = i % 10
    
    while(i // 10 != 0):
        i = i // 10
    head = i

    c[head][tail] += 1

total = 0

for i in range(10):
    for j in range(10):
        total += c[i][j] * c[j][i]
        

print(total)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int h, w, a, b; cin >> h >> w >> a >> b;
  for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
    cout << (i < b ^ j < a);
    if (j == w - 1) {
      cout << '\n';
    }
  }
}

Measured memory_bytes: 1280
#include <iostream>

using namespace std;

int main() {
	int n;
	while (cin >> n, n != 0) {
		int ok_lunch=0, ok_dinner=0, ok_midnight=0;
		int lunch=0, dinner=0, midnight=0;
		for (int i = 0; i < n; i++) {
			int h, m, M; char d;
			cin >> h >> d >> m >> M;
			int t = M - m;
			if (t < 0) t += 60;
			if (11 <= h && h <= 14) {
				lunch++;
				if (t <= 8) ok_lunch++;
			} else if (18 <= h && h <= 20) {
				dinner++;
				if (t <= 8) ok_dinner++;
			} else if (21 <= h && h <= 23 || 0 <= h && h <= 1) {
				midnight++;
				if (t <= 8) ok_midnight++;
			}
		}

		cout << "lunch ";
		if (lunch == 0) cout << "no guest" << endl;
		else cout << ok_lunch * 100 / lunch << endl;

		cout << "dinner ";
		if (dinner == 0) cout << "no guest" << endl;
		else cout << ok_dinner * 100 / dinner << endl;
			
		cout << "midnight ";
		if (midnight == 0) cout << "no guest" << endl;
		else cout << ok_midnight * 100 / midnight << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

N, W = map(int, input().split())
d = defaultdict(list)
w1 = 0
for n in range(N):
    w, v = map(int, input().split())
    d[w].append(v)
    if n == 0:
        w1 = w

# 各重さごとに、価値の高い順にK個とったときの価値の総和を求めておく
best_ks = {}
for w in range(w1, w + 4):
    vs = sorted(d[w], reverse=True)
    s = 0
    best_k = [0]
    for v in vs:
        s += v
        best_k.append(s)
    best_ks[w] = best_k

ans = 0
for w1_num in range(len(d[w1])+1):
    for w2_num in range(len(d[w1+1])+1):
        for w3_num in range(len(d[w1+2])+1):
            for w4_num in range(len(d[w1+3])+1):
                weight \
                    = w1_num * w1 \
                    + w2_num * (w1 + 1) \
                    + w3_num * (w1 + 2) \
                    + w4_num * (w1 + 3)
                # print(w1_num, w2_num, w3_num, w4_num, weight)
                if weight > W:
                    continue
                value \
                    = best_ks[w1][w1_num] \
                    + best_ks[w1 + 1][w2_num] \
                    + best_ks[w1 + 2][w3_num] \
                    + best_ks[w1 + 3][w4_num]
                ans = max(ans, value)
print(ans)


Measured memory_bytes: 7216
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int x=sc.nextInt();
        int y=sc.nextInt();
        int z=sc.nextInt();

        System.out.println(z);
        System.out.println(x);
        System.out.println(y);

    }
}


Measured memory_bytes: 24020
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN = 300050;
const int MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
int a[100050];
int main() {
	int n;
	ios::sync_with_stdio ( false );
	cin >> n;
	for ( int j = 0; j < n; j++ )
		cin >> a[j];
	sort ( a, a + n, greater<int>() );
	int la = 0, lb = 0;
	for ( int j = 0; j < n; j++ ) {
		if ( a[j] == a[j + 1] && la == 0 ) {
			la = a[j];
			a[j] = a[j + 1] = 0;
			continue;
		}
		if ( la != 0 && a[j] == a[j + 1] ) {
			lb = a[j];
			break;
		}
	}
	ll ans = 1LL * la * lb;
	cout << ans;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

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

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

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int main() {
    string N;
    cin >> N;
    REP(i, N.length()) {
        if(N[i] == '7') {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <stdio.h>

void bubbleSort(int *,int);

int main(){
  int N,A[100],i;

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  bubbleSort(A,N);
  
  return 0;
}
  void bubbleSort(int *a,int n)
  {
    int flag=1,i,j,num,count=0;
    while(flag!=0){
      flag=0;
      for(j=n-1;j>=1;j--){
	if(a[j]<a[j-1]){
	  num=a[j];
	  a[j]=a[j-1];
	  a[j-1]=num;
	  count++;
	  flag=1;
	}	 
      }
    }
    for(i=0;i<n;i++){
      printf("%d",a[i]);
      if(i!=n-1)printf(" ");
      }
    printf("\n");
    printf("%d\n",count);
  }

Measured memory_bytes: 604
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

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; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

bool is_inside(int x1, int y1, int r, int x2, int y2) {
  if (pow(abs(x1 - x2), 2) + pow(abs(y1 - y2), 2) <= r * r) {
    return true;
  } else {
    return false;
  }
}

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

  int n, m;
  cin >> n >> m;

  vector<int> ac(n, 0);
  vector<int> wa(n, 0);

  int ans_ac = 0;
  int ans_wa = 0;
  
  rep(i, m) {
    int p;
    string r;
    cin >> p >> r;
    p--;
    if (r == "AC" && ac[p] == 0) {
      ac[p] = 1;
      ans_ac++;
      ans_wa += wa[p];
    } else {
      if (ac[p] == 0) wa[p]++;
    }
  }

  rep(i, n) {
    if (ac[i] == 0) wa[i] == 0;
  }

  cout << ans_ac << " " << ans_wa << endl;

  return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll mod=1e9+7;
ll inf=1e18;

int main(void){
	ll money=1e15;
	ll n,m,s,t,w,x,y,z,d1[100010],d2[100010];
	vector<ll> v[100010],a[100010],b[100010];
	rep(i,100010){
		d1[i]=inf;
		d2[i]=inf;
	}
	cin>>n>>m>>s>>t;
	rep(i,m){
		cin>>w>>x>>y>>z;
		v[w].push_back(x);
		v[x].push_back(w);
		a[w].push_back(y);
		a[x].push_back(y);
		b[w].push_back(z);
		b[x].push_back(z);
	}
	//dijkstra
	d1[s]=0;
	priority_queue<ll> Q;
	Q.push(s);
	while(!Q.empty()){
		ll p=Q.top();Q.pop();
		rep(i,v[p].size()){
			ll q=v[p][i];
			if(d1[q]>d1[p]+a[p][i]){
				d1[q]=d1[p]+a[p][i];
				Q.push(q);
			}
		}
	}
	d2[t]=0;
	Q.push(t);
	while(!Q.empty()){
		ll p=Q.top();Q.pop();
		rep(i,v[p].size()){
			ll q=v[p][i];
			if(d2[q]>d2[p]+b[p][i]){
				d2[q]=d2[p]+b[p][i];
				Q.push(q);
			}
		}
	}
	mp M[100010];
	reg(i,1,n)M[i]=make_pair(d1[i]+d2[i],i);
	sort(M+1,M+n+1);
	ll cnt=1;
	rep(i,n){
		while(M[cnt].second<=i)cnt++;
		cout<<(money-M[cnt].first)<<endl;
	}
	return 0;
}

Measured memory_bytes: 25332
while True:
    h,w = map(int,input().split())
    if h == 0 and w == 0:
        exit()
    
    for i in range(h):
        for j in range(w):
            if (i+j)%2 == 0:
                print("#", end="")
            else:
                print(".", end="")
        print()
    print()


Measured memory_bytes: 7000
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
const int maxn = 1e5 + 5;
int a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n; cin >> n;
    ll a , b; cin >> a >> b;
    for (int i = 2 ; i <= n ; ++i){
        ll x , y; cin >> x >> y;
        ll mul = max((a - 1) / x + 1 , (b - 1) / y + 1);
        a = x * mul;
        b = y * mul;
    }
    cout << a + b << endl;
    return 0;
}


Measured memory_bytes: 3640
N = int(input())
xyh = [list(map(int,input().split())) for _ in range(N)]
xyh = sorted(xyh, key = lambda x: -x[2])
xt, yt, ht = xyh[0]
for Cx in range(101):
  for Cy in range(101):
    H = ht + abs(xt - Cx) + abs(yt - Cy)
    if(all(h == max(H - abs(x - Cx) - abs(y - Cy), 0) for x,y,h in xyh)):
      print(Cx, Cy, H)
      break
  else:
      continue
  break

Measured memory_bytes: 3064
N = input()
A, B, C, D = N[0], N[1], N[2], N[3]
def fn(op1, op2, op3):
    msg = A + op1 + B + op2 + C + op3 + D
    if eval(msg) == 7:
        print(msg + "=7")
        exit()

for op1 in ('+', '-'):
    for op2 in ('+', '-'):
        for op3 in ('+', '-'):
            fn(op1, op2, op3)

Measured memory_bytes: 3064
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
c = [0]*(N+1)
c[0] = 1
c[1] = 1
ans = 1
a = []
al = 0
for i in range(2,N+1):
    c[i] = c[i-1]+c[i-2]
    c[i] %= mod
for i in range(M):
    ai = int(input())
    if i == 0:
        a.append(ai)
    else:
        if ai - al == 1:
            print(0)
            exit()
        else:
            a.append(ai)
    al = ai
if M == 0:
    print(c[N])
    exit()
for i in range(M):
    if i == 0:
        ans *= c[a[i]-1]
        ans %= mod
    if i == M-1:
        ans *= c[N-a[i]-1]
        ans %= mod
    else:
        if a[i+1] != a[i]:
            ans *= c[a[i+1]-a[i]-2]
            ans %= mod
print(ans)


Measured memory_bytes: 46936
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits> 


int main()
{
    long N;
    std::string S;
    std::cin >> N;
    std::cin >> S;
    long count=0;

    long Rcount=0;
    long Gcount=0;
    long Bcount=0;
    for(long i=0; i<N; i++){
        if(S[i]=='R'){
            Rcount++;
        }else if(S[i]=='G'){
            Gcount++;
        }else{
            Bcount++;
        }
    }

    for(long i=0; i<N; i++){
        for(long j=i+1; j<N; j++){
            if(j+(j-i)<N){
                long k=j+(j-i);
                if(S[i]!=S[j] && S[j]!=S[k] && S[i]!=S[k]){
                    count+=1;
                }
            }
        }
    }
    std::cout << Rcount*Gcount*Bcount-count << std::endl;
    return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
int cmp( const void *p, const void *q ) {
    return *(int*)p - *(int*)q;
}
int main(void) {
	long a[3],L,r;
	int n,i;
	while(scanf("%ld %ld %ld",&a[0],&a[1],&a[2]),a[0]) {
		qsort(a,3,sizeof(long),cmp);
		L=a[0]*a[0]+a[1]*a[1];
		scanf("%d",&n);
		for(i=0;i<n;i++) {
			scanf("%ld",&r);
			if(4*r*r>L) printf("OK\n");
			else printf("NA\n");
		}
	}
	return 0;
}

Measured memory_bytes: 588
# -*- coding: utf-8 -*-
# C - Base -2 Number
import sys 
from collections import defaultdict
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M = map(int,readline().split())
A = list(map(int,readline().split()))
S = list(accumulate(A))
d = defaultdict(int)
for i in range(N):
    a = S[i] % M
    d[a] += 1
ans = d[0]
for n in d.values():
    ans += (n-1)*n // 2
print(ans)

Measured memory_bytes: 99352
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    ll r, g, b, n;
    cin >> r >> g >> b >> n;
    ll cnt = 0;
    rep(p, n/r+1){
        rep(q, n/g+1){
            if (r * p + g * q <= n && (n - r * p - g * q)%b == 0) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


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

int main(){
    ll N;
    cin>>N;
    std::vector<ll> A(N);
    ll sum=0,ans=0;
    const ll MOD=1000000007;
    for(ll i=0;i<N;++i){
        cin>>A[i];
        sum+=A[i];
    }
    //cout<<sum<<endl;
    for(ll i=0;i<N-1;++i){
        sum-=A[i];
        //cout<<A[i]<<"*"<<sum<<"="<<A[i]*sum<<"->"<<(A[i]*sum)%MOD<<endl;
        ans+=(A[i]*(sum%MOD))%MOD;
    }
    cout<<ans%MOD;
    
}

Measured memory_bytes: 4836
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		int n = 3 * N;
		long[] a = new long[n];
		String[] s = sc.nextLine().split(" ");
		sc.close();
		for(int i = 0; i < n; i++) {
			a[i] = Long.parseLong(s[i]);
		}
		Arrays.sort(a);
		long sum = 0;
		for(int i = 0; i < N; i++) {
			sum += a[n - 2 * i - 2];
		}
		System.out.println(sum);
	}
}

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

#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for (int i = (n); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main()
{
    double r;
    cin >> r;
    OP(2 * 3.141592 * r);
    return 0;
}

Measured memory_bytes: 3780
#include <iostream>
using namespace std;
int main(void){
    int a, b;
    char s[100][100];
    cin >> a >> b;
    
    for (int i = 0; i < 50; i++) fill(s[i], s[i] + 100, '#');
    for (int i = 50; i < 100; i++) fill(s[i], s[i] + 100, '.');
    
    a--;  b--;
    int h = 0, w = 0;
    while (a != 0) {
        s[h][w] = '.';  w += 2;
        if (w == 100) {
            h += 2;  w = 0;
        }
        a--;
    }
    h = 51, w = 0;
    while (b != 0) {
        s[h][w] = '#';  w += 2;
        if (w == 100) {
            h += 2;  w = 0;
        }
        b--;
    }
    
    cout << "100 100" << endl;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) cout << s[i][j];
        cout << endl;
    }
    
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0)
#define END return EXIT_SUCCESS
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR(I,0,N)
#define ALL(C) (C).begin(),(C).end()
#define INPUT(P) std::cin>>(P)
#define INPUT2(P1,P2) std::cin>>(P1)>>(P2)
#define INPUT3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3)
#define INPUTS(I,N,V) REP(I,N) std::cin>>V[I]
#define OUTPUT(P) std::cout<<P<<std::endl
#define OUTPUT2(P1,P2) std::cout<<P1<<" "<<P2<<std::endl
#define OUTPUT3(P1,P2,P3) std::cout<<P1<<" "<<P2<<" "<<P3<<std::endl
#define OUTPUTS(I,N,V) REP(I,N) std::cout<<V[i]<<std::endl
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ul;
using namespace std;
int i,j,k;
int N,K;
int x[100000];
int a;
int t;
inline void solve(){
  INPUT2(N,K);
  INPUTS(i,N,x);
  a=INT_MAX;
  FOR(i,K,N+1){
    t=min(abs(x[i-K])+x[i-1]-x[i-K], abs(x[i-1])+x[i-1]-x[i-K]);
    a=min(a,t);
  }
  cout<<a<<endl;
}

int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 768
use std::f64;
use std::io::stdin;

fn main() {
    let mut is = String::new();
    stdin().read_line(&mut is).ok();
    let mut itr = is.split_whitespace().map(|e| e.parse::<f64>().unwrap());
    let a = itr.next().unwrap();
    let b = itr.next().unwrap();
    let x = itr.next().unwrap();
    let t = 2.0 * x / a / b;
    let ans;
    if t <= a {
        ans = b.atan2(t) * 180.0 / f64::consts::PI;
    } else {
        let x = a * a * b - x;
        let t = 2.0 * x / a / a;
        ans = t.atan2(a) * 180.0 / f64::consts::PI;
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
N, M = map(int, input().split())

students = [list(map(int, input().split())) for _ in range(N)]
check_p = [list(map(int, input().split())) for _ in range(M)]

for s in students:
    min_distance = (10 ** 8) * 4 + 1
    ans = 0
    for m in range(M):
        distance = abs(s[0] - check_p[m][0]) + abs(s[1] - check_p[m][1])
        if min_distance > distance:
            min_distance = distance
            ans = m + 1
    print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
string s;
int n, sum[200005];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> s;
	for (int i = 0; i < n; i ++)
		sum[i + 1] = sum[i] + (s[i] == '.');
	int ans = n;
	for (int i = 0; i <= n; i ++)
	{
		int now = i - sum[i] + sum[n] - sum[i];
		ans = min(ans, now);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1300
#include<stdio.h>
#include<string.h>
int main(void)
{
	int n,j,b=0;
	char i[100];
	char a[10];
	scanf("%s",&a);
	scanf("%d",&n);
	for(j=1;j<=n;j++){
		scanf("%s",&i);
		strncat(i,i,10);
		if((strstr(i,a))!=NULL){
			b++;
		}
	}
	printf("%d\n",b);
	return 0;
}



Measured memory_bytes: 2036
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <tuple>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    //    ifstream in("input.txt");
    //    cin.rdbuf(in.rdbuf());
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s, t;
    cin >> s >> t;
    
    unordered_map<char, int> smap, tmap;
    int sid, tid;
    sid = 0;
    tid = 0;
    vector<int> sv(s.size()), tv(s.size());
    rep(i, s.size())
    {
        if (smap.find(s[i]) != smap.end()) sv[i] = smap[s[i]];
        else
        {
            smap[s[i]] = sid;
            ++sid;
            sv[i] = smap[s[i]];
        }
        
        if (tmap.find(t[i]) != tmap.end()) tv[i] = tmap[t[i]];
        else
        {
            tmap[t[i]] = tid;
            ++tid;
            tv[i] = tmap[t[i]];
        }
        
        if (sv[i] != tv[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


using Graph = vector<vector<int>>;

int main() {
    string x; cin >> x;
    stack<char> s;
    rep(i, x.size()) {
        char tmp = x[i];
        if(s.empty()) s.push(tmp);
        else {
            if(s.top() == 'S' && tmp == 'T') s.pop();
            else s.push(tmp);
        }
    }

    cout << s.size() << endl;


    return 0;
}



Measured memory_bytes: 644
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, D, H;
	cin >> N >> H >> D;
	cat mod = 1000000007, fac = 1, sum_fac = 1;
	for(int i = 2; i <= N; i++) {
		fac = i * fac % mod;
		sum_fac = (sum_fac + fac) % mod;
	}
	vector<cat> dp(H+1, 0), add(H+D+2, 0);
	add[1] = fac;
	add[D+1] = (-fac) % mod;
	for(int i = 1; i <= H; i++) {
		add[i] = (add[i] + add[i-1]) % mod;
		dp[i] = (dp[i] + add[i]) % mod;
		add[i+1] = (add[i+1] + dp[i] * sum_fac) % mod;
		add[i+D+1] = (add[i+D+1] - dp[i] * sum_fac) % mod;
	}
	dp[H] %= mod;
	if(dp[H] < 0) dp[H] += mod;
	cout << dp[H] << "\n";
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 23680
def main():

    N, K = map(int, input().split())
    S = input()

    count = []
    ct = 0
    for i in range(N):
        if i == 0 or S[i] == S[i-1]:
            ct += 1
        else:
            count.append(ct)
            ct = 1
    count.append(ct)

    happiness = 0
    for c in count:
        happiness += c - 1

    n = len(count) - 1
    if 2 * K >= n:
        return N-1
    else:
        return happiness + 2*K


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


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  int maxi=0;

  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    maxi = max(maxi,a[i]);
  }

  int ans=maxi;
  for (int i = 0; i < n; i++)
  {
    if(abs((maxi+1)/2-a[i])<=abs((maxi+1)/2-ans)){
      ans=a[i];
    }
  }
  cout << maxi << " " << ans << endl;
}

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

int main(){
    int64_t n;
    cin >> n;
    vector<int64_t> a(n+1);
    vector<int64_t> b(n);
    int64_t sum_mons = 0;
    for(int i = 0; i < n+1; i++){
        cin >> a.at(i);
        sum_mons += a.at(i);
    }
    for(int i = 0; i < n; i++){
        cin >> b.at(i);
    }
    int64_t left_attack = 0;
    int64_t left_mons = 0;
    for(int i = n; i > 0; i--){
        left_attack = b.at(i - 1) - a.at(i); //attack - monster
        //残りのattackで前の街のmonster討伐
        if(left_attack >= 0){
            a.at(i-1) = a.at(i-1) - left_attack; 
            if(a.at(i-1) < 0) a.at(i-1) = 0;
        //monsterを倒し切れていない場合は生存モンスターをカウント
        }else{
            left_mons += -left_attack;
        }
    }
    left_mons += a.at(0);
    cout << sum_mons - left_mons << endl;
}


Measured memory_bytes: 1792
import random
n, m, k = map(int, input().split())
# n, m, k = random.randint(1, 10**5), random.randint(1, 10**5), random.randint(10**8, 10**9)
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
# a_list = [random.randint(1, 10**3) for i in range(n)]
# b_list = [random.randint(1, 10**3) for i in range(m)]
# print(n,m,k)
# print(a_list[0], b_list[0])
a_sum = [0]
b_sum = [0]
max_a = 0
for i in range(1, max(n+1, m+1)):
    if i < n+1:
        a_sum.append(a_sum[i-1] + a_list[i-1])
        if a_sum[i] <= k:
            max_a = i
    if i < m+1:
        b_sum.append(b_sum[i-1] + b_list[i-1])

ans = 0
j = m
for i in range(0, max_a+1):
    while b_sum[j] > k - a_sum[i]:
        j -= 1
    ans = max(ans, i+j)
        
print(ans)

Measured memory_bytes: 48916
N, M = list(map(int, input().split()))

X = list(map(int, input().split()))

x = []
X.sort()

for i in range(1,M):
    x.append(abs(X[i] - X[i-1]))
x.sort(reverse=True)


ans = sum(x)

if N >= len(X):
    print(0)
else:
    for i in range(N - 1):
        ans -= x[i]

    print(ans)

Measured memory_bytes: 13968
#include "bits/stdc++.h"
using namespace std;
int count(int y, int m, int d) {
	int sum = 0;
	for (int i = 1; i < y; i++) {
		if (i % 3 == 0) sum += 20 * 10;
		else sum += (20 + 19) * 5;
	}

	for (int i = 1; i < m; i++) {
		if (y % 3 == 0) sum += 20;
		else if (i % 2 == 1) sum += 20;
		else sum += 19;
	}
	sum += (d - 1);
	return sum;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int y,m, d;
		scanf("%d %d %d", &y, &m, &d);
		printf("%d\n", count(1000, 1, 1) - count(y, m, d));
	}
}

Measured memory_bytes: 3200
N=int(input())
sides=[int(x) for x in input().split()]
counter=0
for i in range(N-2):
	for j in range(i+1,N-1):
		for k in range(j+1,N):
			A=sorted([sides[i],sides[j],sides[k]])
			if (A[0]+A[1]>A[2]) and A[0]!=A[1] and A[1]!=A[2] and A[0]!=A[2]:
				counter+=1
				
print(counter)

Measured memory_bytes: 68824
#include <vector>
#include <iostream>
#include <numeric>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s; cin >> s;
    long long n = s.size();
    vector<int> sa = atcoder::suffix_array(s);
    long long ans = n*(n+1)/2;
    for (auto x : atcoder::lcp_array(s, sa)) {
        ans -= x;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 15628
def check(a, b, target):
    if abs(target - a) < abs(target - b):
        return a
    else:
        return b


n, a = int(input()), list(map(int, input().split()))
if n == 2:
    a.sort(reverse = True)
    print(a[0], a[1])
    exit()
a.sort()
l, r = 0, n
target = a[-1] >> 1
while l < r:
    mid = (l + r) >> 1
    if a[mid] > target:
        r = mid
    else:
        l = mid + 1
if a[l] <= target:  # check a[l] and a[l + 1]
    print(a[-1], check(a[l], a[l + 1], target))
else:  # check a[l] and [l - 1]
    print(a[-1], check(a[l - 1], a[l], target))


Measured memory_bytes: 14052
#include <iostream>
using namespace std;
int main()
{
    string w;
    cin >> w;
    if(w == "SUN"){
        cout << 7 << endl;
    }else if(w == "MON"){
        cout << 6 << endl;
    }else if(w == "TUE"){
        cout << 5 << endl;
    }else if(w == "WED"){
        cout << 4 << endl;
    }else if(w == "THU"){
        cout << 3 << endl;
    }else if(w == "FRI"){
        cout << 2 << endl;
    }else{
        cout << 1 << endl;
    }
    return(0);
}


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

using namespace std;

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

  vector<long long> a(n);
  long long s = 0;
  map<long long, long long> mp;
  mp[0]++;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    s += a[i];
    mp[s]++;
  }
  long long ans = 0;
  for (auto kv : mp) {
    ans += kv.second * (kv.second - 1) / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 14336
use std::fs;
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let (n, k): (usize, usize) = parse!(it, 2);
    let a = (0..n).map(|_| parse!(it)).collect::<Vec<usize>>();
    let mut s = 0;
    while 2usize.pow(s) < k {
        s += 1;
    }
    let mut cur = 0;
    loop {
        let c = a.iter().filter(|&x| x & (1 << s) != 0).count();
        if n - c > c && cur + (1 << s) <= k {
            cur += 1 << s
        }
        if s == 0 {
            break;
        }
        s -= 1;
    }
    println!("{}", a.iter().map(|&x| cur ^ x).sum::<usize>());
}

fn test() {
    let mut f = fs::File::open("foo.txt").unwrap();
    let mut s = String::new();
    f.read_to_string(&mut s).unwrap();
    solve(&s);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_main() {
        test();
    }
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 6396
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

ll DP[13][100005];

int main() {
  string S;
  cin>>S;
  if(S[0]=='?') {
    for(int i=0;i<10;++i) DP[i][0] = 1;
  }
  else {
    DP[S[0]-'0'][0] = 1;
  }
  for(int i=1;i<S.size();++i) {
    if(S[i]=='?') {
      for(int j=0;j<13;++j) {
        for(int k=0;k<10;++k) {
          DP[(10*j+k)%13][i] += DP[j][i-1];
          DP[(10*j+k)%13][i] %= mod;
        }
      }
    }
    else {
      for(int j=0;j<13;++j) {
        DP[(10*j+(S[i]-'0'))%13][i] += DP[j][i-1];
        DP[(10*j+(S[i]-'0'))%13][i] %= mod;
      }
    }
  }
  cout<<DP[5][S.size()-1]<<endl;
}



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



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    int n,m,k;
    cin>>n>>m>>k;
    int a[n],b[n];
    int ma = 1e7;
    int ans = 0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ma = min(ma,a[i]);
    }
    ans = ma;
    ma = 1e7;
    for(int i=0;i<m;i++){
        cin>>b[i];
        ma = min(ma,b[i]);
    }
    ans += ma;
    for(int i=0;i<k;i++){
        int x,y,z;
        cin>>x>>y>>z;
        x--,y--;
        ans = min(ans,a[x]+b[y]-z);
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
long long N,D,x,y,ans=0;
int main() {
	cin>>N>>D;
	for(int i=1;i<=N;i++) {
		cin>>x>>y;
		if(x*x+y*y<=D*D) {
			ans++;
		} 
	}
	cout<<ans<<endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<tuple<string, int, int>> a;
  for(int i = 0; i < n; i++) {
    string s;
    int p;
    cin >> s >> p;
    a.push_back(make_tuple(s, 100-p, i));
  }
  sort(a.begin(), a.end());
  for(int i = 0; i < n; i++) {
    int x;
    tie(ignore, ignore, x) = a.at(i);
    cout << x+1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	for(;;){

	int m,n,X[200],Y[200],x[1000],y[1000];
	cin >> m;
	if(m==0)return 0;
	for(int i=0;i<m;i++)cin >> X[i] >> Y[i];
	cin >> n;
	for(int i=0;i<n;i++)cin >> x[i] >> y[i];
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			int ans1=X[i]-x[j];
			int ans2=Y[i]-y[j];
			for(int k=0;k<m;k++){
				int a=X[k]-ans1;
				int b=Y[k]-ans2;
				for(int l=0;l<n;l++){
					if(a==x[l]&&b==y[l])goto next;
				}
				goto fail;
				next:;
			}
			printf("%d %d\n",0-ans1,0-ans2);
			goto a;
			fail:;
		}
	}
	a:;
	
	}
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int H, W, h, w; cin >> H >> W >> h >> w;
    int table[H][W];
    rep(i, H) rep(j, W) table[i][j] = 1;

    rep(i, h){
        rep(j, W){
            table[i][j] = 0;
        }
    }

    rep(i, w){
        rep(j, H){
            table[j][i] = 0;
        }
    }
    int ans = 0;
    rep(i, H) rep(j, W) if(table[i][j]) ans++;
    cout << ans << endl;
}

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

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

    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0;i < n;i++){
        cin >> a[i];
    }
    ll odd = 0;
    ll even = 0;
    ll four = 0;
    for (ll i = 0; i < n; i++){
        if (a[i]%2 != 0){
            odd++;
        }
        else{
            if (a[i]%4 != 0){
                even++;
            }
            else{
                four++;
            }
        }
    }

    if (min(n,(n+1-even)) <= (2*four+1)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

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

int n, m, k, j;

int main(){
  scanf("%d%d%d", &n, &m, &k);
  for(int i = 100; i > 0; i--){
    if(n%i + m%i == 0){
      if(++j == k) printf("%d\n", i);
    }
  }
}

Measured memory_bytes: 256
import numpy as np

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = np.zeros(N, dtype=int)
h = np.array(h)
 
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
 
print(dp[-1])

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


int main(){
	int n;
	cin >> n;
	vector<int> dp(3,0);
	for(int i = 0;i<n;i++){
		vector<int> days(3);
		vector<int> aux_dp(3,0);
		for(int &x : days) scanf("%d",&x);
		for(int j = 0;j<3;j++){
			for(int k = 0;k<3;k++){
				if(j != k){
					aux_dp[k] = max(aux_dp[k],dp[j]+days[k]);
				}
			}
		}
		dp = aux_dp;
	}
	printf("%d\n",max(dp[0],max(dp[1],dp[2])));
}


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

void textIO()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

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


int main()
{
    textIO();
    fastIO();

    long long n, m, k, ans = 0;
    cin >> n >> m >> k;
    vector<long long> f(n), s(m);

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

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

    long long i = 0, j = 0, cnt = 0;

    while(k-f[i] >= 0 && i<n){
        k-=f[i];
        i++;
        cnt++;
    }

    i--;

    ans = max(cnt, ans);

    while(j<m){
        while(k-s[j] >= 0 && j<m){
            k-=s[j];
            j++;
            cnt++;
        }
        ans = max(ans, cnt);

        if(i>=0){
            k+=f[i];
            i--;
            cnt--;
        }
        else{
            break;
        }
    }

    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 6332
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define M 1000001
#define mod 10007

int main(void){
    int N,A[200000]={};
    int x;
    scanf("%d",&N);
    for (int i=0; i<N-1; i++) {
        scanf("%d",&x);
        A[x-1]++;
    }
    for (int i=0; i<N; i++) {
        printf("%d\n",A[i]);
    }
    return 0;
}

Measured memory_bytes: 2516
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>

using namespace std;

int main(void){

    string str;
    string ans[4] = {"NA", "YYMM", "MMYY", "AMBIGUOUS"};
    int flag = 0;

    cin >> str;

    int a = 0, b = 0;

    a += (str[0]-'0')*10;
    a += (str[1]-'0');

    b += (str[2]-'0')*10;
    b += (str[3]-'0');

    if(0 <= a && 1 <= b && b <= 12) flag += 1;
    if(1 <= a && a <= 12 && 0 <= b) flag += 2;

    cout << ans[flag] << endl;

    return 0;
}

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

int main(int argc, char const *argv[])
{
    int a;
    int b;
    cin>>a>>b;
    int c=a+b;
    
    if (c%2==0) {
        cout<<c/2;
    }
    else
    {
        cout<<c/2+1;
    }
    
    
    return 0;
}


Measured memory_bytes: 256
# ABC096
H, W = map(int, input().split())
S = [input()  for i in range(H)]
ans = "Yes"
# 4隅
if S[0][0] == "#":
    if S[0][1] == S[1][0] == ".":
        ans = "No"
if S[0][W-1] == "#":
    if S[0][W-2] == S[1][W-1] == ".":
        ans = "No"
if S[H-1][0] == "#":
    if S[H-2][0] == S[H-1][1] == ".":
        ans = "No"
if S[H-1][W-1] == "#":
    if S[H-2][W-1] == S[H-1][W-2] == ".":
        ans = "No"

# 角っこを除いた横辺
for w in range(1, W-1):
    if S[0][w] == "#":
        if S[0][w-1] == S[0][w+1] == S[1][w] == ".":
            ans = "No"
    if S[H-1][w] == "#":
        if S[H-1][w-1] == S[H-1][w+1] == S[H-2][w] == ".":
            ans = "No"

# 角っこを除いた縦辺
for h in range(1, H-1):
    if S[h][0] == "#":
        if S[h-1][0] == S[h][1] == S[h+1][0] == ".":
            ans = "No"
    if S[h][W-1] == "#":
        if S[h-1][W-1] == S[h][W-2] == S[h+1][W-1] == ".":
            ans = "No"

# 辺以外
for h in range(1, H-1):
    for w in range(1, W-1):
        if S[h][w] == "#":
            if S[h-1][w] == S[h][w-1] == S[h][w+1] == S[h+1][w] == ".":
                ans = "No"

print(ans)

Measured memory_bytes: 3192
#!/usr/bin/env python3
import sys


def solve(N: int, i: int):
    ret = N - i + 1
    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
    i = int(next(tokens))  # type: int
    solve(N, i)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7;

int main() {
  ll n,k; cin>>n>>k;
  ll ans=0;
  // n+1個からk個以上の数を選び出す
  // 選ぶ個数が異なる場合、合計値は同じにはならない
  // 選ぶ数がk~n+1個の場合まで式に当てはめて足していく
  for(ll i=k; i<=n+1; i++) {
    ll minNum = (i*(i-1))/2;
    ll maxNum = i*n-minNum;
    (ans+=maxNum-(minNum-1))%=MOD;
    //cout << "i: " << i << ", min : " << minNum << ", max : " << maxNum << endl;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3652
import java.util.*;
public class Main {
	public void doit() {
		Scanner sc = new Scanner(System.in);
		sc.nextInt();
		sc.nextInt();
		int N = sc.nextInt();
		int wcnt= 0;
		int[] now = new int[2];
		int[] to = new int[2];
		now[0] = sc.nextInt();
		now[1] = sc.nextInt(); 
		for(int i = 1; i < N; i++) {
			to[0] = sc.nextInt();
			to[1] = sc.nextInt();
			int x = to[0] - now[0];
			int y = to[1] - now[1];
			//System.out.printf("%d %d\n", x,y);
			if(x >= 0 && y >= 0 || x < 0 && y < 0) {
				x = Math.abs(x); y = Math.abs(y);
				wcnt += Math.max(x,y);
			} else {
				x = Math.abs(x); y = Math.abs(y);
				wcnt += x+y;
			}
			//System.out.println(wcnt);
			now[0] = to[0]; now[1] = to[1];
		}
	System.out.println(wcnt);
	}
	public static void main(String[] args) {
		new Main().doit();
	}

}

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

int main(){
  int n;
  int k;
  std::cin >> n >> k;
  std::vector<int> v(n);
  rep(i,n){
    std::cin >> v[i];
  }

  sort(v.begin(),v.end());

  int ans=0;
  rep(i,k){
    ans+=v[i];
  }

  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3600
#include<iostream>
using namespace std;
typedef struct{int c,s,f;}RAIL;
int main(void){
    int n,time;
    cin>>n;
    RAIL r[n-1];
    for(int i=0;i<n-1;i++)cin>>r[i].c>>r[i].s>>r[i].f;
    for(int i=0;i<n;i++){
        time=0;
        for(int j=i;j<n-1;j++){
            if(time<r[j].s)time=r[j].s;
            time+=(time%r[j].f==0?0:r[j].f-(time%r[j].f))+r[j].c;
        }
        cout<<time<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
from math import gcd
def main():
  n, m = map(int, input().split())
  alst = list(map(int, input().split()))
  blst = list(map(int, input().split()))
  g1 = alst[0]
  for i in range(1, n):
    g1 = gcd(g1, alst[i])
  
  l2 = blst[0]
  for i in range(1, m):
    g2 = gcd(l2, blst[i])
    l2 = l2 * blst[i] // g2
  
  if g1 % l2 != 0:print(0)
  else:
    x = g1 // l2
    ans = 1
    for solver in range(2, 10000000):
      if solver > x:break
      cnt = 1
      while x % solver == 0:
        cnt += 1
        x //= solver
      ans *= cnt
    print(ans)
  
main() 


Measured memory_bytes: 5668
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n ;
  vector<int> d(n);

  for (int i = 0; i < n; i++)
  {
    cin >> d[i];
  }
  sort(d.begin(),d.end());
  cout << d[n/2]-d[n/2-1] << endl;
  
}

Measured memory_bytes: 640
import math

a,b,h,m = map(int,input().split())
pi = math.pi

h = h * 60 

a_angle = (pi/360) * (h + m)
b_angle = (pi/30) * (h + m)
ab_angle = abs(a_angle - b_angle)

result = a**2 + b**2 - 2 * a * b * math.cos(ab_angle)
print(math.sqrt(result))


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

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

int main(){
  int n, k, l[50];
  int ans = 0;
  std::cin >> n >> k;
  for(int i = 0; i < n; i++) std::cin >> l[i];

  qsort(l, n, sizeof(int), compare_int);
  for(int i = 0; i < k; i++) ans += l[i];
  std::cout << ans;

  return 0;
}


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

typedef long long ll;

int main() {
    bool a=0,b=0;
    string s;cin>>s;
    for(auto x:s) if(x=='A') a=1;else b=1;
    if(a&&b) cout<<"Yes";else cout<<"No";
    return 0;
}

Measured memory_bytes: 384
//	created : 16/04/28
// 	author   : Rp7rf
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define INF 1e9

double tr(int m, int y, double r){
  return (double)m * (1 + y * (r/100));
}

double fr(int m, int y, double r){
  return (double)m * pow(1+r/100,y) ;
}

int main(void){
  int n,y;
  int money = 10000;
  while(cin>>n,n){
    int ans ;
    cin>>y;
    double ret = 0, rate;
    rep(i,n){
      int b,t;
      double r;
      cin>>b>>r>>t;
      if(t == 1){
        rate = tr(money,y,r);
      }else{
        rate = fr(money,y,r);
      }
      if(ret < rate){
        ret = rate;
        ans = b;
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1232