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

int main(){
    ll n;  cin >> n;
    vector<ll> a(n), b(n), c(n);
        for(int i=0; i<n; i++) cin >> a.at(i);
        for(int i=0; i<n; i++) cin >> b.at(i);
        for(int i=0; i<n; i++) cin >> c.at(i);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    ll cnt = 0;
    for(int i=0; i<n; i++){
        ll body = b.at(i);
        ll topcnt = lower_bound(a.begin(), a.end(), body) - a.begin();
        ll bottomcnt = c.end() - upper_bound(c.begin(), c.end(), body);
        cnt += topcnt*bottomcnt;

    }
   
    cout << cnt << endl;

}

Measured memory_bytes: 2560
import java.io.*;
import java.nio.CharBuffer;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        int a = scanner.nextInt();
        int b = scanner.nextInt();

        writer.println(a <= 9 && b <= 9 ? a * b : -1);
        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        private void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        private char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        private String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

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

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

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

Measured memory_bytes: 23124
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;

int N, M;
int dp[310];
int solve(vector<int> cost, vector<int> value) {
  memset(dp, 0, sizeof(dp));

  int ret = 0;
  for(int i=0; i<N; i++) {
    for(int j=0; j<=M; j++) {
      int ncost = j + cost[i];
      if(ncost > M) continue;
      dp[ncost] = max(dp[ncost], dp[j] + value[i]);

      ret = max(ret, dp[ncost]);
    }
  }
  return ret;
}

int main() {
  while(cin >> N >> M) {
    vector<int> C(N), V(N), D(N), L(N);
    string s;
    for(int i=0; i<N; i++) {
      cin.ignore();
      getline(cin, s);
      
      // cin.ignore();
      // cin >> C[i] >> V[i] >> D[i] >> L[i];
      scanf(" %d%d%d%d", &C[i], &V[i], &D[i], &L[i]);
    }

    int ans = 0;
    ans = max(ans, solve(C, V));
    ans = max(ans, solve(C, D));
    ans = max(ans, solve(C, L));
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3204
#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

int freq[26];
int hasil[26];
int indx[26];
int main() {
  string m;
  cin >> m;
  
  memset(freq, 0, sizeof(freq));
  int maxfreq = 0;
  for (int i = 0; i < m.length(); i++){
    char f = m[i];
    freq[f-'a'+1]++;
    if (freq[f-'a'+1] > maxfreq){
      maxfreq = freq[f-'a'+1];
    }
  }
  
  int h = INT_MAX;
  for (int a = 1; a <= 26; a++){
    int distmax = 0;
    int f = a;
    string temp = m;

    temp = (char)(f-1+'a') + temp + (char)(f-1+'a');
    int dist = 0;
    for (int i = 0; i < temp.length(); i++){
      dist++;
      int n = temp[i] - 'a' + 1;
      if(n == f){
        distmax = max(distmax, dist-1);
        dist = 0;
      }
    }

    h = min(h, distmax);
  }

  cout << h << endl;
  return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <array>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <climits>
#include <string.h>
#include <cctype>
#include <set>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using namespace std;

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

// a と b の最大公約数を返す関数
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long gcd(long long a, long long b)
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint& operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
} comb(2000005);

mint g(int r, int c) {
	return comb(r + c + 2, r + 1) - 1;
}

bool comp(int i, int j) {
	return i > j;
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}


int main()
{
	int n, x;
	cin >> n >> x;
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		cin >> tmp;
		sum += tmp;
		if (sum > x)
		{
			cout << (i + 1);
			return 0;
		}
	}
	cout << (n + 1);
}



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

int main(){
	int N;
	int A;
	string ans="second";
	
	cin >> N;
	for(int i=0;i<N;i++)
	{
		cin >> A;
		if(A%2==1)
			ans="first";
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <utility> 
#include <unordered_set>
#include <vector>
#include <list> 
#include <string>
#include <iterator> 
#include <deque>
#include <array>
#include <forward_list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <bitset>
#include <numeric>
using namespace std;


const long double PI = 3.14159265358979323846264338327950;
const int N = 1e5+5;

template <class T>
T gcd(T a, T b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	long long n, m, k, d0, d1;
	cin >> n >> m >> k;
	n -= k;
	if (n < 0) m += n;
	cout << max(0LL, n) <<' '<< max(0LL, m) << '\n';
}
		

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxN = 11;
string s, t, u;
int a, b;
char ss[maxN], tt[maxN], uu[maxN];

int main()
{
  while (scanf(" %s %s", ss, tt) != EOF)
  {
    scanf("%d %d", &a, &b);
    scanf(" %s", uu);
    s = string(ss), t = string(tt), u = string(uu);

    a -= u == s;
    b -= u == t;
    printf("%d %d\n", a, b);
  }
  return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001


int main(){
    cin.sync_with_stdio(false);
    ll n;
    cin >> n;
    ll sq_n = sqrt(n), mini = INF;
    repl(i, 1, sq_n + 1) {
        if (n % i == 0) minch(mini, (ll)max(to_string(i).size(), to_string(n / i).size()));
    }
    cout << mini << endl;
    return 0;
}

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

using namespace std;

const long long NS = (long long)1e5 + 4;
long long N, k;
long long arr[NS];
long long sum[NS], hap[NS];

int main(){
    scanf("%lld %lld", &N, &k);
    for(long long i = 1; i <= N; ++i){
        scanf("%lld", arr + i);
        sum[i] = sum[i - 1] + arr[i];
        hap[i] = hap[i - 1] + max(0ll, arr[i]);
    }
    long long ans = 0;
    for(long long i = 1; i + k - 1 <= N; ++i){
        ans = max(ans, hap[N] - hap[i + k - 1] + hap[i - 1] + max(0ll, sum[i + k - 1] - sum[i - 1]));
    }
    printf("%lld\n", ans);
    return 0;
}


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

int main() {
    string S="";
    cin >> S;
    int mini=9999;
    for(int i=0; i<S.length()-2; i++){
        string temp = S.substr(i,3);
        int x = stoi(temp);
        int diff = x > 753 ? x-753: 753-x;
        if(diff < mini){
            mini = diff;
        } 
    }
    cout << mini << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,a,b,c,ct=0,flag;
    string p,q,r;
    cin>>a>>b>>c;
    flag=0;
    if(a==b && b!=c && a!=c) flag=1;
    else if(b==c && b!=a && c!=a) flag=1;
    else if(a==c && c!=b && a!=b) flag=1;
    if(flag==1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}





Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void)
{
	//w ,h ,x ,y ,r
	const int N = 5;
	int a[N];
	
	for(int i = 0 ; i < N ; i++)
	{
		cin >> a[i];
	}
	
	if( a[2] + a[4] > a[0] )      cout << "No";
	else if( a[2] - a[4] < 0 )    cout << "No";
	else if( a[3] + a[4] > a[1] ) cout << "No";
	else if( a[3] - a[4] < 0 )    cout << "No";
	else						  cout << "Yes";
	
	cout << endl;
	
	
	return 0;
} 



Measured memory_bytes: 3136
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        D = {}
        N = int(line.rstrip("\n"))
        for i in xrange(N):
            d = int(sys.stdin.readline().rstrip("\n"))
            D[d] = 1
        print len(D.keys())

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Measured memory_bytes: 2568
// Oh, this is a fake solution!
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <complex>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef complex<int> P;

int bitcount(int a) {
    int c = 0;
    while (a) c++, a&=a-1;
    return c;
}

inline double cross(const P& a, const P& b) { return imag(conj(a)*b); }
inline double dot(const P& a, const P& b) { return real(conj(a)*b); }

inline int ccw(const P& a, P b, P c) {
    b -= a, c -= a;
    if (cross(b, c) > 0) return 1;
    if (cross(b, c) < 0) return -1;
    if (dot(b, c) < 0) return 2;
    if (norm(b) < norm(c)) return -2;
    return 0;
}

inline bool intersectSS(const P& s0, const P& s1, const P& t0, const P& t1) {
    return ccw(s0, s1, t0) * ccw(s0, s1, t1) <= 0
        && ccw(t0, t1, s0) * ccw(t0, t1, s1) <= 0;
}

int n, g[32], m[32];
P ps[32][32];

int main() {
    for (;;) {
        scanf("%d", &n);
        if (n == 0) return 0;
        rep (i, n) {
            int x, y;
            scanf("%d", m+i);
            rep (j, m[i]) {
                scanf("%d%d", &x, &y);
                ps[i][j] = P(x, y);
            }
        }
        memset(g, 0, sizeof(g));
        rep (i, n) g[i] |= 1<<i;
        rep (i, n) rep (j, m[i]-1) rep (x, i) rep (y, m[x]-1) {
            if (intersectSS(ps[i][j], ps[i][j+1], ps[x][y], ps[x][y+1])) {
                g[i] |= 1<<x, g[x] |= 1<<i;
            }
        }
        const int nn = 1<<n;
        int ans = 0;
        rep (b, nn) {
            bool f = true;
            rep (i, n) if ((b&(1<<i)) && (g[i]&b)!=b) {
                f = false;
                break;
            }
            if (f) ans = max(ans, bitcount(b));
        }
        printf("%d\n", ans);
    }
}

Measured memory_bytes: 884
n=int(input())
import math
s= int(math.sqrt(n))+1

i=2
c1=0
c2=1
ans=0
while i<=s:
    if n%i==0:
        n//=i
        c1+=1
        if c1==c2:
            c1=0
            c2+=1
            ans+=1
    else:
        c2=1
        i+=1
        c1=0
if n>s:
    ans+=1
    
print(ans)


Measured memory_bytes: 9176
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for(int& val: arr) {
        cin >> val;
        val--;
    }
    ll ans = 0, consc = 0;
    for(int i = 0; i < n; i++) {
        if (arr[i] == i) {
            consc += 1;
        } else {
            ans += (consc+1) / 2;
            consc = 0;
        }
    }
    ans += (consc+1) / 2;
    cout << ans << endl;
    return 0;
}




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

N,K,C=map(int,input().split())
S="x"+input().strip()+"x"

N=len(S)
SUML=[0]*N
SUMR=[0]*N

NEXT=0
for i in range(N):
    if i>=NEXT and S[i]=="o":
        SUML[i]=SUML[i-1]+1
        NEXT=i+C+1
    else:
        SUML[i]=SUML[i-1]

S2=S[::-1]

NEXT=0
for i in range(N):
    if i>=NEXT and S2[i]=="o":
        SUMR[i]=SUMR[i-1]+1
        NEXT=i+C+1
    else:
        SUMR[i]=SUMR[i-1]

SUMR=SUMR[::-1]

ANS=[]
for i in range(1,N-1):
    if S[i]=="o" and SUML[i-1]+SUMR[i+1]==K-1:
        ANS.append(i)

print(*sorted(ANS))



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

using namespace std;

int main()
{
  uint64_t N;
  cin >> N;
  
  map<uint64_t, set<pair<uint64_t, uint64_t>>> edges;
  for (uint64_t n = 0; n < N - 1; ++n) {
    uint64_t a, b, c;
    cin >> a >> b >> c;
    
    edges[a - 1].emplace(b - 1, c);
    edges[b - 1].emplace(a - 1, c);
  }
  
  uint64_t Q, K;
  cin >> Q >> K;
  
  vector<uint64_t> depth(N, -1);
  depth[K - 1] = 0;
  queue<uint64_t> queue;
  queue.push(K - 1);
  while (!queue.empty()) {
    uint64_t src = queue.front(); queue.pop();
    
    for (auto pair : edges[src]) {
      if (depth[pair.first] != -1) {
        continue;
      }
      
      depth[pair.first] = depth[src] + pair.second;
      queue.push(pair.first);
    }
  }
  
  for (uint64_t q = 0; q < Q; ++q) {
    uint64_t x, y;
    cin >> x >> y;
    
    cout << (depth[x - 1] + depth[y - 1]) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 26368
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <fstream>
#include <bitset>
#include <time.h>
#include <assert.h>

#define LL long long
#define VI vector<int>
#define VVI vector<vector<int>>
#define VB vector<bool>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

const std::string YES = "YES";
const std::string Yes = "Yes";
const std::string NO = "NO";
const std::string No = "No";

using namespace std;

template <class T> int find_index(T x, const std::vector<T> &v) {
    auto it = std::find(v.begin(), v.end(), x);
    if (it != v.end()) { return (int)std::distance(v.begin(), it); }
    return -1;
}

template <class T> void print(T x) {
    std::cout << x << std::endl;
}
// 4近傍（右, 下, 左, 上）
const vector<int> dy = { 0, -1, 0, 1 };
const vector<int> dx = { 1, 0, -1, 0 };


vector<int> calc(vector<bool> use, vector<vector<int>> A) {

    vector<int> num(A[0].size(), 0);
    FOR(i, 0, A.size()) {
        FOR(j, 0, A[0].size()) {
            if (use[A[i][j]]) {
                num[A[i][j]]++;
                break;
            }
        }
    }

    return num;
}

int main(int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M, 0));
    FOR(i, 0, N) {
        FOR(j, 0, M) {
            int a;
            cin >> a;
            A[i][j] = a - 1;
        }
    }

    int ans = INT_MAX;
    vector<bool> use(M, true);
    FOR(i, 0, M) {
        vector<int> num = calc(use, A);
        int max = MAX(num);
        ans = min(ans, max);
        use[find_index(max, num)] = false;
    }

    cout << ans << endl;
}


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

#define int long long

using namespace std;

const int maxn = 3005;
int grid[maxn][maxn];
int r, c, k;
int dp[2][4][maxn][maxn];

int recur(int i, int j, int took, int flag) {
    if (i == r && j == c) return 0;
    if (dp[flag][took][i][j] != -1) return dp[flag][took][i][j];
    int res = 0;
    if (took != 3 && flag == 0) res = max(res, recur(i, j, took+1, 1) + grid[i][j]);
    if (i != r) res = max(res, recur(i+1, j, 0, 0));
    if (j != c) res = max(res, recur(i, j+1, took, 0));
    dp[flag][took][i][j] = res;
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int a = 0; a < 2; a++) for (int b = 0; b < 4; b++) for (int c = 0; c < maxn; c++) for (int d = 0; d < maxn; d++) dp[a][b][c][d] = -1;
    cin >> r >> c >> k;
    for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) grid[i][j] = 0;
    for (int i = 0; i < k; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        x--;
        y--;
        grid[x][y] = v;
    }
    int res = recur(0, 0, 0, 0);
    cout << res << '\n';
}
/*

 */

Measured memory_bytes: 638984
N, M = map(int, input().split())

g = [[0] * (N+1) for _ in range(N+1)]

for m in range(M):
    a, b = map(int, input().split())
    g[a][b] += 1
    g[b][a] += 1

for i in range(1, N+1):
    print(sum(g[i]))


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


int main() {
    std::string squares;
    std::cin >> squares;
    
    int numOfMarble = 0;
    for(unsigned long i = 0; i < squares.length(); ++i) {
        if(squares.at(i) == '1') {
            ++numOfMarble;
        }
    }
    std::cout << numOfMarble << std::endl;
}

Measured memory_bytes: 3600
def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end

  return last_remainder, last_x * (a < 0 ? -1 : 1)
end

def modinv(e, et)
  g, x = extended_gcd(e, et)
  if g != 1
    raise 'The maths are broken!'
  end
  x % et
end

require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
n,a,b = gets.chomp.split.map(&:to_i)
require 'openssl'

def all(n)
  ret = 2.to_bn.mod_exp(n, MOD) - 1
  ret
end

def nck(n,k)
  ans = 1
  k.times do |i|
    ans = ans * (n-i) % MOD
    ans = ans * modinv(i+1, MOD) % MOD
  end
  ans
end

ans = all(n) - nck(n,a) - nck(n,b)
while ans < 0
  ans += MOD
end
puts (ans + MOD)%MOD


Measured memory_bytes: 3452
s = input()
x = len(s)
y = 0
z = 0
a = x - 1
while(y <= x):
  if (s[y] == "A"):
    z = y
    break
  y += 1
while(y <= x):
  if (s[a]  == "Z"):
    print(str(a - z + 1))
    break
  a -= 1
  y += 1

Measured memory_bytes: 3512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using namespace std;
using namespace __gnu_pbds;
typedef vector <int> vi;
typedef pair <int, int> ii;

const int INF = 1 << 30;
const int maxn = 100010;

int main() {
#ifdef BZ
    freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(6);

    int n;
    cin >> n;

    vi a (2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> a[i];
    }

    sort (a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < 2 * n; i += 2) {
        ans += a[i];
    }
    cout << ans << "\n";


}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{VecDeque, HashSet, BTreeSet, BinaryHeap, HashMap};
#[allow(unused_imports)]
use std::io::{stdin, stdout, Write, BufReader, BufWriter};
#[allow(unused_imports)]
use std::io::prelude::BufRead;


fn main() {
    let vec = read_vector::<i64>();
    let (n, t) = (vec[0], vec[1]);

    let mut heap = BinaryHeap::<i64>::new();
    for _ in 0..n {
        let vec = read_vector::<i64>();
        let (a, b) = (vec[0], vec[1]);
        if b > t {
            continue;
        }
        heap.push(a * (-1));
    }

    if heap.len() == 0 {
        println!("TLE");
    } else {
        println!("{}", heap.pop().unwrap() * (-1));
    }
}

#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .trim()
        .parse()
        .unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::with_capacity(100);
    stdin().read_line(&mut buf).unwrap();
    return buf
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    use std::io::prelude::*;
    let stdin = stdin();
    let mut reader = BufReader::with_capacity(100 * 1024, stdin);
    let mut line = String::with_capacity(100);
    let mut matrix: Vec<Vec<T>> = Vec::new();

    while reader.read_line(&mut line).unwrap() > 0 {
        matrix.push(line
            .trim()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect());
        line.clear();
    }

    return matrix;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
 
int main() {
   int a,b,c;
   cin>>a>>b>>c;
   set<int> s;
   s.insert(a);    s.insert(b);
    s.insert(c);
    if (s.size()==2) cout<<"Yes"<<endl; else cout<<"No"<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007,INF=1e18;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

#define int ll

int n,x;
int a[200020];
int cnt=1;
signed main(){
    cin>>n>>x;
    if(x==1 || x==2*n-1){
        cout<<"No"<<endl;
        return 0;
    }
    
    rep(i,0,n*2-1)a[i]=i+1;
    swap(a[x-1],a[n-1]);
    swap(a[0],a[n-2]);
    swap(a[2*n-2],a[n]);
    cout<<"Yes"<<endl;
    rep(i,0,2*n-1)cout<<a[i]<<endl;
}


Measured memory_bytes: 3072
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    int N, M;
    cin >> N >> M;

    int ans = (1 << M) * (1900 * M + (N - M) * 100);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
int main(){

int n;
cin >> n;
 n = n%10;
 if(n==3) cout << "bon";
 else if(n==0||n==1||n==6||n==8)  cout <<"pon";
 else cout << "hon";

 return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;
constexpr long long int INF = std::numeric_limits<long long int>::max();
constexpr long long int NINF = std::numeric_limits<long long int>::min();
#define int long long int

vector<int> dist(100001, -1);
vector<vector<pair<int, int>>> E(100001);

void dfs(int pos) {
  for (pair<int, int> &p : E[pos]) {
    if (dist[p.first] >= 0) {
      continue;
    }

    dist[p.first] = dist[pos] + p.second;
    dfs(p.first);
  }
}

void solve() {
  int N;
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    E[a].emplace_back(b, c);
    E[b].emplace_back(a, c);
  }

  int Q, K;
  cin >> Q >> K;

  dist[K] = 0;
  dfs(K);

  for (int i = 0; i < Q; i++) {
    int x, y;
    cin >> x >> y;
    cout << dist[x] + dist[y] << endl;
  }
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


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

#define int long long
#define pb emplace_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(0);

int32_t main(){
	fast;
	int r;
	cin >> r;
	cout << r*r;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int x, a, b;
    cin >> x >> a >> b;

    int A = 0, B = 0;
    a > x ? A = a - x : A = x - a;
    b > x ? B = b - x : B = x - b;
    
    if (A < B){
        cout << 'A' << endl;
    }
    else{
        cout << 'B' << endl;
    }
}

Measured memory_bytes: 256
import math
def yogen(b,c,sita):
    a2 = b**2 + c**2 - 2*b*c*math.cos((sita/180)*math.pi)
    a = math.sqrt(a2)
    return a

def jisin(h,m):
    return 0.5*(m+h*60)

def hunsin(m):
    return 6*m

a,b,h,m = map(int,input().split())

print(yogen(a,b,jisin(h,m)-hunsin(m)))

Measured memory_bytes: 62552
#include <bits/stdc++.h>  // ver2.2.2
#define int long long
#define endl "\n"
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Pii pair<int,int>
#define VPii vector<Pii>
#define Tiii tuple<int,int,int>
#define PQi priority_queue<int>
#define PQir priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define itos to_string
#define stoi stoll
#define FI first
#define SE second
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define sortr(v) sort(v,greater<>())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define dem(a,b) ((a+b-1)/(b))
#define Vin(a) rep(iI,0,a.size())cin>>a[iI]
#define Vout(a) rep(lZ,0,a.size()-1)cout<<a[lZ]<<' ';cout<<a.back()<<endl
#define VVout(a) rep(lY,0,a.size()){Vout(a[lY]);}
#define VPout(a) rep(lX,0,a.size())cout<<a[lX].FI<<' '<<a[lX].SE<<endl
#define INF 3000000000000000000  //  3.0*10^18(MAXの1/3くらい)
#define MAX LLONG_MAX
#define MOD 1000000007  //  10^9 + 7
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm
void uniq(Vi &v){sort(ALL(v)); v.erase(unique(ALL(v)),v.end());}  //  uniqのやつ

int mypow(int x, int n, int m){  //  累乗x^n(mod m)  O(log(n))
if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}



signed main() {
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(12);
  int n;
  cin >> n;
  Vi a(n);
  Vin(a);
  
  if(a[0]!=0) {cout<<-1<<endl;return 0;}
  rep(i,0,n-1){
    if(a[i] < a[i+1] && a[i+1]-a[i]>=2) {cout<<-1<<endl;return 0;}
  }
  
  reverse(ALL(a));
  int ans = 0,ct=0;
  
  rep(i,0,n){
    ct=0;
    if(a[i]==0) continue;
    repreq(j,a[i],0){
      if(a[i+ct]==j) ct++;
      else break;
    }
    ans += a[i];
    i += ct-1;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int h, w, n;
  cin>>h>>w>>n;
  cout<<((n-1)/max(h, w)+1)<<'\n';
  return 0;
}


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

int main()
{
  int n;
  cin >> n;
  
  int cnt=0;
  bool flag=true;
  vector<int> num(n);
  
  for(int i=0; i<n; i++)
  {
    int tmp;
    cin >> num.at(i);
    
    
    if(num.at(i) % 2 != 0 || num.at(i) == 0)
    {
      flag = false;
      break;
    }
  }
  
  if(flag)
  {
    while(flag)
    {
      for(int i=0; i<n; i++)
      {
        num.at(i) /= 2;
        
        if (num.at(i) % 2 != 0)
        {
          flag = false;
          break;
        }
      }
      cnt++;
    }
  }
  
  if(cnt < 0) cnt = 0;
  cout << cnt << endl;
}

Measured memory_bytes: 3568
O = input()
E = input()
PASS = ''
if len(O)-len(E)==0:
  for i in range(len(O)):
   PASS += O[i]
   PASS += E[i]
else:
  for i in range(len(E)):
    PASS += O[i]
    PASS += E[i]
  PASS += O[-1]
print(PASS)

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

class Dinic{
public:
  
  struct edge{
    int to,cap,rev;
    edge(){};
    edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){};
  };

  int V;
  vector<vector<edge> > G; //グラフの隣接リスト表現
  vector<int> level;       //sからの距離
  vector<int> iter;        //どこまで調べ終わったか
  int INF;
  
  Dinic():V(-1){};
  Dinic(int V,int INF=1e9):V(V),G(V),level(V),iter(V),INF(INF){}

  //fromからtoへ向かう容量capの辺をグラフに追加。
  void add_edge(int from,int to,int cap){
    assert(from < V && to < V);
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
  }

  //sからの最短距離をBFSで計算する
  void bfs(int s){
    level.clear(); level.resize(V,-1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
      int v = que.front(); que.pop();
      for(edge &e : G[v])
        if(e.cap > 0 && level[e.to] < 0){
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
    }
  }

  //増加パスをDFSで探す。
  int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i= iter[v]; i<(int)G[v].size(); i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[v] < level[e.to]){
        int d = dfs(e.to, t, min(f, e.cap));
        if(d > 0){
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

  //sからtへの最大流を求める
  int max_flow(int s,int t){
    assert(V >= 0);
    int flow=0;
    for(;;){
      bfs(s);
      if(level[t] < 0) return flow;
      iter.clear();iter.resize(V,0);
      int f;
      while((f=dfs(s ,t ,INF)) > 0 ) flow += f;
    }
  }
};

typedef pair<int,int> P;
typedef pair<int,P> P1;

const int INF = 1e9;

int n, m, s, t;
vector<P1> G[205], rG[205];

int d[205];

void dijkstra(){
  
  for(int i=0;i<n;i++) d[i] = INF;
  
  priority_queue<P,vector<P>,greater<P> > q;
  
  d[s] = 0;
  q.push(P(0, s));

  while(!q.empty()){
    
    P tmp = q.top(); q.pop();
    
    int node = tmp.second;
    int cost = tmp.first;

    if( d[node] < cost ) continue;
    
    for(P1 p : G[node] ){
      
      int nnode = p.first;
      int ncost = cost + p.second.first;
      
      if( d[nnode] > ncost ){
	d[nnode] = ncost;
	q.push(P(ncost, nnode));
      }
      
    }
    
  }

}

Dinic din;

int used[205];

void dfs(int x){
  
  if( used[x] ) return ;
  used[x] = 1;
  
  for(P1 p : rG[x]){
    
    int nx = p.first;
    int cost = p.second.first;
    int cap = p.second.second;
    
    if( d[x] - cost == d[nx] ){
      din.add_edge( nx, x, cap );
      dfs( nx );
    }
    
  }
  
}

signed main(){
  
  cin>>n>>m>>s>>t;
  s--, t--;
  
  for(int i=0;i<m;i++){
    
    int u, v, d, c;
    cin>>u>>v>>d>>c;
    
    u--, v--;
    
    G[u].push_back(P1(v, P(d, c)));
    rG[v].push_back(P1(u, P(d, c)));
  }
  
  dijkstra();

  din = Dinic(n);
  
  dfs(t);
  
  cout<<din.max_flow(s, t)<<endl;
  
  return 0;
}



Measured memory_bytes: 3248
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const ll INF = 2e15;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main(){
  ll n, m;
  cin >> n >> m;
  ll count = 0;
  if(2*n>=m){
    print(m / 2);
    return 0;
  }
  count += n;
  m -= 2 * n;
  count += m / 4;
  print(count);
}


Measured memory_bytes: 3616
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 1e5;
int N, K, X[Nmax];

int main(){
	cin >> N >> K;
	for(int i=0; i<N; i++) cin >> X[i];

	int ans = 1e9;
	for(int i=0; i<N-K+1; i++){
		if(X[i+K-1]<=0) ans=min(ans, -X[i]);
		else if(X[i]>=0) ans=min(ans, X[i+K-1]);
		else ans = min(ans, min(-2*X[i]+X[i+K-1], -X[i]+2*X[i+K-1]));
	}

	cout << ans << endl;

	return 0;
}


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

using namespace std;
typedef long long ll;
#define MOD 1000000007
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

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

    ll A[n];
    for(int i=0; i<n; i++) cin >> A[i];

    ll sum = 0;
    ll cnt[61];
    for(ll b=0; b<61; b++) cnt[b] = 0;
    for(ll i=0; i<n; i++)
        for(ll b=0; b<61; b++)
            if(A[i] & (1ull<<b)) cnt[b]++;
    for(ll b=0; b<61; b++) {
        ll m = ((cnt[b] * (n-cnt[b]) % MOD) * ((1ull<<b) % MOD)) % MOD;
        sum += m;
        sum %= MOD;
    }

    cout << sum << endl;


    return 0;
}

Measured memory_bytes: 2560
//#include <fsociety>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
//end of libraries ;
#define INF 99999999999
#define N 2002
#define F first
#define S second
#define pb push_back
#define ll long long
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int n;
int main(){
fcin;
  	cin>>n;
  cout<<n/2+(n%2);

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
signed main(){
  ll n,m;
  ll a[100000],b[100000],c[100000],d[100000],sum[100000];
  cin>>n>>m;
  vector<pair<ll,ll> > pp(m);
  rep(i,n) cin>>a[i]>>b[i];
  rep(i,m) cin>>c[i]>>d[i];
  rep(i,n){
    rep(j,m){
      sum[j] = abs(a[i]-c[j])+abs(b[i]-d[j]);
      pp[j] = make_pair(sum[j],j+1);
    }
    sort(pp.begin(),pp.end());
    cout<<pp[0].second<<"\n";
  }
  return 0;
}

Measured memory_bytes: 2304
#include <iostream>

using namespace std;

int main()
{
    int n,a[100001],i;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    int x=1,sum=1;
    while(a[x]!=2){
        x=a[x];
        sum+=1;
        if(sum>n) break;
    }
    if(sum<=n) cout<<sum;
    else if (sum>n) cout<<"-1";
    return 0;
}


Measured memory_bytes: 3944
while 1:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break

    x = max(a, b)
    y = min(a, b)

    cnt = 0
    while 1:
        cnt += 1
        tmp = x % y
        x, y = y, tmp
        if tmp == 0:
            break

    print(x, cnt)



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

int main() {
  int n,t,a;
  map<int,double> h;
  cin>>n>>t>>a;
  for(int i=1; i<=n; i++){
   int H;
   cin>>H;
   h[i]=t-H*0.006;
  }
  int ans;
  double near_a=1000000;
  for(auto x : h){
    double d_a;
    d_a = abs(a-x.second);
    if(d_a<near_a){
      near_a = min(near_a,d_a);
      ans=x.first;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

// Count pairs s.t. A[i] + A[j] >= threshold
ll Count(const vector<int> &A, int th) {
  ll cnt = 0;
  int N = A.size();
  for (int i = 0; i < N; ++i) {
    int p = -1;  // OK
    int q = N;  // NG
    while (p + 1 < q) {
      int mid = (p + q) / 2;
      if (A[i] + A[mid] >= th) {
	p = mid;
      } else {
	q = mid;
      }
    }
    cnt += p + 1;
  }
  return cnt;
}

int main() {
  ll N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  int p = 2 * A.back() - 1;  // NG (smallest score - 1)
  int q = 2 * A.front() + 1;  // OK (largest score + 1)
  while (p + 1 < q) {
    int mid = (p + q) / 2;
    if (Count(A, mid) < M) {
      q = mid;
    } else {
      p = mid;
    }
  }

  // int cnt = 0;
  // int score = 0;
  // for (int i = 0; i < N; ++i) {
  //   for (int j = 0; j < N; ++j) {
  //     if (A[i] + A[j] >= q) {
  // 	score += A[i] + A[j];
  // 	++cnt;
  //     }
  //   }
  // }
  // score += (M - cnt) * p;

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

  vector<ll> B(N);
  B[N - 1] = A[N - 1];
  for (int i = N - 2; i >= 0; --i) {
    B[i] = B[i + 1] + A[i];
  }
  
  ll score = 0;
  ll cnt = 0;
  for (int i = 0; i < N; ++i) {
    int x = q - A[i];
    auto it = lower_bound(A.begin(), A.end(), x);
    if (it != A.end()) {
      int start = distance(A.begin(), it);
      score += (N - start) * ll(A[i]) + B[start];
      cnt += N - start;
    }
  }
  score += (M - cnt) * p;

  cout << score << endl;
  
  return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	register int x=0;
	register bool f=0;
	register char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}
char cr[200];int tt;
inline void print(register long long x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
int nn[510];
int a[510][510];
int main() {
    int k=read();
    if(k<=500) {
        print(k);
        for(int i=1;i<=k;i++)
        	for(int j=1;j<=k;j++)
        		printf("%d%c", i, " \n"[j == k]); 
    }else{
        int n=500,m=0;
        for(int i=1;i<=n;i++) nn[i]=i+1;
        nn[n]=1,print(500),k-=n;
        for(int i=1;i<=n;i++) {
            int x=++m,y=k?++m:m;
            k-=y-x;
            for(int s=1,t=i;s<=n;s++,t=nn[t])
                a[s][t]=s&1?x:y;
        }
        for(int i=1;i<=n;i++)
        	for(int j=1;j<=n;j++)
        		printf("%d%c", a[i][j], " \n"[j == n]);
    }
    return 0;
}

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

int main(){
  int A, B;
  cin >> A >> B;
  //入力終了
  
  int i;
  bool flag;
  int ans = 0;
  for(int i = A; i<=B; i++){
    string str = to_string(i);
    flag = 1;
    for(int j=0; j<str.size()/2; j++){
      if(str[j] != str[str.size()-1-j]){
	flag = 0;
	break;
      }
    }
    if(flag){
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3764
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

    int a, b; cin>>a>>b;

    for(int i=1; i<=100000; i++){
        int na = i * 8;
        na /= 100;
        int nb = i * 10;
        nb /= 100;

        if(na == a && nb == b){
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace Main
{
	class Program
	{
		static void Main(string[] args)
		{
            var a = int.Parse(Console.ReadLine());
            var s = Console.ReadLine();
            if (a < 3200){
                Console.WriteLine("red");
            }
            else
            {
                Console.WriteLine(s);
            }

		}
	}
}


Measured memory_bytes: 13140
#include <iostream>
using namespace std;
int main(void){
	long n ,t;
	cin >> n >>t;
	long time[n];
	for(int i=0;i< n ;i++){
		cin>>time[i];
	}
	int i=0;
	int j=1;
	int ans=0;
	while(j<n+1){
		if(i+t>time[j]) {
			i=time[j];
			ans=ans+time[j]-time[j-1];
		}else{
			i=time[j];
			ans=ans+t;
		}
		j++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	long int deposit;
	long int x;
	int i;

	scanf("%ld", &x);

	deposit = 100;

	for (i = 0; deposit < x; i++)
	{
		deposit *= 1.01;
	}

	printf("%d\n", i);

	return 0;
}

Measured memory_bytes: 1696
x = int(input())

max_result = 0
# Sarch base between 32 ** 2(lowest p) = 1024 
for b in range(1, 33):
    # Search power between 2~10 because 2(lowest b)^10 = 1024
    for p in range(2, 11):
        canditate = b**p
        if canditate <= x and canditate > max_result:
            max_result = canditate

print(max_result)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int n;
string s;
int q;
int mc[1100000];

main(){
  cin>>n;
  cin>>s;
  cin>>q;

  while(q--){
    int k;
    cin>>k;
    int d=0,m=0,dm=0;
    int ans=0;

    rep(i,n){
      if(s[i]=='D'){
        d++;
      }else if(s[i]=='M'){
        m++;
        dm+=d;
      }else if(s[i]=='C'){
        ans+=dm;
      }

      if(i>=k-1){
        int j=i-k+1;
        if(s[j]=='D'){
          d--;
          dm-=m;
        }else if(s[j]=='M'){
          m--;
        }
      }
    }    
    cout<<ans<<endl;
  }

}


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

#define N 200010 

using namespace std;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {
	int x = 0, f = 1;
	char c = nc();
	while (c < 48) {
		if (c == '-')
			f = -1;
		c = nc();
	}
	while (c > 47) {
		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
	}
	return x * f;
}

int a[N];

int main() {
	int n = rd();
	for (int i = 1; i <= n; i ++ ) {
		a[i] = rd() - i;
	}
	sort(a + 1, a + n + 1);
	int mdl = a[n / 2 + 1];
	ll ans = 0;
	for (int i = 1; i <= n; i ++ ) {
		ans += abs(a[i] - mdl);
	}
	cout << ans << endl ;
	return 0;
}

Measured memory_bytes: 1152