akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
using namespace std;
using ll = long long;
using P = pair<int,int>;
struct primes_ {
	vector<int> v;
	primes_(int n): v{2, 3} {
		if (n < 3) {
			if (n == 2) v = vector<int>(1, 2);
			else v.clear();
			return;
		}
		bool f = false;
		int end = 1;
		for(int i = 5; i <= n; i += (f = !f) ? 2 : 4) {
			while(v[end] * v[end] <= i) end++;
			bool isprime = true;
			for(int k = 0; k < end; k++) {
				if (i % v[k] == 0) {
					isprime = false;
					break;
				}
			}
			if (isprime) v.push_back(i);
		}
	}
	auto begin() {return v.begin();}
	auto end() {return v.end();}
} primes(3333);

ll al[] = {0,60838190672,257212470774,596981215450,1084296609104,1722125036282,2512661322551,3457770622390,4558987534475,5817729717828,7235062807366,8812039622862,10549659220862,12448845177256,14510332007222,16734924755096,19123138141378,21675833225770,24393634293809,27276821356759,30326413365285,33542358268005,36925459066686,40476248899052,44194833598353,48081994935671,52138123487538,56363615930452,60758384185743,65323182791149,70058785460280,74964555109988,80041527790312,85290161753688,90709780843282,96301520878991,102065855149715,108002269398516,114111807921375,120394329084663,126850549017804,133479467089246,140282617787827,147259491582477,154411235469265,161737467121483,169238102781982,176913242475822,184764302482181,192790925674795,200992441246692,209370037656611,217923890158764,226653316365413,235560022983960,244642548171917,253902107151677,263338334303632,272951354222680,282742772106696,292711324081941,302856699362737,313180253381239,323682486495499,334361760892115,345219904513529,356256480873339,367470747430202,378864539458650,390437889429971,402188826344049,414118956306590,426229374669116,438519040875971,450987322450746,463635895079489,476465015795706,489473701762655,502662434241804,516031076204871,529581632274134,543311223215741,557220889209512,571311613610574,585584064718129,600036645526326,614670553358276,629486032479553,644482906053419,659661281999214,675021515919670,690561394962114,706285619557381,722190402701363,738276491989247,754546104527913,770997444637057,787630213195247,804447590347769,821446543739323,838627288460105};

int main() {
	int n;
	scanf("%d", &n);
	int s = 0;
	ll ans = 0;
	for(int i = 0; i <= 100; i++) {
		if ((i+1) * 100000 > n) {
			ans = al[i];
			s = i * 100000;
			break;
		}
	}
	//cout << s << ans << endl;
	for(int k = s+1; k <= n; k++) {
		int t = k;
		int f = 1;
		for(auto p: primes) {
			int cnt = 0;
			while(t % p == 0) {
				t /= p;
				cnt += 1;
			}
			f *= cnt + 1;
		}
		if (t > 1) f *= 2;
		ans += (ll)k * f;
		//if (k % 100000 == 0) {
	//		printf("%lld,", ans);
	//	}
	}
	cout << ans << endl;

	
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
const int N=2050;
char g[N][N];
int n,m;
int le[N][N],ri[N][N],up[N][N],dw[N][N];
int main(void){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",g[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='#'){
                le[i][j]=0;
                continue;
            }
            le[i][j]=1;
            if(j>0 && g[i][j-1]=='.'){
                le[i][j]+=le[i][j-1];
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=m-1;j>=0;j--){
            if(g[i][j]=='#'){
                ri[i][j]=0;
                continue;
            }
            ri[i][j]=1;
            if(j<m-1 && g[i][j+1]=='.'){
                ri[i][j]+=ri[i][j+1];
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         printf("%d ",ri[i][j]);    
    //     }
    //     printf("\n");
    // }
    for(int j=0;j<m;j++){
        for(int i=0;i<n;i++){
            if(g[i][j]=='#'){
                up[i][j]=0;
                continue;
            }
            up[i][j]=1;
            if(i>0 && g[i-1][j]=='.'){
                up[i][j]+=up[i-1][j];
            }
        }
    }
    for(int j=0;j<m;j++){
        for(int i=n-1;i>=0;i--){
            if(g[i][j]=='#'){
                dw[i][j]=0;
                continue;
            }
            dw[i][j]=1;
            if(i<n-1 && g[i+1][j]=='.'){
                dw[i][j]+=dw[i+1][j];
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='#'){
                continue;
            }
            //printf("%d %d\n",i,j);
            // if(i==1 && j==1){
            //     printf("%d %d %d %d\n",le[i][j],ri[i][j],up[i][j],dw[i][j]);
            // }
            ans=max(ans,le[i][j]+ri[i][j]+up[i][j]+dw[i][j]-3);
            //printf("%d\n",ans);
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 69888
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>
#include <cassert>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;

inline bool check(ll x, ll y, ll xMax, ll yMax) { return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string tostring(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }
template<class T> inline T mypow(T x, ll n) { T res = 1; while (n > 0) { if (n & 1)res = res * x;	x = x * x;	n >>= 1; }return res; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

#define For(i,a,b)	for(ll (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define rFor(i,a,b)	for(ll (i) = (a-1);i >= (b);(i)--)
#define rrep(i,n)	rFor(i,n,0)
#define each(i,n)	for(auto &i : n)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define sz(a)		(sizeof(a))
#define tostr(a)	tostring(a)
#define dump(val) 	cerr << #val " = " << val << endl;
#define Fill(a,v)	fill((int*)a,(int*)(a+(sz(a)/sz(*(a)))),v)

const ll dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = 1e17 + 9;

#define int ll
#define double ld

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

	string s[3];
	rep(i, 3) {
		cin >> s[i];
		reverse(all(s[i]));
	}

	int t = 0;
	while (1) {
		if (s[t].size() == 0) {
			cout << char('A' + t) << endl;
			return 0;
		}
		int nt = s[t].back() - 'a';
		s[t].pop_back();
		t = nt;
	}

	return 0;
}

Measured memory_bytes: 256
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

n=int(input())
p=primes(100*n)
a=[]
i=0
j=0
while i<n:
    if p[j]%10==1:
        print(p[j], end=" ")
        i +=1
        j +=1
    else:
        j+=1

Measured memory_bytes: 3064
n = int(input())
a = sorted([int(input()) for i in range(n)])
l = n//2

if n % 2 == 0:
    small = a[:l]
    big = a[l:]
    ans = sum(big) * 2 - sum(small) * 2  - big[0] + small[-1]
    print(ans)

else:
    small = a[:l]
    big = a[l+1:]
    ans = sum(big) * 2 - sum(small) * 2 - min(a[l] - small[-1], big[0] - a[l])
    print(ans)

Measured memory_bytes: 8284
using System;

namespace A___Candy_Distribution_Again
{
    class Program
    {
        static void Main (string[] args)
        {
            var input = Console.ReadLine ().Split (' ');
            var n = int.Parse (input[0]);
            var x = int.Parse (input[1]);
            var a = new int[n];
            var b = 0;
            input = Console.ReadLine ().Split (' ');
            for (var i = 0; i < a.Length; i++)
            {
                a[i] = int.Parse (input[i]);
            }
            Array.Sort (a);
            for (var i = 0; i < a.Length; i++)
            {
                b += a[i];
                if (b < x && i == a.Length - 1)
                {
                    Console.WriteLine (i);
                }
                else if (b == x)
                {
                    Console.WriteLine (i + 1);
                    break;
                }
                else if (b > x)
                {
                    Console.WriteLine (i);
                    break;
                }
            }
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
int Getnum(int n)
{
	int i,s=0;
	for(i=0;i<5;i++)
	{
		if((n>>i)&0x01==1)
			s++;	
	}
	return s;
}
int main()
{
	long long sum=0,t,a[(1<<5)+1]={0};
	int i,tmp,check=0,n;
	char sz[100];
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s",sz);
		switch(sz[0])
		{
			case 'M':
				check|=1<<4;
				a[1<<4]++;
				break;
			case 'A':
				check|=1<<3;
				a[1<<3]++;
				break;
			case 'R':
				check|=1<<2;
				a[1<<2]++;
				break;
			case 'C':
				check|=1<<1;
				a[1<<1]++;
				break;
			case 'H':
				check|=1<<0;
				a[1<<0]++;
				break;
		}
	}
	//printf("%d\n",check);
	for(i=0;i<(1<<5);i++)
	{
		if(Getnum(i)!=3||(check&i)!=i)
			continue;
		tmp=i;
		t=1;
		while(tmp)
		{
			t*=a[tmp&-tmp];
			tmp-=tmp&-tmp;
		}
		//printf("%d %d\n",i,t);
		sum+=t;
	}
	printf("%lld",sum);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
void print(ll x){
	if(x<0)putchar('-'),x=-x;
	int y=x%10+'0';
	if(x>=10)print(x/10);
	putchar(y);
}
ll n,k,ans,mod=1e9+7,a[105],dp[105][200005];
int main(){
	n=read(),k=read();
	for(int i=0;i<n;i++)
		a[i]=read();
	dp[n][k]=1;
	for(int i=n-1;i>=0;i--)
		for(int j=k;j>=0;j--)
			dp[i][j]=(dp[i+1][j]+dp[i][j+1]-dp[i+1][j+a[i]+1]+mod)%mod;
    print(dp[0][0]);
	return 0;
}

Measured memory_bytes: 157184
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int N=0,M=0;
		int[][] PY;
		String[] ID;
		Scanner sc = new Scanner(System.in);
        N=sc.nextInt();
        M=sc.nextInt();
        PY=new int[M][3];
        ID = new String[M+1];
        StringBuilder plpd,xlpd;
        int index=0;
        for(int i=0;i<M;i++){
        	index++;
        	PY[i][0]=index;
        	PY[i][1]=sc.nextInt();
        	PY[i][2]=sc.nextInt();
        }
        sort(PY,new int[]{1,2});
        int X=0;
        for(int i=0;i<M;i++){
        	if(i>0 && PY[i][1]!=PY[i-1][1]){
        		X=1;
        	}else{
        		X++;
        	}
        	plpd=new StringBuilder("");
          	xlpd=new StringBuilder("");
          	for(int k=0;k<6-Integer.toString(PY[i][1]).length();k++){
          		plpd.append("0");
          	}
          	for(int k=0;k<6-Integer.toString(X).length();k++){
          		xlpd.append("0");
          	}
        	ID[PY[i][0]] = plpd.toString()+PY[i][1]+xlpd.toString()+X;
        }
        for(int i=1;i<=M;i++){
        	   System.out.println(ID[i].toString());
           }
	}
	 public static void sort(int[][] ob, final int[] order) {    
         Arrays.sort(ob, new Comparator<Object>() {    
             public int compare(Object o1, Object o2) {    
                 int[] one = (int[]) o1;    
                 int[] two = (int[]) o2;    
                 for (int i = 0; i < order.length; i++) {    
                     int k = order[i];    
                     if (one[k] > two[k]) {    
                         return 1;    
                     } else if (one[k] < two[k]) {    
                         return -1;    
                     } else {    
                         continue;
                     }    
                 }    
                 return 0;    
             }    
         });   
     }    
}


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

int main()
{
    std::pair<int,int> s,t;
    std::cin >> s.first >> s.second >> t.first >> t.second;
    std::string ans;
    for(int i = s.first;i < t.first; i++)ans.push_back('R');
    for(int i = s.second;i < t.second; i++)ans.push_back('U');
    for(int i = s.first;i < t.first ; i++)ans.push_back('L');
    for(int i = s.second;i < t.second; i++)ans.push_back('D');
    ans.push_back('D');
    for(int i = s.first;i <= t.first; i++)ans.push_back('R');
    for(int i = s.second;i <= t.second; i++)ans.push_back('U');
    ans.push_back('L');
    ans.push_back('U');
    for(int i = s.first;i <= t.first ; i++)ans.push_back('L');
    for(int i = s.second;i <= t.second; i++)ans.push_back('D');
    ans.push_back('R');

    std::cout << ans << std::endl;

}

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

using namespace std;

int main(){
    string S,T;
    int ts=-1;
    cin >> S >> T;

    for(int i=S.size()-T.size();0<=i;i--){
        for(int j=0;j<T.size();j++){
            if(S[i+j] != T[j] && S[i+j]!='?'){
                break;
            }
            if(j==T.size()-1){
                ts = i;
            }
        }
        if(ts!=-1){
            break;
        }
    }

    if(ts == -1){
        cout << "UNRESTORABLE" << endl;
    }else{
        for(int i=0;i<T.size();i++){
            S[ts+i] = T[i];
        }
        for(int i=0;i<S.size();i++){
            if(S[i]=='?'){
                cout << 'a';
            }else{
                cout << S[i];
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
MOD = 10**9 + 7

def main():
    n = int(input())
    if n == 1:
        print(0)
    else:
        ans = pow(10, n, MOD)
        ans -= 2 * pow(9, n, MOD)
        ans %= MOD
        ans += pow(8, n, MOD)
        print(ans % MOD)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9188
L = 10
movable = [[-1, -2], [0, -2], [1, -2],
           [-1,  2], [0,  2], [1,  2],
           [-2, -1], [-2, 0], [-2, 1],
           [ 2, -1], [ 2, 0], [ 2, 1]]

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  px, py = a
  n = $<.gets.to_i
  result = "NA"
  sprinkler = $<.gets.split.map(&:to_i).each_slice(2).to_a
  try = ->(x, y, i = 0) {
    if i == n
      result = "OK"
    else
      s = sprinkler[i]
      movable.each do |dx, dy|
        nx = x + dx
        ny = y + dy
        check = ->{
          nx.between?(s[0] - 1, s[0] + 1) && ny.between?(s[1] - 1, s[1] + 1)
        }
        next if nx < 0 or nx >= L or ny < 0 or ny >= L
        try.(nx, ny, i + 1) if check.()
      end
    end
  }
  try.(px, py)
  puts result
end


Measured memory_bytes: 7288
#include<iostream>
using namespace std;
int n;
double t[6]={165.0,170.0,175.0,180.0,185.0,9999999.9};
int cnt[6];
double in;
int main(){
  for(int i=0;i<6;i++)cnt[i]=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>in;
    for(int j=0;j<6;j++){
      if(in<t[j]){cnt[j]++;break;}
    }
  }
  for(int i=0;i<6;i++){
    cout<<i+1<<':';
    for(int j=0;j<cnt[i];j++){
      cout<<'*';
    }
    cout<<endl;
  }
  return 0;
}


Measured memory_bytes: 3076
# Aizu Problem 0055: Sequence
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


for line in sys.stdin:
    a = float(line)
    S = a
    for k in range(9):
        if k % 2 == 0:
            a *= 2
        else:
            a /= 3
        S += a
    print("%.8f" % S)

Measured memory_bytes: 7552
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <deque>
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
const ll inf = 1e18;

void solve()
{
    int n;
    ll a, ans=1;
    bool fl=false;
    cin >> n;
    while(n--)
    {
        cin >> a;
        if(a==0)
        {
            while(n--)
                cin >> a;
            cout << 0 << '\n';
            return;
        }
        if(ans<=inf/a)
            ans *= a;
        else
        {
            fl=true;
            ans=0;
        }
    }
    if(fl)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Measured memory_bytes: 3648
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
cnt = 0
for i in range(n + 1):
    if i % 3 != 0 and i % 5 != 0:
        cnt += i
print(cnt)


Measured memory_bytes: 9176
using System;

class Program
    {
		static void Main(string[] args)
        {
            Console.ReadLine();
            string S = Console.ReadLine();

            string ans = "No";
            if ((S.Length & 1) == 0)
            {
               if ( S.Substring(0, S.Length / 2) == 
                S.Substring(S.Length / 2))
                {
                    ans = "Yes";
                }
            }

            Console.WriteLine(ans);
        }
    }

Measured memory_bytes: 13140
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
#define all(a)  (a).begin(), (a).end()
#define rall(a) (a).rbegin(),(a).rend()
#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++)
#define PB push_back
#define MP make_pair
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main(){
    int n,k;
    string res;
    cin >> n >> k;
    if(n % 2 == 0){
        if(n >= k * 2) res = "YES";
        else res = "NO";
    }
    else{
        if(n+1 >= k*2) res = "YES";
        else res = "NO";
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
/*
[m-solutions2019] D - Maximum Sum of Minimum
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MAX_N = 10000;

int N;
int c[MAX_N];
vector<int> g[MAX_N];
int cid = 0;
int ans[MAX_N];

void dfs(int v, int par = -1) {
    ans[v] = c[cid++];
    for (int to : g[v]) {
        if (to == par) {
            continue;
        }
        dfs(to, v);
    }
}

ll solve() {
    sort(c, c + N, greater<int>());
    dfs(0);
    return accumulate(c + 1, c + N, 0);
}

int main() {
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < N; i++) {
        cin >> c[i];
    }

    cout << solve() << endl;
    for (int i = 0; i < N; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	ll n; cin >> n;
	ll a[n];
	ll ans = 1145148931919810;
	for(ll i = 0; i < n; i++) cin >> a[i];
	for(ll i = -100; i <= 100; i++){
		ll po = 0;
		for(ll j = 0; j < n; j++) po += (a[j] - i) * (a[j] - i);
		ans = min(ans, po);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
def printAry(ary)
  for i in 0..ary.length - 1 do
    if i == 0 then
      printf("#{ary[i]}")
    else
      printf(" #{ary[i]}")
    end
  end
  printf("\n")
end

### main ###
str = STDIN.gets
ary = STDIN.gets.to_s.split(" ")

ary.map!(&:to_i)

printAry(ary)

for i in 1..ary.length - 1 do
  v = ary[i]
  j = i - 1
  while j >= 0 && ary[j] > v do
    ary[j+1] = ary[j]
    j = j - 1
  end
  ary[j+1] = v
  printAry(ary)
end

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


const int MAX_N = 1005;
int d[MAX_N][MAX_N];

int main2() {
  const int INF = 1001001001;
  REP(i, MAX_N) REP(j, MAX_N) d[i][j] = INF;

  int H, W; cin >> H >> W;
  vector<string> s(H);
  REP(i, H) cin >> s[i];

  queue< pair<int,int> > q;
  REP(i, H) REP(j, W) if (s[i][j] == '#') {
    d[i][j] = 0;
    q.push({i, j});
  }

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

  int ans = 0;
  while (!q.empty()) {
    auto p = q.front(); q.pop();
    chmax(ans, d[p.first][p.second]);
    REP(i, 4) {
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if (0 <= nx && nx < H && 0 <= ny && ny < W) {
        if (d[nx][ny] > d[p.first][p.second] + 1) {
          d[nx][ny] = d[p.first][p.second] + 1;
          q.push({nx, ny});
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 13456
#pragma target("avx")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define rep(i,b,e) for(ll i=b; i<e; i++)
#define be(vec) vec.begin(),vec.end()
#define print(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define scan(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	int n, k;
	scanf("%d %d", &n, &k);
	V a(200000, 0);
	rep(i, 0, n){
		int tmp;
		scanf("%d", &tmp);
		a[tmp-1]++;
	}
	std::sort(be(a), std::greater<ll>());
	ll ans = 0;
	rep(i, k, n) ans += a[i];
	printf("%ld\n", ans);
	return 0;
}


Measured memory_bytes: 1792
s = input()

def atgc(l, r):
    global s
    for i in range(l, r):
        if s[i] != "A" and s[i] != "T" and s[i] != "G" and s[i] != "C":
            return False
    return True

t_max = 0

for i in range(0, len(s) + 1):
    for j in range(i + 1, len(s) + 1):
        if atgc(i, j) and t_max < j - i:
            t_max = j - i
            
print(t_max)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int bubbleSort(int A[], int N) {
    int c = 0;
    bool flag = true;

    for (int i = 0; flag; i++) {
        flag = false;
        for (int j = N-1; j >= i+1; j--) {
            if (A[j] < A[j-1]) {
                swap(A[j], A[j-1]);
                flag = true;
                c++;
            }
        }
    }
    return c;
}

int main()
{
    int A[101];
    int N;

    cin >> N;

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

    int c = bubbleSort(A, N);

    for (int i = 0; i < N; i++) {
        cout << A[i];
        if (i != N-1)
            cout << " ";
        else
            cout << "\n";
    }

    cout << c << endl;

    return 0;
}

Measured memory_bytes: 3092
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);


int main() {
    int n;
    string s;
    cin >> n >> s;
    int x = 0;
    int ans = 0;
    rep(i, n) {
        if (s[i] == 'I')x++; else x--;
        ans = max(ans, x);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<vector<int> > vec(2, vector<int>(N+1, 0));
    for(int i=0; i<2; i++) {
        for(int n=0; n<N; n++) {
            int a;
            cin >> a;
            if(i==0) {
                vec[i][n+1] = vec[i][n]+a;
            } else {
                vec[i][n+1] = a;
            }
        }
    }
    
    vec[1][1] += vec[0][1];
    for(int n=1; n<N+1; n++) {
        vec[1][n+1] += max(vec[0][n+1], vec[1][n]);
    }
    
    cout << vec[1][N] << endl;


    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct moves{
  int x, y, z, w;
  void print(){
    cout << x + 1 << " " << y + 1 << " ";
    cout << z + 1 << " " << w + 1 << "\n";
  }
};

vector<moves> ans;

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout.setf(ios::fixed); cout.precision(17);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n, vector<int>(m));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> g[i][j];
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(g[i][j] & 1){
        g[i][j]--;
        if(j + 1 == m){
          if(i + 1 < n){
            ans.push_back({i, j, i + 1, j});
            g[i+1][j]++;
          }
        } else {
          ans.push_back({i, j, i, j + 1});
          g[i][j+1]++;
        }
      }
    }
  }
  cout << ans.size() << "\n";
  for(int i = 0; i < ans.size(); i++){
    ans[i].print(); 
  }
  return 0;
}


Measured memory_bytes: 5236
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main() {
    cin>>N;
    ll odd = (N+1)/2;
    long double p = odd, q = N;
    cout<<fixed<<setprecision(11)<<p/q<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
typedef unsigned long long ull;
typedef long long ll;
#define MAX 10005
using namespace std;

ull mm(ull n) {
  ull max=0;
  while(n > 0) {
    max += n%10;
    n /= 10;
  }
  return max;
}

int main() {
  ull n;
  cin >> n;
  if(n%mm(n) == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
using namespace std;

#define N  100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        ll l,r;
        cin>>l>>r;
        if(r-l+1>=2019)
        	cout<<0;
        else
        {
        	ll ans=hell;
        	for(int i=l;i<=r;i++)
        	{
        		for(int j=i+1;j<=r;j++)
        		{
        			ll p=i%2019;
        			ll q=j%2019;
        			ans=min(ans,(p*q)%2019);
        		}

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

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, N, A):
    H -= sum(A)
    return 'Yes' if H <= 0 else 'No'


def main():
    H, N = read_int_n()
    A = read_int_n()
    print(slv(H, N, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 16496
#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
map<int,int> m;
map<int,int>::iterator it;
int n;int a[200005];
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),m[a[i]]++;
    int ans = 0;
    for(int j=30;j>=1;j--){
        for(it=m.begin();it!=m.end();it++){
            if(it->second==0)
                continue;
        if(m.count((1<<j)-it->first)&&m[(1<<j)-it->first]){
            if(it->first*2==(1<<j)) {
                ans+=it->second/2;
                it->second=0;
            } else{
                if(it->second>=m[(1<<j)-it->first]) {
                    ans+=m[(1<<j)-it->first];
                    it->second-=m[(1<<j)-it->first];
                    m[(1<<j)-it->first]=0;
                } else {
                    ans+=it->second;
                    m[(1<<j)-it->first]-=it->second;
                    it->second=0;
                }
            }
        }
        }
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 10368
n = int(input())
list = [list(map(int,input().split())) for _ in range(3)]  
ans = 0
for i in range(n):
  if i == 0:
    ans += list[1][list[0][i]-1]
  else:
    ans += list[1][list[0][i]-1]
    if list[0][i] == list[0][i-1]+1:
      ans += list[2][list[0][i-1]-1]
print(ans)

Measured memory_bytes: 38384
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
cnt_dic=defaultdict(int)
for i in a:
  cnt_dic[i]+=1
cnt=0
for v in cnt_dic.keys():
  if cnt_dic[v]==v:
    pass
  else:
    if cnt_dic[v]<v:
      cnt+=cnt_dic[v]
    else:
      cnt+=(cnt_dic[v]-v)
print(cnt)

Measured memory_bytes: 18676
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>	
using namespace std;

int main(){
    int n,m,c,answer=0;
    vector<int> b;
    vector<vector<int>> a;
    scanf("%d %d %d",&n,&m,&c);
    b.reserve(m);
    a.assign(n,vector<int>());
    for (int i=0;i<m;i++){
        int tmp;
        scanf("%d",&tmp);
        b.push_back(tmp);
    }
    for (int i=0;i<n;i++){
        a[i].reserve(m);
        for (int j=0;j<m;j++){
            int tmp;
            scanf("%d",&tmp);
            a[i].push_back(tmp);
        }
    }
    for (int i=0;i<n;i++){
        int sum = 0;
        for (int j=0;j<m;j++){
            sum += a[i][j]*b[j];
        }
        sum += c;
        if (sum > 0) {
            answer++;
        }
    }
    printf("%d\n",answer);
}

Measured memory_bytes: 256
N,K=gets.chomp.split(' ').map{|n| n.to_i}

sum = 0
a = N/K
sum += a*a*a
if(K%2==0)
	# max b : N < K*(b+0.5)
	t=(N-K*0.5)/K
	if(t >= 0)
		#puts t
		t = t.to_i
		b = t + 1
		sum += b*b*b
	end
end
puts sum




Measured memory_bytes: 1788
#!/bin/sh

while true;
do
        read line1

        if [ -z "$line1" ]; then
                break
        fi

        # X A B
        # A - B >=0 delicious
        # A+X >= B safe
        # X >= B-A
        # $dead + X >= 0

        X=`echo $line1 | cut -d" " -f 1`
        yummy=`echo $line1 | awk '{print $2-$3}'`
        dead=`echo $line1 | awk '{print $2-$3+$1}'`

        if [ $yummy -ge 0 ]; then
                echo "delicious"
        else
                if [ $dead -ge 0 ]; then
                                echo "safe"
                        else
                                echo "dangerous"
                fi
        fi

done

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
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; }
//Get the highest value and key from a map.
template<typename KeyType, typename ValueType>
std::pair<KeyType,ValueType> get_max( const std::map<KeyType,ValueType>& x ) {
  using pairtype=std::pair<KeyType,ValueType>;
  return *std::max_element(x.begin(), x.end(), [] (const pairtype & p1, const pairtype & p2) {
        return p1.second < p2.second;
  });
}
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  ll q = a % b;

  return gcd(b, q);
}

int main() {
  ll a, b, c, d;
  vector<int> nums;
  cin >> a >> b >> c >> d;
  nums.push_back(c);
  nums.push_back(d);
  ll ex = (c / gcd(max(c, d), min(c, d)) * d);

  ll cnt = 0;
  for (auto x : nums) {
    ll p; 
    if (a < x) {
      p = x;
    } else if (a % x == 0) {
      p = a;
    } else {
      ll r = a % x;
      p = a - r + x;
    }
    if (p == b) {
      ++cnt;
      continue;
    } else if (p > b) {
      continue;
    }
    ll dis = (b - (p + 1) + 1);
    cnt += (dis / x) + 1;
  }

  ll excnt = 0;
  ll p;
  if (a < ex) {
    p = ex;
  } else if (a % ex == 0) {
    p = a;
  } else {
    ll r = a % ex;
    p = a - r + ex;
  }
  if (p == b) {
    ++excnt;
    cout << (b - a + 1) - cnt + excnt << endl;
    return 0;
  } else if (p > b) {
    cout << (b - a + 1) - cnt << endl;
    return 0;
  }
  ll dis = (b - (p + 1) + 1);
  excnt += (dis / ex) + 1;

  cout << (b - a + 1) - cnt + excnt << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}



int main() {
	int n;
	string str;
	cin >> n >> str;

	int Min = INT_MAX;
	int cou = 0;

	rep(i, 1, n) {

		cou += str[i] == 'E';

	}

	Min = cou;

	rep(i, 1, n) {
		if (str[i-1] == 'W') cou++;
		if (str[i] == 'E') cou--;

		Min = min(Min,cou);

	}

	cout << Min << endl;

	return 0;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

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

	vector<ll> ap, an;
	int zn=0;
	rep(i, n){
		if(a[i]==0) zn++;
		else if(a[i]>0) ap.push_back(a[i]);
		else an.push_back(-a[i]);
	}
	sort(ap.begin(), ap.end());
	sort(an.begin(), an.end());

	ll zeronum=(ll)zn*(n-1)-(ll)zn*(zn-1)/2;
	ll neganum=(ll)ap.size()*an.size();
	if(k<=neganum){//nega
		ll l=0, r=1000000000000000000;
		while(l<r){
			ll m=(l+r)/2+1;
			ll cnt=0;
			for(auto e : ap){
				ll ijo=(m-1)/e+1;
				auto it=lower_bound(an.begin(), an.end(), ijo);
				cnt+= an.end() - it;
			}
			bool ok= cnt>=k;
			if(ok) l=m;
			else r=m-1;
		}
		cout<<(-l)<<endl;
	}
	else if(k<=neganum+zeronum){
		cout<< 0 <<endl;
	}
	else{//posi
		k-=neganum+zeronum;

		ll l=0, r=1000000000000000000;
		while(l<r){
			ll m=(l+r)/2;

			ll cnt=0;
			repit(it, ap){
				ll e= *it;
				ll ika=m/e;
				auto en=upper_bound(ap.begin(), ap.end(), ika);
				if(it<en) cnt+= en-it-1;
			}
			repit(it, an){
				ll e= *it;
				ll ika=m/e;
				auto en=upper_bound(an.begin(), an.end(), ika);
				if(it<en) cnt+= en-it-1;
			}

			bool ok= cnt>=k;
			if(ok) r=m;
			else l=m+1;
		}
		cout<< l <<endl;
	}
	return 0;
}


Measured memory_bytes: 6796
N = int(input())
s = [input() for i in range(N)]

s_sorted = list(map(''.join, list(map(sorted, s))))

s_dict = dict()
cnt = 0
for k in s_sorted:
    if k in s_dict:
        cnt += s_dict[k]
        s_dict[k] += 1
    else:
        s_dict[k] = 1

#cnt = 0
# for k in s_dict:
#    cnt += sum(range(s_dict[k]))
#cnt = sum([sum(range(s_dict[k])) for k in s_dict])

print(cnt)

Measured memory_bytes: 38540
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> V;
const long long MOD=1000000007LL;
const long long INFL=1LL << 60;
const int INF=1<<29;


int main() {
    int X,A;
    cin>>X>>A;
    if(X<A)cout<<0<<endl;
    else cout<<10<<endl;
    return 0;
}

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

typedef long long ll;
const int INF = 1 << 30;


int n, m, X, Y;

int x[101], y[101];

int main(){
    cin >> n >> m >> X >> Y;

    for (int i = 0; i < n; i++){
        cin >> x[i];
    }
    for (int i = 0; i < m; i++){
        cin >> y[i];
    }

    sort(x, x+n);
    sort(y, y+m);

    bool check = true;
    if (X < Y && x[n - 1] < y[0] && X < y[0] && x[n-1] < Y) check = false;

    if ( !check){
        cout << "No War" << endl;
    } else {
        cout << "War" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10, INF = 1e9;
int p[MAXN], q[MAXN];
int f[MAXN];
int find(int p) {
    ++p;
    p = max(p, 0);
    p = min(p, MAXN - 1);
    int res = 0;
    for (;p; p -= p&-p)
        res += f[p];
    return res;
}
void add(int p) {
    ++p;
    for (;p < MAXN; p += p&-p)
        ++f[p];
}
int deg[MAXN];
pair <int, int> segment[4 * MAXN];
int lazy[4 * MAXN];
void build(int v, int b, int e) {
    if (e - b == 1) {
        segment[v] = {deg[b], b};
        return;
    }
    int mid = (b + e) / 2;
    build(2 * v, b, mid);
    build(2 * v + 1, mid, e);
    if (segment[2 * v + 1].first <= segment[2 * v].first)
        segment[v] = segment[2 * v + 1];
    else
        segment[v] = segment[2 * v];
}
void shift(int v) {
    lazy[2 * v] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    segment[2 * v].first -= lazy[v];
    segment[2 * v + 1].first -= lazy[v];
    lazy[v] = 0;
}
void clr(int v, int b, int e, int p){
    if (p < b || e <= p)
        return;
    if (e - b == 1) {
        segment[v] = {INF, b};
        return;
    }
    int mid = (b + e) / 2;
    shift(v);
    clr(2 * v, b, mid, p);
    clr(2 * v + 1, mid, e, p);
    if (segment[2 * v + 1].first <= segment[2 * v].first)
        segment[v] = segment[2 * v + 1];
    else
        segment[v]= segment[2 * v];
}
void upd(int v, int b, int e, int l, int r) {
    if (r <= b || e <= l)
        return;
    if (l <= b && e <= r) {
        ++lazy[v];
        --segment[v].first;
        return;
    }
    int mid = (b + e) / 2;
    shift(v);
    upd(2 * v, b, mid, l, r);
    upd(2 * v + 1, mid, e, l, r);
    if (segment[2 * v + 1].first <= segment[2 * v].first)
        segment[v] = segment[2 * v + 1];
    else
        segment[v]= segment[2 * v];
}
int32_t main () {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    --k;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
        q[p[i]] = i;
    }
    for (int i = n - 1; i >= 0; --i) {
        deg[q[i]] = find(q[i] + k) - find(q[i] - k - 1);
        add(q[i]);
    }
    // for (int i = 0; i < n; ++i)
    //     cout << deg[i] << ' ';
    build(1, 0, n);

    for (int i = n - 1; i >= 0; --i) {
    // for (int i = 1; i < 2* n; ++i, cout << ' ') {
    //     if (__builtin_popcount(i) == 1)
    //         cout << '\n';
    //     cout << segment[i].first << ':' << segment[i].second;
    // }
        p[segment[1].second] = i;
        q[i] = segment[1].second;
        clr(1, 0, n, q[i]);
        upd(1, 0, n, q[i] - k, q[i] + k + 1);
    }
    for (int i = 0; i < n; ++i) 
        cout << p[i] + 1 << '\n';
    return 0;
}


Measured memory_bytes: 28672
// Author: πα

#include <bits/stdc++.h>
using namespace std;
#define long int64_t

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, sum = 0;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i], sum += v[i];
    sort(v.begin(), v.end(), greater<>());
    cout << (sum > 4*m*v[m-1] ? "No" : "Yes");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,a,n) for(int i=(a); i<(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
int main() {
  int N; cin >> N;
  string S; cin >> S;
  int ans = 0;
  int sum=0;
  rep(i,N){
    if(S[i]=='I'){
      sum++;
      ans = max(ans, sum);
    }
    else if(S[i]=='D') sum--;  
  }
  cout << ans << endl;
}


Measured memory_bytes: 3568
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);

        int n=scan.nextInt();
        int x[]=new int[n];
        int y[]=new int[n];
        int z[]=new int[n];
        double p1=0,p2=0,p3=0,pi=0;
        for(int i=0;i<n;i++){
            x[i]=scan.nextInt();
        }
        for(int i=0;i<n;i++){
            y[i]=scan.nextInt();
            if(x[i]>=y[i]){
                z[i]=x[i]-y[i];
            }else{
                z[i]=y[i]-x[i];
            }
        }

        for(int i=0;i<n;i++){
            p1+=z[i];
            p2+=z[i]*z[i];
            p3+=z[i]*z[i]*z[i];
            if(z[i]>=pi){
                pi=z[i];
            }
        }
        p2=Math.sqrt(p2);
        p3=Math.pow(p3,1/3.0);

        System.out.printf("%f\n",p1);
        System.out.printf("%f\n",p2);
        System.out.printf("%f\n",p3);
        System.out.printf("%f\n",pi);
    }
}



Measured memory_bytes: 26596
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn vs(a: &mut Vec<Vec<usize>>, n: usize, p1: usize, p2: usize, done: &mut Vec<bool>) -> bool {
    if done[p2 - 1] {
        a[p1 - 1].push(p2);
        done[p1 - 1] = true;
        return false;
    } else if let Some(p3) = a[p2 - 1].pop() {
        if p1 != p3 {
            done[p1 - 1] = true;
            a[p1 - 1].push(p2);
            return vs(a, n, p2, p3, done);
        }
        done[p1 - 1] = true;
        done[p2 - 1] = true;
        return true;
    }
    false
}

fn day(a: &mut Vec<Vec<usize>>, n: usize) -> u32 {
    let mut done: Vec<bool> = vec![false; n];
    let mut cnt: u32 = 0;
    for p1 in 1..(n + 1) {
        if done[p1 - 1] {
            continue;
        } else if let Some(p2) = a[p1 - 1].pop() {
            if vs(a, n, p1, p2, &mut done) {
                cnt += 1;
            }
        }
    }
    cnt
}

fn all(a: &mut Vec<Vec<usize>>, n: usize) -> i32 {
    let mut vs_cnt: u32 = 0;
    let mut day_cnt: i32 = 0;

    while vs_cnt < ((n * (n - 1)) / 2) as u32 {
        let tmp = day(a, n);
        if tmp == 0 {
            day_cnt = -1;
            break;
        } else {
            vs_cnt += tmp;
        }
        day_cnt += 1;
    }

    return day_cnt;
}

fn gcd(x: u64, y: u64) -> u64 {
    if x > y {
        gcd_sub(x, y)
    } else {
        gcd_sub(y, x)
    }
}

fn gcd_sub(x: u64, y: u64) -> u64 {
    let r = x % y;
    if r == 0 {
        y
    } else {
        gcd_sub(y, r)
    }
}

fn main() {
    let ab: Vec<u64> = read_vec();
    let a: u64 = ab[0];
    let b: u64 = ab[1];
    let mut g = gcd(a, b);
    let max = ((g as f64).sqrt() as u64) + 10;
    let mut ans: u64 = 1;
    for i in 2..max {
        if g % i == 0 {
            ans += 1;
        }
        while g % i == 0 {
            g /= i;
        }
        if g == 1 {
            break;
        }
    }
    if (g > 1) {
        ans += 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
from _collections import defaultdict
n=int(input())
A=list(map(int,input().split()))

X=[A[i]-(i+1) for i in range(n)]
Y=[-A[i]-(i+1) for i in range(n)]
ans=0

P=defaultdict(int)
Q=defaultdict(int)

for x in X:
    P[x]+=1
for y in Y:
    Q[y]+=1

p=set(P.keys())
q=set(Q.keys())

r=p&q

for key in r:
    ans+=P[key]*Q[key]
print(ans)


Measured memory_bytes: 79308
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int n;
    cin >> n;
    vector<int> fib(n + 1, 1);
    repd(i, 2, n + 1) {
        fib[i] = fib[i - 1] + fib[i - 2];
    } 

    cout << fib[n] << endl;
    return 0;
}


Measured memory_bytes: 3084
def linearSearch(A, n, key):
	i = 0
	A.append(key)
	while (A[i] != key):
		i += 1
	del A[n]

	return i != n


if __name__ == '__main__':
	
	n = int(input())
	L = list(map(int, input().split()))

	q = int(input())
	Key = list(map(int, input().split()))

	cnt = 0
	for i in range(q):
		if (linearSearch(L, n, Key[i])):
			cnt += 1

	print(cnt)

Measured memory_bytes: 8544
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
	int n;
	int prime[]={3,5,7,11,13,17,19,23,29};
	int arr[]={105,165,195,135,189};
	cin>>n;
	if(n==105) cout<<1<<endl;
	else if(n<105) cout<<0<<endl;
	else{
		int count=0;
		for(int i=0;i<5;i++){
			if(arr[i]<=n) count++;
		}
		cout<<count<<endl;
	}
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

int main() {
    ll n, k;
    cin >> n >> k;
    map<ll, ll> mp;
    vector<P> v;
    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;
        mp[a] += b;
    }

    for(auto m : mp){
        v.emplace_back(P(m.first, m.second));
    }

    sort(v.begin(), v.end());
    for (auto i : v) {
        if (k > i.second) k -= i.second;
        else{
            cout << i.first << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 5368