akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int h, n; cin >> h >> n;
    VI a(n), b(n);
    FOR(i, 0, n)cin >> a[i] >> b[i];

    VL dp(h + 1, LLINF);
    dp[0] = 0;
    FOR(i, 0, h)FOR(j, 0, n) {
        chmin(dp[min(i + a[j], h)], dp[i] + b[j]);
    }

    cout << dp[h] << "\n";
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define pb push_back
#define tam 5120
#define offset 320000
#define se second
#define fi first
#define pitem item*
#define forr(i,p,n) for(ll i=p;i<n;i++)
using namespace std;
typedef long long ll;
const ll MOD=1000000009 ;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
typedef pair<ll,ll> ii;

ll dp[100][100];
ll val[100];
const ll EPS=1e-15;
ll go(ll num)
{
    ll c=0;
    while(num>0)
        c++,num/=10;
    return c;
}
int main()
{
    memset(dp,0,sizeof dp);
    ll n;
    cin>>n;
    ll maxx=1e8;
    for(ll i=1;i*i<=n;i++)
    {
        if (n%i==0)
        {
            maxx=min(maxx,max(go(n/i),go(i)));
        }
    }
    cout<<maxx<<endl;
}

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

int main(){
  string a;
  cin >> a;
  if(a.at(5)>'0')cout << "TBD";
  else if(a.at(6)>'4')cout << "TBD";
  else cout << "Heisei";
}

Measured memory_bytes: 3552
N, K = map(int, input().split())
K += 1
A = [int(i) for i in input().split()]
s = []
i = 0
length = 0

while True:
    if not A[i]:
        start = i + 1
        break
    s.append(i + 1)
    dest = A[i]
    A[i] = None
    i = dest - 1
    length += 1

if K == 2:
    print(s[1])
elif start == s[0]:
    amari = K % length
    if amari == 0:
        print(s[-1])
    else:
        print(s[amari - 1])
else:
    idx = s.index(start)
    s2 = s[idx:]
    length2 = len(s2)
    tmp = length - length2
    if K < tmp:
        print(s[K-1])
    else:
        K -= tmp
        amari = K % length2

        if amari == 0:
            print(s2[-1])
        else:
            print(s2[amari - 1])

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

// Begin {{{
using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0; i < (n); ++i)
#define reps(i, s, n) for (i64 i = (s); i <= (n); ++i)
#define VAR(Type, ...) Type __VA_ARGS__; IN(__VA_ARGS__)
#define Float(x) OUTN(fixed, setprecision(x));

using i64 = int_fast64_t;
using pii = pair<i64, i64>;

template <class A, class B>
inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }

template <class A, class B>
inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

// IN
void IN() {}
template <class Head, class... Tail>
void IN(Head&& head, Tail&&... tail) {
  cin >> head;
  IN(forward<Tail>(tail)...);
}

// OUTS
void OUTS() {}
template <class Head, class... Tail>
void OUTS(Head&& head, Tail&&... tail) {
  cout << head << " \n"[sizeof...(tail)==0];
  OUTS(forward<Tail>(tail)...);
}

template <class T>
void OUTS(vector<T> &vec) {
  for (auto &e : vec) cout << e << " \n"[&e==&vec.back()];
}

template <class T>
void OUTS(vector<vector<T>> &df) {
  for (auto &vec : df) OUTS(vec);
}

// OUTL
void OUTL() {}
template <class Head, class... Tail>
void OUTL(Head&& head, Tail&&... tail) {
  cout << head << "\n";
  OUTL(forward<Tail>(tail)...);
}

template <class T>
void OUTL(vector<T> &vec) {
  for (auto &e : vec) cout << e << "\n";
}

// OUTN
void OUTN() {}
template <class Head, class... Tail>
void OUTN(Head&& head, Tail&&... tail) {
  cout << head;
  OUTN(forward<Tail>(tail)...);
}
// }}} End

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  VAR(string, s);
  i64 res = 0;
  for (auto e : s) {
    if (e == '+') res++;
    else res--;
  }
  OUTL(res);
  return 0;
}


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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7

ll _slice(string s, ll way) {
	ll wait = 0;
	ll res = 0;
	for (auto c : s) {
		wait *= 10;
		wait += c - '0';
		if (way & 1) {
			res += wait;
			wait = 0;
		}
		way >>= 1;
	}
	return res + wait;
}

int main()
{
	ll res = 0;
	string s;
	cin >> s;

	REP(i, 1 << ((int)s.size() - 1))res += _slice(s, i);
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e16;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N,M;
    cin >> N >> M;
    vl A(N);
    rep(i, N) cin >> A[i];
    sort(all(A));

    vc<pair<ll, ll>> B(M);
    rep(i, M) cin >> B[i].second >> B[i].first;
    sort(all(B), greater<pair<ll, ll>>());

    ll ans = accumulate(all(A), 0ll);
    ll ai = 0, bi = 0, rest = B[0].second;
    bool end = false;
    while(ai<N){
        while(ai<N&&rest>0){
            if (A[ai] >= B[bi].first){
                end=true;
                break;
            }
            ans += B[bi].first - A[ai];
            rest--;
            ai++;
        }
        if (end||ai==N) break;
        if (rest == 0) bi++, rest = B[bi].second;
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
const int inf = 1e9; //1(1倍)e(指数)9(10^9)
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> w(n);
	rep(i, n) scanf("%d", &w[i]);
	int ans = inf;
	for(int t = 1; t <= n; t++){
		int l = 0, r = 0;
		rep(i, n) {
			if (i <= t)	l += w[i];
			else r += w[i];
		}
		ans = min(ans, abs(l - r));
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3760
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	char A, B;
	cin >> A >> B;
	if (A == B)
	{
		cout << "H" << endl;
	}
	else
	{
		cout << "D" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (in i = 0ll; i < (in)(n); i++)
const double PI=3.14159265358979323846;
const int64_t waru = 1000000007;
const in INF=1<<30;
using vec = vector<vector<int>>;

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

    return gcd(b, a % b);
}

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

in vlcm(in n,vector<in> a,in m){
  in ret=1ll;
   for(in i=0ll;i<n;i++){
      ret =lcm(ret,a[i]);
     if(ret>m){cout<<0;return -1;}
   }
  return ret;
}

int main(){
  in n,m;
  cin>>n>>m;
  vector<in> a(n);
  rep(i,n) cin>>a[i];
  
  in flag=0ll;
  in flag2=0ll;
  in cnt2=0ll;
  
  while(flag==0ll){
    if(a[0]%2!=0ll) flag=1ll;
    else{ flag=0ll; cnt2 ++;}
    
     rep(i,n){
        if(a[i]%2ll!=0) flag2=1ll;
         else flag2=0ll;
       if(flag != flag2){flag=2ll;break;}
       if(flag==0ll) a[i] /=2ll;
     }
  }
  if(flag==2ll){cout<<0;return 0;}
  //rep(i,n) cout<<a[i];
  
  in x= vlcm(n,a,m);
  if(x==-1ll) return 0;
  in ans =0;
  //cout<<cnt2;
  for(in i=1ll;i*(1<<cnt2-1ll)*x<=m;i+=2ll){
     ans ++;
  }
  cout<<ans;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll a,v,b,w,t;cin>>a>>v>>b>>w>>t;
    bool f=0;
    if(a==b){
        f=1;
    }else if(a<b){
        if(a+v*t>=b+w*t)f=1;
    }else{
        if(b-w*t>=a-v*t)f=1;
    }
    cout<<(f?"YES":"NO")<<endl;
}

Measured memory_bytes: 3624
N = gets.to_i
ts, xs, ys = [0], [0], [0]
N.times do |i|
    ts[i+1], xs[i+1], ys[i+1] = gets.split.map(&:to_i)
end

N.times do |i|
    td = ts[i+1] - ts[i]
    dd = (xs[i+1] - xs[i]).abs + (ys[i+1] - ys[i]).abs
    unless td >= dd && (td - dd) % 2 == 0
        puts 'No'
        exit
    end
end

puts 'Yes'

Measured memory_bytes: 4200
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

const int MAX = 1000;

struct int2
{
	int x;
	int y;
};

class Node
{
public:
	int id;
	double cost;
	int parent;
	bool visited;
	vector<int> edge_to;
	vector<double> edge_cost;

	Node() {}
	Node(int id) : id(id), cost(-1.0), parent(-1), visited(false) {}
	
	bool operator < (const Node& n) const
	{
		return cost > n.cost;
	}
};

int n, m;
Node nodes[MAX];
int2 pos[MAX];
int sid, gid;

void solve()
{
	priority_queue<Node> q;
	nodes[sid].cost = 0.0;
	q.push(nodes[sid]);
	
	while(!q.empty())
	{
		Node nn = q.top();
		q.pop();
		
		if(nn.visited) continue;
		if(nn.id==gid) return;
		nn.visited = true;
		for(int i=0; i<nn.edge_to.size(); i++)
		{
			int to = nn.edge_to[i];
			double cost = nn.cost + nn.edge_cost[i];
			if(nodes[to].cost > cost || nodes[to].cost < 0.0)
			{
				if(nodes[to].visited) continue;
				nodes[to].cost = cost;
				nodes[to].parent = nn.id;
				q.push(nodes[to]);
			}
		}
	}
}

void reset()
{
	for(int i=0; i<n; i++)
	{
		nodes[i].cost = -1;
		nodes[i].parent = -1;
		nodes[i].visited = false;
	}
}

int main(int argc, char** argv)
{
	int b, x, y;
	while(cin >> n, n)
	{
		for(int i=0; i<n; i++)
		{
			cin >> b >> x >> y;
			int2 tmp = {x, y};
			pos[b-1] = tmp;
			nodes[i] = Node(i);
		}
		
		for(int i=1; i<n; i++)
		{
			for(int j=0; j<i; j++)
			{
				int dx = pos[i].x - pos[j].x;
				int dy = pos[i].y - pos[j].y;
				double dist =  sqrt((double)(dx*dx + dy*dy));
				if(dist <= 50.0)
				{
					nodes[i].edge_to.push_back(j);
					nodes[i].edge_cost.push_back(dist);
					nodes[j].edge_to.push_back(i);
					nodes[j].edge_cost.push_back(dist);
				}
			}
		}
		
		cin >> m;
		
		for(int k=0; k<m; k++)
		{
			if(k) reset();
			cin >> sid >> gid;
			sid = sid - 1;
			gid = gid - 1;
			
			solve();
		
			vector<int> way;
			way.push_back(gid);
			Node nn =nodes[gid];
			while(nn.parent != -1)
			{
				way.push_back(nn.parent);
				nn = nodes[nn.parent];
			}
		
			if(way.size() > 1)
			{
				for(int i=0; i<way.size(); i++)
				{
					if(i!=0) cout <<" ";
					cout << way[way.size() - i -1] + 1;
				}
			}
			else
			{
				cout << "NA";
			}
			cout << endl;
		}
	}
}

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

int main(){

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

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  string s;
  cin>>s;
  int ans1=0,ans2=0;
  for(int i=0;i<s.size();i++){
    if(i%2&&s[i]=='0')ans1++;
    if(i%2==0&&s[i]=='1')ans1++;
    if(i%2&&s[i]=='1')ans2++;
    if(i%2==0&&s[i]=='0')ans2++;
  }
  cout<<min(ans1,ans2)<<endl;
  return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<math.h>
#include <string.h>



int main() {
	int i, j, k, l;
	int m, g, n;
	int f = 0;
	int a, b;
	int h[110000];
	int now = 0, max = 0;

	scanf("%d", &n);

	for (i = 0;i < n;i++) {

		scanf("%d", &h[i]);
	}

	for (i = 0;i < n - 1;i++) {
		if (h[i] < h[i + 1]) {
			if (now > max) {
				max = now;
			}
			now = 0;
		}
		if (h[i] >= h[i + 1]) {
			now++;
		}
	}
	if (now > max) {
		max = now;
	}
	f = max;


	printf("%d", f);

	return 0;
}

Measured memory_bytes: 512
n, m = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
left = [lr[i][0] for i in range(m)]
right = [lr[i][1] for i in range(m)]
ans = min(right) - max(left)
print(ans+1 if ans >= 0 else 0)

Measured memory_bytes: 29032
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;
vector<vector<int>> G1(100000),G2(100000);
vector<bool> visit1(100000, false), visit2(100000, false);
int timer = 0;

//?????????????????????DFS?????????????????????????????????????????????????????????
void dfs1(int u,vector<int>& prenum) {
	visit1[u] = true;
	for (int v : G1[u]) {
		if (visit1[v] == false) {
			dfs1(v, prenum);
		}
	}
	prenum[timer++] = u;
}

//?????????????????????????????????????????°????????????DFS
//????§???????????????§??????????????????????????????????????????????????????
//????????§????????¢???????????¶????????£?????????????????§?????°????????????CSS????????£????????????
//??????????´?????????£??????????????????????¨????????????????????????§???????????????????????????????????????
//?????????DFS?????????
//??????????????°?????????CSS????§£?????°???????????§???????????????

//O(V+E)
void dfs2(int u,vector<int>& Ans) {
	visit2[u] = true;
	Ans[u] = timer;
	for (int v : G2[u]) {
		if (visit2[v] == false) {
			dfs2(v, Ans);
		}
	}
}

int main() {
	cin.tie(0);ios::sync_with_stdio(false);
	int V, E; cin >> V >> E;
	vector<int> Ans(V);
	vector<int> prenum(V);
	for (int i = 0; i < E;i++) {
		int s, t; cin >> s >> t;
		G1[s].emplace_back(t);
		G2[t].emplace_back(s);
	}

	for (int i = 0; i < V; i++) {
		if (visit1[i] == false) {
			dfs1(i, prenum);
		}
	}
	timer = 0;
	for (int i = V - 1; i >= 0;i--) {
		if (visit2[prenum[i]] == false) {
			dfs2(prenum[i], Ans);
			timer++;
		}
	}

	int Q; cin >> Q;
	for (int i = 0; i < Q;i++) {
		int u, v; cin >> u >> v;
		if (Ans[u] == Ans[v]) { cout << 1 << endl; }
		else { cout << 0 << endl; }
	}

/*
	cout << "prenum" << endl;
	for (int i = 0; i < V; i++) {
		cout << i << " " << prenum[i] << endl;
	}
	cout << "Ans" << endl;
	for (int i = 0; i < V;i++) {
		cout << i << " " << Ans[i] << endl;
	}
*/
}

Measured memory_bytes: 8652
#include<iostream>
//なんだかbit演算せずにいけそうな雰囲気が...
#include<algorithm>
#include<string>
using namespace std;

int main(){
	string n;
	cin >> n;
	int sub_ans;
	int len = (int)n.size();
	int ans = len;
	for (int i=0;i<len-1;i++) {
	if (n[i]!=n[i+1]) {
	sub_ans = max(i+1, len-i-1);
	ans = min(ans, sub_ans);
	}
		}

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



Measured memory_bytes: 512
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]
class StarrySkyTree:
    # Range Minimum Query
    def __init__(self, N):
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.INF = 2**31 - 1
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1

        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小値を求める
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


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

    enemy = []
    for i in range(N):
        x,h = list(map(int,input().split()))
        if h%A==0:
            enemy.append([x,h//A])
        else:
            enemy.append([x,h//A+1])

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l
    ST = StarrySkyTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i,i+1)
        if v>0:
            count += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()



Measured memory_bytes: 100572
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define RFOR(i, begin, end) for(int i=(end)-1, i##_begin_=(begin);i>=i##_begin_;i--)
#define rep(i, N) FOR(i, 0, N)
#define rrep(i, N) RFOR(i, 0, N)
#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 mp make_pair
using namespace std;
using ll = long long int;
using V = vector<ll>;
using P = pair<ll, ll>;
using VP = vector<P>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
constexpr int inf = 1e9;
constexpr ll  lnf = 1LL << 60;
constexpr int mod = 1e9+7;
template<class T> inline bool chmax(T& a, const T& b) { if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if(a>b) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b? gcd(b, a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}


int main() {
    ll n, k;
    cin >> n >> k;
    V h(n);
    rep(i, n) cin >> h[i];

    ll ret = 0;
    rep(i, n) {
        if(h[i] >= k) ret++;
    }
    cout << ret << endl;
    return 0;
}


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

using namespace std;

#define ll long long int
#define get(a) ll a; cin >> a;
#define show(a) cout << a << endl;
#define full(p) p.begin(), p.end()
#define sz(a) (ll)(a.size())
#define pb push_back


bool not_month(int a)
{
	if(a > 12 or a == 0)
		return true;
	return false;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout<<fixed;
	////////////////////////////////
	get(s);

	int a = s/100;
	int b = s%100;

	if(not_month(a) and not_month(b))
		cout << "NA" << endl;
	else if(not_month(a) and !not_month(b))
		cout << "YYMM" << endl;
	else if(!not_month(a) and not_month(b))
		cout << "MMYY" << endl;
	else if(!not_month(a) and !not_month(b))
		cout << "AMBIGUOUS" << endl;
	return 0;
}

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

long long mincost(long long ar[],long long n)
{
    long long cost[n];

    cost[n-1]=0;
    cost[n-2]=abs(ar[n-2]-ar[n-1]);

    for(long long i=n-3; i>=0; i--){
        long long a=cost[i+1]+abs(ar[i]-ar[i+1]);
        long long b=cost[i+2]+abs(ar[i]-ar[i+2]);
        cost[i] = min(a,b);
    }

    return cost[0];
}

int main()
{
    long long n;
    cin>>n;
    long long ar[n];
    for(long long i=0;i<n;i++){
        cin>>ar[i];
    }
    cout << mincost(ar,n);
}



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

int main(){
    string s;
    int arr[28];
    getline(cin,s);
    for(int i=0;i<26;i++) {arr[i]=0;}
    for(int i=0;s[i];i++){
        int x=s[i]-97;
        arr[x]++;
    }
     for(int i=0;i<26;i++){
        if(arr[i]%2!=0){
            cout<<"No\n";
            return 0;
        }
     }
     cout<<"Yes\n";
     return 0;
}


Measured memory_bytes: 256
n=int(input())
A=list(map(int,input().split()))
L=[0]*(n+1)
R=[0]*(n+1)
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
for i in range(n):
    L[i+1]=gcd(L[i],A[i])
for i in range(n,0,-1):
    R[i-1]=gcd(R[i],A[i-1])
ans=[]
for k in range(n):
    ans.append(gcd(L[k],R[k+1]))
print(max(ans))


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

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    int ans = 0;
    int kotae = 0;
    for (int i=1; i<=n; i++){
        cin >> h[i];
        if(h[i] <= h[i-1]) ans++;
        else ans =0;
        kotae = max(ans,kotae);
    }
    cout << kotae << endl;
    return 0;
}


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

#define int         long long int
#define all(a)      (a).begin(),(a).end()
#define f           first
#define s           second
#define endl        '\n'
#define MOD         1000000007

void solve()
{
    int n ;
    cin >> n ; 
    map<string, int> mp ;
    int mx = 0 ;
    for(int i = 0 ; i < n ; i++)
    {
        string tmp ;
        cin >> tmp ;
        mp[tmp]++ ;
    }
    for(auto i : mp)
    {
        mx = max(i.s, mx) ;
    }
    vector<string> ans ;
    for(auto i : mp)
    {
        if(i.s == mx)
            ans.push_back(i.f) ;
    }
    for(auto i : ans)
        cout << i << endl ;
    
}

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

    int t = 1 ;
    //cin >> t ;
    while(t--)
    {
        solve() ;
    }
    return 0 ;
}

Measured memory_bytes: 25584
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int n;
string field[256];

int vertical(int y, int x){
  int cnt = 0;
  while(1){
    if(y >= n || field[y][x] == '0') break;
    y++;
    cnt++;
  }
  return cnt;
}

int horizonal(int y, int x){
  int cnt = 0;
  while(1){
    if(x >= n || field[y][x] == '0') break;
    x++;
    cnt++;
  }
  return cnt;
}

int diagonal_left(int y, int x){
  int cnt = 0;
  while(1){
    if(x < 0 || y >= n || field[y][x] == '0') break;
    x--, y++;
    cnt++;
  }
  return cnt;
}

int diagonal_right(int y, int x){
  int cnt = 0;
  while(1){
    if(x >= n || y >= n || field[y][x] == '0') break;
    x++, y++;
    cnt++;
  }
  return cnt;
}

int main(){
  while(cin >> n, n){
    for(int i = 0 ; i < n ; i++){
      cin >> field[i];
    }
    
    int ans = 0;
    
    for(int i = 0 ; i < n ; i++){
      for(int j = 0 ; j < n ; j++){
	if(field[i][j] == '1'){
	  ans = max(ans, vertical(i, j));
	  ans = max(ans, horizonal(i, j));
	  ans = max(ans, diagonal_left(i, j));
	  ans = max(ans, diagonal_right(i, j));
	} 
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 996
import java.util.Scanner;
import java.util.LinkedList;

public class Main {
	Scanner sc = new Scanner(System.in);
	int n;
	int len = 55556;
	int[] sosuu = new int[len];
	
	public void run(){
		n = sc.nextInt();
		solve();
	}
	public void solve(){
		
		for(int i = 2; i < len; i++){
			sosuu[i] = 1;
		}
		
		for(int i = 2; i < len; i++){
			if(sosuu[i] == 1){
				int j = i + i;
				while(j < len){
					sosuu[j] = 0;
					j = j + i;
				}
			}
		}
		for(int i = 2; i< len; i++){
			if(i % 5 != 1){
				sosuu[i] = 0;
			}
		}
		
		int num = 0;
		for(int i = 2; i < len; i++){
			if(sosuu[i] == 1){
				System.out.print(i);
				num = num + 1;
				if(num == n){
					break;
				}
				else{
					System.out.print(" ");
				}
			}
		}
	}
	
	
	public static void main(String[] args){
		new Main().run();
	}
	
	static class Pair {
        int first,second;
        public Pair(int a,int b) {
            this.first = a;
            this.second = b;
        }
    }	
}

Measured memory_bytes: 21972
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%9
        t//=9
    j=N-i
    while j>0:
        cnt+=j%6
        j//=6
    ans = min(ans,cnt)
print(ans)

Measured memory_bytes: 8928
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int A[5];
    cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];

    int aa[5];
    for (int i = 0; i < 5; i++)
    {
        aa[i] = A[i] % 10;
    }
    int min = 0;
    for (int i = 1; i < 10; i++)
    {
        if (aa[0] == i || aa[1] == i || aa[2] == i || aa[3] == i || aa[4] == i)
        {
            min = i;
            break;
        }
    }
    //cout<<min<<endl;
    int sum = 0;
    if (min == 0)
    {
        for (int i = 0; i < 5; i++)
        {
            sum += A[i];
        }
        cout << sum << endl;
        return 0;
    }
    for (int i = 0; i < 5; i++)
    {
        sum += A[i];
        if(aa[i]!=0)
        {
            sum += (10 - aa[i]);
        }
    }

    cout << sum - 10 + min << endl;
}

Measured memory_bytes: 256
#pragma GCC optimze("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll inf=1e18, N=3005;
inline ll mult(ll x,ll y){x%=hell;y%=hell;return (1LL*x*y)%hell;}
inline ll add(ll x,ll y){x+=y;return x%hell;}
inline ll powMod(ll base,ll expo){
	if(base==0)return 0;
	ll ans=1;
	while(expo){
		if(expo&1)ans=mult(ans,base);
		base=mult(base,base); 
		expo>>=1;
	}
	return ans;
}
void solve(){
	ll n, k, upto;
	cin>>n>>k;
	vector<ll> dp(k+1);
	dp[0]=1;
	rep(i,0,n){
		cin>>upto;
		vector<ll> tmp(k+1,0);
		rep(used,0,k+1){
			ll L=used+1,R=used+min(upto,k-used);
			if(L<=k)tmp[L]=add(tmp[L],dp[used]);
			if(R+1<=k)tmp[R+1]=add(tmp[R+1],hell-dp[used]);
		}
		ll prefix_sum=0;
		rep(i,0,k+1){
			prefix_sum=add(prefix_sum,tmp[i]);
			dp[i]=add(dp[i],prefix_sum);
		}
	}
	cout<<dp[k];
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 1792
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	h := iSScan(n)
	ans := make([]int, n)
	for i := 1; i < n; i++ {
		if h[i-1] >= h[i] {
			ans[i] = ans[i-1] + 1
		} else {
			ans[i] = 0
		}
	}
	fmt.Println(max(ans))
}


Measured memory_bytes: 5004
#include<iostream>
#include<algorithm>

using namespace std;

#define NMAX 18
#define INF 1000000

int main(){

	int N;
	int ti;
	int t[NMAX][NMAX+1];
	int dp[1<<NMAX];
	int mn;
	bool f;

	while(1){

		cin>>N;
		if(N==0) break;

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

		for(int i=0;i<(1<<N);i++) dp[i]=INF;
		dp[0]=0;
		f=true;

		while(f){
			f=false;
			for(int i=(1<<N)-1;i>=0;i--){
				if(dp[i]!=INF){
					for(int j=0;j<N;j++){
						if((i>>(j)&1)==0){
							mn=t[j][0];
							for(int k=1;k<N+1;k++){
								//cout<<i<<","<<j<<","<<k<<","<<mn<<","<<dp[i]<<endl;
								if((i>>(k-1)&1)==1) mn=min(mn,t[j][k]);
							}
							if(dp[i+(1<<j)]>dp[i]+mn){
								dp[i+(1<<j)]=dp[i]+mn;
								f=true;
							}
						}
					}
				}
			}
		}
		cout<<dp[(1<<N)-1]<<endl;
	}
}

Measured memory_bytes: 1420
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include <fstream>
#include <complex>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i <(b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a,value, sizeof(a))

#define ALL(a) a.begin(),a.end()
#define SZ(a) (int)a.size()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<LL> VI;
typedef pair<int, LL> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX = 1000 * 500  + 7;


struct RMQ
{
    int T[MAX << 2];
    
    void upd(int v, int tl, int tr, int p, int x)
    {
        if (tl == tr)
        {
            T[v] = x;
            return ;
        }
        int tm = (tl + tr)/2;
        if(p <= tm)upd(v + v, tl, tm, p, x);
        else upd(v + v + 1, tm+1, tr, p, x);
        T[v] = max(T[v+v], T[v+v+1]);
    }
    
    int get(int v, int tl, int tr, int l, int r)
    {
        if (r < l)return -INF;
        if (l == tl && r == tr)return T[v];
        int tm = tl + tr >> 1;
        return max(get(v + v, tl, tm, l, min(r, tm)),
                   get(v + v + 1, tm + 1, tr, max(tm+1, l), r));
        
    }
} T;

int P[MAX], Q[MAX], R[MAX], C[MAX];
int k, n;
set<int> S;


void updBlock(int block)
{
    if (C[block] != -1)
    {
        S.erase(-C[block]);
        C[block] = -1;
    }
    int L = block * k;
    int R = min(L + k - 1, n-1);
    int x = T.get(1, 0, n-1, L, R);
   // cout << "-" << x << endl;
    if (x == -INF)return ;
    if (T.get(1, 0,n-1, max(0, Q[x] - k + 1), min(n-1, Q[x] + k + -1)) == x)
        S.insert(-Q[x]), C[block] = Q[x];
}


int main()
{
    //freopen("input.txt", "r", stdin);
    //ios::sync_with_stdio(false);cin.tie(NULL);
    
    scanf("%d %d", &n, &k);
    FOR(i, 0, n)
    {
        scanf("%d", P + i);
        P[i]--;
        Q[P[i]] = i;
        T.upd(1, 0, n-1, i, P[i]);
    }
    
    int cnt = (n + k - 1) / k;
    
    FILL(C, -1);
    
    FOR(i, 0, cnt)
        updBlock(i);
    
   // cout << "*" << endl;
    
    RFOR(i, n, 0)
    {
     //   cout << i << " " << SZ(S) << endl;
        int x = -*S.begin();
        S.erase(S.begin());
        R[x] = i;
        T.upd(1, 0, n-1, x, -INF);
        updBlock(x / k);
        if (x / k - 1 >= 0)updBlock(x / k - 1);
        if (x / k + 1 < cnt)updBlock(x / k + 1);
    }
    
    FOR(i, 0, n)
        printf("%d ", R[i]+1);
    return 0;
}


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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)
#define In(vec) rep(i, n) cin>>vec[i];
#define ANS(s) cout << s << endl

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

typedef long long ll;
typedef vector<int> inv;

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; }

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
int round_int(int a, int b) { return (a + (b - 1)) / b; }


// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

constexpr auto MAX = 100010;

// ────────────────────────────────────────────────────

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

	if (n / 10 == 9 || n % 10 == 9)
	{
		ANS("Yes");
	}
	else
	{
		ANS("No");
	}
}


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

ll const INF = 1LL<<60;

int main(){
	int n,k;
	cin >> n >> k;
	vector<ll> h(n);
	rep(i,n){
		cin >> h[i];
	}
	sort(h.begin(),h.end());
	ll ans = INF;
	rep(i,n-k+1){
		ans = min(ans, h[i+k-1] - h[i]);
	}
	cout << ans << endl;
    return 0;
}



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

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/
#define scd(t) scanf("%d",&t)
#define scld(t) scanf("%ld",&t)
#define sclld(t) scanf("%lld",&t)
#define scc(t) scanf("%c",&t)
#define scs(t) scanf("%s",t)
#define scf(t) scanf("%f",&t)
#define sclf(t) scanf("%lf",&t)
#define mem(a, b) memset(a, (b), sizeof(a))
#define fr(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define gf(i,n) for (int i=0 ; i<n ; i+=1)
#define rfor(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define rep(i, j) FOR(i, 0, j, 1)
#define rrep(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define mp make_pair
#define pb push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define prarr(a,n) gf(i,n){printf("%d ", a[i]);}printf("\n");
#define sumarr(a,n) int zserkd=0;gf(i,n){zserkd+=a[i];}cout<<zserkd<<endl;
const double pi=acos(-1.0);
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<int,int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;

/****** Template of some basic operations *****/
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

int main(){
	
	int n,m;
	cin>>n>>m;
	int h[n];
	gf(i,n)
	{
		cin>>h[i];
	}
	int dead[n+1]={0};
	gf(i,m)
	{
		int o1,o2;
		cin>>o1>>o2;
		if(h[o2-1]>=h[o1-1]&&dead[o1]==0)
			dead[o1]=1;
		if(h[o1-1]>=h[o2-1]&&dead[o2]==0)
			dead[o2]=1;
	}
	int tot=0;
	gf(i,n+1)
	{
		// cout<<dead[is]<<" ";
		if(dead[i]==0&&i!=0)tot++;

	}
	cout<<tot;
	return 0;
}


Measured memory_bytes: 4380
import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
h = [int(x) for x in input().split()]
h = np.array(h)
dp = np.zeros(N, dtype=int)
for i in range(1, N):
  j = max(0, i-K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(dp[N-1])

Measured memory_bytes: 23052
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#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 INF = pow(2,29);
const int MOD = 1000000007;

const int N_MAX = pow(10,6)+1;
vector<bool> isp(N_MAX, true);

void sieve() {
  isp[0] = false;
  isp[1] = false;
  for (int i=2; pow(i,2)<=N_MAX; i++) {
    if (isp[i]) for(int j=2; i*j<=N_MAX; j++) isp[i*j] = false;
  }
}

int main() {
  ll N, P; cin >> N >> P;

  ll result = 1;
  if (N==1) result = P;
  else {
    sieve();
    ll i=2;
    while (i*i<=P) {
      ll count = 0;
      while (P%i==0) {
        P /= i;
        count++;
      }
      result *= pow(i, count/N);
      i++;
    }
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 384
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yay!")
    else:print(":(")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
#n = ip()                                     #入力整数1つ
#n,q= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
b = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(5)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
a = []
for i in range(4):
    a.append(int(b[i]))
if a[0] + a[1] + a[2] + a[3] == 7: c = [b[0],'+',b[1],'+',b[2],'+',b[3],'=7']
if a[0] + a[1] + a[2] - a[3] == 7: c = [b[0],'+',b[1],'+',b[2],'-',b[3],'=7']
if a[0] + a[1] - a[2] + a[3] == 7: c = [b[0],'+',b[1],'-',b[2],'+',b[3],'=7']
if a[0] + a[1] - a[2] - a[3] == 7: c = [b[0],'+',b[1],'-',b[2],'-',b[3],'=7']
if a[0] - a[1] + a[2] + a[3] == 7: c = [b[0],'-',b[1],'+',b[2],'+',b[3],'=7']
if a[0] - a[1] + a[2] - a[3] == 7: c = [b[0],'-',b[1],'+',b[2],'-',b[3],'=7']
if a[0] - a[1] - a[2] + a[3] == 7: c = [b[0],'-',b[1],'-',b[2],'+',b[3],'=7']
if a[0] - a[1] - a[2] - a[3] == 7: c = [b[0],'-',b[1],'-',b[2],'-',b[3],'=7']
print(''.join(c))

Measured memory_bytes: 22284
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A.sort()
BC.sort(key = lambda x:(-x[1]))

i_a = 0
i_bc = 0
while i_a < N:
    if i_bc == M:
        break
    for j in range(BC[i_bc][0]):
        if i_a + j >= N:
            i_a = N
            continue
        if A[i_a + j] >= BC[i_bc][1]:
            i_a = N
        else:
            A[i_a + j] = BC[i_bc][1]
    i_a += BC[i_bc][0]
    i_bc += 1

print(sum(A))


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

using namespace std;


typedef long long int64;

int N, M, W[100000];
vector< int > g[100000];

bool v[100000];
int order[100000], low[100000], ptr;
int64 sum[100000], ans[100000];
vector< int > tree[100000];

void dfs(int idx, int par)
{
  v[idx] = true;
  order[idx] = ptr++;
  low[idx] = order[idx];
  sum[idx] = W[idx];
  for(auto &to : g[idx]) {
    if(!v[to]) {
      dfs(to, idx);
      low[idx] = min(low[idx], low[to]);
      sum[idx] += sum[to];
      tree[idx].emplace_back(to);
    } else if(to != par) {
      low[idx] = min(low[idx], order[to]);
    }
  }
}

void dfs2(int idx, int64 parcost)
{
  bool art = false;
  int64 all = parcost;
  if(idx == 0) {
    if(tree[idx].size() > 1) art = true;
    else art = false;
  } else {
    for(auto &to : tree[idx]) art |= order[idx] <= low[to];
  }
  for(auto &to : tree[idx]) all += sum[to];
  if(art) {
    int64 latte = parcost, malta = 0;
    for(auto &to : tree[idx]) {
      if(order[idx] <= low[to]) malta = max(malta, sum[to]);
      else latte += sum[to];
    }
    ans[idx] = max(latte, malta);
  } else {
    ans[idx] = sum[0] - W[idx];
  }
  for(auto &to : tree[idx]) dfs2(to, all + W[idx] - sum[to]);
}

int main()
{
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> W[i];
  }
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  dfs(0, -1);
  dfs2(0, 0);
  for(int i = 0; i < N; i++) {
    cout << ans[i] << endl;
  }
}

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

int sum_digit(int num) {
    int size, ans;

    ans = 0;

    size = (int)log10((double)num) + 1;

    for (int i = 0; i < size; i++) {
        ans += num % 10;
        num /= 10;
    }

    return ans;
}

int main() {
    int num, sum;
    cin >> num;

    sum = sum_digit(num);

    if (num % sum == 0) {
        cout << "Yes" << endl;
    } else if (num % sum != 0) {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
using System.Collections.Generic;
 
using System.Linq;
using System;
 
namespace Application
{
	class Solution
	{
		static void Main(string[] args)
		{
			var answer = Console.ReadLine();
 
			//末尾から削っていって全部削れるか
 
 
			var words = new List<string>() { "dream", "dreamer", "erase", "eraser" };
 
			while (answer.Length > 0)
			{
				var beforeAnswerLength = answer.Length;
 
				foreach(var word in words)
				{
					if (answer.EndsWith(word))
					{
						answer = answer.Substring(0, answer.Length - word.Length);
					}
				}
 
				if (answer.Length == beforeAnswerLength)
					break;
			}
 
			var result = answer.Length == 0 ? "YES" : "NO";
 
			Console.WriteLine(result);
		}
	}
}

Measured memory_bytes: 31776
n = int(input())
for i in range(1,3501):
  for j in range(1,3501):
   if (4*i*j-n*i-n*j)!=0:
    if (n*i*j)//(4*i*j-n*i-n*j) >0 and  (n*i*j)%(4*i*j-n*i-n*j)== 0:
      print(i,j,(n*i*j)//(4*i*j-n*i-n*j))
      exit()


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

#define int long long

long long ans;
long long n, N;

vector<long long> pri;
vector< pair<int, long long> > p;

long long power ( long long i, int j ) {
    long long ans = 1;
    for ( int I = 0; I < j; I++ ) {
        ans *= i;
    }
    return ans;
}

void tmp ( int pos, long long sum ) {
    if ( pos == p.size() ) {
        if ( sum*sum < N ) {
            long long hant = ( N/sum ) -1;
            if ( hant < 1 ) return;
            if ( N / hant == N % hant ) {
                ans += hant;
            }
        }
        return;
    }
    for ( int i = 0; i <= p[pos].first; i++ ) {
        tmp(pos+1, sum * power( p[pos].second, i ));
    }
}

signed main() {

    cin >> n;
    N = n;
    long long all = 0;

    if ( n == 1 ) {
        puts("0");
        return 0;
    }

    /*
    for ( long long i = 1; i <= n; i++ ) {
//        printf("%3d %3d 商:%3d 余り:%3d", n, i, n/i, n%i);
        if ( n/i == n%i ) {
//            puts(" ###");
            all += i;
        }
  //      else puts("");
    }
    

    */
    while ( n % 2 == 0 ) {
        pri.push_back(2);
        n /= 2;
    }

    for ( long long i = 3; i * i <= n; i += 2 ) {
        while ( n % i == 0 ) {
            pri.push_back(i);
            n /= i;
        }
    }
    if ( n > 1 ) pri.push_back(n);
    sort(pri.begin(), pri.end());

    int prev = pri[0];
    int cnt = 1;
    for ( int i = 1; i < pri.size(); i++ ) {
        if ( prev != pri[i] ) {
            p.push_back ( make_pair ( cnt, prev ) );
            cnt = 1;
            prev = pri[i];
        }
        else cnt++;
    }
    p.push_back( make_pair ( cnt, prev ) );

    tmp(0, 1);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256