akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;

ll solve(ll a, ll b) {
    if (a == b) {
        return 2 * (a - 1);
    }

    ll left = 0, right = 1L << 32;

    while (right - left > 1) {
        ll mid = (left + right) / 2;
        ll maxScore = (mid / 2) * (mid - mid/2);
        if (maxScore <= a * b - 1) {
            //ok
            left = mid;
        }
        else {
            right = mid;
        }
    }

    return left - 2; // ABがふくまれているので除く
}

void Main()
{
    ll Q;
    cin >> Q;

    vector<ll> A(Q), B(Q);
    rep(i, Q) cin >> A[i] >> B[i];
    
    rep(i, Q ) {
        put(solve(A[i], B[i]));
    }
}
signed main(){ Main();return 0;}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using ll = long long;
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;

int main(){
  ll n, k;
  string s;
  cin >> n >> k;
  cin >> s;
  vector<ll> sum;
  sum.push_back(0);
  char prev = s[0];
  rep(i, n){
    if (s[i] != prev){
      sum.push_back(i);
    }
    prev = s[i];
  }
  sum.push_back(n);
  sum.push_back(n);
  ll sz = sum.size();
  sum.push_back(n);
  ll x;
  if (s[0] == '0') x = 0;
  else x = 1;
  ll ans = 1;
  k = min(k, (sz-1)/2);
  for(ll i = x; i+k*2 <= sz; i+=2){
    if (i == 0) ans = max(ans, sum[k*2]);
    else ans = max(ans, sum[i+k*2]-sum[i-1]);
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4372
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 100005;

int n, t, l;

int hou[maxn];

int main()
{
    scanf("%d%d%d", &n, &l, &t);
    int fromm = 0;
    for (int i = 1, x, fx; i <= n; ++i)
    {
        scanf("%d%d", &x, &fx);
        if (fx == 2)
        {
            hou[i] = x - t;
            (fromm -= (l - hou[i] - 1) / l) %= n;
            // cout << "hou = " << hou[i] << endl;
            ((hou[i] %= l) += l) %= l;
        }
        else
        {
            hou[i] = x + t;
            // cout << "hou = " << hou[i] << endl;
            (fromm += hou[i] / l) %= n;
            hou[i] %= l;
        }
    }
    (fromm += n) %= n;
    sort(hou + 1, hou + n + 1);
    // cout << "n = " << n << ' ' << fromm << endl;
    for (int i = fromm + 1; i <= n; ++i)
        printf("%d\n", hou[i]);
    // puts("");
    for (int i = 1; i <= fromm; ++i)
        printf("%d\n", hou[i]);
    return 0;
}


Measured memory_bytes: 1536
H, W = map(int, input().split())

grids = []
for _ in range(H):
    grids.append(input())

hr_scores = []
vr_scores = []


max_value = 0
for w in range(W):
    cnt = 0
    start_h = 0
    lis = []
    for h in range(H):    
        if grids[h][w] == '.':
            cnt += 1
        else:
            lis += [cnt] * (h - start_h) + [0]
            start_h = h + 1
            cnt = 0
    if cnt:
        lis += [cnt] * (h - start_h + 1)
    vr_scores.append(lis)
vr_scores = [[vr_scores[w][h] for w in range(W)] for h in range(H)]
for h in range(H):
    cnt = 0
    start_w = 0
    lis = []
    for w in range(W):
        if grids[h][w] == '.':
            cnt += 1
        else:
            lis += [cnt] * (w - start_w) + [0]
            if cnt:
                max_value = max(
                    max_value,
                    max(vr_scores[h][start_w: w]) + cnt
                )
            start_w = w + 1
            cnt = 0
    if cnt:
        max_value = max(
            max_value,
            max(vr_scores[h][start_w: w + 1]) + cnt
         )

print(max(max_value - 1, 0))

Measured memory_bytes: 126424
#include <iostream>

using namespace std;

int main() {
	char s[4];
	int f, b;
	cin >> s;

	f = 10 * (s[0] - '0') + (s[1] - '0');
	b = 10 * (s[2] - '0') + (s[3] - '0');

	if ((0 < f && f < 13) && (0 < b && b < 13)) {
		cout << "AMBIGUOUS" << endl;
	}
	else if ((0 < f && f < 13) && 0 <= b) {
		cout << "MMYY" << endl;
	}
	else if ((0 < b && b < 13) && 0 <= f) {
		cout << "YYMM" << endl;
	}
	else {
		cout << "NA" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
using namespace std;
 int main(){ 
  string s;
  int k;
  cin>>s>>k;
  vector<string> substrs;
  for (int i = 0; i < k; i++){
    for (int j = 0; j < s.size() - i; j++){
	  string substr = s.substr(j, i + 1);
      if (find(substrs.begin(), substrs.end(), substr) == substrs.end())
        substrs.push_back(substr);
    }
  }
  sort(substrs.begin(), substrs.end());
  cout << substrs[k - 1] << endl;
  return 0;
}

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

int main() {
  int N, count = 0, max = 0;
  string S;
  cin >> N >> S;
  for (int i = 0; i < N; i++) {
    if (S.at(i) == 'I') {
      count++;
      if (count > max) {
        max = count;
      }
    }
    else {
      count--;
    }
  }
  cout << max << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String args[]){
    Scanner scan = new Scanner(System.in);
    while(true){
        int num=scan.nextInt();
        if(num==0){
            break;
        }
        int[] data=new int[num];
        int max=0,min=0,sum=0;
        for(int i=0;i<num;i++){
            data[i]=scan.nextInt();
            if(i==0){
                max=data[i];
                min=data[i];
            }
            else if(data[i]>max){
                max=data[i];
            }
            else if(data[i]<min){
                min=data[i];
            }
            sum=sum+data[i];
        }
        System.out.println((sum-min-max)/(num-2));
    }
  }
}


Measured memory_bytes: 28344
#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, a, MOD = 1e9 + 7;
    cin >> N >> M;
    vector<int> dp(N + 1, 1);
    rep(i, M) {
        cin >> a;
        dp[a] = 0;
    }
    for (int i = 2; i <= N; i++) {
        if (dp[i] != 0) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 640
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

A,B,DEGREE = map(int,input().split())

rad = math.radians(DEGREE)

S = A*B*math.sin(rad)/2.0
C = math.sqrt(A*A+B*B-2*A*B*math.cos(rad))
h = 2*S/A

print("%.10f %.10f %.10f"%(S,A+B+C,h))


Measured memory_bytes: 6424
n = int(input())
x = input()


def count(n):
    ans = 0
    while n:
        ans += n % 2
        n //= 2
    return ans


ma = 5*10**5
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % count(i)]+1

c = x.count("1")
a = int(x, 2) % (c+1)

if c==1:
    for i in range(n):
        if x[i] == "0":
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
        else:
            print(0)
    exit()

b = int(x, 2) % (c-1)
for i in range(n):
    if x[i] == "0":
        print(dp[(a + pow(2,n-i-1,c+1))%(c+1)] + 1)
    else:
        print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)



Measured memory_bytes: 13480
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }
#define INF           1e9
#define INFL          static_cast<lint>(INF)
#define REP(i,n)      for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)     for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)     for(lint i=n-1;i>=0;--i)
#define REPR1(i,n)    for(lint i=n;i>0;--i)
#define REPI(i,ini,n) for(lint i=(ini),i##_len=(n);i<i##_len;++i)
#define REPC(i,obj)   for(auto i:obj)
#define R_UP(a,b)     (((a)+(b)-1)/(b))
#define ALL(obj)      (obj).begin(),(obj).end()
int main()
{
	int n = in(), k = in();
	int dist = 0;
	REP1(i, n)
	{
		int x = in();
		dist += 2 * min(x, abs(x - k));
	}
	cout << dist << endl;
}

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


vector<int> G[100000];
int color[100000];
int white = 0;

bool dfs(int v, int c) {
    color[v] = c;
    if (c == 1) white++;
    for (ll i = 0; i < G[v].size(); i++) {
        if (color[G[v][i]] == c) return false;
        if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
    }
    return true;
}

int main()
{
    ll N, M;
    cin >> N >> M;
    for (ll i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; 
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if (dfs(0,1)) {cout << white*(N-white) - M << endl;} 
    else {cout << N*(N-1)/2 - M << endl;}
    return 0;
}

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

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

  ll x[3];
  ll y[3];
  for(int i = 0; i < 3; i++){
    x[i] = 0;
    y[i] = 0;
  }

  if(s <= 1000000000){
    x[1] = s;
    y[1] = 0;
    x[2] = 0;
    y[2] = 1;
  }else{
    x[1] = 1000000000;
    y[1] = 1;
    x[2] = (x[1] - s % x[1]) % x[1];
    y[2] = (s + x[2]) / x[1];
  }

  for(int i = 0; i < 2; i++){
    cout << x[i] << " " << y[i] << " ";
  }
  cout << x[2] << " " << y[2] << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
const int64_t INF=9999999999999999;
int main() {
 int N;
 cin>>N;
 int count=0;
 vector<int>A(N);
 for(int i=0;i<N;i++){
    cin>>A[i];
 }
 while(true){
 bool ok=true;
 for(int i=0;i<N;i++){
    if(A[i]%2!=0){ok=false;break;}
 }
 if(ok==false){break;}
 else{count++;
 for(int i=0;i<N;i++){
    A[i]/=2;
 }}
 }
 cout<<count<<endl;
 return 0;}

Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		n: usize,
		x: usize,
		mut m: [usize; n],
	}

	let mut sum = 0;
	let mut mmin = 9999;
	for i in 0..n {
		sum += m[i];
		mmin = min(mmin, m[i]);
	}
	println!("{}", (x-sum)/mmin+n);
}



Measured memory_bytes: 2152
#include<stdio.h>
int main()
{
    int n,i,j,k,c=0;
    scanf("%d", &n);
    int s[n+5];
    for(i=0;i<n;i++)
    {
        scanf("%d", &s[i]);
    }
    for(i=1;i<n-1;i++)
    {
        if(s[i-1]<s[i])
        {
            if(s[i]<s[i+1])
                c++;
        }
        else if(s[i-1]>s[i])
        {
            if(s[i]>s[i+1])
                c++;
        }
    }
    printf("%d\n", c);
}


Measured memory_bytes: 1708
#include <stdio.h>

int main(){
    int m1, d1, m2, d2;
    scanf("%d %d", &m1, &d1);
    scanf("%d %d", &m2, &d2);
    if (d1 == 30){
        if (m1 == 4 || m1 == 6 || m1 == 9 || m1 == 11)
            printf("1\n");
        else
            printf("0\n");
    }
    else if (d1 == 31){
        if (m1 == 1 || m1 == 3 || m1 == 5 || m1 == 7 || m1 == 8 || m1 == 10 || m1 == 12)
            printf("1\n");
        else
            printf("0\n");
    }
    else if (d1 == 28 && m1 == 2)
        printf("1\n");
    else
        printf("0\n");
    return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m; cin>>n>>m;
	vector<vector<int>>c(n,vector<int>(m)); for(auto&&i:c)for(auto&&j:i)cin>>j;
	vector<int>b(m); for(auto&&i:b)cin>>i;
	for(int i=0;i<n;++i){
		int sum=0;
		for(int j=0;j<m;++j){
			sum+=c.at(i).at(j)*b.at(j);
		}
		cout<<sum<<"\n"s;
	}
}


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

int main() {
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  char ch = S.at(K - 1);
  if (ch == 'A'){
    S.at(K - 1) = 'a';
  }
  else if (ch == 'B'){
    S.at(K - 1) = 'b';
  }
  else if (ch == 'C'){
    S.at(K - 1) = 'c';
  }
  cout << S << endl;
}


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

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int A, B, K; 
  cin >> A >> B >> K;

  for(int i = A; i < A+K && i < B-K+1; i++){
    cout << i << "\n";
  }
  for(int i = max(A, B-K+1); i <= B; i++){
    cout << i << "\n";
  }

  return 0;
}

Measured memory_bytes: 256
import sys
from collections import deque
import numpy as np
import math
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    x = I()
    a = x//500
    x -= a*500
    b = x//5
    print(1000*a+5*b)
    return

if __name__=='__main__':
    Main()

Measured memory_bytes: 27132
while 1:
	n = input()
	if n == 0: break
	ans = {}
	for i in range(n):
		group,name = raw_input().split(":")
		if i == 0: first = group
		ans[group] = set(name[:-1].split(","))
		while 1:
			for key in ans:
				flag = 0
				if key == first: continue
				for key1 in ans:
					if key in ans[key1]:
						ans[key1] |= ans[key]
						ans[key1].discard(key)
						flag = 1
			if flag == 0: break
	print len(ans[first])

Measured memory_bytes: 4464
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+3;
int a[N],d[N],c[N],b[N],tmp[N];
ll n,m,k,x;
void qmod(){
    while(k){
        if(k&1){
            for (int i=1; i<=n; i++)
                tmp[i]=b[c[i]];
            for (int i=1; i<=n; i++)
                b[i]=tmp[i];
        }
        k>>=1;
        for (int i=1; i<=n; i++)
            tmp[i]=c[c[i]];
        for (int i=1; i<=n; i++)
            c[i]=tmp[i];
    }
}
int main(){
    scanf("%lld",&n);
    for (int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        d[i]=a[i]-a[i-1];
        tmp[i]=b[i]=c[i]=i;
    }
    scanf("%lld%lld",&m,&k);
    for (int i=1; i<=m; i++){
        scanf("%d",&x);
        swap(c[x],c[x+1]);
    }
    qmod();
    ll ans=0;
    for (int i=1; i<=n; i++){
        ans+=1ll*d[b[i]];
        printf("%lld.0\n",ans);
    }
    return 0;
}

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

string index="IVXLCDM";
int trans[]={1,5,10,50,100,500,1000};

int t_num(char c){
	for(int i=0;i<index.size();i++){
		if(c==index[i]){
			return trans[i];
		}
	}
}

int main(){
	string input;
	while(cin>>input){
		int ans=0;
		vector<int> in;
		for(int i=0;i<input.size();i++){
			in.push_back(t_num(input[i]));
		}
		int tmp=0;
		tmp=in[0];
		for(int i=1;i<in.size();i++){
			if(in[i]>in[i-1]){
				tmp=in[i]-tmp;
			}else if(in[i]<in[i-1]){
				ans+=tmp;
				tmp=in[i];
			}else{
				tmp+=in[i];
			}
		}
		ans+=tmp;
		cout<<ans<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define FOR(i, N)         for(int i = 0; i < (N); i++)
using ll = long long;
using vll = vector<ll>;

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int N; cin >> N;
  vll inp(N);
  FOR(i, N) cin >> inp[i];
  sort(inp.begin(), inp.end());
  ll s1 = -1, s2 = -1;
  for(int i = N-1; i - 1 >= 0; i--){
    if(inp[i] == inp[i-1]){
      if(s1 == -1) s1 = inp[i--];
      else{ cout << s1*inp[i]; return 0;} 
    }
  }
  cout << 0;
  return 0;
}

Measured memory_bytes: 3968
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M;
int a[301][301];
bool used[301];
int ans=100000;
void f(int x,int depth){
  if(depth==M)return ;
  int P,Q=0;
  int Count[301]={0};
  used[x]=false;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      if(used[a[i][j]]){Count[a[i][j]]++;break;}
    }
  }
  for(int i=1;i<=M;i++){
    if(Q<Count[i]){Q=Count[i];P=i;}
  }
  ans=min(ans,Q);
  f(P,depth+1);
}
int main(){
  cin >> N >> M;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      cin >> a[i][j];
    }
  }
  for(int i=0;i<=M;i++)used[i]=true;
  f(0,0);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
use proconio::input;

fn main() {
    input! {
        s: String,
    }
    let par = s.len()
        + (if s.as_bytes()[0 as usize] == s.as_bytes()[s.len() - 1] {
            1
        } else {
            0
        });

    println!("{}", if par % 2 == 1 { "First" } else { "Second" })
}


Measured memory_bytes: 2336
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
#include <tuple>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define repeq(i, a, n) for (int i = a; i <= n; ++i)
#define repi(m, itr) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

ll mod = 1000000007;

// 繰り返し二乗法（MOD）
template <typename T>
T DoublingPow(T a, T p)
{
    if (p == 0)
        return 1;
    if (p % 2 == 0)
    {
        T half_p = p / 2;
        T half = DoublingPow(a, half_p);
        return half * half % mod;
    }
    else
    {
        return a * DoublingPow(a, p - 1) % mod;
    }
}

// 素因数分解
// map<素因数, 乗数>
template <typename T>
map<T, T> PrimeFactorize(T n){

    map<T, T> primelist;
    T nrest = n;

    for (T i = 2; i * i <= nrest;++i){
        if(nrest %i == 0){
            T cnt = 0;
            // 同じ素因数で割り切れるだけ割り続ける（最低でも一度は割り切れる）
            while(nrest %i == 0){
                ++cnt;
                nrest /= i;
            }
            primelist[i] += cnt;
        }
    }
    if(nrest != 1){
        primelist[nrest] += 1;
    }
    return primelist;
}


//(10*9*8)/(3*2*1);
//10*9*8 -> ansMul
//3*2*1 -> ansDiv
ll calcComb(ll a, ll b) {
	if (b > a - b) return calcComb(a, a - b);
 
	ll ansMul = 1;
	ll ansDiv = 1;
	for (ll i = 0; i < b; i++)
	{
		ansMul *= (a - i);
		ansDiv *= (i + 1);
		ansMul %= mod;
		ansDiv %= mod;
	}
	//ansMul / ansDivをやりたい
	//ansDivの逆元を使って求めよう！
    ll result = ansMul * DoublingPow(ansDiv, mod - 2) % mod;
    return result;
}
 

//
ll N, M;
ll ans = 1;
int main()
{
    cin >> N >> M;

    map<ll, ll> mp = PrimeFactorize(M);
    repi(mp, itr){
        ans *= calcComb(N + itr->second - 1, N - 1);
        ans %= mod;
    }

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>

int n, m, w[105];
long long v[105];
long long dp[105][100005];
int main() {
	std::cin >> n >> m;
	for (int i = 0; i < n; ++i)
		std::cin >> w[i] >> v[i];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j <= m; ++j) {
			if (j < w[i])
				dp[i + 1][j] = dp[i][j];
			else
				dp[i + 1][j] = std::max(dp[i][j], dp[i][j - w[i]] + v[i]);
		}

	std::cout << dp[n][m] << std::endl;
	return 0;
}


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

const int maxn = 2e5 + 10;

int a[maxn], b[maxn];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
	bool flag = false;
	for (int i = 1; i <= n; i++) 
		if (a[i] != b[i]) flag = true;
	if (!flag) {
		printf("0\n");
		return 0;
	}
	
	long long A = 0, B = 2e9;
	for (int i = 1; i <= n; i++) {
		A += a[i];
		if (a[i] > b[i]) B = min(B, (long long)b[i]);
	} 
	printf("%lld\n", A - B);
	return 0; 
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main()
{
    double x1,x2,y1,y2,rslt,fRslt;
    cin>>x1>>y1>>x2>>y2;
    rslt=((x2-x1)*(x2-x1))+((y2-y1)*(y2-y1));
    fRslt=sqrt(rslt);
    printf("%0.8lf\n",fRslt);
    return 0;
}


Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <algorithm>


bool binary_search(std::vector<int>::iterator a, std::vector<int>::iterator b, int key) {
	if (std::distance(a, b) == 0)
		return false;
	std::vector<int>::iterator mid = a + std::distance(a, b) / 2;
	if (*mid == key)
		return true;
	if (*mid < key)
		return binary_search(mid+1, b, key);
	else
		return binary_search(a, mid, key);


}

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

	std::vector<int> S;
	S.resize(n, 0);
	for (int i = 0; i < n; i++) {
		std::cin >> S[i];
	}

	int q;
	std::cin >> q;
	
	std::vector<int> T;
	T.resize(q, 0);
	for (int i = 0; i < q; i++) {
		std::cin >> T[i];
	}

	int cnt = 0;
	for (int i = 0; i < q; i++) {
		if (binary_search(S.begin(), S.end(), T[i]))
			cnt++;
	}

	std::cout << cnt << std::endl;

	return 0;
}

Measured memory_bytes: 3352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, q;
  string s;
  cin >> n >> q >> s;
  vl sum(n + 1, 0);
  rep2(i, 1, n) {
    sum[i + 1] = sum[i];
    if(s[i - 1] == 'A' && s[i] == 'C') sum[i + 1]++;
  }
  rep(_, q) {
    ll l, r;
    cin >> l >> r;
    l--;
    ll ans = sum[r] - sum[l];
    if(l > 0 && sum[l + 1] > sum[l]) ans--;
    printf("%lld\n", ans);
  }
}

Measured memory_bytes: 1792
import numpy as np

N = int(input())
A = tuple(map(int, input().split()))
A = np.array(A)
A = np.sort(A)

for i in range(N):
    if (i > 0 and A[i-1] == A[i]) or (i < N-1 and A[i] == A[i+1]):
        print('NO')
        break
else:
    print('YES')

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

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

  int temp1 = A * 10 + B + C;
  int temp2 = B * 10 + A + C;
  int temp3 = C * 10 + A + B;

  cout << max({temp1, temp2, temp3}) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  string s, t;
  cin >> s;
  t = s;
  int res = 10000;
  for (int k = 0; k < (int)t.size(); k++) {
    int cnt = 0;
    while (1) {
      int i = 1;
      while (i < (int)s.size() && s[i-1] == s[i]) i++;
      if (i == (int)s.size()) break;
      for (int j = 0; j < (int)s.size()-1; j++) {
	if (s[j] == t[k]) continue;
	s[j] = s[j+1];
      }
      s.pop_back();
      cnt++;
    }
    res = min(res, cnt);
    s = t;
  }
  dump(res);
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        int ans = 0;

        int n,m;

        n = sc.nextInt();
        m = sc.nextInt();

//        int[] a = new int[n];
//        for(int i = 0;i < n;i++){
//            a[i] = sc.nextInt();
//        }
//

        System.out.println(n-m+1);
    }
}


Measured memory_bytes: 22868
from math import sqrt

N = int(input())
ans = 0
for M in range(105,N+1,1):
    if M%2==0:
        continue 
    count=0
    for i in range(1,int(sqrt(M))+2,1):
        if M % i ==0:
            if M % i == 0:
                count+=2
    if count==8:
        ans+=1
print(ans)

Measured memory_bytes: 62264
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    k = int(input())
    vp = [list(map(int, input().split())) for _ in [0]*k]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    # まず各頂点の偶奇を計算する
    parity = [-1]*n
    root = vp[0][0]-1
    p = vp[0][1] % 2
    parity[root] = p
    q = [root]
    while q:  # BFS
        p ^= 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if parity[j] == -1:
                    parity[j] = p
                    qq.append(j)
        q = qq

    # 偶奇と塗った色があっていなければ即座に終了
    for v, p in vp:
        if p % 2 != parity[v-1]:
            print("No")
            return

    # バックトラック法を行い解の範囲を探索する
    ans_range = [[-10**10, 10**10] for _ in [0]*n]
    q = [root]
    vp = {v-1: p for v, p in vp}
    M = 10**10
    m = -10**10
    g2 = [set(gg) for gg in g]
    while q:
        i = q[-1]
        if i in vp:
            if m <= vp[i] <= M:
                M = vp[i]
                m = M
                ans_range[i] = [m, M]
            else:
                print("No")
                return
        else:
            m2, M2 = ans_range[i]
            if M2 < m or M < m2:
                print("No")
                return
            m = max(m, m2)
            M = min(M, M2)
            ans_range[i] = [m, M]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
        m -= 1
        M += 1

    q = [root]
    now = vp[root]
    ans = [None]*n
    g = [set(gg) for gg in g]
    while q:
        i = q[-1]
        if ans[i] != None:
            now = ans[i]
        else:
            if ans_range[i][1] < now:
                now -= 2
            ans[i] = now
        if g[i]:
            j = g[i].pop()
            g[j].remove(i)
            q.append(j)
        else:
            q.pop()
        now += 1
    print("Yes")
    for i in ans:
        print(i)


main()


Measured memory_bytes: 125000
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,K;
    cin>>N;
    cin>>K;
    vector<int> v(N);
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    int minDistance = 0;
    for(int i=0;i<N;i++){
        minDistance += (2*min(abs(v[i]),abs(v[i]-K)));
    }
    cout<<minDistance<<endl;
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 200010;
int N,M;
int A[MC],C[MC];
int Z[MC];
int ans;

int main(){
	cin >> N >> M;
	repp(i,0,N){
		cin >> A[i];
		++C[A[i]];
	}
	repm(i,N,0){
		repp(j,0,C[i]) if(i>j) ++Z[i-j];
		if(!Z[i]) ++ans;
	}
	repp(i,0,M){
		int X,Y;
		cin >> X >> Y;
		--X;
		--C[A[X]];
		if(A[X]>C[A[X]]) if(--Z[A[X]-C[A[X]]] == 0) ++ans;
		A[X] = Y;
		if(Y>C[Y]) if(Z[Y-C[Y]]++ == 0) --ans;
		++C[Y];
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <math.h>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define mod 1000000007
#define INF 2000000000
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}



signed main() {
	int n,ans,a,b;
	cin >> n;
	cin >> a >> b;
	ans = gcd(a, b);
	rep(i, n-2) {
		cin >> a;
		ans = gcd(ans, a);
	}
	cout << ans << endl;
}



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

using namespace std;

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

	string s, t;
	cin >> s >> t;

	int ans = 0;
	for(int i = 0; i < s.size(); ++i) {
		ans += (s[i] != t[i]);
	}

	cout << ans << '\n';

	return 0;
}


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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
#define vc vector<int>

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

	vc l(n);

	int x = 0;
	rep(i, n){
		cin >> l[i];
		x = max(l[i], x);
	}

	int sum = 0;
	rep(i, n){
		sum += l[i];
	}

	if(x < sum - x){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

    return 0;
}



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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

// 素因数分解; 返り値は(素数, 乗数)のvector配列
vector<pair<ll, int>> factorize(ll n) {
	vector<pair<ll, int>> res;
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };
constexpr auto MAX = 100010;

// ──────────────────────────────────────────────────────────────────────────────

int h, w;
vs table;
int DFS(vs t, ii start) {
	queue<ii> que;
	vvb checked(h, vector<bool>(w));
	vvi depth(h, vector<int>(w));

	que.push(start);
	checked[start.first][start.second] = true;

	while (!que.empty()) {
		ii now = que.front(); que.pop();

		rep(k, 4) {
			int y = now.first + dy[k];
			int x = now.second + dx[k];

			if (0 <= x && x < w && 0 <= y && y < h 
				&& checked[y][x] == false 
				&& t[y][x] == '.') {
				checked[y][x] = true;
				que.push({ y, x });
				depth[y][x] = depth[now.first][now.second] + 1;
			}
		}
	}

	int mx = 0;
	rep(i, h) {
		rep(j, w) {
			mx = max(mx, depth[i][j]);
		}
	}
	return mx;
}

int main() {
	cin >> h >> w;
	table.resize(h);

	rep(i, h) {
		cin >> table[i];
	}

	int ans = 0;
	rep(i, h) {
		rep(j, w) {
			if (table[i][j] == '.') ans = max(ans, DFS(table, { i, j }));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

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

	int cnt = 0;
	int harf = 0;
	REP(i, 0, N) {
		int a;
		cin >> a;
		if (a % 4 == 0) cnt++;
		else if (a % 2 == 0) harf++;
	}
	harf /= 2;

	if ((cnt + harf) >= (N / 2)) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  set<int> hoge;
  int a,b,c;
  cin>>a>>b>>c;
  hoge.insert(a);
  hoge.insert(b);
  hoge.insert(c);
  cout<<hoge.size()<<endl;
}

Measured memory_bytes: 256
mod=10**9+7
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if len(a)!=len(set(a)) or len(b)!=len(set(b)):
	print(0)
	exit()

a.sort(reverse=True)
b.sort(reverse=True)
i_a=0
i_b=0
ans=1
for i in range(n*m,0,-1):
	f_a=f_b=0
	if i_a<n:
		if a[i_a]==i:
			f_a=1
			i_a+=1
	if i_b<m:
		if b[i_b]==i:
			f_b=1
			i_b+=1
	if f_a==f_b==1:
		pass
	elif f_a==1:
		ans=ans*i_b%mod
	elif f_b==1:
		ans=ans*i_a%mod
	else:
		r=n*m-i
		ans=ans*(i_a*i_b-r)%mod
print(ans)

Measured memory_bytes: 9336
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000000
#define MAX 2000005
using ll=long long;
using Graph=vector<vector<int>>;
using pp=pair<pair<int,int>,int>;

int n=1;

void update(vector<int> &tree,int a,int b,int x,int i,int left,int right){
  if(b<=left||right<=a){
    return;
  }
  if(a<=left&&right<=b){
    tree[i]=min(x,tree[i]);
    return;
  }
  update(tree,a,b,x,2*i+1,left,(left+right)/2);
  update(tree,a,b,x,2*i+2,(left+right)/2,right);
}

int get(vector<int> &tree,int i){
  i+=n-1;
  int ret=tree[i];
  while(i>0){
    i=(i-1)/2;
    ret=min(tree[i],ret);
  }
  return ret;
}

int main(){
  int N,Q;
  cin>>N>>Q;
  while(n<N){
    n<<=1;
  }
  vector<int> tree1(2*n-1,N-1),tree2(2*n-1,N-1);

  ll ans=((ll)N-2)*((ll)N-2);
  for(int i=0;i<Q;i++){
    int q,x;
    cin>>q>>x;
    x--;
    if(q==1){
      int y=get(tree1,x);
      ans-=(ll)y-1;
      update(tree2,0,y,x,0,0,n);
    }else{
      int y=get(tree2,x);
      ans-=(ll)y-1;
      update(tree1,0,y,x,0,0,n);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 7388
/*-- ILSH  --*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;

#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < ll > 
#define pii pair< ll, ll > 
#define len length 
#define fi first
#define se second
#define dt cout<<"HEre\n";
#define sz(x) (ll)x.size()
const ll inf=1e18+1e17;
const ll mod = 1e9+7;

ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}
const int N=2e5+5;
void dpsol(vii v1, vii &dp){
	dp[0]=1;
	for ( int i=0;i<sz(v1);i++){
		vii dpi(10000,0);
		for ( int j=0;j<10000;j++){
			if ( dp[j]!=0){
				dpi[j]+=dp[j];
				dpi[j+v1[i]]+=dp[j];
			}
		}
		swap( dp,dpi);
	}
}
void solve(){

	vii v1, v2;
	ll cnt=0,n,a;
	cin>>n>>a;
	for ( int i=0;i<n;i++){
		int aa;
		cin>>aa;
		if ( aa-a==0)
			cnt++;
		if ( aa-a<0)
			v2.pb( abs(aa-a));
		if ( aa-a>0)
			v1.pb( aa-a);
	}
	vii dp1(10000,0),dp2(10000,0);
	dpsol(v1,dp1);
	ll ans=(1ll<<cnt);
	dpsol(v2,dp2);
	ll tot=0;
	for ( int i=1;i<10000;i++){
		if ( dp1[i]!=0&&dp2[i]!=0)
			tot+=ans*dp1[i]*dp2[i];
	}
	tot+=ans-1;
	cout<<tot<<'\n';

}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie( NULL);
	cout.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen ("INPUT.txt" , "r" , stdin);
		freopen ("OUTPUT.txt", "w" , stdout);
	#endif
	ll t=1;
	//cin>>t;
	for ( ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
    	solve();
    }
    //	cout << clock() / double(CLOCKS_PER_SEC) << endl;
}


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

int main()
{
  int a, b;
  cin >> a >> b;
  if (a + b >= 10)
  {
    cout << "error" << endl;
  }
  else
  {
    cout << a + b << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
double a, b, x;
bool f(double d) {
	double pi = 3.141592653589793238;
	double S;
	if (a*sin(d / 180.0 * pi) > b * cos(d / 180.0 * pi)) {
		S =(b * b / tan(d / 180.0 * pi)) / 2.0;
	}
	else {
		S = a * b - a * a * tan(d / 180.0 * pi) / 2.0;
	}
	//printf("%.10f\n", x); 
	//printf("%.10f\n", S*a);

	if (x > S*a) {
		//まだちっちゃくできる
		//こぼれすぎ
		return true;
	}
	return false;
}

int main() {
	cin >> a >>b >>x;
	double l = 0.0;
	double r = 90.0;
	for (int n = 0; n < 100; ++n) {
		double x = (l + r) / 2;
		if (f(x)) {
			r = x;
		}
		else {
			l = x;
		}
	}
	printf("%.10f\n", l);
	return 0;
}

Measured memory_bytes: 4300
void main()
{
    long n = rdElem;
    long[] a = rdRow;

    long[long] cnt;
    foreach (x; a)
    {
        ++cnt[x];
    }

    long total;
    long[long] list;
    foreach (key, val; cnt)
    {
        list[key] = val * (val - 1) / 2 - (val - 1) * (val - 2) / 2;
        total += val * (val - 1) / 2;
    }

    foreach (x; a)
    {
        writeln(total - list[x]);
    }
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

Measured memory_bytes: 40336
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    tmp = 0
    for a in A:
        tmp += 1 / a
    ret = 1 / tmp
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


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

int main() {
  int X; cin >> X; // 入力値：２～１０＾５
  int Ans = 0;      // 最小の素数

  if(X==2){Ans=2;}
  else if ( X==3 || X==4 || X==5 ){Ans=5;}
  else if ( X==6 || X==7 ){Ans=7;}
  else if ( X==8 || X==9 || X==10 || X==11 ){Ans=11;}
  else {  // X が１２以上の場合、X/12 以下の数値で割り切れなければ、素数とみなす。
    int tmp_i;  // 割り算用の数値（仮
    int tmp_b;  // true:素数／false:素数で無い
    for(int i=X;i<1000000;i++){
      tmp_i = i/12;
      // i が素数か判定する。
      tmp_b = true; // 初期値は素数判定
      int tmp_M = max(13,i/12);
      for( int j=2 ; j<tmp_M ; j++){
        if(i%j==0){
          tmp_b = false;
          break;
        }
      }
      if(tmp_b){
        Ans=i;
        break;
      }
    }
  }

  cout << Ans << endl;
}


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

int main() {
  int n, m;
  cin >> n >> m;
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int a;
      cin >> a;
      mp[a]++;
    }
  }

  int ans = 0;
  for (auto p : mp) {
    if (p.second == n) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1'000'000'007;
const ll inf=1'000'000'000'000'000'00;
const int INF=1'000'000'000;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int n,x,t;
    cin>>n>>x>>t;
    cout<<(n+x-1)/x*t<<endl;
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int deg = sc.nextInt();
		double s,l,h;

		s = a * b * Math.sin(deg * Math.PI / 180) / 2;
		l = a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(deg * Math.PI / 180));
		h = b * Math.sin(deg * Math.PI / 180);

		System.out.println(s + " " + l + " " + h);
	}

}



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

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

Measured memory_bytes: 256
import scala.collection.mutable

object Main extends App {

  import scala.io.StdIn._

  val Array(n, k) = readLine.trim.split(' ').map(_.toInt)
  val heights = readLine.trim.split(' ').map(_.toInt)
  val queue = mutable.PriorityQueue()(Ordering.by[(Int, Int), Int](_._2).reverse).also{q ⇒ q.enqueue((n - 1, 0))}
  val minCost = Array.tabulate(n){_ ⇒ Int.MaxValue}.also{a ⇒ a(n - 1) = 0}
  while (queue.nonEmpty){
    val (top, cost) = queue.dequeue()
    if (minCost(top) == cost){
      for (k ← math.max(0, top - k) until top){
        if (minCost(k) > cost + math.abs(heights(top) - heights(k))) {
          minCost(k) = cost + math.abs(heights(top) - heights(k))
          queue.enqueue((k, minCost(k)))
        }
      }
    }
  }
  println(minCost(0))
  implicit class Extend[T](value: T){
    def also(func: T ⇒ Unit): T = {func(value); value}
    def let[A](func: T ⇒ A): A = func(value)
  }
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int64_t> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h.at(i);
    }
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());
    for (int i = 0; i < min(k, n); i++) {
        h.at(i) = 0;
    }
    int64_t count = 0;
    for (int i = 0; i < n; i++) {
        count += h.at(i);
    }
    cout << count << endl;
}

Measured memory_bytes: 1792
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		boolean i = true;
	
		String[] s = new String[N];
		
		for(int l = 0;l < N;l++) {
			s[l] = sc.next();
			if(s[l].equals("Y")) i = false;
		}
		sc.close();
	
		if(i) System.out.println("Three");
		else System.out.println("Four");
		
	}

}
//AtCoder089_B


Measured memory_bytes: 21844
S = list(input())
cnt_yes = 0
for i, s in enumerate(S):
    if (i+1) % 2 == 0:
        if s == 'L' or s == 'U' or s == 'D':
            cnt_yes += 1
    else:
        if s == 'R' or s == 'U' or s == 'D':
            cnt_yes += 1

if cnt_yes == len(S):
    print('Yes')
else:
    print('No')


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

int main(){

  long a,b,k;
  cin >> a >> b >> k;
  if(a<k){
  	b=max((long)0,b+a-k);
    a=0;
  }else{
  	a=a-k;
  }
  cout << a << " " << b;
  return 0;
}


Measured memory_bytes: 256