akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000001

template <typename T>
struct BIT{
	vector<T> v;
	int n;
	
	const T init_value = 0;
	
	BIT(int sz){
		n=sz+1;
		v.resize(n,init_value);
	}
	
	BIT(vector<T> &x){
		n=x.size()+1;
		v.resize(n,init_value);
		
		for(int i=0;i<x.size();i++){
			add(i,x[i]);
		}
		
	}

	void add(int x,T val){
		x++;
		while(x < n){
			v[x] = func(v[x],val);
			x += x & (-x);
		}
	}
	
	//区間[0,r)におけるクエリ処理
	T query(int r){
		T ret = init_value;
		
		while(r>0){
			ret = func(v[r],ret);
			r -= r & (-r);
		}
		
		return ret;
	}
	
	T query(int l,int r){
		return query(r) - query(l);
	}
	
	T func(T a,T b){
		return a+b;
	}
	
};

int main(){
	
	long long N;
	cin>>N;
	
	long long need = (N*(N+1)/2 +1)/2;//need以上要る
	
	vector<long long> a(N);
	for(int i=0;i<N;i++)cin>>a[i];
	
	long long ok = 0;
	long long ng = Inf;
	
	while(ng-ok>1){
		long long mid = (ok+ng)/2;
		long long offset = N;
		BIT<long long> B(2*N+1);
		B.add(offset,1);
		long long S = 0;
		long long cnt = 0;
		for(int i=0;i<N;i++){
			if(mid<=a[i])S++;
			else S--;
			cnt += B.query(0,offset+S+1);
			B.add(offset+S,1);
		}
		if(cnt>=need)ok = mid;
		else ng = mid;
	}
	
	cout<<ok<<endl;
	
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

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

  vector<int> ins;
  int x = 0;

  int diff=0;
  rep(i, N) {
    if (S[i]=='(') diff++;
    else diff--; 
  }
  int l=0, r=0; 
  if (diff>=0) r+=diff; else l-=diff;
  string new_S = "";
  rep(i, l) new_S += "(";
  new_S += S;
  rep(i, r) new_S += ")";

  diff = 0;
  int d_max = 0;
  rep(i, new_S.length()) {
    if (new_S[i]=='(') diff++;
    else diff--; 
    d_max = max(d_max, -1*diff);
  }

  rep(i, d_max) cout << '(';
  cout << new_S;
  rep(i, d_max) cout << ')';
  cout << endl;
  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 repi(i, s, n) for (int i = (s); i < (n); i++)
typedef pair<int, int> P;
typedef long long ll;
const int INF = 100100100;
const int MOD = 1e9 + 7;

int main() {

  int N;
  cin >> N;

  vector<int> x(N);
  rep(i, N) { cin >> x[i]; }

  ll ans = INF;
  rep(i, 100) {
    ll buf = 0;
    rep(j, N) {
      buf += pow(x[j] - (i + 1), 2);
      // printf("x[j]:%d i:%d ret:%f buf:%lld\n", x[j], i, pow(x[j] - (i + 1), 2), buf);
    }
    ans = min(ans, buf);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		StringBuilder str = new StringBuilder();
		List<Integer> b = new ArrayList<>();
		//int[] b = new int[N];
		for(int i=0; i<N; i++){
			b.add(Integer.parseInt(sc.next()));
		}
		boolean flag = true;
		while(b.size()>0){
			flag = true;
			for(int i=b.size()-1; i>=0; i--){
				if(b.get(i) == i+1){
					b.remove(i);
					str.insert(0,""+(i+1)+"\n");
					flag = false;
					break;
				}
			}
			
			//System.out.println(b.size());
			if(flag)break;
		}
		if(flag){
			System.out.println("-1");
		}else{
			System.out.println(str);
		}
		
		sc.close();
	}

	
}


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

int main() {
	int H, W;
	cin >> H >> W;
	char a[100][100];
	for (int i = 0; i < H; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < W + 2; i++) {
		cout << "#";
	}
	cout << endl;
	for (int i = 0; i < H; i++) {
		cout << "#";
		for (int j = 0; j < W; j++) {
			cout << a[i][j];
		}
		cout << "#" << endl;
	}
	for (int i = 0; i < W + 2; i++) {
		cout << "#";
	}
	cout << endl;
}

Measured memory_bytes: 256
X, N = map(int, input().split())
if N != 0:
  p = list(map(int, input().split()))
  for i in range(N):
    if X - i not in p:
      print(X - i)
      break
    elif X + i not in p:
      print(X + i)
      break
  else:
    print(X - i - 1)
else:
  print(X)

Measured memory_bytes: 9116
# ABC143E - Travel by Car
def floyd_warshall(dist):
    """
    Compute the shortest paths of all pairs and modify dist.
    """
    V = len(dist)
    for i in range(V):  # intermediate point
        for j, c2 in enumerate(dist[j][i] for j in range(V)):  #  source
            for k, (c1, c3) in enumerate(zip(dist[j], dist[i])):  # target
                if c2 + c3 < c1:
                    dist[j][k] = c2 + c3


def main():
    # FW -> once more FW to edges <= L
    N, M, L, *X = map(int, open(0).read().split())
    ABC, ST = X[: 3 * M], X[3 * M + 1 :]
    INF = 1 << 60
    dist = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dist[i][i] = 0
    for v, u, cost in zip(*[iter(ABC)] * 3):
        dist[v][u] = dist[u][v] = cost
    floyd_warshall(dist)

    # assume distance within L as 1 and compute the number of fueling
    modified_dist = [[1 if x <= L else INF for x in d] for d in dist]
    floyd_warshall(modified_dist)
    ans = []
    for s, t in zip(*[iter(ST)] * 2):
        x = modified_dist[s][t]
        if x < INF:
            ans.append(x - 1)
        else:
            ans.append(-1)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Measured memory_bytes: 97984
n,x=map(int,input().split())
l=[0]
for i in range(n+1):
  l.append(2**(i+1)-1)
m=[0]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  if x<2**(i+1)-1:
    x-=1
  elif x==2**(i+1)-1:
    c+=l[i]+1
    x=0
  elif x>2**(i+1)-1:
    c+=l[i]+1
    if x==m[i+1]:
      x-=1
    x=x-(2**(i+1)-1)
print(c)

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

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

    int count =0;
    for(int i=0; i<N; i++){
        int val = a[i];
        if(i+1 == a[val-1]){
            count += 1;
        }
    }

    cout << count/2 << endl;
    return 0;
}

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

int main()
{
    int i,a,b,c; vector<int> vec; int sum1=0;int sum2=0;
    cin>>a;
    for(i=0;i<a;i++){cin>>b;vec.push_back(b);sum1+=b;}
    int diff=sum1;
    for(vector<int>::iterator iter=vec.begin();iter!=vec.end();iter++)
    {
        sum2+=*iter;
        if(abs(sum1-2*sum2)>diff)
        {break;}
        diff=abs(sum1-2*sum2);
    }
    cout<<diff<<endl;
    return 0;
}


Measured memory_bytes: 256
use proconio::input;
use proconio::marker::Chars;
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused)]
const ALPHA_SMALL: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];
#[allow(unused)]
const ALPHA: [char; 26] = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
fn main() {
    input!(N: String);
    let cs: Vec<char> = N.chars().collect();
    let ans = cs
        .iter()
        .fold(0, |acc, &x| (acc + (x as usize - '0' as usize) % 9));
    if ans % 9 == 0 {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 3208
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

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

	int count = 1, D = 0;
	int L;
	for (int i = 0; i < N; i++) {
		cin >> L;
		D = D + L;
		if (D <= X) {
			count++;
		}
	}

	cout << count << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
	double x, y;

	Point(double x=0, double y=0) : x(x), y(y) {}

	Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

	Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

	Point operator*(const double m) const { return Point(x*m, y*m); }

	Point operator/(const double d) const { return Point(x/d, y/d); }

	bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

	bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }
};

ostream& operator << (ostream& os, const Point& p) {
	os << "(" << p.x << ", " << p.y << ")";
	return os;
}

double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
double atan(Point p) { return atan2(p.y, p.x); }
double norm(Point p) { return p.x * p.x + p.y * p.y; }
double abs(Point p) { return sqrt(norm(p)); }
double distancePP(Point p, Point o) { return sqrt(norm(o - p)); }

int ccw(Point a, Point b, Point c) {
	b = b-a;
	c = c-a;

	if(cross(b, c) > 0.0) return +1;	//conter clockwise
	if(cross(b, c) < 0.0) return -1;	//clockwise
	if(dot(b, c) < 0.0) return +2;	//a on Seg(b,c)
	if(norm(b) < norm(c)) return -2;	//b on Seg(a,c)
	return 0;	//c on Seg(a,b)
}

// bool cmp_y(const Point& a,const Point& b) {
// 	if(a.y != b.y) return a.y < b.y;
// 	return a.x < b.x;
// }

vector<Point> convex_hull(vector<Point> ps) {   
	int n = ps.size();
	sort(ps.begin(),ps.end());

	int k = 0;
	vector<Point> convex(n*2);

	rep(i, n) {
		while (k > 1 && ccw(convex[k-2], convex[k-1], ps[i]) == -1 ) {
			k--;
		}
		convex[ k++ ] = ps[i];
	}

	for(int i = n - 2, t = k; i >= 0; i--) {
		while (k > t && ccw(convex[k-2], convex[k-1], ps[i]) == -1 ) {
			k--;
		}
		convex[ k++ ] = ps[i];
	}

	convex.resize(k-1);
	return convex;
}

double convex_diameter(const vector<Point>& ps) {
	vector<Point> qs = convex_hull(ps);
	int n = qs.size();

	if(n == 2) return distancePP(qs[0], qs[1]);

	int i = 0, j = 0;
	rep(k, n) {
		if(!(qs[i] < qs[k])) i = k;
		if(qs[j] < qs[k]) j = k;
	}

	double ret = 0;
	int si = i, sj = j;
	while(i != sj || j != si) {
		ret = max(ret, distancePP(qs[i], qs[j]));
		if( cross(qs[(i+1)%n] - qs[i], qs[(j+1)%n] - qs[j]) < 0) {
			i = (i + 1) % n;
		} else {
			j = (j + 1) % n;
		}
	}
	return ret;
}

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

	vector<Point> v(n);
	rep(i, n) cin >> v[i].x >> v[i].y;

	cout << fixed;
	cout.precision(20);
	cout << convex_diameter(v) << endl;

	return 0;
}

Measured memory_bytes: 5956
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a); i>n; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
inline int f(int n, vi s, int q, vi t) {
	int cnt = 0;
	rep(j, 0, q) {
		if(count(all(s), t[j])) ++cnt;
	}
	return cnt;
}
int main() {
	int n; cin >> n;
	vi s(n); rep(i, 0, n) cin >> s[i];
	int q; cin >> q;
	vi t(q); rep(i, 0, q) cin >> t[i];
	P(f(len(s), s, q, t));
	return 0;
}

Measured memory_bytes: 3204
n = int(input())
H = list(map(int, input().split()))

cnt = 0
ans = 0
tmp = H[0]
for h in H[1:]:
    if h <= tmp:
        cnt += 1
    ans = max(ans, cnt)
    if h > tmp:
        cnt = 0
    tmp = h

    
print(ans)

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

using namespace std;
typedef long long ll;
ll cnt[110]={};
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);

    ll t=1;
    //cin>>t;
    while(t--)
    {
       ll n,k,x,c=0;
       cin>>n>>k;
       for(int i=0;i<k;i++)
       {
           ll m;
           cin>>m;
           while(m--)
           {
               cin>>x;
               cnt[x]++;

           }
       }
       for(int i=1;i<=n;i++)
        !cnt[i]? c++:c=c;
       cout<<c;
    }
    return 0;
}


Measured memory_bytes: 3576
#pragma GCC optimize ("-O3")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define f(i,x,n) for(ll i=x;i<n;i++)
#define pb push_back
#define mp make_pair
#define debug(x) cout<<x<<"\n";
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
long long MOD=pow(10,9)+7;
long long fact( int n) 
{ 
    long long res = 1, i; 
    for (i = 2; i <= n; i++) 
         res=((res%MOD)*(i%MOD))%MOD;
    return res; 
} 
bool compare(pair<ll,ll>a,pair<ll,ll>b)
{
	 return a.first<b.first;
}
int main() {
	
	int t;
	t=1;
	//cin >> t;
	while(t--){
   int n;
   cin>>n;
   vector<pair<ll,ll>>arr(n);
   ll a,b;
   pair<ll,ll>p;
   for(int i=0;i<n;i++)
   {
   	  cin>>a>>b;
   	  p.first=a;
   	  p.second=b;
   	  arr[i]=p;
   	  
   }
   if(n==1)
   {
   	cout<<0;
   	continue;
   }
    ll max1 = -1e18, min1 = 1e18; 
    ll max2 = -1e18, min2 = 1e18; 
  
    for (int i = 0; i < n; i++) { 
  
        max1 = max(max1, arr[i].first + arr[i].second); 
        min1 = min(min1,  arr[i].first + arr[i].second); 
        max2 = max(max2,  arr[i].first - arr[i].second); 
        min2 = min(min2,  arr[i].first - arr[i].second); 
    } 
  
    cout<< max(max1 - min1, max2 - min2); 

}
	
	return 0;
}  
	
	
	
	
	
	
	
	
	

Measured memory_bytes: 6404
X, N = map(int,input().split())
if N == 0:
    print(X)
    exit()
LP = list(map(int, input().split()))


for i in range(100):
    ans = X - i
    if ans not in LP:
        print(ans)
        exit()
    else:
        dans = X + i
        if dans not in LP:
            print(dans)
            exit()

Measured memory_bytes: 9112
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;
const int MOD = 1000000007;

int main(){
    int n;string s;cin >>n>>s;
    
    vi west(n), east(n);
    
    for(int i=0; i<n; i++){
        if(i)west[i] += west[i-1];
        if(s[i]=='W')west[i]++;
    }
    
    for(int i=n-1; i>=0; i--){
        if(i!=n-1)east[i] += east[i+1];
        if(s[i]=='E')east[i]++;
    }
    
    int ans = 300000;
    for(int i=0; i<n; i++){
        int c;
        if(!i)
            c = east[1];
        else if(i==n-1){
            c = west[n-2];
        }
        else{
            c = east[i+1] + west[i-1];
        }
        
        ans = min(ans, c);
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 6120
import math
 
A, B, C, D = map(int, input().split())

def battle(A, B, C, D):
  C = C-B
  if C <= 0:
    return "Yes"
  A = A-D
  if A <= 0:
    return "No"
  return battle(A,B,C,D)
  
print(battle(A, B, C, D))  

Measured memory_bytes: 9188
//abc112_c.cpp
//Sat Oct 27 09:18:31 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

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

	int flag = 0;
	for (int i=0;i<=100;i++){
		if (flag == 1){
			break;
		}
		for (int j=0;j<=100;j++){
			int temphight = 0;
			flag = 1;
			for (int k=0;k<n;k++){
				if (h[k]==0){
					continue;
				}
				temphight = abs(i-x[k])+abs(j-y[k])+h[k];
				break;
			}
			for (int l=0;l<n;l++){
				if (h[l]==0 && abs(x[l]-i)+abs(y[l]-j) > temphight){
					continue;
				}else if (temphight!=abs(x[l]-i)+abs(y[l]-j)+h[l]){
					flag = 0;
					break;
				}
			}
			if (flag == 1){
				cout << i << " " << j << " " << temphight << endl;
				break;
			}
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)

int main() {

    int a,b;
    scanf("%d %d", &a, &b);

    if( a%2 == 1 && b%2 == 1 ){
        printf ("Yes\n");
    }else{
        printf ("No\n");
    }

    return 0;
}



Measured memory_bytes: 256
import bisect

S = input()
T = input()

ls = len(S)
d = {}
for i, s in enumerate(S):
  if s in d:
    d[s].append(i+1)
  else:
    d[s] = [i+1]


now = 0
ans = 0
pre_t = ''
for t in T:
  if not t in d:
    ans = -1
    break
    
  if t == pre_t:
    idx = bisect.bisect_left(d[t], now+1)
  else:
    idx = bisect.bisect_left(d[t], now)

  if idx == len(d[t]):
    idx = 0
  
  if d[t][idx] > now:
    ans += d[t][idx] - now
  else:
    ans += ls + d[t][idx] - now
  
  now = d[t][idx]
  pre_t = t

print(ans)

Measured memory_bytes: 7540
#include <iostream>
#include<unordered_map>
#include<bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y, long long int p)  
{  
    long long int res = 1;      
  
    x = x % p; 
   
    if (x == 0) return 0; 
  
    while (y > 0)  
    {  
        
        if (y & 1)  
            res = (res*x) % p;  
  
          
        y = y>>1;  
        x = (x*x) % p;  
    }  
    return res;  
}  
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	t=1;
	while(t--)
	{
        int n;
        cin>>n;
        int ans=-1e9;
        int count=0;
       // int ok=1;
        
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            if( x==y)
            {
                count++;
                ans=max(count,ans);
            }
            else
            {
                count=0;
            }
        }
        
        if(ans>=3)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
           
	   
	}
	   
	   
	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

struct point {
  int x, y, d;
  char c;
  point(){};
  point(int a, int b) {
    x = a;
    y = b;
  }
};

int H, W;
vector<string> G;
vector<vector<ll>> d;

void bfs() {
  queue<point> q;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (G[i][j] == '#') {
        q.push(point(i, j));
        d[i][j] = 0;
      }
    }
  }

  while (!q.empty()) {
    point p = q.front();
    q.pop();
    int px = p.x, py = p.y;
    for (int i = 0; i < 4; i++) {
      int nx = px + dx[i], ny = py + dy[i];
      if (nx < 0 || H <= nx || ny < 0 || W <= ny) {
        continue;
      }
      if (d[nx][ny] != -1) {
        continue;
      }
      if (G[nx][ny] != '#') {
        d[nx][ny] = d[px][py] + 1;
        G[nx][ny] = '#';
        q.push(point(nx, ny));
      }
    }
  }
}

void solve() {
  bfs();
  ll res = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      res = max(res, d[i][j]);
    }
  }
  cout << res << "\n";
}

int main() {
  cin >> H >> W;
  G.resize(H);
  d.resize(H, vector<ll>(W, -1));
  for (int i = 0; i < H; i++) {
    cin >> G[i];
  }
  solve();
  return 0;
}

Measured memory_bytes: 25524
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
if sum(A) < sum(B):
    print(-1)
    exit()

l = []
cnt,low = 0,0
for i in range(N):
    if A[i] > B[i]:
        l.append(A[i]-B[i])
    if A[i] < B[i]:
        cnt += 1
        low += B[i] - A[i]

cnt2 = 0
l.sort(reverse=True)
for i in range(len(l)):
    if low <= 0:
        break
    low -= l[i]
    cnt2 += 1
print(cnt + cnt2)

Measured memory_bytes: 24268
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
void bubble_sort(struct Card *card,int n);
void selection_sort(struct Card *card,int n);
struct Card{ 
        char name[2];
        int num;
        int jun;
};

int main(){
        int n;
        int i;
        int yn=0;
        Card card[36];
        Card bubble[36];
        Card selection[36];
        cin>>n;
        for(i=0;i<n;i++){
                cin>>card[i].name[0];
                cin>>card[i].name[1];
                card[i].num=card[i].name[1]-0x30;
                card[i].jun=i;
        }
        for(i=0;i<n;i++){
                bubble[i]=card[i];
                selection[i]=card[i];
        }
        bubble_sort(bubble,n);
        selection_sort(selection,n);
        for(i=0;i<n;i++){
                cout<<bubble[i].name[0]<<bubble[i].num;
                if((i<n-1)&&(bubble[i].num==bubble[i+1].num)){
                        if(bubble[i].jun>bubble[i+1].jun){
                                yn=1;
                        }
                }
                if(i<n-1){
                        cout<<" ";
                }else{
                        cout<<endl;
                }
        }
        if(yn==0){
                cout<<"Stable\n";
        }else{
                cout<<"Not stable\n";
        }
        yn=0;
        for(i=0;i<n;i++){
                cout<<selection[i].name[0]<<selection[i].num;
                if((i<n-1)&&(selection[i].num==selection[i+1].num)){
                        if(selection[i].jun>selection[i+1].jun){
                                yn=1;
                        }
                }
                if(i<n-1){
                        cout<<" ";
                }else{
                        cout<<endl;
                }
        }
        if(yn==0){
                cout<<"Stable\n";
        }else{
                cout<<"Not stable\n";
        }
        return 0;
}

void bubble_sort(struct Card *card,int n){
        int i,j;
        int a,b;
        Card tmp;
        for(i=0;i<n-1;i++){
                for(j=n-1;j>i;j--){
                        a=j;
                        b=j-1;
                        if(card[b].num>card[a].num){
                                tmp=card[b];
                                card[b]=card[a];
                                card[a]=tmp;
                        }
                }
        }

}

void selection_sort(struct Card *card,int n){
        int i,j;
        int minj;
        Card tmp;
        for(i=0;i<n;i++){
                minj=i;
                for(j=i;j<n;j++){
                        if(card[j].num<card[minj].num){
                                minj=j;
                        }
                }
                tmp=card[i];
                card[i]=card[minj];
                card[minj]=tmp;
        }
}

Measured memory_bytes: 3092
#include<stdio.h>
int main(){
  long long a,b,c,d,e;
  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e);
  a-=d*100/b+e*100/c;
  if(d*100%b)a--;
  if(e*100%c)a--;
  //prrintf("%lld %lld",c*100/);
  printf("%lld\n",a<0?-1:a);
  return 0;
}

Measured memory_bytes: 600
#include<stdio.h>
int num[4];
char op[4];
int f(int pos, int hap) {
    if(pos==4) {
        if(hap==7) return 1;
        else return 0;
    }
    if(f(pos+1, hap+num[pos])){
        op[pos]='+';
        return 1;
    }
    if(f(pos+1, hap-num[pos])) {
        op[pos]='-';
        return 1;
    }
    return 0;
}
int main() {
    for(int i=0;i<4;i++) scanf("%1d", num+i);
    f(1, num[0]);
    for(int i=0;i<4;i++) {
        if(i>0) printf("%c", op[i]);
        printf("%d", num[i]);
    }
    printf("=7");
    return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main() {
  int N, A[SIZE], B[SIZE] = {};

  scanf("%d", &N);

  for (int i=0; i<N; i++) {
    scanf("%d", A+i);
  }

  int M = 0;

  for (int i=N; i>=1; i--) {
    bool b = A[i-1];

    for (int j=i-1; j<N; j+=i)
      b ^= B[j];

    B[i-1] = b;
    M += B[i-1];
  }

  printf("%d\n", M);

  bool first = true;
  for (int i=0; i<N; i++) {
    if (!B[i]) continue;

    if (!first) printf(" ");

    printf("%d", i+1);
    first = false;
  }

  puts("");

  return 0;
}


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

int main(){
  vector<char> s;
  char c;
  while(cin >> c){
    if(c!='B'){
      s.push_back(c);
    }
    else if(c=='B' && s.size()!=0){
      s.pop_back();
    }
  }
  for(int i=0;i<s.size();i++){
    cout << s.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
  l_1 = [a[n-1-2*i] for i in range(n//2)]
  l_2 = [a[2*i] for i in range(n//2)]
else:
  l_1 = [a[n-1-2*i] for i in range((n+1)//2)]
  l_2 = [a[2*i+1] for i in range(n//2)]
print(*l_1, *l_2)

Measured memory_bytes: 30912
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;


int H,W,K;
vector<string> S;
vector<vector<int>> ans;



void dfsW(int a,int b,int k){
    
    ans[a][b] = k;
    
    if(a-1 >= 0){
        if(S[a-1][b] == '.' && ans[a-1][b] == -1){
            ans[a-1][b] = k;
            dfsW(a-1, b, k);
        }
    }
    
    if(a+1 < H){
        if(S[a+1][b] == '.' && ans[a+1][b] == -1){
            ans[a+1][b] = k;
            dfsW(a+1, b, k);
        }
    }
    
}

int dfsH(int a,int b,int d){
    if(d == 1 && b == W-1 && ans[a][b] <= 0) return -1;
    
    if(ans[a][b] <= 0){
        return ans[a][b] = dfsH(a,b+d,d);
    }else{
        return ans[a][b];
    }
    
}



int main()
{
    cin >> H >> W >> K;
    S.resize(H);
    rep(i,H) cin >> S[i];
    ans.assign(H,vector<int>(W,-1));
    
    
    int k = 0;
    
    rep(i,H) rep(j,W){
        if(S[i][j] == '#'){
            k++;
            dfsW(i,j,k);
        }
    }
    
    rep(i,W){
        int dd = 1;
        if(ans[0][i] <= 0){
            if(i == W-1) dd = -1;
            rep(j,H){
                dfsH(j,i,dd);
            }
        }
    }
    
    rep(i,H) {rep(j,W) cout << ans[i][j] << " ";cout << endl;}
    
    return 0;
}



Measured memory_bytes: 1280
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000 //1e16
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,r,l,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U; 
    // int a,b;
    cin>>n>>r;
  if(n>=10)
  {
    cout<<r;
    return;
  }
  cout<<r+1000-100*n;
}
 

signed main()
{

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);
	
	ll n, k; cin >> n >> k;

	ll minsum = 0, maxsum = 0;
	ll ans = 0;
	const ll mod = 1000000007;

	for (int i = 1; i <= n + 1; i++) {
		minsum += i - 1, maxsum += n - i + 1;
		//printf("%d %lld %lld\n", i, minsum, maxsum);
		if (i >= k)
			ans += (maxsum - minsum + 1);
	}
	cout << (ans % mod) << endl;
}



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

int main(){
    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    cout << ((s < t) ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
#include<map>
int test[123456], uiop[123456], atai[123456];
using namespace std;
int main() {
	long long n, k = 0; string s; cin >> s;
  for(int h=0;h<s.size()/2;h++){
    if(s[h]!=s[s.size()-h-1]){
      k++;
    }
  }
  cout<<k<<endl;
}

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

int main()
{
  int N;
  ll a[210000];
  ll s[210000];
  ll res=INF;
  cin >> N;

  rep(i,N) cin >> a[i];

  ll sum=0;
  rep(i,N){
    sum += a[i];
    s[i] = sum;
  }
  rep(i,N-1){
    ll x = s[i];
    ll y = sum - s[i];
    res = min(res, abs(x-y));
  }

  cout << res << endl;
}

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

//#define int long long
#define reps(i,s,n) for(ll (i)=(s);(i)<(ll)(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) reps(i,0,n+1)
#define repst(i,s,n) reps(i,s,n+1)
#define reprt(i,n,t) for(ll (i)=(n);(i)>=t;--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln
#define dbga(x,n) for(int (i)=0;i<n;++i){cout<<x[i]<<(i==n-1?'\n':' ');}

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

// 一つのノードが複数の状態を持つグラフは状態ごとにノードを分割して解く
// 今回は会社1〜cmax全てから会社0にコスト1の辺を張ればいい 改札で乗り換えするイメージ
// ↓は素直に今いる路線と違う路線に乗るときコストを増やす実装

int n, m, p, q, c, d[100100];
vpii e[100100];
set<int> us[100100];

signed main() {
	cin >> n >> m;
	rep(i,m) {
		cin >> p >> q >> c;
		e[p].pb({q,c}), e[q].pb({p,c});
	}
	fill(d, d+n+1, inf);
	d[1] = 0;
	priority_queue<pii> q;
	q.push({0,1});
	while (!q.empty()) {
		int v = q.top().se, dis = -q.top().fi; q.pop();
		if (d[v]<dis) continue;
		each(i,e[v]) {
			int td = d[v];
			// 違う路線に乗り換え
			if (!us[v].count(i.se)) td++;
			if (td<d[i.fi]) {
				d[i.fi] = td;
				us[i.fi].clear();
				us[i.fi].insert(i.se);
				q.push({-d[i.fi],i.fi});
			}
			// i.fiへの行き方が同じコストで複数ある場合 都合良い方に乗ってきたことにすればいい
			else if (td==d[i.fi]) us[i.fi].insert(i.se);
		}
	}
	cout << (d[n]==inf ? -1 : d[n]) << ln;
}

Measured memory_bytes: 23412
n,k = map(int,input().split())
li = list(map(int,input().split()))

cnt_a = 0
cnt_b = 0
mod = 10**9 + 7

for i in range(n):
    for j in range(n):
        if i >= j:
            if li[i] > li[j]:
                cnt_b += 1
        else:
            if li[i] > li[j]:
                cnt_a += 1
            
ans = cnt_a * (k*(k+1))//2 +  cnt_b * ((k-1)*k) // 2

print(ans%mod)

Measured memory_bytes: 3188
#include <iostream>
#include <unistd.h>
#include <cmath>
#include <vector>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main(){
    int n,w;    cin >> n >> w;
    vector<pair<int, int> >dic(n);
    rep(i, n)   cin >> dic[i].first >> dic[i].second;
    vector<vector<ll> >dp(w+1, vector<ll>(n+1));
    for(int i = 1; i <= w; i++){
        for(int j = 1; j <= n; j++){
            int w = dic[j-1].first;
            int v = dic[j-1].second;
            dp[i][j] = max(dp[i][j], dp[i][j-1]);
            if(i - w >= 0){
                dp[i][j] = max(dp[i][j], dp[i-w][j-1] + v);
            }
        }
    }
    cout << dp[w][n] << endl;
}


Measured memory_bytes: 84096
n,m=map(int,input().split())
ac=0
ans=[True]*n
wa=[0]*n
for i in range(m):
    p,s=input().split()
    p=int(p)-1
    if s=="AC" and ans[p]:
        ans[p]=False
        ac+=1
    elif s=="WA" and ans[p]:
        wa[p]+=1

cnt=0
for i in range(n):
    if not ans[i]:
        cnt+=wa[i]

print(ac,cnt)

Measured memory_bytes: 4596
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a[ohara],b[ohara],c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll now[ohara];
priority_queue<P> que;
ll res[ohara];

//-------------------------↓↓↓↓↓↓------------------------

//------ 自分を天才だと信じる ------

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

    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i],now[i]=b[i];
    rep(i,n){
        ll hiku=(i==0 ? now[n-1] : now[i-1] )+(i==n-1 ? now[0] : now[i+1] );
        if(hiku<b[i])que.push({b[i],i});
    }
    while(1){
        if(que.empty())break;
        cnt++;
        if(cnt==10000000-10000)break;
        P X=que.top();
        que.pop();
        ll sco,ind;

        sco=X.fi;
        ind=X.se;
        //cout<<sco<<" "<<ind<<"\n";
        //scoをa[ind]までか引けるだけ引く
        ll hiku=(ind==0 ? now[n-1] : now[ind-1] )+(ind==n-1 ? now[0] : now[ind+1] );
        ll kaisuu=(sco-a[ind])/hiku;
        ans+=kaisuu;
        sco=sco-hiku*kaisuu;
        now[ind]=sco;
        //何をpushするか

        ll now_ind=(ind-1+n)%n;
        hiku=(now_ind==0 ? now[n-1] : now[now_ind-1] )+(now_ind==n-1 ? now[0] : now[now_ind+1] );
        if(hiku<now[now_ind])que.push({now[now_ind],now_ind});

        now_ind=(ind+1)%n;
        hiku=(now_ind==0 ? now[n-1] : now[now_ind-1] )+(now_ind==n-1 ? now[0] : now[now_ind+1] );
        if(hiku<now[now_ind])que.push({now[now_ind],now_ind});
    }
    rep(i,n){
        if(now[i]!=a[i]){
            Cout(-1);
            return 0;
        }
    }
    Cout(ans);
    return 0;
}


Measured memory_bytes: 14708
/*
* @author:  codancer
* @createTime:  2020-06-29, 11:14:13
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 1e4+10;
vector<int> prs;
bool vis[N];
void init(){
	vis[1]=1;
	rep(i,2,N-1){
		if(!vis[i]){
			prs.pb(i);
			for(int j=i+i;j<N;j+=i) vis[j]=0;
		}
	}
}
int cal(int x){
	int m=(int)prs.size();
	int ans=1;
	for(int i=0;i<m&&prs[i]*prs[i]<=x;i++){
		int cnt=0;
		while(x%prs[i]==0){
			cnt++;
			x/=prs[i];
		}
		ans*=(cnt+1);
	}
	if(x!=1) ans*=2;
	return ans;
}
ll A[200000];
int main(){
	init();
	ll ans=0;
	int n;
	cin>>n;
	for(ll i=1;i<=100000;i++){
		A[i]=i*(i+1)*(2*i+1)/6;
	}
	int sq=(int)sqrt(n);
	for(ll m=1;m<=sq;++m){
		ans+=m*(m+n/m)*((n/m)+1-m);
	}
	cout<<ans-A[sq]<<endl;
	return 0;
}



Measured memory_bytes: 4532
N = int(input())
Maxi = [0] * N
Ai = []
for i in range(N):
	Ai.append((i, int(input())))

Ai.sort(key = lambda t: t[1], reverse=True)

mi,max = Ai[0]

for i in range(N):
	Maxi[i] = max

Maxi[mi] = Ai[1][1]

for i in range(N):
	print(Maxi[i])


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

int main(){
	string str;
	cin >> str;
	bool is_easy=true;
	for(int i=0; i<str.size(); i++){
		if(i%2==0){
			if(str[i]=='R' || str[i]=='U' || str[i]=='D') continue;
			is_easy = false;
		}else{
			if(str[i]=='L' || str[i]=='U' || str[i]=='D') continue;
			is_easy = false;
		}
	}
	if(is_easy){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
    return 0;
}

Measured memory_bytes: 256
def Meg_nib(ng,border,lists):
    ng = -1
    ok = len(lists) - 1
    if len(lists) == 0 or border >= lists[ok]:
        return -1
    while(abs(ng - ok) > 1):
        mid = (ok + ng) // 2
        if lists[mid] > border:
            ok = mid
        else:
            ng = mid
    return lists[ok]

N = input()
S = input()
ans = 0
k = 0
k2 = 0
k3 = 0
find = [[]for _ in range(10)]
for i in range(len(S)):
    find[int(S[i])].append(i)
for i in range(10):
    for i2 in range(10):
        for i3 in range(10):
            k = Meg_nib(0,-1,find[i])
            if k == -1:
                break
            k2 = Meg_nib(0,k,find[i2])
            if k2 == -1:
                break
            k3 = Meg_nib(0,k2,find[i3])
            if k3 != -1:
                ans += 1
print(ans)

Measured memory_bytes: 40560
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int height(int H, int X, int Y, int Cx, int Cy) {
    return max(H - abs(X - Cx) - abs(Y - Cy), 0);
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int x[100], y[100], h[100];
    rep(i, N) cin >> x[i] >> y[i] >> h[i];

    int hmax = 0;
    rep(i, N) hmax= max(hmax, h[i]);
    REP(Cx, 0, 100) {
        REP(Cy, 0, 100) {
            REP(H, hmax, hmax + 200) {
                bool flag = true;
                rep(i, N) {
                    if (height(H, x[i], y[i], Cx, Cy) != h[i]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << Cx << " " << Cy << " " << H << endl;
                    return 0;
                }
            }
        }
    }

    return 0;
}


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

#define ll long long int
#define endl '\n'
#define mod 1000000007
#define inf 1e18

void testCase()
{
     
   // ll t; cin>>t; while(t--)
    
    {
        ll n,d;
        cin>>n>>d;
        ll cnt=0;
        while(n--)
        {
            double x,y;
            cin>>x>>y;
            ll temp=ceil(sqrt(x*x+y*y));
            if(temp<=d)
            cnt++;
        }
        cout<<cnt;
    }
    
        
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    testCase();
    return 0;
}

Measured memory_bytes: 3832
import sys
readline = sys.stdin.readline

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def main():
    N = int(readline())
    fct = factorize(N)
    res = 0
    for a, b in fct:
        p = 1
        while b - p >= 0:
            b -= p
            res += 1
            p += 1

    print(res)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  ll N, A, B; cin >> N >> A >> B;
  if((B-A)%2==0) cout << (B-A)/2 << endl;
  else{
    ll ans1=0, ans2=0;
    ll A_=A, B_ = B;
    B_ -= (A_-1);
    ans1 += A_-1;
    A_ = 1;
    ans1++;
    B_--;
    ans1 += (B_-A_)/2;
    ll A__ = A;
    ll B__ = B;
    A__ += (N-B__);
    ans2 += (N-B__);
    B__ = N;
    ans2++;
    A__++;
    ans2 += (B__-A__)/2;
    cout << min(ans1, ans2) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define FOR(n) for (int i = 0; i < int(n); i++)
#define FOR1(m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[])
{
  int A, B;

  scanf("%d %d", &A, &B);
  printf("%d\n", A*B-A-B+1);
  
  return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <string>
#include <vector>
#include <ios>
#include <iomanip>
#include <stack>
#include <queue>
#include <algorithm>

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

using namespace std;

const int INF = 100000000;

int main(){
  vector<int> e = vector<int>(3);
  REP(i,3){
    cin >> e[i];
  }

  sort(e.begin(),e.end());

  cout << e[0] * e[1] /2 << endl;
  return 0;
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  vector<bool> dp(k+1,false);
  for(int i=1;i<=k;i++){
    for(int j=0;j<n;j++){
      if(i-a[j]>=0){
        if(!dp[i-a[j]]){
          dp[i]=true;
          break;
        }
      }
    }
  }
  if(dp[k]) cout<< "First" << endl;
  else cout << "Second" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>          // printf(), scanf()

int
main(int argc, char** argv)
{
	int room[4][3][10];
	int b, f, r, v;
	int n;
	int i;

	for (b = 0; b < 4; ++b)
	{
		for (f = 0; f < 3; ++f)
		{
			for (r = 0; r < 10; ++r)
				room[b][f][r] = 0;
		}
	}

	scanf("%d\n", &n);
	for (i = 0; i < n; ++i)
	{
		scanf("%d %d %d %d\n", &b, &f, &r, &v);
		room[b - 1][f - 1][r - 1] += v;
	}

	for (b = 0; b < 4; ++b)
	{
		for (f = 0; f < 3; ++f)
		{
			for (r = 0; r < 10; ++r)
				printf(" %d", room[b][f][r]);

			printf("\n");
		}

		if (b != 3)
			printf("####################\n");
	}

	return 0;
}

Measured memory_bytes: 616
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long n,x,a[105];
	cin>>n>>x;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	int k=0;
	while(x>=a[k]){
		x=x-a[k];
		k++;
		if(k==n){
			if(x==0) break;
			else {k--;break;}
		}
	}
	cout<<k<<endl;
	return 0;
} 

Measured memory_bytes: 384
#ifdef __APPLE__
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <cmath>
#include <ctgmath>
#include <math.h>
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define io ios_base::sync_with_stdio(false), cin.tie(NULL)
#define GFOR(i,a,n) for (i=a;i<n;i++)
#define FOR(i,a,n) for (int i=a;i<n;i++)
#define RFOR(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define tc(t) for (int tc=1; tc<=t; tc++)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<long long int> VLL;
typedef vector<pair<int, int> > VPI;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll, ll> PLL;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll modInverse (ll a) {ll p = mod - 2; return powmod(a, p);}
// head

int main() {
    int n;
    scanf("%d", &n);
    int a[n], max = 0;
    unordered_map<int, int> data;

    FOR (i, 0, n) {
        scanf("%d", a + i);
        max = std::max(max, a[i]);
        data[a[i]]++;
    }

    if (data[1] > 1) {
        cout << 0 << "\n";
        return 0;
    } else if (data[1] == 1) {
        cout << 1 << "\n";
        return 0;
    }

    vector<VI> divisors(max + 1);
    FOR (i, 2, max + 1) {
        for (int j = 2*i; j < max + 1; j+=i) {
            divisors[j].pb(i);
        }
    }

    int ans = 0;
    FOR (i, 0, n) {
        if (data[a[i]] > 1)
            continue;

        for (auto d : divisors[a[i]]) {
            if (data.find(d) != data.end()) {
                goto bad;
            }
        }
        ans++;
        bad: ;
    }


    cout << ans << "\n";
}
//check for edge cases in limits
//printing double may print 1.223232e9 like values, beware of that


Measured memory_bytes: 120892