akhauriyash/Code-Regression huggingface dataset:
from functools import lru_cache


mod = 10 ** 9 + 7
N, K = map(int, input().split())

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)




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


int main(){
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (i < B && j < A) {
                printf("0");
            }
            else if (i >= B && j < A) {
                printf("1");
            }
            else if (i < B && j >= A) {
                printf("1");
            }
            else {
                printf("0");
            }
            
        }
        printf("\n");
    }
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;
 
signed main(){
    int n;cin>>n;
    double p[n];
    REP(i,n)cin>>p[i];
    double dp[n+1][n+1];
    REP(i,n+1)REP(j,n+1)dp[i][j]=0;
    dp[0][0]=1;
    REP(i,n){
        dp[i+1][0]=dp[i][0]*(1-p[i]);
        REP(j,i+1) dp[i+1][j+1]+=dp[i][j]*p[i]+dp[i][j+1]*(1-p[i]);
    }
    double ans=0;
    for(int i=n/2+1;i<=n;i++){
        ans+=dp[n][i];
    }	
  	cout<<fixed<<setprecision(20.20);
    cout<<ans<<endl;
}

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

int main()
{
    int N;
    cin >> N;
    map<string, int> mp;
    for(int a = 0;a < N;a++){
        string str;
        cin >> str;
        mp[str]++;
    }
    int M;
    cin >> M;
    for(int a = 0;a < M;a++){
        string str;
        cin >> str;
        mp[str]--;
    }
    int ans = 0;
    for(pair<string, int> pa : mp){
        ans = max(pa.second, ans);
    }
    cout<<ans<<endl;
    return 0;
}

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


#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  int64_t n;
  cin >> n;
  cout << n*(n-1)/2 << endl;
  return 0;
}




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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;


#include <vector>
#include <sstream>
#include <ostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cassert>

using B = bitset<2000*2000+10>;

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

  int N;
  cin >> N;
  VL xs(N);
  cin >> xs;

  int sum = 0;
  B b;
  b.set(0);
  REP(i,N){
	b |= b << xs[i];
	sum += xs[i];
  }

  int k = b.count() / 2;
  int i = 0;
  while(true){
	if(b[i]){
	  if(--k < 0){
		cout << i << endl;
		break;
	  }
	}
	++i;
  }
  
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

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

ll combination(ll n, ll r) {
  return factorial(n) / (factorial(r) * factorial(n - r));
}

ll permutation(ll n, ll r) { return factorial(n) / factorial(n - r); }

template <typename T>
void remove(std::vector<T>& vector, unsigned int index) {
  vector.erase(vector.begin() + index);
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}
// for (auto p : prime_factor(n)) {
//	while (p.second--) {
//		cout << p.first << endl;
//	}
//}

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> a(n + 1);
  REP(i, n) {
    if (s[i] == '<') {
      a[i + 1] = a[i] + 1;
    }
  }
//  REP(i, n + 1) { cout << a[i] << endl; }
//  cout << "------" << endl;
  RREP(i, n) {
    if (s[i] == '>') {
      a[i] = max(a[i], a[i + 1] + 1);
    }
  }
//  REP(i, n + 1) { cout << a[i] << endl; }
//  cout << "------" << endl;
  ll ans = 0;
  REP(i, n + 1) { ans += a[i]; }
  cout << ans << endl;
  return 0;
}

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

int n,m;
int s[10],c[10];

bool check(int x){
    vector<int> v;
    while(x){
        v.push_back(x%10);
        x/=10;
    }
    if(v.empty())v.push_back(0);
    reverse(v.begin(),v.end());
    if(v.size()!=n)return false;
    for(int i=0;i<m;i++){
        if(s[i]>v.size()||v[s[i]-1]!=c[i])return false;
    }
    return true;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>s[i]>>c[i];
    }
    for(int i=0;i<1000;i++){
        if(check(i)){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;

    return 0;
}

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

typedef long long int64;

const int MOD = 1e9 + 7;

struct Eratosthenes {
  vector< bool > prime;
  Eratosthenes(int _size) {
    init(_size);
  }

  void init(int n) {
    prime.resize(n + 1);
    for(int i = 0; i < prime.size(); ++i) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i = 2; i < sqrt(n); i++) {
      if (prime[i]) {
        for (int j = 0; i * (j + 2) < n; j++) {
	  prime[i * (j + 2)] = false;
	}
      }
    }
  }
};

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

  Eratosthenes e(N + 1);
  
  int64 ans = 1ll;
  for (int i = 2; i <= N; ++i) {
    if (!e.prime[i]) continue;
    int64 sm = 1ll;
    
    for (int j = 2; j <= N; ++j) {
      int64 tmp = j;
      while (tmp % i == 0) {
	sm++;
	tmp /= i;
      }
    }
    (ans *= sm) %= MOD;
  }

  cout << ans << endl;
  
  return 0;
}


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

using namespace std;

int main() {
 	int a, b;
 	scanf("%d %d", &a, &b);
 	bool bb = false;
 	for (int i = 1; i < 4; i++) {
 		if ((a * b * i) & 1) {
 			bb = true;
 			break;
		}
 	}
 	if (bb) printf("Yes\n");
 	else printf("No\n");
	return 0;
}

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

using namespace std;
using ll = long long;
 
int main() {
cout<<fixed<<setprecision(10);

int N;
cin >> N;
vector<string> S(N);

for (int i=0;i<N;i++){
    cin >> S.at(i);
}

sort(S.begin(),S.end());
S.erase(unique(S.begin(), S.end()), S.end());
cout << S.size();
	
}

Measured memory_bytes: 9520
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

int n;
string p;

Int dp[3300][3300];
Int dp_sum[3300][3300];

int main(){
    cin >> n;
    cin >> p;
    dp[0][0] = 1;
    for(int i = 1;i < n;i++){
        for(int j = 0;j <= i-1;j++){
            dp_sum[i-1][j] = dp[i-1][j];
            if(j-1 >= 0)dp_sum[i-1][j] += dp_sum[i-1][j-1];
            dp_sum[i-1][j] %=MOD;
        }
        for(int j = 0;j <= i;j++){
            if(p[i-1] == '<'){
                if(j-1 >= 0)dp[i][j] = dp_sum[i-1][j-1];
            }
            else{
                dp[i][j] = dp_sum[i-1][i-1];
                if(j-1 >= 0) dp[i][j] -= dp_sum[i-1][j-1];
                dp[i][j] %= MOD;
            }
        }
    }
    
    Int ans = 0;
    for(int i = 0;i < n;i++){
        ans += dp[n-1][i];
        ans %= MOD;
    }
    if(ans < 0)ans += MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 156416
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int v = sc.nextInt();
    int b = sc.nextInt();
    int w = sc.nextInt();
    int t = sc.nextInt();
    if(Math.abs(b-a) <= (long)t*(v-w))
      System.out.println("YES");
    else
      System.out.println("NO");
  }
}

Measured memory_bytes: 35852
while True:
    rows = []
    total = {}
    n = int(input())
    if (n == 0):
        break

    for r in range(n):
        datas = map(int, input().split())
        ds = list(datas)
        rows.append(ds)
            
    for r in range(n):
        s = 0
        for c in range(n):
            s += rows[r][c]
            if (c not in total):
                total[c] = rows[r][c]
            else:
                total[c] += rows[r][c]

        rows[r].append(s)
        if (n not in total):
            total[n] = s
        else:
            total[n] += s

    for r in range(n):
        for c in range(len(rows[r])):
            print("{0:>5}".format(rows[r][c]), end="")
        print()

    for t in range(len(total)):
        print("{0:>5}".format(total[t]), end="")
    print()





Measured memory_bytes: 5632
#![allow(non_snake_case)]
use proconio::input;
use std::collections::HashMap;

fn is_bingo(is_hole: &Vec<Vec<bool>>) -> bool {
    let col0 = is_hole[0][0] && is_hole[1][0] && is_hole[2][0];
    let col1 = is_hole[0][1] && is_hole[1][1] && is_hole[2][1];
    let col2 = is_hole[0][2] && is_hole[1][2] && is_hole[2][2];

    let row0 = is_hole[0][0] && is_hole[0][1] && is_hole[0][2];
    let row1 = is_hole[1][0] && is_hole[1][1] && is_hole[1][2];
    let row2 = is_hole[2][0] && is_hole[2][1] && is_hole[2][2];

    let x0 = is_hole[0][0] && is_hole[1][1] && is_hole[2][2];
    let x1 = is_hole[0][2] && is_hole[1][1] && is_hole[2][0];

    return [col0, col1, col2, row0, row1, row2, x0, x1].iter().any(
        |&b| b,
    );
}

fn main() {
    input! {
        As: [[i64; 3]; 3],
        N: usize,
        Bs: [i64; N],
    }

    let mut is_hole: Vec<Vec<bool>> = vec![vec![false; 3]; 3];
    let mut num_to_ind: HashMap<i64, (usize, usize)> = HashMap::new();

    for (i, lst) in As.iter().enumerate() {
        for (j, &a) in lst.iter().enumerate() {
            let tpl: (usize, usize) = (i, j);
            num_to_ind.insert(a, tpl);
        }
    }

    for b in Bs.iter() {
        if num_to_ind.contains_key(&b) {
            let (i, j): (usize, usize) = *num_to_ind.get(&b).unwrap();
            is_hole[i][j] = true;
        }
    }

    let ans = if is_bingo(&is_hole) { "Yes" } else { "No" };
    println!("{}", ans);
}


Measured memory_bytes: 2144
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            var w = Console.ReadLine().Split(' ').Select(x=> int.Parse(x)).ToArray();
            string res;
            int diff = w[0] + w[1] - w[2] - w[3];

            if (diff >0)
            {
                res = "Left";
            }
            else if (diff == 0)
            {
                res = "Balanced";
            }
            else { res = "Right"; }

            Console.WriteLine(res);
        }




    }
}


Measured memory_bytes: 11348
def main():
    from itertools import accumulate
    n, c, *stc = map(int, open(0).read().split())
    table = [0] * 2 * (10 ** 5 + 1)
    m = list(zip(stc[::3], stc[1::3], stc[2::3]))
    m.sort(key=lambda a: (a[2], a[0], a[1]))

    ch_ = 0
    t_ = 0
    for s, t, ch in m:
        if ch != ch_:
            ch_ = ch
            t_ = 0
        if t_ == 2 * s:
            table[t_ + 1] += 1
        else:
            table[2 * s - 1] += 1

        table[2 * t + 1] -= 1
        t_ = 2 * t

    *x, = accumulate(table)
    ans = max(x)

    print(ans)


if __name__ == '__main__':
    main()


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

signed main(){
  lint N, x; cin >> N >> x;
  vector<lint> a(N), b(N);
  for(lint i = 0; i < N; i++) {cin >> a[i]; b[i] = a[i];};
  if(a[0] > x) a[0] = x;
  for(lint i = 1; i < N; i++){
    if(a[i] + a[i - 1] > x) a[i] -= (a[i] + a[i - 1] - x);
  }
  lint ans = 0;
  for(lint i = 0; i< N; i++) ans += (b[i] - a[i]);
  cout << ans << endl;
}

Measured memory_bytes: 1920
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();

            int res = 0;
            for(int i = 0; i < s.Length; ++i)
            {
                if (!s[i].Equals(t[i]))
                {
                    ++res;
                }
            }

            Console.WriteLine(res);
        }
    }
}

Measured memory_bytes: 27272
import sys
input = sys.stdin.readline
N = int(input())
H = [int(x) for x in input().split()]

temp = H[0] - 1
for i in range(1, N) :
    if H[i] > temp :
        temp = H[i] - 1
    elif H[i] == temp :
        temp = H[i]
    else :
        print("No")
        exit()

print("Yes")


Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int Ap,Bp,ABp,Aq,Bq;
  cin >> Ap >> Bp >> ABp >> Aq >> Bq;
  if ( (Ap+Bp)/2 < ABp ) {
    cout << Ap*Aq + Bp*Bq << endl;
  }
  else {
    long int ans = 0;
    int Y;
    Y = min(Aq,Bq);
    ans += ABp * Y * 2;
    int Z,Za;
    if ( Y == Aq ) {
      Z = Bp;
      Za = Bq - Aq;
    }
    else {
      Z = Ap;
      Za = Aq - Bq;
    }
    if ( 2 * ABp >=  Z ) {
      ans += Z * Za;
    }
    else {
      ans += ABp * 2 * Za;
    }
    cout << ans << endl;
  }
}
    

Measured memory_bytes: 256
#include "iostream"
using namespace std;
int main() {
	char a, b;
	cin >> a >> b;
	if (a == 'H') {
		if (b == 'H')cout << 'H' << endl;
		else cout << 'D' << endl;
	}
	else {
		if (b == 'H')cout << 'D' << endl;
		else cout << 'H' << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,y;
  bool able = false;
  cin >> n >> y;
  int i = 0;
  int j = 0;
  for(i = 0;i <= n;i++){
    for(j = 0;j <= n-i;j++){
      int x = 10000*i+5000*j+1000*(n-i-j);
      if(x == y){
        able = true;
        break;
      }
    }
    if(able) break;
  }
  if(able)cout << i << " " << j << " " << n-i-j;
  else cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

class Main {
	public static void main(String args[]) throws IOException {
		@SuppressWarnings("resource")
		Scanner cin = new Scanner(System.in);
		ArrayList<String> inLines = new ArrayList<String>();
		for (; cin.hasNext();) {
			inLines.add(cin.nextLine());
		}
		Solver solver = new Solver();
		solver.solve(inLines);
	}
}

class Solver {

	public void solve(ArrayList<String> inLines) {
		String[] strArr = inLines.get(0).split(" ");
		int N = Integer.parseInt(strArr[0]);
		long A = Long.parseLong(strArr[1]);
		long B = Long.parseLong(strArr[2]);
		strArr = inLines.get(1).split(" ");
		long[] town = new long[N];
		for (int i = 0; i < N; i++)
			town[i] = Long.parseLong(strArr[i]);

		long ans = 0;
		int cnt = 0;
		for (int i = 0; i < N - 1; i++) {
			if ((town[i + 1] - town[i]) * A < B) {
				ans += (town[i + 1] - town[i]) * A;
				cnt++;
			}
		}
		ans += (N - 1 - cnt) * B;
		System.out.println(ans);
	}
}


Measured memory_bytes: 35416
#include <iostream>
using namespace std;
int v[10][10];
int f(int x){
    while(x >= 10) x /= 10;
    return x;
}
int main(void){
    int n;
    cin >> n;
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            v[i][j] = 0;
        }
    }
    
    for(int i=1;i<=n;i++){
        v[f(i)][i%10]++;
    }
    
    long long ans = 0;
    for(int i=1;i<10;i++){
        for(int j=1;j<10;j++){
            ans += v[i][j] * v[j][i];
        }
    }
    cout << ans << endl;
}


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

#define ll long long
#define ull unsigned long long

using namespace std;

const ull MOD = 1000000007;

const ull MAX = 510000;
 
ull fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

ull COM(ull n, ull k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

	ull xval = 0;
	for (int ii = 1; ii < M; ++ii){
		xval += ii * (M-ii) % MOD;
	}
	xval *= N*N % MOD;

	ull yval = 0;
	for (int ii = 1; ii < N; ++ii){
		yval += ii * (N-ii) % MOD;
	}
	yval *= M*M % MOD;
	ull ans = (xval + yval) % MOD;

	//combinationを考慮
	ull total = N*M-2;
	ull select = min(K-2, total - (K-2));

	ans = (ans * COM(total, select)) % MOD;

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 12160
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
  int data1[10],data2[10];
  int sum1=0,sum2=0;
  for(int i=0;i<10;i++){
    cin >> data1[i];
  }
  for(int i=0;i<10;i++){
    cin >> data2[i];
  }
  for(int j=0;j<3;j++){
    for(int i=0;i<9-j;i++){
      if(data1[i]>data1[i+1]){
	int temp;
	temp=data1[i];
	data1[i]=data1[i+1];
	data1[i+1]=temp;
      }
      if(data2[i]>data2[i+1]){
	int temp;
	temp=data2[i];
	data2[i]=data2[i+1];
	data2[i+1]=temp;
      }
    }
    sum1+=data1[9-j];
    sum2+=data2[9-j];
  }
  cout << sum1 << " " << sum2 << endl;
  return 0;
}

Measured memory_bytes: 1164
/*
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<typename T=ll>inline auto vec2(typename vector<T>::size_type h,typename vector<T>::size_type w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
*/
#include<vector>
class mod_int{
private:
    unsigned long long num;
public:
    static constexpr auto mod=static_cast<unsigned long long>(1e9+7);
    static mod_int pow(mod_int x,unsigned long long y)
    {
        return y==0?1:y%2==0?pow(x*x,y/2):x*pow(x,y-1);
    }
    mod_int()=default;
    mod_int(unsigned long long n):num(n%mod)
    {
    }
    explicit operator unsigned long long()const
    {
        return num;
    }
    bool operator==(const mod_int&mi)const
    {
        return num==mi.num;
    }
    bool operator!=(const mod_int&mi)const
    {
        return !operator==(mi);
    }
    mod_int operator~()const
    {
        return pow(*this,mod-2);
    }
    mod_int operator+(const mod_int&mi)const
    {
        return num+mi.num;
    }
    mod_int operator-(const mod_int&mi)const
    {
        return num+mod-mi.num;
    }
    mod_int operator*(const mod_int&mi)const
    {
        return num*mi.num;
    }
    mod_int operator/(const mod_int&mi)const
    {
        return num*(~mi).num;
    }
    mod_int&operator+=(const mod_int&mi)
    {
        return*this=operator+(mi);
    }
    mod_int&operator-=(const mod_int&mi)
    {
        return*this=operator-(mi);
    }
    mod_int&operator*=(const mod_int&mi)
    {
        return*this=operator*(mi);
    }
    mod_int&operator/=(const mod_int&mi)
    {
        return*this=operator/(mi);
    }
};
class combination_modulo:mod_int{
private:
    std::vector<mod_int>factorial_mod;
public:
    combination_modulo(unsigned long long max_n):factorial_mod(max_n+1)
    {
        factorial_mod[0]=1;
        for(unsigned long long i=1;i<=max_n;++i)factorial_mod[i]=factorial_mod[i-1]*i;
    }
    mod_int operator()(unsigned long long n,unsigned long long r)
    {
        return n<r?0:factorial_mod[n]/(factorial_mod[r]*factorial_mod[n-r]);
    }
};
#include<iostream>
int main()
{
    long long x,y;
    std::cin>>x>>y;
    if((2*y-x)%3!=0||(2*x-y)%3!=0){
        std::cout<<0<<std::endl;
    }else{
        long long a=(2*y-x)/3,b=(2*x-y)/3;
        if(a<0||b<0){
            std::cout<<0<<std::endl;
        }else{
            combination_modulo cm(a+b);
            std::cout<<(unsigned long long)cm(a+b,a)<<std::endl;
        }
    }
}


Measured memory_bytes: 5504
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

int dp[310][310][310];

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	rep(i, n + 1) rep(j, n + 1) rep(k, n + 1) dp[i][j][k] = INF;
	dp[0][0][0] = 0;
	rep(i, n) {
		rep(j, n) {
			rep(k, n) {
				int d;
				if (k != 0) d = max(0LL, a[i] - a[k - 1]);
				else d = a[i];
				chmin(dp[i + 1][j][i + 1], dp[i][j][k] + d);
				chmin(dp[i + 1][j + 1][k], dp[i][j][k]);
			}
		}
	}
	int ans = INF;
	rep(j, x + 1) {
		rep(k, n + 1) {
			chmin(ans, dp[n][j][k]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 227584
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);

int extgcd(int a, int b, int &x, int &y){
    int d = a;
    if(b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return d;
}

int gcd_multi(vec a){
    int x, y, g;
    g = a[0];
    FOR(i, 1, a.size()) g = extgcd(g, a[i], x, y);
    return g;
}

signed main(){

    int N; cin >> N;
    vec A(N); readvec(A);

    int odd = 0, oddi;
    REP(i, N){
        if(A[i] % 2 == 1){
            odd++;
            oddi = i;
        }
    }

    if((N - odd) % 2 == 1){
        cout << "First";
        return 0;
    }

    if(!(odd == 1 && A[oddi] > 1)){
        cout << "Second";
        return 0;
    }

    bool f = true;

    while(true){

        A[oddi]--;
        int g = gcd_multi(A);
        REP(i, N) A[i] /= g;

        odd = 0, oddi;
        REP(i, N){
            if(A[i] % 2 == 1){
                odd++;
                oddi = i;
            }
        }

        if((N - odd) % 2 == 1){
            f = !f;
            break;
        }

        if(!(odd == 1 && A[oddi] > 1)) break;

        f = !f;
    }

    if(f){
        cout << "First";
    }else{
        cout << "Second";
    }

    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 1920
n = int(input())
s = [input() for i in range(n)]

ac = s.count('AC')
wa = s.count('WA')
tle = s.count('TLE')
re = s.count('RE')
print('AC'+' '+'x'+' '+str(ac))
print('WA'+' '+'x'+' '+str(wa))
print('TLE'+' '+'x'+' '+str(tle))
print('RE'+' '+'x'+' '+str(re))




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

#define MOD 1000000007

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

    vector<long> nSum(n+1, 0); 
    for (int i = 1; i <= n; i++){
        nSum.at(i) = nSum.at(i-1) + i;
    }
    
    long sumMax, sumMin, cnt = 0;
    for (int i = k; i <= n+1; i++){
        sumMin = nSum.at(i-1);
        sumMax = ( (n-i < 0) ? nSum.at(n) : nSum.at(n) - nSum.at(n-i) );
        cnt = (cnt + sumMax - sumMin + 1) % MOD;
    }

    cout << (int)cnt << endl;

    return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    ll ans=1e18;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            ll x=n/i;
            ans=min(ans,(ll)(i-1)+(x-1LL));
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(){
  char S[3], T[3];
  cin >> S;
  cin >> T;
  
  int cnt = 0;
  for(int i=0; i<3; i++){
    if(S[i] == T[i]){
      cnt++;
    }
  }
  
  cout << cnt;
  return 0;
}

Measured memory_bytes: 256
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	std::string S;
	std::cin >> S;
	
	bool occur[26] = {};
	for (auto ch : S) {
		occur[ch-'a'] = true;
	}
	for (int i = 0; i < 26; ++i) {
		if (!occur[i]) {
			std::cout << (char)('a'+i) << "\n";
			return 0;
		}
	}
	std::cout << "None\n";
}


Measured memory_bytes: 512
// inputに入力データ全体が入る
function Main(input) {
		input = input.split(" ");
	
	//文字列から10進数に変換するときはparseIntを使います
	    var K = parseInt(input[0], 10);
         var X = parseInt(input[1], 10);
    var a = X - (K-1);
    var b = X + (K-1);
    
    var tem = "";
    for (var f = a; f <= b ; f++) {
                 tem += f +' ';}
   //         tem[f] = r;
            console.log(tem)

 // var a = "";
//for (var i = 1; i <= 10; i++) {
 //   a += i;
//}
//console.log(a);
  
  	   }    //    1    
     
  //*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  
  

Measured memory_bytes: 7372
K, N= gets.split(" ").map(&:to_i)
homes = gets.split(" ").map(&:to_i)
mx = 0
homes.push(homes[0]+K)
(N).times do |i|
   result = i+1 > homes.length ? homes[-1] - homes[0] : homes[i+1] - homes[i]
   mx = [result, mx].max
end
puts "#{K-mx}"



Measured memory_bytes: 21384
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい
// https://github.com/atcoder/live_library
// cppdbg: test.exeのterminalに標準入力を打てる

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
#define ub(a,x) (upper_bound(ALL(a),x)-a.begin())
#define lb(a,x) (lower_bound(ALL(a),x)-a.begin())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<ll, vector<ll>, greater<ll> > gpq; //逆順priority_queue
typedef priority_queue<ll> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;


const ll MAX_PDEC=1000000;
vector<ll> D(MAX_PDEC);
void make_prime_list(){
    for(ll i=1;i<=1000000;i++)D[i]=i;
    for(ll i=2;i<=1000000;i++){
        for(ll j=i;j<=1000000;j+=i){
            D[j]=min(D[j],i);
        }
    }
}

void prime_decomposition(ll N,vector<int> &ans){
    ans.clear();
    ll v=N;
    while(v>1){
        ans.push_back(D[v]);
        v/=D[v];
    }
}

void ans2vecpair(vector<int> ans,vector<pii> &p){
    p.clear();
    for(int i=0;i<ans.size();i++){
        if(p.size()==0){
            p.push_back(make_pair(ans[i],1));
        }else if(p[p.size()-1].first==ans[i]){
            p[p.size()-1].second++;
        }else{
            p.push_back(make_pair(ans[i],1));
        }
    }
}

int main(){
    vi ans(0);
    vector<pii> p(0);
    make_prime_list();

    int N;cin>>N;
    int out=0;
    for(int i=1;i<=N;i+=2){
        prime_decomposition(i,ans);
        ans2vecpair(ans,p);
        int dcount=1;
        for(int j=0;j<p.size();j++){
            dcount*=p[j].second+1;
        }
        if(dcount==8)out++;
    }
    cout<<out<<endl;
}

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

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;

int main()
{
    ll n,m;
    cin >> n >> m;
    vector<pair<ll,ll>> a(n), b(m);
    vector<ll> ans(m);
    for(ll i = 0; i < n; i++)cin >> a[i].first >> a[i].second;
    for(ll i = 0; i < m; i++)cin >> b[i].first >> b[i].second;

    for(ll i = 0; i < n; i++){
        ll flag = -1,nin = 1e9;
        for(ll j = 0; j < m; j++){
            if(nin > abs(a[i].first - b[j].first) + abs(a[i].second - b[j].second)){
                nin = abs(a[i].first - b[j].first) + abs(a[i].second - b[j].second);
                flag = j;
            }
        }
        cout << flag + 1 << endl;
    }
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#define maxn 200005
int n,tp;
char st[maxn],s[maxn];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		if(s[i]=='T'&&tp&&st[tp]=='S') tp--;
		else st[++tp]=s[i];
	printf("%d\n",tp);
}

Measured memory_bytes: 512
#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>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1LL << 60;

int N;
long long h[110000][3];
long long dp[110000][3];

int main(){
    int N; cin >> N;
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < 3; ++j){
            cin >> h[i][j];
        }
    }

    rep(i,N){
        rep(j,3){
            rep(k,3){
                if(j==k){
                    continue;
                }
                chmax(dp[i+1][k],dp[i][j]+h[i][k]);
            }
        }
    }

    ll ans = 0;

    rep(i,3){
        chmax(ans,dp[N][i]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 5120
import sys
s=input()
t=input()
n=len(s)
d=dict()
d2=dict()
for i in range(n):
    if t[i] in d.keys():
        if d[t[i]] != s[i]:
            print("No")
            sys.exit()
    else:
        d[t[i]] = s[i]
    
    if s[i] in d2.keys():
        if d2[s[i]] != t[i]:
            print("No")
            sys.exit()
    else:
        d2[s[i]] = t[i]
else:
    print("Yes")

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

int main() {
 UL N;scanf("%u",&N);
 vector<int> A(N); rep(i,N) scanf("%d",&A[i]);
 A.erase(unique(A.begin(),A.end()),A.end());
 rep(i,A.size()) {if(i)printf(" "); printf("%d",A[i]);}
 printf("\n");
 return 0;
}




Measured memory_bytes: 3380
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String O = sc.next();
    String E = sc.next();
    for(int i=0;i<O.length()-1;i++){
      System.out.print(O.substring(i,i+1));
      System.out.print(E.substring(i,i+1));
    }
    System.out.print(O.substring(O.length()-1,O.length()));
    if(O.length()==E.length()){
      System.out.print(E.substring(E.length()-1,E.length()));
    }
                     
  }
  

  
}


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

int main() {
  int N = 0;
  cin >> N;
  int cnt_w = 0, cnt_e = 0;
  int ans = pow(10, 6);
  vector<char> A(N);
  vector<int> S_W(N, 0);
  vector<int> S_E(N, 0);
  rep(i, N){
    cin >> A[i];
  }
  rep(i, N){
    if (A[i]=='W'){
      cnt_w++;
      S_W[i] = cnt_w;
      S_E[i] = cnt_e;
    }
    if (A[i]=='E'){
      cnt_e++;
      S_W[i] = cnt_w;
      S_E[i] = cnt_e;
    }
  }
  rep(i, N){
    if (i==0) ans = min(ans, S_E[N-1] - S_E[i]);
    if (i==N-1) ans = min(ans, S_W[N-1]);
    else ans = min(ans, (S_W[i] + (S_E[N-1] - S_E[i])));
  }
  cout << ans << endl;
}

Measured memory_bytes: 2944
#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, m;
  cin >> n >> m;
  vector<pair<ll, ll>> ab(n);
  rep(i, n){
    cin >> ab[i].first >> ab[i].second;
  }
  sort(ab.begin(), ab.end());
  ll ans = 0;
  int count = 0;
  rep(i, n){
    while(ab[i].second > 0){
      if(count < m){
        ans += ab[i].first;
        ab[i].second--;
        count++;
      }
      else break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define for_p(i, a, b) for(int i = a; i < b; i++)
#define for_m(i, a, b) for(int i = a - 1; i >= b; i--)

//a = s1.size();
//vector<string> s1;
//string s2 = accumulate( s1.begin(), s1.end(), string() );

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0;
  int i = 0, j = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int a1[256], a2[512], a3[1024];
  //char s1[200000], s2[200000], s3[200000];
  string s1, s2, s3;
  
  cin >> a >> s1 >> b;
  
  for(i = 0; i < a; i++){
    if(s1[b - 1] != s1[i]){
      s2 += '*';
    }else{
      s2 += s1[i];
    }
  }
  cout << s2 << endl;
}
  


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

int main() {
  int n;
  cin>>n;
  pair<ll,ll> vec[n];
  for(int i=0;i<n;i++){
    cin>>vec[i].second>>vec[i].first;
  }
  sort(vec,vec+n);
  ll sum=0;
  for(int i=0;i<n;i++){
    sum+=vec[i].second;
    if(sum>vec[i].first){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 3328
n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
t = {}

for i in range(n):
    if s[i] in t:
        t[s[i]] += 1
    else:
        t[s[i]] = 1
ans = sum((i * (i - 1)) // 2 for i in t.values())

print(ans)

Measured memory_bytes: 19504
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define INF 1000000007

typedef pair<int, int> pint;
typedef long long ll;

/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define INF 1000000007

typedef pair<int, int> pint;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    cout << "Christmas ";
    for (int i = 0; i < 25 - N; i++)
    {
        cout << "Eve ";
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <iostream> 

  #include <iomanip>

using namespace std; 

  

int 

main () 

{ 

 double r;
 double pi = 3.14159265359;
 double a, p;
  
  cin >> r;
 a=r*r*pi;
 p= 2*pi*r;
 
   
 std::cout << std::fixed;
    std::cout << std::setprecision(5);
    
  cout<< a << " " << p <<endl; 

  return 0; 

 
} 


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

import sys

from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, R = MAP()
A = [a-1 for a in LIST()]
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

# 全体グラフの最短距離(ここから必要な頂点間だけ使う)
wf = floyd_warshall(G)

ans = INF
for r in range(R):
    # TSP(巡回セールスマン)
    dp = list2d(1<<R, R, INF)
    dp[1<<r][r] = 0
    for bit in range(1, (1<<R)-1):
        for i in range(R):
            if not (bit >> i & 1):
                continue
            for j in range(R):
                if bit >> j & 1:
                    continue
                a, b = A[i], A[j]
                dp[bit|1<<j][j] = min(dp[bit|1<<j][j], dp[bit][i] + int(wf[a,b]))
    ans = min(ans, min(dp[-1]))
print(ans)


Measured memory_bytes: 19176
#include <stdio.h>
#include <string.h>
#define N_MAX 100001


struct Card{
    char mark;
    int number;
    int tag;
};

void SwapElement(struct Card *c,int i, int j){
    struct Card buff;
    buff = c[i];
    c[i] = c[j];
    c[j] = buff;
}

int Partition(struct Card *c,int p, int r){
    int x = c[r].number;
    int i = p-1;
    int j;
    for(j=p;j<r;j++){
        if(c[j].number <= x){
            i++;
            SwapElement(c,i,j);
        }
    }
    SwapElement(c,i+1,r);
    return i+1;
}

void QuickSort(struct Card *c,int p,int r){
    int q;
    if(p<r){
        q = Partition(c,p,r);
        QuickSort(c,p,q-1);
        QuickSort(c,q+1,r);
    }
}

int isStable(struct Card *c, int len){
    int i;
    for(i=1; i<len; i++){
        if(c[i].number==c[i-1].number){
            if(c[i].tag < c[i-1].tag) return 0;
        }
    }
    return 1;
}


int main(){
    int n,i;
    struct Card c[N_MAX];

    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%1s %d",&c[i].mark, &c[i].number);
        c[i].tag = i;
    }

    QuickSort(c,0,n-1);

    if(isStable(c,n)) printf("Stable\n");
    else printf("Not stable\n");

    for(i=0; i<n; i++){
        printf("%c %d\n",c[i].mark,c[i].number);
    }

    return 0;
}


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

int abs(int x,int y){
  int z;
  if(x-y>=0){
    z = x-y;
  }else{
    z = y-x;
  }
  return z;
}

int minimum(int x,int y,int z){
  int min;
  if(x<=y&&x<=z){
    min = x;
  }else if(y<=x&&y<=z){
    min = y;
  }else if(z<=x&&z<=y){
    min = z;
  }
  return min;
}

int main() {
  int N,X,Y,min_dist;
  cin >> N >> X >> Y;
  vector<int> number(N);
  
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      min_dist = minimum(abs(j-i),abs(X,i)+1+abs(j,Y),abs(Y,i)+1+abs(j,X));
      number.at(min_dist)++;
    }
  }
  
  for(int i=1;i<N;i++){
    cout << number.at(i) / 2 << endl;
  }
  
}

Measured memory_bytes: 256
// author-Shivam gupta

#include <bits/stdc++.h>


using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))

#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)

#define IN(A, B, C) assert( B <= A && A <= C)

#define MP make_pair
#define FOR(i,a) for(int i=0;i<a;i++)

#define FOR1(i,j,a) for(int i=j;i<a;i++)

#define EB emplace_back

#define INF (int)1e9

#define EPS 1e-9

#define PI 3.1415926535897932384626433832795

#define MOD 1000000007

#define read(type) readInt<type>()
#define max1 100001
#define out(x) cout<<x<<'\n'
#define out1(x) cout<<x<<" "
#define END cout<<'\n'
const double pi=acos(-1.0);

typedef pair<int, int> PII;

typedef vector<int> VI;

typedef vector<string> VS;

typedef vector<PII> VII;

typedef vector<VI> VVI;

typedef map<int,int> MPII;

typedef set<int> SETI;

typedef multiset<int> MSETI;

typedef long int li;

typedef unsigned long int uli;

typedef long long int ll;

typedef unsigned long long int  ull;

bool isPowerOfTwo (int x)
{
  /* First x in the below expression is
    for the case when x is 0 */
  return x && (!(x&(x-1)));
}
void fast(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll power(ll x, ll y, ll p)
{
    ll res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
ll modInverse(ll n, ll p)
{
    return power(n, p-2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
ll ncr(ll n, ll r,ll p)
{
   // Base case
   if (r==0)
      return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    ll fac[n+1];
    fac[0] = 1;
    for (ll i=1 ; i<=n; i++)
        fac[i] = fac[i-1]*i%p;

    return (fac[n]* modInverse(fac[r], p) % p *
            modInverse(fac[n-r], p) % p) % p;
}

vector<int> v[max1];

void dfs(int ans[],bool x[],int cnt[],int j,int c){
    x[j]=true;
  for(int i=0;i<v[j].size();i++){
        if(cnt[v[j][i]]>=c){ans[v[j][i]]=j;cnt[v[j][i]]=c;}
    if(x[v[j][i]]==false){
        ans[v[j][i]]=j;
        cnt[v[j][i]]=c;
        dfs(ans,x,cnt,v[j][i],c+1);
    }
  }
}
#define deg_to_rad(deg) (((deg) / 360) * 2 * PI)
int main() {
	ll a;
	long double b;
	cin >> a >> b;
	ll tmp = a * (ll) ((b + 1e-6) * 100.0);
	cout << tmp / 100 << "\n";
}





Measured memory_bytes: 6092
#include <bits/stdc++.h>
using namespace std;
int countt = 0;

bool visited[200005];
vector<int> adj [200005];
void dfs(int i){
	visited[i] = true;
	countt++;
	for(int k: adj[i]){
		if(!visited[k]) dfs(k);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M; cin >> N >> M;
	int g = 1;
	for(int i = 0; i < M; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}					
	for(int i = 1; i <= N; i++){
		countt = 0;
		if(!visited[i]){
			dfs(i);
		} 
		g = max(g, countt);
	}
	int a = 0;
	// if(N % g) a++;
	cout << g + a;
	return 0;
}

Measured memory_bytes: 21036
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <queue> 
#include <cctype> 
#include <climits> 
#include <stack> 
#include <map> 
#include <cstring> 
#include <numeric>

using namespace std; 

const long long mod=1e9+7;

int main(){
    long long a,b;
    cin>>a>>b;

    cout<<a*b/__gcd(a,b)<<endl;

    return 0;
}

Measured memory_bytes: 256