akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

#define ma 23456789
int sea[200][200];
int load[200][200];
int dp[1000][200];
int to[1000] = {0};

signed main(void){
  int i, j, k;
  for(int testcase = 0;testcase >= 0;testcase++){
    int2(n, m);
    if(!(n | m))break;
    rep(i, n)rep(j, n){
      sea[i][j] = ma;
      if(i == j)sea[i][j] = 0;
    }
    rep(i, n)rep(j, n){
      load[i][j] = ma;
      if(i == j)load[i][j] = 0;
    }
    rep(i, m){
      int x, y, t;
      char sl;
      scanf("%d %d %d %c", &x, &y, &t, &sl);
      --x; --y;
      if(sl == 'S'){
        sea[x][y] = min(sea[x][y], t);
        sea[y][x] = min(sea[y][x], t);
      }else{
        load[x][y] = min(load[x][y], t);
        load[y][x] = min(load[y][x], t);
      }
    }

    rep(k, n)rep(i, n)rep(j, n){
      sea[i][j] = min(sea[i][j], sea[i][k] + sea[k][j]);
      load[i][j] = min(load[i][j], load[i][k] + load[k][j]);
    }

    int(r);
    rep(i, r)rep(j, n)dp[i][j] = ma;

    scanf("%d", &to[0]); --to[0];
    dp[0][to[0]] = 0;
    rep(j, n)dp[0][j] = min(dp[0][j], sea[to[0]][j] + load[j][to[0]]);

    rep1(i, r){
      scanf("%d", &to[i]); --to[i];
      rep(j, n){
        dp[i][j] = min(dp[i][j], dp[i - 1][j] + load[to[i - 1]][to[i]]);
        rep(k, n)dp[i][j] = min(dp[i][j], dp[i - 1][k] + load[to[i - 1]][k] + sea[k][j] + load[j][to[i]]);
      }
    }

    int res = ma;
    rep(j, n)res = min(res, dp[r - 1][j]);
    pri(res);

    /*if(testcase == 1){
      rep(i, n)rep(j, n)pri3(i, j, load[i][j]);
      rep(i, n)rep(j, n)debug3(i, j, sea[i][j]);
      rep(i, r)rep(j, n)pri3(i, j, dp[i][j]);
    }*/



//*/

//*/ break;
  }
  return 0;
}

Measured memory_bytes: 4308
#include <cstdio>
#include <iostream>
#include <sstream>

#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

#include <chrono>
#include <random>

using namespace std;
using i64 = int_fast64_t;
using ui64 = uint_fast64_t;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<i64>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pii = pair<int, int>;
using pll = pair<i64, i64>;

//////////////////////////////////////////////////

int main() {
  int N, D;
  cin >> N >> D;
  vvi x(N, vi(D));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < D; j++) cin >> x[i][j];
  int ret = 0;
  double eps = 1e-6;
  for (int i = 0; i < N; i++) {
    for (int j = i+1; j < N; j++) {
      i64 sum = 0;
      for (int k = 0; k < D; k++) {
        sum += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
      }
      i64 sr = (i64)floor(sqrt(sum));
      if(sum == sr*sr)ret++;
    }
  }
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
const ll p =1e9 + 7;
ll modpower(ll base, ll power, ll mod=p){
    ll ans =1;
    base%=p;
    while(power){
        if(power&1){
            ans*=base;
            ans%=p;
        }
        base*=base;
        base%=p;
        power>>=1;
    }
    return ans;
}
vector<ll> fact;
vector<ll> invfact;
void computefactorial(int n){
    ++n;
    fact.resize(n);
    invfact.resize(n);
    fact[0]=1;
    for(int i=1;i<n;i++){
        fact[i]=i*fact[i-1];
        fact[i]%=p;
    }
    invfact[n-1]=modpower(fact[n-1],p-2);
    for(int i=n-2;i>=0;i--){
        invfact[i]=(i+1)*invfact[i+1];
        invfact[i]%=p;
    }
}
inline ll ncr(int n,int r){
    if(r>n || n<0){
        return 0;
    }
    return fact[n] * invfact[r]%p * invfact[n-r]%p;
}
void solve(){
    int h,w,a,b;
    cin>>h>>w>>a>>b;   
    ll ans = ncr((h-1)+(w-1),h-1);
    for(int i=1;i<=b;i++){
        ans-=ncr((h-a-1) + (i-1), i-1) * ncr((a-1)+(w-i),w-i);
        ans%=p;
    }
    if(ans<0){
        ans+=p;
    }
    cout<<ans<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    computefactorial(3e5 + 7);
    solve();
}

Measured memory_bytes: 7852
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
ll n,k;
ll arr[100005];
ll dp[100005]={0};
using namespace std;
int main(){
   // #ifndef ONLINE_JUDGE
   // freopen("ins.txt","r",stdin);
   // freopen ("output.txt","w",stdout);
    //#endif
    cin>>n>>k;
    for(ll i=0;i<n;i++){
      cin>>arr[i];
    }
    //cout<<frogstep(0)<<endl;
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(ll i=2;i<n;i++){
      dp[i]=INT_MAX;
      for(ll j=1;j<=k;j++){
        if(i-j>=0){
          dp[i]=min(dp[i],dp[i-j]+abs(arr[i]-arr[i-j]));
        }
      }
    }
    cout<<dp[n-1]<<endl;
    //cout<<dp[n-1]<<endl;


}

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

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    int sum = 0;
    for(int i=0;i<N;i++){
        cin >> vec.at(i);
        sum += vec.at(i);
    }
    // for(int i=0;i<N;i++){
    //     cout << vec.at(i) << endl;
    // }
    // cout << "sum = " << sum << endl;
    int s1 = 0;
    int s2;
    int dif;
    int predif = 100000;
    for(int T=0;T<N-1;T++){
        for(int i=0;i<T+1;i++){
            // cout << "vec.at(i) = "<<vec.at(i)<<endl;
            s1 += vec.at(i);
        }
        s2 = sum -s1;
        dif = abs(s2-s1);
        // cout << "s1 = " << s1 << " s2 = " << s2 << endl;
        if(dif < predif){
            predif = dif;
        }
        s1 = 0;
    }
    cout << predif << endl;
}

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

using namespace std;

int main(){
	int n;
	long long x,tmp,t;
	vector<long long> a,ans;
	long long cost[2001][2001]={};
	cin >> n >> x;
	for(int i=0;i<n;i++){
		cin >> tmp;
		a.push_back(tmp);
	}
	for(int k=0;k<n;k++){
		t=0;
		for(int i=0;i<n;i++){
			if(k==0){
				cost[i][k]=a[i];
			}else{
				if(i>=k){
					cost[i][k]=min(cost[i][k-1],a[i-k]);
				}else{
					cost[i][k]=min(cost[i][k-1],a[n+i-k]);
				}
			}
			t+=cost[i][k];
		}
		ans.push_back(t+k*x);
	}
	sort(ans.begin(),ans.end());
	cout << ans[0] << endl;
	return 0;
}

Measured memory_bytes: 31616
#include <iostream>
#include <stack>
using namespace std;
int main() {
	int n;
	stack<int> array;
	while(cin >> n) {
		if(n == 0) {
			cout << array.top() << endl;
			array.pop();
		} else {
			array.push(n);
		}
	}

	return 0;
}

Measured memory_bytes: 1200
#include <algorithm>
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <cmath>
#include <iomanip>
#include <set>
#include <climits>
#include <utility>
#include <deque>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> als(m);
	vector<int> num(n + 1, 0);
	for (auto& a : als)cin >> a;
	reverse(als.begin(), als.end());
	als.push_back(-1);

	num[n] = 1;
	num[n - 1] = (n - 1 == als[0] ? 0 : 1);
	auto aptr = n - 1 == als[0] && 1 < m - 1 ? 1 : 0;

	for (int i = n - 2; i >= 0; --i) {
		if (i == als[aptr]) {
			if (aptr < m - 1)++aptr;
			continue;
		}
		num[i] = (num[i + 1] + num[i + 2]) % 1000000007;
	}

	cout << num[0] << endl;
	return 0;
}

Measured memory_bytes: 1408
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define rg register
#define f(i,a,b) for(rg int i=a;i<=b;++i)
#define df(i,a,b) for(rg int i=a;i>=b;++i)
#define F(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
using namespace std;
template <typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
template <typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
template <typename T> inline void read(T &n) {
	n=0;rg char ch;while(!isdigit(ch=getchar()));
	for(n=ch^48;isdigit(ch=getchar());n=n*10+(ch^48));
}
typedef long long ll;
ll n,m;
ll gcd(int x,int y) {if(x>y)x^=y^=x^=y;return x?gcd(y%x,x):y;}
signed main() {
	cin>>n>>m;
	cout<<n*m/gcd(n,m);
}


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

struct ver{
    ll d;
    ll f;
};

ll t=0;
vector<vector<ll>> mat;
vector<ver> vers;

void find(ll pos) {
    if(vers[pos].d == 0){
        t++;
        vers[pos].d = t;
        for(ll i:mat[pos]) {
            find(i);
        }
        if(vers[pos].f == 0) {
            t++;
            vers[pos].f = t;
        }
    }
}

int main() {
    ll n;
    cin >> n;
    for(ll i=0;i<n;i++) {
        ll u,k;
        cin>>u>>k;
        vector<ll> aaa;
        for(ll j=0;j<k;j++) {
            ll tmp;
            cin>>tmp;
            aaa.push_back(tmp-1);
        }
        mat.push_back(aaa);
    }
    for(ll i=0;i<n;i++) {
        vers.push_back(ver{0,0});
    }
    for(ll i=0;i<n;i++) {
        if(vers[i].d == 0)find(i);
    }
    for(ll i=0;i<n;i++) {
        cout << i+1<<" "<<vers[i].d<<" "<<vers[i].f<<endl;
    }
}



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

using namespace std;

int const N = 1234567;

int p[N], a[N], sz[N], was[N], chosen[N];
pair<int, int> b[N];

int get(int v) {
	return v == p[v] ? v : (p[v] = get(p[v]));
}

int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) p[i] = i;
	for (int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		p[get(v)] = get(u);
	}
	for (int i = 0; i < n; i++) {
		b[i] = { a[i], i };
	}
	sort(b, b + n);
	for (int i = 0; i < n; i++) {
		sz[get(i)]++;
	}
	if (sz[get(0)] == n) {
		puts("0");
		return 0;
	}
	long long ans = 0;
	int have = 0;
	int comps = 0;
	for (int i = 0; i < n; i++) {
		int v = get(b[i].second);
		if (!was[v]) {
			was[v] = true;
			chosen[i] = true;
			ans += b[i].first;
			have++;
			comps++;
			// if (sz[v] == 1) {
			// 	++one;
			// }
		}
	}
	if (2 * (comps - 1) > n) {
		cout << "Impossible\n";
		return 0;
	}
	for (int i = 0; have < 2 * (comps - 1) && i < n; i++) {
		if (!chosen[i]) {
			ans += b[i].first;
			have++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 11264
/*
Author: Racer5x
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
#define int         long long
#define double      long double
#define pb          emplace_back
#define pf          emplace_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX         2000000000000000000
#define M           1000000007
using namespace std;
 
signed main()
{
    tezz

    int n, k, ans = 0;
    string s;
    cin>>n>>k>>s;
    for(int i=0;i<n-1;i++) if(s[i] == s[i+1]) ans++;
    cout<<min(n-1, 2*k + ans);
} 

Measured memory_bytes: 512
import java.util.Scanner;
 
class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		if(n%500<=a){
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 21204
from collections import Counter

n = int(input())
s_inputs = [input() for i in range(n)]
m = int(input())
t_inputs = [input() for i in range(m)]

s_count = Counter(s_inputs)
t_count = Counter(t_inputs)

ans=0
for s in set(s_inputs+t_inputs):
    tmp = s_count[s]-t_count[s]
    if tmp>ans:
        ans=tmp
print(ans)



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

int main() {
	int a[3];
	for(int i=0;i<3;i++){
		cin>>a[i];
	}
	sort(a,a+3);
	if(a[0]==5 && a[1]==5 && a[2]==7){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
N = int(input())

l = []
for i in range(N):
    l.append(input())

#重複チェック
if len(set(l)) != N:
    print("No")
    exit()

#しりとりチェック
for i in range(N-1):
    if l[i][-1] != l[i+1][0]:
        print("No")
        exit()

print("Yes")


    


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

int N, A[500005], l[500005], r[500005];
stack< pair<int, int> > S;

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", &A[i]);
	long long ans = 0;
	S.push(make_pair(-1, -1));
	for (int i = 0; i < N; i++) {
		while (S.top().first > A[i]) S.pop();
		l[i] = i - S.top().second;
		S.push(make_pair(A[i], i));
	}
	while (!S.empty()) S.pop();
	S.push(make_pair(-1, N));
	for (int i = N - 1; i >= 0; i--) {
		while (S.top().first > A[i]) S.pop();
		r[i] = S.top().second - i;
		S.push(make_pair(A[i], i));
	}
	for (int i = 0; i < N; i++) ans += (long long)A[i] * l[i] * r[i];
	printf("%lld\n", ans);
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

int main()
{
    cout << fixed << setprecision(15);
    ll x;
    cin >> x;

    if(x < 1200){
        cout << "ABC" << endl;
    }
    else{
        cout << "ARC" << endl;
    }
    return 0;
}

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

int main(){
    ll n, p, ans=0;
    cin >> n;

    cin >> p;
    ll min_n = p;
    ans +=1;

    rep(i, n-1){
        cin >> p;
        min_n = min(p, min_n);
        if(min_n==p) ans+=1;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
string s;
int k = 0;
void inp()
{
    getline(cin, s);
}
void process()
{
    for (int i = 0; i < 3; i++)
    {
        if (s[i] == 'R')
        {
            int j = i;
            while (s[j] == s[j+1] && j < 3 && s[j] == 'R')
            j++;
            k = max(k, j-i+1);
        }
    }
    cout << k;
}
int main()
{
	//freopen("test.inp","r",stdin);
    inp();
    process();
	return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>
#include <math.h>

int main(void) {
  double r = 0.0;
  double s = 0.0;
  double l = 0.0;

  scanf("%lf", &r);

  s = M_PI * r * r;
  l = 2.0 * M_PI * r;

  printf("%f %f\n", s, l);

  return 0;
}

Measured memory_bytes: 648
# D
a, b = map(int, input().split())
a -= 1
b -= 1
print("{} {}".format(100, 100))
for i in range(100):
    s = ''
    for j in range(100):
        if j < 50:
            if j % 2 == 0 and i % 2 == 0 and j < 49 and a > 0:
                s += '.'
                a -= 1
            else:
                s += '#'
        else:
            if j % 2 == 0 and i % 2 == 0 and j > 51 and b > 0:
                s += '#'
                b -= 1
            else:
                s += '.'
    print(s)

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

vector<long long> v;
void dfs(ll x, ll num, ll st, ll cc){
	if(v.size() > 100050) return;
	if(num == 0) num += x;
	else {
		num *= 10;
		num += x;
	}
	if(cc > st) return;
	if(cc == st){
		v.push_back(num);
		return;
	}
	if(x-1 >= 0) dfs(x-1,num,st,cc+1);
	if(x+1 <= 9) dfs(x+1,num,st,cc+1);
	dfs(x,num,st,cc+1);
	return;
}

int main(){
	
	ll k; cin>>k;
	for(int i = 1; i <= 10; i++){
		for(int j = 1; j <= 9; j++){
			dfs(j,0,i,1);
		}
	}
	sort(v.begin(),v.end());
	cout<<v[k-1]<<"\n";
}

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

const long long mod=1000000007;

int main(void)
{
  int n,m; cin >> n >> m;
  int broken[n + 1]; rep(i, n) broken[i] = 0;
  long long dp[n + 1]; rep(i, n) dp[i] = 0;
  rep(i,m - 1) {int a; cin >> a; broken[a] = 1;}

  dp[0] = 1;
  if (!broken[1]) dp[1] = 1;
  for(int i = 2; i <= n; i++)
  {
	if (!broken[i - 2])
		dp[i] += dp[i - 2];
	if (!broken[i - 1])
  		dp[i] += dp[i - 1];
	dp[i] %= mod;
  }
  cout << dp[n] << endl;
  return (0);
}


Measured memory_bytes: 1408
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)

using namespace std;
typedef long long ll;

int vs[100000+10];
int n;

bool visited[100000+5][5];
ll memo[100000+5][5];
ll solve(int pos, int flipped) {
  ll &res = memo[pos][flipped];
  if(!visited[pos][flipped]) {
    visited[pos][flipped] = true;
    if(pos == n-1) {
      res = flipped ? -vs[pos] : vs[pos];
    } else {
      ll r1 = (flipped ? -vs[pos] : vs[pos]) + solve(pos+1, 0);
      ll r2 = (flipped ? vs[pos] : -vs[pos]) + solve(pos+1, 1);
      res = max(r1, r2);
    }
  }
  return res;
}

int main(void) {
  scanf("%d", &n);
  REP(i, n) {
    scanf("%d", &vs[i]);
  }
  
  ll res = solve(0, 0);
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int a_old;
	cin >> a_old;
	int64_t ans = 0;
	for (int i = 1; i < n; ++i) {
		int a;
		cin >> a;
		if (a < a_old) {
			ans += (a_old - a);
		} else {
			a_old = a;
		}
	}

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


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
int main(){
	int n,w,a,b,dp[MAX],i,j;
	fill(dp,dp+MAX,1e9+1);
	dp[0]=0;
	cin>>n>>w;
	for(i=0;i<n;i++){
		cin>>a>>b;for(j=MAX-1;j>=a;j--)if(dp[j-a]!=1e9+1)dp[j]=min(dp[j],dp[j-a]+b);
	}
	for(i=MAX-1;i>=0;i--)if(dp[i]<=w){cout<<i<<endl;break;}
}

Measured memory_bytes: 3452
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc_050_C
{
    class Program
    {
        public static long mod = (long)(Math.Pow(10, 9) + 7);
        static void Main(string[] args)
        {
            long n = long.Parse(Console.ReadLine());
            long[] a = Console.ReadLine().Split().Select(long.Parse).ToArray();
            Array.Sort(a);
            if (n % 2 == 0)
            {
                for(long i = 0; i < a.Length; i++)
                {
                    if ((i / 2 + 1)*2-1 != a[i]) { Console.WriteLine(0); return; }
                }
                long ans = 1;
                for (long i = 0; i < a.Length / 2; i++)
                {
                    ans *= 2;
                    ans %= mod;
                }
                Console.WriteLine(ans);
            }
            else
            {
                for (long i = 0; i < a.Length; i++)
                {
                    if (i % 2 == 0 && i == a[i]) { }
                    else if (i % 2 == 1 && i + 1 == a[i]) { }
                    else { Console.WriteLine(0); return; }
                }
                long ans = 1;
                for (long i = 0; i < a.Length / 2; i++)
                {
                    ans *= 2;
                    ans %= mod;
                }
                Console.WriteLine(ans);
            }
        }
    }
}


Measured memory_bytes: 19424
use proconio::input;

fn main() {
    input! {
        n: usize,
        aa: [u64;n],
        q: usize,
        bcs: [(usize,usize);q]
    }
    let mut v = vec![0; 100001];
    for a in &aa {
        v[*a as usize] += 1;
    }
    let mut s: u64 = aa.iter().sum();
    for (b,c) in bcs {
        if b < c {
            s += (v[b] * (c-b)) as u64;
        } else if b > c {
            s -= (v[b] * (b-c)) as u64;
        }
        v[c] += v[b];
        v[b] = 0;
        println!("{}", s);
    }
}


Measured memory_bytes: 6896
#include <bits/stdc++.h> // {{{
// clang-format off
#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define USE1(T) template <typename T> inline
#define USE2(T, U) template <typename T, typename U> inline
#define mygc(c) (c) = getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
 
template<typename T> using vec = std::vector<T>;
template<typename T> using withi = std::pair<T, int>;
using ll = long long;
USE2(T,U)bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE2(T,U)bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE1(T=int)T in(){T x;std::cin>>x;return x;}
USE1(T=int)vec<T>in(int n){vec<T>v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE2(T,U=withi<T>)vec<U>zipi(const vec<T>&x,int s=0){int N=x.size();vec<U>v;v.reserve(N);rep(i,N)v.pb(x[i],s+i);return v;}
USE1(T)vec<T>ndvec(T v,int n){return vec<T>(n,v);}
USE2(T,...Ts)auto ndvec(T v,int n,Ts...ns)->vec<decltype(ndvec(v,ns...))>{return ndvec(ndvec(v,ns...),n);}
USE1(T)void pr(T x){std::cout<<x<<'\n';}
USE2(T,...Ts)void pr(T x,Ts...xs){std::cout<<x<<' ';pr(xs...);}
USE1(T=int)T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
USE1(T=int)void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
// clang-format on
// }}}
struct IoSetup { // {{{
  IoSetup() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.precision(10);
    std::cerr.precision(10);
  }
} iosetup; //}}}
using namespace std;
const int inf = 1001001001;
const ll infl = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  int N;
  while (N = in(), N) {
    auto votes = in<string>(N);
    int vote[26] = {};
    rep(i, N) {
      int rest = N - i - 1;
      vote[votes[i][0] - 'A']++;
      int maxi = max_element(vote, vote + 26) - vote;
      bool fixed = true;
      rep(j, 26) if (maxi != j) {
        if (vote[maxi] <= vote[j] + rest) {
          fixed = false;
          break;
        }
      }
      if (fixed) {
        pr((char)('A' + maxi), i + 1);
        goto END;
      }
    }
    pr("TIE");
  END:;
  }
  return 0;
}

Measured memory_bytes: 3184
#include<stdio.h>//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
struct Node{
	int p,l,r;//親、左の子、右の子
};
Node T[100001];
int N,depth[100001],height[100001];
void setdepth(int u,int d){
	depth[u]=d;
	if(T[u].l!=-1) setdepth(T[u].l,d+1);
	if(T[u].r!=-1) setdepth(T[u].r,d+1);
}
int setheight(int u){
	int h1=0,h2=0;
	if(T[u].l!=-1) h1=setheight(T[u].l)+1;
	if(T[u].r!=-1) h2=setheight(T[u].r)+1;
	height[u]=max(h1,h2);
	return height[u];
}
int getsibling(int u){//uの兄弟を返す
	if(T[u].p==-1) return -1;
	if(T[T[u].p].l!=u&&T[T[u].p].l!=-1) return T[T[u].p].l;
	if(T[T[u].p].r!=u&&T[T[u].p].r!=-1) return T[T[u].p].r;
	return -1;
}
void pre(int u){
	if(u==-1) return;
	printf(" %d",u);
	pre(T[u].l);
	pre(T[u].r);
}
void in(int u){
	if(u==-1) return;
	in(T[u].l);
	printf(" %d",u);
	in(T[u].r);
}
void post(int u){
	if(u==-1) return;
	post(T[u].l);
	post(T[u].r);
	printf(" %d",u);
}
int main(){
	scan(N);
	rep(i,N) T[i].p=T[i].l=T[i].r=-1;
	rep(i,N){
		int v,l,r;
		scan(v>>l>>r);
		T[v].l=l,T[v].r=r;
		if(l!=-1) T[l].p=v;
		if(r!=-1) T[r].p=v;
	}
	int root;
	rep(i,N) if(T[i].p==-1) root=i;
	prin("Preorder");
	pre(root);
	kaigyo;
	prin("Inorder");
	in(root);
	kaigyo;
	prin("Postorder");
	post(root);
	kaigyo;
	return 0;
}



Measured memory_bytes: 3244
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,st;
    cin>>n>>st;
    int cnt=0;
    for(int i=0;i<n;i++){
        long long a,b;
        cin>>a>>b;
        if(sqrt(a*a+b*b)<=st) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 3652
import sys
#input = sys.stdin.buffer.readline

def main():
    S = str(input())
    ans = 10**3
    for i in list(set(S)):
        count = 0
        now = 0
        for j in S:
            if i != j:
                count += 1
            else:
                count = 0
            now = max(now,count)
        ans = min(ans,now)
    
    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
import java.util.*;
import java.lang.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] markSample = {'S', 'H', 'C', 'D'};
        char[] mark = new char[n];
        int[] number = new int[n];
        
        
        for (int i = 0; i < n; i++) {
            mark[i] = sc.next().charAt(0);
            number[i] = sc.nextInt();
        }
        
        
        for (int i = 0; i < 52; i++) {
            char m = markSample[i / 13];
            int num = i % 13 + 1;
            for (int j = 0; j < n; j++) {
                if (number[j] == num && mark[j] == m) {
                    break;
                }
                if (j == n - 1) {
                    System.out.println(m + " " + num);
                }
            }
            
        }
    }
}



Measured memory_bytes: 26276
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int snum = 0, tnum = 0;
    for(int i = 0; i < s.size(); i++){
        if(s.at(i) == 'S')
            snum++;
        else{
            tnum++;
            if(snum > 0){
                tnum--;
                snum--;
            }
        }
    }
    cout << snum + tnum << endl;
}

Measured memory_bytes: 640
function Main(inputData) {
	init(inputData);
	
	var a = inI();
	var b = inI();
	
	out(a-b+1);
}

////////////////////////////////////////////////////////////////////////////////////
var input,inputCnt;

// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug(){
	Main(document.getElementById("input").value);
}

function init(inputData){
    //配列inputに順番に代入
	input = inputData.replace( /\n/g , " " );
	input = input.split(" ");
	inputCnt = 0;
}
//output
const out = (output) => { console.log(output) }
const outln = (output) => { console.log(output+"\n") }

//input
const inS = () => {return input[inputCnt++]};
const inI = () => {return parseInt(inS(), 10)};
const inF = () => {return parseFloat(inS())};

//prototype
Array.prototype.rsort = function(){
  return this.sort(function(a,b){return (a<b ? 1:-1);});
}

Array.prototype.max = function(){
  return Math.max.apply(null, this);
}

Array.prototype.min = function(){
  return Math.min.apply(null, this);
}


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;
    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }
    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}
#[allow(unused_macros)]
macro_rules ! get { ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ;; ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { println ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }

struct SEG {
    buf: Vec<u64>,
    n: usize,
}

impl SEG {
    fn new(size: usize) -> SEG {
        let n = (1..).map(|i| 1 << i).find(|&x| x > size).unwrap();

        SEG {
            buf: vec![0; 2 * n],
            n: n,
        }
    }

    fn add(&mut self, i: usize, x: u64) {
        let mut i = self.n + i - 1;
        self.buf[i] += x;
        while i > 0 {
            i = (i - 1) / 2;
            self.buf[i] = self.buf[i * 2 + 1] + self.buf[i * 2 + 2];
        }
    }

    fn sum(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> u64 {
        if r <= a || b <= l {
            return 0;
        }

        if a <= l && r <= b {
            return self.buf[k];
        }

        let vl = self.sum(a, b, k * 2 + 1, l, (l + r) / 2);
        let vr = self.sum(a, b, k * 2 + 2, (l + r) / 2, r);

        vl + vr
    }
}

fn main() {
    let (n, q) = get!(usize, usize);

    let mut seg = SEG::new(n);

    for _ in 0..q {
        let (com, x, y) = get!(usize, usize, usize);

        if com == 0 {
            seg.add(x, y as u64);
        } else {
            println!("{}", seg.sum(x, y + 1, 0, 0, seg.n));
        }
    }
}



Measured memory_bytes: 7080
n,x,y=map(int,input().split())

ans=[0 for _ in range(n-1)]

for i in range(n-1):
  for j in range(i+1,n):
    t=i+1
    u=j+1
    H=min(abs(u-t),abs(t-x)+1+abs(y-u),abs(t-y)+1+abs(x-u))
    ans[H-1]+=1
    
for l in ans:
  print(l)


Measured memory_bytes: 9356
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 200000000000000
#define MAXN 1000001
#define eps 0.0000000001
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

//////////////

#define S second
#define F first
#define int long long  

//////////

signed main()
{
    fastio;
    int n,W;
    cin>>n>>W;
    int ans[n+1][W+1]={};
    for(int i=1;i<=n;++i)
    {
        int w,v;
        cin>>w>>v;
        for(int j=1;j<=W;++j)
        {
            ans[i][j]=ans[i-1][j];
            if(j-w>=0)
            ans[i][j]=max(ans[i][j],ans[i-1][j-w]+v);
        }
    }
    int an=0;
    for(int i=0;i<=W;++i)
        an=max(ans[n][i],an);
    cout<<an;
}

Measured memory_bytes: 79232
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
a=[0]*n
for i in range(n):
    a[i]=I()-1
j=0
c=0
while j!=1 and c<10**6:
    c+=1
    j=a[j]
print(c if c<10**5 else -1)






Measured memory_bytes: 42728
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
string str;
const int Limit =1000000000;
typedef long long ll;
ll n,T,ans,kari;
int main()
{
  cin>>n>>T;
  cin>>str;
  ans = 0;
  for(int i = 0;i < str.length();i++){
    if(ans >Limit){
      cout <<"TLE"<<endl;
      return 0;
    }
    if(str[i] >='0'&&str[i] <='9'){
      if(str[i]=='0')
	ans++;
      else{
	kari = 1;
	for(int j = 0;j < str[i]-'0';j++){
	  kari *=n;
	  if(kari >Limit){
	    cout <<"TLE"<<endl;
	    return 0;
	  }
	}
	ans +=(kari);
      }
    }
  }
  ans *=T;
  if(ans >Limit){
    cout <<"TLE"<<endl;
  }else
    cout <<ans<<endl;
  return 0;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

template<typename T, typename U>
struct segtree {
	ll n, H;
	
	vector<T> value;
	vector<U> prop;
	vector<bool> dirty;

	segtree<T,U>(vector<T> leaves): n(sz(leaves)) {
		H = 32 - __builtin_clz(2*n-1);

		value.resize(2*n);
		copy(all(leaves),begin(value)+n);
		FORD(i,1,n) value[i] = value[2*i] + value[2*i+1];
		
		dirty.resize(n,false);
		prop.resize(n);
	}

	void apply(ll i, U &upd) {
		value[i] = upd(value[i]);
		if (i < n) prop[i] = prop[i] + upd, dirty[i] = true;
	}

	void rebuild(ll i) {
		for (i /= 2; i; i /= 2) value[i] = prop[i](value[2*i] + value[2*i+1]);
	}

	void propagate(ll i) {
		FORD(h,1,H+1) if (dirty[i >> h]) {
			ll j = i >> h;
			apply(2*j,prop[j]), apply(2*j+1,prop[j]);
			prop[j] = U(), dirty[j] = false;
		}
	}

	void update(ll i, ll j, U upd) {
		if (i == j) return;
		i += n, j += n;
		propagate(i), propagate(j-1);
		for (ll l = i, r = j; l < r; l /= 2, r /= 2) {
			if (l & 1) apply(l++,upd);
			if (r & 1) apply(--r,upd);
		}
		rebuild(i), rebuild(j-1);
	}
	
	T query(ll i, ll j) {
		i += n, j += n;
		propagate(i), propagate(j-1);
		T resl, resr;
		for (; i < j; i /= 2, j /= 2) {
			if (i & 1) resl = resl + value[i++];
			if (j & 1) resr = value[--j] + resr;
		}
		return resl + resr;
	}
};

const ll N = 2e5 + 10, MOD = 998244353;
ll t[N], r[N];

struct node {
	ll x, len;
	node(ll d = 0, ll len = 0): x(d*r[len] % MOD), len(len) { }
	node operator+(node n) {
		node res;
		res.x = (x*t[n.len] + n.x) % MOD;
		res.len = len + n.len;
		return res;
	}
};

struct update {
	ll d = -1;
	node operator()(node n) {
		if (d == -1) return n;
		return node(d, n.len);
	}
	update operator+(update u) {
		if (u.d == -1) return *this;
		return u;
	}
};

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

	t[0] = 1, r[0] = 0;
	FOR(n,1,N) t[n] = 10*t[n-1] % MOD;
	FOR(n,1,N) r[n] = (10*r[n-1] + 1) % MOD;
	
	ll n, q;
	cin >> n >> q;

	vector<node> leaves(n, node(1,1));
	segtree<node,update> S(leaves);
	
	while (q--) {
		ll i, j, d;
		cin >> i >> j >> d;
		i--;
		S.update(i,j,{d});
		cout << S.query(0,n).x << endl;
	}
}



Measured memory_bytes: 20364
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int k;
  vector<int> sosuu(1000001);
  vector<int> ans(1000001);
  for(int i=2; i<=100000; i++){
    k=1;
    for(int j=2; j*j<=i; j++){
      if(i%j==0){
        k=0;
        
        break;
      }
    }
    if(k==1){
      sosuu.at(i+1)=1;
      
    }
  }
  
  
  
  for(int i=2; i<=100000; i++){
    if(sosuu.at(i+1)==1 && sosuu.at((i+1)/2+1)==1 && (i-1)%2==0){
      ans.at(i+1)=1;
    }
  }
  for(int i=2; i<=100000; i++){
    ans.at(i)=ans.at(i)+ans.at(i-1);
  }
  
  int q,x,y;
  cin>>q;
  for(int i=0; i<q; i++){
    cin>>x>>y;
    cout<<ans.at(y+1)-ans.at(x)<<endl;
  }
  
}
      

Measured memory_bytes: 8448
/**
 *   created: 20 August 2019  11:36:13
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) c.begin(),c.end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================

int main()
{
	optimizeIO();
	int tt=1;
	//cin>>tt;
	while(tt--){
		ll n,w;
		cin>>n>>w;
		vl v(n), wt(n);
		rep(i,0,n)
			cin>>wt[i]>>v[i];
		vl mem(1e5+10,INFLL);
		mem[0] = 0;
		rep(i,0,n){
			rrep(j,mem.size(),v[i]){
				mem[j] = min(mem[j], mem[j-v[i]]+wt[i]);
			}
		}
		ll res = 0;
		rep(i,0,mem.size())
			if(mem[i]<=w)
				res = i;
		cout<<res;
	}
	return 0;
}


Measured memory_bytes: 1024
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,a,b,c,d;
    string s;
    cin>>n>>a>>b>>c>>d;
    cin>>s;
    int cnt=0;
    for(int i=a;i<=c;i++){
        if(s[i-1]=='#') cnt++;
        else cnt=0;
        if(cnt==2){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cnt=0;
    for(int i=b;i<=d;i++){
        if(s[i-1]=='#') cnt++;
        else cnt=0;
        if(cnt==2){
            cout<<"No"<<endl;
            return 0;
        }
    }
    if(c<d){
        cout<<"Yes"<<endl;
        return 0;
    }
    else{
        for(int i=b-1;i<=(d-1);i++){
            if(s[i-1]=='.' && s[i]=='.' && s[i+1]=='.') {
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;

}

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


int main(){
    int N;
    cin >> N;
    vector<long> A(N);
    for(int i=0;i<N;++i) cin >> A[i];
    sort(A.begin(),A.end());
    long ans = A[N-1] - A[0];
    cout << ans << endl;
}



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

using namespace std;

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

    long t[100];
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    long gcd = t[0];
    long lcm = t[0];

    for (int i = 1; i < n; i++) {
        long a = lcm;
        long b = t[i];

        long tmp;
        while (b > 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        gcd = a;

        lcm = (lcm / gcd) * t[i];
    }

    cout << lcm << endl;
}


Measured memory_bytes: 384
#include <iostream>

int main()
{
  int H, W;

  std::cin >> H >> W;
  
  char* c = new char[W];
  {
    for (auto i = 0; i < H; ++i)
    {
      for (auto j = 0; j < W; ++j)
        std::cin >> c[j];
      for (auto j = 0; j < W; ++j)
        std::cout << c[j];
      std::cout << '\n';
      for (auto j = 0; j < W; ++j)
        std::cout << c[j];
      std::cout << '\n';
    }
    std::cout << std::flush;
  }
  delete[] c;
  
  return 0;
}


Measured memory_bytes: 256
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


n = int(input())
l = []
for p in primes(55555):
    if p % 5 == 1:
        l.append(p)
print(' '.join(map(str, l[:n])))

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<long long> > vvll;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define INF 1000000000
#define MOD 1000000007
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define p_q priority_queue
 
#define FOR(i, a, b) for (int i=(a); i<=(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)
 
#define MN 100005
#define MC 28
int n;
string s;
int occ[MC];

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

    cin >> n >> s;
    F0R(i, n){
        occ[s[i]-'a']++;
    }
    ll res = 1;
    F0R(i, 26){
        res = (res*(occ[i]+1))%MOD;
    }
    
    cout << res-1 << "\n";
    
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w,k;
  cin>>h>>w>>k;
  vector<string> cs(h);
  for(int i=0;i<h;i++) cin>>cs[i];

  int sh=1<<h;
  int sw=1<<w;

  int ans=0;
  for(int a=0;a<sh;a++){
    for(int b=0;b<sw;b++){
      int cnt=0;
      for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
          if(cs[i][j]=='#' and (a>>i)&1 and (b>>j)&1) cnt++;
      if(cnt==k) ans++;
    }
  }
  cout<<ans<<newl;
  return 0;
}


Measured memory_bytes: 3588
n,a,b = list(map(int, input().split()))
s = input()


for c in s:
    if c == 'a' and (a+b) > 0:
        print("Yes")
        a -= 1
    elif c == 'b' and (a + b) > 0 and b > 0:
        print("Yes")
        b -= 1
    else:
        print("No")


Measured memory_bytes: 9296
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = v
    print(*a)

Measured memory_bytes: 7992