akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
//#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(15); //"for float-base
  // problem"
  ll N;
  cin >> N;
  Vl A(N + 1);
  ll LMAX = 0;
  REP(i, N + 1) {
    cin >> A.at(i);
    LMAX += A.at(i);
  }
  ll ans = 0;

  ll now = 1;

  for (ll j = 0; j < N; j++) {
    ans += now;
    LMAX -= A.at(j);
    //    cout << now << " " << LMAX << endl;  // debug
    if (LMAX <= 0 || now - A.at(j) <= 0) {
      cout << -1 << endl;
      return 0;
    }
    now = min((now - A.at(j)) * 2, LMAX);
  }

  if (now != A.at(N)) {
    cout << -1 << endl;
    return 0;
  }
  ans += A.at(N);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
#define assem99 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define f(i,a,b) for(int i=a; i<b; i++)
#define F first
#define S second
#define sz(a) (int)(a).size()
#define ReadFile freopen("input.txt","r",stdin)
#define WriteFile freopen("output.txt","w",stdout)
int x[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int y[8] = { -1, 0, 1, -1, 1, -1, 0, -1 };
const int MOD = 1e9 + 7, N = 2e5 + 5;
const double pi = acos(-1);

ll fact[N], inv[N], freq[30];

ll fp(ll b, ll p)
{
    if (p == 0)
        return 1;
    ll ans = fp(b, p / 2);
    ans = (ans * ans) % MOD;

    if (p % 2 != 0)
        ans = (ans *(b % MOD)) % MOD;
    return ans;
}

void calc(ll n)
{
    fact[0] = inv[0] = 1;
    for (ll i = 1; i <= n; i++)
    {
        fact[i] = (i * fact[i - 1]) % MOD;
        inv[i] = fp(fact[i], MOD - 2);
    }
}

ll ncr(ll n, ll r)
{
    return ((fact[n] * inv[r]) % MOD * inv[n - r]) % MOD;
}

ll gcd(ll a, ll b)
{
    if (!a)return b;
    return gcd(b % a, a);
}

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

int arr[N];

int main()
{
    assem99;

    int n; cin>>n;
    int arr[N], left[N], right[N];
    f(i, 1, n + 1) cin>>arr[i];
    left[0] = arr[0], right[n] = arr[n];
    f(i, 1, n + 1) left[i] = gcd(arr[i], left[i - 1]);
    for(int i = n - 1; i >= 1; i--) right[i] = gcd(right[i + 1], arr[i]);
    int ans = max(left[n - 1], right[2]);
    f(i, 2, n)
    {
        int g = gcd(left[i - 1], right[i + 1]);
        ans = max(ans, g);
    }
    cout<<ans;

    return 0;
}

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

int main() {
  int a,b;
  
  cin >> a >> b;
  
  if((a==1)&&(b!=1)){
    cout << "Alice";
  }
  else if((a!=1)&&(b==1)){
    cout << "Bob";
  }
  
  else if(a>b){
    cout << "Alice";
  }
  
  else if(a<b){
    cout << "Bob";
  }
  
  else if(a==b){
    cout << "Draw";
  }
    
}


Measured memory_bytes: 256
<?php
 
$file_handle = fopen('php://stdin', "r"); //fopen()は同位フォルダにファイルがあればその名前のみでOK
//$file_handle = fopen('aoj0235_in.txt', "r");
 
//dfs（再帰ver）(根から葉の親までの距離総計を$leafに格納していく)
function dfs($cur) {
    //グローバル変数定義
    global $dist;
    global $leaf;
    global $flag;
     
    //終了条件不要
     
    $childnode = childnode($cur['node']);
    if (empty( $childnode )) return;
    foreach ($childnode as $island_num => $distance) {
    	if ( $flag[$island_num] === 1 ) continue;
        $grandchildnode = childnode($island_num);
        if (!empty($grandchildnode)) {
            $new['node'] = $island_num;
            $new['dist'] = $cur['dist'] + $dist[$cur['node']][$new['node']];
            $flag[$island_num] = 1;
            dfs($new);
        } else {
            $leaf[$cur['node']] = $cur['dist'];     //ここが葉の親ならば
            $dist[$cur['node']][$island_num] = 0;   //バグの修正。孫ノードが存在しない橋への距離を０に。
            $dist[$island_num][$cur['node']] = 0;   //バグの修正。孫ノードが存在しない橋への距離を０に。
        }
    }
}
 
//子ノード抽出
function childnode($island){
    global $dist;
    global $flag;
   //未探索のみ子ノードとして取り出す
   $childnode = array();
   if (!empty($dist[$island])){
       foreach ($dist[$island] as $key => $val){
           if ($flag[$key] !== 1) {
               $childnode[$key] = $val;
           }
       }
   }
   return $childnode;
}
 
//最も根から葉の親までの距離が大きいものを取り出す
function max_dist($leaf){
    $max = 0;
    foreach ($leaf as $key => $val){
        if ($max < $leaf[$key]){
            $max = $leaf[$key];
        }
    }
    return $max;
}
 
function calc(){
    global $dist;
    global $leaf;
    global $max_dist;
    //まずは葉の親までの全部の橋のコストを合計して2倍。
    $sum = 0;
    foreach($dist as $key => $val){
        foreach($dist[$key] as $d2){
            $sum += $d2;
        }
    }
    //$sum = $sum*2;
     
    //$sum から、根から葉の親までの距離が最も大きいものをマイナス
    $sum -= $max_dist;
    return $sum;
}
 
while (1){
    //変数の初期化
    $dist = array();
    $leaf = array();    //$leaf[葉の親のnum] = 根からの距離
    $flag = array();	//探索済みかどうか
 
    //ファイル読み込み
    $stdin = fscanf($file_handle, '%d');    //fscanf()で読み込んだものは配列として格納される
    $n = $stdin[0];
    //終了条件
    if ($n == 0){
        break;
    }
     
    for ($i=0; $i < $n-1; $i++){
        $info = fscanf($file_handle, '%d %d %d');
        $parent = $info[0]; $child = $info[1]; $distance = $info[2];
        $dist[$parent][$child] = $distance;
        $dist[$child][$parent] = $distance;
    }
    
    for ($i=1; $i<=$n; $i++){
    	$flag[$i] = 0;	//すべての島を未探索に。
    }
    
 
    //探索
    $stack['node'] = 1;     //スタートを$stackに入れて開始
    $stack['parent'] = NULL;
    $stack['dist'] = 0;
    $flag[1] = 1;	//最初の島を探索済みにする
    dfs($stack);
    $max_dist = max_dist($leaf);
    $sum = calc();
    
    //出力
    echo $sum;
    echo PHP_EOL;
}
 
fclose($file_handle);

Measured memory_bytes: 6776
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
ll gcd(ll x, ll y) {
	if (x < y)swap(x, y);
	if (y == 0)return abs(x - y);
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
///////////////////////////////////////

int main() {
	int a, b, c; cin >> a >> b >> c;
	int t = a;
	a = b;
	b = t;
	int T = a;
	a = c;
	c = T;
	cout << a << " " << b << " " << c << endl;
	return 0;
}


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

using namespace std;

//#define double long double

const double EPS = 1e-6;
#define eq(a, b) (fabs((a)-(b)) < EPS)

struct Point {
  double x, y;
  Point(double x=0, double y=0):x(x), y(y){}
  Point operator+(Point p) {return Point(x+p.x, y+p.y);}
  Point operator-(Point p) {return Point(x-p.x, y-p.y);}
  Point operator*(double k) {return Point(x*k, y*k);}
  Point operator/(double k) {return Point(x/k, y/k);}  
};
using Vector = Point;

double dot(Vector a, Vector b) {
  return a.x*b.x+a.y*b.y;
}
double cross(Vector a, Vector b) {
  return a.x*b.y-a.y*b.x;
}
double norm(Vector a) {
  return dot(a, a);
}
double abs(Vector a) {
  return sqrt(norm(a));
}

struct Segment {
  Point p1, p2;
  Segment(Point p1=Point(), Point p2=Point()):p1(p1), p2(p2){}
};
using Line = Segment;

const int CCW = 1;
const int CW = -1;
const int BACK = 2;
const int FRONT =-2;
const int ON = 0;

int ccw(Point p0, Point p1, Point p2) {
  Vector a = p1-p0;
  Vector b = p2-p0;
  if(cross(a, b) > EPS) return CCW;
  if(cross(a, b) < -EPS) return CW;
  if(dot(a, b) < -EPS) return BACK;
  if(norm(a) < norm(b)) return FRONT;
  return ON;
}

bool isIntersectSS(Point p1, Point p2, Point p3, Point p4) {
  return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 &&
	  ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0);
}

bool isIntersectSS(Segment s1, Segment s2) {
  return isIntersectSS(s1.p1, s1.p2, s2.p1, s2.p2);
}

double getDistanceLP(Line l, Point p) {
  return abs(cross(l.p2-l.p1, p-l.p1)/abs(l.p2-l.p1));
}

double getDistanceSP(Segment s, Point p) {
  if(dot(s.p2-s.p1, p-s.p1) < 0.0) return abs(p-s.p1);
  if(dot(s.p1-s.p2, p-s.p2) < 0.0) return abs(p-s.p2);
  return getDistanceLP(s, p);
}

double getDistanceSS(Segment s1, Segment s2) {
  if(isIntersectSS(s1, s2)) return 0;
  return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
	     min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

int main() {
  int N;
  cin >> N;
  vector<Segment> segs(N);
  for(int i = 0; i < N; ++i) {
    Point s, t;
    cin >> s.x >> s.y >> t.x >> t.y;
    segs[i] = Segment(s, t);
  }
  if(N > 10000) {
    printf("%.12f\n", 0.0);
    return 0;
  }

  double ans = LDBL_MAX/2;
  for(int i = 0; i < N; ++i) {
    for(int j = i+1; j < N; ++j) {
      //if(i == j) continue;
      ans = min(ans, getDistanceSS(segs[i], segs[j]));
    }
  }
  //printf("%.12Lf\n", ans);
  printf("%.12f\n", ans);  
  
  return 0;
}



Measured memory_bytes: 5684
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
int main(){
    string s,t; cin >> s >> t;
    int ls,lt; ls = s.size(); lt = t.size();
    vector<vector<int>> index(26);
    rep(i,ls) index[s[i]-'a'].push_back(i);
    rep(i,ls) index[s[i]-'a'].push_back(i+ls);
    
    ll ans = 0;
    int now = 0;
    rep(i,lt){
        if(index[t[i]-'a'].size() == 0){
            puts("-1");
            return 0;
        }
        now = *lower_bound(ALL(index[t[i]-'a']), now) + 1;
        if(now >= ls){
            now -= ls;
            ans += ls;
        }
    }
    ans += now;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1724
#include <stdio.h>
#include <math.h>
int main (void)
{
  int H,W, i, s;
for(;;)
{
  scanf("%d %d", &H, &W);
  if( H == 0 && W == 0) break;
  for(i = 1; i<= H; i++)
  {
      for(s= 1; s<= W; s++)
      {
        printf("#");
      }
      printf("\n");
  }
  printf("\n");
}
  return 0;
}

Measured memory_bytes: 1744
// Author : Mahmoud Tarek

#include <bits/stdc++.h>

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define debug(x , y) cerr << #x << " = " << x << y ;

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;

void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}

void FastInputOutput() {
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}


int n ;
vector < double > a ;

int main(){
 cin >> n ;
 a.resize( n ) ;
 forn( int , i , 0 , n ){
   cin >> a[ i ] ;
 }
 sort( all( a ) ) ;
 double sum = 0 ;
 sum = a[ 0 ] + a[ 1 ] ;
 sum /= 2 ;
 forn( int , i , 2 , n ){
    sum = ( sum + a[ i ] ) / 2 ;
 }
 cout << fixed << setprecision( 5 ) << sum ;
 return 0 ;
}



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

public class Hello
{
    public static void Main()
    {
        // Your code here!
        int N = int.Parse(Console.ReadLine());
        string S = Console.ReadLine();
        
        
        int max = 0;
        
       for(int i = 1;i <= S.Length; i++)  //文字列を2つの配列に分割
       {
          
           int sum = 0;
           string X = S.Substring(0, i);
           string Y = S.Substring(i);
           Dictionary<char, int> dic = new Dictionary<char, int>()
           {
               {'a',0},
               {'b',0},
               {'c',0},
               {'d',0},
               {'e',0},
               {'f',0},
               {'g',0},
               {'h',0},
               {'i',0},
               {'j',0},
               {'k',0},
               {'l',0},
               {'m',0},
               {'n',0},
               {'o',0},
               {'p',0},
               {'q',0},
               {'r',0},
               {'s',0},
               {'t',0},
               {'u',0},
               {'v',0},
               {'w',0},
               {'x',0},
               {'y',0},
               {'z',0},
               
            
           };
           
           List<char> idList = dic.Keys.ToList();
           foreach(var a in idList)
           {
               int indexX = X.IndexOf(a);
               int indexY = Y.IndexOf(a);
               if(indexX != -1 && indexY != -1)
               {
                   dic[a] += 1;
               }
           }
           foreach(var a in dic)
           {
               if(a.Value > 0)
               {
                   sum += 1;
               }
           }
           
           if(sum > max)
           {
               max = sum;
           }
           
           
           
       }
       Console.WriteLine(max);
       
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define C 100003
using namespace std;
 
int main()
{
  int n,i,j;
  cin >> n;
  int a[n];
  map<int,int>ck;
  int mx=0;
  for(i=0;i<n;i++)
  {
     cin >> a[i];
        ck[a[i]]++;
     mx=max(mx,a[i]);
  }
  map<int,int>::iterator itr;
  vector<int>v;
  for(itr=ck.begin();itr!=ck.end();itr++)
  {
    if((itr->second)==1)v.push_back(itr->first);  
  }
  int ans=v.size();
  for(i=0;i<n;i++)
  {
      for(j=(2*a[i]);j<=mx;j+=a[i])
      {
          if(ck[j]==1)
          {
              ans--;ck[j]=-1;
          }
      }
  }
  cout << ans ;
}

Measured memory_bytes: 51356
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T> ostream &operator<<(ostream &os, pair<T, T> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL n, k;
  cin >> n >> k;
  VEC<pair<LL, LL>> a(n);
  REP(i, 0, n) { cin >> a[i].first >> a[i].second; }
  //auto f = [](pair<int, int> a, pair<int, int> b) -> bool {
  //  return a.second < b.second;
  //};
  sort(ALL(a));
  DUMP(a);

  LL cnt = 0;
  REP(i, 0, n) {
    //DUMP(cnt);
    cnt += a[i].second;
    if (cnt >= k) {
      cout << a[i].first << endl;
      break;
    }
  }

  return 0;
}


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

struct _cell {
  struct _cell *next;
  struct _cell *prev;
  int key;
};

typedef struct _cell cell;

cell head = { &head, &head, 0 };

void insert_first(int x) {
  // リストの先頭にキーxを持つ要素を追加する
  cell *new;
  new = (cell *)malloc(sizeof(cell));

  new->next = head.next;
  new->prev = &head;
  new->key = x;
  head.next->prev = new;
  head.next = new;
}

void delete(cell *x) {
  if(x == &head)
    return;

  // xのアドレスを持つ要素を削除する
  x->prev->next = x->next;
  x->next->prev = x->prev;

  free(x);
}

// キーxを持つ要素を探し，その要素を削除する
void search_and_delete(int x) {
  cell *p = head.next;

  while(p != &head && p->key != x)
    p = p->next;

  delete(p);
}

int main(void) {
  int n, i, key;
  char operation[20];
  cell *p;

  scanf("%d", &n);

  for(i = 0;i < n;i++) {
    scanf("%s %d", operation, &key);

    if(strstr(operation, "insert")) {
      insert_first(key);
    } else if(strstr(operation, "deleteFirst")) {
      delete(head.next);
    } else if(strstr(operation, "deleteLast")) {
      delete(head.prev);
    } else if(strstr(operation, "delete")) {
      search_and_delete(key);
    }
  }

  p = head.next;
  while(p != head.prev) {
    printf("%d ", p->key);
    p = p->next;
  }

  printf("%d\n", p->key);

  return 0;
}



Measured memory_bytes: 33048
#include<bits/stdc++.h>
using namespace std;
int cost[15][15];
bool use[15];
int n,m,k;
int ans=0x7fffffff;
int check()
{
	int sum[15]={0};
	int money=0;
	for(int i=1;i<=n;++i)
	{
		if(use[i]==false)  continue;
		money+=cost[i][0];
		for(int j=1;j<=m;++j)  sum[j]+=cost[i][j]; 
	}
	for(int i=1;i<=m;++i)  if(sum[i]<k)  return -1;
	return money;
}
void dfs(int len)
{
	int x=check();
	if(x>=0)  ans=min(ans,x);
	if(len>n)  return ;
	use[len]=true;
	dfs(len+1); 
	use[len]=false;
	dfs(len+1);
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i)
	{
		use[i]=false;
		cin>>cost[i][0];
		for(int j=1;j<=m;++j)
		  cin>>cost[i][j];
	}
	dfs(1);
	if(ans>0x7fffffff-10)  cout<<-1;
	else
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3636
N, M = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
T = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x-=1
    y-=1
    T[x].append(y)
    T[y].append(x)

s1 = set()
def dfs(x):
    s1.add(x)
    s2 = set([x])
    stack = [x]
    while stack:
        u = stack.pop()
        for v in T[u]:
            if v not in s1 and v not in s2:
                s1.add(v)
                s2.add(v)
                stack.append(v)
    return s2

ans = 0
for i in range(N):
    if i in s1:
        continue
    I = dfs(i)
    PI = set(P[i] for i in I)
    ans += len(I.intersection(PI))
print(ans)

Measured memory_bytes: 44252
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val N, M = sc.nextInt()
    val G = Array.fill[List[Int]](N+1)(Nil)
    (0 until M) foreach { _ =>
      val u, v = sc.nextInt()
      G(u) = v :: G(u)
    }

    val dp = Array.fill(N+1)(-1)
    val stack = new scala.collection.mutable.Stack[Int]
    (1 to N) foreach { u =>
      if (dp(u) == -1) {
        stack.push(u)
        while (stack.nonEmpty) {
          val u = stack.pop()
          if (u < 0) {
            dp(-u) = 0
            G(-u).foreach { v =>
              dp(-u) = dp(-u) max (dp(v) + 1)
            }
          } else {
            stack.push(-u)
            G(u).foreach { v =>
              if (dp(v) == -1)
                stack.push(v)
            }
          }
        }
      }
    }
    println(dp.max)
  }

}


Measured memory_bytes: 76812
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define ll long long
using namespace std;
const int N=2e5+5,mo=998244353;
int n,_[N],v[N],mu[N],p[N],ps;
char c[N];
ll ans,tot;
bool b[N];
int main(){
	scanf("%d\n",&n);
	fo(i,2,n){
		if(!b[i])p[++ps]=i,mu[i]=-1;
		for(int j=1,u;(u=i*p[j])<=n;++j){
			b[u]=1;
			if(i%p[j]==0)break;
			mu[u]=-mu[i];
		}
	}
	_[0]=1;
	fo(i,1,n)c[i]=getchar()-'0',tot=(tot*2+c[i])%mo;
	tot=(tot+1)%mo;
	fo(i,1,n-1)if(n%i==0&&(n/i)&1){
		ll tt=0;
		fo(j,1,i)tt=(tt*2+c[j])%mo;
		bool is=1;
		fo(j,i+1,n){
			bool a=c[(j-1)%i+1]^(((j-1)/i)&1);
			if(a==c[j])continue;
			if(a<c[j]){
				is=1;break;
			}
			is=0;break;
		}
		fo(j,1,i-1)if(i%j==0&&((i/j)&1)){
			tt=((ll)tt+mo-v[j])%mo;
		}
		tt=(tt+is)%mo;
		v[i]=tt;
		tot=(tot+mo-tt)%mo;
		ans=(ans+(ll)tt*i*2)%mo;
	}
	cout<<(ans+tot*n*2)%mo;
}

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

using namespace std;

string s,t;

int main() 
{
	int sl,tl,da=1e4;
    cin>>s>>t;
    sl=s.length();
	tl=t.length();
    for (int i=0;i+tl<=sl;i++) 
	{
        int zzs=0;
        for(int j=0;j<tl;j++) 
		{
            if(s[i+j]!=t[j]) 
                zzs++;
        }
        da=min(da,zzs);
    }
    cout<<da<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;

int main()
{
    ios::sync_with_stdio(false);
    string a; cin >> a;
    int cnt = 0;
    for (auto g : a){
        cnt += g - '0';
        cnt %= 9;
    }
    cout << (cnt == 0 ? "Yes" : "No") << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    ll n;
    cin>>n;
    ll mn=9999999999999999;
    ll x;
    for(int i=1;i<=5;i++)
    {
        cin>>x;
        if(x<mn)mn=x;
    }
    ll sum=5;
    n-=mn;
    sum+=(n/mn);
    if(n%mn!=0&&n>0)sum++;
    cout<<sum<<'\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=105;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[N][N];
int B[N][N];
int C[N][N];
int match[N], tmp[N];
bool mark[N], ok[N];
bool G[N][N];

bool dfs(int node){
	mark[node]=1;
	for (int v=1; v<=n; v++) if (G[node][v]){
		if (!match[v] || (!mark[match[v]] && dfs(match[v]))){
			match[v]=node;
			return 1;
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>A[i][j];
	for (int j=1; j<=m; j++){
		memset(G, 0, sizeof(G));
		for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) if (A[x][y]) G[x][(A[x][y]+m-1)/m]=1;
		memset(match, 0, sizeof(match));
		memset(ok, 0, sizeof(ok));
//		debug("start")
		int flag=1;
		while (flag--){
			memset(mark, 0, sizeof(mark));
			for (int i=1; i<=n; i++) if (!mark[i] && !ok[i] && dfs(i)) flag=ok[i]=1;
		}
		for (int i=1; i<=n; i++){
			assert(match[i]);
//			debug2(i, match[i])
			int x=match[i];
			for (int y=1; y<=m; y++) if ((A[x][y]+m-1)/m==i){
				B[x][j]=A[x][y];
				A[x][y]=0;
				break ;
			}
		}
	}
	for (int j=1; j<=m; j++){
		for (int i=1; i<=n; i++) tmp[i]=B[i][j];
		sort(tmp+1, tmp+n+1);
		for (int i=1; i<=n; i++) C[i][j]=tmp[i];
	}
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cout<<B[i][j]<<" \n"[j==m];
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cout<<C[i][j]<<" \n"[j==m];
	
	return 0;
}


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

const int MOD = 1000000007;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to))
#define sort(a) sort(a.begin(), a.end())
#define reverse(s) reverse(s.begin(), s.end())
#define p(s) cout << (s) << endl

typedef long long ll;
using namespace std;

template<class T>
void load(vector<T> &v, int n) {
  for (int i = 0; i < n; ++i) {
    T t;
    cin >> t;
    v.push_back(t);
  }
}

template<class T>
T max(vector<T> &v) {
  return *max_element(v.begin(), v.end());
}

template<class T>
T min(vector<T> &v) {
  return *min_element(v.begin(), v.end());
}

void py(bool isUpper = false) {
  if (isUpper) {
    p("YES");
  } else {
    p("Yes");
  }
}

void pn(bool isUpper = false) {
  if (isUpper) {
    p("NO");
  } else {
    p("No");
  }
}

int main() {
  int a;
  string s;
  cin >> a >> s;
  
  if (a >= 3200) p(s);
  else p("red");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define sp  set< pair<ll,ll> >
#define vp vector< pair<ll,ll> >
#define spp set< pair<pair<ll,ll>,ll> >
#define maxe 1000000000000000000
#define ll long long int
#define pb push_back
#define mp  make_pair
#define hurry ios_base::sync_with_stdio(false);cin.tie(NULL)
#define forn(i,n) for(ll (i) = 0 ; (i) < (n) ; ++(i))
#define for1(i,n) for(ll (i) = 1 ; (i) <= (n) ; ++(i))
using namespace std;
int main()
{
  hurry;
ll a,b,c;
string s;
cin>>s;
if(s=="ABC")
cout<<"ARC";
else
cout<<"ABC";

 }

Measured memory_bytes: 3660
N = int(input())
flg = False
for a in range(1,3501):
  for b in range(a,3501):
    A = 4*a*b - N*(a+b)
    B = N*a*b
    if A==B==0:
      c = 1
      flg = True
      break
    elif A!=0 and B%A==0 and B//A>0:
      c = B//A
      flg = True
      break
  if flg:break
print(a,b,c)

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

using namespace std;

/********** TEMPLATE STARTS HERE ***********/

#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define test int t; cin >> t; while(t--)
#define skip continue
#define stop break
#define sz(v) v.size()
#define endl '\n'
#define PI 3.1415926535897932384626433832795
#define EPS 1e-9
#define FR(i, l, r) for(int i = (l); i <= (r); i++)
#define gcd __gcd 
#define FO(i, a) for(auto & i : a)
#define debug(a) cout << #a << ": " << a << endl
#define debug1(a, l, r) FR(i, l, r) cout << a[i] << " "; cout << endl
#define SET(a, b) memset(a, b, sizeof(a));
#define refresh fflush(stdout);

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <pll> vll;

const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;

template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
//template <typename T> inline void out(T x) { cout << x; }

/*********** TEMPLATE ENDS HERE *************/

vi v1;
vi v2;

int ans = INF;

int k;

void solve(vi a, vi b)
{
	for(int i = a.size() - 1; i >= 0; i--)
		if(b.size() < k - i - 1)
			break;
		else
			ans = min(ans, 2 * a[i] + b[k - i - 2]);
}

main()
{
	int n;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		if(x < 0)
			v1.pb(-x);
		else
			v2.pb(x);
	}
	
	reverse(all(v1));
	
	if(v1.empty())
		return cout << v2[k - 1], 0;
	if(v2.empty())
		return cout << v1[k - 1], 0;
	
	if(v1.size() >= k)
		ans = v1[k - 1];
	if(v2.size() >= k)
		ans = min(ans, v2[k - 1]);

	solve(v1, v2);
	solve(v2, v1);
	
	cout << ans;
	
}

//5
//
//v1: 3 4 7 9
//v2: 1 2 3 4

Measured memory_bytes: 1148
N = int(input())
B = list(map(int, input().split())) 
A =[None] * N
A[0] = B[0]

for i in range(1,N-1):
    A[i] = min(B[i-1],B[i])
    i += 1

A[-1] = B[-1]

print(sum(A))


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    v = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = 0

    for vi, ci in zip(v, c):
        if vi >= ci:
            ans += vi - ci

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define mll map<ll,ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define MAX 1e18
#define F first
#define S second
#define all(s) s.begin(),s.end()
#define mod 998244353
ll lcm(ll a,ll b){return (a*b)/(__gcd(a,b));}
ll cel(ll n,ll d){return (n+d-1)/d;}

void hertz()
{
    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
}

int main()
{
    //hertz();
    ll t=5;
    ll x,n;
    cin>>x>>n;
    ll arr[n];
    ll ans=101;
    mll m;

    for (int i = 0; i < n; ++i)
    {
    	cin>>arr[i];
    	m[arr[i]]++;
    }
    ll cur=1;
    ll out;
    for (int i = 0; i < 102; ++i)
    {
    	if(!m.count(i))
    	{
    		if(abs(x-i)<ans)
	    		out=i;
    		ans=min(ans,abs(x-i));
    	}
    }

    cout<<out<<endl;
}

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication46
{
    class Program
    {
        static void Main()
        {
            while (true)
            {
                string a = Console.ReadLine();int s = 0, d = 0;
                if (a == null) break;
                decimal[] b = a.Split().Select(decimal.Parse).ToArray();
                decimal c = b[0]/b[1];string e = c.ToString();
                for( ; d < e.Length; d++)
                {
                    if (e[d] == '.') break;
                }
                for(int r = d + 1; r < b[2] + d + 1; r++)
                {
                    try { s += (int)char.GetNumericValue(e[r]); }
                    catch { s += 0; }
                }
                Console.WriteLine(s);
            }
        }
    }
}

Measured memory_bytes: 9580
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<sstream>

using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a <= 5)
	{
		cout << 0 << endl;
	}
	else if (6 <= a && a <= 12)
	{
		cout << b / 2 << endl;
	}
	else
	{
		cout << b << endl;
	}

}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a) begin(a),end(a)
#define FOR(x,val,to) for(int x=(val);x<int((to));++x)
#define FORE(x,val,to) for(auto x=(val);x<=(to);++x)
#define FORR(x,arr) for(auto &x: arr)
#define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x)
#define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x)
#define REE(s_) {cout<<s_<<'\n';exit(0);}
#define GET(arr) for(auto &i: (arr)) sc(i)
#define whatis(x) cerr << #x << " is " << (x) << endl;
#define e1 first
#define e2 second
#define INF 0x7f7f7f7f
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::string> vs;
typedef int64_t ll;
typedef uint64_t ull;
#define umap unordered_map
#define uset unordered_set
using namespace std;
using namespace __gnu_pbds;

#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; }
template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; }
inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;}
inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}}
inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}}
template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); }
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound
template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 1000001

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m;
    sc(n,m);
    if(n == 2 || m == 2) REE(0)
    if(n == 1 && m == 1) REE(1)
    ll mx = max(n,m);
    if(n == 1 || m == 1){
        REE(mx-2)
    }
    cout << n*m-(2*n+2*m-4);
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
	char c;
	int t = 0, ans = 0;
	while((c = getchar()) != EOF) {
		if('0' <= c && c <= '9') {
			t *= 10;
			t += c - '0';
		}
		else {
			ans += t;
			t = 0;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1120
import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      long n = sc.nextLong();
      long a = sc.nextLong();
      long b = sc.nextLong();

      long cnt = n / (a + b) * a;
      n %= (a + b);
      cnt += Math.min(a, n);
      System.out.println(cnt);
  }
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll ar[M],p[M],c[M],vis[M];

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

	ll k,j,i,h,sm,ans = -1e18,m,v,s,n,mx;

	cin >> n >> k;
	for(i=1;i<=n;++i)
		cin >> p[i];
	ll mn = -1e18;
	ll fl = 0;
	for(i=1;i<=n;++i)
	{
		cin >> c[i];
		if(c[i]>=0)
			fl = 1;
		mn = max(mn,c[i]);
	}
	if(fl == 0)
	{
		cout << mn << "\n";
		return 0;
	}

	for(i=1;i<=n;++i)
	{
		j = p[i];
		h = 0;
		sm = 0;
		while(vis[j] == 0)
		{
			ar[++h] = c[j];
			vis[j] = 1;
			sm += c[j];
			j = p[j];
		}

		m = k/h;
		v = m*sm;
		s = 0;
		mx = 0;
		for(j=1;j<=k%h;++j)
		{
			s += ar[j];
			mx = max(s,mx);
		}
		v += mx;
		ans = max(ans,v);

		if(m>0)
		{
			v = (m-1)*sm;
			s = 0;
			mx = 0;
			for(j=1;j<=h;++j)
			{
				s += ar[j];
				mx = max(s,mx);
			}
			v += mx;
			ans = max(ans,v);
		}

		v = 0;
		s = 0;
		mx = 0;
		for(j=1;j<=min(k,h);++j)
		{
			s += ar[j];
			mx = max(s,mx);
		}
		v += mx;
		ans = max(ans,v);

		for(j=1;j<=n;++j)
			vis[j] = 0;
	}

	cout << ans << "\n";
}


	

Measured memory_bytes: 3800
#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#define all(v) (v).begin(),(v).end()
#define rep(x,y) for(ull i = (x);i<=(y);(x)++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
int dir[8][2] = {-1,0,1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
int dir2[4][2] = {0,1,1,0,0,-1,-1,0};
const ll eps = -3000;

string s;
map<string,string> mp;


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

    mp["Sunny"] = "Cloudy";
    mp["Cloudy"] = "Rainy";
    mp["Rainy"]="Sunny";
    cin>>s;
    cout<<mp[s];
    return 0;
}

Measured memory_bytes: 256
function Main(input) {
	input = input.trim();
  var alphaList = "abcdefghijklmnopqrstuvwxyz".toUpperCase();
  var output = "";
  var H = parseInt(input.split("\n")[0].split(" ")[0]);
  var W = parseInt(input.split("\n")[0].split(" ")[1]);
  for(var i = 1; i <= H; i++){
    var tmp = input.split("\n")[i].split(" ");
    for(var j = 1; j <= tmp.length; j++){
      if(tmp[j - 1] == "snuke"){
         output += alphaList.slice(j - 1,j) + i;
      }
    }
  }
  console.log(output);
  
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7496
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
const int mod = 1000000007;
const ll INF = ll(1e18) + 1;

int main() {
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());

  ll l = -INF, r = INF;
  while (l + 1 < r) {
    ll x = (l + r) / 2;

    bool ok = [&]{
      ll total = 0;
      rep(i, n) {
        ll l = -1; ll r = n;
        while (l + 1 < r) {
          ll middle = (l + r) / 2;
          if(a[i] < 0) {
            if(a[i] * a[middle] < x) r = middle; else l = middle;
          } else {
            if(a[i] * a[middle] < x) l = middle; else r = middle;
          }
        }
        if(a[i] < 0) total += n - r;
        else total += l + 1;
        if(a[i] * a[i] < x) --total;
      }

      total /= 2;
      return total < k;
    }();

    if(ok) l = x; else r = x;
  }

  cout << l << endl;

}

Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>
#include <stack>

using namespace std;

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

const string op = "[(", cl = "])";

int main(){
  int i,j;
  string in;

  while(1){
    getline(cin,in); // cout << in << endl;
    if(in == ".") break;

    bool f = true;
    int N = in.length();
    stack<char> st;

    REP(i,N) REP(j,2){
      if(in[i] == op[j]) st.push(in[i]);
      if(in[i] == cl[j]){
        if(!st.empty() && op[j] == st.top()) st.pop();
        else f = false;
      }
    }

    if(!st.empty()) f = false;
    cout << ((f) ? "yes" : "no") << endl;
  }

  return 0;
}

Measured memory_bytes: 904
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

struct edge {
    ll to, cost;
};

int V;
vector<edge> G[1000000];
ll d[1000000];

void addedge(int st, int ed, ll co) {
    edge e;
    e.to = ed;
    e.cost = co;
    G[st].push_back(e);
}

bool bipartite() {
    fill(d, d + V, -1);
    while (true) {
        int num = 0;
        for (int i = num; i < V; i++) {
            if (d[num] == -1) {
                break;
            }
            num++;
        }
        if (num == V) {
            return true;
        }
        d[num] = 0;
        queue<int> que;
        que.push(num);
        while (que.size() > 0) {
            int base = que.front();
            que.pop();
            int s = G[base].size();
            for (int i = 0; i < s; i++) {
                int to = G[base][i].to;
                if (d[to] == -1) {
                    if (d[base] == 0) {
                        d[to] = 1;
                    } else {
                        d[to] = 0;
                    }
                    que.push(to);
                } else {
                    if (d[to] == 1 && d[base] == 1) {
                        return false;
                    } else if (d[to] == 0 && d[base] == 0) {
                        return false;
                    }
                }
            }
        }
    }
}

int main() {
    ll N, M;
    cin >> N >> M;
    V = N;
    REP(i, 0, M) {
        ll a, b;
        cin >> a >> b;
        addedge(a - 1, b - 1, 1);
        addedge(b - 1, a - 1, 1);
    }
    bool ok = bipartite();
    if (ok) {
        ll zero = 0, one = 0;
        REP(i, 0, N) {
            if (d[i] == 0) {
                zero++;
            } else {
                one++;
            }
        }
        cout << zero * one - M << endl;
    } else {
        cout << N * (N - 1) / 2 - M << endl;
    }
}


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

const unsigned int INF = 1 << 30;
const int MAX_N = 110;
const int MAX_V = 10010;

int main() {
  unsigned int dp[MAX_N][MAX_V];
  int N;
  unsigned int W, weight[MAX_N], value[MAX_N];

  cin >> N >> W;
  for (int i = 0; i < N; ++i) {
    cin >> value[i] >> weight[i];
  }
  for (int i = 0; i < MAX_N; ++i) {
    for (int j = 0; j < MAX_V; ++j) {
      dp[i][j] = INF;
    }
  }

  dp[0][0] = 0;

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < MAX_V; ++j) {
      if (j >= value[i]) {
        dp[i + 1][j] = min(dp[i + 1][j],dp[i][j - value[i]] + weight[i]);
      }
      dp[i + 1][j] = min(dp[i + 1][j],dp[i][j]);
    }
  }

  unsigned int res = 0;
  for (int i = 0; i < MAX_V; ++i) {
    if (dp[N][i] <= W) {
      res = i;
    }
  }

  cout << res << endl;
  
  return 0;
}



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

uint64_t gcd_impl(uint64_t n, uint64_t m) {
    for (int i = 0; i < 10; ++i) {
        uint64_t t = n - m;
        bool q = m > t;
        n = q ? m : t;
        m = q ? t : m;
        if (m == 0) { return n; }
    }
    return gcd_impl(m, n % m);
}

uint64_t gcd(uint64_t n, uint64_t m) {
    return n > m ? gcd_impl(n, m) : gcd_impl(m, n);
}

int main() {
    uint64_t k, x, y, z, total = 0;

	cin >> k;

    for (x = 1; x <= k; x++) {
        for (y = 1; y <= k; y++) {
            for (z = 1; z <= k; z++) {
                total += gcd(x, gcd(y, z));
            }
        }
    }

	cout << total << endl;

	return 0;
}


Measured memory_bytes: 3624
N = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


cnt = 0
for i in range(10, N+1):
    if i % 2 == 0:
        continue
    if len(make_divisors(i)) == 8:
        cnt += 1

print(cnt)

Measured memory_bytes: 3316
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (1..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize2) => {
        read_value!($next, usize) - 2
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!(
    a: usize,
    b: usize,
    );
    for x in 1..20000{
       if  x * 2 / 25 == a && x / 10 == b {
           println!("{}", x);
           return;
       }
    }

    println!("{}", -1);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
typedef long long ll;
ll n;
ll a[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    ll t1 = n/50;
    ll t2 = n%50;
    for(int i = 1; i <= 50; i++){
        a[i] = 50 - i;
        a[i]+=t1;
    }
    for(int i = 1;t2>0;t2--,i++){
        a[i]+=1;
    }
    cout << "50" <<endl;
    for(int i = 1; i <= 49; i++)
        cout << a[i] << " ";
    cout << a[50] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
   char s;
   cin >> s;

   if (isupper(s))
   {
       cout << "A" << endl;
   }
   else
   {
       cout << "a" << endl;
   }

   return 0;

}


Measured memory_bytes: 3584
n=gets.chomp.to_i
A=gets.chomp.split.map(&:to_i)
C=Hash.new{|h, k| h[k] = 0}
A.each{|a| C[a]+=1}
puts C.inject(0){|ans, (k, v)| ans + (v>=k ? v-k : v) }

Measured memory_bytes: 18180
A, B, C, X = int(input()),int(input()),int(input()),int(input())

res = 0
for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if i * 500 + j * 100 + k * 50 == X:
        res += 1
print(res)


Measured memory_bytes: 2940