akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn get_value(x: usize) -> usize {
    let mut x = x;
    let mut ret = 0;
    while x > 0 {
        ret += x % 10;
        x /= 10;
    }
    ret
}

fn main() {
    let k = read::<usize>();
    let mut sunuke = vec![];
    for i in 1..10 {
        sunuke.push(i);
        sunuke.push(i * 10 + 9);
    }
    for i in 3..16 {
        'outer_loop: for v1 in 100..1000 {
            let mut lhs = v1;
            let mut base = 1;
            for _ in 3..i {
                lhs = lhs * 10 + 9;
                base *= 10;
            }
            // println!("{}", lhs);
            let mut rhs = lhs;
            for _ in 0..2000 {
                rhs += base;
                if lhs * get_value(rhs) >= rhs * get_value(lhs) {
                    continue 'outer_loop;
                }
            }
            // println!("{}", rhs);
            // println!("{}", base);
            sunuke.push(lhs);
        }
    }
    sunuke.sort();
    sunuke.dedup();
    for i in 0..k {
        println!("{}", sunuke[i]);
    }
    // for &v in sunuke.iter() {
    //     println!("{}", v);
    // }
    // let MAX_VALUE = 10000000;
    // let mut value = vec![0; MAX_VALUE];
    // for i in 0..MAX_VALUE {
    //     value[i] = get_value(i);
    // }
    // 'outer_loop: for i in 0..1000000 {
    //     for j in i + 1..MAX_VALUE {
    //         if i * value[j] > j * value[i] {
    //             continue 'outer_loop;
    //         }
    //     }
    //     println!("{}", i);
    // }
}


Measured memory_bytes: 4352
import re
while 1:
	n,m = map(int,raw_input().split())
	if n ==0: break
	prize = []
	for i in range(n):
		num,money = raw_input().replace("*","[0-9]").split()
		prize.append([re.compile(num),int(money)])
	ans = 0
	for i in range(m):
		lot = raw_input()
		for num,money in prize:
			if num.search(lot):
				ans += money
				break
	print ans

Measured memory_bytes: 4308
import math
a, b, angle_c = map(float, input().split(" "))

S = (a * b * math.sin(math.radians(angle_c))) / 2
print(round(S, 8))

L = (a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(angle_c))) ** 0.5
print(round(L + a + b, 8))

h = b * math.sin(math.radians(angle_c))
print(round(h, 8))


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

int main(){
  int N;
  cin >> N;
  vector<int> A(N),B(N),C(N-1);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  for(int i=0;i<N;i++){
    cin >> B.at(i);
  }
  for(int i=0;i<N-1;i++){
    cin >> C.at(i);
  }
  int ans=0;
  for(int i=0;i<N;i++){
    ans+=B.at(A.at(i)-1);
    if(i!=0 && A.at(i)==A.at(i-1)+1){
      ans+=C.at(A.at(i-1)-1);
    }
  }
  cout << ans << endl;
}
      
      
    

Measured memory_bytes: 3628
N, M, K =  [int(x) for x in input().split()]

stackA = [int(x) for x in input().split()]
stackB = [int(x) for x in input().split()]

indexB = 0
indexA = 0

books = 0
mostBooks = 0
time = 0

for x in stackB:
    if time + x > K:
        break

    else:
        time += x
        indexB += 1
        books += 1

indexB -= 1

mostBooks = books

for x in stackA:
    time += x
    books += 1

    while time > K and indexB >= 0:
        time -= stackB[indexB]
        indexB -= 1
        books -= 1

    if indexB < 0 and time > K:
        break

    mostBooks = max(mostBooks, books)

print(mostBooks)

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

int digit_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n%10;
        n /= 10;
    }
    return sum;
}

int main() {
    int N, A, B;
    cin >> N >> A >> B;

    int sum = 0;
    for (int i = 1; i <= N; i++) {
        int ds = digit_sum(i);
        if (ds >= A && ds <= B) sum += i;
    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x,y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x,y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define d4(x,y,z,w)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z << " | "<< #w << "--> " << w <<endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;
ll mode=1ll<<32;
const ll maxn=1e3+10;
ll __lcm(ll a, ll b){ return (a*b)/__gcd(a,b); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRand(ll l, ll r){ uniform_int_distribution<int> uid(l, r); return uid(rng); }


void solve(){
	
	ll a,b,c;
  	cin>>a>>b>>c;
  	swap(a,b);
  	swap(a,c);
  	cout<<a<<" "<<b<<" "<<c<<endl;
  
	return;
	
}

int main(){ 
    
    #ifndef ONLINE_JUDGE
  	//	freopen("input.txt", "r", stdin);
    #endif
    srand(time(0)); 
    
    ios::sync_with_stdio(0);
    cin.tie(0);


	//T{ solve(); }
	solve();
		
	
	return 0;
}

Measured memory_bytes: 256
N = gets.chomp.to_i
# d = gets.chomp.split.map(&:to_i)
S = gets.chomp.chars

cnt = 1
prev_color = S[0]

1.upto(N-1).each do |i|
  if (S[i] == prev_color)
    next
  else
    prev_color = S[i]
    cnt += 1
  end
end

p cnt

Measured memory_bytes: 6908
#include <bits/stdc++.h>
using namespace std;
 
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;i<n;i++)
#define ll long long
 
#define pi pair < ll , ll >
#define pb push_back
#define mp make_pair
#define F first
#define S second
 
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 
#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
using namespace std;

const ll mod = 1e9+7;
ll power(ll x, ll y, ll m=mod) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2ll, m) % m; 
    p = (p * p) % m; 
    return (y%2 == 0)? p : (x * p) % m; 
} 

ll modInverse(ll a, ll m = mod) 
{ 
    return power(a, m-2ll, m); 
} 

/*void solve() {
    ll n, k, i, j, p, q, ans = 0;
    n = 3;
    cin>>k;
    ll a[k+1];
    Fo(i,1,k+1) {
        a[i] = power(k/i, n);
    }
    for(i=k;i>0;i--) {
        j = 2*i;
        while(j<=k) {
            a[i] = ( a[i] - a[j] + mod ) % mod;
            j += i;
        }
        ans = ( ans + a[i] * i ) % mod;
        // debug2(i,a[i]);
    }
    ans = (ans+mod)%mod;
    cout<<ans;
}*/

/*void solve() {
    ll n, i, j, k, ans = 0, r[4001], g[4001], b[4001];
    string s;
    cin>>n>>s;
    fo(i,n)r[i]=g[i]=b[i]=0;
    ans = n * ( n-1ll ) * ( n-2ll ) / 6ll;
    fo(i,n) {
        if(s[i]=='R') {
            r[i] = 1;
        }
        if(s[i]=='G') {
            g[i] = 1;
        }
        if(s[i]=='B') {
            b[i] = 1;
        }
        if(i>0) {
            r[i] += r[i-1];
            g[i] += g[i-1];
            b[i] += b[i-1];
        }
    }
    fo(i,n) {
        Fo(k,i+2,n) {
            if(s[i]==s[k]) {
                ans -= (k-i-1);
            } else {
                if(s[i]=='R')ans -= r[k-1] - r[i];
                if(s[i]=='G')ans -= g[k-1] - g[i];
                if(s[i]=='B')ans -= b[k-1] - b[i];
                if(s[k]=='R')ans -= r[k-1] - r[i];
                if(s[k]=='G')ans -= g[k-1] - g[i];
                if(s[k]=='B')ans -= b[k-1] - b[i];
            }
            if((k+i)%2==0) {
                j = (k+i)/2;
                if(s[i]!=s[j] and s[k]!=s[j] and s[i]!=s[k])ans--;
            }
        }
    }
    cout<<ans<<endl;
}*/

/*void solve() {
    ll n, i, j, k, a[200001], e = 0, o = 0, ans = -1e16;
    cin>>n;
    fo(i,n) {
        cin>>a[i];
        if(i%2==0)e+=a[i];
        else o+=a[i];
    }
    ll arr[200001];
    arr[0] = a[0];
    Fo(i,1,n) {
        arr[i] = a[i];
        if(i>=2 and i%2!=0)arr[i] = a[i] + arr[i-2];
        if(i>=3)arr[i] = max(arr[i], a[i]+arr[i-3]);
        debug2(i,arr[i]);
    }

    ans = *max_element(arr,arr+n);
    cout<<ans;
}*/

void solve() {
    ll n,ans=0,i;
    cin>>n;
    Fo(i,1,n+1)if(i%3!=0 and i%5!=0)ans+=i;
    cout<<ans;
}

int main()
{
    fastIO;ll t=1;
    // cin>>t;
    while(t--)solve();
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


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

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

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

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

    ll ans = -INF;
    for(ll l=0;l<=n;++l){
        for(ll r=0;r<=n-l;++r){
            ll left = k - (l + r);
            if(left < 0)continue;

            vector<ll> a;
            for(ll i=0;i<l;++i){
                a.push_back(v[i]);
            }
            for(ll i=0;i<r;++i){
                a.push_back(v[n-i-1]);
            }
            sort(a.begin(), a.end());

            ll sum = 0;
            for(ll i=0;i<a.size();++i){
                sum += a[i];
            }

            for(ll i=0;i<min((ll)a.size(), left);++i){
                if(a[i] < 0){
                    sum -= a[i];
                }else{
                    break;
                }
            }
            ans = max(ans, sum);
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3596
N = int(input())
c = [0]*8
d = 0
for ai in map(int,input().split()):
    if ai <400:
        c[0]=1
    elif 400<= ai <800:
        c[1]=1
    elif 800<= ai <1200:
        c[2]=1
    elif 1200<= ai <1600:
        c[3]=1
    elif 1600<= ai <2000:
        c[4]=1
    elif 2000<= ai <2400:
        c[5]=1
    elif 2400<= ai <2800:
        c[6]=1
    elif 2800<= ai <3200:
        c[7]=1
    elif 3200<= ai:
        d +=1

min_ans=0
for i in c:
    min_ans +=i

max_ans = min_ans + d

if min_ans == 0:
    min_ans = 1

print(min_ans,max_ans)


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

int main() {
    int H, W;
    cin >> H >> W;
    string dummy = "..................................................";
    string pre = dummy, now, next;
    cin >> now;
    for (int i = 0; i < H; i++) {
        if (i == H - 1) {
            next = dummy;
        }
        else cin >> next;
        
        for (int j = 0; j < W; j++) {
            if (now[j] == '#') {
                cout << "#";
                continue;
            }
            int ans = 0;
            if (j > 0 && pre[j - 1] == '#') ans++;
            if (pre[j] == '#') ans++;
            if (j < W - 1 && pre[j + 1] == '#') ans++;
            
            if (j > 0 && now[j - 1] == '#') ans++;
            if (j + 1 < W && now[j + 1] == '#') ans++;
            
            if (j > 0 && next[j - 1] == '#') ans++;
            if (next[j] == '#') ans++;
            if (j + 1 < W && next[j + 1] == '#') ans++;
            cout << ans;
        }
        cout << endl;
        
        pre = now;
        now = next;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
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; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    ll X; cin >> X;
    ll now = 100;
    int ans = 0;
    while(now < X) {
        ++ans;
        now = (double)now / 100 * 101;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
dreamer = "dreamer"
eraser = "eraser"
dream = "dream"
erase = "erase"


def main():
    S = input()

    while len(S):
        lens = len(S)
        if S[ - len(dreamer):] == dreamer:
            S = S[:- len(dreamer)]
        elif S[-len(eraser):] == eraser:
            S = S[:- len(eraser)]
        elif S[-len(dream):] == dream:
            S = S[:-len(dream)]
        elif S[-len(erase):] == erase:
            S = S[:-len(erase)]
        if lens == len(S):
            print("NO")
            return
    print("YES")
    return


main()


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

int main(){
    string s;
    cin >> s;
    long long ans=0;
    long long n=s.size();
    long long b=0;
    for(int i=0;i<n;i++){
        if(s[i]=='B') b++;
        else ans+=b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
n = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
r = 0
for i, j in factorization(n):
    f = 1
    if i==1:
        break
    while j >= f:
        r += 1
        j -= f
        f += 1
print(r)

Measured memory_bytes: 9476
#include <stdio.h>

int main()
{
    int i;
    int n;
    int min, max, input;
    max = -1000000000;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &input);
        
        if(i == 0)
        {
            min = input;
        }
        else
        {
            if(max < input - min)
            {
                max = input - min;
            }
            if(min > input)
            {
                min = input;
            }
        }
    }

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

    return 0;
}



Measured memory_bytes: 2112
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int dp[1000][1000];
int N;

inline int get(int r, int c) {
    if(r < 0 || r >= N || c < 0 || c >= N) return 0;
    return dp[r][c];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(cin >> N) {
        if(N == 0) break;
        for(int i = 0; i < N; ++i) {
            string line;
            cin >> line;
            for(int c = 0; c < N; ++c) {
                dp[i][c] = get(i-1, c) + get(i, c-1) - get(i-1, c-1);
                if(line[c] == '*') dp[i][c]++;
            }
        }
        int ans = 0;
        for(int r = 0; r < N; ++r) {
            for(int c = 0; c < N; ++c) {
                int left = 0, right = N+1;
                while(left < right-1) {
                    int size = (left+right)>>1;
                    const int er = r+size-1;
                    const int ec = c+size-1;
                    if(er >= N || ec >= N) {
                        right = size;
                    } else {
                        int marks = get(er, ec) - get(er, c-1) - get(r-1, ec) + get(r-1, c-1);
                        if(marks == 0) {
                            left = size;
                        } else {
                            right = size;
                        }
                    }
                }
                ans = max(ans, left);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	ll A, B, C, K;
	cin >> A >> B >> C >> K;
	if(K % 2) swap(A, B);

	cout << A - B << endl;
}


Measured memory_bytes: 768
#include<stdio.h>

int main(){
	
	int a, b, c, i, sum = 0;

	scanf("%d %d %d", &a, &b, &c);

	for(i = a; i <= b; i++){
		if(c % i == 0){
			sum++;
		}
	}

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

	return 0;
}

Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1||n==2){
        cout<<n;
    return 0;
    }
    int f;
    while(f=1)
    {
        f=0;
        for(int i=2;i<=n/2;i++)
        {
            if(n%i==0)
                f=1;
        }
        if(f==0) break;
        else n++;
    }
    cout<<n<<endl;
}


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

#define FOR(i, m, n) for(int (i) = (m); (i) < (n); (i)++)
#define FORN(i, m, n) for(int (i) = (m); (i) <= (n); (i)++)
#define FORR(i, m, n) for(int (i) = (m); (i) >= (n); (i)--)
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define repr(i, n) FORR(i, n, 0)
#define repnr(i, n) FORR(i, n, 1)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define setp(n) cout << fixed << setprecision(n);
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
typedef long long ll;
typedef pair<int, int> P;

const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;
const int MAX_N = 1e5;
int main(void){
	int n;
	cin >> n;

	vector<P> a(n);
	vector<P> b(n);
	rep(i, n) cin >> a[i].fs;
	rep(i, n) cin >> b[i].fs;
	rep(i, n) a[i].sc = b[i].sc = i;
	sort(all(a)); sort(all(b));

	rep(i, n) if(a[i].fs > b[i].fs) return puts("No"), 0;
	rep(i, n-1) if(a[i+1].fs <= b[i].fs) return puts("Yes"), 0;

	vector<int> cr(n);
	rep(i, n) cr[a[i].sc] = b[i].sc;
	int cnt = 0, x = 0;
	do{
		cnt++;
		x = cr[x];
	}while(x);
	puts(cnt == n ? "No" : "Yes");

	return 0;
}


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

using namespace std;

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const int tmax=11;
const int vmax=150;

int V,T;
int d[vmax][vmax];
int t[tmax];
int p[1<<tmax][vmax];


int minimum_steiner_tree(){
	if(T<=1)
		return 0;

	rep(k,vmax)rep(i,vmax)rep(j,vmax) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	rep(i,1<<tmax)rep(j,vmax) p[i][j]=inf;

	rep(i,T){
		rep(j,V) p[1<<i][j]=d[t[i]][j];
		rep(j,T) p[1<<i|1<<j][t[j]]=d[t[i]][t[j]];
	}

	for(int k=2;k<T;++k){
		for(int s=(1<<k)-1;(s<(1<<T));){
			rep(x,V){
				int ns=s;
				int cur=-1;
				rep(i,T) if(t[i]==x) cur=i;
				if(cur!=-1) ns|=(1<<cur);
				if(cur!=-1&&s==ns) continue;
				for(int u=(s-1)&s;u!=0;u=(u-1)&s){
					int c=(s&(~u));
					p[ns][x]=min(p[ns][x],p[u][x]+p[c][x]);
				}
			}
			int x=s&-s,y=s+x;
			s=((s&~y)/x>>1)|y;
		}
		for(int s=(1<<k)-1;(s<(1<<T));){
			rep(x,V){
				int ns=s;
				int next=-1;
				rep(i,T) if(t[i]==x) next=i;
				if(next!=-1) ns|=(1<<next);
				if(next!=-1&&s==ns) continue;
				rep(y,V) p[ns][x]=min(p[ns][x],p[s][y]+d[y][x]);
			}
			int x=s&-s,y=s+x;
			s=((s&~y)/x>>1)|y;
		}
	}

	const int mask=(1<<T)-1;
	int ans=p[mask][0];
	rep(i,vmax) ans=min(ans,p[mask][i]);
	return ans;
}

int main(void){
	int h,w;
	while(cin >> h >> w){
		if(h==0)
			break;
		rep(i,vmax)rep(j,vmax) d[i][j]=(i==j)?0:inf;
		V=h*w,T=0;

		rep(i,h*w){
			int in;
			cin >> in;
			if(in) t[T++]=i;
		}
		rep(i,h)rep(j,w){
			int cur=w*i+j;
			if(i+1<h) d[cur][cur+w]=d[cur+w][cur]=1;
			if(j+1<w) d[cur][cur+1]=d[cur+1][cur]=1;
		}
		int res=minimum_steiner_tree();
		cout << V-1-res << endl;
	}
	return 0;
}



// q[s|c][x]=min(q[s|c],p[s][x]+p[c][x]);

// p[s][x]=min(p[s][x],p[s][y]+d[y][x]) y&#8714;s
// p[s][x]=min(p[s][x],q[s][y]+d[y][x]) y&#8714;v/s

Measured memory_bytes: 2448
#include <stdio.h>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim() {
    int d[n], p[n];
    int color[n];
    
    for(int i=0; i<n; i++) {
        color[i] = WHITE;
        d[i] = INFTY;
        p[i] = -1;
    }
    
    d[0] = 0;
    
    while(1) {
        int u;
        int mincost = INFTY;
        for (int i=0; i<n; i++) {
            if (color[i] != BLACK && d[i] < mincost) {
                mincost = d[i];
                u = i;
            }
        }
        
        if (mincost == INFTY) break;
        
        color[u] = BLACK;
        
        for (int v=0; v<=n; v++) {
            if (color[v] != BLACK && M[u][v] != INFTY) {
                if(M[u][v] < d[v]) {
                    d[v] = M[u][v];
                    p[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    
    int sum = 0;
    for (int i=0; i<n; i++) {
        if(p[i] != -1) sum += M[p[i]][i];
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int tmp;
            scanf("%d", &tmp);
            M[i][j] = (tmp == -1) ? INFTY : tmp;
        }
    }
    
    int sum = prim();
    printf("%d\n", sum);
    
    return 0;
}


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

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            string szLine = Console.ReadLine();
            int n = int.Parse(szLine);

            if( n <= 999)
            {
                Console.WriteLine("ABC");
            }
            else
            {
                Console.WriteLine("ABD");
            }
        }
    }
}


Measured memory_bytes: 13140
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
#include<string>
#include<set>
#include<queue>
#include<deque>
#include<iomanip>
using namespace std;
#define Mohamed_Gad fast()
#define ll long long
#define ull unsigned long long
#define all(v) v.begin(),v.end()
#define endl "\n"
#define sz(x) size(x)
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
void Open()
{
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    //freopen("Output.txt", "w", stdout);
#endif

}
//long long frq[100009],prf[100009];

int main() {
    fast();
     int a,b,c;
     cin>>a>>b>>c;
     if((a==5&&b==5&&c==7)||(a==5&&b==7&&c==5)||(a==7&&b==5&&c==5))cout<<"YES"<<endl;
     else cout<<"NO"<<endl;


}


Measured memory_bytes: 256
N = int(raw_input())
A = list(map(int,raw_input().split()))
print ' '.join([str(a) for a in A])

for i in range(1, N):
  v = A[i]
  j = i - 1
  while j >= 0 and A[j] > v:
    A[j+1] = A[j]
    j-=1
  A[j+1] = v
  print ' '.join([str(a) for a in A])


Measured memory_bytes: 4648
#include <iostream>
using namespace std;
int main ()
{
    int a , b , c , k;
    cin>>a>>b>>c>>k;
    int mx = 0;
    int sum = a+b+c;
    
    if(a>=b && a>=c)
    {
        mx=a;
        sum-=a;
    }
    else if(b>=a && b>=c)
    {
        mx=b;
        sum-=b;
    }
    else if(c>=a && c>=b)
    {
        mx=c;
        sum-=c;
    }

    for(int i=0;i<k;++i)
        mx*=2;
        
    cout<<mx+sum<<endl;
    return 0;
}

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

#define taskname "CNT"
const int MOD =1e9+7;
typedef long long LL;

const int lim2=2e6+1;
LL fact[lim2], ifact[lim2];
void computeFactorials(int N);
LL powerMod(LL a, LL n, LL m);
LL combination(int N, int K);
LL countPath(int m, int n);

const int maxK=2e5;
LL F[maxK];

struct TPoint {
    int x,y;
    bool operator< (TPoint a) const {
        return (x+y)<(a.x+a.y);
    }
};
TPoint P[maxK];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N,M,K;
    cin >> N >> M >> K;
    computeFactorials(M+N);
    for (int i=1; i<=K; i++) cin >> P[i].x >> P[i].y;
    P[++K].x = N; P[K].y = M;
    //P[0].x = P[0].y = 1;
    sort(P+1,P+1+K);
    F[1] = countPath(P[1].x, P[1].y);
    for (int i=2; i<=K; i++) {
        F[i] = countPath(P[i].x, P[i].y);
        for (int j=1; j<i; j++) {
            if (P[j].x > P[i].x or P[j].y > P[i].y) continue;
            F[i] -= F[j]*countPath(P[i].x-P[j].x+1, P[i].y-P[j].y+1);
            F[i] %= MOD;
            if (F[i]<0) F[i]+=MOD;
        }
    }
    cout << F[K];
}

LL powerMod(LL a, LL n, LL m) {
    if (n==0) return 1;
    if (n==1) return (a%m);
    LL t=powerMod(a,n/2,m);
    t = (t*t)%m;
    if (n%2) t=(t*a)%m;
    return t;
}

void computeFactorials(int N) {
    fact[0]=1;
    for (int i=1; i<=N; i++) fact[i] = (i*fact[i-1])%MOD;
    ifact[N] = powerMod(fact[N], MOD-2, MOD);
    for (int i=N-1; i>=0; i--)
        ifact[i] = (ifact[i+1]*(i+1))%MOD;
}

LL combination(int N, int K) {
    return ( ((fact[N]*ifact[K])%MOD)*ifact[N-K] )%MOD;
}

LL countPath(int m, int n) {
    return combination(m+n-2,m-1);
}


Measured memory_bytes: 6716
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int X = Integer.parseInt(sc.next());
        int Y = Integer.parseInt(sc.next());
        int Z = Integer.parseInt(sc.next());
        
        int ans = 0;
        X -= Z;
        while(true){
            if(X < Y+Z){
                break;
            }
            X = X - (Y + Z);
            ans++;
        }
        
        System.out.println(ans);
        
    }
}

Measured memory_bytes: 25300
#include <stdio.h>
int main()
{
    long long int n,m;
    scanf("%lld %lld",&n,&m);
    if(n > m/2)
            printf("%lld\n",m/2);
    else
    {
        m = m + n*2;
        printf("%lld\n",m/4);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main () {
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a[n];
    ll i;
    for(i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    ll s=0;
    s+=a[n-1];
    ll j=n-2;
    ll k=0;
    //cout<<"Yo"<<endl;
    for(i=n-3;i>=0;i--)
    {
    //cout<<a[j]<<endl;
		s+=a[j];
    	k++;
    	if(k==2)
    	{
    		k=0;
    		j--;
		}
	}
	cout<<s<<endl;
	return 0;
}

    

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

int main(){
  
  string a,b;
  cin >> a >> b;
  string c=a+b;
  int n=stoi(c);
  for(int i=1; i<=1000; i++){
    if(i*i==n){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}
  

Measured memory_bytes: 256
x = gets.to_i

alf = []
ans = []

for i in "a".."z"
  alf.push(i)
end

loop {
  x = x - 1
  shou = x / 26
  amari = x % 26
  ans.push(alf[amari])
  x = shou
  if x == 0
    break
  end
}
  
puts ans.reverse.join



Measured memory_bytes: 14400
#include <stdio.h>

int main(void)
{
	int height[10];
	int i;
	int highest;
	int hikisu;
	int j;
	
	for(i=0;i<10;i++)
	{
		scanf("%d",&height[i]);
	}
	
	for(j=0;j<3;j++)
	{
	
		highest = -999;
		
		for(i=0;i<10;i++)
		{
			if(highest <= height[i])
			{
				highest = height[i];
				hikisu = i;
			}
		}
		
		printf("%d\n",highest);
		
		height[hikisu] = -1;
		
	}
	
	return 0;
}

Measured memory_bytes: 1860
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<"-1"<<endl;return 0;}
//template

//main
signed main(){
  int N,K;cin>>N>>K;
  if(K>(N-1)*(N-2)/2)fin;
  int ans=(N-1)*(N-2)/2-K;
  ans+=N-1;
  cout<<ans<<endl;
  for(int i=2;i<=N;i++,ans--)cout<<1<<" "<<i<<endl;
  std::vector<int> v(N);
  v[0]=v[1]=1;
  for(int i=2;i<=N;i++){
    for(int j=i+1;j<=N;j++){
      if(ans==0)break;
      cout<<i<<" "<<j<<endl;ans--;
    }
  }
}


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

int main(void) {
    long long N, a[100010];
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    int count = 0;
    long long m, ans = 0;
    bool zero = false;
    m         = abs(a[0]);
    for (int i = 0; i < N; ++i) {
        if (a[i] < 0) {
            ++count;
        } else if (a[i] == 0) {
            zero = true;
        }
        ans += abs(a[i]);
        m = min(abs(a[i]), m);
    }
    if (!zero && count % 2 != 0) {
        ans -= 2 * m;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

int N, M;
string s;

struct DirectedGraph
{
    int V; // 頂点数
    vector<vector<int> > to;
    vector<vector<int> > from;

    vector<bool> used;
    vector<int> vs;

    void dfs(int v)
    {
        used[v] = true;
        for (auto t : to[v]) if (!used[t]) dfs(t);
        vs.push_back(v);
    }
    void rdfs(int v, int k)
    {
        used[v] = true;
        cmp[v] = k;
        for (auto t : from[v]) if (!used[t]) rdfs(t, k);
    }

    vector<int> cmp;
    DirectedGraph(int V) : V(V),
                           to(vector<vector<int> >(V)), 
                           from(vector<vector<int> >(V)),
                           cmp(vector<int>(V))
                           {}
    void add_edge(int from_, int to_)
    {
        to[from_].push_back(to_);
        from[to_].push_back(from_);
    }

    int scc_num = -1;
    int scc()
    {
        used = vector<bool>(V, false);
        vs.clear();
        for (int v = 0; v < V; v++) if (!used[v]) dfs(v);

        used = vector<bool>(V, false);
        scc_num = 0;
        for (int i = vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) rdfs(vs[i], scc_num++);
        return scc_num;
    }
};


int main()
{
    cin >> N >> M >> s;
    DirectedGraph g(N * 2);

    REP(i, M)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (s[a] == s[b])
        {
            g.add_edge(a, b + N);
            g.add_edge(b, a + N);
        }
        else
        {
            g.add_edge(a + N, b);
            g.add_edge(b + N, a);
        }
    }

    cout << (N * 2 != g.scc() ? "Yes" : "No") << endl;
}


Measured memory_bytes: 39620
s = input()
ans_rev = ''
b = 0
for i in range(len(s)-1,-1,-1):
  if s[i] == 'B':
    b += 1
  else:
    if b > 0:
      b -= 1
    else:
      ans_rev += s[i]
for i in range(len(ans_rev)-1, -1,-1):
  print(ans_rev[i], end='')
print()

Measured memory_bytes: 38256
#include<stdio.h>

int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    if(a > b)
       printf("a > b\n");
    if(a < b)
       printf("a < b\n");
    if(a == b)
       printf("a == b\n");

    return 0;
}

Measured memory_bytes: 1748
from numpy import int64, count_nonzero

K, Q, *I = map(int, open(0).read().split())
D, NXM = int64(I[:K]), I[K:]

for n, x, m in zip(*[iter(NXM)] * 3):
    q, r = divmod(n - 1, K)
    T = D % m

    a = (K - count_nonzero(T)) * q + r - count_nonzero(T[:r])
    b = (x % m + T.sum() * q + T[:r].sum()) // m

    print(n - 1 - a - b)

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

import sys
input = sys.stdin.readline

def main():
  N, K = map(int, input().split())
  sushis = [tuple(map(int, input().split())) for _ in range(N)]
  sushis.sort(key=lambda x:x[1], reverse=True)
  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types_max = len(set([c[0] for c in sushis]))
  types = set()
  dups = []

  for c in curr:
    if c[0] in types:
      dups += [c]
    else:
      types.add(c[0])
  types = set(types)

  ps = base(curr) + len(types)**2
  di = {}
  di[len(types)] = ps
  n_types = len(types) + 1
  for l in leave:
    if len(types) >= types_max:
      break
    if len(dups) == 0:
      break
    if not l[0] in types:
      dup = dups.pop()
      di[n_types] = ps - dup[1] + l[1] + n_types**2 - (n_types-1)**2
      ps = di[n_types]
      n_types += 1
      types.add(l[0])

  print(sorted(di.items(), key=lambda x:x[1])[-1][1])


if __name__=='__main__':
  main()

Measured memory_bytes: 24836
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ull unsigned long long
#define ll long long
#define  PII pair<int,int>
using namespace std;
ull read() {
	char c = getchar();
	ull x = 0, f = 1;
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (; isdigit(c); c = getchar())
		x = x * 10 + c - 48;
	return x * f;
}
const int N = 1e5 + 5;
const ll cnt = 1e18;
ull n, a[N];
int main() {
	n = read();
	bool flag = 0;
	for (ull i = 1; i <= n; ++i) {
		a[i] = read();
		if (!a[i])
			flag = 1;
	}
	if (flag) {
		cout << 0 << endl;
		return 0;
	}
	ull res = 1, cntt = 0;
	for (ull i = 1; i <= n; ++i) {
		cntt = res;
		res *= a[i];
		if (res > cnt) {
			cout << -1 << endl;
			return 0;
		}
		if (cntt > res) {
			cout << -1 << endl;
			return 0;
		}
		if (res < a[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 4376
#include<bits/stdc++.h>
#define rep(i,n) for(long long int i=0;i<n;i++)
#define lli long long int
#define ll long long 
#define dd double
#define endl "\n"
#define mod 1000000007
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define limit 1000000000000000000
const double pi=3.14159265358;

using namespace std;

int main()
{
	fast
	lli x,y;
	cin>>x>>y;
	if(y>(x*4) || y<(x*2) || (y%2!=0))
	{
		cout<<"No"<<endl;
		
	}
	else cout<<"Yes"<<endl;
}

Measured memory_bytes: 3612
n=int(input())
A=sorted(list(map(int,input().split())))
L={}
if n==1:
        print(1)
elif n==2:
    if abs(A[0]-A[1])==1:
        print(2)
    else:
        print(1)
else:
    for i in A:
        if i not in L:
            L[i]=1
        else:
            L[i]+=1
    ans=[]
    for j in range(A[0],A[-1]+1):
        if (j in L) and (j-1 in L) and (j+1 in L):
            ans.append(L[j]+L[j+1]+L[j-1])
        elif (j in L) and (j-1 in L):
            ans.append(L[j-1]+L[j])
        elif (j in L) and (j+1 in L):
            ans.append(L[j+1]+L[j])
        elif (j-1 in L) and (j+1 in L):
            ans.append(L[j+1]+L[j-1])
        elif (j in L):
            ans.append(L[j])
    print(max(ans))

Measured memory_bytes: 14164
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n;
int d[N], ans;
vector<int> v[N];
vector<P> edges;
map<P, int> fast;

void dfs(int s, int p, int col){
   col++;
   col %= ans;

   for(auto i: v[s]){
      if(i != p){
         fast[{i, s}] = col;
         fast[{s, i}] = col;
         col++;
         col%= ans;
      }
   }

   for(auto i: v[s]){
      if(i == p)continue;
      dfs(i, s, fast[{i, s}] % ans);
   }
}

int32_t main(){_

   cin>>n;  

   ans = 0;
   for (int i = 0; i < n-1; ++i)
   {
      int x, y;
      cin >> x >> y;
      d[x]++;
      d[y]++;
      edges.push_back({x, y});
      smax(ans, d[x]);
      smax(ans, d[y]);
      v[x].push_back(y);
      v[y].push_back(x);
   }

   dfs(1, -1, -1);

   cout<<ans<<endl;
   
   for(auto it: edges){
      int x = it.F, y = it.S;
      cout<<fast[{x, y}]+1<<endl;
   }

   return 0;
}

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

using namespace std;
    vector<int> sol;
     map<int,int> mp;
     set<int> v1;
     set<int>::iterator it;

int main()
{
    int n,k;
    cin>>n>>k;
    
for(int i=0;i<n;i++)
{
    
    int x;
    cin>>x;
    
    v1.insert(x);
    mp[x]++;
    
}
    
    
for(it=v1.begin();it!=v1.end();it++)
{
    
    sol.push_back(mp[*it]);
}
sort(sol.begin(),sol.end());
int r = max(0,(int)v1.size()-k);
int ans=0;
for(int i=0;i<r;i++)
{
    ans+=sol[i];
    
}
cout<<ans;
    
    
    
    
    
    
}

Measured memory_bytes: 20092
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int n;
string a,s[11];
priority_queue<pair<int,string> >  que;
vector<pair<int,string> > b;
int main(void){
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a;
    que.push(make_pair(a.size(),a));
    if(que.size() > 10) que.pop();
  }
  for(int i = 0; i < min(n,10); i++){
    s[i] = que.top().second;
    que.pop();
  }
  for(int i = 0; i < min(n,10); i++){
    for(int j = 0; j < min(n,10); j++){
      if(i == j) continue;
      b.push_back(make_pair((s[i]+s[j]).size(),s[i]+s[j]));
    }
  }
  sort(b.begin(),b.end());
  cout << b[2].second << endl;
}

Measured memory_bytes: 1220
#include <stdio.h>
#define max(a, b) ((a)>(b) ? (a) : (b))

int main(){
  int n;
  int happiness[100001][3];
  scanf("%d", &n);
  for(int i=0; i<n; i++) for(int j=0; j<3; j++) scanf("%d", &happiness[i][j]);

  int dp[100002][3] = {0};
  
  for(int i=0; i<n; i++){
    for(int j=0; j<3; j++){
      for(int k=0; k<3; k++){
	if(j == k) continue;
	dp[i+1][j] = max(dp[i+1][j], dp[i][k]+happiness[i][j]);
      }
    }
  }

  printf("%d\n", max(dp[n][0], max(dp[n][1], dp[n][2])));
  
  return 0;
}


Measured memory_bytes: 2560
import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Maybe as Maybe
import qualified Text.Printf as Printf
import qualified Control.Monad as Monad
import qualified Data.Array as Array

bit :: Int -> [Int]
bit e = reverse $ bit' e
    where
    bit' 0 = []
    bit' x = (x `mod` 2) : bit' (x `div` 2)

modExp :: Int -> Int -> Int -> Int
modExp x e m = List.foldl' func 1 $ bit e
    where
    func n 0 = n^2 `mod` m
    func n 1 = n^2 `mod` m * x `mod` m

modNum :: Int
modNum = 1000000007

solve :: Int -> [Int] -> Int
solve n xs = if n `mod` 2 == 0 then
               solve' n 0 1 xs
             else
               solve' n 0 2 (tail xs)

solve' :: Int -> Int -> Int -> [Int] -> Int
solve' n _ _ [] = modExp 2 (n `div` 2) modNum
solve' n i c (x:xs) = if c == x then
                        if i `mod` 2 == 0 then
                          solve' n (i+1) c xs
                        else
                          solve' n (i+1) (c+2) xs
                      else
                        0

main :: IO ()
main = getContents >>=
  print .
  (\ (n,as) -> solve n as) .
  (\ [n,as] -> ((read :: String -> Int) n, List.sort . map (read :: String -> Int) . words $ as)) .
  lines

Measured memory_bytes: 28028
k,x=map(int,input().split())

l=0
r=0

if x-(k-1)<-1000000:
  l=-1000000

if x-(k-1)>=-1000000:
  l=x-(k-1)

if x+(k-1)>1000000:
  r=1000000

if x+(k-1)<=1000000:
  r=x+(k-1)

ans=list(range(l,r+1))
s=' '.join([str(n) for n in ans])
print(s)

Measured memory_bytes: 9196
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type Abbreviation ---------- */
using ll = long long;

/* ---------- Constants ---------- */
const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */
template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

int main() {
    int N, C;
    cin >> N >> C;

    int D[C][C];
    for (int i = 0; i < C; i++) {
        for (int j = 0; j < C; j++) {
            int c;
            cin >> c;
            D[i][j] = c;
        }
    }

    int group0[C];
    int group1[C];
    int group2[C];
    fill(group0, group0 + C, 0);
    fill(group1, group1 + C, 0);
    fill(group2, group2 + C, 0);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int c;
            cin >> c;
            c--;

            if ((i+j) % 3 == 0) {
                group0[c]++;
            } else if ((i+j) % 3 == 1) {
                group1[c]++;
            } else {
                group2[c]++;
            }

        }
    }

    ll ret = INF;

    for (int i = 0; i < C; i++) {
        for (int j = 0; j < C; j++) {
            for (int k = 0; k < C; k++) {
                if (i == j || j == k || k == i) continue;
                ll sum = 0;

                for (int p = 0; p < C; p++) {
                    sum += group0[p] * D[p][i];
                    sum += group1[p] * D[p][j];
                    sum += group2[p] * D[p][k];
                }

                ret = min(ret, sum);
            }
        }
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    vector<int> Nums;
    int flag = 1;
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == (char)('0' + flag))
        {
            cnt++;
        }
        else
        {
            Nums.push_back(cnt);
            cnt = 1;
            flag = 1 - flag;
        }
    }
    if (cnt != 0)
    {
        Nums.push_back(cnt);
    }
    // 配列のサイズが偶数じゃなかった場合、端っこの処理がめんどくさい
    // 端っこに一個足すと良い
    if (Nums.size() % 2 == 0)
    {
        Nums.push_back(0);
    }
    // cout << "complete" << endl;
    // Kの値に応じてどこまで見れるか
    // K=0だったら1、K=1だったら3、etc
    // for (int i = 0; i < Nums.size(); i++)
    // {
    //     cout << i << "th:" << Nums[i] << endl;
    // }
    int RANGE = 2 * K + 1;
    int ans = 0;
    for (int i = 0; i < Nums.size(); i += 2)
    {
        int tmp = 0;
        int left = i;
        int right = min((int)Nums.size(), i + RANGE);
        for (int j = left; j < right; j++)
        {
            tmp += Nums[j];
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;
const ll mod = 1e9 + 7;

ll memo[100010];

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    ll res = 0;
    for(ll i = k; i >= 1; --i){
        ll tmp = modpow(k / i, n, mod);
        for(ll j = 2 * i; j <= k; j += i){
            tmp -= memo[j];
            tmp %= mod;
        }
        memo[i] = tmp;
        res += (i * tmp) % mod;
        res %= mod;
    }
    res += mod;
    res %= mod;
    cout << res << endl;
}

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

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define FILE "file"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int INF = numeric_limits<int>::max();
const ll LLINF = numeric_limits<ll>::max();
const ull ULLINF = numeric_limits<ull>::max();
const double PI = acos(-1.0);

long long fac[200010];
long long inv[200010];
long long p2[200010];

long long mod = 1e9 + 7;

long long sqr(long long a)
{
    return a * a % mod;
}

long long binpow(long long a, long long n)
{
    if(n == 0)
        return 1;
    if(n & 1)
        return binpow(a, n - 1) * a % mod;
    return sqr(binpow(a, n >> 1));
}

int cnt[100010];

long long c(long long n, long long k)
{
    if(n < k)
        return 0;
    if(n == k)
        return 1;
    return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int main()
{
//    freopen(FILE".in", "r", stdin);
//    freopen(FILE".out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    fac[0] = fac[1] = inv[0] = inv[1] = 1;
    p2[0] = 1;
    p2[1] = 2;
    for(int i = 2; i <= 200000; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = binpow(fac[i], mod - 2);
        p2[i] = p2[i - 1] * 2LL % mod;
    }
    long long n;
    cin >> n;
    int pos1, pos2;
    for(int i = 1; i <= n + 1; i++)
    {
        int a;
        cin >> a;
        if(cnt[a] != 0)
        {
            pos1 = cnt[a];
            pos2 = i;
        }
        cnt[a] = i;
    }
    for(int k = 1; k <= n + 1; k++)
        cout << (c(n + 1, k) - c(n + pos1 - pos2, k - 1) + mod) % mod << '\n';
    return 0;
}


Measured memory_bytes: 6272
n, k = input().split()
h_list = list(map(int, input().split()))

cost_list = [0] * len(h_list)

for i in range(1, int(n)):
    cost_min = 9999999999999999
    for j in range(int(k)):
        if i-j-1 < 0:
            continue
        cost = cost_list[i-j-1] + abs(h_list[i] - h_list[i-j-1])
        if cost < cost_min:
            cost_min = cost
    cost_list[i] = cost_min

print(cost_list[-1])


Measured memory_bytes: 52448