akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

int main() {
	int N, y;
	cin >> N;
	int a[N][3];
	int dp[N+1][3];
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> a[i][j];
		}
	}
	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[0][2] = 0;
	for(int i = 1; i <= N; ++i) {
		dp[i][0] = max(a[i-1][0]+dp[i-1][1], a[i-1][0]+dp[i-1][2]);
		dp[i][1] = max(a[i-1][1]+dp[i-1][0], a[i-1][1]+dp[i-1][2]);
		dp[i][2] = max(a[i-1][2]+dp[i-1][0], a[i-1][2]+dp[i-1][1]);
	}
	int ans = -1;
	for (int i = 0; i < 3; ++i) {
		if (dp[N][i] > ans) ans = dp[N][i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
a,b,c,d = map(int,input().split())
x,y = c-a, d-b
res = ""
res += 'R' * x + 'U' * y
res += 'L' * x + 'D' * y
res += 'L' + 'U' * (y + 1) + 'R' * (x + 1) + 'D'
res += 'R' + 'D' * (y + 1) + 'L' * (x + 1) + 'U'
print(res)

Measured memory_bytes: 38384
#include <cstdio>
#define NIL -1

struct Node { int parent, left, right; };

Node T[30];
int n;

void priParse(int i) {
    if (i == NIL) return;
    printf(" %d", i);
    priParse(T[i].left);
    priParse(T[i].right);
}

void inParse(int i) {
    if (i == NIL) return;
    inParse(T[i].left);
    printf(" %d", i);
    inParse(T[i].right);
}

void postParse(int i) {
    if (i == NIL) return;
    postParse(T[i].left);
    postParse(T[i].right);
    printf(" %d", i);
}

int main(void) {
    int i, v, l, r, rt;
    scanf("%d", &n);

    for (i = 0; i < n; i++) T[i].parent = NIL;

    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &v, &l, &r);
        T[v].left = l;
        T[v].right = r;
        if (l != NIL) T[l].parent = v;
        if (r != NIL) T[r].parent = v;
    }

    for (i = 0; i < n; i++) {
        if (T[i].parent == NIL) rt = i;
    }

    printf("Preorder\n");
    priParse(rt);
    printf("\nInorder\n");
    inParse(rt);
    printf("\nPostorder\n");
    postParse(rt);
    printf("\n");

    return 0;
}

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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

int main() {
  int64 H, W;
  cin >> H >> W;
  int X[1000000];
  int Y[1000000];
  memset(X, -1, sizeof(X));
  memset(Y, -1, sizeof(Y));
  for(int i = 0; i < H; i++) {
    int y;
    cin >> y;
    --y;
    if(~Y[y]) {
      cout << 0 << endl;
      return 0;
    }
    Y[y] = i;
  }
  for(int i = 0; i < W; i++) {
    int x;
    cin >> x;
    --x;
    if(~X[x]) {
      cout << 0 << endl;
      return 0;
    }
    X[x] = i;
  }
  int64 usedY = 0, usedX = 0;
  int64 rest2 = 0; // 両方埋まっている

  // 残っている行
  int64 mul = 1;

  for(int i = H * W - 1; i >= 0; i--) {
    if(~X[i] && ~Y[i]) {

      rest2 += usedY;
      rest2 += usedX;

      ++usedY;
      ++usedX;

    } else if(~X[i]) {

      (mul *= usedY % mod) %= mod;

      rest2 += (usedY - 1);
      ++usedX;

    } else if(~Y[i]) {


      (mul *= usedX % mod) %= mod;
      rest2 += (usedX - 1);
      ++usedY;

    } else {

      (mul *= rest2) %= mod;
      --rest2;

    }


  }

  cout << mul << endl;
}


Measured memory_bytes: 8064
import sys
# A,B,C = [int(n) for n in input().split()]
# N = int(input())
# A = [0]*N
# for i in range(N):
#     A[i] = int(input())
S = str(input())
# T = str(input())
if(int(S[6]) +int(S[5])*10  > 4 or (int(S[6]) == 4 and int(S[8])*10 +int(S[9])  > 30 ) ):
    print("TBD")
else:
    print("Heisei")


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

struct UnionFind
{
    vector<int> parent; // par[i] \in [1,n] is the parent of ith element
    vector<int> depth;  // depth of the tree whose root is ith element
    vector<int> size;   // size of the tree whose root is the ith element

    // Constructer
    UnionFind(int n)
    {
        for (int i = 0; i < n; i++)
        {
            parent.push_back(i); // Init root by itself (there is n tree initially)
            depth.push_back(0);
            size.push_back(1);
        }
    };

    // Retrive the parent + contraction for better performance
    int root(int i)
    {
        // Base case
        if (parent[i] == i)
            return i;

        // Contraction by recursion; every node will have the same root by this, and the depth will become 2
        parent[i] = root(parent[i]);

        return parent[i];
    }

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);

        // If the trees has the same root, do nothing
        if (rx == ry)
            return;

        // Merge to the shallower tree

        if (depth[rx] < depth[ry])
        {
            parent[rx] = ry;
            size[ry] += size[rx];
        }
        else
        {
            parent[ry] = rx;
            size[rx] += size[ry];

            // If same depth, use x
            if (depth[rx] == depth[ry])
                depth[rx]++;
        }
    }

    // True if x and y belongs to the same tree
    bool same(int x, int y)
    {
        return root(x) == root(y);
    }

    int getSize(int x)
    {
        return size[root(x)];
    }
};

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

    UnionFind uf(N);
    vector<int> ans(N);
    vector<vector<int>> frnd(N, vector<int>(0));

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;

        // Adjust index
        a -= 1;
        b -= 1;

        // Construct union find tree
        uf.unite(a, b);
        frnd[a].push_back(b);
        frnd[b].push_back(a);
    }

    for (int i = 0; i < N; i++)
    {
        ans[i] = uf.getSize(i) - 1;
        ans[i] -= frnd[i].size();
    }

    for (int i = 0; i < K; i++)
    {
        int c, d;
        cin >> c >> d;

        // Adjust index
        c -= 1;
        d -= 1;

        // If in the same group, decrease the count
        if (uf.same(c, d))
        {
            ans[c] -= 1;
            ans[d] -= 1;
        }
    }

    // Main
    for (int i = 0; i < N; i++)
    {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 11372
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
#include <sstream>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;



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

    string s;
    cin >> s;
    (s[0] == '7' || s[1] == '7' || s[2] == '7') ? (cout << "Yes" << endl) : (cout << "No" << endl);

    
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int main(void)
{
    int N, M;
    std::vector<int> A;
    std::cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        int a;
        std::cin >> a;
        A.push_back(a % M);
    }

    std::partial_sum(A.begin(), A.end(), A.begin(), [M](int a, int b){return (a+b) % M;});
    std::sort(A.begin(), A.end());

    std::vector<int> set;
    int n = 0, cnt = 1;
    for (auto a: A)
    {
        if (a != n)
        {
            set.push_back(cnt);
            n = a;
            cnt = 1;
        }
        else
        {
            cnt += 1;
        }
    }
    set.push_back(cnt);

    long ans = 0;
    for (auto s: set)
    {
        ans += static_cast<long>(s) * static_cast<long>(s - 1) / 2;
    }

    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 1144
# coding: utf-8
import time
import re
import math
import fractions

def main():
    global N,A,B,C,D,memo,mx,mn,temp
    N=int(input())
    D=list(map(int,input().split()))
    D.sort()
    print(D[N//2]-D[N//2-1])

start=time.time()
main()
#print("処理速度 {}sec".format(time.time()-start))
#"YNeos"[True::2]
#A=list(map(int,input().split()))
#A,B,C=map(int,input().split())
#n=int(input())
# global N,A,B,C,D,memo,mx,mn,temp



Measured memory_bytes: 16044
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<tuple<int, int, int, int>> v(q);
    int a, b, c, d;
    REP(i, q) {
        cin >> a >> b >> c >> d;
        a--; b--;
        v[i] = {a, b, c, d};
    }

    deque<vi> que;
    vi x(n, 1);
    que.emplace_back(x);
    set<vi> memo;

    int ans = 0;
    while (!que.empty()) {
        auto x = que.front(); que.pop_front();
        // bool ok = true;
        // REP(i, n - 1) {
        //     if (x[i + 1] < x[i]) {
        //         ok = false;
        //         break;
        //     }
        // }
        // if (!ok) continue;

        int t = 0;
        REP(i, q) {
            tie(a, b, c, d) = v[i];
            if (x[b] - x[a] == c) t += d;
        }
        chmax(ans, t);

        // REP(i, n) {
            REP(j, n) {
                vi z = x;
                if (z[j] == m) continue;
                if (j != n - 1 and z[j] + 1 > z[j + 1]) continue;
                z[j]++;
                if (memo.count(z)) continue;
                que.emplace_back(z);
                memo.emplace(z);
            }
        // }
    }
    cout << ans << endl;
}


Measured memory_bytes: 13764
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define int long long
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
const int N=2005;
inline double cal(int i){
	int t=i,sum=0;
	while(t){
		sum+=t%10; t/=10; 
	}
	return (double)i/sum;
} 
signed main(){
	int n,de=1,dq=0; cin>>n;
	for(int i=1;;i++){
		int flag=0;
		for(int j=1;j<=101;j++)if(cal(dq+de)>cal(dq+j*de)){
			flag=1; break;
		}
		if(flag)de*=10; dq+=de;
		cout<<dq<<endl; if(--n==0)return 0;
	} 
}


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

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

#define YesNo(b) ((b) ? "Yes" : "No")
#define YESNO(b) ((b) ? "YES" : "NO")

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

int Q;
vi a, b, c, d;

int point(vi A)
{
    int p = 0;
    for (int i = 0; i < Q; i++)
    {
        if (A[b[i]-1] - A[a[i]-1] == c[i])
            p += d[i];
    }
    return p;
}

int dfs(vi &A, int i, int N, int M)
{
    if (i == N)
    {
        return point(A);
    }

    int max_point = 0;
    int prev = (i == 0) ? 1 : A[i-1];
    for (int j = prev; j <= M; j++)
    {
        A[i] = j;
        int p = dfs(A, i+1, N, M);
        max_point = max(max_point, p);
    }
    return max_point;
}


int main()
{
    int N, M;
    cin >> N >> M >> Q;
    a = vi(Q);
    b = vi(Q);
    c = vi(Q);
    d = vi(Q);
    for (int i = 0; i < Q; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];

    vi A(N);

    int ans = dfs(A, 0, N, M);
    cout << ans << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;using ll=int_fast64_t;using ld=long double;using pll=pair<ll,ll>;using pld=pair<ld,ld>;
const ll INF=1LL<<60;void solve();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);solve();}
#define fi first
#define se second
#define SELECTOR(_1,_2,_3,_4,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep2,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
#define _rep2(i,k,n,d) for(ll i=k;d!=0&&d>0?i<n:i>n;i+=d)
template<class T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<class... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<class T> inline bool chmax(T &a,const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a,const T &b){if(a>b){a=b; return 1;} return 0;}
template<class T> void contout(const T &v){for(auto it=v.begin();it!=v.end();++it,cerr<<(it!=v.end()?" ":"\n"))cout<<*it;}

void solve(){
  ll n,m; cin>>n>>m;
  vector<pll> key;
  rep(i,m){
    ll a,b; cin>>a>>b;
    ll t=0;
    rep(_,b){
      ll c; cin>>c;
      t+=1<<(--c);
    }
    key.emplace_back(t,a);
  }
  const ll N=1<<n;
  vector<ll> dp(N,INF);
  dp[0]=0;
  rep(i,m){
    auto newdp=dp;
    ll t,a; tie(t,a)=key[i];
    rep(j,N){
      chmin(newdp[j|t],dp[j]+a);
    }
    dp=newdp;
  }
  ll ans=dp[N-1];
  cout<<(ans!=INF?ans:-1)<<"\n";
}

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

string repeat(char c, int num){
  string ans="";
  for(int i=0;i<num;i++){
    ans += c;
  }
  return ans;
}

int main(){
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  tx -= sx;ty -= sy;
  string ans = "";
  ans += repeat('U', ty);
  ans += repeat('R', tx);
  ans += repeat('D', ty);
  ans += repeat('L', tx);
  ans += "L" + repeat('U', ty+1) + repeat('R', tx+1) + "D";
  ans += "R" + repeat('D', ty+1) + repeat('L', tx+1) + "U";
  cout << ans << endl;
}

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

num = 0
for i in range(n):
    if a[i] >= b[i]:
       # print(a[i],b[i])
        a[i] -= b[i]
        num += b[i]
        b[i] = 0
        
    elif a[i] < b[i]:
        num += a[i]
        #a[i] = 0
        b[i] -= a[i]
        num += min(b[i],a[i+1])
        a[i+1] = max(a[i+1]-b[i],0)
        
print(num)

Measured memory_bytes: 18624
from collections import deque

H, W = map(int, input().split())
C = [input() for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(S, G):

    visited = [[False] * W for _ in range(H)]
    c = 0

    visited[S[0]][S[1]] = True
    que = deque([(S[0], S[1], 0)])

    while que:
        ci, cj, c = que.popleft()

        if ci == G[0] and cj == G[1]:
            return c

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and C[ni][nj] != '#':
                visited[ni][nj] = True
                que.append((ni, nj, c+1))
    return 0


sg = [[0, 0], [H-1, W-1]]
ans = 0
ans += bfs(sg[0], sg[1])

if ans == 0:
    print('-1')
else:
    num = sum([n.count('#') for n in C])
    result = H * W - (num + ans + 1)
    print(result)


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

int main(void){
    int a, b, t;
    cin >> a >> b >> t;

    int ans = 0;
    for(int i = 1; i * a <= t; i++){
        ans += b;
    }

    cout << ans << endl;
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  int cnt = 0;
  int a   = 0;
  int b   = 0;
  int ab  = 0;
  for (int i = 0; i < n; i++) {
	  string s;
	  cin >> s;
	  if (s.front() == 'B' && s.back() == 'A') {
		  ab++;
		} else if (s.front() == 'B') {
		  b++;
		} else if (s.back() == 'A') {
		  a++;
		}
	  for (int j = 0; j < s.length() - 1; j++) {
		  if (s.substr(j, 2) == "AB") {
			  cnt++;
			}
		}
	}
  if (ab == 0) {
	  cnt += min(a, b);
	} else if (a + b > 0) {
	  cnt += ab + min(a, b);
	} else {
	  cnt += (ab - 1);
	}
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main() {
	long long int a, b, t, ab, gcd, lcm;

	while (std::cin >> a >> b) {
		ab = a * b;
		while (a % b > 0) {
			t = a % b;
			a = b;
			b = t;
		}
		gcd = b;
		lcm = ab / gcd;
		std::cout << gcd << " " << lcm << std::endl;
	}

	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define MN 200005
#define MM 600005
#define ll long long
#define mod 1000000007
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n;ll ans=1;
char s[MN];
int main(){
	scanf("%d%s",&n,s+1);
	n*=2;
	int j=0,k=0;
	F(i,1,n){
		if((s[i]=='B')^k)++j,k^=1;
		else ans=ans*j--%mod,k^=1;
	}
	if(j)ans=0;
	F(i,1,n/2)ans=ans*i%mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<bits/stdc++.h>
#define pq priority_queue
using namespace std;
#define MZ 1000000007
int num[100005],dp[100005][2];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",num+i);
    dp[1][0]=dp[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=min(dp[i-1][0],dp[i-1][1])+1;
        dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
        if(num[i-1]>=num[i])
            dp[i][0]=min(dp[i-1][0],dp[i][0]);
        if(num[i-1]<=num[i])
            dp[i][1]=min(dp[i-1][1],dp[i][1]);
    }
    printf("%d\n",min(dp[n][0],dp[n][1]));
    return 0;
}


Measured memory_bytes: 1408
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()

l = 0
r = N
print(0, flush=True)
retl = input()
if retl == "Vacant": exit()

print(N-1, flush=True)
retr = input()
if retr == "Vacant": exit()

while 1:
	m = (l+r)//2
	print(m, flush=True)
	retm = input()
	if retm == "Vacant": exit()

	if (m-l)%2 == 0 and retm == retl or (m-l)%2 == 1 and retm != retl:
		l = m
		retl = retm
	else:
		r = m
		retr = retm




Measured memory_bytes: 10436
Q = int(input())
#エラトスてねす
que=[]     
for i in range(Q):
    l,r = map(int,input().split())
    que.append((l,r))


M = 10**5+10
prime=[True]*M
prime[0]=False
prime[1]=False
for i in range(2,M):
    if prime[i]:
        for j in range(2,(M-1)//i+1):
            prime[i*j]=False
con=[0]*M
for j in range(3,M):
    if prime[j] and prime[(j+1)//2]:
        con[j] = con[j-1]+1
    else:
        con[j]=con[j-1]


ans =[]
for i in range(Q):
    l,r = que[i]
    ans.append(con[r]-con[l-1])
print('\n'.join(map(str, ans)))

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

//Compiler version g++ 6.3.0
typedef long long int lli;
int main()
{
    lli n;
    cin>>n;
    lli a[n],b[n],c[n];
    lli i,j;
    for(i=0;i<n;i++)
    {
      cin>>a[i]>>b[i]>>c[i];
    }
    lli dp[n][3];
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];
    for(i=1;i<n;i++)
    {
      dp[i][0]=a[i]+max(dp[i-1][1],dp[i-1][2]);
      dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
      dp[i][2]=c[i]+max(dp[i-1][1],dp[i-1][0]);
    }
    
cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}

Measured memory_bytes: 8300
#include<iostream>
int main()
{
	for(int i = 1; i <= 9; i++)
	{
		for(int j = 1; j <= 9; j++)
		{
			std::cout << i << 'x' << j << '=' << i*j << std::endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3056
n, m = gets.split.map(&:to_i)
s = [0]
sum = 0
now = 0
for i in 1...n do
  s[i] = s[i-1] + gets.to_i
end
m.times do
  a = gets.to_i
  sum += (s[now+a]-s[now]).abs
  now += a
end
puts sum%100000

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

using ll = long long;
using namespace std;

const int INF = 1e9;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int n = s.size();
  int m = t.size();
  vector<vector<int>> dp(n, vector<int>(m, 0));
  dp[0][0] = (s[0] == t[0]);
  for (int j = 1; j < m; ++j) {
    if (s[0] == t[j])
      dp[0][j] = 1;
    dp[0][j] = max(dp[0][j], dp[0][j - 1]);
  }
  for (int i = 1; i < n; ++i) {
    dp[i][0] = dp[i - 1][0];
    if (s[i] == t[0])
      dp[i][0] = 1;
    for (int j = 1; j < m; ++j) {
      if (s[i] == t[j])
        dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
      dp[i][j] = max({dp[i][j], dp[i - 1][j], dp[i][j - 1]});
    }
  }
  string ans;
  int i = n - 1, j = m - 1;
  while (i >= 0 && j >= 0 && dp[i][j] > 0) {
    while (i > 0 && dp[i][j] == dp[i - 1][j])
      --i;
    while (j > 0 && dp[i][j] == dp[i][j - 1])
      --j;
    ans.push_back(s[i]);
    --i;
    --j;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 35584
#include <stdio.h>
int main(void){
        int i,j,h,w;

        while(1){
                scanf("%d %d",&h,&w);
                if(h==0 && w==0) break;

                for(i=0;i<h;i++){
                        for(j=0;j<w;j++){
                                if(i==0 || i==h-1 || j==0 || j== w-1)
                                        printf("#");
                                else
                                        printf(".");

                        }puts("");
                }puts("");
        }
        return 0;
}


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

int main() {
    string str;
    cin >> str;
    cout << str.at(0) << (str.length() - 2) << str.at(str.length() - 1) << endl;
}

Measured memory_bytes: 256
import math

N,M = map(int,input().split())
A = []
n = 0
if N == 1:
    print(M)
else:
    ans = 1
    for i in range(1, int(math.sqrt(M))+1):
        if (M % i == 0):
            if i <= M//N:
                A.append(i)
            if M/i <= M//N:
                A.append(int(M/i))
    A.sort()
    print(A[-1])

Measured memory_bytes: 3060
N, K = [int(s) for s in input().split(' ')]
P = [int(s) for s in input().split(' ')]
s = []
a = sum(P[0:K])
s.append(a)
for p0, p1 in zip(P, P[K:]):
    a = a - p0 + p1
    s.append(a)

print((max(s) + K) / 2)


Measured memory_bytes: 32064
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A,B; cin >> A >> B;
    int ans;
    if((A+B)%2 == 0){
        ans = (A+B)/2;
        cout << ans <<endl;
    }else{
        cout << "IMPOSSIBLE" << endl;

    } 
}

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

int main(){
    int A, B, C, D;
  
    cin >> A >> B >> C >> D;

    while(true) {
        // takahashi kougeke
        C = C - B;
        if(C <= 0) {
            cout << "Yes" << endl;
            break;
        }
        // aoki kougeki
        A = A - D;
        if(A <= 0) {
            cout << "No" << endl;
            break;
        }
    }
}

Measured memory_bytes: 3592
#include<stdio.h>
#include<math.h>
int main(){
  int n,i,j,a;
  int flag,c=0;
  int s;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    if (a==2){
      c++;
      continue;
    }
    else if(a<2 || a%2==0){
      continue;
    }
    else{
      flag=0;
      s=sqrt(a);
      if(s==a*a)break;
      for (j=3;j<=s;j+=2){
	  if (a%j==0){
	    flag=1;
	    break;
	  }
	}
    }
    if(flag==0){
      c++;
    }
  }
  printf("%d\n",c);
  return 0;
}



Measured memory_bytes: 2064
#include <stdio.h>

int solve(int n) {
        if (n == 0) {
                return 0;
        }

        if (n % 10 == 7) {
                return 1;
        }

        solve(n / 10);
}

int main() {
        int n;
        int rc;

        rc = scanf("%3d", &n);
        if (rc == 0) {
                perror("scanf");
                return 1;
        }

        if (solve(n) == 1) {
                printf("Yes\n");
        } else {
                printf("No\n");
        }

        return 0;
}


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

void merge(vector<int>&a,vector<char>&c,int left,int mid,int right){
	int n1=mid-left,n2=right-mid;
	vector<int>tmpa1(n1),tmpa2(n2);
	vector<char>tmpc1(n1),tmpc2(n2);
	for(int i=left,j=0;i<mid;++i)tmpa1.at(j)=a.at(i),tmpc1.at(j++)=c.at(i);
	for(int i=mid,j=0;i<right;++i)tmpa2.at(j)=a.at(i),tmpc2.at(j++)=c.at(i);
	tmpa1.push_back(1e9),tmpa2.push_back(1e9);
	for(int i=left,j=0,k=0;i<right;++i){
		if(tmpa1.at(j)<=tmpa2.at(k))a.at(i)=tmpa1.at(j),c.at(i)=tmpc1.at(j++);
		else a.at(i)=tmpa2.at(k),c.at(i)=tmpc2.at(k++);
	}
}

void mergesort(vector<int>&a,vector<char>&c,int left,int right){
	int mid=(left+right)/2;
	if(left+1<right){
		mergesort(a,c,left,mid);
		mergesort(a,c,mid,right);
		merge(a,c,left,mid,right);
	}
}

int partition(vector<int>&a,vector<char>&c,int p,int r){
	int x=a.at(r),i=p-1;
	for(int j=p;j<r;++j){
		if(a.at(j)<=x){
			swap(a.at(++i),a.at(j));
			swap(c.at(i),c.at(j));
		}
	}
	swap(a.at(++i),a.at(r));
	swap(c.at(i),c.at(r));
	return i;
}

void quicksort(vector<int>&a,vector<char>&c,int p,int r){
	if(p<r){
		int q=partition(a,c,p,r);
		quicksort(a,c,p,q-1);
		quicksort(a,c,q+1,r);
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<int>v(n),v2(n);
	vector<char>c(n),c2(n);
	for(int i=0;i<n;++i)cin>>c.at(i)>>v.at(i);
	v2=v,c2=c;
	mergesort(v,c,0,n);
	quicksort(v2,c2,0,n-1);
	if(c==c2)cout<<"Stable\n"s;
	else cout<<"Not stable\n"s;
	for(int i=0;i<n;++i)cout<<c2.at(i)<<" "s<<v2.at(i)<<"\n"s;
}


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

from itertools import product
import numpy as np

def main():
    N = II()
    A, G, C, T = 0, 1, 2, 3
    dp = np.zeros((N + 1, 4, 4, 4), int)
    dp[0, T, T, T] = 1
    for n in range(N):
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) == (A, G, C):
                    continue
                if (p2, p1, cur) == (A, C, G):
                    continue
                if (p2, p1, cur) == (G, A, C):
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                dp[n + 1, cur, p1, p2] = \
                    (dp[n + 1, cur, p1, p2] + dp[n, p1, p2, p3]) % MOD
    ans = np.sum(dp[N])

    return ans % MOD

print(main())

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

int W, H, x, y, r;

int main() {
    cin >> W >> H >> x >> y >> r;
    if (x>=r && y>=r && x+r<=W && y+r<=H) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>

#define MIN(x, y) (x < y ? x : y)
#define MAX(x, y) (x > y ? x : y)

using namespace std;


int main(){
	int N;
	cin >> N;
	
	int X[200000];
	int tmp[200000];
	for(int i = 0; i < N; ++i){
		cin >> X[i];
		tmp[i] = X[i];
	}
		
	sort(tmp, tmp + N);
	
	for(int i = 0; i < N; ++i){
		// 中央値以下
		if(X[i] <= tmp[N / 2 - 1]){
			cout << tmp[N / 2] << endl;
		} else{
			cout << tmp[N / 2 - 1] << endl;
		}
	}
}



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


int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.rbegin(), a.rend());
    int alice = 0;
    int bob = 0;
    rep(i, n) {
        if ((i+1) % 2 == 1) alice += a[i];
        else bob += a[i];
    }
    cout << alice - bob << endl;
    return 0;
}

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

using namespace std;



int main() {
	int n,tmp;
	cin >> n;
	pair<int, pair<int, int>>* sorted_weight = new pair<int, pair<int, int>>[n * n];
	int* equiv = new int[n];


	int cnt_equiv = 0;
	int cnt_edge = 0;
	int cost = 0;
	
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> tmp;
			sorted_weight[i * n + j] = make_pair(tmp, make_pair(i, j));
		}
		equiv[i] = 0;
	}
	sort(sorted_weight, sorted_weight + n * n);
	for (int i = upper_bound(sorted_weight, sorted_weight + n * n, make_pair(-1, make_pair(n, n))) - sorted_weight;cnt_edge<n-1;i++) {
		if (equiv[sorted_weight[i].second.second] == 0 || equiv[sorted_weight[i].second.first] == 0) {
			cnt_edge++;
			cost += sorted_weight[i].first;
			if (equiv[sorted_weight[i].second.second] == 0 && equiv[sorted_weight[i].second.first] == 0) {
				cnt_equiv++;
				equiv[sorted_weight[i].second.second] = equiv[sorted_weight[i].second.first] = cnt_equiv;
			}
			else if (equiv[sorted_weight[i].second.second] == 0) {
				equiv[sorted_weight[i].second.second] = equiv[sorted_weight[i].second.first];
			}
			else {
				equiv[sorted_weight[i].second.first] = equiv[sorted_weight[i].second.second];
			}
		}
		else if (equiv[sorted_weight[i].second.second] != equiv[sorted_weight[i].second.first]) {
			cnt_edge++;
			cost += sorted_weight[i].first;
			tmp = equiv[sorted_weight[i].second.second];
			for (int j = 0;j < n;j++) {
				if (equiv[j] == tmp)equiv[j] = equiv[sorted_weight[i].second.first];
			}
		}
	}
	
	cout << cost << endl;
}



Measured memory_bytes: 3204
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
for i in range(H):
    for j in range(W):
        A[i][j] = A[i][j]%2
flag=0
for i in range(H):
    if i%2==0:
        for j in range(W):
            if A[i][j]==1:
                cur = (i,j)
                flag=1
                break
        if flag==1:break
    else:
        for j in range(W-1,-1,-1):
            if A[i][j]==1:
                cur = (i,j)
                flag = 1
                break
        if flag==1:break
B = []
if flag==0:
    N=0
else:
    i,j = cur
    ind = 1
    while i<H:
        if i%2==0:
            while j<W:
                if j==W-1:
                    if ind==1 and i<H-1:
                        B.append([(i,j),(i+1,j)])
                    i += 1
                    if i<H and A[i][j]==1:
                        ind = 1-ind
                    break
                else:
                    if ind==1:
                        B.append([(i,j),(i,j+1)])
                    j += 1
                    if A[i][j]==1:
                        ind = 1-ind
        else:
            while j>=0:
                if j==0:
                    if ind==1 and i<H-1:
                        B.append([(i,j),(i+1,j)])
                    i += 1
                    if i<H and A[i][j]==1:
                        ind = 1-ind
                    break
                else:
                    if ind==1:
                        B.append([(i,j),(i,j-1)])
                    j -= 1
                    if A[i][j]==1:
                        ind = 1-ind
    N = len(B)
print(N)
for i in range(N):
    (i1,j1),(i2,j2)=B[i]
    print(i1+1,j1+1,i2+1,j2+1)

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

int main() {
  string s;
  cin >> s;

  int cnt = 0;
  if(s == "RRR") cnt = 3;
  if(s == "RRS") cnt = 2;
  if(s == "SRR") cnt = 2;
  if(s == "RSR") cnt = 1;
  if(s == "RSS") cnt = 1;
  if(s == "SRS") cnt = 1;
  if(s == "SSR") cnt = 1;
  cout << cnt << endl;
  return 0;
}



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

const long long MAX_N = 2e5 + 5, inf = 1e9 + 7;
long long n;
long long Arr[MAX_N];
long long P[MAX_N];
long long psum[MAX_N];
long long cnt[MAX_N];
long long dp[MAX_N];

void process(long long d) {
	memset(cnt, 0, sizeof cnt);
	memset(dp, 0, sizeof dp);
	for (long long i = 1; i <= n; i++) {
		P[i] = (d <= Arr[i]? +1: -1);
		psum[i] = P[i] + psum[i - 1];
	}
}

long long calc(long long d) {
	long long res = 0;
	cnt[100000] = 1;
	
	for (long long i = 1; i <= n; i++) {
		dp[i] = dp[i - 1];
		if (P[i] == +1)
			dp[i] += cnt[100000 + psum[i - 1]];
		else
			dp[i] -= cnt[100000 + psum[i]];
			
		res += dp[i] + cnt[100000+ psum[i]];
		cnt[100000+ psum[i]]++;
	}
	
	return res;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (long long i = 1; i <= n; i++)
		cin >> Arr[i];
	
	long long s = 1, e = inf;
	while (e - s > 1) {
		long long mid = e + s >> 1;
		
		process(mid);
		if (calc(mid) < ((((n * (n + 1)) >> 1) + 1) >> 1))
			e = mid;
		else
			s = mid;
	}
	
	cout << s << "\n";
	return 0;
}

Measured memory_bytes: 7168
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(o,0,n)cout<<v[o]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tihs if(fopen("inp.txt","r"))freopen("inp.txt", "r", stdin),freopen("out.txt", "w", stdout);
using namespace std;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define M 100010

int main(){
	IOS;
	tihs;

	ll n;cin>>n;n*=2;
	ll a[n];
	rep(i,0,n)cin>>a[i];
	sort(a,a+n);
	ll ans=0,i=0;
	while(i<n)ans+=a[i],i+=2;
	tel(ans);
	

	return 0;
}

Measured memory_bytes: 256
N,M = gets.split(" ").map(&:to_i)

wa = Array.new(100000, 0)
ac = Array.new(100000, false)
wanum = 0
acnum = 0

for i in 1..M do
  ary = gets.split(" ")
  targetSubject = ary[0].to_i
  targetResult = ary[1]
  next if ac[targetSubject]
  if targetResult == "AC"
    ac[targetSubject] = true
    acnum += 1
    wanum += wa[targetSubject]
  else
    wa[targetSubject] += 1
  end
end

puts "#{acnum} #{wanum}"

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

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	while (cin >> N >> M, N&&M) {
		int r; cin >> r;
		vector<vector<int>>v(M, vector<int>(1300, 0));
		rep(i, 0, r) {
			int t, n, m, s; cin >> t >> n >> m >> s;
			m--;
			if (s) {
				v[m][t]++;
			}
			else {
				v[m][t]--;
			}
		}
		rep(i, 0, M) {
			rep(j, 1, v[i].size())v[i][j] += v[i][j - 1];
			rep(j, 0, v[i].size())v[i][j] = v[i][j] > 0;
			rep(j, 1, v[i].size())v[i][j] += v[i][j - 1];
		}

		int q; cin >> q;
		rep(i, 0, q) {
			int ts, te, m; cin >> ts >> te >> m;
			m--;
			//rep(i, ts-1, te + 1)cout << v[m][i] << (i == te + 9 ? '\n':  ' ');
			cout << v[m][te-1] - v[m][ts-1] << endl;

		}
	}
	return 0;
}

Measured memory_bytes: 52488
line = gets.chomp.split(' ').map { |e| e.to_i }
k = line[0]
s = line[1]

count = 0

for x in 0..k
  for y in 0..k
    z = s - x - y
    if 0 <= z && z <= k
      count += 1
    end
  end
end

puts count 

Measured memory_bytes: 1788
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val A = Array(N) { sc.next().toInt() }
        val Anum = LongArray(100001)
        A.forEach {
            Anum[it]++
        }
        val Q = sc.next().toInt()
        var ans = A.map { it.toLong() }.sum()
        repeat(Q) {
            val B = sc.next().toInt()
            val C = sc.next().toInt()
            val r = C - B
            ans += Anum[B] * r
            Anum[C] += Anum[B]
            Anum[B] = 0L
            pw.println(ans)
        }
    }
}


Measured memory_bytes: 64960
#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 3005;
    template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
    template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
    template <typename T> void read(T &x) {
        x = 0; int f = 1;
        char c = getchar();
        for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
        for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
        x *= f;
    }
    template <typename T> void write(T x) {
        if (x < 0) x = -x, putchar('-');
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T> void writeln(T x) {
        write(x);
        puts("");
    }
    int n, ans, P;
    int fac[MAXN], inv[MAXN], dp[MAXN][MAXN];
    int c(int x, int y) {
        if (y > x) return 0;
        else return 1ll * fac[x] * inv[y] % P * inv[x - y] % P;
    }
    void update(int &x, int y) {
        x = (x + y) % P;
    }
    int power(int x, int y, int P) {
        if (y == 0) return 1;
        int tmp = power(x, y / 2, P);
        if (y % 2 == 0) return 1ll * tmp * tmp % P;
        else return 1ll * tmp * tmp % P * x % P;
    }
    int getdp(int x) {
        int mul = power(2, power(2, n - x, P - 1), P);
        int chs = power(2, n - x, P), now = 1, ans = 0;
        for (int i = 0; i <= x; i++) {
            update(ans, 1ll * dp[x][i] * now % P);
            now = 1ll * now * chs % P;
        }
        return 1ll * mul * ans % P;
    }
    int main() {
        read(n), read(P);
        fac[0] = 1;
        for (int i = 1; i <= n; i++)
            fac[i] = 1ll * fac[i - 1] * i % P;
        inv[n] = power(fac[n], P - 2, P);
        for (int i = n - 1; i >= 0; i--)
            inv[i] = inv[i + 1] * (i + 1ll) % P;
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i; j++) {
            if (j) dp[i][j] += dp[i - 1][j - 1];
            update(dp[i][j], dp[i - 1][j] * (j + 1ll) % P);
        }
        for (int i = 0; i <= n; i++)
            if (i & 1) update(ans, 1ll * (P - c(n, i)) * getdp(i) % P);
            else update(ans, 1ll * c(n, i) * getdp(i) % P);
        writeln(ans);
        return 0;
    }

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)

#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload3(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)

#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))

template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl

int main(){
    int n,i;
    cin>>n>>i;
    cout<<n-i+1<<endl;
    return 0;
}	

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

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

    ll ans = LINF;
    // buy : C 
    for(ll i=0;i<=2*max(x,y);i+=2){
        ll n = i/2;
        ll cost = i * c;
        if(n < x) cost += a * (x-n);
        if(n < y) cost += b * (y-n);
        chmin(ans,cost);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>
#include <bitset>
#include <list>
#include <iomanip>
#include <cctype>

#define for0(i, N)    for (int i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (int i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (int i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (int i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (int i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (int i = (x), a = 0; a < (N);  \
                              i = (i + 1) % (N), ++a)

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b, int){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b + 1;
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b++;
    return temp;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b, int){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b - 1;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b--;
    return temp;
}

using namespace std;

typedef long long ll;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;
typedef vector<ll> vll;
typedef vector<ld> vld;


int main(void){
    cin.tie(0); ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);
    int n;
    cin >> n;
    vll a(n);
    for0(i, n)cin >> a[i];

    for0(i, n){
        if (a[i] % 2 == 0 && (a[i] % 3 != 0 && a[i] % 5 != 0)) {
            cout << "DENIED" << "\n";
            return 0;
        }
    }
    cout << "APPROVED" << "\n";

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		String T = sc.next();

		int ans = T.length();

		for (int start = 0; start <= S.length() - T.length(); start ++) {

			int diff = 0;

			for (int i = 0; i < T.length(); i++) {
				if (T.charAt(i) != S.charAt(start + i)){
					diff++;
				}
			}
			ans = Math.min(ans, diff);
		}

		System.out.println(ans);
	}


}

Measured memory_bytes: 35564
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define SORTR(x) sort(ALLR(x));
#define SORT(x) sort(ALL(x));
#define SUM(x) accumulate(ALL(A), 0);
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
typedef vector<ll> VI;
typedef vector<VI> VVI;
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 <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}


void Main()
{
	ll N;
	ll result=0;
	cin>>N;
	VI vec(N);
	REP(i, N) cin >> vec[i];

	REP(i,N-2){
		if(min({vec[i+2],vec[i+1],vec[i]})!=vec[i+1]&&max({vec[i+2],vec[i+1],vec[i]})!=vec[i+1])
			result++;
	}

	cout << result << "\n";
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 256