akhauriyash/Code-Regression huggingface dataset:
let solve =
    let rec sol xs =
        match xs with
        | [] -> 0
        | [_] -> 0
        | x :: y :: zs -> min x y + sol zs
    in List.sort >> sol

let () =
    let _ = stdin.ReadLine()
    let xs = stdin.ReadLine().Split(' ') |> Array.map int |> List.ofArray
    in solve xs |> printfn "%d"


Measured memory_bytes: 4944
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var x = int.Parse(line[0]);
            var y = int.Parse(line[1]);
            var b = int.Parse(line[2]);
            var p = int.Parse(line[3]);
            var wari = (x * b + y * p) * 0.8;
            int pay;
            if (b >= 5 && p >= 2) { pay = (int)wari;  Console.WriteLine(pay);   continue; }
            var norm = x * b + y * p;
            var bminus = (x * 5 + y * p) * 0.8;
            var pminus = (x * b + y * 2) * 0.8;
            if (b >= 5 && p < 2) pay = (int)Math.Min(norm, pminus);
            else if (b < 5 && p >= 2) pay = (int)Math.Min(norm, bminus);
            else pay = norm;
            Console.WriteLine(pay);
        }
    }
}

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

int n;
int a[3005];
long long dp[3005][3005];
const long long MN = 1e15;
long long f(int l, int r, bool turn){
	if (l == r) return turn ? a[l] : -a[l];
	long long &ret = dp[l][r];
	if (ret != -MN) return ret;
	if (turn){
		ret = max(ret, f(l+1, r, turn^1) + a[l]);
		ret = max(ret, f(l, r-1, turn^1) + a[r]);
	} else {
		ret = MN;
		ret = min(ret, f(l+1, r, turn^1) - a[l]);
		ret = min(ret, f(l, r-1, turn^1) - a[r]);
	}
	//cout << l << ' ' << r << " : " << turn << " _ " << ret << '\n';
	return ret;
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
		dp[i][j] = -MN;
	cout << f(1, n, 1) << '\n';
	return 0;
}


Measured memory_bytes: 70784
#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;



int main() {
    int n=read(), m=read(), k=read();
    if(n<m) swap(n,m);
    printf("%d\n", (k-1)/n+1);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<cmath>
#include<stack>
#include <algorithm>
#include <functional>
//#include<stdlib.h>
using namespace std;
int main() {
	int n, m,ap=0,bp=0;
	long long int q = 0;
	cin >> n >> m;
	vector<int>a(n+1);
	vector<vector<long long int>>b(m+1, vector<long long int>(2, 0)); //[n][2]
	vector<long long int>c(m+1);
	for (int t = 0; t < n; t++) { cin >> a[t]; }
	for (int t = 0; t < m; t++) 
	{
		cin >> b[t][0] >> b[t][1];
		c[t] = (b[t][1] << 17) + b[t][0]; 
	}//枚、数
	std::sort(a.begin(), a.end(), std::greater<int>());
	std::sort(c.begin(), c.end(), std::greater<long long int>());
	for (int t = 0; t < m; t++) 
	{
		b[t][0] = (c[t] & 131071);
		b[t][1] = (c[t] >> 17);
	}
	for (int t = 0; t < n;)
	{
		if (b[bp][1] > a[ap])
		{
			if (n - t  < b[bp][0]) { b[bp][0] = n - t ; }
			q += b[bp][1] * b[bp][0];
			t += b[bp][0];
			bp++;
		}
		else 
		{
			q += a[ap];
			t++; ap++;
		}
	}
	cout << q;
	return 0;
}

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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;





int main() {
	
	ll n, m;
	cin >> n >> m;

	VLL x(m);

	REP(i, m)cin >> x[i];

	sort(ALL(x));

	ll left = 0, right = m - 1;

	if (n >= m) {
		cout << 0 << endl;
		return 0;
	}
	if (n == 1) {
		cout << x[m - 1] - x[0] << endl;
		return 0;
	}
	
	VI a(m - 1);
	REP(i, m - 1)a[i] = x[i + 1] - x[i];

	ll ans = 0;

	sort(ALL(a));

	REP(i, m - 1 - n + 1)ans += a[i];

	cout << ans << endl;


}


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

int main() {
	string N;
	cin >> N;
	long long sum = 0;
	for (char n : N) {
		sum += static_cast<long long>(n - '0');
	}
	if (sum % 9 == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

}

Measured memory_bytes: 3708
#include <bits/stdc++.h>
#define N 301
using namespace std;


int n, a, b, c, x;
double dp[N][N][N];


double f(int a, int b, int c) {
	if (a==0 && b==0 && c==0) return 0;
	if (a<0 || b<0 || c<0) return 0;
	if (dp[a][b][c]!=0) return dp[a][b][c];
	double ea, eb, ec, ans;
	ea = f(a-1,b,c);
	eb = f(a+1,b-1,c);
	ec = f(a,b+1,c-1);
	ans = (a*ea+b*eb+c*ec+n)/(a+b+c);
	//printf("(%d %d %d) -> %.2lf\n",a,b,c,ans);
	return dp[a][b][c]=ans;
}


int main() {
	cin>>n;
	for (int i=0; i<n; i++) {
		cin>>x;
		if (x==1) a++;
		if (x==2) b++;
		if (x==3) c++;
	}
	printf("%.20lf\n",f(a,b,c));
	return 0;
}

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

int main(){
        long long t, n, k, i;
        cin >> t;
        for (int j = 0; j < t; j++){
                long long ans = 0;
                cin >> n >> k;
                vector<long long> a(n);
                vector<long long> b;
                for (i = 0; i < n; i++) cin >> a[i];
                for (i = 0; i < n - 1; i++) b.push_back(a[i + 1] - a[i]);
                sort(b.begin(), b.end());
                for (i = 0; i < n - k; i++) ans += b[i];
                cout << ans << endl;
        }
        return 0;
}


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

using namespace std;

int main()
{
    int A, B;
    int n;

    cin >> A >> B;

    n = 1;
    while(true){
        if(A + (A-1) * (n-1) >= B) break;
        ++n; 
    }

    if(B == 1) n = 0;

    cout << n << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define val(cx, cy) cx>=0 && cx<h && cy>=0 && cy<w && grid[xx][yy]=='.'
using namespace std;
int h,w,k;

inline int ce(int a, int b) {
	if (a%b==0) return a/b;
	else return a/b+1;
}

int main() {
	scanf("%d%d%d", &h, &w, &k);
	char grid[h][w+5];
	int dist[805][805];
	memset(dist,-1,sizeof(dist));
	for (int i=0; i<h; i++) {
		scanf("%s", grid[i]);
	}
	
	int sx, sy;
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			if (grid[i][j]=='S') {
				sx=i; sy=j;
				break;
			}
		}
	}
	
	int x[4]={1,0,-1,0};
	int y[4]={0,1,0,-1};
	dist[sx][sy]=0;
	queue<pair<int, int> > q;
	q.push({sx,sy});
	while (!q.empty()) {
		int px=q.front().first, py=q.front().second;
		q.pop();
		for (int i=0; i<4; i++) {
			int xx=px+x[i], yy=py+y[i];
			if (val(xx,yy) && (dist[xx][yy]==-1 || dist[px][py]+1<dist[xx][yy])) {
				dist[xx][yy]=dist[px][py]+1;
				q.push({xx,yy});
			}
		}
	}
	int ans=INT_MAX;
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			//printf("%d ", dist[i][j]);
			if (dist[i][j]!=-1 && dist[i][j]<=k) {
				ans=min(ans,ce(i,k));
				ans=min(ans,ce(h-i-1,k));
				ans=min(ans,ce(j,k));
				ans=min(ans,ce(w-j-1,k));
			}
		}
		//printf("\n");
	}
	printf("%d\n", ans+1);
}


Measured memory_bytes: 3456
A = list(map(int, input().split()))
A.sort()
ans = 0
count = [0, 0]
for a in A:
    if a & 1:
        count[1] += 1
    else:
        count[0] += 1
if (count[0] == 0)or(count[1] == 0):
    m = A[2]
    ans += (3*m-sum(A))
    ans //= 2
else:
    if (A[1]-A[0]) & 1:
        m = A[2]+1
        ans += (3*m-sum(A))
        ans //= 2
    else:
        m = A[2]
        ans += (3*m-sum(A))
        ans //= 2
print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
int main(void)
{
  int a,b,c;
  int i;
  int count;
  
  scanf("%d",&a);
  scanf("%d",&b);
  printf("\n");
  for(i=0;i<a;i++){
    scanf("%d",&c);
    if(c>=b){
      count+=1;
    }
  }
    printf("%d\n",count);
   
  return 0;
}

Measured memory_bytes: 128
program collatz_problem
  implicit none
  integer :: s, u(1000000) = -1, i = 1
  read(*,*) s
  u(s) = 1
  do
    i = i+1
    s = merge(s/2,3*s+1,mod(s,2) == 0)
    if (u(s) > 0) exit
    u(s) = i
  end do
  write(*,'(i0)') i
end program collatz_problem

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
LL n;
LL p[111];
LL q[111];
LL r[111];
LL b[111];
LL m[111];

LL GCD(LL x,LL y){
  if(x < y) x^=y^=x^=y;
  LL r = x % y;
  if(r) return GCD(y,r);
  else return y;
}

LL solve(int k){
  if(k == 0) return 1;
  if(m[k]) return m[k];
  LL rm = solve(r[k]) * p[k];
  LL bm = solve(b[k]) * q[k];
  LL l = rm * bm / GCD(rm,bm);
  //cout << "k = " << k << " : " << l/p[k] << " + " << l/q[k] << endl;
  return m[k] = l/p[k] + l/q[k];
}

int main(void){
  while(cin >> n && n){
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    memset(r,0,sizeof(r));
    memset(b,0,sizeof(b));
    memset(m,0,sizeof(m));
    for(int i = 1; i <= n; i++){
      cin >> p[i] >> q[i] >> r[i] >> b[i];
      LL g = GCD(p[i],q[i]);
      p[i] /= g;
      q[i] /= g;
    }
    LL res = 0;
    for(int i = 1; i <= n; i++){
      res = max(res,solve(i));
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    
    int count = 0;
    for (int i = 1; i < n; i++)
    {
        count += (n - 1) / i;
    }

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

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

a = [0  for i in range(n)]
b = [0  for i in range(n)]
x = [[0,0,0]  for i in range(n)]

for i in range(n):
    a[i],b[i]=map(int,input().split())
    x[i][0]=abs(a[i]+b[i])
    x[i][1]=a[i]
    x[i][2]=b[i]

s=sorted(x,reverse=True)
#print(s)

nu=n//2
mod=n%2

count=0
for i in range(nu):
    count+=s[i*2][1]
  #  print(count)
    count-=s[i*2+1][2]
 #   print(count)

if mod==1:
    count+=s[2*nu][1]

    

    

print(count)

Measured memory_bytes: 25580
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<pair<ll, ll>> ab{};

    for (auto &&i: irange(0LL, N)){
        ll a, b;
        cin >> a >> b;
        ab.emplace_back(make_pair(a, b));
    }
    sort(ab.begin(), ab.end(), [](pair<ll, ll> p1, pair<ll, ll> p2){return p1.first < p2.first;});
    ll ind{0};
    for (auto &&i: irange(0LL, N)){
        ind += ab.at(i).second;
        if (ind >= K){
            cout << ab.at(i).first << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 2420
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
using namespace std;


int main() {

	long long N;
	cin >> N;

	vector<long long> p(N, 0);
	for (long long i = 0; i < N; i++) {
		cin >> p[i];
		p[i] -= 1;
	}

	long long ans = 0;
	for (long long i = 0; i < N; i++) {
		if (i == p[i]) {
			ans += 1;
			i++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4000
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int h, w;
	cin >> h >> w;
	char s[51][51];
	int whitenum = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> s[i][j];
			if(s[i][j] == '.') whitenum++;
		}
	}
	queue<pair<int, int> > qu;
	vector<vector<int> > stepnum(51, vector<int>(51, -1));
	stepnum[0][0] = 1;
	qu.push(make_pair(0, 0));
	int dx[4] = {1, 0, -1, 0};
	int dy[4] = {0, 1, 0, -1};
	while(!qu.empty()){
		int x = (qu.front()).first;
		int y = (qu.front()).second;
		qu.pop();
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= h || ny >= w || s[nx][ny] == '#' || stepnum[nx][ny] >= 0) continue;
			stepnum[nx][ny] = stepnum[x][y] + 1;
			qu.push(make_pair(nx, ny));
		}
	}
	if(stepnum[h -  1][w - 1] >= 0) cout << whitenum - stepnum[h - 1][w - 1] << endl;
	else cout << -1 << endl;
}

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

typedef long long ll;
#define mod 1000000007
#define pb push_back
#define mk make_pair
#define test cout<<"#"
#define INF 1e9+5
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, w;
	cin>>n>>w;
	vector<ll> s(n);
	vector<ll> val(n);
	for(ll x = 0; x < n; x++)
		cin>>s[x]>>val[x];
	vector<ll> ans(w+1);
	for(ll x = 0; x < n; x++)
	{
		for(ll y = w; y>=1; y--)
		{
			if(s[x]<=y)
			{
				ans[y] = max(ans[y], ans[y-s[x]]+val[x]);
			}
		}
	}
	cout<<ans[w]<<"\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const long long mod = (long long)1e9 + 7;
long long inved(long long a){
    long long x = 1, y = 0, u = 0, v = 0, k = a, l = mod;
    long long tmp1, tmp2, tmp3;
    while (l != 0){
        tmp1 = x, tmp2 = y;
        x = u, y = v;
        u = tmp1 - u * (k / l), v = tmp2 - v * (k / l);
        tmp3 = k;
        k = l;
        l = tmp3 % l;
    }
    return (x + mod) % mod;
}
long long fact[20000010];
long long invf[20000010];
long long comb(int n, int k){
  long long tmp = (fact[n] * invf[k]) % mod;
  tmp *= invf[n-k];
  tmp %= mod;
  return tmp;
}
const int maxf = 20000003;
int main(){
  long long H, W, K;
  cin >> H >> W >> K;
  fact[0] = 1;
  for (int i=0;i<maxf;i++){
    fact[i+1] = fact[i] * (i+1) % mod;
  }
  invf[maxf] = inved(fact[maxf]);
  for (int i=maxf;i>0;i--){
    invf[i-1] = invf[i] * i % mod;
  }
  long long tmp1 = (((K+1)*(K+2)%mod)*(2*K+3*(1-H+mod))%mod)*inved(6)%mod;
  tmp1 += (H-1+K*(W+1))%mod;
  tmp1 %= mod;
  long long S = tmp1 * comb((int)H+W-2, (int)H-1) % mod;
  if (H >= 2){
    tmp1 = (((W+1)*((K*(K+3))%mod))%mod)*inved(2)%mod;
    S += tmp1 * comb((int)H+W-2, (int)H-2) % mod;
    S %= mod;
  }
  if (W >= 2){
    tmp1 = (K*(K+3+2*(mod-H))%mod)*inved(2)%mod;
    S += tmp1 * comb((int)H+W-2, (int)H) % mod;
    S %= mod;
  }
  S *= fact[(int)H] * fact[(int)W] % mod;
  S %= mod;
  S *= invf[(int)H+W-K];
  S %= mod;
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 316116
import scala.io.StdIn

import scala.annotation.tailrec

object Main extends App {
  val n = StdIn.readInt

  @tailrec
  def rec(acc:Int,num:Int):Int = {
    if((num&1) == 1) acc
    else {
      rec(acc+1,num>>1)
    }
  }
  val ans = (1 to n)./:(1,0)((max,i) => {
    val cnt = rec(0,i)
    if(max._2 < cnt) (i,cnt) else max
  })._1
  println(ans)
}

Measured memory_bytes: 27456
module IntSet = Set.Make (struct 
  type t = int
  let compare = compare
end)

let rec dfs succ unvisited v =
  let unvisited' = IntSet.remove v unvisited in
  if IntSet.is_empty unvisited' then 1
  else
    List.map (fun v' ->
      if IntSet.mem v' unvisited' then dfs succ unvisited' v'
      else 0) (succ v)
    |> List.fold_left ( + ) 0

let () = Scanf.scanf "%d %d\n" (fun n m ->
  let succ = Array.make n []
  in
  ignore (Array.init m (fun _ ->
    Scanf.scanf "%d %d\n" (fun a b ->
      succ.(a - 1) <- b - 1 :: succ.(a - 1);
      succ.(b - 1) <- a - 1 :: succ.(b - 1))));
  Printf.printf "%d\n" (dfs
    (fun i -> succ.(i))
    (Array.init n (fun i -> i)
      |> Array.fold_left (fun s i -> IntSet.add i s) IntSet.empty) 0))


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

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

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }

void compute() {

}

int bf(ll N) {
  int maxi = 0;
  rep(i,N+1) {
    maxi = max(maxi,__builtin_popcount(i));
  }
  return maxi;
}

int main() {
  ll n;
  cin >> n;
  //for(n=1;n<=1000;++n) {
    for(int i=60;i>=0;--i) {
      if( (n>>i) & 1 ) {
	int ans = max(i,__builtin_popcount(n));
	cout << ans << endl;
	//cout << bf(n) << endl;
	//assert( ans == bf(n));
	break;
      }
    }
    //}
  compute();
  return 0;
}



Measured memory_bytes: 3080
using System;
using System.Collections.Generic;
using System.Linq;

namespace Hanafuda_Shuffle
{
    class Program
    {
        static void Main(string[] args)
        {
            while(true)
            {
                string[] s = Console.ReadLine().Split(' ');
                if (s.Contains("0")) break;
                int n = int.Parse(s[0]);
                int r = int.Parse(s[1]);
                List<int> yama = Enumerable.Range(1, n).Reverse().ToList();
                for (int i = 0; i < r; i++)
                {
                    string[] m = Console.ReadLine().Split(' ');
                    int p = int.Parse(m[0]);
                    int c = int.Parse(m[1]);
                    List<int> cut = yama.GetRange(p - 1, c);
                    yama.RemoveRange(p - 1, c);
                    yama = cut.Concat(yama).ToList();
                }
                Console.WriteLine("{0}", yama[0]);
            }
        }
    }
}

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

int main()
{
  int64_t n, k, ans = 0;
  cin >> n >> k;
  if (abs(n - k) >= n)
    ans = n;
  else
  {
    if (n % k == 0)
      ans = 0;
    else
    {
      n = n % k;
      ans = min(n, abs(n - k));
    }
  }
  cout << ans << "\n";
}


Measured memory_bytes: 256
class LargestSquare():
    def __init__(self, map):
        self.max_width = 0
        self.map = []
        self.dp = []
        for r in map:
            self.dp.append([int((x==0)) for x in r])
            self.map.append(r[:])
            if 0 in r:
                self.max_width = 1

    def find(self):
        for row in range(1, len(self.dp)):
            for col in range(1, len(self.dp[0])):
                if self.map[row][col] == 1:
                    self.dp[row][col] = 0
                else:
                    self.dp[row][col] = min(self.dp[row-1][col-1], min(self.dp[row-1][col], self.dp[row][col-1])) + 1
                    self.max_width = max(self.max_width, self.dp[row][col])
        return self.max_width * self.max_width



if __name__ == '__main__':
    # ??????????????\???
    # f = open('input.txt')
    #height, width = [int(x) for x in f.readline().strip().split(' ')]
    height, width = [int(x) for x in input().strip().split(' ')]

    map = []
    for _ in range(height):
        # map.append([int(x) for x in f.readline().strip().split(' ')])
        map.append([int(x) for x in input().strip().split(' ')])


    # ???????????????
    S = LargestSquare(map)
    result = S.find()

    # ???????????¨???
    print(result)

Measured memory_bytes: 69956
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	X, Y = getlist()
	ans = 0
	if X == 1:
		ans += 300000
	elif X == 2:
		ans += 200000
	elif X == 3:
		ans += 100000
	if Y == 1:
		ans += 300000
	elif Y == 2:
		ans += 200000
	elif Y == 3:
		ans += 100000
	if X == 1 and Y == 1:
		ans += 400000
	print(ans)
	
if __name__ == '__main__':
	main()

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

int main() {
	long long n,m;
	cin >> n >> m;
	vector <pair<long long,long long>> p;
	for (int i=0; i<n; i++){
		int a,b;
		cin >> a >> b;
		p.push_back(make_pair(a,b));
	}
	sort(p.begin(),p.end());
	long long ans=0;
	int ind=0;
	while (m>0){
		long long a=p[ind].first;
		long long b=p[ind].second;
		if (m>=b){
			m-=b;
			ans+=a*b;
		}
		else{
			ans+=m*a;
			m=0;
		}
		ind++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
const ll mod=1000000007;
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

int main() {
  int n; cin >>n;
  string s;cin >> s;
  string prev="";
  int cnt = 1;
  for(int i=0; i<n;++i){
    auto sub = s.substr(i,1);
    if(sub!=prev && prev!="") ++cnt;
    prev = sub;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=998244353;
const ll inf=0x3f3f3f3f;
using namespace std;
ll inv[200010];
ll ksm(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) ans=ans*a%mod;
    return ans;
}
ll C(ll a,ll b)
{
    return (inv[a]*ksm(inv[b],mod-2)%mod)*ksm(inv[a-b],mod-2)%mod;
}
int main()
{

    inv[1]=1;inv[0]=1;
    for(int i=2;i<=200005;i++) inv[i]=inv[i-1]*i%mod;
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    ll p=ksm(m-1,n-1-k);

    for(int i=k;i>=0;i--)
    {
        ans=(ans+C(n-1,i)*m%mod*p%mod)%mod;
        p=p*(m-1)%mod;
    }
//    for(int i=n-1;i>=max(0ll,n-k-1);i--)
//    {
//        ans=(ans+(C(n-1,i)*ksm(m,1)%mod)*ksm(m-1,i))%mod;
//    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5188
from collections import Counter
N = int(input())
r = [input() for _ in range(N)]
r1 = Counter(r)
M = int(input())
b = [input() for _ in range(M)]
b1= Counter(b)
#print(r1)
#print(b1)
ans = 0
for i in r1.keys():
  if i in b1:
    ans = max(ans,r1[i]-b1[i])
  else:
    ans = max(ans,r1[i])
print(ans)

Measured memory_bytes: 3316
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] mins = new int[n];
        int[] maxs = new int[n];
        int[] minBucket = new int[n+1];
        int[] maxBucket = new int[n];
        
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            int sPos = str.indexOf(' ');
            mins[i] = Integer.parseInt(str.substring(0, sPos)) - 2;
            maxs[i] = Integer.parseInt(str.substring(sPos + 1)) - 2;
            
            minBucket[Math.min(mins[i], n)]++;
            maxBucket[Math.min(maxs[i], n-1)]++;
        }
        int maxmin = 0;
        int curPeep = 0;
        for (int i = n; i > 0; i--) {
            curPeep += maxBucket[i-1] - minBucket[i];
            if (i <= curPeep) {
                maxmin = i;
                break;
            }
        }
        
        System.out.println(maxmin);
        
    }

}

Measured memory_bytes: 0
#include<stdio.h>

int main(void)
{
	int a[3];
	int Goukei;
	char Kekka;
	while(1)
	{
		Goukei = 0;
		scanf("%d %d %d", &a[0], &a[1], &a[2]);
		if (a[0] == -1 && a[1] == -1 && a[2] == -1)
		{
			break;
		}
		Goukei = a[0] + a[1];
		if (a[0] == -1 || a[1] == -1)
		{
			Kekka = 'F';
		}
		else if (Goukei >= 80)
		{
			Kekka = 'A';
		}
		else if (80 > Goukei && Goukei >= 65)
		{
			Kekka = 'B';
		}
		else if (65 > Goukei && Goukei >= 50)
		{
			Kekka = 'C';
		}
		else if (50 > Goukei && Goukei >= 30)
		{
			if (a[2] >= 50)
			{
				Kekka = 'C';
			}
			else
			{
				Kekka = 'D';
			}
		}
		else if (30 > Goukei)
		{
			Kekka = 'F';
		}
		printf("%C\n", Kekka);
	}
}


Measured memory_bytes: 2100
#include <stdio.h>

int
main(void)
{
	int i, h, w;
	char str[301];

	for (;;) {
		scanf("%d %d", &h, &w);

		if (h == 0 && w == 0)
			break;

		for (i = 0; i < w; i++)
			str[i] = '#';
		str[i] = '\0';

		for (i = 0; i < h; i++)
			puts(str);

		printf("\n");

	}

	return 0;
}



Measured memory_bytes: 2036
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;



int main() {
  ll a, b, c, d; cin >> a >> b >> c >> d;
  ll ans = a * c;
  ans = max(ans,a*d);
  ans = max(ans,b*c);
  ans = max(ans,b*d);
  cout << ans << endl;
  

	return 0;
}



Measured memory_bytes: 3632
import sys
input = sys.stdin.readline

N = int(input())
cx = [i for i in range(101)]
cy = [i for i in range(101)]
x = []
y = []
h = []
flag = True
index = 0
for i in range(N):
    xi,yi,hi = map(int,input().split())
    x.append(xi)
    y.append(yi)
    h.append(hi)
    if hi != 0 and flag:
        index = i
answer = []
for cx in range(101):
    for cy in range(101):
        H = h[index]+abs(x[index]-cx)+abs(y[index]-cy)
        for i in range(N):
            if h[i] == max(H-abs(x[i]-cx)-abs(y[i]-cy),0):
                if i == N-1:
                    answer = [cx,cy,H]
                continue
            else:
                break

print(str(answer[0])+' '+str(answer[1])+' '+str(answer[2]))



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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
#define mp make_pair


int main() {
  int n;
  cin >> n;
  vl a(n);
  rep (i, n) {
    cin >> a[i];
  }
  sort(all(a));
  ll res = 0;
  rep (aaa, 2) {
    int idx = (n - 1) / 2;
    ll l = a[(n - 1) / 2];
    int i0 = 0, i1 = n - 1;
    ll ans = 0;
    while (i0 < i1) {
      if (i1 == idx) {
        break;
      }
      ans += abs(l - a[i1]);
      l = a[i1];
      i1--;
      if (i0 == idx) {
        break;
      }
      ans += abs(l - a[i0]);
      l = a[i0];
      i0++;
      
    }
    reverse(all(a));
    chmax(res, ans);
  }
  cout << res << endl;
}
  


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int a, b, c;
    cin >> a >> b >> c;
    for (int i = 1; i <= b; ++i) {
        if (a * i % b == c) {
            puts("YES");
            return 0;
        }
    }
    puts("NO");
}


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

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

s = sum(P[:K])
m = s

for i, p in enumerate(P[K:]):
    s = s + p - P[i]
    m = max(m, s)


print('{:.9f}'.format((m+K)/2))

    



Measured memory_bytes: 25060
h,w,k = list(map(int,input().split()))
list1 = [[str(c) for c in input()] for j in range(h)]

count1 = 0
for i in range(1<<h):
    for j in range(1<<w):
        count = 0
        for ia in range(h):
            if i&(1<<ia):continue
            for ib in range(w):
                if j&(1<<ib):continue
                if list1[ia][ib] == '#':
                    count += 1
        if count == k:
            count1 += 1


print(count1)

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

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

	int W, H;
	int N;
	cin >> W >> H >> N;
	int x[110], y[110];
	int a[110];
	int r = W, l = 0, u = H, d = 0;
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> a[i];
		if (a[i] == 1) {
			l=max(l, x[i]);
		}
		else if (a[i] == 2) {
			r = min(r, x[i]);
		}
		else if (a[i] == 3) {
			d = max(d, y[i]);
		}
		else {
			u = min(u, y[i]);
		}
	}
	if (u <= d || l >= r) {
		cout << 0;
	}
	else cout << (r - l) * (u - d);
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

M = sum(A)
mid = M // 2

t = 0
for i in range(N):
  t += A[i]
  if t >= mid:
    l = t - A[i]
    r = t
    break

ans = abs((M - r) - r)
ans = min(ans, abs((M - l) - l))

print(ans)

Measured memory_bytes: 89040
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
if sorted(a)[n&1:] == sorted([*range(1 + n % 2, n, 2)] * 2):
    print(pow(2, n // 2, 10**9 + 7))
else:
    print(0)


Measured memory_bytes: 19988
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)n;i++)
#define REP1(j,n) for(int j=0;j<(int)n;j++)
#define REPD(i,n) for(int i=n;i>=0;i--)
#define REPD1(j,n) for(int j=n;j=>0;j--)
#define REPS(i,n) for(int i=1;i<=(int)n;i++)
#define REPS1(j,n) for(int j=1;j<=(int)n;j++)
#define rep(i,a,n) for(int i=a;i<=(int)n;i++)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b)cout << c << endl;
	else if (a == c) cout << b << endl;
	else cout << a << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef pair<long long , long long> p;

long long calc(p a,p b){
	return abs(a.first-b.first)+abs(a.second-b.second);
}

int main(void){
	int n,m; cin >> n >> m;
	vector <p> student;
	vector <p> checkpoint;
	for(int i=0; i<n; i++){
		p coor;
		cin >> coor.first >> coor.second;
		student.push_back(coor);
	} 

	for(int i=0; i<m; i++){
		p coor;
		cin >> coor.first >> coor.second;
		checkpoint.push_back(coor);
	} 

	for(int i=0; i<n; i++){
		int res=1;
		long long d=1e8*4;
		for(int j=0; j<m; j++){
			long long man = calc(student[i],checkpoint[j]);
			if(d>man){
				d=man;
				res = j+1;
			}
			
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>

int main() {
	// 入力
	int n, m;
	std::cin >> n >> m;
	std::vector<std::vector<int>> vec(n);
	std::vector<int> d(n, -1);
	std::stack<int>  s;

	for (int i = 0; i < m; i++) {
		int a, b;
		std::cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	// 連結成分分解
	for (int i = 0; i < n; i++) {
		if (d[i] != -1) continue;
		if (vec[i].size() == 0) continue;
		s.push(i);
		while(!s.empty()){
			int x = s.top();
			s.pop();
			for (int j = 0; j < vec[x].size(); j++) {
				if (d[vec[x][j]] == -1) {
					d[vec[x][j]] = i;
					s.push(vec[x][j]);
				}
			}
		}
	}

	int q;
	std::cin >> q;
	while (q--) {
		int a, b;
		std::cin >> a >> b;
		if (d[a] != -1 && d[b] != -1 && d[a] == d[b]) {
			std::cout << "yes" << std::endl;
		}
		else {
			std::cout << "no" << std::endl;
		}
	}
}


Measured memory_bytes: 8592
N = int(input())
A = list(map(int,input().split()))

S = [0]*N
i = 0

while i != N-1 and i == 0 and i < N-1:
    for j in range(i+1,N):
        if A[i] >= A[j]:
            S[j] = A[i] - A[j]
        else:
            i = j
            continue
    i = j

print(sum(S))

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

int main(void){
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for (int i = 0; i < N; i++) cin >> w[i] >> v[i];
    vector<vector<long long>> dp(N+1, vector<long long>(100001, 100000000001));
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= 100000; j++) {
            if (dp[i][j] != 100000000001) {
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
                dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j]+w[i]);
            }
        }
    }
    for (int i = 100000; i >= 0; i--) {
        if (dp[N][i] <= W) {
            cout << i << endl;
            break;
        }
    }
}


Measured memory_bytes: 83204
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

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


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7

n, m, x = map(int, input().split())
prices = []
mat = []
for _ in range(n):
    nums = read_n_item()
    prices.append(nums[0])
    mat.append(nums[1:])


def check(nums):
    for num in nums:
        if num < x:
            return False
    return True


def dfs(cur, pos, price, min_price):
    if check(cur):
        min_price = min(price, min_price)
        return min_price
    if pos == n:
        return min_price

    min_price = min(dfs(cur, pos+1, price, min_price), min_price)

    nxt = [0] * len(cur)
    for i in range(len(cur)):
        nxt[i] = cur[i] + mat[pos][i]
    min_price = min(min_price, dfs(nxt, pos+1, price+prices[pos], min_price))
    return min_price

min_price = dfs([0]*m, 0, 0, float('inf'))

if min_price == float('inf'):
    print(-1)
else:
    print(min_price)


Measured memory_bytes: 10316
#include<iostream>
#include<string>
using namespace std;
int main(){
    string w;
    while(cin>>w){
        if(w=="-") break;
        int m,h;
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>h;
            w=w.substr(h)+w.substr(0,h);
        }
        cout<<w<<endl;
    }
    return 0;
}


Measured memory_bytes: 3216
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

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

    vector <int> a(N);
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        cin >> a[i];

        if ((i%2 == 0) && a[i]%2) {
            ++ans;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3624
K = 32
P = 998244353
pa = (1 << 30) - ((1 << 30) % P)
M = []
N, S = map(int, input().split())
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = 1 << K * S
mmm = (1 << K) - 1
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += mm
    s += s >> a * K
    s -= ((s & m) >> 30) * pa
    ans += s & mmm

print(ans % P)

Measured memory_bytes: 3316
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
typedef unsigned int ui;
ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x%mod;
		x = x * x%mod;
		n >>= 1;
	}
	return res;
}
int main() {
	ll n; ll i;
	cin >> n;
	ll t = (n - 2) / 2;
	ll pm[1000001]; pm[0] = (ll)1;
	for (i = 1; i < 1000001; i++) {
		pm[i] = pm[i - 1] * i % MOD;
	}
	ll inv[1000001]; inv[0] = 1;
	for (i = 1; i < 1000001; i++) {
		inv[i] = mod_pow(pm[i], MOD - 2, MOD);
	}
	ll csum[1000001];
	ll sum = 0;
	for (i = t; i >= 0; i--) {
		csum[t - i] = (pm[n - 1 - i] * pm[n - 2 - i] % MOD)*inv[n - 2 - 2 * i] % MOD;
		if (i == t) {
			sum = sum+(csum[t - i] * (n - 1 - i) % MOD)%MOD;
		}
		else {
			sum = (sum+((csum[t- i] - csum[t - 1 - i] + MOD) % MOD)*(n - i - 1) % MOD)%MOD;
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 21760
#include <stdio.h>

int main(void){
  int H, W;
  scanf("%d%d", &H, &W);

  char a[H][W+1];
  for (int i = 0; i < H; i++) {
    scanf("%s", a[i]);
  }

  int s[H][W];
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if(a[i][j] == '#') s[i][j] = 1;
      else s[i][j] = 0;
    }
  }
  s[0][0] = 0;

  int i = 0, j = 0;
  while(1){
    if(j+1 < W && s[i][j+1] == 1){
      s[i][j+1] = 0;
      j++;
      continue;
    }
    if(i+1 < H && s[i+1][j] == 1){
      s[i+1][j] = 0;
      i++;
      continue;
    }
    break;
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if(s[i][j] == 1){
        printf("Impossible\n");
        return 0;
      }
    }
  }

  printf("Possible\n");

  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(){
int a[1001],b[1001],c,d,i,j;
double x,y,z,w=0;
scanf("%d %d\n",&c,&d);
for(i=0;i<c;i++){
scanf("%d %d\n",&a[i],&b[i]);
}
for(i=0;i<c;i++){
x=a[i],y=b[i];
z=y/x;
if(w<z){
w=z;
}
}
printf("%lf\n",d*w);
return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;




int main()
{
    map<ll,ll> g;
    int N;
    cin >> N;
    const ll mod = 998244353;
    vector<ll> D(N);
    rep(i,N) cin >> D[i];

    rep(i,N) g[D[i]]++;
    
    
    
    if(D[0] != 0 || g[0] != 1){
        cout << 0 << endl;
        return 0;
    }
    
    ll ans = 1;
    for (auto p : g) {
        auto a = p.first;
        auto b = p.second;
        b %= mod;
        if(a == 0) continue;
        for (ll i = 0; i < b; i++) {
            ans *= g[a-1];
            ans %= mod;
        }
        
        //cout << p.first << " -> " << p.second << endl;
    }
    
    

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



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

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
using vvl = vector<vl>;
using pll = pair<ll,ll>;
using vb = vector<bool>;

const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;

#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define xx first
#define yy second

#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define FORD(i,a,b) for (int i=int(b)-1; i>=(a); i--)

#define rv(type,name,count) vector<type> name(count); FOR(_i,0,count) cin >> name[_i];
#define grid(type,name,c1,c2) vector<vector<type>> name(c1, vector<type>(c2)); FOR(_i,0,c1)FOR(_j,0,c2)cin >> name[_i][_j];

int main() {
	string s, t;
	cin >> s >> t;
	ll cur = -1;
	ll total = 0;
	vvl v(26);
	FOR(i,0,2*sz(s)) {
		v[s[i%sz(s)]-'a'].pb(i);
	}
	for(char c : t) {
		auto it = upper_bound(all(v[c-'a']), cur);
		if (it == v[c-'a'].end()) {
			cout << -1 << endl;
			return 0;
		}
		total += *it - cur;
		cur = *it % sz(s);
	}
	cout << total << endl;
}


Measured memory_bytes: 2800
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    AB = [(a,b) for (a,b) in zip(A,B)]
    AB = sorted(AB, key=lambda ab: ab[0])
    val = 0
    for (a,b) in AB:
        if M == 0:
            break
        if M >= b:
            val += a * b
            M -= b
        else:
            val += a * M
            M = 0
    print(val)
    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
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 20576
import java.util.*;
import java.io.*;

public class Main {

    static void impossible(){
        System.out.println("NO");
        System.exit(0);
    }

    static int[] answer(int N, int end){// route of 0 -> end
        //assert bitCount(end) is odd
        if(N==1) return new int[]{0, 1};
        if(N==2){
            switch(end){
                case 1: return new int[]{0,2,3,1};
                default: return new int[]{0,1,3,2};
            }
        }

        int[] ans = new int[1 << N];
        if((end&(1<<(N-1)))==0){
            int[] smaller = answer(N-1, end);
            for(int i=0; i<smaller.length; i++){
                if((i&1)==0){
                    ans[2*i] = smaller[i];
                    ans[2*i+1] = smaller[i] | (1<<(N-1));
                }else{
                    ans[2*i] = smaller[i] | (1<<(N-1));
                    ans[2*i+1] = smaller[i];
                }
            }
            return ans;
        }else{
            int[] smaller1 = answer(N-1, 1);
            for(int n=0; n<(1<<(N-1)); n++) ans[n]=smaller1[n];
            int[] smaller2 = answer(N-1, end^(1<<(N-1))^1);
            for(int n=0; n<(1<<(N-1)); n++) ans[(1<<(N-1))+n]=smaller2[n] ^ (1<<(N-1)) ^ 1;
            return ans;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        if(Integer.bitCount(A^B) %2 ==0) impossible();

        System.out.println("YES");
        int[] ans = answer(N, A^B);
        for(int i=0; i<ans.length; i++) ans[i] ^= A;
        for(int i=0; i<ans.length; i++){
            System.out.print(ans[i]);
            if(i==ans.length-1) System.out.println();
            else System.out.print(" ");
        }


    }
}

Measured memory_bytes: 44348
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }


int main() {

	ll N;
	cin >> N;
	cout << N / 3 << endl;

}

Measured memory_bytes: 256
import java.util.Scanner

var N=0
var D=0
var answer=0
val sc=Scanner(System.`in`)
fun main(args:Array<String>){
    N=sc.nextInt()
    D=sc.nextInt()
    var ary=Array(N,{Array(D,{0})})
    for(i in 0..(N-1)){
        for(j in 0..(D-1)){
            ary[i][j]=sc.nextInt()
        }
    }
    for(i in 0..(N-1)){
        for(j in 0..(i-1)){
            var tmp=0
            for(k in 0..(D-1)){
                tmp+=(ary[i][k]-ary[j][k])*(ary[i][k]-ary[j][k])
            }
            if(tmp==root(tmp)*root(tmp)){
                answer++
            }
        }
    }
    println(answer)
}

fun root(a: Int): Int {
    var a = a

    var ketasu = 0
    var tmp = a
    while (tmp > 0) {
        ketasu++
        tmp /= 10
    }
    val constant = (ketasu + 1) / 2    //よく使うので定数化
    if (ketasu >= 1) {
        val suuji = IntArray(constant)
        tmp = a
        for (i in 0 until constant) {
            suuji[constant - 1 - i] = a % 100
            a /= 100
        }
        var ans = 0
        var kai = 0
        var mae = 0
        if (constant <= 1) {
            for (i in 10 downTo 0) {
                if (suuji[0] >= i * i) {
                    return i
                }
            }
        } else {
            for (i in 0 until constant) {
                mae += kai * 2
                for (j in 9 downTo 0) {
                    if ((mae * 10 + j) * j <= suuji[i]) {
                        ans = ans * 10 + j
                        mae *= 10
                        kai = j
                        if (i + 1 < constant) {
                            suuji[i + 1] += (suuji[i] - (mae + j) * j) * 100
                        }
                        break
                    }
                }
            }
        }
        return ans
    } else {
        return 0
    }
}


Measured memory_bytes: 31136
import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * Created by Aksenov239 on 23.10.2016.
 */
public class Main {
    public static void main(String[] args) {
        new Main().run();
    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

    public String nextToken() throws  IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException{
        return Integer.parseInt(nextToken());
    }

    public void solveA() throws IOException {
        String s = nextToken();
        String f = "CF";
        int p = 0;
        for (int i = 0; i < s.length() && p < f.length(); i++) {
            if (s.charAt(i) == f.charAt(p)) {
                p++;
            }
        }
        if (p == 2) {
            out.println("Yes");
        } else {
            out.println("No");
        }
    }

    public void solveB() throws IOException {
        int k = nextInt();
        int t = nextInt();
        int[] a = new int[t];
        int max = 0;
        for (int i = 0; i < t; i++) {
            a[i] = nextInt();
            max = Math.max(a[i], max);
        }

        if (2 * max > k) {
            out.println(max - 1 - (k - max));
        } else {
            out.println(0);
        }
    }

    public void run() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);

            solveB();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 8272