akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int main(void){

    int n;
    cin >> n;
    
    int min = 1000000000;
    for(int i=1; i<n; i++) {
        int a = i;
        int b = n-a;

        int sum = 0;
        while(a > 0) {
            sum += a % 10;
            a /= 10;
        }
        while(b > 0) {
            sum += b % 10;
            b /= 10;
        }
        
        if(min > sum) min = sum;

    }
    
    cout << min << endl;

    return 0;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  //入力に対する処理
  char b, ans; cin >> b;
  //処理
  if(b == 'A'){
    ans = 'T';
  }else if(b == 'T'){
    ans = 'A';
  }else if(b == 'G'){
    ans = 'C';
  }else{
    ans = 'G';
  }
  
  //答えの出力
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
int main(void){
    int a,b,c,d,x,y;
    std::cin>>a>>b>>c>>d;
    x=(a+b+c+d)/60;
    y=(a+b+c+d)%60;
    std::cout<<x<<std::endl<<y<<std::endl;
    return 0;
}

Measured memory_bytes: 3072
X,Y = gets.split.map &:to_i
MOD = 10 ** 9 + 7

def modinv(a,m)
  b,u,v = m,1,0
  while b > 0
    t = a / b
    a -= t * b; a,b = b,a
    u -= t * v; u,v = v,u
  end
  u %= m
end

def modfact(n,m)
  ans = 1
  (1..n).each do |i|
    ans *= i
    ans %= m
  end
  ans
end

T = (Y * 2 - X) / 3
S = (X * 2 - Y) / 3

if (X + Y) % 3 != 0 || T < 0 || S < 0 
  puts 0
  exit
end

a = modfact(S+T,MOD)
bb = modfact(S,MOD)
b = modinv(bb,MOD)
cc = modfact(T,MOD)
c = modinv(cc,MOD)

d = a * b % MOD
e = d * c % MOD

puts e


Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int K, T,a[101];
int main() {
	cin >> K >> T;
	for (int i = 0; i < T; i++) cin >> a[i];
	int max_a = a[0];
	for (int i = 1; i < T; i++) {
		if(max_a < a[i]) max_a = a[i];
	}
	int ans = max(0, 2 * max_a - K - 1);
	cout <<ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
import random
import time
my_input = sys.stdin.readline

start = time.time()
D = int(input())
C = list(map(int, my_input().split()))
S = [list(map(int, my_input().split())) for _ in range(D)]


def main():
    cnt = 0
    best_ans, best_score = generate_first_ans()
    while time.time() - start < 1.81:
        cnt += 1
        ans = best_ans[:]

        x = random.random()
        if x > 0.2:
            si, sj = random.randint(0, 364), random.randint(0, 364)
            if si == sj:
                continue
            ans[si], ans[sj] = ans[sj], ans[si]
        else:
            ans[random.randint(0, 364)] = random.randint(0, 25)

        score = calc_score(ans)
        if score > best_score:
            best_score = score
            best_ans = ans

    #print(best_score, cnt)
    for a in best_ans:
        print(a + 1)


def generate_first_ans():
    best_ans = []
    best_score = 0
    last_day = [-1] * 26
    for d in range(365):
        d_ans = -1
        d_score = -float('inf')
        d_last_day = [-1] * 26
        for t in range(26):
            d_tmp_score = 0
            d_tmp_score += S[d][t]
            d_tmp_last_day = last_day[:]
            d_tmp_last_day[t] = d
            for c, ld in zip(C, d_tmp_last_day):
                d_tmp_score -= c * (d - ld)

            if d_tmp_score > d_score:
                d_ans = t
                d_score = d_tmp_score
                d_last_day = d_tmp_last_day[:]

        best_ans.append(d_ans)
        best_score += d_score
        last_day = d_last_day[:]

    return best_ans, best_score


def calc_score(T):
    score = 0
    last_day = [-1] * 26
    for d, t in enumerate(T):
        score += S[d][t]
        last_day[t] = d
        for c, ld in zip(C, last_day):
            score -= c * (d - ld)
    return score


if __name__ == "__main__":
    main()


Measured memory_bytes: 83664
#include <iostream>
#include <algorithm>

using namespace std;
static const int MAX = 1000;
static const int VMAX = 10000;

int n, A[MAX], s;

int B[MAX], T[VMAX + 1];

int slove() {
    int ans = 0;
    bool V[MAX];

    for (int i = 0; i < n; i++) {
        B[i] = A[i];
        V[i] = false;
    }
    sort(B, B + n);
    for (int i = 0; i < n; i++) {
        T[B[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        if (V[i]) continue;

        int cur = i;
        int S = 0;
        int m = VMAX;
        int an = 0;
        while (true) {
            V[cur] = true;
            an++;
            int v = A[cur];
            m = min(m, v);
            S += v;
            cur = T[v];
            if (V[cur]) break;
        }
        ans+=min(S+(an-2)*m,m+S+(an+1)*s);
    }
    return ans;
}

int main() {
    cin >> n;
    s = VMAX;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        s = min(s, A[i]);
    }

    int ans = slove();
    cout << ans << endl;
    return 0;
}


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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, a, b;
  while (cin >> n >> a >> b) {
    vector<int> v(n, 0);
    for (int i = 0; i < a; ++i) {
      ++v[i];
    }
    for (int i = 0; i < b; ++i) {
      ++v[n - 1 - i];
    }
    cout << min(a, b) << ' ' << count(v.begin(), v.end(), 2) << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br =
			new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		while(true) {
			String[] line = br.readLine().split(" ");
			int a = Integer.parseInt(line[0]);
			int b = Integer.parseInt(line[1]);
			if(a == 0 && b == 0) 
				break;

			if(a <= b) {
				System.out.println(a + " " + b);
			} else {
				System.out.println(b + " " + a);
			}
		}
	}
}

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

int main() {
	
	int n;
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	int index=0,ans=0;
	for(int i=1;i<n;i++)
	{
		if (arr[i]>arr[i-1])index=i;
		ans=max(ans,i-index);
	}
	cout<<ans;
	
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7; 
const int maxn=1e6;
int x,y;
ll Finv[maxn+5],jc[maxn+5];
ll modpow(ll x,ll n,ll mod)
{
	ll res=1;
	for(;n;x=x*x%mod,n/=2)
	if(n&1)res=res*x%mod;
	return res;
}
void init()
{
	jc[0]=Finv[0]=1;
	for(int i=1;i<=maxn;++i)
	{
	 jc[i]=jc[i-1]*i;
	 if(jc[i]>=mod)jc[i]%=mod;
    }
	Finv[maxn]=modpow(jc[maxn],mod-2,mod);
	for(int i=maxn-1;i>=1;--i)
	{
	 Finv[i]=Finv[i+1]*(i+1);
	 if(Finv[i]>=mod)Finv[i]%=mod;
    }
}
int C(int n,int m)
{
	if(m<0||m>n)return 0;
	return jc[n]*Finv[n-m]%mod*Finv[m]%mod;
}
int cal(int x,int y)
{
	if(!((x*2>=y)||(y*2>=x)))return 0;
	if((x+y)%3)return 0;
	int a=(x+y)/3; 
	return C(a,x-a);
}
int main()
{
	init();
	scanf("%d%d",&x,&y);
	printf("%d\n",cal(x,y));
	return 0;
}

Measured memory_bytes: 15872
def list_count(my_list):
    dic={} #辞書型の宣言
    for num in my_list:
        if num in dic: #もしnumがkeyとして辞書にあれば
            dic[num]+=1 #valueに+1
        else: #なければ
            dic[num]=1 #dicにnumというkeyを追加し、対応するvalueを1とする
    return dic
s=input()
t=input()
n=len(s)
dic={}
for i in range(n):
    if s[i] in dic and dic[s[i]]!=t[i]:
        print("No")
        exit()
    else:
        dic[s[i]]=t[i]
dic2={}
for i in range(n):
    if t[i] in dic2 and dic2[t[i]]!=s[i]:
        print("No")
        exit()
    else:
        dic2[t[i]]=s[i]
print("Yes")


Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int const MOD = 1000000007;

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main() {
    int n; cin >> n;
    int a[100010] = {};
    int sum = 0;

    rep(i,0,n) {
        cin >> a[i];
        sum += a[i];
    }

    int cs[100010] = {};
    int ret[100010] = {};
    int cntnum = 0;
    if(sum % (n * (n+1) / 2)) cout << "NO" << endl;
    else {
        cntnum = sum / (n*(n+1) / 2);
        rep(i,0,n) {
            int prev = (i - 1 + n) % n;
            if(a[i] <= a[prev]) {
                int s = a[prev] - a[i];
                if( (s+cntnum) % n != 0 ) {
                    cout << "NO" << endl;
                    return 0;
                }
                cs[i] += (s + cntnum) / n;
            }
        }

        rep(i,0,n) {
            ret[0] += cs[i] * ((n - i) % n + 1);
        }
        // printf("ret: %lld, ratio = %lf\n", ret[0], ratio);
        rep(i,1,n) {
            ret[i] = ret[i-1] - cs[i] * n + cntnum;
        }

        rep(i,0,n) {
            if(ret[i] != a[i]) {
                cout << "NO" << endl;
                return 0;
            }
        }
        cout << "YES" << endl;
    }
    return 0;
}

Measured memory_bytes: 2560
#include <iomanip>
#include <iostream>
 
using namespace std;
 
int main()
{ 
	double a, b, c, d, e, f;

	while (cin >> a >> b >> c >> d >> e >> f)
	{
		// matrix
		double y = (d * c - a * f) / (d * b - a * e);
		double x = (c - b * y) / a;
		cout << setprecision(3) << fixed << x << " " << y << endl;
	}

	return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
//printf("%.12Lf\n",);
int keta(int x){
	rep(0,i,30){
		if(x<10){
			return i+1;
		}
		x=x/10;
	}
}
int gcd(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return bb;
		}	
		bb=bb%aa;
		if(bb==0){
			return aa;
		}
	}
}	
int lcm(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return x/bb*y;
		}	
		bb=bb%aa;
		if(bb==0){
			return x/aa*y;
		}
	}
}
bool p(int x){
	if(x==1)return false;
	rep(2,i,sqrt(x)+1){
		if(x%i==0&&x!=i){
			return false;
		}
	}	
	return true;
}
int max(int a,int b){
	if(a>=b)return a;
	else return b;
}
int min(int a,int b){
	if(a>=b)return b;
	else return a;
}	
int n2[41];		
int nis[41]; 
int nia[41];
int mody[41];
int nn;
int com(int n,int y){
	int ni=1;
	for(int i=0;i<41;i++){
		n2[i]=ni;
		ni*=2;
	}
	int bunsi=1,bunbo=1;
	rep(0,i,y)bunsi=(bunsi*(n-i))%mod;
	rep(0,i,y)bunbo=(bunbo*(i+1))%mod;
	mody[0]=bunbo;
	rep(1,i,41){
		bunbo=(bunbo*bunbo)%mod;
		mody[i]=bunbo;
	}
	rep(0,i,41)nis[i]=0;
	nn=mod-2;
	for(int i=40;i>=0;i-=1){
		if(nn>n2[i]){
			nis[i]++;
			nn-=n2[i];
		}
	}
	nis[0]++;
	rep(0,i,41){
		if(nis[i]==1){
			bunsi=(bunsi*mody[i])%mod;
		}
	}
	return bunsi;
}
int yakuwa(int n){
	int sum=0;
	rep(1,i,sqrt(n+1)){
		if(n%i==0)sum+=i+n/i;
		if(i*i==n)sum-=i;
	}
	return sum;
}	
bool hei(int n){
	rep(0,i,100){
		if(i*i==n){
			return true;
		}
	}
	return false;
}
int pow(int b,int a){	
	int aa=1;
	rep(0,i,a)aa*=b;	
	return aa;
}	
int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
signed main(){
	ic(n)
	ic(k)
	ic(m)
	if(m-k-n>=0&&(m-k-n)*(m-k-n)>4*n*k)c("Yes")
	else c("No")
}	

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
const int N=1e7+10;
int n,k;
int fac[N],inv[N];
template <typename T>
inline void read(T &x)
{
	T flg=1;x=0;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') flg=-flg;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=flg;
}
template <typename T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline int ksm(int b,int p)
{
	int ans=1;
	while(p)
	  {
	  	if(p&1) ans=ans*b%MOD;
	  	b=b*b%MOD;
	  	p>>=1;
	  }
	return ans;
}
inline void get_inv()
{
	fac[0]=1;inv[0]=1;
	for(register int i=1;i<=n;++i) fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(register int i=n-1;i>=1;--i)
	  inv[i]=inv[i+1]%MOD*(i+1)%MOD;
}
inline int C(int n,int m)
{
	if(m>n) return 0;
	if(m==n) return 1;
	return fac[n]%MOD*inv[m]%MOD*inv[n-m]%MOD;
}
signed main()
{
	read(n);read(k);
	get_inv();
	for(register int i=1;i<=k;++i)
	  write(C(n-k+1,i)*C(k-1,i-1)%MOD),puts("");
	return 0;
}

Measured memory_bytes: 2304
from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))
ans = 0
for i, A_sums in enumerate(A_sums_list):
    B_min = 0
    B_max = M + 1
    while True:
        B_index = int((B_max + B_min) * 0.5)
        if A_sums + B_sums_list[B_index] <= K:
            B_min = B_index
        else:
            B_max = B_index
        if B_max - B_min == 1:
            break   
    if i + B_min > ans and A_sums + B_sums_list[B_min] <= K:
        ans = i + B_min
print(ans)

Measured memory_bytes: 135796
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

typedef double ld;
typedef long long ll;
typedef pair<int,int> pii;

const int INF = 1e8 + 10;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

int main(){ _

	int N,M;
	cin >> N >> M;

	vector<vector<int>> g(N+1, vector<int>(N+1, INF));

	vector<tuple<int,int,int>> E;

	while(M--){
		int x,y,z;	
		cin >> x >> y >> z;
		
		g[x][y] = z;
		g[y][x] = z;
		E.pb({x,y,z});
	}

	for(int k = 1; k <= N; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}

	int ans = 0;
	for(auto [x,y,z] : E){
		if(g[x][y] < z) ans++;
	}

	cout << ans << endl;

	return 0;
}


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

int main() {
  int N;
  int i=0,id;
  int ans=0;

  cin >> N;

  vector<int> d(N);

  while(cin >> id) {
    d[i] = id;
    i++;
  }

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

  ans = d[N/2] - d[N/2-1];

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    yes = 'YES'
    no = 'NO'

    if sum(A) % 2 == 0:
        print(yes)
    else:
        print(no)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 14108
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>

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; }

char ToUpper(char cX) { return toupper(cX); }
char Tolower(char cX) { return tolower(cX); }

const long long INF = 1LL << 60;
const long long MOD = 1000000007;

using namespace std;
typedef unsigned long long ull;
typedef  long long ll;

vector<vector<ll>> dp;

ll gcd(ll x, ll y)
{
	ll r;
	if (x < y) {
		swap(x, y);
	}
	while (y > 0) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}
int main()
{
	ll a, b;
	cin >> a >> b;
	cout << gcd(a, b) << endl;
	return 0;
}



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

#define clr(i, j)     memset(i, j, sizeof(i))
#define pb            push_back

typedef long long     ll;

//-*
ll g[1005];
int h,w;

const ll mod = 1e9 + 7;int as,fs,ts;
int main() {
ll a,b,n;cin>>n;
cin>>a>>b;
for(int i=0;i<n;i++){
   ll k;
   cin>>g[i];
  // if(k<=a){as++;}  if(k<=b&&k>a){ts++;}if(k>b){fs++;}
}
  for(int i=0;i<n;i++){
   ll k=g[i];
  // cin>>g[i];
   if(k<=a){as++;} 
   if(k<=b&&k>a){ts++;}
   if(k>b){fs++;}
}
 
 cout<<min(min(as,ts),fs);
}

Measured memory_bytes: 256
package main

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

func main() {
	Count := ReadLineInt()[0]
	Result := 0

	for i := 1; i <= Count; i++ {
		if !(i%5 == 0 || i%3 == 0) {
			Result += i
		}
	}

	fmt.Println(Result)
}

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

func fln(format string, elements ...interface{}) {
	fmt.Printf(format+"\n", elements...)
}

var BufReader = bufio.NewReaderSize(os.Stdin, 1e6)

func ReadLine() string {
	a, _, _ := BufReader.ReadLine()
	return string(a)
}

func ReadLineInt() (result []int) {
	in := strings.Split(ReadLine(), " ")
	result = make([]int, 0, 2)
	for _, v := range in {
		t, _ := strconv.Atoi(v)
		result = append(result, t)
	}
	return
}


Measured memory_bytes: 1788
from operator import itemgetter
n, m = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
removed = -1
ans = 0
for a, b in ab:
  if a > removed:
    removed = b-1
    ans += 1
print(ans)

Measured memory_bytes: 18980
#include<stdio.h>

int main()
{
	char str[1002];
	int i;

	fgets(str,1002,stdin);
	for(i=0;str[i]!='\n'&&i<1000;i++)
	{
		str[i]-=(char)3;
		if(str[i]<'A')
		{
			str[i]+=(char)(-'A'+'Z'+1);
		}
	}
	printf(str);
	return 0;
}

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

using namespace std;

#define fo(i,n) for(int i=0; i<n; i++)
#define Fo(i,k,n) for(int i=k; i<n; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it=a.begin(); it!=a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int n,k;
vi hi;
vvi dp(100005,vi(101,INT_MAX));

void printt(){
    Fo(i,1,k+1){
        dp[n][i]=0;
    }
    Fo(i,1,k+1){
        dp[n-1][i]=abs(hi[n-1]-hi[n]);
    }
    for(int i=n-2;i>0;i--) {
        dp[i][1]=abs(hi[i]-hi[i+1])+dp[i+1][k];
        Fo(j,2,k+1){
            dp[i][j]=min(dp[i][j-1],abs(hi[i]-hi[((i+j) > n) ? n : (i+j)])+dp[((i+j) > n) ? n : (i+j)][k]);
        }
    }
    // Fo(i,1,n){
    //     cout<<dp[i][k]<<endl;
    // }
    cout<<dp[1][k]<<endl;
}

void take_inp() {
    cin>>n>>k;
    hi.resize(n+1);
    Fo(i,1,n+1){
        int temp;
        cin>>temp;
        hi[i]=temp;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    take_inp();
    printt();
    return 0;
}

Measured memory_bytes: 43648
#include <iostream>
#include <regex>
#include <locale>
#include <cmath>
using namespace std;
 
int main() {
  vector<int> vec;
  int n, k;
  cin >> n >> k;
  // while(n < k) {
  //   vec.push_back(n % k);
  //   n /= k;
  // }
  // reverse(vec);
  // for
  int digit;
  for(digit = 1; n >= pow(k, digit); digit++) {} 
  cout << digit;
}

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

long long cur;

vector<int> arr(1e6);
vector<int> size(1e6);

void make_set(int n){
	for(int i = 1; i <= n; i++){
		arr[i] = i;
		size[i] = 1;
	}
}

int find(int x){
	if(x == arr[x]) return x;
	return arr[x] = find(arr[x]);
}

void union_set(int x, int y){
	int px = find(x);
	int py = find(y);

	if(px!=py){	
		if(size[px] < size[py]){
			swap(px,py);
		}
			arr[py] = px;	
			cur -= 1LL*(size[px]*size[py]);
			size[px]+=size[py];
			size[py]=0;
	}
}


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

	cur = 1LL*n*(n-1)/2;
	make_set(n);

	vector<int> u(m);
	vector<int> v(m);

	for(int i = 0;i < m; i++){
		cin>>u[i]>>v[i];
	} 
	vector<long long> ans(m);
	for(int i = m-1; i>=0; i--){
		ans[i] = cur;
		union_set(u[i],v[i]);
	}
	for(int i = 0; i < m; i++){
		cout<<ans[i]<<"\n";
	}

}

Measured memory_bytes: 10752
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;

LL a[4005],tree[12005];

void update(int n, int s, int e, int si, int ei, LL v)
{
    if(e<si|s>ei)return;
    if(si<=s&&e<=ei){
        tree[n]=v;
        return;
    }
    int m=(s+e)/2,lch=2*n,rch=lch+1;
    update(lch,s,m,si,ei,v);
    update(rch,m+1,e,si,ei,v);
    tree[n]=min(tree[lch],tree[rch]);
}

LL query(int n, int s, int e, int si, int ei)
{
    if(e<si|s>ei)return 1e18;
    if(si<=s&&e<=ei)return tree[n];
    int m=(s+e)/2,lch=2*n,rch=lch+1;
    LL v1,v2;
    v1=query(lch,s,m,si,ei);
    v2=query(rch,m+1,e,si,ei);
    return min(v1,v2);
}

int main()
{
    int i,j,t=0;
    LL n,p,x,S=0,m,dap=1e18,res;
    scanf("%lld %lld", &n, &p);
    for(i=1;i<=2*n;i++)update(1,1,2*n,i,i,1e18);
    for(i=1;i<=n;i++){
        scanf("%lld", &a[i]);
        a[i+n]=a[i];
        update(1,1,2*n,i,i,a[i]);
        update(1,1,2*n,n+i,n+i,a[n+i]);
    }
    for(j=0;j<n;j++){
        res=0;
        for(i=n+1;i<=2*n;i++){
            m=query(1,1,2*n,i-j,i);
            res+=m;
        }
        dap=min(dap,res+j*p);
    }
    printf("%lld\n", dap);
    return 0;
}


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

using namespace std;

int main(){
    vector<int> X(3);
    cin >> X[0] >> X[1] >> X[2];
    sort(X.begin(), X.end());

    int ans = 0;
    if((X[2] - X[1]) % 2 == 0 && (X[2] - X[0]) % 2 == 0){
        ans = (X[2] - X[1])/2 + (X[2] - X[0])/2;
    }else if((X[2] - X[1]) % 2 == 0 && (X[2] - X[0]) % 2 == 1){
        ans = (X[2] - X[1])/2 + (X[2] - X[0] - 1)/2 + 2;
    }else if((X[2] - X[1]) % 2 == 1 && (X[2] - X[0]) % 2 == 0){
        ans = (X[2] - X[1] - 1)/2 + (X[2] - X[0])/2 + 2;
    }else{
        ans = (X[2] - X[1] - 1)/2 + (X[2] - X[0] - 1)/2 + 1;
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}typedef long long ll;
const int N=2e5+10;
const int MAXN=N<<2;
const ll INF=1e17;
int m,A,B,n,X[N];ll dp[N];
ll S[N],ans=INF;
#define ls (u<<1)
#define rs (u<<1|1)
#define MID (l+r)>>1
ll T1[N<<2],T2[N<<2];
void Rebuild(int u,int l,int r){
	T1[u]=T2[u]=INF;
	if(l==r) return;
	int mid=MID;
	Rebuild(ls,l,mid),Rebuild(rs,mid+1,r);
}
inline void Insert(int u,int l,int r,int p,ll x){
	T1[u]=min(T1[u],x-p),T2[u]=min(T2[u],x+p);
	if(l==r) return;int mid=MID;
	if(mid>=p) Insert(ls,l,mid,p,x);
	else       Insert(rs,mid+1,r,p,x);
	return;
}
ll Query(int u,int l,int r,int L,int R,const ll*T){
	if(L>R) return INF;
	if(l>=L&&r<=R) return T[u];
	int mid=MID;
	if(mid>=R) return Query(ls,l,mid,L,R,T);
	if(mid< L) return Query(rs,mid+1,r,L,R,T);
	return min(Query(ls,l,mid,L,mid,T),Query(rs,mid+1,r,mid+1,R,T));
}
inline void Solve(int A,int B){
	X[0]=A;Rebuild(1,1,n);dp[1]=abs(X[1]-B);
	ans=min(ans,dp[1]+S[m]),Insert(1,1,n,X[0],dp[1]);
	for(int i=2;i<=m;++i) {int x=X[i];
		ll L=Query(1,1,n,1,x,T1);
		ll R=Query(1,1,n,x,n,T2);
		dp[i]=min(L+x,R-x)+S[i-1];
		Insert(1,1,n,X[i-1],dp[i]-S[i]);
		ans=min(ans,dp[i]+S[m]-S[i]);
	}return;
}
int main()
{
	init(n),init(m),init(A),init(B);
	for(int i=1;i<=m;++i) init(X[i]);
	for(int i=2;i<=m;++i) S[i]=S[i-1]+abs(X[i]-X[i-1]);
	Solve(A,B),Solve(B,A),cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 16640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int s[] = new int[n];
			double m = 0;
			double sum = 0;

			for (int i = 0; i < n; i++) {
				s[i] = sc.nextInt();
				sum += s[i];
			}
			m = sum / n;

			sum = 0;

			for (int i = 0; i < n; i++) {
				sum += (s[i] - m) * (s[i] - m);
			}

			double a = Math.sqrt(sum / n);
			System.out.println(a);
		}
	}

}

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

using namespace std;

const int INF = 1e9 + 5;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> v(n);
    for(int& x: v) scanf("%d",&x);
    vector<int> dp(n,INF);
    dp[0] = 0;
    for(int i=0;i<n;++i){
        for(int j : {i+1,i+2}){
           if(j<n) dp[j] = min(dp[j],dp[i] + abs(v[i]-v[j]));
        }
    }
    printf("%d\n",dp[n-1]);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
template <typename Functor>
struct fix_type
{
    Functor functor;
    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const& { return functor(functor, std::forward<Args>(args)...); }
};
template <typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor) { return {std::forward<Functor>(functor)}; }
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> to(N, -1);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        to[u] = v;
    }
    vector<int> label(N), cycle;
    iota(label.begin(), label.end(), 0);
    vector<bool> used(N, false), reached(N, false);
    auto getcycle = [&](int s) {
        for (int i = 0; i < 2 * N; i++, s = to[s]) {
            used[s] = true;
            if (to[s] == -1) { break; }
        }
        if (reached[label[s]]) { return; }
        reached[label[s]] = true, cycle.push_back(s);
        if (to[s] == -1) { return; }
        for (int p = to[s]; p != s; p = to[p]) { label[p] = s; }
    };
    for (int i = 0; i < N; i++) {
        if (not used[i]) { getcycle(i); }
    }
    vector<vector<int>> g(N);
    for (int i = 0; i < N; i++) {
        if (to[i] == -1 or label[i] == label[to[i]]) { continue; }
        g[label[to[i]]].push_back(label[i]);
    }
    auto dfs = fix([&](auto&& self, const int s) -> ll {
        ll ans = 1;
        for (const int to : g[s]) { (ans *= self(self, to)) %= MOD; }
        return (ans + 1) % MOD;
    });
    ll ans = 1;
    for (const int c : cycle) { (ans *= dfs(c)) %= MOD; }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3180
#include <iostream>
#include <vector>
#include <algorithm>

#define INF 1'000'000'010

using namespace std;

int main()
{
	int n, w;
	cin >> n >> w;
	int sum = 0;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		sum += b[i];
	}
	
	vector<vector<long long>> dp(n + 1, vector<long long>(sum + 1, INF));
	dp[0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= sum; j++) {
			if (j < b[i]) {
				dp[i + 1][j] = dp[i][j];
			}
			else {
				dp[i + 1][j] = min(dp[i][j], dp[i][j - b[i]] + a[i]);
			}
		}
	}

	for (int i = sum; i > 0; i--) {
		if (dp[n][i] <= w) {
			cout << i << endl;
			return 0;
		}
	}
	cout << 0 << endl;

	return 0;
}

Measured memory_bytes: 80256
#include<iostream>
#include<string>
#include<utility>
#include<cstdio>
 
using namespace std;
 
typedef struct{
    char symbol;
    int number;
}Card;
 
const int Sentinel = 200000000;
 
int partition(int Card[],int p,int r);
void quicksort(Card A[],int p,int r);
void merge(Card A[],int left,int mid,int right);
void mergeSort(Card A[],int left,int right);
 
int main(){
    int n; cin>>n;
    Card *card1,*card2;
	card1 = new Card[n]; card2 = new Card[n];
 
    for(int i=0;i<n;i++){
        //cin>>card1[i].symbol>>card1[i].number;
		cin>>card1[i].symbol;
		scanf("%d",&card1[i].number);
        card2[i] = card1[i];
    }
 
    quicksort(card1,0,n-1);
    mergeSort(card2,0,n);
 
    int judge = 0;
    for(int i=0;i<n;i++){
        if(card1[i].symbol!=card2[i].symbol){
            cout<<"Not stable"<<endl;
            judge = 1;
            break;
        }
    }
 
    if(judge==0) cout<<"Stable"<<endl;
 
    for(int i=0;i<n;i++){
		printf("%c %d\n",card1[i].symbol,card1[i].number);
        //cout<<card1[i].symbol<<" "<<card1[i].number<<endl;
    }

	delete [] card1; delete [] card2;
 
    cin.get();
    cin.get();
}

int partition(Card A[],int p,int r){
	int x = A[r].number;
	int i = p-1;
	for(int j=p;j<r;j++){
		if(x>=A[j].number){
			i++;
			swap(A[i],A[j]);
		}
	}
	swap(A[r],A[i+1]);
	return i+1;
}
 
void quicksort(Card A[],int p,int r){
    if(p<r){
        int q = partition(A,p,r);
        quicksort(A,p,q-1);
        quicksort(A,q+1,r);
    }
}
 
void merge(Card A[],int left,int mid,int right){
    int n1 = mid-left, n2 = right-mid;
    Card *L,*R;
    L = new Card[n1+1]; R = new Card[n2+1];
    for(int i=0;i<n1;i++) L[i] = A[left+i];
    for(int i=0;i<n2;i++) R[i] = A[mid+i];
    L[n1].number = R[n2].number = Sentinel;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        if(L[i].number<=R[j].number){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
        }
    }
    delete [] L; delete [] R;
}
 
void mergeSort(Card A[],int left,int right){
    if(left+1<right){
        int mid = (left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }
}

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

const int ha=998244353;
const int N=1000000;
int fac[N+5],ifac[N+5];

int Pow(int a,int b)
{
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%ha)
        if(b&1) ans=1ll*ans*a%ha;
    return ans;
}

void Init()
{
    fac[0]=1;
    for(int i=1;i<=N;i++)
        fac[i]=1ll*fac[i-1]*i%ha;
    ifac[N]=Pow(fac[N],ha-2);
    for(int i=N-1;i>=0;i--)
        ifac[i]=1ll*ifac[i+1]*(i+1)%ha;
}

inline int C(const int &n,const int &m){return 1ll*fac[n]*ifac[m]%ha*ifac[n-m]%ha;}
inline int invC(const int &n,const int &m){return 1ll*ifac[n]*fac[m]%ha*fac[n-m]%ha;}

int main()
{
    int n,m;Init();
    cin>>n>>m;
    int t=min(n,m),ans=0;
    for(int i=1;i<=t;i++)
        ans=(ans+1ll*C(2*i,i)*C(n+m-2*i,n-i))%ha;
    ans=1ll*ans*invC(n+m,n)%ha*ifac[2]%ha;
    printf("%d\n",(ans+max(n,m))%ha);
    return 0;
}

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

int main(){
	int N;
	cin >> N;
	int a[N+1];
	int i;
	for( i=0; i<N; i++ ){
		cin >> a[i];
	}
  	a[N+1] = -1;
  
	sort(a, a+N);
  
	int tmp, count, point;
	int sum = 0;
	
	tmp = a[0];
	point = 0;
	
	for( i=1; i<=N; i++ ){
		if( tmp != a[i] ){
			count = i - point;
			if( tmp < count ){
				sum = sum + count - tmp;
			}
			if( tmp > count ){
				sum = sum + count;
			}
			tmp = a[i];
			point = i;
		}
	}
  
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 2222;
const int MAX_V = MAX * MAX;
int n;
int a[MAX];
bitset<MAX_V> bit;

int main(void) {
    cin >> n;
    REP(i, n) {
        cin >> a[i];
    }
    const int sum = accumulate(a, a + n, 0);
    bit[0] = 1;
    REP(i, n) {
        bit |= bit << a[i];
    }
    int ans = (sum + 1) / 2;
    for (; !bit[ans]; ans++) ;
    cout << ans << endl;
}


Measured memory_bytes: 2048
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<sstream>
using namespace std;

typedef long long ll;

int main() {
  int N; cin >> N;
  int ans = 1e9;
  for ( int i = 1; i < N; i++ ) {
    int tmp = i;
    int tmp2 = N-i;
    int cnt = 0;
    while(tmp>0) {
      cnt+=tmp%10;
	tmp/=10;
    }
    while(tmp2>0) {
      cnt+=tmp2%10;
	tmp2/=10;
    }
    ans = min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}


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

a = 10**9+7
count = [0 for i in range(k)]
sum = 0

res = n
e = []
while res != 0:
    e.append(res%2)
    res = res // 2

def exp(m, e, a):
    sum = 0
    ans = 1
    t = m
    for i in e:
        ans = (ans*(t**i))%a
        t = (t**2)%a
    return ans

for i in range(k, 0, -1):
    count[i-1] = exp(k//i, e, a)
    j = 2
    while i*j <= k:
        count[i-1] -= count[i*j-1]
        j += 1
    count[i-1] %= a
    sum += (i*count[i-1])%a

sum %= a
print(sum)

Measured memory_bytes: 11280
import math
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
d=0
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    d+=math.sqrt((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)
print(d/n)


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define dump(x)      cerr << #x << " = " << (x) << endl;

const LL MOD = 1e9 + 7;
inline LL mod_add(LL a, LL b) { return (a + b) % MOD; }
inline LL mod_sub(LL a, LL b) { return (a + MOD - b) % MOD; }
inline LL mod_mul(LL a, LL b) { return ((a % MOD) * (b % MOD)) % MOD; }
LL mod_bipow(LL x, LL y) {   // x^y by bisection method
    if (y == 0) return 1;
    else if (y == 1) return x % MOD;
    else if (y % 2 == 0) {
        LL val = mod_bipow(x, (LL)(y / 2));
        return mod_mul(val, val);
    } else {
        LL val = mod_bipow(x, (LL)(y / 2));
        return mod_mul(mod_mul(val, val), x);
    }
}
LL mod_inv(LL x) { return mod_bipow(x, MOD - 2); }   // x^{-1} = x^{MOD-2} (MOD: prime number)
LL mod_div(LL a, LL b) { return mod_mul(a, mod_inv(b)); }   // a/b = a*b^{-1}

class Combination {
    VI facts, inv_facts;
public:
    Combination(LL N) : facts(N + 1), inv_facts(N + 1) {
        REP(i, N + 1) facts[i] = i == 0 ? 1 : mod_mul(facts[i - 1], i);
        for (LL i = N; i >= 0; i--) inv_facts[i] = i == N ? mod_inv(facts[N]) : mod_mul(inv_facts[i + 1], i + 1);   // (i!)^{-1}=((i+1)!)^{-1}*(i+1)
    }
    LL nCr(LL n, LL r) {
        return mod_mul(facts[n], mod_mul(inv_facts[r], inv_facts[n - r]));
    }
};

int main() {
    LL N, M, K;
    cin >> N >> M >> K;

    LL ans = 0;
    FOR(d, 1, N) {
        ans = mod_add(ans, mod_mul(d, mod_mul(mod_mul(mod_sub(N, d), M), M)));
    }
    FOR(d, 1, M) {
        ans = mod_add(ans, mod_mul(d, mod_mul(mod_mul(mod_sub(M, d), N), N)));
    }
    Combination c(N * M);
    ans = mod_mul(ans, c.nCr(N * M - 2, K - 2));
    cout << ans << endl;
	
    return 0;
}


Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll a[225816],k,ans=0ll,tree[225816];
int n;
vector<P> v; 

void update(int x){
	while(x<225816){
		++tree[x];
		x += (x&(-x));
	}
}

ll query(int x){
	ll ret = 0ll;
	while(x){
		ret += tree[x];
		x -= (x&(-x));
	}
	return ret;
}

bool comp(P a, P b){
	return ((a.first == b.first)?(a.second < b.second):(a.first < b.first));
}

int main(void){
	int i;
	fill(tree,tree+225816,0ll);
	cin >> n >> k;
	a[0] = 0ll;
	v.push_back(P(a[0],1));
	for(i=1; i<=n; ++i){
		cin >> a[i];
		a[i] -= k;
		a[i] += a[i-1];
		v.push_back(P(a[i],i+1));
	}
	sort(v.begin(),v.end(),comp);
	for(i=0; i<=n; ++i){
		ans += query(v[i].second);
		update(v[i].second);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9072
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;

int main(){
  int N,M;
  cin>>N>>M;
  set<int> sSet,eSet;
  for(int i=0;i<M;i++) {
    int ai,bi;
    cin>>ai>>bi;
    if (ai == 1) sSet.insert(bi);
    if (bi == N) eSet.insert(ai);
  }
  bool exit=false;
  for (set<int>::iterator it=sSet.begin();!exit&&it!=sSet.end();it++) {
    if(eSet.find(*it)!=eSet.end())exit=true;
  }

  if(exit)cout<<"POSSIBLE"<<endl;
  else cout<<"IMPOSSIBLE"<<endl;
  return 0;
}


Measured memory_bytes: 9600
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main()
{
    int S, W;
    cin >> S >> W;

    if (S > W) {
        cout << "safe" << endl;
    }
    else {
        cout << "unsafe" << endl;
    }
}


Measured memory_bytes: 3132
#include <iostream>

using namespace std;

int a[6];

int main() 
{
    int x , y;
    cin >> x >> y;
    for(int i = 0 ; i <= x ; i++)
        for(int j = 0 ; j <= x ; j++)
        {
            if(i + j == x && 2 * i + 4 * j == y)
            {
                cout << "Yes\n";
                return 0;
            }
        }
        cout << "No\n";
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>

int main(){
	long long int a,b,c,k;
	
	while(scanf("%lld %lld %lld %lld",&a,&b,&c,&k)!=EOF){
		for(int i=0;i<k;i++){
			if(a>b && a>c)
				a*=2;
			else if(b>a && b>c)
				b*=2;
			else
				c*=2;
		}
		printf("%lld\n",a+b+c);
	}
	return 0;
}

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

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

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

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

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

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

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

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

fn main(){
    input!{
        n:usize,
        m:usize,
        c:i64,
        bn:[i64;m],
        an:[[i64;m];n],
    }
    let mut ans = 0;
    for j in 0..n {
        let res:i64 = an[j as usize].iter().zip(bn.iter()).map(|(&x1,&x2)| x1 * x2).sum();
        if res + c > 0 {
            ans +=1;
        }
    }
    println!("{}",ans);
}

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

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(K: int, X: int):
    print(YES if 500*K >= X else NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(K, X)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import qualified Data.ByteString.Char8 as C
import Data.Maybe (fromJust, isNothing)

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

main :: IO ()
main = do
  [n,y] <- readInts
  putStrLn $ f n y

type Mai = Int
type Yen = Int
type Pochi = (Int,Int,Int)

minPochi :: Yen -> Pochi
minPochi y = (a,b,c)
  where
    (a,r) = y `quotRem` 10000
    (b,s) = r `quotRem` 5000
    c     = s `quot` 1000

canPay :: Mai -> Yen -> Maybe Pochi
canPay n y = h i
  where
    i = minPochi y
    h :: Pochi -> Maybe Pochi
    h p@(a,b,c)
      | m == 0 = Just p
      | m > 3 && b > 0 = h (a,  b-1,c+5)
      | m > 0 && a > 0 = h (a-1,b+2,c)
      | otherwise = Nothing
      where
        m = n-(a+b+c)

f :: Mai -> Yen -> String
f n y
  | isNothing p = "-1 -1 -1"
  | otherwise   = show a ++ " " ++ show b ++ " " ++ show c
  where
    p = canPay n y
    Just (a,b,c) = p

otsdm' :: Mai -> Yen -> [Pochi]
otsdm' n y =
  [(a,b,n-a-b)
  | let a0 = y `quot` 10000
  , a <- [0 .. a0]
  , let b0 = (y - 10000*a) `quot` 5000
  , b <- [0 .. b0]]

gok :: Pochi -> Yen
gok (a,b,c) = 10000*a +5000*b + 1000*c 

otsdm :: Mai -> Yen -> String
otsdm n y
  | null os = "-1 -1 -1"
  | otherwise = show a ++ " " ++ show b ++ " " ++ show c
  where
    os = filter (\o -> y == gok o) $ otsdm' n y
    (a,b,c) = head os

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

using namespace std;

int main() {

	long n;
	cin >> n;

	vector<long> a(n + 1), b(n + 1);
	for (long i = 1; i < n; i++) {
		cin >> b[i];
	}
	a[0] = b[1];
	a[1] = b[1];
	b[n ] = 10000000;
	for (long i = 1; i < n; i++) {
		a[i] = min(b[i], b[i + 1]);
	}


	cout << accumulate(a.begin(),a.end(),0) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int x[400][400],y[400][400],mark[400][400];
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>x[i][j];
            y[i][j]=x[i][j];
            mark[i][j]=1;
        }
    }
    for(int k=0; k<n; k++)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                y[i][j]=min(y[i][j],y[i][k]+y[k][j]);
            }
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(x[i][j]!=y[i][j])
            {
                cout<<"-1"<<endl;
                return 0;
            }
        }
    }
    for(int k=0; k<n; k++)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==j || j==k || i==k)
                    continue;
                if(x[i][j]==x[i][k]+x[k][j])
                {
                    mark[i][j]=0;
                }
            }
        }
    }
    ll sum=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(mark[i][j])sum+=x[i][j];

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


Measured memory_bytes: 4984