akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod =1e9+7;
const int maxn = 1e5+5;
ll a[maxn];
ll b[maxn];

ll C[maxn];
ll inv[maxn];

int n,k;
void getinv()
{
	inv[1] = 1;
	for (int i = 2; i <= n; ++i) inv[i] = (long long)(mod-mod/i) * inv[mod%i]%mod;	
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0) 
	{
		x=1;y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}


void getC()
{
	memset(C,0,sizeof(C));
	C[n-k+1] = 1;
	ll beg = k-1, end = 1;
	for(int i=n-k;i>=1;i--)
	{
		ll x=0,y=0;
		beg++;
		exgcd(end,mod,x,y);
		C[i] = C[i+1]%mod*beg%mod*x%mod;
		C[i] = (C[i]%mod+mod)%mod;
		end++;
	}

}

bool cmp(ll a,ll b)
{
	return a>b;
}
int main()
{
    
	while(cin>>n>>k)
	{
		memset(b,0,sizeof(b));
		
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			a[i] = a[i]%mod;
		}
		sort(a+1,a+1+n,cmp);
		getC();
		ll ans = 0;
		for(int i=1;i<=n;i++)
		{
			b[i] = (C[i]%mod - C[n+1-i]%mod)%mod;
		}
		for(int i=1;i<=n;i++)
		{
			ans = (ans%mod + a[i]*b[i]%mod)%mod;
		}
		
		cout<<ans<<"\n";
	}
 } 
 
 /*
 10 5
 1000000000 999999999 999999998 999999997 999999996 123456789 111111111 9 8 7
 */

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
const int K = 10 + 7;
const int MOD = 998244353;
int n;
int k;
int dp[N];
int sum[N];
int l[K];
int r[K];

int rep(int x)
{
    x %= MOD;
    if (x < 0)
    {
        x += MOD;
    }
    return x;
}

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

    cin >> n >> k;
    dp[1] = sum[1] = 1;
    for (int i = 1; i <= k; i++)
    {
        cin >> l[i] >> r[i];
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            int first = max(1, i - r[j]);
            int last = i - l[j];
            if (last >= 1)
            {
                dp[i] = rep(dp[i] + sum[last] - sum[first - 1]);
            }
        }
        sum[i] = rep(sum[i - 1] + dp[i]);
    }
    cout << dp[n] << "\n";
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    string a, b;
    cin >> a >> b;
    if (a == "H") {
        cout << b << endl;
    } else {
        cout << (b == "H" ? "D" : "H") << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const LL MOD = 1000000007LL;
int dp[1001];
int main() {
	int N;
	while (cin >> N, N) {
		int r, w;
		vector<P> book;
		for (int i = 0; i < N; i++) {
			cin >> r >> w;
			book.emplace_back(r, w);
		}
		sort(book.begin(), book.end());
		int r_sum = 0, w_sum = 0;
		for (int i = 0; i < N; i++) {
			r_sum += book[i].first;
			w_sum += book[i].second;
		}
		if (r_sum >= 2 * book[N - 1].first) {
			cout << r_sum + w_sum << endl;
			continue;
		}
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < N - 1; i++) {
			for (int j = 1000; j >= 0; j--) {
				if (j >= book[i].second) {
					dp[j] = max(dp[j], dp[j - book[i].second] + book[i].second);
				}
			}
		}
		int t = book[N - 1].first - (r_sum - book[N - 1].first);
		cout << r_sum + w_sum + (t - dp[t]) << endl;
	}
}


Measured memory_bytes: 3116
using System;
using static System.Console;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(ReadLine());
        int ans = 0;
        for(int i = 1; i <= N; i++)
        {
            if(Digit(i) % 2 == 1)
            {
                ans++;
            }
        }
        WriteLine(ans);
    }

    static int Digit(int num)
    {
        return (num == 0) ? 1 : ((int)Math.Log10(num) + 1);
    }
}

Measured memory_bytes: 13140
n = gets.to_i
v = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

s = [ ]
n.times do |i|
  ooo = v[i] - c[i]
  s.push ooo unless ooo < 0
end

result = [ ]
for x in 1..s.size
  result.concat s.combination(x).map{ |comb| comb.inject(&:+) }
end

p result.empty? ? 0 : result.max


Measured memory_bytes: 17528
#include <stdio.h>
#include <algorithm>

using namespace std;

#define INF 1000000000

int a[2002], n, k, q;
int b[2002];

int f(int l, int r) {
	for(int i=1;i<=n;i++) {
		if(l<=a[i] && a[i]<=r) b[i]=1;
		else if(a[i]<l) b[i]=0;
		else b[i]=2;
	}
	int len=0, c1=0, res=0;
	for(int i=1;i<=n+1;i++) {
		if(b[i]==0) {
			res+=max(0,min(c1,len-k+1));
			len=c1=0;
		} else if(b[i]==1) {
			len++; c1++;
		} else len++;
	}
	return res;
}

int main() {
	scanf("%d %d %d",&n,&k,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int res=(1<<30);
	for(int i=1;i<=n;i++) {
		int st=a[i];
		if(f(st,INF)<q) continue;
		if(f(st,st)>=q) {
			puts("0");
			return 0;
		}
		int lo=st, hi=INF;
		while(lo+1<hi) {
			int mid=(lo+hi)/2;
			if(f(st,mid)>=q) hi=mid;
			else lo=mid;
		}
		res=min(res,hi-st);
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 128
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var m = int.Parse(line[1]);
        var x = int.Parse(line[2]);
        var y = int.Parse(line[3]);
        line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
         line = Console.ReadLine().Trim().Split(' ');
        var b = Array.ConvertAll(line, int.Parse);
        Array.Sort(a);
        Array.Sort(b);
        var amax1 = a[n - 1];
        var bmin1 = b[0] ;
        for (int i = x + 1; i <= y; i++)
        {
            if (amax1 < i && i <= bmin1) { Console.WriteLine("No War"); goto end; }
        }
        Console.WriteLine("War");
        end:;
    }
}


Measured memory_bytes: 11220
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	static final PrintStream out = System.out;
	static Scanner sc = new Scanner(System.in);
	static final long Mod = 2019L;
	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
		System.exit(0);
	}
	void solve() {
		long L = nextLong();
		long R = nextLong();
		if(L <= Mod && Mod <= R || R - L >= Mod) {
			out.println(0);
			return;
		}

		long min = Mod;
		for(long i=L;i<R;i++) {
			for(long j=i+1;j<=R;j++) {
				min = Math.min(i*j%Mod,min);
			}
		}
		out.println(min);
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)a[i] = nextInt();
		return a;
	}
	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)a[i] = nextLong();
		return a;
	}
	public int nextInt() {
		return Integer.parseInt(next());
	}
	public long nextLong() {
		return Long.parseLong(next());
	}
	public String next() {
		return sc.next();
	}

}

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

const int MAX_N = 500000;
int ans = 0;
const int INF = 2100000000;


void merge(int A[], int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    int L[MAX_N], R[MAX_N];
    
    for (int i = 0; i < n1; i++) {
        L[i] = A[left + i];
    }
    for (int i = 0; i < n2; i++) {
        R[i] = A[mid + i];
    }
    
    L[n1] = INF;
    R[n2] = INF;
    
    int l = 0;
    int r = 0;
    for (int i = left; i < right; i++) {
        if (L[l] <= R[r]) {
            A[i] = L[l];
            l++;
        } else {
            A[i] = R[r];
            r++;
        }
        ans++;
    }
}

void merge_sort(int A[], int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        merge_sort(A, left, mid);
        merge_sort(A, mid, right);
        merge(A, left, mid, right);
    }
}

int main(void){
    // Your code here!
    int N;
    int S[MAX_N];
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    
    merge_sort(S, 0, N);
    for (int i = 0; i < N; i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << S[i];
    }
    cout << endl << ans << endl;
    return 0;
}



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

int main(){
    string s;
    cin >> s;
    ll n = s.size();
    ll sum = 1 + n * (n-1) / 2;
    vector<ll> c(26, 0);
    rep(i, 0, n) c[s[i] - 'a']++;
    rep(i, 0, 26) sum -= c[i] * (c[i] - 1) / 2;
    cout << sum << endl;
    return 0;
}

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

int main() {
  int h;
  cin >> h;
  int w;
  cin >> w;
  vector<vector <char>> a(h, vector<char>(w));
  for (int i = 0; i < h; i = i + 1) {
    for (int j = 0; j < w; j = j + 1) {
      cin >> a.at(i).at(j);
    }
  }
  vector<vector<bool>> judge(h, vector<bool>(w, true));
  for (int i = 0; i < h; i = i + 1) {
    int count = 0;
    for (int j = 0; j < w; j = j + 1) {
      if (a.at(i).at(j) == '.') {
        count = count + 1;
      }
    }
    if (count == w) {
      for (int j = 0; j < w; j = j + 1) {
        judge.at(i).at(j) = false;
      }
    }
  }
  
  for (int j = 0; j < w; j = j + 1) {
    int count = 0;
    for (int i = 0; i < h; i = i + 1) {
      if (a.at(i).at(j) == '.') {
        count = count + 1;
      }
    }
    if (count == h) {
      for (int i = 0; i < h; i = i + 1) {
        judge.at(i).at(j) = false;    
      }
    }
  }
  
  for (int i = 0; i < h; i = i + 1) {
    int count = 0;
    for (int j = 0; j < w; j = j + 1) {
      if (judge.at(i).at(j) ) {
        cout << a.at(i).at(j);
      } else {
        count = count + 1;
      }
    }
    if (count != w) {
      cout << endl;
    }
  }
}



Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<queue>

using namespace std;

#define fi first
#define se second

const int maxn = 1e3+10;
const int Move[4][2] = {-1,0,1,0,0,1,0,-1};
char mp[maxn][maxn];
int step[maxn][maxn];
bool vis[maxn][maxn];
int n,m;

bool check(int x,int y) 
{
    if(x<0 || y<0|| x>=n || y>=m || vis[x][y] || mp[x][y]=='#') 
	{
		return false;	
	}
    return true;
}

int BFS() 
{
    queue<pair<int,int> > q;
    q.push(make_pair(0,0));
    step[0][0]=1;
    vis[0][0]=true;
    while(!q.empty())
	{
        pair<int,int> t=q.front();
        q.pop();
        for(int i=0;i<4;i++) 
		{
            int tox=t.fi+Move[i][0];
            int toy=t.se+Move[i][1];
            if(tox==n-1 && toy==m-1) 
			{
				return step[t.fi][t.se]+1;
			}
            if(check(tox,toy)) 
			{
                vis[tox][toy]=true;
                step[tox][toy]=step[t.fi][t.se]+1;
                q.push(make_pair(tox,toy));
            }
        }
    }
    return -1;
}


int main()
{
    cin>>n>>m;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) 
		{
            cin>>mp[i][j];
            if(mp[i][j]=='#') 
			{
				cnt++;
			}
        }
    }
    int res=BFS();
    if(res==-1) 
	{
        cout<<"-1"<<endl;
    } 
	else 
	{
        cout<<n*m-res-cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

using namespace std;
const double PI = 3.14159265358979323846;
int main() {
    double a;
    cin >> a;
     cout << setprecision(16) <<  2.0 * a * PI  << endl;

}


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

using namespace std;

int main(int argc, char const *argv[]) {
	int c[26];
	for(int i = 0; i < 26; i++) {
		c[i] = 10000;
	}
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		char s[51];
		scanf("%s", s);
		int ci[26] = {};
		for(int j = 0; j < strlen(s); j++) {
			ci[s[j] - 'a']++;
		}
		for(int j = 0; j < 26; j++) {
			c[j] = min(c[j], ci[j]);
		}
	}
	for(int i = 0; i < 26; i++) {
		for(int j = c[i]; j > 0; j--) {
			printf("%c", 'a' + i);
		}
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

#define M 1000003 //最大値以上の素数
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  
  if ( ch == 'A'){
    return 1;
  }
  else if ( ch == 'C'){
    return 2;
  }
  else if ( ch == 'G'){
    return 3;
  }
  else if ( ch == 'T'){
    return 4;
  }
  return 0;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1 + key % (M - 1); }

int find(char str[]){

  int key;
  int i = 0,j,hash,a,b;

  key = getKey(str);
  a = h1(key);
  b = h2(key);

  while(i < M){  
    j = (a + i * b) % M;
    if(H[j][0] == '\0'){
      return 0;
    }
    else if(strcmp(H[j],str) == 0){
      return 1;
      break;
    }
    i++;
  }
  return 0;
}


int insert(char str[]){
  
  int key;
  int i = 0,j,hash,a,b;

  key = getKey(str);
  a = h1(key);
  b = h2(key);
  
  while(i < M){
    j = (a + i * b) % M;
    if(H[j][0] == '\0'){
      strcpy(H[j],str);
      break;
    }
    i++;
  }
  return 0;
}

int main(){
  int i, n, h;
  char str[L], com[9];
  for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
  scanf("%d", &n);
    
  for ( i = 0; i < n; i++ ){
    scanf("%s %s", com, str);
	
    if ( com[0] == 'i' ){
      insert(str);
    } else {
      if (find(str)){
	printf("yes\n");
      } else {
	printf("no\n");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 14280
N,M = map(int,input().split())
E = []
for i in range(N):
  S = list(map(int,input().split()))
  S.remove(S[0])
  L = list(set(S))
  
  E.extend(L)
p = 0
for j in range (M):
  if E.count(j+1) == N:
    p += 1
print(p)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp3
{
    class Watch
    {
        static void Main(string[] args)
        {
            int S = int.Parse(Console.ReadLine());
            int h = S / 3600;
            int m = S % 3600 / 60;
            int s = S % 3600 % 60;
            Console.WriteLine(string.Format("{0}:{1}:{2}", h, m, s));
        }
        
    }
}



Measured memory_bytes: 9220
#include <iostream>

using namespace std;

int N;

int main(){
    int x,i,j;
    int sum = 0;
    cin >> N;
    int d[50];
    for(i=0; i<N; i++){
        cin >> d[i];
    }
    
    for(i=0; i < N-1; i++){
        for(j=i+1; j < N; j++){
            sum += d[i] * d[j];
        }
    }

    cout << sum; 

    return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define con continue
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 1ll<<61;
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<int, PP> PPP;
struct edge { int to; int to2; int cost; };
int dp[108][4][4][4];
signed main() {
	int n; cin >> n;
	rep(i, 4)rep(j, 4)rep(k, 4)dp[3][i][j][k]++;
	dp[3][0][1][2]--;
	dp[3][1][0][2]--;
	dp[3][0][2][1]--;
	for (int i = 4; i <= n; i++) {
		rep(j, 4) {
			rep(k, 4) {
				rep(l, 4) {
					rep(m, 4) {
						if (j == 0 && k == 1 && l == 2)con;
						if (j == 0 && k == 2 && l == 1)con;
						if (j == 1 && k == 0 && l == 2)con;
						if (k == 0 && l == 1 && m == 2)con;
						if (k == 1 && l == 0 && m == 2)con;
						if (k == 0 && l == 2 && m == 1)con;
						if (j == 0 && l == 1 && m == 2)con;
						if (j == 0 && k == 1 && m == 2)con;
						dp[i][k][l][m] += dp[i-1][j][k][l];
						dp[i][k][l][m] %= mod;
					}
				}
			}
		}
	}
	int ans = 0;
	rep(i, 4)rep(j, 4)rep(k, 4) {
		ans += dp[n][i][j][k];
		ans %= mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
// header {{{
// header {{{
#include <bits/stdc++.h>
using namespace std;
 
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y
 
#define ASSERT(expr...) assert((expr))
 
using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
 
using f32 = float;
using f64 = double;
// }}}
 
constexpr i64 INF = 1'010'000'000'000'000'017LL;
 
constexpr i64 MOD = 1'000'000'007LL;
 
constexpr f64 EPS = 1e-12;
 
constexpr f64 PI = 3.14159265358979323846;
 
#define M5 100007
#define M9 1000000000
 
 
// util {{{
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
 
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define ll long long int
#define VI vector <ll>
template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
 
template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
 
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
 
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}
// }}}
 
// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
 
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}
 
//--------------------------------------------------------------------
 
bool isOK(int mid, double key){
 
    if((double)mid*mid > key) {
             return true;
     } else {
              return false;
     }
}
 
 int binary_search(double key) {
    int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int right = 2000000000;
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
 
        if (isOK(mid, key)) right = mid;
        else left = mid;
    }
 
    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}
 
void solve() {
    ll a,b,c;
    cin >> a >> b >> c;
    ll m = c - a - b;
 
 
    if(m>0&& 4*a*b < m*m ){
        cout << "Yes";
    } else{
        cout << "No";
    }
}
 
signed main() {
 
    solve();
 
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <sstream>
using namespace std;

#define REP(i,a,n) for(i=a; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define foreach(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); it++)

int n;
bool used[110];
double x[110], y[110], z[110], r[110];
const double inf = 999999999.9;
vector<pair<int, double> > dist[110];


double sqr(double x){ return x*x; }

bool isoverlap(int i, int j){
    return (sqr(x[i]-x[j]) + sqr(y[i]-y[j]) + sqr(z[i]-z[j]) <= sqr(r[i]) + 2.0*r[i]*r[j] + sqr(r[j]));
}

int main(){
    int i,j,k;

    while( cin >> n, n){
        rep(i,n) cin >> x[i] >> y[i] >> z[i] >> r[i];

        // init
        rep(i,n) dist[i].clear();
        memset(used, false, sizeof(used));

        rep(i,n){
            REP(j,i+1,n){
                if( isoverlap(i,j) ){
                    dist[i].push_back(make_pair(j,0.0));
                    dist[j].push_back(make_pair(i,0.0));
                }
                else{
                    double cost = sqrt(sqr(x[i]-x[j]) + sqr(y[i]-y[j]) + sqr(z[i]-z[j])) - (r[i] + r[j]);
                    dist[i].push_back(make_pair(j,cost));
                    dist[j].push_back(make_pair(i,cost));
                }
            }
        }

        // debug
        /*
        rep(i,n){
            rep(j,dist[i].size()){
                printf("%d -> %d , cost = %lf\n",i,dist[i][j].first, dist[i][j].second);
            }
        }
        puts("");
        */

        double res = 0.0;

        used[0] = true;
        rep(k,n-1){
            int id = -1;
            double cost = inf;

            rep(i,n) if( used[i] ) {
                rep(j,dist[i].size()){
                    //printf("i:%d --> u:%d\n",i,dist[i][j].first);
                    int u = dist[i][j].first;
                    double tmp = dist[i][j].second;
                    if( used[u] ) continue;
                    if( tmp < cost ){
                        cost = tmp;
                        id = u;
                    } 
                }
            }

            //printf("k = %d, id = %d\n",k,id);

            if( id == -1 ){
                exit(1);
            }
            used[id] = true;
            res += cost;
        }

        printf("%.3lf\n", (k == n-1 ? res : 0.0) ); 
    }

    return 0;
}

Measured memory_bytes: 1144
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define rep(i,n) for (long long i=0; i < (n); ++i)
#define rep2(i,n,m) for(long long i=n;i<=m;i++)
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
int main() {
  int n ,p;
  cin >> n>>p ;
  vector<int> A(n) ;
  rep(i,n) cin >>A[i] ;
  int odd = 0 ;
  rep(i,n) {
    if(A[i]%2==1) odd++ ;
  }
  int even= n-odd ;
  ll base= pow(2,even) ;
  ll all=pow(2,odd) ;
  ll ans=0 ;//奇数のもの
  for(int i=0;2*i+1<=odd;i++){
    int c=2*i+1 ;
    ll comb=1 ;
    rep(j,c){
      comb*=(odd-j) ;
    
      comb/=(j+1) ;
    }
   ans+=comb ;
  }
    if(p==1)
    cout << base*ans <<endl ;
    else
     cout <<base*(all-ans) <<endl ; 
     return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
const int INF = 1001001001;

ll max(ll a, ll b ){
    return (a<b) ? b : a ; 
}

int main() {

    int n,m ;
    ll k ;
    cin >> n >> m >> k ;    
    ll a[n] ;
    ll b[m] ;
    for (int i = 0; i < n; i++) cin >> a[i] ;
    for (int i = 0; i < m; i++) cin >> b[i] ;
    
    ll c[m+1] ;
    c[0] = 0 ;
    for (int i = 0; i < m; i++)
    {
        c[i+1] = c[i] + b[i] ;
    }
    
    ll ans = 0 ;
    ll t = 0 ;
    for (int i = 0; i <= n; i++)
    {
        if(i!=0){
        t += a[i-1] ;
        }
        if(t>k) break;
        int left = -1 ;
        int right = m+1 ;

        while (right-left>1)
        {
        int mid = (right+left)/2 ;
        if(c[mid] + t <= k)
         left = mid ;
        else 
         right = mid ;        
        }       
        ans = max(ans , i + left) ;
    }
    cout << ans << endl ;    
    return 0; 
}

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

int main(){
	string s,p;
	cin>>s>>p;
	char c[s.size()*2];
	for(int i=0;i<s.size()*2;i++) c[i]=s[i%s.size()];
	for(int i=0;i<s.size();i++){
		for(int j=0;c[i+j]==p[j]&&j<p.size();j++){
			if(j==p.size()-1){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout<<"No"<<endl;
	return 0;
}



Measured memory_bytes: 3200
#include <cmath>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;

using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    vector<ll> as;
    as.resize(n);
    for(int i = 0;i < n;i++)
    {
        cin >> as[i];
    }
    sort(as.begin(), as.end(), std::greater<ll>());
    ll sum = 0;
    int count = 0;
    for(auto e : as)
    {
        if(sum + e < k)
        {
            sum += e;
            count++;
        }
        else
        {
            count = 0;
        }
    }
    
    cout << count << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  
  deque<ll> que;
  for(int i = 0; i < n; i++)
  {
	int v;
	cin >> v;
	if(i % 2 == 0) {
	  que.push_front(v);
	} else {
	  que.push_back(v);
	}
  }

  if(n % 2 == 1) {
	for(int i = 0; i < n; i++) {
	  cout << (i > 0 ? " " : "") << que[i];
	}
  } else {
	for(int i = n - 1; i >= 0; i--) {
	  cout << (i < n - 1 ? " " : "") << que[i];
	}
  }
  cout << endl;
  
  return 0;
}


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

int main()
{
    int K;
    cin >> K;
    int d[K+1]; //modK = 0,1,2,....,K-1
    fill(d, d + K, 1e9); 
    d[1] = 1;
    deque<int> que;
    que.push_back(1);
    while(!que.empty()) {
        int p = que.front(); que.pop_front();
        if(d[(p+1)%K] > d[p] + 1) {
            //1の位が9の時の辺は、より小さい数から10倍して行った方が距離が短く、
            //行き先の頂点がすでに訪れられていることがわかるので、
            //考慮しなくても良いことがわかる。
            //例, 1->10->11->,,,->19->20 よりも、1->2->20の方が距離が短い
            d[(p+1)%K] = d[p] + 1; que.push_back((p+1)%K);
        }
        if(d[(p*10)%K] > d[p]) {
            d[(p*10)%K] = d[p]; que.push_front((p*10)%K);
        }
        /*
        for(int i = 0; i < K; ++i) {
            cout << d[i] << " ";
        }
        cout << endl;
        */
    }
    cout << d[0] << endl;
    return 0;
}

Measured memory_bytes: 896
#include<stdio.h>

int main(){
  int n, i, j, key, k;
  scanf("%d", &n);
  int A[n];
  for(i = 0 ; i < n ; i++){
    scanf("%d", &A[i]);
  }
  for(k = 0 ; k < n ; k++){
    if(k == n - 1)printf("%d", A[k]);
    else printf("%d ", A[k]);
  }
  printf("\n");
  for(i = 1 ; i < n ; i++){
    key = A[i];
    j = i - 1;
    while(j >= 0 && A[j] > key){
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = key;
    for(k = 0 ; k < n ; k++){
      if(k == n - 1)printf("%d", A[k]);
      else printf("%d ", A[k]);
    }
    printf("\n");
  }
  return 0;
}



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

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

    string S;
    cin >> S;

    if(S == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
}

Measured memory_bytes: 3600
s=str(input())
co=int(1)
n=len(s)
A=[]
for i in range(1,n):
    if s[i]!=s[i-1]:
        A.append(co)
        co=1
    else:
        co+=1
A.append(co)
m=len(A)
how=0
if s[0]=='T':
    how=1

S=int(0)
T=int(0)
for i in range(how,m-how):
    if i%2==how:##s
        S+=A[i]
    else:##t
        T+=A[i]
        if S<T:
            n-=2*S
            T=0
            S=0
        else:
            n-=2*T
            S-=T
            T=0


print(n)

Measured memory_bytes: 4324
#include <stdio.h>

char S[114514];

int asumisu;
char mizuhasu[114514];

int main(void) {
	int i;
	int kitaeri = 0;
	if (scanf("%114513s", S) != 1) return 1;
	mizuhasu[0] = '#';
	asumisu = 0;
	for (i = 0; S[i] != '\0'; i++) {
		if (mizuhasu[asumisu] == (S[i] == '0' ? '1' : '0')) {
			kitaeri += 2;
			asumisu--;
		} else {
			mizuhasu[++asumisu] = S[i];
		}
	}
	printf("%d\n", kitaeri);
	return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        int y = Math.abs(x1 - x2);
        int x = Math.abs(y1 - y2);
        int x3 = 0;
        int y3 = 0;
        int x4 = 0;
        int y4 = 0;
        if (x1 < x2 && y1 <= y2) {
            x3 = x2 - x;
            y3 = y2 + y;
            x4 = x1 - x;
            y4 = y1 + y;
        }
        if (x1 >= x2 && y1 <= y2) {
            x3 = x2 - x;
            y3 = y2 - y;
            x4 = x1 - x;
            y4 = y1 - y;
        }
        if (x1 >= x2 && y1 > y2) {
            x3 = x2 + x;
            y3 = y2 - y;
            x4 = x1 + x;
            y4 = y1 - y;
        }
        if (x1 < x2 && y1 > y2) {
            x3 = x2 + x;
            y3 = y2 + y;
            x4 = x1 + x;
            y4 = y1 + y;
        }
        System.out.println(x3 + " " + y3 + " " + x4 + " " + y4);

    }

}

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

int main() {
  long long w,h,x,y;
  scanf("%d %d %d %d", &w,&h,&x,&y);

  double ww = w;
  double hh = h;
  double ansa = ww*hh/2;
  long long ansb = 0;

  if(x*2==w && y*2==h) ansb = 1;

  std::cout << std::fixed << std::setprecision(15);



  cout << ansa << " " << ansb << endl;
 
  
}



Measured memory_bytes: 256
N=int(input())
a=list(map(int,input().split()))
cumSum = [0]
for i in range(N):
    cumSum.append(cumSum[i]+a[i])
def csum(l,r):
    return(cumSum[r]-cumSum[l-1])
def value(i):
    return(abs(csum(1,i)-csum(i+1,N)))
ans = value(1)
for i in range(1,N):
    ans = min(ans,value(i))
print(ans)

Measured memory_bytes: 23784
/// kAAzuki Hoshino


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define rep1(i, a, b) for(int i =a; i >=b; i--)
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define MAX 500000
#define K 30
//#define endl '\n'
typedef tree<
int,
null_type,less<int>,
rb_tree_tag,tree_order_statistics_node_update>
ordered_set;
int x,y,deg[100],cnt[100];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
for(int i=1;i<4;i++){
   cin >> x >> y;
   deg[x]++;
   deg[y]++;
}
for(int i=0;i<6;i++){
   cnt[deg[i]]++;
}
if(cnt[1]==2&&cnt[2]==2){
   cout << "YES" << endl;
}
else {
   cout << "NO" << endl;
}

return 0;}
///....


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

char *tbl[] = {"dream", "erase", "dreamer", "eraser"};
int len[] = {5, 5, 7, 6};
char str[100001];

int main() {
	int i;
	int pos;

	scanf("%s", str);
	pos = strlen(str);


	while(pos > 0) {
		for(i = 0; i < 4; i++) {
			if(pos >= len[i] && strcmp(tbl[i], &str[pos - len[i]]) == 0) {
				str[pos - len[i]] = '\0';
				break;
			}
		}
		if(i == 4) {
			printf("NO\n");
			return 0;
		}
		pos -= len[i];
	}

	printf("YES\n");

	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define Pair pair<int,int>


int H,W;
char s[52][52];

int find_shortest_route(){
	int x,y;
	bool visit[H+2][W+2];
	Pair prev[H+2][W+2];
	queue<Pair> q;

	for(int i=0;i<H+2;i++){
		for(int j=0;j<W+2;j++){
			visit[i][j] = false;
		}
	}

	q.push({1,1});
	visit[1][1] = true;

	while(!q.empty()){
		x = q.front().first; y = q.front().second;
		//cout << x << ", " << y << endl;
		q.pop();
		if(s[x-1][y] != '#' && !(visit[x-1][y]) ){
			prev[x-1][y] = {x,y};
			visit[x-1][y] = true;
			q.push({x-1,y});
		}

		if(s[x][y+1] != '#' && !(visit[x][y+1]) ){
			prev[x][y+1] = {x,y};
			visit[x][y+1] = true;
			q.push({x,y+1});
		}

		if(s[x+1][y] != '#' && !(visit[x+1][y]) ){
			prev[x+1][y] = {x,y};
			visit[x+1][y] = true;
			q.push({x+1,y});
		}

		if(s[x][y-1] != '#' && !(visit[x][y-1]) ){
			prev[x][y-1] = {x,y};
			visit[x][y-1] = true;
			q.push({x,y-1});
		}
	}
	x = H; y = W;
	int limit = 0;
	while(x != 1 || y != 1){
		s[x][y] = '%';
		int a = prev[x][y].first; 
		int b = prev[x][y].second;
		x = a; y = b; limit++;
		if(limit > H*W) return -1;
		//cout << x << ", " << y << endl;
	}
	s[1][1] = '%';
	return 1;
}

int solve(){
	if(find_shortest_route() == -1){
		cout << "-1" << endl;
		return 0;
	}
	int count = 0;
	for(int i=1;i<H+1;i++){
		for(int j=1;j<W+1;j++){
			if(s[i][j] == '.') count++;
		}
	}
	cout << count << endl;
	return 0;
}



int main(){
	cin >> H >> W;
	for(int i=0;i<H+2;i++){
		s[i][0] = '#';
		s[i][W+1] = '#';
	}

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

	for(int i=1;i<H+1;i++){
		for(int j=1;j<W+1;j++){
			cin >> s[i][j];
		}
	}

	solve();

	// for(int i=0;i<H+2;i++){
	// 	for(int j=0;j<W+2;j++){
	// 		cout << s[i][j];
	// 	}
	// 	cout << endl;
	// }

	
	return 0;






}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <climits>
#include <cfloat>


using namespace std;

int d[16384];

int main()
{
	int n;
	while (scanf("%d", &n), n)
	{
		for (int i = 0; i < n; ++i)
			scanf("%d", d + i);
		sort(d, d + n);
		long long  ans = 0;
		long long  t = 0;
		for (int i = 1; i < n; ++i)
		{
			t += d[i-1];
			ans += t;
		}
		printf("%lld\n", ans);
	}

	return 0;
}

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

int a, b, c;

int main() {
	cin >> a >> b >> c;
	int i, j, t = 0;
	for( i = 0; i < 100; i++) {
		for( j = 0; j <= a; j++) {
			if (t % 60 == c)
				break;
			t += (j < a);
		}
		if ( j <= a )
			break;
		t += b;
	}
	if ( i < 100 )
		cout << t << endl;
	else
		cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 1164
R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        if r*R+g*G>N:
            continue
        if (N-r*R-g*G)%B==0:
            ans += 1

print(ans)

Measured memory_bytes: 40556
n,m=map(int,input().split())
mod=10**9+7
dp=[1]*(n+1)
for _ in range(m):
  dp[int(input())]=0
dp[1]*=dp[0]
for i in range(2,n+1):
  dp[i]*=dp[i-1]+dp[i-2]
print(dp[-1]%mod)

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

int main()
{
    long numa, numb, numx;
    cin >> numa >> numb >> numx;
    if(numa==0){
        cout << numb/numx + 1 << endl;
        return 0;
    }
    cout << numb/numx - (numa-1)/numx <<endl; 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
    #define sz(a) (int)(a).size()
    #define debug(x) (cerr << #x << ": " << x << "\n")
     
    using namespace std;
     
    template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
    template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
    const int INF = 1e5+2;
    const long long hell = 998244353ll;
     
    int n , m , ans = 0;
    vector<int>color(INF,2);
    vector<vector<int>>bp(2);
    vector<vector<char>>arrr(INF);
    char arr[51][51];
    vector<vector<bool>>bani(51,vector<bool>(51,false));
     
    void dfs(pair<int,int>v , pair<int,int> p , pair<int,int> pp , int k){
    	if(bani[v.first][v.second] || ans ) return;
    	bani[v.first][v.second] = true;
    	if(k >= 4 && p != pp && v != p){
    	 	ans = 1;
    	 	return;
	}
	
    }
     
    void solve(){
    	cin >> n;
    	if(n==1){
    		cout << 1.00000000 << endl; 
    		return ;
    	}
    	if(n==0){
    		cout << 0.000000 << endl;
    		return ;
    	}
    	double aa = (double)n/2;	
    	if(n&1){
    		aa += 1;
    		//cout << aa << endl;
    		cout << (double)((n/2)+1)/n << endl;
    	}else{
    		cout << 0.500000000 << endl;
    	}
    		
    }
    int main(){
        	
    	ios_base::sync_with_stdio(0);cin.tie(0);
    	  cout.precision(10);
    cout << fixed;	
    	int q=1;
    #ifdef LOCAL
      	cin>>q;
    #endif
      	while(q--){
      		solve();
      	}
    #ifdef LOCAL
       	cout << "Time elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif	
    	return 0;
    }

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

const ll tenPowEighteen = 1000000000000000000;

int main()
{
    ll a,b;
    string c;
    cin>>a>>c;

    b = (c[0]-'0');
    b = (b*10) + (c[2]-'0');
    b = (b*10) + (c[3]-'0');

    ll ans = (a*b)/100;
    cout<<ans;

    return 0;
}


Measured memory_bytes: 3620
N=int(input())
A=[]
for i in range(N):
  a=int(input())
  A.append(a)
  
ans=max(A)
for i in range(N):
  if A[i]==ans:
    b=A[:i]
    c=A[i+1:]
    aa=b+c
    an=max(aa)
    if an==ans:
      for j in range(N-i):
        print(ans)
      break
    else:
      print(an)
  else:
    print(ans)

Measured memory_bytes: 16244
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int calc(int i, int j, int x, int y){

	int use;
	int dontUse;

	dontUse = j-i;
	use = abs(x-i) + abs(y-j) + 1;

	return min(dontUse, use);

}

int main()
{
	int N, X, Y;
	cin >> N >> X >> Y;
	vector<int> res;

	res.resize(N);
	for(int i=1; i<N; i++){
		res[i] = 0;
	}

	for(int i=1; i<N; i++){
		for(int j=i+1; j<N+1; j++){
				res[calc(i, j, X, Y)] += 1;
		}
	}

	for(int k=1; k<N; k++){
		cout << res[k] << endl;
	}


	return 0;
}

Measured memory_bytes: 256
import sys
from io import StringIO
import unittest
import os


# 実装を行う関数
def resolve():
    s = list(input())
    k = int(input())

    # 各桁をaにするために必要な処理回数を求める。(1桁ずつ求めていく)
    need_cnt_list = [26 - (ord(i) % 97) for i in s]
    # アルファベット(小文字)のaASCIIは97。なので、mod97でアルファベットを番号に置換できる(a=0 z=25)。ちなみに大文字Aは65。
    # for i in s:
    #     work += 26 - (ord(i) % 97)

    ans = []

    zan_cnt = k

    for num, i in enumerate(need_cnt_list):
        # 値がaの場合何もしない(既に最適解)
        if s[num] == "a":
            ans.append("a")
        # 値を1週させてaにできる場合、該当文字をaにする。
        elif zan_cnt >= i:
            zan_cnt -= i
            # 該当文字をaにする。
            ans.append("a")
        # 値を1週させてaにできない場合、その桁は何も処理せず次の桁に進む。
        else:
            ans.append(s[num])

    # 最後に、最終桁を延々と処理した結果が答え。
    # ※「余ったkを全て最終桁に使用した場合の最終桁の文字」で最終文字を置換
    now_last = ord(ans[-1]) - 97
    last = zan_cnt % 26 + now_last

    # 最終桁の文字を置き換え
    ans[-1] = chr(last + 97)
    print("".join(ans))
    return


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """xyz
4"""
        output = """aya"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """a
25"""
        output = """z"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """codefestival
100"""
        output = """aaaafeaaivap"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """bbb
100000000"""
        output = """aaz"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_2(self):
        test_input = """bbb
75"""
        output = """aaa"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_2(self):
        test_input = """bbc
74"""
        output = """aaa"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_3(self):
            test_input = """bba
74"""
            output = """aay"""
            self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()


Measured memory_bytes: 62856
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = Integer.parseInt(sc.next());
    int p = 0, sum = 0;
    int max = 0;
    for (int i = 0; i < N; i++) {
      p = Integer.parseInt(sc.next());
      sum += p;
      if (p > max) {
        max = p;
      }
    }
    System.out.println(sum - max / 2);
  }
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

unordered_map<ll, int> mp;
unordered_set<int> st[1000010];
queue<pii> q;
int n, f[1000010];

int find(int x)
{
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}

ll getid(int x, int y)
{
    if (x < y)
        swap(x, y);
    return (ll)x * n + y;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n * 2 - 2; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        st[x].insert(y);
        st[y].insert(x);
        mp[getid(x, y)]++;
        if (mp[getid(x, y)] == 2)
            q.push(pii(x, y));
    }
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    unordered_set<int>::iterator it;
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        x = find(x);
        y = find(y);
        if (x == y)
            continue;
        st[x].erase(y);
        st[y].erase(x);
        if (st[x].size() < st[y].size())
            swap(x, y);
        for (it = st[y].begin(); it != st[y].end(); ++it)
        {
            int z = *it;
            mp[getid(y, z)] = 0;
            st[z].erase(y);
            st[z].insert(x);
            mp[getid(x, z)]++;
            st[x].insert(z);
            if (mp[getid(x, z)] == 2)
                q.push(pii(x, z));
        }
        f[y] = x;
        st[y].clear();
    }
    int s = 0;
    for (int i = 1; i <= n; ++i)
        s += (f[i] == i);
    if (s == 1)
        puts("YES");
    else
        puts("NO");
    return 0;
}

Measured memory_bytes: 89288
n,m,x = map(int, input().split())
c = [0 for i in range(n)]
a = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    tmp = list(map(int, input().split()))
    c[i] = tmp[0]
    for j in range(m):
        a[i][j] = tmp[j + 1]
able = False
ans = 10**8
for i in range(2**n):
    price = 0
    flag = True
    buy = [0 for j in range(n)]
    rikai = [0 for j in range(m)]
    for j in range(n):
        if i>>j & 1 == 1:buy[j] = 1
    for j in range(n):
        if buy[j] == 1:
            price += c[j]
            for k in range(m):
                rikai[k] += a[j][k]
    for j in range(m):
        if rikai[j] < x:
            flag = False
            break
    if not flag:continue
    able = True
    ans = min(ans,price)
if able:print(ans)
else:print(-1)

Measured memory_bytes: 9276
A['   '];M;B,X,Y;W,J,I;main(){scanf("%d%d",&I,&M);for(;~scanf("%d%d",&X,&Y);){B=Y+1;for(J=1;J*J<=M;J++){I=(X+J-1)/J,W=Y/J+1;A[I]++;A[W<B?W:B]--;B=I;}for(I=1;I<B;I++){if((X-1)/I<Y/I){A[I]++;A[I+1]--;}}}for(I=1;I<=M;I++){A[I]+=A[I-1];printf("%d\n",A[I]);}}

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

const int64_t INF = 1e18 + 1;
const int64_t MAX_POSSESS = 2500;
const int MAX_N = 50;
const int MAX_M = 100;
const int MAX_EDGE = MAX_M * MAX_POSSESS;
struct Edge
{
  int64_t to;
  int64_t fare;
  int64_t time;
};

std::vector<Edge> uniqueEdge[(MAX_N + 1) * MAX_POSSESS];

int64_t ToUniqueNodeId(const int64_t nodeId, const int64_t possess)
{
  int64_t p = std::min(possess, MAX_POSSESS - 1);
  return nodeId * (MAX_POSSESS) + p;
}

std::vector<int64_t> dijkstra(const int64_t& startNodeId)
{
  std::vector<int64_t> dp((MAX_N + 1) * MAX_POSSESS, INF);
  dp[startNodeId] = 0;
  auto compare = [&](int64_t lhs, int64_t rhs){return dp[lhs] > dp[rhs];};
  std::priority_queue<int64_t, std::vector<int64_t>, decltype(compare) > pq(compare);
  pq.push(startNodeId);
  int64_t count = 0;
  while (!pq.empty())
  {
    int64_t nodeId = pq.top();
    pq.pop();
    for (const auto& edge : uniqueEdge[nodeId])
    {
      const int64_t cost = dp[nodeId] + edge.time;
      if (cost < dp[edge.to])
      {
        dp[edge.to] = cost;
        pq.push(edge.to);
      }
    }
  }
  return dp;
}

int main()
{
  int n, m;
  int64_t s;
  std::cin >> n >> m >> s;
  std::vector<Edge> edge[MAX_N];
  for (int i = 0; i < m; ++i)
  {
    int u, v;
    int64_t a, b;
    std::cin >> u >> v; --u; --v;
    std::cin >> a >> b;
    edge[u].push_back({v, a, b});
    edge[v].push_back({u, a, b});
  }

  int64_t c[MAX_N], d[MAX_N];
  for (int i = 0; i < n; ++i)
  {
    std::cin >> c[i] >> d[i];
  }

  for (int nodeId = 0; nodeId < n; ++nodeId)
  {
    for (int nowPossess = 0; nowPossess < MAX_POSSESS; ++nowPossess)
    {
      int64_t srcNodeId = ToUniqueNodeId(nodeId, nowPossess);
      int64_t dstNodeId = ToUniqueNodeId(nodeId, nowPossess + c[nodeId]);
      uniqueEdge[srcNodeId].push_back({dstNodeId, 0, d[nodeId]});
      for (const auto& to : edge[nodeId])
      {
        if (nowPossess < to.fare) continue;
        int64_t moveNodeId = ToUniqueNodeId(to.to, nowPossess - to.fare);
        uniqueEdge[srcNodeId].push_back({moveNodeId, to.fare, to.time});
      }
    }
  }
  auto totalTime = dijkstra(ToUniqueNodeId(0, std::min(s, MAX_POSSESS - 1)));
  for (int nodeId = 1; nodeId < n; ++nodeId)
  {
    int64_t ans = INF;
    for (int possess = 0; possess < MAX_POSSESS; ++possess)
    {
      int64_t uniqueNodeId = ToUniqueNodeId(nodeId, possess);
      ans = std::min(ans, totalTime[uniqueNodeId]);
    }
    std::cout << ans << std::endl;
  }
  return 0;
}

Measured memory_bytes: 29396
/**
 *    created by : PawPaw       
**/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  

using namespace __gnu_pbds;  
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,  
        tree_order_statistics_node_update>  
        ordered_set;  

#define F(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define LL long long
#define PHI acos(-1)
#define EPS 0.000000001
#define N 100001
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define FbO find_by_order
#define OoK order_of_key

LL a[N], b[N];

bool check(int x, int n, LL m, LL v, LL p){
  b[x] += m;
  v--;
  vector<pair<LL, int>> pp(n);
  RF(i, n-1, n-p+1){
    if(i == x) return true;
    if(v) b[i] += m;
    else break;
    v--;
  }
  LL point = m*v;  
  RF(i, n-p, 0){
    if(i == x) continue;
    LL k = max((LL)0, min(b[x]-b[i], min(point, m)));
    b[i] += k;
    point -= k;
  }
  if(point) return false;
  else {
    F(i, 0, n-1){
      pp[i] = MP(b[i], i);
    }
    sort(pp.begin(), pp.end());
    int pos = 1;
    LL bef = pp[n-1].first;
    RF(i, n-1, 0){
      if(bef > pp[i].first) pos = n-i;
      bef = pp[i].first;
      if(pp[i].second == x){
        return (pos <= p);
      }
    }  
  }
  return false;
}

int solve(){
  int n;
  LL m, v, p;
  cin >> n >> m >> v >> p;
  int l = 0, r=n-1, mid;
  F(i, 0, n-1) cin >> a[i];
  sort(a, a+n);
  while(l != r){
    F(i, 0, n-1) b[i] = a[i];
    mid = (l+r)/2;
    if(check(mid, n, m, v, p)){
      r = mid;
    } else {
      l = mid+1;
    }
  }
  cout << n - l << endl;
  return 0;
}

void fun(){
  int t = 1;
  // cin >> t;
  while(t--) solve();
} 

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

Measured memory_bytes: 3556