akhauriyash/Code-Regression huggingface dataset:
import sys

A,B,C,X,Y = list(map(int,input().split()))

if A+B < 2*C:
    print(A*X+B*Y)
else:
    pre = []
    pre.append(max(X,Y)*2*C)
    if X>Y:
        #X>YならY枚Bピザを用意してX-Y枚Aピザを買うのも候補
        pre.append(Y*2*C+(X-Y)*A)
    elif X<Y:
        #X枚Aピザを用意してY-X枚Bピザ
        pre.append(X*2*C+(Y-X)*B)
    else:

        pre.append(Y*2*C+(X-Y)*A)
        pre.append(X*2*C+(Y-X)*B)
    print(min(pre))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll x,y;cin>>x>>y;
  ll ans=0;
  for(ll i=x;;){
    ans++;
    if(2*i>y)break;
    i*=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    W, a, b = map(int, input().split())
    if (a <= b <= a + W) or (a <= b + W <= a + W):
        print(0)
    elif (b <= a <= b + W) or (b <= a + W <= b + W):
        print(0)
    else:
        print(min(abs(b + W - a), abs(a + W - b)))


if __name__ == '__main__':
    main()


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

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

  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  sort(A.rbegin(), A.rend());

  long long W = 0, H = 0;
  for(int i = 1; i < N; i++) {
    if(A[i-1] == A[i]) {
      if(!W) {
        W = A[i];
        // cout << "W: " << W << endl;
        i++;
      }
      else if(!H) {
        H = A[i];
        // cout << "H: " << H << endl;
        break;
      }
    }
  }

  if(W && H) {
    cout << W * H << endl;
  }
  else {
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 3676
use std::cmp;

#[allow(dead_code)]
pub struct Scanner<'a> {
    _buf: &'a str,
    iter: ::std::str::SplitWhitespace<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    pub fn new(buf: &'a str) -> Self {
        Scanner {
            _buf: buf,
            iter: buf.split_whitespace(),
        }
    }

    pub fn array<T>(&mut self, n: usize) -> Vec<T>
        where T: ::std::str::FromStr,
              T::Err: ::std::fmt::Debug,
    {
        let mut res = Vec::with_capacity(n);
        for _ in 0..n {
            res.push(self.value());
        }
        res
    }

    pub fn value<T>(&mut self) -> T
        where T: ::std::str::FromStr,
              T::Err: ::std::fmt::Debug,
    {
        self.next().parse().unwrap()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.next().chars().collect()
    }

    fn next(&mut self) -> &str {
        self.iter.next().unwrap()
    }
}

struct Solver {
    _n: i64,
    vv: Vec<Vec<i64>>,
    memo: Vec<Vec<Option<i64>>>,
}

impl Solver {
    fn new(n: i64, vv: Vec<Vec<i64>>) -> Self {
        Solver {
            _n: n,
            vv: vv,
            memo: vec![vec![None; n as usize]; 3],
        }
    }

    /// i 日目の行動 j
    fn f(&mut self, i: i64, j: i64) -> i64 {
        if i == 0 { return self.vv[j as usize][0]; }

        if self.memo[j as usize][i as usize].is_none() {
            let mut res = 0;
            for k in 0..3 {
                if k == j { continue; }
                res = cmp::max(res, self.f(i-1,k));
            }
            res += self.vv[j as usize][i as usize];
            self.memo[j as usize][i as usize] = Some(res);
        }
        self.memo[j as usize][i as usize].unwrap()
    }
}

fn main() {
    let mut _input = String::new();
    {
        use ::std::io::Read;
        ::std::io::stdin().read_to_string(&mut _input).unwrap();
    }
    let mut sc = Scanner::new(&_input);

    let n = sc.value::<i64>();
    let mut a = Vec::with_capacity(n as usize);
    let mut b = Vec::with_capacity(n as usize);
    let mut c = Vec::with_capacity(n as usize);
    for _ in 0..n {
        a.push(sc.value::<i64>());
        b.push(sc.value::<i64>());
        c.push(sc.value::<i64>());
    }

    let mut sol = Solver::new(n, vec![a,b,c]);
    let mut ans = 0;
    for j in 0..3 {
        ans = cmp::max(ans, sol.f(n-1, j));
    }

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


Measured memory_bytes: 22396
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    near = list(product(range(-2, 3), repeat=2))

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy in near:
            cnt = (abs(dx) + abs(dy) >= 2)
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))


Measured memory_bytes: 95400
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <climits>
#include <sstream>

using namespace std;

int main(){
    int a, b, c;

    cin >> a >> b >> c;

    bool flag = true;

    if(a+b == c) flag = true;
    else if(a+c == b) flag = true;
    else if(b+c == a) flag = true;
    else flag = false;

    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x,y;
  cin >>x>>y;
  if( x==1 ||x==3||x==5||x==7||x==8||x==10||x==12){
    if( y==1 ||y==3||y==5||y==7||y==8||y==10||y==12)
      cout <<"Yes";
    else cout <<"No";
  }
  else if(x==4 ||x==6||x==9||x==11){
    if(y==4 ||y==6||y==9||y==11)
      cout<<"Yes";
    else cout<<"No";
  }
  else cout<<"No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;
vector<ll> ans;

int main()
{
    int n, k, c;
    cin >> n >> k >> c;
    string s;
    cin >> s;
    int workMax = 0;
    int cur = 0;
    VI candid;
    rep(i, n)
    {
        if (cur != 0)
        {
            cur--;
        }
        else
        {
            if (s[i] == 'o')
            {
                workMax++;
                cur = c;
                candid.push_back(i);
            }
        }
    }
    if (k < workMax)
    {
        cout << endl;
        return 0;
    }
    cur = candid.size() - 1;
    candid.push_back(IINF);
    VI ans;
    bool change = false;
    for (int i = n - 1; i >= 0; i--)
    {
        //cerr << cur << " " << candid[cur] << " " << i << endl;
        if (candid[cur] == i)
        {
            // cerr << "i" << change << endl;
            ans.push_back(candid[cur]);
            cur--;
            continue;
        }
        if (cur == -1)
            break;
        if (s[i] == 'o' && candid[cur + 1] - i > c)
        {
            candid[cur] = i;
            cur--;
            if (cur == -1)
                break;
        }
    }

    sort(ALL(ans));

    rep(i, ans.size())
    {
        cout << ans[i] + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3448
#include <iostream>
#include <cmath>
using namespace std;
 
int main(int argc, char const* argv[])
{
    int a, b;
    cin >> a >> b;

    if(b%100 != 0){
        cout << int(b * pow(100, a)) << endl;
    }
    else {
        cout << int((b + 1) * pow(100, a)) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
ab_list = [tuple(map(int,input().split())) for _ in range(M)]

def check():
    halfways = [0 for _ in range(N)]
    for a,b in ab_list:
        if a==1:
            halfways[b] = 1
    for a,b in ab_list:
        if b==N:
            if halfways[a] == 1:
                return True
    return False

if check():
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 88132
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  int N, Y; scanf("%d%d", &N, &Y);
  Y /= 1000;

  for (int i = 0; i <= N; i++){
    for (int j = 0; i + j <= N; j++){
      int now = i * 10 + 5 * j + (N - i - j);
      if (now == Y){
        printf("%d %d %d\n", i, j, N - i - j);
        return 0;
      }
    }
  }
  printf("-1 -1 -1\n");

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const long long INF = 1LL << 60;

int main() 
{
    string s;
    pair<string,int> p;
    vector<string> v;
    vector<string> u;
    while(cin >> s){
        v.push_back(s);
        bool e = true;
        for(int i = 0; i < u.size(); i++){
            if(u[i] == s){
                e = false;
            }
        }
        if(e) u.push_back(s);
    }
    int n = u.size();

    int cnt[n];
    for(int i = 0; i < n; i++){
        cnt[i] = 0;
    }
    int l = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < v.size(); j++){
            if(u[i] == v[j]){
                cnt[i]++;
            }
            int m = v[j].size();
            l = max(l,m);
        }
    }
    int k = 0;
    for(int i = 0; i < n; i++){
        k = max(k,cnt[i]);
    }
    for(int i = 0; i < n; i++){
        if(cnt[i] == k){
            cout << u[i] << ' ';
        }
    }
    for(int i = 0; i < n; i++){
        if(u[i].size() == l){
            cout << u[i] << endl;
        }
    }
}


Measured memory_bytes: 3168
vs = set()
from collections import defaultdict
def dfs_w(d, stack):
    depthh = defaultdict(int)
    path = [0]
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(v)
            pvs.add(v)
            depthh[v] = depthh[parent] + dpd

            for u, dpd in d[v]:
                if u in pvs:
                    if depthh[u] != depthh[v] + dpd:
                        return False
                if u in vs:
                    continue
                stack += [(-v, dpd), (u, dpd)]
        else:
            path.pop()

    return True
#    return S, F, depth, depthh

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 123912
def main():
    n, T = map(int, input().split())
    min_c = 1000
    is_able = False

    for _ in range(n):
        c, t = map(int, input().split())
        if t <= T:
            is_able = True
            if c < min_c:
                min_c = c

    if is_able:
        print(min_c)
    else:
        print("TLE")


if __name__ == "__main__":
    main()


Measured memory_bytes: 62324
#include<stdio.h>
#define min(a,b) ((a) < (b) ? a : b)
#define max(a,b) ((a) > (b) ? a : b)
main()
{

    int i,a[100000],count;
    count=0;
    for(i=0;i<=100000;i++)
    {
        scanf("%d",&a[i]);
        count++;
        if(a[i]==0)
            break;
    }
    for(i=0;i<count-1;i++)
    {
        printf("Case %d: %d\n",i+1,a[i]);
    }


    return 0;




}



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

typedef long long int ll;
typedef long double ld;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MOD (ll)(1e9 + 7)
#define vi vector<int>
#define vii vector<vector<int> >
#define vl vector<ll>
#define vll vector<vector<ll> >
#define vc(T, nm) vector<T> nm
#define pb push_back
#define popb pop_back
#define si set<int>
#define sl set<ll>
#define F first
#define S second
#define pii pair<int, int>
#define mp make_pair
#define ins insert
#define ers erase
#define endl "\n"
#define mul(a, b) ((a % MOD) * (b % MOD)) % MOD
#define adr(a, b) ((a % MOD) + (b % MOD)) % MOD
#define FORA(x, s, e, inc) for(ll x = s; x != e; x += inc)
#define ROFA(x, s, e, inc) for(ll x = s; x != e; x -= inc)
#define FOR(x, s, e) FORA(x, s, e, 1)
#define ROF(x, s, e) ROFA(x, s, e, 1)
#define loop(x, n) FOR(x, 0, n)
#define rd1(t, a) 					t a; cin >> a;
#define rd2(t, a, b) 				rd1(t, a); rd1(t, b); 
#define rd3(t, a, b, c) 			rd2(t, a, b); rd1(t, c);
#define rd4(t, a, b, c, d) 			rd3(t, a, b, c); rd1(t, d);
#define rd5(t, a, b, c, d, e) 		rd4(t, a, b, c, d); rd1(t, e);
#define rd6(t, a, b, c, d, e, f) 	rd5(t, a, b, c, d, e); rd1(t, f);
#define rdA(t, nm, len)				t nm[len]; loop(i, len) {cin >> nm[i];}
#ifdef DEBUG
	#define deb(v) cout << endl << #v << ": " << v << endl
	#define db1(v) cout << endl << #v << ": " << "[ "; for(auto x: v) {cout << x << " ";}; cout << "]" << endl;
	#define db2(v) cout << endl << #v << ": " << endl; for(auto r: v) {cout << "[ "; for(auto x: r) {cout << x << " ";}; cout << "]" << endl;};
	#define dbl cout << "-------------------------------" << endl
#else
	#define deb(v)
	#define db1(v)
	#define db2(v)
	#define dbl
#endif

ll cav(ll q) {
    ll cl = (-1 + sqrt(1 + 8 * q)) / 2;
    
    return cl;
}

void SieveOfEratosthenes(int n, vl &pms)  {
	ll on = n; 
//    n = sqrt(n);
    bool prime[n+1]; 
//    vector<bool> prime(n + 1, );
    memset(prime, true, sizeof(prime)); 
  
    for (int p = 2; p*p <= on; p++) { 
        if (prime[p] == true) {
            for (int i=p*p; i<=on; i += p) 
                prime[i] = false; 
        } 
    }
    
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          pms.pb(p);
}

void solve() {
 	rd1(ll, n);
	ll on = n;
	map<ll, ll> m;
	vl pms;
	SieveOfEratosthenes(1001111, pms);
	ll tp = n;
	for(auto x: pms) {
	    if(n % x == 0) {
	        ll ct = 0;
	        while( n % x == 0 ) {
	            ct++;
	            n = n / x;
	        }
	        m[x] = ct;
	    }
	}
	if(n > 2) {
	    m[on] = 1;
	}
	
	int ans = 0;
	for(auto x: m) {
	    ll prime = x.F, pwr = x.S;
	    ans += cav(pwr);
	}
	
	cout << ans;
}

int main() {
	
	fastio;

//	rd1(ll, t);
 	ll t = 1;

    while(t--) {
//        deb(t);
        solve();
    }
    
	return 0;
}

Measured memory_bytes: 5264
#include <stdio.h>
using namespace std;

class Node
{
public:
	int key;
	Node* previous;
	Node* next;
};

class DoublyLinkedList
{
private:
	Node* sentinel;
public:
	DoublyLinkedList ()
	{
		sentinel = new Node;
		sentinel->previous = sentinel;
		sentinel->next = sentinel;
	}
	~DoublyLinkedList ()
	{
		Node* element = sentinel->next;

		while (element != sentinel)
		{
			element = element->next;
			delete element->previous;
		}

		delete sentinel;
	}

	void Insert (int key)
	{
		Node* newElement = new Node;
		newElement->key = key;

		Node* firstElement = sentinel->next;
		
		sentinel->next = newElement;
		newElement->previous = sentinel;
		newElement->next = firstElement;
		firstElement->previous = newElement;
	}
	void Delete (int key)
	{
		Node* element = sentinel->next;

		//1??¨?????????????????????????????????
		while (element != sentinel && element->key != key)
		{
			element = element->next;
		}

		if (element != sentinel)
		{
			Node* previousElement = element->previous;
			Node* nextElement = element->next;

			previousElement->next = nextElement;
			nextElement->previous = previousElement;

			delete element;
		}
	}
	void DeleteFirst ()
	{
		Node* firstElement = sentinel->next;
		Node* secondElement = firstElement->next;

		if (firstElement != sentinel)
		{
			sentinel->next = secondElement;
			secondElement->previous = sentinel;

			delete firstElement;
		}
	}
	void DeleteLast ()
	{
		Node* lastElement = sentinel->previous;
		Node* lastPreviousElement = lastElement->previous;

		if (lastElement != sentinel)
		{
			sentinel->previous = lastPreviousElement;
			lastPreviousElement->next = sentinel;

			delete lastElement;
		}
	}
	void PrintData ()
	{
		Node* element = sentinel->next;

		while (element != sentinel->previous)
		{
			printf ("%d ", element->key);
			element = element->next;
		}
		printf ("%d\n", sentinel->previous->key);
	}
};

int main ()
{
	DoublyLinkedList list;

	int processCount;

	scanf ("%d", &processCount);

	for (int lp = 0; lp < processCount; lp++)
	{
		char command[20];
		scanf ("%s", command);

		if (command[0] == 'i')
		{
			int key;
			scanf ("%d", &key);
			list.Insert (key);
		}
		else if (command[6] == 'F')
		{
			list.DeleteFirst ();
		}
		else if (command[6] == 'L')
		{
			list.DeleteLast ();
		}
		else
		{
			int key;
			scanf ("%d", &key);
			list.Delete (key);
		}
	}

	list.PrintData ();

	return 0;
}

Measured memory_bytes: 33920
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<stdio.h>
using namespace std;

int main() {
	int n, k;
	int x[110];
	int d = 0;
	cin >> n;
	cin >> k;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < n; i++) {
		if (2 * x[i] < k)
			d += x[i];
		else
			d += k - x[i];
	}
	cout << 2 * d << endl;
}

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

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

using namespace std;

int main() {
  long long n, m;
  std::cin >> n >> m;

  if (n == 1) {
    n = 1;
  } else {
    n -= 2;
  }

  if (m == 1) {
    m = 1;
  } else {
    m -= 2;
  }

  std::cout << n * m << std::endl;

  return 0;
}


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

from collections import Counter

Acnt = Counter(A)

ans = [-1] * 2
for key,cnt in Acnt.items():
    if cnt >= 4:
        if key > ans[0]:
            ans[0] = key
        if key > ans[1]:
            ans[1] = key
    elif cnt >= 2:
        if key > ans[0]:
            ans[0] = key
    
    ans.sort()

if -1 in ans:
    print(0)
else:
    print(ans[0] * ans[1])

Measured memory_bytes: 18316
#include<stdio.h>

int main(void){
    int a1,a2,a3;
    
    scanf("%d %d %d",&a1,&a2,&a3);
    if(a1+a2+a3>=22){
        printf("bust\n");     
    }
    else{
        printf("win\n");
    }

    return 0;
}

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


#define ALL(a) 		(a.begin() , a.end())
#define ll 			long long int
#define ff          first
#define ss          second
#define pb          push_back
#define ar 			array
#define mp 			make_pair
#define f(i,a,b)   	for(ll i =a;i<=b;i++)
#define inf 		INT_MAX
#define pll 		pair<ll,ll>
#define mat 		vector<vector<ll>>

const ll INF = 1e18;
void init(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE 
		freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
}
 
bool checkp2(ll n){
	return n && !(n & (n-1));
}

ll numsetbit(ll n){
	ll count = 0;
	for(;n;count++){
		n = n & (n-1);
	}
	return count;
}
 
ll power(ll x , ll n , ll mod){
    x = x % mod;
	ll po = 1;
	while(n){
		if(n & 1){
			po = (po*x) % mod;
		}
		n = n>>1;
		x = ((x % mod) * (x % mod)) % mod;
	}
	return po;
}
 
bool isPrime(ll x){
	if(x < 2)
		return 0;
	for(ll y = 2; y * y <= x; y++){
		if(x % y == 0){
			return 0;
		}
	}
	return true;
}





void solve(){


	string s;
	cin>>s;
	ll count = 0;
	for(ll i= 0;i<s.length();i++){
		count += s[i] - '0';
		count %= 9;
	}
	if(count % 9 == 0){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}



}

int main(){
	
	init();
	ll t = 1;
	//cin>>t;
	for(ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Measured memory_bytes: 3740
import itertools
import sys
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
a=[]
for i in range(1,n+1):
    a.append(i)
c=tuple(p)
d=tuple(q)
cnt=0
ans=0
ansl=0
if c==d:
    print(0)
    sys.exit()
for i in itertools.permutations(a):
    
    if c==i:
        ans=cnt
    elif d==i:
        ansl=cnt
    cnt+=1
print(abs(ans-ansl))

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.Scanner;

public class Main{
	static int nine[] = { 9, 81, 729, 6561, 59049 };
	static int six[] = { 6, 36, 216, 1296, 7776, 46656 };

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();

		ArrayList<Integer> arr = new ArrayList<>();

		arr.add(N);

		int wk;
		int wk9;
		int wk6;
		for (int i = 0; true; i++) {
			for (int j = 0; j < Math.pow(2, i); j++) {
				wk = arr.get((int) Math.pow(2, i) - 1 + j);

				wk9 = wk - getNine(wk);
				wk6 = wk - getSix(wk);

				if(wk9 == 0 || wk6 == 0) {
					System.out.println(i+1);
					return;
				}
				arr.add(wk9);
				arr.add(wk6);
			}
		}
	}

	public static int getNine(int a) {
		for (int i = 1; i <= nine.length; i++) {
			if (a >= nine[nine.length - i]) {
				return nine[nine.length - i];
			}
		}
		return 1;
	}

	public static int getSix(int a) {
		for (int i = 1; i <= six.length; i++) {
			if (a >= six[six.length - i]) {
				return six[six.length - i];
			}
		}
		return 1;
	}

}

Measured memory_bytes: 22404
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Func cin2;
    void calc()
    {
        cin = new Scanner();
        cin2 = new Func();
        int N=cin.nextInt();
        int[] a=cin.ArrayInt(N,0);
      int count=0;
      for(int i=1;i<N-1;i++)
      {
        if(a[i-1]<a[i]&&a[i]<a[i+1])count++;
        else if(a[i+1]<=a[i]&&a[i]<=a[i-1])count++;
      }
      Console.WriteLine(count);
        
    }
}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Answer
{
    public void Int2DArrayAns(int[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
    public void Char2DArrayAns(char[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
}

class Func
{
    public long GCDLong(long a, long b)
    {
        while(a!=0)
        {
          long t=a;
          a=b%a;
          b= t;
        }
      
        return b;        
    }
}


Measured memory_bytes: 13140
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Arrays;

public class Main {

	static FastScanner sc = new FastScanner();

	public static void main(String[] args) throws Exception {
		int[] hist = new int[256];
		int[] I = new int[256];
		double[] en = new double[257];
		StringBuilder sb = new StringBuilder();
		while (true) {
			int N = sc.nextInt();
			if (N == 0) break;
			for (int i = 0; i < N; ++i) {
				double v = 1.0 * (i + 1) / N;
				en[i + 1] = -v * Math.log(v);
				I[i] = sc.nextInt();
			}
			double best = Double.MAX_VALUE;
			int bs = 0;
			int ba = 0;
			int bc = 0;
			for (int s = 0; s < 16; ++s) {
				for (int a = 0; a < 16; ++a) {
					OUT: for (int c = 0; c < 16; ++c) {
						Arrays.fill(hist, 0);
						int r = s;
						for (int i = 0; i < N; ++i) {
							r = (a * r + c) & 0xFF;
							hist[(I[i] + r) & 0xFF]++;
						}
						double e = 0;
						for (int i = 0; i < 256; ++i) {
							if (hist[i] != 0) {
								e += en[hist[i]];
								if (e > best) continue OUT;
							}
						}
						if (e < best - 1e-10) {
							best = e;
							bs = s;
							ba = a;
							bc = c;
						}
					}
				}
			}
			sb.append(bs + " " + ba + " " + bc + "\n");
		}
		System.out.print(sb);
	}

	static class FastScanner {
		Reader input;

		FastScanner() {
			this.input = new BufferedReader(new InputStreamReader(System.in));
		}

		int nextInt() throws IOException {
			int sign = 1;
			int b = input.read();
			while ((b < '0' || '9' < b) && b != '-' && b != '+') {
				b = input.read();
			}
			if (b == '-') {
				sign = -1;
				b = input.read();
			} else if (b == '+') {
				b = input.read();
			}
			int ret = b - '0';
			while (true) {
				b = input.read();
				if (b < '0' || '9' < b) return ret * sign;
				ret *= 10;
				ret += b - '0';
			}
		}
	}

}

Measured memory_bytes: 21468
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	long long N,D;
	cin >> N >> D;
	long long x,y;

	int count=0;
	for(int i=0; i<N; i++){
		cin >> x;
		cin >> y;
		long long x2 = x*x;
		long long y2 = y*y;
		long long D2 = D*D;
		if((x2+y2) <= D2){
			count++;
		}
	}
	cout << count << endl;
	return 0;
}

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

const int inf = 1e9;
const ll linf = 1e18;

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

    int n, l; cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    deque<int> deq;
    for (int i = 0; i < n; i++) {
        while (!deq.empty() && a[deq.back()] >= a[i]) deq.pop_back();
        deq.push_back(i);
        if (i >= l - 1) {
            cout << a[deq.front()] << " \n"[i == n - 1];
            if (deq.front() == i - l + 1) deq.pop_front();
        }
    }
    return 0;
}


Measured memory_bytes: 6808
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define F first
#define S second
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define N 200010
using namespace std;
void solve()
{
    ll n,m,k; cin>>n>>m>>k;
    vector<ll> v1(n),v2(m);
    rep(i,0,n) cin>>v1[i];
    rep(i,0,m) cin>>v2[i];
    vector<ll> vp1(n+1,0),vp2(m+1,0);
    rep(i,1,n+1) vp1[i]=vp1[i-1]+v1[i-1];
    rep(i,1,m+1) vp2[i]=vp2[i-1]+v2[i-1];
    ll ans=upper_bound(all(vp2),k)-vp2.begin()-1;
    for(ll i=1;i<=n;i++)
    {
        if(vp1[i]>k)break;
        auto it=upper_bound(all(vp2),k-vp1[i])-vp2.begin();
        it--;
        ans=max(ans,i+it);
    }
    cout<<ans<<endl;
}
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int t=1;
  //cin>>t;
  //freopen("b2.in", "r", stdin);
  //freopen("output2.txt", "w", stdout);
  for(int i=1;i<=t;i++)
  {
      solve();
  }
  return 0;
}



Measured memory_bytes: 9496
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=998244353,N=2e7+5;
int n,a,b,ans,fac[N],inv[N];

int fpow(int x,int y){
    int res=1;
    for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
    return res;
}

int C(int n,int m){
    if(m<0||n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int calc(int x,int y){
    if(y<=x-1) return 0;
    return (C(x+y,x)-C(x+y,x-1)+mod)%mod;
}

signed main(){
    read(n);read(a);read(b);
    if(!b){
        write(1);
        return 0;
    }
    fac[0]=1;
    for(int i=1;i<=n+n;i++) fac[i]=fac[i-1]*i%mod;
    inv[n+n]=fpow(fac[n+n],mod-2);
    for(int i=n+n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; 
    for(int i=0;i<=n-b;i++){
        int num=calc(i,b-1);
        if(i+b==n){
            if(a==i) ans=(ans+num)%mod;
        }
        else{
            int x=n-b-i-1,y=a-i;
            ans=(ans+num*C(x+y,y)%mod)%mod;
        }
    }
    write(ans);
}

Measured memory_bytes: 312704
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int Max=1e9;

int main()
{
	int n,m;
	int i,j;
	int d[200005],t[200005];
	scanf("%d",&n);
	for(i=1;i<=n;i++){
	    scanf("%d",&d[i]);
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++){
	    scanf("%d",&t[i]);
	}
	sort(d+1,d+n+1);
	sort(t+1,t+m+1);
	int p=1,q=1,ans=0;
	while(p<=n&&q<=m){
		if(d[p]==t[q]){
			p++;
			q++;
			ans++;
		}
		else
		   p++;
	}
	if(ans==m)
	    printf("YES\n");
    else
	   printf("NO\n");
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int n;
int main()
{
	cin>>n;
	for (int i=0;i<10;++i)
	{
		if ((1<<i)<=n)
		{
			continue;
		}
		else
		{
			cout<<(1<<(i-1))<<endl;
			return 0;
		}
	}
	return 0;
}

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

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

  vector<long long> A(N);
  for(int i = 0;i < N;i++) cin >> A[i];

  sort(A.rbegin(),A.rend());
  long long ans = A[0],num = 1;
  for(int i = 1;i < N;i++) {
    if(num == N-1) break;
    ans += A[i];
    num++;
    if(num == N-1) break;
    ans += A[i];
    num++;
  }

  cout << ans << endl;
  
}


Measured memory_bytes: 4780
/* Simplicity and Goodness */

#include <bits/stdc++.h>
using namespace std;
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define deb(x) cout << #x << ' ' << x << '\n'
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define per(i,ini) for(int i=ini;i>=0;i--)
#define tc int tt; scn(tt); while(tt --)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int N = 1e5+2;

#define PI 3.14159265359

int main()
{
    int a, b, h, m;
    cin >> a >> b >> h >> m;

    double hr = (h * 30.0) + (30.0 * m /60);
    double mn = m * 6;
    double deg = abs(hr - mn) * PI;
    deg /= (180.0);

    double c = (a*a) + (b*b) - (2.0 * a * b * cos(deg));
    c = sqrt(c);

    cout << fixed << setprecision(15) << c;

    return 0;   
}

Measured memory_bytes: 4104
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
using ll = long long;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vs = vector<string>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using vm = vector<short>;
using vmm = vector<vector<short>>;
signed main() {
    ll n;
    ll a;
    ll count = 0;
    ll ans = 1;
    ll kako = 0;
    cin >> n;
    for (int i = 0; i <= n; i++) {
        a = i;
        for (int j = 0; j < 10; j++) {
            if (a % 2 == 0) {
                a = a / 2;
                count++;
            }
            else {
                if (count >= kako) {
                    kako = count;
                    ans = i;
                }
            }
        }
        count = 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  int n,k;
  cin>>n>>k;
  if(n%k==0) cout<<0<<endl;
  else cout<<1<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 3608
using DataStructures

function main()
    n, m = parse.(Int, split(readline()))
    a = parse.(Int, split(readline()))

    h = MutableBinaryMaxHeap(a) 

    for i in 1:m
        v, i = top_with_handle(h)
        update!(h, i, v÷2)
    end

    println(sum(pop!(h) for i in 1:length(h)))
end

main()

Measured memory_bytes: 216808
#include <stdio.h>

int main(){
    
    int N;
    int i;
    int x[255] = {0};
    int y[255] = {0};
    int z;
    int sum;
    
    scanf("%d",&N);
    
    
    for(i = 0; i < N; i++){
        scanf("%d",&x[i]);
    }
    for(i = 0; i < N; i++){
        scanf("%d",&y[i]);
    }
    for(i = 0; i < N; i++){
        z = x[i] - y[i];
        if(z > 0)sum = sum + z;
    }
    
    printf("%d",sum);
    

    return 0;
}

Measured memory_bytes: 128
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846
#ifdef LOCAL
#include <sys/types.h>
#include <sys/timeb.h>
#include <intrin.h> 
#include <thread>
#else
#include <sys/time.h>
#endif

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)

const int N = 100005;
int a[N], b[N], r[N];

int main(){
	int n;
	cin >> n;
	REP(i, n)scanf("%d", a + i);
	REP(i, n)scanf("%d", b + i);
	int ret = 0;
	int cnt = 0;
	LL plus = 0;
	REP(i, n) {
		if (a[i] < b[i]) {
			ret++;
			plus += b[i] - a[i];
		}
		else r[cnt++] = a[i] - b[i];
	}
	sort(r, r + cnt, greater<int>());
	if (plus <= 0) {
		cout << 0 << endl;
		return 0;
	}
	REP(i, cnt) {
		plus -= r[i];
		if (plus <= 0) {
			cout << ret + i + 1 << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <set>
using namespace std;
set <int> S;
int sum;
int V[2000005], V2[2000005];
bool X[2000005];
int A[2005];
int ind, ind2, N;
void Read()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> A[i], sum += A[i];
}

void Solve()
{
    V[++ind] = 0;
    X[0] = 1;
    for(int i = 1; i <= N; i++)
    {
        ind2 = 0;
        for(int j = 1; j <= ind; j++)
        {
            if(A[i] + V[j] <= sum / 2 && X[A[i] + V[j]] == 0)
            {
                V2[++ind2] = A[i] + V[j];
                X[A[i] + V[j]] = 1;
            }
        }
        for(int j = 1; j <= ind2; j++)
            V[++ind] = V2[j];
    }
    for(int j = sum / 2; j >= 0; j--)
        if(X[j] == 1)
    {
        cout << sum - j << "\n";
        return;
    }
}
int main()
{
    Read();
    if(N == 1)
    {
        cout << sum << "\n";
        return 0;
    }
    Solve();
    return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=20;
ll k,l,r,len,dig[MAXN],dp[MAXN][MAXN],g[MAXN];
ll chk (ll x) {
	len=0;
	while (x) {
		dig[++len]=x%10;
		x/=10;
	}
	ll ans=g[len];
	for (int j=1;j<dig[len];j++) {ans+=dp[len][j];}
	for (int i=len-1;i>=1;i--) {
		for (int j=dig[i+1]-1;j<=min(dig[i]-1,dig[i+1]+1);j++) {if (0<=j&&j<=9) ans+=dp[i][j];}
		if (abs(dig[i]-dig[i+1])>1) {break;}
	}
	return ans;
}
int main () {
	scanf("%lld",&k);
	for (int i=0;i<=9;i++) {dp[1][i]=1;}
	g[1]=1;
	for (int i=2;i<=11;i++) {
		g[i]=g[i-1];
		for (int j=1;j<=9;j++) {g[i]+=dp[i-1][j];}
		dp[i][0]=dp[i-1][1]+dp[i-1][0];
		for (int j=1;j<=8;j++) {dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];}
		dp[i][9]=dp[i-1][8]+dp[i-1][9];
	}
	l=1,r=1e11;
	//for (int i=70;i<=110;i++) {
	//	printf("%d  %lld\n",i,chk(i));
	//}
	//system("pause");
	while (l<r) {
		ll mid=(l+r)>>1;
		if (chk(mid)-1>=k) {r=mid;}
		else {l=mid+1;}
	}
	printf("%lld\n",l-1);
	return 0;
}

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

int debug(int64_t n, int64_t k, int64_t a[], int64_t val) {
	vector<int64_t> v;
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			v.push_back(a[i] * a[j]);
		}
	}
	sort(v.begin(), v.end());
	int idx = upper_bound(v.begin(), v.end(), val) - v.begin();
	cout << idx << '\n';
	cout << v[idx] << '\n';
	cout << v[idx - 1] << '\n';
}

int main() {
	const int64_t INF = 1e9 + 10;
	const int64_t LINF = 1e18 + 10;

	int64_t n, k; cin >> n >> k;
	int64_t a[n];
	for(int i = 0; i < n; ++i) cin >> a[i];
	sort(a, a + n);
	int64_t plus[n + 2];
	plus[0] = -INF, plus[n + 1] = INF;
	for(int i = 1; i <= n; ++i) {
		plus[i] = a[i - 1];
	}
	int64_t minus[n + 2];
	for(int i = 0; i < n + 2; ++i) {
		minus[i] = plus[(n + 1) - i];
	}
	// ある数midがk番以上であるか
	int64_t ok = LINF, ng = -LINF;
	while(abs(ok - ng) > 1) {
		int64_t mid = (ok + ng) / 2;
		// mid以下を数える
		int64_t cnt = 0;
		for(int i = 0; i < n; ++i) {
			if(a[i] > 0) {
				int ok_idx = 0, ng_idx = n + 1;
				while(abs(ok_idx - ng_idx) > 1) {
					int mid_idx = (ok_idx + ng_idx) / 2;
					int64_t val = a[i] * plus[mid_idx];
					if(mid_idx == 0) val = -LINF;
					if(mid_idx == n + 1) val = LINF;
					if(val <= mid) {
						ok_idx = mid_idx;
					} else {
						ng_idx = mid_idx;
					}
				}
				cnt += (ok_idx < i + 1 ? ok_idx : ok_idx - 1);
			} else if(a[i] == 0) {
				if(0 <= mid) {
					cnt += n - 1;
				}
			} else {
				int ok_idx = 0, ng_idx = n + 1;
				while(abs(ok_idx - ng_idx) > 1) {
					int mid_idx = (ok_idx + ng_idx) / 2;
					int64_t val = a[i] * minus[mid_idx];
					if(mid_idx == 0) val = -LINF;
					if(mid_idx == n + 1) val = LINF;
					if(val <= mid) {
						ok_idx = mid_idx;
					} else {
						ng_idx = mid_idx;
					}
				}
				cnt += (ok_idx < n - i ? ok_idx : ok_idx - 1);
			}
		}
		cnt /= 2;
		// cerr << "mid : " << mid << '\n';
		// cerr << "cnt : " << cnt << '\n';
		if(cnt >= k) {
			ok = mid;
		} else {
			ng = mid;
		}
	}
	cout << ok << '\n';
	// debug(n, k, a, 0);
	return 0;
}

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

ll gcd(ll a,ll b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

ll kaizyou(ll N){
  ll num=1;
  for(ll i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

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

int main(){
  int N;
  cin >> N;
  vector<int>p(N);
  for(int i=0;i<N;i++){
    cin >> p.at(i);
  }
  int num=p.at(0);
  int ans=1;
  for(int i=1;i<N;i++){
    if(p.at(i)<num){
      ans++;
      num=p.at(i);
    }
  }
  cout << ans << endl;
}
      
  
  
  

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int mod=1e9+7;
int n,sum[1000005],a[1000005],ans;
inline int read()
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
inline void write(int x)
{
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++) ans=(ans+a[i]*(sum[n]-sum[i]))%mod;
	write(ans);
	return 0;
}

Measured memory_bytes: 9864
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] array = new int[100010][2];
        for (int i = 0; i < 100010; i++) {
            array[i][0] = i;
        }
        
        while (n-- > 0) {
            int num = sc.nextInt();
            array[num][1]++;
            if (num != 0) array[num - 1][1]++;
            array[num + 1][1]++;
        }
        
        Arrays.sort(array, (a, b) -> Integer.compare(a[1], b[1]));
        int x = array[100009][1];
        
        System.out.println(x);
    }
}


Measured memory_bytes: 63424
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def sRaw():
    return input().rstrip("\r")

def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


def main():
    S = sRaw()
    nLs = [0]*(len(S)+1)
    for idx,c in enumerate(S):
        if c=="<":
            nLs[idx+1] = nLs[idx]+1
    nRs = [0]*(len(S)+1)
    for idx, c in enumerate(S[::-1]):
        if c==">":
            nRs[len(nRs)-idx-2] = nRs[len(nRs)-idx-1]+1
    mas = [max(nLs[idx],nRs[idx]) for idx in range(len(nLs))]
    return sum(mas)

if __name__ == "__main__":
    print(main())


Measured memory_bytes: 89672
import java.util.*;

public class Main{
  public static void main (String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    String S = sc.next();
    long[] num = new long[S.length()+1];
    
    for(int i = 0; i < num.length; i++) {
      num[i] = 0;
    }
    
    for(int i = 0; i < S.length(); i++) {
      if(S.charAt(i)=='<' ) {
        num[i+1] = Math.max(num[i+1],num[i]+1);
      }
    }
    
    for(int i = S.length()-1; i >= 0; i--) {
      if(S.charAt(i)=='>') {
        num[i]=Math.max(num[i+1]+1, num[i]);
      }
    }
    
    long ans = 0;
    for(int i = 0; i < num.length; i++) {
      ans += num[i];
    }
    
    System.out.println(ans);
  
  }
}
    

Measured memory_bytes: 46148