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


long long cache[100005];

long long jump(int *a, int n, int k, int i) {
    if (i >= n) {
        return 2e9;
    }

    if (i == n-1) {
        return 0;
    }

    if (cache[i] != -1) {
        return cache[i];
    }

    long long minCost = 2e9;
    for (int m = 1; m <= k && i + m < n; m++) {
        minCost = min(minCost, jump(a, n, k, i+m) + abs(a[i] - a[i+m]));
    }

    cache[i] = minCost;
    return minCost;
}

int main() {
    int n, k;
    cin>>n>>k;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }

    for (int i = 0; i <= n; i++) cache[i] = -1;
    cout<<jump(a, n, k, 0)<<endl;
}



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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[505];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    ll sum = 0;
    REP(i, N) {
        cin >> A[i];
        sum += A[i];
    }

    vector<ll> v;
    for (ll i = 1; i * i <= sum; ++i) {
        if (sum % i != 0)
            continue;
        v.push_back(i);
        v.push_back(sum / i);
    }

    ll ans = 1;
    REP(i, v.size()) {
        vector<ll> u;
        ll s = 0;
        REP(j, N) {
            ll m = A[j] % v[i];
            u.push_back(m);
            s += (v[i] - m);
        }
        sort(u.begin(), u.end());
        ll t = 0;
        REP(j, N) {
            t += u[j];
            s -= (v[i] - u[j]);
            if (t == s) {
                if (t <= K)
                    ans = std::max(ans, v[i]);
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b + c || b == a + c || c == a + b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

int main() {
  int N; cin >> N;
  vector<int> a(N+1), b(N);
  rep(i, N+1) cin >> a[i];
  rep(i, N) cin >> b[i];
  
  long long ans = 0;
  rep(i, N) {
    if(b[i] <= a[i]) {
      ans += b[i];
      continue;
    } else if(b[i] <= a[i]+a[i+1]) {
      ans += b[i];
      a[i+1] -= b[i]-a[i];
      continue;
    } else {
      ans += a[i]+a[i+1];
      a[i+1] = 0;
    }
  }
  
  cout << ans << endl;
  

}

Measured memory_bytes: 1024
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct edge {
	int x, y, tp;
	edge() : x(-1), y(-1), tp(-1) {};
	edge(int x_, int y_, int tp_) : x(x_), y(y_), tp(tp_) {};
};
int main() {
	int N, D1, D2;
	cin >> N >> D1 >> D2;
	vector<vector<vector<edge> > > g(2 * N, vector<vector<edge> >(2 * N));
	for (int i = -2 * N; i <= 2 * N; ++i) {
		for (int j = -2 * N; j <= 2 * N; ++j) {
			int tp = -1;
			if (i * i + j * j == D1) tp = 0;
			if (i * i + j * j == D2) tp = 1;
			if (tp != -1) {
				for (int k = 0; k < 2 * N; ++k) {
					for (int l = 0; l < 2 * N; ++l) {
						if (0 <= k + i && k + i < 2 * N && 0 <= l + j && l + j < 2 * N) {
							g[k][l].push_back(edge(k + i, l + j, tp));
						}
					}
				}
			}
		}
	}
	vector<vector<int> > col(2 * N, vector<int>(2 * N));
	for (int i = 0; i < 2; ++i) {
		vector<vector<int> > dist(2 * N, vector<int>(2 * N, -1));
		for (int j = 0; j < 2 * N; ++j) {
			for (int k = 0; k < 2 * N; ++k) {
				if (dist[j][k] == -1) {
					dist[j][k] = 0;
					int c0 = 1, c1 = 0;
					queue<pair<int, int> > que; que.push(make_pair(j, k));
					vector<pair<int, int> > lis;
					while (!que.empty()) {
						pair<int, int> u = que.front(); que.pop();
						lis.push_back(u);
						for (edge e : g[u.first][u.second]) {
							if (e.tp == i && dist[e.x][e.y] == -1) {
								dist[e.x][e.y] = dist[u.first][u.second] ^ 1;
								que.push(make_pair(e.x, e.y));
								if (dist[e.x][e.y] == 0) ++c0;
								else ++c1;
							}
						}
					}
					for (pair<int, int> l : lis) {
						if ((dist[l.first][l.second] == 1) ^ (c0 < c1)) {
							col[l.first][l.second] |= 1 << i;
						}
					}
				}
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < 2 * N; ++i) {
		for (int j = 0; j < 2 * N; ++j) {
			if (col[i][j] == 0 && cnt++ < N * N) {
				cout << i << ' ' << j << '\n';
			}
		}
	}
	return 0;
}

Measured memory_bytes: 170956
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

using namespace std;

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

	int N;
	cin >> N;

	cout << N / 3;

	return 0;
}

Measured memory_bytes: 3644
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <ctime>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

#define delete(a,n) a.erase(remove(all(a),n),a.end())
template<typename T, typename S> vector<T>& operator<<(vector<T>& a, S b) { a.push_back(b); return a; }
template<typename T> void operator>>(vector<T>& a, int b) {while(b--)if(!a.empty())a.pop_back();}
bool isprime(int n){ if(n<2)return false;  for(int i=2;i*i<=n;i++)if(n%i==0)return false;  return true;} 
ll b_pow(ll x,ll n){return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;}
string itos(int n){stringstream ss;ss << n;return ss.str();}

long long in(){
	long long n;
	scanf("%lld",&n);
	return n;
}

int A[201] , B[201] , C[201];

int T[201];
int dp[201][201] = {};
int N,M;

int dfs(int pos,int prev){
	if( pos == N ) return 0;
	if( dp[pos][prev] != -1 ) return dp[pos][prev];
	int ans = 0;
	for(int i = 0 ; i < M ; i++){
		if( A[i] <= T[pos] && T[pos] <= B[i] ){
			ans = max( ans , dfs(pos+1,C[i]) + abs(C[i]-prev)  );
		}
	}
	return dp[pos][prev] = ans;
}
//ok
int main(){
	memset(dp,-1,sizeof(dp));
	//ios_base::sync_with_stdio(false);
	cin >> N >> M;
	for(int i = 0 ; i < N ; i++){
		cin >> T[i];
	}
	for(int i = 0 ; i < M ; i++){
		cin >> A[i] >> B[i] >> C[i];
	}
	int ans = 0;
	for(int i = 0 ; i < M ; i++){
		if( A[i] <= T[0] && T[0] <= B[i] ){
			ans = max( ans , dfs(1,C[i]) );
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1344
#include <cstdio>
#include <algorithm>
#include <vector>
static const int MAXN = 1e5 + 3;

int n, a[MAXN];
std::vector<int> e[MAXN];

int ans[MAXN];
void dfs(int u)
{
    //if (e[u].size() == 0) { ans[u] = 0; return; }
    ans[u] = 0;
    std::vector<int> s;
    for (std::vector<int>::iterator i = e[u].begin(); i != e[u].end(); ++i) {
        dfs(*i);
        s.push_back(ans[*i]);
    }
    std::sort(s.begin(), s.end());
    for (int i = 0; i < (int)s.size(); ++i) ans[u] = std::max(ans[u], s[i] + (int)s.size() - i);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        scanf("%d", &a[i]); --a[i];
        e[a[i]].push_back(i);
    }

    dfs(0);
    printf("%d\n", ans[0]);

    return 0;
}


Measured memory_bytes: 14336
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  bool dp[n+10][4][1000] = {};
  dp[0][0][0] = 1;
  rep(i,n){
    rep(j,4){
      rep(k,1000){
        if(dp[i][j][k]){
          dp[i+1][j][k] = 1;
          dp[i+1][j+1][10*k+s[i]-'0'] = (j < 3);
        }
      }
    }
  }
  int ans = 0;
  rep(i,1000) if(dp[n][3][i]) ans ++;
  cout << ans << endl;
}


Measured memory_bytes: 120836
#include <bits/stdc++.h>
using namespace std;
int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  if ( (A+B) < 2*C ){
    cout << A*X + B*Y << endl;			//ABせっと０
  } else if ( A > 2*C && X >= Y ){
    cout << 2*C*X << endl;				//全部ABせっと
  } else if ( B > 2*C && X < Y ){
    cout << 2*C*Y << endl;				//全部ABせっと
  } else if ( X > Y && (A+B) > 2*C ){
    cout << 2*C*Y + A*(X-Y) << endl;	//ABせっと + Aかいたす
  } else{
    cout << 2*C*X + B*(Y-X) << endl;	//ABせっと + Bかいたす
  }
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	ll n;
	cin >> n;
	n--;
	ll s = 26;
	int len = 1;
	while (n >= s) {
		n -= s;
		s *= 26;
		len++;
	}
	string ans = "";
	rep(_, len) ans += 'a';
	while (n) {
		len--;
		char c = n % 26 + 'a';
		ans[len] = c;
		n /= 26;
	}
	cout << ans << '\n';
}

Measured memory_bytes: 3640
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

const pi = math.Pi

var mod int = pow(10, 9) + 7
var Umod uint64 = 1000000007
var ans, cnt int

// x文字目の時に，あまりiである数をカウント
var dp = [13]int{}

func main() {
	var S string
	fmt.Scan(&S)

	dp[0] = 1
	for i := 0; i < len(S); i++ {
		var nextdp = [13]int{}
		t, _ := strconv.Atoi(string(S[i]))
		for j := 0; j < 13; j++ {
			if string(S[i]) == "?" {
				for k := 0; k < 10; k++ {
					nextdp[(j*10+k)%13] += dp[j]
					nextdp[(j*10+k)%13] %= mod

				}
			} else {
				nextdp[(j*10+t)%13] += dp[j]
				nextdp[(j*10+t)%13] %= mod
			}
		}
		dp = nextdp
	}
	fmt.Println(dp[5])

}

/*  ----------------------------------------  */

var reader = bufio.NewScanner(os.Stdin)

func read() string {
	reader.Scan()
	return reader.Text()
}

func lcm(x, y int) int {
	return (x / gcd(x, y)) * y
}

func gcd(x, y int) int {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

var fac [1000000]int
var finv [1000000]int
var inv [1000000]int

func combination_init() {
	fac[0], fac[1] = 1, 1
	finv[0], finv[1] = 1, 1
	inv[1] = 1

	// invは a^(-1) mod p
	// pをaで割ることを考える

	// p/a*(a) + p%a = p
	// p/a*(a) + p%a = 0          (mod p)
	// -p%a = p/a*(a)             (mod p)
	// -p%a *a^(-1)= p/a          (mod p)
	// a^(-1)= p/a * (-p%a)^(-1)  (mod p)
	// a^(-1) =

	for i := 2; i < 1000000; 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
	}
}

func combination(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[y] * finv[x-y] % mod) % mod
	//return fac[x] / (fac[y] * fac[x-y])
}

func permutation(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[x-y] % mod) % mod
	//return fac[x] / fac[x-y]
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }
func ceil(x int) int   { return int(math.Ceil(float64(x))) }

type SortBy [][]int

func (a SortBy) Len() int           { return len(a) }
func (a SortBy) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool { return a[i][0] < a[j][0] }

type PriorityQueue []int

func (h PriorityQueue) Len() int            { return len(h) }
func (h PriorityQueue) Less(i, j int) bool  { return h[i] < h[j] }
func (h PriorityQueue) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PriorityQueue) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PriorityQueue) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


Measured memory_bytes: 5504
#include<cstdio>

using namespace std;

int main(void){
	int n;
	while (1){
		int A = 0, B = 0;
		scanf("%d", &n);
		if (n == 0)return 0;
		for (int i = 0; i < n; i++){
			int a, b;
			scanf("%d %d", &a, &b);
			if (a > b){
				a += b;
				b = 0;
			}
			if (a < b){
				b += a;
				a = 0;
			}
			A += a;
			B += b;
		}
		printf("%d %d\n", A, B);
	}
}

Measured memory_bytes: 1028
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cfloat>
#include <algorithm>
#define PB push_back
#define ll long long
#define ull unsigned long long
#define uint unsigned
#define PIE (3.14159265358979323846)
#define MOD 1000000007;
using namespace std;

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

    int n {};
    cin >> n;
    cout<<n*n*n<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef vector<lint> vlint;

#define inf 1e+9
#define endl "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rep_rev(i, n) for (int i = n-1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()

#define pb push_back
#define eb emplace_back
#define Size(c) (int)(c).size()

#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))

template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

template <class T, class S> inline bool chmax(T &a, S b) {
    if(a < b) {a = b;return 1;} return 0;
}
template <class T, class S> inline bool chmin(T &a, S b) {
    if(a > b) {a = b;return 1;} return 0;
}
template <class T>
void line(vector<T> &x){for (auto&& xi : x) cin >> xi;}

inline void IN(void){ return;}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){ cin >> first; IN(rest...); return;}

#define INT(...) int __VA_ARGS__; IN (__VA_ARGS__)
#define LINT(...) lint __VA_ARGS__; IN (__VA_ARGS__)
#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)

template <class T> void UNIQUE(vector<T> &x) {
    sort(all(x)); x.erase(unique(all(x)), x.end());
}
template <class T> void print_vec(T first, T end){
    for (auto i = first; i < end - 1; i++) cout << *i << " ";
    cout << *(end-1) << endl;
}

template<class... T>
void debug_print(T... args){
    vector<lint> tmp = initializer_list<lint>{args...};
    print_vec(all(tmp));
}
template<class T>
void print(T a){ cout << a << endl;}

vector<string> Yes = {"No", "Yes"};
vector<string> YES = {"NO", "YES"};

int ord(char x){ return (int)(x - 'a');}
char chr(lint x){ return (char)(x + (lint)('a'));}
lint mod = 1e9+7;
// lint mod = 

lint sum(vlint a){lint ret = 0; for(auto&& v:a) ret += v; return ret;}
lint vmini(vlint a, lint &index){
    lint ret = LLONG_MAX;
    rep(i, Size(a)){ if (chmin(ret, a[i])) index = i;}
    return ret;
}
lint vmaxi(vlint a, lint &index){
    lint ret = -LLONG_MAX;
    rep(i, Size(a)){ if (chmax(ret, a[i])) index = i;}
    return ret;
}

lint vmin(vlint a){
    lint ret = LLONG_MAX; for (auto && v : a) chmin(ret, v); return ret;
}
lint vmax(vlint a){
    lint ret = -LLONG_MAX; for (auto && v : a) chmax(ret, v); return ret;
}


int main(){
    INT(n, m);
    vector<vlint> ans;
    vlint check(n+1, 0); int cnt = 1; int diff = n-1;
    while (cnt < cnt + diff){
        ans.pb({cnt, cnt + diff});
        cnt++;
        diff -= 2;
        if (n % 2 == 0 && diff+2 > n/2 && diff <= n/2) diff--;
    }
    rep(i, m){
        print_vec(all(ans[i]));
    }
}


Measured memory_bytes: 9528
# B - Ordinary Number

N = int(input().rstrip())
p_s = input().split()
p = [int(s) for s in p_s]

cnt = 0
for i in range(1,N-1):
    if (p[i-1] < p[i]) and (p[i] < p[i+1]):
        cnt += 1
    elif (p[i+1]) < p[i] and (p[i] < p[i-1]):
        cnt += 1

print(cnt)


Measured memory_bytes: 3060
n = int(input())
ac = 0
wa = 0
tle = 0
re = 0

for i in range(n):
  s = input()
  
  if s == "AC":
    ac += 1
  elif s == "WA":
    wa += 1
  elif s == "TLE":
    tle += 1
  elif s == "RE":
    re += 1
    
print("AC x",ac)
print("WA x",wa)
print("TLE x",tle)
print("RE x",re)

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

int main()
{
  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i, n) {
    cin >> p[i];
  }
  sort(p.begin(), p.end());
  int ans = 0;
  rep(i, k) {
    ans += p[i];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <stdio.h>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
long long int pos(long long int a  ){
    if( a>=0){return a;}
    return -a;
}
long long int dp[100005];
int main(){
    int n,k;
    cin>>n>>k;
    vector <long long int> v;
    for(int i = 0;i<n;i++){
        long long int z;cin>>z;
        v.push_back(z);
    }
    dp[0] = 0;
    dp[1] = pos(v[1]-v[0] );
    for(int i = 2;i<n;i++){
        for(int j = 1;j<=min(k,i);j++ ){
            if(j==1){
                dp[i] = dp[i-1]+pos(v[i]-v[i-1]);
            }
            else{
                dp[i] = min(dp[i], dp[i-j] + pos(v[i]-v[i-j] )  );
            }
        }
    }
    cout<<dp[n-1];
}


Measured memory_bytes: 1908
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
#define DBG(X) cout << #X << "=" << (X) << '\n';
#define SAY(X) cout << (X) << '\n';
#else
#define DBG(X)
#define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

std::string pad(int num)
{
    char buffer[4];
    std::snprintf(buffer, sizeof(buffer), "%03d", num);
    return buffer;
}

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

int solve()
{
    int N, M;

    std::cin >> N >> M;

    vector<int> h = fetch_vec<int>(N);
    vector<vector<int>> conn(N, vector<int>());

    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }

    int counter = 0;

    for (int i = 0; i < N; ++i) {
        if (conn[i].empty()) {
            ++counter;
        } else {
            int maxHeight = 0;
            for (int obs : conn[i]) {
                maxHeight = max(maxHeight, h[obs]);
            }

            if (maxHeight < h[i])
                ++counter;
        }
    }

    return counter;
}

int main()
{
    std::cout << solve() << std::endl;
    //solve();

    return 0;
}

Measured memory_bytes: 8796
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int n; cin >> n;
  LL sum = 0;
  for (int i = 1; i <= n; i ++) {
    if (i % 3 != 0 && i % 5 != 0) {
      sum += i;
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 3636
using System;
    class Program
    {
        static void Main(string[] args)
        {
            string[] xInputMax = Console.ReadLine().Split(' ');
            int xMaxX = int.Parse(xInputMax[0]);
            int xMaxY = int.Parse(xInputMax[1]);

            long xSumX = SumAreaLength(Console.ReadLine(), xMaxX);
            long xSumY = SumAreaLength(Console.ReadLine(), xMaxY);

            long xDivisor = 1000000007;
            Console.WriteLine(((xSumX % xDivisor) * (xSumY % xDivisor)) % xDivisor);
        }

        static long SumAreaLength(string xInputString, int xMaxCount)
        {
            string[] xInput = xInputString.Split(' ');
            long xSum = 0;
            for (int i = 0; i < xMaxCount; ++i)
            {
                xSum += long.Parse(xInput[i]) * (2 * i - xMaxCount + 1);
            }
            return xSum;
        }
    }

Measured memory_bytes: 30940
def mfvinput(i):
    print(i)
    seat[i] = input()
    if seat[i] == 'Vacant':
        exit()

n = int(input())
seat = [None] * n

mfvinput(0), mfvinput(n - 1)
l, r = 0, n
for _ in range(20):
    tmp = (l + r) // 2
    mfvinput(tmp)
    if (tmp % 2 == l % 2) == (seat[tmp] == seat[l]):
        l = tmp
    else:
        r = tmp


Measured memory_bytes: 9604
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

//Main
public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		
			
			int d=sc.nextInt(),t=sc.nextInt(),s=sc.nextInt();
			
			long aa=s*t;
			
			
			
			
			if (aa>=d)
			{
				System.out.println("Yes");
			}
			else
			{
				System.out.println("No");
			}
			
			
			
			
		
		

	}

	static final Random random = new Random();

	static void ruffleSort(int[] a) {
		int n = a.length;//shuffle, then sort 
		for (int i = 0; i < n; i++) {
			int oi = random.nextInt(n), temp = a[oi];
			a[oi] = a[i];
			a[i] = temp;
		}
		Arrays.sort(a);
	}

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

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

		int[] readArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

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

}


Measured memory_bytes: 32936
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while (true) {
			int T = stdIn.nextInt();
			int P = stdIn.nextInt();
			int R = stdIn.nextInt();
			if(T == 0 && P == 0 && R == 0) break;
			Team[] teamData = new Team[T];
			for (int i = 0; i < T; i++) {
				teamData[i] = new Team(i);
			}
			for (int i = 0; i < R; i++) {
				int tID = stdIn.nextInt();
				int pID = stdIn.nextInt();
				int time = stdIn.nextInt();
				String message = stdIn.next();
				if (message.equals("WRONG")) {
					teamData[tID - 1].wdata[pID]++;
				}
				if (message.equals("CORRECT")) {
					teamData[tID - 1].c++;
					teamData[tID - 1].p += teamData[tID - 1].wdata[pID] * 1200
							+ time;
				}
			}
			Arrays.sort(teamData, new MyComparator());
			for (int i = 0; i < T; i++) {
				System.out.println(teamData[i].id + 1 + " " + teamData[i].c
						+ " " + teamData[i].p);
			}
		}
		
	}
}
class MyComparator implements Comparator<Team> {

	
	public int compare(Team o1, Team o2) {
		if(o1.c < o2.c) {
			return 1;
		}
		else if(o1.c > o2.c) {
			return -1;
		}
		else if(o1.p < o2.p) {
			return -1;
		}
		else if(o1.p > o2.p) {
			return 1;
		}
		else if(o1.id < o2.id) {
			return -1;
		}
		else if(o1.id > o2.id) {
			return 1;
		}
		return 0;
		
	}
	
}
class Team {
	public int id;
	public int c;
	public int p;
	public int[] wdata;
	
	public Team(int x) {
		id = x;
		c = 0;
		p = 0;
		wdata = new int[11];
	}
}

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

int main() {
    string s, ans = "NO";
    cin >> s;
    int n = s.size();
    unordered_map<char, int> mp;
    mp['a'] = 0;
    mp['b'] = 0;
    mp['c'] = 0;
    for (int i = 0; i < n; i++) {
        mp[s.at(i)]++;
    }
    if (n == 1) {
        ans = "YES";
    } else if (n == 2) {
        if (s.at(0) != s.at(1)) ans = "YES";
    } else if (n >= 3) {
        int q = n / 3, r = n % 3;
        if (r == 0) {
            if (mp['a'] == q && mp['b'] == q && mp['c'] == q) {
                ans = "YES";
            }
        } else if (r == 1) {
            if ((mp['a']==q+1&&mp['b']==q&&mp['c']==q) || (mp['a']==q&&mp['b']==q+1&&mp['c']==q) || (mp['a']==q&&mp['b']==q&&mp['c']==q+1)) {
                ans = "YES";
            }
        } else {
            if ((mp['a']==q+1&&mp['b']==q+1&&mp['c']==q) || (mp['a']==q+1&&mp['b']==q&&mp['c']==q+1) || (mp['a']==q&&mp['b']==q+1&&mp['c']==q+1)) {
                ans = "YES";
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3708
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  int K, S, cnt=0;
  cin >> K >> S;
  for(int i=0; i<=K; i++){
    for(int j=0; j<=K; j++){
        if(S-i-j >= 0 && S-i-j <= K) cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 3604
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	
	
	string S, T;
	long long int ans = 100000000;
	
	cin >> S;
	cin >> T;
 
	rep(i, S.size()-T.size()+1){
		int tmp = 0;
		rep(j, T.size()){
			if(S[i+j] != T[j]){
				tmp++;
			}
		}
		if(ans > tmp){
			ans = tmp;
		}
	}
 
	cout << ans;
 
	return 0;
}

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

using namespace std;

typedef long long ll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
ll modpow(ll a,ll b){
  ll r=1;
  while(b){
    if(b&1)r=r*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return r;
}

const int MX = 25212521;
ll fact[MX];
ll ifact[MX];

int h,w,k;

int main(){
  scanf("%d%d%d",&h,&w,&k);
  fact[0] = 1;
  FOR(i,1,MX)fact[i] = fact[i-1]*i%MOD;
  ifact[MX-1] = modpow(fact[MX-1], MOD-2);
  FORR(i,1,MX)ifact[i-1] = ifact[i]*i%MOD;
  ll ans = 0;
  FOR(p,max(0,k-w),min(h,k)+1){
    ll X = p;
    ll Y = k-X;
    ll hPx = fact[h] * ifact[h-X] % MOD;
    ll wPy = fact[w] * ifact[w-Y] % MOD;
    ll ifxy = ifact[X] * ifact[Y] % MOD;
    ll val = fact[X+Y+1] * ifxy % MOD;
    val = val * ifact[3] % MOD * (2*X*Y%MOD + 3*k + 6) % MOD;
    val = (val - fact[X+Y]*ifxy%MOD + MOD) % MOD;
    ans += hPx * wPy % MOD * val % MOD;
  }
  ans %= MOD;
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 394240
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, k, res = 0;
int main(void){
    // Your code here!
    cin >> n >> k;
    vector<int> l(n);
    for (int i = 0; i < n; i++)
        cin >> l[i];
    
    sort(l.begin(), l.end(), greater<int>());
    for (int i = 0; i < k; i++)
        res += l[i];
    
    cout << res << endl;
}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define int                     long long int
#define ld                      long double
#define pb                      push_back
#define MOD                     1000000007
#define inf                     3e18
#define vi                      vector<int>
#define vld                     vector<ld>
#define pii                     pair<int,int>
#define mii                     map<int,int>
#define fi                      first
#define se                      second
#define fastIO                  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << " "<< name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}

typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> pbds; 
		//order_of_key (k) : Number of items strictly smaller than k .
		//find_by_order(k) : K-th element in a set (counting from zero) (returns an iterator)           


void inp_out()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	freopen("debug.txt", "w", stderr);
	#endif
}

int32_t main()
{
	fastIO
	inp_out();
	int n; 
	cin >> n; 
	
	int ans = 0, x = 0; 
	for(int a = 1; a < n;  ++ a)
		ans += (n - 1) / a;
	cout << ans; 
	return 0;
}

Measured memory_bytes: 3648
# coding:utf-8

# 入力
N, Q = map(int, input().split(' '))
S = input()
ql = [map(int, input().split(' ')) for _ in range(Q)]

# 累積和の作成
cl = [0, 0]
for i in range(N-1):
    if S[i] + S[i+1] == 'AC':
        cl.append(cl[-1]+1)
    else:
        cl.append(cl[-1])

# クエリに対する出力
for l, r in ql:
    print(cl[r] - cl[l])

Measured memory_bytes: 52036
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) (int)v.size()
#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; 
#define prl cerr<<"called: "<< __LINE__ << endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

const int N = 2020;
const int M = 1e9 + 7;
// long long?

ll fat[N],inv[N];
ll C(int n,int k){
  if(k>n)return 0;
  return mod(fat[n]*mod(inv[k]*inv[n-k],M),M);
}

void init(){
  fat[0] = inv[0] = 1;
  for(int i=1;i<N;i++){
    fat[i] = (1LL*fat[i-1]*i)%M;
  }
  inv[N-1] = exp(fat[N-1],M-2,M);
  for(int i=N-2;i>=0;i--){
    inv[i] = (inv[i+1]*(i+1))%M;
  }
}
int32_t main(){
  fastio;
  init();
  int S;
  cin >> S;
  ll cur=0;
  for(int k=1;k<=S;k++){
    int tem = k*3;
    if(tem > S)break;
    int need = S - tem;
    cur = mod(cur + C(need + k - 1, k-1),M);
  }
  cout << cur << endl;
  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Measured memory_bytes: 3664
#!/usr/bin/env python3
n,*a=map(int, open(0).read().split())
a.sort()
ans = 0
c  = 0
for i in range(n-1):
    c += a[i]
    if c*2 < a[i+1]:
        ans = 0
    else:
        ans += 1
print(ans + 1)


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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int x,y; cin >> x >> y;
	x--; y--;
	cout << x*y;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 256
using System;

class Program
{
    static bool checking(int[] a)
    {
        return (a[0] + a[1] == a[2] || a[1] + a[2] == a[0] || a[2] + a[0] == a[1]);
    }

    static int Main()
    {   
        int[] a = new int[3];
        int inp,n;
        string[] str;
        string result;

        n = int.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            str = (Console.ReadLine()).Split(' ');
            for (int j = 0; j < 3; j++)
            {
                
                inp = int.Parse(str[j]);
                a[j] = inp * inp;
            }

            if (checking(a))
                result = "YES";
            else
                result = "NO";

            Console.WriteLine("{0}", result);

        }

        



        return 0;
    }
}
       

Measured memory_bytes: 5504
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
s = STR()
t = Counter(s)
ans = t['R'] * t['G'] * t['B']
for i in range(n):
    for j in range(i + 1, n):
        k = j + (j - i)
        if k < n and set([s[i], s[j], s[k]]) == set(['R', 'G', 'B']):
            ans -= 1
print(ans)

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

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

    bool flag[4][13] = {false};
    rep(i, n) {
        string s;
        int a;
        cin >> s >> a;
        a--;

        if (s == "S")
            flag[0][a] = true;
        else if (s == "H")
            flag[1][a] = true;
        else if (s == "C")
            flag[2][a] = true;
        else
            flag[3][a] = true;
    }

    rep(i, 4) {
        rep(j, 13) {
            if (!flag[i][j]) {
                if (i == 0)
                    cout << "S ";
                else if (i == 1)
                    cout << "H ";
                else if (i == 2)
                    cout << "C ";
                else
                    cout << "D ";
                cout << j + 1 << endl;
            }
        }
    }

    return 0;
}


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

int main(){
	int n;
	int sum[101][101] = {};
	cin >> n;
	int ma = -1000000000;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			cin >> sum[i][j];
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = i;j <= n;j++){
			for(int k = 1;k <= n;k++){
				for(int l = k;l <= n;l++){
					ma = max(ma,sum[j][l] - sum[i - 1][l] - sum[j][k - 1] + sum[i - 1][k - 1]);
				}
			}
		}
	}
	cout << ma << endl;
	return 0;
}

Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
const int offset=100010;
#define lowb(x) x&-x
int n,a[offset],s[offset*10],bit[offset*10];
void add(int x)
{
	while(x<=2*offset)
	{
		bit[x]++;
		x+=lowb(x);
	}
}
long long query(int x)
{
    long long sum=0;
    while(x>=1)
    {
    	sum+=bit[x];
    	x-=lowb(x);
	}
    return sum;
}
bool check(int x)
{
    for(int i=1;i<=2*offset;i++)
		bit[i]=0;
    s[0]=0;
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+(a[i]>=x?1:-1);
    long long sum=0;
    for(int i=0;i<=n;i++)
	{
        sum+=query(s[i]+offset);
        add(s[i]+offset);
    }
    return sum>=1ll*n*(n+1)/4;
}
int main()
{
    cin>>n;
    int l=0,r=0;
    for(int i=1;i<=n;i++)
	{
        cin>>a[i];
        r=max(r,a[i]);
    }
    while(l<=r)
	{
        int mid=(l+r)/2;
        if(check(mid))
			l=mid+1;
        else
			r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}


Measured memory_bytes: 7168
h, w = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))

c = [[0] * w for i in range(h)]

num = a.pop(0)
color = 1
#print(num)
for i in range(h):
    for j in range(w):
        if num == 0:
            num = a.pop(0)
            color += 1

        c[i][j] = color
        num -= 1
for i in range(h):
    temp = c[i]
    if i % 2 == 1:
        temp = temp[::-1]
    print(*temp)

Measured memory_bytes: 3828
A,B,C,D=map(int,input().split())

L=1
while L:
    if C-B<=0:
        print('Yes')
        break
    elif A-D<=0:
        print('No')
        break
    A-=D
    C-=B

# if C//B+C%B<=A//D+A%D:
#     print('Yes')
# else:
#     print('No')

Measured memory_bytes: 9112
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cstdio>

using ll = long long;

using namespace std;

void max_self(ll& a, ll b) {
    a = max(a, b);
}
void min_self(ll& a, ll b) {
    a = min(a, b);
}

const ll INF = 1e18L + 5;

int main() {
    int n, W;
    scanf("%d%d", &n, &W);
    vector<int> weight(n), value(n);
    for (int i=0; i<n; ++i) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    int sum_value = 0;
    for (int x : value) {
        sum_value += x;
    }
    vector<ll> dp(sum_value + 1, INF); // 0 ... W
    dp[0] = 0;
    // dp[i] - the minimum total weight of items with total value exactly i
    for (int item=0; item<n; ++item) {
        for (int value_already = sum_value - value[item]; value_already >= 0; --value_already) {
            //~ for(int weight_already = 0; weight_already <= W - weight; ++weight_already) {
            min_self(dp[value_already+value[item]], dp[value_already] + weight[item]);
        }
    }
    ll answer = 0;
    for(int i=0; i<=sum_value; ++i) {
        if (dp[i] <= W) {
            answer = max(answer, (ll) i);
        }
        //~ min_self(answer, dp[i]);
    }
    printf("%lld\n", answer);
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
//#include  <iostream>
 using namespace std;
 
#define IOS         ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define FOR(i,a,n)  for(int i = (a); i<(n); ++i) 
#define mp(a , b)   make_pair(a , b)
#define pb(a)       push_back(a)
#define si(n)       scanf("%d" , &n)
#define pi(n)       printf("%d", n )
#define sl(n)       scanf("%lld" ,&n)
#define pl(n)       printf("%lld",n)
#define pin(n)      printf("%d\n", n)
#define pis(n)      printf("%d ", n)
#define pln(n)      printf("%lld\n", n)
#define endl "\n"

typedef long long ll;
 
 

int main(){
     
    IOS;
    
  //  freopen("input.in", "r", stdin);
   // freopen("output.in", "w", stdout);
   
     string s;
     cin>>s;

     int len = s.length();
      
      for(int i=0; i<len/2; i++){

      	if(s[i] != s[len-1-i]){
      	    cout<<"No";
      	     return 0;
      	}
      }

      int l=0, r = (len/2-1);

      while(l<=r){

      	if(s[l] != s[r]){
      		cout<<"No";
      		return 0;
      	}
      	l++;
      	r--;
      }

    cout<<"Yes";



   

  return 0;
    
}


Measured memory_bytes: 256
using System;

namespace ITP1
{
    class Program
    {
        static void Main(string[] args)
        {
            int m, f, r;
            while (true)
            {
                string[] input = Console.ReadLine().Split(' ');
                m = int.Parse(input[0]);
                f = int.Parse(input[1]);
                r = int.Parse(input[2]);

                if (m == -1 & f == -1 & r == -1) break;
                else if(m == -1 | f == -1 )
                {
                    Console.WriteLine("F");
                }
                else if (m+f >= 80)
                {
                    Console.WriteLine("A");
                }
                else if (m+f >= 65)
                {
                    Console.WriteLine("B");
                }
                else if (m+f >= 50)
                {
                    Console.WriteLine("C");
                }
                else if (m+f >= 30)
                {
                    if (r >= 50)
                    {
                        Console.WriteLine("C");
                    }
                    else
                    {
                        Console.WriteLine("D");
                    }
                }
                else
                {
                    Console.WriteLine("F");
                }
            }
        } 

    }
}

Measured memory_bytes: 8828
//
// Created on 2020/08/16.
//


#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
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; }
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;



int main() {
    string s;
    cin>>s;
    int ans = 0;
    bool last = false;
    int temp = 0;
    for (int i = 0; i < 3; ++i) {
        if(s[i] == 'R'){
            if(last){
                temp ++;
            }else{
                last = true;
                temp = 0;
                temp ++;
            }
        }else{
            last = false;
            ans = max(temp,ans);
        }
    }
    ans = max(temp,ans);
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  int N, A;
  cin >> N >> A;
  
  int x;
  x = N - 500 * (N / 500);
  
   if(x <= A){
   	cout << "Yes" << endl;
   }
   else{
	cout <<"No" << endl;
   }
 }

Measured memory_bytes: 256
#include<stdio.h>
int main(){
int A,B,C,D,x,y;
scanf("%d %d %d %d",&A,&B,&C,&D);
		x=(A+D-1)/D;
		y=(C+B-1)/B;
		if(x>=y){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	return 0;
}


Measured memory_bytes: 1616
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50 + 10;
int a[maxn];
int main()
{
  int n , k;
  scanf("%d%d",&n,&k);
  for(int i = 0 ; i < n ; i++) scanf("%d",&a[i]);
  int ans = 0;
  for(int i = 1 ; i <= min(k,n); i++) // 取i个
  {
    for(int j = 0 ; j <= i ; j++) // 左边j个 右边 i-j个
    {
      int sum = 0;
      vector<int>v;
      for(int l = 0 ; l < j ; l ++) v.push_back(a[l]) , sum += a[l];
      for(int l = n - 1 ; l >= n - (i - j); l--) v.push_back(a[l]) , sum += a[l];
      sort(v.begin(),v.end());
      for(int l = 0 ; l < k - i ; l++)
      {
        if(v[l] < 0) sum -= v[l];
      }
      ans = max(ans,sum);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	
	if (s < t) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
flags = [i >=1 for i in H]
flags.append(False)

ans = 0
while any(flags):
    for i in range(N):
        if flags[i] and not flags[i+1]:
            ans += 1
        H[i] = H[i] - 1 if H[i] else 0
    flags = [e >= 1 for e in H]
    flags.append(False)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#define MAX 80001
using namespace std;

class state{
public:
  int n,ans;
  bool f;
};

int main(){
  string str;
  while(cin >> str && str != "0"){
    int an,ans;
    vector<state> v;
    state s;
    an = ans = 0;
    for(int i=0;i<str.size();i++){
      int n = str[i] - '0';
      if(n == 0){
	for(int j=0;j<v.size();j++) v[j].f = (v[j].f + 1) % 2;
	ans += an;
      }
      else{
	s.n = n;
	s.ans = 1 + an;
	s.f = false;
	an = 0;
	v.push_back(s);

	for(int j=v.size()-2;j>=0;j--){
	  if(v[j].f) v[j].n += n;
	  else v[j].n -= n;
	  v[j].f = (v[j].f + 1) % 2;

	  if(v[j].n < 0) v[j].n += 11;
	  else if(v[j].n >= 11) v[j].n -= 11;

	  if(v[j].n == 0){
	    an += v[j].ans;
	    v.erase(v.begin()+j);
	  }
	}
	ans += an;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1116