akhauriyash/Code-Regression huggingface dataset:
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 1
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	c := getNextString(scanner)
	fmt.Fprintln(writer, fmt.Sprintf("%c", c[0]+1))
}


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

// マクロ //
#define rep(i,N) for(int i = 0; i < (int)(N); i++)
#define all(x) x.begin(), x.end()
#define sort(x) sort(all(x))
#define uniq(x) x.erase(unique(all(x)), x.end())
#define vsum(x) accumulate(all(x), 0)
#define cou(x) cout << x << endl
#define y() cout << "Yes" << endl
#define n() cout << "No" << endl
#define Y() cout << "YES" << endl
#define N() cout << "NO" << endl
#define x2(x) (x) * (x)
#define db(i) cout << #i << " = " << i;

// 型エイリアス //
using lint = long long;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vli = vector<lint>;
using vc = vector<char>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvli = vector<vli>;
using vvb = vector<vb>;
using vvc = vector<vc>;
using vvs = vector<vs>;
using mii = map<int, int>;
using mili = map<int, lint>;
using mci = map<char, int>;
using mcli = map<char, lint>;
using msi = map<string, int>;
using msli = map<string, lint>;


// 関数 //
template<class T, class Q> lint gcd_(T a, Q b) {
    int t;
    while (b != 0) {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

template<class T, class Q> lint lcm_(T a, Q b) {
    return a * b / gcd(a, b);
}

double distance(pii a, pii b) {
    double dist;
    dist = sqrt(x2(a.first - b.first) + x2(a.second - b.second));
    return dist;
}

lint perm(int a) {
    lint perm = 1;
    for (int i = a; i >= 1; i--) {
        perm *= i;
    }
    return perm;
}

lint combination(int n, int m) {
    long double c = 1;
    for (int i = n, k = 1; i > m; i--, k++) {
        c *= i;
        c /= k;
    }
    return (lint)c;
}

template<class T, class Q> inline bool chmin(T& a, Q b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

// 定数 //
const double pi = acos(-1);
const int mod = 1000000007;
const int MOD = 998244353;
const int inf = 1045141919;
const lint linf = ((1LL << 62) - 1);


// キーワード //
#define elif else if

// End of Template //



int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    int a, b;
    cin >> a >> b;
    cou((a <= b ? "unsafe" : "safe"));
}

Measured memory_bytes: 3692
#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>
#include <stack>
#include <functional>

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(ll i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(ll i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, z, w;
	cin >> n >> z >> w;
	vector<int> a(n);
	rep (i, n) {
		cin >> a[i];
	}
	if (n == 1) {
		cout << abs(w - a[0]) << "\n";
	} else {
		cout << max(abs(w - a[n - 1]), abs(a[n - 1] - a[n - 2])) << "\n";
	}
	return 0;
}

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

int main() {
	int n,m;
	cin >> n>> m;
	cout << (n * (n-1) + m * (m-1)) / 2 << endl;
		return 0;
}


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

// definitions
#define __Imperial_Lord__ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define _cps CLOCKS_PER_SEC
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i, l, r) for (long long i = (l); i < (long long)(r); i++)
#define repb(i, r, l) for (long long i = (r); i > (long long)(l); i--)
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define high(x) __builtin_popcountll(x)
#define pb push_back
#define pf push_front
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c <<endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d <<endl
#define exec cerr<<"Time taken : "<<(ld)(clock())/_cps<<"s"<<endl
#define mod1 998244353
#define mod 1000000007
#define pi 3.1415926535897932384

using namespace std;

// alias name for common data types
typedef vector<long long> vl;
typedef vector<long double> vld;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector< pair<long long, long long> > vp;
typedef vector<tuple<long long , long long , long long> > vtup;
typedef deque <long long> dql;
typedef deque <char> dqc;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

const ll INF=1e18;

template <class ...Args>
istream &read_args(Args &...args) {return (cin >> ... >> args);}
#define read(...)   __VA_ARGS__; read_args(__VA_ARGS__)

// cin and cout overloaded for vectors
template<typename T>    istream& operator>>(istream& is,  vector<T>& v)
{
    for (auto& i : v) 
        is >> i;        
    return is;
}
template<typename T>    ostream& operator<<(ostream& os,  vector<T>& v)
{
    for (auto& i : v) 
        os << i << ' '; 
        return os;
}


// code beigns in main
int main()
{
    __Imperial_Lord__
    ll t=1;
    // cin >> t;
    
    while(t--)
    {
        ll read(l,r,d);
        ll cnt=0;
        rep(i,l,r+1)
            if(i%d==0) cnt++;
        p1(cnt);
    }   
    exec;
}

Measured memory_bytes: 3796
type tree = Nil | Node of int * tree * tree

let create () = Nil

let insert x t =
  let rec doit = function
    | Nil -> Node (x, Nil, Nil)
    | Node (y, l, r) ->
      if x < y then Node (y, doit l, r)
      else Node (y, l, doit r) in
  doit t

let preorder f t =
  let rec doit = function
    | Nil -> ()
    | Node (x, l, r) -> f x; doit l; doit r in
  doit t

let inorder f t =
  let rec doit = function
    | Nil -> ()
    | Node (x, l, r) -> doit l; f x; doit r in
  doit t

let print t =
  inorder (fun e -> print_string " "; print_int e) t;
  print_newline ();
  preorder (fun e -> print_string " "; print_int e) t;
  print_newline ()

let find x t =
  let rec doit = function
    | Nil -> false
    | Node (y, _, _) when x = y -> true
    | Node (y, l, _) when x < y -> doit l
    | Node (_, _, r) -> doit r in
  doit t

let delete x t =
  let rec dudu = function
    | Nil -> exit 1
    | Node (x, Nil, _) -> x
    | Node (_, l, _) -> dudu l
  and wa = function
    | Nil -> exit 1
    | Node (_, Nil, r) -> r
    | Node (x, l, r) -> Node (x, wa l, r)
  and doit = function
    | Nil -> exit 1
    | Node (y, l, r) when x = y ->
      if l = Nil then r
      else if r = Nil then l
      else Node (dudu r, l, wa r)
    | Node (y, l, r) when x < y -> Node (y, doit l, r)
    | Node (y, l, r) -> Node (y, l, doit r) in
  doit t

let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let m = read_int () in
  let t = ref (create ()) in
  for _ = 0 to m - 1 do
    match read_line () |> split_on_char ' ' with
    | ["insert"; n] -> t := insert (int_of_string n) !t
    | ["find"; n] -> print_endline (if find (int_of_string n) !t then "yes" else "no")
    | ["delete"; n] -> t := delete (int_of_string n) !t
    | _ -> print !t
  done

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

const int N = 105;
const int inf = 1e9 + 7;

int H, W;
char G[N][N];
int f[N][N];

int main() {
	scanf("%d%d", &H, &W);
	for (int i = 1; i <= H; i++) {
		scanf("%s", G[i] + 1);
	}
	f[1][1] = (G[1][1] != '.');
	for (int s = 3; s <= H + W; s++) {
		for (int x = max(s - W, 1); x <= H && x < s; x++) {
			int y = s - x;
			f[x][y] = 1e9 + 7;
			if (x > 1)
				f[x][y] = min(f[x][y], f[x - 1][y] + (G[x - 1][y] != G[x][y]));
			if (y > 1)
				f[x][y] = min(f[x][y], f[x][y - 1] + (G[x][y - 1] != G[x][y]));
		}
	}
	int ans = ((G[H][W] != '.') + f[H][W] + 1) >> 1; 
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back

const long long int INF=1001001001001001001;
int N,M,X;
int H[100002];
struct edge{
  int to;
  int cost;
};

vector<edge> E[100002];
long long int d[100002];
int main(){
  long long int ans=0;
  scanf("%d %d %d",&N,&M,&X);
  rep(i,N){
    scanf("%d",&H[i]);
  }
  rep(i,M){
    int a,b,t;
    scanf("%d %d %d",&a,&b,&t);
    a--;b--;
    edge e;e.cost=t;
    e.to=a;E[b].pb(e);
    e.to=b;E[a].pb(e);
  }
  //dijkstra
  priority_queue< pair<long long int,int> ,vector<pair<long long int,int> >, greater<pair<long long int,int> >  >  que;
  fill(&d[0],&d[N],INF);
  d[0]=0;
  que.push(make_pair(0,0) );
  while(que.size()){
	  pair<long long int,int> p=que.top();que.pop();
	  int n=p.second;long long int c=p.first;
	  if(d[n]<c)continue;
	  rep(i,E[n].size()){
		  if(E[n][i].cost>H[n])continue;
		  int nt=E[n][i].cost;
		  if(/*??????*/X-d[n]<E[n][i].cost){nt+=E[n][i].cost-max(X-d[n],(long long)0);/*??????*/}
		  if(/*??????*/X-d[n]-E[n][i].cost>H[E[n][i].to]){
			  nt+=X-d[n]-E[n][i].cost- H[E[n][i].to] ;/*?????????*/
			  }
		  if(d[E[n][i].to ]>d[n]+nt){
			  d[E[n][i].to ]=d[n]+nt;
			  que.push( make_pair(d[E[n][i].to],E[n][i].to ) );
		  }
	  }
  }
  ans=d[N-1];
  ans+=H[N-1]-max(X-d[N-1],(long long)0);
  if(d[N-1]==INF)printf("-1\n");
  else printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 15584
h,w,k=map(int,input().split(' '))
d=[]
for i in range(h):
    d.append(input())

rbits=[]
for i in range(2**h):
    s=bin(i)
    s=s[s.index('b')+1:]
    s=(h-len(s))*'0'+s
    rbits.append(s)

cbits=[]
for i in range(2**w):
    s=bin(i)
    s=s[s.index('b')+1:]
    s=(w-len(s))*'0'+s
    cbits.append(s)


    
ans=0


for i in rbits:
    for j in cbits:
        a=0
        for c in range(h):
            if i[c]=='1':
                for e in range(w):
                    if j[e]=='1' and d[c][e]=='#':
                        a+=1
        if a==k:
            ans+=1

print(ans)






Measured memory_bytes: 68216
//binary tree
//https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_B

#include <iostream>
#include <string>
#define NIL -1
using namespace std;

struct Node{
    int parent;
    int left;
    int right;
};

inline int get_sibling(Node T[], int i);
inline int get_child(Node T[], int i);
inline string type_of_node(Node T[], int i);
void get_depth(Node T[], int depth[], int p, int i);
int get_height(Node T[], int height[], int i);

int main(){
    int n;
    cin >> n;
    int depth[n];
    int height[n];
    Node T[n];
    for (int i = 0; i < n; i++){
        T[i].parent = NIL;
        T[i].left = NIL;
        T[i].right = NIL;
    }
    int id, l, r;
    for (int i = 0; i < n; i++){
        cin >> id >> l >> r;
        T[l].parent = id;
        T[r].parent = id;
        T[id].left = l;
        T[id].right = r;
    }
    int s;
    for (int i = 0; i < n; i++){
        if (T[i].parent == NIL)
            s = i;
    }
    get_depth(T, depth, 0, s);
    get_height(T, height, s);
    for (int i = 0; i < n; i++){
        cout << "node " << i << ": parent = ";
        cout << T[i].parent << ", sibling = ";
        cout << get_sibling(T, i) << ", degree = ";
        cout << get_child(T, i) << ", depth = ";
        cout << depth[i] << ", height = ";
        cout << height[i] << ", " << type_of_node(T, i) << endl;
    }
    return 0;
}

/*inline*/ int get_sibling(Node T[], int i){
    if (T[i].parent == NIL)
        return -1;
    else if (i == T[T[i].parent].right)
        return T[T[i].parent].left;
    else if (i == T[T[i].parent].left)
        return T[T[i].parent].right;
}

/*inline*/ int get_child(Node T[], int i){
    int count = 0;
    if (T[i].left != NIL)
        count++;
    if (T[i].right != NIL)
        count++;
    return count;
}

/*inline*/ string type_of_node(Node T[], int i){
    if (T[i].parent == NIL)
        return "root";
    else if (T[i].left == NIL && T[i].right == NIL)
        return "leaf";
    else
        return "internal node";
}

void get_depth(Node T[], int depth[], int p, int i){
    depth[i] = p;
    if (T[i].left != NIL)
        get_depth(T, depth, p + 1, T[i].left);
    if (T[i].right != NIL)
        get_depth(T, depth, p + 1, T[i].right);
}

int get_height(Node T[], int height[], int i){
    int h1, h2;
    h1 = h2 = 0;
    if (T[i].right != NIL)
        h1 = get_height(T, height, T[i].right) + 1;
    if (T[i].left != NIL)
        h2 = get_height(T, height, T[i].left) + 1;
    return height[i] = max(h1, h2);
}


Measured memory_bytes: 3220
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    auto as = readln.split.to!(int[]);
    int[][] T;
    T.length = N;
    foreach (_; 1..N) {
        auto uv = readln.split.to!(int[]);
        auto u = uv[0]-1;
        auto v = uv[1]-1;
        T[u] ~= v;
        T[v] ~= u;
    }
    auto res = new int[](N);
    auto DP = new int[](N);
    DP[] = int.max;
    size_t idx;

    void solve(int i, int p) {
        auto a = as[i];
        size_t len = idx, pi;
        int pa;
        if (idx == 0 || DP[idx-1] < a) {
            DP[idx++] = a;
        } else if (DP[0] >= a) {
            pa = DP[0];
            DP[0] = a;
        } else {
            size_t l, r = idx-1;
            while (l+1 < r) {
                auto m = (l+r)/2;
                if (DP[m] >= a) {
                    r = m;
                } else {
                    l = m;
                }
            }
            pi = r;
            pa = DP[r];
            DP[r] = a;
        }
        res[i] = idx.to!int;

        foreach (j; T[i]) if (j != p) solve(j, i);

        if (idx != len) {
            idx = len;
        } else {
            DP[pi] = pa;
        }
    }

    solve(0, -1);
    foreach (r; res) writeln(r);
}

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

#define int long long

using namespace std;

double dp[3005][3005]={0}; // probab of having i heads using 1->j coins(taking all).

signed main(){
	int n;
	cin>>n;
	double p[n];
	for(int i=0;i<n;i++) cin>>p[i];
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i=1;i<=n;i++){
		dp[0][i] = dp[0][i-1]*(1-p[i-1]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j] = dp[i-1][j-1]*p[j-1] + dp[i][j-1]*(1-p[j-1]);
		}
	}
	double ans=0;
	for(int i=1;i<=n;i++){
		if(i>n/2){
			ans += dp[i][n];
		}
	}
	cout<<setprecision(10)<<ans;
}

Measured memory_bytes: 74336
p, g = 998244353, 3
def convolve(a, b):
    def fft(f):
        for l in range(k)[::-1]:
            d = 1 << l
            v = W[k-1-l]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p

    def ifft(f):
        for l in range(k):
            d = 1 << l
            v = iW[k-1-l]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
 
    n0, n1 = len(a), len(b)
    k = (max(n0, n1) - 1).bit_length() + 1
    n = 1 << k
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    W = [w]
    for i in range(k):
        W.append(W[-1] ** 2 % p)
    invw = pow(w, p-2, p)
    iW = [invw]
    for i in range(k):
        iW.append(iW[-1] ** 2 % p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))


Measured memory_bytes: 203232
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
using namespace std;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
signed main() {
	int a[3], b[3];
	int cnta = 0, cntb = 0, cntc = 0, cntd = 0;
	rep(i, 3)cin >> a[i] >> b[i];
	rep(i, 3) {
		if (a[i] == 2)cnta++;
		if (a[i] == 3)cntb++;
		if (b[i] == 2)cntc++;
		if (b[i] == 3)cntd++;
	}
	if (cnta + cntc == 2 && cntb + cntd == 2)puts("YES");
	else puts("NO");
	getchar(); getchar(); return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<deque>
#include<map>
#include<queue>

typedef long long ll;

#define debug(x) cout << #x << '=' << x << endl;
#define debug_arr(a, n) for(ll i = 0; i < n; i++)cout << a[i] << ' '
#define inf 100000000000
#define loop(i,n) for(ll i = 0; i < n; i++)
#define graph vector<vector<ll>>
#define P pair<ll,ll>

using namespace std;

struct cakes{
    ll i;
    ll j;
    ll k;
    ll sum;

    cakes(ll i, ll j, ll k, ll sum): i(i),j(j),k(k),sum(sum){}
};

bool isChecked[1000][1000][1000] = {false};

int main(){
    ll x,y,z;
    cin >> x >> y >> z;

    ll k;
    cin >> k;

    auto compare = [](const cakes& a, const cakes& b){
        return a.sum < b.sum;
    };

    auto sortCompare = [](const ll& l, const ll& r){
        return l > r;
    };

    priority_queue<cakes, vector<cakes>, decltype(compare)> q{compare};

    vector<ll> a(x),b(y),c(z);

    loop(i,x) cin >> a[i];
    loop(i,y) cin >> b[i];
    loop(i,z) cin >> c[i];

    sort(a.begin(), a.end(), sortCompare);
    sort(b.begin(), b.end(), sortCompare);
    sort(c.begin(), c.end(), sortCompare);

    ll count = 0;
    cakes initCakes = cakes(0,0,0,a[0]+b[0]+c[0]);

    isChecked[0][0][0] = true;
    q.push(initCakes);

    while(1){
        cakes tmp = q.top();
        q.pop();
        // cout << tmp.i << tmp.j << tmp.k << endl;
        cout << tmp.sum << endl;

        if(isChecked[tmp.i + 1][tmp.j][tmp.k] == false && tmp.i + 1 < x){
            q.push(cakes(tmp.i+1,tmp.j,tmp.k,a[tmp.i+1]+b[tmp.j]+c[tmp.k]));
            isChecked[tmp.i + 1][tmp.j][tmp.k] = true;
        }
        if(isChecked[tmp.i][tmp.j+1][tmp.k] == false && tmp.j + 1 < y){
            q.push(cakes(tmp.i,tmp.j+1,tmp.k,a[tmp.i]+b[tmp.j+1]+c[tmp.k]));
            isChecked[tmp.i][tmp.j + 1][tmp.k] = true;
        }
        if(isChecked[tmp.i][tmp.j][tmp.k+1] == false && tmp.k + 1 < z){
            q.push(cakes(tmp.i,tmp.j,tmp.k+1,a[tmp.i]+b[tmp.j]+c[tmp.k+1]));
            isChecked[tmp.i][tmp.j][tmp.k+1] = true;
        }

        count ++;
        if(count == k)break;
    }

    return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  
  int sum = 0;
  
  vector<int> vec(M);
  for (int i = 0; i < M; i++) {
    cin >> vec.at(i);
    sum += vec.at(i);
  }
  
  if (N - sum < 0) {
    cout << -1 << endl;
  } else {
    cout << N - sum << endl;
  }
}


Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<functional>
#include<cstdlib>
#include<queue>
#include<deque>
const double PI = acos(-1);
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
using ll =long long;
const int mod = 1000000007;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
};
//fixed << setprecision(2)
bool  Array_check(ll y, ll x,ll d,ll w) {
	if (x < 0 || x >= w || y<0 || y>=d) {
		return false;
	}
	else {
		return true;
	}
	
}
//小文字=大文字+32
int main() {
	string s;
	string t;
	cin >> s >> t;
	for (int i = s.size() - t.size(); i >= 0;i--) {
		rep(j, t.size()){
			if (t[j] != s[i+j]&&s[i+j]!='?') {
				break;

			}
			if (j+1 == t.size()) {
				rep(k, i) {
					if (s[k] == '?') {
						cout << 'a';
					}
					else {
						cout << s[k];
					}
				}
				cout << t;
				for (int k = i + t.size(); k < s.size(); k++) {
					if (s[k] == '?') {
						cout << 'a';
					}
					else {
						cout << s[k];
					}

				}
				return 0;
			}


		}

	}
	cout << "UNRESTORABLE";

}


Measured memory_bytes: 3596
def main():
    s = list(input())
    
    if(len(s)!=6):
        main()
    
    for e in s:
        if(e.islower()==False):
            main()
    
    if(s[2]==s[3] and s[4]==s[5]):
        print("Yes")
    else:
        print("No")
main()

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

int main(){
    int n;
    cin >> n;
    int h[n];
    int dp[n];
    for(int i = 0; i < n; i++){
        cin >> h[i];
        //一緒に初期化もやる
        dp[i] = 0;
    }
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for(int i = 2; i < n; i++){
        int tmp1 = abs(h[i] - h[i-1]);
        int tmp2 = abs(h[i] - h[i-2]);
        dp[i] = min(dp[i-1]+tmp1, dp[i-2]+tmp2);
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

vector<vector<P>> g;
vector<int> col;

void dfs(int a, int b, int c){
  col[a] = c;
  for(auto v: g[a]){
    if(col[v.first] != -1) continue;
    if(v.second % 2 == 0) dfs(v.first,a,c);
    else dfs(v.first,a,1-c);
  }
}


int main(){
  int N; cin >> N;
  g.resize(N);
  col.assign(N,-1);
  for(int i = 0; i < N-1; i++){
    int a,b,c; cin >> a >> b >> c;
    a--; b--;
    g[a].push_back(P(b,c));
    g[b].push_back(P(a,c));
  }
  dfs(0,-1,1);
  for(auto v: col){
    cout << v << endl;
  }
  return 0;
}

Measured memory_bytes: 8192
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n, c := nextInt(), nextInt()
	ds := make([][]int, c)
	for i := 0; i < c; i++ {
		ds[i] = make([]int, c)
	}
	counts := make([][]int, 3)
	for i := 0; i < 3; i++ {
		counts[i] = make([]int, c)
	}
	for i := 0; i < c; i++ {
		for j := 0; j < c; j++ {
			ds[i][j] = nextInt()
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			counts[(i+j)%3][nextInt()-1]++
		}
	}

	res := 1 << 30
	for i := 0; i < c; i++ {
		for j := 0; j < c; j++ {
			if i == j {
				continue
			}

			for k := 0; k < c; k++ {
				if i == k || j == k {
					continue
				}

				t := 0
				for l := 0; l < c; l++ {
					t += ds[l][i] * counts[0][l]
					t += ds[l][j] * counts[1][l]
					t += ds[l][k] * counts[2][l]
				}

				if res > t {
					res = t
				}
			}
		}
	}

	fmt.Println(res)
}

Measured memory_bytes: 1152
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define SIZE 100010

typedef struct node {
    char elem;
    struct node *next;
} node;

void push(node **first, char elem) {
    node *new = (node *)malloc(sizeof(node));
    if(new == NULL) exit(1);
    new->elem = elem;
    new->next = *first;
    *first = new;
}

char pop(node **first) {
    char elem;
    node *tmp = *first;
    if(tmp == NULL) exit(1);
    elem = tmp->elem;
    *first = tmp->next;
    free(tmp);
    return elem;
}

int main() {
    char s[SIZE] = {'\0'};
    char popped;
    int num_red = 0, num_blue = 0;
    int popped_num = 0;
    node *first;

    scanf("%s", s);
    for(int i = 0; i < strlen(s); i++) {
        push(&first, s[i]);
    }

    while(first != NULL) {
        popped = pop(&first);
        if(popped == '0') num_red++;
        else              num_blue++;
    }
    popped_num = (num_red < num_blue) ? num_red : num_blue;
    popped_num *= 2;

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

    return 0;
}


Measured memory_bytes: 4948
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define endl '\n'
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
#define iter1 vector<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=2e5+7;
const int inf=1e18+1e9;
const int mod=1e9+7;
const ld eps=1e-9;

int h[N];
int dp[N];

main ()
{
    ios;
    int n;
    cin>>n;
    int k=2;
    for (int i=1;i<=n;++i){
        cin>>h[i];
    }
    dp[1]=0;
    dp[0]=inf;
    for (int i=2;i<=n;++i){
        dp[i]=inf;
        for (int j=1;j<=min(i-1,k);++j){
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1792
using System;

class Program
{
    static void Main(string[] args)
    {
        int n, x, i, j, k;
        int total = 0;
        int cou = 0;

        while (true)
        {
            //整数受け取り
            string[] str = Console.ReadLine().Split(' ');
            n = int.Parse(str[0]);
            x = int.Parse(str[1]);
                
            //n, xが0の場合終了
            if (n == 0 && x == 0)
            {
                break;
            }

            //判定
            for (i = 1; i <= n; i++)
            {
                for (j = i + 1; j <= n; j++)
                {
                    for (k = j + 1; k <= n; k++)
                    {
                        total = i + j + k;

                        if (total == x)
                        {
                            cou++;
                        }
                        else
                        {
                            total = 0;
                        }
                    }
                }
            }
            Console.WriteLine(cou);
            cou = 0;
        }
    }
}


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

int main() {
  int n;
  cin>>n;
  int h[25];
  for (int i=0; i<n; i++) {
    cin>>h[i];
  }

  int ans=0;
  bool flag;
  for (int i=0; i<n; i++) {
    flag=true;
    for (int j=0; j<i; j++) {
      if (h[i]<h[j]) flag=false;
    }
    if (flag) ans++;
  }
  cout<<ans<<endl;
  return 0;
}



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

typedef long long ll;
const int N=100010;
ll k;
int n,m,id[N];
ll x[N];int nxt[N];ll cf[N],ans[N];bool vis[N];int cnt;
void dfs(int st){
	while(!vis[st])
	{
	id[++cnt]=st;
	vis[st]=1;
	st=nxt[st];
//	printf("check_id_id id[%d]:%d\n",cnt,id[cnt]);
    }
    return;
}
int main(){
	///freopen("in.txt","r",stdin);
	//freopen("arbitout.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf("%lld",&x[i]);
    	cf[i]=x[i]-x[i-1];
    	nxt[i]=i;
    //	printf("cf[%d]:%d\n",i,cf[i]);
    }
    scanf("%d%lld",&m,&k);
    for(int i=1;i<=m;i++){
    	int kk;
    	scanf("%d",&kk);
        swap(nxt[kk],nxt[kk+1]);
	 }
	// for(int kk=1;kk<=n;kk++)printf("nxt[%d]:%d\n",kk,nxt[kk]);
	 for(int i=1;i<=n;i++){
	 	if(!vis[i]){
	        cnt=0;
	 		dfs(i);
	 		if(cnt==1) ans[id[1]]=cf[id[1]];
	 		else {
	 		for(int j=1;j<=cnt;j++){
	 		ans[id[j]]=cf[id[(k+j-1)%cnt+1]];
		     }  
	 	}
	    }
	 }
	ll anss=0;
	 for(int i=1;i<=n;i++){
	    anss+=ans[i];
	 //	printf("well_down_cf[%d]:%d,anss:%d  ",i,cf[i],anss);
	 	 printf("%lld.0\n",anss);
	 }
}

Measured memory_bytes: 4736
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<complex>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 100;
LL n, a, b, c, d;

bool ok(LL from, LL to)
{
	if (from > to) return false;
	if (to < 0) return false;
	if (from > n) return false;

	return true;
}

void yes()
{
	cout << "YES" << endl;
	exit(0);
}

void no()
{
	cout << "NO" << endl;
	exit(0);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> a >> b >> c >> d;

	if (c + d == 0)
	{
		if (a == b) yes();
		no();
	}

	if (a > b) swap(a, b);
	if (c > d) swap(c, d);
	n--;

	LL to = (b - a + n * d) / (c + d);
	LL from = (b - a + n* c + (c + d - 1)) / (c + d);

	//cout << from << " " << to << endl;
	if (ok(from, to)) yes();
	no();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ii pair<int,int>
#define x first
#define y second

using namespace std;

bool check(vector<int>&a,vector<int>&b){
    for(int i = 0;i <a.size();i++){
        if(a[i]!= b[i]){
            return false;
        }
    }
    return true;
}

int main(){
    ll x,k;
    cin >> x >> k;
    if(x*500 < k){
        cout << "No";
    }
    else{
        cout << "Yes";
    }
}


Measured memory_bytes: 256
import statistics as stat
import collections as cl

N = int(input())

s_li = []
s_dic = {}
c = 0
for i in range(N) :
    s = ''.join(sorted(list(input())))
    # con = s_li.count(s)
    # if (con >= 1) :
    #     c += con
    # s_li.append(s)
    if (s in s_dic) :
        c += s_dic[s]
        s_dic[s] += 1
    else :
        s_dic[s] = 1

print(c)

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

int main(void) {
  int i, j;
  int N, M;
  int max = 0;
  int numbers[100] = {};
  char cards[100][11] = { { } };
  scanf("%d", &N);
  for(i = 0;i < N;i++) {
    char temp[11];
    scanf("%s", temp);
    for(j = 0;j < 100;j++) {
      if(cards[j][0] == '\0' || strcmp(temp, cards[j]) == 0) break;
    }
    strcpy(cards[j], temp);
    numbers[j]++;
  }
  scanf("%d", &M);
  for(i = 0;i < M;i++) {
    char temp[11];
    scanf("%s", temp);
    for(j = 0;j < 100;j++) {
      if(cards[j][0] == '\0' || strcmp(temp, cards[j]) == 0) break;
    }
    strcpy(cards[j], temp);
    numbers[j]--;
  }
  for(i = 0;i < 100;i++) {
    if(max < numbers[i]) max = numbers[i];
  }
  printf("%d\n", max);
  return 0;
}


Measured memory_bytes: 128
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  var data = parseInt( chunk );
  var h = Math.floor( data/3600 );
  data = data%3600;
  var m = Math.floor( data/60 );
  var s = Math.floor( data%60 );  
  console.log( h+':'+m+':'+s );
} )

Measured memory_bytes: 7648
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <iomanip>       // fixed, setprecision
using namespace std;

int main()
{
  int N, c = 0;
  cin >> N;
  vector<int> L(N);
  for (int i = 0; i < N; i++)
  {
    cin >> L.at(i);
  }
  sort(L.rbegin(), L.rend());
  for (int i = 0; i < N; i++)
  {
    for (int j = i + 1; j < N; j++)
    {
      for (int k = j + 1; k < N; k++)
      {
        if (L[i] != L[j] && L[j] != L[k] && L[k] != L[i] && (L[i] < L[k] + L[j]))
        {
          c++;
        }
      }
    }
  }
  cout << c << endl;
}


Measured memory_bytes: 3184
#include<iostream>
using namespace std;
int main(){
  int t,n,ans,st,st2;
  while(cin>>t){
    if(t==0) break;
    cin >> n;
    ans = 0;
    for(int i=0;i<n;i++){
      cin >> st >> st2;
      ans += st2 - st;
    }
    if(ans>=t) cout << "OK" << endl;
    else cout << t - ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
from collections import Counter

from sys import stdin

input = stdin.readline

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

An = Counter([int(i) for i in input().split()])


def main():
    # 要素数(v) 多い順 インデックス K 含んでそれよりも後ろ
    # 先頭 K + 1 個目から 末尾 まで
    # 要素数(v) 合計
    print(sum([v for k, v in An.most_common()[K:]]))

    return


main()


Measured memory_bytes: 39272
#include <stdio.h>
int main(void){
  int i,cnt=0,temp=0;
  char S[15];
  if(scanf("%s",S)<1) return 1;
  for(i=0;S[i];i++){
    if(S[i]=='A'||S[i]=='C'||S[i]=='G'||S[i]=='T'){
      temp++;
      cnt=(cnt>temp? cnt : temp);
    }
    else{
      temp=0;
    }
  }
  printf("%d\n",cnt);    
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
 ll i,a[100001]={0},dp[100001]={0},n,cost,k;
 cin>>n>>k;
 for(i=0;i<n;i++)
 {
     cin>>a[i];
 }
 for(i=2;i<=n;i++)
    {if(i==2)
     dp[i]=abs(a[i-1]-a[i-2]);
    else
    {
        ll mini=INT_MAX,z;
    for(z=1;z<=k;z++)
        {
        cost=dp[i-z]+abs(a[i-1]-a[i-1-z]);
        mini=min(cost,mini);
      if(i-1-z==0)
        break;
    }
    dp[i]=mini;
    }
 }
 cout<<dp[n];

}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

struct edge {
    int from, to;
    ll cost;
};

class Dijkstra {
    int V;
    vector<vector<edge>> edges;
    vector<ll> dist;
    vector<ll> prev;

public:
    Dijkstra(int v) : V(v) {
        edges.resize(V);
        dist.resize(V, INF);
        prev.resize(V, INF);
    }

    void add_edge(int from, int to, ll cost) {
        edges[from].push_back({from, to, cost});
    }

    /**
     * @param goal 0-indexed
     * @return return cost to reach the goal. return INF if the goal is unreachable.
     */
    ll get_cost(int goal) {
        return dist[goal];
    }

    void exec(int start) {
        dist[start] = 0;
        priority_queue<P, vector<P>, greater<>> queue;
        queue.push({dist[start], start});
        while (!queue.empty()) {
            P p = queue.top();
            queue.pop();
            ll prev_cost = p.first;
            ll src = p.second;
            if (dist[src] < prev_cost) continue;

            for (edge &e : edges[src]) {
                ll to = e.to;
                ll cost = e.cost;
                if (cost != INF && dist[to] > dist[src] + cost) {
                    dist[to] = dist[src] + cost;
                    queue.push({dist[to], to});
                    prev[to] = src;
                }
            }
        }
    }
};

void Main() {
    int N, M;
    cin >> N >> M;
    Dijkstra dijkstra(N);
    rep(i, M) {
        ll l, r, c;
        cin >> l >> r >> c;
        l--;
        r--;
        dijkstra.add_edge(l, r, c);
    }
    rep2(i, 1, N) {
        dijkstra.add_edge(i, i - 1, 0);
    }

    dijkstra.exec(0);

    ll ans = dijkstra.get_cost(N - 1);

    if (ans != INF) {
        cout << ans << '\n';
    } else {
        cout << -1 << '\n';
    }
}

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


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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n,a;
    cin>>n>>a;
    int p=n%500;
    if(p<=a)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;

}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>
#include <unordered_map>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;
unordered_map<ll, ll> val[200000];
ll num[200000];
int main(void){
    ll N, M;
    cin>>N>>M;
    ll X;
    MEMSET(num, 0);
    rep(i, N){
        cin>>X;
        num[X%M]++;
        val[X%M][X]++;
    }
    ll count=0;
    rep1(i, (M%2==0 ? M/2-1 : M/2)){
        ll count1=0, count2=0;
        //cout<<i<<sp<<M-i<<endl;
        for(auto itr : val[i]) count1+=itr.second/2;
        for(auto itr : val[M-i]) count2+=itr.second/2;
        count+=min(num[i], num[M-i]);
        //cout<<count<<endl;
        count+=max((ll)0, min((num[i]-num[M-i])/2, count1));
        //cout<<count<<endl;
        count+=max((ll)0, min((num[M-i]-num[i])/2, count2));
    }
    count+=num[0]/2;
    if(M%2==0) count+=num[M/2]/2;
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 18944
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    #= str(stdin.readline().rstrip())
    n,k = map(int, stdin.readline().rstrip().split())
    p = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    p.sort()
    ans = 0
    for i in range(k):
        ans += p[i]
    print(ans)

main()


Measured memory_bytes: 9236
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine();
        Double intinput = Double.Parse(input);
        Double output = Math.Pow(intinput,3);
        Console.WriteLine(output);
    }
}




Measured memory_bytes: 15932
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll,int> P;
typedef tree<P,null_type,less<P>,rb_tree_tag,tree_order_statistics_node_update> Tree;
Tree st;

int main(){
	int N,K;
	cin>>N>>K;
	st.insert(P(0,0));
	ll sum = 0;
	ll ans = 0;
	rep(i,N){
		ll a;
		scanf("%lld",&a);
		sum += a-K;
		int num = st.order_of_key(P(sum,N));
		ans += num;
		st.insert(P(sum,i+1));
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 12800
N = int(input())
#= map(int,input().split())
a =list(map(int,input().split()))
# [list(map(int,input().split())) for i in range(N)]
counter = 1
for i in range(N):
    if a[i]==counter:
        counter +=1
if (N-counter+1)==N:
    print('-1')
else:
    print(N-counter+1)


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

bool solve() {
    string S;
    cin >> S;
    while(3 < S.size()) {
        ll cnt[3] = {};
        vector<ll> idx;
        for(ll i = 0; i < S.size(); i++) {
            if(!(i + 2 < S.size() && 
                 S[i] == 'A' &&
                 S[i + 1] == 'B' &&
                 S[i + 2] == 'C')) {
                cnt[S[i] - 'A']++;
            } else {
                idx.push_back(i);
                i += 2;
            }
        }
        char c = 0;
        if(!cnt[0] && cnt[1] && cnt[2]) c = 'A';
        if(cnt[0] && !cnt[1] && cnt[2]) c = 'B';
        if(cnt[0] && cnt[1] && !cnt[2]) c = 'C';
        if(c == 0) break;
        string T;
        ll idx_i = 0;
        for(ll i = 0; i < S.size(); i++) {
            if(idx_i < idx.size() && i == idx[idx_i]) {
                T += c;
                idx_i++;
                i += 2;
            } else {
                T += S[i];
            }
        }
        S = move(T);
    }
    return S == "ABC";
}

int main() {
    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}



Measured memory_bytes: 3260
N=int(input())
listA=[list(map(int,input().split())) for i in range(N)]
listA.sort(key=lambda x:x[1])
jikan=0
deki=True
for i in range(N):
    jikan=jikan+listA[i][0]
    if jikan > listA[i][1]:
        deki=False
if deki:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 53728
#include<stdio.h>
#define MAX 500001

int n;

int left(int);
int right(int);

void maxHeapify(int H[],int i){
  int l,r,largest,temp;
  l=left(i);
  r=right(i);
  if(l<=n&&H[l]>H[i])
    largest=l;
  else
    largest=i;

  if(r<=n&&H[r]>H[largest])
    largest=r;

  if(largest!=i){
    temp=H[i];
    H[i]=H[largest];
    H[largest]=temp;
    maxHeapify(H,largest);
  }
}

void buildMaxHeap(int H[]){
  int i;
  for(i=n/2;i>=1;i--){
    maxHeapify(H,i);
  }
}


int left(int i){
  i*=2;
  if(i>n)
    return MAX;
  else
    return i;
}

int right(int i){
  i=2*i+1;
  if(i>n)
    return MAX;
  else
    return i;
}

int main(){
  int i,H[MAX];
  scanf("%d",&n);
  for(i=1;i<n+1;i++){
    scanf("%d",&H[i]);
  }
  buildMaxHeap(H);

  for(i=1;i<n+1;i++){
    printf(" %d",H[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 2552
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
int main() {
   int a1,a2,a3;
   cin >> a1 >> a2 >> a3;
   if(a1 + a2 + a3 <= 21){
      cout << "win" << endl;
   }else{
      cout << "bust" << endl;
   }
   return 0;
}

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

typedef long long ll;

/* メモリ食い過ぎ注意 */
#define int ll
#define ALL(v) v.begin(), v.end()
#define _REP(i, n) for (int i = 0; i < n; i++)
#define REP(n) _REP(i, n)

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

int par[100010];
int rnk[100010];

void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        par[i] = i;
        rnk[i] = 0;
    }
}

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

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (rnk[x] < rnk[y])
    {
        par[x] = y;
    }
    else
    {
        par[y] = x;
        if (rnk[x] == rnk[y])
            rnk[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

signed main()
{
    int n, m;
    int x[100000], y[100000], z[100000];
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> x[i] >> y[i] >> z[i];

    init(n + 1);
    for (int i = 0; i < m; i++)
    {
        unite(x[i], y[i]);
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (par[i] == i)
        {
            cnt++;
        }
        else
        {
            par[i] = par[par[i]];
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 4096