akhauriyash/Code-Regression huggingface dataset:
class PriorityQueue
  def initialize(array = [])
    @data = []
    array.each{|a| push(a)}
  end

  def push(element)
    @data.push(element)
    bottom_up
  end

  def pop
    if size == 0
      return nil
    elsif size == 1
      return @data.pop
    else
      min = @data[0]
      @data[0] = @data.pop
      top_down
      return min
    end
  end

  private

  def swap(i, j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def size
    @data.size
  end

  def parent_idx(target_idx)
    (target_idx - (target_idx.even? ? 2 : 1)) / 2
  end

  def bottom_up
    target_idx = size - 1
    return if target_idx == 0
    parent_idx = parent_idx(target_idx)
    while (@data[parent_idx] > @data[target_idx])
      swap(parent_idx, target_idx)
      target_idx = parent_idx
      break if target_idx == 0
      parent_idx = parent_idx(target_idx)
    end
  end

  def top_down
    target_idx = 0

    # child がある場合
    while (has_child?(target_idx))
      child_left_idx = target_idx*2+1
      child_right_idx = target_idx*2+2

      # 右側の child が無い場合
      if @data[child_right_idx].nil?
        if @data[target_idx] > @data[child_left_idx]
          swap(target_idx, child_left_idx)
        end
        return
      end

      if @data[child_left_idx] < @data[child_right_idx]
        if @data[target_idx] > @data[child_left_idx]
          swap(target_idx, child_left_idx)
          target_idx = child_left_idx
        else
          return
        end
      else
        if @data[target_idx] > @data[child_right_idx]
          swap(target_idx, child_right_idx)
          target_idx = child_right_idx
        else
          return
        end
      end
    end
  end

  # @param Integer
  # @return Boolent
  def has_child?(idx)
    ((idx * 2) + 1) < (@data.size - 1)
  end
end


N, M = gets.chomp.split(' ').map(&:to_i)

AB = []
N.times do |i|
  AB[i] = gets.chomp.split(' ').map(&:to_i)
end

group_by_day = Hash[AB.group_by{|v|v[0]}.sort]

day_fee = Array.new(M){[]}
group_by_day.each do |k,v|
  day_fee[k-1] = v.map{|j| j[1]}
end

# require 'pry'
# binding.pry

ans = 0
pq = PriorityQueue.new
day_fee.each_with_index do |fees, idx|
  break if idx > M - 1
  fees.each do |fee|
    pq.push(fee*(-1))
  end
  ans += pq.pop.to_i
  # p pq
  # p pq.pop*(-1)
end

puts ans*(-1)


Measured memory_bytes: 38284
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long c = sc.nextLong();
    long[] x = new long[n + 1];
    long[] v = new long[n + 1];
    for (int i = 1; i <= n; i++) {
      x[i] = sc.nextLong();
      v[i] = sc.nextLong();
    }
    long[] a = new long[n + 1];
    long[] aa = new long[n + 1];
    long asum = 0;
    for (int i = 1; i <= n; i++) {
      asum += v[i];
      a[i] = Math.max(a[i - 1], asum - x[i]);
      aa[i] = Math.max(aa[i - 1], asum - x[i] * 2);
    }
    long[] b = new long[n + 2];
    long[] bb = new long[n + 2];
    long bsum = 0;
    for (int i = n; i > 0; i--) {
      bsum += v[i];
      b[i] = Math.max(b[i - 1], bsum - (c - x[i]));
      bb[i] = Math.max(bb[i - 1], bsum - (c - x[i]) * 2);
    }
    long res = 0;
    for (int i = n + 1; i > 0; i--) {
      res = Math.max(res, Math.max(a[i - 1] + bb[i], aa[i - 1] + b[i]));
    }
    System.out.println(res);
  }
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

struct Vertex
{
    vector<int> child;
    vector<int> parent;
    int count = 0;
};

Vertex V[5005];

int main()
{
    ll N, M;
    cin >> N >> M;
    REP(i, M)
    {
        int w, l;
        cin >> w >> l;
        w--;
        l--;
        V[w].child.push_back(l);
        V[l].parent.push_back(w);
    }

    queue<int> q;
    REP(i, N)
    {
        if (V[i].child.size() == 0)
            q.push(i);
    }

    int d = q.size() == 1 ? 0 : 1;
    vector<int> ans;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        ans.push_back(t + 1);
        int add = 0;
        REP(i, V[t].parent.size())
        {
            int p = V[t].parent[i];
            V[p].count++;
            if (V[p].count == V[p].child.size())
            {
                q.push(p);
                add++;
            }
        }
        if (add > 1)
            d = 1;
    }
    for (int i = ans.size() - 1; i >= 0; --i)
    {
        cout << ans[i] << endl;
    }
    cout << d << endl;
    return 0;
}


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

typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> v(9, vector<int>(9, 0));
    rep(i, N) {
        int l = i + 1, r = l % 10;
        if (r == 0) continue;
        //cout << l << endl;
        while (l > 9) l /= 10;
        v[l - 1][r - 1]++;
        //cout << l << " " << r << endl;
    }
    ll ans = 0;
    rep(i, 9) {
        rep(j, 9) {
            //cout << i << j << v[i][j] << v[j][j] << endl;
            ans += v[i][j] * v[j][i];
        }
    }
    cout << ans << endl;
}

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

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MM = 1000000000;
#define mod = MM + 7;
#define INF (ll)1e18
#define pi acos(-1.0)
#define MAX 100005
#define NIL -1
#define rep(i, n) for(int i = 0; i < n; i++)
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main(){
    int n; cin >> n;
    int x[n], y[n], h[n];
    tuple<int,int,int> G = make_tuple(-1,-1,-1);
    rep(i,n){
        cin >> x[i] >> y[i] >> h[i];
        if(h[i] >= 1) G = make_tuple(x[i],y[i],h[i]);
    }
    vector<tuple<int,int,int>> V;
    for(int Cx = 0; Cx <= 100; Cx++){
        for(int Cy = 0; Cy <= 100; Cy++){
            ll V = get<2>(G)+abs(get<0>(G) - Cx)+abs(get<1>(G) -Cy);
            V = max(V,0LL);
            bool flg = true;
            for(int i = 0; i < n; i++){
                ll VV = V-abs(x[i]-Cx)-abs(y[i]-Cy);
                VV = max(VV,0LL);
                if(h[i] != VV) flg = false;
            }
            if(flg){
                cout << Cx << " " << Cy << " " << V << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
#include <cstdio> 
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(a)  (a).begin(),(a).end()
int n,m;
int p[100000],y[100000]; vector<ll> yd[100001];
int main(){
  scanf("%d%d",&n,&m);
  rep(i,m){
    scanf("%d%d",&p[i],&y[i]);
    yd[p[i]].push_back(y[i]);
  }
  rep(i,n){
    sort(ALL(yd[i+1]));
  }
  rep(i,m){
    printf("%012lld\n",ll(p[i])*1000000+int(lower_bound(ALL(yd[p[i]]),y[i])-yd[p[i]].begin())+1);
  }
}


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

#define scl(x) scanf("%lld",&x)
#define sc(x)  scanf("%d",&x)
#define ll long long
#define lop(i,n) for(int i=0;i<n;++i)
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const int N=1e5+100;
int n,l[N],r[N];
set<ii> sl,sr;

ll solve(int xr){
	lop(i,n){
		sl.insert(ii(l[i],i));
		sr.insert(ii(r[i],i));
	}
	ll ret=0;
	int cur=0;
	for(int j=0;j<n;j++){
		int i,to=cur;
		if((j&1)^xr) i=sr.begin()->second;
		else i=sl.rbegin()->second;
		if(cur<l[i])to = l[i];
		else if(cur>r[i])to=r[i];
		ret+=abs(cur-to);
		cur=to;
		sr.erase(ii(r[i],i));
		sl.erase(ii(l[i],i));
	}
	return ret+abs(cur);
}
int main(){
#ifndef ONLINE_JUDGE
	//freopen("i.txt","r",stdin);
#endif
	sc(n);
	lop(i,n)
		sc(l[i]),sc(r[i]);
	cout<<max(solve(0),solve(1));

}


Measured memory_bytes: 12416
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, r, l;}; /*p: 親(parent) l,r*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX], H[MAX];

int height(int);
void print(int u){
  int i, c, n;
  printf("node %d: parent = %d, sibling = ", u, T[u].p);

  if(T[u].p==NIL)printf("%d, ",NIL);
  else if(T[T[u].p].r != u && T[T[u].p].r !=NIL)printf("%d, ",T[T[u].p].r);
  else if(T[T[u].p].l != u && T[T[u].p].l !=NIL)printf("%d, ",T[T[u].p].l);
  else printf("%d, ",-1);
  
  i=0;
  if(T[u].l != NIL)i++;
  if(T[u].r != NIL)i++;
  

  printf("degree = %d, ",i);

  printf("depth = %d, ",D[u]);

 
  printf("height = %d, ",H[u]);
  
  if(T[u].p == NIL/*ここを埋める (fill this blank)*/) printf("root\n");
  else if(T[u].l == NIL && T[u].r == NIL) printf("leaf\n");
  else printf("internal node\n");
  
  
}

void calcDepth(int u, int p){
  D[u] = p;
 
  if(T[u].l != NIL/*ここを埋める(fill this blank)*/) {
    calcDepth(T[u].l, p+1/*ここを埋める(fill this blank)*/);
   }
 
  if(T[u].r != NIL/*ここを埋める(fill this blank)*/) {
    calcDepth(T[u].r, p+1/*ここを埋める(fill this blank)*/);
   }
}

int height(int u){
  int h1 = 0, h2 = 0;

  
  
  if(T[u].l != NIL/*ここを埋める(fill this blank)*/) {
    h1 = height(T[u].l) + 1;
   }
 
  if(T[u].r != NIL/*ここを埋める(fill this blank)*/) {
    h2 = height(T[u].r) + 1 ;
   }
 
  if(h1 > h2)return H[u] =  h1;
  else return H[u] = h2;
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child;
  int root = NIL;
 scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r  = NIL;
  
  for(i=0; i<n; i++){
    scanf("%d", &id);
    for(j = 0, sib = NIL; j<2; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[id].r = child; //左の兄弟に繋げる (connect to left sibling)
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
   
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);
  i = height(root);

  //出力 (output)
  for(i=0; i<n; i++) print(i);

 
  return 0;
}




Measured memory_bytes: 2048
# import collections


def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()

    # sames = 0
    # C = collections.Counter(A)
    # for v in C.values():
    #     if v > 1:
    #         sames += 1

    a_max = A[-1]
    dp = [0] * (a_max + 1)
    # dp = [True] * a_max
    # A = set(A)

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

    r = 0
    for a in A:
        if dp[a] == 1:
            r += 1

    print(r)

    #     if dp[a - 1]:
    #         tmp_a = a * 2
    #         while tmp_a < a_max + 1:
    #             dp[tmp_a - 1] = False
    #             tmp_a += a

    # r = 0
    # for a in A:
    #     if dp[a - 1]:
    #         r += 1

    # print(r - sames)


if __name__ == '__main__':
    main()


Measured memory_bytes: 33248
#include<stdio.h>

int main (void){
        char s[1000000],k[100000];
        scanf("%s",s);
        for(int i = 0;i < 100000 ;i++){
                if(i % 2 == 0){
                        k[i / 2] = s[i];
                }
        }
        puts(k);
        return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//#include "atcoder/all"
//using namespace atcoder;

int digits(ll n){
	if(n == 0) return 1;
	int res = 0;
	while(n > 0){
		n /= 10;
		res++;
	}
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> s(m);
	vector<char> c(m);
	rep(i,m) cin >> s[i] >> c[i];
	rep(i,1000){
		if(digits(i) != n) continue;
		bool ok = true;
		string t = to_string(i);
		rep(j,m){
			if(t[s[j]-1] != c[j]){
				ok = false;
				break;
			}
		}
		if(ok){
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}


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


int main() {
  int n,T;cin>>n>>T;
  int ans=10000;
  for(int i=0;i<n;i++)
  {
    int c,t;cin>>c>>t;
    if(T>=t)
      ans=min(ans,c);
  }
  if(ans==10000)
    cout<<"TLE"<<endl;
  else
  cout<<ans<<endl;
}
      


    


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll a;ld b;
    cin >>a>>b;
    ll ans=a*round(b*100);
    cout <<ans/100<<endl;
    return 0;
}

Measured memory_bytes: 3764
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }
#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }
#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
const int inf = INT_MAX;
const double eps = 0.0000001;
const double PI = acos(-1.0);
const int MOD = 1e9+7;
const int N  = 1e5+5;

int a[N], dp[N], n;

int solve (int k) {
	if (k < 0) return 1;
	if (k == 0) return 0;
	if (dp[k] != -1) return dp[k];
	for (int i = 0; i < n; i++) {
		if (solve(k-a[i]) == 0) {
			dp[k] = 1;
			return 1;
		}
	}
	dp[k] = 0;
	return 0;
}

signed main(){
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif  
    IOS;

    memset(dp,-1,sizeof(dp));
    int k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    	cin >> a[i];
    if (solve(k)) cout << "First";
    else cout << "Second";
    return 0;
}

Measured memory_bytes: 2944
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main(void)
{
  int best,i,j,a,b,c,task[3],con[6],order[6][3]={{0,1,2},
                                             {0,2,1},
                                             {1,0,2},
                                             {1,2,0},
                                             {2,0,1},
                                             {2,1,0}};
  scanf("%d %d %d",&a,&b,&c);
  task[0]=a;
  task[1]=b;
  task[2]=c;

  for(i=0;i<6;i++)
  {
    con[i]=abs(task[order[i][0]]-task[order[i][1]])
           +abs(task[order[i][2]]-task[order[i][1]]);
      //     printf("%d\n",con[i]);
  }

  best=con[0];
  for(i=0;i<5;i++)
  {
    if(con[i]>con[i+1]) best=con[i+1];
  }
  printf("%d\n",best);


  return 0;
}


Measured memory_bytes: 128
n, m = map(int, input().split())
ab = sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0])
ans = 0
i = 0
while m-ab[i][1]>0:
    m -= ab[i][1]
    ans += ab[i][0]*ab[i][1]
    i += 1
ans += ab[i][0] * m
print(ans)

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

typedef long long ll;
typedef pair<int, int> pii; 
const int N = 2e5+10, mod = 1e9+7;

void solve() {
    int n; cin >> n;

    if (n == 1) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
}   

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--) solve();
    return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;

int MAX_M = 101;
int MAX_N = 101;

int max_entry(int *a, int n){
  int ans = a[0];
  for(int i = 0; i < n; i++){
    if(a[i] > ans)
      ans = a[i];
  }
  return ans;
}

int min_entry(int *a, int n){
  int ans = a[0];
  for(int i = 0; i < n; i++){
    if(a[i] < ans)
      ans = a[i];
  }
  return ans;
}


int main(){
  
  int N;
  int M;
  int X[MAX_N];
  int Y[MAX_M];
  /* read input */
  scanf("%d", &N);
  scanf("%d", &M);
  scanf("%d", X);
  scanf("%d", Y);
  for(int i = 1; i <= N; i++){
    scanf("%d", X+i);
  }
  for(int i = 1; i <= M; i++){
    scanf("%d", Y+i);
  }
  
  /* solve problem*/
  if(max_entry(X, N+1) < min_entry(Y, M+1)){
    printf("No War");
  }
  else printf("War");
  
  
  return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif
using namespace std;

int main() {
  int a;
  cin >> a;
  for (int i = -1000; i < 1000; i++) {
    for (int j = -1000; j < 1000; j++) {
      if (powl(i, 5) - powl(j, 5) == a) {
        cout << i << " " << j;
        return 0;
      }
    }
  }
  return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
for (int i = 0; i < N; i++) {
cin >> list[i];
}
// for文
for (int i = 0; i < N; i++) {
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
//配列の内容表示
dout << "====listの内容====\n";
for (int i = 0; i < N; i++) dout << list[i] << endl;
dout << "====ここまで====\n";
*/


Measured memory_bytes: 3688
import sys


def solve():
    step = input()
    flag = True
    
    for i in range(len(step)):
        if i % 2 == 0:
            if step[i] != 'R' and step[i] != 'U' and step[i] != 'D':
                print('No')
                sys.exit()
        else:
            if step[i] != 'L' and step[i] != 'U' and step[i] != 'D':
                print('No')
                sys.exit()
    
    print('Yes')


if __name__ == '__main__':
    solve()

Measured memory_bytes: 3060
n,k = map(int,input().split())
hei_list = []
for i in range(n):
    tmp = int(input())
    hei_list.append(tmp)
hei_list.sort()
for i in range(n-k+1):
    tmp_dist = hei_list[i + k - 1] - hei_list[i]
    if i == 0:
        min_dist = tmp_dist
    elif tmp_dist < min_dist:
        min_dist = tmp_dist
print(min_dist)

Measured memory_bytes: 7384
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()
A = inintl()

ans = 10**6

for a in A:
    cnt = 0
    while a % 2 == 0:
        a /= 2
        cnt += 1
    if cnt < ans:
        ans = cnt

print(ans)


Measured memory_bytes: 63416
S=list(input())
N=len(S)
A=[0 for i in range(N)]
cnt=0
for i in range(1,N):
    if S[i]=="L":
        cnt-=1
        A[i]=cnt
    else:
        cnt=0
cnt=0
for i in range(1,N):
    if S[N-1-i]=="R":
        cnt+=1
        A[N-1-i]=cnt
    else:
        cnt=0
#print(A)
ANS=[0 for i in range(N)]
for i in range(N):
    if abs(A[i])%2==0:
        ANS[A[i]+i]+=1
    else:
        if A[i]>0:
            ANS[A[i]-1+i]+=1
        else:
            ANS[A[i]+1+i]+=1
print(*ANS)

Measured memory_bytes: 11024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

const int M = 33;
const int N = 1001;

char text[N];
char word[N][M];
char tmp[M], ansm[M], ansl[M]; 

int cmp(const void *a, const void *b) {
	return strcmp((char *)a, (char *)b);
}

void solve(int k) {
	qsort(word, k, sizeof(word[0]), cmp);
	int maxs = -1;
	int cnt = 1;
	strcpy(tmp, word[0]);
	strcpy(ansl, word[0]);
	int maxl = strlen(word[0]);
	for (int i=1; i<k; ++i) {
		if (maxl < strlen(word[i])) maxl = strlen(word[i]), strcpy(ansl, word[i]);
		if (!strcmp(tmp, word[i])) ++cnt;
		else {
			if (maxs < cnt) {
				maxs = cnt;
				strcpy(ansm, tmp);
			}
			cnt = 1;
			strcpy(tmp, word[i]);
		}
	}
	if (maxs < cnt) strcpy(ansm, tmp);
}

int main() {
	int i = 0;
	while (scanf("%s", word[i++]) != EOF);
	solve(i);
	cout<<ansm<<" "<<ansl<<endl;
	return 0;
}

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

int main() {
    int const MOD = 1e9 + 7;
    int n, m;
    cin >> n >> m;

    ll ans = 1;
    if (abs(n - m) <= 1) {
        for (ll i = 1; i <= n; i++) ans = (ans * i) % MOD;
        for (ll i = 1; i <= m; i++) ans = (ans * i) % MOD;
        if (n == m) ans = (ans * 2) % MOD;
    } else
        ans = 0;

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


Measured memory_bytes: 3640
#include <stdio.h>
#define N 1000

int t,n,d[N],f[N],M[N][N] = {};
char c[N];

void visit(int);
void depth();

int main(){
  int a,b,c,i,j;
  
  scanf("%d", &n);
  for (i=1;i<=n;i++) {
    scanf("%d%d",&a,&b);
    for (j=1;j<=b;j++) {
      scanf("%d",&c);
      M[a][c] = 1;
    }
  }
  
  depth();
  
  for (i=1;i<=n;i++) {
    printf("%d %d %d\n",i,d[i],f[i]);
  }
  
  return 0;
}

void visit(int a){
  int i;
  
  c[a] = 'G';
  d[a] = ++t;
  for (i=1;i<=n;i++) {
    if (M[a][i] == 1 && c[i] == 'W') {
      visit(i);
    }
  }
  c[a] = 'B';
  f[a] = ++t;
}
  
void depth(){
  int i;
  for (i=1;i<=n;i++) c[i] = 'W';
  t = 0;
  for (i=1;i<=n;i++) if (c[i] == 'W') visit(i);
}

Measured memory_bytes: 996
import java.io.*;
import java.util.Arrays;

public class Main {
    private static int[] pos = new int[5];
    private static int k;

    private static String solver() {
        int min = Arrays.stream(pos).min().getAsInt();
        int max = Arrays.stream(pos).max().getAsInt();
        if(k >= max - min){
            return "Yay!";
        }else{
            return ":(";
        }

    }


    public static void main(String[] args) {

        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(is);

        try {
            for(int i=0; i<5; i++) {
                String[] inputArray = br.readLine().split(" ");
                pos[i] = Integer.parseInt(inputArray[0]);
            }
            String[] inputArray = br.readLine().split(" ");
            k = Integer.parseInt(inputArray[0]);
        } catch (Exception e) {
            e.printStackTrace();
        }

        System.out.println(solver());

    }
}

Measured memory_bytes: 26580
#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

void selectionSort(int n, deque<int> a) {
    int count = 0;
    for (int i = 0; i <= n - 1; ++i) {
        int minj = i;
        for (int j = i; j <= n - 1; ++j) {
            if (a[j] < a[minj]) {
                minj = j;
            }
        }
        if (i != minj) {
            int t = a[i];
            a[i] = a[minj];
            a[minj] = t;
            ++count;
        }
    }

    for (int i = 0; i < n-1; ++i) {
        cout << a[i] << " ";
    }
    cout << a[n-1] << endl << count << endl;
}

int main(int argc, char* argv[]) {
    deque<int> a;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    selectionSort(n, a);

    return 0;
}



Measured memory_bytes: 3108
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9+7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,x,y,z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

template <std::int_fast64_t Modulus> class modint {
  using u64 = std::int_fast64_t;
public:
  u64 a;
  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};
#pragma endregion

int main() {
  cin >> H >> W;
  if(H == 1 || W == 1) cout << 1;
  else cout << (H*W+1)/2;
}




Measured memory_bytes: 256
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,b,c;
	cin>>a>>b>>c;
	if(a+b-c>0)puts("No");
	else puts((c-a-b)*(c-a-b)>4*a*b?"Yes":"No");
	return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>                          //include all library  
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <string.h>
#include <functional> // greater<int> はfunctionalヘッダ
using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)          //REP(i, 10){...} //i=0～i=9までのループ
#define REPR(i, n) for(int i = n;i >= 0;i--)        //REPR(i, 10){...} //i=10～i=0までのループ
#define FOR(i, m, n) for(int i = m;i < n;i++)       //FOR(i, 3, 10){...} //i=3～i=9までのループ
#define FORR(i, m, n) for(int i = m;i >= n;i--)     //FORR(i, 10, 3){...} //i=10～i=3までのループ
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
#define PI 3.141592653589
#define npos -1


int main(){
  int n;
  cin >> n;
  int array[100003] = {};
  int maxi = -1*INF;
  int count=0;

  REP(i,n)
  {
    int num;
    cin >> num;
    array[num] += 1;
    maxi = max(num,maxi);
  }

  REP(i,maxi+1)
  {
    int sum=array[i]+array[i+1]+array[i+2];
    count = max(count,sum);
  }

  cout << count;
}

Measured memory_bytes: 640
#include<stdio.h>
#define N 101
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INF -1

int d[N],color[N],Q[N];
int head=0,tail=0;

void enqueue(int x,int n){
  Q[tail]=x;
  if(tail+1==n)
    tail=0;
  else tail++;
}

int dequeue(int n){
  int x;
  x=Q[head];
  if(head+1==n)
    head=0;
  else head++;
  return x;
}

void bfs(int Adj[N][N],int s,int n){
  int u,v;
  for(u=1;u<=n;u++){
    color[u]=WHITE;
    d[u]=INF;
    Q[u]=0;
  }
  color[s]=GRAY;
  d[s]=0;
  enqueue(s,n);
  while(tail!=head){
    u=dequeue(n);
    for(v=1;v<=n;v++)
      if(Adj[u][v]==1 && color[v]==WHITE){
        color[v]=GRAY;
        d[v]=d[u]+1;
        enqueue(v,n);
      }
    color[u]=BLACK;
  }
}

int main(){
  int n,i,j,Adj[N][N],u,k,v;
  scanf("%d",&n);
  for(i=0;i<N;i++){
    for(j=0;j<N;j++)
      Adj[i][j]=0;
  }

  for(i=1;i<=n;i++){
    scanf("%d%d",&u,&k);
    for(j=1;j<=k;j++){
      scanf("%d",&v);
      Adj[u][v]=1;
    }
  }
  bfs(Adj,1,n);

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



Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
long long n,m=10,sum;
int main()
{
	cin>>n;
	if(n%2==0)
	{
		while(m<=n)
		{
			sum+=n/m;
			m*=5;
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
#include <cctype>
#include <cstdio>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)

int get()
{
    char c;
    while (!isdigit(c=getchar()));
    int k=c-'0';
    for (; isdigit(c=getchar()); k=k*10+c-'0');
    return k;
}

using namespace std;
const int N=3010,mod=1e9+7;
char s[N];
int n,m,ans,c[N][N],f[N][N],a[N];
struct data
{
    int l,r;
    bool operator<(const data &x) const
    {
        return l<x.l || (l==x.l && r>x.r);
    }
} b[N];

int main()
{
    n=get(),m=get();
    rep(i,0,n)
    {
        c[i][0]=1;
        rep(j,1,i)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
    scanf("%s",s+1);
    rep(i,1,n)
        a[i]=a[i-1]+s[i]-48;
    rep(i,1,m)
        b[i].l=get(),b[i].r=get();
    sort(b+1,b+1+m);
    int t=0;
    rep(i,1,m)
        if (b[i].r>b[t].r)
            b[++t]=b[i];
    m=t,b[m+1].l=n+1,f[0][0]=1;
    rep(i,1,m)
    {
        int w=a[b[i].r]-a[max(b[i].l-1,b[i-1].r)];
        int l=min(b[i].r,b[i+1].l-1)-b[i].l+1;
        int mx=b[i].r-b[i].l+1-l;
        rep(j,0,l)
            rep(k,max(0,w-j),mx)
                f[i][k]=(f[i][k]+1ll*f[i-1][j+k-w]*c[l][j])%mod;
    }
    rep(i,0,n)
        ans=(ans+f[m][i])%mod;
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 51200
function main()
	s = readline()
	t = readline()
	ds = Dict{Char, Int}()
	dt = Dict{Char, Int}()
	ss = Array{Int}(length(s))
	st = Array{Int}(length(s))
	for i in 1:length(s)
		if haskey(ds, s[i])
			ds[s[i]] += 1
		else
			ds[s[i]] = 1
		end
		ss[i] = ds[s[i]]
	end
	for i in 1:length(s)
		if haskey(dt, t[i])
			dt[t[i]] += 1
		else
			dt[t[i]] = 1
		end
		st[i] = dt[t[i]]
	end
	if ss == st
		print("Yes")
	else
		print("No")
	end
end

main()

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

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> v1(100001), v2(100001);
  for (int i = 1; i <= n; i++) {
    int temp;
    cin >> temp;
    if (i % 2 == 0) {
      v1[temp].second = temp;
      v1[temp].first++;
    } else {
      v2[temp].second = temp;
      v2[temp].first++;
    }
  }
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());

  if (v1[100000].second == v2[100000].second) {
    cout << min(n - v1[100000].first - v2[99999].first,
                n - v1[99999].first - v2[100000].first)
         << endl;
  } else {
    cout << n - v1[100000].first - v2[100000].first << endl;
  }

  return 0;
}


Measured memory_bytes: 1792
x,n=map(int,input().split())
P=sorted(list(map(int,input().split())))
if n==0:print(x);exit()
ans=10**9
add=0
point=-1
for i in range(-100,200):
    if i==P[add]:
        if add!=n-1:add +=1
        continue
    else:
        if abs(i-x)<ans:
            point=i
            ans=abs(i-x)
print(point)

Measured memory_bytes: 61732
#include<iostream>
using namespace std;
int main(){
  int a,b,c,k;cin>>a>>b>>c>>k;
  int s=0;

  if(k-a>0){ k-=a; s+=a; }
  else if(k-a==0){ cout<<a<<endl; return 0; }
  else{ cout<<k<<endl; return 0;}

  if(k-b>0){ k-=b; }
  else if(k-b==0){ cout<<s<<endl; return 0; }
  else{ cout<<s<<endl; return 0;}

  cout<<s-k<<endl;
  return 0;
}


Measured memory_bytes: 3588
using System;

namespace ABC066C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Int32.Parse(Console.ReadLine());
            string[] bufs = Console.ReadLine().Split(' ');
            int[] res = new int[n];

            if (n % 2 == 0)
            {
                for (int i = 0; i < n / 2; i++)
                {
                    res[i] = Int32.Parse(bufs[(n - 1 - 2 * i)]);
                }

                for (int i = n / 2; i < n; i++)
                {
                    res[i] = Int32.Parse(bufs[(i - n / 2) * 2]);
                }
            }
            else
            {
                for (int i = 0; i <= n / 2; i++)
                {
                    res[i] = Int32.Parse(bufs[(n - 1 - 2 * i)]);
                }

                for (int i = n / 2 + 1; i < n; i++)
                {
                    res[i] = Int32.Parse(bufs[i * 2 - n]);
                }
            }

            for (int i = 0; i < n; i++)
            {
                if(i != 0) { Console.Write(' '); }
                Console.Write(res[i]);
            }
            Console.WriteLine();

        }
    }
}


Measured memory_bytes: 35512
import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N
;


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = parseInt(st.nextToken());
		List<Integer> prices = new ArrayList<>();
		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine());
			prices.add(parseInt(st.nextToken()));
		}

		List<Integer> newP = prices.stream()
			.sorted((a, b) -> {
				return b-a;
			})
			.collect(Collectors.toList());

		int sum = newP.get(0) /2;

		for(int i=1;i<newP.size();i++) {
			sum += newP.get(i);

		}

		System.out.println(sum);

	}

}

Measured memory_bytes: 29268
n = gets.chomp.to_i
x = []
y = []
1.upto(n) do |i|
  x[i], y[i] = gets.chomp.split.map(&:to_i)
end

arr = (1..n).to_a

total = 0.0
t = 0
arr.permutation(n) do |a|
  t += 1
  0.upto(n-2) do |i|
    total += Math.sqrt((x[a[i]]-x[a[i+1]])**2 + (y[a[i]]-y[a[i+1]])**2)
  end
end
p total / t


Measured memory_bytes: 2172
#include<bits/stdc++.h>
using namespace std;
int kvalue[3000];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int n = s.size();
    int j = 0;
    string t = "keyence";
    int m = t.size();
    int breaks = 0;
    string answer = "NO";
    int r = 0;
    string first = "", second = "";
    for(int i = 0 ; i < n; i++)
    {
        if(s[i] == t[j])
        {
            first += s[i];
            j++;

            if(j == m)
            {
                cout << "YES\n";
                return 0;

            }
        }
        else
        {int p = 6;
            int tillnow = first.size();
            int req = 7 - tillnow;
            for(int k = n-1; k >=0 ; k--)
            {
                if(s[k] == t[p])
                {
                    second = s[k] + second;
                    p--;
                    if(second.size() == req)
                    {
                        first = first + second;
                        if(first == t)
                        {
                           // cout << "Hre\n";
                            cout << "YES\n";
                            return 0;
                        }
                    }
                }
                else
                {
                    cout << "NO\n";
                    return 0;
                }


            }

        }




    }



return 0;}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<queue>
#define N (998244353)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> Q;

int p[200010];



int main(void){
    string s;
    cin>>s;
    if(s[s.length()-1]=='3')cout<<"bon";
    else{
        if(s[s.length()-1]=='0'||s[s.length()-1]=='1'||s[s.length()-1]=='6'||s[s.length()-1]=='8')cout<<"pon";
        else cout<<"hon";
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>
#define N 100000

int preParse(int,int);

struct Node{
  int p,l,r,s,deg,dep,h;
};

struct Node T[N];
int main()
{
  int n,i,j,m,hei,a,b;

  scanf("%d",&n);
  for(i=0; i<n; i++){
    T[i].p=-1;
    T[i].s=-1;
  }
  for(i=0; i<n; i++){
    scanf("%d",&j);
    scanf("%d%d",&T[j].l,&T[j].r);
  }
  
  for(i=0; i<n; i++){
    a=T[i].l;
    b=T[i].r;
    if(a==-1 && b==-1)T[i].deg=0;
    else if(a==-1 || b==-1)T[i].deg=1;
    else T[i].deg=2;
    T[a].p=i;
    T[b].p=i;
    T[a].s=b;
    T[b].s=a;
  }
  
  for(i=0; i<n; i++){ 
    m=T[i].p;
    T[i].dep=0;
    while(1){
      if(m==-1)break;
      else {
	m=T[m].p;
	T[i].dep++;
      }
    }

    hei=preParse(i,0);
    T[i].h = hei-1;

    hei=0;

  }

  for(i=0; i<n; i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, ",i,T[i].p,T[i].s,T[i].deg);
    printf("depth = %d, height = %d, ",T[i].dep,T[i].h);

    if(T[i].p == -1)printf("root\n");
    else if(T[i].deg == 0)printf("leaf\n");
    else printf("internal node\n");
  }
  
  return 0;
}

preParse(int u, int h){
  int a=0,b=0;
  if(u==-1){
    return h;
  }
  else h++;

  a=preParse(T[u].l,h);
  b=preParse(T[u].r,h);
  if(a>=b)return a;
  else return b;
}

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

int main(){
  int a=0,b=0,c;
  for(int i=0; i<3; i++){
    cin >> c;
    if(c==7) a++;
    else if(c==5) b++;
  }
  if(a == 1 && b == 2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 3e5 + 10;
int n, a[N];

bool chk(int l, int r) {
    int la = -1, lb = -1, mn = n + 1, mx = -1;
    rep(i, l, r)
        mn = min(mn, a[i]), mx = max(mx, a[i]);
    if (mn != l || mx != r) return 0;
    rep(i, l, r) {
        if (i < a[i]) {
            if (a[i] < la) return 0;
            la = a[i];
        } else if (i > a[i]) {
            if (a[i] < lb) return 0;
            lb = a[i];
        }
    } return 1;
}

int main() {
    cin >> n;
    rep(i, 1, n) scanf("%d", &a[i]);
    rep(i, 1, n) {
        if (i == a[i]) continue;
        int pos;
        for (pos = i; pos <= n - 2; pos += 2)
            if (a[pos + 1] != pos + 1 || a[pos + 2] == pos + 2) break;
        if (!chk(i, pos)) { puts("No"); return 0; }
        i = pos;
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define all(x)     		(x).begin(),(x).end()
#define ub    			upper_bound
#define lb 				lower_bound
#define int 			long long
#define endl			'\n'
#define ff              first
#define ss              second
#define ull		unsigned long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define si 				set<int>		
#define mii             map<int,int>
#define umii			unordered_map<int ,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define rep(i,a,n)		for(int i=a;i<n;++i)
#define repd(i,a,n)		for(int i=a;i>n;--i)
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define Mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define deb(x)			cout<<#x <<"="<<x<<endl;
#define deb2(x,y)		cout<<#x<<"="<<x<<"  "<<#y<<"="<<y<<endl;
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int Pow(int a,int b){int res=1;while(b>0){if(b&1)res*=a;a*=a;b/=2;}return res;}
int MPow(int a,int  b){int res=1;while(b>0){if(b&1)res=(res*a)%Mod;a=(a*a)%Mod;b/=2;}return res%Mod;}
int log(int x){return 64-__builtin_clzll(x)-1;}



void c_p_p()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
struct Node
{
	int a,b,c,d;
	
};
const int Max=1e5+1;
int Dp[101][Max];
int Knapsack(int W[], int V[], int cap,int n)
{
	if(n==0 || cap<0)
		return 0;
	if(Dp[n][cap]==-1)
	{
		if(W[n]<=cap)
		{
			return Dp[n][cap]=max(V[n]+Knapsack(W,V,cap-W[n],n-1),Knapsack(W,V,cap,n-1));
		}
		return Dp[n][cap]=Knapsack(W,V,cap,n-1);

	}
	return Dp[n][cap];
}

int32_t main()
{
	c_p_p();
	memset(Dp,-1,sizeof(Dp));
	int n,cap;
	cin>>n>>cap;
	int W[n+1],V[n+1];
	rep(i,1,n+1)
	{
		cin>>W[i]>>V[i];
	}
	cout<<Knapsack(W,V,cap,n);
	return 0;
}
	

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

int main(){
  int N;
  cin >> N;
  vector<int64_t> vec(N);
  for (int i = 0; i < N; i++) {
   cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());

  bool ans = true;
  for (int i = 0; i < N; i++) {
     if (i>0 && vec.at(i)==vec.at(i-1)){
         ans=false;
         break;         
     }
  }

  if (ans) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9


int main(){

  int N;
  cin >> N;
  vector<int> a(N);
  vector<ll> sum(N+1, 0);
  REP(i, N){
    cin >> a[i];
    sum[i+1] = sum[i] + a[i];
  }
  ll ans = INF * INF;
  FOR(i, 1, N){
    ans = min(ans, abs(sum[i] - (sum[N]-sum[i])));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
# ABC122 B-ATCoder

S = input()
ans = 0
l, r = 0, 0
ls = len(S)

for i in range(ls):
    if S[i] in "ATGC":
        r += 1
    else:
        r += 1
        l = r
    ans = max(ans, r-l)
print(ans)

Measured memory_bytes: 38256
#include <cstdio>
#include <vector>
#include <algorithm>

int main()
{
  int n;
  scanf("%d",&n);
  std::vector<long long> a(n);
  long long S=0;
  for(int i=0;i<n;i++){
    scanf("%lld",&a[i]);
    S+=a[i];
  }
  long long ans=S,s=0ll;
  for(int i=0;i<n;i++){
    s+=a[i];
    ans=std::min(ans,std::max(s,S-s)-std::min(s,S-s));
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 1792
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <queue>
using namespace std;

int main(){
	int n;
	cin >> n;
	int inf = n + 10;
	vector<int> dp(n + 1, inf);
	dp[n] = 0;
	for (int c = n; c >= 0; c--) {
		if (dp[c] == inf) continue;
		if(c-1>=0)
			dp[c - 1] = min(dp[c - 1], dp[c] + 1);
		int t;
		t = 6;
		while (c-t>=0) {
			dp[c - t] = min(dp[c - t], dp[c] + 1);
			t *= 6;
		}
		t = 9;
		while (c - t >= 0) {
			dp[c - t] = min(dp[c - t], dp[c] + 1);
			t *= 9;
		}
	}
	cout << dp[0] << endl;
	return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <iostream>

using namespace std;

char e[102][102];
bool vis1[102],vis2[102];
int n,m;

int main() {
	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>e[i][j];
			if(e[i][j]=='#') vis1[i]=1,vis2[j]=1;
		}
	}
	
	int ok=0;
	for(int i=1;i<=n;i++) {
		ok=0;
		for(int j=1;j<=m;j++) {
			if(vis1[i]&&vis2[j]) printf("%c",e[i][j]),ok=1;
		}if(ok) printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 256
D, N = list(map(int,input().split()))

n = []
for i in range(1,1001):
    if D == 0:
        if i % 100 !=0:
            n.append(i)
        continue
    elif D == 1:
        if i % 100 !=0:
            n.append(100*i)
        continue      
    elif D == 2:
        if i % 100 !=0:
            n.append(10000*i)
        continue
print(n[N-1])


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

template<typename T>
class SegTree {
    int n;
    T def;
    function<T(T, T)> operation;
    vector<T> data;

    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return data[k];
        T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2);
        T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r);
        return operation(c1, c2);
    }

public:
    SegTree<T>(int _n, T _def, function<T(T, T)> _operation)
    : def(_def), operation(_operation) {
        n = 1;
        while (n < _n) n *= 2;
        data = vector<T>(2 * n - 1, def);
    }

    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    void change(int i, T x) {
        i += n - 1;
        data[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    T operator[](int i) { return data[i + n - 1]; }
};

void solve() {
  int n;
  cin >> n;
  vector<int> h(n);
  rep(i, n) cin >> h[i];
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<int> zip = h;
  sort(all(zip));
  SegTree<ll> dp(n, 0, [](ll a, ll b) { return max(a, b); }); // debuged, int to ll
  rep(i, n) {
    int it = lb(zip, h[i]);
    ll ma = dp.query(0, it);
    // cout << it << " " << ma << endl;
    dp.change(it, ma + a[i]);
    // rep(j, n) cout << dp[j] << " "; cout << endl;
  }
  ll ans = 0;
  rep(i, n) chmax(ans, dp[i]);
  cout << ans << endl;
}


Measured memory_bytes: 6784
//
//  main.cpp
//  maximum_heap
//
//  Created by ???????????? on 2017/10/16.
//  Copyright ?? 2017 ????????????. All rights reserved.
//

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int A[500010];

void max_heepify(int A[], int ind){
    int left = ind*2;
    int right = ind*2+1;
    int largest;
    if (left <= n && A[left] > A[ind] ){
        largest = left;
    }
    else{
        largest = ind;
    }
    if(right <= n && A[right] > A[largest]){
        largest = right;
    }
    
    if(largest != ind){
        int temp = A[ind];
        A[ind] = A[largest];
        A[largest] = temp;
        
        max_heepify(A, largest);
    }
    
}

void build_maxheep(int A[]){
    for(int i = n/2; i> 0; i--){
        max_heepify(A, i);
    }
}

int main(int argc, const char * argv[]) {
    scanf("%d", &n);
//    int A[n];
    for(int i = 1; i <= n; i++ ){
        scanf("%d", &A[i]);
    }
    build_maxheep(A);
    
    for(int i = 1; i<=n; i++){
        cout<<" ";
        cout<<A[i];
    }
    cout <<endl;
//    std::cout << "Hello, World!\n";
    return 0;
}

Measured memory_bytes: 5184
#include <iostream>
#include <string>

using namespace std;

int main(void){
    int n, cout = -1, flag = 1;
    int a[200];
    
    cin >> n;
    
    for(int i = 0 ; i < n; i++)
        cin >> a[i];

    while(flag)
    {
        cout++;
        for(int i = 0 ; i < n; i++)
        {
            if(a[i]%2==0)
                a[i]/=2;
            else
            {
                flag = 0;
                break;
            }
        }
    }
    
    std::cout << cout<< std::endl;
}

Measured memory_bytes: 256