akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int x=sc.nextInt();
		
		int a[]=new int [n];
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
		}
		//Arrays.sort(a);
		long sum=0;
		for(int i=0;i<n-1;i++){
			if((a[i]+a[i+1])>x){
				int m=a[i]+a[i+1]-x;
				int b=a[i+1]-m;
				sum+=m;
				if(b<0){
					a[i+1]=0;
					a[i]+=b;
				}else{
					a[i+1]-=m;
				}
				
			}
		}
		//System.out.println(Arrays.toString(a));
		System.out.println(sum);
		
	}
}


Measured memory_bytes: 51692
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
using pp=pair<int,pair<int,int>>;
#define MAX 200003
#define MOD 1000000007
#define INF 1000000000000000000

int main(){
  int A;
  cin>>A;
  cout<<A+A*A+A*A*A<<endl;
}


Measured memory_bytes: 3632
def pr(n):
    c=0
    for i in range(2,int(n**(1/2))+1):
        if n%i==0:
            break
        else:c+=1
    if c==int(n**(1/2))-1:
        return 1
def sol(n):
    s=n
    while pr(s)!=1:
        s+=1
    return s
n= int(input())
print(sol(n))


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

int main() {

    int N;

    vector<int> n_vec;

    

    cin >> N ;

    for (int i = 1; i <= N; i++){

        n_vec.push_back(i);
    }

    
    int max_n = 0;
    int max_cnt = 0;;

    for (int i = 0; i < n_vec.size(); i++){

        int cnt = 0;
        int t = n_vec.at(i);
        do
        {
         t = t / 2;
         cnt++;
         if (t == 0){
             break;
         }   

        } while (true);

        if (max_cnt < cnt){
            max_cnt = cnt;
            max_n = n_vec.at(i);

        }

    }

    cout << max_n << endl;




}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define forr(i,a,n)	for(int i=a; i<n; i++)
#define loop(i,a,n)	for(int i=a; i>=n; i--)

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

	int a;
	cin>>a;
	int b[a];
	forr(i,0,a)
		cin>>b[i];
	sort(b,b+a);
	long long int c=(b[0]+b[a-1])/2,ct=0,d[101]={},l=0;
	//cout<<c<<' ';
	forr(i,1,100)
	{ct=0;
		forr(j,0,a)
		{
			ct+=(pow((abs(i-b[j])),2));
		}
		//cout<<ct<<'\n';
		d[l++]=ct;
	}
	sort(d,d+l);
	cout<<d[0];
	//forr(i,0,l)	cout<<d[i]<<" ";
	
	return 0;	
}

Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    if i == n-1 and i+1 == p[i]:
        ans += 1
    elif i+1 == p[i]:
        temp = p[i]
        p[i] = p[i+1]
        p[i+1] = temp
        ans += 1


print(ans)


Measured memory_bytes: 14008
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point {
  public:
  double x, y;
  Point(double x = 0, double y = 0): x(x), y(y) {}
  Point operator + (Point p) { return Point(x + p.x, y + p.y); }
  Point operator - (Point p) { return Point(x - p.x, y - p.y); }
  Point operator * (double a) { return Point(a * x, a * y); }
  Point operator / (double a) { return Point(x / a, y / a); }
  double norm() { return x*x + y*y; }
  double abs() { return pow(norm(), 0.5); }
  bool operator < (const Point &p) const {
    return x != p.x ? x < p.x : y < p.y;
  }
};
typedef Point Vector;
struct Segment {
  Point p1, p2;
};
double dot(Vector a, Vector b) {
  return a.x * b.x + a.y * b.y;
}
Point project(Segment s, Point p) {
  Vector base = s.p2 - s.p1;
  double r = dot(p-s.p1, base) / base.norm();
  return s.p1 + base * r;
}
Point reflect(Segment s, Point p) {
  return p + (project(s, p) - p) * 2.0;
}
double cross(Point a, Point b) {
  return a.x*b.y - a.y*b.x;
}
ll ccw(Point p0, Point p1, Point p2) {
  Vector a = p1 - p0, b = p2 - p0;
  if (cross(a, b) > EPS) return 1;
  if (cross(a, b) < -EPS) return -1;
  if (dot(a, b) < -EPS) return 2;
  if (a.norm() < b.norm()) return -2;
  return 0;
}
bool intersect(Point p1, Point p2, Point p3, Point p4) {
  return ccw(p1, p2, p3)*ccw(p1, p2, p4)<=0 && ccw(p3, p4, p1)*ccw(p3, p4, p2)<=0;
}

int main() {
  ll n;
  cin >> n;
  Point p1, p2, p3, p4;
  rep(i, n) {
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y;
    if (intersect(p1, p2, p3, p4)) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }
}


Measured memory_bytes: 3220
// https://ei1333.github.io/luzhiled/
// http://beet-aizu.hatenablog.com/entry/2017/01/04/113233
// http://www.prefield.com/algorithm/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vd = vector<ld>;
using vs = vector<string>;
using vb = vector<bool>;
using vvl = vector<vector<ll>>;
using vvd = vector<vector<ld>>;
using vvs = vector<vector<string>>;
using vvb = vector<vector<bool>>;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;
using Graph = vector<vector<ll>>;
const ll INF = 1LL << 60;
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
#define tl 1'000'000'007
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REREP(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define REFOR(i, n, a) for (ll i = n; i >= a; i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define debug cout << "line : " << __LINE__ << " debug" << endl;
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ind(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << endl;} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#define in1(A) REP(i,A.size()) in(A[i]);
#define in2(A,B) REP(i,A.size()) in(A[i],B[i]);
#define in3(s,t,u) REP(i,sz(s)){in(s[i] , t[i] , u[i]);}
#define in4(s,t,u,v) REP(i,sz(s)){in(s[i] , t[i] , u[i] , v[i]);}
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
struct Point{ ld x,y; };
ld dist(Point a, Point b){return sqrt(abs(a.x-b.x)*abs(a.x-b.x)+abs(a.y-b.y)*abs(a.y-b.y));} // ２点間の距離 
ll gcd(ll a, ll b) { return b != 0 ? gcd(b, a % b) : a; }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b;} 
ll fact(ll n){ if(n < 2) return 1; return (n * fact(n-1))%tl; } //階乗
inline ll updiv(ll a,ll b){ return (a + b - 1) / b; } //切り上げ
template<typename T,typename U>ll ceil(T a,U b){return (a + b - 1) / b;}
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); }
//-------------------------------------------------------------------------------------------------
int main(){
    init();
    inl(k);
    queue<ll> T;
    REP(i,9) T.push(i+1);
    ll x;
    REP(i,k){
        x= T.front();
        T.pop();
        if(x%10) T.push(10*x+(x%10)-1);
        T.push(10*x+x%10);
        if(x%10!=9) T.push(10*x+(x%10)+1);
        
    }
    out(x);
}

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

using namespace std;

#define Rep(i,a,b)  for (int i=(a);i<(b);i++)
#define rep(i,n)    for (int i=0;i<(n);i++)
#define all(x)      (x).begin(), (x).end()

#define ll long long

bool dfs(vector<pair<int, int>> road, int town) {
	bool ret = false;
	if (road.size() == 0)
		return true;
	rep (i, road.size()) {
		if (road[i].first == town) {
			vector<pair<int, int>> new_road = road;
			new_road.erase(new_road.begin() + i);
			ret = dfs(new_road, road[i].second);
			if (ret == true)
				break;
		}
		if (road[i].second == town) {
			vector<pair<int, int>> new_road = road;
			new_road.erase(new_road.begin() + i);
			ret = dfs(new_road, road[i].first);
			if (ret == true)
				break;
		}
	}
	return ret;
}

bool solve(vector<pair<int, int>> road) {
	rep (i, 4) {
		if (dfs(road, i + 1))
			return true;
	}
	return false;
}

int main()
{
	vector<pair<int, int>> road;
	int a, b;

	rep (i, 3) {
		cin >> a >> b;
		road.push_back(make_pair(a, b));
	}

	if (solve(road))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}


Measured memory_bytes: 256
from collections import defaultdict
N = int(input())


m = defaultdict(int)

for i in range(1, N+1):
    s = str(i)
    if s[-1] != "0":
        m[s[0] + s[-1]] += 1

ans = 0
for i in range(1, N+1):
    s = str(i)
    ans += m[s[-1] + s[0]]


print(ans)


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

void Main() {
	int S, W;
	cin >> S >> W;
	if (S <= W) {
		cout << "unsafe" << endl;
	}
	else {
		cout << "safe" << endl;
	}
}


int main() {
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int a,b,c,count=3;
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);cout.tie(NULL);
 cin>>a>>b>>c;
 if(a==b)
 {
     count--;
     if(a==c)
     count--;
 }
 else if(b==c)
 {
     count--;
     if(a==c)
     count--;
 }
 else if(a==c)
 {
     count--;
     if(a==b)
     count--;
 }
 cout<<count;

	return 0;
}

Measured memory_bytes: 256
a = []
3.times do |i|
  a[i] = gets.chomp.split.map(&:to_i)
end
n = gets.chomp.to_i
b = []
n.times do
  b.push(gets.chomp.to_i)
end
c = []
3.times do |i|
  c[i] = Array.new(3, false)
end
3.times do |i|
  3.times do |k|
    if b.include?(a[i][k])
      c[i][k] = true
    end
  end
end
3.times do |i|
  if c[i].all?
    puts 'Yes'
    exit
  end
end
3.times do |i|
  if c[0][i] && c[1][i] && c[2][i]
    puts 'Yes'
    exit
  end
end
if (c[0][0] && c[1][1] && c[2][2]) || (c[2][0] && c[1][1] && c[0][2])
  puts 'Yes'
  exit
end
puts 'No'


Measured memory_bytes: 3836
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
typedef long long LL;
typedef long double Lf;
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
#define rep(i,n)Rep(i,0,n)
#define Ma(x,y) ((x)>(y)?(x):(y))
#define mi(x,y) ((x)<(y)?(x):(y))
#define N 100001
#define MOD 1000000007
int acs(const void* a, const void* b) { return *(int*)a - *(int*)b; }//1,2,3,4
int des(const void* a, const void* b) { return *(int*)b - *(int*)a; }//9,8,7,6
int cmp_char(const void* a, const void* b) { return *(char*)a - *(char*)b; }//a,b,c,d
int cmp_str(const void* a, const void* b) { return strcmp(*(const char**)a, *(const char**)b); }//aaa,aab
//temmie_のsnippet

int main() {
	LL a, b, v, w, t, len,vel;
	scanf("%lld%lld%lld%lld%lld", &a, &v, &b, &w, &t);
	len = Ma(b - a, a - b);
	vel = Ma(v - w, w - v);
	if (len <= vel*t&&v>w)printf("YES"); else printf("NO");

	return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
map<int, int>mp;
int main(){
	int n, m;
	cin>> n >> m;
	int a, b;
	for(int i = 1; i <= m; ++i){
		scanf("%d %d", &a, &b);
		if(a == 1){
			if(mp[b] == n){
				cout<<"POSSIBLE"<<endl;
				return 0;
			}
			mp[b] = 1;
		}
		if(b == 1){
			if(mp[a] == n){
				cout<<"POSSIBLE"<<endl;
				return 0;
			}
			mp[a] = 1;
		}
		if(a == n){
			if(mp[b] == 1){
				cout<<"POSSIBLE"<<endl;
				return 0;
			}
			mp[b] = n;
		}
		if(b == n){
			if(mp[a] == 1){
				cout<<"POSSIBLE"<<endl;
				return 0;
			}
			mp[a] = n;
		}
	}
	cout<<"IMPOSSIBLE"<<endl;
	return 0;
}

Measured memory_bytes: 9600
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(){T ret;cin>>ret;return ret;}
template<typename T=ll>inline auto vec2(size_t h,size_t w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
inline void setp(int n){cout<<fixed<<setprecision(n);}
inline void delnl(){cin.ignore(numeric_limits<streamsize>::max(),'\n');}

int main()
{
    ll n=in();
    vector<ll>l(n);for(auto&i:l)i=in();
    sort(l.begin(),l.end());
    ll ans=0;
    for(ll i=0;i<n;++i){
        for(ll j=0;j<n;++j){
            if(i!=j){
                ll ui=upper_bound(l.begin(),l.end(),abs(l[i]-l[j]))-l.begin();
                ll li=lower_bound(l.begin(),l.end(),l[i]+l[j])-l.begin();
                ll len=li-ui;
                if(ui<=i&&i<li)--len;
                if(ui<=j&&j<li)--len;
                ans+=len;
            }
        }
    }
    cout<<ans/6<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }

int main()
{
  ll N, x=0;
  cin >> N;
  vector<ll> A(N), ans(N);
  rep(i, N) {cin >> A[i]; A[i] *= 2;}

  rep(i, N){
    x = A[i] - x;
  }
  x /= 2; 

  rep(i, N){ 
    cout << x << " ";
    x = A[i] - x;
  }
}

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

int main(){
    int n, m;
    double total=0;
    std::cin>>n>>m;
    int a[n];
    std::string result;
    for(int i=0;i<n;++i){
        std::cin>>a[i];
        total+=a[i];
    }

    total=total*(1/(4*(double)m));
    for(int i=0;i<n;++i){
        if(a[i]>=total) m--;
    }

    result=(m<=0)?"Yes":"No";
    std::cout<<result;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int LinerSearch(int*,int,int);

int main(){
  int i,n,j,key,S[10000],t=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&j);
  for(i=0;i<j;i++){
    scanf("%d",&key);
    if(LinerSearch(S,n,key)==1)
      t++;
  }
  printf("%d\n",t);
  return 0;
}

int LinerSearch(int *S,int n,int key){
  int i=0;
  S[n] = key;
  while(S[i]!=key){
    i++;
    if(i==n)return 0;
  }
  return 1;
}



Measured memory_bytes: 2108
import Control.Applicative
import Data.List
import Data.Char

getInt :: IO Int
getInt = (\a -> read a :: Int) <$> getLine

getIntArray :: IO [Int]
getIntArray = ((map (\a -> read a :: Int)) . words) <$> getLine

getStrArray :: Int -> IO [String]
getStrArray 0 = return [] :: IO [String]
getStrArray n = (:) <$> getLine <*> (getStrArray (n - 1))

to2018 :: String -> String
to2018 (_:_:_:_:rst) = "2018" ++ rst

main = do
    print =<< (`div` 3) <$> getInt


Measured memory_bytes: 508
#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
#define ll long long
#define PI 3.141592653589
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EPS 1e-7
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
const ll MOD = 1e9+7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
ll fast_power(ll x, ll p){
    ll res = 1;
    while(p > 0){
        if(p & 1){
            res = (res * x);
        }
        p = p >> 1;
        x = (x*x);
    }
    return res;
}
string s,t;
int dp[3005][3005];

int solve(int i, int j) {
    if (i == s.length() || j == t.length())
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
    int ans = 0;
    if (s[i] == t[j]) {
        return dp[i][j] = solve(i + 1, j + 1) + 1;
    }
    else
        return dp[i][j] = max(solve(i + 1,j), solve(i, j + 1));
}

void print(int i, int j) {
    if (i == s.length() || j == t.length())
        return;
    if (s[i] == t[j]) {
        cout << s[i];
        print (i + 1, j + 1);
        return;
    }
    if (dp[i + 1][j] > dp[i][j + 1])
        print (i + 1,j);
    else
        print (i, j + 1);
}

int main() {
    IO;
    cin >> s >> t;

    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = t.length() - 1; j >= 0; j--) {
            if (s[i] == t[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    print(0,0);
    return 0;
}


Measured memory_bytes: 35712
#include<stdio.h>
int main(void){
	int N,M,A,i,S=0;
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++){
		scanf("%d",&A);
		S=S+A;
	}
	if(S<=N){
		printf("%d",N-S);
	}
	if(S>N){
		printf("-1");
	}
	return 0;
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for( int i=a; i<b; i++)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<pii>vpi;
void solve(){
    ll H,W;
    cin>>H>>W;
    vector<vector<char>> G(H,vector<char>(W));
    string S;
    for(ll i =0;i<H;i++){
        cin>>S;
        for(ll j =0;S[j];j++){
            G[i][j] = S[j];
        }
    }
    vvll dp(H,vll(W,0));
    dp[H-1][W-1] = 1;
    for(ll i = H-1;i>=0;i--){
        for(ll j = W-1;j>=0;j--){
            if(G[i][j]=='.'){
                // dp[i][j] = dp[i][j+1] + dp[i+1][j];
                if(j!=W-1){
                    dp[i][j]+=dp[i][j+1];
                }
                if(i!=H-1){
                    dp[i][j]+=dp[i+1][j];
                }
                dp[i][j]%=((ll)1e9) +7;
            }
        }
    }
    cout<<dp[0][0]<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll t;
    t = 1;
    while(t--){
        solve();
    }
}

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

typedef pair<int, int> ii;

int dist[505][505];
bool available[505][505];

int P[250005];

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

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

    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j ++){
            dist[i][j] = min(min(i, N-1-i), min(j, N-1-j));
            //printf("%d ", dist[i][j]);
            available[i][j] = true;
        }
        //printf("\n");
    }

    long long ans = 0;
    for(int z = 0; z < N*N; z ++){
        scanf("%d", &P[z]);
        int x = (P[z]-1)/N;
        int y = (P[z]-1)%N;

        /*printf("input: %d\n", P[z]);

        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j ++){
                printf("%d ", dist[i][j]);
            }
            printf("\n");
        }*/


        ans += dist[x][y];
        available[x][y] = false;

        queue<ii> q;
        for(int k = 0; k < 4; k ++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(dist[nx][ny] > dist[x][y]){
                dist[nx][ny] = dist[x][y];
                q.push(ii(nx, ny));
            }
        }

        q.push(ii(x, y));
        while(!q.empty()){
            ii temp = q.front(); q.pop();
            int x = temp.first;
            int y = temp.second;
            for(int k = 0; k < 4; k ++){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(nx >= 0 && nx < N && ny >= 0 && ny < N){
                    if(dist[nx][ny] > dist[x][y]+available[x][y]){
                        dist[nx][ny] = dist[x][y] + available[x][y];
                        q.push(ii(nx, ny));
                    }
                }
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 5964
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const double PI=acos(-1);
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
#define Rep(i,a,b) for (int i=(a);i<(b);i++)
#define Per(i,a,b) for (int i=(a);i>(b);i--)
#define travel_set(it,a) for (set<int>::iterator (it)=(a).begin();(it)!=(a).end();(it)++)
#define travel_map(it,a) for (map<int>::iterator (it)=(a).begin();(it)!=(a).end();(it)++)
#define travel_vec(it,a) for (vector<int>::iterator (it)=(a).begin();(it)!=(a).end();(it)++)
#define p(x) cout << x << endl;
#define def cout << "find" << endl;
#define what_is(x) cout << #x << " is " << x << endl;
template <class T>T sqr(T x){return x*x;}
template <class T>T alex(T x){return (x>0)?x:-x;}
template <class T>void read(T&x){
	x=0;T f=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if (ch=='-')f=-1,ch=getchar();
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=f;
}

//---------------------------------------------------head---------------------------------------------------

int n;
#define maxn 100005
struct Edge{
	int son[maxn<<1],nxt[maxn<<1],lnk[maxn],tot;
	void add(int x,int y){
		tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
		tot++;son[tot]=x;nxt[tot]=lnk[y];lnk[y]=tot;
	}
}edge;
int cnt[maxn];
int middle;
int f[maxn],g[maxn];
int father[maxn];
bool vis[maxn];
void setfather(int now){
	vis[now]=true;
	for (int j=edge.lnk[now];j;j=edge.nxt[j])
		if (!vis[edge.son[j]]){
			father[edge.son[j]]=now;setfather(edge.son[j]);
		}
}
bool used;
int cwy[maxn];
int d[maxn];
bool check_que(int mid){
	d[0]=0;
	rep(i,1,cwy[0])if (i!=mid)d[++d[0]]=cwy[i];
	rep(i,1,d[0])if (d[i]+d[d[0]-i+1]>middle)return false;
	return true;
}
void dfs(int now){
	for (int j=edge.lnk[now];j;j=edge.nxt[j])if (edge.son[j]!=father[now])
		dfs(edge.son[j]);
	// vector<int>cwy;cwy.clear();
	cwy[0]=0;
	for (int j=edge.lnk[now];j;j=edge.nxt[j])if (edge.son[j]!=father[now]){
		cwy[++cwy[0]]=f[edge.son[j]]+1;
	}
	if (cnt[now])cwy[++cwy[0]]=0;
	sort(cwy+1,cwy+cwy[0]+1);
	if (now==1){
		rep(i,1,cwy[0]/2)if (cwy[i]+cwy[cwy[0]-i+1]>middle)used=false;
	}
	else{
		if (cnt[now]){
			int l=1,r=cwy[0];
			while (l<=r){
				int mid=(l+r)>>1;
				if (check_que(mid))r=mid-1;
				else l=mid+1;
			}
			if (l>cwy[0])used=false;
			else f[now]=cwy[l];
		}
		else{
			int l=1,r=cwy[0];
			while (l<=r){
				int mid=(l+r)>>1;
				if (check_que(mid))r=mid-1;
				else l=mid+1;
			}
			if (l>cwy[0])used=false;
			else f[now]=cwy[l];
		}
	}
	// printf("%d %d %d\n",now,f[now],used);
}
bool check(int mid){
	middle=mid;
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(vis,0,sizeof(vis));
	used=true;dfs(1);return used;
}
int main(){
	read(n);
	Rep(i,1,n){
		int x,y;read(x);read(y);
		edge.add(x,y);
		cnt[x]^=1;cnt[y]^=1;
	}
	int ans=0;
	rep(i,1,n)if (cnt[i])ans++;
	printf("%d ",ans/2);
	int l=1,r=n;setfather(1);
	// printf("%d\n",check(4));
	// printf("%d\n",check(2));
	while (l<=r){
		int mid=(l+r)>>1;
		if (check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);return 0;
}

Measured memory_bytes: 7808
using System;
using System.Linq;

class AtCoderCS {
    static void Main(string[] args) {
        int[] NK = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int N = NK[0], K = NK[1];

        long ans = 0, min = 0, max = 0;
        for (int i = 0; i < N + 1; i++) {
            min += i;
            max += N - i;
            if (i >= K - 1)
                ans += (max - min + 1)% 1000000007;
        }

        Console.WriteLine(ans % 1000000007);
    }
}

Measured memory_bytes: 28308
import java.util.Scanner;

public class Main {

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

	    String a=gs();
	    String b=gs();

        String s=new StringBuffer(b).reverse().toString();
        //System.out.println(2*b-a);
        if (s.equals(a)) {
        	System.out.print("YES");
        }else {
        	System.out.print("NO");
        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
	
	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35600
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		int e = sc.nextInt();
		
		if (a == 0) {
		    System.out.println(1);
		} else if (b == 0) {
		    System.out.println(2);
		} else if (c == 0) {
		    System.out.println(3);
		} else if (d == 0) {
		    System.out.println(4);
		} else if (e == 0) {
		    System.out.println(5);
		}
		    

	}
}

Measured memory_bytes: 35700
#include <stdio.h>

int main()
{
	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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	ll a[3];
	rep(i,3)cin >> a[i];
	
	int ret = 0;
	while(1){
		sort(a,a+3);
		if((a[0]&1)||(a[1]&1)||(a[2]&1)){
			cout << ret << endl;
			return 0;
		}
		a[1] -= a[0];
		a[2] -= a[0];
		a[0] -= a[0];
		if(a[2] == 0){
			puts("-1");
			return 0;
		}
		a[0] = a[1]+a[2];
		a[1] = a[0]-a[1];
		a[2] = a[0]-a[2];
		rep(i,3)a[i] /= 2;
		ret ++;
	}
	cout << ret << endl;
}


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

int main() {
	int ans;
	int n, k;

	cin >> n >> k;
	if( n >= k ) {
		ans = min( n % k, 1 );
	}
	else {
		ans = 1;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn._

object Main extends App {
  val n = readInt()
  val graph = collection.mutable.Seq.fill(n, n)(0)

  for (i <- 1 to n) {
    val input = readLine().split(" ").toList.map(_.toInt)
    val u = input.head - 1
    val k = input(1)
    for (j <- 1 to k) {
      graph(u)(input(1 + j) - 1) = 1
    }
  }

  graph.foreach(g => println(g.mkString(" ")))
}

Measured memory_bytes: 46264
// Template
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <cassert>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, r) for (int i = (l); i < (r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET{IOSET(){cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Main Code
int main() {
    int k;
    cin >> k;
    
    if (!(k & 1)) {
        cout << -1 << "\n";
        return 0;
    }
    if (k % 5 == 0) {
        cout << -1 << "\n";
        return 0;
    }
    
    ll now = 0;
    int ans = 0;
    do {
        now *= 10;
        now += 7;
        now %= k;
        ++ans;
    } while (now);
    
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3648
public class Main{
  static int N = 1000001;
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    int[] p;
    int pn, i, n, sum;

    p = new int[N / 6];
    pn = getprime(p);

    for(;;){
      n = sc.nextInt();
      if(n == 0)break;
      sum = 0;
      for(i = 0;i < n;i++)sum += p[i];
      out.println(sum);
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
  private static int getprime(int[] p){
    int i, j, count = 0;
    boolean[] e;
    e = new boolean[N];
    e[0] = true; e[1] = true;
    for(i = 2;i < N;i++)if(!e[i]){
      p[count++] = i;
      for(j = i * 2;j < N;j+=i)e[j] = true;
    }
    return count;
  }
}

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

using namespace std;


int main() {
    int a = 0, b = 0, c = 0;
    cin >> a >> b >> c;
    vector<int> vec = {};

    vec.push_back(a);
    vec.push_back(b);
    vec.push_back(c);

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

    cout << vec.at(0) + vec.at(1) << endl;
}

Measured memory_bytes: 3564
import heapq
N, K = map(int, input().split())

l = []
for i in range(N):
    a, b = map(int, input().split())
    heapq.heappush(l, (a, b))

k = 0
while K > k:
    a, b = heapq.heappop(l)
    k += b

print(a)




Measured memory_bytes: 16692
#include<bits/stdc++.h>
using namespace std;
const int MX = 1000005;

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(MX);
  for (int &i : a) cin >> i;
  a.push_back(0);
  sort(a.begin(), a.end());
  a.push_back(0);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i - 1] == a[i]) continue;
    for (int j = a[i]; j < MX - 2; j += a[i]) b[j]++;
    if (b[a[i]] == 1 and a[i] != a[i + 1]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 8712
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = set(map(int, input().split()))
    if 1 in n and 9 in n and 7 in n and 4 in n:
        print('YES')
    else:
        print('NO')
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
 
using namespace std;
 
int getArriveTime(int a,int b,int c){
    bool visited[60][60][2];
    memset(visited,false,sizeof(visited));
    int d = 0,st = 1,e = 0;
    for(int i = 0 ; ; i++,d++){
	if(i >= 60){ i %= 60; e++; }
	if(c == i && st) return c+e*60;
	if(visited[i][d][st]) return -1;
	visited[i][d][st] = true;
	if(d >= a && st == 1){ d = 0; st = 0; }
	if(d >= b && st == 0){ d = 0; st = 1; }
    }
    return -1;
}
 
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int res = getArriveTime(a,b,c);
    cout << (res >= 0 ? res : -1) << endl;
    return 0;
}

Measured memory_bytes: 3092
#include <stdio.h>
     
    const long long sup = (long long)1 << 60;
     
    typedef struct {
    	int t, h, cost;
    } edge;
     
    int main()
    {
    	int i, u, w, c, N, M, P;
    	edge e[5001];
    	scanf("%d %d %d", &N, &M, &P);
    	for (i = 0; i < M; i++) {
    		scanf("%d %d %d", &u, &w, &c);
    		e[i].t = u;
    		e[i].h = w;
    		e[i].cost = P - c;
    	}	
     
    	int k, flag[2501] = {};
    	long long min[2501];
    	for (i = 2, min[1] = 0; i <= N; i++) min[i] = sup;
    	for (k = 1, flag[N] = 1; k < N; k++) {
    		for (i = 0; i < M; i++) {
    			u = e[i].t;
    			w = e[i].h;
    			c = e[i].cost;
    			if (min[u] < sup && min[w] > min[u] + c) min[w] = min[u] + c;
    			if (flag[w] == 1) flag[u] = 1;
    		}
    	}
    	for (i = 0; i < M; i++) {
    		u = e[i].t;
    		w = e[i].h;
    		c = e[i].cost;
    		if (min[u] < sup && min[w] > min[u] + c && flag[w] == 1) break;
    	}
    	
    	if (i == M) printf("%lld\n", (min[N] < 0)? -min[N]: 0);
    	else printf("-1\n");
    	fflush(stdout);
    	return 0;
    }

Measured memory_bytes: 1824
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void mergeSort(int *,int,int);
int *S;
int *L;
int *R;
int *sortS;
int n;
int count=0;;
int main(){
  
  int q;
  int flug=0;
  int i,j;
  
  scanf("%d",&n);
  S = (int *)malloc(sizeof(int) * n);

  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
 
  mergeSort(S,0,n);
  

  for(i=0;i<n-1;i++){
    printf("%d ",S[i]);
  }
  
  printf("%d\n%d\n",S[i],count);
}

void merge(int *A,int left,int mid,int right){
  int n1,n2;
  int i,j,k;
 
  n1 = mid - left;
  n2 = right - mid;
  L = (int *)malloc(sizeof(int)*(n1+2));
  R = (int *)malloc(sizeof(int)*(n2+2));
  for (i = 0;i < n1; i++){
    L[i] = A[left + i];
  }
  for (i = 0; i<n2;i++){
    R[i] = A[mid + i];
  }
  L[n1] = 1000000001;
  R[n2] = 1000000001;
  i = 0;
  j = 0;
  for (k = left;k<right;k++){
    count++;
    if(L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
    }else {
      A[k] = R[j];
      j = j + 1;
    }
  }
}


void mergeSort(int *A,int left,int right){
  int mid;
  if(left+1<right){
    mid = (left +right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}



Measured memory_bytes: 64616
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w; cin >> h >> w;
    char s[h][w];
    rep(i, h) rep(j, w) cin >> s[i][j];
    int reached[h][w]; rep(i, h) rep(j, w) reached[i][j] = 0;
    queue<pii> q;
    rep(i, h) {
        rep(j, w) {
            if (s[i][j] == '#') {
                //reached[i][j] = 1;
                q.push({i, j});
                //s[i][j] = 'a';
                
                while (!q.empty()) {
                    int y = q.front().first, x = q.front().second;
                    q.pop();
                    rep(i, 4) {
                        int ny = y + dy[i], nx = x + dx[i];
                        if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
                        if (reached[ny][nx] || s[ny][nx] == '.') continue;
                        reached[ny][nx] = 1;
                        s[ny][nx] = 'a';
                        q.push({ny, nx});

                    }
                }
            }
        }
        
    }
    
    /*
    rep(i, h) {
        rep(j, w) cout << s[i][j] << " ";
        cout << endl;
    }
    */
    rep(i, h) rep(j, w) {
        if (s[i][j] == '#') {
            cout << "No" << endl;
            return 0;
        }
    }
     
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
using System;

namespace _174.c
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var k = int.Parse(Console.ReadLine());
            long a = 7;
            var ans = -1;

            for (var i = 0; i < k; i++)
            {
                if (a % k == 0)
                {
                    ans = i + 1;
                    break;
                }
                a = (a % k) * 10 + 7;
            }

            Console.WriteLine(ans.ToString());
        }
    }
}

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

using namespace std;

#define FOR(v, b, e)   for (int v = (b); v < (e); ++v)

int main () {
	int N;
	cin >> N;
	vector<int> A(N);
	for (auto& a : A) cin >> a;

	int result = 1;
	if (N > 1) {
		int s = A[1] - A[0];
		FOR (i, 2, N) {
			int d = A[i] - A[i - 1];
			if (d == 0) continue;
			if ((d > 0) && (s < 0)) {
				++result;
				s = 0;
				continue;
			}
			if ((d < 0) && (s > 0)) {
				++result;
				s = 0;
				continue;
			}
			s = d;
		}
	}
	cout << result << endl;
}

Measured memory_bytes: 640
def dot(a: complex, b: complex):
    return (a.conjugate() * b).real


def cross(a: complex, b: complex):
    return (a.conjugate() * b).imag


def is_contained(p: complex, g: list):
    flag = False

    for i in range(len(g)):
        a, b = g[i] - p, g[(i + 1) % len(g)] - p
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and 0 < b.imag:
            if cross(a, b) < 0:
                flag = not(flag)
        if cross(a, b) == 0 and dot(a, b) <= 0:
            return 1

    return 2 if flag else 0


n = int(input())
g = [complex(*map(int, input().split())) for _ in range(n)]
q = int(input())

for _ in range(q):
    p = complex(*map(int, input().split()))
    print(is_contained(p, g))



Measured memory_bytes: 5724
#include<stdio.h>

int Min(int a,int b){
    if(a<b) return a;
    return b;
}

int Max(int a,int b){
    if(a>b) return a;
    return b;
}



int main(void){
    int N,A,B;
    scanf("%d %d %d",&N,&A,&B);
    int min,max;
    max=Min(A,B);
    min=Max(0,A+B-N);

    printf("%d %d",max,min);
    

    return 0;
}

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

int main() {
    //input
    string str;
    cin >> str;
    if((str.at(0) == str.at(1) && str.at(1) == str.at(2)) || (str.at(1) == str.at(2) && str.at(2) == str.at(3))){
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
a, b, c, x, y = gets.chomp.split.map(&:to_i)
sum = 0

while x > 0 || y > 0
  if x >= 1 && y >= 1
    if c * 2 < a + b
      x -= 1
      y -= 1
      sum += (c * 2)
    else
      x -= 1
      y -= 1
      sum += (a + b)
    end
  elsif x >= 1
    if c * 2 < a
      x -= 1
      sum += (c * 2)
    else
      x -= 1
      sum += a
    end
  elsif y >= 1
    if c * 2 < b
      y -= 1
      sum += (c * 2)
    else
      y -= 1
      sum += b
    end
  end
end

puts sum

Measured memory_bytes: 1788
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
ll gcd(ll a, ll b)
{
	for (;;)
	{
		if (a < b)swap(a, b);
		a %= b;
		if (a == 0)return b;
	}
}
bool d[101010];
string t[4] = { "dream","dreamer","erase","eraser" };
void no()
{
	printf("NO\n");
	exit(0);
}
int main()
{
	string s;
	cin >> s;
	d[0] = true;
	for (int i = 0; i < s.size(); i++)
	{
		if (!d[i])continue;
		for (int j = 0; j < 4; j++)
		{
			if (i + t[j].size() <= s.size())
			{
				bool f = true;
				for (int k = 0; k < t[j].size(); k++)if (s[i + k] != t[j][k])f = false;
				if (f)d[i + t[j].size()] = true;
			}
		}
	}
	printf((d[s.size()]) ? "YES\n" : "NO\n");
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a,b; cin>>a>>b;
    a+=b;
    ll n = stoll(a);
    for(int i=1; i*i<=n; i++){
        if (n%i==0 && n/i==i){
            cout<<"Yes\n";
            return 0;
        }
    }
    cout<<"No\n";
    return 0;
}


Measured memory_bytes: 256
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, m) revi(i, m, 0)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define allr(n) (n.rbegin(), n.rend())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

int main() {
  int N, K, X, Y;
  ci(N, K, X, Y);
  K >= N ? co(X * N) : co(X * K + Y * (N - K));
}

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

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= b; ++i)
#define fo(i,a,b) for(int i = a; i<= b; ++i)
#define pii pair<ll,ll> 
#define vec(a) vector<a >
#define all(a) a.begin(),a.end()
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

using namespace std;
using ll = long long;
ll md=MD;

ll exp(ll a,ll b){ll r=1ll;while(b>0){if(b&1){r=r*(a%md);r=(r+md)%md;}b>>=1;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll Min(ll a,ll b){if(a<b)return a; return b;}
ll Max(ll a,ll b){if(a>b)return a; return b;}
int32_t main() {
    IOS;

        ll n;
        cin>>n;
        vec(long double) v(n);
        rep(i,0,n-1) cin>>v[i];
        sort(all(v));
        long double ans=(v[0]+v[1])/2;
        rep(i,2,n-1)
        {
        	ans=(ans+v[i])/2;
        }
        cout<<setprecision(6)<<fixed;
        cout<<ans;


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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,x; cin>>n>>m>>x;
	vector<vector<int>>books(n,vector<int>(m));
	vector<int>prices(n);
	for(int i=0;i<n;i++){
		cin>>prices[i];
		for(int j=0;j<m;j++){
			cin>>books[i][j];
		}
	}
	set<set<int>>vis;
	stack<set<int>>stk;
	stack<vector<int>>know;
	for(int i=0;i<n;i++){
		stk.push({i});
		vis.insert({i});
		know.push(books[i]);
	}
	int mn=INT_MAX;
	while(!stk.empty()){
		set<int>cur=stk.top(); stk.pop();
		vector<int>cur_kn = know.top(); know.pop();
		bool all_good=true;
		for(int i=0;i<m;i++){
			if(cur_kn[i]<x){
				all_good=false;
				break;
			}
		}
		if(all_good){
			int cnt=0;
			for(const auto& c:cur){
				cnt += prices[c];
			}
			mn = min(mn, cnt);
		}
		for(int i=0;i<n;i++){
			if(cur.count(i)) continue;
			set<int>cp=cur;
			cp.insert(i);
			if(vis.count(cp)) continue;
			vis.insert(cp);
			vector<int>cp_kn=cur_kn;
			for(int j=0;j<m;j++)
				cp_kn[j] += books[i][j];
			stk.push(cp);
			know.push(cp_kn);
		}
	}
	if(mn == INT_MAX) cout<<-1<<endl;
	else cout<<mn<<endl;
	return 0;
}

Measured memory_bytes: 5188
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int R, G;
    cin >> R >> G;
    cout << 2 * G - R << endl;
    return 0;
}

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

#define Yes(condition) cout << (condition ? "Yes" : "No") << endl

using namespace std;

int main(){
    int n;
    vector<int> prev(3), now(3);
    bool flag = true;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) cin >> now.at(j);
        int d = (now.at(0) - prev.at(0)) - abs(now.at(1) - prev.at(1)) - abs(now.at(2) - prev.at(2));
        if (d < 0 || d % 2) {
            flag = false;
            break;
        }
        prev = now;
    }
    Yes(flag);
    return 0;
}


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

int main(){
    vector<int> a(3);
    int x,y,ans;
    for(int i=0;i<3;i++)cin >> a[i];
    sort(a.begin(),a.end());
    x=a[2]-a[1];y=a[1]-a[0];
 
        if(y%2==0){
        ans=x+y/2;
        }else{
            ans=1+x+(y+1)/2;
        }
    
    cout << ans <<endl;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
l=[['#' for i in range(w+2)] for j in range(2)]
l[1:1]=[list('#'+input()+'#') for i in range(h)]
p=[]
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='#':
      p.append([i,j])
d=[[-1,0],[1,0],[0,-1],[0,1]]
r=-1
while len(p)!=0:
  r+=1
  s=[]
  for i, j in p:
    for di, dj in d:
      di+=i
      dj+=j
      if l[di][dj]=='.':
        l[di][dj]='#'
        s.append([di,dj])
  p=s
print(r)

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

int main(){
//srandom((unsigned long)time(NULL));
//x y z
//(x+y)/2 z
//(x+y+2z)/4
//v大のものほどあとに合成するべき
int n;
cin>>n;
vector<int> v;
for(int i=0;i<n;i++){
    int x;
    cin>>x;
    v.emplace_back(x);
}
sort(v.begin(),v.end());
double ans=v[0];
for(int i=1;i<n;i++){
    ans=(ans+v[i])/2.0;
}
cout<<fixed<<setprecision(6)<<ans<<endl;


return 0;
}

Measured memory_bytes: 256
a, b, c = map(int, input().split())
h = max(a, b, c)
s = a + b + c
ans = 0
if h % 2 == s % 2:
  ans = (h * 3 - s) // 2
else:
  ans = ((h + 1) * 3 - s) // 2
print(ans)

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

const int N = 200005;

int n, m, k;
long long a[N], b[N];

int solve() {
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
    a[i] += a[i-1];
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%lld", &b[i]);
    b[i] += b[i-1];
  }

  int ans = 0;
  for (int i = 0; i <= n; ++i) {
    if (a[i] > k) break;
    // cerr << k - a[i] << " " << (upper_bound(b, b + m + 1, k - a[i]) - b - 1) << endl;
    ans = max(ans, i + (int) (upper_bound(b, b + m + 1, k - a[i]) - b - 1));
  }
  printf("%d\n", ans);
  return 0;
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  while (t--) solve();
  return 0;
}


Measured memory_bytes: 6948
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

li.sort()

point = 1
lin = [1,n]
for i in range(m):
    lin = [max(lin[0],li[i][0]),min(lin[1],li[i][1])]
    if lin[1]-lin[0] <= 0:
        point += 1
        lin = li[i]
print(point)

Measured memory_bytes: 27872