akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    int N,x;
    cin >> N >>x;
    int a[N];
    rep(i,N){
        cin >> a[i];
    }
    sort(a,a+N);
    int sum=0;
    int ans=0;
    rep(i,N){
        sum+=a[i];
        if(x<sum){
            ans=i;
            break;
        }
        else{
            ans=i+1;
        }
    }
    if(x>sum) ans=N-1;
    cout << ans << endl;
}


Measured memory_bytes: 256
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include <random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), n)
#define ub(v,n) upper_bound(v.begin(), v.end(), n)
#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")

template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 998244353;const int MAX = 200020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 1e18;


vector<int>v[3];

bool comp(const P &p1, const P &p2) {
	return p1.first + p1.second < p2.first + p2.second;
}
void solve() {
	int N, K; cin >> N >> K;
	if (2*K>N+1) {
		print(-1); return;
	}
	REP(i, 3)v[i].resize(N);
	REP(i, 3) {
		REP(j, N) {
			v[i][j] = K + i * N + j;
		}
	}
	int d = (N - 1) / 2;
	int l1 = 0, r1 = d, l2 = d + 1, r2 = min(N-1,l2+d-1);
	VREVERSE(v[0]);
	while (l1 < r1) {
		swap(v[0][l1], v[0][r1]);
		l1++, r1--;
	}
	while (l2 < r2) {
		swap(v[0][l2], v[0][r2]);
		l2++, r2--;
	}
	vector<P>ans;
	REP(i, N) {
		ans.push_back({ v[0][i],v[1][i] });
	}
	sort(all(ans), comp);
	REP(i, N) {
		pe(ans[i].first); pe(ans[i].second); print(v[2][i]);
	}
}


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

	solve();
}




Measured memory_bytes: 6256
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	std::string s; cin >> s;
	
	if(std::stoi(s.substr(5, 2)) <= 4) printf("Heisei\n");
	else printf("TBD\n");
	return 0;
}


Measured memory_bytes: 764
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  int t[n], x[n], y[n];
  for (int i = 0; i < n; i++) cin >> t[i] >> x[i] >> y[i];
  if (t[0] != x[0] + y[0]) {
    cout << "No" << endl;
    return 0;
  }
  for (int i = 1; i < n; i++) {
    int diffX = abs(x[i] - x[i - 1]);
    int diffY = abs(y[i] - y[i - 1]);
    int diffT = t[i] - t[i - 1];
    if (diffT < diffX + diffY) {
      cout << "No" << endl;
      return 0;
    } else if (diffT == diffX + diffY) {
      cout << "Yes" << endl;
      return 0;
    } else if ((diffX + diffY - 1) % 2 != 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

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

const string YES = "Yes";
const string NO = "No";

void solve(long long X, long long Y){
    if (Y > X*4 || Y % 2 != 0) {
        cout << NO << endl;
        return;
    }

    int turu = 0;
    int kame = X;
    for (;turu <= X && kame >= 0;++turu, --kame){
        if (turu * 2 + kame * 4 == Y) {
            cout << YES << endl;
            return;
        }
    }
    cout << NO << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    solve(X, Y);
    return 0;
}


Measured memory_bytes: 3768
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arraya = new int[n];
        for (int i = 0; i < n; i++) {
            arraya[i] = sc.nextInt();
        }
        int[] arrayb = new int[n];
        for (int i = 0; i < n; i++) {
            arrayb[i] = sc.nextInt();
        }
        
        int[] suma = new int[n];
        suma[0] = arraya[0];
        for (int i = 1; i < n; i++) {
            suma[i] = suma[i-1] + arraya[i];
        }
        // System.out.println(Arrays.toString(suma));
        
        int[] sumb = new int[n];
        sumb[n-1] = arrayb[n-1];
        for (int i = n-2; i >= 0; i--) {
            sumb[i] = sumb[i+1] + arrayb[i];
        }
        // System.out.println(Arrays.toString(sumb));
        
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, suma[i] + sumb[i]);
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 21844
#include<stdio.h>
int main(){
  int n,m,i,sum=0,count=0;
  scanf("%d%d",&n,&m);
  int a[n+1];
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    sum+=a[i];
  }
  for(i=0;i<n;i++){
    if(4*a[i]*m>=sum)
      count++;
  }
  if(count>=m)
    printf("Yes\n");
  else
    printf("No\n");
  return 0;
}


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

const uint64_t M = 1'000'000'007;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    int n;
    string s;
    cin >> n;
    cin >> s;

    map<char, int> cnt;
    for(int i=0;i<n;i++) cnt[s[i]]++;

    uint64_t ans = 1;
    for(auto x:cnt){
        ans *= x.second+1;
        ans %= M;
    }

    cout << (ans+M-1)%M << endl;
    
    return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int count = 0;
    for (int i = a; i <= b; i++) {
      String _i = new String().valueOf(i);
      if (_i.charAt(0) == _i.charAt(4) && _i.charAt(1) == _i.charAt(3)) {
        count++;
      }
    }
    System.out.println(count);
  }

}


Measured memory_bytes: 30804
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i) sort((i).begin(),(i).end(), greater<int>());
#define YES(i) cout << ((i) ? "Yes" : "No") << endl;
constexpr auto INF = 1000000000;
constexpr auto LLINF = 9223372036854775807;
constexpr auto mod = 1000000007;

ll dp[101][100001];

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

int main() {

	int n, W;
	cin >> n >> W;
	VI w(n);
	vector<ll> v(n);
	FOR(i, n)cin >> w[i] >> v[i];

	FOR(i, 101)FOR(j, 100001)dp[i][j] = mod;
	dp[0][0] = 0;

	FOR(i, n)FOR(j, 100001) {
		if (v[i] <= j)chmin(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
		chmin(dp[i + 1][j], dp[i][j]);
	}

	ll ans = 0;
	FOR(i, 100001) {
		if (dp[n][i] <= W)ans = i;
	}

	cout << ans << endl;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    int ans = INF;
    if(h % 3 == 0) ans = 0;
    else if(w % 3 == 0) ans = 0;
    else{
        for(int i = 1; i <= h - 1; i++){
            int a = i * w;
            int b = (h - i) * (w / 2);
            int c = (h - i) * w - b;
            ans = min(ans, max({a, b, c}) - min({a, b, c}));
            b = (h - i) / 2 * w;
            c = (h - i + 1) / 2 * w;
            ans = min(ans, max({a, b, c}) - min({a, b, c}));
            // cout << a << ' ' << b << ' ' << c << ' ' << ans << endl;
        }
        for(int i = 1; i <= w - 1; i++){
            int a = i * h;
            int b = (w - i) * (h / 2);
            int c = (w - i) * h - b;
            ans = min(ans, max({a, b, c}) - min({a, b, c}));
            b = (w - i) / 2 * h;
            c = (w - i + 1) / 2 * h;
            ans = min(ans, max({a, b, c}) - min({a, b, c}));
            // cout << a << ' ' << b << ' ' << c << ' ' << ans << endl;

        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#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 <cmath>
#include <iomanip>
#include <ctype.h>

using namespace std;
using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

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

ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

bool my_compare(pair<string, int> a, pair<string, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }

    if (a.second != b.second) {
        return a.second > b.second;
    }
    else {
        return true;
    }
}

int main()
{
    int H, W;
    cin >> H >> W;

    vector<vector<char> > A(H, vector<char>(W));
    vector<vector<int> > B(H, vector<int>(W));

    rep(i, H) rep(j, W) cin >> A[i][j];

    rep(i, H) rep(j, W) {
        if (A[i][j] == '.') { B[i][j] = 1; }
        else { B[i][j] = 0; }
    }

    int p;

    deque<int> C,D;

    rep(i, H) {
        p = 1;
        rep(j, W) {
            p = p * B[i][j];
        }
        if (p != 1) { C.push_back(i); }
    }

    rep(j, W) {
        p = 1;
        rep(i, H) {
            p = p * B[i][j];
        }
        if (p != 1) { D.push_back(j); }
    }

    int s = C.size();
    int t = D.size();

    for (int i = 0; i < s; ++i) {
        for (int j = 0; j < t; ++j) {
            cout << A[C[i]][D[j]];
        }
        cout << endl;
    }

}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <ostream& out = cout, class... T> void prints(T&&...){ }
template <ostream& out = cout, class... T> void printd(T&&...){ }
template <ostream& out = cout, class... T> void printb(T&&...){ }
template <ostream& out = cout, class... T> void printArr(T&&...){ }
#endif

void imos2(vector<ll>& buf, int idx, int len, int a0){
    buf[idx] += a0;
    buf[idx + 1] += - (a0 - 1);
    buf[idx + len] += - (a0 + len);
    buf[idx + len + 1] += a0 + len - 1;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<ll> as(n);
    for(int i = 0; i < n; i++){
        cin >> as[i];
    }
    ll acc = 0;
    vector<ll> buf(m + 10);
    for(int i = 1; i < n; i++){
        int f = as[i - 1], t = as[i];
        printd(buf);
        if(f < t){
            acc += t - f;
            imos2(buf, f + 2, t - f - 1, 1);
            // if(f + 1 < t){
            //     buf[f + 2] += 1;
            //     buf[t + 1] += - (t - f);
            //     buf[t + 2] += t - f - 1;
            // }
        }else{
            acc += m + t - f;
            if(!(f == m && t == 1)){
                int t2 = m;
                imos2(buf, f + 2, t2 - f - 1, 1);
                // if(f + 1 < t2){
                //     buf[f + 2] += 1;
                //     buf[t2 + 1] += - (t2 - f);
                //     buf[t2 + 2] += t2 - f - 1;
                // }
                int v = m - f;//, v2 = m + t - f;
                imos2(buf, 1, t, v);
                // if(t == 1){
                //     buf[1] += v;
                //     buf[2] += - 2 * v;
                //     buf[3] += v;
                // }else{
                //     buf[1] += v;
                //     buf[2] += - (v - 1);
                //     buf[t + 1] += - v2;
                //     buf[t + 2] += v2 - 1;
                // }
            }
        }
    }
    printd(buf);
    for(int i = 0; i < 2; i++){
        for(int j = 1; j < m + 9; j++){
            buf[j] += buf[j - 1];
        }
        printd(buf);
    }
    ll maxi = *max_element(buf.begin(), buf.end());
    cout << acc - maxi << '\n';
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
void alert(vector<int> vec){
  for(int i=0; i<vec.size()-1; i++) cout << vec.at(i) << " ";
  cout << vec.at(vec.size()-1) << endl;
}

int main(){
  string S; cin >> S;
  for(int i=0; i<S.size(); i++){
    if(i%2==0){
      if(S.at(i)=='L'){
        cout << "No" << endl;
        return 0;
      }
    }
    else{
      if(S.at(i)=='R'){
        cout << "No"<< endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    int H, W, h, w; cin >> H >> W >> h >> w;
    cout << H * W - h * W - w * (H - h) << "\n";
}


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

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n-1; i >= 0; i--)
#define FOR(i, n, m) for(int i = n; i < (int)(m); i++)
#define PRINT(x) cout << x << endl
#define ALL(v) v.begin(), v.end()
#define INF (ll)1e18
#define PI 3.14159265358979

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

ll MOD = 1000000007;

int main()
{
    ll N;
    cin >> N;
    vector<ll> a(N);
    ll odd = 0;
    REP(i, N) {
        cin >> a[i];
        odd += a[i] % 2;
    }
    if(odd > 0) {
        PRINT("first");
    } else {
        PRINT("second");
    }
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	int n;
	while (cin >> n, n)
	{
		vector<vi> g(27);
		vs v;
		REP(i, n)
		{
			string s; cin >> s;
			while (s.size() < 10) s += 'z' + 1;
			v.push_back(s);
		}
		REP(i, n)REP(j, i)
		{
			string u = v[i], d = v[j];
			int t = 0;
			while (u[t] == d[t]&&t<10) t++;
			if (t == 10) continue;
			int un = u[t] - 'a', dn = d[t] - 'a';
			if (un != dn) g[un].push_back(dn);
		}
		bool f = true;
		if (g[26].size() > 0) f = false;
		REP(i, 26)
		{
			sort(ALL(g[i]));
			g[i].erase(unique(ALL(g[i])), g[i].end());
		}
		vector<bool> vis(26);
		REP(i, 26)
		{
			stack<pii> st;
			st.push(pii(i, 0));
			while (st.size())
			{
				int tmp = st.top().first, cnt = st.top().second;
				st.pop();
				if (cnt>30)
				{
					f = false;
					goto end;
				}
				REP(j, g[tmp].size())
				{
					st.push(pii(g[tmp][j], cnt+1));
				}
			}
		}
	end:;
		puts(f ? "yes" : "no");
	}
	return 0;
}

Measured memory_bytes: 4028
from collections import deque
N, M, A = map(int, input().split())
MP = [[0]*M for i in range(N)]
sx = sy = gx = gy = -1
for i in range(N):
    for j, c in enumerate(input()):
        if c == '#':
            MP[i][j] = 1
        elif c == 'S':
            sx = j; sy = i
        elif c == 'G':
            gx = j; gy = i
U = [[set() for i in range(M)] for j in range(N)]
DD = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(sx, sy, 0, 0, 3)])
for i in range(A+1):
    for j in range(A+1):
        U[sy][sx].add((i, j, 1))
        U[sy][sx].add((i, j, 3))
pp = ((sx, sy), (gx, gy))
while que:
    x, y, a, b, d = que.popleft()

    if (x, y) not in pp:
        d0 = (d-1) % 4
        dx, dy = DD[d0]
        nx = x + dx; ny = y + dy
        if 0 <= nx < M and 0 <= ny < N and MP[ny][nx] == 0:
            if d % 2 == 0:
                if b < A and (a, b+1, d0) not in U[ny][nx]:
                    U[ny][nx].add((a, b+1, d0))
                    que.append((nx, ny, a, b+1, d0))
            else:
                if a < A and (a+1, b, d0) not in U[ny][nx]:
                    U[ny][nx].add((a+1, b, d0))
                    que.append((nx, ny, a+1, b, d0))

        d1 = (d+1) % 4
        dx, dy = DD[d1]
        nx = x + dx; ny = y + dy
        if 0 <= nx < M and 0 <= ny < N and MP[ny][nx] == 0:
            if d % 2 == 0:
                if a < A and (a+1, b, d1) not in U[ny][nx]:
                    U[ny][nx].add((a+1, b, d1))
                    que.append((nx, ny, a+1, b, d1))
            else:
                if b < A and (a, b+1, d1) not in U[ny][nx]:
                    U[ny][nx].add((a, b+1, d1))
                    que.append((nx, ny, a, b+1, d1))

    dx, dy = DD[d]
    nx = x + dx; ny = y + dy
    if 0 <= nx < M and 0 <= ny < N and MP[ny][nx] == 0:
        if (a, b, d) not in U[ny][nx]:
            U[ny][nx].add((a, b, d))
            que.append((nx, ny, a, b, d))

if U[gy][gx]:
    print(min(a+b for a, b, d in U[gy][gx]))
else:
    print(-1)



Measured memory_bytes: 63836
#include <stdio.h>
#define MAX_ 1000000
#define MIN_ -1000000

int main(){
	int K;
	int X;
	scanf("%d",&K);
	scanf("%d",&X);
	
  	int min_bk;
  	int max_bk;
  	
  	min_bk=X-K+1;
  	max_bk=X+K-1;
  	
  	for(int i=min_bk;i<max_bk;i++){
    	printf("%d ",i);
    }
  printf("%d",max_bk);
  
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
int main(){
  int a = 0;
  int c = 0;
  int b = 0;
  int d = 0;
  cin >> a >> c;
  b = max(a,c);
  d = min(a,c);
  int e = 0;
  for(int i = 0;i <= b - 1;i++){
    if(i == b - 1){
    cout << d << endl;
    }
    else{
      cout << d;
    }
    e++;
  }
  return 0;
}

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

const int MOD = 1e9+7;
const int MAX = 1e6+10;
const int INF = 0x3fffffff;
bool a[MAX];

int C(int a,int b){
	if(a<b)	return 0;
	else return a/b+C(a/b,b);
}
void init(){
	memset(a,true,sizeof(a));
	a[0]=a[1]=false;
	for(int i=2;i<=MAX;i++){
		if(a[i]){
			for(int j=i+i;j<MAX;j+=i){
				a[j]=false;
			}
		}
	}
}
int main(){
	int n;
	init();
	while(scanf("%d",&n)!=EOF){
		LL sum=1;
		int i=2;
		while(i<=n){
			if(a[i]){
				sum=sum*(LL)(C(n,i)+1)%MOD;
			}
			i++;
		} 
		printf("%lld\n",sum);
	}
	
	return 0;
}

Measured memory_bytes: 1280
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,Z,W = LI()
    a = LI()

    s = abs(W - a[-1])
    if N == 1:
        print(s)
        return

    u = [0] * N
    d = [0] * N

    u[-2] = d[-2] = min_u = max_d = abs(a[-1] - a[-2])
    for i in range(N-3,-1,-1):
        u[i] = max(max_d,abs(a[i]-a[-1]))
        d[i] = min(min_u,abs(a[i]-a[-1]))
        min_u = min(min_u,u[i])
        max_d = max(max_d,d[i])

    print(max(s,max_d))
if __name__ == '__main__':
    main()

Measured memory_bytes: 75396
#include <stdio.h>

int main(void){
    int k,a,b,i;
    scanf("%d",&k);
    scanf("%d%d",&a,&b);
    for(i = a;i <= b;i++){
        if(i%k == 0){
            printf("OK");
            break;
        }else if(i == b){
            printf("NG");
            break;
        }
    }
    return 0;
}

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

int main(){
	string s;
  	cin >> s;
  	
  	int n = s.size();
  	bool ans = true;
  
  	rep(i, n / 2){
    	if(s.substr(i, 1) != s.substr(n-1-i, 1)){
          	ans = false;
        	break;
        }
    }
  
  	rep(i, n / 4){
    	if(s.substr(i, 1) != s.substr(n/2-1-i, 1)){
          	ans = false;
        	break;
        }
    }
  
  	int x = (n + 3) / 2 - 1;
  	for(int i = x; i <= n - x / 2; i++){
    	if(s.substr(i, 1) != s.substr(n-i+x-1, 1)){
          	ans = false;
        	break;
        }
    }
  
  	if(ans) cout << "Yes" << endl;
  	else cout << "No" << endl;
}

Measured memory_bytes: 256
def run():
    first_line=input()
    second_line=input()
    
    virt_line=first_line+first_line[0:len(second_line)]
    find_flag=False
    for i in range(len(first_line)):
        same=True
        for j in range(len(second_line)):
            
            if second_line[j] != virt_line[i+j]:
                same=False
            
        if same is True:
            find_flag=True
            
    if find_flag:
        print("Yes")
    else:
        print("No")

run()


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

int main(){
  long S;
  cin>>S;
  long ans=0;
  int len=to_string(S).length()-1;
  //cout<<"len:"<<len<<endl;
  for(int i=0;i<(1<<len);i++){
    int dig=1;
    long tmp=S;
    for(int j=0;j<len;j++){
      if(i & (1<<j)){
        //cout<<dig<<endl;
        ans+=tmp%(10*dig);
        tmp/=10*dig;
        //cout<<"ans:"<<ans<<endl;
        dig=1;
      }else{
        dig*=10;
      }
      //cout<<"tmp:"<<tmp<<endl;
    }
    //cout<<"tmp2:"<<tmp<<endl;
    ans+=tmp;
    //cout<<"ans:"<<ans<<endl;
  }
  cout<<ans<<endl;
  
//    int n = 10;
//
//    // {0, 1, ..., n-1} の部分集合の全探索
//    for (int bit = 0; bit < (1<<n); ++bit)
//    {
//        /* bit で表される集合の処理を書く */
//
//
//        /* きちんとできていることを確認してみる */
/*        // bit の表す集合を求める
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // i が bit に入るかどうか
                S.push_back(i);
            }
        }

        // bit の表す集合の出力
        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }*/

  return 0;
}


Measured memory_bytes: 256
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m = na()
ab = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

p, q = ab[0]
p -= 1
q -= 1
uf = UnionFind(n)
uf.unite(p, q)
path = deque()
path.append(p)
path.append(q)
length = 2

while True:
    for i in g[p]:
        if not uf.same(p, i):
            uf.unite(p, i)
            path.appendleft(i)
            p = i
            length += 1
            break
    else:
        break

while True:
    for i in g[q]:
        if not uf.same(q, i):
            uf.unite(q, i)
            path.append(i)
            q = i
            length += 1
            break
    else:
        break

l = list(path)
print(length)
print(*[i + 1 for i in l])

Measured memory_bytes: 50812
/*#include <bits/stdc++.h>
using namespace std;
string ans,s[3055][3055],s1,s2;
int dp[3055][3055],n,m,ma;
int main()
{

    cin>>s1>>s2;
    if (s1.size()>s2.size()) swap(s1,s2);
    n=s1.size();
    m=s2.size();
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            dp[i+1][j+1]=dp[i][j+1];
            s[i+1][j+1]=s[i][j+1];
            if (s1[i]==s2[j])
            {
                    dp[i+1][j+1]++;
                    s[i+1][j+1]=s[i+1][j+1]+s1[i];
            }
            if (dp[i+1][j+1]<=dp[i+1][j])
            {
                s[i+1][j+1]=s[i+1][j];
                dp[i+1][j+1]=dp[i+1][j];
            }
            //cout<<s[i+1][j+1]<<dp[i+1][j+1]<<" ";
        }

    }
    for (int i=0;i<=m;i++)
    {
        if (dp[n][i]>ma)
        {
            ma=dp[n][i];
            ans=s[n][i];
        }
    }
    cout<<ans;
}*/
#include<bits/stdc++.h>
using namespace std;
int dp[1009][1009],m,n,ans,md=1e9+7;
string s[10000];
int main()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
    {
         cin>>s[i];
    }
    memset(dp,0,sizeof(dp));
    dp[1][1]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (i==1 && j==1) continue;
            if (s[i-1][j-1]=='#') continue;
            dp[i][j]=dp[i-1][j]%md+dp[i][j-1]%md;
            dp[i][j]%=md;

        }
    }
    cout<<dp[n][m];
}


Measured memory_bytes: 5376
import itertools
import numpy as np

N,M,X=list(map(int,input().split()))
C=[]
A=[]
for i in range(N):
  s=list(map(int,input().split()))
  C.append(s[0])
  A.append(np.array(s[1:]))
combs=[]
lis = range(N)
for i in range(1,N+1):
  for team in itertools.combinations(lis, i):
    combs.append(team)
lp=0
for comb in combs:
  price=0
  skill=np.array([0 for i in range(M)])
  for i in comb:
    price+=C[i]
    skill+=A[i]
  if min(skill)>=X:
    if lp==0:
      lp=price
    elif lp>price:
      lp=price
if lp==0:
  print(-1)
else:
  print(lp)

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

int a, b, c, ans = -1, now = 0;

int main() {
  cin >> a >> b >> c;
  while(ans == -1) {
    // cout << a + now << " " << now << endl;
    if((now + a) % 60 == 0) {
      if(now % 60 <= c) ans = (now / 60) * 60 + c;
    }
    else {
      if((now % 60 < (now + a) % 60) && now % 60 <= c && c <= (now + a) % 60)
        ans = (now / 60) * 60 + c;
      if((now + a) % 60 < now % 60) {
        if(now % 60 <= c) ans = (now / 60) * 60 + c;
        if(c <= (now + a) % 60) ans = ((now + a) / 60) * 60 + c;
      }
    }
    now += a + b;
    if(now % 60 == 0) break;
  }
  cout << ans << endl;
  return 0;
}



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

int main() {
	for( int i = 1; i <= 9; ++i ) {
		for( int j = 1; j <= 9; ++j ) {
			cout << i << 'x' << j << '=' << (i*j) << endl;
		}
	}
}



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

string day[] = {
	"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
};

int main() {
	int y, m, d, c, h;
	while (cin >> m >> d, m) {
		y = 2004 - (m <= 2);
		m = m + 12 * (m <= 2);
		c = y / 100;
		y %= 100;
		h = d + (26 * (m + 1)) / 10 + y + y / 4 + 5 * c + c / 4;
		cout << day[h % 7] << endl;
	}
	return 0;
}

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

#define ll long long
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)

//library----------------------------------------------

#define NMAX 50
 
ll comb(int n,int k){
    ll ans = 1;
    Rep(i,1,k+1){
        ans*=n-i+1;
        ans/=i;
    }
    return ans;
}

int main(){
    int N,A,B; cin>>N>>A>>B;
    ll v[NMAX];
    rep(i,N) cin>>v[i];
    sort(v,v+N,greater<ll>());

    double ave = 0.0;
    rep(i,A) ave += v[i];
    ave /= A;
    printf("%.10f\n",ave);

    ll ans = 0LL;
    int x=A-1,y=A-1;
    while(v[x-1]==v[x]&&x-1>=0) x--;
    while(v[y]==v[y+1]&&y+1<N) y++;    
    for(int i=A; i<=(x?A:B); i++){
        ans += comb(y-x+1,i-x);
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int N,K;
char s[2000010];
const int MOD = 1e9 + 7;
LL pw[2000010],fac[2000010],pw1[2000010];
LL qpow(LL x,LL y){
    LL re = 1;
    for (; y; y>>=1,x=x*x%MOD)
        if (y&1) re=re*x%MOD;
    return re;
}
LL C(LL n,LL m){
	return fac[n]*qpow(fac[m],MOD-2)%MOD*qpow(fac[n-m],MOD-2)%MOD;
}
int main(){
    scanf("%d%s",&K,s+1);
    N = strlen(s+1);
    fac[0] = 1;
    pw[0] = 1;
    pw1[0] = 1;
    for (int i=1; i<=2000000; i++) {
        fac[i] = fac[i-1]*i%MOD;
        pw[i] = pw[i-1]*26%MOD;
    	pw1[i] = pw1[i-1]*25%MOD;
	}
	LL ans = 0;
	for (int i=N; i<=N+K; i++){
		ans += pw[N+K-i] * C(i-1,N-1)%MOD * pw1[i-N]%MOD;
		ans %= MOD;
	} 
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 51572
def enq(a,x)
  b=a[i=-1] and b=a and until b.frozen?
    x < (a=b)[-1] or return a << x
    x > a[0] or return a.unshift x
    b = a[i = a.bsearch_index{|y| x < (y.frozen? ? y: y[0])}-1]
  end
  a[i+9] or return a.insert i+1, x
  i>0 ? a[i]=[b,x] : enq(a[i+=1].to_a,x)  rescue a[i]=[x,a[i]]
end
def deq(a) r=a.shift; a[0].frozen? or a.unshift *a.shift; r end
def poq(a) r=a.pop; a[-1].frozen? or a.push *a.pop; r end
N,M,*A = $<.read.split.map{|x| x.to_i}
A.sort!
M.times { break if A[-1]==0; enq A, (poq A)/2 }
p A.flatten.inject(0,:+)

Measured memory_bytes: 15976
x,n=map(int,input().split())

if n==0:
  print(x)
  exit()

p=list(map(int,input().split()))

for diff in range(200):
  if x-diff not in p:
    print(x-diff)
    exit()

  if x+diff not in p:
    print(x+diff)
    exit()


Measured memory_bytes: 9084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll LLINF = (ll)1e18;
const ll INTINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
template <class T> void chmin(T& a, const T b){a=min<T>(a,b);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

set<long long> Divisor(long long N) {
    set<long long> ret;
    for (long long i = 1; i*i <= N; ++i) {
        if (N%i == 0) {
            ret.insert(i);
            ret.insert(N / i);
        }
    }
    return ret;
}

int main() {
	ll N; cin >> N;
	ll ans = 0;
	auto d = Divisor(N);
	for(auto e:d){
		if(e==1) continue;
		ll m = e - 1;
		if(N/m==N%m) ans += m;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define all(ppp) ppp.begin(),ppp.end()
#define out(ppp) cout<<(ppp)<<endl
#define out1(ppp) cout<<(ppp) 
#define MAX_CHAR 256

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define pb push_back

typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<vpi> vvpi;

typedef set<pi> spi;

const int INF=INT_MAX;

void solve(){
    int a,b,t;
    cin>>a>>b>>t;
    int ans=t/a;
    out(ans*b);

}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second
// 多倍長
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using boost::rational;
using boost::multiprecision::cpp_int;

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

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

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;



int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n,m;
    cin >> n >> m;
    vector<pint> gaku(n);
    vector<pint> check(m);
    rep(i, n){
        int a,b;
        cin >> a >> b;
        gaku[i] = pint(a, b);
    }
    rep(i, m){
        int c,d;
        cin >> c >> d;
        check[i] = pint(c, d);
    }
    rep(i, n){
        int ans = 0;
        int kyori = INF;
        rep(j, m){
            int now = abs(gaku[i].fs - check[j].fs) + abs(gaku[i].sc - check[j].sc);
            if(now < kyori){
                kyori = now;
                ans = j + 1;
            }
        }
        print(ans);
    }

}

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

int main() {
    int A,B,C;
    int N;

    cin >> A >> B >> C;
    cin >> N;
    
    
    
    int flag =0;
    
    for(int i=0;i<N;i++){
        if((flag == 0)&&(A>=B)){
            B = B*2;
            if(A<B){
                flag = 1;
            }
        }
        else if((flag == 0)&&(A<B)){
            flag = 1;
            C = C*2;
        }
        else if((flag == 1)&&(B>=C)){
            C = C*2;
        }
    }
    if((A<B)&&(B<C)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;

}


Measured memory_bytes: 3636
extern crate core;

use std::fmt;
use std::cmp::{max, min};
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
fn main() {
    let mut money:Vec<usize> = vec![0; 100001];
    let_all!(n: usize, d: usize, x: usize);
    let mut current = x;
    let mut prices = Vec::<Vec<usize>>::with_capacity(d);
    for _ in 0 .. d{
        let res = read_line!(' '; usize);
        prices.push(res);
    }
    let prices = prices;
    for i in 1 .. d{
        for j in 0 .. current + 1 {
            money[j] = j;
        }
        for p in 0 .. n {
            if prices[i][p] > prices[i - 1][p] {
                for j in prices[i - 1][p] .. current + 1 {
                    if money[j - prices[i - 1][p]] + prices[i][p] > money[j] {
                        let new = money[j - prices[i - 1][p]] + prices[i][p];
                        money[j] = new;
                    }
                }
            }
        }
        current = money[current];
    }
    println!("{}", current);
}




Measured memory_bytes: 5028
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N;
int D[200010];
int M;
int T[200010];

int main () {
  cin >> N;
  for (auto i = 0; i < N; ++i) {
    cin >> D[i];
  }
  cin >> M;
  for (auto i = 0; i < M; ++i) {
    cin >> T[i];
  }
  multiset<int> S;
  for (auto i = 0; i < N; ++i) {
    S.insert(D[i]);
  }
  for (auto i = 0; i < M; ++i) {
    auto it = S.find(T[i]);
    if (it == S.end()) {
      cout << "NO" << endl;
      return 0;
    } else {
      S.erase(it);
    }
  }
  cout << "YES" << endl;
}


Measured memory_bytes: 11136
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,j) for(int i=0;i<(j);++i)
#define reps(i,j,k) for(int i=j;i<k;++i)
int n,m,s,d;
char stage[50][20];
int check(){
    int now = m;
    rep(i,d){
        reps(j,1,n-1){
            if(stage[i][j-1] == '1' && stage[i][j] == '1')return 1;
        }
    }
    rep(i,d){
        if(now < n-1 && stage[i][now] == '1')now++;
        else if(now >= 1&&stage[i][now-1] == '1')now--;
    }
    if(now == s)return 0;
}
int main(){
    while(scanf("%d",&n),n){
        scanf("%d%d%d",&m,&s,&d);
        m--,s--;
        rep(i,d)scanf("%s",stage[i]);
        if(check()==0){
            puts("0");
            goto exit;
        }
            rep(i,d){
                rep(j,n-1){
                    if(stage[i][j]=='0'){
                        stage[i][j]='1';
                        if(check()==0){
                            printf("%d %d\n",i+1,j+1);
                            goto exit;
                        }
                        stage[i][j]='0';
                    }
                }
            }
            puts("1");
        exit:;
        memset(stage,0,sizeof(stage));
    }
    return 0;
}

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

int main() {
	int N;
	cin >> N;
	vector<int> a(N);
	for (int& i : a) cin >> i;
	if (is_sorted(a.begin(), a.end())) cout << 0;
	else {
		vector<int> tmp1 = a;
		sort(tmp1.begin(), tmp1.end());
		int tmp2 = 0;
		for (int i = 0; i < N; ++i) {
			if (a[i] != tmp1[i]) ++tmp2;
		}
		int i, Q;
		cin >> Q;
		for (i = 0; i < Q; ++i) {
			int x, y;
			cin >> x >> y;
			int tmp3 = 0;
			if (a[x - 1] == tmp1[x - 1]) --tmp3;
			if (a[y - 1] == tmp1[y - 1]) --tmp3;
			swap(a[x - 1], a[y - 1]);
			if (a[x - 1] == tmp1[x - 1]) ++tmp3;
			if (a[y - 1] == tmp1[y - 1]) ++tmp3;
			tmp2 -= tmp3;
			if (tmp2 == 0) break;
		}
		if (i == Q) cout << -1;
		else cout << i + 1;
	}
	cout << endl;
}


Measured memory_bytes: 5272
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 16, mo = 1e9+7;
int n,m,f[N][1<<15|3],to[N],cnt[1<<15|3],mi[N],S[15000000],len;
void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
int main() {
	read(n);read(m);mi[0]=1;rep(i,1,n)mi[i]=2LL*mi[i-1]%mo;
	while(m--){int x,y;read(x);read(y);to[x]|=1<<y-1;}
	f[0][0]=1;int all=(1<<n)-1;rep(i,1,all)cnt[i]=cnt[i>>1]+(i&1);
	rep(s,0,all)for(int s1=all^s;s1;s1=(s1-1)&(all^s)){
		if((s1&3)==3)continue;
		int xs=1;rep(i,1,n)if(s>>i-1&1)xs=1LL*xs*(mi[cnt[to[i]&s1]]-1)%mo;
		rep(i,1,n)if(!(s>>i-1&1)&&!(s1>>i-1&1))xs=1LL*xs*mi[cnt[to[i]&s1]]%mo;
		len++;S[len]=xs;
	}
	rep(d,0,n-1){
		len=0;
		rep(s,0,all)for(register int s1=all^s;s1;s1=(s1-1)&(all^s)){
			if((s1&3)==3)continue;
			len++;add(f[d+1][s|s1],1LL*S[len]*f[d][s]%mo);
		}
	}
	ll res=0;rep(d,0,n)res+=f[d][all];cout<<(res%mo+mo)%mo;
	return 0;
}


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

int main() {
    int n, m; cin >> n >> m;
    vector<string> data(n);
    for (int i = 0; i < n; i++) cin >> data[i];

    mcf_graph<int,int> graph(n * m + 2);
    int s = n * m, t = s + 1;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (data[i][j] == '#') continue;

            int id = i * m + j;
            int cost = (n - 1) - i + (m - 1) - j;
            graph.add_edge(id, t, 1, cost);

            if (data[i][j] == 'o') {
                graph.add_edge(s, id, 1, 0);
                ans += cost;
            }
            if (i + 1 < n && data[i+1][j] != '#') {
                int idd = (i + 1) * m + j;
                graph.add_edge(id, idd, 1000, 0);
            }
            if (j + 1 < m && data[i][j+1] != '#') {
                int idd = i * m + (j + 1);
                graph.add_edge(id, idd, 1000, 0);
            }
        }
    }

    cout << ans - graph.flow(s, t).second << endl;
    return 0;
}

Measured memory_bytes: 4152