akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(int)(a); i++)
typedef long long ll;
template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////
const ll inf = 1LL<<60;
const ll mod = 998244353;

int main()
{
  int h,w,k; cin>>h>>w>>k;
  vector<string> s(h);
  rep(i, h) cin>>s[i];

  vector<int> b(h, -1);
  vector<vector<int>> a(h, vector<int>(w));
  int p = 1;
  rep(i, h) {
    bool flg = false;
    rep(j, w) if (s[i][j] == '#') flg = true;
    if (flg) {
      b[i] = i;
      bool tmp = false;
      rep(j, w) {
        if (s[i][j] == '#') {
          if (tmp) p++;
          else tmp = true;
        }
        a[i][j] = p;
      }
    }
    if (flg) p++;
  }

  int t = -1;
  int first = -1;
  rep(i, h) {
    if (b[i] > -1) {
      t = i;
      if (first < 0) first = i;
    }
    b[i] = t;
  }
  rep(i, h) {
    if (b[i] < 0) a[i] = a[first];
    else a[i] = a[b[i]];
  }

  rep(i, h) {
    rep(j, w) {
      if (j > 0) cout << " ";
      cout << a[i][j];
    }
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 4172
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin>>N;
  int count=0;
  vector<int> card(N);
  
  for(int i=0;i<N;i++)
    cin>>card.at(i);
  
  sort(card.begin(),card.end());
  reverse(card.begin(),card.end());
  
  for(int i=0;i<N;i++){
    if(i%2==0)
      count+=card.at(i);
    else
      count-=card.at(i);
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
/*
    Author      : Dinesh Verra
    College     : ABV-IIITM
    Date        : 15/08/2020
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp> 
// using namespace boost::multiprecision; 
using namespace std;
typedef long long ll;
// #define ll int
typedef unsigned long long ull;
#define cu continue
#define br break
#define pb push_back
#define eb emplace_back
#define mod 1000000007
#define inf LLONG_MAX
#define pll pair <ll,ll>
#define min_pq priority_queue <pll> ,vector <pll>, greater <pll> > > 
#define F first
#define S second
#define vll vector <ll>
#define vpll vector <pll>
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define all(v) v.begin(),v.end()
#define nl cout<<'\n'

template <typename A1>
void prn(A1&& arg)
{
	cout<<arg<<'\n';
}
template <typename A1, typename... A>
void prn(A1&& arg, A&&... args)
{
	cout<<arg<<' ';
	prn(args...);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n,k;
	cin>>n>>k;
	ll a[n],b[n],c[n],d[n];
	for(ll i=0;i<n;i++) 
	{
		cin>>a[i];
		a[i]--;
	}
	for(ll i=0;i<n;i++) cin>>c[i];
	ll tmp,x,mx,cnt;
	for(ll i=0;i<n;i++)
	{
		tmp=0,mx=-inf,cnt=0;
		x=a[i];
		tmp+=c[x];
		cnt++;
		while(x!=i)
		{
			x=a[x];
			cnt++;
			tmp+=c[x];
		}
		b[i]=tmp;
		d[i]=cnt;
	}
	ll ans=-inf;
	for(ll i=0;i<n;i++)
	{
		tmp=-inf;
		if(b[i]>0 && k>d[i])
		{
			tmp=(b[i]*((k-1)/d[i]));
			ll rem=(k-1)%d[i] + 1;
			if(rem>0)
			{
				ll y=0;
				cnt=0;
				mx=0;
				x=a[i];
				cnt++;
				y+=c[x];
				mx=max(mx,y);
				while(cnt<rem && x!=i)
				{
					x=a[x];
					cnt++;
					y+=c[x];
					mx=max(mx,y);
				}
				tmp+=mx;
			}		
			ans=max(ans,tmp);

			ll y=0;
			mx=-inf;
			cnt=0;
			x=a[i];
			cnt++;
			y+=c[x];
			mx=max(mx,y);
			while(cnt<k && x!=i)
			{
				x=a[x];
				cnt++;
				y+=c[x];
				mx=max(mx,y);
			}
			ans=max(ans,mx);
		}
		else
		{
			cnt=0;
			mx=-inf;
			ll y=0;
			x=a[i];
			cnt++;
			y+=c[x];
			mx=max(mx,y);
			while(cnt<k && x!=i)
			{
				x=a[x];
				cnt++;
				y+=c[x];
				mx=max(mx,y);
			}
			ans=max(ans,mx);
		}
	}
	prn(ans);
}

Measured memory_bytes: 3744
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<map>
#include<set>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(a) (a).begin(),(a).end()
#define PI 3.141592653589793238
#define INF 1050000000
#define INFL (long long)(4e18)

using vi = vector<int>;


int main() {

	string S;

	cin >> S;

	bool ans = true;

	int N = S.size();
	
	for (int i = 0,j = N-1; i < N; i++, j--) {
		if (S[i] != S[j])ans = false;
	}

	for (int i = 0, j = (N-1)/2-1; i < (N-1)/2; i++, j--) {
		if (S[i] != S[j])ans = false;
	}

	for (int i = (N+3)/2 -1,j = N-1; i < N; i++, j--) {
		if (S[i] != S[j])ans = false;
	}

	cout << ((ans) ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a,b = LI()

    return max([a+b,a-b,a*b])




print(main())



Measured memory_bytes: 7496
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll x;
  cin >> x;
  vector<ll> a;
  ll m = 5000;
  REP(i, m + 1) {
    ll t = pow(i, 5);
    a.push_back(t);
    if (i == 0) {
      continue;
    }
    a.push_back(-t);
  }
  sort(ALL(a));
  REP(i, SZ(a)) {
    ll q = a[i];
    ll qq = i - 5000;
    auto it = lower_bound(ALL(a), q + x);
    if (it != a.end() && *it == q + x) {
      cout << distance(a.begin() + m, it) << " " << qq << endl;
      return 0;
    }
  }
}

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

using namespace std;

//------------------------------- Libraries --------------------------------//

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//akari : 1D, yukari : 2D, maki : 3D vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//akane : ascending order, aoi : decending order
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Dubug Functions ---------------------------//
inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}
//------------------------------- Solver ------------------------------------//

void solve()
{
    int n;
    cin >> n;
    akari<double> dp(n + 1);
    dp[0] = 1;
    for (int _ = 0; _ < n; _++)
    {
        double p;
        cin >> p;
        akari<double> nx(n + 1);
        nx[0] = dp[0] * (1 - p);
        for (int i = 1; i <= n; i++)
        {
            nx[i] = dp[i] * (1 - p) + dp[i - 1] * p;
        }
        swap(dp, nx);
    }
    cout << setprecision(12) << accumulate(dp.begin() + (n + 1) / 2, dp.end(), 0.) << endl;
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mxN = 2e5 + 5;
const int INF = 1e9 + 7;

int n, d1, d2;

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> d1 >> d2;
		if (d1 == d2)
			++cnt;
		else
			cnt = 0;
		if (cnt == 3)
		{
			cout << "Yes";
			return 0;
		}
	}
	if (cnt == 3)
	{
		cout << "Yes";
		return 0;
	}
	cout << "No";
	return 0;
}
//19-09-2020 19:58:11

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7;

int32_t main()
{
	IO_OP;
	
	int n, k;
	cin >> n >> k;
	if(k & 1){
		int ans = 1;
		for(int i=0;i<3;i++)
			ans *= n/k;
		cout << ans << endl; 
	} else {
		int ans1 = 1, ans2 = 1;
		for(int i=0;i<3;i++)
			ans1 *= n/k;
		for(int i=0;i<3;i++)
			ans2 *= ((n+k/2)/k);
		cout << ans1 + ans2 << endl;
	}  
	
}



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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    string S;
    cin >> S;

    cout << ((S == "ARC")? "ABC":"ARC") << endl;
}


Measured memory_bytes: 3560
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>

using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> vec(m);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a>> b;
        vec[i]=make_pair(b,a);
    }
    sort(vec.begin(),vec.end());
    int count=1;
    int ins=vec[0].first;
    for(int i=0;i<m;i++){
        if(ins<=vec[i].second){
            count++;
            ins = vec[i].first;
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 1024
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

tt = list(t)
d = {'r':p, 's': r, 'p':s}
dp = [d[t[i]] for i in range(n)]

for i in range(n-k):
    if tt[i]==tt[i+k]:
        dp[i+k] = 0
        tt[i+k] = 'x'

print(sum(dp))



Measured memory_bytes: 10688
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector <int > a;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int x;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		a[i] -= x;
	}
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += max(0, a[i]);
	
	cout << sum;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 400010


int main() {
	int a[N];
	int mi[N];
	int ma[N];
	priority_queue<pair<int,int> >mis;
	priority_queue<pair<int, int> >mas;

	int n, k;
	int x, y, z;
	int s, ans;
	bool v = true;
	ans = 0;
	scanf("%d %d",&n,&k);
	f(i, n) {
		scanf("%d", &a[i]);
	}
	f(i, k) {
		mis.push(make_pair(-a[i], i));
		mas.push(make_pair(a[i], i));
	}
	x = -mis.top().first;
	y = mas.top().first;
	mi[0] = x;
	ma[0] = y;
	f(i, n - k) {
		mis.push(make_pair(-a[k+i], k+i));
		mas.push(make_pair(a[k+i], k+i));
		x= mis.top().second;
		while (x <= i) {
			mis.pop();
			x = mis.top().second;
		}
		x = mas.top().second;
		while (x <= i) {
			mas.pop();
			x = mas.top().second;
		}
		x = -mis.top().first;
		y = mas.top().first;
		mi[i + 1] = x;
		ma[i + 1] = y;
	}
	ans = n - k + 1;
	f(i, n - k) {
		if ((mi[i] == a[i]) && (ma[i + 1] == a[k + i]))ans--;
	}
	x = 0;
	s = 0;
	f(i, n-1) {
		if (a[i] < a[i + 1])x++;
		else x = 0;
		if (x == (k - 1))s++;
	}
	if (s > 0)ans -= (s - 1);
	printf("%d\n", ans);
	return 0;
}

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

static const int MAX=100;

int main(){
    int N; cin >> N;
    vector<int> D;
    D.push_back(0);
    for(int i=0;i<N;i++){
        int d; cin >> d;
        D.push_back(d);
    }
    sort(D.begin(),D.end());
    vector<int> ans;
    ans.push_back(0);
    for(int i=1;i<D.size();i++){
        if(i%2==1) ans.push_back(D[i]);
        else ans.push_back(24-D[i]);
    }
    /*
    for(int i=0;i<ans.size();i++){
        cout << ans[i] << endl;
    }
    */
    sort(ans.begin(),ans.end());
    ans.push_back(24);
    int a=100;
    for(int i=0;i<ans.size()-1;i++){
        a=min(ans[i+1]-ans[i],a);
    }
    cout << a << endl;
}

Measured memory_bytes: 256
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

a.sort()

d = []
for i in range(m):
	d.append([int(i) for i in input().split()])
	
d.sort(key = lambda x: x[1])
d.reverse()
i = 0

for j in range(n):
	if a[j] < d[i][1]:
		d[i][0] -= 1
		a[j] = d[i][1]
		if d[i][0] == 0:
			i += 1
			if i == m:
				break
				
print(sum(a))


Measured memory_bytes: 26956
n = gets.to_i
a = gets.split(' ').map{ |a| a.to_i }
sunuke = 0
arai = a.inject(:+)
ans = Array.new(n, Float::INFINITY)

n.times do |i|
  v = a.shift
  break if a.empty?
  sunuke += v
  arai -= v
  ans[i] = (sunuke - arai).abs
end

puts ans.min


Measured memory_bytes: 16772
#include <stdio.h>
int main(){
	long long int Q[5];
	long long int Qex[5];
	int i,j;
	long long int min;
	long long int N,result=0;
	scanf("%lld%lld%lld%lld",&Q[0],&Q[1],&Q[2],&Q[3]);
	scanf("%lld",&N);	
	
	N=N*4;//整数リットルに変
	
	Qex[0]=8*Q[0];
	Qex[1]=4*Q[1];
	Qex[2]=2*Q[2];
	Qex[3]=Q[3];
	min=Qex[3];
	for(i=2;i>=0;i--)
	{
		if(min>=Qex[i]){
			min=Qex[i];
			}
	}
	
	if(min==Qex[3])
	{
		result=result+Q[3]*(N-N%8)/8;
	    N=N%8;
	    min=Qex[2];
	for(i=1;i>=0;i--)
	{
		if(min>=Qex[i]){
			min=Qex[i];
			}
	}
	}
	
	if(min==Qex[2])
	{
		result=result+Q[2]*(N-N%4)/4;
	    N=N%4;
	    min=Qex[1];
	for(i=0;i>=0;i--)
	{
		if(min>=Qex[i]){
			min=Qex[i];
			}
	}
	}
	
	if(min==Qex[1])
	{
		result=result+Q[1]*(N-N%2)/2;
	    N=N%2;
	    min=Qex[0];
	}
	
	if(min==Qex[0])
	{
		result=result+Q[0]*N;
	}
	
	printf("%lld",result);
	}

Measured memory_bytes: 128
#pragma GCC optimize("Ofast,fast-math,unroll-loops,inline,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,avx,avx2,abm,mmx,popcnt")

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>

using namespace std;
#define pb push_back
#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    int mn10 = 1e18;
    int sum = 0;
    while (n--) {
        int x;
        cin >> x;
        sum += x;
        if (x % 10) mn10 = min(mn10, x);
    }
    if (mn10 == 1e18) {
        cout << 0;
    } else if (sum % 10 == 0) {
        cout << sum - mn10;
    } else {
        cout << sum;
    }


}

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

int main(){
	int n,m[1000],g = 0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> m[i];
	}
	for(int o = 0; o < n; o++){
		sort(m,m+o+1);
		for(int j = 0; j < n;j++){

			if(j)cout << " ";
			cout << m[j];
		}
	cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ep emplace_back
#define st first
#define sc second

using namespace std;

const ll mod = 998244353;
const int e = 1e6 + 69;
const int base = 311;

// dung igt thay cho gt luc tinh giai thua
// 3
// cach tao hoan vi tu n so : n*(n+1)/2;

ll s[e];
int a, b, n;


int main()
{
    cin >> n;
    vector<ll>kt(100);
    ll dem = 0;
    bool chk = false;
    ll cur = 0;
    for(int i=1; i<=n; i++)
    {
        cin >> s[i];
        if(s[i] >0 && s[i] < 400 && kt[1] == 0)
        {
            dem ++;
            kt[1] ++;
        }
        else if(s[i] >399 && s[i] < 800 && kt[2] == 0)
        {
            dem ++;
            kt[2] ++;
        }
        else if(s[i] >799 && s[i] < 1200 && kt[3] == 0)
        {
            dem ++;
            kt[3] ++;
        }
        else if(s[i] >1119 && s[i] < 1600 && kt[4] == 0)
        {
            dem ++;
            kt[4] ++;
        }
        else if(s[i] >1599 && s[i] < 2000 && kt[5] == 0)
        {
            dem ++;
            kt[5] ++;
        }
        else if(s[i] >1999 && s[i] < 2400 && kt[6] == 0)
        {
            dem ++;
            kt[6] ++;
        }
        else if(s[i] >2399 && s[i] < 2800 && kt[7] == 0)
        {
            dem ++;
            kt[7] ++;
        }
        else if(s[i] >2799 && s[i] < 3200 && kt[8] == 0)
        {
            dem ++;
            kt[8] ++;
        }
        else if(s[i] > 3199)
        {
            cur ++;
            dem ++;
        }
    }
    cout << max(dem - cur, 1LL)   <<" "<<dem;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

int main(){
  ll N;
  cin>>N;
  
  for(ll i=sqrt(N); i>=1; i--){
    if(N%i==0){
      cout<<i+N/i-2<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
# this is the third task 
from collections import defaultdict
N=int(input())
n=1
s=3
brkLoop=False
while True :
    r=(s)**2-(1)-(1)-(n)
    if ( r >= N ):
        break;  
    else:
        n=n+1   
        s=s+1
out=defaultdict(list)
for (x,y,z) in tuple((i,j,k) for i in range(1, n+1) for j in range (1,n+1) for k in range(1,n+1)):
    r=(x+y+z)**2-(x*y)-(y*z)-(x*z)
    if ( r <= N ):
        out[r].append((x,y,z))
for i in range(1,N+1):
    if ( i in out):
        print (len(out[i]))
    else:
        print(0)



Measured memory_bytes: 98180
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	int H,W;
	public void solve() {
		H = nextInt();
		W = nextInt();

		for(int i = 0;i < H;i++){
			for(int j = 0;j < W;j++){
				if(next().equals("snuke")){
					out.print((char)('A' + j));
					out.println((i + 1));
				}
			}
		}
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 8404
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int M = 1e5+10;
int dp[2][M];
int main(){
    int n,k,a;
    cin >> n >> k;
    fill(dp[0],dp[0]+M,1);
    for(int i = 1; i <= n; ++i){
        cin >> a;
        for(int j = 0; j <= k; ++j){
            int r = j;
            int l = max(j-a,0);
            dp[i&1][j] = dp[i&1^1][r] - (l ? dp[i&1^1][l-1] : 0);
            if(dp[i&1][j] < 0)dp[i&1][j] += mod;
        }
        if(i != n){
            for(int j = 1; j <= k; ++j){
                dp[i&1][j] += dp[i&1][j-1];
                if(dp[i&1][j] >= mod)dp[i&1][j]-=mod;
            }
        }
    }
    cout << dp[n&1][k];
    return 0;
}

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

const int maxV = 90010;

 
const int maxN = 1e5+10;

const int INF = 1e9+6;
const int MOD = 1e9+7;


int n,k;
int a[maxN];
int b[maxN];
ll gcd(ll x,ll y)
{
	if(y == 0)
		return x;
	else
		return gcd(y,x%y);
}
int cnt = 0;
int main() {
	ll p,q;
	scanf("%lld%lld",&p,&q);
	ll z = gcd(p,q);
	
	ll u = z;
	vector<int> v;
	v.push_back(1);
	for(int i=2;i<=sqrt(z);i++)
	{
		while(u%i == 0)
		{
			v.push_back(i);
			u /= i;
		} 
	}
	v.push_back(u);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int ans = v.size();
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr0=limii()
arr=sorted(arr0)

#print(arr)

cenleft=arr[n//2 -1]
cenright=arr[n//2]
for i in range(n):
    if arr0[i]==cenleft:
        print(cenright)
    elif arr0[i]==cenright:
        print(cenleft)
    elif arr0[i]>=cenright:
        print(cenleft)
    else:
        print(cenright)



Measured memory_bytes: 110928
/*
Author: Sanskar Agarwal
Nick: sanskarag
Birla Institute Of Technology, Mesra
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define RF(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
#define INF 100009
#define mod 1000000007
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define test while(t--)solve();

void solve()
{
	int s, w;
	cin >> s >> w;
	if (w >= s)
		cout << "unsafe" << endl;
	else
		cout << "safe" << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("../input.txt", "r", stdin);
	freopen("../output.txt", "w", stdout);
#endif
	fast
	int t;
	// cin >> t;
	t = 1;
	test
	return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;

int main() {
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> a(m);
    rep(i,m) cin >> a[i];
    int zero = 0, nn= 0;
    rep(i,m) {
        if(a[i]<x) zero++;
        else nn++;
    }
    cout << min(zero, nn) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 100005
vector<int> adj[mx], idx[mx];
int ans[mx];
void dfs(int u, int p, int prv)
{
	int put = 1;
	for (int i = 0; i < adj[u].size(); i++)
		{
			int v = adj[u][i];
			int id = idx[u][i];
			if (v == p) continue;
			if (put == prv) put++;
			ans[id] = put;
			dfs(v, u, put);
			put++;
		}
}
int deg[mx] = {0};
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, a, b;
	cin >> n;
	int xxx = 0;
	for (int i = 1; i < n; i++)
		{
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
			idx[a].push_back(i);
			idx[b].push_back(i);
			deg[a]++; deg[b]++;
			xxx = max(xxx, max(deg[a], deg[b]));
		}
	int go = 0;
	for (int i = 1; i <= n; i++) if (deg[i] == xxx) go = i;
	cout << xxx << endl;
	dfs(go, -1, -1);
	for (int i = 1; i < n; i++) cout << ans[i] << endl;
}

Measured memory_bytes: 13696
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;
typedef pair<int,int> pi;

const int N=200005;
int R,C;
int ID(){
	static int x,y;
	scanf("%d%d",&x,&y);
	if(x!=R&&x!=0&&y!=C&&y!=0)return -1;
	if(y==0)return x;
	if(x==R)return y+R;
	if(y==C)return R+C+R-x;
	return R+C+R+C-y;
}

int n,m,vi[N],le;
pi v[N];

int main(){
	scanf("%d%d%d",&R,&C,&n);
	for(int i=1;i<=n;i++){
		int a=ID(),b=ID();
		if(a==-1||b==-1)continue;
		if(a>b)swap(a,b);
		v[++m]={a,i},v[++m]={b,-i};
	}
	sort(v+1,v+m+1);
	for(int i=1;i<=m;i++){
		if(v[i].se>0)vi[++le]=v[i].se;
		else if(vi[le]!=-v[i].se)puts("NO"),exit(0);
		else vi[le--]=0;
	}
	puts("YES");
	return 0;
}

Measured memory_bytes: 2048
N = int(input())
A = [int(i) for i in input().split()]

S = [0] * (N + 1)
for i in range(1, N+1):
    S[i] = S[i-1] + A[i-1]

dict = {}
for i in range(N+1):
    s = S[i]
    if s not in dict:
        dict[s] = 1
    else:
        dict[s] += 1

ans = 0
for s in dict.values():
    ans += s * (s - 1) // 2

print(ans)

Measured memory_bytes: 41452
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
  int n,i,j,k,orderlen,strlen;
  string order,str,tempstr1,tempstr2;
  char temp;
  cin >> n;
  for(i=0;i<n;i++){
    cin >> order;
    reverse(order.begin(),order.end());
    cin >> str;
    orderlen=order.size();
    strlen=str.size();
    for(j=0;j<orderlen;j++){
      if(order[j]=='J'){
	temp=str[strlen-1];
	for(k=strlen-1;k>=1;k--){
	  str[k]=str[k-1];
	}
	str[0]=temp;
      }
      else if(order[j]=='C'){
	temp=str[0];
	for(k=0;k<strlen-1;k++){
	  str[k]=str[k+1];
	}
	str[strlen-1]=temp;
      }
      else if(order[j]=='E'){
	tempstr1=tempstr2="";
	for(k=0;k<strlen;k++){
	  if(k<strlen/2) tempstr1+=str[k];
	  else tempstr2+=str[k];
	}
	str="";
	str+=tempstr2;
	str+=tempstr1;
	if(strlen%2==1){
	  temp=str[0];
	  for(k=0;k<strlen/2;k++){
	    str[k]=str[k+1];
	  }
	  str[strlen/2]=temp;
	}
      }
      else if(order[j]=='A'){
	reverse(str.begin(),str.end());
      }
      else if(order[j]=='P'){
	for(k=0;k<strlen;k++){
	  if('1'<=str[k]&&str[k]<='9') str[k]-=1;
	  else if(str[k]=='0') str[k]='9';
	}
      }else{//M
	for(k=0;k<strlen;k++){
	  if('0'<=str[k]&&str[k]<='8') str[k]+=1;
	  else if(str[k]=='9') str[k]='0';
	}
      }
    }
    cout << str << endl;
  }
  return 0;
}

Measured memory_bytes: 1208
import Data.Array
import Data.Array.ST

counter::Int -> [(Int,Int)] -> Array Int Int
counter n path = runSTArray $ do
              ar<-newArray (1,n) 0
              mapM_ (writer ar) path
              return ar
                where writer ar (a,b) = do
                                v<-readArray ar a
                                writeArray ar a (v+1)
                                v<-readArray ar b
                                writeArray ar b (v+1)

n_get::Int ->IO [(Int,Int)]
n_get 0 =return []
n_get n =do
  d<-getLine
  let a:b:[]= map read (words d)
  rest <- n_get (n-1)
  return ((a,b):rest)

print_n::[Int] -> IO()
print_n []= return ()
print_n (x:xs)=do
  print x
  print_n xs

main::IO()
main=do
  nmc<-getLine
  let n:m:[]=map read (words nmc)
  dat<-n_get m
  print_n (elems (counter n dat))


Measured memory_bytes: 1020
#include<iostream>
using namespace std;
#include<string>
#define REP(i,a,b) \
for(int i=a; i<b; i++)
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long int
typedef vector<int> vi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define present(c,x) ((c).find(x) != (c).end())
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end();i++)
int main()
{
	string s;
	cin >> s;
	int n = s.length();
	if(s[0] != 'A')cout << "WA";
	else
	{
		int count = 0;
		REP(i,2,n-1)
		{
			if(s[i] == 'C')
			{
				count++;
			}
		}
		if(count != 1)cout << "WA";
		else
		{
			count = 0;
			REP(i,0,n)
			{
				if(s[i] <= 'Z')
					count++;
			}
			if(count > 2)cout << "WA";
			else cout << "AC";
		}
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
#define P pair<int, int>
using namespace std;
int main(void){
    ll N ;
    cin >> N ;
    ll a[N] ;
    for(int i = 0 ; i < N ; i++){
        cin >> a[i] ;
    }
    sort(a , a+ N ) ;
    ll now = a[0] ;
    ll count = 1 ; 
    ll ans = 0 ;
    for(int i = 0 ; i < N -1  ; i++ ){
        if(a[i+1] == now){
            count ++ ;
        }else{
            if(count >= now){
                ans += count - now ;
            }else{
                ans += count ;
            }
            count = 1 ;
            now = a[i+1] ;
        }
    }
    if(count >= now){
                ans += count - now ;
            }else{
                ans += count ;
            }
    

    cout << ans << endl;


    
    }
    
  

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll              long long int
#define ull             unsigned long long int
#define mod             1000000007 
#define pb              push_back
#define mp              make_pair
#define count_1(n)      __builtin_popcountll(n) //set bits
#define fr              first
#define sc              second

bool isPrime(ll n) {

  if (n == 1) {
    return false;
  }

  for (ll i = 2; i*i <=n; i++) {
    if (n % i == 0) return false;
  }

  return true;
}

 
   
ll power(ll x, ll y, ll p)  
{  
    ll res = 1;     
    x = x % p;  
                
    if (x == 0) return 0;  
  
    while (y > 0)  
    {  
        if (y & 1)  
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
} 

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        if (arr[mid] == x) 
            return mid; 
  
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    return -1; 
} 



int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin>>s;
    cout<<s;
    if(s[s.size()-1]=='s')
        cout<<"es";
    else
        cout<<"s";
}

Measured memory_bytes: 3672
#include <iostream>
#include <bits/stdc++.h>
#include <iomanip>
#include<math.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
int  main(){
  ios_base::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
    ll x,i,j,a,b,flag=1;
    cin>>x;
    for(i=0;i<125;i++){
      for(j=-125;j<i;j++){
        a=i*i*i*i*i;
        b=j*j*j*j*j;
        if(a-b==x){
          flag=0;
          break;
        }
      }if(!flag) break;
    }
    cout<<i<<" "<<j<<endl;
  }


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define INF INT_MAX
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
char s[100005];
int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   cin>>s;
   int ans=0;
   SFOR(i,1,strlen(s)){
    if(s[i]==s[i-1]){
      ans++;
      if(s[i]=='0') s[i]='1';
      else s[i]='0';
    }
   }
   cout<<ans<<endl;
   return 0;
}


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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;

constexpr int MOD = 1000000007;

ll mpow(ll m, ll n) {
    if (n == 0) { return 1; }
    if (n % 2 == 1) { return (m * mpow(m, n - 1)) % MOD; }
    ll sub = mpow(m, n / 2);
    return (sub * sub) % MOD;
}

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

    int m, n;
    cin >> m >> n;
    cout << mpow(m, n) << endl;

    return 0;
}


Measured memory_bytes: 3156
row = input().split(' ')
n = int(row[0])
a = int(row[1])
b = int(row[2])
s = input()
passed_kokunai = 0
passed_kaigai = 0
ans = list()
for i, ch in enumerate(s):
    if passed_kokunai + passed_kaigai >= a + b:
        ans.append('No')
        continue
    if ch == 'a':
        ans.append('Yes')
        passed_kokunai += 1
    elif ch == 'b' and passed_kaigai < b:
        ans.append('Yes')
        passed_kaigai += 1
    else:
        ans.append('No')
for elem in ans:
    print(elem)

Measured memory_bytes: 4792
#include<bits/stdc++.h>
using namespace std;
int main()
{
 	int n,m,i,sum=0;
 	cin>>n>>m;
 	int a[n];
 	for(i=0;i<m;i++)
 	{
 		cin>>a[i];
 		sum+=a[i];
	 }
	 if(sum>n)
	 cout<<"-1";
	 else
	 cout<<n-sum;
  
  return 0;
}
    

Measured memory_bytes: 3668
#include<iostream>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int cities[n+10]{};
  while(m--){
  	int a,b;
    cin >> a >> b;
    cities[a]++;
    cities[b]++;
  }
  for(int i=1;i<=n;++i){
  	cout << cities[i] << endl;
  }
return 0;
}

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

using namespace std;
typedef long long ll;

int main() {
ll R, G, B, n;
cin >> R >> G >> B >> n;
ll r, g, b, cont = 0;
for(int i=0; i<=n; i++){
r = i;

for(int j=0; j<=n; j++){
g = j;
b = (n - r*R - g*G)/B;
if(b >= 0 && n - r*R - g*G == b*B){
cont++;
}

}
}
cout << cont;

return 0;
}

Measured memory_bytes: 256
N, C = map(int, input().split())
x = []
v = []
for _ in range(N):
    xi, vi = map(int, input().split())
    x.append(xi)
    v.append(vi)
vsp = [0] * (N + 1)
vsn = [0] * (N + 1)
dprp = [0] * (N + 1)
dprn = [0] * (N + 1)
dpsp = [0] * (N + 1)
dpsn = [0] * (N + 1)
for i in range(N):
    vsp[i + 1] = vsp[i] + v[i]
    vsn[i + 1] = vsn[i] + v[N - 1 - i]
    dprp[i + 1] = max(dprp[i], vsp[i + 1] - 2 * x[i])
    dpsp[i + 1] = max(dpsp[i], vsp[i + 1] - x[i])
    dprn[i + 1] = max(dprn[i], vsn[i + 1] - 2 * (C - x[N - 1 - i]))
    dpsn[i + 1] = max(dpsn[i], vsn[i + 1] - (C - x[N - 1 - i]))
ans = max([max(dprp[i] + dpsn[N - i], dprn[i] + dpsp[N - i])
           for i in range(N + 1)])
print(ans)


Measured memory_bytes: 37852
N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)
INF = float("inf")
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -INF
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)


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

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

    vector<int> p(n);
    int cnt = 0, min = 200001;
    for (int i = 0; i < n; i++) {
        cin >> p.at(i);
        if (p.at(i) <= min) cnt++;
        if (p.at(i) < min) min = p.at(i);
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3920
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, Q; cin >> N >> Q;
	vector<int> a(N); rep(i, 0, N) { cin >> a[i]; }
	rep(i, 0, Q) {
		int x; cin >> x;
		int sum(0), l(0), ans(0);
		rep(j, 0, N) {
			sum += a[j];
			while (sum > x)sum -= a[l++];
			ans += j - l + 1;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3512
n = int(input())
s = list(input())
Count = 0
for i in range(n):
    f = list(set(s[:(i+1)]))
    r = list(set(s[(i+1):]))
    count = 0
    for j in range(len(f)):
        for k in range(len(r)):
            if f[j] == r[k]:
                count += 1
    if Count < count:
        Count = count
print(Count)

Measured memory_bytes: 3064
n,m = gets.split.map(&:to_i)
a = Hash.new(0)
n.times do
  gets.chomp.chars.each do |c|
    a[c] += 1
  end
end

b = Hash.new(0)
a.values.each do |v|
  case v % 4
  when 0
    b[4] += v / 4
  when 1,2
    b[4] += v / 4
    b[v % 4] += 1
  when 3
    b[4] += v / 4
    b[2] += 1
    b[1] += 1
  end
end

p4 = (n/2)*(m/2)
p2 = (n%2)*(m/2)+(n/2)*(m%2)
p1 = (n%2)*(m%2)

if p1 >= b[1] && p2 >= b[2]
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>    // std::sort
using namespace std;

int main(int argc, char const *argv[]) {
  int task[3];
  for (int i=0;i<3;i++)
  {
    cin >> task[i];
  }
  sort(task,task+3);
  cout << (task[1]-task[0])+(task[2]-task[1]);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}



///////////////////////////

ll N, M;
vector<ll> A;

ll ch(ll x) {//和がx以上になる組の個数を返す
	ll ans = 0;
	rep(i, N) {
		auto itr = lower_bound(A.begin(), A.end(), x - A[i]);
		ans += distance(itr, A.end());
	}
	return ans;
}


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

	A.assign(N,0);
	rep(i, N) cin >> A[i];

	sort(A.begin(), A.end());

	
	ll le = -1;
	ll ri = 300000;
	while (ri - le > 1) {
		ll m = (le + ri) / 2;
		//cout << m <<endl; 
		//cout << ch(m) << endl;
		if (ch(m) < M) { ri = m; }
		else { le = m; }
	}

	ll X = le;//和がX以上のものについて握手

	//cout << X<<endl;

	vector<ll> sum(N+1);

	sum[N] = 0;

	for (int i = N - 1; i >= 0; i--) {
		sum[i] = sum[i + 1] + A[i];
	}

	ll ans = 0;
	rep(i, N) {
		auto itr = lower_bound(A.begin(), A.end(), X - A[i]);
		ans += sum[distance(A.begin(), itr)];
		//cout << ans;
		ans += A[i] * distance(itr, A.end());
		//cout << ans << endl;
	}

	ans -= X * (ch(X) - M);

	cout << ans;

	system("PAUSE");

}


Measured memory_bytes: 2040
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>

using namespace std;

int main(){
	int A, B, C, D, x, y;
	scanf("%d", &A);
	scanf("%d", &B);
	scanf("%d", &C);
	scanf("%d", &D);

	if (A > B){
		x = B;
	}
	else{
		x = A;
	}

	if (C > D){
		y = D;
	}
	else{
		y = C;
	}

	printf("%d\n", x + y);
	return 0;
}

Measured memory_bytes: 128
n, m = map(int, input().split())
a_list = [int(i) for i in input().split()]

sort_a_list = sorted(a_list)[::-1]

for i, num in enumerate(range(m)):
    if sort_a_list[i] < sum(sort_a_list)/(4*m):
        print("No")
        exit()

print("Yes")


Measured memory_bytes: 38512
n = int(input())
t, a = map(int, input().split())
y = 0
z = 0
# aに近い値を調べる
h = list(map(int, input().split()))
for i in range(1,n+1):
  x = t - (h[i-1] * 0.006)
#  print(x)
  if y ==0:
    y=x
    z=i
  else:
    if abs(x-a) <= abs(y-a):
      y = x
      z = i
print(z)


Measured memory_bytes: 3060
#include<stdio.h>
int main(void)
{
	int n,i,four=0;
	char ara[n];

	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%c",&ara[i]);

	for(i=0;i<n;i++)
		if(ara[i]=='Y'){
			four=1;break;
		}

	if(four==1)
		printf("Four\n");
	else printf("Three\n");

	return 0;
}


Measured memory_bytes: 128
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let s = read::<String>().chars().collect::<Vec<_>>();
    let k = read::<usize>();

    for i in 0..n {
        if s[i] == s[k - 1] {
            print!("{}", s[i]);
        } else {
            print!("*");
        }
    }
    println!("");
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 2124
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static void solve() {
		int n = in.nextInt();
		int[] a = new int[n];
		for (int i=0; i<n; i++) {
			a[i] = in.nextInt();
		}

		boolean[] g = new boolean[10000];

		for (int i=0; i<10000; i++) {
			if (g[i]) continue;
			int d = 1;
			while (i / (int)Math.pow(10,d) != 0) d++;
			boolean f = false;
			for (int j=0; j<n; j++) {
				int p = 0, dig = 1;
				if (j+d-1 >= n) break;
				for (int k=j+d-1; k>=j; k--) {
					p += dig*a[k];
					dig *= 10;
				}
				g[p] = true;
				if (p == i) {
					f = true;
					break;
				}
			}

			if (!f) {
				out.println(i);
				return;
			}
		}
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 30252
N,C,K=map(int,input().split())
time=[]
for _ in range(N):
    T=int(input())
    time.append(T)
sort_time=sorted(time)
ans=1
max_N=0
max_time=sort_time[0]+K
for time in sort_time:
    if max_time==0:
        max_time=time+K
    if time<=max_time:
            max_N+=1
    else:
        ans+=1
        max_time=time+K
        max_N=1
        continue
    if max_N==C:
        ans+=1
        max_time=0
        max_N=0
if C==1:
    print(N)
else:
    print(ans)
    

Measured memory_bytes: 81484
//Sangeeta Mishra
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less
using namespace __gnu_pbds;

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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define rep(i,a,n)    for(int i=a; i<=n; ++i)
#define rep1(i,a,n)   for(int i=a; i>=n; --i)
#define pb            push_back
#define mp            make_pair
#define int           long long
#define fr            first
#define sc            second
#define vc            vector
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define rall(x)       (x).rbegin(),(x).rend()
#define N             (int)(1e6+5)
#define M             1000000007
#define MM            998244353
#define PI            3.14159265358979
#define INF           1000000000000000

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mii;

int n,m,ans; string str;

int solve(){
    int a,b,c; cin>>a>>b>>c;
    if(a==b&&b!=c) cout<<"Yes";
    else if(a==c&&a!=b) cout<<"Yes";
    else if(b==c&&a!=c) cout<<"Yes";
    else cout<<"No";
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);
    //std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

S = gets.chomp

max_count = 0
count = 0
S.split('') do |s|
  if ['A', 'C', 'G', 'T'].include?(s)
    count += 1
    max_count = count if count > max_count
  else
    count = 0
  end
end

puts max_count


Measured memory_bytes: 14340
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    arr = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14,
           1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    K = int(input())
    print(arr[K - 1])


if __name__ == "__main__":
    main()


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

int main() {
  double a, b, x;
  cin >> a >> b >> x;
  
  cout << fixed << setprecision(10);
  
  double d = 180 / acos(-1);
  if(a * b == 2 * x / a) cout << atan(b / a) * d << endl;
  else if(a * b < 2 * x / a){
    cout << atan(2 * (b - x / a / a) / a) * d << endl;
  }
  else{
    cout << atan(b / (2 * x / a / b)) * d << endl;
  }
}

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

class Main{
    public static void main(String[] args){
	BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	try{
	    int n;
	    while((n = Integer.valueOf(sc.readLine())) != 0){
		int sum=0, fact=5;
		for(int i=1; i<=n && fact<=n; i++){
		    sum+=n/fact;
		    fact*=5;
		}
		System.out.println(sum);
	    }
	}catch(Exception e){
	    System.out.println("Error");
	}
    }
}

Measured memory_bytes: 9232