akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)


int main(){
    int n, m;
    cin >> n >> m;
    map<int, int> mp;
    priority_queue<pii> q;
    rep(i, m){
        int a, b;
        cin >> a >> b;
        mp[a] += b;
        q.push(make_pair(mp[a], -a));
        while(true){
            pii p = q.top();
            if(mp[-p.second] == p.first){
                cout << -p.second << " " << p.first << endl;
                break;
            }
            q.pop();
        }
    }
}

Measured memory_bytes: 6256
import math
N, A, B, C, D = map(int, input().split(' '))
# 10 3 100 5 180


a_count = math.ceil(N/A)
c_count = math.ceil(N/C)

a_cost = a_count * B
c_cost = c_count * D

print(min([a_cost, c_cost]))


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

int main(){
    int a,b,k;
    cin>>a>>b>>k;
    vector<int> ans;
    if(b-a+1<=k*2){
        for(int i=0;i<=b-a;i++){
            cout<<a+i<<endl;
        }
        return 0;
    }
    else{
        for(int i=0;i<k;i++){
            ans.push_back(a+i);
            ans.push_back(b-i);
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

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

typedef long long ll;

void output() { std::cout << std::endl; }
void input() {}

template <template <class...> class Template, class Type>
struct is_template : std::false_type {};
template <template <class...> class Template, class... Args>
struct is_template<Template, Template<Args...>> : std::true_type {};

template <class T> using is_vector = is_template<std::vector, T>;

// template <class T> using is_list = is_template<std::list, T>;

// template <class T> using is_map = is_template<std::map, T>;

template <class Head, class... Tail> void input(Head &&head, Tail &&... tail) {
  std::cin >> head;

  input(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail> void output(Head &&head, Tail &&... tail) {
  std::cout << head;
  if (sizeof...(tail))
    std::cout << " ";

  output(std::forward<Tail>(tail)...);
}

template <class... Tail> void input(std::vector<ll> &&head, Tail &&... tail) {
  std::for_each(head.begin(), head.end(), [](int &elem) { std::cin >> elem; });

  input(std::forward<Tail>(tail)...);
}
template <class... Tail> void output(std::vector<ll> &&head, Tail &&... tail) {
  bool first = true;
  for (int &elem : head) {
    if (!first)
      printf(" ");
    std::cout << elem;
    first = false;
  }
  if (sizeof...(tail))
    std::cout << " ";

  output(std::forward<Tail>(tail)...);
}

int main() {
  ll a, b;
  input(a, b);
  output(a * b, (a + b) * 2);

  return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1000000007;
char S[210][210];
vector<int> g[210];
int depth[210];
queue<int> que;
bool bo=false;
int M;

void add_edge(int u,int v){g[u].push_back(v); g[v].push_back(u);}

void bfs(int n){
  que.push(n);
  while(que.size()){
    int w=que.front(); que.pop();
    for(int j=0;j<g[w].size();j++){
      if(depth[g[w][j]]==1000){
        depth[g[w][j]]=depth[w]+1; que.push(g[w][j]);
      }
      else if(abs(depth[g[w][j]]-depth[w])==1){depth[w]+=0;}
      else if(abs(depth[g[w][j]]-depth[w])==0){bo=true; return;}
      M=max(M,depth[g[w][j]]);
    }
  }
}

int main(){
  int N;
  cin >> N;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){cin >> S[i][j];}
  }
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){if(S[i][j]=='1')add_edge(i,j);}
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){depth[j]=1000;}
    M=0;
    depth[i]=0;
    bfs(i);
    if(bo){cout << -1 << endl; return 0;}
    ans=max(ans,M);
    //cout << depth[1] << endl;
  }
  cout << ans+1 << endl;
}

Measured memory_bytes: 512
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        boolean[] dp = new boolean[k * 2 + 1];
        for (int i = 0 ; i < k; i++) {
            for (int j = 0 ; j < n; j ++) {
                dp[i + arr[j]] = dp[i + arr[j]] || !dp[i];
            }
        }
//        debug(dp);
        System.out.println(dp[k] ? "First" : "Second");
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N,A,B,a,b;
  cin >> N >> A >> B;
  a=A*N;
  if(a>=B){
    cout << B << endl;
  }
  else{
    cout << a << endl;
  }
  
 }
   

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct edge{
  int a,b,c;
  bool operator<(const edge &e) const {
    return c < e.c;
  }
};

struct uni{
  int d[111];
  void init(){
    memset(d,-1,sizeof(d));
  }
  int find(int a){ return d[a]<0?a:(d[a]=find(d[a])); }
  void marge(int a,int b){
    a = find(a); b = find(b);
    if( a == b ) return;
    if( d[a] > d[b] ) swap(a,b);
    d[a]+=d[b]; d[b] = a;
  }  
  bool same(int a,int b){
    return find(a) == find(b);
  }
};

int N,M;
int main(){
  while( ~scanf("%d",&N) && N ){
    scanf("%d",&M);
    vector<edge> E;    
    for(int i=0;i<M;i++){
      int a,b,c;
      scanf("%d,%d,%d",&a,&b,&c);
      c/=100; c--;
      E.push_back( (edge){a,b,c} );
    }
    sort(E.begin(),E.end());
    uni U; U.init();
    int res = 0;
    for(int i=0;i<M;i++){
      edge &e=E[i];
      if( U.same(e.a,e.b) ) continue;
      U.marge(e.a,e.b);
      res+=e.c;
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1356
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()

print(3*(N**2))


Measured memory_bytes: 5844
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int dp[N][N];
pair<int,int> pre[N][N];
int main()
{
	ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
	for(int i=1;i<=s.size();i++)
	{
		for(int j=1;j<=t.size();j++)
		{
			if(s[i-1]==t[j-1])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				pre[i][j]=make_pair(i-1,j-1);
			}
			else if(dp[i-1][j]>dp[i][j-1])
			{
				dp[i][j]=dp[i-1][j];
				pre[i][j]=make_pair(i-1,j); 
			}
			else
			{
				dp[i][j]=dp[i][j-1];
				pre[i][j]=make_pair(i,j-1); 
			}
		}
	}
	int sw=s.size(),tw=t.size();
	string ans="";
	while(sw&&tw)
	{
		auto nxt=pre[sw][tw];
		if(nxt.first+1==sw&&nxt.second+1==tw)
			ans+=s[sw-1];
		sw=nxt.first;
		tw=nxt.second;
	}
	for(int i=ans.size()-1;i>=0;i--)
		cout<<ans[i];
	cout<<endl;
	return 0;
}


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

const int MAX = 1e5, MOD = 1000000007;
long long dp[MAX+1][13];

int getDigit(char c) {
    return c - '0';
}

long long int power(long long int x, long long int y){
    long long int res=1;
    if(y<=0)
        return res;
    while(y){
        if(y%2)
            res=(res*x)%13;
        y=y/2;
        x=(x*x)%13;
    }
    return res;
}

int main() {
    string inp;
    cin >> inp;
    int len = inp.length();
    dp[len][0] = 1;

    for(int i = len - 1; i >= 0; --i) {
        long long powr = power(10, len - i - 1);

        for(int j = 0; j < 13; ++j) {
            if(inp[i] != '?') {
                long long digit = getDigit(inp[i]) * powr;
                dp[i][(digit + j) % 13] = (dp[i][(digit + j) % 13] + dp[i+1][j]) % MOD;

            }

            else {
                for(int k = 0; k <= 9; ++k) {
                    long long digit = powr * k;
                    dp[i][(digit + j) % 13] = (dp[i][(digit + j) % 13] + dp[i+1][j]) % MOD;
                }
            }
        }
    }

    cout << dp[0][5];
    return 0;
}


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

int main(){
  string S; cin >> S;
  int n = (int)S.size();
  int ans = 0;
  rep(i,n/2){
    if(S[i] != S[n-1-i]){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

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

int n, h;
vi heights;
int dp[100001];

int calc(int i){
	if(dp[i]!=-1) return dp[i];
	if(i==0) return dp[i]=0;
	if(i==1) return dp[i]=abs(heights[i]-heights[i-1]);
	return dp[i]=min(abs(heights[i]-heights[i-1])+calc(i-1), abs(heights[i]-heights[i-2])+calc(i-2));
}

int main(){
  // freopen("input.txt", "r", stdin); 
  // freopen("output.txt", "w", stdout);
  cin.sync_with_stdio(0); cin.tie();
  cin.exceptions(cin.failbit);

  cin >> n;
  rep(i, 1, n){
  	cin >> h;
  	heights.pb(h);
  }
  rep(i, 0, n) dp[i]=-1;
  cout << calc(n-1);
}

Measured memory_bytes: 7232
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int n;
    cin >> n;
    int a[n];
    rep(i, n) { cin >> a[i]; }

    int index_0 = 0, index_1 = 0;
    int num_0 = 0, num_1 = 0;

    rep(i, n) {
        if (a[i] >= num_0) {
            num_0 = a[i];
            index_0 = i;
        }
    }
    rep(i, n) {
        if (i == index_0) {
            continue;
        }
        if (a[i] >= num_1) {
            num_1 = a[i];
            index_1 = i;
        }
    }

    rep(i, n) {
        if (i != index_0) {
            cout << num_0 << endl;
        } else {
            cout << num_1 << endl;
        }
    }
    return 0;
}

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 2432
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String[] line = scanner.nextLine().split(",");
			int num = Integer.parseInt(line[0]);
			double w = Double.parseDouble(line[1]);
			double h = Double.parseDouble(line[2]);
			double bmi = w / (h * h);
			if (bmi >= 25) {
				System.out.println(num);
			}
		}
	}
}

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

int A[100000];

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  int count = 0;
  for ( int i = 0; i < N - 1; i++ )
  {
    if ( S[i] == 'A' && S[i+1] == 'C' ) {
      count++;
    }
    A[i+1] = count;
  }
  for ( int i = 0; i < Q; i++ )
  {
    int l, r;
    cin >> l >> r;
    int ans = A[r-1] - A[l-1];
    cout << ans << endl;
  }
}

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

using namespace std;
using ll = long long;

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

#define ALL(o) (o).begin(), (o).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T, vector<T>, greater<T> >;

const ll MOD = 1000000007;

V<V<int> > x;
V<int> v;

void initv(){
    REP(i,131) {
        v.push_back(i*i);
    }
}
int dist(int a, int b, int d) {
    int ans = 0;
    REP(i,d) {
        ans += (x[a][i]-x[b][i]) * (x[a][i]-x[b][i]);
    }
    return ans;
}

bool c(int a) {
    REP(i,131) {
        if(a == v[i]) return true;
    }
    return false;
}

int main() {
    int n,d,t;
    initv();

    cin >> n >> d;
    x = V<V<int> >(n, vector<int>(d, 0));
    REP(i,n) {
        REP(j,d) {
            cin >> t;
            x[i][j] = t;
        }
    }

    int dis;
    int cnt = 0;
    REP(i,n) {
        FOR(j,i+1,n) {
            dis = dist(i,j,d);
            if(c(dis)) {
                cnt++;
            }
        }
    }

    cout << cnt << endl;

}



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

class A
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var a = Console.ReadLine().Split().Select(int.Parse).ToList();

		for (int i = 0; i < n; i++)
		{
			var v = a[i];
			var j = a.BinarySearch(0, i, v, null);
			if (j < 0) j = ~j;
			a.RemoveAt(i);
			a.Insert(j, v);
			Console.WriteLine(string.Join(" ", a));
		}
	}
}



Measured memory_bytes: 18200
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int BASE = 100000;

ll N; 
int a[100005], tree[200005], cum[100005];
vector<int> c1[200005], c2[200005];

int get_cum(int idx){
	int sum = 0;
	for(; idx; idx -= (idx & -idx))
		sum += tree[idx];
	return sum;
}

void add_val(int idx, int val, int TN){
	for(; idx <= TN; idx += (idx & -idx))
		tree[idx] += val;
}

ll count_low(int k){
	for(int i = 0; i <= 2 * BASE; i++)
		c1[i].clear(), c2[i].clear();

	ll sum = 0, cur = 0;
	for(int i = 1; i <= N; i++){
		c1[BASE + cur].push_back(i);
		c2[BASE + ((a[i] < k) ? --cur : ++cur)].push_back(i);
		add_val(i, 1, N);
	}

	for(int i = 0 ; i <= 2 * BASE; i++){
		if(!c1[i].size() && !c2[i].size()) continue;
		sort(c1[i].begin(), c1[i].end());
		sort(c2[i].begin(), c2[i].end());

		for(int r : c2[i])
			sum += get_cum(r);
		for(int l : c1[i])
			add_val(l, -1, N);

		ll leven = 0, lodd = 0;
		for(int ri = 0, li = 0; ri < c2[i].size(); ri++){
			while(li < c1[i].size() && c1[i][li] < c2[i][ri]){
				(c1[i][li++] & 1) ? lodd++ : leven++;
			}
			if(c2[i][ri] & 1) sum -= leven;
			else sum -= lodd;
		}
	}
	return sum;
}

int main()
{
	scanf("%lld", &N);
	for(int i = 1; i <= N; i++)
		scanf("%d", &a[i]);

	ll tot = N * (N - 1) / 2 + N;
	int l = 0, r = 1000000000, m, ans = -1;
	while(l <= r){
		m = (l + r) / 2;

		if(count_low(m) >= tot / 2 + 1){
			r = m - 1;
		}
		else ans = m, l = m + 1;
	}
	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 23424
#include <bits/stdc++.h>
using namespace std;
int main() {
	double a, b, h, m;
	double c, hrad, mrad, crad;
	cin >> a >> b >> h >> m;
	hrad = h * M_PI / 6.0 + m * M_PI / (12.0 * 30.0);
	mrad = m * M_PI / 30.0;
	crad = fabs(hrad - mrad);
	if (crad > M_PI) {
		crad -= 2.0 * M_PI;
	}
	c = sqrt(a * a + b * b - 2.0 * a * b * cos(crad));
	cout << fixed << setprecision(20) << c << endl;
}

Measured memory_bytes: 4256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

#define mem(ar,a)       memset(ar,a,sizeof ar)
#define iOS               ios_base::sync_with_stdio(false);cin.tie(NULL); 
#define pb(x)           push_back(x)
#define all(c)          c.begin(), c.end()
#define ff              first
#define ss              second
#define nl              '\n'

int main()
{
    iOS
    long long int n,x,t; cin>>n>>x>>t;
	if(n%x==0){
      cout<<t*(n/x); return 0;
    }
    cout<< t* (ceil)((float)(n)/(float)(x));
}



Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int h,w;
	cin>>h>>w;
	vector<string> g(h);
	int ans=0;
	rep(i,h){
		cin>>g[i];
		rep(j,w){
			if(g[i][j]=='.') ans++;
		}
	}
	vector<vector<int>> dist(h,vector<int>(w,INF));
	auto bfs=[&](){
		Pi s=Pi(0,0);
		Pi go=Pi(h-1,w-1);
		vector<int> dx={1,-1,0,0},dy={0,0,1,-1};
		queue<Pi> que;
		que.push(s);
		dist[s.fi][s.se]=0;
		while(!que.empty()){
			Pi now=que.front();
			que.pop();
			rep(i,4){
				int nx=now.fi+dx[i],ny=now.se+dy[i];
				if(0<=nx && nx<=h-1 && 0<=ny && ny<=w-1){
					if(g[nx][ny]!='#' && dist[nx][ny]==INF){
						dist[nx][ny]=dist[now.fi][now.se]+1;
						que.push(Pi(nx,ny));
					}
				}
			}
		}
		return dist[go.fi][go.se];
	};
	bfs();
	if(dist[h-1][w-1]==INF){
		cout<<-1<<endl;
		return 0;
	}
	cout<<ans-dist[h-1][w-1]-1<<endl;
}

Measured memory_bytes: 256
let content = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', buf => {
  content += buf;
});

process.stdin.on('end', () => {
  let [, nums] = content
    .trim()
    .split('\n')
    .map(line => line.split(' '));
  const bsortResult = bubbleSort(nums);
  console.log(bsortResult.join(' '));
  console.log('Stable');

  const ssortResult = selectionSort(nums);
  const isStable = ssortResult.every((n, i) => n === bsortResult[i]);
  console.log(ssortResult.join(' '));
  console.log(isStable ? 'Stable' : 'Not stable');
});

const compare = (a, b) => {
  const numA = +a[1];
  const numB = +b[1];
  return numA - numB;
};

const selectionSort = nums => {
  nums = nums.slice(0);
  for (let i = 0; i < nums.length; i++) {
    let minIdx = i;
    for (let j = i; j < nums.length; j++) {
      if (compare(nums[minIdx], nums[j]) > 0) {
        minIdx = j;
      }
    }
    
    if (compare(nums[minIdx], nums[i]) !== 0) {
      let tmp = nums[minIdx];
      nums[minIdx] = nums[i];
      nums[i] = tmp;
    }
  }
  
  return nums;
};


const bubbleSort = nums => {
  nums = nums.slice(0);
  let flag = true;
  let min = 1;
  while(flag) {
    flag = false;
    for (let i = nums.length - 1; i >= min; i--) {
      if (compare(nums[i], nums[i - 1]) < 0) {
        flag = true;
        const tmp = nums[i];
        nums[i] = nums[i - 1];
        nums[i - 1] = tmp;
      }
    }
    min++;
  }

  return nums;
};


Measured memory_bytes: 15348
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef pair<int, int>P;
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
typedef vector<vector<ll>> mat;
typedef vector<int> vec;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll qp(ll a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };



void solve() {
    ll a, b, c, d, e , m, n, k, x,l,r,t;
    string s;
    ll ans = 0;
    double dans = 0;
    string sans = "Yes";
    vector<ll> ar;

    cin >> n;


    rep1(i,9){
        ll tmp = i * 111;
        if(tmp >= n){
            ans = tmp;
            break;
        }
    }

    std::cout << ans << endl; 

    // std::cout << sans << endl; 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    solve();
    // stop
        return 0;
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1)
    printEoln();
  if (suc == 2)
    printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

template <class T, class U> void chmax(T &a, U b) {
  if (a < b)
    a = b;
}

template <class T, class U> void chmin(T &a, U b) {
  if (b < a)
    a = b;
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

const int maxN = 8 + 5;
int n, m;
vector<vi> graph(maxN);
int ans;

void dfs(int current, array<bool, maxN> isStayed, int cnt) {
  if (cnt == n) {
    ans++;
    return;
  }
  isStayed[current] = true;
  for (auto &v : graph[current]) {
    if (!isStayed[v])
      dfs(v, isStayed, cnt + 1);
  }
}

signed main() {
  std::cin >> n >> m;
  REP(i, m) {
    int a, b;
    std::cin >> a >> b;
    graph[a].PB(b);
    graph[b].PB(a);
  }
  array<bool, maxN> isStayed;
  dfs(1, isStayed, 1);
  print(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e09 + 7;

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

  ll n;
  cin >> n;

  vector<ll> y; //sqrtまでの約数列挙
	for(ll i = 1; i * i <= n; i++){
		if(n % i == 0) y.pb(i);
	}


  ll a, b, ans = 10000;
  REP(i, y.size()){
    a = 0, b = 0;
    ll z = n / y[i];
    while(y[i]){
      a++;
      y[i] /= 10;
    }
    while(z){
      b++;
      z /= 10;
    }
    ans = min(ans, max(a, b));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

string s;

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  int a,b,v,w,t;
  cin >> a >> v >> b >> w;
  cin >> t;
  int d = abs(a-b);
  if(d<=v*t-w*t){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }

return 0;
}
///....


Measured memory_bytes: 3656
#include <stdio.h>

int main(void)
{
	int uru[3000];
	int x, y;
	int year, year2, flag, fl;
	
	x = 0;
	for (y = 4; y <= 3000; y++) {
		if (y % 4 == 0) {
			if (y % 100 == 0) {
				if (y % 400 == 0) {
					uru[x] = y;
					x++;
				}
			}
			else {
				uru[x] = y;
				x++;
			}
		}
	}
	fl = 0;
	while (1) {
		flag = 0;
		scanf("%d %d", &year, &year2);
		if (year == 0 && year2 == 0) {
			break;
		}
		if (fl != 0) {
			printf("\n");
		}
		for (y = 0; y < x; y++) {
			if (uru[y] >= year && uru[y] <= year2) {
				printf("%d\n", uru[y]);
				flag++;
			}
		}
		if (flag == 0) {
			printf("NA\n");
		}
		fl++;
	}
	
	return (0);
}

Measured memory_bytes: 624
#inport
import sys
import numpy as np
#import itertools as itlt
#from collections import deque

#input 
N,A,B = [int(x) for x in sys.stdin.readline().split()]

num = int(np.floor(N/(A+B)))*A
if (N%(A+B)) >= A:
    num = num + A
else:
    num = num + N%(A+B)

print(int(num))


Measured memory_bytes: 27116
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

void traverse(lint node, vec<vec<lint>>& adj, plint banned_edge, vec<bool>& visited) {
    for (lint neighbor : adj.at(node)) {
        if (visited.at(neighbor)) continue;
        else if ((banned_edge.first == node && banned_edge.second == neighbor) ||
                 (banned_edge.first == neighbor && banned_edge.second == node)) continue;
        visited.at(neighbor) = true;
        traverse(neighbor, adj, banned_edge, visited);
    }
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    lint N, M;
    cin >> N >> M;
    vec<vec<lint>> adj(N, vec<lint>());
    vec<plint> edges;
    range(i, 0, M) {
        lint a, b;
        cin >> a >> b;
        a--; b--;
        adj.at(a).emplace_back(b);
        adj.at(b).emplace_back(a);
        edges.emplace_back(a, b);
    }
    lint ans = 0;
    for (const auto edge : edges) {
        vec<bool> visited(N, false);
        visited.at(0) = true;
        traverse(0, adj, edge, visited);
        if (any_of(visited.begin(), visited.end(),
            [](auto item){return item == false;})) ans += 1;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

using iPair = pair<int, int>;

vector<vector<pair<int, int> > > graph;
vector<int> dist; 

void add_edge(int u, int v, int wt) {
	graph[u].push_back(make_pair(v, wt));
	graph[v].push_back(make_pair(u, wt));
}

int longest_path_in_min_moves(int V, int src) {
	priority_queue<iPair, vector<iPair>, greater<iPair> > pq;
	pq.push(make_pair(0, src));

	dist = vector<int> (V, INT_MAX);
	dist[src] = 0;

	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		for (auto x : graph[u]) {
			int v = x.first;
			int weight = x.second;

			if (dist[v] > dist[u] + weight) {
				dist[v] = dist[u] + weight;
				pq.push(make_pair(dist[v], v));
			}
		}
	}

	int longest = 0;
	for (int i = 0; i < V; ++i) {
		if (dist[i] != INT_MAX) {
			longest = max(longest, dist[i]);
		}
	}

	return longest;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int h, w;
	cin >> h >> w;

	vector<string> maze(h);
	for (int i = 0; i < h; ++i) {
		cin >> maze[i];
	}

	graph = vector<vector<pair<int, int> > > (h * w, vector<pair<int, int> > ());
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (maze[i][j] == '.') {
				if (i > 0 && maze[i - 1][j] == '.') {
					add_edge(i * w + j, (i - 1) * w + j, 1);
				}
				if (i < h - 1 && maze[i + 1][j] == '.') {
					add_edge(i * w + j, (i + 1) * w + j, 1);
				}
				if (j > 0 && maze[i][j - 1] == '.') {
					add_edge(i * w + j, i * w + j - 1, 1);
				}
				if (j < w - 1 && maze[i][j + 1] == '.') {
					add_edge(i * w + j, i * w + j + 1, 1);
				}
			}
		}
	}

	int max_moves = -1;
	for (int i = 0; i < h * w; ++i) {
		max_moves = max(max_moves, longest_path_in_min_moves(h * w, i));
	}

	cout << max_moves << "\n";

	return 0;

}

Measured memory_bytes: 3692
#include<iostream>
using namespace std;
int main()
{
  string a,b,c;
  int m,n;
  cin>>a>>b;
  cin>>m>>n;
  cin>>c;
  if(c==a)
    cout<<m-1<<" "<<n<<endl;
  else if(c==b)
     cout<<m<<" "<<n-1<<endl;
  return 0;
}


Measured memory_bytes: 256
def solve(k, a):
    def gcd(a: int, b: int) -> int:
        if b == 0:
            return a
        else:
            return gcd(b, a % b)

    g = a[0]
    for a_ in a:
        g = gcd(g, a_)

    df = max(a) - k
    return (df >= 0) and (df % g == 0)


if __name__ == '__main__':
    _, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    print('POSSIBLE' if solve(k, a) else 'IMPOSSIBLE')


Measured memory_bytes: 14240
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int w = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		int res = 0;
		if (Math.abs(a - b) < w) {
			res = 0;
		} else {
			res = Math.abs(a - b) - w;
		}
		
		System.out.println(res);
	}
  
    static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}


Measured memory_bytes: 22996
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
    string A, B;

    cin >> A >> B;

    if (A == B) cout << "EQUAL" << endl;
    else if (A.size() < B.size() || A.size() == B.size() && A < B) cout << "LESS" << endl;
    else cout << "GREATER" << endl;

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def rdp_resolve(e: str) -> int:
    def evaluate() -> int:
        nonlocal p
        if e[p] in env:
            p += 1
            return env[e[p - 1]]
        if e[p] == '-':
            p += 1
            return 1 - evaluate()
        p += 1
        lval = evaluate()
        op = e[p]
        p += 1
        rval = evaluate()
        p += 1
        if op == '^':
            return lval ^ rval
        else:
            return lval & rval
    res = 0
    env = {"0": 0, "1": 1}
    for a, b, c, d in itertools.product(range(2), range(2), range(2), range(2)):
        env.update({"a": a, "b": b, "c": c, "d": d})
        p = 0
        res = (res << 1) | evaluate()
    return res

def rdp_init() -> None:
    global rdp_sessions
    rdp_sessions = dict()
    rookies = dict()
    for ch in "01abcd":
        rookies[rdp_resolve(ch)] = 1
    while rookies:
        rdp_sessions.update(rookies)
        entries = dict()
        for k, v in rookies.items():
            candidate = 0xFFFF - k
            weight = v + 1
            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):
                entries[candidate] = weight
        for (k1, v1), (k2, v2) in itertools.product(rookies.items(), rdp_sessions.items()):
            candidate = k1 ^ k2
            weight = v1 + v2 + 3
            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):
                entries[candidate] = weight
            candidate = k1 & k2
            weight = v1 + v2 + 3
            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):
                entries[candidate] = weight
        rookies = entries

        
if __name__ == '__main__':
    rdp_init()
    while True:
        line = input()
        if line == '.':
            break
        print(rdp_sessions[rdp_resolve(line)])

Measured memory_bytes: 7864
unittest
{
	assert( [ "2 60", "10 10", "100 100" ].parse.expand.solve == 110 );
	assert( [ "3 60", "10 10", "10 20", "10 30" ].parse.expand.solve == 60 );
	assert( [ "3 60", "30 10", "30 20", "30 30" ].parse.expand.solve == 50 );
	assert( [ "10 100", "15 23", "20 18", "13 17", "24 12", "18 29", "19 27", "23 21", "18 20", "27 15", "22 25" ].parse.expand.solve == 145 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nt = input.front.split.to!( long[] );
	auto abs = new long[ 2 ][ nt[ 0 ] ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
	}
	return tuple( nt[ 1 ], abs );
}

auto solve( long t, long[ 2 ][] abs )
{
	// 時間内に全部頼んで食べ終われるならそれで良し
	auto mt = 0L;
	auto md = 0L;
	foreach( ab; abs )
	{
		mt += ab[ 0 ];
		md += ab[ 1 ];
	}
	if( mt <= t ) return md;
	
	// dp[ 経過時間 ] = 美味しさの合計
	auto dp = new long[ 1 + t ];
	dp[ 1 .. $ ] = -1;
	foreach( ab; abs.sort() )		// 食べる時間が一番長いやつを最後に持ってくるべきなので必要時間が小さい順に試す
	{
		foreach_reverse( long tt; 0L .. t )
		{
			if( dp[ tt ] < 0 ) continue;
			
			auto k = min( t, tt + ab[ 0 ] );		// ラストオーダーに間に合えば食べる時間がオーバーしても良い
			dp[ k ] = max( dp[ k ], dp[ tt ] + ab[ 1 ] );
		}
	}
	return dp[ $ - 1 ];
}


Measured memory_bytes: 892
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public long getBalance(int[] A, int L, int R, long[][] memo) {
        // System.out.println(String.format("L: %d, R: %d", L, R));
        if (L == R) {
            return A[L];
        }
        if (memo[L][R] != Long.MIN_VALUE) {
            return memo[L][R];
        }
        long left = A[L] - getBalance(A, L + 1, R, memo);
        long right = A[R] - getBalance(A, L, R - 1, memo);
        long maxHere = Math.max(left, right);
        // if (maxHere > memo[L][R]) {
        //     memo[L][R] = maxHere;
        // }
        return memo[L][R] = maxHere;
    }
    public static void main(String[] args)  {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            br.readLine();
          	Main app = new Main();
            String[] split = br.readLine().split(" ");
            int n = split.length;
            int[] A = new int[n];
            for (int i = 0; i < n; i++) {
               A[i] = Integer.parseInt(split[i]); 
            }
            long[][] memo = new long[n + 1][n + 1];
            for (long[] row: memo) {
                Arrays.fill(row, Long.MIN_VALUE);
            }
            long result = app.getBalance(A, 0, n - 1, memo);
            System.out.println(result);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 129488
n = int(input())
x = list(map(int,input().split()))

avg1 = sum(x)//n
avg2 = avg1+1

ans1 = int(sum([(i - avg1)**2 for i in x]))
ans2 = int(sum([(i - avg2)**2 for i in x]))

print(min(ans1,ans2))


Measured memory_bytes: 9188
import sys
N = int(input())
H = list(map(int, input().split()))

H.reverse()

for i in range(N-1):
    if H[i] < H[i+1]:
        if H[i+1] - H[i] == 1:
            H[i+1] -= 1
        else:
            print("No")
            sys.exit(0)
print("Yes")


Measured memory_bytes: 14252
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main()
{
    ll Max=-1;
    ll A,B,C,K,jian;
    while(cin>>A>>B>>C>>K)
    {
        Max=max(A,B);
        Max=max(Max,C);
        if(Max==A) jian=A;
        if(Max==B) jian=B;
        if(Max==C) jian=C;
        ll sum=A+B+C-jian;
        while(K--)
        {
            Max=Max*2;
            //cout<<Max<<endl;
        }
        sum=sum+Max;
        cout<<sum<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int limit = 7369791;
int main()
{
	int M, N;
	bitset< limit + 1 > primeList;
	while(cin >> M >> N, M) {
		primeList.reset();
		for(int i = M; i <= limit; i++) {
			if(primeList[i] == false) {
				N--;
				if(N < 0) {
					cout << i << endl;
					break;
				}
				for(int j = 2 * i; j <= limit; j += i) {primeList[j] = true;}
			}
		}
	}
}


Measured memory_bytes: 3992
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, X = il()
    print('YES' if A > X - B and X >= A else 'NO')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int gcd(int a,int b){
  if(b==0){
    return a;
  }
  else{
    return gcd(b,a%b);
  }
}
int main(){
  int i,j,n;
  cin >> n;
  int a[1000010],b[1000010];
  for(i=0;i<n;i++){
    cin >> a[i];
    b[i]=a[i];
  }
  vector<int> x(1000010);
  for(i=0;i<=1000000;i++){
    x[i]=i;
  }
  for(i=2;i*i<=1000000;i++){
    if(x[i]!=i){
      continue;
    }
    for(j=i*2;j<=1000000;j=j+i){
      x[j]=i;
    }
  }
  int res=0;
  vector<int> c(1000010,0);
  for(i=0;i<n;i++){
    vector<int> d;
    while(a[i]>1){
      if(c[x[a[i]]]==1){
        res=1;
        break;
      }
      d.push_back(x[a[i]]);
      a[i]=a[i]/x[a[i]];
    }
    for(j=0;j<d.size();j++){
      c[d[j]]=1;
    }
  }
  if(res==0){
    cout << "pairwise coprime" << endl;
    return 0;
  }
  for(i=0;i<n;i++){
    a[i]=b[i];
  }
  int ans=gcd(a[0],a[1]);
  for(i=2;i<n;i++){
    ans=gcd(ans,a[i]);
  }
  if(ans==1){
    cout << "setwise coprime" << endl;
  }
  else{
    cout << "not coprime" << endl;
  }
}

Measured memory_bytes: 18764
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 h = 0;

        for(int i=1; i<=b-a; i++){
            h += i;
        }
        System.out.println(h - b);
    }
}

Measured memory_bytes: 22228
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a = a[::-1]

s = [0] * p
for i in range(p, n + 1):
    s.append(s[-1] + a[i - 1])
s = s[1:]

ans = 0
for i in range(1, n + 1):
    if i <= p:
        ans += 1
    else:
        if v - 1 <= p - 1:
            if a[i - 1] + m >= a[p - 1]:
                ans += 1

        else:
            if v - p <= n - i:
                if a[i - 1] + m >= a[p - 1]:
                    ans += 1
            else:
                if a[i - 1] + m < a[p - 1]:
                    continue
                elif a[i-1] * (i - p) >= m * (v - n) + s[i - 2]:
                    ans += 1

print(ans)


Measured memory_bytes: 14484