akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
using namespace std;


template<typename T, typename E>
struct SegmentTree {
    using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    int n, height;
    F f;
    G g;
    H h;
    T ti;
    E ei;
    vector<T> dat;
    vector<E> laz;
    SegmentTree(F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei){}
    void init(int n_){
        n = 1; height = 0;
        while(n < n_) n<<=1, height++;
        dat.assign(2*n, ti);
        laz.assign(2*n, ei);
    }
    void build(const vector<T>& v){
        int n_ = v.size();
        init(n_);
        for(int i = 0;i < n_;i++) dat[n+i] = v[i];
        for(int i = n-1;i;i--) dat[i] = f(dat[(i<<1)|0], dat[(i<<1)|1]);
    }
    inline T reflect(int k){
        return laz[k] == ei ? dat[k] : g(dat[k], laz[k]);
    }
    inline void propagate(int k){
        if(laz[k] == ei) return;
        laz[(k<<1)|0] = h(laz[(k<<1)|0], laz[k]);
        laz[(k<<1)|1] = h(laz[(k<<1)|1], laz[k]);
        dat[k] = reflect(k);
        laz[k] = ei;
    }
    inline void thrust(int k){
        for(int i = height;i;i--) propagate(k>>i);
    }
    inline void recalc(int k){
        while(k>>=1) dat[k] = f(reflect((k<<1)|0), reflect((k<<1)|1));
    }
    //0-indexed [a, b)
    void update(int a, int b, E x){
        if(a >= b) return;
        thrust(a+=n);
        thrust(b+=n-1);
        for(int l = a, r = b+1;l < r;l>>=1, r>>=1){
            if(l&1) laz[l] = h(laz[l], x), l++;
            if(r&1) --r, laz[r] = h(laz[r], x);
        }
        recalc(a);
        recalc(b);
    }
    void setVal(int a, T x){
        thrust(a+=n);
        dat[a] = x; laz[a] = ei;
        recalc(a);
    }
    //0-indexed [a, b)
    T query(int a, int b){
        if(a >= b) return ti;
        thrust(a+=n);
        thrust(b+=n-1);
        T vl = ti, vr = ti;
        for(int l = a, r = b+1;l < r;l>>=1, r>>=1){
            if(l&1) vl = f(vl, reflect(l++));
            if(r&1) vr = f(reflect(--r), vr);
        }
        return f(vl, vr);
    }
    //0-indexed
    T operator[](int i){
        return query(i, i+1);
    }
};


int N, D, A;
pair<int, int> M[200010];
vector<pair<int, int>> v;


signed main(){
    cin >> N >> D >> A;
    for(int i = 0;i < N;i++) cin >> M[i].first >> M[i].second;

    sort(M, M+N);
    for(int i = 0;i < N;i++) v.emplace_back(M[i].second, 1);

    auto f = [](pair<int, int> a, pair<int, int> b){ return make_pair(a.first+b.first, a.second+b.second); };
    auto g = [](pair<int, int> a, int b){ return make_pair(a.first+a.second*b, a.second); };
    auto h = [](int a, int b){ return a+b; };
    SegmentTree<pair<int, int>, int> seg(f, g, h, make_pair(0, 1), 0);
    seg.build(v);

    int i = 0, ans = 0;
    while(i < N){
        int h = seg[i].first;
        int c = ceil((double)h/A);
        ans += c;
        int rm = upper_bound(M, M+N, make_pair(M[i].first+2*D, -1), [](pair<int, int> x, pair<int, int> v){ return x.first < v.first; })-M;
        seg.update(i, rm, -c*A);
        while(i < N and h <= 0) i++, h = seg[i].first;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 20972
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int l = sc.nextInt();
		
		// 計算
		int result = 0;
		int skip = 0;
		if(l >= 0){
		    skip = 1;
		}else if(l + n - 1 <= 0 ){
		    skip = n;
		}else{
		    skip = 0;
		}
		for(int i = 1; i <= n; i++){
		    if(i == skip) continue;
		    result += l + i - 1;
		}

		// 出力
		System.out.println(result);
		
	}
}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll=long long;
#define chmax(x, y) { x = max(x, y); }
#define chmin(x, y) { x = min(x, y); }

int main(){
    ll n,cnt=0;
    cin>>n;
    ll a[200005];
    ll maxnum=0;
    rep(i,n) cin>>a[i];

    rep(i,n){
        chmax(maxnum,a[i]);
        cnt+=maxnum-a[i];
    }
    cout<<cnt<<endl;
    return 0;

}

Measured memory_bytes: 5148
#include <iostream>                                             
using namespace std;                                            
                                                                
int main() {                                                    
  int n;                                                        
  cin >> n;                                                     
  int debt = 100000;                                            
  double interest = 1.05;                                       
  for (int i=1; i<=n; i++) {                                    
    debt *= interest;                                           
    if (debt%1000!=0) {                                         
      debt += 1000-(debt%1000);                                 
    }                                                           
  }                                                             
  cout << debt << endl;                                         
  return 0;                                                     
}                                                               
                                                                
                                                                
                                                                
                                                                
                                                                
                                                                
     

Measured memory_bytes: 2960
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int a, b, c;
    cin >> a >> b >> c;

    if(a == b) cout << c << endl;
    if(b == c) cout << a << endl;
    if(c == a) cout << b << endl;
}
    

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

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 200005;
int n, a[MX], in, vis[MX];
ll k;
vi v;

void dfs (int u) {
	v.pb(u);
	if (vis[a[u]] != -1) {
		in = a[u];
		return;
	}
	vis[a[u]] = vis[u] + 1;
	dfs(a[u]);
}

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

	cin >> n >> k;
	k++;
	forn (i, n) cin >> a[i + 1];

	memset(vis, -1, sizeof(vis));
	vis[1] = 0;
	dfs(1);

	if (k <= v.size()) {
		cout << v[k - 1] << endl;
		return 0;
	}

	k -= vis[in] + 1;
	k %= (int(v.size()) - vis[in]);

	cout << v[vis[in] + k] << endl;

	return 0;
}

Measured memory_bytes: 11720
// ABC 055 D
#include<bits/stdc++.h>
 
using namespace std;
//container util
//------------------------------------------
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).begin(),(c).end(),greater<int>())

#define PB(a) push_back(a)

#define ALL(x) (x).begin(),(x).end()
#define MAX_EL(c) *max_element((c).begin(),(c).end())
#define MIN_EL(c) *min_element((c).begin(),(c).end())
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef string str;
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
int N,A,B,C;
const int INF = 1e9;
VI l;

int dfs(int i,int a,int b,int c,VI l){
  if(i==N)  return min({a,b,c}) > 0 ? abs(a-A)+abs(b-B)+abs(c-C)-30 : INF;
  int ret0 = dfs(i+1,a,b,c,l);
  int ret1 = dfs(i+1,a+l[i],b,c,l)+10;
  int ret2 = dfs(i+1,a,b+l[i],c,l)+10;
  int ret3 = dfs(i+1,a,b,c+l[i],l)+10;
  return min({ret0,ret1,ret2,ret3});
}

int main(){
// magic spell------------------------------
  cin.tie(0);
  ios::sync_with_stdio(false);
//------------------------------------------

  cin >> N >> A >> B >> C;
  VI l(N);
  REP(i,N){
    cin >> l[i];
  }
  cout << dfs(0,0,0,0,l) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main()
{
    double r;
    std::cin >> r;

    printf("%.12lf\n", 2 * r * acos(-1));
}


Measured memory_bytes: 3776
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>

using namespace std;

int main(){
  int N; cin >> N;
  vector<double> p(N);
  for(int i = 0; i < N; i++){ cin >> p[i];}
  
  double dp[3000][3000];
  for(int i = 0; i < 3000; i++){
    for(int j = 0; j < 3000; j++){
      dp[i][j] = 0;}} //初期化
  
  dp[0][0] = 1.0;
  //初期条件
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j <= i; j++){
      dp[i+1][j+1] += dp[i][j] * p[i];
      dp[i+1][j] += dp[i][j] * ( 1.0 - p[i]);}}
  
  double sum = 0.0;
  for(int j = ( N + 1 ) / 2; j <= N; j++){
    sum += dp[N][j];}
  
  cout << setprecision(10) << sum << endl;
  return 0;}
    
  

Measured memory_bytes: 70528
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int n;
vector<pair<ll, ll>> v;

bool cmp(pair<ll, ll> &a, pair<ll, ll> &b) {
    return atan2(a.second, a.first) < atan2(b.second, b.first);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        pair<ll, ll> p; scanf("%lld%lld", &p.first, &p.second);
        if (p.first || p.second) v.pb(p);
    }
    n = (int)v.size();
    sort(v.begin(), v.end(), cmp);
    ll ans = 0;
    for (int i = 0; i < n; i++) { // enum each vector
        int j = i; ll x = 0, y = 0;
        for (int k = 0; k < n; k++) {
            x += v[j].first; y += v[j].second; // just pick all vector and maintain ans
            ans = max(ans, x * x + y * y);
            if (++j == n) j = 0;
        }
    }
    printf("%.15f\n", sqrt(ans));
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<climits>
#include<algorithm>
#define LL long long
using namespace std;

int n,m,d[15][15],sum[15];

int main(void)
{
    while(scanf("%d",&m) && m)
    {
        memset(d,0x3f,sizeof(d));
        int i,j,k;
        for(i=0; i<10; i++)
            d[i][i]=0;
        n=-1;
        while(m--)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            d[a][b]=min(d[a][b],c);
            d[b][a]=d[a][b];
            n=max(n,max(a,b));
        }
        n++;
        for(k=0; k<n; k++)
        {
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                    d[j][i]=d[i][j];
                }
            }
        }
        memset(sum,0,sizeof(sum));
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                sum[i]+=d[i][j];
            }
        }
        int id=0,dis=sum[0];
        for(i=1; i<n; i++)
        {
            if(sum[i]<dis)
            {
                dis=sum[i];
                id=i;
            }
        }
        printf("%d %d\n",id,dis);
    }
    return 0;
}



Measured memory_bytes: 3084
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);


signed main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string X;
	cin >> X;
	int t = 0, s = 0;
	rep(i, X.size()) {
		if (X[i] == 'S')s++;
		else  if (s)s--;
		else t++;
	}
	cout << s + t << endl;
}

Measured memory_bytes: 848
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <stdio.h>
#include <string.h>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS * max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x * x + y * y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;



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

	vector <ll> a(N);
	vector <ll> b(N);
	vector <ll> d(N);

	ll suma = 0;
	ll sumb = 0;
	for (int i = 0; i < N; ++i)
	{
		scanf("%lld", &a[i]);
		suma += a[i];
	}
	for (int i = 0; i < N; ++i)
	{
		scanf("%lld", &b[i]);
		sumb += b[i];
	}

	for (int i = 0; i < N; ++i)
	{
		d[i] = a[i] - b[i];
	}
	sort(d.begin(), d.end());

	ll ans = 0;
	if (suma < sumb)
	{
		ans = -1;
	}
	else
	{
		ll fusoku = 0;

		for (int i = 0; i < N; ++i)
		{
			if (d[i] < 0)
			{
				fusoku -= d[i];
				ans++;
			}
		}

		for (int i=N-1;i>=0;--i)
		{
			if (d[i] > 0 && fusoku > 0)
			{
				if (fusoku >= d[i])
				{
					fusoku -= d[i];
					d[i] = 0;
					ans++;
				}
				else
				{
					d[i] -= fusoku;
					fusoku = 0;
					ans++;
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>

using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define vsort(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end());

const int MOD = 1000000007;
const int INF = INT_MAX;



int main()
{
    int n, d;
    cin >> n >> d;
    int x[n][d];
    rep(i, n){
        rep(j, d){
            cin >> x[i][j];
        }
    }

    int cnt = 0;
    for (int i=0; i < n-1; i++){
        for (int j=i+1; j < n; j++){
            int len = 0;
            for (int k=0; k < d; k++){
                len += (x[i][k]-x[j][k]) * (x[i][k]-x[j][k]);
            }
            int flag = 0;
            for (int k=0; k <= pow(len, 0.5); k++){
                if (k*k == len) flag = 1;
            }
            cnt += flag;
        }
    }

    cout << cnt << endl;

    
    return 0;
}




//              g++ -std=c++1z  

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


int main() {
    int h, w;
    cin >> h >> w;
    vector<string> vec;
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        if (count(s.begin(), s.end(), '.') == s.size()) continue;
        vec.push_back(s);
    }


    for (int j = 0; j < w; j++) {
        bool flag = true;
        for (int i = 0; i < vec.size(); i++) {
            if (vec.at(i).at(j) == '#') flag = false;
        }

        if (flag) {
            for (int i = 0; i < vec.size(); i++) {
                vec.at(i).erase(vec.at(i).begin()+j);
            }
            w--;
            j--;
        }
    }


    for (auto elem : vec) {
        cout << elem << endl;
    }

    return 0;
}


Measured memory_bytes: 256
using static System.Console;

class Program
{
  static void Main(string[] args)
  {
			string[] s = ReadLine().Split(' ');
			int A = int.Parse(s[0]), B = int.Parse(s[1]);
			if ((A > 8) || (B > 8)) WriteLine(":(");
			else WriteLine("Yay!");
  }
}

Measured memory_bytes: 11092
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int insertionSort(vector<int>&a,int g) {
	int ret(0);
	rep(i, g, a.size()) {
		int v = a[i];
		int j = i - g;
		while (j >= 0 && a[j] > v) {
			a[j + g] = a[j];
			ret++;
			j -= g;
		}
		a[j + g] = v;
	}
	return ret;
}
void shellSort(vector<int>&a) {
	vector<int>g;
	for (int n = 1; n <= a.size(); n = 3 * n + 1)g.emplace_back(n);
	reverse(all(g));
	int sum(0);
	cout << g.size() << endl;
	rep(i, 0, g.size()) {
		cout << g[i] << (i == g.size() - 1 ? '\n' : ' ');
		sum += insertionSort(a, g[i]);
	}
	cout << sum << endl;
	rep(i, 0, a.size())cout << a[i] << endl;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> a(N); rep(i, 0, N) { cin >> a[i]; }
	shellSort(a);
	return 0;
}

Measured memory_bytes: 6680
/* ex4_3 KitamoriFumiya */
#include <stdio.h>
 
// 積雪の高さを計算して出力する関数
void snow(int west, int east){
	int difference, snow_height; // difference(西の塔の高さと東の塔の高さの差), snow_height(積雪の高さ)をint型の整数として宣言
	difference = east - west; // differenceを計算
	snow_height = 0; // 積雪の高さは初めは0としておく
	// まず、西の塔の高さを求める
	int level = 1; // 塔の高さは西から1,(1+2),(1+2+3)となっていくので初めのlevel(高さの増加分)は1とする
	// levelがdifferenceより小さい時、積雪の高さをを増加させる
	// ここで求めた積雪の高さは上の方が見えている西の塔の高さ
	while (level < difference){
		snow_height = snow_height + level; // levelの分だけ高さを増加
		level++; // 高さの増加分を1増やす
	}
	snow_height = snow_height - west; // 求めた西の塔の高さから見えている部分を引いて積雪の高さを求める
	printf("%d\n", snow_height); // 積雪の高さを出力
}
 
int main(void){
	int west, east; // west(西の塔の見えている部分の高さ), east(東の塔の見えている部分の高さ)をint型の整数として宣言
	scanf("%d %d", &west, &east); // westとeastを入力
	
	snow(west, east); // 積雪の高さを計算して出力する関数を実行
	
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include<math.h>
#define MAX 500005
#define INFINITY 2000000000

int i,j,k,n;
int S[MAX];
int count = 0;

void merge(int A[], int l, int m, int r){
  int n1, n2;
  n1 = m - l;
  n2 = r - m;
  int L[n1+1], R[n2+1];
  for (i = 0; i < n1; i++)
    L[i] = A[l + i];
  for (i = 0; i < n2; i++)
    R[i] = A[m + i];
  L[n1] = INFINITY;
  R[n2] = INFINITY;
  i = 0;
  j = 0;
  for (k = l; k < r; k++){
    if (L[i] <= R[j]){
      A[k] = L[i];
      i++;
      count++;
    }
    else{
       A[k] = R[j];
       j++;	
       count++;
    }
  }
}

void mergeSort(int A[], int l, int r){
  if (l+1 < r){
  	int m;
    m = (l + r)/2; 
    mergeSort(A, l, m);
    mergeSort(A, m, r);
    merge(A, l, m, r);
  }
}

int main(void){
	scanf("%d ", &n);
	for(i=0; i<n; i++)
		scanf("%d ", &S[i]);
	
	mergeSort(S,0,n);
	
	for (i=0; i<n; i++){
		if (i<n-1)
			printf("%d ", S[i]);
		else printf("%d\n", S[i]);
	}
	printf("%d\n", count);
	
	return 0;
}


Measured memory_bytes: 5596
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
int a[20];
int n,p;
int prod10[21];
int dfs(int x,int up,bool odd,int lsum,int rsum)
{
	if(lsum+rsum+prod10[up*2+odd-x+1]-prod10[up+odd]-prod10[up]+prod10[x-1]<p) return 0;
	if(lsum+rsum-prod10[up*2+odd-x+1]+prod10[up+odd]+prod10[up]-prod10[x-1]>p) return 0;
	if(x==up+1)
	{
		return prod10[odd];
	}
	int ans=0;
	int tot=0;
	for(int i=up*2+odd;i>=up*2+odd-x+1;i--)
		tot*=10,tot+=a[i];
	tot*=prod10[up*2+odd-x];
	int sum[21];
	memset(sum,-1,sizeof(sum));
	for(int i=0;i<=9;i++)
		for(int j=(x==1)?1:0;j<=9;j++)
		{
			if(lsum+prod10[up*2+odd-x]*(i-j)<tot) break;
			if(sum[i-j+10]==-1)
				sum[i-j+10]=dfs(x+1,up,odd,lsum+prod10[up*2+odd-x]*(i-j),rsum+prod10[x-1]*(j-i));
			ans+=sum[i-j+10];
		}
	return ans;
}
signed main()
{
	scanf("%lld",&p);
	int k=0;
	int tmp=p;
	while(tmp) a[++k]=tmp%10,tmp/=10;
	prod10[0]=1;
	for(int i=1;i<=20;i++)
		prod10[i]=prod10[i-1]*10;
	int ans=0;
	for(int i=1;i<=9;i++)
		for(int j=0;j<=1;j++)
			ans+=dfs(1,i,j,0,0);
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1000000
int cost[1000][1000];
int d[1000];
bool used[1000];
int V;

void dijkstra(int s){
 
  d[s] = 0;
  while(true){
    int v = -1;
    for(int u = 0 ; u <= V ; u++){
      if(!used[u] && (v == -1 || d[u] < d[v]))v = u;
    }

    if(v == -1) break;

    used[v] = true;

    for(int u = 0 ; u <= V ; u++ ){
      d[u] = min(d[u], d[v] + cost[v][u]);
    }
  }
}

int main(){
  int u,v,c;
  int ans,ansi;
  int j;
  while( cin >> V, V) {
    int min = 100000000;

    for(int i = 0 ; i <= V ; i++ ){
      for(int j = 0 ; j <= V ; j++ ){
	cost[i][j] = INF;
      }
    }

    for(int i = 0 ; i < V ; i++){
      cin >> v >> u >> c;
      cost[v][u] = c;
      cost[u][v] = c;
    }
    for( j = 0; j < V ; j++){
      fill(d,d + (V+1) , INF);
      fill(used,used + (V+1),false);

      dijkstra(j);
      ans = 0;	
      for(int i = 0 ; i <= V ; i++){
	if(d[i] < INF)ans +=  d[i];
      }
      for(int i = 0 ; i <= V ; i++){

      }
      if(min > ans && ans != 0 ){
	min = ans;
	ansi = j;
      }
    }
    cout << ansi<<" "<< min << endl;
  }

}

Measured memory_bytes: 1216
#pragma GCC optimize("Ofast")
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <iterator>
#include <string.h>

using namespace std;
#ifndef DEBUGING
ostream cnull(NULL);
#define cerr cnull
#endif // !DEBUGING

#define PB push_back
#define MP make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define RFOR(i, b, a) for (int i = b-1; i>=a; --i)
#define FILL(a, b) memset(a, b, sizeof a)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()

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

const int INF = 1000 * 1000 * 1000;
const LL LINF = 1LL * INF * INF;
const int MAX = 100010;
const long double PI = acos(-1.);
const double EPS = 1e-6;
const LL mod = INF + 7;

int n;
PII a[100005];

set<PII> l;
set<PII, greater<PII> > r;
//11/42

int dist(int &x, int i)
{
	if (x >= a[i].first && x <= a[i].second)
	{
		return 0;
	}
	if (x > a[i].second)
	{
		int y = x - a[i].second;
		x = a[i].second;
		return y;
	}
	int y = a[i].first - x;
	x = a[i].first;
	return y;
}

int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> a[i].first >> a[i].second;
	}

	LL best = 0;
	FOR(i, 0, 2)
	{
		bool flag = (bool)i;
		LL ans = 0;
		int st = 0;
		FOR(i, 0, n)
		{
			l.insert(MP(a[i].second, i));
			r.insert(MP(a[i].first, i));
		}

		while (l.size())
		{
			if (flag)
			{
				int id = r.begin()->second;
				//cout << st << ' ' << a[id].first << ' ' << a[id].second << endl;
				int x = dist(st, id);
				ans += x;
				l.erase(MP(a[id].second, id));
				r.erase(MP(a[id].first, id));
			}
			else
			{
				int id = l.begin()->second;
				//cout << st << ' ' << a[id].first << ' ' << a[id].second << endl;
				int x = dist(st, id);
				ans += x;
				l.erase(MP(a[id].second, id));
				r.erase(MP(a[id].first, id));
			}
			flag ^= 1;
		}
		ans += abs(st);

		best = max(best, ans);


	}
	
	cout << best << endl;


	return 0;
}



Measured memory_bytes: 10368
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

#import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  #q = queue.Queue()
  #q.put(i)
  stack = [i]
  #while not q.empty():
  while len(stack)>0:
    #print('v:',visited)
    #p = q.get()
    p = stack.pop()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        #q.put(f)
        stack.append(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)


Measured memory_bytes: 117588
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
ll n, m;
int main()
{
    cin >> n >> m;
    ll h1 = (m % 2 == 0) ? m / 2 : (m / 2 + 1);
    ll h2 = m / 2;
    if (n == 1 || m == 1)
        cout << 1 << endl;

    else if (n & 1)
        cout << (h1 * (n - n / 2) + h2 * (n / 2)) << endl;
    else
        cout << n / 2 * (h1 + h2) << endl;
}

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

using namespace std;

int main()
{
	vector<string> map;
	vector<string> ans;
	string tmp;
	int h, w;
	
	cin >> h >> w;
	
	for (int i = 0; i < h; i++) {
		cin >> tmp;
		map.push_back(tmp);
	}
	
	for (int i = 0; i < h; i++) {
		cout << map[i] << endl << map[i] << endl;
	}
	
	return (0);
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int a, b, c;
		a = scan.nextInt();
		b = scan.nextInt();
		c = scan.nextInt();

		int aki = a - b;

		c -= aki;

		if(c <= 0) {
			c = 0;
		}

		System.out.println(c);
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。ｓ
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param a 基数
	 * @param n 乗数
	 * @param primeNumMod 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myModPow(long a, long n, long primeNumMod) {

		long ans = 1;

		//乗数が0の場合→1
		if (n == 0)
			return 1;

		if (primeNumMod == 0) {
			//modを使わないとき

			while (n > 0) {

				if (n % 2 == 0) {
					//累乗が偶数の時

					a *= a;
					n = n / 2;
				} else {
					//累乗が奇数の時
					ans *= a;
					n--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			while (n > 0) {

				if (n % 2 == 0) {
					//累乗が偶数の時

					a *= myMod(a, primeNumMod);
					n = n / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(a, primeNumMod);
					n--;

				}
			}

			return myMod(ans, primeNumMod);

		}

	}

}


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

#define inf 0x3f3f3f3f
#define INF 1000111000111000111LL
#define mod 1000000007
#define pi acos(-1.0)
#define eps 1e-8
#define endl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define all(cc) (cc).begin(),(cc).end()
using lli = long long int ;
using pii = pair<int, int> ;
using vi = vector<int> ;
using vb = vector<bool> ;
using vvi = vector<vector<int>> ;
using vlli = vector<long long int> ;
using vpii = vector<pair<int, int>> ;

int main()
  {
    ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
    int n, k, x, tot, ans=0 ;
    cin>> n >> k ;
    vi cnt(n+1, 0) ;
    for(int i=0 ; i<n ; i++)
      {
        cin>> x ;
        cnt[x]++ ;
      }
    vpii a ;
    for(int i=1 ; i<=n ; i++)
      if(cnt[i])
        a.pb(mp(cnt[i], i)) ;
    sort(all(a)) ;
    tot=a.size() ;
    if(tot>k)
      {
        x=tot-k ;
        for(int i=0 ; i<x ; i++) ans+=a[i].fi ;
      }
    cout<< ans ;
  }


Measured memory_bytes: 3188
p=lambda x:print(x,end="")
a,b,c,d=map(int,input().split())
l="URDL"
e,f=d-b,c-a
for i in[0,2]:p(l[i]*e+l[i+1]*(f))
for i in[0,2]:p(l[(i+3)%4]+l[i]*(e+1)+l[i+1]*(f+1)+l[(i+2)%4])

Measured memory_bytes: 3064
import sys
n,k=map(int,input().split())
x=list(map(int,input().split()))
left=[]
right=[]
origin=0
for u in x:
    if u<0:
        left.append(abs(u))
    elif u==0:
        origin+=1
    else:
        right.append(u)
left.sort()
k-=origin
if k==0:
    print(0)
    sys.exit()
r=len(right)
l=len(left)
ans=float("inf")
if k<=r:
    ans=right[k-1]
if k<=l:
    ans=min(ans,left[k-1])
for i in range(k-1):
    if i<r and k-i-2<l:
        y=right[i]+left[k-i-2]+min(right[i],left[k-i-2])
        ans=min(ans,y)
print(ans)

Measured memory_bytes: 63000
using System;
using System.Collections.Generic;
class Program
    {
    	static void Main(string[] args)
    	{
            string s = Console.ReadLine();
            int ans = 0;
            int count = 0;
            foreach(char c in s)
            {
                if ("ATCG".Contains(c.ToString())) count++;
                else count = 0;

                if (count > ans) ans = count;
            }
            Console.WriteLine(ans);
        }
    }
    //mcs Main.cs
    //mono Main.exe

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fr(i,n,x) for(int i=0;i<n;i+=x)
#define pb push_back
int main(){
	int l,r,d;
	cin>>l>>r>>d;
	int a=ceil((l*1.0)/d);
	int b=(r/d);
	cout<<b-a+1;
}

Measured memory_bytes: 3560
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5;

int readInt ()
{
    bool minus = false;
    int result = 0;
    char ch;
    ch = getchar();
    while (true)
    {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus = true;
    else result = ch-'0';
    while (true)
    {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus)
        return -result;
    else
        return result;
}
main() {
    string s;
    cin >> s;
    int n = 4;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            puts("Bad");
            return 0;
        }
    }
    puts("Good");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ph push
#define ptc putchar
#define enter putchar('\n')
#define mod 998244353
using namespace std;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef long long lnt;
typedef unsigned long long ull;
inline int read(){
	int x = 0;char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 1) + (x << 3) + c - '0' , c = getchar();
	return x;
}
inline void write(int x){
	if (!x){
       ptc('0');
       return;
	}
	int dg[20] , len = 0;
	while (x) dg[len++] = x % 10 , x /= 10;
	while (len--) ptc(dg[len]+'0');
}
inline void writeln(int x){
	write(x);
	ptc('\n');
}
inline int add(int x,int y){
	x += y;if (x >= mod) x -= mod;
	return x;
}
inline int sub(int x,int y){
	x -= y;if (x < 0) x += mod;
	return x;
}
inline int qpow(int x,int y){
	int res = 1;
	while (y){
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;y >>= 1;
	}
	return res;
}

const int N = 20;


int nodecnt = 0;
int n , lim;
int f[N + 1][1 << N] ;
int last[2] , nxt[N + 1][1 << N][2];

 
int main(){
	scanf("%d%d",&n,&lim);
//	n = 20;lim= 0;
	
	for (int i = 0;i <= n;i++){
		for (int j = 0;j < 1 << i;j++){
			char c = getchar();while (c != '0' && c != '1') c = getchar();
			f[i][j] = c - '0'; 
		}
	}
	
	memset(nxt , -1 , sizeof nxt);
	
	for (int mask = 0;mask < 1 << n;mask++){
		memset(last , -1 , sizeof last);
		int state = 0;
		for (int i = 1;i <= n;i++){
			last[(mask >> (i - 1)) & 1]	= i;
			
			for (int d = 0;d < 2;d++){
				nxt[i][mask][d] = last[d];
//				printf("pos %d Mask %d d %d %d\n",i,mask,d,last[d]);
			}
		}
	}
	
	
	for (int i = 0;i <= n;i++){
		
		for (int j = 1;i + j <= n;j++){
			for (int k = 0;k < 1 << (i + j);k++)
			if (f[i + j][k]){
				for (int d = 0;d < 2;d++){
					if (nxt[j][k][d] != -1){
						int Nxt = nxt[j][k][d];
						if (Nxt == j) continue; 
//						printf("%d %d %d %d\n",i,j,k,Nxt);
						f[i + Nxt][((k >> j) << Nxt) + (k & ((1 << Nxt) - 1))] += f[i + j][k];
					}
				}
				f[i][k >> j] += f[i + j][k]; 
			}
		}
		
		
	}
	
	
	for (int i = n;i >= 0;i--){
		for (int mask = 0;mask < 1 << i;mask++){
//			printf("%d %d %d\n",i,mask,f[i][mask]);
			if (f[i][mask] >= lim){
				for (int d = i;d >= 1;d--) printf("%d",(mask>>(d-1))&1);
				return 0;
			}
		}
	}
	
	
	return 0;
}



Measured memory_bytes: 219392
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;


int main(void){

	long long int sum;
	int max, min, N;
	cin >> N;
	int temp;
	for(int i = 0; i < N; i++){
		cin >> temp;
		if(i == 0){
			sum = temp;
			min = temp;
			max = temp;
		}
		else{
			if(temp > max) max = temp;
			if(temp < min) min = temp;
			sum = sum + temp;
		}
		
	}
	cout << min << " " << max << " " << sum << endl;
	return 0;
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
ll ar[2000007],a,b, test, sum,t,x=0,p,q,y,i,j,k=0,l,cnt;
double ex;
int main()
{
    ll test;
    cin>>a>>b;
    for(i=1; i<=a; i++)
        cin>>ar[i];
    cnt=0;
    ll p;
    for(i=1; i<=b; i++)
        sum+=ar[i];

    cnt=sum;
    p=1;
    k=0;
    for(i=b+1; i<=a; i++)
    {   sum=sum+ar[i]-ar[++k];
        if(sum>=cnt)
        {
            cnt=sum;
            p=i-b+1;
        }
    }
    for(i=p; i<p+b; i++)
    {
        k=ar[i];
        ex+=(1.0*k*(k+1)/2)/k;
    }


    printf("%0.12lf",ex);
    return 0;
}


Measured memory_bytes: 1792
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto nk = readln.split.to!(int[]);
    auto N = nk[0];
    auto K = nk[1];
    int r;
    while (N) {
        ++r;
        N /= K;
    }
    writeln(r);
}

Measured memory_bytes: 256
# encoding:utf-8


def main(s):
	alphabet = "abcdefghijklmnopqrstuvwxyz"
	d = {alphabet[i]:i for i in range(26)}
	if s == "zyxwvutsrqponmlkjihgfedcba":
		print("-1")
	elif len(s) < 26:
		for i in range(26):
			if alphabet[i] not in s:
				print(s + alphabet[i])
				break
	else:
		tail = [d[s[25]]]
		for i in range(0, 25):
			if d[s[24 - i]] >= max(tail):
				tail.append(d[s[24 - i]])
				continue
			else:
				tmp = min([x for x in tail if x >= d[s[24-i]]])
				print(s[0:(24-i)] + alphabet[tmp])
				break


if __name__ == '__main__':
	s = input()
	main(s)

Measured memory_bytes: 3064
#include <stdio.h>
int A[100][100],B[20][100][100];
int main(){
	const int INF=1<<29;
	int n,m,c,s,g;
	for(;scanf("%d%d%d%d%d",&n,&m,&c,&s,&g),n;){
		int i,j,k,x;
		//?????¢??????????????????
		for(i=0;i<n;i++)for(j=0;j<n;j++){
			A[i][j]=INF;
			for(k=0;k<c;k++)B[k][i][j]=INF;
		}
		//?????????????????¨????§??????????????????¢????±???????
		for(i=0;i<m;i++){
			int x,y,d,c;
			scanf("%d%d%d%d",&x,&y,&d,&c);
			x--,y--,c--;
			if(B[c][x][y]>d)B[c][x][y]=d;
			if(B[c][y][x]>d)B[c][y][x]=d;
		}
		int p[c];
		for(x=0;x<c;x++){
			scanf("%d",&p[x]);
			for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++){
				if(B[x][i][j]>B[x][i][k]+B[x][k][j]){
					B[x][i][j]=B[x][i][k]+B[x][k][j];
				}
			}
		}
		//??¨???????????¢????§???????????????????????????????
		for(k=0;k<c;k++){
			int x=p[k],q[x],r[x];
			q[0]=0;
			for(i=1;i<x;i++)scanf("%d",&q[i]);
			for(i=0;i<x;i++)scanf("%d",&r[i]);
			for(i=0;i<n;i++)for(j=0;j<i;j++)if(B[k][i][j]<INF){
				int y=x-1;
				for(;B[k][i][j]<q[y];y--);
				int v=r[y]*(B[k][i][j]-q[y]);
				for(y--;y>=0;y--)v+=r[y]*(q[y+1]-q[y]);
				if(A[i][j]>v)A[i][j]=A[j][i]=v;
			}
		}
		//?§??????????????????????????±???????
		for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++){
			if(A[i][j]>A[i][k]+A[k][j]){
				A[i][j]=A[i][k]+A[k][j];
			}
		}
		printf("%d\n",A[s-1][g-1]>=INF ? -1 : A[s-1][g-1]);
	}
	return 0;
}

Measured memory_bytes: 1420
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>

using namespace std;

int main(){
  vector<int> x(3);
  for (int i=0;i<3;i++) cin>>x.at(i);
  sort(x.begin(),x.end());
  int ans;
  ans=x.at(2)*10+x.at(1)+x.at(0);
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;
using ll = long long;

template<class T>
vector<T> divisor(T n){
    vector<T> res;
    for(T i = 1; i * i <= n; i++){
        if(n % i == 0){
            res.push_back(i);
            T j = n / i;
            if(i != j)res.push_back(j);
        }
    }
    return res;
}

const int MAX = 1000000;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> in(MAX + 1);
    for(int i = 0; i < n; i++)cin >> a[i], in[a[i]]++;
    int sum = 0;

    for(int i = 0; i < n; i++) {
        vector<int> num = divisor(a[i]);
        int res = 0;
        for(int j = 0; j < num.size(); j++) {
            res += in[num[j]];
        }
        if(res == 1)sum++;
    }
    cout << sum << '\n';
}


Measured memory_bytes: 7928
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()
    B = LI()

    A = [B[0], ]
    for i in range(N-2):
        A.append( min(B[i], B[i+1]))
    A.append(B[N-2])
    print(sum(A))

main()

Measured memory_bytes: 3064
#!/usr/bin/env python3
N,K,Q=(int(x) for x in input().split())
a=[int(input()) for i in range(Q)]#正解者
l=[]
for j in range(N):
    l.append(K-Q)
for k in range(Q):
  l[a[k]-1]+=1

for n in range(N):
    if(l[n]>=1):
        print("Yes")
    else:
        print("No")

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

using namespace std;

int solve(vector<int> p, int n) {
    int min = p.at(0);
    int ans = 1;
    for(int i=1; i<n; ++i) {
        if (min >= p.at(i)) {
            ++ans;
            min = p.at(i);
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i=0; i<n; ++i)
        cin >> p.at(i);
    cout << solve(p,n);
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <cmath>
using ll = long long;
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;

int main(){
  ll n;
  cin >> n;
  vector<ll> x(n), y(n), h(n);
  rep(i, n) cin >> x[i] >> y[i] >> h[i];
  ll H, cx, cy;
  bool flag;
  rep(i, 101){
    rep(j, 101){
      flag = true;
      cx = i, cy = j;
      rep(k, n){
        if (h[k] == 0) continue;
        H = h[k] + abs(x[k]-cx) + abs(y[k]-cy);
        break;
      }
      rep(k, n){
        if (h[k] == 0){
          if (H > abs(x[k]-cx) + abs(y[k]-cy)){
            flag = false;
            break;
          }
        }
        else{
          if (H != h[k] + abs(x[k]-cx) + abs(y[k]-cy)){
            flag = false;
            break;
          }
        }
      }
      if (flag) break;
    }
    if (flag) break;
  }
  cout << cx << ' ' << cy << ' ' << H << endl;
  
  return 0;
}

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

using namespace std;

#define ar array
#define ll long long

const int M=1e9+7;
int n,a,b;
ll iv[200001];

ll nck(int n, int k){
    ll ans=1;
    for(int i=1;i<=k;i++)
        ans=ans*(n-i+1)%M*iv[i]%M;
    return ans;
}

ll powM(ll b, int p){
    ll r=1;
    for(;p;b=b*b%M,p/=2)
        if(p&1)
            r=r*b%M;
    return r;
}

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


    iv[1]=1;
    for(int i=2;i<=200000;i++){
        iv[i]=M-M/i*iv[M%i]%M;
    }
    cin>>n>>a>>b;
    ll ans=powM(2,n);
    cout<< (ans+2*M-nck(n,a)-nck(n,b)+M-1)%M;
    return 0;
}


Measured memory_bytes: 1792
n = int(input())
max_1 = 0
max_2 = 0
a_list = []
for i in range(n):
    a = int(input())
    a_list.append(a)
    if max_1 < a:
        max_2 = max_1
        max_1 = a
    elif max_2 < a:
        max_2 = a
#print(max_1,max_2)
for i in range(n):
    if a_list[i] == max_1:
        print(max_2)
    else:
        print(max_1)


Measured memory_bytes: 16956
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long x,k,d,s,l,p,q;
    cin>>x>>k>>d;
    s=x;
    if(x<0)
    {
        s=(-1)*x;
    }
    l=s/d;
    if(l>=k)
    {
        cout<<s-(k*d)<<endl;
    }
    else
    {
        p=s-(l*d);
        q=k-l;
        if(q%2==0)
        {
           cout<<p<<endl;
        }
        else
        {
            cout<<(-1)*(p-d)<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3616
#include <stdio.h>

int main(void)
{
	int n,k,l[100],no;
	int count=0;
	int sum=0;
	
	scanf("%d%d",&n,&k);
	
	for(int i=0;i<n;i++){
		
		scanf("%d",&(l[i]));
		
	}
	
	
	while(count<k){
		
		int max=-1;
		
		for(int i=0;i<n;i++){
			
			if(max<l[i]){
				max=l[i];
				no=i;
			}
			
		}
		
		count++;
		
		l[no]=-2;
		
		sum=sum+max;
	}
	
	printf("%d\n",sum);
	
	return 0;
}
	

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

int main() {
  cout <<fixed <<setprecision(6);
  int n; cin >>n;
  double ans = 0;
  double buf;
  for (int i=0; i<n; i++){
    cin >>buf;
    ans += 1/buf;
  }
  ans = 1/ans;
  
  cout <<ans;
  cout <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#define N 101
#define INF (1e9)
using namespace std;
int n,a[N],b[N],ans,c;
bool used[N];
 
int main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i]>>b[i];
  for(int i=1;i<=31;i++){
    c=INF;
    for(int j=0;j<n;j++)
      if(!used[j]&&a[j]<=i&&i<=b[j]){
	if(c==INF) c=j;
	else if(b[j]<b[c]) c=j;
      }
    if(c!=INF) used[c]=true;
  }
  for(int i=0;i<n;i++)
    if(used[i]) ans++;
  cout<<ans*100+(31-ans)*50<<endl;
  return 0;
}

Measured memory_bytes: 1164
S = list(input())
before = "R"
num = 0
nlist = []
for ch in S:
    if ch == before:
        num += 1
    else:
        nlist.append(num)
        num = 1
    before = ch
else:
    nlist.append(num)
ans = []
for i in range(len(nlist)):
    if i%2 == 0:
        sans = [0] * (nlist[i] - 1)
        num = (nlist[i]-nlist[i]//2)+nlist[i+1]//2
        sans.append(num)
        ans[len(ans):len(ans)] = sans
    else:
        sans = [0] * nlist[i]
        num = (nlist[i]-nlist[i]//2)+nlist[i-1]//2
        sans[0] = num
        ans[len(ans):len(ans)] = sans

print(' '.join(map(str,ans)))


Measured memory_bytes: 11944
// C - Many Medians
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,e)

int main(){
	int N; cin>>N;
	vector<pair<int,int>> X(N);
	rpz(i, N){
		int x; cin>>x;
		X[i] = make_pair(x, i);
	}
	sort(all(X));
	vi ans(N);
	rpz(i, N) ans[X[i].second] = i<N/2? X[N/2].first: X[N/2 - 1].first;
	rpz(i, N) cout<< ans[i] <<endl;
}

Measured memory_bytes: 4480
//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
int num[maxn],d[maxn],prime[maxn],vis[maxn];
void fun(int n)
{
	memset(vis,0,sizeof(vis));
	num[1]=1;
	d[1]=1;
	prime[0]=0;
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			prime[++prime[0]]=i;
			d[i]=1;
			num[i]=2;
		}
		for(int j=1;j<=prime[0]&&i<=n/prime[j];j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				d[i*prime[j]]=d[i]+1;
				num[i*prime[j]]=num[i]/(d[i]+1)*(d[i]+2);
				break;
			}
			d[i*prime[j]]=1;
			num[i*prime[j]]=num[i]*2;
		}
	}
}
int main(){
	fun(maxn-2);
	ll ans = 0;
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)ans += 1ll*i*num[i];
	cout << ans;
	return 0;
}


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

int main() {
  int n;
  list<int> xs;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int a;
    cin >> a;
    if (i % 2)
      xs.push_back(a);
    else
      xs.push_front(a);
  }
  if (n % 2) xs.reverse();
  for (auto it = xs.begin(); it != xs.end(); ++it) {
    cout << *it;
    if (it != --xs.end()) cout << " ";
  }
  cout << endl;
}


Measured memory_bytes: 8448
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	
ll n,c1,c2,c3,c4;
cin>>n;
c1=9;
c2=900;
c3=90000;
if(n<=99 && n>=10)
cout<<"9\n";
else if(n<=99 && n<10)
cout<<n;
	
else if(n>=100 && n<=999)
cout<<c1+(n-100+1);
else if(n>=1000 && n<=9999 )
cout<<(c1+c2);
else if(n>=10000 && n<=99999)
cout<<(c1+c2+(n-10000+1));
else
cout<<(c1+c2+c3);	
}

Measured memory_bytes: 256