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

// ------------------------- DEBUGGING -----------------------------------------------------------------
#ifdef DEBUG
#define debug(args...) { vector<string> _v = split(#args, ','); err( _v.begin(), args); cerr << endl; }
vector<string> split( const string& s, char c) {
      vector<string> v;
      stringstream ss( s);
      string x;
      while ( getline( ss, x, c))
            v.emplace_back( x);
      return move( v);
}
void err( vector<string>::iterator it) { }
template<typename T, typename... Args>
void err( vector<string>::iterator it, T a, Args... args) {
      cerr << it -> substr( ( *it)[0] == ' ', it -> length()) << " = " << a << '\t';
      err( ++it, args...);
}
#else
#define debug(...)
#endif
// -------------------------- MACROS -------------------------------------------------------------------

#define int long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define fr(i,j,k) for(i = j; i < (k); i++)
#define all(x) x.begin(), x.end()
#define el '\n'
#define remax(a,b) a = max(a, b)
#define remin(a,b) a = min(a, b)

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<pii> vpi;
// ---------------------------  TEMPLATE ENDS  -------------------------------------------------------

const pii dxy[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
const int mod = 1e9+7;
const int inf = 2e18;
const ld eps = 1e-9;
const int NN = 1e5 + 2;

vvi adj;

void solve(){
      int i = 0, j = 0, k = 0, n = 0, m = inf;
      vi c(3, 0);
      fr(i, 0, 3) {cin>>c[i];}
      map<pii, int> to;
      to[{1, 2}] = to[{2, 1}] = c[0];
      to[{1, 3}] = to[{3,1 }] = c[2];
      to[{2,3}] = to[{3,2}] = c[1];
            vi v = {1, 2, 3};
      do{
      	j = 0;
      	fr(i, 0, 2) {
      		j += to[{v[i+1], v[i]}];
      	}
      	remin(m, j);
      } while(next_permutation(all(v)));
      cout << m;
}

int32_t main(){
#ifndef DEBUG
      ios::sync_with_stdio(false); cin.tie(0); 
#endif
      int T = 1, tc;
      // cin >> T;
      for(tc = 1; tc <= T; tc++){
            solve();
      }
      return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD = (int)1e9 + 7;
int INF = (int)2e18;
// Comment out below and program paste

// #include "UnionFind.hpp"
// #include "power.hpp"

class rest {
      public:
      string name;
      int point;
      int rank;
      int number;
};

bool sorting(rest &a, rest &b) {
      if (a.name < b.name) {
            return true;
      } else if (a.name == b.name) {
            return a.point > b.point;
      } else {
            return false;
      }
}

bool numberSort(rest &a, rest &b) {
      return a.number < b.number;
}

signed main() {
      int N;
      cin >> N;
      vector<rest> restaurant(N);
      for (int i = 0; i < N; i++) {
            cin >> restaurant[i].name >> restaurant[i].point;
            restaurant[i].number = i + 1;
      }
      sort(restaurant.begin(), restaurant.end(), sorting);
      for (int i = 0; i < N; i++) {
            cout << restaurant[i].number << endl;
      }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >> n;
    vector<char> s(n);
    rep(i,n) cin >> s[i];
    bool flag = false;
    for(int i =0; i < n; i++) {
        if(s[i] == 'Y') flag = true;
    }
    if(flag) cout << "Four" << endl;
    else cout << "Three" << endl;
}

Measured memory_bytes: 256
N=int(input())
l_A=[int(e) for e in input().split(' ')]
l_B=[int(e) for e in input().split(' ')]
l_C=[int(e) for e in input().split(' ')]

result=sum(l_B)
for i,A in enumerate(l_A):
    if i == 0:
        A_pre=A
        continue
    if A == A_pre+1:
        result += l_C[A_pre-1]
    A_pre=A
print(result)

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

using namespace std;

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

	int count = 0;
	int n = min(a, b);
	while (true)
	{
		if ((a % n == 0) && (b % n == 0))
			if (++count >= k)
				break;
		--n;
	}

	cout << n << endl;
	return 0;
}


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

void solve(long long A, long long B, long long C, long long D) {
    ll CDlcm = (C * D) / __gcd(C, D);
    A--;
    ll tmpA = A - A / C - A / D + A / CDlcm;
    ll tmpB = B - B / C - B / D + B / CDlcm;
    cout << tmpB - tmpA << endl;
}

int main() {
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    long long C;
    scanf("%lld", &C);
    long long D;
    scanf("%lld", &D);
    solve(A, B, C, D);
    return 0;
}


Measured memory_bytes: 3592
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();

        long a = sc.nextLong();
        long b = sc.nextLong();
        long n = sc.nextLong();

        long x = n;
        if (n >= b-1)
            x = b-1;

        System.out.println(calc(a, b, x));
    }

    static long calc(long a, long b, long x) {
        return a * x / b - a * (x / b);
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

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

int main() {
    int N;
    cin >> N;
    vector<int> p(N + 1);
    for (int i = 0; i < N; ++i) cin >> p[i];
    
    vector<int> a(N + 1), b(N + 1);
    for (int i = 0; i < N; ++i) a[i + 1] = (i + 1) * N;
    for (int i = 0; i < N; ++i) b[i + 1] = N * N + 1 - a[i + 1];
    for (int i = 0; i < N; ++i) a[p[i]] += i;
    
    for (int i = 1; i < N; ++i) cout << a[i] + 1 << " ";
    cout << a[N] + 1 << endl;
    for (int i = 1; i < N; ++i) cout << b[i] + 1 << " ";
    cout << b[N] + 1 << endl;
    return 0;
}


Measured memory_bytes: 896
#include<cstdio>
#include<cstring>
int f[100005];
int min(int x,int y) {return x<y?x:y;}
int main()
{
	int n;scanf("%d",&n);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j*=6) f[i]=min(f[i],f[i-j]+1); 
		for(int j=1;j<=i;j*=9) f[i]=min(f[i],f[i-j]+1); 
	}
	printf("%d\n",f[n]);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int N, C, ans, D, cnt;
bool p[1000][1000];
string s[1000];
int main()
{
	cin >> C >> N;
	for(int i = 0; i < N; i++)
		cin >> s[i];
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			p[i][j] = s[i][j] - '0';
	for(int i = 0; i < N / 2; i++)
	{
		for(int j = 0; j < N / 2; j++)
		{
			if(p[i][j] != p[N - i - 1][j] || p[i][j] != p[i][N - j - 1] || p[i][j] != p[N - i - 1][N - j - 1])
			{
				cnt++;
			}
		}
	}
	if(!cnt)
		ans++;
	for(int i = 0; i < C - 1; i++)
	{
		cin >> D;
		for(int j = 0; j < D; j++)
		{
			int r2, c2, r, c;
			bool boo = 0;
			cin >> r2 >> c2;
			r2--; c2--;
			r = r2; c= c2;
			if(r >= N / 2)
			{
				r += -N + 1;
				r *= -1;
			}
			if(c >= N / 2)
			{
				c += -N + 1;
				c *= -1;
			}

			if(p[r][c] != p[N - r - 1][c] || p[r][c] != p[r][N - c - 1] || p[r][c] != p[N - r - 1][N - c - 1])
			{
				boo = 1;
			}
			p[r2][c2] ^= 1;
			if(p[r][c] == p[N - r - 1][c] && p[r][c] == p[r][N - c - 1] && p[r][c] == p[N - r - 1][N - c - 1])
			{
				cnt--;
			}
			else
			{
				if(!boo)
					cnt++;
			}
		}
		if(!cnt)
			ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5068
#include<stdio.h>
#include<stdlib.h>

struct magic{
  int damage;
  int cost;
};

int min_cost(int hp, struct magic m[], int size, int max_damage){
  int *c;
  int i, j, flag;
  int result;

  c = (int *)malloc(sizeof(int)*(hp+max_damage));

  c[0] = 0;
  for(i=1; i<hp+max_damage; i++){
    if(i > m[0].damage){
    	flag = (i%m[0].damage == 0) ? 0 : 1;
      c[i] = (i/m[0].damage + flag)*m[0].cost;
    }else{ /* i >= m[1].damage */
      c[i] = m[0].cost;
    }
  }

  for(j=1; j<size; j++){
    for(i=1; i<hp+max_damage; i++){
      if(i > m[j].damage){
        if(c[i] > c[i-m[j].damage] + m[j].cost){
          c[i] = c[i-m[j].damage] + m[j].cost;
        }
      }else{
        if(c[i] > m[j].cost){
          c[i] = m[j].cost;
        }
      }
    }
  }

  result = c[hp];
  for(i=hp+1; i<hp+max_damage; i++){
    if(c[i] < result){
      result = c[i];
    }
  }

  return result;
}

int main(){
  int h, n;
  int i;
  struct magic *mset;
  int max_damage = 0, result;

  scanf("%d %d", &h, &n);
  mset = (struct magic *)malloc(sizeof(struct magic)*n);
  for(i=0; i<n; i++){
    scanf("%d %d", &(mset[i].damage), &(mset[i].cost));
    max_damage = (mset[i].damage > max_damage ) ? mset[i].damage : max_damage;
  }

  result = min_cost(h, mset, n, max_damage);
  printf("%d", result);

  return 0;
}


Measured memory_bytes: 256
def main():
    S = input()
    mod = pow(10, 9) + 7
    n = len(S)
    # print(S)
    countA, countAB, countABC = 0, 0, 0
    strA, strNonA = 0, 1
    for i in range(n):
        if S[i] == "A":
            countA += strNonA + strA
            strA += strNonA
            strNonA = 0
        elif S[i] == "B":
            countAB += countA
        elif S[i] == "C":
            countABC += countAB
        else:
            countABC = 3*countABC + countAB
            countAB = 3*countAB + countA
            countA = 3*countA + strNonA + strA
            strA = 3*strA + strNonA
            strNonA *= 2

        countA %= mod
        countAB %= mod
        countABC %= mod
        strA %= mod
        strNonA %= mod
        # print(countA, countAB, countABC, strA, strNonA)

    return countABC % mod

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 40176
N, X = map(int, input().split())

#     1 2 3 4 5 6 7 8 9 0 1 2 3 4
# L0:     p   p       p   p
# L1:   b   p   b   b   p   b
# L2: b           p           b

def rec(n, x):

    if n==0: return 1  # レベル0ではpが１つ
    if x==1: return 0  

    all = (1<<(n+1)) - 3  # 1つ低レベルの総数
    p = (1<<(n)) - 1  # 1つ低レベルのパティ数
    
    # 今レベルは b + rec(n-1) + p + rec(n-1) + b
    if x <= all + 1: return rec(n-1, x-1)  #  低レベル + 1の大きさであれば今レベルから採るpはなし
    if x == all + 2: return p + 1  # 低レベル + 2の大きさであれば、低レベルのp数 + 今レベルの中間のp１つ
    if x <= all * 2 + 2: return p + 1 + rec(n-1, x-all-2)  # 上2つを通過しているので少なくとも低レベル1つと中間のpは食べている. 後は低レベル２つ目のp数に帰着
    if x == all * 2 + 3: return p * 2 + 1  # 低レベル2つまるごと + 中間のp
    return -1000000

print(rec(N, X))


Measured memory_bytes: 38384
#include<stdio.h>
int main(void){
	int S,h,m,s;
	scanf("%d",&S);
	h = (S / 3600);//??????????????¨??????
	m = (S % 3600)/60;//??????????????????????§???°
	s = (S % 3600)%60;
	printf("%d:%d:%d\n",h,m,s);
	
	return 0;
}

Measured memory_bytes: 1848
#include <bits/stdc++.h>
 
#define int         long long
#define ll          long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<pii>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
 
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
} 
void solve(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    while(k > 0 && b <= a)b *= 2,k--;
    while(k > 0 && c <= b)c *= 2,k--;
    //cout << a<< " " << b << " " << c;
    if(b > a && c > b)cout << "Yes\n";
    else cout << "No\n";
}
 
signed main()
{
    showoff;
    int T = 1;
    //cin >> T;
    FOR(t,1,T+1){
        solve();
        //cout << "\n";
    }
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...

Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
  int n, d;
  cin >> n >> d;
  vector<vector<int>> vec;
  for(int i=0; i<n; i++){
    vector<int> v(d);
    vec.push_back(v);
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<d; j++){
      int p;
      cin >> p;
      vec[i][j] = p;
    }
  }
  int count = 0;
  for(int i=0; i<n-1; i++){
    for(int j=i+1; j<n; j++){
      double sum = 0;
      for(int a=0; a<d; a++){
        double dis = vec[i][a] - vec[j][a];
        sum += dis * dis;
      }
      double result = sqrt(sum);
      if(result == int(result)){
        count++;
      }
    }
  }
  cout << count << endl;
  return 0;
}

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


int main(void){
    ll A,B;cin>>A>>B;

    for(int i=0;i<1300;i++){
        ll a = (i*8)/100;
        ll b = (i*10)/100;

        if(a==A && b==B){
            cout<<i<<endl;
            return 0;
        }
    }

    cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256
//Name: Pankaj Mandrawal (pankaj_m05)
//Problem: FROG 2
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mod 10000000009
#define sz(c) int((c).size())
#define sortall(x) sort(all(x))         
#define PI 3.1415926535897932384626     
#define all(c) (c).begin(), (c).end()
#define clr(x) memset(x, 0, sizeof(x))  
#define INF numeric_limits< int >::max() 
#define MIN numeric_limits< int >::min()
#define rall(c) (c).rbegin(), (c).rend()
#define deb(x) cerr << #x << " = " << x << endl
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int) n; ++i)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, l, r) for(int i = (int)(l); i < (int)(r); ++i)
#define tr(c, it) for(typeof(c).begin() it = c.begin(); it != c.end(); it++)
#define deb2(x, y) cerr << #x << " = " << x << "," << #y << " = " << y << endl

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<ll> vill;
typedef vector<vi> vvi;
typedef pair <int,int> pi; 

ll mypow(ll x, ll y) { 
    if (y == 0) 
        return 1; 
    ll p = mypow(x, y / 2) % mod; 
    p = (p * p) % mod; 
    if (!(y & 1)) 
        return p;
    return (p * x) % mod; 
} 

void plssolve() {
	int n, k; cin >> n >> k;
	vi arr(n);
	for(auto &it: arr) 
		cin >> it;
	vi dp(n, INF);
	dp[0] = 0;
	for(int it = 0; it < n; ++it) {
		for(int j = it + 1; j < it + k + 1; ++j) {
			if(j < n) 
				dp[j] = min(dp[j], dp[it] + abs(arr[it] - arr[j]));
		}
	}
	cout << dp[n - 1] << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);
    cout << fixed;
    int t = 1;
    //cin >> t;
    while(t--) {
        plssolve();
    }
    return 0;
}

Measured memory_bytes: 1024
public partial class IntroductionToProgramming{
	public static void Main(){
		string[] line = System.Console.ReadLine().Split(' ');

		int h = int.Parse(line[0]);
		int w = int.Parse(line[1]);

		while (!(h == 0 && w == 0))
		{
			string f = new string('#', w);
			string s = new string('.', w - 2);
			System.Console.WriteLine(f);
			for (int i = 0; i < h - 2; i++ )
			{
				System.Console.WriteLine("#" + s + "#");
			}
			System.Console.WriteLine(f);
			System.Console.WriteLine(string.Empty);

			string[] line2 = System.Console.ReadLine().Split(' ');

			h = int.Parse(line2[0]);
			w = int.Parse(line2[1]);
		}
	}
}

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

using namespace std;
typedef long long ll;

const int MAX_N = 55;

int n,a,x;
ll dp[2][MAX_N*MAX_N][MAX_N];

int main()
{
	cin >> n >> a;
	dp[0][0][0]=dp[1][0][0]=1;
	for (int i=1; i<=n; i++)
	{
		cin >> x;
		for (int k=1; k<=n; k++)
		{
			for (int s=0; s<=n*a; s++)
				dp[i&1][s][k]=dp[(i+1)&1][s][k];
			for (int s=x; s<=n*a; s++)
				dp[i&1][s][k]+=dp[(i+1)&1][s-x][k-1];

		}
	}
	ll ans=0;
	for (int k=1; k<=n; k++)
		ans+=dp[n&1][a*k][k];
	cout << ans;
	return 0;
}

Measured memory_bytes: 2432
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()
#define sz(a) (int)a.size()
#define filename "infinite"
const int inf = (1ll << 30) - 1;
const int N = (int)2e5 + 5;
using namespace std;

int n, h;
char s[N], st[N];


void solve() {
	scanf("%s", s);
	n = strlen(s);
	for (int i = 0; i < n; i++) {
		if (s[i] == 'S' || h == 0 || st[h-1] == 'T') {
			st[h++] = s[i];
		} else {
			h--;
		}
	}
	printf("%d\n", h);
	
}

int main () {

	solve();


    return 0;
}




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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

int main(int argc, char **argv)
{
	ll N; cin >> N;
	vector<ll> A(N), B(N);
	REP(i, N)
		cin >> A[i] >> B[i];
	vector<ll> index(N);
	iota(ALL(index), 0ll);

	sort(ALL(index), [&](auto &a, auto &b)
					 {
						 return (A[a] + B[a] > A[b] + B[b]);
					 });

	ll res{0};
	bool ist{true};
	REP(i, N)
	{
		if (ist)
			res += A[index[i]];
		else
			res -= B[index[i]];
		ist ^= true;
	}

	std::cout << res << std::endl;
}


Measured memory_bytes: 2560
n = int(input())
h = list(map(int, input().split()))

dp = [0] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))

print(dp[-1])

Measured memory_bytes: 13980
//package Beginner121;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int H = s.nextInt();
        int W = s.nextInt();
        int h = s.nextInt();
        int w = s.nextInt();
        System.out.println(H*W + h*w - h*W - H*w);

    }
}

Measured memory_bytes: 21588
/***************************************** 
****       Solution by SlavicG        ****
*****************************************/
 
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm> 
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;++i)
#define MX 10000000001
#define pow2(a) ((a)*(a))
#define pb push_back
#define vair <vector<pair<int,int>>
#define vi vector<int>
#define mp make_pair
#define pf push_front
#define all(v) v.begin(), v.end()
#define endl "\n"
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 int longestIncreasingSubsequenceLenghtDP(int a[],int n){
    int dp[n],ans=0;
    for(int k = 0;k<n;k++){
        dp[k] = 1;
        for(int i = 0;i<k;i++){
            if(a[i] <= a[k]){
                dp[k] = max(dp[k],dp[i] + 1);
                ans = max(dp[k],ans);
            }
        }
    }
    return ans;
 }
int result[1000] = {0};
int factDP(int n) 
{
   if (n >= 0) {
      result[0] = 1;
      for (int i = 1; i <= n; ++i) {
         result[i] = i * result[i - 1];
      }
      return result[n];
   }
}
bool checkPrime(int n)
{
    if(n<2) return false;
    for(int x = 2;x*x <=n;x++)
    {
        if(n%x == 0)return false;
    }
    return true;
}
vector<int> primeFactors(int n){
    vector<int> f;
    for(int x = 2;x*x<=n;x++){
        while(n%x==0){
            f.push_back(x);
            n/=x;
        }
    }
    if(n>1)f.push_back(n);
    return f;
}
int binary_Search_Classic(int n, int arr[],int target){
	int l,r,mid;
	l=0;
	r=n-1;
	while(l<=r){
		mid= l+(r-l)/2;
		if(arr[mid] == target){
			return mid;
		}
		if(arr[mid] < target){
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	return -1;
	
}
vector<int> Two_PointerSumOfTwo(vector<int> arr, int target)
{
	int l = 0, r = arr.size()-1;
	vector<int> ans;
	while(l<r){
		if(arr[l] + arr[r] == target)
		{
			ans.push_back(l);
			ans.push_back(r);
			break;
		}else if(arr[l] + arr[r] > target){
			r--;
		}else{
			l++;;
		}
	}
	return ans;
}
int countDistinctCharsString(string s) {
    unordered_map<char, int> m; 
    for (int i = 0; i <(int)s.length(); i++) { 
        m[s[i]]++; 
    }
    return m.size(); 
} 
int main()
{
	int h,n;
	cin >> h >> n;
	int ans = h/n;
	if(h%n!=0)
	{
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
N, M = map(int, input().split())
mvals = list(map(lambda x: -int(x), input().split()))

import heapq
heapq.heapify(mvals)

for _ in range(M):
    price = heapq.heappop(mvals)
    heapq.heappush(mvals, price / 2)

res = sum(map(lambda x:int(-x), mvals))
print(res)

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

using namespace std;

// MACROS

#define ll long long
#define ull unsigned long long
#define ld long double

#define vi vector<int>
#define vll vector<ll>
#define vld vector<ld>
#define u_s unordered_set

#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i, n) for (ll (i) = 0; i < n; i++)
#define FORN(i, a, b) for (ll (i) = a; i < b; i++)
#define FORE(i, l) for (auto (i) : l)

#define pb push_back
#define pob pop_back
#define emp emplace

#define in(n) cin >> (n);
#define debug(n) cout << #n << ": " << n << '\n';

// FUNCTIONS

template< typename T >
inline T gcd(T a, T b) { if (b) return gcd(b, a % b); return a; }

template< typename T >
inline T ext_gcd(T a, T b, T & x, T & y) { if (a == 0) { x = 0; y = 1; return b; } T x1, y1; T g = ext_gcd(b % a, a, x1, y1); x = y1 - (b / a) * x1; y = x1; return g; }

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    ll a, b;
    cin >> a >> b;
    if (a + b == 3) cout << 3 << '\n';
    else if (a + b == 4) cout << 2 << '\n';
    else cout << 1 << '\n';    
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    char str[100001];
    int i,j,x,ans=0;
    scanf("%s",&str);
    for(j=0;j<26;j++){
        for(i=0;str[i]!='\0';i++){
            x = str[i];
            if(x==(j+97)){
                break;
            }
            if(str[i+1]=='\0'){
                putchar(j+97);
                ans = 1;
                break;
            }
        }
        if(ans==1) break;
    }
    if(ans==0){
        printf("None\n");
    }
    return 0;
}

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

using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr ll mod = static_cast<ll>(1e9 + 7);

int n, k;
double dp[200005];
int main() {
	std::cin >> n >> k;

	double tmp = 1.0 / n;
	std::fill(dp, dp + n + 1, tmp);
	dp[0] = 0;
	bool check = true;

	while (check) {
		bool ok = false;

		for (int i = k - 1; i > 0; --i) {
			if (dp[i] != 0)
				ok = true;
			dp[2 * i] += dp[i] / 2;
			dp[0] += dp[i] / 2;
			dp[i] = 0;
		}

		check = ok;
	}

	std::cout << std::setprecision(10) << std::fixed << 1.0 - dp[0] << std::endl;
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<malloc.h>
#include<math.h>
#include<x86intrin.h>


int my_gets(char *buf,int nBuf,FILE *fp){
    int ch;

    while(--nBuf >0){
        ch=getc(fp);
        if(ch==EOF || ch=='\n')
            break;
        *(buf++)=(char)ch;
    }
    *(buf)='\0';

    return nBuf;
}

void InputIntAry(int *a,int nDigit,int N){      //nDigitは想定される最大桁数
    char *buf,*ptr;

    buf=(char*)malloc( (N*(nDigit+2)) * sizeof(char) );
    my_gets(buf,N*(nDigit+2),stdin);

    ptr=strtok(buf," ");
    while(ptr!=NULL && N-->0){
        *(a++)=atoi(ptr);
        ptr=strtok(NULL," ");
    }
    free(buf);
}

int CmpInt(const void *a, const void *b){        //b-aを返す(qsortなら降順)
    return *((int*)b)- *((int*)a);
}

int main(){
    uint64_t cnt=0;
    int N;
    int A[100001],B[100000];

    scanf("%d%*c",&N);
    InputIntAry(A,10,N+1);
    InputIntAry(B,10,N);

    for(int i=0; i<N; i++){
        if(A[i] >= B[i]){  //倒しきれない or 拮抗
            cnt += B[i];
        }
        else{
            B[i] -= A[i];
            cnt += A[i];

            if(A[i+1] >= B[i]){
                A[i+1] -= B[i];
                cnt += B[i];
            }
            else{
                cnt += A[i+1];
                A[i+1] = 0;
            }
        }
    }
    printf("%llu\n",cnt);

    return 0;
}

Measured memory_bytes: 1996
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> T;
typedef pair<long double , ll> Ps;
typedef pair<ll, bool> Pb;

const ll INF = 1e18;
const ll fact_table = 3200008;
long double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll, vector<ll>, greater<ll> > pqls;
priority_queue <P, vector<P>, greater<P> > pqps;
//small priority queue
//top pop

ll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
ll dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
char dir[] = "DRUL";
//↓,→,↑,←

#define endl "\n"
#ifdef ENJAPMA
#undef endl
#endif
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)();
#define pc(x) cout << x << ",";
#define rep(i, n) for (ll i = 0; i < (n); i ++)

// const ll mod = 998244353ll;
const ll mod = 1000000007ll;

ll mypow(ll a, ll b, ll mod) {ll x = 1; while (b) {while (!(b & 1)) {(a *= a) %= mod; b >>= 1;}(x *= a) %= mod; b--;} return x;}
void YES(bool cond) { if (cond) { p("YES");} else { p("NO");} return;}
void Yes(bool cond) { if (cond) { p("Yes");} else { p("No");} return;}

ll line_count = 0;

void line(){

    line_count ++;
    string s = (line_count % 2) ? "v-v-v-v-v-v-v-v-v-v" : "^-^-^-^-^-^-^-^-^-^";
    cout << endl << s << endl << endl;
}

/*
ll fact[fact_table + 5],rfact[fact_table + 5];

void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/

bool multicase = false;

ll n, m, k, num, a, b, c, d, e, h, q, ans, sum;
string s;
ll used[1000005];
ll x[1000005];

bool check(ll num, ll div){
    if(num == div) {
        if (used[div] <= 1) {
            return false;
        } else {
            return true;
        }
    } else {
        return (used[div]);
    }
}
void solve() {
    cin >> n;
    for(ll i=0;i<n;i++){
        cin >> x[i];
        a = x[i];
        used[a] ++;
    }
    for(ll i=0;i<n;i++){
        ll num = x[i];
        bool dame = false;
        for(ll j=1;j*j<=num;j++){
            if(num % j == 0){
                dame = dame || check(num, num / j);
                dame = dame || check(num, j);
            }
        }
        if(!dame)ans ++;
    }
    p(ans);
    return;
}

int main() {
    // init();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;
    if (multicase) {
        cin >> q;
    } else {
        q = 1;
    }
    while (q--) {
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    // solve();
    return 0;
}
















Measured memory_bytes: 12824
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pr pair<int, int>
#define v1d vector<int>
#define mp make_pair
#define pb push_back
#define v1p vector<pr>
#define vb vector<bool>
#define v2d vector<vector<int>>
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define S(v) sort(v.begin(), v.end())
#define RS(v) sort(v.rbegin(), v.rend())
#define eb emplace_back
#define endl "\n"
#define MOD 1000000007
#define pqx priority_queue <int>
#define pqn priority_queue <int, v1d, greater<int> >
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int32_t main() {
    fio
    int n; cin >> n;
    v1d a(n), b(n);
    for(int i=0; i<n; ++i) {
        cin >> a[i] >> b[i];
    }
    S(a);
    S(b);
    int l, r;
    if(n & 1) {
        l = a[n / 2];
        r = b[n / 2];
    }
    else {
        l = a[(n / 2) - 1] + a[n / 2];
        r = b[(n / 2) - 1] + b[n / 2];
    }
    cout << r - l + 1;
}

Measured memory_bytes: 6364
def straight?(cards)
  _cards = cards.dup
  _cards[0] += 13 if _cards[0] == 1 && _cards[1] == 10#1,10,?,?,?だったら14,10,11,12,13に絞って良い

  _cards.sort! #再ソート
  f = true
  for i in 1..4 #1,2,3,4,5などの連番判定
    f = false unless _cards[i] == _cards[i-1]+1
  end
  return f
end

def card_group_by(cards)
  return cards.group_by{|card|
    card
  }.map{|k, v|
    [k, v.size]
  }.sort_by{|e| #枚数が多い順に並べる
    -e[1]
  }
end

def one_pair?(cards)
  gcards = card_group_by(cards)
  if gcards[0][1] == 2 && !two_pair?(cards) then
    return true
  end
  return false
end

def two_pair?(cards)
  gcards = card_group_by(cards)
  if gcards[0][1] == 2 && gcards[1][1] == 2 then
    return true
  end
  return false
end

def three_card?(cards)
  gcards = card_group_by(cards)
  if gcards[0][1] == 3 && !full_house?(cards) then
    return true
  end
  return false
end

def full_house?(cards)
  gcards = card_group_by(cards)
  if gcards[0][1] == 3 && gcards[1][1] == 2 then
    return true
  end
  return false
end

def four_card?(cards)
  gcards = card_group_by(cards)
  if gcards[0][1] == 4 then
    return true
  end
  return false
end

while s = gets
  break if s == nil
  cards = s[0..-2].split(",").map{|card|
    card.to_i
  }.sort
  if four_card?(cards) then
    puts "four card"
  elsif full_house?(cards) then
    puts "full house"
  elsif straight?(cards) then
    puts "straight"
  elsif three_card?(cards) then
    puts "three card"
  elsif two_pair?(cards) then
    puts "two pair"
  elsif one_pair?(cards) then
    puts "one pair"
  else
    puts "null"
  end
end

Measured memory_bytes: 5100
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int A, B, C;
  int result;
  cin >> A >> B >> C;
  if(A == B && B == C){
    result = 1;
  } else if(A == B || B == C || C == A){
    result = 2;
  } else{
      result = 3;
  }
  cout << result;
}

Measured memory_bytes: 256
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()
    stk = []
    pool_stk = []

    ans = 0
    for i, e in enumerate(S):
        if e=='\\':
            stk.append(i)
        elif e=='/':
            if stk:
                idx_d = stk.pop()
                pool_layer = i - idx_d
                ans += pool_layer
                if pool_stk and idx_d<pool_stk[-1][0]:
                    merged_pool = 0
                    while pool_stk and idx_d<pool_stk[-1][0]:
                        pool_tmp = pool_stk.pop()
                        merged_pool += pool_tmp[1]
                    pool_stk.append((idx_d, merged_pool+pool_layer))
                else:
                    pool_stk.append((idx_d, pool_layer))
    
    print(ans)
    print(len(pool_stk), *[i[1] for i in pool_stk])

if __name__ == '__main__':
    resolve()



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

#define int long long

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

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

const int INF=1001001001001001001ll;

int N,Q;
int B[222222];

int acc[222222];
vint qs[222222];

int dp[222222];

struct segtree{
    static const int SEG=1<<18;
    vint dat;
    segtree():dat(SEG*2,INF){}
    void update(int k,int x){
        k+=SEG-1;
        chmin(dat[k],x);
        while(k){
            k=(k-1)/2;
            dat[k]=min(dat[k*2+1],dat[k*2+2]);
        }
    }
    int query(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return INF;
        if(a<=l&&r<=b)return dat[k];
        return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
    }
};

signed main(){
    cin>>N;
    rep(i,N)cin>>B[i];
    rep(i,N)acc[i+1]=acc[i]+1-B[i];
    cin>>Q;
    rep(i,Q){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        qs[l].pb(r);
    }

    fill_n(dp,222222,INF);
    dp[0]=0;
    segtree seg;

    for(int i=0;i<N;i++){
        for(auto &r:qs[i]){
            int tmp=seg.query(i,r);
            chmin(tmp,dp[i]-acc[i]);
            chmin(dp[r+1],tmp+acc[r+1]);
            seg.update(r,tmp);
        }
        chmin(dp[i+1],dp[i]+B[i]);
    }

    cout<<dp[N]<<endl;
    return 0;
}


Measured memory_bytes: 18816
import math

X=int(input())
ans = X

def is_prime(n):
  if n==1:
    return False
  for i in range(2, int(math.sqrt(n))+1):
    if n%i == 0:
      return False
  return True

while True:
  if is_prime(ans):
    print(ans)
    exit()
  ans+=1

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

int main()
{
	auto check = [](bool same, char l, char r) {
		return same == (l == r);
	};

	int n;
	string s;
	cin >> n >> s;

	for (int fst = 0; fst < 2; fst++)
	{
		for (int snd = 0; snd < 2; snd++)
		{
			string ans(n, ' ');
			ans[0] = "WS"[fst];
			ans[1] = "WS"[snd];

			for (int i = 1; i < n - 1; i++)
			{
				ans[i + 1] = "WS"[((ans[i] == 'S') == (s[i] == 'o')) == (ans[i - 1] == 'S')];
			}

			if (check(((ans[n - 1] == 'S') == (s[n - 1] == 'o')), ans[0], ans[n - 2]) && check(((ans[0] == 'S') == (s[0] == 'o')), ans[1], ans[n - 1]))
			{
				cout << ans << endl;
				return 0;
			}
		}
	}

	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
  int n,o,p,x;
  x=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>o>>p;
    if(o==p){
      x++;
      if(x==3){
        i=n;
      }
    }else{
      x=0;
    }
  }if(x==3){
    cout<<"Yes\n";
  }else{
    cout<<"No\n";
  }
  return 0;
}

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

int main() {
    int x, y;
    cin >> x >> y;
    string s[x][y];
    bool T = false;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            cin >> s[i][j];
        }
    }
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (s[i][j] == "snuke") {
                char c = j + 'A';
                printf("%c%d\n", c, i+1); 
                T = true; 
                break;
            }
        }
        if (T) break;
    }
}

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

int main() {
    int64_t K;
    cin >> K;
    int64_t ans = 0;

    for (int64_t a = 1; a <= K; a++) {
        for (int64_t b = 1; b <= K; b++) {
            for (int64_t c = 1; c <= K; c++) {
                ans += gcd(gcd(a, b), c);
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3636
from heapq import heappush, heappop
while True:
  n, m = map(int, input().split())
  if n == 0:break
  s, p, g = input().split()
  edges = {}
  for _ in range(m):
    a, b, d, t = input().split()
    if a not in edges:edges[a] = []
    if b not in edges:edges[b] = []
    d = int(d)
    t = int(t)
    edges[a].append((b, d // 40 + t))
    edges[b].append((a, d // 40 + t))
  
  INF = 10 ** 20
  def score(start, goal):
    dist = {name:INF for name in edges.keys()}
    dist[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
      total, name = heappop(que)
      if name == goal:
        return total
      for to, cost in edges[name]:
        if dist[to] > total + cost:
          dist[to] = total + cost
          heappush(que, (total + cost, to))
  
  print(score(s, p) + score(p, g))


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

int n;
vector<int> a;
vector<int> g[101010];
int root;

static const int INF = 0x3f3f3f3f;

int dfs(int v, int prev) {
        int sum = 0;
        int ma = -1;
        for (auto u : g[v]) {
                if (u == prev) continue;
                int get = dfs(u, v);
                ma = max(ma, get);
                sum += get;
        }
        if (ma == -1) return a[v];
        if (sum > 2 * a[v] || sum < a[v]) throw -1;
        int t = 2 * a[v] - sum;
        if (v == root) {
                if (t == 0) return INF;
                else throw -1;
        }
        if (sum >= 2 * ma) { 
                return t;
        } else {
                int possible = sum - ma;
                if (possible >= a[v] - t) return t;
                else throw -1;
        }
}

int main() {
        cin >> n;
        a.resize(n);
        for (int i = 0; i < n; i ++) cin >> a[i];
        for (int i = 0; i < n - 1; i ++) {
                int p, q;
                cin >> p >> q;
                p --, q --;
                g[p].push_back(q);
                g[q].push_back(p);
        }
        if (n == 2) {
                cout << (a[0] == a[1] ? "YES" : "NO") << endl;
                return 0;
        }
        for (int i = 0; i < n; i ++) if (g[i].size() != 1) {
                root = i;
                break;
        }
        //cerr << root << endl;
        try {
                if (dfs(root, -1) == INF) cout << "YES" << endl;
        }
        catch (int err) {
                cout << "NO" << endl;
                return 0; 
        }
        return 0;
}



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

template <typename T>
class SegmentTree
{
    std::vector<T> arr;
    const std::size_t size;
    const std::function<T(const T, const T)> operation;
    const T initial_value;

    std::size_t calc_size(const std::size_t N) const
    {
        std::size_t n = 1;
        while (n < N + 1)
        {
            n *= 2;
        }
        return n;
    }

    void initialize_array()
    {
        this->arr = std::vector<T>(2 * this->size - 1, this->initial_value);
    }

    T query(const std::size_t a, const std::size_t b, const std::size_t k, const std::size_t l, const std::size_t r) const
    {
        if (r <= a || b <= l)
        {
            return this->initial_value;
        }
        if (a <= l && r <= b)
        {
            return this->arr[k];
        }
        else
        {
            return this->operation(
                this->query(a, b, 2 * k + 1, l, (l + r) / 2),
                this->query(a, b, 2 * k + 2, (l + r) / 2, r));
        }
    }

public:
    SegmentTree(const std::size_t N, const std::function<T(const T, const T)> func, const T init) : size(this->calc_size(N)), operation(func), initial_value(init)
    {
        this->initialize_array();
    }

    void update(const std::size_t idx, const T value)
    {
        std::size_t modify_idx = idx;
        modify_idx += this->size - 1;
        this->arr[modify_idx] = value;
        while (modify_idx > 0)
        {
            modify_idx = (modify_idx - 1) / 2;
            this->arr[modify_idx] = this->operation(this->arr[modify_idx * 2 + 1], this->arr[modify_idx * 2 + 2]);
        }
    }

    T query(const std::size_t idx) const
    {
        return this->arr[idx + this->size - 1];
    }

    // [idx_a, idx_b)
    T query(const std::size_t idx_a, const std::size_t idx_b) const
    {
        return this->query(idx_a, idx_b, 0, 0, this->size);
    }

    T operator[](const std::size_t idx) const
    {
        return this->arr[idx + this->size - 1];
    }
};

int main()
{
    size_t N;
    int K;
    cin >> N >> K;

    SegmentTree<int> st(
        300005,
        [](int a, int b) { return max(a, b); },
        0);

    int A;
    for (size_t i = 0; i < N; i++)
    {
        cin >> A;
        A++;
        size_t l = max(A - K, 1);
        size_t r = min(A + K + 1, 300005);
        int maximum = st.query(l, r);
        st.update(A, maximum + 1);
    }
    int ans = 0;
    for (int i = 1; i < 300005; i++)
    {
        ans = max(ans, st.query(i));
    }
    cout << ans << endl;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;


struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};

ll pw(ll x, ll y) {
    ll res=1;
    while (y) {
	if (y%2) res=res*x%mod;
	x=x*x%mod;y=y/2;
    }
    return ((res%mod)+mod)%mod;
}

int n, m;
int u[maxn], v[maxn];
ll w[maxn];

ll x;

vector<int> ord;

ll st(int mustUse=-1) {
    dsu0 dsu;
    dsu.init(n);
    ll tot = 0;
    if (~mustUse) {
	tot += w[mustUse];
	dsu.join(u[mustUse], v[mustUse]);
    }
    for (int i: ord) {
	if (dsu.join(u[i],v[i])) {
	    tot += w[i];
	}
    }

    return tot;
}

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

    cin>>n>>m;
    cin>>x;
    for (int i=0; i<m; i++) {
	cin>>u[i]>>v[i]>>w[i];
	--u[i]; --v[i];
    }
    
    ord.resize(m);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i, int j) {
	    return w[i]<w[j];
	});


    ll mst = st();
    if (mst > x) {
	out(0);
    }

    
    ll slack = 0;
    ll target = 0;

    for (int i=0; i<m; i++) {
	ll res = st(i);
	if (res == x) {
	    target++;
	} else if (res > x) {
	    slack++;
	}
    }

    // watch(slack);
    // watch(target);

    if (target == 0) {
	out(0);
    }


    
    if (mst == x) {
	// Any edge that is part of an MST can be whatever colors, as long as not all same
	ll res = pw(2, slack) * (pw(2, target)-2) % mod;
	res %= mod;
	res += mod;
	res %= mod;
	out(res);
    }

    assert(x > mst);


    // Edges on X-ST can be mostly whatever, but at least 1 must be different from the "base MST" edges
    // so that we are exactly 1 tweak away from the same color MST to the X-ST.
    ll res = 2  *  (pw(2, target)-1)%mod  *  pw(2, slack) % mod;

    res %= mod;
    res += mod;
    res %= mod;
    cout<<res<<endl;
    
    return 0;
}


// 1. if mst<x, all edges of mst must be same color, otherwise we'd pick it over x-st/
// 2. mst needs to be 1 edge tweak away from x-st. this is because if one of the "tweaked" edges is opposite color,
// then we'd just pick that "semi-tweaked" st instead of tweaking all the way to the full x-st


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

int H,W;
std::vector<std::pair<int,int>> dirs = { {-1,0}, {0,1}, {1,0}, {0,-1} };
int ans = 0;
std::vector<std::vector<int>> A;

void sol ( int count, std::vector<std::pair<int,int>> l ) {
  if ( count == H*W ) return ;

  std::vector<std::pair<int,int>> rtn;
  for(int i=0; i<l.size(); i++) {
    for( std::pair<int,int> dir : dirs ){
      std::pair<int,int> next = {dir.first + l[i].first, dir.second + l[i].second} ;
      if ( !(next.first >= 0 && next.first < H && next.second >=0 && next.second < W) ) continue;
      if ( A[next.first][next.second] == 0 ) {
        A[next.first][next.second] = 1;
        rtn.push_back(next);
        count++;
      }
    }
  }
  ans++;
  sol(count, rtn);
}

int main (void) {
  std::cin >> H >> W;

  A.resize(H); for(int i=0; i<H; i++) A[i].resize(W);

  std::vector<std::pair<int,int>> l;

  int count = 0;
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      char a; std::cin >> a;
      if ( a == '#' ) {
        A[i][j] = 1;
        l.push_back( {i, j} );
        count++;
      }
      if ( a == '.' ) A[i][j] = 0;
    }
  }

  sol(count, l);
  std::cout << ans << std::endl;

  return 0;
}

Measured memory_bytes: 22784
<?php
fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%s", $s);
$r = count_chars($s, 1);
$p = $x = 0;
for ($i = 0; $i < $n - 1; $i++) {
	$d = ord($s[$i]);
	$r[$d]--;
	if ($r[$d] && !isset($l[$d])) {
		$l[$d] = 1;
		if (++$p > $x) $x = $p;
	} elseif (!$r[$d] && isset($l[$d])) {
		$p--;
	}
}
echo $x;

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

typedef pair<long long, long long> P;

int main(){
    int n, w;
    cin >> n >> w;
    vector<long long> ans(w + 1, 0);
    int x, y;
    queue<P> que;
    for (int i = 0; i < n; i++){
        cin >> x >> y;
        for (int j = 0; j <= w; j++){
            if (x + j > w) break;
            que.push({x + j, max(ans[x + j], ans[j] + y)});
        }
        while (que.size()){
            ans[que.front().first] = que.front().second;
            que.pop();
        }
    }
    cout << *max_element(ans.begin(), ans.end()) << endl;
}

Measured memory_bytes: 2760
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  int x, a;
  cin >> x >> a;
  if (x < a) {
    cout << 0 << "\n";
  } else {
    cout << 10 << "\n";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

int main(){
    ll k;
    string s;
    cin >> k >> s;
    if (s.size() <= k) cout << s << endl;
    else
        cout << s.substr(0, k) << "..." << endl;
}



Measured memory_bytes: 3628