akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define MOD 1000000007 
#define MOD1 998244353
#define ll long long int
#define db double
#define endl "\n"
#define INF 1000000000000000000
#define INF1 1000000000
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define debx cout<<" X "<<endl;
#define deby cout<<" Y "<<endl;
#define debz cout<<" Z "<<endl;
#define deb(x) cout << '>' << #x << ':' << x << endl;
using namespace std;
 
ll mpow(ll a, ll b){
    if(!b)
        return 1;
    ll temp=mpow(a,b/2);
    temp=(temp*temp)%MOD;
    if(b%2)
        return (a*temp)%MOD;
    return temp;
}
ll mod_in(ll n){
    return mpow(n,MOD-2);
}
ll cl(ll a, ll b){
    if(a%b)
        return 1+a/b;
    return a/b;
}
ll dig(ll n){
    if(!n)
        return 0;
    return 1 + dig(n/10);
}
int main(){
    // fastio
    ll n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    for(ll i=0 ; i<n ; i++)
        cout<<s[i]<<t[i];
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			String result = "Yes";
			int[][] arr = new int[3][3];
			for(int i = 0; i < 3; i++) {
				for(int j = 0; j < 3; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			int a[] = new int[3];
			int b[] = new int[3];
			a[0] = 0;
			for(int i = 0; i < 3; i++) {
				b[i] = arr[0][i] - a[0];
				a[i] = arr[i][0] - b[0];
			}
			l : for(int i = 0; i < 3; i++) {
				for(int j = 0; j < 3; j++) {
					if(a[i] + b[j] != arr[i][j]) {
						result = "No";
						break l;
					}
				}
			}
			System.out.println(result);
	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <iomanip>

void Output(int arr[4][13]) {
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 13; ++j) {
			if (arr[i][j] == 0) {
				switch (i) {
				case 0:
					std::cout << "S" << " " << j + 1 << std::endl;
					break;
				case 1:
					std::cout << "H" << " " << j + 1 << std::endl;
					break;
				case 2:
					std::cout << "C" << " " << j + 1 << std::endl;
					break;
				case 3:
					std::cout << "D" << " " << j + 1 << std::endl;
					break;
				}
			}
		}
	}
}

int main()
{
	int tramp[4][13] = {};
	int n, cardNum;
	char art;
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		std::cin >> art >> cardNum;
		if (cardNum <= 0 || cardNum > 13) {
			return -1;
		}

		if (art == 'S') {
			tramp[0][cardNum-1] = 1;
		}
		else if (art == 'H') {
			tramp[1][cardNum-1] = 1;
		}
		else if(art == 'C') {
			tramp[2][cardNum-1] = 1;
		}
		else if(art == 'D') {
			tramp[3][cardNum-1] = 1;
		}
		else {
			return -1;
		}
	}
	Output(tramp);

}




Measured memory_bytes: 3080
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) {
		LScanner sc=new LScanner(System.in);
		String s=sc.next();
		long sum=0;
		long w_ks=0;
		for(int i=0; i<s.length(); i++) {
			if(s.charAt(i)=='W') {
				sum+=i;
				w_ks++;
			}
		}
		System.out.println(sum-w_ks*(w_ks-1)/2);
	}

	static class LScanner {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public LScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}

Measured memory_bytes: 26600
MOD = 10 ** 9 + 7


def solveBrute(K, S):
    # On the i-th iteration, dp[j] counts all strings of length i which contains S[:j] as a subsequence

    N = len(S)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N + K):
        nextDp = [0] * (N + 1)
        for j in range(N):
            nextDp[j] += dp[j] * 25
            nextDp[j + 1] += dp[j]
        nextDp[N] += dp[N] * 26

        dp = nextDp
        for j in range(N + 1):
            dp[j] %= MOD
        # print(dp)

    return dp[N]


def solveBrute2(K, S):
    import numpy as np

    def matrixPower(mat, k):
        assert k >= 0
        if k == 0:
            return np.eye(mat.shape[0], dtype=np.int64)
        if k == 1:
            return mat
        temp = matrixPower(mat, k // 2)
        ret = (temp @ temp) % MOD
        if k % 2:
            return (ret @ mat) % MOD
        return ret

    # For intution, can interpret the bruteforce as a matrix multiplication:
    # {{0, 0, 0, 1}} . MatrixPower[{{25, 0, 0, 0}, {1, 25, 0, 0}, {0, 1, 25, 0}, {0, 0, 1, 26}}, 8] . {{1}, {0}, {0}, {0}}
    # https://www.wolframalpha.com/input/?i=%7B%7B0%2C+0%2C+0%2C+1%7D%7D+.+MatrixPower%5B%7B%7B25%2C+0%2C+0%2C+0%7D%2C+%7B1%2C+25%2C+0%2C+0%7D%2C+%7B0%2C+1%2C+25%2C+0%7D%2C+%7B0%2C+0%2C+1%2C+26%7D%7D%2C+8%5D+.+%7B%7B1%7D%2C+%7B0%7D%2C+%7B0%7D%2C+%7B0%7D%7D

    N = len(S)

    mat = 25 * np.eye(N + 1, dtype=np.int64,)
    mat[N][N] += 1
    for i in range(N):
        mat[i + 1][i] = 1

    vec = np.zeros((N + 1, 1), dtype=np.int64)
    vec[0] = 1

    res = matrixPower(mat, N + K) @ vec
    return int(res[N]) % MOD


def solve(K, S):
    def modInverse(a, p):
        # Fermat's little theorem, a**(p-1) = 1 mod p
        return pow(a, p - 2, p)

    # Precompute all factorials
    fact = [1]
    for i in range(1, 2 * (10 ** 6) + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p

    total = 0
    N = len(S)
    for i in range(N, N + K + 1):
        total += nCr(N + K, i) * pow(25, N + K - i, MOD)
        total %= MOD
    return total


(K,) = [int(x) for x in input().split()]
S = input()
ans = solve(K, S)
# assert ans == solveBrute(K, S) == solveBrute2(K, S)
print(ans)


Measured memory_bytes: 165676
#include<stdio.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
int field[14][14];

int main(){
  int x, y, size, maxs, ans, i, j;
  while(scanf("%d,%d,%d", &x, &y, &size) != EOF){
    x += 2;
    y += 2;
    if(size == 1){
      field[x][y]++;
      field[x + 1][y]++;
      field[x][y + 1]++;
      field[x - 1][y]++;
      field[x][y - 1]++;
    }
    if(size == 2){
      field[x][y - 1]++;
      field[x][y]++;
      field[x][y + 1]++;
      field[x + 1][y - 1]++;
      field[x + 1][y]++;
      field[x + 1][y + 1]++;
      field[x - 1][y - 1]++;
      field[x - 1][y]++;
      field[x - 1][y + 1]++;
    }
    if(size == 3){
      field[x][y - 1]++;
      field[x][y]++;
      field[x][y + 1]++;
      field[x + 1][y - 1]++;
      field[x + 1][y]++;
      field[x + 1][y + 1]++;
      field[x - 1][y - 1]++;
      field[x - 1][y]++;
      field[x - 1][y + 1]++;
      field[x + 2][y]++;
      field[x][y + 2]++;
      field[x - 2][y]++;
      field[x][y - 2]++;
    }
  }
  for(i = 2;i < 12;i++){
    for(j = 2;j < 12;j++){
      if(field[i][j] == 0)ans++;
      maxs = max(maxs, field[i][j]);
    }
  }
  printf("%d\n%d\n", ans, maxs);
  return 0;
}

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

#define ll long long
#define pb push_back
#define eb emplace_back
//#define st first
#define sc second

using namespace std;

const ll mod = 1e9 + 7;
const int e = 55;
const int base = 311;

// dung inverse module de tinh nCk
// beginer 82
// mbeginer
// cach tao hoan vi tu n so : n*(n+1)/2;

//vector<pair<ll,ll>>adj[e];
//vector<ll>adj[e];

/*ll Pow(ll n, ll dem)
{
    if(dem == 0) return 1;
    if(dem == 1) return n ;
    ll t = Pow(n, dem/2);
    if(dem % 2 == 0) return (t*t);
    else return ((t * t) * n);
}*/

/*ll C(ll k, ll n)
{
    if(k == 0) return 1;
    if(n < k) return 0;
    return (gt[n]%mod * (igt[k]%mod * igt[n-k]%mod)%mod)%mod;
}*/

ll n, m, k, q;
ll a[e], b[e], c[e], d[e];
ll x[e];
ll ans =0;

void dequy(ll i, ll cur)
{
    if(i == n+1)
    {
        ll sum = 0;
        for(int j=1; j<=q; j++)
        {
            if(x[b[j]] - x[a[j]] == c[j])
            {
                sum += d[j];
            }
        }
        ans = max(ans, sum);
        return ;
    }
    else
    {
        for(int j=cur; j<=m; j++)
        {
            x[i] = j;
            dequy(i+1, j);
        }
    }
}

int main()
{
   cin >> n >> m >> q;
   for(int i=1; i<=q; i++)
   {
       cin >> a[i] >> b[i] >> c[i] >> d[i];
   }
   dequy(1, 1);
   cout << ans;
}
/*

*/


Measured memory_bytes: 3600
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){
  int n,m,x,i,j;
  int inc = 0,dec = 0;
  
  scanf("%d %d %d",&n,&m,&x);
  
  char s[m];
  
  for(i=0;i<=m;i++){
    scanf("%d",&s[i]);
  }
  
  for(i=x;i<=n;i++){
    for(j=0;j<m;j++){
    if(i == s[j]){
      inc++;
    }
    }
  }
  
  for(i=x;i>=0;i--){
    for(j=0;j<m;j++){
    if(i == s[j]){
      dec++;
    }
    }
  }
  

  if(inc<=dec)
    printf("%d",inc);
  else
    printf("%d",dec);
  
  return 0;
}

Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " ";
#define INF 10000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    long double n,ans=0;
    cin>>n;
    vector<long double>p((int) n);
    const lli c=n;
    rep(i,n) cin>>p[i];
    vvec(long double) dp(c+1,vec(long double)(c+1));
    dp[0][0]=1;
    for(lli i=1;i<n+1;i++){
        rep(j,i+1){
            if(j>0){
                dp[i][j]=dp[i-1][j]*(1.0-p[i-1])+dp[i-1][j-1]*p[i-1];
            }
            else{
                dp[i][j]=dp[i-1][j]*(1.0-p[i-1]);
            }
        }
    }
    for(lli i=c/2+1;i<c+1;i++){
        ans+=dp[c][i];
    }
    printf("%.10Lf",ans);
}

Measured memory_bytes: 144292
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;


int main(){
    int n;
    cin >> n;
    int ans[] = {0,0,0,0};
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        if(s == "AC"){
            ans[0]++;
        } else if(s == "WA"){
            ans[1]++;
        } else if(s == "TLE"){
            ans[2]++;
        } else {
            ans[3]++;
        }
    }

    cout << "AC x " << ans[0] << endl;
    cout << "WA x " << ans[1] << endl;
    cout << "TLE x " << ans[2] << endl;
    cout << "RE x " << ans[3] << endl;
    
    return 0;
}

Measured memory_bytes: 3628
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


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

  vector<vector<ll>> P(4 * K, vector<ll>(4 * K, 0));
  vector<vector<ll>> acc(4 * K + 1, vector<ll>(4 * K + 1, 0));

  for (int i = 0; i < N; i++) {
    int x, y; char c;
    cin >> x >> y >> c;
    if (c == 'W') {
      y += K;
    }
    x %= 2 * K; y %= 2 * K;
    P[y][x] += 1;
    P[y + 2 * K][x] += 1;
    P[y][x + 2 * K] += 1;
    P[y + 2 * K][x + 2 * K] += 1;
  }

  for(int i = 1; i <= 4 * K; i++) {
    for(int j = 1; j <= 4 * K; j++) {
      acc[i][j] = acc[i - 1][j] + acc[i][j - 1] - acc[i - 1][j - 1] + P[i - 1][j - 1]; 
    }
  }

  auto get = [&K, &acc](int x, int y) {
    return acc[y + K][x + K] - acc[y][x + K] - acc[y + K][x] + acc[y][x];
  };

  ll ma = 0;
  for (int i = K; i < 3 * K; i++) {
    for (int j = K; j < 3 * K; j++) {
      ll sum = 0;
      sum += get(i, j);
      sum += get(i - K, j - K);
      ma = max(ma, sum);
    }
  }
  cout << ma << endl;
  return 0;
}

Measured memory_bytes: 250624
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
# input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n, k = map(int, input().split())
    head = sum(i for i in range(k))
    tail = sum(n-i for i in range(k))
    ans = tail - head + 1
    for i in range(k, n+1):
        head += i
        tail += n - i
        ans += tail - head + 1
        ans %= MOD
    print(ans)



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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,29)-1;

const int N_MAX = pow(10,5);

struct UnionFind {
  vector<int> par;

  UnionFind(int N) : par(N) { rep(i, N) par[i] = i; }

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

  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx==ry) return;
    par[rx] = ry;
  }

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

};

int main() {
  int N; cin >> N;
  bool used[2*N_MAX]={};
  UnionFind tree(2*N_MAX);
  rep(i,N) {
    int x, y; cin >> x >> y; x--; y--;
    used[x]=true; used[y+N_MAX]=true;
    tree.unite(x, y+N_MAX);
  }
  ll arr[2*N_MAX]={};
  rep(i,2*N_MAX) {
    if (used[i]) {
      int r = tree.root(i);
      if (i>=N_MAX) arr[r%N_MAX+N_MAX]++;
      else arr[r%N_MAX]++;
    }
  }

  // rep(i,2*N_MAX) if (arr[i]) cout << i << " " << arr[i] << endl;
  ll result = 0;
  rep(i,N_MAX) result += arr[i] * arr[i+N_MAX];
  result -= N;
  cout << result << endl;
  return 0;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define MMAX (ll)(1e9)
#define MAX 20000

int main(){
	ll n;
	cin >> n;
	ll a[n+1], b[n+1], p[n];
	for(int i=0; i<n; i++) cin >> p[i];
	for(int i=1; i<=n; i++){
		a[i]=i*2*MAX;
		b[i]=MMAX-a[i];
	}
	for(int i=0; i<n; i++){
		b[p[i]]+=i;
	}

	for(int i=1; i<=n; i++) cout << a[i] << " ";
	cout << endl;
	for(int i=1; i<=n; i++) cout << b[i] << " ";
	cout << endl;

	return 0;
}

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

string a, b, c = "";
int matriz[3002][3002];


int lcs(int t, int l)
{   

    if(t < 0 || l < 0)
    {
        return 0;
    }
    if(matriz[t][l] >= 0)
    {
        return matriz[t][l];
    }
    if(a[t] == b[l])
    {
        return matriz[t][l] = lcs(t-1, l-1) + 1;
    }
    else
    {
        return matriz[t][l] = max(lcs(t, l-1), lcs(t-1, l));
    }


}


void lcsstring(int t, int l)
{   

    if(t < 0 || l < 0)
    {
        return;
    }
    if(a[t] == b[l])
    {
        c += a[t];
        //return matriz[t][l] = lcs(t-1, l-1) + 1;
        lcsstring(t-1,l-1);
    }
    else
    {
        if(matriz[t][l] == lcs(t, l-1))
            lcsstring(t, l-1);
        else
            lcsstring(t -1, l);
        //return matriz[t][l] = max(lcs(t, l-1), lcs(t-1, l));
    }


} 


int main(){

    
    int qtd = 0;


    getline(cin ,a);
    
    getline(cin, b);
    
    memset(matriz, -1, sizeof(matriz));
    
    int maior = lcs(a.size() - 1, b.size() - 1);

    lcsstring(a.size() - 1, b.size() - 1);

    reverse(c.begin(), c.end());

    cout << c << endl;

    return 0;
}


Measured memory_bytes: 35712
#include<stdio.h>
#define N 25

typedef struct{
  int par;
  int left;
  int right;
}node;

node T[N];

void preorder(int);
void inorder(int);
void postorder(int);

int main(){
  int n,id,i;

  scanf("%d",&n);

  for(i=0;i<n;i++) T[i].par = -1;

  for(i=0;i<n;i++){

    scanf("%d",&id);
    scanf("%d %d", &T[id].left, &T[id].right);

    if(T[id].left != -1) T[T[id].left].par = id;

    if(T[id].right != -1) T[T[id].right].par = id;

  }

  for(i=0; i<n; i++){

    if(T[i].par == -1){


      printf("Preorder\n");
      preorder(i);

      printf("\nInorder\n");
      inorder(i);

      printf("\nPostorder\n");
      postorder(i);

      printf("\n");
      break;

    }
  }

  return 0;
}


void preorder(int n){
  printf(" %d",n);

  if(T[n].left != -1) preorder(T[n].left);
  if(T[n].right != -1) preorder(T[n].right);

}

void inorder(int n){
  if(T[n].left != -1) inorder(T[n].left);

  printf(" %d",n);

  if(T[n].right != -1) inorder(T[n].right);

}

void postorder(int n){

  if(T[n].left != -1) postorder(T[n].left);

  if(T[n].right != -1) postorder(T[n].right);

  printf(" %d",n);
}

Measured memory_bytes: 616
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			scanner.nextLine();
			List<Store> list = IntStream.range(0, n).mapToObj(i -> {
				Store store = new Store();
				store.price = scanner.nextInt();
				store.amount = scanner.nextInt();
				scanner.nextLine();
				return store;
			}).sorted((x, y) -> x.price - y.price).collect(Collectors.toList());
			long sum = 0;
			for (int i = 0; i < list.size(); i++) {
				Store store = list.get(i);
				if (store.amount >= m) {
					sum += (long) store.price * m;
					break;
				} else {
					sum += (long) store.price * store.amount;
					m -= store.amount;
				}
			}
			System.out.println(sum);
		}
	}

	private static class Store {
		int price;
		int amount;
	}
}


Measured memory_bytes: 157988
#include<stdio.h>
int main(){
  int w,h,i,j,dp[55][55]={1};
  char d[55][55];
  scanf("%d %d",&h,&w);
  for(i=0;i<h;i++){
    for(j=0;j<w;j++)scanf(" %c",&d[i][j]);
  }
  for(i=0;i<h+w;i++){
    for(j=0;j<h;j++){
      if(i-j<0||w<=i-j)continue;
      if(dp[j+1][i-j]>dp[j][i-j]+d[j+1][i-j]-'0'||dp[j+1][i-j]==0){
	 dp[j+1][i-j]=dp[j][i-j]+d[j+1][i-j]-'0';
      }
      if(dp[j][i-j+1]>dp[j][i-j]+d[j][i-j+1]-'0'||dp[j][i-j+1]==0){
	 dp[j][i-j+1]=dp[j][i-j]+d[j][i-j+1]-'0';
      } 
    }
  }
  /*for(i=0;i<h;i++){
    for(j=0;j<w;j++)printf("%d ",dp[i][j]);
    printf("\n");
    }//*/
  printf("%d\n",dp[h-1][w-1]-1);
  return 0;
}
      

Measured memory_bytes: 620
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define F first
#define S second
const string nl="\n";
const ll MOD=1e9+7;
const ll ARR_MAX = 1e5+1;
const ll INF=1e14;

void solve(){
    int n;cin>>n;
    ld p[n];
    for(int i=0;i<n;i++){
    	cin>>p[i];
    }
    ld dp[n+1][n+1]={}; //dp[i][j]= probability of having j heads after (i-1)th toss.
    dp[0][0]=1;
    for(int i=0;i<n;i++){
    	for(int j=0;j<=i+1;j++){
    		if(j!=0){
    			dp[i+1][j]=dp[i][j-1]*p[i];
    		}
    		dp[i+1][j]+=dp[i][j]*(1-p[i]);
    	}
    }
    // for(int i=0;i<=n;i++){
    // 	for(int j=0;j<=n;j++){
    // 		cout<<dp[i][j]<<" ";
    // 	}
    // 	cout<<nl;
    // }
    ld prob=0;
    for(int i=n;2*i>n;i--){
    	prob+=dp[n][i];
    }
	cout<<fixed<<setprecision(11);
    cout<<prob<<nl;
}

int main(){
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 140928
#include<stdio.h>
#include<string.h>
#define min(a,b) ( (a) < (b) ? (a) : (b) )

char str[200001];
int ans,sumT,sumS;

int main(void){
	register int i,len;
	scanf("%s",str);
	len=strlen(str);
	for(i=0;i<len;i++){
		if(str[i]=='S')
			sumS++;
		else if(sumS)
			sumT++;
		if(sumS>=sumT){
			ans+=min(sumS,sumT)<<1;
			sumS-=min(sumS,sumT);
			sumT=0;
		}
	}
	printf("%d\n",len-ans);
	return 0;
}

Measured memory_bytes: 384
N = int(input())
a = [2 if int(x) % 4 == 0 else 1 if int(x) % 2 == 0 else 0 for x in input().split()]
if N % 2 == 0:
    if sum(a) >= N:
        print('Yes')
    else:
        print('No')
else:
    if sum(a) >= N-1:
        print('Yes')
    else:
        print('No')



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

#define MOD 1000000007
#define ll long long int 
#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

// double dp[3000][3001];

int main()
{
    off;

    int n,k; cin>>n>>k;
    int arr[n];

    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }
    int dp[k+1];

    for (int i = 0; i < arr[0]; ++i)
    {
        dp[i] = 0;
    }

    for (int i = arr[0]; i <= k; ++i)
    {
        dp[i] = 1;
        for (int j = 0; j < n && arr[j] <= i; ++j)
        {
            dp[i] = min(dp[i], dp[i-arr[j]]);
        }
        dp[i] = dp[i]^1;
    }

    if(dp[k])
        cout<<"First";
    else
        cout<<"Second";
    return 0;
}


Measured memory_bytes: 640
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 1e9 + 7;
const int mxN = 1e6 + 5;

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

int dp[mxN][11][2][2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	rep(i, 10) dp[0][i][(i == 0)][(i == 9)] = 1;
	repn(i, 1, n){
		rep(j, 10) rep(m, 10) rep(k, 2) rep(l, 2){
			(dp[i][j][k | (j == 1)][l | (j == 9)] += dp[i - 1][m][k][l]) %= MOD;
		}
	}
	int ans = 0LL;
	rep(i, 10) (ans += dp[n - 1][i][1][1]) %= MOD;
	cout << ans << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

inline int read()
{
    int num=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch^48);
        ch=getchar();
    }
    return w?-num:num;
}

inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
int arr[1000000];
ll brr[1000000];
ll crr[1000000];
char cc[1000000];
int main()
{
  ll n =read();
  int  num =1;int sum =0 ;
  for(int i=0;i<n;i++){
    arr[i]=read();
    if(arr[i]!=num){
        sum++;
    }
    else num++;
  }
  if(sum == n)cout<<-1<<endl;
  else   cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 2304
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))
min_num = 1
min_index = A.index(min_num)

left_opes = math.ceil(min_index / (K - 1))
left_index = left_opes * (K - 1)

right_opes = math.ceil((N - 1 - left_index) / (K - 1))

print(left_opes + right_opes)


Measured memory_bytes: 13812
def abc150_c_count_order_2():
    N = int(input())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    factorial = [1]
    for i in range(1, N+1):
        factorial.append(factorial[i-1] * i)

    def find_index(permutation, lst):
        indices = []
        for p in permutation:
            i = lst.index(p)
            indices.append(i)
            lst.pop(i)
        # print(indices)
        idx = 0
        for i in range(N):
            idx += factorial[N - i - 1] * (indices[i])
        # print(idx)
        return idx

    a = find_index(P, list(range(1, N+1)))
    b = find_index(Q, list(range(1, N+1)))
    print(abs(a-b))


##########
if __name__ == "__main__":
    abc150_c_count_order_2()


Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))

_mean1 = sum(a)//n
_mean2 = _mean1+1

_sum1=0
_sum2=0

for i in a:
    _sum1+=(i - _mean1)**2
    _sum2+=(i-_mean2)**2
    
print(min(_sum1, _sum2))

Measured memory_bytes: 3060
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

main = do
  [a,b]<-map read . words <$> getLine
  put $ ceiling ((a + b)/2)


Measured memory_bytes: 508
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef long long lli;

int h, w, y, x, d;
lli l, c;
char data[100][100];
lli vis[100][100][4];
string dir = "NESW";
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

bool check(int y, int x){
  if(y < 0 || y >= h) return false;
  if(x < 0 || x >= w) return false;
  return data[y][x] != '#';
}

void solve(){
  int m, o;
  fill(vis[0][0], vis[100][0], -1);
  bool f = false;
  vis[y][x][d] = c++;
  while(c <= l){
    int ny = y + dy[d];
    int nx = x + dx[d];
    while(!check(ny, nx)){
      d = (d+1) % 4;
      ny = y + dy[d];
      nx = x + dx[d];
    }
    y = ny;
    x = nx;
    if(vis[y][x][d] == -1 || f) vis[y][x][d] = c;
    else{
      f = true;
      lli m = c - vis[y][x][d];
      lli o = l - c;
      o %= m;
      c = l - o;
    }
    c++;
  }
  cout << y+1 << ' ' << x+1 << ' ' << dir[d] << endl;
}

main(){
  while(cin >> h >> w >> l && (h|w|l)){
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin >> data[i][j];
        for(int k=0;k<4;k++){
          if(data[i][j] == dir[k]){
            data[i][j] = '.';
            y = i;
            x = j;
            d = k;
            c = 0;
          }
        }
      }
    }
    solve();
  }
}

Measured memory_bytes: 0
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
ld EPS = 1e-12;
int INF = numeric_limits<int>::max() / 2;
int MOD = 1e9 + 7;
#define rep(i,n) for(int i=0;i<n;i++)


ll f(ll n){
    ll p = (n+1)/2;
    ll ans;
    if(n%2 == 0){
        ans = p%2 ^ n;
    }else{
        ans = p%2;
    }
    return ans;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b;
	cin >> a >> b;
	cout << (f(b) ^ f(a - 1)) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
//	cut here before submit 
//	freopen ("testcase.S4I", "r", stdin );
	string str = "";
	while (getline (cin, str ) ){
		stringstream ss (str );
		int n;
		ss >> n;
		int res = 0;
		rep (a, 10 ) rep (b, 10 ) rep (c, 10 ) rep (d, 10 ){
			if (a + b + c + d == n ){
				res++;
			} // end if
		} // end rep
		printf ("%d\n", res );
	} // end while
	
	return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <string>
#include <sstream>
#define kMaxIndex 10000

int main(void){
    std::string datasetArr[kMaxIndex];
    int intData = 0;
    for(int index = 0; index < kMaxIndex; ++index)
    {
        /* input */
        getline(std::cin, datasetArr[index]);
        
        /* output */
        std::istringstream iss(datasetArr[index]);
        iss >> intData;
        if(intData == 0)
        {
            break;
        }
        else
        {
            std::cout << "Case "<< index+1 << ": " << intData << std::endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 10101010

int main()
{
    int K;
    cin >> K;
    int count_digit=0;
    int K_=K;
    long val=0;
    ll ans=0;
    if(K%10==2||K%10==4||K%10==6||K%10==8||K%10==0||K%10==5){
        cout << -1;
    }else{
        while(K_!=0){
            count_digit++;
            K_/=10;
        }

        rep(i,count_digit){
            val+=7*pow(10,i);
            ans=count_digit;
        }
        if(val<K){
            val+=7*pow(10,count_digit);
            ans=count_digit+1;
        }
        while(val%K!=0){
            ans++;
            val%=K;
            val*=10;
            val+=7;
        }
        cout << ans << endl;
    }
    
}


Measured memory_bytes: 3992
#include<stdio.h>

int A[1000000], n;

int binarySearch(int key) {
	int left = 0;
	int right = n;
	int mid;
	while(left < right) {
		mid = (left + right) / 2;
		if(A[mid] == key) return 1;
		if(key < A[mid]) right = mid;
		else if(key > A[mid]) left = mid+1; 
	}
	return 0;	
}

int main() {
	int i, q, key, sum = 0;
	
	scanf("%d", &n);
    for(int i = 0; i < n; i++) { 
        scanf("%d", &A[i]);
    }
    
    scanf("%d", &q);
    for(int i = 0; i < q; i++) {
	    scanf("%d", &key);
		if( binarySearch(key)) sum++; 
	}
	printf("%d\n", sum);
	
	return 0;    
}
  

Measured memory_bytes: 3104
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        int count = 0;
        boolean sw = false;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        double dMax = Double.MIN_VALUE;
        double dMin = Double.MAX_VALUE;
        //StringBuilder answer=new StringBuilder();
        //input
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();

        String ans[] = {"Yes","No"};

        int ansNum = 1;
        for (int i=1;i<10;++i)
        {
            for (int j = 1;j<10;++j)
            {
                if (i*j == n)
                {
                    ansNum = 0;
                }
            }
        }

        System.out.println(ans[ansNum]);

        sc.close();
    }
}

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

int A,B,C,D,Area1,Area2;
int main() {
    cin >> A >> B >> C >> D;

    Area1=A*B;
    Area2=C*D;

    if(Area1>Area2){
        cout << Area1 << endl;
    }
    else if(Area1==Area2){
        cout << Area1 << endl;
    }
    else{
        cout << Area2 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
S=input()
L=[]
for i in range(len(S)):
	if S[i]=="1":
		L.append(1)
	elif S[i]=="0":
		L.append(0)
	elif S[i]=="B":
		L=L[0:-1]
for i in range(len(L)):
	print(L[i],end="")
print()

Measured memory_bytes: 3060
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5002;
typedef long long ll;
struct cy{
	int H,P;
}a[N];
int n,i,j;
ll f[N];
int Min(int x,int y){
	return x<y?x:y;
}
bool cmp(cy x,cy y){
	return Min(x.H,y.H-x.P)>Min(y.H,x.H-y.P);
}
void init(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&a[i].H,&a[i].P);
	sort(a+1,a+n+1,cmp);
}
void work(){
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(i=1;i<=n;i++){
		for(j=N-2;j>=0;j--)
			if(f[j]<=a[i].H)
				f[j+1]=min(f[j+1],f[j]+a[i].P);
	}
	for(i=N-1;i>=0;i--)
		if(f[i]<1ll<<50){
			printf("%d\n",i);
			return;
		}
}
int main(){
	init();
	work();
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<limits.h>
#include<assert.h>
#include<stdbool.h>
#include<stddef.h>
#include<stdint.h>
#include<string.h>
#include<unistd.h>
#include<stdlib.h>

#include<ctype.h>
#include<time.h>
typedef long long ll;
#define pi 3.14159
int main()
{ 
int x,flag=0;
scanf("%d",&x);
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
if(i*j==x){flag=1;break;}}}
printf((flag==1)?"Yes":"No");



return 0;
}

Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

int main() {
    int x, y, z, K;
    cin >> x >> y >> z >> K;
    vector<Int> a(x), b(y), c(z);

    for (int i = 0; i < x; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < y; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < z; i++) {
        cin >> c[i];
    }
    sort(a.begin(), a.end(), greater<>());
    sort(b.begin(), b.end(), greater<>());
    sort(c.begin(), c.end(), greater<>());

    vector<Int> ans;
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            for (int k = 1; k <= z; k++) {
                if (i * j * k <= K) {
                    ans.push_back(a[i - 1] + b[j - 1] + c[k - 1]);
                } else {
                    break;
                }
            }
        }
    }

    sort(ans.begin(), ans.end(), greater<>());
    for (int i = 0; i < K; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 1404
#include<iostream>

using namespace std;

struct point{
	double x;
	double y;
};

struct rect{
	point LB;
	point RT;
};

istream& operator >> ( istream& s , rect& d );
bool isIntersection( const rect& a , const rect& b );

int main(void)
{
	rect a, b;

	while(1)
	{
		cin >> a >> b;
		if( cin.eof() ) break;
		cout << ( isIntersection( a , b ) ? "YES" : "NO" ) << endl;
	}

	return 0;
}

istream& operator >> ( istream& s , rect& d )
{
	return s >> d.LB.x >> d.LB.y >> d.RT.x >> d.RT.y;
}

bool isIntersection( const rect& a , const rect& b )
{
	if( a.LB.y > b.RT.y || a.RT.y < b.LB.y || a.LB.x > b.RT.x || a.RT.x < b.LB.x )
	{
		return false;
	}
	else
	{
		return true;
	}
}

Measured memory_bytes: 1216
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k, c = map(int, readline().split())
s = input()
cnt_1 = 0
cnt_2 = n - 1
cnt = [0, 0]
ans = [0] * n
for i in range(n):
    if s[cnt_1] == 'o':
        ans[cnt_1] += 1
        cnt_1 += c
        cnt[0] += 1
    cnt_1 += 1
    if cnt_1 > n - 1:
        break
for i in range(n):
    if s[cnt_2] == 'o':
        ans[cnt_2] += 1
        cnt_2 -= c
        cnt[1] += 1
    cnt_2 -= 1
    if cnt_2 < 0:
        break
if max(cnt) > k:
    print()
else:
    for i in range(n):
        if ans[i] == 2:
            print(i + 1)


Measured memory_bytes: 6360
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using Graph = vector<vector<int>>;
using P = pair<int,int>;
using ll =long long;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int vec[3] = {3,5,7};

int keta(ll n){
    int res=0;
    while(n){
        n /= 10;
        res++;
    }
    return res;
}

int main(){
    ll n;cin>>n;
    int tt = n;
    int size = keta(n);
    //cout << "size is " << size << endl;
    queue<ll> con;
    queue<ll> que;
    for(int i=3;i<=7;i+=2) que.push(i);
    for(int i=0;i<size-1;i++){ // 桁数
        queue<ll> sub;
        while(!que.empty()){
            ll tmp = que.front();
            que.pop();
            rep(j,3){
                int t = 10*tmp + vec[j];
                con.push(t);
                sub.push(t);
            }
        }
        while(!sub.empty()){
            ll t = sub.front();
            sub.pop();
            que.push(t);
        }
    }
    ll ans = 0;
    while(!con.empty()){
        ll t = con.front();
        con.pop();
        //int t_s = keta(t);
        string s = to_string(t);
        bool thr=false,fiv=false,sev=false;
        if(t>n) continue;
        rep(i,s.size()){
            if(s[i]=='3') thr = true;
            else if(s[i]=='5') fiv = true;
            else if(s[i]=='7') sev = true;
        }
        if(thr && fiv && sev){
            //cout << t << " is good" << endl;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <complex>
#include <cassert>

#define enp     puts("**chkchkchkchkchk**")
#define A       first
#define B       second
#define MP      make_pair

using namespace std;

typedef long long ll;
typedef unsigned int uint;

const int INF = 0x60000000;
const int MINF = -1000000000;
const int mod = 1000000007;
const ll cons = 100000;
const double pi = 3.141592653589793;


int main()
{
	int n;
	scanf("%d", &n);

	ll a = 0, b = 0;

	for (int i = 0; i < n; i++)
	{
		ll x, y;
		cin >> x >> y;

		ll L = 0;
		ll R = (ll)2e18 / max(x, y);

		while (L + 1 < R)
		{
			ll mid = L + R >> 1;

			ll X = x*mid;
			ll Y = y*mid;

			if (X >= a && Y >= b)R = mid;
			else L = mid;
		}

		a = R*x;
		b = R*y;
	}

	printf("%lld\n", a + b);

	return 0;
}

Measured memory_bytes: 256
#coding: utf-8
import math
import heapq

N = int(input())

A = []
for i in range(N):
    a = tuple(map(int, input().split()))
    A.append(a)

ans = 0
for a1 in A:
    for a2 in A:
        ans += math.sqrt((a1[0]-a2[0])**2 + (a1[1]-a2[1])**2)

ans /= N
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
ll mod=1e18;
const ll inf = (ll)1e17;
const ld eps = 1e-12;
const ld PI = 3.14159265358979323846;
ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}
long modInverse(long a) {return powmod(a, mod-2);}
ll my_rand(){ll a=rand();ll b=rand();return (a*RAND_MAX+1)+b;}
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

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

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()


int main(){
    ios::sync_with_stdio(false);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    reverse(s.begin(),s.end());
    int n=s.size();
    map<ll,ll>m;
    m[0]=1;
    ll val=0;
    ll base=1;
    ll res=0;
    for(int i=0;i<n;i++){
        val=base*(s[i]-'0')+val;
        val%=2019;
        base*=10;
        base%=2019;
        if(m[val]){
            res+=m[val];
        }
        m[val]++;
    }
    cout<<res<<endl;
    return 0;
    }


Measured memory_bytes: 3752
#![allow(unused_imports, non_snake_case)]
use proconio::{
    input, fastout,
    marker::{Chars, Bytes, Usize1}
};

#[fastout]
fn main() {
    input!{
        s: Chars,
        t: Chars,
    }
    let n = s.len();
    let m = t.len();
    let mut ans = m;
    for i in 0..n-m+1 {
        let mut cur = 0;
        for j in 0..m {
            if s[i+j] != t[j] {cur += 1};
        }
        ans = std::cmp::min(ans, cur);
    }
    println!("{}", ans);
}


Measured memory_bytes: 2148
def func(x1, y1, x2, y2):
    xd = x2 - x1
    yd = y2 - y1
    for i in range(xd):
        print("R", end="")
    for j in range(yd):
        print("U", end="")
    return

def func2(a1, b1, a2, b2):
    ad = a2 - a1
    bd = b2 - b1
    for k in range(ad):
        print("L", end="")
    for l in range(bd):
        print("D", end="")
    
a = list(map(int,input().split()))

func(a[0],a[1],a[2],a[3])
func2(a[0],a[1],a[2],a[3])
print("D", end="")
func(a[0],(a[1] - 1),(a[2] + 1),a[3])
print("L", end="")
print("U", end="")
func2(a[0],(a[1] - 1),(a[2] + 1),a[3])
print("R", end="")

Measured memory_bytes: 47848
import java.util.HashSet;
import java.util.Scanner;

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

    long MOD = 1_000_000_007;
    int N = scanner.nextInt();
    int M = scanner.nextInt();
    HashSet<Integer> a = new HashSet<>();
    for (int i = 0; i < M; i++) a.add(scanner.nextInt());
    long[] dp = new long[N + 1];
    dp[0] = 1;
    if (!a.contains(1)) dp[1] = 1;
    for (int i = 2; i <= N; i++) {
      if (!a.contains(i)) {
        dp[i] += dp[i - 1];
        if (dp[i] >= MOD) dp[i] -=MOD;
        dp[i] += dp[i - 2];
        if (dp[i] >= MOD) dp[i] -=MOD;
      }
    }
    System.out.println(dp[N]);
  }
}


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

int main(){
    int n,m;cin >> n >> m;
    int p[m];string s[m];
    rep(i,m)cin >> p[i] >> s[i];

    map<int,int> mp;
    int ac = 0,wa = 0;

    rep(i,m){
        if(s[i] == "WA" && mp[p[i]] != -1){
            mp[p[i]] += 1;
        } else if(s[i] == "AC" && mp[p[i]] != -1){
            ac += 1;wa += mp[p[i]];
            mp[p[i]] = -1;
        }
    }
    cout << ac << " " << wa << endl;
    return 0;
}

Measured memory_bytes: 10752
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

int H, W;
char S[15][15];
int half;
int ary[12];
bool ary_flg[12];

bool check()
{
	bool flg[12] = {};
	int cnt = 0;
	for (int y1 = 0; y1 < H; y1++)
	{
		if (flg[y1]) continue;
		for (int y2 = y1 + 1; y2 < H; y2++)
		{
			if (flg[y2]) continue;
			bool is_valid = true;
			for (int x = 0; x < W; x++)
			{
				if (S[y1][ary[x]] != S[y2][ary[W - x - 1]])
				{
					is_valid = false;
					break;
				}
			}
			if (is_valid)
			{
				flg[y1] = true;
				flg[y2] = true;
				cnt += 2;
				break;
			}
		}
	}

	if (H % 2 == 1)
	{
		if (H - 1 != cnt)
		{
			return false;
		}

		int c;
		REP(y, H)
		{
			if (!flg[y])
			{
				c = y;
				break;
			}
		}
		for (int x = 0; x < W / 2; x++)
		{
			if (S[c][ary[x]] != S[c][ary[W - x - 1]])
			{
				return false;
			}
		}

		return true;
	}
	else
	{
		return (H == cnt);
	}
}

void comb2(int n)
{
	if (n >= W)
	{
		if (check())
		{
			cout << "YES" << endl;
			exit(0);
		}
		return;
	}

	int index = W - (n - half) - 1;
	int init = ary[n - half];
	for (int i = init; i < W; i++)
	{
		if (ary_flg[i]) continue;
		ary[index] = i;
		ary_flg[i] = true;
		comb2(n + 1);
		ary_flg[i] = false;
	}

}

void comb(int n)
{
	if (n >= W / 2)
	{
		if (W % 2 == 1 && n == W / 2)
		{
			for (int i = 0; i < W; i++)
			{
				if (!ary_flg[i])
				{
					ary_flg[i] = true;
					ary[n] = i;
					comb(n + 1);
					ary_flg[i] = false;
				}
			}
			return;
		}

		comb2(n);
		return;
	}

	int init = n == 0 ? 0 : (ary[n - 1] + 1);
	for (int i = init; i < W; i++)
	{
		ary[n] = i;
		ary_flg[i] = true;
		comb(n + 1);
		ary_flg[i] = false;
	}
}

signed main()
{
	cin >> H >> W;
	REP(y, H)
	{
		cin >> S[y];
	}
	half = W / 2;
	if (W % 2 == 1) half++;
	comb(0);
	cout << "NO" << endl;
}






Measured memory_bytes: 384
using System;
class SS
{
  static void Main()
  {
    var lines=Console.ReadLine().Split(' ');
    int K=int.Parse(lines[0]);
    int M=int.Parse(lines[1]);
    int distance=0;
    int before=0;
    lines=Console.ReadLine().Split(' ');
    int now=0;
    before=int.Parse(lines[0]);
    distance=before+K-int.Parse(lines[M-1]);
    for(int i=1;i<M;i++)
    {
      now=int.Parse(lines[i]);
      if(distance<now-before)
      distance=now-before;
      before=now;
    }
    Console.WriteLine(K-distance);
  }
}

Measured memory_bytes: 28892
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			int n=in.nextInt(),m=in.nextInt(),a=in.nextInt();
			if((n|m|a)==0)
				return;
			int A[][]=new int[1001][n+1];
			int sh=1;
			int sw=a;
			for(int i=0;i<m;i++)
			{
				int h=in.nextInt();
				int p=in.nextInt();
				int q=in.nextInt();
				sh=Math.max(sh,h);
				A[h][p]=q;
				A[h][q]=p;
			}
			for(;;)
			{
				if(A[sh][sw]!=0)
					sw=A[sh][sw];
				sh--;
				if(sh==0)
					break;
			}
			System.out.println(sw);
		}
	}
}

Measured memory_bytes: 71140