akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
 
//#define int long long
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define reps(i,n) for(ll i=0;i<=n;i++)
#define PI 3.14159265358979323846264338327950L

ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
 
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    ios_base::sync_with_stdio(false);
    ll h,n;
    cin >> h >> n;
    vector<ll> a(n,0);
    rep(i,n){
        cin >> a[i];
        h -= a[i];
        if(h<=0){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3932
def main():
    n=int(input())
    s=input()
    r=[]
    g=[]
    b=[]
    rdict={}
    gdict={}
    bdict={}
    ans=0
    for i in range(n):
        if s[i]=='R':
            r.append(i)
            rdict[2*i]=2*i
        if s[i]=='G':
            g.append(i)
            gdict[2*i]=2*i
        if s[i]=='B':
            b.append(i)
            bdict[2*i]=2*i
    ans=len(r)*len(g)*len(b)
    for i in r:
        for j in g:
            if i+j in bdict:
                ans-=1
    for i in g:
        for j in b:
            if i+j in rdict:
                ans-=1
    for i in b:
        for j in r:
            if i+j in gdict:
                ans-=1
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9564
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		int odd = 0;
		int cnt2 = 0;
		int cnt4 = 0;
		for(int i = 1; i <= n; i++) {
			int x;
			scanf("%d", &x);
			if(x & 1) odd++;
			else {
				if(x % 4 == 0) cnt4++;
				else cnt2++;
			}
		}
		if(odd > cnt4 + 1) printf("No\n");
		else {
			if(odd <= cnt4) printf("Yes\n");
			else if(odd == cnt4 + 1) {
				if(cnt2 > 0) printf("No\n");
				else printf("Yes\n");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int lli;
#define optimize ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define pii pair<int,int>
#define mii map<int,int>
#define F first
#define S second
#define forn(i,n) for(int i = 0; i<n; i++)
#define forab(i,a,b) for(int i = a; i<b; i++)
#define forll(i,a,b) for(lli i = a; i<b; i++)
#define mp make_pair
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define debug(x) cout<<#x<<" : "<<x<<endl
#define all(x) x.begin(),x.end()
#define printv(v) for(auto it : v) cout<<it<<" ";cout<<endl;
#define prec(n) fixed<<setprecision(n)
const lli mod = 1000000007;
const int mod2 = 998244353;
const int N = 1e5;


template <typename T>
T power(T base, T exp)
{
    T res = 1;
    while(exp > 0)
    {
        if(exp & 1)
        	res=(res%mod * base%mod)%mod;
        
        base = (base%mod * base%mod)%mod;
        exp >>= 1;
    }
    return res;
}


int main()
{
	optimize

	#ifndef ONLINE_JUDGE
	freopen("inputf.in", "r", stdin);
	freopen("outputf.in", "w", stdout);
	#endif

	lli n;
	cin>>n;

	if(n<2)
		cout<<0<<endl;
	else
		cout<<(power(10LL, n)+power(8LL, n)-power(9LL, n)-power(9LL, n)+mod+mod)%mod<<endl;


	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes                \
    cout << "Yes" << endl; \
    return 0;
#define No                \
    cout << "No" << endl; \
    return 0;
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;

template <typename T>
void print(const T &v);

int N, M, Q;
vector<vector<int>> pt;

void dps(int depth, vector<int> v)
{
    if (depth == N)
    {
        pt.push_back(v);
        return;
    }
    for (int i = v[v.size() - 1]; i <= M; i++)
    {
        vector<int> cp = v;
        cp.push_back(i);
        dps(depth + 1, cp);
    }
    return;
}

int main()
{
    cin >> N >> M >> Q;
    vector<int> a(Q), b(Q), c(Q), d(Q);
    rep(i, Q) cin >> a[i] >> b[i] >> c[i] >> d[i];
    for (int i = 1; i <= M; i++)
    {
        vector<int> n;
        n.push_back(i);
        dps(1, n);
    }
    int ans = 0;
    for (int i = 0; i < pt.size(); i++)
    {
        int total = 0;
        for (int j = 0; j < Q; j++)
        {
            if (pt[i][b[j] - 1] - pt[i][a[j] - 1] == c[j])
            {
                total += d[j];
            }
        }
        ans = max(ans, total);
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 9772
// #include <bits/stdc++.h>
#include <iostream> // cin, cout, string
#include <algorithm> // sort, min, max
#include <vector>
#include <utility> // pair, swap
#include <functional>
#include <iomanip> // setprecision
#include <map>
#include <set> // multiset
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <stack>
#include <queue> // priority_queue
#include <deque>
#include <bitset>
#include <complex>

using namespace std;

// #define int long long

using ll = long long;
using ld = long double;

// template<class T1, class T2> using P = pair<T1, T2>;
template<class T> using vec = vector<T>;
template<typename T> using func = function<T>;

using pii = pair<int, int>;
using ppi = pair<pii, int>;
using pip = pair<int, pii>;
using ppp = pair<pii, pii>;

using vi = vec<int>;
using vvi = vec<vi>; // Graph
using vp = vec<pii>;

constexpr int IINF =  0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL;
// constexpr int INF = sizeof(int) == sizeof(long long) ? LINF : IINF;
constexpr ll MOD = 1e9+7;

#define for_(i, a, b) for(int i = (a);i < (b);++i)
#define rfor_(i, a, b) for(int i = (b)-1;i >= (a);--i)

#define rep(i, n) for_(i, 0, n)
#define rrep(i, n) rfor_(i, 0, n)

#define pb push_back
#define mp make_pair
#define mt make_tuple
// eb(*,*) = pb(mp(*,*))
#define eb emplace_back
#define ft first
#define sd second

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)(a).size()
#define rev(a) reverse(all(a))
// #define sum(...) accumulate(range(__VA_ARGS__), 0LL)

#define endl '\n'
#define dec(n) fixed << setprecision(n)
#define zfl(n)  setfill(‘0’) << setw(n)
#define debug(x) cerr << #x << ": " << (x) << endl

template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

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 (b < a) { a = b; return true; } return false; }

template<typename T> istream &operator>>(istream &is, vector<T> &v) { for(auto&& x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for(int i=0; i<(int)v.size(); ++i) cout << v[i] << ( i+1 != (int)v.size() ? " " : "" ); return os; }

template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { os << p.first << " " << p.second; return os; }

const int limit = 100007;

ll r, D, x;

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

  cin >> r >> D >> x;
  rep(i, 10) {
    x = r*x - D;
    cout << x << endl;
  }

  return 0;
}


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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 200007 , __ = 533333 , mo = 924844033 , gmo = 5 , igmo = 554906420;

int to[__],ne[__],he[_],ecnt=1;
inline void adde(int a,int b){to[++ecnt]=b,ne[ecnt]=he[a],he[a]=ecnt;}
inline void addde(int a,int b){adde(a,b),adde(b,a);}

inline lint powa(lint a,lint t)
{
	lint b=1;
	while(t){if(t&1)b=b*a%mo;a=a*a%mo,t>>=1;}
	return b;
}

inline lint inva(lint a)
{
	return powa(a,mo-2);
}

lint jc[__],rjc[__];

inline void fuck(int n=__-1)
{
	jc[0]=jc[1]=rjc[0]=1;
	for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i%mo;
	rjc[n]=inva(jc[n]);
	for(int i=n-1;i>=1;i--)rjc[i]=rjc[i+1]*(1ll+i)%mo;
}

int rev[__];

inline int nttmake(int n)
{
	int nn=1,lg=0;
	while(nn<n)nn<<=1,lg++;
	rev[0]=0;
	for(int i=1;i<nn;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
	return nn;
}

inline void ntt(lint a[],int nn,int dir)
{
	for(int i=0;i<nn;i++)if(rev[i]>i)swap(a[i],a[rev[i]]);
	for(int i=1;i<nn;i<<=1)
		for(int j=0,g=powa(dir>0?gmo:igmo,(mo-1)/(i+i));j<nn;j+=i+i)
			for(int k=0,ig=1,x,y;k<i;k++,ig=1ll*ig*g%mo)
				x=a[j+k],y=1ll*ig*a[j+k+i]%mo,a[j+k]=(x+y)%mo,a[j+k+i]=(x-y+mo)%mo;
	if(dir<0)for(int i=0,x=inva(nn);i<nn;i++)a[i]=a[i]*x%mo;
}

int n,sz[_]={0},cnts[_]={0};

void dfs(int x,int ff)
{
	sz[x]=1;
	for(int i=he[x];i;i=ne[i])
	{
		int b=to[i];
		if(b==ff)continue;
		dfs(b,x),sz[x]+=sz[b],cnts[sz[b]]--,cnts[n-sz[b]]--;
	}
}

lint A[__],B[__];

int main()
{
	fuck();
	
	n=ty();
	for(int i=1,a,b;i<n;i++)a=ty(),b=ty(),addde(a,b);

	dfs(1,0),cnts[n]=n;

	int nn=nttmake(n+n+1);
	for(int i=0;i<=n;i++)A[i]=jc[n-i]*(cnts[n-i]+mo)%mo;
	for(int i=n+1;i<nn;i++)A[i]=0;
	for(int i=0;i<=n;i++)B[i]=rjc[i];
	for(int i=n+1;i<nn;i++)B[i]=0;
	ntt(A,nn,1),ntt(B,nn,1);
	for(int i=0;i<nn;i++)A[i]=A[i]*B[i]%mo;
	ntt(A,nn,-1);
	
	for(int i=1;i<=n;i++)printf("%lld\n",A[n-i]*rjc[i]%mo);

	return 0;
}


Measured memory_bytes: 34944
S=input()
L=["KIH","B","R"]
R=[]
for i in range(16):
	T="0"*(4-len(str(bin(i))[2:]))+str(bin(i))[2:]
	st=""
	if T[0]=="1":
		st+="A"
	for i in range(1,4):
		st+=L[i-1]
		if T[i]=="1":
			st+="A"
	R.append(st)
for i in R:
	if i==S:
		print("YES")
		exit()
print("NO")



Measured memory_bytes: 3064
import numpy as np
s = input()

A = []
for i in range(6):
    m = [-(j*10**i%13)%13 for j in range(10)]
    tmp = []
    for j in m:
        tmp.append([[1 if (k-l)%13==j else 0 for k in range(13)] for l in range(13)])
    tmp.append([[1 if (k-l)%13 in m else 0 for k in range(13)] for l in range(13)])
    A.append(tmp)
A = np.array(A)

dp = np.zeros(13, dtype=int)
dp[0] = 1
m = 1
for ind, i in enumerate(reversed(s)):
    i = int(i) if i!='?' else 10
    tmp = np.dot(A[ind%6, i, :, :], dp)
    dp = tmp%(10**9+7)
print(dp[5])


Measured memory_bytes: 14656
module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.container.rbtree;
import std.conv;
import std.stdio;
import std.string;
import std.traits;

struct Input
{
	int n;
    int[2][] d;
}

void parseInput(T)(out Input input, T adapter)
{
	with (input)
	{
		adapter.readf!"%d\n"(n);
        int[2] pair;
        foreach (i; 0..n)
        {
		    adapter.readf!"%d %d\n"(pair[0], pair[1]);
            d ~= pair;
        }
	}
}

struct Output
{
}

auto main2(Input* input)
{
    with (input)
    {
        int zoro = 0;
        foreach (pair; d)
        {
            if (pair[0] == pair[1])
            {
                zoro++;
                if (zoro == 3)
                    return "Yes";
            }
            else
                zoro = 0;
        }

        if (zoro == 3)
            return "Yes";
        else
            return "No";
    }
}

alias retType = ReturnType!main2;
static if (!is(retType == void))
{
	unittest { writeln("begin unittest"); }
	auto _placeholder_ = ReturnType!main2.init;

	unittest // example1
	{
		string example =
`5
1 2
6 6
4 4
3 3
3 2
`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == "Yes");
	}

	unittest // example2
	{
		string example =
`5
1 1
2 2
3 4
5 5
6 6
`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == "No");
	}

	unittest // example3
	{
		string example =
`6
1 1
2 2
3 3
4 4
5 5
6 6
`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(result);
		assert(result == "Yes");
	}

	unittest { writeln("end unittest"); }

	void parseExample(out Input input, string example)
	{
		parseInput(input, new StringAdapter(example));
	}
}

class StdinAdapter
{
	// readf!"%s"は使えない
	// https://issues.dlang.org/show_bug.cgi?id=19820
	uint readf(alias format, A...)(auto ref A args) { return std.stdio.readf!format(args); }
	string readln() { return std.stdio.readln().strip(); }
}

class StringAdapter
{
	import std.format;
	string _s;
	this(string input) { _s = input; }
	uint readf(alias format, A...)(auto ref A args) { return _s.formattedRead!format(args); }
	string readln()
	{
        string ret;
		auto i = _s.countUntil("\n");
		if (i == -1) { ret = _s; _s = ""; }
        else { ret = _s[0..i]; _s = _s[i+1..$]; }
		return ret;
	}
}

void printResult(T)(T result)
{
	static if (isFloatingPoint!T) writefln("%f", result);
	else writeln(result);
}

void main()
{
	Input input = void;
	parseInput(input, new StdinAdapter());
	static if (is(retType == void))
		main2(&input);
	else
	{
		auto result = main2(&input);
		printResult(result);
	}
}


Measured memory_bytes: 2848
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
//using
using namespace std;
using vi = vector <int>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//グローバル変数宣言
 ll a=0,b=0,c=0,e=0,n=0,k=0;


int main(){
   ll m,x;
   cin>>n>>m>>x;
   vi A(n+1);
   rep(i,m)cin>>A[i];
   rep(i,m)if(A[i]<x)b++;else c++;
   print(min(b,c))
}


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

const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  ll res = 0;
  ll mi = 0, mx = 0;
  for (int i=n+1; i>=k; --i) {
    res = (res+(mx-mi)+1) % MOD;
    mi += n+1-i;
    mx += i-1;
  }
  cout << res << endl;
  return 0;
}

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

using namespace std;

int main(){

int N;
cin >> N;
int t[N+1];
long long sum=0;
for(int i=1;i<=N;i++){
    cin >>t[i];
    sum+=t[i];
}
int M;
cin >> M;
int p[M+1];
int x[M+1];
for(int i=1;i<=M;i++){
cin >>p[i]>>x[i];
}

for(int i=1;i<=M;i++){
cout<<sum-t[p[i]]+x[i]<<endl;
}

 return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>

int main() {
	int n, k;
	cin >> n >> k;
	int h[200000];
	rep(i, n) {
		cin >> h[i];
	}
    int tmp;    // 一時格納用
	sort(h, h + n,greater<int>());
	ll c(0);
	rep(i, n - k) {
		c += h[i + k];
	}
	cout << c;
	return 0;
}

Measured memory_bytes: 1024
def bubble_sort(A):
    num = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                num += 1
                
    print(' '.join(list(map(str, A))))
    print(num)

n = input()
A = list(map(int, input().split()))
bubble_sort(A)


Measured memory_bytes: 5604
s = [input() for i in range(3)]
t = {'a':0, 'b':1, 'c':2}
winner = {0:'A', 1:'B', 2:'C'}
index = [0,0,0]
length = [len(s[i]) for i in range(3)]
turn = 0
while True:
  if index[turn] >= length[turn]:
    print(winner[turn])
    exit()
  c = s[turn][index[turn]]
  index[turn] += 1
  turn = t[c]

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

map<ll, ll> prime_factorization(ll n){
	map<ll, ll> ans;
	ll a = 2;
	while(n >= a*a){
		if(n % a == 0){
			ans[a]++;
			n /= a;
		}else{
			a++;
		}
	}
	ans[n]++;
	
	return ans;
}

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	map<ll, ll> pf;
	rep(i, n){
		int in;
		cin >> in;
		a.at(i) = in;
		auto m = prime_factorization(in);
		for(auto p : m){
			if(pf[p.first] < p.second) pf[p.first] = p.second;
		}
	}
	mint all = 1;
	for(auto p : pf){
		mint pf = p.first % mod;
		mint ps = p.second % mod;
		all *= pf.pow(ps.x);
	}

	mint ans = 0;
	rep(i, n){
		ans += all / a.at(i);
	}
	cout << ans.x << endl;
	return 0;
}

Measured memory_bytes: 896
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        r: usize,
        c: usize,
        k: usize,
        rcv: [(Usize1, Usize1, usize); k],
    }

    let mut items = vec![vec![0; c]; r];
    
    for (r, c, v) in rcv {
        items[r][c] = v;
    }

    let mut dp = vec![vec![vec![None; 4]; c]; r];
    dp[0][0][0] = Some(0);

    for i in 0..r {
        for j in 0..c {
            for k in (0..=2).rev() {
                if let Some(a) = dp[i][j][k] {
                    let a_plus = a + items[i][j];
                    if let Some(b) = dp[i][j][k+1].as_mut() {
                        *b = std::cmp::max(*b, a_plus);
                    } else {
                        dp[i][j][k+1] = Some(a_plus);
                    }
                }
            }

            for k in 0..4 {
                if let Some(a) = dp[i][j][k] {
                    if i + 1 < r {
                        if let Some(b) = dp[i+1][j][0].as_mut() {
                            *b = std::cmp::max(*b, a);
                        } else {
                            dp[i+1][j][0] = Some(a);
                        }
                    }
                    if j + 1 < c {
                        if let Some(b) = dp[i][j+1][k].as_mut() {
                            *b = std::cmp::max(*b, a);
                        } else {
                            dp[i][j+1][k] = Some(a);
                        }
                    }
                }
            }
        }
    }

    let mut ans = 0;
    for k in 0..4 {
        if let Some(a) = dp[r-1][c-1][k] {
            ans = std::cmp::max(ans, a);
        }
    }
    println!("{}", ans);
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)

using ll = long long;
using pint = pair<int, int>;
using mint = map<int, int>;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m, d;
    cin >> n >> m >> d;
    double ans;
    if(d == 0){
        ans = 1.0*(m-1)/n;
    }
    else{
        ans = 2.0*(m-1)*(n-d)/n/n;
    }

    cout << setprecision(15) << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define ll long long
#define F first
#define S second
#define FF first.first
#define FS first.second
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e16, MOD=998244353;
     
ll n, q=1, a[N], b[N], c[N], m, x, y, z, X, Y, Z, o, u, h, w, mx, mn, ans=INF, Ans, k;
string s, S;
vector <ll> v[N];
pair<ll, ll> p[N];

int main(){ios_base::sync_with_stdio(false), cin.tie(0);
                    
//    cin>>q;
                        
    while(q--){ans=INF;
        
        cin>>n;
        for (int i=1; i<n; i++){
        	cin>>x;
        	a[x]++;
		}
		for (int i=1; i<=n; i++)cout<<a[i]<<'\n';
	}
	return 0;
}

Measured memory_bytes: 28552
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

char s[201000];
int pA,pZ,n;
int main() {
	scanf("%s",s);
	n=strlen(s);
	rep(i,0,n) if (s[i]=='A') { pA=i; break;}
	rep(i,0,n) if (s[i]=='Z') pZ=i;
	printf("%d\n",pZ-pA+1);
}


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


int main(){
	int n;
	cin >> n;
	int u,v;
	cin >> u >> v;
	u--; v--;
	vector<int> to[100005];
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		a--;b--;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	
	vector<int> dist1(n, INF);
	vector<int> dist2(n, INF);
	queue<int> que1;
	queue<int> que2;
	
	dist1[u] = 0;
	que1.push(u);
	
	while(!que1.empty()) {
		int t = que1.front();
		que1.pop();
		for (auto next : to[t]) {
			if (dist1[next] != INF) continue;
			dist1[next] = dist1[t] + 1;
			que1.push(next);
		}
	}
	
	dist2[v] = 0;
	que2.push(v);
	
	while(!que2.empty()){
		int t = que2.front();
		que2.pop();
		for (auto next : to[t]){
			if (dist2[next] != INF) continue;
			dist2[next] = dist2[t] + 1;
			que2.push(next);
		}
	}
	
	int ans = 0;
	rep(i,n){
		if(dist1[i] < dist2[i]) {
			ans = max(ans, dist2[i]);
		}
	}
	
	cout << max(ans-1, 0) << endl;
	
    return 0;
}

Measured memory_bytes: 6656
s=input()
l=len(s)
dp=[[0]*4 for i in range(l+1)]
dp[0][0]=1
mod=10**9+7
for i in range(l):
    c = s[i]
    dp[i+1][0]=dp[i][0] 
    dp[i+1][1]=dp[i][1] 
    dp[i+1][2]=dp[i][2] 
    dp[i+1][3]=dp[i][3] 
    if c=="A":
        dp[i+1][1]+=dp[i][0]
    if c=="B":
        dp[i+1][2]=dp[i][2]+dp[i][1] 
    if c=="C":
        dp[i+1][3]=dp[i][3]+dp[i][2]
    if c=="?":
        dp[i+1][0] = (3*dp[i][0])%mod
        dp[i+1][1] = (dp[i][0] + 3*dp[i][1]) % mod
        dp[i+1][2] = (dp[i][1] + 3*dp[i][2]) % mod
        dp[i+1][3] = (dp[i][2] + 3*dp[i][3]) % mod
        

print(dp[-1][3]%mod)

Measured memory_bytes: 53868
#include <iostream>
#include <array>
#include <string.h>
using namespace std;
// 202004250319
int maxval( int array[], int n ){
    
    int max = 0; 
    int m = 0; 
    for( int i = 0; i < n; i++ ){
        if( array[i] >= max){
            max = array[i];
            m = i;
        }
    }
    return m;
}

int main(void){
    int n;
    cin >> n;
    int a[n], b[n];
    for( int i = 0; i < n; i++ ){
        cin >> a[i];
    }
    int max = maxval( a, n ) ;
    int max2 = 0 ;
    for( int i = 0; i < n; i++ ){
        if( a[i] > max2 && i != max ) max2 = a[i];
        //if( a[i] > max2 && a[i] != max ) max2 = a[i];
    }
    
    for( int i = 0; i < n; i++ ){
        if( a[max] == a[i]) {
            cout << max2 << endl;
        }else{
            cout << a[max] << endl;
        }
    }
    return 0;
}


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

int main(){
    long long K, A, B;
    cin >> A >> B >> K;

    if(K < A+B) {
        if(A < K)
            cout << "0" << " " << A+B-K << endl;
        else
            cout << A-K << " " << B << endl;   
    } else 
        cout << "0" << " " << "0" << endl;
}


Measured memory_bytes: 256
using System;

namespace ABC168C
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var a = double.Parse(input[0]);
            var b = double.Parse(input[1]);
            var h = int.Parse(input[2]);
            var m = int.Parse(input[3]);

            double aAng = 360 / 12 * h + 0.5 * m;
            double bAng = 360 / 60 * m;
            double ang = Math.Abs((aAng - bAng));
            if (ang >= 180)
            {
                ang = 360 - ang;
            }
            var cos = Math.Cos(ang * Math.PI / 180.0);
            double ans = Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2) - (2 * a * b * cos));
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 18960
#string = ' '.join(list(input() for _ in range(int(input()))))
n,m = map(int,input().split())
a = list(map(int,input().split()))
c = 0
k = (1/(4*m))*(sum(a))
for i in a:
    if i>=k:
        c+=1
if c>=m:
    print("Yes")
else:
    print("No")

    


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

dp = [float("inf")] * n #dpテーブル
#dp[i]:=i番目の足場まで来るのに必要な最小コスト

#初期条件
dp[0]=0
dp[1]=abs(h[1]-h[0])

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

print(dp[n-1])

Measured memory_bytes: 13928
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

int main() {
	char S[200005];
	cin >> S;

	int N = strlen(S);
	char* T = new char[N];

	for (int i = 0; i < N; i++) {
		T[i] = '\0';
	}
	{
		int c = 0;
		for (int i = 0; i < N; i++) {
			if (S[i] == 'C') {
				if (c > 0 && T[c - 1] == 'B') {
					T[c - 1] = 'D';
				}
				else {
					T[c] = 'C';
					c++;
				}
			}
			else {
				T[c] = S[i];
				c++;
			}
		}
	}

	N = strlen(T);
	T[N] = 'B';
	for (int i = 0; i < N; i++) {
		if (T[i] != 'A' && T[i] != 'D') {
			T[i] = 'B';
		}
	}
	N = strlen(T);

	long* table = new long[N + 1];
	table[0] = 0;
	for (int i = 1; i <= N; i++) {
		table[i] = table[i - 1] + i;
	}

	long count = 0;
	{
		int pre = -1;// 左側の壁
		for (int k = 0; k < N; k++) {
			if (T[k] == 'B') {// 壁だったら
				int n = k - 1 - pre;

				if (n > 1) {
					long dcount = 0;
					long dsum = 0;
					for (int i = pre + 1; i < k; i++) {
						if (T[i] == 'D') {
							dcount++;
							dsum += i - pre;
						}
					}
					count += dsum - table[dcount];

				}
				pre = k;
			}
		}
	}

	cout << count << endl;

	return 0;
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long int
// #define ll long long int
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define endl '\n'
#define all(x) x.begin(),x.end()
#define f(i,j,l) for(i=j;i<l;i++)
#define smax(a,b) a=max(a,b)
// #if !defined(ONLINE_JUDGE)
// #include "debugging.h"
// #endif
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
// erase,insert same as normal set

// int const mod = 7340033;
// int const mod = 998244353;
int const mod = 1e9+9;
int power(int a,int b,int m){
    int res = 1;
    while(b){
        if(b&1){
            // res = res*a;
            res = (res*a)%m;
        }
        a=(a*a)%m;
        // a%=m;
        b=b/2;
    }
    return res;
}
// ll mul(ll num1,ll num2,ll m){
//     ll x = (num1*num2)%m;
//     return x;
// }

// ll add(ll num1,ll num2,ll m){
//     ll x = ((num1%m)+(num2%m))%m;
//     return x;
// }

// ll sub(ll num1,ll num2,ll m){
//     ll x = (((num1%m)-(num2%m))%m + m)%m;
//     return x;
// }


int inverse(int x , int m){
    return power(x,m-2,m);
}

int const N = 1e5+5;
int const inf = 2e18;

void solve(){  
    int i,j;
    int l,r,d;
    cin>>l>>r>>d;
    cout << r/d - (l-1)/d<<endl;
}           

int32_t main(){
    IOS;
    int t;
    t = 1;
    // precompute();
    // cin>>t;
    for(int tt=1;tt<=t;tt++){
        solve();
    }
    return 0;
}


/*

*/

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define pii pair<ll,ll>
#define sc(x) scanf("%lld",&x)
long double pi=3.141592653;
 
int main(){
	long double r;
	cin>>r;
	r=2*r;
	r=r*pi;
	std::cout << std::setprecision(12) << r;
	return 0;
}


Measured memory_bytes: 3776
# AOJ GRL_2_B
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B

import sys
from heapq import heappush, heappop

V, E, r = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for _ in range(0, E)]

def solve(V, Edge, r):
    if V <= 1:
        return 0
    q = [[] for _ in range(0, V)]
    for s, t, w in Edge:
        heappush(q[t], (w, s))
    M = [(0, -1) for _ in range(0, V)]
    for t in range(0, V):
        if t != r:
            w, s = heappop(q[t])
            M[t] = (w, s)
    
    used = [False for _ in range(0, V)]
    hist = []
    cycle = []
    for t in range(0, V):
        w, s = M[t]
        if s == -1 or used[t] == True:
            continue
        if used[t] == False:
            used[t] = True
            hist += [t]
            tt = s
            while used[tt] == False:
                used[tt] = True
                hist += [tt]
                w, s = M[tt]
                if s == -1:
                    hist = []
                    break
                tt = s
            if used[tt] == True and s != -1 and 0 < len(hist):
                try:
                    k = hist.index(tt)
                    cycle = hist[k:]
                except:
                    continue
                finally:
                    pass
                break
                
    if len(cycle) == 0:
        return sum(m[0] for m in M)

    parent = min(cycle)
    rn = [0 for _ in range(0, V)]
    k = 0
    for t in range(0, V):
        if k == parent:
            k += 1
        if t in cycle:
            rn[t] = parent
        else:
            rn[t] = k
            k += 1
            
    Vp = V - len(cycle) + 1
    Ep = []
    for s, t, w in Edge:
        if s in cycle:
            if t in cycle:
                continue
            else:
                Ep += [[parent, rn[t], w]]
        else:
            if t in cycle:
                Ep += [[rn[s], parent, w - M[t][0]]]
            else:
                Ep += [[rn[s], rn[t], w]]
    r = rn[r]
    return solve(Vp, Ep, r) + sum(M[t][0] for t in cycle)

print(solve(V, Edge, r))



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

#define SZ(x) (int) x.size()

const int N = 1e5;
int n;
vector <int> G[N + 7];
int rootg;
vector <int> H[N + 7];
int rooth;

int a[N + 7];
vector <int> S[N + 7];

int dfs0(int v, vector <int> (&T)[N + 7]) {
  vector <int> koncowki(SZ(T[v]));
  for (int i = 0; i < SZ(T[v]); ++i) {
    koncowki[i] = dfs0(T[v][i], T);
  }
  
  for (int i = 0; i + 1 < SZ(T[v]); i += 2) {
    int u = koncowki[i];
    int v = koncowki[i + 1];
    S[v].push_back(u);
    S[u].push_back(v);
  }
  
  if (SZ(T[v]) % 2 == 0) return v;
  else return koncowki.back();
}

void dfs1(int v, int k) {
  a[v] = k;
  for (int u : S[v]) {
    if (a[u] == 0) dfs1(u, -k);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    if (x == -1) rootg = i;
    else G[x].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    if (x == -1) rooth = i;
    else H[x].push_back(i);
  }
  
  bool dasie = 1;
  for (int i = 1; i <= n; ++i) if (SZ(G[i]) % 2 != SZ(H[i]) % 2) dasie = 0;
  
  if (!dasie) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  } 
  cout << "POSSIBLE" << endl;
  
  dfs0(rootg, G);
  dfs0(rooth, H);
  
  for (int i = 1; i <= n; ++i) if (SZ(G[i]) % 2 == 0 && a[i] == 0) dfs1(i, 1);
  
  for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
  cout << endl;
  return 0;
}

Measured memory_bytes: 17664
def dist(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5


def dist_high(index1, index2):
    return max(dist(
            xyr[index1][0],
            xyr[index1][1],
            xyr[index2][0],
            xyr[index2][1]) - (xyr[index1][2] + xyr[index2][2]), 0)


def min_value_index(array):
    min_value = float("inf")
    min_index = -1
    for i, v in array:
        if min_value > v:
            min_value = v
            min_index = i
    return min_value, min_index

stx, sty, enx, eny = map(int, input().split())
n = int(input())
xyr = [[stx, sty, 0]] + [list(map(int, input().split())) for x in range(n)] + [[enx, eny, 0]]

nodes = {x: float("inf") for x in range(len(xyr))}
nodes[0] = 0
now = 0

while now != (len(xyr) - 1):
    for i in nodes.keys():
        if i == now:
            continue

        nodes[i] = min(nodes[i], nodes[now] + dist_high(now, i))
    del nodes[now]
    now = min_value_index(nodes.items())[1]
print(nodes[n + 1])


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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<ll, ll> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, k;
	cin >> n >> k;
	vector<int> f(n + 10);
	priority_queue<P> q;
	priority_queue<P, vector<P>, greater<P>> q2;
	rep(i, n) {
		ll t, d;
		cin >> t >> d;
		q.push(P(d, t));
	}
	
	int cnt = 0;
	ll kind = 0, s = 0;
	while (cnt < k) {
		P p = q.top();
		q.pop();
		q2.push(p);
		s += p.first;
		if (f[p.second] == 0) kind++;
		f[p.second]++;
		cnt++;
	}
	
	ll ans = s + kind * kind;
	while (!q.empty()) {
		P p = q.top();
		q.pop();
		if (f[p.second]) continue;
		ll m = -1;
		while (!q2.empty()) {
			P p2 = q2.top();
			q2.pop();
			if (f[p2.second] > 1) {
				f[p2.second]--;
				m = p2.first;
				break;
			}
		}
		if (m == -1) break;
		kind++;
		f[p.second]++;
		s += p.first;
		s -= m;
		ans = max(ans, s + kind * kind);
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 5232
n = int(input())
h_l = list(map(int, input().split()))
m = [0] * n
m[0] = 0
m[1] = abs(h_l[1] - h_l[0])
for i in range(2, n):
    m[i] = min(m[i-1] + abs(h_l[i] - h_l[i-1]), m[i-2] + abs(h_l[i] - h_l[i-2]))
print(m[-1])

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

vector<int> should_check_h(40,0);
vector< vector<int> > should_check_v(41,vector<int>(2,0));
int n,r;

bool check_h_(int l,int h,double c){
    if(l<0){
        if(((l+1)*(l+1)+(h-c)*(h-c))<r*r){
            return false;
        }
    }else if(l>=0){
        if((l*l+(h-c)*(h-c))<r*r){
            return false;
        }
    }
    return true;
}

bool check_v_(int l,int d,int u,double c){
    double m;
    if(d<=c && c<=u){
        m=0;
    }else{
        m=min((u-c)*(u-c),(d-c)*(d-c));
    }
    if((l*l+m)<(r*r)) return false;
    return true;
}

bool check(double c){
    for(int i=0;i<40;i++){
        //cout << "h l:" << i-20 << " h:" << should_check_h.at(i) << " c:" << c << " result:" <<check_h_(i-20,should_check_h.at(i),c) << endl;
        if(!(check_h_(i-20,should_check_h.at(i),c))) return false;
    }
    for(int i=0;i<41;i++){
        if(!(check_v_(i-20,should_check_v.at(i).at(0),should_check_v.at(i).at(1),c))) return false;
    }
    return true;
}

int main(){
    cin >> r >> n;
    while(n!=0 || r!=0){
        for(int i=0;i<40;i++) should_check_h.at(i)=0;
        for(int i=0;i<n;i++){
            vector<int> p(3);
            cin >> p.at(0) >> p.at(1) >> p.at(2);
            for(int j=p.at(0);j<p.at(1);j++){
                should_check_h.at(j+20)=max(should_check_h.at(j+20),p.at(2));
            }
        }
        should_check_v.at(0).at(1)=20;
        should_check_v.at(40).at(1)=20;
        for(int i=1;i<40;i++){
            int l=should_check_h.at(i-1);
            int r_=should_check_h.at(i);
            should_check_v.at(i).at(0)=min(l,r_);
            should_check_v.at(i).at(1)=20;
        }
    /*
    for(int i=0;i<40;i++) cout << should_check_h.at(i) << " ";
    cout << endl;
    for(int i=0;i<41;i++) cout << should_check_v.at(i).at(0) << " " <<should_check_v.at(i).at(1) << "  ";
    cout << endl;
    */

   //二分探索
   //cout << "aaaaaaa" << endl;
   double a,b;a=-r;b=20;
   while((a+0.00001)<b){
       double m=(a+b)/2;
       if(check(m)){
           a=m;
       }else{
           b=m;
       }
   }
   //cout << "ccccccccccc" << endl;
   cout << a+r << endl;
   cin >> r >> n;
   }
}


Measured memory_bytes: 3308
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n,m;
    cin >> n >> m;
    int c[m];
    for(int i=0;i<m;i++) cin >> c[i];
    int dp[n+10]; //n円にする最小枚数
    dp[0]=0;
    for(int i=1;i<=n;i++){
        int a[30];
        for(int i=0;i<30;i++){
            a[i]=100000000;
        }
        for(int j=0;j<m;j++){
            if(i-c[j]>=0) a[j]=dp[i-c[j]]+1;
        }
        sort(a,a+20);
        dp[i] = a[0];
    }
    cout << dp[n] << endl;
}



Measured memory_bytes: 3336
/**

    WARNING
          This Code Sucks
                        Just Like My Life :(

**/
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using orderd_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int n, k, cost[N], dp[N];
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1 ; i <= n ; i++)
        scanf("%d",&cost[i]);
    dp[1] = 0;
    dp[2] = abs(cost[1]-cost[2]);
    for(int i = 3; i <= n ; i++){
        dp[i] = 1e9;
        for(int j = max(1, i - k) ; j <= i - 1 ; j++){
            dp[i] = min(dp[i], dp[j] + abs(cost[i] - cost[j]));
        }
    }
    printf("%d",dp[n]);
    return 0;
}


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

#define ll long long 
#define pi  pair<int,int>
#define ti  tuple<int,int,int>
#define mt  make_tuple
#define mk  make_pair
#define vi  vector<int>
#define vll vector<ll>
#define fastInOut ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pr(a) for(auto x:a) cout<<x<<" ";
#define prmap(m) for(auto x:m) cout<<x.first<<" "<<x.second<<"\n";


ll n,m;
int main() {
    fastInOut
    char c;
 cin>>c;
  if(c=='z')
     cout<<'a';
  else 
     cout<<(++c);

   
  return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;
#define CRP(t, x) const t &x
#define OPL(t, x) bool operator<(CRP(t, x)) const
#define FIL(x, v) memset(x, v, sizeof(x))
#define CLR(x) FIL(x, 0)
#define NE1(x) FIL(x, -1)
#define INF(x) FIL(x, 0x3f)
#ifndef _DEBUG
#define _DEBUG 0
#endif // !_DEBUG
#define IFD if (_DEBUG)
typedef long long ll, i64;
const int N = 1e6 + 60;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d", (n - 1 + k - 2) / (k - 1));
    return 0;
}

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

typedef long long LL;

int n;

void into(){
  scanf("%d",&n);
}

void work(){
}

void outo(){
  printf("%d\n",(n-2)*180);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 3752
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int N, a[200];

int main()
{
    cin >> N;
    for (int i = 0; i<N; ++i)
    {
        cin >> a[i];
    }
    sort(a,a+N,greater<int>());
    int alice = 0;
    int bob = 0;
    for (int i=0; i<N; ++i)
    {
        if(i%2==0) alice += a[i];
        else bob += a[i];
    }

    cout << alice - bob << endl;
    return 0;
}

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

int main() {
 int N,M,X;
 cin >> N >> M;
  for (int i=0; i<M; i++){
  cin >> X;
  N-=X;
  }
 if (N<0){cout << -1 << endl;}
 else {cout << N << endl;}
}



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

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  int a = 10 * g + b;
  
  if(a % 4 == 0) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}


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

int64_t gcd(int64_t a, int64_t b)
{
  int64_t m = std::abs(std::max(a, b)), n = std::abs(std::min(a, b));
  return (n == 0) ? m : gcd(n, m % n);
}

int main()
{
  int64_t N, X;
  std::cin >> N >> X;
  
  std::vector<int64_t> x(N);
  for (int64_t n = 0; n < N; ++n) {
    std::cin >> x[n];
    
    x[n] -= X;
  }
  
  int64_t y = gcd(x[0], x[0]);
  for (int64_t n = 1; n < N; ++n) {
    y = gcd(x[n], y);
  }
  std::cout << y << std::endl;
  
  return 0;
}

Measured memory_bytes: 1024
<?php
list($n) = ints();
$a = ints();
$c = 1;
for ($i = 0; $i < $n - 1; ++$i) {
    if ($a[$i] === $a[$i + 1]) continue;
    if (isset($p)) {
        if (($p === '<' && $a[$i] > $a[$i + 1]) || ($p === '>' && $a[$i] < $a[$i + 1])) {
            ++$c;
            unset($p);
        }
    } else {
        if ($a[$i] < $a[$i + 1]) $p = '<';
        elseif ($a[$i] > $a[$i + 1]) $p = '>';
    }
}
echo $c;
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 27292
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>
       
using namespace std;
       
#define endl '\n'
#define MOD 1000000007
#define INF 1ll<<30
 
// #define MAX 100010
 
#define eps 1e-11
#define bit_max 1ll<<32
#define _USE_MATH_DEFINES


int n,m;
int zz[30];
long long int total_sum = -1;
long long int ans = -1;
void solve(int a,int b,int c)
{
    if(a>n)
        return;
    if(a>total_sum)
    {
        total_sum = a;
        ans = b;
    }
    if(c>=m)
        return;
    solve(a+zz[c],b|(1<<c),c+1);
    solve(a,b,c+1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // #ifndef ONLINE_JUDGE
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
    // #endif
    int a,b;
    cin>>a>>b;
    if(a==b)
        cout<<"Draw"<<endl;
    else if(a==1)
        cout<<"Alice"<<endl;
    else if(b==1)
        cout<<"Bob"<<endl;
    else if(a>b)
        cout<<"Alice"<<endl;
    else
        cout<<"Bob"<<endl;
    return 0;
}

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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main(){
	int a[6];
	int i,j,n;
	for(i=0;i<5;i++){scanf("%d",&a[i]);}
	sort(a,a+5);
	int minim = inf;
	do{
		int time = 0;
		for(i=0;i<5;i++){
			if(time%10 == 0) {
				time += a[i];
			}else{
				int selisih = 10 - time%10;
				time+=selisih;
				time += a[i];
			}
		}
		minim = min(minim, time);
	}while(next_permutation(a,a+5));
	printf("%d\n",minim);
	return 0;
};

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

using namespace std;

#define EPS 1.0e-9

typedef long long ll;
typedef unsigned long long ull;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

#define x first
#define y second

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

	int a, b, c;

	cin >> a >> b >> c;

	if(a == b && b == c)
		cout << "No\n";

	else if(a == b || a == c || b == c)
		cout << "Yes\n";

	else
		cout << "No\n";

    return 0;
}


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

int main() {
  int N, A;
  cin >> N >> A;

  if (N%500 <= A) {
    cout << "Yes" << endl;
  }
  // ここにプログラムを追記
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;


int main() {
  int a;
  cin >> a;
  int f=a/2,g=a/2+a%2;
  cout << f*g << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int n,m,a[101],b,i,j;
	int c[101]={0},d=0;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d",&a[i]);
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			scanf("%d",&b);
			if(b==a[i])c[j]++;
			else c[a[i]]++;
		}
		d=0;
	}
	for(i=1;i<=n;i++)printf("%d\n",c[i]);
	return 0;
}



Measured memory_bytes: 2104