akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
typedef long long ll;
typedef long double ld;
#define trace(x)  cerr << #x << ": " << x << endl;
const ll N=1e5+5;
int main()
{
	fast;ll n;cin>>n;ll a[n];map<ll,ll> mp;ll sum=0;
	for(ll i=0;i<n;i++)
	{
		cin>>a[i];mp[a[i]]++;sum+=a[i];
	}
	ll q;cin>>q;
	while(q--)
	{
		ll b,c;cin>>b>>c;
		sum-=(mp[b]*b);sum+=(mp[b]*c);mp[c]+=mp[b];mp[b]=0;
		cout<<sum<<"\n";
	}
}

Measured memory_bytes: 10288
import sys
input = sys.stdin.readline
INF = 2**31 - 1

class LazySegmentTree:
    def __init__(self, n):
        LV = (n-1).bit_length()
        self.N0 = 2 ** LV
        self.data = [INF] * (2*self.N0)
        self.lazy = [None] * (2*self.N0)
        
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
    
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            
            L >>= 1; R >>= 1
        
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            
            if v is None:
                continue
            
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        L = self.N0 + l; R = self.N0 + r
        
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
                
            L >>= 1; R >>= 1
            
        for i in ids:
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = INF
        
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
                
            L >>= 1; R >>= 1
            
        return s

n, q = map(int, input().split())
lst = LazySegmentTree(n)

for _ in range(q):
    que = list(map(int, input().split()))
    
    if que[0] == 0:
        s, t, x = que[1], que[2], que[3]
        lst.update(s, t+1, x)
    elif que[0] == 1:
        s, t = que[1], que[2]
        print(lst.query(s, t+1))


Measured memory_bytes: 12432
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
int ans, n;
string t;
int to_int(char ch) { return ch - '0'; }
void dfs(int pos, int cnt, string s)
{
    if(pos >= n)
    {
        ans = min(ans, cnt);
        return;
    }
    if(s[pos] == t[pos])
    {
        dfs(pos + 1, cnt, s);
        return;
    }
    int d = (to_int(t[pos]) - to_int(s[pos]) + 10) % 10;
    for(int i = pos; i < n; i++)
    {
        s[i] = '0' + (to_int(s[i]) + d) % 10;
        dfs(pos + 1, cnt + 1, s);
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n, n)
    {
        ans = INF;
        string s; cin >> s >> t;
        dfs(0, 0, s);
        cout << ans << endl;
    }
    return 0;
}




Measured memory_bytes: 3108
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m = map(int, input().split())
s = []
p = []
k = []
for i in range(m):
    s.append(list(map(int, input().split())))
    s[i].pop(0)
p = list(map(int, input().split()))

#print()
ans = 0
for i in range(2**n):
    on = []
    for j in range(n):
        if ((i>>j) & 1):
            on.append(j)
    #print('on:', on)
    allon = True
    for j in range(m):
        sumv = 0
        for x in s[j]:
            if (x - 1) in on:
                sumv += 1
        #print(j,':', sumv)
        if sumv%2 != p[j]:
            allon = False
            break
    if allon:
        ans += 1
#print()
print(ans)

Measured memory_bytes: 5076
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := nextInt()
	M := nextInt()

	c := 0

	for i := 0; i < M; i++ {
		c += nextInt()
	}

	if c <= N {
		fmt.Println(N - c)
	} else {
		fmt.Println(-1)
	}
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 1880
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

	final static int SIZE = 8;
	final static int MARGIN = 3;
	final static char BOMB = 1;
	final static char BOMBED = 0;
	static Deque<int[]> bombs;
	static byte[][] map;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null) {

			int n = Integer.parseInt(line);

			br.readLine();// 空行スキップ
			for (int i = 0; i < n; ++i) {
				bombs = new ArrayDeque<int[]>();
				map = new byte[SIZE + MARGIN * 2][SIZE + MARGIN * 2];

				for (int j = MARGIN; j < SIZE + MARGIN; ++j) {
					line = br.readLine();
					for (int k = MARGIN; k < SIZE + MARGIN; ++k) {
						map[j][k] = (byte) (line.charAt(k - MARGIN) - '0');
					}
				}

				int x = Integer.parseInt(br.readLine());
				int y = Integer.parseInt(br.readLine());
				x += MARGIN - 1;
				y += MARGIN - 1;

				bombs.offer(new int[] { y, x });
				map[y][x] = BOMBED;
				while (!bombs.isEmpty()) {
					bomb();
				}
				System.out.print(print(i + 1, map));
				br.readLine();// 空行スキップ
			}
		}
	}

	static void bomb() {

		final int[] V = { 1, -1, 0, 0 };
		final int[] H = { 0, 0, 1, -1 };

		int[] yx = bombs.poll();
		int y = yx[0];
		int x = yx[1];

		// map[y][x] = BOMBED;

		for (int i = 0; i < 4; ++i) {
			for (int j = 1; j <= 3; ++j) {
				int yv = y + V[i] * j;
				int xh = x + H[i] * j;
				if (map[yv][xh] == BOMB) {
					bombs.offer(new int[] { yv, xh });
					map[yv][xh] = BOMBED;
				}
			}
		}
	}

	static String print(int n, byte[][] map) {

		StringBuilder sb = new StringBuilder();
		sb.append("Data " + n + ":\n");
		for (int i = MARGIN; i < SIZE + MARGIN; ++i) {
			for (int j = MARGIN; j < SIZE + MARGIN; ++j) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		return sb.toString();
	}

}

Measured memory_bytes: 16880
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;
const double PI = acos(-1);

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

	queue<int> q;
	for (int i = 0; i < k; i++) q.push(a[i]);

	for (int i = k; i < n; i++) {
		if (q.front() < a[i]) cout << "Yes" << endl;
		else cout << "No" << endl;
		q.pop();
		q.push(a[i]);
	}
}


Measured memory_bytes: 4780
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define frr(j,i,n) for(int i=j;i<=n;++i)
using namespace std;
char grid[1001][1001];
ll dp[1001][1001];
int r,c;
ll go(int r,int c)
{
    if(r==1 and c==1)
        return 1;

    if(dp[r][c]!=-1)
        return dp[r][c];
    ll x=0,y=0;
    if(r-1>0 and grid[r-1][c]=='.')
        x=go(r-1,c);
    if(c-1>0 and grid[r][c-1]=='.')
        y=go(r,c-1);

    return dp[r][c]= (x+y)%mod;




}
void solve()
{
    memset(dp,-1,sizeof(dp));
    cin>>r>>c;
    frr(1,i,r)
    {
        frr(1,j,c)
            cin>>grid[i][j];
    }
    cout<<go(r,c)<<"\n";

	

}
int main() 
{
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt","r",stdin);
	// 	freopen("output.txt","w",stdout);
	// #endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t=1;
	// cin>>t;
	while(t--)
	solve();
	return 0;
}



Measured memory_bytes: 12532
import java.util.*;
import java.lang.*;
 
class Main{
	public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    char line = sc.next().toCharArray()[0];
    if(Character.isLowerCase(line)){
    	System.out.println("a");
    	}
      else {
      	System.out.println("A");
      }
    }
}

Measured memory_bytes: 35604
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
    #define ll long long int
    #pragma GCC optimize("O3")
    #pragma GCC optimize("Ofast")
    #define all(a) (a).begin(), (a).end()
    #define sz size
    #define f first
    #define s second
    #define pb push_back
    #define er erase
    #define in insert
    #define mp make_pair
    #define pi pair
    #define rc(s) return cout<<s,0
    #define mod 1000000007
    #define PI 3.14159265359
    #define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
    using namespace std;
    ll n,ans=1e12;
    vector<ll>v;
    int32_t main(){
    CODE_START;
    cin>>n;
    for(ll i=1;i<=sqrt(n);i++)
    if(n%i==0){
        v.pb(i);
    }
    for(ll i=0;i<v.size();i++)
    ans=min(ans,v[i]+n/v[i]);
    cout<<ans-2<<endl;
    }
   


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

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

const int MAX = 510000;
const int MOD = 1000000007;

int64_t fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(){
    int64_t x,k,d ;
    cin >> x >> k >> d ;

    x = abs(x) ;
    if (x/d > k)
    {
        cout << (x - d*k) << endl ;
        return 0 ;
    }
    k -= x/d ;
    x %= d ;
    if (k % 2 == 0)
    {
        cout << x << endl ;
    }else
    {
        cout << abs(x-d) << endl ;
    }
    
    
    
}

Measured memory_bytes: 3620
import java.util.*;
class Main
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int d = scan.nextInt();
        boolean flag = false;

        if(Math.abs(a - c) <= d) flag = true;
        if(Math.abs(a - b) <= d && Math.abs(b - c) <= d) flag = true;

        out(flag);
        scan.close();
    }

    public static void out(boolean flag)
    {
        if(flag) System.out.print("Yes");
        else System.out.println("No");
    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
int main(void){
    long long n,m;
    cin>>n>>m;
    vector<long long> x(n,0);
    long long Num;
    long long ac=0,wa=0;
    string res;
    vector<long long> tmp(n,0);
    rep(i,m){
        cin>>Num>>res;
        if(res=="WA"&&x[Num-1]==0){
            tmp[Num-1]++;
        }
        if(res=="AC"&&x[Num-1]==0){
            ac++;
            wa+=tmp[Num-1];
            x[Num-1] = 1;
        }
    }
    cout<<ac<<" "<<wa<<endl;
}


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

void main_()
{
    ll N;
    cin >> N;
    vector<ll> As;
    As.reserve(N);
    copy_n(istream_iterator<ll>(cin), N, back_inserter(As));

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        auto self_pair = As[i] / 2;
        ans += self_pair;
        As[i] -= self_pair * 2;
        if (i < N - 1 && As[i] == 1 && As[i + 1] > 0) {
            As[i]--;
            As[i + 1]--;
            ans++;
        }
    }
    cout << ans << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 1024
#! usr/bin/env python
# -*- coding: utf-8 -*-

MAX_N = 10005
MAX_M = 11
dp = [[-1 for j in range(MAX_N)] for i in range(MAX_M)]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp[0][0] = 0
    for i in range(M):
        for j in range(N+1):
            if j < f[A[i]]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-f[A[i]]]+1)

    ans = []
    cj = N
    for i in range(M, 0, -1):
        for j in range(cj//f[A[i-1]], -1, -1):
            x = dp[i-1][cj-f[A[i-1]]*j]
            y = dp[i][cj]
            if dp[i-1][cj-f[A[i-1]]*j] == dp[i][cj] - j:
                for k in range(j):
                    ans.append(str(A[i-1]))
                cj -= f[A[i-1]] * j
                break

    print("".join(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 41200
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <map>
using namespace std;

#define prec(i) cout << fixed << setprecision(i)

void outPut_YN(bool isYes) {
	if (isYes)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

const long long MOD = 1000000007;

long long fact(long long k) {
	long long sum = 1;
	for (long long i = 2; i <= k; i++)
		sum *= i;

	return sum;
}

long long fact_mod(long long k) {
	long long sum = 1;
	for (long long i = 2; i <= k; i++)
		sum = (sum * i) % MOD;

	return sum;
}

int ctoi(char c) {
	if (c >= '0' && c <= '9')
		return c - '0';
	else
		return -1;
}

long long pow_mod(int a, int b) {
	long long ans = 1;
	for (int i = 0; i < b; i++)
		ans = (ans * a) % MOD;

	return ans;
}

long long powll(long long a, long long  b) {
	long long ans = 1;
	for (long long i = 0; i < b; i++)
		ans = ans * a;

	return ans;
}

long long modinv(long long a) {

	long long b = MOD, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= MOD;
	if (u < 0) u += MOD;

	return u;
}

long long _gcd(long long a, long long b)
{
	if (a < b)
		swap(a, b);

	if (a % b == 0)
		return b;
	else
		return _gcd(b, a % b);
}

long long _lcm(long long a, long long b)
{
	return (((a * b) % MOD) * modinv(_gcd(a, b))) % MOD;
}

long long ncr(long long n, long long r) {
	long long sum = 1;
	for (long long i = r + 1; i <= n; i++)
		sum *= i;

	return sum;
}

int main()
{
	long long n, cnt = 0, pt = 0;
	string s;

	cin >> s;

	if (s.length() % 2 != 0) {
		outPut_YN(false);
		return 0;
	}
		
	for (int i = 0; i < s.length(); i += 2) {
		if (s[i] != 'h' || s[i + 1] != 'i') {
			outPut_YN(false);
			return 0;
		}

	}

	outPut_YN(true);

	return 0;
}

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

int main(void){
    int N,M; cin >> N >> M;
    vector<string> A(N);
    vector<string> B(M);

    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<M; i++) cin >> B[i];

    for(int i=0; i<N-M+1; i++){
        for(int j=0; j<N-M+1; j++){
            bool match=true;
            for(int k=0; k<M; k++){
                for(int l=0; l<M; l++){
                    if(A[i+k][j+l]!=B[k][l]) match=false;
                }
            }
            if(match){
                cout << "Yes" << endl;
                return 0;
            }

        }
    }

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

Measured memory_bytes: 256
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
input=sys.stdin.readline
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n
        self.n = n
        #self.ps=set(range(n)) #not tested
    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def same(self,x,y):
        return self.root(x) == self.root(y)

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            #self.ps.discard(y)##親の集合からyを取り除く
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        for x in range(self.n):
            self.root(x)
        s = set()
        for par in self.par:
            s.add(par)
        return s

"""
edges :: [(cost,u,v) for every Edge]
"""
def Kruskal(edges,n):
    tot=0
    edges.sort()
    uf = unionfind(n)
    for cost,u,v in edges:
        if uf.same(u,v):
            pass
        else:
            uf.unite(u,v)
            tot+=cost
    return tot

xy=[]
n = ni()
for i in range(n):
    x,y=lma()
    xy.append((i,x,y))
xy.sort(key=lambda x:x[1])
#print(xy)
ed=[]
INF=10**15
ip=INF
xp=INF
yp=INF
for i,x,y in xy:
    if ip!=INF:
        ed.append((x-xp,i,ip))
    ip=i;xp=x;yp=y

xy.sort(key=lambda x:x[2])
#print(xy)
ip=INF
xp=INF
yp=INF
for i,x,y in xy:
    if ip!=INF:
        ed.append((y-yp,i,ip))
    ip=i;xp=x;yp=y
#print(ed)
print(Kruskal(ed,n))


Measured memory_bytes: 122548
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n,a,b,cal,ans=0,tcal[101],Scal,sum;
	double pcal[101],scal;
	cin>>n>>a>>b>>cal;
	for(int i=0;i<n;i++){
		cin>>tcal[i];
		pcal[i]=tcal[i]/b*1.0;
	}
	sort(tcal,tcal+n,greater<int>());
	for(int i=0;i<n;i++){
		scal=cal;
		sum=a;
		for(int j=0;j<i;j++){
			scal+=tcal[j];
			sum+=b;
		}
		Scal=scal/sum;
		ans=max(ans,Scal);
	}
	cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int read()
{
    char c=getchar();int f=1,sum=0;
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){sum=sum*10+c-'0';c=getchar();}
    return sum*f;
}
int n,x;LL sum;
bitset<2005*2005> dp;
int main()
{
    n=read();dp[0]=1;
	for(int i=1;i<=n;i++)x=read(),dp|=dp<<x,sum+=x;
    for(int i=sum+1>>1;i<=sum;i++)
    if(dp[i]) return !printf("%d\n",i);
}

Measured memory_bytes: 1792
import sys
from itertools import starmap
readline = sys.stdin.readline
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
def cross(a, b):
    return a.real * b.imag - a.imag * b.real
def dot(a, b):
    return a.real * b.real + a.imag * b.imag
def norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
s = Segment(*starmap(complex, zip(*[map(int, readline().split())] * 2)))
n = int(readline())
for _ in [0] * n:
    p2 = complex(*map(float, readline().split()))
    ap = project(s, p2)
    print(ap.real, ap.imag)

Measured memory_bytes: 7944
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
#MOD = 10**9+7
MOD = 10**9+7
import math
N,K = map(int,input().split())
ans = [0]*K
for i in range(K):
    p = K-i
    a = pow(math.floor(K/p),N,MOD)
    x = 1
    while p*(x+1) <= K:
        a -= ans[p*(x+1)-1]
        x = x+1
    ans[p-1] = a%MOD
s = 0
for i in range(K):
    s += (i+1)*ans[i]
    s = s%MOD
print(s)

Measured memory_bytes: 11288
/**
    @Author:Monk78
    @Topic:H-Grid1
**/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll>Vl;
typedef pair<ll,ll>PII;
typedef vector<PII>Vll;
typedef vector<pair<ll,pair<ll,ll> > >Vlll;
typedef priority_queue<ll>PQL;
typedef map<ll,ll>MP;
#define S second;
#define F first;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end));i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back

#define MAX 100005
#define f(i,a,b) for(int i=(a);i<(b);i++)
#define rf(i,a,b) for(int i=(a);i>=b;i--)
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define vpshVar() int main()
const ll mod=1e9+7;
vpshVar(){
    ll H,W;
    sl(H);sl(W);
    char str[H][W];
    for(ll i=0;i<H;i++){
     for(ll j=0;j<W;j++){
        cin>>str[i][j];
     }
    }
    ll dp[H+1][W+1];
    dp[0][0]=0;
    bool check=true;
    for(ll i=0;i<W;i++){
        if(str[0][i]=='.'&& check)
        {
            dp[0][i]=1;
        }
        else {
                dp[0][i]=0;
            check=false;
        }
    }
    check=true;
    for(ll i=0;i<H;i++){
        if(str[i][0]=='.' && check)dp[i][0]=1;
        else {
                dp[i][0]=0;
            check=false;
        }
    }

    for(ll i=1;i<H;i++){
        for(ll j=1;j<W;j++){
                if(str[i][j]=='.')
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];

                else dp[i][j]=0;
                dp[i][j]=(dp[i][j] % mod);
            }
        }
    pl(dp[H-1][W-1]%mod)
;
return 0;
}


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

int main(){
  int N;
  string S;

  cin >> N >> S;
  
  rep(i, S.length()){
    int ans = S.at(i) - 'A';
    ans = (ans + N) % 26;

    putchar('A'+ ans);
  }
  cout << endl;
} 

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

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

    vector<int> vec(n);

    rep(i, n) {
        cin >> vec.at(i);
        vec.at(i)--;
    }
     
    int ans = 0;
    int next = 0;
    while (ans < n ) {
        ans++;
        next = vec.at(next);
        if (next == 1) break;
        // cout << next << " " << ans << endl;

    }

    if (ans == n && next != 1) {
        ans = -1;
    }

    cout << ans << endl;

}

Measured memory_bytes: 640
def readinput():
    n,k=map(int,input().split())
    return n,k

def main(n,k):
    ans=0
    for i in range(1,n+1):
        p=1/n
        point=i
        while(point<k):
            point*=2
            p/=2
        #print(p)
        ans+=p
    return ans

if __name__=='__main__':
    n,k=readinput()
    ans=main(n,k)
    print(ans)


Measured memory_bytes: 9048
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = 2e9;
const int MAX_N = 200000;
const int MAX_M = 200000;

int N = 3, ans = 0;
vi a(N);

int main() {
  // cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  if (((a[1]-a[0])&1) == 0) {
    ans = (a[1]-a[0])/2 + a[2]-a[1];
  } else {
    a[0]++; a[2]++;
    ans = (a[1]-a[0])/2 + a[2]-a[1] + 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
 /*   double t,x;
    cin>>t>>x;
    t=t/x;
    cout<<t*1.0<<'\n';*/
  
   /* int a,b,c;
    cin>>a>>b>>c;
    cout<<(a*b)/2<<'\n';*/

   /* int d;
    cin>>d;
    if(d==22){
        cout<<"Christmas Eve Eve Eve"<<'\n';
    }else if(d==23){
        cout<<"Christmas Eve Eve"<<'\n';
    }else if(d==24){
        cout<<"Christmas Eve"<<'\n';
    }else if(d==25){
        cout<<"Christmas"<<'\n';
    }*/

   /* int x,y;
    cin>>x>>y;
    y=y/2;
    cout<<x+y<<'\n';*/

   /* int n,a,b;
    cin>>n;
    if(n==1){
        cout<<"Hello World"<<'\n';
    }else{
        cin>>a>>b;
        cout<<a+b<<'\n';
    }*/

   /* int n;
    cin>>n;
    if(n==111){
        cout<<999<<'\n';
    }else if(n==119){
        cout<<991<<'\n';
    }else if(n==199){
        cout<<911<<'\n';
    }else if(n==191){
        cout<<919<<'\n';
    }else if(n==999){
        cout<<111<<'\n';
    }else if(n==911){
        cout<<199<<'\n';
    }else if(n==919){
        cout<<191<<'\n';
    }else if(n==991){
        cout<<119<<'\n';
    }*/

  /*  int a[5];
    for(int i=0; i<3; i++){
        cin>>a[i];
    }
    sort(a,a+3,greater<int>());
    a[0]=a[0]*10;
    a[0]=a[0]+a[1]+a[2];
    cout<<a[0]<<'\n';*/

  /*  int a,b;
    cin>>a>>b;
    a=a*b;
    if(a%2==0){
        cout<<"No"<<'\n';
    }else{
        cout<<"Yes"<<'\n';
    }*/

  /*int a,b;
    cin>>a;
    b=a/2;
    if(a%2==0){
        cout<<b*b<<'\n';
    }else{
        cout<<b*(b+1)<<'\n';
    }*/

    int n,i;
    cin>>n>>i;
    cout<<n-i+1<<'\n';
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int a, b, c, x, y; cin >> a >> b >> c >> x >> y;
	ll ans = inf;
	rep(i, max(x, y) + 1){
		ll cost = 2 * i * c + a * max(0, x - i) + b * max(0, y - i);
		ans = min(ans, cost);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	static final long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] T = new int[N];
		int[] A = new int[N];
		
		for(int i=0; i<N; i++)
			T[i] = sc.nextInt();
		for(int i=0; i<N; i++)
			A[i] = sc.nextInt();
		
		long ans = 1;
		int idx = 0;
		for(; idx<N; idx++) {
			if(idx>0 && T[idx-1]==T[idx])
				ans = (ans * T[idx])%MOD;
			if(T[idx]==T[N-1])
				break;
		}
		
		if(T[idx]!=A[idx] || A[idx]!=A[0]) {
			System.out.println(0);
			sc.close();
			return;
		}
		idx++;
		
		for(; idx<N; idx++) {
			if(idx<N-1 && A[idx]==A[idx+1])
				ans = (ans * A[idx])%MOD;
		}
		
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 75248
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18
// cout << fixed << setprecision(10);

int main() {
    uint N, M;
    llong K;
    cin >> N >> M >> K;
    vector<int> A(N, 0);
    vector<int> B(M, 0);
    for (auto &a: A) cin >> a;
    for (auto &b: B) cin >> b;

    uint numAmax = N;
    vector<llong> SumA(N+1, 0);
    bool setnum = false;
    for (uint i=1; i<SumA.size(); i++) {
        SumA[i] = SumA[i-1] + static_cast<llong>(A[i-1]);
        if (!setnum) {
            if (SumA[i] == K) {
                numAmax = i;
                setnum = true;
            }
            else if (SumA[i] > K) {
                numAmax = i - 1;
                setnum = true;
            }
        }
    }

    vector<llong> SumB(M+1, 0);
    for (uint i=1; i<SumB.size(); i++) {
        SumB[i] = SumB[i-1] + static_cast<llong>(B[i-1]);
    }

    vector<uint> numRead(numAmax + 1);
    uint numReadMax = 0;
    auto begin = SumB.cbegin();
    auto end = SumB.cend();

    for (uint numA=0; numA<=numAmax; numA++) {
        llong K2 = K - SumA[numA];
        numRead[numA] = numA;
        auto pos = lower_bound(begin, end, K2);
        int d;
        if (pos == end) {
            d = SumB.size() - 1;
        }
        else {
            llong thresh = *pos;
            if (thresh > K2) {
                d = distance(begin, pos) - 1;
                if (d < 0) d = 0;
            }
            else {
                d = distance(begin, pos);
            }
        }
        numRead[numA] += d;
        if (numRead[numA] > numReadMax) {
            numReadMax = numRead[numA];
        }
    }
    cout << numReadMax << endl;
    return 0;
}


Measured memory_bytes: 8684
n,k=map(int,input().split())

X=list(map(int,input().split()))
V=[]
for i in range(n-k+1):
    Y=X[i+k-1]-X[i]   
    V.append(Y+min(abs(X[i]),abs(X[i+k-1])))

print(min(V))

Measured memory_bytes: 14384
#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
//int coprime[maxn];//coprime互质
//int flags[maxn];
#define int long long

bool prime(int n){
	if(n==1){
		return false;
	} 
	if(n==2){
		return true;
	}
	if(n%2==0){
		return false;
	}
	double sqrtn = sqrt(n);
	for(int i = 3;i<=sqrtn;i+=2){
		if(n%i==0){ //no prime
			return false;
		}
	}
	return true;
}
/*int judge(int n,int m){ //判断互质 
	int flag = 1;
	for (int d=2; d<=min(m, n); d++){
        if (m%d == 0 && n%d == 0){
        	flag = 0;
            break;
        }
    }
    return flag;
}*/
vector<int> coprime;
signed main(){
	//memset(flags,0,sizeof(flags));
	//ll a,b;
	int a,b;
	cin>>a>>b;
	//scanf("%lld%ld",&a,&b); //a,b<10^12
	//12 18 3
	//公共的公约数1 2 3 6 12互质 13互质 23互质 总共有3 
	//int times = 0;
	int temp = min(a,b);
	for(int i = 1;i*i<=temp;i++){
		if(temp%i==0){
			coprime.push_back(i);
			if(i*i!=temp){
				coprime.push_back(temp/i);
			}
			//coprime[times] = i;
			//times++;
		}
	}
	/*for(int i = 0;i<times;i++){
		printf("%d\n",coprime[i]);
	}*/
	int ans = 0;
	int t = max(a,b);
	for(int i = 0;i<coprime.size();i++){
		if(t%coprime[i]==0 && prime(coprime[i])){
			ans++;
		}
	} 
	cout<<ans+1<<endl;
	//printf("%d\n",ans+1);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=8005;
int n,m,f[N][N],M;
signed main(){
	scanf("%lld%lld",&n,&M);
	f[0][n+1]=1;
	for (int i=0;i<=3*n;i++)
		for (int j=-n;j<=3*n;j++){
			(f[i+1][j+1+(n+1)]+=f[i][j+(n+1)])%=M;
			(f[i+2][j-1+(n+1)]+=f[i][j+(n+1)]*(i+1))%=M;
			(f[i+3][j+(n+1)]+=f[i][j+(n+1)]*(i+2)%M*(i+1))%=M;
		}
	int ans=0;
	for (int i=0;i<=n;i++)(ans+=f[3*n][3*i+(n+1)])%=M;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 376960
#include <iostream>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
	int n,k;
	cin >> n >> k;

	int x,cnt=0;
	while(n--){
		cin >> x;
		if(x>=k){
			cnt++;
		}
	}

	cout << cnt << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int main() {
  int n;
  cin >> n;
  vector<queue<int>> s(n);
  int q, t, x;
  cin >> q;
  while (cin >> q >> t) {
    if (q == 0) {
      cin >> x;
      s[t].push(x);
    } else if (q == 1) {
      if (!s[t].empty())
        cout << s[t].front() << endl;
    } else {
      if (!s[t].empty())
        s[t].pop();
    }
  }
}


Measured memory_bytes: 4348
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll MOD = 1000000007;
const double PI = 3.141592653589793238463;
const ll N=2e5+9;
ll fastpow(ll base, ll exp)
{
    if (exp == 0)
        return 1;
    if (exp == 1)
        return base % MOD;
    ll t = fastpow(base, exp / 2);
    t = (t * t) % MOD;
    if (exp % 2 == 0)
        return t;
    else
        return ((base % MOD) * t) % MOD;
}
ll binomialCoeff(ll n, ll k)
{
    ll res = 1;
    if ( k > n - k )
        k = n - k;
    for (int i = 0; i < k; ++i)
    {
        res = res*(n - i)%MOD;
        res=res*fastpow(i+1,MOD-2)%MOD;
    }
    return res;
}
int main()
{
    FASTINOUT;
    ll x,y,z;
    cin>>x>>y>>z;
    ll sum=fastpow(2,x)-1;
    ll res=binomialCoeff(x,y);
    ll kl=binomialCoeff(x,z);
    sum=(sum-res+MOD)%MOD;
    sum=(sum-kl+MOD)%MOD;
    cout<<sum<<endl;
    return 0;
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n,k;
    cin >> n >> k;
    if((n - 1) * (n - 2) / 2 < k){
        ANS(-1);
        return 0;
    }
    int32 m = n - 1 + (n - 1) * (n - 2) / 2 - k;
    cout << m << endl;
    FOR(i,1,n)cout << i << " " << n << endl;
    int32 x = (n - 1) * (n - 2) / 2 - k;
    FOR(i,1,n)FOR(j,1,n){
        if(i <= j)break;
        if(x <= 0)break;
        cout << i << " " << j << endl;
        x--;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  string s;
  cin>>n;
  map<string,int> mp;
  for(int i=0;i<n;i++){
    cin>>s;
    mp[s]++;
  }
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>s;
    mp[s]--;
  }
  int c=0;
  for(auto a:mp){
    c=max(c,a.second);
  }
  cout<<c<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

typedef pair<int,int> P;

const int INF = 1e9;


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

	int d,g;
	cin >> d >> g;

	int p[d],c[d];
	for(int i=0;i<d;i++){
		cin >> p[i] >> c[i];
	}

	int point,num;
	int ans = INF;
	for(int i=0;i<(1<<d);i++){
		point=num=0;
//		cout << "\n--" << i << "--\n";
		for(int j=0;j<d;j++){

			//cout << "ボーナス判定 " << (i>>j) << " & " << 1 << "\n";
				
			if((i>>j & 1) == 1){
				//cout << "ボーナス：" << j << "  " << point << "->";
				point += 100*(j+1)*p[j]+c[j];
				//cout << point << "  " << num << "->";
				num += p[j];
				//cout << num << "\n";
			}
		}
		if(point < g){
			for(int j=d-1;j>=0;j--){
				if(((i>>j) & 1) == 0){
					//cout << 100*(j+1) <<"\n";
					for(int k=1;k<p[j];k++){
						point += 100*(j+1);
					//	cout << "    " << point <<"\n";
						num++;
						if(point >= g) break;
					}
				}
				if(point >= g) break;
			}
		}
		if(point >= g){
		//	cout <<"\n" << i << " " << num << " " << point << "\n";
			ans = min(ans,num);
		}
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, input().split()))

def while_pop(arr):
    res = [0] * N
    tmp = []
    for i, a in enumerate(arr):
        cnt = 1
        while tmp:
            aa, c = tmp.pop()
            if aa < a:
                tmp.append((aa, c))
                break
            else:
                cnt += c
        tmp.append((a, cnt))
        res[i] = cnt
    return res

left = while_pop(A)
right = while_pop(A[::-1])[::-1]

answer = 0
for i in range(N):
    answer += left[i] * right[i] * A[i]
    
print(answer)

Measured memory_bytes: 72980
#include <iostream>
#include <math.h>
using namespace std;

struct point{
  double x;
  double y;
};


void koch(int n,point a,point b){

  if(n == 0) return;

  point s,t,u;
  double th = M_PI * 60.0 / 180.0;
  s.x = (2.0 * a.x + 1.0 * b.x) / 3;
  s.y = (2.0 * a.y + 1.0 * b.y) / 3;
  t.x = (1.0 * a.x + 2.0 * b.x) / 3;
  t.y = (1.0 * a.y + 2.0 * b.y) / 3;
  u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
  u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;


  koch(n - 1,a,s);
  cout << s.x << " " << s.y << endl;
  koch(n - 1,s,u);
  cout << u.x << " " << u.y << endl;;
  koch(n - 1,u,t);
  cout << t.x << " " << t.y << endl;;
  koch(n - 1,t,b);

}

int main(){

  int n;
  cin >> n;
  point a,b;
  a.x = a.y = b.y = 0;
  b.x = 100;

  cout << a.x << " " << a.y << endl;;
  koch(n,a,b);
  cout << b.x << " " << b.y << endl;;

}

Measured memory_bytes: 3288
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		new Main();
	}
	public Main(){
//		new ABC105().doIt();
		new ABC106().doIt(); //No_chedck
//		new ABC107().doIt();
//		new ABC108().doIt(); //Math
//		new ABC109().doIt(); //LCM
	}
	class ABC105{
		void doIt() {
			long n = sc.nextLong();
			String str = "";
			for(long i = 1; n != 0; i *= -2) {
				if((n % (i*2)) != 0) {
					n -= i;
					str = "1" + str;
				}
				else{
					str = "0" + str;
				}
//				System.out.println(str);
			}
			if(str.isEmpty()) str = "0";
			System.out.println(str);
		}
	}
	class ABC106{
		void doIt() {
			String str = sc.next();
			long K = sc.nextLong();
			int ans = 0;
			for(int i = 0;i < str.length();i++) {
				long pos = i + 1;
				int num = Integer.parseInt(""+str.charAt(i));
				if(pos == K || num > 1) {
					ans = num;
					break;
				}
			}
			System.out.println(ans);
		}
	}
	class ABC107{
		void doIt() {
			int N = sc.nextInt();
			int K = sc.nextInt() - 1;
			long x[] = new long[N];
			long ans = Integer.MAX_VALUE;
			for(int i = 0;i < N ;i++)x[i] = sc.nextLong();
			for(int i = 0;i < N - K;i++) {
				long dist = Math.abs(x[i] - x[i + K]);
				if(x[i + K] < 0)dist = dist + Math.abs(0 - x[i + K]);
				else if(x[i] > 0)dist = dist + Math.abs(0 - x[i]);
				else dist = dist + Math.min(Math.abs(x[i]),x[i+K]);
				ans = Math.min(ans, dist);
			}
			System.out.println(ans);
		}
	}
	class ABC108{
		void doIt() {
			int N = sc.nextInt();
			int K = sc.nextInt();
			long A = 0;
			long A_2 = 0;
			for(int i = 1;i <= N;i++) {
				if(i % K == 0)A++;
				else if(i*2 % K == 0)A_2++;
			}
			long ans = A*A*A + A_2*A_2*A_2;
			System.out.println(ans);
		}
	}
	class ABC109{
		int euqulid(int A,int B) {
			if(B > 0)return euqulid(B,A % B);
			else return A;
		}
		void doIt(){
			int n = sc.nextInt();
			int X = sc.nextInt();
			int ans = Integer.MAX_VALUE;
			for(int i = 0;i < n;i++) {
				int x = sc.nextInt();
				int dist = Math.abs(x - X);
				if(i == 0)ans = dist;
				else ans = euqulid(dist,ans);
			}
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int main()
{
    ll l,r,ans=0;
    cin>>l>>r;
    ll y=2019;
    if(l==0||r==0)ans=0;
    else if(l/y==r/y)
    {
        ans=1e9;
        rep(i,l,r)rep(j,i+1,r+1) ans=min(ans,i*j%y);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
int main(){
  ll x;
  cin>>x;
  rep2(A,-1000,1000){
    rep2(B,-1000,1000){
     if(pow(A,5)-pow(B,5)==x){
       cout<<A<<" "<<B<<endl;
    return 0;
     }
  }
  }
return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)


using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;

//Appropriately Changed
using edge=struct{int to,cost;};
using G=vector<vector<edge>>;

//Appropriately Changed
void add_edge(G &graph,int from,int to,int cost){ 
	graph[from].push_back({to,cost});
}

auto chuliu(const G &graph,int root){
	using W=int;
	const W inf=1<<28;
	
	const int n=graph.size();
	vector<int> cost(n,inf),pv(n);

	rep(v,n) for(auto &e:graph[v]) if(chmin(cost[e.to],e.cost)) pv[e.to]=v;

	bool term=true;
	vector<int> comp(n,-1),used(n,-1);
	
	rep(v,n){
		if(used[v]!= -1 or cost[v]==inf or v==root) continue;

		int cur=used[v]=v;
		for(cur=pv[cur]; cur!=root && used[cur] == -1; cur=pv[cur]) used[cur]=v;

		if(used[cur]==v){
			term=false,comp[cur]=cur;	
			for(int w=pv[cur]; w != cur; w = pv[w]) comp[w]=cur;
			break;
		}
	}

	G ret(n);
	if(term){
		rep(v,n){
			if(v!=root and pv[v]!=-1)
				add_edge(ret,pv[v],v,cost[v]);
		}
		return ret;
	}

	const int nroot=(comp[root]==-1)?root:comp[root];
	G ngraph(n);
	using E=tuple<int,int,int>;
	map<E,E> dict;

	rep(v,n){
		for(auto &e:graph[v]){			
			int a=v,b=e.to,c=e.cost;
			if(comp[a]!=-1) a=comp[a];
			if(comp[b]!=-1) c-=cost[b],b=comp[b];
			if(a==b) continue;
			dict[E(a,b,c)]=E(v,e.to,e.cost);
			add_edge(ngraph,a,b,c);
		}
	}
	
	auto ntree=chuliu(ngraph,nroot);

	int unuse=-1;
	rep(v,n){
		for(auto &e:ntree[v]){
			int a,b,c;
			tie(a,b,c)=dict[E(v,e.to,e.cost)];
			if(comp[b]!=-1) unuse=b;
			add_edge(ret,a,b,c);
		}
	}

	rep(v,n){
		if(comp[v]==-1 or v==unuse) continue;
		add_edge(ret,pv[v],v,cost[v]); 
	}
	
	return ret;
}

int main(void){
	int v,e,r;
	cin >> v >> e >> r;
	G graph(v);
	rep(i,e){
		int a,b,w;
		cin >> a >> b >> w;
		add_edge(graph,a,b,w);
	}

	auto tree=chuliu(graph,r);
	int ans=0;
	rep(i,v) for(auto &e:tree[i]) ans+=e.cost;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5076
#include <utility>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

template <class T>
class primal_dual {
public:
  using value_type = T;
  using size_type = int;
  using pair = std::pair<value_type, size_type>;

  static constexpr value_type inf = std::numeric_limits<value_type>::max();

  struct edge_type {
    size_type to, rev;
    value_type cap, cost;
  };

private:
  size_type size;
  std::vector<std::vector<edge_type>> graph;
  std::vector<value_type> dist, potential;
  std::vector<size_type> prev_v, prev_e;

  inline bool chmin(value_type &lhs, const value_type &rhs) const {
    if (lhs > rhs) {
      lhs = rhs;
      return true;
    }
    return false;
  }

public:
  primal_dual() { }
  primal_dual(size_type size_) { init(size_); }

  void init(size_type size_) {
    size = size_;
    graph.assign(size_, { });
    dist.assign(size_, 0);
    potential.assign(size_, 0);
    prev_v.assign(size_, 0);
    prev_e.assign(size_, 0);
  }

  void add_edge(size_type from, size_type to, value_type cap, value_type cost) {
    graph[from].push_back(edge_type{ to, (size_type) graph[to].size(), cap, cost });
    graph[to].push_back(edge_type{ from, (size_type) graph[from].size() - 1, 0, -cost });
  }

  value_type min_cost_flow(size_type start, size_type goal, value_type flow) {
    value_type res = 0;
    while (flow > 0) {
      std::fill(dist.begin(), dist.end(), inf);
      std::priority_queue<pair, std::vector<pair>, std::greater<pair>> que;
      dist[start] = 0;
      que.emplace(dist[start], start);
      while (!que.empty()) {
        value_type d = que.top().first;
        size_type u = que.top().second;
        que.pop();
        if (d > dist[u]) {
          continue;
        }
        for (size_type i = 0; i < graph[u].size(); ++i) {
          auto &e = graph[u][i];
          if (e.cap > 0 && chmin(dist[e.to], dist[u] + e.cost + potential[u] - potential[e.to])) {
            que.emplace(dist[e.to], e.to);
            prev_v[e.to] = u;
            prev_e[e.to] = i;
          }
        }
      }
      if (dist[goal] >= inf) {
        return inf;
      }
      for (size_type i = 0; i < size; ++i) {
        potential[i] += dist[i];
      }
      value_type use = flow;
      for (size_type u = goal; u != start; u = prev_v[u]) {
        chmin(use, graph[prev_v[u]][prev_e[u]].cap);
      }
      flow -= use;
      res += use * potential[goal];
      for (size_type u = goal; u != start; u = prev_v[u]) {
        auto &e = graph[prev_v[u]][prev_e[u]];
        e.cap -= use;
        graph[u][e.rev].cap += use;
      }
    }
    return res;
  }

};

int main() {
  int V, E, F;
  std::cin >> V >> E >> F;
  primal_dual<int> net(V);
  for (int i = 0; i < E; ++i) {
    int u, v, c, d;
    std::cin >> u >> v >> c >> d;
    net.add_edge(u, v, c, d);
  }
  auto ans = net.min_cost_flow(0, V - 1, F);
  if (ans == decltype(net)::inf) {
    std::cout << "-1\n";
  }
  else {
    std::cout << ans << '\n';
  }
  return 0;
}


Measured memory_bytes: 3216
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <math.h>
using namespace std;

int main(void){
    // Here your code !
    long long N, A, B;
    cin >> N >> A >> B;

    long long  H[N];

    for (long long i = 0; i < N; i++) {
        cin >> H[i];
    }

    long long start = 1;
    long long last = 1000000000;
    long long T, TB, SUM, temp;

    while ((last != start)) {
        T = start + (last - start) / 2;
        TB = T * B;
        SUM = 0;
        for (int i = 0; i < N; i++) {
            temp = (H[i] - TB);
            if (temp > 0) SUM += (temp + (A - B) - 1) / (A - B);
        }
        // cout << start << " " << " " << last << endl;

        if (SUM > T) {start = T + 1;}
        else {last = T;}

    }

    cout << last << endl;
    return 0;
}


Measured memory_bytes: 1024
n, x = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
goukei = 0
count = 0

if sum(a) < x:
    count = n-1
elif sum(a) == x:
    count = n
else:
    for i in range(n):
        goukei += a[i]
        if goukei > x:
            break
        else:
            count += 1

print(count)


Measured memory_bytes: 3060