akhauriyash/Code-Regression huggingface dataset:
/*
 * Strongly Connected Components
 * A direced graph is strongly connected if every two nodes are reachable from
 * each other. In a strongly connected component of a directed graph, every two
 * nodes of the component are mutually reachable.
 *
 * Input
 * A directed graph G(V,E) and a sequence of queries where each query contains a
 * pair of nodes u and v.
 *
 * |V| |E|
 * s0 t0
 * s1 t1
 * :
 * s|E|−1 t|E|−1
 * Q
 * u0 v0
 * u1 v1
 * :
 * uQ−1 vQ−1
 * |V| is the number of nodes and |E| is the number of edges in the graph. The
 * graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.
 *
 * si and ti represent source and target nodes of i-th edge (directed).
 *
 * ui and vi represent a pair of nodes given as the i-th query.
 *
 * Output
 * For each query, pinrt "1" if the given nodes belong to the same strongly
 * connected component, "0" otherwise.
 *
 * Constraints
 * 1 ≤ |V| ≤ 10,000
 * 0 ≤ |E| ≤ 30,000
 * 1 ≤ Q ≤ 100,000
 */

#include <algorithm>
#include <functional>
#include <iostream>
#include <stack>
#include <vector>

#define MAXN 10010
#define MAXM 30030

using namespace std;

struct edge {
  int to, next;
};

bool visited[MAXN];

void dfs(int i, vector<edge> &E, vector<int> &LE,
         const function<void(int)> &preprocess,
         const function<void(int)> &postprocess) {
  if (visited[i])
    return;
  visited[i] = true;
  preprocess(i);
  for (int e = LE[i]; e != -1; e = E[e].next)
    dfs(E[e].to, E, LE, preprocess, postprocess);
  postprocess(i);
}

int main() {
  vector<int> LE(MAXN, -1), LErev(MAXN, -1);
  vector<edge> E(MAXM), Erev(MAXN + MAXM);

  int n, m;
  cin >> n >> m;
  for (int src, dst, i = 0; i < m; ++i) {
    cin >> src >> dst;
    E[i] = {dst, LE[src]};
    LE[src] = i;
    Erev[i] = {src, LErev[dst]};
    LErev[dst] = i;
  }

  // adding dummy node with index n for DFS
  for (int i = m; i < m + n; ++i) {
    Erev[i] = {i - m, LErev[n]};
    LErev[n] = i;
  }

  fill(visited, visited + MAXN, false);
  stack<int> grev_post; // pop off in descending postnumber order in Grev
  dfs(n, Erev, LErev, [](int x) { return; }, [&](int x) { grev_post.push(x); });
  grev_post.pop(); // dummy node

  vector<int> scc(n);
  fill(visited, visited + MAXN, false);
  for (int i = 1; !grev_post.empty(); ++i) {
    while (!grev_post.empty() && scc[grev_post.top()])
      grev_post.pop();
    if (grev_post.empty())
      break;
    dfs(grev_post.top(), E, LE, [&](int x) { scc[x] = i; },
        [](int x) { return; });
  }

  int q;
  cin >> q;
  for (int s, t; cin >> s >> t;) {
    cout << (scc[s] == scc[t]) << endl;
  }
}


Measured memory_bytes: 4552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) (v).begin(),(v).end()
#define debug(x) cout << #x << '=' << x << '\n'
const long long MOD=1e9+7;
//const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?'\n':' ');
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> cnt(N,0);
    for (int i=0;i<N-1;++i){
        int A; cin >> A;
        ++cnt[--A];
    }
    for (int i=0;i<N;++i) cout << cnt[i] << '\n';
}

Measured memory_bytes: 3964
#include<stdio.h>

int main(){
	int K,N;
  	scanf("%d %d",&K,&N);
  
  	int A[N],ans=0,sum=0,max=0;
  	for(int i=0;i<N;i++){
	  	scanf("%d",&A[i]);
      if(i>0){		
      	sum += A[i] - A[i-1];
      }
      if(max<(A[i]-A[i-1])){
      	max = A[i] - A[i-1];
      }
    }
  	int lest=0;
    lest = K-sum;
  	
  	if(lest > max){
        max = lest;
    	ans = sum + lest - max;
    }else{
    	ans = sum + lest - max;
    }
    
  	printf("%d",ans);  	  	  	
	return 0;
}

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

int main(){
    int a,b,t;
    cin >> a >> b >> t;
    int ans = 0;
    for(int i = 1; i * a <= t; i++) {
        ans += b;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
//C - Remainder Minimization 2019
//20190912

using System;
using System.Linq;
using System.Collections.Generic;


namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] lr = Console.ReadLine().Split().Select(long.Parse).ToArray();

            long L = lr[0];
            long R = lr[1];

            if (R - L >= 2019)
            {
                Console.WriteLine(0);
            }
            else
            {
                long min = 2018;
                for (long i = L; i < R; i++)
                {
                    for (long j = i + 1; j <= R; j++)
                    {
                        min = Math.Min(min, i * j % 2019);
                    }
                }
                Console.WriteLine(min);
            }
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
  int p,q,m;
  cin>>p>>q>>m;
  vi a(p),b(q);
  vi x(m),y(m),c(m);
  rep(i,p)cin>>a[i];
  rep(i,q)cin>>b[i];
  rep(i,m)cin>>x[i]>>y[i]>>c[i];

  std::vector<int>::iterator iter = std::min_element(a.begin(), a.end());
  size_t index = std::distance(a.begin(), iter);
  int m_a=a[index];
  iter = std::min_element(b.begin(), b.end());
  index = std::distance(b.begin(), iter);
  int m_b=b[index];
  ll int ans=m_b+m_a;
  rep(i,m){
    if(ans>a[x[i]-1]+b[y[i]-1]-c[i]){
      ans = a[x[i]-1]+b[y[i]-1]-c[i];
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 2176
#include<iostream>
#include<cstring>

#define MAX 100005
#define abs(a) ((a) > 0 ? a : -a)
using namespace std;
struct People{
	int root,dis;
};
People root[MAX];

int FindRoot(int p)
{
	if(root[p].root == p)
		return p;
	int y = root[p].root;
	root[p].root = FindRoot(root[p].root);
	root[p].dis += root[y].dis;
	return root[p].root;
}
bool Merage(int p1,int p2,int dis)
{
	int root1 = FindRoot(p1),root2 = FindRoot(p2);
	int dis1 = root[p1].dis,dis2 = root[p2].dis;
//	cout << root1 << ":" << root2 << endl;
//	cout << dis1 << ":" << dis2 << endl;
	if(root1 == root2){
		if(dis1 - dis2 == dis)
			return true;
		else
			return false;
	}else{
		root[root1].root = root2;
		root[root1].dis = -dis1 + dis + dis2; 
		return true;
	}
}
int main( )
{
	for(int i = 1; i < MAX; i++)
		root[i] = (People){i,0};
	int n,m;
	cin >> n >> m;
	
	for(int i = 0; i < m; i++){
		int l,r,d;
		cin >> l >> r >> d;
		if(!Merage(l,r,d)){
			cout << "No" << endl;
			return 0;
		}
		/*for(int i = 1; i <= n; i++)
			cout << root[i].root << " " << root[i].dis << "|";
		cout << endl; */
	}
	cout << "Yes" << endl;
	return 0;
}



Measured memory_bytes: 1024
lines = []
while line = gets
    lines << line.chomp.split(' ')
end

N = lines[0][0].to_i
K = lines[0][1].to_i
R = lines[1][0].to_i
S = lines[1][1].to_i
P = lines[1][2].to_i
T = lines[2][0]

a = []
for i in 1..K do
  a[i-1] = []
end

for i in 1..N do
  mod = i % K
  a[mod].push(T[i-1])
end

def point(x)
  if x == "r" then
    return P
  elsif x == "p" then
    return S
  else
    return R
  end
end
    
def win(x)
  if x == "s"
    return "r"
  elsif x == "r"
    return "p"
  else
    return "s"
  end
end

score = 0
for i in 0..K-1 do
  previous = "x"
  for j in 1..a[i].length do
    if previous != win(a[i][j-1]) then
      score += point(a[i][j-1])
      previous = win(a[i][j-1])
    else
      previous = "x"
    end
  end
end
    
print score

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

int main(){
	
	int n;
	int a[99999];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	
	
	cout<<a[n/2]-a[n/2-1];

	return 0;
} 

Measured memory_bytes: 640
# ABC-137-D
import heapq

N, M = map(int, input().split())
day_value = [[] for _ in range(M+1)]

for _ in range(N):
    A, B = map(int, input().split())
    if A <= M:
        day_value[A].append(B)

ans = 0
check_M = 1
BA = []
heapq.heapify(BA)

while check_M <= M:
    for item in day_value[check_M]:
        heapq.heappush(BA, -1*item)
    try:
        max_B = heapq.heappop(BA)
    except:
        check_M += 1
        continue
    ans += (-1) * max_B
    check_M += 1
print(ans)

Measured memory_bytes: 18564
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define N 110
using namespace std;
char s[N],t[N];
int n,ans;
void check(int x)
{
	bool bo=0;
	for(int i=1;i<=n;i++) {t[i]=s[i];if(s[i]==x) bo=1;}
	if(bo==0) return;
	int tmp=0,m=n;
	while(1)
	{
		bo=1;
		for(int i=1;i<=m;i++) if(t[i]!=x) {bo=0;break;}
		if(bo) {ans=min(ans,tmp);return;}
		tmp++;
		for(int i=1;i<m;i++) if(t[i+1]==x) t[i]=x;
		m--;
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	ans=1e9;
	for(int i='a';i<='z';i++) check(i);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using vl = vector<long long>;
using P = pair<long long,long long>;
const ll mod = 1000000007;

ll inv(ll x){
	ll x0 = x;
	rep(i,9){
		ll r = x;
	  rep(j,9){
	  	r *= x;
	  	r %= mod;
	  }
	  x = r;
	}
	rep(i,5){
		x *= x0;
		x %= mod;
	}
	return x;
}
ll conbi(ll n,ll k){
	ll ans = 1;
	for(ll i = n - k + 1;i<n+1;i++){
		ans *= i;
		ans %= mod;
	}
	rep(i,k){
		ans *= inv(i+1);
		ans %= mod;
	}
	return ans;
}

int main(){
	ll x,y; cin >> x >> y;
	if((2*x - y) % 3 != 0 || 2*x < y || 2*y < x){
		cout << 0 << endl;
		return 0;
	}
	// x = p + 2q,y = 2p + q
	ll p,q;
	p = (2*y - x)/3; q = (2*x - y)/3;
	cout << conbi(p+q,p) << endl;
}

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

typedef long long ll;

ll mat[505][505];
int H, W, h, w;
ll x, s;

int main()
{
	scanf("%d%d%d%d", &H, &W, &h, &w);
	if (h*w == 1)
	{
		printf("No\n");
		return 0;
	}
	x = 999999999ll/(h*w-1);
	for (int i = 0;i < H;i++) for (int j = 0;j < W;j++) mat[i][j] = x;
	for (int i = h-1;i < H;i+=h) for (int j = w-1;j < W;j+=w) mat[i][j] = (1-h*w)*x-1;
	for (int i = 0;i < H;i++) for (int j = 0;j < W;j++) s += mat[i][j];
	if (s > 0)
	{
		printf("Yes\n");
		for (int i = 0;i < H;i++)
		{
			for (int j = 0;j < W;j++) printf("%lld ", mat[i][j]);
			printf("\n");
		}
	} else printf("No\n");
	return 0;
}


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

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

	ll N;
	cin >> N;
	map<ll,set<ll> > A; // (score, {p1,...,ps})
	for (ll i = 0; i < N; i++) {
		ll a;
		cin >> a;
		A[a].insert(i + 1);
	}
	vector<vector<ll> > dp(N + 1, vector<ll>(N + 1, 0)); // dp[x=0,...,N][y=0,...,N] = high score;
	dp[0][0] = 0;
	ll currentXY = 0; // 今、x+yがどこまで計算され、DPに保存されたか。
	ll maxScore = 0;
	for (auto it = A.rbegin(); it != A.rend(); it++) {
		// 同じAのものについて、まとめて計算する。
		ll myA = it->first;
		set<ll>* s = &it->second;
		ll sSize = s->size();
//		cout << "Ai = " << myA << ", size = " << sSize << endl;
		// sを小さい方から順にindexまで累積和
		vector<ll> cumm(sSize + 1, 0);
		ll count = 0;
		ll mySum = 0;
		for (auto jt = s->begin(); jt != s->end(); jt++) {
			count++;
			cumm.at(count) = (mySum += *jt);
		}
//		for (int i = 0; i <= sSize; i++) { cout << cumm[i] << ", "; } cout << "mysum = " << mySum << endl;
		for (ll z = 0; z <= currentXY; z++) {
			// z の場所から飛ばす。
			ll zx = currentXY - z;
			ll zy = z;
//			cout << "(zx,zy) = (" << zx << "," << zy << ")" << endl;
			for (ll y = 0; y <= sSize; y++) {
				ll x = sSize - y;
				// 座標は、(zx,zy) から (zx + x, zy + y) へ
				ll myscore = myA * (mySum - 2 * cumm[y] - x * (2 * zx + x + 1) / 2 + y * (2 * (N - zy) - y + 1) / 2);
				if (dp[zx + x][zy + y] < dp[zx][zy] + myscore) { dp[zx + x][zy + y] = dp[zx][zy] + myscore; }
//				cout << "(zx,zy,x,y,myscore) = (" << zx << "," << zy << "," << x << "," << y << "," << myscore << ")" << endl;
				if (maxScore < dp[zx + x][zy + y]) { maxScore = dp[zx + x][zy + y]; }
			}
		}
		currentXY += sSize;
	}
	cout << maxScore << endl;

/*
	for (int x = N; x >= 0; x--) {
		for (int y = 0; y <= N; y++) {
			cout << dp[x][y] << " ";
		}
		cout << endl;
	}
*/
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int cnt[222222];

signed main(){
    int N;cin>>N;
    rep(i,N){
        int a;cin>>a;cnt[a]++;
    }

    int ans=0;
    for(int i=1;i<100000;i++){
        chmax(ans,cnt[i-1]+cnt[i]+cnt[i+1]);
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <bitset>
#include <utility>
#include <ctime>
#include <cassert>
#include <climits>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii > vii;
typedef vector<pair<int, pair<int, int> > > viii;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<vii> vvii;

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define MEM(a,b) memset(a,(b),sizeof(a))
#define tr(c,it) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define all(a) a.begin(),a.end()
#define loop(x,a,b) for(int (x) = (a);(x)<(b);(x)++)
#define rep(x,n)   for(int (x)=0;(x)<(n);(x)++)
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ain(a,n) int ((a)[(n)]); for(int i=0; i<(n); i++) cin>>((a)[i])  
#define md 1000000007
#define MAXN 200005

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    ain(a,n);
    ain(b,m);
    sort(a,a+n);
    sort(b,b+m);
    if(y > x and y > a[n-1] and x < b[0] and b[0] > a[n-1])
    	cout<<"No War";
    else 
    	cout<<"War";
    return 0;
}


Measured memory_bytes: 256
s = input()
t = input()

def to_num_list(s):
    word_dic = {}
    word_number = []
    idx = 0
    for i in s:
        if i not in word_dic:
            word_dic[i] = idx
            idx += 1
        word_number.append(word_dic[i])
    return word_number

if to_num_list(s) == to_num_list(t):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 6832
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <list>
#define INF 10000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	int ans = (100 * (n - m) + 1900 * m) * (1 << m);
	cout << ans << endl;
	return 0;
}


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

// 基本テンプレート
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// 型
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// 定数
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion

#define int long long


signed main()
{
    int n;
    cin >> n;
    vector<int> v(n*3);
    rep(i, n*3) {
        cin >> v[i];
    }
    sort(v);

    int cnt = 0;
    int ans = 0;
    for(int i=v.size()-2; i>0; i-=2) {
        ans += v[i];
        cnt++;
        if(cnt==n) break;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 2560
function main(s) {
	s = s.split("\n");
	t = s[0].split(" ").map(x => Number(x));
	function cmp(x, y) {
		return Number(x) - Number(y);
	}
	l = s[1].split(" ").map(x => Number(x)).sort(cmp).reverse();
	var x = 0;
	for (var i = 0; i < t[1]; i++) {x += l[i];}
	console.log(x);
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));



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

using namespace std;

int main()
{
    int x;
    cin>>x;
    char c[x];
    for(int i=0 ;i<x;i++){
        cin>>c[i];
    }
int    counter =0;
    for(int i=0 ;i<x;i++){
        if(c[i]!=c[i+1])counter++;
    }
    cout<<counter;
    return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define N 600005
using namespace std;
int n,m,l,r,c[N];
struct node{int l,r,len;}a[N];
inline bool cmp(node aa,node bb){return aa.len<bb.len;}
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y){for(int i=x;i<=m;i+=lowbit(i))c[i]+=y;}
inline int sum(int x){int ans=0;for(int i=x;i;i-=lowbit(i))ans+=c[i];return ans;}
int main(){
	scanf("%d%d",&n,&m);int tot=0;
	for (int i=1;i<=n;i++){
		scanf("%d%d",&l,&r);
		a[i].l=l;a[i].r=r;
		a[i].len=r-l+1;
	}
	sort(a+1,a+n+1,cmp);int j=1;
	for (int i=1;i<=m;i++){
		for (;j<=n;j++){
			if (a[j].len>i) break;
			add(a[j].l,1);
			if (a[j].r+1<=m) add(a[j].r+1,-1);
		}
		int ans=n-j+1;
		for (int j=i;j<=m;j+=i) ans=ans+sum(j);
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 7040
#define _CRT_SECURE_NO_WARNINGS
#include<utility>
using std::swap;
struct PairingHeap {
	struct Node {
		int key;
		Node *head, *next;
		Node(int key) : key(key), head(0), next(0) { }
	} *r;

	Node *merge(Node *i, Node *j) {
		if (!i || !j) return i ? i : j;
		if (i->key < j->key) swap(i, j);
		j->next = i->head; i->head = j;
		return i;
	}
	Node *mergeList(Node *s) {
		Node n(0);
		while (s) {
			Node *a = s, *b = 0;
			s = s->next; a->next = 0;
			if (s) { b = s; s = s->next; b->next = 0; }
			a = merge(a, b); a->next = n.next;
			n.next = a;
		} // s == 0
		while (n.next) {
			Node *j = n.next;
			n.next = n.next->next;
			s = merge(j, s);
		}
		return s;
	}
	int  top() { return r->key; }
	void pop() { r = mergeList(r->head); }
	void push(int key) { r = merge(r, new Node(key)); }
	bool empty() { return !r; }
	PairingHeap() : r(0) { }
};
#include<cstdio>
#include<string>
void scan(std::string &s) {
	s.clear();
	int c = fgetc(stdin);
	while (c == ' ' || c == '\n') c = fgetc(stdin);
	while (c != ' '&&c != '\n') {
		s.push_back(c);
		c = fgetc(stdin);
	}
}

int main() {
	PairingHeap Q;
	std::string s;
	int k;
	while (scan(s),s[2] != 'd') {
		if (s[0] == 'i') {
			scanf("%d", &k);
			Q.push(k);
		}
		else {
			printf("%d\n", Q.top());
			Q.pop();
		}
	}
	return 0;
}


Measured memory_bytes: 49708
#include<iostream>
using namespace std;
int main(){
    int tate,yoko,x,y,t;
    while(1){
        cin >> tate >> yoko;
        if(tate==0 && yoko==0){
            break;
        }
        for(x=0;x<tate;x++){
            if(x%2==0){
                for(y=0;y<yoko;y++){
                    if(y%2==0) cout << "#";
                    else cout <<".";
                }
            }
            else {
                for(y=0;y<yoko;y++){
                    if(y%2==0) cout << ".";
                    else cout <<"#";
                }
            }
            y=0;
            cout << endl;
        }
        x=0;
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h> 
using namespace std;
#define endl "\n"
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef long long ll;
#define MOD 1000000007;
 
int main() 
{ 
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    ll sum = 0;
    ll m = INT_MAX;
    ll ans=0;
    ll a[n];
    for(int i = 0; i < n;i++){
        cin >> a[i];
    }
    sort(a,a+n,greater<ll>());
    
    ans+=a[0];
    int k = 1;
    int i = n-2;
    while(i > 1){
        ans+=2*(a[k]);
        i-=2;
        k++;
    }
    if(i==1){
        ans+=a[k];
    }
    cout << ans << endl;


    
    return 0;
}

Measured memory_bytes: 5256
#include <bits/stdc++.h>
using namespace std;
 
int m = 1e9+7; 
int dp[1001][1001];
int sol(vector<vector<char>> &s, int i, int j)
{
    int h = s.size();
    int w = s[0].size();
    if(i <0 || i>=h || j<0 || j>=w)
        return 0;
    if(i == h-1 && j == w-1)
        return 1;
    if(dp[i][j] != -1)
        return dp[i][j];
    if(s[i][j] == '#')
        return 0;
    return dp[i][j] = (sol(s,i+1,j)%m + sol(s, i,j+1)%m)%m;
    
}

int main() 
{
    int h , w;
    cin>>h>>w;
    vector<vector<char>> s(h, vector<char>(w));
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i<h; i++)
    {
        for(int j = 0; j<w; j++)
            cin>>s[i][j];
    }
    cout<<sol(s, 0, 0);
	return 0;
}


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 200005;
int N;
vector<int> edges[MAX_N];

vector<int> nodes[2];
void reg(int pos = 0, int depth = 0, int pre = -1)
{
  nodes[depth%2].push_back(pos);
  for(int next : edges[pos]) {
    if (next == pre) continue;
    reg(next, depth+1, pos);
  }
}

int ans[MAX_N];
unordered_map<int, bool> OK;
int num[4];

void solve(int pos = 0, int pre = -1)
{
  for(int next : edges[pos]) {
    if (next == pre) continue;
    solve(next, pos);
  }
  
}

signed main()
{
  cin >> N;
  REP(n,N-1) {
    int a, b; cin >> a >> b;
    a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  reg();

  if(nodes[0].size() > nodes[1].size()) {
    swap(nodes[0], nodes[1]);
  }

  num[1] = N/3 + (N%3 >= 1);
  num[2] = N/3 + (N%3 >= 2);
  num[3] = N/3;

  if(nodes[0].size() <= num[3]) {
    for(int node : nodes[0]) {
      ans[node] = 3;
      num[3]--;
    }
    for(int node : nodes[1]) {
      FOR(i,1,4) {
        if(num[i] > 0) {
          ans[node] = i;
          num[i]--;
          break;
        }
      }
    }
  } else {
    for(int node : nodes[0]) {
      if(num[1] > 0) {
        ans[node] = 1;
        num[1]--;
      } else {
        ans[node] = 3;
        num[3]--;
      }
    }
    for(int node : nodes[1]) {
      if(num[2] > 0) {
        ans[node] = 2;
        num[2]--;
      } else {
        ans[node] = 3;
        num[3]--;
      }
    }
  }

  memset(num, 0, sizeof(num));
  REP(n,N) {
    if(n > 0) cout << " ";
    cout << ans[n] + num[ans[n]]*3;
    num[ans[n]]++;
  }
  cout << endl;

  return 0;
}


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

int main() {
  long long int a,b;
  cin>>a>>b;
  
  if(b>=2*a){
    b=b-2*a;
    cout<<a+b/4<<endl;
  }
  else{
    cout<<b/2<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (INT_MAX / 4)
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
/* clang-format off */
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" << "\n";
/* clang-format on */

int main() {
  int n;
  cin >> n;
  vector<int> p(n), tmp(n);
  REP(i, n) { cin >> p.at(i); }
  REP(i, n) { tmp.at(i) = p.at(i); }
  sort(ALL(tmp));
  int diff = 0;
  REP(i, n) {
    if (tmp.at(i) != p.at(i)) diff++;
  }
  if (diff <= 2)
    cout << "YES"
         << "\n";
  else
    cout << "NO"
         << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
//#include<math.h>
int ifcl(int p0[2],int p1[2],int p2[2],int p3[2]){
  long long x0=p1[0]-p0[0],x1=p2[0]-p0[0],x2=p3[0]-p0[0]/*,x3=x2-x1,x4=x0-x1,x5=-x1*/;
  long long y0=p1[1]-p0[1],y1=p2[1]-p0[1],y2=p3[1]-p0[1]/*,y3=y2-y1,y4=y0-y1,y5=-y1*/;
  long long x3=p3[0]-p2[0],x4=p1[0]-p2[0],x5=p0[0]-p2[0];
  long long y3=p3[1]-p2[1],y4=p1[1]-p2[1],y5=p0[1]-p2[1];
  long long x6=p2[0]-p1[0],x7=p3[0]-p1[0]/*,x3=x2-x1,x4=x0-x1,x5=-x1*/;
  long long y6=p2[1]-p1[1],y7=p3[1]-p1[1]/*,y3=y2-y1,y4=y0-y1,y5=-y1*/;
  
  long long c1=(x0*y1-y0*x1)*(x0*y2-y0*x2),c2=(x3*y4-y3*x4)*(x3*y5-y3*x5);
  long long d1=x1*x6+y1*y6,d2=x2*x7+y2*y7,d3=x1*x2+y1*y2,d4=x6*x7+y6*y7;
  if(c1==0&&c2==0)return (d1>0&&d2>0&&d3>0&&d4)?0:1;
  return (c1<=0&&c2<=0)?1:0;
}
/*double dMIN(double a,double b){return a<b?a:b;}
double drpl(int p0[2],int p1[2],int p2[2]){
  int a=p0[1]-p1[1],b=p0[0]-p1[0],c=p0[0]*p1[1]-p1[0]*p0[1];
  int d=p2[1]-p1[1],e=p2[0]-p1[0];
  int f=p2[1]-p0[1],g=p2[0]-p0[0];
  if(a*d+b*e<0||a*f+b*g>0)return dMIN(hypot(d,e),hypot(f,g));
  return abs(p2[0]*a-p2[1]*b+c)/hypot(a,b);
}
double drll(int *p0,int *p1,int *p2,int *p3){
  double l=drpl(p2,p3,p0);
  l=dMIN(l,drpl(p2,p3,p1));
  l=dMIN(l,drpl(p0,p1,p2));
  l=dMIN(l,drpl(p0,p1,p3));
  if(ifcl(p0,p1,p2,p3))l=0;
  return l;
  }*/
int main(){
  int p[4][2],n,i;
  scanf("%d",&n);
  while(n--){
    for(i=0;i<8;i++)scanf(" %d",&p[i/2][i%2]);
    printf("%d\n",ifcl(p[0],p[1],p[2],p[3]));
  }
  return 0;
}

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

bool check(const std::string& input) {
  if(input == "01" or
     input == "02" or
     input == "03" or
     input == "05" or
     input == "06" or
     input == "07" or
     input == "08" or
     input == "09" or
     input == "10" or
     input == "11" or
     input == "12") 
  {
    return true; 
  }
  
  return false;
}

int main()
{
  std::string input;
  std::cin >> input;

  bool yymm = false, mmyy =false;

  for(int i = 0; i < 2; i++) {
    std::string work_str;
    work_str.push_back(input[2*i]);
    work_str.push_back(input[1+2*i]); 

    if (i == 0) {
      mmyy = check(work_str); 
    }
    else {
      yymm = check(work_str); 
    }
  }

  if(yymm and mmyy) {
    std::cout << "AMBIGUOUS" << std::endl; 
    return 0;
  }

  if(yymm) {
    std::cout << "YYMM" << std::endl; 
    return 0;
  }

  if(mmyy) {
    std::cout << "MMYY" << std::endl; 
    return 0;
  }

  std::cout << "NA" << std::endl;

  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Here your code !
    int a,b;
    scanf("%d %d",&a,&b);
    if(a<b){
    printf("a < b\n");
    }else if(a>b){
    printf("a > b\n");
    }else if(a==b){
    printf("a == b\n");
    }
    
    return 0;
}

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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

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

  int remain = n % 500;
  if (remain <= a) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

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

int main(void){  
  int s1,s2;
  while(cin>>s1>>s2,s1||s2){
    int n[5] = {0}, mi = 0;
    n[0] = s1 + s2;
    FOR(i,1,5){
      cin >> s1 >> s2;
      n[i] = s1 + s2;
    }
    FOR(i,1,5){
      if(n[mi] < n[i] ) mi = i;
    }
    printf("%c %d\n",'A'+mi,n[mi]);
  }
  return 0;
}

Measured memory_bytes: 0
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
import heapq
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 10 ** 9 + 7
def mint(lis):
    return list(map(int, lis))

def bifind(arr_sorted, x):
    idx = bisect_left(arr_sorted, x)
    if idx == len(arr_sorted):
        return False
    if arr_sorted[idx] == x:
        return True
    else:
        return False
def getyaku(n):
    ret = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            ret.append(i)
            ret.append(n // i)

    return ret

def find(x, a):
    idx = bisect_left(a, x)
    if idx == len(a):
        return False
    if a[idx] == x:
        return True
    else:
        return False

def main():
    n = getN()
    nums = getList()
    nums = [(x, i+1) for i, x in enumerate(nums)]
    nums.append((0, INF))
    nums.sort(key=lambda x: -x[0] * INF + x[1])
    # print(nums)
    mx = INF
    ans = [0 for i in range(n+1)]
    tmp_tgt = INF
    through = 0
    for a,b in nums:
        if a != mx:
            diff = mx - a



            if mx != INF:
                ans[tmp_tgt] += through * diff
            mx = a
            if b < tmp_tgt:
                tmp_tgt = b
        through += 1
    for an in ans[1:]:
        print(an)

if __name__ == "__main__":
    main()



Measured memory_bytes: 84368
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ALL(v) (v).begin(), (v).end()
#define ios() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
constexpr ll MOD = 1e9+7;
constexpr ll INF = 1LL << 60;
constexpr int Inf = 1e9;
inline int in() {int x; cin >> x; return x;}
template <typename T> inline void out(const T& x) {cout << x << endl;}
template <class T> inline bool chmin(T &a, T b){if (a > b){a = b;return 1;}return 0;}
template <class T> inline bool chmax(T &a, T b){if (a < b){a = b;return 1;}return 0;}
//UP = 0;RIGHT = 1; DOWN = 2; LEFT =3;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b)
{
  if (a < b)
    gcd(b, a);
  int r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}
void eratos(bool * isPrime,int max){
  fill(isPrime,isPrime + max,true);
  isPrime[0] = false; 
  isPrime[1] = false; 
  for(int i=2; i<=max/i; ++i) 
      if(isPrime[i]) 
          for(int j=2; j<=max/i; ++j) 
              isPrime[i*j] = false;    
}
//

vector<int> divisor(int n){
  vector<int> ret;
  for(int i = 0;i * i <= n;i++){
    ret.push_back(i);
    if(i*i != n) ret.push_back(i);
  }
  sort(ALL(ret));
  return ret;
}

signed main()
{
  ios();
  int N,M;
  cin >> N >> M;
  int A[N];
  vector<pair<int,int>> BC(M);
  for(int i = 0;i < N;i++) {
    cin >> A[i];
  }
  rep(i,M) {
    cin >> BC[i].first >> BC[i].second;
  }
  sort(BC.begin(),BC.end(),[](auto a, auto b){ return a.second > b.second;});
  sort(A, A+N);
  int bci = 0;
  int j = 0;
  for (int i = 0; i < N; i++ ) 
  {
    if(A[i] >= BC[bci].second)continue;
    A[i] = BC[bci].second;
    j++;
    if(j % BC[bci].first == 0 ) bci ++,j=0;
    if(bci >= M) break;
  }
  int sum = 0;
  rep(i,N){
    sum += A[i];
  }
  cout << sum << endl;

}


Measured memory_bytes: 2560
S = input()
T = input()
S_dict={}
T_dict={}
for i in range(len(S)):
    if S[i] not in S_dict:
        S_dict[S[i]] = 1
    else:
        S_dict[S[i]] += 1
    if T[i] not in T_dict:
        T_dict[T[i]] = 1
    else:
        T_dict[T[i]] += 1
S_list=list(S_dict.values())
T_list=list(T_dict.values())
S_list.sort()
T_list.sort()
result='Yes'
for (x,y) in zip(S_list,T_list):
    if int(x)!=int(y):
        result='No'
print(result)

Measured memory_bytes: 42268
#include <math.h>
#include <ctype.h>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
struct omt{omt(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int main(){
    int x, y;
    cin >> x >> y;

    if(x % y != 0) cout << x << endl;
    else cout << -1 << endl;

    return 0;
}

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


int main() {
    int n;
    cin >> n;
    vector<ll> a(n+1),x(n);
    for (int i=0;i<n;i++) cin >> a[i];
    x[0]=0;
    for (int i=0;i<n;i++) {
        if (i%2==0) x[0]+=a[i];
        else x[0]-=a[i];
    }
    for (int i=1;i<n;i++) {
        x[i]=(a[i-1]-x[i-1]/2)*2;
    }
    for (int i=0;i<n;i++) {
        cout << x[i];
        if (i!=n-1) cout << ' ';
        else cout << endl;
    }
}

Measured memory_bytes: 2944
import math
 
A, B = map(int, input().split())
min_ans = -(-A // 0.08)
 
kouho = [min_ans]
to_continue = True
while to_continue:
    min_ans += 1
    if math.floor(min_ans * 0.08) == A:
        kouho.append(min_ans)
    else:
        break
        
print_flag = False
for i in kouho:
    if math.floor(i * 0.1) == B:
        print_flag = True
        print(int(i))
        break
    
if print_flag == False:
    print(-1)

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

#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
using namespace std;

int main(){
	int n;	cin >> n;
	long long int a[n];
	for( int i = 0; i < n; i++ ){
		cin >> a[i];
	}
	long long int ans;

	sort( a, a + n, greater<long long int>() );

	ans = 0;
	int j = 0;
	for( int i = 0; i < n - 1; i++ ){
		ans += a[j];
		if( i % 2 == 0 )	j++;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 5188
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    if (n % 2) {
        for (int i = 1; i <= m; i++) cout << i << ' ' << n - i << '\n';
    } else {
        for (int i = 1; i <= (m + 1) / 2; i++) cout << i << ' ' << n - i + 1 << '\n';
        for (int i = (m + 1) / 2 + 1; i <= m; i++) cout << i << ' ' << n - i << '\n';
    }
}


Measured memory_bytes: 3620
#include <iostream>
#include <map>
using namespace std;
int main() {
    int N, a[100000], ans = 0;
    map<int, int> m;
    map<int, int>::iterator itr;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        itr = m.find(a[i]);
        if (itr == m.end()) m.insert(make_pair(a[i], 1));
        else m[a[i]]++;
    }
    for (itr = m.begin(); itr != m.end(); ++itr) {
        if (itr->first > itr->second) ans += itr->second;
        else if (itr->first < itr->second)  ans += itr->second - itr->first;
    }
    cout << ans << endl;
}

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

bool done[100][100];
int H=1,W;
char field[100][100];
int ans;

int solve(int i,int j){
	if(done[i][j]==1 || i<0 || H<=i || j<0 || W<=j) return 0;
	done[i][j]=1;
	int x[4]={1,0,-1,0},y[4]={0,1,0,-1};
	for(int k=0;k<4;k++){
		if(field[i][j]==field[i+x[k]][j+y[k]]){
			solve(i+x[k],j+y[k]);
		}
	}
	return 0;
}

int main(){
	cin>>H>>W;
	while(H){
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				cin>>field[i][j];
			}
		}
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(!done[i][j]){
					ans++;
					solve(i,j);
				}
			}
		}
		cout<<ans<<endl;
		ans=0;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				done[i][j]=0;
			}
		}
		cin>>H>>W;
	}
	return 0;
}

Measured memory_bytes: 1956
n = int(input())
h = list(map(int,input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(n):
  if i+1 < n:
    dp[i+1] = min(dp[i]+abs(h[i+1]-h[i]),dp[i+1])
  if i+2 < n:
    dp[i+2] = min(dp[i]+abs(h[i+2]-h[i]),dp[i+2])
print(dp[-1])

Measured memory_bytes: 13980
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

int main()
{
    int N,A;
    cin >> N >> A;
    if(N%500 <= A) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

using namespace std;

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

int main() {
  int a[10];
  rep (i, 10) cin >> a[i];
  sort(a, a+ 10, greater<int>());
  cout << a[0] << endl;
  cout << a[1] << endl;
  cout << a[2] << endl;
  return 0;
}

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

int main(){
  int64_t A,B,C;
  cin>>A>>B>>C;

  int64_t a=0,b=0,c=0;
  a=((A+1)/2)*B*C-(A/2)*B*C;
  b=A*((B+1)/2)*C-A*(B/2)*C;
  c=A*B*((C+1)/2)-A*B*(C/2);
  cout<<min(a,min(b,c))<<endl;
}


Measured memory_bytes: 256
#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 vll=vector<ll>;
using vc=vector<char>;

int dr[4]={-1,0,0,1};
int dc[4]={0,-1,1,0};
int r,c;

void search25(const vector<vc> &field, vector<vi> &dist, int sr, int sc, deque<pair<int,int>> &que){
    for(int i=-2;i<=2;i++){
        for(int j=-2;j<=2;j++){
            if(sr+i<0||sr+i>r||sc+j<0||sc+j>c) continue;
            if(field[sr+i][sc+j]=='#') continue;
            if(dist[sr+i][sc+j]>dist[sr][sc]+1){
                dist[sr+i][sc+j]=dist[sr][sc]+1;
                que.push_back({sr+i,sc+j});
            }
        }
    }
}

void bfs(const vector<vc> &field, vector<vi> &dist, int sr, int sc){
    deque<pair<int,int>> que;
    que.push_back({sr,sc});
    dist[sr][sc]=0;
    while(!que.empty()){
        auto v=que.front(); que.pop_front();
        for(int i=0;i<4;i++){
            int nextr=v.first+dr[i];
            int nextc=v.second+dc[i];
            if(field[nextr][nextc]=='#') continue;
            if(dist[nextr][nextc]>dist[v.first][v.second]){
                dist[nextr][nextc]=dist[v.first][v.second];
                que.push_front({nextr,nextc});
            }
        }
        search25(field,dist,v.first,v.second,que);
    }
}

int main(){
    cin >> r >> c;
    int sc,sr,gc,gr;
    cin >> sr >> sc >> gr >> gc;
    vector<vc> field(r+2,vc(c+2,'#'));
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> field[i][j];
        }
    }
    vector<vi> dist(r+2,vi(c+2,1e9));
    bfs(field,dist,sr,sc);
    if(dist[gr][gc]==1e9) cout << "-1" << endl;
    else cout << dist[gr][gc] << endl;
}

Measured memory_bytes: 8640
def f(n):
    cnt = 0
    while n:
        buf = n
        pc = 0
        while buf:
            pc += buf%2
            buf //= 2
        n = n%pc
        cnt += 1
    return cnt

N = int(input())
X = input()

v1, v2 = 0, 0
cnt = X.count("1")
for i, j in enumerate(X[::-1]):
    if j=="1":
        v1 += pow(2, i, cnt+1)
        v1 %= (cnt+1)

        if cnt>1:
            v2 += pow(2, i, cnt-1)
            v2 %= (cnt-1)

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        c2 = cnt+1
        buf = (v1+pow(2, p, c2))%c2
        print(f(buf)+1)
    else:
        c2 = cnt-1
        if c2>0:
            buf = (v2-pow(2, p, c2))%c2
            print(f(buf)+1)
        else:
            print(0)

Measured memory_bytes: 9500
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <math.h>
#define INF 1000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;

int main(){
  string a,b;
  cin >> a >> b;
  string c=a+b;
  int i = stoi(c);
  int j=sqrt(i);
  if(j*j==i)cout << "Yes" << endl;
  else  cout << "No" << endl;
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    vi a(1233);
    a[1] = 300000;
    a[2] = 200000;
    a[3] = 100000;

    int x,y;
    Scd2(x,y);
    int ans = a[x]+a[y]+((x==1&&y==1)?400000:0);

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

    return 0;
}





Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#define REP(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

const int INF = 1e7;

int nRow, nCol, limit;
set<int> walls;
inline int encode(int i, int j) {
  return i*nCol + j;
}
inline bool isWall(int i, int j) {
  if(i < 0 || j < 0 || i >= nRow || j >= nCol) return true;
  return walls.count(encode(i, j)) != 0;
}
map<int,int> dists;
inline int getDist(int i, int j) {
  int key = encode(i, j);
  if(dists.count(key) == 0) {
    return INF;
  } else {
    return dists[key];
  }
}

const int DI[4] = {1, 0, -1, 0};
const int DJ[4] = {0, 1, 0, -1};

char buf[1000000+10];
int main(void) {
  scanf("%d%d%d", &nRow, &nCol, &limit);
  int si, sj, gi, gj;
  scanf("%d%d%d%d", &si, &sj, &gi, &gj);
  --si;
  --sj;
  --gi;
  --gj;
  REP(i, nRow) {
    scanf("%s", buf);
    REP(j, nCol) {
      if(buf[j] == '@') {
        walls.insert(encode(i, j));
      }
    }
  }
  queue<pair<int,int> > q;
  dists[encode(si, sj)] = 0;
  q.push(make_pair(si, sj));
  while(!q.empty()) {
    pair<int,int> cur = q.front(); q.pop();
    int ci = cur.first;
    int cj = cur.second;
    int curDist = getDist(ci, cj);
    REP(d, 4) {
      REP(k, limit) {
        int ni = ci + DI[d] * (k+1);
        int nj = cj + DJ[d] * (k+1);
        if(isWall(ni, nj)) {
          break;
        }
        int dist = getDist(ni, nj);
        if(dist <= curDist) {
          break;
        }
        dists[encode(ni, nj)] = curDist + 1;
        if(dist == INF) {
          q.push(make_pair(ni, nj));
        }
      }
    }
  }
  int res = getDist(gi, gj);
  cout << (res == INF ? -1 : res) << endl;
  return 0;
}


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

int main(){
	int x, y, t;

	while (1){
		cin >> x >> y;
		if (x == 0 && y == 0) break;
		if (x > y){
			t = x; x = y; y = t;
		}
		cout << x << " " << y << endl;
	}

	return 0;
}


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

const int a[3] = {0, 1, 2};
const int b[3] = {1, 2, 0};
const int c[3] = {2, 0, 1};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n;
    cin >> n;
    vector<vector<char> > s(3, vector<char>(n));
    REP(i, 3) REP(j, n) cin >> s[i][j];

    int cnt = 0;
    REP(j, n) {
        REP(i, 3)
            if (s[a[i]][j] == s[b[i]][j] && s[b[i]][j] != s[c[i]][j])
                cnt++;
        if (s[0][j] != s[1][j] && s[0][j] != s[2][j] && s[1][j] != s[2][j])
            cnt += 2;
    }

    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
signed main(){
  int n;
  while(cin>>n,n){
    vector<P> vp(n);
    for(int i=0;i<n;i++) cin>>vp[i].first>>vp[i].second;
    sort(vp.rbegin(),vp.rend());
    int sum=0,res=0;
    for(int i=0;i<n;i++) sum+=vp[i].first;
    for(int i=0;i<n;i++) res+=vp[i].second;
    if(sum<vp[0].first*2){
      bool dp[1111];
      memset(dp,0,sizeof(dp));
      dp[0]=1;
      for(int i=1;i<n;i++){
	for(int j=1111;j>=vp[i].second;j--){
	  if(dp[j-vp[i].second]) dp[j]=1;
	}
      }
      int ans=0;
      for(int i=0;i<=vp[0].first*2-sum;i++)
	if(dp[i]) ans=i;
      cout<<vp[0].first*2+res-ans<<endl;
    }else{
      cout<<sum+res<<endl;
    }
  }
  return 0;
}

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

int main() {
	int n,k,a[1000];
	cin >> n>>k;
	for(int i=0; i<n; i++) cin>>a[i];
	sort(a, a+n);
	int sum=0;
	for(int i=0; i<k; i++) sum+=a[i];
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3628
<?php

    fscanf(STDIN,"%d",$N);
    $list = explode(" ", trim(fgets(STDIN)));
    $count=0;
    $countgu=0;

   foreach($list as $a){
       if($a%2==0){
           $countgu++;
           if($a%3==0){
             $count++;
           }elseif($a%5==0){
               $count++;
           }else{
           break;
           }
       }
   }

    if($count==$countgu){
        echo "APPROVED\n";
    }else{
        echo "DENIED\n";
    }

Measured memory_bytes: 4604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main(){
	int N;
	cin>>N;
	ll ans=1;
	for(ll i=1;i<=N;i++){
		(ans*=i)%=MOD;
	}
	cout<<ans<<endl;

}

Measured memory_bytes: 256