akhauriyash/Code-Regression huggingface dataset:
from collections import Counter, deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1


# 変化しないものを数える
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1
LIS = LIS[:N - K + 1]


# スライド最小値を計算
slide_min = deque([])
MIN = []
for k in range(N):
    while slide_min and P[slide_min[-1]] >= P[k]:
        slide_min.pop()
    slide_min.append(k)

    if k < K - 1:
        continue

    if slide_min[0] + K <= k:
        slide_min.popleft()
    MIN.append(P[slide_min[0]])


# スライド最大値を計算
slide_max = deque([])
MAX = []
for k in range(N):
    while slide_max and P[slide_max[-1]] <= P[k]:
        slide_max.pop()
    slide_max.append(k)

    if k < K - 1:
        continue

    if slide_max[0] + K <= k:
        slide_max.popleft()
    MAX.append(P[slide_max[0]])


for i in range(N - K + 1):
    flg = False
    if LIS[i] >= K:
        flg = True

    if (i + 1 < N - K + 1) and (P[i] == MIN[i]) and (P[i + K] == MAX[i + 1]):
        flg = True

    ans -= flg

if len([l for l in LIS if l >= K]):
    ans += 1
print(ans)


Measured memory_bytes: 33888
// #pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

const int maxN = 150010;
const int MAXM = 310;
const int MAXK = 17;
const int MOD = 1000000007;
const ll INF = 10000000000000000LL;
const ll inf = 5000000000000LL;

int n;

int a[maxN],b[maxN];
int A,B,C;
int d[maxN];

int ans = 1000000009;
void dfs(int k)
{
	if(k>n)
	{
		vector<int> v[5];
		for(int i=1;i<=n;i++)
		{
		//	printf("%d ",d[i]);
			v[d[i]].push_back(a[i]);
		}
		//cout<<endl;
		int tmp = 0; 
		for(int i=1;i<4;i++)
		{
			if(v[i].size() == 0)
				return;
			int sum = 0;
			for(auto y:v[i])
			{
				sum += y;
			}
			tmp += (v[i].size()-1)*10 + abs(sum - b[i]);
		}
		ans = min(ans,tmp);
		return;
	}
	for(int i=0;i<=3;i++)
	{
		d[k] = i;
		dfs(k+1);
 	}
}

int main()
{
    scanf("%d%d%d%d", &n,&b[1],&b[2],&b[3]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	dfs(1);
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, a, n) for (int i = a; i <= (n); ++i)

using namespace std;
using ll = long long;

int main() {
    string S; cin >> S;
    string T; cin >> T;

    T.pop_back();
    if (S == T) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3612
n = int(input())

def dfs(x):
    if x>n:
        return 0
    cnt = 1 if all(str(x).count(a) > 0 for a in '753') else 0
    for a in '753':
        cnt += dfs( int(str(x)+a) )
    return cnt
print(dfs(0))

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	string s;
	cin>>s;
	if(s=="zyxwvutsrqponmlkjihgfedcba"){
		cout<<-1<<endl;
		return 0;
	}
	int al[26]={0};
	for(int i = 0; i < s.size(); i++){
		al[s[i]-'a']++;
	}
	for(int i = 0; i < 26; i++){
		if(al[i]>1){
			cout<<-1<<endl;
			return 0;
		}
	}
	for(int i = 0; i < 26; i++){
		if(s.size()<26 && al[i]==0){
			cout<<s+(char)('a'+i)<<endl;
			return 0;
		}
	}

	for(int i = s.size()-1; i >= 0; i--){
		int cnt=0;
		if(s[i]=='z'){
			al[s[i]-'a']=0;
			continue;
		}
		while(1){
			if(al[(char)(s[i]+cnt) - 'a']>0){
				if((char)(s[i]+cnt) == 'z'){
					al[s[i]-'a']=0;
					break;
				}
				cnt++;
			}else{
				int end = i;
				s[i]+=cnt;
				for(int j = 0; j <= end; j++){
					cout<<s[j];
				}printf("\n");
				return 0;
			}

		}
	}

	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
import sys

list=1000000*[1]

list[0] = 0
list[1] = 0
for i in range(1,1000000):
	if list[i] == 1:
		for j in range(i*i,1000000,i):
			list[j] = 0

for line in sys.stdin:
	a = int(line)
	b = 0
	for x in range(1,a+1):
		b += list[x]
	print b

Measured memory_bytes: 59500
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i,n) for(int i=0;i<(int)(n);i++)
static const int mod = 1e9+7;
static const long long INF = 1LL << 60;
typedef long long ll;
 int main(){
    int N, M;
    cin >> N >> M;
    vector<int> a(N+1, true); //壊れている床
    rep(i,M){
        int num; cin >> num;
        a[num] = false;
    }
    vector<long long int> dp(N+1);
    dp[0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j <= min(N,i+2);j++){
            if(a[j]){
                dp[j] += dp[i];
                dp[j] %= mod;
            }
        }
    }
    cout << dp[N] << endl;
} 




Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 2005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 + c - '0';
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    out(x / 10);
    }
    putchar('0' + x % 10);
}
int64 X,Y;

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    read(X);read(Y);
    int l = 1;
    while(X <= Y / 2) {++l;X *= 2;}
    out(l);enter;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
      StringBuilder sb = new StringBuilder();
      
      for (int j = 0;j < S.length();j++){
        if(S.charAt(j) == '1') {
          sb.append('9');
        } else if(S.charAt(j) == '9') {
          sb.append('1');
        } else{
          sb.append(S.charAt(j));
        }
      }
      S = sb.toString();
      println(S);
        return ;
    }
    static long getLong(String val) {return Long.parseLong(val);}
    static int getInt(String val) {
        return Integer.parseInt(val);
    }

    static void println(String val){System.out.println(val);};
    static void println(int val){System.out.println(val);};
    static void println(long val){System.out.println(val);};
    static void println(Object val){System.out.println(val);};
}


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

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                        \
	sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
	{
sim > struct rge
{
	c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifdef LOCAL
	~debug()
	{
		cerr << endl;
	}
	eni(!=) cerr << boolalpha << i;
	ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c &)
	{
		ris;
	}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define forn(i, n) for (ll i = 0; i < int(n); i++)
#define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define M_PI 3.14159265358979323846
#define EPS 1e-7

void solve()
{
	string n; cin >> n;
	ll sum = 0;
	for (int i = 0; i < n.size(); ++i)
	{
		sum += n[i] - '0';
	}
	vector<ll> a(len(n));
	a[0] = n[0] - '0' - 1;
	if (len(n) == 1) 
	{
		cout << n << endl;
		return;
	}
	for (int i = 1; i < a.size(); ++i)
	{
		a[i] = 9;
	}
	cout << max(sum, accumulate(all(a), 0LL));
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Measured memory_bytes: 3660
function main(lines) {
  const [N, X, T] = na();
  
  const turn = Math.ceil(N/X);
  const ans = turn * T;
  
  return ans;
}



const lines = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");

let lineCount = 0;
const s = () => lines[lineCount++];
const n = () => Number(s());
const b = () => BigInt(s());
const sa = () => s().split(' ');
const na = () => sa().map(Number);
const ba = () => sa().map(BigInt);

const ans = main(lines);
console.log( ans );

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

int main(void){
    int n;
    cin >> n;
    vector<tuple<string, int, int> > data;
    string s;
    int i,p;
    for(i=1;i<=n;i++){
        cin >> s >> p;
        data.push_back(make_tuple(s,-p,i));
    }
    sort(data.begin(), data.end());
    for(auto d: data){
        cout << get<2>(d) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <climits>
#include <cstring>
#include <ctype.h>
#include <sstream>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

#define FOR(i,a,b) for (int i=a;i<b;i++)
inline void in(int &a) {scanf("%d",&a);}

int N, M, Q;
bool board[2005][2005];
int prefix[2005][2005];
bool edgebawah[2005][2005];
int prefixbawah[2005][2005];
bool edgesamping[2005][2005];
int prefixsamping[2005][2005];

// int dr[] = {1,0,-1,0};
// int dc[] = {0,1,0,-1};

int main(){
    scanf("%d %d %d",&N,&M,&Q);
    char line[2005];
    FOR(i,1,N+1){
        scanf("%s",line);
        FOR(j,1,M+1){
            board[i][j] = line[j-1]=='1';
        }
    }
    FOR(i,1,N){
        FOR(j,1,M+1){
            edgebawah[i][j] = board[i][j] && board[i+1][j];
        }
    }
    FOR(i,1,N+1){
        FOR(j,1,M){
            edgesamping[i][j] = board[i][j] && board[i][j+1];
        }
    }
    FOR(i,1,N+1){
        FOR(j,1,M+1){
            prefix[i][j] = board[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            prefixbawah[i][j] = edgebawah[i][j] + prefixbawah[i-1][j]+prefixbawah[i][j-1]-prefixbawah[i-1][j-1];
            prefixsamping[i][j] = edgesamping[i][j]+prefixsamping[i-1][j]+prefixsamping[i][j-1]-prefixsamping[i-1][j-1];
            // cout<<prefixsamping[i][j]<<' ';
        }
        // puts("");
    }
    int a, b, c, d;
    int p, pb, ps;
    FOR(i,0,Q){
        scanf("%d %d %d %d",&a,&b,&c,&d);
        p = prefix[c][d]+prefix[a-1][b-1]-prefix[a-1][d]-prefix[c][b-1];
        if (a!=c) pb = prefixbawah[c-1][d]+prefixbawah[a-1][b-1]-prefixbawah[a-1][d]-prefixbawah[c-1][b-1];
        else pb = 0;
        if (b!=d) ps = prefixsamping[c][d-1]+prefixsamping[a-1][b-1]-prefixsamping[a-1][d-1]-prefixsamping[c][b-1];
        else ps = 0;
        printf("%d\n",p-pb-ps);
    }
    return 0;
}


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

const int m = 100000;
int main(){
  ll n;
  vector<ll> a(m+1);
  cin >> n;
  rep(i,n){
    int x;
    cin >> x;
    a[x]++;
  }
  int q;
  cin >> q;
  vector<ll> b(q),c(q);
  rep(i,q) cin >> b[i] >> c[i];

  ll sum=0;
  for(int i=1;i<=m;i++) sum+=a[i]*i;
  rep(i,q){
    int B=b[i],C=c[i];
    sum+=a[B] * (C-B);
    a[C]+=a[B];
    a[B]=0;
    cout << sum << "\n";
  }
  return 0;
}

Measured memory_bytes: 5596
# -*- coding: utf-8 -*-
import math
import sys

n, m = map(int, input().split())

if math.fabs(n - m) == 1:
    k = 1
elif n == m:
    k = 2
else:
    k = 0

print(math.factorial(n) % 1000000007 * math.factorial(m) % 1000000007 * k % 1000000007)


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

using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    int sum = 2*a-1;
    if(b + b - 1 > sum){
        sum = b + b - 1;
    }
    if(a+b > sum){
        sum = a+b;
    }
    cout << sum << endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  int mxindex;
  int max;
  int Asum = 0;
  int Bsum = 0;
  for(int i=0; i<n; i++){
    mxindex = 0;
    max = a[0];
    for(int j=0; j<n; j++){
      if(a[mxindex] < a[j]){
        mxindex = j;
        max = a[j];
      }
    }
    if(i%2==0){
      Asum += max;
    }else{
      Bsum += max;
    }
    a[mxindex] = 0;
  }
  cout << Asum-Bsum << endl;
}

Measured memory_bytes: 256
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;

typedef long long ll;
typedef pair<ll, int> P;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const ll INF = 1000000000000000;

struct edge {
    int to;
    ll cost;
    edge(int t, ll c) : to(t), cost(c) {}
    edge() {}
};

const int MAXV = 100010;
const int MAXE = 500020;
vector<edge> G[MAXV];
ll dist[MAXV];

void dijkstra(int s) {
    for (int i = 0; i < MAXV; i++) dist[i] = INF;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(make_pair(0, s));
    dist[s] = 0;
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            int next = e.to;
            if (dist[next] > dist[v] + e.cost) {
                dist[next] = dist[v] + e.cost;
                que.push(make_pair(dist[next], next));
            }
        }
    }
}

int main(void) {
    int V, E, r;
    cin >> V >> E >> r;
    for (int i = 0; i < E; i++) {
        int s, t;
        ll d;
        cin >> s >> t >> d;
        G[s].push_back(edge(t, d));
    }
    dijkstra(r);
    for (int i = 0; i < V; i++) {
        if (dist[i] >= INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
    return 0;
}

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

using namespace std;

long long c2(long long n){
    if(n < 2) return 0;
    return (n-1)*n/2;
}

void solve(){
    int i,j;
    string str;
    int n;
    cin >> n;
    vector<long long> a(n),c(n+1,0);
    for(i = 0;i < n;i++){
        cin >> a[i];
        c[a[i]]++;
    }
    long long ans = 0;
    for(i = 1;i <= n;i++){
        ans += c2(c[i]);
    }
    for(i = 0;i < n;i++){
        cout << ans-c2(c[a[i]])+c2(c[a[i]]-1) << endl;
    }
}

int main(){
    solve();
}


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

int main() {
    int n, f = 1;
    std::cin >> n;
    char c[n / 2], d[n / 2];
    for (int i = 0; i < n / 2 ; ++i) {
        std::cin >> c[i];
    }
    for (int i = 0; i < n / 2; ++i) {
        std::cin >> d[i];
        if(c[i] != d[i]){
            f = 0;
            break;
        }
    }
    if (n % 2 == 1) f = 0;
    
    if (f) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
}


Measured memory_bytes: 256
# ALDS_10_B - 連鎖行列積

import sys

N = int(input())

M = []
for n in range(N):
    r, c = map(int, sys.stdin.readline().strip().split())
    if n == 0:
        M.append(r)
    M.append(c)


# dp 初期化
dp = [[float('inf')] * N for _ in range(N)]
for n in range(N):
    dp[n][n] = 0

# dp 更新
for l in range(1, N):
    for i in range(N - l):
        j = i + l
        for k in range(i, j):
            # print(f'k: {k}, i: {i}, j: {j}')
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + M[i] * M[k + 1] * M[j + 1])

# for i in range(len(dp)):
#     print(dp[i])

print(dp[0][N - 1])



Measured memory_bytes: 5672
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> a(N);
    for(int i = 0; i < N; i++) cin >> a[i];
    sort(a.begin(), a.end(), greater<ll>());
    ll ans = 0;
    ll idx = 0;
    ll timer = 1;
    for(int i = 1; i < N; i++) {
        ans += a[idx];
        timer++;
        if(timer == 2) {
            timer = 0;
            idx++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4768
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map { it.toInt() }.groupBy { it }.entries.sortedBy { it.key }
    val aMax = aa.maxBy { it.key }!!.key
    val isDividable = BooleanArray(aMax+1){false}

    aa.forEach { a ->
        if (a.value.size > 1) isDividable[a.key] = true

        for (i in a.key*2 until isDividable.size step a.key) {
            isDividable[i] = true
        }
    }

    println(aa.count { !isDividable[it.key] })
}

Measured memory_bytes: 107756
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#define INF 1000000000
#define LINF 9000000000000000000
#define mod  1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
  
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

signed main(){
  int H, W;
  char s[405][405];
  ll g[405][405];
  UnionFind uf(160005);

  cin >> H >> W;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> s[i][j];
    }
  }

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(s[i][j] == '.') continue;
      for(int k = 0; k < 4; k++){
	int x = j + dx[k], y =i + dy[k];
	if(0 <= x && x < W && 0 <= y && y < H && s[y][x] == '.'){
	  for(int l = 0; l < 4; l++){
	    int xx = x + dx[l], yy = y + dy[l];
	    if(xx == j && yy == i) continue;
	    if(0 <= xx && xx < W && 0 <= yy && yy < H && s[yy][xx] == '#'){
	      uf.unite(i*W+j, yy*W+xx);
	    }
	  }
	}
      }
    }
  }

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(s[i][j] == '.') continue;
      for(int k = 0; k < 4; k++){
	int x = j + dx[k], y = i + dy[k];
	ll cnt = uf.size(i * W + j);
	if(0 <= x && x < W && 0 <= y && y < H && s[y][x] == '.'){
	  g[y][x] = max(g[y][x], cnt);	  
	}
      }
    }
  }

  ll ans = 0;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      ans += g[i][j];
    }
  }
  cout << ans << endl;
  return 0;
}

/*

4 4
....
.#.#
....
...#

*/


Measured memory_bytes: 2304
import sys
sys.setrecursionlimit(200000)

def dfs(v, p=-1, c=0):
  for i in range(len(to[v])):
    u, w=to[v][i]
    if u==p:
      continue
    color[u]=(c+w)%2
    dfs(u, v, color[u])
    
N=int(input())
uvw=[list(map(int, input().split())) for _ in range(N-1)]
to=[[] for _ in range(N)]
color=[0 for _ in range(N)]
for i in range(N-1):
  u, v, w=uvw[i]
  u-=1
  v-=1
  to[u].append([v, w%2])
  to[v].append([u, w%2])

dfs(0)
for i in range(N):
  print(color[i])

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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

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

	vector<long long int> func(n + 1, 1);
	func[0] = 0;

	REP(i, 2, n + 1){
		for(int j = i; j <= n; j += i){
			func[j]++;
		}
	}

	long long int ans = 0;
	REP(i, 1, n + 1){
		ans += i * func[i];
	}

	cout << ans;

	return 0;
}

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

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

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

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

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

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

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

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

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

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

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        m: usize,
        v: [(usize1, chars); m]
    }
    let mut pe = vec![0; n];
    let mut ac = vec![0; n];
    for pr in &v {
        if ac[pr.0] == 1 {
            continue;
        }
        if pr.1[0] == 'A' {
            ac[pr.0] = 1;
        } else {
            pe[pr.0] += 1;
        }
    }
    println!("{} {}", ac.iter().cloned().sum::<usize>(), pe.iter().cloned().zip(ac).fold(0, |ac, (p, a)| ac + p * a));
}


Measured memory_bytes: 10492
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());//int型
		String sline = sc.next();
		String[] s = new String[n];
		for (int i=0; i<n; i++){
			s[i] = String.valueOf(sline.charAt(i));
		}
		int r = 0;
		int b = 0;
		for (int i = 0; i<n; i++){
			if (s[i].equals("R")){
				r++;
			} else {
				b++;
			}
		}
		if(r>b) {
			System.out.println("Yes");
		} else if (r<=b) {
			System.out.println("No");
		}
		
	}

}


Measured memory_bytes: 22736
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
#define int ll
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false


signed main(void){
    int A;
    string b;
    cin >> A >> b;
    int B=0;
    REP(i,b.size()){
        if(b[i]!='.'){
            B*=10;
            B+=(b[i]-'0');
        }
    }
    int R = A*B;
    R /=100;
    cout << R << endl;
    return 0;
}




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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define debug(x) cerr << (#x) << "is "<< x << "\n"

using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e4 + 10;

vector<int> g[N];
vector<bool> vis(N,false);
vector<int> c;
vector<int> score;
int l=0;
ll ans=0;

void dfs(int u,int e){
	for(auto v : g[u]){
		if(v!=e){
			score[v] = c[l++];
			dfs(v,u);
		}
	}
}

void dfs1(int u){
	vis[u] = true;
	for(auto v : g[u]){
		if(vis[v]) continue;
		ans+=min(score[v],score[u]);
		dfs1(v);
	}
}

int32_t main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	int n;
	cin >> n;
	f(i,0,n-1){
		int a,b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	c.assign(n,0);
	score.assign(n+1,0);
	f(i,0,n){
		cin >> c[i];
	}
	sort(all(c),greater<int>());
	ll start=-1;
	f(i,1,n+1){
		if(g[i].size()==1){
			start=i;
			break;
		}
	}
	score[start] = c[l];
	l++;
	dfs(start,-1);
	dfs1(start);
	cout << ans << "\n";
	f(i,1,n+1){
		cout << score[i] << " ";
	}
	return 0;
}

Measured memory_bytes: 1408
from sys import stdin


def main():
    A = stdin.readline().rstrip()
    B = stdin.readline().rstrip()
    if A == B:
        print('EQUAL')
    elif len(A) < len(B):
        print('LESS')
    elif len(A) > len(B):
        print('GREATER')
    else:
        for a, b in zip(A, B):
            if a < b:
                print('LESS')
                break
            elif a > b:
                print('GREATER')
                break
            else:
                pass


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
typedef long long lint;
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(lint (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
typedef map<lint,lint> M;
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
    
 
  int main(){
   lint n,q;
   string s;
   cin>>n>>q;

   cout<<n*q;
          }
     
  
      
      
    

  
          
  

Measured memory_bytes: 3724
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define mp(a,b) make_pair((a), (b))
#define mt(a,b,c) make_tuple((a),(b),(c))
#define DEBUGM(d,n,m,i,j) printf("DEBUGM :\n"); rep(i,n){ rep(j,m) printf("%d ", d[i][j]); printf("\n");} printf("DEBUGM END LINE\n")

typedef long long ll;

const ll INF =1LL << 62;
const int inf =1 << 29;

#define MAX_VER 105

int d[MAX_VER][MAX_VER];

void init(){
    rep(i,MAX_VER) rep(j,MAX_VER)d[i][j] = i==j ? 0 : inf;
}
void make(vector<vector<pair<int, int> > > &adl){
    rep(i, adl.size()) rep(j,adl[i].size()){
        int v = i, u = adl[i][j].first,c = adl[i][j].second;
        u--;
        d[v][u] = c; d[u][v] = c; 
    }
}

void warshall_floyd(int v){
    rep(k,v){ 
        rep(i,v){ 
            rep(j,v){
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<tuple< int, int, int> > ed(m);
    vector<vector <pair<int, int> > > adl(n);
    rep(i,m){
        int a,b,c;
        cin >> a >> b >> c;
        ed[i] = mt(a,b,c);
        adl[a-1].push_back(mp(b,c));
        adl[b-1].push_back(mp(a,c));
    }
    init();
    make(adl);
    warshall_floyd(n);
    //DEBUGM(d,n,n,i,j);
    int ans=0;
    rep(i,m){
        if(d[get<0>(ed[i])-1][get<1>(ed[i])-1] < get<2>(ed[i])) ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

a,b=rl()
#print('Odd' if a*b%2==1 else 'Even')
OE(a*b)

Measured memory_bytes: 2940
from itertools import permutations
from math import sqrt, factorial

n = int(input())
x, y = [], []
for _ in range(n):
    x_, y_ = map(int, input().split())
    x.append(x_); y.append(y_)

routeSum = 0
perm = list(permutations(i for i in range(n)))
for route in perm:
    for i in range(n-1):
        routeSum += sqrt( (x[route[i]] - x[route[i+1]])**2 + (y[route[i]] - y[route[i+1]])**2 )

print(routeSum/factorial(n))

Measured memory_bytes: 46704
#include <stdio.h>
#include <algorithm>

#define LIM_A 100001

char str[10001];
int y, m, d;
unsigned long long A[LIM_A];

void receive_input() {
	fgets(str, sizeof(str), stdin);
	sscanf(str, "%d/%d/%d", &y, &m, &d);

}

void initialize() {
	// nop
}

int main(void) {
	receive_input();
	initialize();

	if (m < 5) {
		printf("Heisei\n");
	} else {
		printf("TBD\n");
	}

	return 0;
}


Measured memory_bytes: 128
n,d = list(map(int,input().split()))
x = []
for i in range(n):
    x.append(list(map(int,input().split())))

def dist(a,b):
    return sum([(p-q)**2 for p,q in zip(a,b)])

def is_sqrt(p):
    if p == int(p**0.5)**2:
        return True
    else:
        return False

ans = 0

for i in range(n):
    for j in range(i,n):
        if i == j:
            pass
        else:
            # print("dist:",dist(x[i],x[j]))
            if is_sqrt(dist(x[i],x[j])):
                ans += 1
print(ans)

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

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    //cout<<"I must do it...Yeahhh";
    
    int tt=1;
    //cin>>tt;
    for(int kk=0;kk<tt;kk++)
    {
        int n,k,ans=1000000000000000000;
        cin>>n>>k;

        if(n>k)
            n%=k;

        if(abs(n-k)>n)
            cout<<n;
        else
            cout<<abs(n-k);

        //cout<<"Case #"<<kk+1<<": "<<trace<<' '<<r<<' '<<c<<'\n';
    }
    //cerr<<"[Execution : "<<(1.0*clock())/CLOCKS_PER_SEC<<"s]\n";
    return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := NewScanner()

	n := sc.NextInt()
	h := sc.NextInt()

	a := make([]int, n, n)
	b := make([]int, n, n)

	for i := 0; i < n; i++ {
		a[i] = sc.NextInt()
		b[i] = sc.NextInt()
	}
	sort.Ints(a)
	sort.Ints(b)

	amx := a[n-1]

	ans := 0
	for i := n - 1; i >= 0; i-- {
		if b[i] < amx {
			break
		} else {
			h -= b[i]
			ans++
			if h <= 0 {
				fmt.Printf("%+v\n", ans) // output for debug
				return
			}
		}
	}

	if h%amx == 0 {
		fmt.Printf("%+v\n", ans+(h/amx)) // output for debug
	} else {
		fmt.Printf("%+v\n", ans+1+(h/amx)) // output for debug
	}
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

int main(){
  int n; cin>>n;
  string s; cin>>s;
  rep(i,s.size()){
    rep(j,n){
      if(s[i]!='Z') s[i]++;
      else s[i]='A';
    }
  }
  cout<<s<<endl;
}

Measured memory_bytes: 3608
#include <stdio.h>

#include <ctype.h>



int main(){



  char a[1200];



  fgets(a,sizeof(a),stdin);



  int i;

  

  for(i=1;i<=1200;i++){



    if(a[i-1]=='\n')



      break;



    if(isupper(a[i-1]))



      printf("%c",tolower(a[i-1]));



    else if(islower(a[i-1]))



      printf("%c",toupper(a[i-1]));



    else



      printf("%c",a[i-1]);



  }



  printf("\n");



  return 0;



}

Measured memory_bytes: 524
fun main(args: Array<String>) {
    var n=readLine()!!.toInt()
    var nums=readLine()!!.split(" ").map { it.toInt() }
    var check=true
    for(num in nums){
        if(num%2==0){
            if(num%3!=0&&num%5!=0){
                println("DENIED")
                check=false
                break
            }
        }
    }
    if(check){
        println("APPROVED")
    }


}


Measured memory_bytes: 37732
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100000;

int main()
{
	int sx,sy,tx,ty;
	P pos;
	cin >> sx;
	cin >> sy;
	cin >> tx;
	cin >> ty;
	pos.first = sx;
	pos.second = sy;
	cout << "L";
	pos.first--;
	while(pos.second != ty+1){
		cout << "U";
		pos.second++;
	}
	while(pos.first != tx){
		cout << "R";
		pos.first++;
	}
	cout << "D";
	pos.second--;
	while(pos.first != sx){
		cout << "L";
		pos.first--;
	}
	while(pos.second != sy){
		cout << "D";
		pos.second--;
	}
	while(pos.first != tx){
		cout << "R";
		pos.first++;
	}
	while(pos.second != ty){
		cout << "U";
		pos.second++;
	}
	cout << "R";
	pos.first++;;
	while(pos.second != sy-1){
		cout << "D";
		pos.second--;
	}
	while(pos.first != sx){
		cout << "L";
		pos.first--;
	}
	cout << "U";
	pos.second++;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    // AtCoder
    // template
    ll n;
    cin >> n;
    map<string, ll> mp;

    rep(i, n) {
        string tmp;
        cin >> tmp;

        mp[(string)tmp]++;
    }

    cout << mp.size() << endl;
}


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

int main()
{
    vector<int> n(3);
    rep (i, 3)
        cin >> n[i];

    sort(n.begin(), n.end());
    cout << n[2] * 10 + n[1] + n[0] << endl;
    return 0;
}

Measured memory_bytes: 3552
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef pair<int, pi> pii;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define fax(i, a) for (int i = 0; i < (a); i++)
#define f0x(i, a, b) for (int i = (a); i < (b); i++)
#define faxd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define f0xd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define memeset memset

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

const int mod = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 200005;
const ld PI = 4*atan((ld)1);

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

ll comp(int n, int m) {
  long long num = m - 1;
  long long res_x = 0, res_y = 0;
  res_x = (long long)((num + 1) * (2 * num + 4) * num / 12) % mod;
  res_x = res_x * n * n % mod;
 
  num = n - 1;
  res_y = (long long)((num + 1) * (2 * num + 4) * num / 12) % mod;
  res_y = res_y * m * m % mod;
  return (res_x + res_y) % mod;
}
ll C(int a, int b) {
  long long top = 1, bot = 1;
  for (int i = 0; i < b; ++i) {
    top = top * (a - i) % mod;
    bot = bot * (b - i) % mod;
  }
 
  long long binpow = mod - 2, botinv = 1;
  while (binpow) {
    if (binpow & 1)
      botinv = botinv * bot % mod;
    bot = bot * bot % mod;
    binpow >>= 1;
    binpow %= mod;
  }
  return (top * botinv) % mod;
}
int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   int N,M,K; cin >> N >> M >> K;
   ll res = comp(N,M);
   cout << (res * C(N*M-2, K-2))%mod << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repR(i, n) for(int i = n; i >= 0; ++i)
#define FDS(i, n) for(int i = 0; i < n; ++i)
#define FDSR(i, n) for(int i = n; 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 VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define itn int
#define ednl endl
using namespace std;
typedef long long ll;
int main(){
	int N,K;
	vector<int> a(N);
	cin>>N>>K;
	FDS(i,N){
		cin>>a[i];
	}
	if((N-1)%(K-1)==0){
		cout<<(N-1)/(K-1)<<endl;
	}
	else{
		cout<<(N-1)/(K-1)+1<<endl;
	}
}

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;
typedef tuple<long long, long long, long long> tllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
bool compTuple(const tllint& arg1, const tllint& arg2) { return get<2>(arg1) > get<2>(arg2); }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    vector<int> l(n);
    for(int in=0;in<n;++in) {
        cin >> l[in];
    }

    int ans = 0;
    sort(l.begin(), l.end());
    for(int in=0;in<n;++in) {
        for(int jn=in+1;jn<n;++jn) {
            for(int kn=jn+1;kn<n;++kn) {
                if(l[kn]<l[in]+l[jn]&&l[in]!=l[jn]&&l[jn]!=l[kn]&&l[kn]!=l[in]) ++ans;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
n = int(input())
a = [0]
a += (list(map(int, input().split())))
a.append(0)
cost = 0
for i in range(n+1):
    cost += abs(a[i+1]-a[i])

for j in range(1, n+1):
    print(cost+abs(a[j-1]-a[j+1])-abs(a[j+1]-a[j])-abs(a[j]-a[j-1]))

Measured memory_bytes: 13920
#include<stdio.h>

int main(void)
{
        int n, a, b, i;
        scanf("%d", &n);

        if(n==1){
          printf("Hello World");}
        else if(n==2) {
               scanf("%d%d", &a, &b);
               i=a+b;
               printf("%d", i);
        }
        return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>

void countingsort(std::vector<int> &v, std::vector<int> &res)
{
    const int maxint = 10000;
    std::vector<int> counter(maxint, 0);

    for (int i = 0; i < v.size(); i++) {
        counter[v[i]]++;
    }

    for (int i = 1; i < maxint; i++) {
        counter[i] += counter[i-1];
    }

    for (int i = v.size() - 1; i >= 0; i--) {
        res[counter[v[i]]] = v[i];
        counter[v[i]]--;
    }
}

int main(int argc, char const *argv[])
{
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }

    std::vector<int> res(n+1);
    countingsort(v, res);

    for (int i = 1; i < n; i++) {
        std::cout << res[i] << " ";
    }
    std::cout << res[n] << std::endl;

    return 0;
}

Measured memory_bytes: 16800
var input = require('fs').readFileSync('/dev/stdin', 'utf8').trim();
var lines = input.split('\n');

while (true) {
    var x = +lines.shift();
    var h = +lines.shift();
    if (x + h == 0)
        break;

    console.log(((x * x) + (x * Math.sqrt(4 * h * h + x * x))).toFixed(6));
}

Measured memory_bytes: 7636
#pragma warning (disable:4996)
#include"bits/stdc++.h"
#include<cassert>
#define int long long
#define MRE assert(0);
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const long long mod = 1000000007;
const long long inf = 1ll<<61;
typedef pair<int, int> P;
typedef pair<int, P > PP;
int rwa[200006];

int modpow(int a, int x, int p) {
	int res = 1;
	while (x) {
		if (x & 1)res = res*a%p;
		a = a*a%p;
		x >>= 1;
	}
	return res;
}

signed main() {
	int n, p; cin >> n >> p;
	string s; cin >> s;
	rep(i, n)rwa[i] += s[i] - '0';
	for(int i=n-1;i>0;i--) {
		rwa[i - 1] = (rwa[i - 1] * modpow(10, n - i , p) + rwa[i]) % p;
	}
	rwa[n - 1] %= p;

//	rep(i, n)cout << rwa[i] << endl;

	map<int, int>M;
	rep(i, n)M[rwa[i]]++;
	M[0]++;
	int ans = 0;

	for (auto itr = M.begin(); itr != M.end(); itr++) {
		int x = itr->second;
		ans += x*(x - 1) / 2;
	}

	if (p == 2||p==5) {
		int res = 0;
		rep(i, n) {
			int D = s[i] - '0';
			if (D%p == 0) {
				res += i + 1;
			}
		}
		ans = res;
	}
	cout << ans << endl;
}

Measured memory_bytes: 2564
/**Bismillahir Rahmanir Raheem
    Author:Refat(BSMRSTU)**/
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const double pi=2*acos(0.0);
const double esp=1e-9;
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}
int ar[N];
int main() {
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);
    int test=1,h,n,sum=0;
    ///scanf("%d",&test);
    for(int cs=1; cs<=test; cs++) {
       scanf("%d %d",&h,&n);
       for(int i=1;i<=n;i++){
        scanf("%d",&ar[i]);
        sum+=ar[i];
       }
       if(sum>=h){
        printf("Yes\n");
       }
       else{
        printf("No\n");
       }
    }
    return 0;
}



Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int n,k,t=1,len[2003],can[2003][20003],siz,b,loc,b1[10003],len1,che=1;
string ans,a[2003],p,dp[10003];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		len[i]=a[i].length();
		for(int j=0;j<len[i];j++)
			if(a[i][j]!='a'&&a[i][j]!='b')
				che=0;
	}
	if(che==1)
	{
		for(register int i=1;i<=n;i++)
		{
			len1=a[i].length();
			for(register int j=k-len1;j>=1;j--)
			if(b1[j]==1)
			{
				if(b1[j+len1]==1)
				{
					if(dp[j+len1]>dp[j]+a[i])
						dp[j+len1]=dp[j]+a[i];
				}
				else
					dp[j+len1]=dp[j]+a[i],b1[j+len1]=1;
			}
			if(b1[len1]==1)
				dp[len1]=min(dp[len1],a[i]);
			else
				dp[len1]=a[i],b1[len1]=1;		
		}
		cout<<dp[k];
		return 0;
	}
	for(int i=1;i<=n+1;i++)
		can[i][0]=1;
	for(int i=n;i>=1;i--)
		for(int j=k;j>=0;j--)
		{
			if(can[i+1][j]==1||can[i+1][j+len[i]]==1)
				can[i][j+len[i]]=1;
			if(can[i+1][j]==1)
				can[i][j]=1;
		}
	siz=k;
	while(t<=n&&ans.length()<k)
	{
		b=0;
		for(int i=n;i>=t;i--)
			if(siz-len[i]>=0&&can[i+1][siz-len[i]]==1&&(b==0||a[i]<=p))
				p=a[i],b=1,loc=i;
		t=loc+1,ans+=p,siz-=len[loc];
		if(b==0)
			return 0;
	}
	cout<<ans;
	return 0;	
}


Measured memory_bytes: 156544