akhauriyash/Code-Regression huggingface dataset:
n = int(input())
ans = 0
for i in range(n):
    ans += (i + 1) * (n - i)
    
for _ in range(n - 1):
    u, v = map(int, input().split())
    ans -= min(u, v) * (n - max(u, v) + 1)

print(ans)

Measured memory_bytes: 9176
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
const double pi=acos(-1.0),eps=1e-8;
const int maxn=1e5+10;
const ll mod=1e9+7;
int main()
{
    int k;
    scanf("%d", &k);
    ll n = 7;
    int ans = 1;
    if(k%2==0 || k%5==0)
    {
        printf("-1");
        return 0;
    }
    while(1)
    {
        if(n % k==0)
        {
            printf("%d", ans);
            break;
        }
        ans ++;
        n = n*10+7;
        n%=k;
    }
    return 0;
}


Measured memory_bytes: 3824
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000;
int n, m, a[maxn + 10], cnt[maxn + 10], cov[maxn + 10], ans;

void modify(int p, int v) {
	if (p >= 1) {
		ans -= !!cov[p];
		ans += !!(cov[p] += v);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		modify(a[i] - (cnt[a[i]]++), 1);
	}
	while (m--) {
		int x, y; scanf("%d%d", &x, &y);
		modify(a[x] - (--cnt[a[x]]), -1);
		a[x] = y;
		modify(y - (cnt[y]++), 1);
		printf("%d\n", n - ans);
	}
}


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

using namespace std;

int a[100001];

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



Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define per(i,n) for(int i=n-1;i>=0;++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)
#define per1(i,n) for(int i=n; i>=1; ++i)
#define debug cout << "line : " << __LINE__ << " debug" << endl
#define Dcout(N) cout << setprecision(20) << N << endl
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF 1e9
const int mod = 1000000007;
typedef long long ll;
//------------------------------------------------------------------------

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

  int n; cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  sort(all(a));
  rep(i,n-1){
    if(a[i]==a[i+1]){
      cout << "NO" << endl;
      return 0;
    }
  }
  
  cout << "YES" << endl;

  return 0;
}




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

int n,cnt,k,sum;
int main(){
	while(1){
		cin >>n;
		if(n==0)break;
		cnt=0;
		k=0;
		sum=0;
		while(1){
			if(n<sum)break;
			k++;
			sum+=k;
		}
		for(int i=2;i<k;i++){
			if(i%2==0){
				if(n%i==i/2)cnt++;
			}else{
				if(n%i==0)cnt++;
			}
		}
		cout <<cnt <<endl;
	}
	return 0;
}

Measured memory_bytes: 3000
package main

import (
	"fmt"
	"math"
)

func getMin(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

var N int
var values []int
var height []int

func getMinValues(i int) int {
	value1 := values[i-1] + abs(height[i]-height[i-1])
	value2 := values[i-2] + abs(height[i]-height[i-2])
	return getMin(value1, value2)
}

func main() {
	fmt.Scan(&N)
	height = make([]int, N)
	var tmp int
	for i := 0; i < N; i++ {
		fmt.Scan(&tmp)
		height[i] = tmp
	}
	values = make([]int, N)
	values[0] = 0
	values[1] = abs(height[1] - height[0])
	for i := 2; i < N; i++ {
		values[i] = getMinValues(i)
	}
	fmt.Println(values[N-1])
}


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


def reconstruction(n, preorder, inorder):
    result = []

    def rec(preorder, inorder):
        if preorder == [] or inorder == []:
            pass
        else:
            index = inorder.index(preorder[0]) + 1
            rec(preorder[1:index], inorder[0:index-1])
            rec(preorder[index:], inorder[index:])
            result.append(str(preorder[0]))

    rec(preorder, inorder)
    print(" ".join(result))


if __name__ == "__main__":
    n = int(input())
    preorder = [int(x) for x in input().split()]
    inorder = [int(x) for x in input().split()]
    reconstruction(n, preorder, inorder)

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

bool iscat(const string& S) {
    vector<vector<int>> mem(S.size(), vector<int>(S.size() + 1, -1));
    function<bool(int, int)> dfs = [&](int p, int l) {
        if (l <= 0) return true;
        if (S[p] != 'm' || S[p + l - 1] != 'w') return false;
        if (mem[p][l] != -1) return mem[p][l] == 1;
        rep(i, l) if (S[p + i] == 'e') {
            if (dfs(p + 1, i - 1) && dfs(p + i + 1, l - i - 2)) return mem[p][l] = 1, true;
        }
        mem[p][l] = 0;
        return false;
    };
    return dfs(0, S.size());
}

int main() {
    string S; cin >> S;
    cout << (iscat(S) ? "Cat" : "Rabbit") << endl;
}

Measured memory_bytes: 3972
A, B, K = list(map(int, input().split()))

if A > 0:
    if A <= K:
        K = K-A
        A = 0
       
    else:
        A = A-K
        K = 0
    
if A==0 and B > 0 and K > 0:
    if B <= K:
        B = 0
    else:
        B = B-K
  
print(str(A)+" "+str(B))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
 int main()
 {
     long long  t, n, k, x;
     cin>>n>>x>>t;
      long long  c = n / x;
      if(n % x !=0)
          c++;
      cout<<c * t<<"\n";
     return 0;
     
 }

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

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<vector<int>> card(K, vector<int>(N/2));
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < N/2; j++) {
            cin >> card[i][j];
            card[i][j]--;
        }
    }
    
    random_device rd;
    mt19937 mt(rd());
    bool finished = 0;
    while (!finished) {
        finished = 1;
        
        vector<int> seq(N);
        for (int i = 0; i < N; i++) {
            seq[i] = mt() % 2;
        }
        
        for (int i = 0; i < K; i++) {
            int sum = 0;
            for (int j = 0; j < N/2; j++) {
                sum += seq[card[i][j]];
            }
            if (sum < N/8 || sum > 3*N/8) {
                finished = 0;
                break;
            }
        }

        if (finished) {
            for (int i = 0; i < N; i++) {
                cout << seq[i];
            }
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3892
import java.util.Scanner;

public  class Main{
	public static void main(String[] args){
	Scanner stdIn = new Scanner(System.in);
	int n = stdIn.nextInt();
	int x = stdIn.nextInt();
	int t = stdIn.nextInt();
	if(n%x == 0){
	System.out.println(n/x*t);
}
else {System.out.println((n/x+1)*t);}
}
}

Measured memory_bytes: 35588
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <cmath>
#include <numeric>
#include <functional>
#include <stack>
#include <iomanip>
#include <map>
#include <cstdio>

int main() {
	std::string s;

	std::cin >> s;

	int a = std::count(s.begin(), s.end(), 'a');
	int b = std::count(s.begin(), s.end(), 'b');
	int c = std::count(s.begin(), s.end(), 'c');

	if (a == b) {
		if (c - 1 == a || c + 1 == a || c == a) {
			std::cout << "YES" << std::endl;
		}
		else {
			std::cout << "NO" << std::endl;
		}
	}
	else if (a == c) {
		if (b - 1 == a || b + 1 == a || b == a) {
			std::cout << "YES" << std::endl;
		}
		else {
			std::cout << "NO" << std::endl;
		}
	}
	else if (b == c) {
		if (a - 1 == b || a + 1 == b || a == b) {
			std::cout << "YES" << std::endl;
		}
		else {
			std::cout << "NO" << std::endl;
		}
	}
	else {
		std::cout << "NO" << std::endl;
	}

	return 0;
}


Measured memory_bytes: 512
from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)

directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in range(-2, 3):
                for g in range(-2, 3):
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        dist[h][w] = cost
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))

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

int main(){
  int N;
  char S;
  string M = "Three";
  
  cin >> N;
  
  for(int i = 0 ; i < N ; i++){
    cin >> S;
    if(S == 'Y'){
      M = "Four";
      break;
    }
  }
  
  cout << M << endl;
  
}

Measured memory_bytes: 256
VAR N,i,j,count,kq:INTEGER;
begin
 readln(n);
 i:=1;
 if n < 105 then writeln('0') else
 if n = 105 then writeln('1') else 
 begin
   while i <= n do 
    begin
    count:=0;
    for j:=1 to n do 
     if i mod j = 0 then inc(Count);
    if count = 8 then inc(kq);
    inc(i,2);
    end;
  writeln(kq);
 end;
 end.

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

const int MAXN = 105;
int n, a[MAXN];
long long A, r, ans;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i], A += a[i];
	ans = A;
	for (int i = 0; i < n; i++) {
		r += a[i];
		ans = min(ans, abs(r - (A - r)));
	}
	cout << ans;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

int dp[50][410][410];

int main()
{
	int n,ma,mb;
	cin >> n >> ma >> mb;
	vi a(n),b(n),c(n);
	rep(i,n) cin >> a[i] >> b[i] >> c[i];

	rep(i,50) rep(j,410) rep(k,410) dp[i][j][k] = INF;
	dp[0][0][0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 410; j++){
			for(int k = 0; k < 410; k++){
				if(dp[i][j][k] != 1e5){
					dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
					dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][k]);
				}
			}
		}
	}
	int ans = INF;
	for(int j = 1; j < 410; j++){
		for(int k = 1; k < 410; k++){
			if(j*mb == k*ma) ans = min(ans,dp[n][j][k]);
		}
	}
	cout << (ans == INF ? -1 : ans) << endl;
	return 0;
}

Measured memory_bytes: 33024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int h, w;
    cin >> h >> w;
    vector<string> a(h);
    rep(i, h) cin >> a[i];
    
    const int di[] = {1, 0, -1, 0};
    const int dj[] = {0, 1, 0, -1};

    rep(i, h) rep(j, w) {
        if (a[i][j] == '#') {
            bool ok = false;
            rep(k, 4) {
                int ni = i + di[k];
                int nj = j + dj[k];
                if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
                if (a[ni][nj] == '#') ok = true;
            }
            if (!ok) {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    
}


Measured memory_bytes: 3668
from itertools import product
n, m = map(int,input().split())
S = []
for i in range(m):
    s = list(map(int,input().split()))
    S.append(s[1:])
p = list(map(int,input().split()))
ans = 0
for c in product([0, 1], repeat = n):
    ok = True
    for j in range(m):
        sm = 0
        for k in S[j]:
            sm += c[k-1]
        if sm % 2 != p[j]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)
    
            




Measured memory_bytes: 9164
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0].split(" ")[0]);
  var K = parseInt(input[0].split(" ")[1]);
  var S = input[1].split("");
  var cnt=0;
  var queue=[0];
  var ans=0;
  for(var i=0;i<N;i++){
    if(i==N-1){
      if(S[i]==1){
        ans=Math.max(ans,i-queue[0]+1);
      }else{
        if(S[i]!=S[i-1]){
          if(cnt>=K){
            ans=Math.max(ans,i-queue[0]);
            queue.shift();
          }else{
            ans=Math.max(ans,i-queue[0]+1);
          }
        }else{
          ans=Math.max(ans,i-queue[0]+1);
        }
      }
    }else if(i==0){
      if(S[i]==0){
        cnt++;
      }
    }else if(S[i]==0&&S[i]!=S[i-1]){
      if(cnt>=K){
        ans=Math.max(ans,i-queue[0]);
        queue.shift();
      }else{
        cnt++;
      }

    }else if(S[i]==1&&S[i]!=S[i-1]){
      queue.push(i);
    }
  }

  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

typedef long long LL;
typedef pair<LL,LL> PII;

const int MAXN = 200000;
vector<int> group[MAXN];
int main() {
	int N,M;
	
	vector<int> input;
	cin >> N >> M;
	for(int i=0; i<N; i++) {
		int x;
		cin >> x;
//		input.push_back(x);
		group[x%M].push_back(x);
	}
	for(int i=0; i<MAXN; i++)
		sort(group[i].begin(), group[i].end());
	vector<int> pair(MAXN, 0);
	
	for(int i=0; i<MAXN; i++) {
		bool flag = false;
		for(int j=0; j<group[i].size(); j++) {
			if(flag) {
				if(group[i][j] == group[i][j-1]) pair[i]++, flag = false;
				else flag = true;
			}
			else flag = true;
		}
		
	}
	
	int ans = 0;
	
	for(int i=0; i<=M/2; i++) {
		if( (i + i) % M == 0) {
			ans += group[i].size() - group[i].size() % 2 ;
			
			continue;
		}
		int p = group[i].size();
		int q = group[M-i].size();
		
		int score = min(p,q) * 2;;
		
		if(p>q) {
			if(p-q < 2 * pair[i]) score = p+q - (p+q)%2;
			else score += pair[i] * 2;
		}
		else {
			if(q-p < 2 * pair[M-i]) score = p+q - (p+q)%2;
			else score += pair[M-i] * 2;
		}
		ans += score;
//		cout << ans << endl;
	}
	//for(int i=0; i<M; i++) cout << pair[i] << endl;
	
	cout << ans / 2 << endl;
	return 0;
}



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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
constexpr int INF = 1001001001;
//constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;

struct UnionFind {
    vector<int> par, rank;
    int count_comp;

    UnionFind(int n) : par(n , -1), rank(n, 0),count_comp(n) { }

    int root(int x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        count_comp--;
        return true;
    }
};

int main() {
    ll N, M, Q; cin >> N >> M >> Q;
    int a, b, c;
    set<pii> sing, dob;
    rep(i, Q) {
        cin >> a >> b >> c;
        if(a > b) swap(a,b);

        if (c == 0) sing.insert(mp(a, b));
        else dob.insert(mp(a, b));
    }

    if (M == N - 1) {
        cout << (dob.empty() ? "Yes" : "No" ) << endl;
        return 0;
    }

    UnionFind uf(N);
    bool can = true;

    for (auto funi : sing) {
        a = funi.F, b = funi.S;
        /*if (uf.same(a, b)) {
            can = false;
            break;
        }
        else */uf.unite(a, b);
    }

    for (auto funi : dob) {
        a = funi.F, b = funi.S;
        if (uf.same(a, b)) {
            can = false;
            break;
        }
    }

    ll num = uf.count_comp;
    if (M > N - num + num * (num - 1) / 2 ) can = false;

    cout << (can ? "Yes" : "No") << endl;

}


Measured memory_bytes: 5760
use std::collections::HashMap;

fn main() {
    let _ = read::<usize>();
    let mut v = read_vec::<usize>();
    v.sort();
    
    const LIMIT: usize = 2000000;

    let mut map = HashMap::new();
    for x in v.iter() {
        let entry = map.entry(x.clone()).or_insert(0);
        *entry += 1;
    }

    let mut memo = vec![false; LIMIT];
    let mut ret = 0;
    for x in v.iter() {
        if memo[*x] {
            continue;
        }

        if map[x] == 1 {
            ret += 1;
        }

        let mut tmp = *x;
        while tmp < LIMIT {
            memo[tmp] = true;
            tmp += *x;
        }
    }
    println!("{}", ret);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 12300
#include <stdio.h>
#include <stdlib.h>

int main()
{ long long int num;
  scanf("%lld", &num);
  long long int total=0.5*num*(num+1);
  long long int mod3= num/3;
  long long int mod5= num/5;
  long long int mod15= num/15;

  long long int sum15=0.5*(mod15)*(30+15*(mod15-1));
  long long int sum3=(0.5*(mod3)*(6+3*(mod3-1)))-sum15;
  long long int sum5=(0.5*(mod5)*(10+5*(mod5-1)))-sum15;

  long long int ans = total - sum3 -sum5 -sum15;
  printf("%lld", ans);

  return 0;
}

Measured memory_bytes: 1736
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 998244353
nums = 2*(10**5) # 制約に合わせよう
g1, g2, inverse = [1, 1] , [1, 1], [0, 1]
 
for num in range(2, nums + 1):
    g1.append((g1[-1] * num) % mod)
    inverse.append((-inverse[mod % num] * (mod//num)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n, m, k = map(int, input().split())
ans = 0
for i in range(k+1):
    ans += m*cmb(n-1, i, mod)*pow(m-1, n-i-1, mod)
    ans %= mod
print(ans)



Measured memory_bytes: 32752
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author Silviase
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    Scanner in = new Scanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    ECrestedIbisVsMonster solver = new ECrestedIbisVsMonster();
    solver.solve(1, in, out);
    out.close();
  }

  static class ECrestedIbisVsMonster {

    public void solve(int testNumber, Scanner in, PrintWriter out) {
      int h = in.nextInt();
      int n = in.nextInt();
      int[] atk = new int[n];
      int[] mag = new int[n];
      // x減らすための最小の魔法消費
      int[] dp = new int[h + 1];
      for (int i = 0; i < n; i++) {
        atk[i] = in.nextInt();
        mag[i] = in.nextInt();
      }
      for (int i = 0; i < h + 1; i++) {
        dp[i] = (int) 1e9;
      }

      dp[0] = 0;

      for (int i = 0; i < n; i++) {
        for (int j = 0; j < h + 1; j++) {
          if (atk[i] > j) {
            dp[j] = Math.min(dp[j], mag[i]);
          } else {
            dp[j] = Math.min(dp[j], mag[i] + dp[j - atk[i]]);
          }
        }
      }

      out.println(dp[h]);
    }

  }
}



Measured memory_bytes: 29416
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(void){
  int data;
  cin >> data;
  int w = data/1000;
  int x = (data - w*1000)/100;
  int y = (data - w*1000 - x*100)/10;
  int z = data - w*1000 - x*100 - y*10;
  if (x == y){
    if (w == x || y == z){
      cout << "Yes";
      return 0;
    }
  }
  cout << "No";
  return 0;
}

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

int main(){
  int aa[8][8]={ {0,1,2,3,4,5,6,7},
                 {1,0,300,500,600,700,1350,1650},
		 {2,300,0,350,450,600,1150,1500},
	         {3,500,350,0,250,400,1000,1350},
	       	 {4,600,450,250,0,250,850,1300},
	       	 {5,700,600,400,250,0,600,1150},
	       	 {6,1350,1150,1000,850,600,0,500},
	       	 {7,1650,1500,1350,1300,1150,500,0}};
  int bb[8][8]={ {0,1,2,3,4,5,6,7},
		 {1,0,6,13,18,23,43,58},
		 {2,6,0,7,12,17,37,52},
		 {3,13,7,0,5,10,30,45},
		 {4,18,12,5,0,5,25,40},
		 {5,23,17,10,5,0,20,35},
		 {6,43,37,30,25,20,0,15},
		 {7,58,52,45,40,35,15,0}};

  int i,j,n,time00,time01,time10,time11,n2,disc,mo;
  int disc2;
  while(1){
    disc2=0;
    disc=0; //flag
    cin >> n;
    if(n == 0)break;
    cin >> time00 >> time01;
    cin >> n2;
    cin >> time10 >> time11;

   
    if((time10 == 19 && time11 <= 30) || (time00 == 19 && time01 <=30)){disc2=1;}
      else if(time00 == 18 || time10 == 18)disc2=1;
      else if((time10 == 17 && time11>=30) || (time00 == 17 && time01 >=30))disc2=1;
      if(bb[n2][n]<=40 && disc2==1)disc=1; 
   

    mo=aa[n][n2];
    if(disc == 1){
      mo=mo/2;
      disc=0;
      disc2=0;
       if(mo%50 !=0)mo=(mo-(mo%50))+50;
    }
    cout << mo << endl;


    }
  return 0;

}

Measured memory_bytes: 0
#include<iostream>
#include <algorithm>
#include <string>
using namespace std;
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(int)(n); i++)
typedef long long ll;
const int INF = numeric_limits<int>::max();
const int MOD = (1e9 + 7);


int main(){
  int N; cin >> N; ll a[N];
  rep(i, N){
    cin >> a[i];
  }
  ll b[N]  = {};
  rep(i, N){
    if((N%2) == (i%2)) b[(i+N)/2] = a[i];
    else b[(N-i)/2] = a[i];
  }
  rep(i, N){
    cout << b[i] << endl;
  }
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define lli long long int
#define f(i,a,b) for(i=a;i<b;i++)
#define ff first
#define sc second
#define pb push_back
#define full(v) v.begin(),v.end()
#define ms(a) memset(a,0,sizeof(a))
#define mod 1000000007
#define mod2 998244353
#define msb(b) memset(b,true,sizeof(b))
#define msf(b) memset(b,false,sizeof(b))
#define MAXN 100005

int main()
{
    fio;
    int n,i;
    cin >> n;
    lli a[n], x = 0;
    vector<lli> res(n,-1);
    f(i,0,n)  
      cin >> a[i];
    f(i,0,n)
      x ^= a[i];
    f(i,0,n)
      res[i] = x ^ a[i];
    f(i,0,n)
      cout << res[i] << " ";
}


Measured memory_bytes: 6300
/*
      author  : nishi5451
      created : 14.08.2020 19:33:29
*/

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


int main(){
    string s,t;
    cin >> s >> t;
    int len = s.size();
    for(int i=0; i<len; i++){
        string rot;
        rot=s.substr(i,len);
        if(rot==t){
            cout << "Yes" << endl;
            return 0;
        }
        s.push_back(s[i]);
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3604
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, D, A = MAP()
XH = [LIST() for _ in range(N)]

XH.sort(key = lambda x: x[0])

X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

ans = 0
imos = [0]*(N+1)
tmp = 0
for i in range(N):
	x, h = XH[i]
	tmp += imos[i]
	left = h-tmp
	if 0 < left:
		cnt = -(-left//A)
		damage = A*cnt
		idx = bisect(X, x+2*D)
		tmp += damage
		imos[idx] -= damage
		ans += cnt

print(ans)



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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  // Including tree_order_statistics_node_update

using namespace __gnu_pbds;
using namespace std;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c), x) != (c).end())
#define minei(x) min_element(x.begin(), x.end()) - (x).begin()
#define maxei(x) max_element(x.begin(), x.end()) - (x).begin()
#define LSOne(S) (S & (-S))

#define uns(v) sort((v).begin(), (v).end()), v.erase(unique(v.begin(), v.end()), v.end())
#define acusum(x) accumulate(x.begin(), x.end(), 0)
#define acumul(x) accumulate(x.begin(), x.end(), 1, multiplies<int>());
#define bits(x) __builtin_popcount(x)
#define oo INT_MAX
#define inf 1000000000
#define MAXN 1000007
#define MOD 1000000007

const double pi = acos(-1.0);
const double eps = 1e-11;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int X, Y, A, B, C, nm;
    ll res = 0;
    priority_queue<int, vector<int>, greater<int> > Red;
    priority_queue<int, vector<int>, greater<int> > Green;
    priority_queue<int> ColorLess;
    cin >> X >> Y >> A >> B >> C;
    for (int i = 0; i < A; i++) {
        cin >> nm;
        Red.push(nm);
        if (sz(Red) > X) Red.pop();
    }
    for (int i = 0; i < B; i++) {
        cin >> nm;
        Green.push(nm);
        if (sz(Green) > Y) Green.pop();
    }
    for (int i = 0; i < C; i++) {
        cin >> nm;
        ColorLess.push(nm);
    }

    for (int i = 0; i < C; i++) {
        if (sz(Red) < X) {
            Red.push(ColorLess.top());
            ColorLess.pop();
        } else if (sz(Green) < Y) {
            Green.push(ColorLess.top());
            ColorLess.pop();
        }
    }
    while (!ColorLess.empty()) {
        int tp = ColorLess.top();
        ColorLess.pop();
        if (Red.top() <= Green.top()) {
            if (Red.top() < tp) {
                Red.pop();
                Red.push(tp);
            } else
                break;
        } else if (Green.top() < Red.top()) {
            if (Green.top() < tp) {
                Green.pop();
                Green.push(tp);
            } else
                break;
        }
    }
    while (!Green.empty()) {
        res += Green.top();
        Green.pop();
    }
    while (!Red.empty()) {
        res += Red.top();
        Red.pop();
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define END return 0
typedef int64_t ll;
const int mod7 = 1e9 + 7;
const int mod9 = 1e9 + 9;
const int inf = 1 << 30;
const ll INF = 1LL << 60;
template<typename T> T gcd(T a, T b) {return b ? gcd(b, a % b) : abs(a);}
template<typename T> T lcm(T a, T b) {return a / gcd(a, b) * b;}
template<typename T> bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}
template<typename T> bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) {fill((T*)array, (T*)(array+N), val);}

int main() {
    int h, a;
    cin >> h >> a;
    cout << (h + a - 1) / a << endl;
}

Measured memory_bytes: 256
from heapq import heappop as hpop, heappush as hpush
def da (s, t, L, n):
	PreV = [None for i in range(n+1)]
	D = [float("inf") for i in range(n+1)]
	Q = list()
	PreV[s] = (0,0)
	D[s] = 0
	hpush(Q, (0,s))
	lenQ = 1
	while lenQ > 0:
		tmp = hpop(Q)
		lenQ -= 1
		for v in L[tmp[1]] :
			tmpd = tmp[0] + v[0]
			if tmpd < D[v[1]]:
				D[v[1]] = tmpd
				hpush(Q, (tmpd, v[1]))
				PreV[v[1]] = (tmpd, tmp[1])
				lenQ += 1
	return PreV

while 1:
	w,h = map(int,raw_input().split())
	if (w,h) == (0,0):
		break
	L = [[] for i in range(w*h)]
	for j in range(h * 2 - 1):
		wall = map(int,raw_input().split())
		if j % 2 == 0:
			for i in range(w-1):
				if wall[i] == 0:
					L[i+w*j/2].append((1,i+w*j/2+1))
					L[i+w*j/2+1].append((1,i+w*j/2))
		else :
			for i in range(w):
				if wall[i] == 0:
					L[i+w*(j-1)/2].append((1,i+w*(j-1)/2+w))
					L[i+w*(j-1)/2+w].append((1,i+w*(j-1)/2))
	route = da(0, w*h-1, L, w*h)
	print 0 if route[w*h-1] is None else route[w*h-1][0]+1

Measured memory_bytes: 5088
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  double xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2;
  while(cin>>xa1>>ya1>>xa2>>ya2>>xb1>>yb1>>xb2>>yb2){
    if((max(xb1,xb2)-min(xa1,xa2))*(max(xa1,xa2)-min(xb1,xb2))>=0&&(max(yb1,yb2)-min(ya1,ya2))*(max(ya1,ya2)-min(yb1,yb2))>=0) cout<<"YES"<<endl;
    else
      cout<<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
 int s;
 cin >> s;
  
 if ( s==107 ||s==117 ||s==127 ||s==137 ||s==147 ||s==157 || s==167 ||s==187 ||s==197 ||
      (s>=170 && s<=179) ||
      s==207 ||s==217 ||s==227 ||s==237 ||s==247 ||s==257 ||s==267 ||s==287 ||s==297 || 
      (s>=270 && s<=279) ||
      s==307 ||s==317 ||s==327 ||s==337 ||s==347 ||s==357 ||s==367 ||s==387 ||s==297 ||
      (s>=370 && s<=379) ||
      s==407 ||s==417 ||s==427 ||s==437 ||s==447 ||s==457 ||s==467 ||s==487 ||s==497 ||
      (s>=470 && s<=479) ||
      s==507 ||s==517 ||s==527 ||s==537 ||s==547 ||s==557 ||s==567 ||s==587 ||s==597 ||
      (s>=570 && s<=579) ||
      s==607 ||s==617 ||s==627 ||s==637 ||s==647 ||s==657 ||s==667 ||s==687 ||s==697 ||
      (s>=670 && s<=679) ||
      (s>=700 && s<=799) ||
      s==807 ||s==817 ||s==827 ||s==837 ||s==847 ||s==857 ||s==867 ||s==887 ||s==897 ||
      (s>=870 && s<=879)||
      s==907 ||s==917 ||s==927 ||s==937 ||s==947 ||s==957 ||s==967 ||s==987 ||s==997 ||
      (s>=970 && s<=979)
     ) { 
  cout << "Yes" << endl; 
  }
 
  else {
  cout << "No" << endl;
  }
}

Measured memory_bytes: 3640
import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

  final int N = sc.nextInt();
  final int K = sc.nextInt();
  final String baseK = Integer.toString(N,K);
  
  System.out.println(baseK.length());
  
	}
}

Measured memory_bytes: 23892
import java.util.*;

public class Main {
    static int[][] mp;
    static int H, W;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        W = sc.nextInt();
        mp = new int[H][];
        Set<Integer> visited = new HashSet<>();
        for(int i=0;i<H;i++){
            String s = sc.next();
            mp[i] = new int[W];
            char[] sca = s.toCharArray();
            for(int j=0;j<W;j++)
                mp[i][j] = sca[j] == '#' ? 1 : 0;
        }
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingInt(obj->obj.fc));
        pq.add(new State(0,0,0, mp[0][0]));
        visited.add(key(0,0));
        int first = mp[0][0];
        while(!pq.isEmpty()){
            State st = pq.poll();
            visited.add(key(st.y, st.x));
            if(st.y==H-1 && st.x==W-1){
                System.out.println(st.fc + first);
                return;
            }
            if(st.y+1 < H){
                int add=0;
                if(st.isBlk==0 && mp[st.y+1][st.x]==1)
                    add=1;
                if(!visited.contains(key(st.y+1, st.x)))
                    pq.add(new State(st.x, st.y + 1, st.fc+add, mp[st.y + 1][st.x]));
            }
            if(st.x+1 < W){
                int add=0;
                if(st.isBlk == 0 && mp[st.y][st.x+1] == 1)
                    add=1;
                if(!visited.contains(key(st.y, st.x+1)))
                    pq.add(new State(st.x+1, st.y, st.fc + add, mp[st.y][st.x+1]));
            }
        }

    }
    private static int key(int h, int w){
        return h*100+w;
    }

    private static class State{
        int x,y;
        int fc;
        int isBlk;
        State(int x, int y, int fc, int isBlk){
            this.x = x;
            this.y = y;
            this.fc = fc;
            this.isBlk = isBlk;
        }
    }
}


Measured memory_bytes: 31684
#include <stdio.h>
int abs(int n){
		if(n<0){
		return -1*n;}else
		return n;}
long long int kaizyou_amari(int n){
	long long int i,sum;
	sum=1;
	for(i=1;i<=n;i++){
		sum*=i;
		if(sum>=1000000007){
			sum%=1000000007;}
	}
	return sum;}
			
int main(void)
{int N,A,M,B,i,k,l,m,flag,sum;
	long long int x;
	scanf("%d%d",&N,&M);
	int a[100000];
	int b[100000];
	int c[50];
	int d[50];
	int tmp[50];
	b[0]=1;
	flag=0;
	if(N==M){
		x=kaizyou_amari(N)*kaizyou_amari(M);
		x%=1000000007;
		x=(x*2)%1000000007;
		printf("%lld",x);}
	else if((N==M-1)||(N==M+1)){
		x=kaizyou_amari(N)*kaizyou_amari(M);
		x%=1000000007;
		printf("%lld",x);}
		else
		printf("0");



	return 0;
}


Measured memory_bytes: 128
from fractions import Fraction

N = input()
T, A = map(int, raw_input().split())
H = map(int, raw_input().split())

v = float('inf')
x = -1

for i in xrange(N):
    vv = T - H[i] * Fraction(6, 1000)
    vvv = abs(A - vv)
    if vvv < v:
        v = vvv
        x = i

print x + 1


Measured memory_bytes: 4392
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int main(){
    long long n,m;cin>>n>>m;
    long long res = 1;
    for(int i=1;i<=n;i++){
        res*=i;
        res%=mod;
    }
    for(int i=1;i<=m;i++){
        res*=i;
        res%=mod;
    }
    if(n==m){
        res*=2;
        res%=mod;
        cout<<res<<endl;
        return 0;
    }
    else if(n-m==1||n-m==-1){
        cout<<res<<endl;
        return 0;
    }
    else{
        cout<<"0"<<endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
const int MOD = 1000000007;
ll cnt =0;

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

   int a[n+1];
   for(int i=0;i<n;i++){
       cin >> a[i];
   }
   a[n]=k+a[0];
   int max =0;
   for(int i=0;i<n;i++){
       
       if(a[i+1]-a[i] > max){
           max = a[i+1] - a[i];
       }

   }
   cout << k - max << endl;

}

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        dd[A[i]]+=1
        
    ans=sum(A)
        
    Q=I()
    for i in range(Q):
        b,c=MI()
        cnt=dd[b]
        ans=ans+cnt*(c-b)
        print(ans)
        dd[c]+=cnt
        dd[b]=0

        
    
    

main()


Measured memory_bytes: 93800
n = gets.chomp.to_i
b = gets.chomp.split.map(&:to_i)

ans_arr = []
n.times do |i|
    if i == 0 
        ans_arr.push(b[0])
        next
    elsif i == n-1
        ans_arr.push(b[i-1])
        break
    end
    if b[i-1] < b[i]
        ans_arr.push(b[i-1])
    else
        ans_arr.push(b[i])
    end
end
p ans_arr.inject(:+)

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9+3;
const ll INF = 1e18+3;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<ll mod> struct Mod_Int{
    ll x;
    Mod_Int() {}
    Mod_Int(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod){}

    Mod_Int &operator += (const Mod_Int &p) {
        x = (x + p.x) % mod;
        return *this;
    }

    Mod_Int &operator -= (const Mod_Int &p) {
        x = (x + mod - p.x) % mod;
        return *this;
    }

    Mod_Int &operator *= (const Mod_Int &p) {
        x = (x * p.x) % mod;
        return *this;
    }

    Mod_Int &operator /= (const Mod_Int &p) {
        *this *= p.inverse();
        return *this;
    }

    Mod_Int operator -() const {return Mod_Int(-x);}

    Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}

    Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}

    Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}

    Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}

    bool operator == (const Mod_Int &p) const {return x == p.x;}

    bool operator != (const Mod_Int &p) const {return x != p.x;}

    Mod_Int pow(ll n) const{
        Mod_Int now = *this, ret = 1;
        while(n > 0){
            if(n & 1) ret *= now;
            now *= now, n >>= 1;
        }
        return ret;
    }

    Mod_Int inverse() const{
        return pow(mod-2);
    }
};

using mint = Mod_Int<MOD>;
const int MAX_N = 3e6;
mint fac[MAX_N+1];

void init(){
    fac[0] = 1;
    rep2(i, 1, MAX_N){
        fac[i] = fac[i-1]*mint(i);
    }
}

mint comb(mint n, mint k){
    return fac[n.x]/(fac[n.x-k.x]*fac[k.x]);
}

mint perm(mint n, mint k){
    return fac[n.x]/fac[n.x-k.x];
}

int main(){
    init();
    int r[2], c[2];
    rep(i, 2) cin >> r[i] >> c[i];
    r[1]++, c[1]++;
    mint ans = 0;
    ans += comb(r[1]+c[1], r[1])-1;
    ans -= comb(r[1]+c[0], r[1])-1;
    ans -= comb(r[0]+c[1], r[0])-1;
    ans += comb(r[0]+c[0], r[0])-1;
    cout << ans.x << endl;
}

Measured memory_bytes: 23680
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>

using namespace std;
vector<string> split(string str, char del);

int main() {
	string s;
	cin >> s;
	int n[4] = { s[0],s[1],s[2],s[3] };
	int c[4] = { 0 };

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (n[i] == n[j]) {
				c[i]++;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		if (!(c[i] == 0 || c[i] == 2)) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}




vector<string> split(string str, char del) {
	vector<string> result;
	string subStr;

	for (const char c : str) {
		if (c == del) {
			result.push_back(subStr);
			subStr.clear();
		}
		else {
			subStr += c;
		}
	}

	result.push_back(subStr);
	return result;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	long long ans=0,dem=0;
	if(s.length()<3) printf("0");
	else{
		for(int i=0;i<s.length()-1;i++){
			if(s[i]=='A') dem++;
			else if(s[i]=='B'&&s[i+1]=='C'){
				ans+=dem;
				i++;
			}
			else dem=0;
		}
		printf("%lld",ans);
	}
}

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

int main () {
  int m1, m2, d1, d2; 
  cin >> m1 >> d1 >> m2 >> d2; 
  if (m2 == 1 && m1 == 12) {
    if ((m2 - m1) % 12 == 1) {
      cout << 1 << endl;
      return 0;
    }   
  } else {
    if (m2 > m1 && (m2 - m1) % 12 == 1) {
      cout << 1 << endl;
      return 0;
    }   
  }
  cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
h, w = list(map(int, input().split()))
grid = [input() for _ in range(h)]

dp = [[10000]*w for _ in range(h)]
dp[0][0] = 0 if grid[0][0] == "." else 1

for i in range(h):
    for j in range(w):
        if i > 0:
            if grid[i][j] == "#" and grid[i-1][j] == ".":
                dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j > 0:
            if grid[i][j] == "#" and grid[i][j-1] == ".":
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
            else:
                dp[i][j] = min(dp[i][j], dp[i][j-1])

print(dp[h-1][w-1])

Measured memory_bytes: 9320
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = 2005;
long long a[2 * N];


int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n;
    long long x;
    scanf("%d%lld", &n, &x);

    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        a[n + i] = a[i];
    }

    long long ans = 0;
    for (int i = 0; i < n; i++)
        ans += a[i];

    for (int sh = 1; sh < n; sh++)
    {
        long long cur = sh * x;
        multiset <long long> s;

        for (int i = 0; i < sh; i++)
            s.insert(a[n - 1 - i]);

        for (int i = n; i < 2 * n; i++)
        {
            s.insert(a[i]);
            cur += *s.begin();
            s.erase(s.find(a[i - sh]));
        }
        ans = min(ans, cur);
    }
    printf("%lld\n", ans);

	return 0;
}




Measured memory_bytes: 384
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int> 
#define vi vector<int> 
#define FOR(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define fi first
#define se second
using namespace std;
void solve()
{
	int n;
	cin>>n;
	vector<int> sum,diff;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		sum.pb(x+y);
		diff.pb(x-y);
		
	}
	sort(all(sum));
	sort(all(diff));
	cout<<max({abs(sum[n-1]-sum[0]),abs(diff[n-1]-diff[0])});
}
int32_t main()
{
	//freopen("shell.in", "r", stdin);
	//freopen("shell.out", "w", stdout);
	int t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}
// Problem : E - Dist Max
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)



Measured memory_bytes: 6644
#include<iostream>
#include<stdlib.h>
#include<limits.h>
int main()
{
	int n,x[20],i,j,a,b,r,t;
	struct S{int a,b;};
	static S s[2097152];
	while(std::cin>>n,n)
	{
		for(a=b=i=0;i<n;++i)std::cin>>x[i];
		s[0].a=s[0].b=0;
		for(i=0;i<n;++i)for(j=(1<<i)-1;j<(1<<(i+1))-1;++j)
		{
			s[j*2+1]=s[j],s[j*2+1].a+=x[i];
			s[j*2+2]=s[j],s[j*2+2].b+=x[i];
		}
		for(r=INT_MAX,i=(1<<n)-1;i<(1<<(n+1))-1;++i)
			t=abs(s[i].a-s[i].b),r=(r<t?r:t);
		std::cout<<r<<'\n';
	}
	return 0;
}

Measured memory_bytes: 16000
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static HashMap<String, Integer> map = new HashMap<String, Integer>();
	static char[] form;
	static int pos;

	public static void main(String[] args) {
		while (true) {
			String symbol = sc.next();
			if (symbol.length() > 2) break;
			map.put(symbol, sc.nextInt());
		}
		while (true) {
			String line = sc.next();
			if (line.equals("0")) break;
			form = line.toCharArray();
			int ans = solve();
			System.out.println(ans == -1 ? "UNKNOWN" : ans);
		}
	}

	static int solve() {
		pos = 0;
		HashMap<String, Integer> elem = parse();
		int sum = 0;
		for (String symbol : elem.keySet()) {
			if (!map.containsKey(symbol)) return -1;
			sum += elem.get(symbol) * map.get(symbol);
		}
		return sum;
	}

	static HashMap<String, Integer> parse() {
		HashMap<String, Integer> ret = new HashMap<String, Integer>();
		while (pos < form.length) {
			if (form[pos] == '(') {
				++pos;
				HashMap<String, Integer> sub = parse();
				int mul = parseInt();
				for (String symbol : sub.keySet()) {
					int cur = ret.containsKey(symbol) ? ret.get(symbol) : 0;
					ret.put(symbol, cur + sub.get(symbol) * mul);
				}
			} else if (form[pos] == ')') {
				++pos;
				break;
			} else {
				String symbol = "" + form[pos];
				++pos;
				if (pos < form.length) {
					if ('a' <= form[pos] && form[pos] <= 'z') {
						symbol += form[pos];
						++pos;
					}
				}
				int mul = parseInt();
				int cur = ret.containsKey(symbol) ? ret.get(symbol) : 0;
				ret.put(symbol, cur + mul);
			}
		}
		return ret;
	}

	static int parseInt() {
		int ret = 0;
		while (pos < form.length && '0' <= form[pos] && form[pos] <= '9') {
			ret *= 10;
			ret += form[pos] - '0';
			++pos;
		}
		return ret == 0 ? 1 : ret;
	}

}

Measured memory_bytes: 20408