akhauriyash/Code-Regression huggingface dataset:
//g++でビルド

#include "bits/stdc++.h"

using namespace std;

int n;
vector<int> a;
vector<int> b;
vector<int> c;

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        int s;
        cin >> s;
        a.push_back(s);
    }
    for(int i=0; i<n; i++){
        int s;
        cin >> s;
        b.push_back(s);
    }
    for(int i=0; i<n; i++){
        int s;
        cin >> s;
        c.push_back(s);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    long long result = 0;

    for(int i = 0; i < n; i++){
        long long low=lower_bound(a.begin(),a.end(),b[i])-a.begin();
        long long hi=c.end()-upper_bound(c.begin(),c.end(),b[i]);
        if(low<0)low=0;
        if(hi<0)hi=0;
        result+=hi*low;
    }

    cout << result << endl;
    return 0;
}

Measured memory_bytes: 1784
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (1 << 11), K = 11;
int n, k, q, a[N], val[N], used[N], par[N], m;
vector <int> pos[N];
priority_queue <int> pq;
priority_queue <int, vector <int>, greater <int> > st[N];

void upd(int x) {
	while ((int)st[x].size() > k - 1) {
		pq.push(st[x].top());
		st[x].pop();
	}
}

void make_set(int x) {
	par[x] = x;
	st[x].push(a[x]);
}

int find_set(int x) {
	if (x == par[x]) return x;
	return par[x] = find_set(par[x]);
}

void union_set(int x, int y) {
	x = find_set(x), y = find_set(y);
	if (x == y) return;
	if ((int)st[x].size() < (int)st[y].size())
		swap(x, y);
	par[y] = x;
	while (!st[y].empty()) {
		st[x].push(st[y].top());
		st[y].pop();
	}
	upd(x);
}

void add(int x) {
	upd(x);
	used[x] = 1;
	if (used[x - 1])
		union_set(x - 1, x);
	if (used[x + 1])
		union_set(x, x + 1);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> k >> q;
	vector <int> b;
	for (int i = 1; i <= n; i++) cin >> a[i], b.pb(a[i]);
	sort(all(b));
	b.erase(unique(all(b)), b.end());
	m = b.size();
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(all(b), a[i]) - b.begin() + 1;
		val[x] = a[i];
		a[i] = x;
		pos[x].pb(i);
		make_set(i);
	}
	int ans = 1e9;
	for (int i = m; i >= 1; i--) {
		for (int j : pos[i])
			add(j);
		while ((int)pq.size() > q) pq.pop();
		if ((int)pq.size() == q)
			ans = min(ans, val[pq.top()] - val[i]);
	}
	cout << ans;
}


Measured memory_bytes: 3960
#主人の大好きな数字
fav = 753
listA = list(input())
N = len(listA)
#ダックスフンドの選ぶ数字
s = 0

for i in range(0,N-2):
  a,b,c = map(str,listA[i:i+3])
  x = a+b+c
  if abs(fav-s) > abs(fav-int(x)):
    s = int(a+b+c)
print(abs(fav-s))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define all(x) x.begin(),x.end()
#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define N

int main(){
	FIO;
	string s; cin >> s;
    if(s=="ABC") cout << "ARC" << endl;
    else cout << "ABC"  << endl;
	return 0;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    void solve() {
        input();
        int N;
        cin >> N;
        vector<ll> A(N);
        rep(i, 0, N) cin >> A[i];
        sort(all(A));
        for (int i = 0; i < A.size() - 1; ++i) {
            A[i + 1] += A[i];
        }
        A.push_back(0);

        int ans = 0;
        for (int i = N - 1; i >= 0; --i) {
            if (A[i] * 3 >= A[i + 1]) {
                ans++;
            } else {
                break;
            }
        }
        cout << ans << endl;

    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 2424
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    VI d(N);
    LL ans = 0;
    REP(i,N) cin >> d[i];
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            ans += d[i] * d[j];
        }
    }
    cout << ans << endl;

}


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

string s[305];

int typ[305][305];

vector <int> ans[90000+50];


int main()
{
    // cout << "Hello World!" << endl;
    ios::sync_with_stdio(false);
    int h,w,k;
    cin>>h>>w>>k;
    
    int last=0;
    bool topfound=false;
    for(int i=1;i<=h;i++){
        cin>>s[i];
        s[i]="@"+s[i];
        
        int le=1;
        bool found=false;
        for(int j=1;j<=w;j++){
            if(s[i][j]=='#'){
                topfound=true;
                found=true;
                for(int kk=le;kk<=j;kk++){
                    typ[i][kk]=last+1;
                    
                }
                last++;
                le=j+1;
            }
        }
        
        for(int kk=le;kk<=w;kk++){
            typ[i][kk]=typ[i][kk-1];
        }
        
        if(topfound==false){
            continue;
        }
        else{
            if(found==false){
                
                for(int j=1;j<=w;j++){
                    typ[i][j]=typ[i-1][j];
                }
            }
        }
        
        
    }
    
    
    for(int i=h;i>=1;i--){
        bool found=false;
        
        for(int j=1;j<=w;j++){
            if(typ[i][j]!=0){
                found=true;
            }
        }
        
        if(found==false){
            for(int j=1;j<=w;j++){
                typ[i][j]=typ[i+1][j];
            }
        }
    }
    
    
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cout<<typ[i][j]<<" ";
        }
        cout<<"\n";
    }
    
    
    return 0;
}


Measured memory_bytes: 3328
A, B = map(int, input().split())
if A <= B:
    s0, s1 = '.', '#'
    M, m = B, A
else:
    s0, s1 = '#', '.'
    M, m = A, B

print(100, 100)

ans = [[s0] * 100 for _ in range(100)]
ans[0] = [s1] * 100
ans[1] = [s0, s1] * 50
M -= 1
m -= 1

y, x = 2, 0
for _ in range(m):
    ans[y][x] = s1
    x += 2
    if x >= 100:
        y += 1
        x = y % 2
y, x = 98, 1
for _ in range(M - m):
    ans[y][x] = s1
    x += 2
    if x >= 100:
        y -= 2
        x = 1
for a in ans:
    print(''.join(map(str, a)))



Measured memory_bytes: 3188
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        set<string> se;
        string str; cin >> str;
        for(int j=0; j<str.size()-1; ++j){
            string head, tail;
            head = str.substr(0, j+1);
            tail = str.substr(j+1, str.size()-j);
            string tmp; tmp = head+tail;
            se.insert(tmp);
            tmp = tail+head;
            se.insert(tmp);
            
            reverse(head.begin(), head.end());
            tmp = head+tail;
            se.insert(tmp);
            tmp = tail+head;
            se.insert(tmp);
            
            reverse(head.begin(), head.end());
            reverse(tail.begin(), tail.end());
            tmp = head+tail;
            se.insert(tmp);
            tmp = tail+head;
            se.insert(tmp);
            
            reverse(head.begin(), head.end());
            tmp = head+tail;
            se.insert(tmp);
            tmp = tail+head;
            se.insert(tmp);
        }
        cout << se.size() << endl;
    }
    
}



Measured memory_bytes: 3128
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;


void printarray(int n, int a[])
{
    for (int i = 1; i < n + 1; i++)
    {
        cout << a[i];
        if (i != n)
            cout << " ";
    }
    cout << endl;
}

int cycleanalysis(int n, int a[])
{
    int pos, ret, next;
    pos = 0, ret = 0;
    for (int i = 1; i < n + 1; i++)
    {
        pos = i;
        while (a[pos] != pos)
        {
            ret += (a[pos] + a[a[pos]]);
            next = a[pos];
            swap(a[pos], a[a[pos]]);
            pos = next;
        }
    }

    return ret;
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    double n, weight, total, vi, wi;
    vector<tuple<double, double, double>> material;
    cin >> n >> weight;
    for (int i = 0; i < n; i++){
    cin >> vi >> wi;
    material.push_back(make_tuple(vi/wi, vi, wi));
    }
    sort(material.rbegin(),material.rend());

    for (tuple<double, double, double> x : material){
        if (weight >= get<2>(x)) {
            total += get<1>(x);
            weight -= get<2>(x);
        }
        else if (weight > 0){
            total += get<0>(x)*weight;
            weight = 0;
        }
    }
        
    printf( "%.8f", total );

    return 0;
}


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

int main(){
    l1 a,b,c,d;

    cin>>a>>b>>c>>d;

    l1 ans[6];
    ans[0] = a*c;
    ans[1] = a*d;
    ans[2] = b*c;
    ans[3] = b*d;
    l1 answer;
    if((a<0&&b>0) || (c<0&&d>0)){
        answer = 0;
    }else{
        answer = -1000000000000000000;
    }
    rep(i,4){
        answer = max(answer,ans[i]);
    }

    cout<<answer;

    return 0;
}

Measured memory_bytes: 3660
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    char[] c=sc.next().toCharArray();
    int sum=0;
    for(int i=0;i<4;i++){
      if(c[i]=='+'){
        sum++;
      }else{
        sum--;
      }
    }
    System.out.println(sum);
  }
}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int F,T;
	bool f=true;
	char c;
	int Q;
	string s;
	cin>>s;
	scanf("%d",&Q),getchar();
	for(int i=0;i<Q;i++){
		scanf("%d",&F),getchar();
		if(F==1) f^=1;
		else{
			scanf("%d",&T),getchar();
			scanf("%c",&c),getchar();
			if(T==1&&f==true || T==2&&f==false)
				s.insert(s.begin(),c);
			if(T==1&&f==false || T==2&&f==true)
				s.push_back(c);
		}
	}
	if(!f)reverse(s.begin(),s.end());
	cout<<s<<endl;
}

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

int main() {
    int N, sum = 0;
    cin >> N;
    for(int i = 0; i < N; i++){
        int l, r;
        cin >> l >> r;
        sum += (r - l) + 1;
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
import sys
import fractions
input = sys.stdin.buffer.readline
def lcm(x,y):
  return((x*y)//fractions.gcd(x,y))
def main():
  N=int(input())
  arr=list(map(int,input().split()))
  MOD=1000000007 
  LCM=1
  for i in arr:
    LCM=lcm(LCM,i)
  ans=0
  for i in arr:
    ans += LCM//i
  print(ans%MOD)
if __name__=="__main__":
  main()

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

class Program {
    static string ReadLine() { return Console.ReadLine().Trim(); }
    static int ReadInt() { return int.Parse(Console.ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    static void Display(int[] xs) {
//        for (int i = 0; i < xs.Length; i++) {
//            if (i > 0) Console.Write(' ');
//            Console.Write(xs[i]);
//        }
//        Console.WriteLine();


//        string[] ss = new string[xs.Length];
//        for (int i = 0; i < xs.Length; i++) {
//            ss[i] = xs[i].ToString();
//        }

//        Console.WriteLine(string.Join(" ", ss));

        string[] ss = xs.Select(e => e.ToString()).ToArray();
        Console.WriteLine(string.Join(" ", ss));
    }

    static void Main() {
        int n = ReadInt();
        int[] xs = ReadInts();
        if (n != xs.Length) throw new Exception();

        Display(xs);
        for (int i = 1; i < xs.Length; i++) {
            int key = xs[i];
            // insert xs[i] into the sorted sequence xs[0..j-1]
            int j = i - 1;
            while (j >= 0 && xs[j] > key) {
                xs[j+1] = xs[j];
                j--;
            }
            xs[j+1] = key;

            // output
            Display(xs);
        }
    }
}

Measured memory_bytes: 6116
#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--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,a;
    cin >> n >> a;
    n %= 500;
    Yes(n <= a);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define MAXN 100000
using namespace std;
typedef pair<int, int> Pii;
int main(){
	int lim[3] = {0,0,MAXN*3+1}, cnt[3];
	Pii a[3*MAXN];
	int N = 0;
	long long ans = 0;
	cin >> lim[0] >> lim[1] >> cnt[0] >> cnt[1] >> cnt[2];
	for(int i=0; i<3; i++)
		while(cnt[i]--){
			cin >> a[N].first;
			a[N++].second = i;
		}
	sort(a, a+N, greater<pair<int, int>>());
	N = lim[0] + lim[1];
	for(int i=0; N; i++){
		if(!lim[a[i].second])
			continue;
		ans += a[i].first;
		lim[a[i].second]--;
		N--;
	}
	cout << ans << endl;
}


		



Measured memory_bytes: 2560
N,A,B=map(int, input().split())
V=list(map(int, input().split()))
d={}
for v in V:
    if v in d:
        d[v]+=1
    else:
        d[v]=1
k=sorted(d.keys(),reverse=True)
def comb1(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    a=b=1
    for i in range(1,k+1):
        a=a*(n-k+i)
        b=b*i
    return a//b
ans=0
if d[k[0]]>=A:
    for x in range(A,min(B,d[k[0]])+1):
        ans+=comb1(d[k[0]],x)
    ave=k[0]
else:
    n=d[k[0]]
    a=[k[0]]*d[k[0]]
    for i in range(1,len(k)):
        if n+d[k[i]]>=A:
            break
        else:
            n+=d[k[i]]
            a+=[k[i]]*d[k[i]]
    ans=comb1(d[k[i]],A-n)
    a+=[k[i]]*(A-n)
    from statistics import mean
    ave=mean(a)
print(ave)
print(ans)

Measured memory_bytes: 5148
n=int(input())
a=list(map(int,input().split()))
kosu=[0 for i in range(n)]
kosu0=3
josu=0
ans=1
cnt=0
for i in a:
  if i==0:
    josu=kosu0
    kosu0-=1
    kosu[i]+=1
  else:
    josu=kosu[i-1]-kosu[i]
    kosu[i]+=1
  ans*=josu
  ans%=1000000007
  josu=0
print(ans)

Measured memory_bytes: 14396
#define INF 999999
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
typedef pair<int, int> P;
int mas[10][10],mass[10][10];
int d[100][100];
int dx[] ={0,0,1,1,-1,-1,2,2,2,-2,-2,-2},dy[] = {2,-2,2,-2,2,-2,0,1,-1,0,1,-1};
int n,sx,sy,kx[10],ky[10];
int cnt = 0,cnt2 = 0;
bool f = 0;
int bfs();
int main(){
  while(1){
    cnt2 = 0;
    cin >> sx >> sy;
    if(sx == 0 && sy == 0)break;
    cin >> n;
    for(int i = 0; i < n; i++){
      cin >> kx[i] >> ky[i];
      mas[ky[i]][kx[i]] = i + 1;
    }
    int ans = bfs();
    if(ans == 1) cout << "OK" << endl;
    else cout << "NA" << endl;
  }
}
int bfs(){
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
      d[i][j] = INF;
    }
  }
  queue <P> que;
  que.push(P(sx,sy));
  d[sy][sx] = 0;
  while(!que.empty()){
    if(cnt == 1)cnt2++;
    cnt = 0;
    P p = que.front();
    que.pop();
    if(cnt2 == n){
      return 1;  
    }
    for(int i = 0; i < 12; i++){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(nx >= 0 && ny >= 0 && nx <= 9 && ny <= 9 && nx >= kx[cnt2] - 1 && nx <= kx[cnt2] + 1 && ny >= ky[cnt2] - 1 && ny <= ky[cnt2] + 1 && d[ny][nx] == INF){
	que.push(P(nx,ny));
	d[ny][nx] = 1;
	cnt = 1;
      }
    }
  }
  return -1;
}

Measured memory_bytes: 1200
#include <iostream>
#include "bits/stdc++.h"

using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i, a, b) for(ll i=a;i<b;i++)
#define REP(i, a) for(ll i=0;i<a;i++)
#define jkl ll debug = 0;
#define RREP(i, a) for(ll i=a;i>0;i--)
#define rrep(i, a, b) for(ll i=a-1;i>=b;i--)
#define printall(n, array) {for(ll i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> Pi;
typedef pair<ll, Pi> V;
typedef vector<ll> VE;
typedef vector<vector<ll>> VVE;
const ll mod = 1e9 + 7; //10^9+7

int main() {
    string s;
    ll n, k;
    cin >> n >> s >> k;
    jkl;
    char target = s[k - 1];
    REP(i, s.size()) {
        if(s[i] != target)s[i] = '*';
    }
    print(s);
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static FastReader input = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);

	static int n;
	static int[] a;
	static int[] memo;
	static final int INF = (int) 1e9;
	static int k  ;
	
	static int solve(int n) {

		if (n < 0)
			return INF;

		if (n == 0)
			return 0;

		if (memo[n] != -1)
			return memo[n];

		int min = INF;

		for (int i = 1; i<=k && n-i>=0; i++) {
			min = Math.min(min, Math.abs(a[n]-a[n-i])+ solve(n-i));
		}

		return memo[n] = min;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {

		n = input.nextInt();
		k = input.nextInt();
		a = new int[n];
		memo = new int[n + 10];
		Arrays.fill(memo, -1);

		for (int i = 0; i < n; i++)
			a[i] = input.nextInt();

		System.out.println(solve(n - 1));

	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		String nextLine() throws IOException {
			String str = "";
			str = br.readLine();
			return str;
		}
	}
}


Measured memory_bytes: 47328
import java.util.*;


public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        if(N%func(N)==0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
        System.out.println();
    }
    public static int func(int x){
        if(x/10==0){
            return x%10;
        }
        return x%10+func(x/10);
    }
}


Measured memory_bytes: 21972
N=int(input())
H=list(map(int,input().split()))
if N==1:
  print("Yes")
  exit()
if H[0]<H[1]:
  H[0]-=1
elif H[0]>H[1]:
  print("No")
  exit()
for i in range(1,N):
  if H[i-1]<H[i]:
    H[i]-=1
  elif H[i-1]>H[i]:
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 14252
#[allow(dead_code)]
fn main() {
    let n = i::u();
    let mut a = i::iv(n);
    a.sort();
    let mut max = a[n - 1];
    let mut min = a[0];
    let mut ans = Vec::new();
    for i in 1..n - 1 {
        if a[i] < 0 {
            ans.push(format!("{} {}", max, a[i]));
            max = max - a[i];
        } else {
            ans.push(format!("{} {}", min, a[i]));
            min = min - a[i];
        }
    }
    println!("{}", max - min);
    for i in ans {
        println!("{}", i);
    }
    println!("{} {}", max, min);
}

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::num::*;
#[allow(unused_imports)]
use std::str::*;

#[allow(dead_code)]
mod i {
    use super::*;

    pub fn read<T: FromStr>() -> T {
        stdin()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse::<T>()
            .ok()
            .unwrap()
    }

    pub fn str() -> String {
        read()
    }

    pub fn s() -> Vec<char> {
        str().chars().collect()
    }

    pub fn i() -> i64 {
        read()
    }

    pub fn u() -> usize {
        read()
    }

    pub fn u2() -> (usize, usize) {
        (read(), read())
    }

    pub fn u3() -> (usize, usize, usize) {
        (read(), read(), read())
    }

    pub fn f() -> f64 {
        read()
    }

    pub fn c() -> char {
        read::<String>().pop().unwrap()
    }

    pub fn iv(n: usize) -> Vec<i64> {
        (0..n).map(|_| i()).collect()
    }

    pub fn iv2(n: usize) -> Vec<(i64, i64)> {
        (0..n).map(|_| iv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv(n: usize) -> Vec<usize> {
        (0..n).map(|_| u()).collect()
    }

    pub fn uv2(n: usize) -> Vec<(usize, usize)> {
        (0..n).map(|_| uv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv3(n: usize) -> Vec<(usize, usize, usize)> {
        (0..n).map(|_| uv(3)).map(|a| (a[0], a[1], a[2])).collect()
    }

    pub fn fv(n: usize) -> Vec<f64> {
        (0..n).map(|_| f()).collect()
    }

    pub fn cmap(h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| s()).collect()
    }
}


Measured memory_bytes: 13436
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  string S1, S2, S3;
  transform(s1.begin(), s1.end(), s1.begin(), ::toupper);
  transform(s2.begin(), s2.end(), s2.begin(), ::toupper);
  transform(s3.begin(), s3.end(), s3.begin(), ::toupper);
  cout << s1[0] << s2[0] << s3[0] << "\n";
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

int main() {
  int N;
  while (cin >> N) {
    vector<double> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    vector<double> dp(1, 0);
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
      vector<double> ndp(i + 2, 0);
      for (int j = 0; j <= i; j++) {
        ndp[j] += dp[j] * (1 - p[i]);
        ndp[j + 1] += dp[j] * p[i];
      }
      dp = ndp;
    }
    double res = 0;
    for (int i = 0; i <= N; i++) {
      int j = N - i;
      if (i > j) res += dp[i];
    }
    printf("%.20f\n", res);
  }
  return 0;
}


Measured memory_bytes: 384
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  vector<int> vi;
typedef  pair<int,int> pii;
typedef  pair<int,string> pis;
double pi=3.1415926535898;
#define speed      ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define lop(i,n)   for(int i=0;i<int(n);i++)
#define rep(i,a,b) for(int i=a;i<=int(b);++i)
#define rng(i,a,b) for(int i=a;i>=int(b);i--)
#define ms(x,a)    memset(x,a,sizeof(x))
#define all(x)     (x).begin(),(x).end()
#define sz(x)      int(x.size())
#define pb         push_back
#define r0         return 0;
#define CC         continue;
#define bb(x)      cerr<< x <<endl;
#define F          first
#define S          second       //  __builtin_popcount;
//freopen("output.txt","w",stdout),freopen("input.txt","r",stdin);
const ll M  = 1e9+7 ;
const int N = 300100;
const int inf = INT_MAX;
const double eps = 1e-7;
//////////////////////    Hi    ^_^  hack me if you can :P

int a[100];
int n, p;
int s;
ll mem[100][5005];
ll dp ( int i, int s)
{
    if ( i == n) return s%2 == p;
    ll &r = mem[i][s];
    if (r!=-1)
    {
        return r;
    }
    return r = dp(i+1,s+a[i])+dp(i+1,s);
}
int main()
{
    speed;
    cin >> n >> p;
    lop(i,n) cin >> a[i];
    ms(mem,-1);
    cout << dp(0,0);

    return 0;
}


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

int main(){
  int n,k; cin >>n >>k;
  vector<int> p(n);
  rep(i,n) cin >>p[i];
  sort(p.begin(), p.end());
  int ans = 0;
  rep(i,k) ans+=p[i];
  cout << ans << endl;
  return 0; 
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define int long long
bool ch(int a,int b){
  int x=1000000000000000LL;
  x/=a;
  x/=b;
  return x==0;
}
signed main(){
  int n,m,a,b,p,q;
  cin>>n>>m>>a>>b>>p>>q;
  if(a==1&&b==1){
    //cout<<m%(p+q)<<endl;
    if(ch(n,p+q)) cout<<min(m%(p+q),(p+q)-m%(p+q))<<endl;
    else{
      int t=n*(p+q);
      if(m>=t) cout<<m-t<<endl;
      else cout<<min(m%(p+q),(p+q)-m%(p+q))<<endl;
    }
    return 0;
  }
  int ans=m;
  int ta=1,tb=1;
  vector<int> v;
  for(int i=0;i<n;i++){
    if(ch(p,ta)) break;
    if(ch(q,tb)) break;
    int t=p*ta+q*tb;
    //cout<<t<<endl;
    if(t<=m) v.push_back(t);
    else{
      ans=min(ans,t-m);
      break;
    }
    if(ch(ta,a)) break;
    if(ch(tb,b)) break;
    ta*=a;tb*=b;
  }
  int x=v.size();
  int y=x/2;
  set<int> s;
  for(int i=0;i<(1<<y);i++){
    int t=0;
    for(int j=0;j<y;j++) if((i>>j)&1) t+=v[j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }    
    //cout<<t<<endl;
    s.insert(-t);
    ans=min(ans,m-t);
  }
  
  for(int i=0;i<(1<<(x-y));i++){
    int t=0;
    for(int j=0;j<(x-y);j++) if((i>>j)&1) t+=v[y+j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }
    //cout<<t<<endl;
    ans=min(ans,m-t);
    int u=t-m;
    int k=*s.lower_bound(u);
    ans=min(ans,m-(t-k));
  }
  
  s.clear();
  for(int i=0;i<(1<<y);i++){
    int t=0;
    for(int j=0;j<y;j++) if((i>>j)&1) t+=v[j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }    
    //cout<<t<<endl;
    s.insert(t);
    ans=min(ans,m-t);
  }
  
  int inf=m*2;
  s.insert(inf);
  for(int i=0;i<(1<<(x-y));i++){
    int t=0;
    for(int j=0;j<(x-y);j++) if((i>>j)&1) t+=v[y+j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }
    //cout<<t<<endl;
    ans=min(ans,m-t);
    int v=m-t;
    int l=*s.lower_bound(v);
    if(l!=inf) ans=min(ans,(t+l)-m);
  }
  //assert(ans>=0);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 39876
#include<iostream>
#include<vector>

using namespace std;

int main(void){
  int a,b,c,n;
  while(cin>>a>>b>>c,a+b+c){
  cin>>n;
  vector<int> in(a+b+c+1,2);
  vector<vector<int> > jud(n,vector<int>(4,0)); 
  for(int l = 0 ; l < n ; l ++){
    int i , j , k , r;
    cin>>i>>j>>k>>r;
    if(r == 1){
      in[i] = in[j] = in[k] = 1;
    }
    jud[l][0] = i ; jud[l][1] = j ;
    jud[l][2] = k ; jud[l][3] = r;
  }
  
  for(int i = 0 ; i < jud.size() ; i ++){
    if(jud[i][3] == 0){
      if(in[jud[i][0]] == 1 && in[jud[i][1]] == 1) in[jud[i][2]] = 0;
      if(in[jud[i][2]] == 1 && in[jud[i][0]] == 1) in[jud[i][1]] = 0;
      if(in[jud[i][2]] == 1 && in[jud[i][1]] == 1) in[jud[i][0]] = 0;
    }
  }    
  
  for(int i = 1 ; i < in.size() ; i ++)
    cout<<in[i]<<endl;
  }
  return 0;
}

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

using namespace std;

vector<int> v(3);

int main(){
	ios_base::sync_with_stdio(false);
  	cin >> v[0] >> v[1] >> v[2];
  	sort(v.begin(), v.end());
  	if(v[2] & 1){
    	cout << v[0] * 1LL * v[1] << endl;
    } else{
    	cout << 0 << endl;
    }

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll MOD=10000000;
const ll INF=1000000001;
const ll LINF=4000000000000000010;
const double EPS=1e-9;
int main(){
    ll h,w;cin>>h>>w;
    ll ans=LINF;
    ll s=h*w;
    for(ll i=1;i<=h-1;i++){
        ll s1=i*w;
        ll s2=(w/2)*(h-i);
        ll s3=s-s1-s2;
        ll ma=max(s1,max(s2,s3));
        ll mi=min(s1,min(s2,s3));
        ans=min(ans,ma-mi);
        s2=w*((h-i)/2);
        s3=s-s1-s2;
        ma=max(s1,max(s2,s3));
        mi=min(s1,min(s2,s3));
        ans=min(ans,ma-mi);
    }
    for(ll i=1;i<=w-1;i++){
        ll s1=i*h;
        ll s2=(h/2)*(w-i);
        ll s3=s-s1-s2;
        ll ma=max(s1,max(s2,s3));
        ll mi=min(s1,min(s2,s3));
        ans=min(ans,ma-mi);
        s2=h*((w-i)/2);
        s3=s-s1-s2;
        ma=max(s1,max(s2,s3));
        mi=min(s1,min(s2,s3));
        ans=min(ans,ma-mi);
    }
    cout<<ans<<endl;
}


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

using namespace std;

int main(int argc, char *argv[]) {
    int N;
    cin >> N;
    vector<int> arr(N);
    vector<int> arr1;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    arr1 = arr;
    sort(arr.begin(), arr.end());

    int last = arr[N - 1];
    int last2 = arr[N - 2];

    for (int j = 0; j < N; j++) {
        int cur = arr1[j];
        if (cur == last) {
            cout << last2 << endl;
        } else {
            cout << last << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3200
from collections import deque

h,w,n=map(int,input().split())

w+=2
G=[list('X'*w)]
for i in range(h):
    G+=[list('X'+input()+'X')]
G+=[list('X'*w)]
h+=2

def bfs(sx,sy,gx,gy):
    que=deque()
    g=[[float('inf')]*w for _ in range(h)]
    g[sx][sy]=0
    que.append((sx,sy))
    xy=[(0,-1),(-1,0),(1,0),(0,1)]

    while que:
        x,y=que.popleft()
        if x==gx and y==gy:break
        for dx,dy in xy:
            nx=x+dx
            ny=y+dy
            if G[nx][ny]!='X' and g[nx][ny]==float('inf'):
                que.append((nx,ny))
                g[nx][ny]=g[x][y]+1
    return g[gx][gy]


res=0

goals=[(0,0) for i in range(n+1)]

for i in range(1,h):
    for j in range(1,w):
        if G[i][j]=='S':
            goals[0]=(i,j)
        if G[i][j].isdecimal():
            num=int(G[i][j])
            goals[num]=(i,j)

for i in range(len(goals)-1):
    sx,sy=goals[i][0],goals[i][1]
    gx,gy=goals[i+1][0],goals[i+1][1]
    
    res+=bfs(sx,sy,gx,gy)

print(res)


Measured memory_bytes: 35396
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto xn = readln.split.to!(int[]);
    auto X = xn[0];
    auto N = xn[1];
    bool[101] ps;
    foreach (p; readln.split.to!(int[])) ps[p] = true;
    foreach (d; 0..100) {
        auto x = X-d;
        if (x < 0 || !ps[x]) {
            writeln(x);
            return;
        }
        auto y = X+d;
        if (y > 100 || !ps[y]) {
            writeln(y);
            return;
        }
    }
}

Measured memory_bytes: 2764
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


int main()
{
	priority_queue<double> que;
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		double A;
		cin >> A;
		que.push(A);
	}

	for (int i = 0; i < M; i++)
	{
		double top = que.top();
		que.pop();
		que.push(top / 2);
	}

	long long int answer = 0;
	while (!que.empty())
	{
		answer += (int)que.top();
		que.pop();
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 1400
# -*- coding: utf-8 -*-
"""
Created on Sat May 30 16:32:18 2020

@author: NEC-PCuser
"""

a, b, x = map(int, input().split())

a_shou = a // x
b_shou = b // x

ans = b_shou - a_shou

if (a % x == 0):
    ans += 1

print(int(ans))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
bool isPrime(int x){
    if(x==1)return 0;
    if(x==2)return 1;
    if(x%2==0)return 0;
    for(int i=3;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
int main() {
    int x; cin >> x;
    for(int i=x; i<1000000000; i++){
        if(isPrime(i)){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
use libm::{floor, log10};
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: u32,
    }
    let mut ans = 0;
    for i in 1..=n {
        if floor(log10(i as f64)) as u32 % 2 == 0 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2164
arr1 = str(input())
arr = arr1.split()
n = int( arr[0] )
k = int( arr[1] )

if k >= n :
    print(0)
else:
    totalMonster1 = str( input() )
    totalMonster  = totalMonster1.split()
    tMonster = []
    for i in totalMonster:
        tMonster.append(int(i))
    tM1 = sorted(tMonster)
    tM = tM1[::-1]
    tM = tM[k:]
    #print(tM)
    print(sum(tM))


Measured memory_bytes: 92108
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

  int n, d;
  cin >> n >> d;
  vector<vector<int>> v(n, vector<int>(d));
  rep(i, 0, n) { rep(j, 0, d) cin >> v[i][j]; }

  int ans = 0;
  rep(i, 0, n) {
    rep(j, i + 1, n) {
      int sum_val = 0;
      rep(k, 0, d) {
        int t = v[i][k] - v[j][k];
        sum_val += t * t;
      }
      double v = sqrt(sum_val);
      if (floor(v) == v) ans++;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<bool> f(N+10, 0);
	vector<int> a(N+10, 1);
	f[1] = 1;
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		f[y] = f[x] || f[y];
		a[y]++, a[x]--;
		if (!a[x]) f[x] = 0;
	}
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (f[i]) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(){
  int n,x,i,j,k,count;
 
  while(1){
   
    scanf("%d%d",&n,&x);
 
    if(n==0 && x==0)break;
    else{
      count=0;
      for(i=1; i<=n; i++){
    for(j=i+1; j<=n; j++){
      for(k=j+1; k<=n; k++){
        if(i+j+k == x)count++;
      }
    }
      }
      printf("%d\n",count);
    }
  }
  
  return 0;
}

Measured memory_bytes: 600
#include <stdio.h>
#define MAX 100005
#define NIL -1

int D[MAX];

struct node{
  int k;
  int parent;
  int left;
  int right;
};

struct node T[MAX];

void getDepth(int, int);
void print(int);

int main(){
  int n, m, i, j, temp, v, id, a;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;  
  }
  for(i = 0; i < n; i++){
    scanf("%d %d", &v, &m);
    for(j = 0; j < m; j++){
      scanf("%d",&id);
      if(j == 0){
	T[v].left = id;
      }
      if(j != 0){
	T[temp].right = id;
      }
      T[id].parent = v;
      temp = id;
    }
  }
  
  for(i = 0; i < n; i++){
    if(T[i].parent == NIL) a = i;
  }
  
  getDepth(a, 0);
  for(i = 0; i < n; i++){
    print(i);
  }
  
  return 0;
}

void getDepth(int u, int d){
  D[u] = d;
  if(T[u].left != NIL) getDepth(T[u].left, d + 1);
  if(T[u].right != NIL) getDepth(T[u].right, d);
}

void print(int u){
  int i, c, count;

  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("depth = %d, ",D[u]);

  if(T[u].parent == NIL){
    printf("root, ");
  }
  else if(T[u].left == NIL){
    printf("leaf, ");
  }
  else {
    printf("internal node, ");
  }
  printf("[");
  i = 0;
  for(c = T[u].left; c != NIL; c = T[c].right){
    if(i) printf(", ");
    printf("%d",c);
    i++;
  }
  printf("]\n");
}



Measured memory_bytes: 3808
Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    if A==B:
        print((A-1)*2)
    elif A+1==B:
        print((A-1)*2)
    else:
        SQ=int(pow(A*B,0.5))
        if SQ**2==A*B:
            print((SQ-1)*2-1)
        elif SQ*(SQ+1)<A*B:
            print((SQ-1)*2+1)
        else:
            print((SQ-1)*2)

Measured memory_bytes: 38384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
using namespace std;
string s;
using MIte = multimap<int, int>::iterator;




int main() {
	long W, H, x, y;
	cin >> W >> H >> x >> y;

	double maxarea = (double)W * (double)H * 0.5;
	int onlyone = 0;
	if ((2 * x == W) && (2 * y == H)) {
		onlyone = 1;
	}
	else {
		onlyone = 0;
	}

	cout << fixed << setprecision(12) << maxarea << " ";
	cout << onlyone <<  endl;


	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [0]

max_fee = 0
for i in range(1, n + 2):
    max_fee += abs(a[i] - a[i - 1])

for i in range(1, n + 1):
    res = max_fee - abs(a[i] - a[i - 1]) - \
        abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1])
    print(res)


Measured memory_bytes: 20636
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

//////////////////////////////////////


int main() {
	ll N, K;
	cin >> N >> K;

	vector<ll> p(N + 1);
	repn(i, N) cin >> p[i];

	sort(++p.begin(), p.end());

	ll ans = 0;
	repn(i, K) ans += p[i];
	cout << ans << endl;
	
}


Measured memory_bytes: 3584
import java.io.*;
   
class Main {
  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    
    String[] strAry = str.split(" ");
    
    int x = Integer.parseInt(strAry[0]);
    int y = Integer.parseInt(strAry[1]);
    int z = Integer.parseInt(strAry[2]);
    
    int i,cnt = 0;
    
    for(i = x; i <= y; i++){
        if(z % i == 0){
            cnt++;
        }
         }
         System.out.println(cnt);
  }
}

Measured memory_bytes: 24460
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
a_max_1 = max(a)
b = sorted(a, reverse=True)
a_max_2 = b[1]

for i in range(n):
    if a[i] == a_max_1:
        print(a_max_2)
    else:
        print(a_max_1)


Measured memory_bytes: 14204
def main():
    n, m = map(int, input().split())
    dp = [0] * (n + 1)
    dp[0] = 1
    for _ in range(m):
        a = int(input())
        dp[a] = -1
    mod = 10 ** 9 + 7

    for i in range(n + 1):
        if dp[i] == 0:
            if i - 1 >= 0 and dp[i - 1] != -1:
                dp[i] = (dp[i] + dp[i - 1]) % mod
            if i - 2 >= 0 and dp[i - 2] != -1:
                dp[i] = (dp[i] + dp[i - 2]) % mod

    print(dp[-1] % mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 70740
#ifdef __GNUC__ 
#include <bits/stdc++.h>
auto & in = std::cin;
#else
std::istringstream in;
#endif
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/dynamic_bitset.hpp>
using namespace std;
#define ALL(v) std::begin(v),std::end(v)
using u6 = std::uint64_t;

struct Calc {
};
int main() {
#ifndef __GNUC__ 
	in.str("1 2 3 4");
#endif
	int R, G, B, N;
	array<int,3> RGB;
	u6 count = 0;
	for (auto &rgb : RGB)in >> rgb;
	in >> N;
	sort(ALL(RGB),std::greater<>());
	for (int r = 0; r<=N; r += RGB[0]) {
		for (int g = 0; r+g<=N; g += RGB[1]) {
			if ((N-r-g)%RGB[2]==0)++count;
		}
	}
	cout << count << endl;
}


Measured memory_bytes: 256
n,a,b = map(int, input().split())

MOD = (10**9 + 7)
from functools import reduce
from operator import mul

def mulMOD(x,y):
    return x*y%MOD

def nCr(n,r):
    num = reduce(mulMOD, range(n, n - r, -1))
    den = reduce(mulMOD, range(1, r + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

ans = (pow(2,n,MOD) -nCr(n,a)-nCr(n,b)-1)%MOD
print(ans)

Measured memory_bytes: 3572
#include <iostream>
#include <string>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  string o, e; cin >> o >> e;
  REP(i, o.size()) {
    cout << o[i];
    if (i < e.size()) cout << e[i];
  }
  cout << endl;
  return 0;
}

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//Yes, Noと表示後終了
void fYn(bool a)
{
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  exit(0);
}

//実行部
void Main()
{
  ll n, ans = 0;
  cin >> n;
  for(ll i = 1;i <= n;i++)
  {
    if(i % 3 != 0&&i % 5 != 0)
    ans += i;
  }
  fin(ans)
  return;
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 3600