akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    if(m==1)return 0*puts("0");
    if (n>=m) {
        puts("1");
        return 0;
    }
    m-=n;
    cout<<(m+n-2)/(n-1)+1<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
typedef long long int ll;
ll N, K;

ll solve(ll x) {
    ll lb = -1, ub = 1LL << 60;
    while(ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        ll val = mid - (mid / K + 1);
        if(val < x) lb = mid;
        else ub = mid;
    }

    if(ub % K == 0) return ub + 1;
    return ub;
}

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

    ll ans = 0;
    for(int i=0; i<N-1; i++) {
        ans = solve(ans);
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 2748
N = int(input())
S = input()

Rs = []
Bs = []
Gs = []

for i in range(len(S)):
    if S[i] == 'R':
        Rs.append(i)
    if S[i] == 'G':
        Gs.append(i)
    if S[i] == 'B':
        Bs.append(i)

#print(Rs)
#print(Gs)
#print(Bs)

sum = 0

for r in Rs:
    for g in Gs:
        sum += len(Bs)

        if r > g:
            l = r-g
            if r+l < len(S) and S[r + l] == 'B':
                sum -= 1
            if g-l > 0 and S[g - l] == 'B':
                sum -= 1

        else:
            l = g-r
            if len(S) > g + l and S[g + l] == 'B':
                sum -= 1
            if r - l > 0 and S[r - l] == 'B':
                sum -= 1

        if (r + g) % 2 == 0 and S[int((r + g) / 2)] == 'B':
            sum -= 1
            #print(r, end = " ")
            #print(g)

print(sum)

Measured memory_bytes: 9284
#include <iostream>
#include <math.h>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	ll x; cin >> x;
	ll a = 2 * (x / 11);
	ll b = x % 11;

	if (b != 0)
	{
		if (b > 6 && b < 11)a += 2;
		if (b <= 6)a++;
	}
	cout << a << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 9223372036854775807LL
#define inf 1000000007
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define lol long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
int c[1010][20];
int dp1[1<<13],dp2[1<<13];
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    int a[1010],b[1010];
    cin >>N>>M;
    for(int i=0;i<M;i++){
	cin >>a[i]>>b[i];
	for(int j=0;j<b[i];j++){
	    cin >>c[i][j];
	    c[i][j]--;
	}
    }
    for(int i=0;i<(1<<N);i++) dp1[i]=dp2[i]=inf;
    dp1[0]=0;
    for(int i=0;i<M;i++){
	for(int j=0;j<(1<<N);j++){
	    if(dp1[j]!=inf){
		int pos=0;
		for(int k=0;k<b[i];k++) pos|=(1<<c[i][k]);
		dp1[j|pos]=min(dp1[j|pos],dp1[j]+a[i]);
	    }
	}
	//for(int j=0;j<(1<<N);j++) dp1[j]=dp2[j],dp2[j]=inf;
    }
    if(dp1[(1<<N)-1]!=inf) cout <<dp1[(1<<N)-1]<<'\n';
    else cout <<"-1\n";
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

void ABC170B()
{
	int X, Y;
	cin >> X >> Y;

	for (int i = 0; i <= X; ++i)
	{
		int y = i * 2 + (X - i) * 4;
		if (y == Y)
		{
			cout << "Yes" << endl;
			return;
		}
	}
	cout << "No" << endl;
}

int main()
{
	ABC170B();
	return 0;
}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline
from collections import deque

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
visit = set()                                 # 訪れたかどうかをメモ ([]をつけないとtupleが展開されて各要素をsetに入れる操作になってしまう)
next_set = deque()                            # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる

def debug(p, t):
    player = p
    debug_grid = list(list(grid[h]) for h in range(H))
    debug_grid[start[0]][start[1]] = "S"
    debug_grid[goal[0]][goal[1]] = "G"
    debug_grid[player[0]][player[1]] = "P"
    print("~~~~~~~~~ t = " + str(t+1) + "  ~~~~~~~~")
    for debug_h in range(H):
        print("".join(debug_grid[debug_h][debug_w] for debug_w in range(W)))

def search(start=(0,0), goal=(None,None)):      #
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set.append((start, 0))                 # スタート地点を決める。第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        h, w = p
        for dh, dw in move:                     # 頂点 p から進める経路の候補から一つ選ぶ
            q = (h + dh, w + dw)
            if q[0] < 0 or q[0] >= H or q[1] < 0 or q[1] >= W:
                continue
            if grid[q[0]][q[1]] == "#":         # 壁があったら進まない
                continue
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            #### (debug code) ######
            # debug(q, t)
            ########################
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


H,W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
cnt = 0

for h in range(H):
    grid.append(input())
    cnt += grid[-1].count(".")
start = (0,0)
goal = (H-1, W-1)
res = search(start,goal)
if res == -1:
    print(-1)
else:
    print(cnt - res - 1)

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

int N;
string s;
int main(){
    cin >> N;
    cin >> s;
    int num = 0;
    for (int i = 0; i < N; i++){
        if (s[i] == 'R'){
            num += 1;
        }
        else{
            num -= 1;
        }
    }
    if (num > 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int main(){
	ios::sync_with_stdio(0);
	ll n, k;
	cin >> n >> k;
	vector<ll> vs(n+1, 0);
	ll ans = 0;
	for(int i=1; i<=n; ++i){
		cin >> vs[i]; vs[i]%=k;
		if(vs[i]==0) vs[i] = 1;
		else vs[i] = -(vs[i]-1);
	}
	for(int i=1; i<=n; ++i){
		vs[i] += vs[i-1];
		if(vs[i]>0) vs[i]%=k;
		else vs[i] = (((-vs[i])%k)*(k-1))%k;
	}
//	for(int i=0; i<=n; ++i)
//		cout << vs[i] << (i==n?'\n':' '); 	
	map<ll, ll> mp;
	for(int i=0; i<=n; ++i){ 
		if(i-k>=0) --mp[vs[i-k]];
		ans += mp[vs[i]];
		++mp[vs[i]];
	}
	cout << ans << endl;

}


Measured memory_bytes: 14336
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    int k,s;
    cin>>k>>s;

    int result=0;
    REP(i,k+1){
        REP(j,k+1){
            if(0<=s-i-j&&s-i-j<=k){
                result++;
            }
        }
    }

    cout << result << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL)

int main(){
	FastIO;
	int t;
	cin >> t;
	string Map[4] = {"AC" , "WA" , "TLE" , "RE"};
	vector < int > v(4 , 0);
	while(t--){
		string s;
		cin >> s;
			if(s == "AC")
				v[0]++;
			if(s == "WA")
				v[1]++;
			if(s == "TLE")
				v[2]++;
			if(s == "RE")
				v[3]++;
	}
	for(int i = 0;i < v.size();i++){
		cout << Map[i] << " x  " << v[i] << "\n";
	}
	return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <string>

#define Yes cout << "Yes" << endl
#define No cout << "No" << endl

using namespace std;

int main(void) {
	int N; cin >> N;
	vector<string> W;
	for (int i = 0; i < N; i++) {
		string w; cin >> w;
		if (i != 0 && w.front() != W.at(i-1).back()) {
			No; return 0;
		}
		for (auto j:W)
			if (j == w) {
				No; return 0;
			}
		W.push_back(w);
	}

	Yes;
	//for (auto i : W) cout << i << endl;
}


Measured memory_bytes: 256
n = gets.to_i
p = gets.split.map(&:to_i)

flag = true
ans = 0
(0..n-2).to_a.each do |i|
  newFlag = p[i] < p[i+1]
  ans += 1 if newFlag == flag && i != 0
  flag = newFlag
end
puts ans


Measured memory_bytes: 1788
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
count = 0
for i in range(n):
  if a[i] >= b[i]:
    count += b[i]
  else:
    count += a[i]
    if a[i+1] > b[i]-a[i]:
      count += (b[i]-a[i])
      a[i+1] -= (b[i]-a[i])
    else:
      count += a[i+1]
      a[i+1] = 0
print(count)

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

int Search(int A[],int n,int key)
{
    int i=0;
    A[n]=key;
    while(A[i]!=key)
    {
        i++;
    }
    return i!=n;
}

int main()
{
    int A[10005],n,key,i,q;
    int cnt=0;
    cin>>n;
    for(i=0;i<n;++i)
    {
        cin>>A[i];
    }

    cin>>q;

    for(i=0;i<q;++i)
    {
        cin>>key;
        cnt+=Search(A,n,key);
    }
    cout<<cnt<<endl;

    return 0;
}


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

int main(void){
    int n;
    cin >> n;
    int h[n];
    rep(i,n){
        int x;
        cin >> x;
        h[i] = x;
    }
    int nmax = 0;
    int ans = 0;
    rep(i,n){
        if(h[i] >= nmax){
            ans++;
            nmax = h[i];
        }
    }
    cout << ans <<endl;
    
    return 0;
}





Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int d = a / b;
		int r = a % b;
		double f = (double) a / b;

		System.out.print(d + " " + r + " ");
		System.out.printf("%f%n", f);
		sc.close();
	}
}


Measured memory_bytes: 26492
from functools import reduce

n, _, c = map(int, input().split())
bs = tuple(map(int, input().split()))

count = 0
for i in range(n):
    if reduce(
        lambda x, y: x + y[0] * y[1],
        zip(bs, map(int, input().split())),
        0,
    ) + c > 0:
        count += 1

print(count)


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

template <typename T> inline void rd(T& x) {
	int si = 1; char c = getchar(); x = 0;
	while(!isdigit(c)) si = c == '-' ? -1 : si, c = getchar();
	while(isdigit(c)) x = x * 10 + c - 48, c = getchar();
	x *= si;
}
template <typename T, typename... Args>
inline void rd(T& x, Args&... args) { rd(x); rd(args...); }

#define fi first
#define se second

typedef long long ll;
typedef double ff;
typedef std::pair<int, int> pii;

const int kN = 1e5 + 5, kD = 12;

int n, m, c[kN], t[kN][kD];
std::vector <int> E[kN];

int main() {
	rd(n, m);
	for(int i = 1; i <= m; ++i) {
		int x, y; rd(x, y);
		E[x].push_back(y); E[y].push_back(x);
	}
	int q; rd(q);
	for(int i = 1; i <= q; ++i) {
		int v, d; rd(v, d, c[i]);
		t[v][d] = i;
	}
	for(int k = 1; k <= 10; ++k) 
		for(int i = 1; i <= n; ++i)
			for(auto v : E[i])
				for(int j = 0; j < 10; ++j)
					t[v][j] = std::max(t[i][j + 1], t[v][j]);
	for(int i = 1; i <= n; ++i) {
		int x = 0;
		for(int j = 0; j <= 10; ++j) x = std::max(x, t[i][j]);
		printf("%d\n", c[x]);
	}
	return 0;
}

Measured memory_bytes: 11512
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll N;
    cin >> N;
    vector<ll> h(N);
    rep(i, N) cin >> h[i];

    ll ans = 0;
    while(1){
        bool s = false;
        rep(i,N){
            if(h[i] == 0 && s){
                ++ans;
                break;
            }
            else if(h[i] >= 1){
                if(i == N - 1) ++ans;
                s = true;
                --h[i];
            }
        }
        if(!s) break;
    }

    print(ans);
    return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val mp = mutableMapOf<String, Int>()
    repeat(n) {
        val s = readLine()!!.toCharArray().sortedArray().joinToString("")
        if (mp[s] == null) {
            mp[s] = 1
        } else {
            mp[s] = mp[s]!! + 1
        }
    }
    var ans = 0L
    mp.forEach {
        val cnt = it.value
        if (cnt > 1) {
            ans += cnt * (cnt - 1L) / 2L
        }
    }
    println(ans)
}


Measured memory_bytes: 69716
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a < b && b < c) cout << "Yes" << endl;
    else cout << "No" << endl;
}



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

typedef long long ll;
ll M = 1e9 + 7;
ll n, ans, s[100][2], w[100];
int main()
{
	ll i, j, t, x, z;
	cin >> n;
	w[0] = 1;
	for (i = 1; i <= 61; i++) w[i] = (w[i - 1] * 2) % M;
	for (i =0; i < n; i++) {
		scanf ("%lld", &t);
		x = t;
		for (j = 0; j <= 61; j++) {
			z= x % 2;
			ans = (ans + s[j][1 - z] * w[j]) % M;
			s[j][z]++;
			x /= 2;
		}
	}
	cout << ans << endl;
    return 0;
}


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

int main() {
  ll n;
  cin >> n;
  vector<string> s(n);
  ll m = 0;
  ll a = 0;
  ll r = 0;
  ll c = 0;
  ll h = 0;
  rep(i,n) {
    cin >> s[i];
    if(s[i].at(0)=='M') m++;
    if(s[i].at(0)=='A') a++;
    if(s[i].at(0)=='R') r++;
    if(s[i].at(0)=='C') c++;
    if(s[i].at(0)=='H') h++;
  }
  ll ans = 0;
  ans += m*a*r;
  ans += m*a*c;
  ans += m*a*h;
  ans += m*r*c;
  ans += m*r*h;
  ans += m*c*h;
  ans += a*r*c;
  ans += a*r*h;
  ans += a*c*h;
  ans += r*c*h;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6144
while True:
    m, f, r = map(int,input().split())
    if m==-1 and f==-1 and r==-1:
        break
    if m==-1 or f==-1:
        print('F')
    elif m+f >= 80:
        print('A')
    elif 65 <= m+f <=80:
        print('B')
    elif 50 <= m+f < 65 or 30 <= m+f <50 and r >= 50:
        print('C')
    elif 30 <= m+f < 50:
        print('D')
    elif 30 > m+f:
        print('F')


Measured memory_bytes: 5596
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define  ll long long
#define  ull unsigned long long
#define  ul unsigned long
#define all(v) v.begin(),v.end()
void fast()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
}
void in_out()
{
	freopen("input.in", "r", stdin);
	freopen("output.in", "w", stdout);
}
int main()
{
	fast();
	int n;
	cin >> n;
	set<int>s;
	int x;
	while (n--)
	{
		cin >> x;
		s.insert(x);
	}
	cout << s.size();
	
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int N,a,j=1,ans=0;
int main() {
  cin >> N;
  for(int i = 0;i < N;++i){
    cin >> a;
    if(a == j){
      j++;
    }else{
      ans += 1;
    }
  }
  if(j == 1)
    cout << -1;
  else
    cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define  rep(i,n) for(li i = 0; i < (n); ++i)
#define  red(i,n) for(li i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a) 
using namespace std;
using li = long long;
using ul = unsigned long long;
using vi = vector<li>;
using vs = vector<string>;
inline ul gcd(ul a,ul b) { return b?gcd(b,a%b):a; }
const int INF=1000000009;


int main()
{
    int n;
    cin>>n;
    char s;
    rep(i,n) {
        cin>>s;
        if(s=='Y') cout<<"Four\n",exit(0);
    }
    cout<<"Three\n";

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
 
void init();
void solve();
 
#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
 
#ifdef LOCAL
#define lcout(a) cout << a;
#define lcoutln(a) cout << a << endl;
#define lcerr(a) cerr << a;
#define lcerrln(a) cerr << a << endl;
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
 
#define MOD 1000000007
 
signed main()
{
	init();
	solve();
}

string s;

void init()
{
  cin >> s;
}
 
void solve()
{
  string ans = "YAKI";
  rep(i, 4) {
    if (ans[i] != s[i]) {
      cout << "No" << endl;
      return;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
typedef long long ll;
using namespace std;
vector<int> V;

int main(void){
    // Your code here!
   int N;
   cin >> N;
   int x[N], y[N];
   V.resize(N);
   for(int i = 0; i < N; i++) cin >> x[i] >> y[i];
   
   int times = 1;
   for(int i = N; i >= 1; i--) times *= i;
   
   for(int i = 1; i <= N; i++) {
       V[i-1] = i;
   }
   
   double sum = 0.0;
   do {
       vector<int> a(N);
       for(int i = 0; i < N; i++){
           a[i] = V[i];
       }
       
       double dis = 0;
       for(int i = 1; i < a.size(); i++){
           dis += sqrt((x[V[i] - 1] - x[V[i-1] - 1]) * (x[V[i] - 1] - x[V[i-1] - 1])
           + (y[V[i] - 1] - y[V[i-1] - 1]) * (y[V[i] - 1] - y[V[i-1] - 1]));
           
       }
       sum += dis;
    } while(next_permutation(V.begin(), V.end()));   
   
   double ans = sum / times;
   printf("%.10f", ans);
   return 0;
}


Measured memory_bytes: 256
#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr <<"debug "<< i << std::endl;

//const ll MOD = 998244353;
const ll MOD = 1e9+7;
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll h,w;
  std::cin>>h>>w;

  std::vector<std::vector<bool>> red(h,std::vector<bool>(w,false)),blue(h,std::vector<bool>(w,false));

  rep(i,0,h){
    red[i][0]=true;
    blue[i][w-1]=true;
    if(i%2==0){
      rep(j,0,w-1)red[i][j]=true;
    }else{
      rep(j,1,w)blue[i][j]=true;
    }
  }

  rep(i,0,h){
    std::string s;
    std::cin>>s;
    rep(j,0,w){
      if(s[j]=='#'){
        red[i][j]=true;blue[i][j]=true;
      }
    }
  }

  rep(i,0,h){
    rep(j,0,w)std::cout<<((red[i][j])?'#':'.');
    std::cout<<"\n";
  }

  std::cout<<"\n";

  rep(i,0,h){
    rep(j,0,w)std::cout<<((blue[i][j])?'#':'.');
    std::cout<<"\n";
  }

  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int main(){
  int x,n;
  cin >> x >> n;
  if(n==0){
    cout << x << endl;
    return 0;
  }
  vector<int> p(n,0);
  for(int i=0;i<n;i++){
    cin >> p[i];
  }
  int ans=0;
  bool b=true;
  for(int i=0;i<=50;i++){
    ans=x-i;
    b=true;
    for(int j=0;j<n;j++){
      if(p[j]==ans) b=false;
    }
    if(b) break;
    ans=x+i;
    b=true;
    for(int j=0;j<n;j++){
      if(p[j]==ans) b=false;
    }
    if(b) break;
  }
  cout << ans << endl;
  return 0;
}  


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

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


int main(){

    ll n;
    cin >> n;
    vector<ll> a(n);
    map<ll, ll> mp;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    ll ans = 0;
    for(auto iter : mp){
        ans += iter.second * (iter.second - 1) / 2;
    }
    for(int i = 0; i < n; i++){
        ll v = mp[a[i]];
        ll before = v * (v - 1) / 2;
        ll after = (v-1) * (v - 2) / 2;
        cout << ans - before + after << endl;
    }
    return 0;
}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll 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


std::vector<long long> binomial_coefficient(long long N){
    /*
    Copyright (c) 2020 0214sh7
    https://github.com/0214sh7/library/
    */
    
    std::vector<long long> fac;
    std::vector<long long> facIE;
    std::vector<long long> comb;
    for(int i=0;i<=N;i++){
        if(i==0){
            fac.push_back(1);
        }else{
            fac.push_back(i*fac[i-1]%MOD);
        }
    }
    for(int i=0;i<=N;i++){
        long long r=1,b=fac[i],e=MOD-2;
        while(e){
            if(e&1){
                r=(r*b)%MOD;
            }
            b=(b*b)%MOD;
            e >>=1;
        }
        facIE.push_back(r);
    }
    for(int i=0;i<=N;i++){
        long long r=fac[N];
        r = (r*facIE[i])%MOD;
        r = (r*facIE[N-i])%MOD;
        comb.push_back(r);
    }
    return comb;
}


int main(void){
    ll K;
    string S;
    cin >> K >> S;
    
    ll N = S.size();
    
    ll Ans = 0;
    
    vector<ll> nC = binomial_coefficient(N+K);
    
    ll x = 1;
    REP(i,K+1){
        ll r = nC[i];
        
        ll d = (r*x)%MOD;
        Ans+=d;
        Ans%=MOD;
        
        x = (x*25)%MOD;
    }
    
    cout << Ans << endl;
    
    /*
    REP(i,N+1){
        REP(j,N+2){
            REP(k,26){
                REP(l,26){
                    string T = S;
                    string a;a.push_back('a'+k);
                    string b;b.push_back('a'+l);
                    
                    T.insert(i,a);
                    T.insert(j,b);
                    G.push_back(T);
                    
                }
            }
        }
    }
    
    sort(G.begin(),G.end());
    int Ans=0;
    REP(i,G.size()){
        if(i==0 || G[i]!=G[i-1]){
            Ans++;
        }
    }
    cout << Ans << endl;*/
    
    
    return 0;
}



Measured memory_bytes: 59980
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define loop(s, v, it) for (s::iterator it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = e[i].nxt)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, sum) memset(a, sum, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int N = 100010 ;
const int INF = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const int MOD = 1000000007 ;
const double eps = 1e-7 ;
void douout(double x){ printf("%lf\n", x + 0.0000000001) ; }
template <class T> void print(T a) { cout << a << endl ; exit(0) ; }
template <class T> void chmin(T &a, T b) { if (a > b) a = b ; }
template <class T> void chmax(T &a, T b) { if (a < b) a = b ; }
template <class T> void upd(T &a, T b) { (a += b) %= MOD ; }
template <class T> void mul(T &a, T b) { a = (ll) a * b % MOD ; }

int T ;
int a, b, c, d, x ;

signed main(){
//	file("test") ;
	scanf("%lld", &T) ;
	while (T--) {
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d) ;
		c-- ; d-- ;
		x = (max(a, b) - 1) / (min(a, b) + 1) + 1 ;
		int la, lb ; // a 打头的那段区域的长度， b ~~~
		if (a >= x * b) {
			la = a + b ;
			lb = 0 ;
		}
		else if (b >= x * a) {
			la = 0 ;
			lb = a + b ;
		}
		else {
			la = (1ll * x * a - b) / (x - 1) ; // 类似鸡兔同笼的道理
			lb = (1ll * x * b - a) / (x - 1) ;
		}
		bool cb = a - la + la / (x + 1) - lb / (x + 1) == 0 ;
		rep(i, c, d) {
			bool isb = i < la ? i % (x + 1) == x : i >= a + b - lb ? (a + b - i - 1) % (x + 1) != x : cb ;
			putchar(isb ? 'B' : 'A') ;
		}
		enter ;
	}
	return 0 ;
}

/*
写代码时请注意：
	1.ll？数组大小，边界？数据范围？
	2.精度？
	3.特判？
	4.至少做一些
思考提醒：
	1.最大值最小->二分？
	2.可以贪心么？不行dp可以么
	3.可以优化么
	4.维护区间用什么数据结构？
	5.统计方案是用dp？模了么？
	6.逆向思维？
*/




Measured memory_bytes: 384
#include <bits/stdc++.h>
#define inf 1000000007
#define mod 1000000007
//#pragma GCC optimize(2)
#define int long long
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,res=1;
int p[5000],s[5000],cnt;
void dfs(int x,int k)
{
	if(x==cnt+1)
	{
		if(k==1) return;
		int t=n;
		while(t%k==0) t/=k;
		if(t%k==1) res++;
		return;
	}
	for(int i=0;i<=s[x];i++)
	{
		dfs(x+1,k);
		k*=p[x];
	}
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int t=n;
	for(int i=2;i*i<=t;i++)
		if(t%i==0)
		{
			p[++cnt]=i;
			while(t%i==0) s[cnt]++,t/=i;
		}
	if(t>1) p[++cnt]=t,s[cnt]=1;
	t=n-1;
	for(int i=2;i*i<=t;i++)
		if(t%i==0)
		{
			int cur=1;
			while(t%i==0) cur++,t/=i;
			res*=cur;
		}
	if(t>1) res*=2;
	res--;
	dfs(1,1);
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
import static java.lang.System.in;
import static java.lang.System.out;

import java.io.*;
import java.util.*;

public class Main {
	static final double EPS = 1e-10;
	static final double INF = 1L << 31;
	static final double PI = Math.PI;

	public static Scanner sc = new Scanner(in);
	static StringBuilder sb = new StringBuilder();
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public void run() throws IOException {
		String input;
		String[] inputArray;
		input = br.readLine();
		inputArray = input.split(" ");
		int h = Integer.valueOf(inputArray[0]);
		int w = Integer.valueOf(inputArray[1]);
		for (int i=0; i<h; i++){
			input = br.readLine();
			inputArray = input.split(" ");
			for (int j=0; j<w; j++){
				if (inputArray[j].equals("snuke")){
					sb.append((char)('A'+j));
					sb.append((i+1));
					return;
				}
			}
		};
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
		ln(sb);
	}
	public static void ln(Object obj) {
		out.println(obj);
	}
}


Measured memory_bytes: 9300
/* ITP1_9_C */
#include <stdio.h>

#define CARD_NAME_LIMIT 101
#define WIN_POINT 3
#define DRAW_POINT 1

/* ????????????????????????????????¢??° */
void init_array_char(char array[], short length);
/* ???????????§??????????????¢??° */
short comp_dictionary_order(char array1[], char array2[]);

int main(void)
{
	short turn = 0;
	scanf("%hd", &turn);
	
	short taro_score = 0;
	short hanako_score = 0;
	
	char taro_card[CARD_NAME_LIMIT];
	char hanako_card[CARD_NAME_LIMIT];
	
	short ii;
	for( ii = 0; ii < turn; ii++ )
	{
		init_array_char(taro_card, CARD_NAME_LIMIT);
		init_array_char(hanako_card, CARD_NAME_LIMIT);
		
		scanf("%s", taro_card);
		scanf("%s", hanako_card);
		
		if( 1 == comp_dictionary_order(taro_card, hanako_card) )
		{
			taro_score += WIN_POINT;
		}
		else if( -1 == comp_dictionary_order(taro_card, hanako_card) )
		{
			hanako_score += WIN_POINT;
		}
		else
		{
			taro_score += DRAW_POINT;
			hanako_score += DRAW_POINT;
		}
	}
	printf("%hd %hd\n", taro_score, hanako_score);
	
	return 0;
}

/* ????????????????????????????????¢??° */
void init_array_char(char array[], short length)
{
	short ii;
	for( ii = 0; ii < length; ii++ )
	{
		array[ii] = '\0';
	}
}

/* ???????????§??????????????¢??° */
short comp_dictionary_order(char array1[], char array2[])
{
	short ii, char_comp;
	for( ii = 0; '\0' != array1[ii] && '\0' != array2[ii]; ii++ )
	{
		char_comp = array1[ii] - array2[ii];
		if( 0 == char_comp )
		{
			continue;
		}
		else if( 0 < char_comp )
		{
			return 1;
		}
		else if( 0 > char_comp )
		{
			return -1;
		}
	}
	
	if( '\0' == array1[ii] && '\0' == array2[ii] )
	{
		return 0;
	}
	else if( '\0' != array1[ii] && '\0' == array2[ii] )
	{
		return 1;
	}
	else if( '\0' == array1[ii] && '\0' != array2[ii] )
	{
		return -1;
	}
}

Measured memory_bytes: 596
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as BS
main=do
 [n,c,k]<-map read.words<$>getLine
 t<-replicateM n (read.BS.unpack<$>BS.getLine)
 print (f (sort t) c k 0)
  where f [] _ _ i = i
        f (a:t) c k i = f (g (a:t) c (k+a)) c k (i+1)
        g [] _ _ = []
        g t 0 _ = t
        g (b:t) c k = if b<=k then (g t (c-1) k) else (b:t)

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

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

    int count = 0;
    int max_length = 0;

    for (int i = 0; i < S.size(); i++)
    {
        if (S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T')
        {
            count++;
        }
        else
        {
            count = 0;
        }
        max_length = max_length > count ? max_length : count;
    }

    cout << max_length << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int a, b;

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

	cin >> a >> b;
	if (a > b) {
		cout << "a" << " > " << "b" << "\n";
	}
	else if (a < b) {
		cout << "a" << " < " << "b" << "\n";
	}
	else {
		cout << "a" << " == " << "b" << "\n";
	}
	cin >> a;
	return 0;
}

Measured memory_bytes: 3112
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    ll ans = a*x + b*y;
    chmin(ans, c*2*x + b*max(y-x, 0LL));
    chmin(ans, a*max(x-y, 0LL) + c*2*y);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def is_ok(x):
    trainings = 0
    for i in range(N):
        t = A[i] - x // F[i]
        if t > 0:
            trainings += t
    return trainings <= K


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

A.sort()
F.sort(reverse=True)

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)


Measured memory_bytes: 119500
// D - Insertion
#include <bits/stdc++.h>
using namespace std;

int main(){
	int _N; cin>>_N;//not used
	string S; cin>>S;

	int r = 0;//r = depth
	int l = 0;
	for(char s:S){
		if(s == '(') r++;
		else{
			r--;
			if(r < 0){
				r = 0;
				l++;
			}
		}
	}

	cout<< string(l,'(') + S + string(r,')') <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;

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

  int a,b,c,k;
  cin>>a>>b>>c>>k;
  int ans = 0;
  int mx = max({a,b,c});
  ans = a + b + c + mx * pow(2, k) - mx;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
//2^15=32768
//2^15<184^2
int data[201];
bool num[40001];
main(){
  data[0]=0;
  for(int i=1;i<=200;i++){
    data[i]=i*i;
    num[data[i]]=true;
  }
  int n;
  while(1){
    cin >> n;
    if(n==0) break;

    int count=0;
    for(int a=0;a<=200;a++){
      if(data[a]>n){
	break;
      }
      for(int b=a;b<=200;b++){
	if(data[a]+data[b]>n){
	  break;
	}
	for(int c=b;c<=200;c++){
	  if(data[a]+data[b]+data[c]>n) break;
	  int tmp=n-data[a]-data[b]-data[c];
	  if(tmp>n) continue;
	  if(tmp<data[c]) continue;
	  if(num[tmp]) count++;
	}
      }
    }

    cout << count << endl;
  }
  return 0;
}

Measured memory_bytes: 904
#include"bits/stdc++.h"
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())

int main() {
	int A, B, C, K;
	cin >> A >> B >> C >> K;
	if (A >= K) {
		cout << K << endl;
	}
	else if (A + B >= K) {
		cout << A << endl;
	}
	else {
		cout << A - K + A + B << endl;
	}
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main(){
 string t = "CODEFESTIVAL2016";
 string s;
 cin >> s; 
 ll ans = 0;
  REP(i,SZ(s)){
    if(s[i] != t[i]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 764
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll a; cin >> a;
    string s; cin >> s;
    cout << (a >= 3200 ? s : "red") << endl;
    
}

Measured memory_bytes: 764
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	char b;
	cin>>b;
	if(b=='A') cout<<'T'<<endl;
	else if(b=='T') cout<<'A'<<endl;
	else if(b=='C') cout<<'G'<<endl;
	else cout<<'C'<<endl;
	return 0;
}


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

typedef long long ll;

ll N;
map<char, map<ll, set<double>>> Vs;
double R = 1e20;

void update(double t) {
  if (t < 0) return;
  double res = 1;
  for (char xy : {'x', 'y'}) {
    set<double> avs;
    for (const auto &d_vs : Vs[xy]) {
      ll d = d_vs.first;
      const auto &vs = d_vs.second;
      avs.insert(*vs.begin() + d * t);
      avs.insert(*vs.rbegin() + d * t);
    }
    res *= *avs.rbegin() - *avs.begin();
  }
  R = min(R, res);
}
int main() {
  cin >> N;
  for (ll i = 0; i < N; ++i) {
    double x, y;
    char d;
    cin >> x >> y >> d;
    Vs['x'][d == 'R' ? 1 : d == 'L' ? -1 : 0].insert(x);
    Vs['y'][d == 'U' ? 1 : d == 'D' ? -1 : 0].insert(y);
  }
  update(0);
  for (char xy : {'x', 'y'}) {
    for (ll d : {0, 1, -1}) {
      if (!Vs[xy].count(d)) continue;
      for (ll d2 : {0, 1, -1}) {
        if (d >= d2) continue;
        if (!Vs[xy].count(d2)) continue;
        const auto &vs = Vs[xy][d], &vs2 = Vs[xy][d2];
        update((*vs2.begin() - *vs.begin()) / (d - d2));
        update((*vs2.rbegin() - *vs.rbegin()) / (d - d2));
      }
    }
  }
  cout << setprecision(10) << R << endl;
  return 0;
}


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

struct my_heap {
    multiset<ll> s1;
    multiset<ll> s2; // s2 <= s1
    ll sum1;

    my_heap() : sum1(0) {}

    void add(ll x) {
        if (s1.empty() && s2.empty() || !s1.empty() && x >= *s1.begin()) {
            s1.insert(x);
            sum1 += x;
        }
        else s2.insert(x);
    }

    ll get(int k) {
        while (s1.size() < k) {
            ll x = *s2.rbegin();
            auto it = s2.end();
            s2.erase(--it);
            s1.insert(x);
            sum1 += x;
        }
        while (s1.size() > k) {
            ll x = *s1.begin();
            s1.erase(s1.begin());
            sum1 -= x;
            s2.insert(x);
        }
        return sum1;
    }

    void del(ll x) {
        if (s1.find(x) != s1.end()) s1.erase(s1.find(x)), sum1 -= x;
        else if (s2.find(x) != s2.end()) s2.erase(s2.find(x));
        else assert(0);
    }

    int size() const {
        return s1.size() + s2.size();
    }
};

ll fastsolve(int m, vector<int> n, vector<vector<int> > a) {
    ll ans = 0;
    vector<pair<int, int> > b;
    for (int i = 0; i < m; i++) {
        ans += a[i][0];
        b.push_back({-a[i][0] + a[i][1], -a[i][0] + a[i][2]});
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());

    my_heap h1, h2;
    int ex1 = n[1];
    int ex2 = n[2];

    ll s2 = 0;
    for (int i = 0; i < ex1; i++) {
        s2 += b[i].first;
        h1.add(-b[i].first + b[i].second);
    }
    for (int i = ex1; i < (int)b.size(); i++) {
        h2.add(b[i].second);
    }

    ll result = -8e18;
    for (int cnt = ex1; cnt <= ex1 + ex2; cnt++) {
        result = max(result, ans + s2 + h1.get(cnt - ex1) + h2.get(ex2 - cnt + ex1));

        if (cnt < ex1 + ex2) {
            s2 += b[cnt].first;
            h1.add(-b[cnt].first + b[cnt].second);
            h2.del(b[cnt].second);
        }
    }
    return result;
}

int main() {
#ifdef HOME
    assert(freopen("in", "r", stdin));
#endif


    vector<int> n(3);
    while (scanf("%d%d%d", &n[0], &n[1], &n[2]) == 3) {
        int m = n[0] + n[1] + n[2];
        vector<vector<int> > a(m, vector<int>(3));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        printf("%lld\n", fastsolve(m, n, a));
    }


#ifdef HOME
    cerr << "time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

Measured memory_bytes: 16632
#include <stdio.h>

int main() {
	int L, R, d, ctr = 0;
	scanf ("%d %d %d", &L, &R, &d);
	
	for (int i = L; i <= R; i++){
		if (i % d == 0){
			ctr += 1;
		}
	}
	printf ("%d", ctr);
	return 0;
}

Measured memory_bytes: 1688
#include <iostream>
#include <vector>
#include <tuple>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <functional>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;


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

  int n,k,d,tmp,ans=0;
  cin >> n >> k;
  int a[n];
  REP(i,n) a[i] = 0;

  REP(i,k){
    d = 0;
    cin >> d;
    REP(j,d){
      cin >> tmp;
      a[tmp-1] ++;
    }
  }

  REP(i,n){
    if (a[i]==0){
      ans++;
    }
  }


  cout << ans;

}
  


Measured memory_bytes: 3632
N=int(input())

import copy

raw=[0]*10
a=[]

for i in range(10):
  a.append(copy.deepcopy(raw))

ans=0
#print(a)

for i in range(1,N+1):
  temp=str(i)
  #print(temp)
  a[int(temp[0])][int(temp[-1])]+=1

#print(a)

for i in range(10):
  for j in range(10):
    ans+=a[i][j]*a[j][i]

print(ans)  



Measured memory_bytes: 3444
import java.util.Scanner;

public class Main {
    static long mod = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(), a = sc.nextLong(), b = sc.nextLong();
        long ans = pow(2, n) - comb(n, a) - comb(n, b) - 1;
        if(ans < 0) ans += (-ans / mod + 1) * mod;
        System.out.println(ans);
    }
    static long pow(long x, long n) {
        long a = 1;
        do {
            if((n & 1) == 1) a = (a * x) % mod;
            x = (x * x) % mod;
        } while((n >>= 1) > 0);
        return a;
    }
    static long comb(long n, long r) {
        long mol = n, den = r;
        for(int i = 1; i < r; i++) {
            mol = (mol * (n - i)) % mod;
            den = (den * i) % mod;
        }
        return mol * pow(den, mod - 2) % mod;
    }
}

Measured memory_bytes: 23124
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int cnt[110];
int main()
{
	int N;
	cin >> N;
	for (int i = 2; i <= N; i++) {
		int tmp = i;
		for (int j = 2; j <= N; j++) {
			while (tmp % j == 0) {
				tmp /= j;
				cnt[j]++;
			}
		}
	}
	int ans = 0;
	for (int i = 2; i <= N; i++) {
		if (cnt[i] >= 74) ans++;
		if (cnt[i] >= 24) {
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 2) ans++;
			}
		}
		if (cnt[i] >= 14) {
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 4)ans++;
			}
		}
		if (cnt[i] >= 4) {
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 14) ans++;
			}
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 4) {
					for (int k = j + 1; k <= N; k++) {
						if (cnt[k] >= 2) ans++;
					}
				}
			}
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 2) {
					for (int k = j + 1; k <= N; k++) {
						if (cnt[k] >= 4) ans++;
					}
				}
			}
		}
		if (cnt[i] >= 2) {
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 24) ans++;
			}
			for (int j = i + 1; j <= N; j++) {
				if (cnt[j] >= 4) {
					for (int k = j + 1; k <= N; k++) {
						if (cnt[k] >= 4) ans++;
					}
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3596
using System;

namespace atcoderA
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int K = int.Parse(Console.ReadLine());
            int X = int.Parse(Console.ReadLine());
            int Y = int.Parse(Console.ReadLine());
            int ans = 0;
            if (N > K)
            {
                ans = X * K + Y * (N - K);
            }
            else
            {
                ans = X * N;
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int a,b;
	cin>>a>>b;
	if((a+b)%2==0) cout<<(a+b)/2<<endl;
	else cout<<(a+b)/2+1<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
// scanf("%d %d %d %d",&w,&b,&d,&s); %lld
// printf("%d\n" ,points);
// const double PI=acos(-1);

int main(){
    fastIO;
    int a,b,c,k;
    cin >> a >> b >> c;
    cin >> k;
    while(b<=a && k){
        b*=2;
        k--;
    }
    while(c<=b && k){
        c*=2;
        k--;
    }
    if(a<b && b<c) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3584