akhauriyash/Code-Regression huggingface dataset:
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define in insert
#define ld long double


#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define int ll
const ll mod =1e9+7;
const ll MAX_NODES =200001;
const ll MAX_LOG =50;
const ll maxn = 400000+10;

int32_t main()
{

   IOS
   int n;
   cin>>n;
   int t = n-1;
   set<int> s;
   for(int i = 1;i*i<=t;i++){
     if(t%i==0){
       s.in(i);
       if(i*i!=t){
         s.in(t/i);
       }
     }
   }
   vl div;
   for(int i = 2;i*i<=n;i++){
     if(n%i==0){
       div.pb(i);
       if(i*i!=n){
         div.pb(n/i);
       }
     }
   }
   div.pb(n);
   for(int i = 0;i<div.size();i++){
     int x =  n;
     while(x%div[i] == 0)
      x/=div[i];
      if(x%div[i] == 1)
        s.in(div[i]);
   }
   while(*s.begin()<2){
     s.erase(*s.begin());
   }
   cout<<s.size();
   
}

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

struct Card {char suit, value;};

void bubble(struct Card A[], int N) {
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= i + 1; j--) {
			if (A[j].value < A[j - 1].value) {
				Card t = A[j];
				A[j] = A[j - 1];
				A[j - 1] = t;
			}
		}
	}
}

void selection(struct Card A[], int N) {
	for (int i = 0; i < N; i++) {
		int minj = i;
		for (int j = i; j < N; j++) {
			if (A[j].value < A[minj].value) minj = j;
		}
		Card t = A[i];
		A[i] = A[minj];
		A[minj] = t;
	}
}

void print(struct Card A[], int N) {
	for (int i = 0; i < N; i++) {
		if (i > 0) cout << " ";
		cout << A[i].suit << A[i].value;
	}
	cout << endl;
}

bool isStable(struct Card C1[], struct Card C2[], int N) {
	for (int i = 0; i < N; i++) {
		if (C1[i].suit != C2[i].suit) return false;
	}
	return true;
}

int main() {
	Card C1[100], C2[100];
	int N;
	char ch;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> C1[i].suit >> C1[i].value;
	}

	for (int i = 0; i < N; i++) C2[i] = C1[i];

	bubble(C1, N);
	selection(C2, N);

	print(C1, N);
	cout << "Stable" << endl;
	print(C2, N);
	if (isStable(C1, C2, N)) cout << "Stable" << endl;
	else cout << "Not stable" << endl;

	return 0;
}


Measured memory_bytes: 3104
N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))
L = [0] * (sum(T)*2+1)
R = [0] * (sum(T)*2+1)
xt, xv = 0, 0
for t, v in zip(T, V):
    for tt in range(xt*2+1, (t+xt)*2+1):
        xv += .5
        L[tt] = min(v, xv)
    xt += t
    xv = min(v, xv)
xt, xv = 0, 0
for t, v in zip(T[::-1], V[::-1]):
    for tt in range(xt*2+1, (t+xt)*2+1):
        xv += .5
        R[tt] = min(v, xv)
    xt += t
    xv = min(v, xv)
print(sum(map(min, L, R[::-1]))/2)

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
	ll n,a[214514],b[214514];
int main() {

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b,b+n);
	ll num1=b[n-1],num2=b[n-2];
	if(num1==num2)for(int i=0;i<n;i++)cout<<num1<<endl;
	else for(int i=0;i<n;i++){
		if(a[i]==num1)cout<<num2<<endl;
		else cout<<num1<<endl;
	}
	return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>

int main(void) {
	int a, b;
	scanf("%d%d", &a, &b);

	if (a == 1 && b == 2)
		printf("3");
	if (a == 1 && b == 3)
		printf("2");
	if (a == 2 && b == 3)
		printf("1");
	if (b == 1 && a == 2)
		printf("3");
	if (b == 1 && a == 3)
		printf("2");
	if (b == 2 && a == 3)
		printf("1");
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define betheflash ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vs vector<string>
#define vvi vector<vector<int>>
#define mii map<int,int>
#define msi map<string,int>
#define mis map<int,string>
#define pb push_back
#define mod 1000000007
using namespace std;
void solve()
{
	ll n,ans=0,ans2=0;
	cin>>n;
	ans=n/500;
	ans*=1000;
	n=n%500;
	ans2=n/5;
	ans2*=5;
	ans=ans+ans2;
	cout<<ans;
}
int main()
{
    betheflash
	int t=1;
	//cin>>t;
	for(int ha=0;ha<t;ha++)
	{
		solve();
	}
    return 0;
}

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



signed main(){
    int n,m,k,a;
    cin >> n>>m;
    int ans[m]={};
    for(int i=0;i<n;i++){
        cin >> k;
        for(int j=0;j<k;j++){
            cin >> a;
            ans[a-1]++;
        }
    }
    int b=0;
    for(int i=0;i<m;i++){
        if(ans[i]==n)b++;
    }
    cout << b;
    return 0;
}

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

a = [list(map(int,input().split())) for _ in range(n)]

lst = []

for i in range(n):
    for j in range(i+1,n):
        if a[j][0]-a[i][0] < 0:
            lst.append([a[i][0]-a[j][0], a[i][1]-a[j][1]])
        if a[j][0]-a[i][0] == 0:
            lst.append([a[i][0]-a[j][0], abs(a[i][1]-a[j][1])])
        else:
            lst.append([a[j][0]-a[i][0], a[j][1]-a[i][1]])

if n ==1:
    print(1)
else:
    x = 0
    for i in range(len(lst)):
        c = 1
        for j in range(i+1,len(lst)):
            if lst[i] == lst[j]:
                c += 1
        x = max(x,c)
    print(n-x)

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

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

const int MAX = 2 * 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

struct Combination{
    private:
        vector<long long> fac, finv, inv;
    
    public:
        Combination(){
            fac = finv = inv = vector<long long> (MAX);

            fac[0] = fac[1] = 1;
            finv[0] = finv[1] = 1;
            inv[1] = 1;
            for (int i = 2; i < MAX; i++){
                fac[i] = fac[i - 1] * i % MOD;
                inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
                finv[i] = finv[i - 1] * inv[i] % MOD;
            }
        }

        long long getCom(int n, int k){
            if (n < k) return 0;
            if (n < 0 || k < 0) return 0;
            return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
        }
};

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

    Combination com = Combination();

    ll ans = 0;
    rep(i, min(K + 1, N)) {
        int m = N - i;
        ans += com.getCom(N, i) * com.getCom(N-1, m-1) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}

Measured memory_bytes: 4992
using System.Collections.Generic;using System.Linq;using static System.Console;class K{int[]G=>ReadLine().Split().Select(i=>int.Parse(i)-1).ToArray();int N;static void Main()=>new K().Z();void Z(){var I=G;N=I[0]+1;WriteLine(string.Join(" ",C(G,G,I[1]).Select(i=>i+1)));}int[]C(int[]p,int[]q,int K){int[]P=I(p),Q=I(q),x=E(M(q,P,Q,p),K/6),y=I(x);switch(K%6){case 0:return M(x,p,y);case 1:return M(x,q,y);case 2:return M(x,q,P,y);case 3:return M(x,q,P,Q,y);case 4:return M(x,q,P,Q,p,Q,y);default:return M(x,q,P,Q,p,p,Q,y);}}int[]I(int[]a){var c=new int[N];for(var i=0;i<N;i++)c[a[i]]=i;return c;}int[]M(int[]a,int[]b){var p=new int[N];for(var i=0;i<N;i++)p[i]=a[b[i]];return p;}int[]M(params int[][]a)=>a.Aggregate(M);int[]E(int[]a,int b){var p=new int[N];var f=new bool[N];for(var i=0;i<N;i++)if(!f[i]){var l=new List<int>();var x=i;while(!f[x]){l.Add(x);f[x]=true;x=a[x];}var C=l.Count;for(var j=0;j<C;j++)p[l[j]]=l[(j+b)%C];}return p;}}

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

int main() {
  int k;
  cin >> k;
  int a = 0;
  for(int i = 0; i < 2000000; i++) {
    a = (a*10 + 7) % k;
    if(a == 0) {
      cout << i+1 << endl;
      return 0;
    }
  }
  
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 3620
import java.util.Scanner;
import java.util.ArrayList;
import java.io.*;

class RollingHash {
  final long base = 10007L;
  final long mod = 999999937L;
  long[] power;
  long[] hash;

  RollingHash(String s) {
    int n = s.length();
    power = new long[n + 1];
    hash = new long[n + 1];
    power[0] = 1L;
    for (int i = 0; i < n; i++) {
      power[i + 1] = power[i] * base % mod;
      hash[i + 1] = (hash[i] * base + s.charAt(i)) % mod;
    }
  }

  long getHash(int l, int r) {
    return ((hash[r] - hash[l] * power[r - l]) % mod + mod) % mod;
  }
}

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

    RollingHash rhT = new RollingHash(T);
    RollingHash rhP = new RollingHash(P);
    
    if (T.length() < P.length()) {
      return;
    }

    PrintWriter out = new PrintWriter(System.out);
    long pHash = rhP.getHash(0, P.length());
    // System.err.println(pHash);
    for (int i = 0; i < T.length() - P.length() + 1; i++) {
      long tHash = rhT.getHash(i, i + P.length());
      // System.err.println(tHash);
      if (pHash == tHash) {
        out.println(i);
      }
    }
    out.close();
  }
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] != t[i])
      ans++;
  }
  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 3796
#include<stdio.h>
int main(){
int a[102],i,b,c,x,y,d=0,z,g;
while(1){
scanf("%d\n",&b);
if(b==0){
break;
}
else{
for(i=0;i<b+1;i++){
scanf("%d ",&a[i]);
}
scanf("\n");
x=a[1]-a[0];
y=a[2]-a[1];
z=a[3]-a[2];
g=a[4]-a[3];
if(x==z){
c=x;
}
else if(y==z){
c=y;
}
else{
c=x;
}
for(i=1;i<b;i++){
if(x+y==z && z==g){
d=a[1];
break;
}
else if(x+y==z && z!=g){
d=a[3];
break;
}
else if(a[i+1]-a[i]!=c){
d=a[i+1];
break;
}
}
if(d==0){
d=a[0];
}
printf("%d\n",d);
d=0;
}
}
return 0;
}



Measured memory_bytes: 2048
use std::io::{Read, stdin};
use std::str::FromStr;

fn main() {
    let n: u32 = read();
    let k: u32 = read();
    let mut ans: u64 = k as u64;
    for _i in 0..n-1 {
        ans *= (k - 1) as u64;
    }
    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

Measured memory_bytes: 4352
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int edge[10000010];
int main()
{
    int n,i,j,k,x,y,ans,curr,temp,m;
    int tc;
    cin >> n;
    for(i=1;i<=n;i++) {
        for(j=i;j<=n;j+=i) {
            edge[j]++;
        }
    }
    ll chaeng = 0;
    for(i=1;i<=n;i++) chaeng += 1LL*i*edge[i];
    cout<< chaeng << endl;
    return 0;
}


Measured memory_bytes: 42620
# できなかった
# アームの長さが決まると(xm+ym)mod2は一定になる、これが一定でなければ無理
# (xj+yj)mod2=1としてよい、長さ1の腕を追加することで0の場合も考えられる
# (u,v)=(x+y,x-y)(回転座標)とすると、ui,viをu(i+1),v(i+1)から独立に決定できる(+d,-dいづれかはされることが確定している)
# よってdiを決めたときにui,viを決める問題をu,vについて独立に解けば、各関節の向きを決定できる
# u(i+1)=ui+diとなるi∈{1,...,m}の集合をSとすると、u(m)=-Σ(1≦i≦m) di +Σ(i∈S) 2di が成り立つ
# -2*10^9≦Uj,Vj≦2*10^9 と 1≦m≦40 より m=31,di=2^(i-1) とできる。すると、Uj=-(2^31-1) +Σ(i∈S) 2di となる
# つまりΣ(i∈S) 2di =Uj+(2^31-1) となるようにSを選ぶことができるので解ける

n=int(input())
listXY=[list(map(int,input().split())) for _ in range(n)]
listUV=[[listXY[i][0]+listXY[i][1],listXY[i][0]-listXY[i][1]]for i in range(n)]

isOdd=listUV[0][0]%2
canReach=1
for i in range(1,n):
    if isOdd!=listUV[i][0]%2:
        canReach=0
        break

if not canReach:
    print(-1)
else:
    offset=2**31-isOdd
    m=32-isOdd
    d=[2**i for i in range(32)]
    w=[]
    for i in range(n):
        x,y=0,0
        u,v=listUV[i][0]+offset,listUV[i][1]+offset
        s=''
        if not isOdd:
            s='L'
            x=x-1
        for k in range(31):
            u //= 2
            v //= 2
            u1, v1 = u % 2, v % 2
            # L(-d,-d),R(+d,+d),D(-d,+d),U(+d,-d)
            if u1 == 0 and v1 == 1:
                s += 'D'
                y=y-d[k]
            elif u1 == 0 and v1 == 0:
                s += 'L'
                x=x-d[k]
            elif u1 == 1 and v1 == 1:
                s += 'R'
                x=x+d[k]
            elif u1 == 1 and v1 == 0:
                s += 'U'
                y=y+d[k]
        w.append(s)
        # print(x,y,s)
    # print(listXY)
    # print(listUV)
    print(32-isOdd)
    s=''
    if not isOdd:
        s='1 '
    for i in range(31):
        s+=str(d[i])+' '
    print(s)
    for i in range(n):
        print(w[i])


Measured memory_bytes: 3572
// ALDS1_2_B: Selection Sort

use std::str::FromStr;

fn selection_sort(a: &mut Vec<i64>, n: usize) -> usize {
    let mut i: usize = 0;
    let mut sw: usize = 0;
    while i < n - 1 {
        let mut minj: usize = i;
        let mut j: usize = i;
        while j < n {
            if a[j] < a[minj] {
                minj = j;
            }
            j += 1;
        }
        let t: i64 = a[i];
        a[i] = a[minj];
        a[minj] = t; 
        if i != minj {
            sw += 1;
        }
        i += 1;
    }
    sw
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n = s.trim().parse::<usize>().unwrap();

    s.clear();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut it = s.split_whitespace().map(|n| i64::from_str(n).unwrap());
    let mut a: Vec<i64> = Vec::new();
    while let Some(v) = it.next() {
        a.push(v);
    }

    let sw = selection_sort(&mut a, n);

    print!("{}", a[0]);
    for i in 1..n {
        print!(" {}", a[i]);
    }
    println!();

    println!("{}", sw);
}


Measured memory_bytes: 5028
import java.util.Scanner;
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	static long lcm (int a, int b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}


		public static void main(String[] args) {
			Scanner scan=new Scanner(System.in);
			int a=scan.nextInt();
			long sum=0;
			long rui[]=new long[a];
			for(int i=0;i<a;i++) {
				int b=scan.nextInt();
				sum+=b;
				rui[i]=sum;
			}
			long min=1145123123123114191L;
			for(int i=0;i<a-1;i++) {
				long r=rui[i]*2-sum;
				long uo=Math.abs(r);
				min=min>uo?uo:min;
			}
			System.out.println(min);
		}
}

Measured memory_bytes: 81432
# coding: utf-8
N = gets().to_i
A = gets.split.map{|e| e.to_i}
save_idx = {}

# 今のindexを記録
A.each_with_index do |e, i|
  save_idx[e] = i
end

# 値順にソート
A.sort!
  
# 記録したidx+1を出力
A.each do |_e|
  p save_idx[_e] + 1
end


Measured memory_bytes: 22404
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

template<class Val, class Cmp>
struct SlidingWindow {
    SlidingWindow(const vector<Val> &a) :cmp(), a(a), l(0), r(0), deq() {
    }
    void proceedTo(int lef, int rig) {
        while (r < rig)stepR();
        while (l < lef)stepL();
    }
    void stepL() {
        if (deq[0] == l++) deq.pop_front();
    }
    void stepR() {
        while (!deq.empty() && !cmp(a[deq.back()], a[r])) deq.pop_back();
        deq.push_back(r++);
    }
    int getIndex() {
        return deq[0];
    }
    Val getValue() {
        return a[deq[0]];
    }
    Cmp cmp;
    vector<Val> a;
    int l, r;
    deque<int> deq;
};
using SlidingMin32 = SlidingWindow<int, less<int>>;
using SlidingMax32 = SlidingWindow<int, greater<int>>;
using SlidingMin64 = SlidingWindow<long long, less<long long>>;
using SlidingMax64 = SlidingWindow<long long, greater<long long>>;

/*
最大値のスライド
[i, i+K)の最大値をすべて求める。
O(|data|)
*/
template<class Val>
vector<Val> maxSlide(int length, vector<Val> data, Val minValue = -1) {
    int num = (int)data.size();
    deque<int> deq;
    vector<Val> res(num, minValue);
    for (int i = 0; i < num; ++i) {
        while (!deq.empty() && data[deq.back()] <= data[i]) {
            deq.pop_back();
        }
        deq.push_back(i);
        if (i >= length - 1) {
            res[i - length + 1] = data[deq.front()];
            if (deq.front() == i - length + 1)deq.pop_front();
        }
    }
    for (int i = 1; i < length; ++i) {
        res[num - i] = data[deq.front()];
    }
    return res;
}

void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    vi A(N);
    rep(i, N)cin >> A[i];

    const ll MI = LLONG_MIN / 3;
    vll cur(N + 1, MI), nex(N + 1);
    rep(i, N)cur[i + 1] = A[i];
    rep(i, K - 1) {
        fill(all(nex), MI);
        SlidingMax64 ma(cur);
        for (int j = 1; j <= N; ++j) {
            ma.proceedTo(max(0, j - M), j);
            nex[j] = ma.getValue() + A[j - 1] * (i + 2ll);
        }
        swap(cur, nex);
    }
    ll ans = *max_element(all(cur));
    cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using str = string;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
const double PI = 3.141592653589793238;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define REP(i, m, n) for (int i = m; i < (int)n; i++)
#define all(a) (a).begin(), (a).end()
#define allg(a) (a).begin(), (a).end(), greator<>()
#define d20 std::setprecision(20)
#define veci vector<int>
#define vecll vector<long long int>
#define vecb vector<bool>
#define vecd vector<double>
template <typename T>
T lcm(T a, T b)
{
	return a / __gcd(a, b) * b;
}
void comb(vector<vector<long long int>> &v)
{
	for (size_t i = 0; i < v.size(); i++)
	{
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (size_t k = 1; k < v.size(); k++)
	{
		for (size_t j = 1; j < k; j++)
		{
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}
ll repeat_squaring(ll n, ll p, ll m)
{
	if (p == 0)
		return 1;
	if (p % 2 == 0)
	{
		ll t = repeat_squaring(n, p / 2, m);
		return t * t % m;
	}
	return n * repeat_squaring(n, p - 1, m);
}

int main()
{
	int n, m;
	cin >> n >> m;
	vecll a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));
	vector<Pll> bb(m);
	rep(i, m)
	{
		ll b, c;
		cin >> b >> c;
		bb[i] = make_pair(c, b);
	}
	sort(all(bb), greater<>());
	int now = 0, a_now = 0;
	while (bb[now].first > a[a_now] && a_now < n)
	{
		bb[now].second--;
		a[a_now++] = bb[now].first;
		if (bb[now].second == 0)
		{
			now++;
		}
	}
	ll ans = 0;
	for (ll x : a)
		ans += x;
	std::cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N; cin >> N;
    vector<int> A(N),B(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
        B[i] = A[i];
    }
    sort(B.begin(), B.end());
    int ma = B[N-1], sma = B[N-2];
    
    for(int i = 0; i < N; i++){
        if(A[i] == ma) cout << sma << endl;
        else cout << ma << endl;
    }
}

Measured memory_bytes: 3200
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

// Sort
type Val struct {
	id, num int
}
type ByNum []Val

func (a ByNum) Len() int           { return len(a) }
func (a ByNum) Less(i, j int) bool { return a[i].num < a[j].num }
func (a ByNum) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N, T := sc.nextInt(), sc.nextInt()
	ans := 0
	before := sc.nextInt()
	for i := 1; i < N; i++ {
		t := sc.nextInt()
		ans += min(T, t-before)
		before = t
	}
	ans += T

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}


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

using namespace std;

int main (void) {
    long long X;
    cin >> X;

    for ( long long A=-200; A<200; A++ ) {
        for ( long long B=-200; B<200; B++ ) {
            if ( A * A * A * A * A - B * B * B * B * B == X ) {
                cout << A << " " << B << endl;
                return 0;
            }
        }
    }
    return 1;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 103, M = N << 1;

int n, a[N];
LL ans = INF;

int main()
{
	//File("");
	n = gi <int> ();
	for (int i = 1; i <= n; i+=1) a[i] = gi <int> ();
	for (int i = -100; i <= 100; i+=1)
	{
		LL res = 0;
		for (int j = 1; j <= n; j+=1)
			res += abs(i - a[j]) * abs(i - a[j]);
		ans = min(ans, res);
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
#define sz 200002
#define pb push_back
#define ff first
#define ln '\n'

#define ss second
#define ll long long
#define VEC vector<ll int>v
#define TEST() int test;cin>>test; while(test--)
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;

//ll int LCM(ll int a,ll int b) { ll int gcd=__gcd(a,b);ll int lcm=a*b/gcd;return lcm;}
//ll int bigmod(ll int b, ll int p, ll int m){if(p==0)return 1;if(p%2!=0) return b%m*fun(b,p-1,m)%m;if(p%2==0){ ll int res=fun(b,p/2,m);return (res%m*res%m)%m;}}
//void seive() { prime[np++]=2;for(i=3; i<=sz; i+=2){if(mark[i]==0){ prime[np++]=i;for(j=i*i; j<=sz; j+=i) mark[j]=1; } }}
//string add(string s1,string s2) {string s;int j=s1.size()-1,c=0,m; for(int i=s2.size()-1; i>=0; i--) {if(j>=0)m=s2[i]-'0'+s1[j]-'0'+c;else m=s2[i]-'0'+c; if(m>9) { s+=m%10+'0';c=m/10; } else {  c=0;s+=m+'0'; }j--; } if(c!=0) {s+=c+'0'; }reverse(s.begin(),s.end());return s;}
//int pos;string mul(int n) {string s;for(int i=0; i<pos; i++) { s+="0"; }pos++;int c=0,m; for(int i=s1.size()-1; i>=0; i--) { m=(s1[i]-'0')*n+c;if(m>9) { s+=m%10+'0';c=m/10;} else { c=0; s+=m+'0';} }while(c!=0) { s+=c%10+'0';c=c/10;}    reverse(s.begin(),s.end());return s;}

int main()
{

ll a,b,c;
cin>>a>>b>>c;
if(a+b>=c){
  cout<<"No"<<endl;
  return 0;
}
ll int s1=c-a-b,s2=4LL*a*b;
if(s1*s1>s2)cout<<"Yes"<<endl;

else cout<<"No"<<endl;


}



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

int main() {
  int N, K, x;
  cin >> N >> K;
  x = 1;
  for(int i = 0; i < N; i++){
    
    if(x <= K){
      x *= 2;
    }
    else if(x > K){
      x += K;
    }
  }
  cout << x << endl;

}


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

int main(){
  int n; cin>>n;
  int x[n],y[n],c[n];
  int mx,my,mc=0;
  bool flag = true;
  for(int i=0;i<n;i++){
    cin>>x[i]>>y[i]>>c[i];
    if(mc<c[i]){
      mc=c[i];
      mx=x[i]; my=y[i];
      flag =true;
    }else if(mc==c[i]){
      flag=false;
    }
  }if(flag){
    for(int i=0;i<n;i++){
      if(c[i]!=max(0,mc-abs(x[i]-mx)-abs(y[i]-my))){
        break;
      }if(i==n-1){
        cout<<mx<<' '<<my<<' '<<mc<<endl;
        return 0;
      }
    }
  }while(true){
  mc++;
  for(int i=0;i<101;i++){
    for(int j=0;j<101;j++){
      for(int k=0;k<n;k++){
        if(x[k]==i && y[k]==j) break;
        if(c[k]!=max(0,mc-abs(x[k]-i)-abs(y[k]-j))){
        break;
      }if(k==n-1){
          cout<<i<<' '<<j<<' '<<mc<<endl;
          return 0;
        }
      }
    }
  }
  }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int n,i;
	cin>>n;
	double a[n+1],sum=0;
	string s[n+1];
	for(i=1;i<=n;i++)cin>>a[i]>>s[i];
	for(i=1;i<=n;i++)
	if(s[i]=="JPY")sum+=a[i]*1.0;
	else
	sum+=a[i]*380000.0;
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define REP(i,N) for(int i = 0; i < (int)N; i++)

int hako[1000100];
int main(){
	int n;
	while(cin >> n){
		int ret = 0;
		REP(i,1000100)hako[i] = 0;
		for(int i=2;i<=n;i++){
			if(hako[i] == 1)continue;
			ret++;
			for(int j=i;j <= n;j+=i){
				hako[j] = 1;
			}
		}
		cout << ret << endl;
	}
	return 0;
}

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

//#define int long long

using namespace std;

signed main(){
    int S;
    cin >> S;
    
    int A[4];
    A[0] = S / 1000;
    A[1] = (S / 100) % 10;
    A[2] = (S / 10) % 10;
    A[3] = S % 10;
    
    char op[2] = {'+' ,'-'};
    
    for(int i = 0; i < 8; ++i){
        string s = string() + to_string(A[0]);
        int ans = A[0];
        for(int j = 0; j < 3; ++j){
            if((i >> j) & 1){
                ans += A[j + 1];
                s += "+" + to_string(A[j + 1]);
            } else {
                ans -= A[j + 1];
                s += "-" + to_string(A[j + 1]);
            }
        }
        if(ans == 7){
            s += "=7";
            cout << s << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 200010
//#define M 61
//#define MOD 100003
//vector <pair<int,int> > edge[M];
//int d[N][N];
//priority_queue <pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
//queue <int> q;
//ll cnte[N];
//int ans=0;
//vector <int> edge[N];
//int arr[N];
ll a[N];
void solve()
{
	ll n,sum=0;
	cin>>n;
	for (int i=1;i<=n;i++) 
		cin>>a[i];
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	sum+=a[1];
	int cnt=1;
	for (int i=2;i<=n;i++)
	{
		if ((n-1-cnt)>=2)
		{
			sum+=a[i]*2;
			cnt+=2;
		}
		else if(n-1-cnt==0)
		{
			cout<<sum<<endl;
			return;
		}
		else
		{
			sum+=a[i];
			cout<<sum<<endl;
			return;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	int t;
//	cin>>t;
//	while (t--)
		solve();
	return 0;
} 

Measured memory_bytes: 5200
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

int loss(const int x) {
    if (x == 0) {
        return 10;
    } else {
        return x;
    }
}

int main(int argc, char **argv) {
    int t[5];
    int should_last = 0;
    int min_mod = 10;
    int min_mod_idx = -1;
    for (int i = 0; i < 5; i++) {
        std::cin >> t[i];
    }

    for (int i = 0; i < 5; i++) {
        int mod = t[i] % 10;
        if (mod != 0 && mod < min_mod) {
            min_mod = mod;
            min_mod_idx = i;
        }
    }

    int ret = 0;
    if (min_mod == 10) {
        for (int i = 0; i < 5; i++) {
            ret += t[i];
        }
    } else {
        for (int i = 0; i < 5; i++) {
            if (i == min_mod_idx || t[i] % 10 == 0) {
                ret += t[i];
            } else {
                ret += t[i] + 10 - t[i] % 10;
            }
        }
    }
    std::cout << ret << std::endl;
    return 0;
}


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

using namespace std;

int H , W , d;

char color[4] = { 'R', 'Y', 'G', 'B' };

inline int read(){
	int s = 0 , w = 1;
	char ch = getchar();
	while((ch < '0') || (ch > '9')){
		if(ch == '-'){
			w = -1;
		}
		ch = getchar();
    }
   	while((ch >= '0') && (ch <= '9')){
   		s = s * 10 + ch - '0';
		ch = getchar();
	}
   	return s * w;
}

#pragma GCC optimize("inline,Ofast",3)
#pragma GCC optimize(2)
#pragma GCC optimize(3)

int main(){

	H = read();
	W = read();
	d = read();
	
	for(int i = 1 ; i <= H ; i++ ){
		for(int j = 1 ; j <= W ; j++ ){
			int x = i + j + W , y = i - j + W;
			cout << color[((x / d) & 1) * 2 + ((y / d) & 1)];
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF 1000000000
#define MOD 1000000007



int main() {
    ll H, W; cin >> H >> W;
    vector<string> M(H);
    for(string &s:M)
        cin >> s;
    vector<vector<ll>> dp(H, vector<ll>(W));
    dp[0][0] = 1;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(i+1<H && M[i+1][j]!='#') dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
            if(j+1<W && M[i][j+1]!='#') dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
        }
    }
    
    
    cout << dp[H-1][W-1] << endl;
    return 0;
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

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; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const map<S, T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<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> 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);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m;
double memo[301][301][301];

double solve(int i, int j, int k) {
    int emp = n - i - j - k;
    if (emp == n) return 0;
    if (memo[i][j][k] > 0) return memo[i][j][k];
    double ans = 0;
    if (i) ans += (1 + solve(i - 1, j + 1, k)) * i / n;
    if (j) ans += (1 + solve(i, j - 1, k + 1)) * j / n;
    if (k) ans += (1 + solve(i, j, k - 1)) * k / n;
    double q = (emp / (double)n);
    return memo[i][j][k] = (ans + q) / (1 - q);
}

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    while(cin >> n){
        int c[3] = {0, 0, 0};
        REP(i, n) {
            int x;
            cin >> x;
            c[x - 1] ++;
        }
        printf("%.20f\n", solve(c[2], c[1], c[0]));
    }
    return 0;
}


Measured memory_bytes: 213376
s = gets.chomp.chars

if s.length%2 != 0
  puts "No"
  exit
end

for i in 0..(s.length-1)
	if i%2 == 0
      if(s[i] != 'h')
        puts "No"
        exit
      end
    else
      if(s[i] != 'i')
        puts "No"
        exit
      end
    end
end
puts "Yes"

Measured memory_bytes: 3836
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int> > vvi;
typedef vector<vector<double> > vvd;

int main(){

    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int result = 0;

    for(int i=0; i<=a; ++i){
      for(int j=0; j<=b; ++j){

        int q = ( x - 500*i - 100*j )/50;
        int r = ( x - 500*i - 100*j )%50;
        if ( r == 0 and 0 <= q and q <= c ) ++result;

      }
    }

    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<iomanip>
#include<utility>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define fi first
#define sec second
#define mp make_pair
#define pb push_back
#define rep(a,b,c) for(int a=1;a<=b;a+=c)
#define repp(a,b,c,d) for(int a=b;a<=c;a+=d)

const double PI=acos(-1);
const double EPS=1e-12;
const int MOD=1e9+7;
const int INF=1<<30;


using namespace std;


int main(){
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,in;
	cin>>in;
	rep(i,50000,1){
		n=(int)floor((double(i)*1.08));
		if(n==in){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<":("<<endl;
	return 0;
}


Measured memory_bytes: 256
# 2019-11-23 21:00:35(JST)
import sys
import collections
import math

def main():
    m = int(sys.stdin.readline().rstrip())

    a = collections.defaultdict(int)
    for _ in range(m):
        d, c = map(int, sys.stdin.readline().split())
        a[d] += c
    

    b = 0
    for i in range(10):
        b += (i + 9) * a[i]
    
    ans = math.ceil((b - 9)/ 9) - 1
    print(ans)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)


using namespace std;

bool is_ok(const vector<int64_t> & as, int64_t v, int64_t k) {
	int64_t c = 0;
	FOR_LT(i, 0, as.size()) {
		int64_t a = as[i];
		if (a == 0) {
			if (0 <= v) c += as.size() - 1;
			continue;
		}
		if (a < 0) {
			int64_t cv = 0;
			if (v > 0) cv = v / a;
			else       cv = (v + a + 1) / a;
			auto it = lower_bound(as.begin(), as.end(), cv);
			c += as.end() - it;

			if (cv <= a) c--;
		}
		else {
			int64_t cv = 0;
			if (v > 0) cv = v / a;
			else       cv = (v - a + 1) / a;
			auto it = upper_bound(as.begin(), as.end(), cv);
			c += (it - as.begin());

			if (a <= cv) c--;
		}
	}
	assert((c & 1) == 0);
	return (k <= (c / 2));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int64_t n, k; cin >> n >> k;

	vector<int64_t> as(n); for (auto& a : as) cin >> a;
	sort(as.begin(), as.end());

	int64_t okv = 1000000000000000001LL;
	int64_t ngv = -1000000000000000001LL;

	while (true) {
		if (ngv + 1 == okv) break;

		int64_t m = (okv + ngv) / 2;
		if (is_ok(as, m, k)) okv = m;
		else ngv = m;
	}

	cout << okv << endl;

	return 0;
}

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

int64_t gcm(int64_t x,int64_t y)
{
  if(x%y==0)
   return y;
  return gcm(y,x%y);
}


int main()
{
  int64_t n;
  cin>>n;
  cout<<n*2/gcm(2,n)<<endl;
}

Measured memory_bytes: 3568
def main():
    import sys
    input = sys.stdin.readline

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

    ans = 0
    all_num = sum(A)
    for i in range(N, 1, -1):
        all_num -= A[i - 1]
        ans += A[i - 1] * all_num
    print(ans % (10 ** 9 + 7))


main()


Measured memory_bytes: 31300
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}
 
 
 
 
 
 
 




bool s[405][405];
bool used[405][405];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int main()
{
   int h,w;
   cin>>h>>w;
   for(int i=1;i<=h;i++){
        string t;
        cin>>t;
        for(int j=0;j<t.length();j++){
             s[i][j+1]=(t[j]=='#');
        }
   }
   ll res=0,bl=0,wc=0;
   for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
             if(used[i][j])continue;
             bl=0,wc=0;
             queue<pair<int,int>> q;
             q.push({i,j});
             used[i][j]=true;
             while(!q.empty()){
                  int x=(q.front()).fi,y=(q.front()).se;
                  q.pop();
                  if(s[x][y])bl++;
                  else wc++;
                  for(int d=0;d<4;d++){
                       int nx=x+dx[d],ny=y+dy[d];
                       if(nx<1||nx>h||ny<1||ny>w)continue;
                       if(s[nx][ny]==s[x][y])continue;
                       if(!used[nx][ny]){
                            used[nx][ny]=true;
                            q.push({nx,ny});
                       }
                  }
             }
             res+=bl*wc;
        }
   }
   cout<<res;
}




































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

using namespace std;

template <typename T>
T power(T a, long long b) {
  T r = 1;
  while (b) {
    if (b & 1) {
      r *= a;
    }
    a *= a;
    b >>= 1;
  }
  return r;
}

int inverse(int a, int m) {
  a %= m;
  if (a < 0) {
    a += m;
  }
  int b = m, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= a * t;
    swap(a, b);
    u -= v * t;
    swap(u, v);
  }
  if (u < 0) {
    u += m;
  }
  return u;
}

template <int _P>
struct modnum {
  static constexpr int P = _P;

 private:
  int v;

 public:
  modnum() : v(0) {
  }

  modnum(long long _v) {
    v = _v % P;
    if (v < 0) {
      v += P;
    }
  }

  explicit operator int() const {
    return v;
  }

  bool operator==(const modnum& o) const {
    return v == o.v;
  }

  bool operator!=(const modnum& o) const {
    return v != o.v;
  }

  modnum inverse() const {
    return modnum(::inverse(v, P));
  }

  modnum operator-() const {
    return modnum(v ? P - v : 0);
  }
  
  modnum operator+() const {
    return *this;
  }

  modnum& operator++() {
    v++;
    if (v == P) {
      v = 0;
    }
    return *this;
  }
  
  modnum& operator--() {
    if (v == 0) {
      v = P;
    }
    v--;
    return *this;
  }

  modnum operator++(int) {
    modnum r = *this;
    ++*this;
    return r;
  }
  
  modnum operator--(int) {
    modnum r = *this;
    --*this;
    return r;
  }

  modnum& operator+=(const modnum& o) {
    v += o.v;
    if (v >= P) {
      v -= P;
    }
    return *this;
  }

  modnum operator+(const modnum& o) const {
    return modnum(*this) += o;
  }

  modnum& operator-=(const modnum& o) {
    v -= o.v;
    if (v < 0) {
      v += P;
    }
    return *this;
  }

  modnum operator-(const modnum& o) const {
    return modnum(*this) -= o;
  }

  modnum& operator*=(const modnum& o) {
    v = (int) ((long long) v * o.v % P);
    return *this;
  }

  modnum operator*(const modnum& o) const {
    return modnum(*this) *= o;
  }
  
  modnum& operator/=(const modnum& o) {
    return *this *= o.inverse();
  }

  modnum operator/(const modnum& o) const {
    return modnum(*this) /= o;
  }
};

template <int _P>
ostream& operator<<(ostream& out, const modnum<_P>& n) {
  return out << int(n);
}

template <int _P>
istream& operator>>(istream& in, modnum<_P>& n) {
  long long _v;
  in >> _v;
  n = modnum<_P>(_v);
  return in;
}

using num = modnum<998244353>;

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<num> fact(m * 3 + n);
  fact[0] = 1;
  for (int i = 1; i < m * 3 + n; ++i) {
    fact[i] = fact[i - 1] * i;
  }
  vector<num> inv_fact(m * 3 + n);
  for (int i = 0; i < m * 3 + n; ++i) {
    inv_fact[i] = num(1) / fact[i];
  }
  auto C = [&](int i, int j) {
    if (i < j) {
      return num(0);
    }
    return fact[i] * inv_fact[j] * inv_fact[i - j];
  };
  num ans = 0;
  for (int i = m; i >= 0; i -= 2) {
    if (i <= n) {
      int t = (m * 3 - i) / 2;
      ans += C(n, i) * (C(t + n - 1, n - 1) - C(t + n - 1 - m, n - 1) * i - C(t + n - 2 - m, n - 1) * (n - i));
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 19840
import sys

n,A,B,C=map(int,input().split())

x=[int(input()) for _ in range(n)]
inf=10**9

def dfs(cur,a,b,c):
    if cur==n:
        #print("abs",abs(a-A),abs(b-B),abs(c-C))
        #print("abs...",abs(a-A)+abs(b-B)+abs(c-C)-30)
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else inf
    ret0 = dfs(cur+1,a,b,c)
    ret1 = dfs(cur+1,a+x[cur],b,c) + 10
    ret2 = dfs(cur+1,a,b+x[cur],c) + 10
    ret3 = dfs(cur+1,a,b,c+x[cur]) + 10
    #print(ret0,ret1,ret2,ret3)
    return min(ret0, ret1, ret2, ret3)

print(dfs(0,0,0,0))

Measured memory_bytes: 3064
# ゴール：3.5.15の倍数 以外の数字を合計したい
N = int(input())

sum_exclusion = 0  # 計算結果を入れる変数

for i in range(1, N + 1):
    if not (i % 15 == 0 or i % 3 == 0 or i % 5 == 0):
        sum_exclusion += i  # rangeが空になるまで、条件に合う数値が足されていく

print(sum_exclusion)


Measured memory_bytes: 9164
#include<stdio.h>
int main(){
  int n,d,i,j,k,num=0;
  scanf("%d%d",&n,&d);
  int x[n+1][d+1];
  for(i=0;i<n;i++)
    for(j=0;j<d;j++)
      scanf("%d",&x[i][j]);
  for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++){
      int count=0,l=1;
      for(k=0;k<d;k++)
        count+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
      while(count>l*l)
        l++;
      if(count==l*l)
        num++;
    }
  printf("%d\n",num);
  return 0;
}


Measured memory_bytes: 128
#include <cstdio>

int sg(int x, const int &K) {
	if( x % K == 0 ) return x / K;
	int p = x / K + 1, q = x % K;
	return sg(x - (q + p - 1) / p * p, K);
}

int main() {
	int N, ans = 0; scanf("%d", &N);
	
	for(int i=1;i<=N;i++) {
		int A, K; scanf("%d%d", &A, &K);
		ans ^= sg(A, K);
	}
	puts(ans ? "Takahashi" : "Aoki");
}
/*
sg[i] = (i % K == 0 ? i / K : sg[i - i/K - 1])
*/

Measured memory_bytes: 128