akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a > b ? -1 : a < b;
}

int N, K;
int T[114514];

int tomatu[114514];

int main(void) {
	int i;
	int sumipe;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &T[i]) != 1) return 1;
	}
	for (i = 1; i < N; i++) {
		tomatu[i - 1] = T[i] - T[i - 1] - 1;
	}
	qsort(tomatu, N - 1, sizeof(*tomatu), cmp);
	sumipe = T[N - 1] + 1 - T[0];
	for (i = 0; i < K - 1; i++) {
		sumipe -= tomatu[i];
	}
	printf("%d\n", sumipe);
	return 0;
}



Measured memory_bytes: 2760
#include "bits/stdc++.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;
    
    int ans = 0;
    for (int i = 0; i < (S.size()/2); i++)
    {
        /* code */
        // cout << S[i] << ' ' << S[S.size() - i - 1] << endl;
        if (S[i] != S[S.size() - i - 1]){
            /* code */
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
	string s;
	int res = 0, count = 0;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'A' || s[i] == 'T' || s[i] == 'C' || s[i] == 'G')
		{
			while (s[i] == 'A' || s[i] == 'T' || s[i] == 'C' || s[i] == 'G')
			{
				count++;
				i++;
				if (res < count)
				{
					res = count;
				}
			}
			count = 0;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int c=0;
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

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

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }



    public static void main(String[] args)throws IOException {
        FastReader fr = new FastReader();
        int n = fr.nextInt();
        int k=fr.nextInt();
        int arr[] =new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = fr.nextInt();
        }
        int sums[]=new int[n];
        Arrays.fill(sums,Integer.MAX_VALUE);
        sums[0]=0;
        sums[1]=Math.abs(arr[1]-arr[0]);
        for(int i=0;i<n;i++)
        {
            int j=i+1;
            int c=1;
            while(j<n&&c<=k)
            {
                sums[j]=Math.min(sums[i]+Math.abs(arr[j]-arr[i]),sums[j]);
                j++;
                c++;
            }
        }
        System.out.println(sums[n-1]);


    }




}


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

using namespace std;

#define int long long

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

#define rep(i,a,b) for (int i = a; i <= (int)b; ++i)
#define f first
#define s second

#define single_test

const int maxn = 1e5 + 4;
int a[maxn][3];
int dp[maxn][3], n;

int go(int pos, int last) {
    if (pos == n) {
        return 0;
    }
    int &ref = dp[pos][last];
    if (ref != -1) {
        return ref;
    }
    int ans = 0;
    for (int i = 0; i < 3; ++i) {
        if (i != last) {
            ans = max(ans, a[pos][i] + go(pos + 1, i));
        }
    }
    return ref = ans;
}

void solve() {
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < 3; ++i) {
        ans = max(ans, a[0][i] + go(1, i));
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Measured memory_bytes: 16088
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

int in[105];
int main() {
	int N, i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &in[i]);
	sort(in + 1, in + N + 1);

	int ans = 0;
	for (i = N; i >= 1; i--) {
		if (N % 2 == i % 2) ans += in[i];
		else ans -= in[i];
	}
	return !printf("%d\n", ans);
}

Measured memory_bytes: 256
#include <stdio.h>

   int A[1000000], n;

int search(int a) 
{
   int l = 0;
   int r = n;
   int m;

   while ( l < r ) {
      m = ( l + r ) / 2;
      if ( a == A[ m ] ) return 1;
      if ( a > A[ m ] ) l = m + 1;
      else if ( a < A[ m ] ) r = m;
   }
   return 0;
}

int main()
{
   int i, q, a;
   int wa = 0;

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

   for ( i = 0; i < q; i++ ) {
      scanf("%d", &a);
      if ( search( a ) ) {
         wa = wa + 1;
      }
   }
   printf("%d\n", wa);

   return 0;
} 

   

Measured memory_bytes: 2128
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

a, b, c = MAP()

# 解毒剤入りおいしいの全部 + 毒入りを食べれる最大
print(b + min(a+b+1, c))


Measured memory_bytes: 5844
#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
#define MAXN 100005

LL min(LL x, LL y) {if(x<y) return x; return y;}

int n, m, s, t, u, v;
LL a, b, f=1e15, ans[MAXN];

struct Graph
{
	int cnt, head[MAXN], vis[MAXN];
	LL dis[MAXN];
	
	struct Edge {int next, to; LL dis;} edge[MAXN*2];
	
	std::queue<int> q;
	
	void addedge(int from, int to, LL dis)
	{
		edge[++cnt].next=head[from];
		edge[cnt].to=to;
		edge[cnt].dis=dis;
		head[from]=cnt;
	}
	
	void spfa(int s)
	{
		for(int i=1; i<=n; i++) dis[i]=INF;
		memset(vis, 0, sizeof(vis));
		q.push(s); vis[s]=1; dis[s]=0;
		while(!q.empty())
		{
			int x=q.front(); q.pop();
			vis[x]=0;
			for(int i=head[x]; i; i=edge[i].next)
			{
				int to=edge[i].to;
				if(dis[to]>dis[x]+edge[i].dis)
				{
					dis[to]=dis[x]+edge[i].dis;
					if(!vis[to]) q.push(to), vis[to]=1;
				}
			}
		}
	}
} g1, g2;

int main()
{
	
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d%lld%lld", &u, &v, &a, &b);
		g1.addedge(u, v, a); g1.addedge(v, u, a);
		g2.addedge(v, u, b); g2.addedge(u, v, b);
	}
	g1.spfa(s);  g2.spfa(t);
	ans[n+1]=INF;
	for(int i=n; i>=1; i--) ans[i]=min(ans[i+1], g1.dis[i]+g2.dis[i]);
	for(int i=1; i<=n; i++) printf("%lld\n", f-ans[i]);
}

Measured memory_bytes: 12032
class Dice:
    """????????????????????????"""
    def __init__(self, s):
        self.s = [0 for _ in range(6)]
        self.s[0] = s[0]
        self.s[1] = s[1]
        self.s[2] = s[2]
        self.s[3] = s[3]
        self.s[4] = s[4]
        self.s[5] = s[5]

    def roll(self, direction):          # ???????????????????§??????¢????????¢
        temp = self.s[0]
        if direction == "E":
            self.s[0] = self.s[3]
            self.s[3] = self.s[5]
            self.s[5] = self.s[2]
            self.s[2] = temp
        elif direction == "N":
            self.s[0] = self.s[1]
            self.s[1] = self.s[5]
            self.s[5] = self.s[4]
            self.s[4] = temp
        elif direction == "S":
            self.s[0] = self.s[4]
            self.s[4] = self.s[5]
            self.s[5] = self.s[1]
            self.s[1] = temp
        elif direction == "W":
            self.s[0] = self.s[2]
            self.s[2] = self.s[5]
            self.s[5] = self.s[3]
            self.s[3] = temp

    def issame(self, s):
        answer = 0
        for _ in range(3):
            for _ in range(4):
                self.roll("N")
                self.roll("E")
                self.roll("S")
                if self.s == s:
                    answer = 1
            self.roll("N")
            for _ in range(4):
                self.roll("N")
                self.roll("E")
                self.roll("S")
                if self.s == s:
                    answer = 1
            self.roll("E")
        return answer


n = int(input())
for i in range(n):
    s = list(map(int, input().split()))
    code = "dice{} = Dice(s)".format(i)
    exec(code)

answer = "Yes"
for i in range(n-1):
    for j in range(i+1, n):
        code = "ans = dice{0}.issame(dice{1}.s)".format(i, j)
        exec(code)
        if ans == 1:
            answer = "No"

print(answer)

Measured memory_bytes: 7920
import sys
import math
import fractions
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def factorize(n):
    b = 2
    fct = dict()
    while b * b <= n:
        while n % b == 0:
            n //= b
            if b in fct:
                fct[b] += 1
            else:
                fct[b] = 1
        b = b + 1
    if n > 1:
        if b in fct:
            fct[n] += 1
        else:
            fct[n] = 1
    return fct


def divmod(x, mod=10**9 + 7):
    return pow(x, mod - 2, mod)


def solve():

    N = int(input())
    A = list(map(int, input().split()))
    B = [[1] for _ in range(N)]

    fac_list = dict()
    for i in range(N):
        d = factorize(A[i])
        for k, v in d.items():
            fac_list[k] = max(fac_list.get(k, 0), v)

    lcm = 1
    for k, v in fac_list.items():
        lcm *= (k**v)
        lcm %= mod

    ans = 0
    for i in range(N):
        ans += divmod(A[i])
        ans %= mod

    ans *= lcm
    ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()


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

int main(){
    int n,x;
    cin >> n >> x;
    int m;
    int mini = 1000;
    for (int i = 0; i < n; i++){
        cin >> m;
        mini =  min(mini,m);
        x -= m;
    }
    cout << n + x/mini << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  // 一年の秒数
  int a, b;
  int ans = 24;
 
  // 以下のコメント/* */を消して追記する
  cin >> a >> b;
  
  int x = a + b;
  if(x % 2 == 0)  //あまりましなし
  {
  	ans = x / 2;
  }
  else
  {
  	ans = x / 2 + 1;
  }
  
  cout << ans << endl;
}

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

using lint = long long;
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define repu(i, a, b, s) for(int i = int(a); i < int(b); i += int(s))
#define repd(i, a, b, s) for(int i = int(a); i > int(b); i += int(s))
#define endl "\n"
constexpr lint INF = 2e18;
constexpr lint MOD = 1e9 + 7;

void solve() {
    lint N, T, A;
    cin >> N >> T >> A;

    vector<lint> H(N);
    for(auto &&it : H) {
        cin >> it;
    }

    double min_diff = INF;
    lint ans = -1;

    rep(i, N) {
        double diff = abs(A - (T - H[i] * 0.006));
        if(diff < min_diff) {
            min_diff = diff;
            ans = i + 1;
        }
    }

    cout << ans << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    solve();
}

Measured memory_bytes: 3552
#[allow(dead_code)]
fn main() {
    let (n, k) = i::u2();
    let a = i::uv(n);

    let mut l = vec![1];
    let mut s = HashSet::new();
    let mut c = 0;
    let mut last = 0;
    loop {
        if s.contains(&a[l[c] - 1]) {
            last = a[l[c] - 1];
            break;
        }
        l.push(a[l[c] - 1]);
        s.insert(a[l[c] - 1]);
        c += 1;
    }
    let mut l_start = 0;
    for i in 0..l.len() {
        if l[i] == last {
            l_start = i;
            break;
        }
    }
    if k < l.len() {
        println!("{}", l[k]);
        return;
    }
    let loop_len = l.len() - l_start;

    let k = (k - l_start) % loop_len;
    println!("{}", l[l_start + k]);
    //dbg!(c, l, k, loop_len, last, l_start);
}

#[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: 8064
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef int_fast64_t ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}
ll gcd(ll a,ll b){ll c=max(a,b);ll d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modfact(ll a){ll b=1;FOR(i,2,a)b=b*i%MOD;return b;}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}
ll modcomb(ll n, ll k){ll b=1;k=min(n-k,k);DOWN(i,n,n-k+1)b=b*i%MOD;return b*modpow(modfact(k),MOD-2)%MOD;}

ll N;
ll A[50], B[50];

int main() {
    fastio();
    cin >> N;
    REP(i, N) cin >> A[i];
    ll ans = 0, tmp;
    while (true) {
        tmp = 0;
        REP(i, N) {
           B[i] = A[i] / N;
           tmp += B[i];
           A[i] -= B[i] * N;
        }
        if(tmp == 0) break;
        ans += tmp;
        REP(i, N)
            A[i] += (tmp - B[i]);
    }
    cout << ans << endl;
	return 0;
}

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

IL int gi(){
    int data = 0 , m = 1; char ch = 0;
    while(ch!='-' && (ch<'0'||ch>'9')) ch = getchar();
    if(ch == '-'){m = 0 ; ch = getchar() ; }
    while(ch >= '0' && ch <= '9'){data = (data<<1) + (data<<3) + (ch^48) ; ch = getchar(); }
    return (m) ? data : -data ; 
}

#define mod 1000000007
IL void add(int &x , int y) {x += y ; if(x >= mod) x -= mod ; }

int f[3005][3005][2],n,m,Ans ; 
int main() {
	n = gi() ; m = gi() ;
	f[0][0][1] = 1 ; for(int j = 1; j <= n; j ++) f[0][j][0] = 1 ;
	for(int i = 0; i < m; i ++)
		for(int j = 0; j <= n; j ++)
			for(int op = 0; op <= 1; op ++) {
				if(j) add(f[i + 1][j][op | (j == 1)] , f[i][j][op]) ;
				if(j) add(f[i + 1][j - 1][op | (j == 1)] , f[i][j][op]) ;
				if(j < n) add(f[i + 1][j][op] , f[i][j][op]) ;
				if(j < n) add(f[i + 1][j + 1][op] , f[i][j][op]) ;
			}
	Ans = 0 ;
	for(int j = 0; j <= n; j ++) add(Ans , f[m][j][1]) ;
	cout << Ans << endl ;
}


Measured memory_bytes: 70656
H, W = gets.split.map(&:to_i)
c = Array.new(10) { gets.split.map(&:to_i) }
A = Array.new(H) { gets.split.map(&:to_i) }

10.times do |k|
  10.times do |i|
    10.times do |j|
      c[i][j] = [c[i][j], c[i][k] + c[k][j]].min
    end
  end
end

puts A.flatten.map { |a| a != -1 ? c[a][1] : 0 }.inject(0, &:+)


Measured memory_bytes: 3324
s = int(input())
DP = [s]
S = set()
S.add(s)
cnt = 1
while True:
    cnt += 1
    if DP[-1] % 2 == 0:
        x = DP[-1] // 2
    else:
        x = DP[-1] * 3 + 1
    if x in S:
        break
    S.add(x)
    DP.append(x)


print(cnt)

Measured memory_bytes: 61760
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod (ll)1000000007
#define INF LLONG_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
signed main() {
	int h, w, a, b;
	cin >> h >> w >> b >> a;
	rep(i, h) {
		rep(j, w) {
			if (i < a && j < b)cout << 1;
			else if (a <= i && b <= j)cout << 1;
			else cout << 0;
		}
		cout << endl;
	}
	return 0;
}

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

using namespace std;

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


Measured memory_bytes: 3556
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	
	int n;
	
	string str;
	
	char c[100];
	
	cin >> n;
	
	for(int loop = 0; loop < n; loop++){
		cin >> str;
		
		if(cin.eof()){
			break;
		}
		
		for(int i = 0; i < 100; i++){
			c[i] = ' ';
		}
		
		int index = 50;
		
		for(int i = 0; i < str.size(); i += 3){
			c[index] = str[i];
			
			if(i == str.size()){
				break;
			}
			
			if(str[i + 2] == '>'){
				index++;
			}else{
				index--;
			}
		}
		
		for(int i = 0; i < 100; i++){
			if(c[i] != ' '){
				printf("%c", c[i]);
			}
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 1172
words = lambda t : list(map(t, input().split()))

def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

def lcm(x,y):
    return (x * y) // gcd(x,y)

def num_div(k,s):
    return s // k

a,b,c,d = words(int)

cd_lcm = lcm(c,d)

n_div_till_b = num_div(c,b) + num_div(d,b) - num_div(cd_lcm, b)
n_div_till_am1 = num_div(c,a-1) + num_div(d,a-1) - num_div(cd_lcm,a-1)

ans = (b-a+1) - n_div_till_b + n_div_till_am1

print(ans)


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



int main() {
  string s;
  cin >> s;
  if(s[s.length() - 1] == 's') cout << s << "es" << endl;
  if(s[s.length() - 1] != 's') cout << s << "s" << endl;



}

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

using namespace std;

using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for (auto &i : mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    cin >> a;
    vl d(n);
    rep(_, k) {
        vl imos(n + 1);
        rep(i, n) {
            imos[max(0LL, i - a[i])]++;
            imos[min(n, i + a[i] + 1)]--;
        }
        ll now = 0;
        rep(i, n) {
            now += imos[i];
            a[i] = now;
        }
        ll cnt = 0;
        rep(i, n) {
            if (a[i] >= n) cnt++;
        }
        if (cnt == n) {
            rep(i, n) {
                a[i] = n;
            }
            break;
        }
    }
    rep(i, n) {
        cout << a[i] << ' ';
    }
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 7900
#include <stdio.h>
int main() {
    long long n;
    scanf("%lld", &n);
    long long t1 = n / 3, t2 = n / 5, t3 = n / 15;
    printf("%lld\n", n * (n + 1) / 2 - 3 * t1 * (t1 + 1) / 2 - 5 * t2 * (t2 + 1) / 2 + 15 * t3 * (t3 + 1) / 2);
}


Measured memory_bytes: 1732
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
q = int(input())
tei = 0
x = []
nnn = []
import bisect
def press(a):
    n = len(a)
    b = set(a)
    b = list(b)
    b.sort()
    c = [0] * n
    for i in range(n):
        c[i] = bisect.bisect_left(b,a[i])
    return b,c
for i in range(q):
        nnn.append(input().rstrip())
for i in range(q):
        nn = nnn[i]
        if int(nn[0]) == 1:
                _,a,b = map(int,nn.split())
                x.append(a)
x.sort()
mo,za = press(x)
mo = x
d = dict()
for i in range(len(x)):
        d[mo[i]] = za[i]+1
dg = dict()
for i in range(len(x)):
        dg[za[i]+1] = mo[i]
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
bit1 = BIT(len(x))
bit2 = BIT(len(x))
now = -1
def cheak(x,y):
  o = bit2.sum(x)
  if y >= o:
    return 0
  else:
    return 1
for i in range(q):
        nn = nnn[i]
        if int(nn[0]) == 1:
                _,a,b = map(int,nn.split())
                tei += b
                bit1.add(d[a],a)
                bit2.add(d[a],1)
                now += 1
        else:
                dai = len(x)
                syo = 1
                while True:
                        if dai-syo <= 1:
                                if cheak(syo,now//2) == 1:
                                        dai = syo
                                break
                        kon = (dai+syo)//2
                        c = cheak(kon,now//2)
                        if c == 1:
                                dai = kon
                        else:
                                syo = kon
                ans = 0
                ans -= bit1.sum(dai) - dg[dai]*bit2.sum(dai)
                ans += bit1.sum(len(x)) -bit1.sum(dai) -((bit2.sum(len(x))-bit2.sum(dai))*dg[dai])
                print(dg[dai],tei+ans)

Measured memory_bytes: 112084
N, K = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)

INF = 10**18
dp = Array.new(N+1){Array.new(N+1){Hash.new(INF)}}
dp[0][0][0] = 0
N.times do |i|
    N.times do |j|
        dp[i][j].each do |k, v|
            if k < as[i]
                dp[i+1][j+1][as[i]] = [dp[i+1][j+1][as[i]], v].min
            else
                nk = k+1
                nv = v + nk - as[i]
                dp[i+1][j][k] = [dp[i+1][j][k], v].min
                dp[i+1][j+1][nk] = [dp[i+1][j+1][nk], nv].min
            end
        end
    end
end
ans = (K..N).map{|k| dp[N][k].values.min}.min
puts ans

Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)

const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

int N,T; 
int dp[3010][3010];
int dp2[3010][3010];
int w[3010],v[3010];

void solve(){
    for(int i=N-1;i>=0;i--){
        for(int j=0;j<T;j++){
            if(j<w[i]){
                dp[i][j] = dp[i+1][j];
            } else {
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
            }
        }
    }
}

void solve2(){
    for(int i=0;i<N;i++){
        for(int j=0;j<T;j++){
            if(j<w[i]){
                dp2[i+1][j] = dp2[i][j];
            } else {
                dp2[i+1][j] = max(dp2[i][j],dp2[i][j-w[i]]+v[i]);
            }
        }
    }
}

signed main() {
    cin >> N >> T;
    rep(i,N){
        cin >> w[i] >> v[i];
    }
    solve(); solve2();
    int ans=0;
    rep(i,N){
        rep(j,T){
            ans = max(ans,dp2[i][j]+dp[i+1][T-1-j]+v[i]);
        }
    }
    cout << ans << endl;
}


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

using namespace std;

long long a[3010];
int n;
long long res[3010][3010];

long long resi(int l, int d)
{
    if(l > d) return 0;
    if(res[l][d] != 0) return res[l][d];
    if(n % 2 != (d-l) % 2)
        res[l][d] = max(resi(l + 1, d) + a[l], resi(l, d - 1) + a[d]);
    else
        res[l][d] = min(resi(l + 1, d) - a[l], resi(l, d - 1) - a[d]);
    return res[l][d];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    cout << resi(0, n - 1);
    

    
    return 0;
}

Measured memory_bytes: 70272
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize
    }
    let mut ans = vec![];
    let mut b = 0;
    while n + 1 >= 1 << b + 1 {
        b += 1;
    }
    let m = n + 1 - (1 << b);
    let mut r = b + m.count_ones() as usize;
    for i in 0..b {
        if m & 1 << i != 0 {
            ans.push(r);
            r -= 1;
        }
        ans.push(i + 1);
    }
    println!("{}", ans.len() * 2);
    for i in 0..ans.len() {
        print!("{} ", ans[i]);
    }
    for i in 1..ans.len() {
        print!("{} ", i);
    }
    println!("{}", ans.len());
}


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

int main(){
  int h,w;
  cin>>h>>w;
  vector<string> a(h);
  for(int i=0; i<h; ++i)cin>>a[i];

  set<pair<int,int>> black;
  for(int i=0; i<h; ++i){
    for(int j=0; j<w; ++j){
      if(a[i][j]=='#')black.insert(make_pair(i,j));
    }
  }

  vector<vector<int>> b(h, vector<int>(w, 0));
  bool flg=true;

  vector<int> dx{0, 1, 0, -1}, dy{1, 0, -1, 0};

  int count=0, ans=0;
  while(black.size()!=0){
    set<pair<int,int>> black2;
    for(pair<int,int> z:black){
      int y,x;
      for(int k=0; k<4; ++k){
        y=z.first+dy[k], x=z.second+dx[k];
        if(0<=y && y<h && 0<=x && x<w && a[y][x]=='.'){
          b[y][x]=count+1;
          a[y][x]='#';
          black2.insert(make_pair(y,x));
        }
      }
    }
    ans=count;
    ++count;
    black.swap(black2);
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 52096
#include <stdio.h>
#include <string.h>
char a[200];
int main()
{
  int n,i,j,t,h;
  for(;;){
    scanf("%d",&n);
    if(n==0) break;
    memset(a,0,sizeof(a));
    for(i=0;i<n;i++){
      scanf("%d",&j);
      a[j-1] = 1;
    }
    i=0;
    j=1;
    t=h=n;
    for(;;){
      for(;i<n*2;i++){
	if(a[i] == j){
	  if(j==1){
	    if(--t == 0) break;
	    j = 0;
	  }else{
	    if(--h == 0) break;
	    j = 1;
	  }
	  a[i] = -1;
	}
      }
      if(t == 0 || h == 0) break;
      if(i==n*2){
	i = 0;
	j = (j==1)?0:1;
      }
    }
    printf("%d\n%d\n",h,t);
  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int main(){
	double ax,ay,bx,by,cx,cy,dx,dy;
	double abx,aby,cdx,cdy;
	for(;scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy)!=EOF;){
		abx=bx-ax;aby=by-ay;
		cdx=dx-cx;cdy=dy-cy;
		if(abx*cdx+aby*cdy==0)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 0
# coding: utf-8
"""this is python work script"""
def sum_num(i):
    sum_tmp = 0
    p = i
    for _ in range(5):
        p, mod = divmod(p, 10)
        sum_tmp += mod
        if p == 0:
           break
    return sum_tmp

def solve(N, num_min, num_max):
    """solve problem"""
    result = 0
    for i in range(1, N+1):
        sum_tmp = sum_num(i)
        if num_min <= sum_tmp and sum_tmp <= num_max:
            result += i
    return result

def main():
    N, A, B = list(map(int, input().rstrip().split(' ')))
    answer = solve(N, A, B)
    print(answer)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int n, a[100010], b[100010];
ll ans;

void solve(){
	scanf("%d", &n);
	rep(i, n)scanf("%d%d", a+i, b+i);
	ll ad = 0;
	for(int i=n-1;i>=0;i--){
		ll t = (a[i] + ad) % b[i];
		t = (t ? b[i] - t : 0);
		ad += t;
		ans += t;
	}
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Measured memory_bytes: 1024
//default
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
typedef pair<int, int> P_i;
typedef pair<double,double> P_d;
#define rep(i,n) for(int i=0;i<(n);++i)
#define alrep(i,j,n) for(int i=0;i<(n);++i)for(int j=i+1;j<(n);++j)
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;int ans=0;
#define answer cout << ans << 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 MOD=1e9+7;
const long long INF = 1LL << 60;

signed main(){
  int N,K;
  double ans=-1;
  cin >> N >> K;
  double p[N];
  rep(i,N){
    cin >> p[i];
    p[i]=(double)(p[i]+1)/(double)2;
  }
  double res=0;
  rep(i,K){
    res+=p[i];
  }
  chmax(ans,res);
  rep(i,N-K){
    res-=p[i];
    res+=p[i+K];
    chmax(ans,res);
  }
  cout << fixed << setprecision(6) << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int main(){
int a,b,c;
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
if(a<b && b<c){
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}

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

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_V(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_M(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}

int main() {
    int n, k;
    cin >> n >> k;
    if (k > (n - 1) * (n - 2) / 2) {
        cout << -1 << endl;
        return 0;
    }

    V<pair<int, int>> edge;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            edge.push_back({i, j});
        }
    }

    for (int i = 0; i < k; i++) {
        edge.pop_back();
    }

    cout << edge.size() << endl;
    for (auto e : edge) {
        cout << e.first << " " << e.second << endl;
    }

    return 0;
}

Measured memory_bytes: 384
n, k = map(int, input().split())
s = list(input().strip())

streaks = []
c = s[0]
i = 1
count = 1
while True:
    if i == n:
        streaks.append(count)
        break
    if s[i] == c:
        i += 1
        count += 1
    else:
        streaks.append(count)
        c = s[i]
        i += 1
        count = 1

accs = [0]
for num in streaks:
    accs.append(accs[-1] + num)
if accs[-1] != n:
    accs.append(n)

flag = s[0] == '0'
res = []
for i in range(len(accs)):
    if flag:
        index = i + 2 * k
    else:
        index = i + 2 * k + 1
    index = min(index, len(accs) - 1)
    res.append(accs[index] - accs[i])
    flag = not flag

print(max(res))

Measured memory_bytes: 12620
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int main(){

    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll A = max(a*c, a*d);
    ll B = max(b*c, b*d);
    cout << max(A,B) << endl;
    return 0;

}


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

using namespace std;

const long long INF = 1LL << 60;

long long dp1[5000][5001];
long long dp2[5000][5001];

int solve(const vector<vector<int>>& g, const vector<long long>& A, int pos, int prev){
    int res = 1;
        if(A[pos] > 0) dp1[pos][1] = A[pos];
        dp2[pos][1] = A[pos];
    if(g[pos].size() == 1 && prev != -1) return res;
    vector<long long> ndp1(g.size()+1), ndp2(g.size()+1);
    for(auto next : g[pos]){
        if(next == prev) continue;
        int size = solve(g, A, next, pos);
        for(int i=1;i<=res+size;i++) ndp1[i] = ndp2[i] = INF;
        for(int i=1;i<=size;i++){
            for(int j=1;j<=res;j++){
                if(dp1[pos][j] != INF){
                    if(dp1[next][i] != INF){
                        ndp1[i+j-1] = min(ndp1[i+j-1], dp1[next][i] + dp1[pos][j]);
                    }
                    if(dp1[next][i] != INF || dp2[next][i] < 0){
                        ndp1[i+j] = min(ndp1[i+j], dp1[pos][j]);
                    }
                }
                ndp2[i+j-1] = min(ndp2[i+j-1], dp2[next][i] + dp2[pos][j]);
                if(dp1[next][i] != INF || dp2[next][i] < 0){
                    ndp2[i+j] = min(ndp2[i+j], dp2[pos][j]);
                }
            }
        }
        res += size;
        for(int i=0;i<=res;i++){
            dp1[pos][i] = ndp1[i];
            dp2[pos][i] = ndp2[i];
        }
    }
    return res;
}

int main(){
    int N;
    while(cin >> N && N){
        for(int i=0;i<N;i++){
            for(int j=0;j<=N;j++) dp1[i][j] = dp2[i][j] = INF;
        }
        vector<long long> A(N);
        for(auto& t : A) cin >> t;
        vector<vector<int>> g(N, vector<int>());
        for(int i=0;i<N-1;i++){
            int U, V; cin >> U >> V;
            --U; --V;
            g[U].push_back(V);
            g[V].push_back(U);            
        }
        solve(g, A, 0, -1);
        for(int i=1;i<=N;i++){
            if(dp1[0][i] != INF || dp2[0][i] < 0){
                cout << i-1 << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 746404
#include<iostream>
#include<iomanip>
#include<limits>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include <functional>

#define big ((long long)(1e9)+7)

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main()
{
	ll n,a,b;
	cin >> n >> a >> b;
	if(a > b)
	{
		cout << 0 << endl;
		return 0;
	}
	else if(n == 1)
	{
		if(a == b)
		{
			cout << 1 << endl;
		}
		else
		{
			cout << 0 << endl;
		}
	}
	else
	{
		cout << (b-a)*(n-2)+1 << endl;
	}
}


Measured memory_bytes: 256
#include <stdio.h>

int Selectionsort(int a[], int n);
void swap(int *a, int *b);

int main(){
	int i,n,x;
	int a[100];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	x=Selectionsort(a,n);
	for(i=0;i<=n-1;i++){
		if(i>0) printf(" ");
		printf("%d",a[i]);
	}
	printf("\n");
	printf("%d\n",x);
	return 0;
}

int Selectionsort(int a[], int n){
	int i,j;
	int count=0,min;
	for(i=0;i<n;i++){
		min=i;
		for(j=i;j<n;j++){
			if(a[j]<a[min]){
				min=j;
			}
		}
		if(i!=min){
			swap(&a[i],&a[min]);
			count++;
		}
	}
	return count;
}

void swap(int *a, int *b){
	int c;
	c=*a;
	*a=*b;
	*b=c;
}

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

int main(){
  int N, K;
  cin >> N >> K;
  
  int ans = 0;
  vector<int> l(N);
  REP(i, 0, N) cin >> l.at(i);
  sort(l.begin(), l.end(), greater<int>());
  REP(i, 0, K) ans += l.at(i);
  cout << ans << endl;
  return 0;
}

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

namespace _0048_Class
{
    class Program
    {
        static void Main(string[] args)
        {
            string str;
            while ((str = Console.ReadLine()) != null)
            {
                double weight = double.Parse(str);
                if (weight <= 48.00)
                {
                    Console.WriteLine("light fly");
                }
                else if (weight > 48.00 && weight <= 51.00)
                {
                    Console.WriteLine("fly");
                }
                else if (weight > 51.00 && weight <= 54.00)
                {
                    Console.WriteLine("bantam");
                }
                else if (weight > 54.00 && weight <= 57.00)
                {
                    Console.WriteLine("feather");
                }
                else if (weight > 57.00 && weight <= 60.00)
                {
                    Console.WriteLine("light");
                }
                else if (weight > 60.00 && weight <= 64.00)
                {
                    Console.WriteLine("light welter");
                }
                else if (weight > 64.00 && weight <= 69.00)
                {
                    Console.WriteLine("welter");
                }
                else if (weight > 69.00 && weight <= 75.00)
                {
                    Console.WriteLine("light middle");
                }
                else if (weight > 75.00 && weight <= 81.00)
                {
                    Console.WriteLine("middle");
                }
                else if (weight > 81.00 && weight <= 91.00)
                {
                    Console.WriteLine("light heavy");
                }
                else if(weight > 91.00)
                {
                    Console.WriteLine("heavy");
                }
            }
        }
    }
}



Measured memory_bytes: 15892
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = list(map(lambda x: (x[0], x[1], x[0]*x[1]/((x[0]-1)*D)) ,[(2, A), (3, B), (5, C),]))
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if cost >= ans:
            continue

        for r, co1, n2 in abc:
            if rest < n2:
                ans = min(ans, rest*D + cost)
                continue

            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            a3 = r - a2
            if a2 == a3:
                heappush(dq, (cost + co1 + a3*D, a1+1))
            elif a2 > a3:
                a1 += 1
                a2 = a3

            heappush(dq, (cost + co1 + a2*D, a1))

    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 10328
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

count = 0
for i in range(N):
  ip = C
  for j in range(M):
    ip += B[j] * A[i][j]
  if ip > 0:
    count += 1
      
print(count)

Measured memory_bytes: 3064
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

aL = [0 for _ in range(n+1)]
bL = [0 for _ in range(m+1)]

for i in range(n):
    aL[i+1] = aL[i] + a[i]
for i in range(m):
    bL[i+1] = bL[i] + b[i]

ans = 0
j = m

for i in range(n+1):
    if aL[i] > k:
        break
    while bL[j] > k - aL[i]:
        j -= 1
    ans = max(ans, i+j)

print(ans)

Measured memory_bytes: 47344