akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main () {
  int n, a;
  cin >> n >> a;
  char dp[n][a];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < a; j++) {
      cin >> dp[i][j];  
    }  
  }
    
  // まずは横からみる
  int yoko[n];
  for (int i = 0; i < n; i++) {
    yoko[i] = 0;  
  }
  int tate[a];
  for (int i = 0; i < a; i++) {
    tate[i] = 0;  
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < a; j++) {
      if (dp[i][j] == '#') {
        yoko[i] = 1;
        tate[j] = 1;
      }
    }  
  }
  int tt = 0;
  for (int i = 0; i < n; i++) {
    tt = 0;
    for (int j = 0; j < a; j++) {
      if (yoko[i] == 0 || tate[j] == 0) {  
      }  
      else {
        tt = 1;
        cout << dp[i][j];  
      }
      if (j == (a - 1) && tt == 1) {
        cout << endl;    
      }
    }  
  }
}

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            int[,] dp = new int[n + 1, n + 1];
            int[] p = new int[n + 1];

            string[] input = Console.ReadLine().Split(' ');
            p[0] = int.Parse(input[0]);
            p[1] = int.Parse(input[1]);

            for (int i = 2; i <= n; i++)
            {
                input = Console.ReadLine().Split(' ');
                p[i] = int.Parse(input[1]);
            }

            for(int l = 2; l <= n; l++)
            {
                for(int i = 1; i <= n - l + 1; i++)
                {
                    int j = i + l - 1;
                    dp[i, j] = int.MaxValue;

                    for(int k = i; k <= j - 1; k++)
                    {
                        dp[i, j] = Math.Min(
                            dp[i, j],
                            dp[i, k] + dp[k + 1, j] + p[i - 1] * p[k] * p[j]);
                    }
                }
            }
            Console.WriteLine(dp[1, n]);
        }
    }
}

Measured memory_bytes: 9208
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define FOR(i, m, n) for(int i = (int)m; i < (int)n; i++)
#define REP(i, n) FOR(i, 0, n)
using ll = long long;
ll mod = 1000000007;
using namespace std;

int main() {
    int x;
    cin >> x;
    int ans = 0;
    FOR(i, 1, 10000) {
        if(i * 100 <= x && x <= i * 100 + i * 5) ans = 1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
void t(string a);

int main() {
  
  bool istrue = false;
  int c,f;
  cin >> c >> f;
  cerr << c << f << endl;
  //if(f%2 == 1 || f > c*4 ) istrue = false;//奇数・足が多すぎるなら終了
  
  for(int i = 0;i<=c;i++){//動物の数だけ試行
    cerr << i << c << f <<  endl;
    //亀
    if(  ( i * 4 + ( c - i ) * 2 )  == f   ){
      cerr << "s" << endl;
      istrue = true;
      break;
    } 
  }

  
  
    if(istrue == true) cout << "Yes" << endl;
  if(istrue == false) cout << "No" << endl;
  
}



Measured memory_bytes: 3544
fun main(args: Array<String>) {
    readLine()!!.toInt()
    val ans = readLine()!!.split(" ")
            .map { it.toInt() }
            .groupBy { it }
            .map { if (it.key > it.value.count()) it.value.count() else it.value.count() - it.key }
            .sum()
    println(ans)
}


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

#define all(v) (v).begin(), (v).end()
using namespace std;

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

    vector <int> A(no_of_elements);
    vector <int> sorted_A(no_of_elements);
    for(int i = 0; i < no_of_elements; i++)
    {
        scanf("%d", &A[i]);
        A[i] -= (i + 1);

        sorted_A[i] = A[i];
    }

    sort(all(sorted_A));

    int median_index = no_of_elements/2 + no_of_elements%2 - 1;
    int median = sorted_A[median_index];

    long long answer = 0;
    for(int i = 0; i < no_of_elements; i++)
        answer += abs(A[i] - median);

    printf("%lld\n", answer);

    return 0;
}


Measured memory_bytes: 1792
N,P = map(int,input().split())
A = [int(i)%2 for i in input().split()]

odd = sum(A)
even = N - odd
import math

def Comb(a,b):#aCbを返す
    if a>= b:
        return int(math.factorial(a)/(math.factorial(b)*math.factorial(a-b)))
    else:
        return 0
if P == 0:
    ans = 2**N
    for i in range(1,odd+1,2):
        ans -= Comb(odd,i)*(2**even)
    print(ans)
else:
    ans = 0
    for i in range(1,odd+1,2):
        ans += Comb(odd,i)*(2**even)
    print(ans)



Measured memory_bytes: 3064
#include <stdio.h>

#define N 100000

int main() {
	static char t[N + 1];
	int n, k, r, s, p, x, i, j, ans;

	scanf("%d%d%d%d%d%s", &n, &k, &r, &s, &p, t);
	ans = 0;
	for (x = 0; x < k; x++)
		for (i = x; i < n; ) {
			j = i + k;
			while (j < n && t[j] == t[i])
				j += k;
			ans += ((j - i) / k + 1) / 2 * (t[i] == 's' ? r : t[i] == 'p' ? s : p);
			i = j;
		}
	printf("%d\n", ans);
	return 0;
}


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

int main() {
    string s; cin >> s;
    //アルファベットの全探索
    for (char c = 'a'; c <= 'z'; c++) {
        bool ans = false;
        //例えば文字列'a'が文字列sに入っているか確認
        for (int i = 0; i < s.length(); i++) {
            if (c == s[i]) {
                ans = true;
            }
        }
        if (!ans) {
            cout << c << endl;
            return 0;
        }
    }

    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

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

  //x(x-1)/2 = Nとなるxが存在しなければ構築できない。
  int x = 2; //集合の数
  while(x * (x - 1) / 2 < N) x++;

  if(x * (x - 1) / 2 == N){
    cout << "Yes\n" << x << endl;
    //集合の要素数sz;
    int sz = 2 * N / x;
    int ans[x][sz];
    int ed = sz + 1; //端の数
    for(int i = 0; i < sz; i++){
      ans[0][i] = i + 1;
    }

    for(int i = 1; i < x; i++){
      for(int j = 0; j < sz; j++){
        if(j < i){
          ans[i][j] = ans[j][i - 1];
        } else {
          ans[i][j] = ed;
          ed++;
        }
      }
    }

    for(int i = 0; i < x; i++){
      cout << sz << " ";
      for(int j = 0; j < sz; j++){
        cout << ans[i][j] << " ";
      }
      cout << endl;
    }
  }

  else{
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,k,a[N];
ll dp[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dp[2]=abs(a[1]-a[2]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=0x3f3f3f3f;
        for(int j=1;j<=k&&i-j>=1;j++)
            dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
    }
    printf("%d\n",dp[n]);
}


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

ll absll(ll a){
  if(a<0){
    return a * -1;
  }
  return a;
}

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n,0);
  ll count = 0;
  ll sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if(a[i]<0){
      count++;
      sum += a[i] * -1;
      a[i] *= -1;
    }else{
      sum += a[i];
    }
  }
  sort(a.begin(), a.end());
  if(count%2==0){
    cout << sum << endl;
  }else{
    cout << sum + a[0]*-2 << endl;
  }
  return 0;
}


Measured memory_bytes: 4032
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define int long long
using namespace std;

typedef pair<int, int> Pii;

void readline(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str());
}
void readline(int N, vector<double> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atof(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atof(s.c_str());
}
void readindex(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str()) - 1;
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str()) - 1;
}

/* Unoin-Find tree */

#define MAX_N 100000
int unionfind_par[MAX_N];
int unionfind_rank[MAX_N];

void unionfind_init(int n){
    REP(i, n){
        unionfind_par[i] = i;
        unionfind_rank[i] = 0;
    }
}

int unionfind_find(int x){
    if(unionfind_par[x] == x){
        return x;
    }else{
        return unionfind_par[x] = unionfind_find(unionfind_par[x]);
    }
}

void unionfind_unite(int x, int y){
    x = unionfind_find(x);
    y = unionfind_find(y);
    if(x == y) return;

    if(unionfind_rank[x] < unionfind_rank[y]){
        unionfind_par[x] = y;
    }else{
        unionfind_par[y] = x;
        if(unionfind_rank[x] == unionfind_rank[y]) unionfind_rank[x]++;
    }
}

bool unionfind_same(int x, int y){
    return unionfind_find(x) == unionfind_find(y);
}

/* end */

signed main(){

    int N, M;
    cin >> N >> M;
    vector<int> p(N);
    readindex(N, p);

    unionfind_init(N);

    int x, y;
    REP(i, M){
        cin >> x >> y;
        unionfind_unite(x - 1, y - 1);
    }

    int ans = 0;

    REP(i, N){
        if(unionfind_same(i, p[i])) ans++;
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef int Int;
typedef pair<Int,Int> pii;
typedef pair<Int,double> pid;
typedef pair<double,double> pdd;
typedef pair<Int,pii> pip;
typedef pair<double,Int> pdp;
#define A first
#define B second
#define pb(x) push_back(x)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (x).size()
#define CLR(x) memset(x,0,sizeof x)
#define pdebug() printf("%d\n",__LINE__)
#define Itype(a) typeof(a.begin()) 
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define FORO(i,n) REP(i,0,(int)n-1)
#define FORI(i,n) REP(i,1,(int)n)
#define FORIT(i,t) for(Itype(t) i = t.begin();i != t.end();i++)
#define eps 1e-6
#define sqr(x) ((x)*(x))
#define dist(_a,_b) sqrt(sqr(_a.A-_b.A)+sqr(_a.B-_b.B))
#define norm(_a) sqrt(sqr(_a.A)+sqr(_a.B))
template<typename T>void getMin(T &a,T b) { if(a > b) a = b; }
template<typename T>void getMax(T &a,T b) { if(a < b) a = b; }
const int inf = 1000000007;

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

    int N;
    string S;
    cin >> N >> S;
    int dp[N][2];

    for(int i = 0;i < N;i++) {
        if(i > 0) {
            dp[i][0] = dp[i - 1][0] + (S[i] == '#');
            dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + (S[i] == '.');
        } else {
            dp[i][0] = S[i] == '#';
            dp[i][1] = S[i] == '.';
        }
    }

    cout << min(dp[N - 1][0], dp[N - 1][1]) << endl;
    return 0;
}

Measured memory_bytes: 2196
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    A, B, C = [int(x) for x in input().strip().split()]
    K = int(input())
    while B <= A:
        B *= 2
        K -= 1
    if K < 0:
        print('No')
        return True
    while C <= B:
        C *= 2
        K -= 1
    if K < 0:
        print('No')
        return True
    print('Yes')


if __name__ == '__main__':
    main()

Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n = 1e6;
int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  ll mi = 1e10;
  ll index = 0;
  for(int i=0 ; i<n ; i++){
    cin >> a[i];
  }
  ll res = 0; ll right = 0;
  while(true){
    if(res==0){
      right += k;
    }else{
      right += k-1;
    }
    res++;
    if(right >= n) break;
  }
  cout << res << endl;
  return 0;
}


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

int main(){
    int N;
    string X;
    cin>>N;
    vector<string> S(N);
    vector<int> T(N);
    for(int i=0;i<N;i++)cin>>S.at(i)>>T.at(i);
    cin>>X;
    int cnt;
    for(int i=0;i<N;i++){
        if(S.at(i)==X){
            cnt=i;
            break;
        }
    }
    int sum=0;
    for(int i=cnt+1;i<N;i++){
        sum+=T.at(i);
    }
    cout<<sum<<endl;


}




Measured memory_bytes: 256
# https://qiita.com/mochizukikotaro/items/c335e6dcc5020ead0b92
class PriorityQueue
  attr_reader :data

  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))

      a = left_child_idx(target_idx)
      b = right_child_idx(target_idx)

      if @data[b].nil?
        c = a
      else
        c = @data[a] >= @data[b] ? a : b
      end

      if @data[target_idx] < @data[c]
        swap(target_idx, c)
        target_idx = c
      else
        return
      end
    end
  end

  # @param Integer
  # @return Integer
  def left_child_idx(idx)
    (idx * 2) + 1
  end

  # @param Integer
  # @return Integer
  def right_child_idx(idx)
    (idx * 2) + 2
  end

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

_, m = gets.split.map(&:to_i)
pq = PriorityQueue.new(gets.split.map(&:to_i))
while m > 0
  x = pq.pop / 2
  pq.push x
  m -= 1
end
p pq.data.inject(:+)


Measured memory_bytes: 11916
#include<stdio.h>
#include<math.h>

int kiriage( double x )
{
    return (int)( x < 0.0 ? x : x+0.9 );
}

int main(){
  int i,j,k;
  int N,K;
  long double tmp,tmpp;
  long double ans=0.0;
  scanf("%d %d",&N,&K);
  for(i=1;i<=N;i++){
    tmp=(long double)i;
    tmpp=1/(long double)N;
    while(tmp < K){
      tmp*=2.0;
      tmpp*=0.50;
    }
    ans += tmpp;
  }
  
  printf("%.20Lf\n",ans);
  return 0;
}

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

using namespace std;

bool isPalindrome(int n)
{
    int n2 = n, n3 = 0;
    while(n)
    {
        n3 += n % 10;
        n3 *= 10;
        n /= 10;
    }
    n3 /= 10;
    return n2 == n3;
}

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

    int a, b;
    cin >> a >> b;
    int ans = 0;
    for(int i = a; i <= b; i++)
    {
        if(isPalindrome(i))
            ans++;
    }
    cout << ans;

    return 0;
}


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

int main() {
  int a;
  cin >> a;
  ll b, n;
  cin >> b >> n;
  ll x = min(n, b-1);
  ll ans = a*x / b;
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
 	int k;
  cin>>k;
  cout<<a[k-1];
}

Measured memory_bytes: 256
// 13/09/2020  @ 17:32:08
// *****************************************************************
// *****************************************************************
#include <bits/stdc++.h>
// *****************************************************************
// *****************************************************************
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(chrono::high_resolution_clock::now().time_since_epoch().count());
#define fr(i,n) for(llu i=0;i<n;i++)
#define fl(j,a,b) for(llu j=a;j<=b;j++)
#define Pi 3.1415926535897932384626
#define mod 1e9+7
#define MID(a,b) ((a + b) >> 1)
#define MAX(a,b) ((a) > (b) ? (a): (b))
#define MIN(a,b) ((a) < (b) ? (a) :(b))
#define pb push_back
#define mp make_pair
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define printer(a, n) fr(i,n) cout << a[i] << " ";
// *****************************************************************
// *****************************************************************
typedef long long unsigned int llu;
typedef long long int ll;
// *****************************************************************
// *****************************************************************
using namespace std;
// *****************************************************************
// *****************************************************************

                   // Dream it. Wish it. Do it.

                         // tannatsri //

              // Without tact you can learn nothing.

// *****************************************************************
// *****************************************************************
bool rev(ll a, ll b) {
    return a > b;
}
// *****************************************************************
void solution() {
    ll a,b, c, d;
    ll p1, p2;
    cin >> a >> b >> c >> d;
    p1 = a * c;
    p2 = a * d;
    ll p3 = b * c;
    ll p4 = b * d;
    ll ans = MAX(MAX(MAX(p3, p4), p2), p1);
    if(ans < 0) {
        if((0 >= a and 0 <= b) or (0 >= c and 0 <= d)) ans = 0;
    }
    cout << ans;

}
// *****************************************************************
int main() {
    IOS;
    #ifndef ONLINE_JUDGE
        freopen("C:/Users/Mr.Tanishq/Desktop/noc/input.txt", "r", stdin);
        freopen("C:/Users/Mr.Tanishq/Desktop/noc/output.txt", "w", stdout);
        freopen("C:/Users/Mr.Tanishq/Desktop/noc/error.txt", "w", stderr);
    #endif
    // *****************************************************************
    // *****************************************************************
    int t = 1;
    // cin >> t;
    while(t--) {

       solution();
       cout << "\n";
    }
    return 0;
}

Measured memory_bytes: 3660
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n, q; rd(n, q);
  int s=0;
  while(q--){
    int t, k; rd(t, k);
    if(t){
      (s+=k)%=n;
    }else{
      writeln(((k-1)+s)%n+1);
    }
  }
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}



Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, D; cin >> N >> D;
  
  if(N % (2*D + 1) == 0) cout << N / (2*D + 1) << endl;
  else cout << N / (2*D + 1) + 1 << endl;
}

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

int H, W;
vector<P> G[401][401];
string s[401];

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

vector<P> onaji;
map<int, bool> mp;





ll dfs(pair<int, int> p, bool next, bitset<401*401>& ok) {
    ok[p.first*W+p.second] = 1;
    ll ret = 0;
    for (auto v : G[p.first][p.second]) {
        // 白の時
        if (!next and !ok[v.first*W+v.second]) {
            ok[v.first*W+v.second] = 1;
            ret += dfs(v, !next, ok) + 1;
        }
        else if (!ok[v.first*W+v.second]){
            ok[v.first*W+v.second] = 1;
            ret += dfs(v, !next, ok);

            mp[v.first*W+v.second] = true;
            onaji.push_back(v);
        }
    }
    return ret;
}

int main() {
    cin >> H >> W;
    rep(i, H) cin >> s[i];

    vector<P> pos;
    rep(i, H) rep(j, W) {
        if (s[i][j] == '#') {
            pos.emplace_back(i, j);
            rep(d, 4) {
                int nr = i + dy[d];
                int nc = j + dx[d];
                if (0 <= nr and nr < H and 0 <= nc and nc < W and s[nr][nc] == '.') {
                    G[i][j].emplace_back(nr, nc);
                    G[nr][nc].emplace_back(i, j);
                }
            }
        }
    }

    ll ans = 0;
    bitset<401*401> ok;
    int onaji_idx = 0;
    map<int, bool> batu;
    for (auto p : pos) {
        if (mp[p.first*W+p.second]) continue;
        int tmp = dfs(p, false, ok);
        if (onaji_idx < onaji.size()) {
            ans += (onaji.size() - onaji_idx) * tmp;
            onaji_idx = onaji.size();
        }
        ans += tmp;
        ok.reset();
    }

    cout << ans << endl;
}


Measured memory_bytes: 25588
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
 
#define MOD 1000000007
void init();
void solve();

signed main()
{
	init();
	solve();
}

bool dp[5010][10010];
vector<int> A;
int N, K;

void init()
{
	cin >> N >> K;
	rep(i, N) {
		int t;
		cin >> t;
		if (t < K) A.PB(t);
	}
	N = A.size();
	sort(all(A));
}

bool isok(int pos)
{
	bool dp[2][5010];
	rep(i, 2) rep(j, 5010) dp[i][j] = false;
	dp[0][0] = true;
	int now = 1;
	rep(i, N) {
		if (i == pos) continue;
		int pre = 1 - now;
		rep(j, K) {
			if (dp[pre][j]) {
				dp[now][j] = true;
				if (j + A[i] < K) {
					dp[now][j+A[i]] = true;
					if (j + A[i] >= K - A[pos]) return true;
				}
			}
		}
		now = pre;
	}
	return false;
}

void solve()
{
	if (isok(0)) {
		cout << 0 << endl;
		return;
	}
	if (!isok(N-1)) {
		cout << N << endl;
		return;
	}
	int ok = N-1;
	int ng = 0;
	while (ok - ng > 1) {
		int mid = (ok + ng) / 2;
		if (isok(mid)) ok = mid;
		else ng = mid;
	}
	cout << ok << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL
#define Yes 7
#define No -7

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

Node root;

void insert(int);
void inorder(Node);
void preorder(Node);
int find(int);
//Node Mini(Node);

int main(){

  int i = 0;
  int n = 0, key = 0, fans = 0;
  char com[7];
  Node u;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%s",com);
    
    if(com[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }
    else if(com[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(com[0] == 'f'){
      scanf("%d",&key);
      fans = find(key);
      if(fans == Yes)printf("yes\n");
      else if(fans == No)printf("no\n");
    }
  }
  
  return 0;
}

void insert(int key){

  Node y = NIL; /* x's parent  */
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = key;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;    /* settei parent */
    if(z->key < x->key){
      x = x->left;   /* move to left child */
    }
    else{
      x = x->right;  /* move to right child */
    }
  }

  z->parent = y;

  if(y == NIL){ /* if T is empty  */
    root = z;
  }
  else if(z->key < y->key){
    y->left = z; /* y'left is z */
  }
  else {
    y->right = z; /* y'right is z */
  }
  
}

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}

void preorder(Node u){
  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}

int find(int key){
  Node x = root;

  while(x != NIL){
    if(key == x->key)return Yes;
    if(x->key < key)x = x->right;
    else x = x->left;
  }
  return No;
}



Measured memory_bytes: 20524
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 100005
int a[M],cnt[M],Com1[M],Com2[M];
const int P=1e9+7;
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=1ll*res*a%P;
		a=1ll*a*a%P;
		b>>=1;
	}
	return res;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	int x,l=0,r=0;
	for(int i=1;i<=n;i++)if(cnt[i]==2)x=i;
	for(int i=1;i<=n+1;i++){
		if(a[i]==x&&l)r=i;
		else if(a[i]==x)l=i;
	}
	Com1[0]=1;Com2[0]=1;
	for(int i=1;i<=n+1;i++){
		Com1[i]=1ll*Com1[i-1]*(n-i+2)%P*ksm(i,P-2)%P;
	}
	for(int i=1;i<=n-r+l;i++)Com2[i]=1ll*Com2[i-1]*(n-i+1-r+l)%P*ksm(i,P-2)%P;
	for(int i=1;i<=n+1;i++){
		if(i==1)printf("%d\n",n);
		else if(i==n+1)puts("1");
		else {
			printf("%d\n",(1ll*Com1[i]-Com2[i-1]+P)%P);
		}
	}
	return 0;
}

Measured memory_bytes: 2816
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();

        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
        	arr[i] = sc.nextInt();
        }

        int[] leftCnt = new int[n];
        int[] rightCnt = new int[n];
        int[] totalCnt = new int[n];
        for(int i = 0; i < n; i++) {
        	int cnt = 0;
        	for(int j = 0; j < i; j++) {
        		if(arr[j] < arr[i])
        			cnt++;
        	}
        	leftCnt[i] = cnt;
        	cnt = 0;
        	for(int j = i + 1; j < n; j++) {
        		if(arr[j] < arr[i])
        			cnt++;
        	}
        	rightCnt[i] = cnt;
        	totalCnt[i] = leftCnt[i] + rightCnt[i];
        }
        
        int MOD = 1000000007;
        
        long kk = k * (k - 1) / 2 % MOD; 
        
        long asn = 0;
        for(int i = 0; i < n; i++) {
        	asn += ((totalCnt[i] * kk % MOD) + (k * rightCnt[i]) % MOD) % MOD;
        }
        System.out.println(asn % MOD);
    }
}


Measured memory_bytes: 28400
// Problem : D - Preparing Boxes
// Contest : AtCoder - AtCoder Beginner Contest 134
// URL : https://atcoder.jp/contests/abc134/tasks/abc134_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

/* DEBUGGING */
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif

/* MACROS */ 
typedef long long int ll;
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

typedef map<int,int> mii;

#define  ff          first
#define  ss          second
#define  pb          push_back
#define  IOS         ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  lb          lower_bound
#define  ub          upper_bound
#define  all(x)      (x).begin(), (x).end()
#define  lcm(x, y)   ((x) * (y) / __gcd(x, y))
#define  ps(x,y)     fixed<<setprecision(y)<<x
#define  setbit(x)   __builtin_popcountll(x)
#define  rep(i,a,b)  for(int i=a ; i<b ; ++i)
#define  repr(i,a,b) for(int i=a ; i>=b ; --i)

/* CONSTANTS */ 
#define PI 3.141592653589793
const ll MOD = 1e9 + 7;
const ll INF = 1000000000;
const ll MAX_N = 2e5 + 2;

// #define cerr if(false)cerr
/* CODE STARTS HERE */

void solve(){
    int n,sum; cin >> n;
    vi v(n+1),ball(n+1,0);
    rep(i,1,n+1) cin >> v[i];
    
    for(int i=n;i>=1;--i){
        sum = 0;
        
        for(int j=2*i;j<=n;j+=i){
            sum += ball[j];
        }
        
        if((sum%2) != v[i]){
            ball[i] = 1;
        }
    }
    
    cout << accumulate(all(ball),0) << "\n";
    rep(i,1,n+1) if(ball[i]) cout << i << " ";
    
}

int main(){
    IOS;
    solve();
}

Measured memory_bytes: 4708
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int sum=0;
  string str;
  cin >> str;
  
  for (int i = 0; i < 4; i++) {
    for (int j = 1; j+i < 4;j++) {
      if(str.at(i) == str.at(i+j)) {
        sum += 1;
      }
    }
  }
  if (sum == 2) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}

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

int main(){
    string s;cin>>s;
    if (s.size() == 1){
        cout << 0 << endl;
        return 0;
    }
    vector<int> w_indices;
    for (int i=0;i<s.size();i++){
        if (s[i] == 'W'){
            w_indices.push_back(i);
        }
    }
    long long acc = 0;
    for (int i=0;i<w_indices.size();i++){
        acc += w_indices[i] - i;
    }
    cout << acc << endl;
    return 0;
}

Measured memory_bytes: 1532
#include<stdio.h>
typedef struct{
  int parent;
  int left;
  int right;
} Tree;
Tree tree[10000];
//int s=0,t=0;
#define NIL -1
int getheight(int);
int main()
{
  int i,id,j,n,k,depth=0,num,l,r,degree=0,height=0;
 
  scanf("%d",&n);

  for(i=0;i<n;i++){
    if(i>0)break;
  }
 
  for(i=0;i<n;i++){
    tree[i].parent=NIL;
  }
 
  for(i=0;i<n;i++){
    scanf("%d%d%d",&id,&l,&r);
    tree[id].left=l;
    tree[id].right=r;
    if(l!=NIL && r!=NIL){
      tree[l].parent=id;
      tree[r].parent=id;
    }
    else if(l!=NIL && r==NIL){
      tree[l].parent=id;
    }
    else if(l==NIL && r!=NIL){
      tree[r].parent=id;
    }
  }

  for(i=0;i<n;i++){
    printf("node %d: parent = %d, ",i,tree[i].parent);
    if(tree[i].parent==NIL){
      printf("sibling = -1, ");
    }
    else if(tree[tree[i].parent].left==i){
      printf("sibling = %d, ",tree[tree[i].parent].right);
    }
    else{
      printf("sibling = %d, ",tree[tree[i].parent].left);
    }
    printf("degree = ");
    if(tree[i].left!=NIL && tree[i].right!=NIL){
      printf("2, ");
    }
    else if(tree[i].left==NIL && tree[i].right==NIL){
      printf("0, ");
    }
    else printf("1, ");
 
    num=i;
    while(tree[num].parent!=NIL){
      depth++;
      num=tree[num].parent;
    }
    printf("depth = %d, ",depth);
    depth=0;
 
    printf("height = ");
    height=getheight(i);
    printf("%d,",height);
    //s=0;t=0;
     
    if(tree[i].parent==NIL){
      printf(" root\n");
    }
    else if(tree[i].left==NIL && tree[i].right==NIL){
      printf(" leaf\n");
    }
    else {
      printf(" internal node\n");
      }
  }
  return 0;
}

int getheight(int i)
{
  int s=0,t=0;
  if(tree[i].left==NIL && tree[i].right==NIL)return 0;

  if(tree[i].left!=NIL){
  s=getheight(tree[i].left)+1;
  }
  if(tree[i].right!=NIL){
  t=getheight(tree[i].right)+1;
  }
  if(s>t){
    
    return s;
  }
  else{
    return t;
  }
}



Measured memory_bytes: 2128
class Dice

  def initialize
    @top = 1
    @near = 2
    @right = 3
  end

  def north
    @top, @near = @near, 7-@top
  end

  def east
    @top, @right = 7-@right, @top
  end

  def west
    @top, @right = @right, 7-@top
  end

  def south
    @top, @near = 7-@near, @top
  end

  def right
    @near, @right = @right, 7-@near
  end

  def left
    @near, @right = 7-@right, @near
  end

  attr_reader :top
end

loop do
  count = STDIN.readline.to_i
  break if count == 0

  dice = Dice.new
  ans = dice.top

  count.times do
    command = STDIN.readline
    dice.send(command.chomp.downcase)
    ans += dice.top
  end

  puts ans
end

Measured memory_bytes: 6092
import math

A, B = [int(item) for item in input().split()]

def gdc(A, B):
    if B == 0:
        return A
    else:
        return gdc(B, A % B)

def chk_pn(num):
    flag = True
    if num  <= 3:
        pass
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = False
                break
    return flag

def mk_factor(num):
    max_divisor = int(math.sqrt(num))+1
    divisor = 2
    factor_list = [1]

    while divisor <= max_divisor:
        if num % divisor == 0:
            factor_list.append(divisor)
            num /= divisor
        else:
            divisor += 1
    if num != 1.0:
        factor_list.append(num)
    return factor_list

GDC = gdc(A, B)
#pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]

print(len(set(mk_factor(GDC))))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define int long long
#define rep(i, n) for (signed i = 0; i < signed(n); i++)
#define REP(i, s, n) for (signed i = signed(s); i < signed(n); i++)
using namespace __gnu_pbds;
using namespace std;

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

signed main() {
    using key = pair<int, int>;
    tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update> tr;
	int N, K; cin >> N >> K;
	V v(N); input(v);
	V s(N + 1);
    int ans = 0;
    tr.insert(make_pair(0, -1ll));
	rep(i, N) {
		s[i + 1] = s[i] + v[i] - K;
        int num = tr.order_of_key(make_pair(s[i + 1], N));
        num = max(0ll, num);
        ans += num;
        tr.insert(make_pair(s[i + 1], (int)i));
	}
    cout << ans << endl;
}

Measured memory_bytes: 15872
N,K=map(int,input().split())
V=list(map(int,input().split()))
import heapq
turn=min(N,K)
m=0
for A in range(turn+1):
  for B in range(turn+1-A):
    h=[]
    heapq.heapify(h)
    if A>0:
      h=V[:A]+h
    if B>0:
      h=h+V[len(V)-B:]
    heapq.heapify(h)  

    ans=sum(h)
    for i in range(K-A-B):
      if h!=[]:
        f=heapq.heappop(h)
 
        if f<0:
          ans-=f
    m=max(ans,m)


    
print(m)   

Measured memory_bytes: 9124
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(X, N, Ps):
    Ps = set(Ps)
    d = 0
    while True:
        if X - d not in Ps:
            return X - d
        if X + d not in Ps:
            return X + d
        d += 1


if __name__ == "__main__":
    X, N = tuple(map(int, input().split(" ")))
    Ps = []
    if N > 0:
        Ps = list(map(int, input().split(" ")))
    print(solve(X, N, Ps))


Measured memory_bytes: 9476
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int inf=10000;
char c[1000][1000];
int d[1000][1000],n,h,w,ans=0,dx[]={1,0,-1,0},dy[]={0,1,0,-1},i,j,sx,sy,gx,gy;
int func(char s,char g){
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      d[i][j]=inf;
      if(s==c[i][j]){
	sx=i;
	sy=j;
      }
      if(g==c[i][j]){
	gx=i;
	gy=j;
      }
    }
  }
  //cout<<sx<<" "<<sy;
  //cout<<gx<<" "<<gy;
  queue< pair<int,int> > q;
  q.push(pair<int,int> (sx,sy));
  d[sx][sy]=0;
  while(q.size()){
    pair<int,int> p=q.front();
    q.pop();
    if(p.first==gx&&p.second==gy)
      break;
    for(i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
      // cout<<nx<<" "<<ny<<" "<<c[nx][ny]<<" "<<d[nx][ny]<<endl;
      if(nx<h&&nx>=0&&ny<w&&ny>=0&&c[nx][ny]!='X'&&d[nx][ny]==inf){
	
	q.push(pair<int,int>(nx,ny));
	d[nx][ny]=d[p.first][p.second]+1;
      }
    }
  }
  //cout<<d[gx][gy]<<endl;
  return d[gx][gy];
}
int main(){
  char sg[]="S123456789";
  cin>>h>>w>>n;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin>>c[i][j];
    }
  }
  for(int k=0;k<n;k++){
    ans+=func(sg[k],sg[k+1]);
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 8028
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////

int n,m,a,b,c,d[100005] = {};
string s,t;

int main(){

    cin >> n >> a >> b;

    int i = 0;
    while(1){
        if(i%2 == 0){
            if(a < b){
                a++;
            }else{
                a--;
            }
            if(a == b){
                P("Borys");
                ret 0;
            }
        }else{
            if(a < b){
                b--;
            }else{
                b++;
            }
            if(a == b){
                P("Alice");
                ret 0;
            }
        }

       i++; 
    }
	
	return  0;
}

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

#ifdef LOCAL
#include "/home/shahraaz/bin/debug.h"
#else
#define db(...)
#endif

using ll = long long;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

const int NAX = 2e5 + 5, MOD = 1000000007;

const int _n = 1e5 + 10;
vector<int> Fact(_n), Inv(_n);
const int kmod = 1000000007;

int mul(int a, int b, int mod = kmod)
{
    return (long long)a * b % mod;
}

int add(int a, int b, int mod = kmod)
{
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b, int mod = kmod)
{
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int power(int base, int index, int mod = kmod)
{
    if (index == 0)
        return 1;
    int temp = power(base, index / 2, mod);
    temp = mul(temp, temp, mod);
    if (index & 1)
        temp = mul(temp, base, mod);
    return temp;
}

int mod_inv(int x, int mod = kmod)
{
    return power(x, kmod - 2);
}

void pre()
{
    Fact[0] = 1;
    for (int i = 1; i < _n; ++i)
        Fact[i] = mul(Fact[i - 1], i);
    Inv[_n - 1] = mod_inv(Fact[_n - 1]);
    for (int i = _n - 2; i >= 0; --i)
        Inv[i] = mul(Inv[i + 1], (1 + i));
}

int ncr(int n, int r)
{
    if (n < 0 || r < 0 || n - r < 0)
        return 0;
    return mul(Fact[n], mul(Inv[r], Inv[n - r]));
}

class Solution
{
private:
public:
    Solution() {}
    ~Solution() {}
    void solveCase()
    {
        int n, k;
        cin >> n >> k;
        int res = 0;
        vector<int> lkDp(k + 1);
        for (ll i = k; i >= 1; i--)
        {
            int allow = k / i;
            // res = add(res, power(allow, n));
            int curr = power(allow, n);
            for (ll j = 2 * i; j <= k; j += i)
                curr = sub(curr, lkDp[j]);
            lkDp[i] = curr;
            res = add(res, mul(i,curr));
        }
        db(lkDp);
        cout << res << '\n';
    }
};

int32_t main()
{
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int t = 1;
    // cin >> t;
    Solution mySolver;
    for (int i = 1; i <= t; ++i)
    {
        mySolver.solveCase();
#ifdef LOCAL
        cerr << "Case #" << i << ": Time " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " s.\n";
        TimeStart = chrono::steady_clock::now();
#endif
    }
    return 0;
}


Measured memory_bytes: 4524
import itertools
import math
import sys

n = int(input())
h = list(map(int, input().split()))
# start = [0] * n
# ans = 0
# flag = True
# index = 0
# while start != h:
#     start_from_0 = True
#     for i in range(index, n):
#         if start[i] < h[i]:
#             start[i] += 1
#             continue
#         if start[i] == h[i]:
#             if i == n - 1:
#                 index = 0
#                 ans += 1
#                 start_from_0 = False
#                 print(start)
#                 break
#             ans += 1
#             index = i + 1
#             start_from_0 = False
#             print(start)
#             break
#     if start_from_0:
#         print(start)
#         index = 0
#         ans += 1
# print(ans)
deleted_something = False
# encountered_0 = False
ans = 0
while h.count(0) != n:
    deleted_something = False
    for i in range(n):
        if h[i] == 0 and deleted_something:
            break
        if h[i] == 0:
            continue
        h[i] -= 1
        deleted_something = True
    ans += 1
print(ans)





Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007*1ll
using namespace std;
int ar[200002] ;
vector<int>ps,ne,tup ;
bool cmp(int a , int b) {return a>b ; }
int32_t main()
{
    int n,k ; cin>>n>>k ;
    int an=1 ;
    for(int i = 0 ; i < n ; i++) {cin>>ar[i] ; if(ar[i]>=0) an=0 ;}
    if(k==n)
    {
        int ans=1 ;
        for(int i = 0 ; i < n ; i++)
        {
            int x=ar[i] ;
            x=(x+mod)%mod ;
            ans=(ans*x)%mod ;
        }
        cout<<ans<<endl ;
    }
    else
    {
        if(an)
        {
           // cout<<"jkl "<<k<<endl ;
            if(k&1ll) sort(ar,ar+n,cmp) ;
            else sort(ar,ar+n) ;
            int ans=1 ;
            for(int i = 0 ; i < k ; i++)
            {
                int x=ar[i] ;
                x=(x+mod)%mod ;
                ans=(ans*x)%mod ;
            }
            cout<<ans<<endl ;
        }
        else
        {
           // cout<<"oo"<<endl ;
            int ans=1 ;
            for(int i = 0 ; i < n ; i++)
            {
                if(ar[i]>=0) ps.push_back(ar[i]) ;
                else ne.push_back(ar[i]) ;
            }
            sort(ps.begin(),ps.end()) ;
            sort(ne.rbegin(),ne.rend()) ;
          //  for(int i = 0 ; i < ps.size() ; i++) cout<<ps[i]<<" " ; cout<<endl ;
          //  for(int i = 0 ; i < ne.size() ; i++) cout<<ne[i]<<" " ; cout<<endl ;
            if(k&1)
            {
                int x=ps.back() ; ps.pop_back() ;
                ans=(ans*x*1ll) ;
            }
            while((int)ps.size()>1)
            {
                int x=ps.back() ; ps.pop_back() ;
                int y=ps.back() ; ps.pop_back() ;
                tup.push_back((x*y*1ll)) ;
            }
            while((int)ne.size()>1)
            {
                int x=ne.back() ; ne.pop_back() ;
                int y=ne.back() ; ne.pop_back() ;
                tup.push_back((x*y*1ll)) ;
            }
            sort(tup.rbegin(),tup.rend()) ;
            //for(int i = 0 ; i < (int)tup.size() ; i++) cout<<tup[i]<<" " ; cout<<endl ;
            for(int i = 0 ; i < k/2 ; i++)
            {
                ans%=mod ; tup[i]%=mod ;
                ans=(ans*tup[i])%mod ;
            }
            cout<<ans%mod<<endl ;

        }
    }

}
// -1000000000 -1 -1000000000 -1000000000 -1000000000


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

int main() {
	int x; cin >> x;
	if (x == 1) {
		cout << 1 << endl;
		return 0;
	}

	int ans = 0;
	for (int i = 2; i < x; i++) {
		int b = i*i;
		while (b <= x) {
			ans = max(ans, b);
			b *= i;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
def main():
  A,B,C,X,Y = list(map(int, input().split()))

  min_cost = 2 * (10 ** 5) * max(A, B, C)

  for i in range(max(X, Y) + 1):
    num_c = 2 * (max(X, Y) - i)
    num_b = max(0, Y - num_c // 2)
    num_a = max(0, X - num_c // 2)
    total = A * num_a + B * num_b + C * num_c
    min_cost = min(total, min_cost)

  print(min_cost)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main(){
    int n;
    cin >> n;
    if(n>999){
        cout << "ABD";
    }else{
        cout << "ABC";
    }
    return 0;

}

Measured memory_bytes: 256
M=10**9+7
f=input
n,m=map(int,f().split())
s,t=0,1
u=0 if m<1 else int(f())
for i in range(n):
  if i==u-1:
    s,t=t,0
    try: u=int(f())
    except: pass
  else: s,t=t,(s+t)%M
print(t)

Measured memory_bytes: 3060
import java.awt.geom.*;
import java.io.*;
import java.util.*;

public class Main{
	int [] dp;
	int max = 1000;

	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int [] data = new int[5];
			int a = sc.nextInt();
			int b = sc.nextInt();
			if((a|b) == 0) break;
			data[0] = a + b;
			for(int i = 1 ; i < 5; i++){
				data[i] = sc.nextInt() + sc.nextInt();
			}
			
			int max = 0;
			int ind = -1;
			for(int i = 0 ; i < 5; i++){
				if(max < data[i]){
					max = data[i];
					ind = i;
				}
			}
			System.out.println((char) (ind + 'A')  + " " + max);
		}
	}

	private void debug(Object... o) { System.out.println("debug = " + Arrays.deepToString(o)); }

	public static void main(String[] args) {
		new Main().doit();
	}
}

Measured memory_bytes: 21080
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    bool f{true};
    if(n&1){
        int l=1,r=n;
        fr(i,m){
            cout<<l<<" "<<r<<'\n';
            ++l,--r;
        }
    }
    else{
        int l=1,r=n;
        fr(i,m){
            cout<<l<<" "<<r<<'\n';
            ++l,--r;
            if(f&&4*l>n) ++l,f=false;
        }
    }
}

Measured memory_bytes: 3652