akhauriyash/Code-Regression huggingface dataset:
/**********************************************
 * author : deepak nayan
 * file   : e:/Solutions/atcoder/abc051_b.cpp
 * time   : Sat May  2 22:11:46 2020
 * quest  : B - Sum of Three Integers
 *********************************************/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int k, s, count = 0;
  cin >> k >> s;
  for (int i = 0; i <= k; ++i) {
    for (int j = 0; j <= k; ++j) {
      int rem = s - (i + j);
      if (rem >= 0 && rem <= k)
        count++;
    }
  }
  cout << count << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,k,tinggi,ayy=0;
int main () {
cin  >> n >> k;
for (int i=1; i<=n; i++) {
	cin >> tinggi;
		if (tinggi >= k) {
			ayy++;
		}
}
	cout << ayy << endl;
}


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

int main() {
  int n; cin >> n;
  int v[n], c[n];
  for (auto &a : v) cin >> a;
  for (auto &b : c) cin >> b;
  int ans = 0;
  for (int i=0; i<n; ++i) ans += max(v[i]-c[i], 0);
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node {
  int key;
  Node *next, *prev;
};

Node *nil;

Node* listSearch(int key) {
  Node *cur = nil->next;
  while (cur != nil && cur->key != key) {
    cur = cur->next;
  }
  return cur;
}

void init() {
  nil = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void printList() {
  Node *cur = nil->next;
  int isf = 0;
  while(1) {
    if (cur == nil) break;
    if (isf++ > 0) printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t) {
  if (t == nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst() {
  deleteNode(nil->next);
}

void deleteLast() {
  deleteNode(nil->prev);
}

void deleteKey(int key) {
  deleteNode(listSearch(key));
}

void insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main() {
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;

  scanf("%d", &n);
  init();

  for (i = 0; i < n; i++) {
    scanf("%s%d", com, &key);
    if (com[0] == 'i') {
      insert(key);
      np++;
      size++;
    } else if (com[0] == 'd') {
      if (strlen(com) > 6) {
        if (com[6] == 'F') {
          deleteFirst();
        } else if (com[6] == 'L') {
          deleteLast();
        }
      } else {
        deleteKey(key);
        nd++;
      }
      size--;
    }
  }

  printList();
  return 0;
}



Measured memory_bytes: 33804
#include <iostream>
using namespace std;
int main () {
    string s, c;
    int count = 0;
    cin >> c;
    for (int i = 0; i < c.length(); i++)
        if ('A' <= c[i] && c[i] <= 'Z')
            c[i] += 32;
    while (cin >> s) {
        for (int i = 0; i < s.length(); i++)
            if ('A' <= s[i] && s[i] <= 'Z')
                s[i] += 32;
        if (s == c)
            count++;
    }

    cout << count << '\n';

} 


Measured memory_bytes: 3176
#include <iostream>
#include <cmath>
#include <map>

#define ll long long
#define max(A, B) ((A) > (B) ? (A) : (B))
#define min(A, B) ((A) < (B) ? (A) : (B))

using namespace std;

void perform() {
  ll n, w; cin >> n >> w;
  ll dp[n+1][w+1];
  ll v, t;
  for (int i = 0; i < n+1; i++) {
    v = t = 0;
    if (i > 0) cin >> v >> t;
    for (int j = 0; j < w+1; j++) {
      dp[i][j] = 0;
      if (i == 0);
      else if (v > j) dp[i][j] = dp[i-1][j];
      else dp[i][j] = max(dp[i-1][j], dp[i-1][j - v] + t);
    }
  }
  cout << dp[n][w] << endl;
}

int main() {
  ll t = 1; //cin >> t;
  while(t--){perform();}
  return 0;
}


Measured memory_bytes: 79104
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
#include <string.h>
#include <numeric>
using namespace std;

#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(i,v) for(auto &(i):(v))
#define eachr(i,v) for(auto &(i)=(v).rbegin();(i)!=(v).rend();(i)++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())

//typedef complex<double> P;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));}
bool deq(double a,double b) {return abs(a-b)<eps;}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;



int n, a[404], s[404], dp[404][404];

int rec(int l, int r) {
	if (l==r) return 0;
	int &res = dp[l][r];
	if (res!=-1) return res;
	res = 1ll<<60;
	reps(i,l,r) chmin(res, rec(l,i) + rec(i+1,r) + s[r]-s[l-1]);
	return res;
}

signed main() {
	cin >> n;
	reps(i,1,n+1) cin >> a[i];
	reps(i,1,n+1) s[i] += a[i], s[i+1] += s[i];
	memset(dp, -1, sizeof(dp));
	cout << rec(1,n) << endl;
}

Measured memory_bytes: 1536
#include <stdio.h>
#include <math.h>
int main()
{
    int a, b, c, t;
    scanf("%d %d %d", &a, &b, &c);
    if(a<b)
    {
        t=a;
        a=b;
        b=t;
    }
    if(a<c)
    {
        t=a;
        a=c;
        c=t;
    }
    if(c>b)
    {
        t=c;
        c=b;
        b=t;
    }
    printf("%d\n", a-c);

    return 0;

}


Measured memory_bytes: 128
// inputに入力データ全体が入る
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    tmp0 = input[0].split(" ");
    A = Number(tmp0[0]);
    B = Number(tmp0[1]);
   
    ans = 0;
    if(A<=5){
        ans=0;
    }else if(6<=A && A <= 12){
        ans = B/2
    }else{
        ans=B
    }
    console.log(ans);
  }
  //*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
  Main(require("fs").readFileSync("/dev/stdin", "utf8"));
//   Main("30 100\n");

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

int main() {
	int N;
	cin >> N;
	for( size_t i = 0; i < N; i++ ) {
		string S;
		cin >> S;
		set<string>SS;
		SS.insert( S );
		for( int i = 1; i < S.size(); i++ ) {
			string T, U;
			T = S.substr( i );
			U = S.substr( 0, i );
			SS.insert( U + T );
			SS.insert( T + U );
			reverse( T.begin(), T.end() );
			SS.insert( U + T );
			SS.insert( T + U );
			reverse( U.begin(), U.end() );
			SS.insert( U + T );
			SS.insert( T + U );
			reverse( T.begin(), T.end() );
			SS.insert( U + T );
			SS.insert( T + U );
		}
		reverse( S.begin(), S.end() );
		SS.insert( S );
		cout << SS.size() << endl;
	}
}

Measured memory_bytes: 3100
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static Map<Integer, ArrayList<Integer>> map;
	public static int N;
	public static void main(String[] args) {
		Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		N = scan.nextInt();
		int M = scan.nextInt();
		Integer []p = new Integer[N];
		int []x = new int[M];
		int []y = new int[M];
		for(int i = 0; i < N; i++) {
			p[i] = scan.nextInt();
		}
		for(int i = 0; i < M; i++) {
			x[i] = scan.nextInt();
			y[i] = scan.nextInt();
		}
		scan.close();

		// 隣接リスト
		map = new TreeMap<Integer, ArrayList<Integer>>();
		for(int i = 0; i < M; i++) {
			if(!map.containsKey(x[i])) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				list.add(y[i]);
				map.put(x[i], list);
			}else {
				map.get(x[i]).add(y[i]);
			}
			if(!map.containsKey(y[i])) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				list.add(x[i]);
				map.put(y[i], list);
			}else {
				map.get(y[i]).add(x[i]);
			}
		}

//		for(int i : map.keySet()) {
//			System.out.print(i + " : ");
//			for(int j = 0; j < map.get(i).size(); j++) {
//				System.out.print(map.get(i).get(j) + " ");
//			}
//			System.out.println();
//		}

		int []color = new int[N + 1];
		Arrays.fill(color, 0);

		assignColor(color);
//		for(int i = 1; i <= N; i++) {
//			System.out.println(color[i]);
//		}

		int t = 0;
		int sum = 0;

		for(int i = 1; i <= N; i++) {
//			for(int j = 0; j < N; j++) {
//				if(i == p[j]) {
//					t = j + 1;
//					break;
//				}
//			}
			if(color[p[i - 1]] == color[i]) {
				sum ++;
			}
		}

		System.out.println(sum);


	}
	public static void dfs(int r, int c, int[] color) {
		Deque<Integer> stack = new ArrayDeque<Integer>();
		stack.push(r);
		color[r] = c;
		while(!stack.isEmpty()) {
			int u = stack.getFirst();
			stack.pop();
			if(map.containsKey(u)) {
				for(int i = 0; i < map.get(u).size(); i++) {
					int v = map.get(u).get(i);
					if(color[v] == 0) {
						color[v] = c;
						stack.push(v);
					}
				}
			}
		}
	}
	public static void assignColor(int[] color) {
		int id = 1;
		for(int i = 1; i <= N; i++) {
			if(color[i] == 0) {
				dfs(i, id++, color);
			}
		}
	}
}

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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;


template <typename M>
class lazy_segment_tree {
	using T1 = typename M::t1;
	using T2 = typename M::t2;
	const int n;
	vector<T1> data;
	vector<T2> lazy;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	void push(int node) {
		if (lazy[node] == M::id2()) return;
		if (node < n) {
			lazy[node * 2] = M::op3(lazy[node * 2], lazy[node]);
			lazy[node * 2 + 1] = M::op3(lazy[node * 2 + 1], lazy[node]);
		}
		data[node] = M::op2(data[node], lazy[node]);
		lazy[node] = M::id2();
	}
	void suc(int l, int r, int node, int lb, int ub, T2 val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			lazy[node] = M::op3(lazy[node], val);
			return;
		}
		push(node);
		int c = (lb + ub) / 2;
		suc(l, r, node * 2, lb, c, val);
		suc(l, r, node * 2 + 1, c, ub, val);
		data[node] = M::op1(M::op2(data[node * 2], lazy[node * 2]), M::op2(data[node * 2 + 1], lazy[node * 2 + 1]));
	}
	T1 sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return M::id1();
		if (l <= lb && ub <= r) return M::op2(data[node], lazy[node]);
		int c = (lb + ub) / 2;
		return M::op2(M::op1(sub(l, r, node * 2, lb, c), sub(l, r, node * 2 + 1, c, ub)), lazy[node]);
	}
public:
	lazy_segment_tree(int n_) : n(size(n_)), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {}
	lazy_segment_tree(int n_, T1 v1) : n(size(n_)), data(n * 2, v1), lazy(n * 2, M::id2()) {}
	lazy_segment_tree(const vector<T1>& data_) : n(size(data_.size())), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {
		init(data_);
	}
	void init() {
		for (int i = n - 1; i >= 1; i--) data[i] = M::op1(data[i * 2], data[i * 2 + 1]);
	}
	void init(const vector<T1>& data_) {
		for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
		init();
	}
	void update(int l, int r, T2 val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T1 find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

struct RURM {
	using t1 = int;
	using t2 = int;
	static t1 id1() { return INT_MAX; }
	static t2 id2() { return -1; }
	static t1 op1(const t1& l, const t1& r) { return min(l, r); }
	static t1 op2(const t1& l, const t2& r) { return r != id2() ? r : l; }
	static t2 op3(const t2& l, const t2& r) { return r != id2() ? r : l; }
};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  LL N,Q;
  cin >> N >> Q;

	lazy_segment_tree<RURM> seg(N);
	seg.init();

	REP(i,Q){
		LL y;
		cin >> y;
		if(y==0){
			LL s, t, x;
			cin >> s >> t >> x;
			seg.update(s, t, x);
		}
		else
		{
			LL s, t;
			cin >> s >> t;
			cout << seg.find(s, t) << endl;
		}
	}
}



Measured memory_bytes: 4856
import java.util.Scanner;

public class Main {
    int[] h;
    int[] dp;
    int N;

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

    private void run() {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        h = new int[N];
        dp = new int[N];
        for (int i = 0; i < N; i++) {
            h[i] = scanner.nextInt();
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        dp[1] = Math.abs(h[0] - h[1]);

        for(int i = 2; i < N; i++) {
            dp[i] = Math.min(Math.abs(h[i] - h[i-1]) + dp[i-1], Math.abs(h[i] - h[i-2]) + dp[i-2]);
        }

        int ans = dp[N-1];
        System.out.println(ans);
    }
}

Measured memory_bytes: 61196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

const int MAX_N = 2000000;
ll inv[MAX_N + 10];
ll fac[MAX_N + 10], facInv[MAX_N + 10];
class MATH{
public:
	MATH(){
		inverse();
		factroial();
	}
	ll nCk(ll n, ll k){// n! / k!*(n-k)!
		if(k < 0 || k > n) return 0;
		ll ret = fac[n];
		(ret *= facInv[k]) %= MOD;
		(ret *= facInv[n - k]) %= MOD;
		return ret;
	}
	ll nHk(ll n, ll k){// nHk = n+k-1 C k = (n+k-1)! / k! * (n-1)!
		if(n == 0 && k == 0) return 1;
		ll ret = fac[n + k - 1];
		(ret *= facInv[k]) %= MOD;
		(ret *= facInv[n - 1]) %= MOD;
		return ret;
	}
	ll nPk(ll n, ll k){//nPk = n! / (n-k)!
		if(k < 0 || k > n) return 0;
		ll ret = fac[n];
		(ret *= facInv[n - k]) %= MOD;
		return ret;
	}
private:
	void inverse(void){
		inv[1] = 1;
		for (int i = 2; i <= MAX_N; ++i){
			// inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
			inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
		}
	}
	void factroial(void){
		fac[0] = facInv[0] = 1;
		for (int i = 1; i <= MAX_N; ++i){
			fac[i] = (fac[i - 1] * i) % MOD;
			facInv[i] = (facInv[i - 1] * inv[i]) % MOD;
		}
	}
};

int main(void) {
	int H, W, A, B;
	cin >> H >> W >> A >> B;
	MATH ma;
	ll ans = 0;
	for (int i = 1; i <= H - A; ++i) {
		ll h1 = i, w1 = B;
		ll h2 = H - i + 1, w2 = W - B;
		ll d1 = fac[h1 + w1 - 2] * facInv[h1 - 1] % MOD * facInv[w1 - 1] % MOD;
		ll d2 = fac[h2 + w2 - 2] * facInv[h2 - 1] % MOD * facInv[w2 - 1] % MOD;
		ans += d1 * d2 % MOD;
		// printf("%lld %lld %lld %lld %lld %lld %lld\n", h1, w1, h2, w2, d1, d2, ans);
	}
	printf("%lld\n", ans % MOD);
	return 0;
}

Measured memory_bytes: 47104
import sys
def input():
    return sys.stdin.readline()[:-1]

X = int(input())

ans = X
while True:
    N = int(ans**0.5) + 1
    flag = True
    for i in range(2,N):
        if ans%i==0:
            flag = False
            break
    if flag:
        break
    ans += 1
print(ans)

Measured memory_bytes: 3188
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
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; }
const string YES = "Yes";
const string NO = "No";

void solve(long long D, long long T, long long S){
    cout << ((T*S >=D) ? YES : NO) <<endl;
}
int main(){
    long long D;
    scanf("%lld",&D);
    long long T;
    scanf("%lld",&T);
    long long S;
    scanf("%lld",&S);
    solve(D, T, S);
    return 0;
}


Measured memory_bytes: 3148
#define dbg(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define dpri(x) dbg(#x ": %d\n", x)
#define dprs(x) dbg(#x ": %s\n", x)
#include <stdio.h>
#include <ctype.h>
typedef long long ll;
const int MYINF = 1e9+7;

int main(int argc, char **argv)
{
	char *p = NULL;
	size_t i, n;
	getline(&p, &n, stdin);
	for (i = 0; i < n; i++) {
		if (p[i] == '\0') break;
		else if (islower(p[i])) putchar(toupper(p[i]));
		else if (isupper(p[i])) putchar(tolower(p[i]));
		else putchar(p[i]);
	}
	return 0;
}

Measured memory_bytes: 524
S = input()
N = len(S)
mod = 10**9+7

A_cum = [0] * N
C_cum = [0] * N
q_sum_left = [0] * N
q_sum_right = [0] * N
for i in range(N - 1):
    s = S[i]
    if s == 'A':
        A_cum[i + 1] = A_cum[i] + 1
    else:
        A_cum[i + 1] = A_cum[i]
    if s == '?':
        q_sum_left[i + 1] = q_sum_left[i] + 1
    else:
        q_sum_left[i + 1] = q_sum_left[i]
for i in range(N - 1, 0, -1):
    s = S[i]
    if s == 'C':
        C_cum[i - 1] = C_cum[i] + 1
    else:
        C_cum[i - 1] = C_cum[i]
    if s == '?':
        q_sum_right[i - 1] = q_sum_right[i] + 1
    else:
        q_sum_right[i - 1] = q_sum_right[i]
ans = 0
for i in range(N):
    if S[i] == 'B' or S[i] == '?':
        ans = (ans + (A_cum[i] * pow(3, q_sum_left[i], mod) + q_sum_left[i] * pow(3, max(0, q_sum_left[i] - 1), mod))
               * (C_cum[i] * pow(3, q_sum_right[i], mod) + q_sum_right[i] * pow(3, max(0, q_sum_right[i] - 1), mod))) % mod

print(ans)


Measured memory_bytes: 47212
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    int N; cin >> N;
    vector<int> d(N); rep(i, N) cin >> d[i];
    sort(d.begin(), d.end());
    int cnt = 0;
    rep1(i, 100100) {
        if((d.end() - lower_bound(d.begin(), d.end(), i)) == N / 2) {
            cnt ++;
        }
    }
    cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

struct Graph {
    struct Vertex { int n, h; };
    struct Edge { int i, n; };
    Graph(int n, int m) : v(n, { -1, 0 }), e(m), n(n), m(0) {}
    void add_edge(int i, int j) {
        e[m] = { j, v[i].n };
        v[i].n = m;
        m++;
    }
    void solve() {
        int r = 0;
        for (int i = 0; i < n; i++) {
            int b = 1, h = v[i].h;
            for (int j = v[i].n; j >= 0; j = e[j].n) {
                Edge& o = e[j];
                if (h <= v[o.i].h) {
                    b = 0;
                    break;
                }
            }
            r += b;
        }
        cout << r << endl;
    }
    vector<Vertex> v;
    vector<Edge> e;
    int n, m;
};

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

    int n, m;
    cin >> n >> m;

    Graph g(n, m * 2);
    for (int i = 0; i < n; i++) {
        cin >> g.v[i].h;
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;

        g.add_edge(a, b);
        g.add_edge(b, a);
    }
    g.solve();

    return 0;
}

Measured memory_bytes: 5580
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int a,b,c=1,cnt=0;
string s;
signed main()
{
	cin>>a>>b;
	while(1){
		if(c>=b){
			cout<<cnt;
			break;
		}
		c+=a-1;
		cnt++;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define SZ(x) ((int)(x).size())
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define REP(i,n) for (int i = 0; i < n; ++i)
#define FOR(i,a,b) for (int i = a; i <= b; ++i)
#define M 1000000007
#define MM 998244353
#define SZ(a) int((a).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define mod 1000000007
using ll = long long;

//a and b are assumed to be taken modulo p
inline ll add(ll a, ll b, ll p = mod){ ll c = a + b; if(c >= p) c -= p; return c; }
inline ll sub(ll a, ll b, ll p = mod){ ll c = a - b; if(c < 0) c += p; return c; }
inline ll mul(ll a, ll b, ll p = mod){ return (a * 1ll * b) % p; }
 
using VI = vector<int>;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using VLL = vector<ll>;
using ld = long double;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
      
}
ll power(ll x, ll y, ll p)
{
    ll res = 1;     // Initialize result
  
    x = x % p; // Update x if it is more than or
                // equal to p
  
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;
  
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*1ll*x) % p;
    }
    return res;
}
const int MX = 2e5+10;
const int MX2 = 1e6+5;

ll INF= 4 * (ll)1e18;
int mx = 2 * (ll)1e9 + 10;
set<ll> Sx[MX];
set<ll> Sy[MX];
int main(int argc, const char * argv[]) {

    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); // insert code here...
    string s;
    cin >> s;
    if (s.size() < 6) cout << "No"<<endl;
    else if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes"<<endl;
    }
    else {
        cout << "No"<<endl;
    }
    return 0;
    
}


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

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1e9;
using namespace std;
typedef long long ll;

int n;
vector <ll> vx;
ll x[200100];

int main(){
  cin >> n;
  rep(i,1,n+1){
    cin >> x[i];
    vx.push_back(x[i]);
  }
  sort(all(vx));
  ll med1 = vx[n/2-1];
  ll med2 = vx[n/2];
  // std::cout << med1 << med2 << '\n';
  rep(i,1,n+1){
    if(x[i] > med1)std::cout << med1 << '\n';
    else std::cout << med2 << '\n';
  }
}


Measured memory_bytes: 5488
#include<cstdio>
using ll = long long;
using ull = unsigned long long;
const static int MOD = 998244353;
ull dp[3001][3001];

int main(){
    ull A, B, C, D;
    scanf("%llu %llu %llu %llu", &A, &B, &C, &D);
    dp[A][B] = 1;
    for (unsigned i = A + 1; i <= C; i++){
        dp[i][B] = dp[i-1][B]*B %MOD;
    }
    for (unsigned i = B + 1; i <= D; i++){
        dp[A][i] = dp[A][i-1]*A %MOD;
    }
    for (ull i = A + 1; i <= C; i++){
        for (ull j = B + 1; j <= D; j++){
            dp[i][j] = ((dp[i-1][j]*j %MOD) + (dp[i][j-1]*i %MOD) + MOD - ((i-1)*(j-1)%MOD*dp[i-1][j-1]%MOD)) %MOD;
        }
    }
    printf("%llu\n", dp[C][D]);    
	return 0;
}

Measured memory_bytes: 71968
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;
typedef pair<int, int> P;

unsigned long long int calc(int a)
{
	unsigned long long int temp = 1;
	for (int i = 2; i <= a; ++i)
	{
		temp *= i;
		temp %= 1000000007;
	}
	return(temp);
}

void solve()
{
	int N, M;
	cin >> N >> M;
	if (abs(N - M) > 1)
	{
		cout << 0 << endl;
		return;
	}
	unsigned long long int monkey = 0;
	unsigned long long int dog = 0;
	if (abs(N - M) == 1)
	{
		monkey = calc(N);
		dog = calc(M);
		cout << (monkey * dog) % 1000000007 << endl;
	}
	else
	{
		monkey = calc(N);
		dog = monkey;
		cout << (monkey * dog * 2) % 1000000007 << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

int main() {
  int N;
  cin >> N;
  bool is47 = false;
  if (N==4||N==7) cout <<"Yes" << endl;
  else if (N >= 7) {
    for (int i=0; 7*i<=N; i++) {
      if ((N-7*i)%4==0) {
        is47 = true; break;
      }
    }
    if (is47) cout << "Yes" << endl;
    else cout << "No" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
h,w,n=map(int,input().split())
r,c=map(int,input().split())
s=input()
t=input()
xr=xl=xd=xu=yr=yl=yd=yu=0
for i in range(n):
    xr+=s[i]=='R'
    xl+=s[i]=='L'
    xd+=s[i]=='D'
    xu+=s[i]=='U'
    if w-c-(xr-yl)<0 or c-1-(xl-yr)<0 or h-r-(xd-yu)<0 or r-1-(xu-yd)<0:
        print('NO')
        break
    yr+=t[i]=='R'
    yr-=w-c-(yr-xl)<0
    yl+=t[i]=='L'
    yl-=c-1-(yl-xr)<0
    yd+=t[i]=='D'
    yd-=h-r-(yd-xu)<0
    yu+=t[i]=='U'
    yu-=r-1-(yu-xd)<0
else:
    print('YES')

Measured memory_bytes: 3888
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#define INF 100000000000000
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

int main(){
    llong X,Y,Z;
    llong temp;
    cin >> X >> Y >> Z;
    temp = X;
    X    = Y;
    Y    = temp;

    temp = X;
    X    = Z;
    Z    = temp;

    cout << X << " " << Y << " " << Z << endl;
}

Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=200005;
struct edge{
	int to,next,f;
}e[N*2];
int head[N],tot=1;
int n,ans,a[N],b[N];
int nd,S,T,ida[N],idb[N];
int cur[N],q[N],dis[N];
void add(int x,int y){
	e[++tot]=(edge){y,head[x],1};
	head[x]=tot;
	e[++tot]=(edge){x,head[y],0};
	head[y]=tot;
}
bool bfs(){
	int h=0,t=1;
	For(i,1,nd) dis[i]=-1;
	dis[S]=0; q[1]=S;
	while (h!=t){
		int x=q[++h];
		for (int i=head[x];i;i=e[i].next)
			if (dis[e[i].to]==-1&&e[i].f){
				dis[e[i].to]=dis[x]+1;
				if (e[i].to==T) return 1;
				q[++t]=e[i].to;
			}
	}
	return 0;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int k,rest=flow;
	for (int &i=cur[x];i;i=e[i].next)
		if (dis[e[i].to]==dis[x]+1&&e[i].f){
			k=dfs(e[i].to,min(rest,e[i].f));
			e[i].f-=k; e[i^1].f+=k; rest-=k;
			if (!rest) break;
		}
	if (rest) dis[x]=-1;
	return flow-rest;
}
void getid(int *a,int *id){
	For(i,0,n-1)
		if (!id[i]){
			++nd;
			for (int x=i;!id[x];x=a[x])
				id[x]=nd;
		}
}
int main(){
	scanf("%d",&n);
	For(i,0,n-1) scanf("%d",&a[i]);
	For(i,0,n-1) scanf("%d",&b[i]);
	getid(a,ida); getid(b,idb);
	S=++nd; T=++nd;
	For(i,0,n-1){
		if (a[i]==i&&b[i]==i) ++ans;
		else if (a[i]==i) add(idb[i],T);
		else if (b[i]==i) add(S,ida[i]);
		else{
			add(idb[i],ida[i]);
			if (a[i]==b[i])
				add(ida[i],idb[i]);
		}
	}
	for (;bfs();){
		For(i,1,nd) cur[i]=head[i];
		ans+=dfs(S,1<<30);
	}
	printf("%d\n",n-ans);
}
/*
a[i]变:T,不变:S 
b[i]变:S,不变:T 
*/

Measured memory_bytes: 11264
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define EPS 10e-8

using namespace std;
typedef pair<llong, llong> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

llong K;
llong res[50];

void solve(llong N) {
    llong x = K / N;
    llong y = K % N;

    for(int i = 0; i < N - y; ++i)
        res[i] = N - 1 + x - y;
    
    for(int i = N - y; i < N; ++i)
        res[i] = N - 1 + x + N - y + 1;
    
}

int main(int argc, char **argv) {
    cin >> K;
    llong N = 50;

    solve(N);
    cout << N << endl;
    for(int i = 0; i < N; ++i) {
        if(i != 0) cout << " ";
        cout << res[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
get :: Int -> Int -> Int -> Int -> Int -> Int
get n c d l r 
  | l + 1 < r = let mid = (l + r) `div` 2 in if mid * c - (n - mid) * d >= 0 then (get n c d l mid) else (get n c d mid r)
  | otherwise = if l >= 0 then l else 0

check :: Int -> Int -> Int -> Int -> Bool
check n dd c d
  | dd >= 0 = any (\(ll, rr) -> ll <= dd && dd <= rr) (takeWhile (\(ll, rr) -> ll <= dd) [(i * c - (n - i) * d, i * d - (n - i) * c) | i <- [(get n c d (-1) n)..n]])
  | dd < 0 = check n (-dd) c d

main :: IO ()
main = do
  n:a:b:c:d:_ <- fmap (map read . words) getLine
  putStrLn $ if check (n - 1) (b - a) c d then "YES" else "NO"


Measured memory_bytes: 1020
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let (n, l): (usize, usize) = read();
    let tv: Vec<(f64, usize)> = readn(n);


    let mut deq: VecDeque<(f64, usize)> = VecDeque::new();
    let mut sum = 0;
    let mut total_value = 0.0;
    for i in 0..n {
        while sum + tv[i].1 > l {
            let (t, v) = deq.pop_front().unwrap();
            let trash = min(v, sum + tv[i].1 - l);
            sum -= trash;
            total_value -= trash as f64 * t;
            if v - trash >= 1 {
                deq.push_front((t, v - trash));
                break
            }
        }
        deq.push_back((tv[i].0, tv[i].1));
        sum += tv[i].1;
        total_value += tv[i].0 * tv[i].1 as f64;

        println!("{:.12}", total_value / l as f64);

        while deq.len() >= 2 {
            let (t0, v0) = deq.pop_back().unwrap();
            let (t1, v1) = deq.pop_back().unwrap();
            if t1 <= t0 {
                deq.push_back((t1, v1));
                deq.push_back((t0, v0));
                break
            }
            let vf0 = v0 as f64;
            let vf1 = v1 as f64;
            deq.push_back(((t0 * vf0 + t1 * vf1) / (vf0 + vf1), v0 + v1));
        }
    }
}

Measured memory_bytes: 30784
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;
ll M = 1e6*3+1;
vector<bool> used(M,true);
vector<int> prime;
void make(){
    used[0] = used[1] = false;
    for(int i=1;i<M;i++){
	if( (i%7==1 || i%7==6) && used[i]){
	    prime.push_back(i);
	    for(int j=2;j*i<M;j++) used[i*j] = false;
	}
    }
    return ;
}


int main(){
    make();
  //  cout<<prime.size()<<endl;
    while(1){
	int n;
	cin>>n;
	if(n==1)break;
	cout<<n<<':';
	set<int> ans;
	for(int i=0;i<prime.size() ;i++){
	    if( n % prime[i]  == 0){
		ans.insert(prime[i]);
		//while(n%prime[i] == 0) n/=prime[i];
	    }
	}
	for(auto it:ans)cout<<' '<<it;
	cout<<endl;
    }
    return 0;
}



Measured memory_bytes: 5156
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=5e3+4;
const ull base=263;
int n;
char ss[N];
ull f[N][N];
inline bool ok(int len) {
	for (int i=1;i<=n-len*2+1;++i)
		for (int j=i+len;j+len-1<=n;++j)
			if (f[i][len]==f[j][len])
				return true;
	return false;
}
inline int find(int l,int r) {
	while (l<r) {
		int mid=l+r-(l+r>>1);
		if (ok(mid)) l=mid;
		else r=mid-1;
	}
	return l;
}
int main() {
	scanf("%d%s",&n,ss+1);
	for (int i=1;i<=n;++i)
		for (int j=1;i+j-1<=n;++j)
			f[i][j]=f[i][j-1]*base+ss[i+j-1];
	int x=0,y=n>>1;
	printf("%d\n",find(x,y));
	return 0;
}

Measured memory_bytes: 194816
import java.util.*;


public class Main {

    private static int K;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        K = sc.nextInt();
        LinkedList<Integer> s = new LinkedList<>();
        s.add(0);
        long ans = dfs(s, 0, true);
        System.out.println(ans);
    }

    private static long dfs(LinkedList<Integer> s, int digit, boolean allZero) {
        long ret = 0;
        if (digit == 10) {
            if (K-- == 0) {
                for (int ss : s) {
                    ret *= 10;
                    ret += ss;
                }
            }
            return ret;
        }

        int last = s.getLast();
        for (int i = 0; i <= 9; i++) {
            if (allZero || -1 <= i-last && i-last <= 1) {
                s.add(i);
                ret = dfs(s, digit+1, allZero && i == 0);
                if (ret > 0) {
                    break;
                }
                s.removeLast();
            }
        }

        return ret;
    }
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


// #define MAX_N 10^100 101桁
#define MAX_K 3
#define DIGIT 110
#define SMALLER 2

string N;
i64 K;

i64 dp[DIGIT][SMALLER][MAX_K + 1]; // [決定した桁数][未満フラグ][0でない数字の個数]


i64 solve() {
  const i64 L = N.length();
  REP(i, DIGIT) {
    REP(j, SMALLER) {
      REP(k, MAX_K + 1) {
        dp[i][j][k] = 0;
      }
    }
  }
  dp[0][0][0] = 1;

  REP(i, L) {
    i64 D = N[i] - '0';
    REP(j, SMALLER) {
      REP(k, K+1) {
        for (i64 d = 0; d <= (j ? 9 : D); d++) {
          if (d != 0 && k == K) continue;
          dp[i + 1][j || (d < D)][k + (d != 0)] += dp[i][j][k];
        }
      }
    }
  }

  return dp[L][0][K] + dp[L][1][K];
}

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

  i64 res = solve();
  cout << res << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M, K;
vector<int> A, B;
string S, T;

void input() {
  int x, y, z;
  cin >> N;
  A.resize(N);

  rep(i, 0, N - 1) {
    int x;
    cin >> x;
    A[i] = x - 1;
  };
}
void solve() {
  int ans = 0;
  int i;
  A.push_back(-1);
  for (i = 0; i < N; ++i) {
    if (A[i] == i) {
      ans++;
      if (A[i + 1] == i + 1) {
        i++;
      }
    }
  }
  cout << ans << endl;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 1792
def main():
    N = int(input())
    W = list(map(int, input().split()))
    ans = 10 ** 10
    lst = [0 for _ in range(N)]
    lst[0] = W[0]

    for i in range(1, N):
        lst[i] = lst[i - 1] + W[i]

    for T in range(N - 1):
        S1 = lst[T]
        S2 = lst[-1] - lst[T]
        diff = abs(S1 - S2)
        if diff < ans:
            ans = diff

    print(ans)


if __name__ == "__main__":
    main()


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

namespace _1_2_C {
    class Program {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var array = input.Split(' ').Select(x => int.Parse(x)).OrderBy(x => x).ToArray();
            Console.WriteLine($"{array[0]} {array[1]} {array[2]}");
        }
    }
}



Measured memory_bytes: 16520
S = [int(x) if x != "?" else -1 for x in input()]
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    DP[1], DP[0] = DP[0], DP[1]
    for j in range(13):
        DP[0][j] = 0
    for j in range(13):
        if S[i] == -1:
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+S[i])%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w = (w + DP[0][j]) % g
        DP[0][j] = w

print(DP[0][5] % g)


Measured memory_bytes: 4092
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n = I()
L = [[0, 0, 0]] + LIR(n)
for i in range(n):
    t, x, y = L[i]
    nxt_t, nxt_x, nxt_y = L[i+1]
    if nxt_t - t < abs(nxt_x - x) + abs(nxt_y - y) or (abs(nxt_x - x) + abs(nxt_y - y) - nxt_t - t) % 2:
        print('No')
        break
else:
    print('Yes')

Measured memory_bytes: 58204
#include <bits/stdc++.h>
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)

typedef unsigned long long ull;
typedef long long ll;

const int INF = 1001001001;
const int MOD = 1000000007;

using namespace std;
using P = pair<int,int>;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }


int main() {
  vector<ll> foods{ 100, 101, 102, 103, 104, 105 };
  ll x;
  cin >> x;

  bool able = false;
  for (int i = 1; 100*i <= x; i++) {
      ll rem = x - 100*i;
      if (0<=rem && rem<=5*i) able = true;
  }
  cout << able << endl;
  return 0;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())
count = 0

if A == B:
    if A != C:
        count += 1

if B == C:
        if B != A:
            count += 1

if A == C:
        if A != B:
            count += 1

if count >= 1:
    print('Yes')
else:
    print('No')

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

#define faster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define fill(a,v)  memset(a, v, sizeof (a))
#define FOR(i,a,n) for (int i=a;i<n;i++)
#define FORD(i,a,n) for (int i=n-1;i>=a;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N=501000;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const ll LINF = LLONG_MAX;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

int main()
{
	faster;

	int n, k;

	cin >> n >> k;
	vi h(n), dp(n, INF);
	for(int i=0; i < n; ++i)	cin >> h[i];

	dp[0] = 0;
	for(int i = 1; i < n; ++i){
		for(int j = i-1; j >= 0 && j >= i-k; --j){
			dp[i] = min(dp[i], dp[j] + abs(h[i]-h[j]));
		}
	}
	cout << dp[n-1];

	return 0;
}

// READ
// THINK
// CODE
// DEBUG
// AC


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
int dev(int a);
int main()

 {

   int n;
scanf("%d",&n);


dev(n);

 }

int dev(int a){
    int r,count;
while(a>0){
    r=a%10;
    if(r==7){
        count=1;;
        break;
    }else{
    count=0;
    a=a/10;
    }

}if(count==0)
printf("No");
else
    printf("Yes");
}


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

// clang-format off
#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << x << endl

#define rep(i, n) for (int i = 0; i < (int)(n); ++(i))
#define reps(i, n) for (int i = 1; i <= (int)(n); ++(i))
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --(i))
#define rreps(i, n) for (int i = (int)(n); i > 0; --(i))

#define range(i, l, r) for (int i = (int)l; i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = ((int)(r) - 1); i >= (int)l; --(i))

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)

using int32 = int;
using int64 = long long;

constexpr int mod     = 1e9 + 7;
constexpr int32 inf   = 1001001001;
constexpr int64 infll = 1001001001001001001ll;
constexpr int dx[]    = {0, -1, 1, 0, -1, 1, -1, 1},
              dy[]    = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { os << v[0]; for (int i = 1; i < v.size(); ++i) os << " " << v[i]; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

template<typename T = int> T input() { T x; cin >> x; return x; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

void solver() {
    string s;
    cin >> s;

    cout << (s < "2019/04/31" ? "Heisei" : "TBD") << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}



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

int main()
{
	int s;
	cin >> s;
	s %= 10;
	if (s == 3) {
		cout << "bon" << endl;
	}
	else if (s == 0 || s == 1 || s == 6 || s == 8) {
		cout << "pon" << endl;
	}
	else {
		cout << "hon" << endl;
	}
	return 0;
}

Measured memory_bytes: 3676