akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline

W,H,N = list(map(int,input().split()))
x0 = 0
y0 = 0
x1 = W
y1 = H

for i in range(N):
    x,y,a = list(map(int,input().split()))

    if a == 1:
        x0 = max(x,x0)
    elif a == 2:
        x1 = min(x,x1)
    elif a == 3:
        y0 = max(y,y0)
    elif a == 4:
        y1 = min(y,y1)
X = [x0,x1,y0,y1]

print(max(0,x1-x0)*max(0,y1-y0))


Measured memory_bytes: 9172
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <string.h>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

#ifndef INT_MAX
#  define INT_MAX std::numeric_limits<int>().max()
#endif
#ifndef INT_MIN
#  define INT_MIN std::numeric_limits<int>().min()
#endif
#define LL_MAX std::numeric_limits<ll>().max()
#define LL_MIN std::numeric_limits<ll>().min()
#define INF LL_MAX

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
// 配列の初期化
#define ZERO(p) memset(p, 0, sizeof(p))
// 配列の初期化(-1)
#define MINUS(p) memset(p, 1, sizeof(p))

#define MOD 1000000007

ll N, M;

ll factorial(ll n) {
    ll ret = 1;
    while(n >= 1) {
        ret *= n;
        ret %= MOD;
        n--;
    }
    return ret;
}

int main()
{
    cin >> N >> M;

    if( abs(N - M) > 1) {
        printf("0\n");
        return 0;
    }
    ll ret = 1;
    ret = factorial(N) * factorial(M);
    ret %= MOD;
    if( N == M ) {
        ret *= 2;
        ret %= MOD;
    }
    printf("%lld\n", ret);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
c = 0
f = 0
for i in range(n):
    d1, d2 = map(int, input().split())
    if d1 == d2:
        c += 1
    else:
        c = 0
    if c == 3:
        f = 1
if f:
    print("Yes")
else:
    print("No")

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	string s;
	cin>>s;
	if(s[s.size()-1]=='s')s+="es";
	else s+="s";
	cout<<s<<endl;
}


Measured memory_bytes: 3644
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

from math import sqrt
n = int(input())
d = [list(map(int,input().split())) for i in range(n)]

#町iと町jの距離を計算
distance_nest_list = []
for i in d:
    distance_list = []
    for j in d:
        distance_list.append(sqrt((i[0] - j[0])**2 + (i[1] - j[1])**2))
    distance_nest_list.append(distance_list)

#全経路列挙
from itertools import permutations
path_list = list(permutations(range(n),n))
path_cnt = len(path_list)

ans = 0
for path in path_list:
    for i in range(n-1):
        ans += distance_nest_list[path[i]][path[i+1]]
print(ans/path_cnt)

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

int n;
int a[100];

bool check(int x, int r)
{
	int st = 0;
	for (int i = 0; i < n; i++){
		if (a[i] > x) return false;
		if (st + a[i] > x){
			--r;
			st = 0;
		}
		st += a[i];
	}
	
	return r > 0;
}

int main()
{
	int m;
	while (scanf("%d %d", &m, &n), n){
		for (int i = 0; i < n; i++){
			scanf("%d", &a[i]);
		}
		
		int l = 1, r = 1500000;
		while (l <= r){
			int mid = (l + r) / 2;
			if (check(mid, m)) r = mid - 1;
			else l = mid + 1;
		}
		
		printf("%d\n", l);
	}
	
	return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1000000007;

int main(){
    int A,B;
    cin >> A >> B;
    if((A%2==1 and B%2==1)or(B%2==0 and A%2==0)){
        cout << (A+B)/2;
    }else{
        cout << "IMPOSSIBLE";
    }

}

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

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

  N *= 100;

  for (int i = 0; i <100; ++i) {
    if ((N + i) % 108  == 0) {
       cout << (N+i)/108 << endl;
      return 0;
    }   
  }
  cout << ":(" << endl;
                                                                                                       
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int r,c;
  while(cin>>r>>c&&r&&c){
    cout<<(r%2&&c%2?"no":"yes")<<endl;
  }
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
#define TE 2e6+5
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int N; cin >> N;
	vector<vector<ll>> cnt(64, vector<ll>(30));
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		ll temp = 0;
		int len = s.size(), tens = 0;
		bool flag = false;
		for (int j = 0; j < len; j++) {			
			if (s[j] != '.') {
				temp *= 10;
				temp += s[j] - '0';
				if (flag) tens++;
			}
			else flag = true;
			
		}
		
		for (int i = 0; i < 9 - tens; i++)temp *= 10;
		//cout << "temp=" << temp << endl;
		int two = 0, five = 0;
		while (temp % 2 == 0) {
			two++, temp /= 2;
		}
		while (temp % 5 == 0) {
			five++, temp /= 5;
		}
		cnt[two][five]++;
		//cout << "two=" << two << " five=" << five << endl;
	}

	ll ans = 0;
	for (int i = 0; i < 64; i++) {
		for (int j = 0; j < 30; j++) {
			for (int a = max(0,18 - i); a < 64; a++) {
				for (int b = max(0,18 - j); b < 30; b++) {
					ans += cnt[i][j] * (cnt[a][b] + (i == a && j == b ? -1 : 0));
					//if (cnt[i][j] > 0 && cnt[a][b])
						//cout << "i=" << i << " j=" << j << " a=" << a << " b=" << b << " ans=" << ans << endl;
				}
			}

		}
	}
	cout << ans / 2 << endl;

}


Measured memory_bytes: 3556
# AOJ 0042 A Thief
# Python3 2018.6.22 bal4u

MAX = 1003

for cno in range(1, 100):
	lim = int(input())
	if lim == 0: break
	print("Case ", cno, ":", sep='')
	N = int(input())
	vw = [(0, 0)]
	for i in range(N):
		v, w = list(map(int, input().split(',')))
		vw.append((v, w))

	V = [[0 for j in range(MAX)] for i in range(2)]
	W = [[0 for j in range(MAX)] for i in range(2)]		
	k1, k2 = 0, 1
	for i in range(1, N+1):
		for j in range(1, lim+1):
			v, w = vw[i]
			if w > j:
				V[k2][j] = V[k1][j]
				W[k2][j] = W[k1][j]
			else:
				d = j - w
				if V[k1][d] + v >= V[k1][j]:
					V[k2][j] = V[k1][d] + v
					W[k2][j] = W[k1][d] + w
				else:
					V[k2][j] = V[k1][j]
					W[k2][j] = W[k1][j]
		k1, k2 = k2, k1
	print(V[k1][lim], W[k1][lim], sep='\n')


Measured memory_bytes: 5728
main = do
  line <- getLine
  let 
    n = read line
    upmod n x
      | x < 0 = 
        let m = mod n x in 
          if m == 0 then 0
          else (-x)+m
      | otherwise = mod n x
    updiv n x
      | x < 0 =
        let u = upmod n x in
          if u == 0 then div n x
          else (div n x)+1
      | otherwise = div n x
    func n
      | n == 0 = [0]
      | n == 1 = [1]
      | otherwise = (upmod n (-2)) : (func $ updiv n (-2))
    output ls =
      putStrLn $ foldr (++) [] (map show $ reverse ls)
    in
      output $ func n


Measured memory_bytes: 508
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime> 
#include <memory.h>
#include <assert.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;

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

    cout << min(A*N, B) << endl;

    return 0;
}

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

int main() {
    ll N;
    cin >> N;

    vector<ll> ya;
    for (ll i = 1; i <= sqrt(N); ++i) {
        if (N % i == 0) {
            ya.push_back(i);
            ya.push_back(N / i);
        }
        if (i * i == N)
            ya.pop_back();
    }

    ll ans = 0;
    for (int i = 1; i < ya.size(); ++i) {
        ll tmp = N;
        while (tmp % ya[i] == 0) {
            tmp /= ya[i];
        }
        if (tmp % ya[i] == 1)
            ++ans;
    }

    for (ll i = 1; i <= sqrt(N - 1); ++i) {
        if ((N - 1) % i == 0)
            ans += 2;
        if (i * i == N - 1)
            --ans;
    }

    cout << ans - 1 << endl;

    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	int n,m,find;
	char a[50][50],b[50][50];

	scanf("%d %d",&n,&m);
	FOR(i,0,n) scanf("%s",a[i]);
	FOR(i,0,m) scanf("%s",b[i]);

	FOR(i,0,n-m+1){
		FOR(j,0,n-m+1){
			find = 1;
			FOR(k,0,m){
				FOR(l,0,m){
					if(a[i-k][j-l] != b[k][l]) find = 0;
				}
			}
			if(find == 1){
				printf("Yes\n");
				return 0;
			}
		}
	}

	printf("No\n");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
#define rep1(i,n) for(int i=1;i<=int(n);++i)

int main(void){
    int n;
    cin >> n;
    vector<ll> a(n+1), p(n+1), s(n+1);
    rep(i,n+1) {
        cin >> a[i];
    }
    if (n == 0) {
        cout << ((a[0] == 1) ? 1 : -1) << endl;
        return 0;
    }
    if (a[0] == 1) {
        cout << -1 << endl;
        return 0;
    }
    s[n] = a[n];
    p[n] = 0;
    for (int d = n-1; d >= 0; d--) {
        s[d] = s[d+1] + a[d];
        p[d] = s[d] - a[d];
        if (p[d] <= 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    s[0] = p[0] = 1;
    rep1(d,n){
        p[d] = min(p[d-1]*2 - a[d], p[d]);
        if (p[d] < 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << accumulate(all(p), 0LL) + accumulate(all(a), 0LL) << endl;
    return 0;
}


Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;

int main() {
  int A, B, cnt = 0;
  cin >> A >> B;
  rep2(i, A, B + 1) {
    string s = to_string(i);
    if(s[0] == s[4] && s[1] == s[3])
      cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())

if N >= M:
    print(0)
    exit()

XXX = list(map(int, input().split()))
XXX.sort()

sections = [abs(XXX[i] - XXX[i + 1]) for i in range(M) if i < M - 1]
sections.sort(reverse=True)
not_arrived = sum(sections[:N-1])

print((XXX[-1] - XXX[0]) - not_arrived)


Measured memory_bytes: 13968
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	boolean f(String s, int st, int ed) {
		for (; st < ed; st++, ed--) {
			if (s.charAt(st - 1) != s.charAt(ed - 1)) {
				return false;
			}
		}
		return true;
	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		String S = sc.next();

		sc.close();

		int N = S.length();
		if (f(S, 1, N) && f(S, 1, (N - 1) / 2) && f(S, (N + 3) / 2, N)) {
			out.println("Yes");
		} else {
			out.println("No");
		}

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  cin >> n;
  set<int> k;
  rep(i,n){
    int tmp;
    cin >> tmp;
    if(k.count(tmp)){
      cout << "NO" << endl;
      return 0;
    }
    k.insert(tmp);
  }
  cout << "YES" << endl;
}


Measured memory_bytes: 9600
#include <iostream>
#include <string>

int main()
{
	std::string s;
	std::getline(std::cin, s);

	for (int slen = (s.size() - 1) / 2; slen >= 1; slen--) {
		bool is_even_str = true;
		for (int i = 0; i < slen; i++) {
			if (s[i] != s[slen + i]) {
				is_even_str = false;
				break;
			}
		}

		if (is_even_str) {
			std::cout << (slen * 2) << std::endl;
			return 0;
		}
	}

	return 1;
}


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

typedef long long ll;
 
int main(){
  string a, b, c;
  cin >> a >> b >> c;
  if(a.substr(a.length()-1,1) != b.substr(0,1)){
    cout << "NO" << endl;
    return 0;
  }
  if(b.substr(b.length()-1,1) != c.substr(0,1)){
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 256
from math import factorial
from collections import defaultdict


def cmb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


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

dA = defaultdict(int)
for i in A:
    dA[i] += 1

sm = 0

for i in dA.values():
    if i >= 2:
        sm += cmb(i, 2)
    else:
        sm += 0

for j in A:
    print(sm - (dA[j] - 1))

Measured memory_bytes: 26780
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)

int n, arr[100050], l, q, a, b, p[100050][20];

int main() {
  	ios_base::sync_with_stdio(0);
  	cin.tie(0);
	cin >> n;
	FOR(i, 1, n) cin >> arr[i];
	cin >> l >> q;
	FOR(i, 1, n-1) p[i][0] = upper_bound(arr+1, arr+n+1, arr[i]+l) - arr - 1;
	p[n][0] = -1;
	FOR(k, 1, 17) {
		FOR(i, 1, n) {
			if (p[i][k-1] != -1) p[i][k] = p[p[i][k-1]][k-1];
			else p[i][k] = -1;
		}
	}
	while (q--) {
		cin >> a >> b;
		if (a > b) swap(a, b);
		int ans = 0;
		for(int k = 17; k >= 0; k--) {
			if (p[a][k] == -1) continue;
			if (p[a][k] <= b) {
				a = p[a][k];
				ans += (1<<k);
			}
		}
		if (a != b) ans++;
		cout << ans << "\n";
	}
}


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


def solve(N: int, K: int, R: int, S: int, P: int, T: str):
    memo = [""]*N

    for i in range(N):
        t = T[i]
        if t == "r":
            if i < K:
                memo[i] = "p" 
            else:
                if memo[i-K] == "p":
                    memo[i] = "."
                else:
                    memo[i] = "p"

        elif t == "s":
            if i < K:
                memo[i] = "r" 
            else:
                if memo[i-K] == "r":
                    memo[i] = "."
                else:
                    memo[i] = "r"
        else:
            if i < K:
                memo[i] = "s" 
            else:
                if memo[i-K] == "s":
                    memo[i] = "."
                else:
                    memo[i] = "s"
    score = 0

    for i in range(N):
        if memo[i] == "p":
            score+=P
        elif memo[i] == "s":
            score += S
        elif memo[i] == "r":
            score += R
        else:
            continue
    
    print(score)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    T = next(tokens)  # type: str
    solve(N, K, R, S, P, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 4212
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << endl; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "abc162_d.cpp"

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

  int n;
  cin >> n;
  string s;
  cin >> s;

  vl cumR(n + 1, 0), cumG(n + 1, 0), cumB(n + 1, 0);
  REP(i, n) {
    cumR[i + 1] = cumR[i];
    cumG[i + 1] = cumG[i];
    cumB[i + 1] = cumB[i];
    if (s[i] == 'R') {
      cumR[i + 1]++;
    }
    if (s[i] == 'G') {
      cumG[i + 1]++;
    }
    if (s[i] == 'B') {
      cumB[i + 1]++;
    }
  }

  ll ans = 0;

  REP(i, n) {
    FOR(j, i + 1, n) {
      if (s[i] == s[j])
        continue;
      if ((s[i] == 'R' && s[j] == 'G') || (s[i] == 'G' && s[j] == 'R')) {
        ans += cumB[n] - cumB[j + 1];
        if (j + (j - i) < n && s[j + (j - i)] == 'B')
          ans--;
      }
      if ((s[i] == 'R' && s[j] == 'B') || (s[i] == 'B' && s[j] == 'R')) {
        ans += cumG[n] - cumG[j + 1];
        if (j + (j - i) < n && s[j + (j - i)] == 'G')
          ans--;
      }
      if ((s[i] == 'B' && s[j] == 'G') || (s[i] == 'G' && s[j] == 'B')) {
        ans += cumR[n] - cumR[j + 1];
        if (j + (j - i) < n && s[j + (j - i)] == 'R')
          ans--;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3676
#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
multiset<long long>Set1, Set2;
int n, E, T, w[101000];
long long D[101000];
int main(){
    int i, pv = 1;
    scanf("%d%d%d",&n,&E,&T);
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    w[n+1] = E;
    D[1] = w[1];
    for(i=1;i<=n;i++){
        long long r = 1e15, tp;
        Set2.insert(D[i] - w[i]);
        while(pv<=i && (w[i] - w[pv]) * 2 > T){
            Set2.erase(Set2.find(D[pv] - w[pv]));
            Set1.insert(D[pv] - 1ll*3*w[pv]);
            pv++;
        }
        if(!Set1.empty()){
            tp = *Set1.begin();
            if(r > tp + w[i]*3ll) r = tp + w[i]*3ll;
        }
        tp = *Set2.begin();
        if(r > tp + w[i] + T) r = tp + w[i] + T;
        D[i+1] = w[i+1] - w[i] + r;
    }
    printf("%lld\n",D[n+1]);
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll h; 
    cin >> h;
    ll res = 0, mem = 1;
    while (h) {
        res += mem;
        h /= 2;
        mem *= 2;
    }
    cout << res << endl;
    return 0;
}

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}

vector<pair<int,ll>> vec[100000];
ll cost[100000];
void dfs(int now,ll COST){
    cost[now]=COST;
    int next;
    REP(i,vec[now].size()){
        next=vec[now][i].first;
        if(cost[next]<0){
            dfs(next,COST+vec[now][i].second);
        }
    }
}
int counter(int x){
    if(!x)return 0;
    return counter(x>>1)+(x&1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A=in();
    int B=in();
    ll ans;ans=lcm(A,B);
    print(ans);
}


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

int main() {
  int N,X,T;
  int P = 0;
  cin >> N >> X >> T;
  if(N%X == 0){
  P = N / X;
  }else{
  P = (N / X) + 1;
  }

  cout << P*T << endl;
  return 0;
  }


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
	int N;
	cin >> N;
	cout << (N - 2) * 180 << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int[][] square = new int[14][14];
		int[] func1_x = {1,0,-1,0};
		int[] func1_y = {0,1,0,-1};
		int[] func2_x = {1,1,0,-1,-1,-1,0,1};
		int[] func2_y = {0,1,1,1,0,-1,-1,-1};
		int[] func3_x = {2,0,-2,0};
		int[] func3_y = {0,2,0,-2};
		
		while(stdIn.hasNext()){
			String str = stdIn.nextLine();
			int x = (int)str.charAt(0)-(int)'0'+2;
			int y = (int)str.charAt(2)-(int)'0'+2;
			square[x][y]++;
			if((int)str.charAt(4)-(int)'0'==1){
				for(int i=0;i<4;i++){
					square[x+func1_x[i]][y+func1_y[i]]++;
				}
			}
			else if((int)str.charAt(4)-(int)'0'==2){
				for(int i=0;i<8;i++){
					square[x+func2_x[i]][y+func2_y[i]]++;
				}
			}
			else if((int)str.charAt(4)-(int)'0'==3){
				for(int i=0;i<8;i++){
					square[x+func2_x[i]][y+func2_y[i]]++;
				}
				for(int i=0;i<4;i++){
					square[x+func3_x[i]][y+func3_y[i]]++;
				}
			}
		}
		int count = 0;
		int depth = 0;
		for(int i=2;i<=11;i++){
			for(int j=2;j<=11;j++){
				if(square[i][j]==0){
					count++;
				}
				if(square[i][j]>depth){
					depth = square[i][j];
				}
			}
		}
		
		System.out.println(count);
		System.out.println(depth);
	}
}

Measured memory_bytes: 15324
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main() {
    int N, K; cin >> N >> K;
    string S; cin >> S;

    for (int i = 0; i < N; ++i) {
        
    }
    int right = 0;     
    int res = 0;
    int sum0 = 0;
    for (int left = 0; left < N; ++left) {
        while (right < N) {
            if(S[right] == '0' && (right == 0 || S[right-1] == '1')) {
                ++sum0;
            }
            if(right == N-1 || (sum0==K && (S[right]=='1' && S[right+1]=='0'))) break;
            ++right;

        }
        res = max(res, right - left);
        if (left == right) ++right;
        else if(S[left] == '0' && S[left+1] == '1') --sum0;
    }
    cout << (res  + 1)<< endl;
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

void solve(){
	int n, T, t, last, ans = 0;
	scanf("%d%d%d", &n, &T, &last);
	REP(i, 1, n) {
		scanf("%d", &t);
		ans += min(t - last, T);
		last = t;
	}
	ans += T;
	printf("%d\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()
void solve(long long N, long long K){
  ll x = roundup(N,K);
  ll y = N/K;
  cout << min(abs(K*x - N) , abs(K*y - N)) << endl;
}

int main(){
    long long N;
	scanf("%lld",&N);
	long long K;
	scanf("%lld",&K);
    solve(N, K);
}


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

int main(){
    int x1,x2,x3,x4,x5;
    cin >> x1 >> x2 >> x3 >> x4 >> x5;
    if(x1 == 0){
        cout << '1' << endl;
    }else if(x2 == 0){
        cout << '2' << endl;
    }else if(x3 == 0){
        cout << '3' << endl;
    }else if(x4 == 0){
        cout << '4' << endl;
    }else if(x5 == 0){
        cout << '5' << endl;
    }
    return 0;
}

Measured memory_bytes: 3520
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)
#include <vector>
using namespace std;

template <class Monoid>
struct BIT_2D {
  vector<vector<Monoid>> bit;
  // identity element
  Monoid ide;
  // bit.size()
  int N;
  // bit[i].size()
  int M;

  BIT_2D(int n, int m, Monoid ide)
      : N(n), M(m), ide(ide), bit(n, vector<Monoid>(m, ide)) {}

  void add(int r, int c, Monoid value) {
    for (int i = r; i < N; i |= i + 1) {
      for (int j = c; j < M; j |= j + 1) {
        bit[i][j] += value;
      }
    }
  }

  // sum[(0,0),(r,c)]
  Monoid sum(int r, int c) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
      for (int j = c; j >= 0; j = (j & (j + 1)) - 1) {
        res += bit[i][j];
      }
    }
    return res;
  }
  // sum[(r1,c1),(r2,c2)]
  Monoid sum(int r1, int c1, int r2, int c2) {
    return sum(r2, c2) - sum(r1 - 1, c2) - sum(r2, c1 - 1) +
           sum(r1 - 1, c1 - 1);
  }

  Monoid get(int r, int c) { return sum(r, c, r, c); }

  void set(int r, int c, Monoid value) { add(r, c, value - get(r, c)); }
};

i64 H,W,T,Q;
i64 t[101010];
int c[101010];
int r1[101010];
int c1[101010];
int r2[101010];
int c2[101010];
int main(){
    cin >> H >> W >> T >> Q;
    using q = pair<i64, pair<int, int>>;
    priority_queue<q,vector<q>,greater<q>> que;
    for(int i = 0;i < Q;i++){
        scanf("%d%d%d%d",&t[i],&c[i],&r1[i],&c1[i]);
        if(c[i] == 2){
            scanf("%d%d",&r2[i],&c2[i]);
        }
        que.push({t[i],{c[i],i}});

        //たい焼きが焼けるイベント
        if(c[i] == 0){
            que.push({t[i] + T,{-1,i}});
        }
    }

    BIT_2D<int> yakinow(H + 1,W + 1,0);
    BIT_2D<int> alre(H + 1,W + 1,0);

    while(!que.empty()){
        auto q = que.top();
        int kind = q.second.first;
        int i = q.second.second;
        que.pop();

        if(kind == -1){
            yakinow.set(r1[i],c1[i],0);
            alre.set(r1[i],c1[i],1);
        }
        if(kind == 0){
            yakinow.set(r1[i],c1[i],1);
        }
        if(kind == 1){
            alre.set(r1[i],c1[i],0);
        }
        if(kind == 2){
            int ans1 =  yakinow.sum(r1[i],c1[i],r2[i],c2[i]);
            int ans2 =  alre.sum(r1[i],c1[i],r2[i],c2[i]);
            printf("%d %d\n",ans2,ans1);
        }
    }
    return 0;
}



Measured memory_bytes: 39664
#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;


int main() {
    ll a, b, n;
    scanf("%lld%lld%lld", &n, &a, &b);
    if(a>b) {
        printf("0\n");
        return 0;
    }
    if(n==1) printf(a==b? "1\n" : "0\n");
    else printf("%lld\n", (n-1)*b+a -(n-1)*a-b +1);
    return 0;
}

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

int main() {
	int A, B, T;
	cin >> A >> B >> T;
	cout << T / A * B;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

*/

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

int main(){
  int n; cin >> n;
  vector<int> a(n);

  for(int i=0; i<n; ++i) cin >> a[i];

  double ans = 0;

  for(int i=0; i<n; ++i){
    ans += 1.0/a[i];
  }

  printf("%.5lf\n", 1.0/ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <algorithm>
#include <numeric>
using namespace std;
const long long INF = 1LL<<40;

int main() {
    long long N, K; cin >> N >> K;
    vector<vector<long long> > s(N); // s[i] := 種類 i の美味しさの集合
    for (int i = 0; i < N; ++i) {
        long long t, d; cin >> t >> d; --t;
        s[t].push_back(d);
    }

    // 各種類について、美味しい順に並べる
    for (auto &v : s) {
        sort(v.begin(), v.end(), greater<long long>());
        if (v.empty()) v.push_back(-INF); // 番兵
    }

    // 「美味しさの最大値」の大きいネタ順
    sort(s.begin(), s.end(), [&](vector<long long> a, vector<long long> b) {
            return a[0] > b[0];});
 
    // まず K 種類選ぶ場合
    long long cur = 0;
    priority_queue<long long> que;
    for (int i = 0; i < K; ++i) {
        cur += s[i][0];
        for (int j = 1; j < s[i].size(); ++j) que.push(s[i][j]);
    }
    for (int i = K; i < N; ++i) for (int j = 0; j < s[i].size(); ++j) que.push(s[i][j]);

    // 走査
    long long res = cur + K*K;
    for (long long x = K-1; x >= 1; --x) {
        long long v = s[x][0];
        long long w = que.top();
        if (v < w) {
            que.pop(); cur += w;
            que.push(v); cur -= v;
        }
        res = max(res, cur + x*x);
    }
    cout << res << endl;
}

Measured memory_bytes: 8696
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <set>
#include <cmath>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b+1;i++)
#define Per(i,b,a) for(int i=b;i>=a;i--)
int main(){
    int H,W;
    cin>>H>>W;
    string s;
    bool masu[100][100];
    rep(i,H){
        cin>>s;
        rep(j,W){
            if(s[j]=='#') masu[i][j] = false;
            else masu[i][j] = true;
        }
    }
    int ans[100][100];
    if(masu[0][0]) ans[0][0] = 0;
    else ans[0][0] = 1;
    rep(i,H-1){
        ans[i+1][0] = ans[i][0];
        if((!masu[i+1][0]) & masu[i][0]) ans[i+1][0] += 1;
    }
    rep(i,W-1){
        ans[0][i+1] = ans[0][i];
        if((!masu[0][i+1]) & masu[0][i]) ans[0][i+1] += 1;
    }
    // rep(i,H){
    //     rep(j,W) cout<<masu[i][j]<<" ";
    //     cout<<endl;
    // }
    int temp1,temp2;
    rep(i,H){
        rep(j,W){
            if(i==0||j==0) continue;
            temp1 = ans[i-1][j];
            temp2 = ans[i][j-1];
            if((!masu[i][j]) & masu[i-1][j]) temp1 += 1;
            if((!masu[i][j]) & masu[i][j-1]) temp2 += 1;
            // cout<<temp1<<" "<<temp2<<endl;
            ans[i][j] = min(temp1,temp2);
        }
    }
    // rep(i,H){
    //     rep(j,W)cout<<ans[i][j]<<" ";
    //     cout<<endl;
    // }
    cout<<ans[H-1][W-1]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,h,w;
  cin>>n>>h>>w;
  cout<<(n-h+1)*(n-w+1)<<endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
nSum = 0
for i in range(n):
    cnt = 0
    for j in range(i + 1):
        if (i + 1) % (j + 1) == 0:
            cnt += 1
    if cnt == 8 and (i + 1) % 2 != 0:
        nSum += 1

print(nSum)


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

using ll  = long long;
using pii = pair<int,int>;
#define dbg(n) cout<<'\n'<<#n<<" is "<<n<<'\n';
#define pb push_back
#define all(v) v.begin(), v.end()
#define cs(i) cout<<"Case "<<i+1<<": \n"; 
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N   = 1e5+5;
const int INF = 0x7fffffff;

int dp[N][5],a[N],b[N],c[N];

int main(){
    int n,t,hold=0;

    cin>>n;

    
    memset(dp,-1,sizeof dp);

    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];

    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];

    dp[0][3]=max(dp[0][1],max(dp[0][0],dp[0][2]));
    for(int i=1;i<n;i++){
        dp[i][0]=a[i]+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
        dp[i][2]=c[i]+max(dp[i-1][1],dp[i-1][0]);
        dp[i][3]=max(dp[i][1],max(dp[i][0],dp[i][2])); //dbg(dp[i][3])
    }
    cout<<dp[n-1][3]<<endl;
    return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#define DIM 100005
using namespace std;
int n, m, v, p, i, sol;
int w[DIM];
long long sp[DIM], sum;
int main(){
    cin>> n >> m >> v >> p;
    for(i = 1; i <= n; i++){
        cin>> w[i];
    }
    sort(w + 1, w + n + 1);
    for(i = 1; i <= n; i++){
        sp[i] = sp[i - 1] + w[i];
    }
    for(i = 1; i <= n; i++){
        if(w[i] + m >= w[n - p + 1]){
            sum = (i + p - 1) * 1LL * m;
            if(i < n - p + 1){
                sum += (w[i] + m) * 1LL * (n - p + 1 - i) - (sp[n - p + 1] - sp[i]);
            }
            if(sum >= m * 1LL * v){
                sol++;
            }
        }
    }
    cout<< sol;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define N 400011
#define MAX 1000000007
#define int long long
using namespace std;
struct point{
	int x,y,z;
}ee[N];
struct node{
	int no,data;
	bool operator<(const node &other)const{
		return data>other.data;
	}
}temp;
priority_queue<node> pq;
struct apple{
	int v,nxt,q;
}edge[N*4];
int indexx[N],tot,n,m,vist[N],dist[N],dis[2][N],sum[2][N],ans,que[N];
int S,T,Ans,d[N];
void addedge(int x,int y,int z){
	edge[++tot].v=y;
	edge[tot].q=z;
	edge[tot].nxt=indexx[x];
	indexx[x]=tot;
}
void dij(int st){
	memset(dist,0x3f,sizeof(dist));
	memset(vist,0,sizeof(vist));
	temp.no=st;
	temp.data=0;
	dist[st]=0;
	pq.push(temp);
	while(!pq.empty()){
		temp=pq.top();pq.pop();
		int x=temp.no;
		if(vist[x]) continue;
		vist[x]=1;
		int t=indexx[x],vv,qq;
		while(t){
			vv=edge[t].v;
			qq=edge[t].q;
			if(dist[vv]>dist[x]+qq){
				dist[vv]=dist[x]+qq;
				temp.no=vv,temp.data=dist[vv];
				pq.push(temp);
			}
			t=edge[t].nxt;
		}
	}
}
void bfs(int st,int k){
	int head=0,tail=0;
	que[++tail]=st;
	sum[k][st]=1; 
	while(head<tail){
		int x=que[++head];
		int t=indexx[x],vv;
		while(t){
			vv=edge[t].v;
			d[vv]--;
			sum[k][vv]=(sum[k][vv]+sum[k][x])%MAX;
			if(!d[vv]){
				que[++tail]=vv;
			}
			t=edge[t].nxt;
		}
	}
}
signed main(){
	int x,y,z;
	scanf("%lld%lld",&n,&m);
	scanf("%lld%lld",&S,&T);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		ee[i].x=x;
		ee[i].y=y;
		ee[i].z=z;
		addedge(x,y,z);
		addedge(y,x,z);
	}
	dij(S);Ans=dist[T];
	for(int i=1;i<=n;i++) dis[0][i]=dist[i];
	memset(indexx,0,sizeof(indexx));tot=0;
	for(int i=1;i<=m;i++){
		if(dist[ee[i].x]>dist[ee[i].y]) swap(ee[i].x,ee[i].y);
		if(dist[ee[i].x]+ee[i].z==dist[ee[i].y]){
			addedge(ee[i].x,ee[i].y,1);
			d[ee[i].y]++;
		}
	}
	bfs(S,0);
	memset(d,0,sizeof(d));
	memset(indexx,0,sizeof(indexx));tot=0;
	for(int i=1;i<=m;i++){
		addedge(ee[i].x,ee[i].y,ee[i].z);
		addedge(ee[i].y,ee[i].x,ee[i].z);
	}
	dij(T);
	for(int i=1;i<=n;i++) dis[1][i]=dist[i];
	memset(indexx,0,sizeof(indexx));tot=0;
	for(int i=1;i<=m;i++){
		if(dist[ee[i].x]>dist[ee[i].y]) swap(ee[i].x,ee[i].y);
		if(dist[ee[i].x]+ee[i].z==dist[ee[i].y]){
			addedge(ee[i].x,ee[i].y,1);
			d[ee[i].y]++;
		}
	}
	bfs(T,1);
	ans=sum[0][T]*sum[0][T]%MAX;
	for(int i=1;i<=m;i++){
		x=ee[i].x,y=ee[i].y,z=ee[i].z;
		if(dis[0][x]>dis[0][y]) swap(x,y);
		if(dis[0][x]+dis[1][y]+z==Ans){
			int t=sum[0][x]*sum[1][y]%MAX;
			if(abs(dis[0][x]-dis[1][y])<z){
				ans=(ans-t*t%MAX+MAX)%MAX;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[0][i]==dis[1][i] && dis[0][i]+dis[1][i]==Ans){
			int t=sum[0][i]*sum[1][i]%MAX;
			ans=(ans-t*t%MAX)%MAX;
		}
	}
	ans=(ans%MAX+MAX)%MAX;
	printf("%lld",ans);
	return 0;
} 

Measured memory_bytes: 35388
#include <bits/stdc++.h>
using namespace std;
vector<long long> v;
long long mod=1e9+7, dp[200005][20];
long long solve(long long id,long long rem){
    if(id==v.size()){
        if(rem==5)  return 1;
        else
            return 0;
    }
    if(dp[id][rem]!=-1){
        return dp[id][rem];
    }
    long long ans=0;
    if(v[id]==-1){
        for(long long i=0;i<10;i++){
            ans+=solve(id+1,(rem*10+i)%13);
            ans%=mod;
        }
    }
    else{
        ans+=solve(id+1,(rem*10+v[id])%13);
        ans%=mod;
        
    }
    return dp[id][rem] = ans;
}
int  main()
{
    memset(dp,-1,sizeof(dp));
    string s;
    cin>>s;
    long long i;
    for(i=0;i<s.length();i++){
        if(s[i]=='?')   v.push_back(-1);
        else    v.push_back(s[i]-'0');
    }
    cout<<solve(0,0);
}


Measured memory_bytes: 40436
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    ll N = S.size();
    ll ans = 0;
    rep(i,0,1 << (N-1)){
        ll num = 1;
        rep(j,0,N-1){
            ans += (S[N-1-j] - '0') * num;
            if(!(i >> j & 1)){
                num *= 10;
            }else{
                num = 1;
            }
        }
        ans += (S[0] - '0') * num;
    }
    print(ans);
}


Measured memory_bytes: 256
xp0, yp0, xp1, yp1 = map(int, input().split())
q = int(input())

xp1 = complex(xp1 - xp0, yp1 - yp0)
eps = 1e-8

for _ in range(q):
    x, y = map(int, input().split())
    xp2 = complex(x - xp0, y - yp0)

    temp = xp1.conjugate() * xp2
    dot = temp.real
    cross = temp.imag
    if abs(cross) < eps:
        if dot == 0:
            print("ON_SEGMENT")
        elif dot > 0:
            if abs(xp1) >= abs(xp2):
                print("ON_SEGMENT")
            else:
                print("ONLINE_FRONT")
        else:
            print("ONLINE_BACK")
    elif cross > 0:
        print("COUNTER_CLOCKWISE")
    else:
        print("CLOCKWISE")



Measured memory_bytes: 5632
import java.io.*;

public class Main {
	public static Point third(Point a,Point b){
		Point d=new Point(b.x-a.x,b.y-a.y);
		double x=d.x*0.5-d.y*(Math.sqrt(3)*0.5);
		double y=d.y*0.5+d.x*(Math.sqrt(3)*0.5);
		Point c=new Point(a.x+x,a.y+y);
		return c;
	}
	public static void carve(Point start,Point end,int n){
		if (n==0){
			end.print();
		}else{
			Point p1=new Point((end.x/3+start.x/3*2),(end.y/3+start.y/3*2));
			Point p3=new Point((start.x/3+end.x/3*2),(start.y/3+end.y/3*2));
			Point p2=third(p1,p3);
			carve(start,p1,n-1);
			carve(p1,p2,n-1);
			carve(p2,p3,n-1);
			carve(p3,end,n-1);
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		Point s=new Point(0.0,0.0);
		Point e=new Point (100,0);
		s.print();
		carve(s,e,n);
	}
}

class Point{
	double x,y;
	public Point(double px,double py){
		this.x=px;
		this.y=py;
	}
	public void print(){
		System.out.println(x+" "+y);
	}
}

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

long long md(pair<long long,long long> x,pair<long long,long long> y){
    return max(x.first,y.first)-min(x.first,y.first)+max(x.second,y.second)-min(x.second,y.second);
}

int main(){
    long long a,b,x,l,r;
    cin >> a >> b >> x;
    l=a/x;
    if(a%x!=0)
    l++;
    r=b/x;
    cout << r-l+1 << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
#define mk make_pair
#define fir first
#define sec second
using namespace std;
const int N=3010 ,mod=1000000007;
int n,m,a[N],f[N][N],t1[N],t2[N],t3[N],t4[N];
ll iv2=(mod+1)>>1;
int pw(int x,int y){
	int re=1;
	for(int i=y;i;i>>=1,x=(ll)x*x%mod){
		if(i&1)re=(ll)re*x%mod;
	}
	return re;
}
int main(){
//	freopen("D.in","r",stdin);
//	freopen("D.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		f[i][j] = bool(a[i] > a[j]);
	} 
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		for(int j=1;j<=n;j++)if(j!=y&&j!=x){
			t1[j] = iv2*(f[j][x]+f[j][y])%mod;
			t2[j] = iv2*(f[x][j]+f[y][j])%mod;
			t3[j] = iv2*(f[j][y]+f[j][x])%mod;
			t4[j] = iv2*(f[y][j]+f[x][j])%mod; 
		}
		for(int j=1;j<=n;j++)if(j!=y&&j!=x){
			f[j][x] = t1[j];
			f[x][j] = t2[j];
			f[j][y] = t3[j];
			f[y][j] = t4[j];
		}
		int t= iv2*(f[x][y]+f[y][x])%mod;
		f[x][y] = f[y][x]= t;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++){
		ans = (ans + f[i][j])%mod;
	}
	ans = (ll) ans * pw(2,m) %mod;
	printf("%d\n",ans);
	return 0;
}//by tkys_Austin;


Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
map<int,int> cx;
int n,m;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int a;scanf("%d",&a);
		cx[a]++;
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int a;scanf("%d",&a);
		if(cx[a]!=0) cx[a]--;
		else{
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define mod 1000000007
#pragma GCC optimize ("-O2")
#define mod2 998244353
#define MAXN 1000000000
#define v32 vector<int>
#define v64 vector<lli>
#define v1024 vector <vector <int>>
#define v4096 vector <vector <lli>>
#define vt vector
#define f(x, y, z) for (lli x = y; x < z; x++)
#define fd(x, y, z) for (lli x = y; x > z; x--)
#define lb lower_bound
#define ld long double
#define m64 map<lli,lli>
#define m32 map<int,int>
#define m64it map<lli,lli>::iterator
#define m32it map<int,int>::iterator
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ist insert
#define endl "\n"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define p_q priority_queue 
#define min_p_q priority_queue <pair<lli,int>,vt <pair<lli,int>>,greater <pair<lli,int>>>
using namespace std;
using namespace __gnu_pbds; 

//USE AT YOUR OWN RISK
lli tmod(lli x,lli m=mod){return (x%m+m)%m;}

template <typename T> 
void DEBUG_ARR(vt<T> a,char c)
{
	f(i,0,a.size())cout<<a[i]<<c;
	cout<<"\n";
}

//make sure x is below mod
lli power(lli x, lli y,lli m=mod) 
{
    lli res = 1;  
   
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x)%m; 
        y = y>>1; 
        x = (x*x)%m;  
    }
    if(res<0)
       res+=m; 
    return res; 
}

// lli fact[2000009];
// lli ncr(lli n,lli r){
//     lli ans=fact[n];
//     if(r>n)return 1;
//     if(r<0)return 0;
//     if(n<0)return 0;
//     ans=(ans*power(fact[n-r],mod-2))%mod;
//     ans=(ans*power(fact[r],mod-2))%mod;
//     return ans;
// }
void normalize(lli &a,lli &b){
    if(a==0 && b==0)return;
    if(a<0){
        a=-a;
        b=-b;
    }
    else if(a==0){
        if(b<0)b=-b;
    }
    lli g=__gcd(abs(a),abs(b));
    if(g!=0){
        a/=g;
        b/=g;
    }
}
const int N=2e5+5;

//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
int smallestprime[(int)1e7+10];
int nodivisors[(int)1e7+5];
int main() 
{ 
    // fact[0]=1;
    // f(i,1,2000001)fact[i]=(i*fact[i-1])%mod;
    f(i,2,10000001){
        if(smallestprime[i]==0)
        for(lli j=1;j*i<=10000000;j++){
            if(smallestprime[j*i]==0)
            smallestprime[j*i]=i;
        }
    }
    nodivisors[1]=1;
    fastio;
    int t=1;
    // cin>>t;
    // int temp=t;
    // cout<<smvalallestprime[5]<<"\n";
	while(t--){
        // cout<<"Case #"<<temp-t<<": ";
        // clock_t t=clock();
        // ifstream in("cave.in");
        // ofstream out("cave.out");
        lli n;
        cin>>n;
        lli ans=1;
        f(i,2,n+1){
            lli count=0;
            lli temp=smallestprime[i];
            lli tempi=i;
            while(tempi%temp==0){
                tempi/=temp;
                count++;
            }
            nodivisors[i]=(1+count)*nodivisors[tempi];
            ans+=nodivisors[i]*i;
        }
        cout<<ans<<"\n";
        // cout<<clock()-t<<"\n";
    }   
    return 0; 	
}


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

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

using ll = long long;
using pii = pair<int, int>;

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
    	cin >> a[i];
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
    	for (int j = i + 1; j < n; ++j) {
    		int lo = j + 1, hi = n - 1, it = -1;
    		while (lo <= hi) {
    			int mid = lo + hi >> 1;
    			if (a[mid] < a[i] + a[j]) {
    				it = mid;
    				lo = mid + 1;
    			}
    			else hi = mid - 1;
    		}
    		if (it != -1) ans += ((ll)it - j);
    	}
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
n = int(input())
T, A = map(int,input().split())
H = list(map(int, input().split()))
tempara = []
sa = []
for i in range(n):
    tempara.append(T - H[i] * 0.006)
    sa.append(abs(A - tempara[i]))
print(sa.index(min(sa)) + 1)


Measured memory_bytes: 3060