akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size())cout << a[i] << " ";cout << "\n"
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
template<class T> inline bool change(T a,T b){if(a > b){swap(a,b);return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
ll fac[cmax], finv[cmax], inv[cmax];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S;
    cin >> S;ll s = S.size(),ans = 0;
    rep(i,s){
        if(S[i] == '2')ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
  lint n;
  cin >> n;
  lint a, b;
  cin >> a >> b;
  cout << ((b - a) % 2 == 0
             ? (b - a) / 2
             : (b - a - 1) / 2 + 1 + (n - b <= a - 1 ? n - b : a - 1))
       << endl;

  return 0;
}


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

int main() {
  int N,i;
  cin >> N;
  vector<double> v(N);
  for(i=0; i<N; i++)
    cin >> v.at(i);
  sort(v.begin(), v.end());
  
  for(i=0; i<N-1; i++)
    v.at(i+1) = (v.at(i)+v.at(i+1))/2;
  cout << v.at(N-1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, a[55], lo=0, hi=0, lp, hp;
int main(){
    scanf("%i", &n);
    fox(l, n){
        scanf("%i", &a[l]);
        if (lo>=a[l]) lp=l;
        lo=min(lo, a[l]);
        if (hi<=a[l]) hp=l;
        hi=max(hi, a[l]);
    }
    hp++; lp++;
    cout << 2*n << endl;
    if (hi>-lo){
        cout << hp << ' ' << 1 << endl;
        cout << hp << ' ' << 1 << endl;
        fox1(l, n-1){
            cout << l << ' ' << l+1 << endl;
            cout << l << ' ' << l+1 << endl;
        }
    } else {
        cout << lp << ' ' << n << endl;
        cout << lp << ' ' << n << endl;
        fox1r(l, n-1){
            cout << l+1 << ' ' << l << endl;
            cout << l+1 << ' ' << l << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int K, S,ans=0;
	cin >> K >> S;
	for (int X = 0; X <=K; X++) {
		for (int Y = 0; Y <= K; Y++) {
			int Z = S - X - Y;
			if (Z >= 0 && Z <= K) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}

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

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    int dp[100100];
    rep(i,n) dp[i] = INF;
    
    dp[0] = 0;
    rep(i,n) {
        for (int j = 1; j<=k; ++j) {
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

H,W,M = MI()

X = [0]*(H+1)  # X[i] = x座標がiである爆破対象はいくつあるか
Y = [0]*(W+1)  # Y[i] = y座標がiである爆破対象はいくつあるか

from collections import defaultdict
d = defaultdict(int)  # d[(h,w)] == 1 ⇔ 座標(h,w)に爆破対象が存在する

for i in range(M):
    h,w = MI()
    X[h] += 1
    Y[w] += 1
    d[(h,w)] = 1

mx = max(X)
my = max(Y)
ans = mx+my
A = [i for i in range(1,H+1) if X[i] == mx]
B = [i for i in range(1,W+1) if Y[i] == my]

if len(A)*len(B) > M:
    print(ans)
else:
    for i in A:
        for j in B:
            if d[(i,j)] == 0:
                print(ans)
                exit()
    print(ans-1)


Measured memory_bytes: 167916
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll e(ll s,ll p,ll x){
    if(x==0)return 0;
    if(s==1)return 1;
    if(x<=s/2)return e((s-3)/2,(p-1)/2,x-1);
    else return p/2+1+e((s-3)/2,(p-1)/2,x-s/2-1);
}
int main(){
    ll n,x,s=1,p=1;cin>>n>>x;
    for(int i=0;i<n;i++){
        s=s*2+3; p=p*2+1;
    }
    cout<<e(s,p,x)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

int dp[1010101][2];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int ans = 0;
    reverse(S.begin(), S.end());
    int N = S.size();
    REP(i,1010101) dp[i][0] = dp[i][1] = INF;
    dp[0][0] = 0;
    REP(i,N){
        int a = S[i] - '0';
        chmin(dp[i+1][0], min(dp[i][0], dp[i][1]) + a);
        chmin(dp[i+1][1], min(dp[i][0] + 11 - a, dp[i][1] + 9 - a));
    }
    cout << min(dp[N][0], dp[N][1]) << endl;
}


Measured memory_bytes: 9372
def D():
    N,M = map(int,input().split())
    a = [[]for _ in range(8)]
    for _ in range(N):
        x,y,z = map(int,input().split())
        a[0].append(x+y+z)
        a[1].append(x+y-z)
        a[2].append(x-y+z)
        a[3].append(x-y-z)
        a[4].append(-x+y+z)
        a[5].append(-x+y-z)
        a[6].append(-x-y+z)
        a[7].append(-x-y-z)
    ans = [0]*8
    for i in range(8):
        a[i].sort(reverse = True)
        ans[i] = sum(a[i][:M])
    
    print(max(ans))

D()

Measured memory_bytes: 3316
#include <bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ll long long int
using namespace std;
ll ans = 0, sum = 0, n, k, counter = 0, w, h;
string s;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(50, vector<ll>(50, 0));

int main()
{
	ll m; bool flg = false;
	while (true)
	{
		cin >> n >> m;
		if (!n && !m) return 0;
		vector<ll> va, vb;
		va.resize(n); vb.resize(m);
		REP(i, n) cin >> va[i];
		REP(i, m) cin >> vb[i];
		ll asum = accumulate(va.begin(), va.end(), 0), bsum = accumulate(vb.begin(), vb.end(), 0);
		REP(i, n)
			REP(j, m) {
			if (asum - va[i] + vb[j] == bsum - vb[j] + va[i]) {
				cout << va[i] << " " << vb[j] << endl;
				j = m;
				i = n;
				flg = true;
			}
		}
		if (!flg) cout << "-1" << endl;
		flg = false;
	}
}

Measured memory_bytes: 3096
def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD

    return ret


X, Y = map(int, input().split())

MOD = 10 ** 9 + 7

if (2 * Y - X < 0 or 2 * X - Y < 0
        or (2 * Y - X) % 3 != 0
        or (2 * X - Y) % 3 != 0):
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

print(comb(a + b, a))


Measured memory_bytes: 38640
import java.util.ArrayList;
import java.util.Scanner;

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

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        ArrayList<Integer> a = new ArrayList<>();
        int count = 0;

        for (int i = 0; i < n; i++) {
            int nextInt = sc.nextInt();
            a.add(nextInt);
            if (i > nextInt - 1 && a.get(nextInt-1) == i + 1) {
                ++count;
            }
        }

        System.out.println(count);
        

    }
}

Measured memory_bytes: 63288
#include<bits/stdc++.h>
using namespace std;
int main(){
        string s; cin >> s;
        long long int k; cin >> k;
        int one_cnt = 0;
        for (auto x : s){
            if (x == '1') ++one_cnt;
            else break;
        }
        if (one_cnt >= k) cout << s[one_cnt-1] << endl;
        else cout << s[one_cnt] << endl;
    return 0;
}


Measured memory_bytes: 3592
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

struct UnionFind
{
  int n;
  std::vector<int> par,size;
  UnionFind(int sz) : n(sz), par(sz,0), size(sz,1) {
    std::iota(par.begin(),par.end(),0);
  }
  int find(int x) {
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x=find(x);y=find(y);
    if(x==y) return;
    if(size[x]<size[y]) std::swap(x,y);
    size[x]+=size[y];
    par[y]=x;
  }
};


signed main() {
	int n,m,k;
	std::cin >> n >> m >> k;
	UnionFind uf(n);
	std::vector<std::vector<int> > blocked(n,std::vector<int>());
	std::vector<int> friends(n,0);
	rep(i,m) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		friends[a]++;
		friends[b]++;
		uf.unite(a,b);
	}
	rep(i,k) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		blocked[a].emplace_back(b);
		blocked[b].emplace_back(a);
	}
	rep(i,n) {
		int count = uf.size[uf.find(i)]-1;
		count-=friends[i];
		for(auto b:blocked[i]) if(uf.find(i)==uf.find(b)) count--;
		std::cout << count << ' ';
	}
	std::cout << ENDL;
	return 0;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
string a;
string b;
pair<int,int> dp[3005][3005];
int lst[3005][3005];
int x,y;
int main() {
	cin >> a >> b;
	for(int i=1; i<=a.length(); i++) {
		for(int j=1; j<=b.length(); j++) {
			if(a[i-1]==b[j-1]) {
				dp[i][j]={dp[i-1][j-1].first+1,i*3005+j};
				if(dp[i-1][j-1].first==0) lst[i][j]=-1;
				else lst[i][j]=dp[i-1][j-1].second;
			} else {
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	if(dp[a.length()][b.length()].first==0) return 0;
	x = dp[a.length()][b.length()].second / 3005;
	y = dp[a.length()][b.length()].second % 3005;
	string ans="";
	while(true) {
		ans = a[x-1] + ans;
		int tmp = lst[x][y];
		if(tmp==-1) break;
		x = tmp / 3005;
		y = tmp % 3005;
	}
	cout << ans << endl;
}

Measured memory_bytes: 105984
#include <bits/stdc++.h>
using namespace std;
#define make_pair(a, b) mp(a, b)
typedef pair<int, int> pii; 
typedef long long ll;
const int maxn = 2e5 + 10;
int c[maxn];
int n;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if(a == b) c[i] = 1;
	}
	for(int i = 3; i <= n; ++i)
	{
		if(c[i] && c[i - 1] && c[i - 2])
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

Measured memory_bytes: 3760
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int ans = 0;
    int[] a = new int[n + 1];

    for (int i = 1; i < n; i++) {
      for (int j = 1; (i * j) < n; j++) {
        a[i * j]++;
      }
    }

    for (int i = 1; i <= n; i++) {
      ans += a[i];
    }

    System.out.println(ans);

  }
}

Measured memory_bytes: 40272
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


int main(){
    int T = 1; //cin>>T;
    for(int t = 1; t <= T; t++){
    	int x; cin >> x;
    	if(x >= 30) cout << "Yes\n";
    	else cout << "No\n";
    }
    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
const int maxn=2e5+5;
typedef long long ll;
using namespace std;
int a[maxn],b[maxn];
int main(int argc, char *argv[]) {
//    freopen("in.text", "r", stdin);
//    freopen("out.text", "w", stdout);
    int n; cin>>n;
    for(int i=1;i<=n;++i){
        cin>>b[i];
        a[b[i]]++;
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
        ans+=(ll)a[i]*(a[i]-1)/2;
    for(int i=1;i<=n;++i)
        cout<<ans-a[b[i]]+1<<endl;
}


Measured memory_bytes: 3712
N = int(input())
A = list(map(int, input().split()))

money = 1000
stock = 0

for i in range(N):
    if i == N - 1:
        money += stock * A[i]
        break
    if A[i] < A[i + 1]:
        buy_stock = money // A[i]
        money -= A[i] * buy_stock
        stock += buy_stock
    elif A[i] > A[i + 1]:
        money += A[i] * stock
        stock = 0

print(money)


Measured memory_bytes: 9064
#include<bits/stdc++.h>
using namespace std;
 
main(){
 
 
int n;
cin>>n;
 vector <long long int > h(n);
 for(int i=0;i<n;i++)cin>>h[i];
  vector <long long  int > dp(n,1e10);
  dp[0]=0;
  
  for(int i=0;i<n-1;i++){
  dp[i+1]=min(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
    if((i+2)<n){
    
    dp[i+2]=min(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
    
    }   
  }
  cout<<dp[n-1];

}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


long long A, B;

long long gcd(long long  a, long long b);

int main()
{
	cin >> A;
	cin >> B;


	long long ans = 1;

	long long G = gcd(A, B);
	long long g = G;


	for (long long i = 2; i*i <= G; i++) {
		if (g%i == 0) {
			ans++;
			while(g%i == 0) {g /= i;}
		}
	}

	if (g != 1) { ans++; }

	cout << ans << endl;

	return 0;
}
long long gcd(long long  a, long long b)
{
	if (a%b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a%b));
	}
}

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

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

Node *NIL, *root;
bool flag;

void init(void){
  root=(Node*)malloc(sizeof(Node));
  
  root->key=INT_MAX;
  root->left=NIL;
  root->right=NIL;
}

void insert(int key){
  Node *in=(Node*)malloc(sizeof(Node));
  Node *tmp=root;
  Node *par;
  
  in->key=key;
  in->left=NIL;
  in->right=NIL;

  if(root->key == INT_MAX) root=in;
  else{
    while(tmp != NIL){
      par=tmp;
      if(tmp->key > in->key) tmp=tmp->left;
      else tmp=tmp->right;
    }
    in->parent=par;
    if(in->parent->key > in->key) in->parent->left=in;
    else in->parent->right=in;
  }
}

void find(Node *point, int key){
  if(point == NIL) return;
  if(point->key == key){
    flag=true;
    return;
  }
  
  if(key < point->key) find(point->left, key); 
  else find(point->right, key);
}


void preorder(Node *point){
  if(point == NIL) return;

  printf(" %d", point->key);
  preorder(point->left);
  preorder(point->right);
}

void inorder(Node *point){
  if(point == NIL) return;

  inorder(point->left);
  printf(" %d", point->key);
  inorder(point->right);
}

void print(){
  inorder(root);
  printf("\n");
  preorder(root);
  printf("\n");
}

int main(){
  int  i, n, key;
  char com[7];

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

  for(i=0; i<n; i++){
    scanf("%s %d", com, &key);
    if(com[0] == 'i') insert(key);
    else if(com[0] == 'f'){
      flag=false;
      find(root, key);
      if(flag) printf("yes\n");
      else printf("no\n");
    }
    else print();
    
  }
  
}



Measured memory_bytes: 21860
#include <iostream>
using namespace std;
static unsigned int inf = 1e9+7;
static int bn = 1e5;
int main(){
    int n;
    int sum = 0;
    cin >> n;
    if(n%2==0)sum = n/2-1;
    else sum = n/2;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>

int Mymax(int a,int b);
int Mymin(int a,int b);
int main(){
	int N1,N2,N3,N4;
	int A,B;
	scanf("%d %d %d %d",&N1,&N2,&N3,&N4);
	
	int x = 1974;
	int y;
	int judge = 0;
	y = 1000*N1+100*N2+10*N3+N4;
	if(y == x){
		judge = 1;
	}
	y = 1000*N1+100*N2+10*N4+N3;
	if(y == x){
		judge = 1;
	}
	y = 1000*N1+100*N3+10*N2+N4;
	if(y == x){
		judge = 1;
	}
	y = 1000*N1+100*N3+10*N4+N2;
	if(y == x){
		judge = 1;
	}
	y = 1000*N1+100*N4+10*N3+N2;
	if(y == x){
		judge = 1;
	}
	y = 1000*N1+100*N4+10*N2+N3;
	if(y == x){
		judge = 1;
	}
	//
	y = 1000*N2+100*N1+10*N3+N4;
	if(y == x){
		judge = 1;
	}
	y = 1000*N2+100*N1+10*N4+N3;
	if(y == x){
		judge = 1;
	}
	y = 1000*N2+100*N3+10*N1+N4;
	if(y == x){
		judge = 1;
	}
	y = 1000*N2+100*N3+10*N4+N1;
	if(y == x){
		judge = 1;
	}
	y = 1000*N2+100*N4+10*N1+N3;
	if(y == x){
		judge = 1;
	}
	y = 1000*N2+100*N4+10*N3+N1;
	if(y == x){
		judge = 1;
	}
	//
	y = 1000*N3+100*N1+10*N2+N4;
	if(y == x){
		judge = 1;
	}
	y = 1000*N3+100*N1+10*N4+N2;
	if(y == x){
		judge = 1;
	}
	y = 1000*N3+100*N2+10*N1+N4;
	if(y == x){
		judge = 1;
	}
	y = 1000*N3+100*N2+10*N4+N1;
	if(y == x){
		judge = 1;
	}
	y = 1000*N3+100*N4+10*N1+N2;
	if(y == x){
		judge = 1;
	}
	y = 1000*N3+100*N4+10*N2+N1;
	if(y == x){
		judge = 1;
	}
	//
	y = 1000*N4+100*N1+10*N2+N3;
	if(y == x){
		judge = 1;
	}
	y = 1000*N4+100*N1+10*N3+N2;
	if(y == x){
		judge = 1;
	}
	y = 1000*N4+100*N2+10*N1+N3;
	if(y == x){
		judge = 1;
	}
	y = 1000*N4+100*N2+10*N3+N1;
	if(y == x){
		judge = 1;
	}
	y = 1000*N4+100*N3+10*N1+N2;
	if(y == x){
		judge = 1;
	}
	y = 1000*N4+100*N3+10*N2+N1;
	if(y == x){
		judge = 1;
	}
	
	if(judge == 1){
		printf("YES");
	}else{
		printf("NO");
	}
	return 0;
}

int Mymax(int a,int b){
	int r;
	if(a > b){
		r = a;
	}else{
		r = b;
	}
	return r;
}

int Mymin(int a,int b){
	int r;
	if(a < b){
		r = a;
	}else{
		r = b;
	}
	return r;
}

Measured memory_bytes: 128
#include<iostream>
#include<set>

using namespace std;

int main()
{
	multiset<int ,greater<int> > num;
	int n;
	
	for(;cin >> n;)
	{
		num.clear();
		num.insert(n);
		for(int i=0;i<4;i++)
		{
			cin >> n;
			num.insert(n);
		}
		
		multiset<int,greater<int> >::iterator it = num.begin();
		
		for(;it!=num.end();)
		{
			it++;
			if(it!=num.end())
			{
				it--;
				cout << *it << " " ;
			}
			else
			{
				it--;
				cout << *it << endl;
			}
			
			it++;
		}
	}
}

Measured memory_bytes: 0
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define int long long int
constexpr int MOD = 1000000000 + 7; // 10 ** 9 + 7
using namespace std;

int dp[100000 + 2][13];

void add(int i, int n) {
  n %= 13;
  for (int p = 0; p < 13; p++) {
    int idx = (p + n) % 13;
    dp[i + 1][idx] += dp[i][p];
    dp[i + 1][idx] %= MOD;
  }
}

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

  reverse(s.begin(), s.end());

  dp[0][0] = 1;

  int base = 1;
  for (int i = 0; i < s.size(); i++) {
    char c = s[i];
    if (c == '?') {
      for (int n = 0; n < 10; n++) {
        add(i, base * n);
      }
    } else {
      add(i, base * (c - '0'));
    }
    base = (base * 10) % 13;
  }

  cout << dp[s.size()][5] << endl;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 10704
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long x = sc.nextLong();
		long count = b/x-a/x;
		if (a%x==0) {
			count ++;
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 35648
#include <iostream>
using namespace std;
#define rep(i, n) for(int i=1;i<n;i++)

int main(){
    int num;
    cin >> num;
    int count=0, ans=0;
    rep(i, num+1){
        if(i%2 == 1){
            rep(j, i+1){
                if(i%j == 0){
                    count++;
                }
            }
            if(count == 8){
                ans++;
            }
            count=0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3604
#!/usr/bin/env python3
import sys

#lines = stdin.readlines()
def rint():
    return map(int, sys.stdin.readline().split())

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())

N = oint()

d = list(rint())

if d[0] != 0:
    print(0)
    exit()

d.sort()

if N > 1 and d[1] == 0:
    print(0)
    exit()

n = 1
c = 0
cprev = 1
ans = 1
for i in range(1, N):
    if d[i] == n:
        c+=1
    elif d[i] != n+1:
        print(0)
        exit()
    else:
        ans = (ans* pow(cprev, c, 998244353))%998244353
        n += 1
        cprev = c
        c = 1

ans = (ans* pow(cprev, c, 998244353))%998244353
print(ans)




Measured memory_bytes: 14396
/* template.cpp(shinobu_menkoi) {{{ */
#include <bits/stdc++.h>
using namespace std;

// clang-format off
#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rep1(n) rep2(_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, n) rep4(i, a, n, 1)
#define rep4(i, a, n, s) for (lint i = (a); i < (lint)(n); i += (s))
#define rrep(...) GET_MACRO(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rrep1(a) rrep2(_, a)
#define rrep2(i, a) rrep3(i, a, 0)
#define rrep3(i, a, n) rrep4(i, a, n, 1)
#define rrep4(i, a, n, s) for (lint i = (a); i >= (lint)(n); i -= (s))
#define each(i, ctn) for (auto &&i : (ctn))

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'
#define TEMP_T template <class T>
#define TEMP_TU template <class T, class U>

TEMP_T using vec = vector<T>;
TEMP_T using heap = priority_queue<T>;
TEMP_T using minheap = priority_queue<T, vec<T>, greater<T>>;
using lint = long long;
using ulint = unsigned long long;
using ld = long double;
using vi = vec<int>;
using vvi = vec<vi>;
using vvvi = vec<vvi>;
using pii = pair<int, int>;
using vs = vec<string>;

TEMP_TU ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << p.fi << " " << p.se; }
TEMP_TU istream &operator>>(istream &is, pair<T, U> &p) { return is >> p.fi >> p.se; }

constexpr int INF{1001001001};
constexpr lint LINF{1001001001001001001ll};
constexpr int MOD{(int)1e9 + 7};
constexpr double EPS{1e-9};
const double PI{acos(-1)};
constexpr int dx[]{0, 1, 0, -1, 1, -1, 1, -1}, dy[]{1, 0, -1, 0, 1, -1, -1, 1};

inline bool inside(int y, int x, int h, int w) { return y >= 0 && x >= 0 && y < h && x < w; }
TEMP_T inline bool chmin(T &a, const T &b) { if (a > b) a = b; return a > b; }
TEMP_T inline bool chmax(T &a, const T &b) { if (a < b) a = b; return a < b; }
TEMP_T inline void print(const T &x) { cout << x << '\n'; }
TEMP_T inline void print(const vec<T> &v, string d = "\n") { rep(i, v.size()) cout << v[i] << (i == (lint)(v.size() - 1) ? "\n" : d); }
template <class T = int> inline T in() { T x; cin >> x; return x; }
template <class T = string> vec<T> split(const string &s, char d = ',') {
  vec<T> v; stringstream ss(s); for (string b; getline(ss, b, d); ) {
    stringstream conv(b); T t; conv >> t; v.eb(t); } return v;
}
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } pre__;
// clang-format on
/* }}} */

signed main() {
  lint N = in();
  map<lint, lint> m;
  rep(i, N) {
    lint a = in();
    m[a]++;
  }

  lint cnt = 0;
  lint res = 0;
  vec<lint> v;
  for (auto itr = m.rbegin(); itr != m.rend() && cnt != 2; ++itr) {
    if (itr->second < 2) continue;
    if (itr->second >= 4 && cnt != 1) {
      res = itr->first * itr->first;
      break;
    }
    v.emplace_back(itr->first);
    cnt++;
  }

  cout << (v.size() == 2 ? v[0] * v[1] : res) << endl;
}


Measured memory_bytes: 6528
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  val n = sc.nextInt
  val vs: List[Double] = List.fill(n)(sc.nextDouble)
  val sorted: List[Double] = vs.sorted
  val result = sorted.tail.foldLeft(sorted.head)((v1, v2) => (v1 + v2) / 2)
  println(result)
}


Measured memory_bytes: 25900
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#define ll long long
using namespace std;

int main() {
	ll a, b;
	ll maxs, size;
	cin >> a >>b;
	maxs = min(a, b);
	size = a + b - min(a, b);
	for (int i = 0; i < size; i++) {
		cout << maxs;
	}
	cout << endl;



	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int segsize = 19;

ll SegTree[1<<segsize],Lazy[1<<segsize];
bool Flag[1<<segsize];
void denpa(int k,int l,int r)
{
	if(Flag[k])
	{
		SegTree[k]+=Lazy[k];
		//if(Lazy[k]!=INT_MAX)
		if(r-l>1)
		{
			Lazy[2*k] += Lazy[k];
			Lazy[2*k+1] += Lazy[k];
			Flag[k*2] = Flag[k*2+1]=true;
		}
		Lazy[k]=0;
		Flag[k] = false;

	}
}

void update(int a,int b,ll x,int k=1,int l=0,int r =-1)
{
	if(r<0)r=(1<<(segsize-1));
	//cout<<a<<' '<<b<<' '<<x<<' '<<k<<' '<<l<<' '<<r<<endl;
	denpa(k,l,r);
	if(b<=l||r<=a)return;
	if(a<=l&&r<=b)
	{
		Lazy[k] = (1LL)*x;
		Flag[k] = true;
		denpa(k,l,r);
	}
	else
	{
		update(a,b,x,k*2,l,(l+r)/2);
		update(a,b,x,k*2+1,(l+r)/2,r);
		SegTree[k] = min(SegTree[k*2],SegTree[k*2+1]);
	}
}

ll getsum(int a,int b,int k=1,int l=0,int r=-1)
{
	if(r<0)r = 1<<(segsize-1);
	denpa(k,l,r);
	if(b<=l||r<=a)return LLONG_MAX;
	if(a<=l&&r<=b)return SegTree[k];
	ll vl = getsum(a,b,k*2,l,(l+r)/2);
	ll vr = getsum(a,b,2*k+1,(l+r)/2,r);
	return min(vl,vr);
}

int main()
{
	for(int i = 0;i<(1<<segsize);i++)
	{
		SegTree[i]=0;
		Lazy[i] = 0;
	}
	int n,q;
	cin >> n >> q;
	for(int i = 0;i<q;i++)
	{
		int op;
		cin >> op;
		if(op)
		{
			int a,b;
			cin >> a >> b;
			
			cout<<getsum(a,b+1)<<endl;
		}
		else
		{
			int a,b,x;
			cin >> a >> b >> x;
			
			update(a,b+1,x);
		}
		//for (int i = 0; i < (1<<segsize); i++){cout<<SegTree[i]<<' '<<Lazy[i]<<endl;}cout<<endl;
		
		
	}
}


Measured memory_bytes: 11464
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int s[1000],top;
int pop();
void push(int);

int main(){
  int l,m;
  char h[100];
  top=0;

  while(scanf("%s", h) !=EOF){
    if(h[0] == '-')
      {

	m=pop();
	l=pop();
	push(l-m);

      }
    else if(h[0] == '+')
      {

	m=pop();
	l=pop();
	push(l+m);
      }
    else if(h[0] == '*')
      {
	l=pop();
	m=pop();
	push(l*m);
      }
    else push(atoi(h));
    }
  
  printf("%d\n",pop());

  return 0;
}


int pop(){
  top--;
  return s[top+1];
}

void push(int d){
  s[++top]=d;
}
       



Measured memory_bytes: 2108
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

int b_row,b_col,memo[16][3][3];

char b[2];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= 2 && col >= 0 && col <= 2)return true;
	else{
		return false;
	}
}

int translate(char ch){
	switch(ch){
	case 'A':return 0;
	case 'B':return 1;
	case 'C':return 2;
	case 'D':return 10;
	case 'E':return 11;
	case 'F':return 12;
	case 'G':return 20;
	case 'H':return 21;
	case 'I':return 22;
	}

	return -1; //must not reach here.
}

int main(){

	int n,tmp,energy_row,energy_col,row,col,div_row[4] = {-1,0,0,1},div_col[4] = {0,-1,1,0};
	char start[2],energy[2];

	while(true){
		scanf("%d",&n);
		if(n == 0)break;

		for(int i = 0; i < 16; i++){
			for(int p = 0; p < 3; p++){
				for(int k = 0; k < 3; k++)memo[i][p][k] = 0;
			}

		}

		scanf("%s %s %s",start,energy,b);

		tmp = translate(b[0]);
		b_row = tmp/10;
		b_col = tmp%10;

		tmp = translate(energy[0]);
		energy_row = tmp/10;
		energy_col = tmp%10;

		tmp = translate(start[0]);

		row = tmp/10,col = tmp%10;

		memo[0][row][col] = 1;

		for(int loop = 0; loop <= n-1; loop++){
			for(int i = 0; i < 3; i++){
				for(int k = 0; k < 3; k++){
					if(i != b_row || k != b_col){
						for(int p = 0; p < 4; p++){
							if(rangeCheck(i+div_row[p],k+div_col[p]) == true && (i+div_row[p] != b_row || k + div_col[p] != b_col)){
								memo[loop+1][i+div_row[p]][k+div_col[p]] += memo[loop][i][k];
							}else{
								memo[loop+1][i][k] += memo[loop][i][k]; 
							}
						}
					}
				}
			}
		}

		printf("%.8lf\n",((double)memo[n][energy_row][energy_col])/((double)pow(4,n)));
	}

	return 0;
}

Measured memory_bytes: 2688
//include
//------------------------------------------
#include <bits/stdc++.h> // only for GCC

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

//container util
//------------------------------------------
#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

//repetition
//------------------------------------------
#define loop(i,a,b) for(ull i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define iter(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define riter(i,c) for(auto i=(c).rbegin(); i!=(c).rend(); ++i)

//constant
//--------------------------------------------
const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

// output vector
// ------------------------------------------
namespace std {
    template<typename T>ostream&operator<<(ostream&os, vector<T>const&v){
        iter(it,v) os<<*it<<(it+1==v.end()?"":",");
        return os;
    }
    template<typename T, typename U>ostream&operator<<(ostream&os,const pair<T,U>&p){
        return os << "[" << p.dirst << "," << p.second << "]";
    }
}

//clear memory
// ------------------------------------------
#define clr(a,i) memset((a), (i) ,sizeof(a))

int main(){
   int y,m,d;
   while(cin >> y >> m >> d){
      if(y<1868) cout << "pre-meiji" << endl;
      else if(y==1868){
         if(m<9) cout << "pre-meiji" << endl;
         else if(m==9){
            if(d<8) cout << "pre-meiji" << endl;
            else cout << "meiji " << y-1867 << " " << m << " " << d << endl;
         }else cout << "meiji " << y-1867 << " " << m << " " << d << endl;
      }
      else if(y<1912) cout << "meiji " << y-1867 << " " << m << " " << d << endl;
      else if(y==1912){
         if(m<7) cout << "meiji " << y-1867 << " " << m << " " << d << endl;
         else if(m==7){
            if(d<30) cout << "meiji " << y-1867 << " " << m << " " << d << endl;
            else cout << "taisho " << y-1911 << " " << m << " " << d << endl;
         }else cout << "taisho " << y-1911 << " " << m << " " << d << endl;
      }
      else if(y<1926) cout << "taisho " << y-1911 << " " << m << " " << d << endl;
      else if(y==1926){
         if(m<12) cout << "taisho " << y-1911 << " " << m << " " << d << endl;
         else if(m==12){
            if(d<25) cout << "taisho " << y-1911 << " " << m << " " << d << endl;
            else cout << "showa " << y-1925 << " " << m << " " << d << endl;
         }
      }
      else if(y<1989) cout << "showa " << y-1925 << " " << m << " " << d << endl;
      else if(y==1989){
         if(m==1){
            if(d<8) cout << "showa " << y-1925 << " " << m << " " << d << endl;
            else cout << "heisei " << y-1988 << " " << m << " " << d << endl;
         }else cout << "heisei " << y-1988 << " " << m << " " << d << endl;
      }else cout << "heisei " << y-1988 << " " << m << " " << d << endl;
   }
}

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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if ((A < C && B > C) || (A > C && B < C))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


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

int main() {
    int64_t n, k;
    cin >> n >> k;

    vector<int64_t> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<bool> seen(n, false);
    vector<int64_t> b(n, -1);
    int64_t pt_town = 0;
    int64_t num_town = 0;
    while(!seen[pt_town]) {
        seen[pt_town] = true;
        b[num_town] = pt_town;
        pt_town = a[pt_town];
        num_town++;
    }

    //cout << "pt: " << pt_town << endl;
    //cout << "nm: " << num_town << endl;
    //for(int i = 0; i < n; i++) cout << b[i] << " ";
    //cout << endl;

    for(int i = 0; i < n; i++) {
        if(b[i] == pt_town) {
            //cout << "i: " << i << endl;
            if(k <= i) {
                cout << b[k] + 1 << endl;
            } else {
                k -= i;
                k %= num_town - i;
                //cout << "k: " << k << endl;
                cout << b[i + k] + 1 << endl;
            }
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 6384
"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

n = int(input())
s = input()
print(s.count("ABC"))

Measured memory_bytes: 2940
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;

// Required random number generators

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
    #ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        //freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t clk;
    clk = clock();
//-----------------------------------------------------------------------------------------------------------//

    set<ll> S;
    FORI(i,0,105)
    {
        S.insert(i);
    }
    READV(X);
    READV(N);
    FORI(i,0,N)
    {
        READV(x);
        S.erase(S.find(x));
    }
    auto it=S.lower_bound(X);
    ll a1=*it;
    ll a2=*it;
    if(it!=S.begin())
    {
        it--;
        a2=*it;
    }
    if(a1-X>=X-a2)
    {
        cout<<a2<<endl;
    }
    else
    {
        cout<<a1<<endl;
    }

//-----------------------------------------------------------------------------------------------------------//


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

    return 0;
}

Measured memory_bytes: 3800
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
  int h, n;
  cin >> h >> n;
  int a[1005], b[1005], c[1005];
  for(int i=0; i<n; i++){
    cin >> a[i] >> b[i];
  }
  vector<vector<int>> z(n, vector<int>(2));
  vector<int> dp(h+5, 1001001001);
  dp[0] = 0;
  for (int i = 0; i < n; i++){
    for(int j=0; j<h; j++){
      int nj = min(j + a[i], h); //範囲外アクセスへの対策 基本はj+a
      dp[nj] = min(dp[nj], dp[j] + b[i]); //何もしない か 
                                          //攻撃して(減る体力jがnjになって)魔力を消耗するか
    }
  }
  cout << dp[h] << "\n";
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int n,k;
multiset<int> choice;
multiset<int> choice2;
int v[60];
int cnt;
int tt;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	int res=0;
	for(int i=0;i<=min(n,k);i++){
		cnt=tt;
		choice=choice2;
		if(i!=0){
			choice.insert(v[i]);
			cnt+=v[i];
		}
		tt=cnt;
		choice2=choice;
		for(int j=0;j<=min(n-i,k-i);j++){
			if(j!=0){
				choice.insert(v[n-j+1]);
				cnt+=v[n-j+1];
			}
			int lft=k-i-j;
			int ct=0;
			int tmp=cnt;
			for(__typeof(choice.begin()) it=choice.begin();it!=choice.end()&&ct<lft;it++){
				if(*it>=0)
					break;
				tmp-=*it;
				ct++;
			}
			res=max(res,tmp);
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define inv_num_valtype int

//比較関数
int compare(inv_num_valtype a, inv_num_valtype b){
	return a - b;
}

//昇順
int inv_num_sub(inv_num_valtype *origin, int left, int right, inv_num_valtype *tmp){
	int ans = 0;
	if(right - left > 1){
		int i, j, k, half = (left + right) / 2;
		ans += inv_num_sub(origin, left, half, tmp);
		ans += inv_num_sub(origin, half, right, tmp);
		for(i = left; i < right; i++){
			tmp[i] = origin[i];
		}
		for(i = left, j = left, k = half; i < right; i++){
			if(k == right){
				origin[i] = tmp[j];
				j++;
			}
			else if(compare(tmp[j], tmp[k]) <= 0 && j < half){
				origin[i] = tmp[j];
				j++;
			}
			else{
				origin[i] = tmp[k];
				ans += k - i;
				k++;
			}
		}
	}
	return ans;
}

//i < j && a[i] > a[j] となる組(i, j)の数
//effect: sortされる
int inv_num(inv_num_valtype *origin, int N){
	inv_num_valtype *tmp = (inv_num_valtype *)malloc(sizeof(inv_num_valtype) * N);
	return inv_num_sub(origin, 0, N, tmp);
}

int less_than(int k, int N, int *a, int *b){
	int i;
	b[0] = 0;
	for(i = 0; i < N; i++){
		if(a[i] > k){
			b[i + 1] = b[i] + 1;
		}
		else{
			b[i + 1] = b[i] - 1;
		}
	}
	return inv_num(b, N + 1);
}

signed main(){
	int N, i;
	scanf("%lld", &N);
	int *a = (int *)malloc(sizeof(int) * N);
	int *b = (int *)malloc(sizeof(int) * (N + 1));
	int *c = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%lld", &a[i]);
		c[i] = a[i];
	}
	int res = inv_num(c, N);
	int l = -1, h, r = N;
	while(r - l > 1){
		h = (l + r) / 2;
		if(less_than(c[h], N, a, b) > ((N * (N + 1)) / 2) / 2){
			r = h;
		}
		else{
			l = h;
		}
	}
	printf("%lld\n", c[r]);
	return 0;
}

Measured memory_bytes: 16640
#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cmath>
#define INF 1000000000
#define MOD 1000000007
#define ll long long int
using namespace std;



int main(){
ll N; cin>>N;
vector <ll> path; path.resize(7,0);
ll time = 0;
for(int i=1;i<=5;i++) cin>>path[i];
//pathを書き換える
//cout<<endl;
//cout<<path[1]<<endl;
for(int i=2;i<=5;i++) {
  if(path[i] > path[i-1]) path[i] = path[i-1];
  //cout<<path[i]<<endl;
}

ll big = 1;
for(int i=2;i<=5;i++){
  if(path[i] != path[i-1]) big = i;
}
//cout<<big<<endl;
if(big == 11){
  time = N/path[1];
  if(N % path[1] != 0) time++;
  time += 4;
  cout<<time<<endl;
} else {
  time = N/path[big];
  if(N % path[big] != 0) time++;
  time += 5- (big );
  cout<<time + (big-1)<<endl;
}


  return 0;
}

Measured memory_bytes: 256
//hi
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long int LL;
int main(void){
    int n;
    scanf("%d",&n);
    int i;
    int cur=1;
    LL ans=0;
    for(i=0;i<n;i++){
		int d;
		scanf("%d",&d);
		if(d==cur){
			cur++;
		}else{
			ans+=d/cur;
			if(d%cur==0) ans--;
			if(cur==1) cur++;
		}
	}
	printf("%lld\n",ans);
    return 0;
}


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


int main(){ 
    int n;
    cin>>n;
    int a=0,w=0,t=0,r=0;

    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s=="AC")a++;
        else if(s=="WA")w++;
        else if(s=="TLE")t++;
        else r++;
    }
    
    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<w<<endl;
    cout<<"TLE x "<<t<<endl;
    cout<<"RE x "<<r<<endl;
 
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
#define le 1000000007;
int main(){
  while(1==1){
  int n;
  cin >> n;
  if(n==0)break;
  long long int sum=0;
  vector<int> v(n,0);
  for(int i=0;i<n;i++){
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  for(int i=1;i<n-1;i++){
    sum+=v[i];
  }
  cout << sum/(n-2) << endl;
  }
  return 0;
}

Measured memory_bytes: 3008
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

//===
template<class T>
struct Edge {
    int src, to;
    T cost;

    Edge (int to, T cost):
        src(-1), to(to), cost(cost) {};
    Edge (int src, int to, T cost):
        src(src), to(to), cost(cost) {};

    operator int() const {
        return to;
    };
};

template <class T>
using WeightedGraph = vector<vector<Edge<T>>>;
using UnWeightedGraph = vector<vector<int> >;
//===

//===
// require graph/basic.cpp
// #include <limits>
// #include <queue>
// if s->u path is nothing, min_cost[u] = numeric_limits<T>::max()
// time:O((V+E) log V)
template<class T>
vector<T> dijkstra(WeightedGraph<T> &g, int s) {
    const T INF = numeric_limits<T>::max();
    using P = pair<T, int>;

    vector<T> min_cost(g.size(), INF);
    //vector<T> restore(g.size(), -1);
    priority_queue<P, vector<P>, greater<P> > que;
    que.emplace(0, s);

    while (!que.empty()) {
        T cost = que.top().first;
        int pos = que.top().second;
        que.pop();

        if (min_cost[pos] != INF) continue;
        min_cost[pos] = cost;
        for (Edge<T> e:g[pos]) {
            if (min_cost[e.to] <= cost + e.cost) continue;
            que.emplace(cost + e.cost, e.to);
            //restore[npos] = pos;
        }
    }

    return min_cost;
};
//===

WeightedGraph<llong> g;
vector<vector<llong>> mins;
vector<llong> cnt;
llong n, x, y;

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

    cnt.resize(n + 1, 0);
    g.resize(n + 1);
    mins.resize(n + 1);

    for (int i = 1; i < n; i++) {
        g[i].emplace_back(i + 1, 1);
        g[i + 1].emplace_back(i, 1);
    }
    g[x].emplace_back(y, 1);
    g[y].emplace_back(x, 1);

    for (int i = 1; i <= n; i++) {
        mins[i] = dijkstra(g, i);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cnt[mins[i][j]]++;
        }
    }

    for (int i = 1; i < n; i++) {
        cout << cnt[i] / 2 << endl;
    }

    return 0;
}


Measured memory_bytes: 31744
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int A, B; cin >> A >> B;
    if((A * B) % 2 == 1){
        cout << "Yes";
    }else{
        cout << "No";
    }
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 256
#include <cstdio>

int n;
int A[200000];
int L[100001];
int R[100001];

long int merge(int l, int r, int m){
    int i;
    for(i=0;i<m-l;i++)L[i] = A[l+i];
    for(i=0;i<r-m;i++)R[i] = A[m+i];
    L[m-l] = 1000000001;
    R[r-m] = 1000000001;
    int idL = 0, idR = 0;
    long int cnt = 0;
    for(i=l;i<r;i++){
        if(L[idL]<=R[idR]){
            A[i] = L[idL];
            idL++;
        }else{
            A[i] = R[idR];
            idR++;
            cnt+=m-l-idL;
        }
    }
    return cnt;
}

long int mergeSort(int l, int r){
    if(r-l==1)return 0;
    int m = (l+r)/2;
    long int cnt = 0;
    cnt += mergeSort(l,m);
    cnt += mergeSort(m,r);
    cnt += merge(l,r,m);
    return cnt;
}

int main(){
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",A+i);
    }
    printf("%ld\n",mergeSort(0,n));
    return 0;
}



Measured memory_bytes: 4240