akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define all(cont) cont.begin(), cont.end()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define fore(i,a,b) for(int i=a,almo5t=b;i<almo5t;++i)
#define SZ(x) ((int)x.size())
#define EPS 1e-9
#define PI acos(-1)
#define MOD 1000000007
#define FIN std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)


using namespace std;
typedef long long int ll;


ll inf = 1e12 + 5;

int main(){
    FIN;
    //freopen("../../input.txt", "r", stdin);freopen("../../output.txt", "w", stdout); 
    int n,w;cin>>n>>w;
    int N = n*1000 + 1;
    ll dp[n+1][N];

    fore(i,0,n+1){
        fore(j,0,N){
            dp[i][j] = inf;
        }
    }
    vector<pair<int,int>> values;
    fore(i,0,n){
        int wi,vi;cin>>wi>>vi;
        values.pb({wi,vi});
    }

    sort(values.begin(),values.end());

    

    fore(i,1,n+1){
        int wi = values[i-1].first;
        int vi = values[i-1].second;
        dp[i-1][0] = 0;
        fore(j,1,N){
            dp[i][j] = min(dp[i-1][max(j-vi,0)]+wi,dp[i-1][j]);
        }
    }

    /*fore(i,0,n+1){
        fore(j,0,N){
            if(dp[i][j] != inf){
                cout<<dp[i][j]<<" ("<<j<<") ";
            }else{
                cout<<"-1 ";
            }

        }cout<<"\n";
    }*/

    ll ans = 0;
    for(int j = N-1; j>=0 ;j--){
        bool posible = false;

        fore(i,0,n+1){
            if(dp[i][j]<=w){
                posible = true;
            }
        }
        if(posible){
            ans = j;
            break;
        }
    }
    cout<<ans;
    return 0;
}

// ============== Notes =============== //
// common bugs
// - remove reader 
// - fastio
// - int overflow (especially intermediate expressionns)
// - array bounds (indices bigger than MAXN?, is MAXN correct?)
// - special cases (n=1, graph not connected?)
// - re-initialize efficiently between test cases


Measured memory_bytes: 82552
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1000000007
typedef long long ll;
const int INF32 = 2147483647;
const ll INF64  = 9223372036854775807;
using namespace std;
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;
}

using P = pair<int, int>;
vector<string> maze;
vector<vector<int>> cnt;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
queue<P> que;

void bfs(int height, int width) {
    //   | height   -->
    //   v         width
    //
    // 注意事項：
    // maze と cnt は resize()すること
    // cnt の初期値は -1 に設定すること
    // que に始点を push()すること

    while (!que.empty()) {
        auto now = que.front();
        que.pop();
        for (int mov = 0; mov < dx.size(); mov++) {
            int ny = now.first + dy[mov];
            int nx = now.second + dx[mov];

            if (ny < 0 || height <= ny || nx < 0 || width <= nx) {
                continue;
            }

            if (cnt[ny][nx] == -1) {
                que.push(P(ny, nx));
                cnt[ny][nx] = cnt[now.first][now.second] + 1;
            }
        }
    }
}

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

    int H, W;
    cin >> H >> W;
    maze.resize(H);
    cnt.resize(H, vector<int>(W, -1));
    REP(i, H) cin >> maze[i];

    int cnt_b = 0;
    REP(i, H) {
        REP(j, W) {
            if (maze[i][j] == '#') {
                cnt[i][j] = -INF32;
                cnt_b++;
            }
        }
    }
    que.push(P(0, 0));
    cnt[0][0] = 0;

    bfs(H, W);

    int ans = cnt[H - 1][W - 1];
    if (ans != -1) {
        ans = H * W - (ans + 1) - cnt_b;
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i <= (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;

int main() {
  string S;
  cin >> S;
  
  string T = "ATCG";
  
  int ans = 0;
  rep(i,S.size()) {
    int now = 0;
    repf(j,i,S.size()) {
      bool ok = false;
      rep(k,T.size()) {
        if (S.at(j) == T.at(k)) ok = true;
      }
      if (ok) {
        now++;
        ans = max(ans,now);
      }
      else {
        break;
      }
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <queue>
#include <cstdio>
#include <numeric>
#include <set>
#include <map>


using namespace std;


int main()
{
    int N;
    cin >> N;
    set<int> s;
    vector<int> d(N);
    
    for (int i = 0; i < N; i++) {
        cin >> d[i];
        s.insert(d[i]);
    }

    cout << s.size() << endl;

}

Measured memory_bytes: 256
alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
a, b = map(int, input().split())
for i in range(a):
  c= input().split()
  for j in range(b):
    if c[j] == "snuke":
      print(alph[j] + str(i + 1))
      exit()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	ll n,y;
	cin >> n >> y;
	rep(i,0,n+1){
		rep(j,0,n-i+1){
			ll a = n - i - j;
			if( a >= 0 ){
				if( 1000* a + 5000*j + 10000*i == y && a + j + i == n ){
					cout << i << " " << j << " " << a << endl;
					ret 0;
				}
			}
		}
	}

	cout << "-1 -1 -1" << endl;
	ret 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <tuple>
#include <vector>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << *t++;
        if(t != V.end())
            cout << " ";
    }
    cout << endl;
}

int gcd(int x, int y) {
    int tmp;
    if(x > y)
        return gcd(y, x);
    int r;
    while((r = x % y)) {
        x = y;
        y = r;
    }
    return y;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << endl;
}



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

int main() {
  // 部分文字列をいちいち評価しては時間が足りなさそう
  int n,q; cin>>n>>q;
  string s; cin>>s;
  vector<int> l(q);
  vector<int> r(q);
  for(int i=0; i<q; i++) cin>>l[i]>>r[i];
  // 先頭からi文字目まで数えたときのACの数
  vector<int> numAC(n,0);
  for(int i=1; i<s.length(); i++) {
    if(s[i]=='C' && s[i-1]=='A') numAC[i]=numAC[i-1]+1;
    else numAC[i]=numAC[i-1];
  }
  for(int i=0; i<q; i++) {
    int ans = numAC[r[i]-1]-numAC[l[i]-1];
    cout << ans << endl;
  }
}


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

#define int long long

using namespace std;
 main() {
    int n , m , k , l , r ,mid ;
    cin >> n >> m;
    k = m / n;
    for (int i = k ;i >=1;i--)
    {
        if (m%i==0)
        {
            cout << i;
            exit(0);
        }
    }
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}
 
const int maxn=10;
//i_am_noob
int n,a[3][3],b[maxn];
bool bl[3][3];

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	rep(3) rep1(j,3){
		cin >> a[i][j];
		bl[i][j]=false;
	}
	cin >> n;
	rep(n) cin >> b[i];
	rep(n){
		rep1(j,3) rep1(k,3){
			if(b[i]==a[j][k]){
				bl[j][k]=true;
			}
		}
	}
	rep(3) if(bl[i][0]&&bl[i][1]&&bl[i][2]){
		print1("Yes");
		return 0;
	}
	rep(3) if(bl[0][i]&&bl[1][i]&&bl[2][i]){
		print1("Yes");
		return 0;
	}
	if(bl[0][0]&&bl[1][1]&&bl[2][2]){
		print1("Yes");
		return 0;
	}
	if(bl[0][2]&&bl[1][1]&&bl[2][0]){
		print1("Yes");
		return 0;
	}
	print1("No");
	return 0;
}


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

#define rep(i,n) for(ll i=0;i<n;i++)
#define REP(i,a,n) for(ll i=a;i<n;i++)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef pair<ll, ll> pll;

const int INF = 100000000;
const ll LINF = 1e18+5;

int main() {
    ll N, M;
    cin >> N >> M;
    if(N==M) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int main(){
    int n, t;
    while(cin>>n && n){
        vector<string> s(n);
        vector<int> r(n, 0);
        rep(i, n){
            cin>>s[i];
            rep(j, s.size()){
                if(s[i][j]=='.') r[i]++;
                else break;
            }
        }
        for(int i = 0; i < n; i++){
            if(r[i]==0) continue;
            s[i][r[i]-1]='+';
            for(int j = 0; j < r[i]-1; j++){
                s[i][j]=' ';
            }
        }
        rep(i, *max_element(all(r))){
            for(int j = 0; j < n; j++){
                if(i >= s[j].size()) continue;
                if(s[j][i]=='+'){
                    for(int k = j + 1; k < n; k++){
                        if(i >= s[k].size()) continue;
                        if(s[k][i]=='+'){
                            for(int l = j + 1; l < k; l++){
                                if(i >= s[l].size()) continue;
                                s[l][i]='|';
                            }
                            break;
                        }
                        else if(s[k][i]!=' ') break;
                    }
                }
            }
        }
        for(int i = 0; i < n; i++){
            cout<<s[i]<<endl;
        }
    }
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll x, y, s;
    while (cin >> x >> y >> s, x || y || s) {
        ll ans = 0;
        rep(a, 1, s+1) rep(b, 1, s+1) {
            if (a * (100 + x) / 100 + b * (100 + x) / 100 == s) {
                chmax(ans, a * (100 + y) / 100 + b * (100 + y) / 100);
            }
        }
        cout << ans << endl;
    }
}



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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

ll op(ll a, ll b) {
    return max(a, b);
}

ll e() {
    return 0;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, K;
    cin >> N >> K;

    segtree<ll, op, e> seg(300010);

    REP(i, N){
        ll a;
        cin >> a;
        
        ll l = a-K;
        l = max(l, 0LL);
        ll r = a+K+1;
        r = min(300005LL, r);

        ll sum = seg.prod(l, r);

        seg.set(a, sum+1);
    }

    cout << seg.all_prod() << endl;

    return 0;
}

Measured memory_bytes: 13840
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N; cin >> N;
  vector<int> d(N);
  
  for(auto &it: d)
    cin >> it;
  
  int sol = 0;
  for(int i=0; i<N-1; i++)
    for(int j=i+1; j<N; j++)
      sol += d.at(i) * d.at(j);
  
  cout << sol << endl;

}

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

#pragma GCC diagnostic warning "-Wconversion"

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) begin(a), end(a)
#define has(a, b) (a.find(b) != a.end())
#define fora(i, n) for(int i = 0; i < n; i++)
#define forb(i, n) for(int i = 1; i <= n; i++)
#define forc(a, b) for(const auto &a : b)
#define ford(i, n) for(int i = n; i >= 0; i--)
#define maxval(t) numeric_limits<t>::max()
#define minval(t) numeric_limits<t>::min()
#define imin(a, b) a = min(a, b)
#define imax(a, b) a = max(a, b)

#define dbgs(x) #x << " = " << x
#define dbgs2(x, y) dbgs(x) << ", " << dbgs(y)
#define dbgs3(x, y, z) dbgs2(x, y) << ", " << dbgs(z)
#define dbgs4(w, x, y, z) dbgs3(w, x, y) << ", " << dbgs(z)

using ll = long long;

ll gcd(ll a, ll b)
{
        return (b == 0) ? a : gcd(b, a % b);
}

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

        ll n, k;
        cin >> n >> k;

        ll g = 0, m = 0;
        fora(i, n)
        {
                ll q;
                cin >> q;
                g = gcd(g, q);
                imax(m, q);
        }
        bool ok = k % g == 0 && k <= m;
        if (ok)
                cout << "POSSIBLE" << endl;
        else
                cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <string>
#include <bitset>
#include <tuple>
#include <cmath>
#include <map>
#include <cstdio>

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

using namespace std;

using ll = long long;
using ull = unsigned long long;

using Pll  = pair<ll, ll>;
using Pull = pair<ull, ull>;

#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define F first
#define S second

#define rep( i, n ) for ( int i = 0; i < (int)( n ); ++i )
#define reps( i, n ) for ( int i = 1; i <= (int)( n ); ++i )
#define rrep( i, n ) for ( int i = (int)( ( n ) - 1 ); i >= 0; --i )
#define rreps( i, n ) for ( int i = (int)( ( n ) ); i > 0; --i )
#define arep( i, v ) for ( auto &&i : ( v ) )

template<typename T> T gcd( const T a, const T b ) { return ( b ? gcd( b, a % b ) : a ); }

#define ALL( c ) ( c ).begin(), ( c ).end()
#define RALL( c ) ( c ).rbegin(), ( c ).rend()
#define UNIQUE( c ) ( c ).erase( unique( ( c ).begin(), ( c ).end() ), ( c ).end() )

constexpr ll MOD = 1000000007LL;

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev

template<typename T = ll> class UnionFind {
public:
	UnionFind( T n ) { rep( i, n ) { par.resize( n ); siz.resize( n ); par[i] = i; siz[i] = 1; } }
	T find( T x ) { if ( x == par[x] ) return ( x ); else return( par[x] = find( par[x] ) ); }
	void unite( T x, T y ) { T xx = find( x ); T yy = find( y ); if ( xx == yy ) return;
		if ( siz[xx] <= siz[yy] ) swap( xx, yy ); par[yy] = xx; siz[xx] += siz[yy]; }
private:
	vector<T> par, siz;
};

template<typename T = ll> T power( T a, T b, T m = MOD ) {
	T res = 1;
	while ( b > 0 ) { if ( b & 1 ) res = res * a % m;
		a = a * a % m; b >>= 1; }
	return ( res );
}

/*
constexpr ll MAX = 500010;
ll fact[MAX];
ll inv[MAX];
ll inv_fact[MAX];

template<typename T> void initComb( T n, T m = MOD )
{
	fact[0] = fact[1] = inv_fact[0] = inv_fact[1] = 1;
	inv[1] = 1;
	for ( int i = 2; i < n; i++ ) {
		fact[i] = ( fact[i - 1] * i ) % m;
		inv[i] = m - inv[m % i] * ( m / i ) % m;
		inv_fact[i] = inv_fact[i - 1] * inv[i] % m;
	}
}

template<typename T> T comb( T n, T r, T m = MOD )
{
	if ( n < r ) return ( 0 );
	if ( n < 0 || r < 0 ) return ( 0 );
	return ( fact[n] * ( inv_fact[r] * inv_fact[n - r] % m ) % m );
}
*/

void replace( string &s, string t, string r ) {
	string::size_type p = 0;
	while ( ( p = s.find( t, p ) ) != string::npos ) {
		s.replace( p, t.length(), r );
		p += r.length();
	}
}


int main()
{
	ll W, H, x, y;
	cin >> W >> H >> x >> y;

	cout << fixed << setprecision( 20 );
	cout << (double)W * H / 2 << " "
		 << ( ( ( x * 2 == W ) && ( y * 2 == H ) ) ? 1 : 0 ) << endl;

	return ( 0 );
}


Measured memory_bytes: 632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define reset(x,n) memset((x),(n),sizeof(x))
#define all(n) (n).begin(),(n).end()
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0);
ll dp[100005];
int main(){
	reset(dp,0x3f);
	dp[0]=0;
	//cout<<dp[0]<<'\n';
	ll n,w,v,c;
	cin>>n>>w;
	for(int i=0;i<n;i++){
		cin>>c>>v;
		for(int i=100000;i>=v;i--){
			if(dp[i-v]<dp[100001]){
				dp[i]=min(dp[i],dp[i-v]+c);
			}
		}
	}
	ll x=100000;
	while(dp[x]>w)x--;
	cout<<x<<'\n';
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>

using namespace std;

int main() {

  vector<int> hand;

  int rock,scissors,paper;


  while(1) {

    int temp;

    cin >> temp;

    hand.clear();

    hand.push_back(temp);

    if(hand[0]==0) break;

    for(int i=1;i<5;i++) {

      cin >> temp;
      hand.push_back(temp);

    }

    rock=scissors=paper=0;

    for(int i=0;i<5;i++) {

      if(hand[i]==1) rock=1;

      if(hand[i]==2) scissors=1;

      if(hand[i]==3) paper=1;

    }

    if(rock==1 && scissors==1 && paper==1) {

      for(int i=0;i<5;i++) cout << "3" << endl;

    }

    else if(rock==1 && scissors==1) {

      for(int i=0;i<5;i++) {

	if(hand[i]==1) cout << "1" << endl;

	else if(hand[i]==2) cout << "2" << endl;

      }

    }

    else if(scissors==1 && paper==1) {

      for(int i=0;i<5;i++) {

	if(hand[i]==2) cout << "1" << endl;

	else if(hand[i]==3) cout << "2" << endl;

      }

    }

    else if(paper==1 && rock==1) {

      for(int i=0;i<5;i++) {

	if(hand[i]==3) cout << "1" << endl;

	else if(hand[i]==1) cout << "2" << endl;

      }

    }

    else if(rock==1) {

      for(int i=0;i<5;i++) cout << "3" << endl;

    }

    else if(scissors==1) {

      for(int i=0;i<5;i++) cout << "3" << endl;

    }

    else if(paper==1) {

      for(int i=0;i<5;i++) cout << "3" << endl;

    }

    else cout << "error!" << endl;

  }

  return 0;

}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int now = 0;
    while (a > 0 && c > 0) {
        if (now % 2 == 0) {
            c -= b;
        } else {
            a -= d;
        }
        now++;
    }
    cout << (now % 2 == 1 ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    class Tuple
    {
        public string Item1 { get; set; }
        public int Item2 { get; set; }
        public Tuple(string item1, int item2)
        {
            Item1 = item1;
            Item2 = item2;
        }
        public static Tuple Create(string item1, int item2)
        {
            return new Tuple(item1, item2);
        }
    }
    private static IEnumerable<List<T>> permutations<T>(List<T> ints, bool root = true)
    {
        if(ints.Count <= 0)
        {
            yield return new List<T>();
            yield break;
        }
        for(int i = 0; i < ints.Count; i++)
        {
            List<T> a = new List<T>(ints);
            a.RemoveAt(i);
            foreach(List<T> b in permutations(a, false))
            {
                b.Add(ints[i]);
                if(root) b.Reverse();
                yield return b;
            }
        }
    }
    private static IEnumerable<Tuple> Iter(List<int> ints)
    {
        if (ints.Count == 1)
        {
            yield return Tuple.Create(ints[0].ToString(), ints[0]);
            yield break;
        }
        for (int i = 1; i < ints.Count; i++)
            foreach(Tuple lhs in Iter(ints.Take(i).ToList()))
                foreach(Tuple rhs in Iter(ints.Skip(i).ToList()))
                    for (int j = 0; j < 3; j++)
                    {
                        if (j == 0)
                            yield return Tuple.Create(string.Format("({0}+{1})", lhs.Item1, rhs.Item1),
                            lhs.Item2 + rhs.Item2);
                        else if (j == 1)
                            yield return Tuple.Create(string.Format("({0}-{1})", lhs.Item1, rhs.Item1),
                            lhs.Item2 - rhs.Item2);
                        else
                            yield return Tuple.Create(string.Format("({0}*{1})", lhs.Item1, rhs.Item1),
                            lhs.Item2 * rhs.Item2);
                    }
    }
    private static IEnumerable<string> Is10(List<int> ints)
    {
        foreach(var tpl in Iter(ints))
            if(tpl.Item2 == 10)
                yield return tpl.Item1;
    }
    public static void Main()
    {
	for(;;)
	{
	    string str = Console.ReadLine();
	    if(str == "0 0 0 0") { return; }
	    List<int> ints = str.Split(new char[]{' '}).AsEnumerable().Select(int.Parse).ToList();
            string result = null;
	    foreach(List<int> i in permutations(ints))
                if ((result = Is10(i).FirstOrDefault(t => t != "")) != null)
                    break;
            Console.WriteLine(result != null ? result : "0");
	}
    }
}

Measured memory_bytes: 6308
#include <bits/stdc++.h>
#define int long long
#define gcd            __gcd
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x,y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;

int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
int modi(int a, int m)
{
    return power(a, m - 2, m);
}
int32_t main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        ans^=v[i];
    }
    for(int i=0;i<n;i++)
    {
        cout<<(ans^v[i])<<" ";
    }
    cout<<endl;

}

Measured memory_bytes: 4720
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int INF=1e8;

signed main(){
	int n,m;
    cin>>n>>m;
    vi c(m);
    rep(i,0,m) cin>>c[i];
    int dp[50010]={};
    rep(i,0,50010) dp[i]=INF;
    dp[0]=0;
    rep(i,0,m){
        rep(j,0,50010){
            if(j-c[i]>=0) dp[j]=min(dp[j],dp[j-c[i]]+1);
            //if(j+c[i]<50010) dp[j+c[i]]=min(dp[j+c[i]],dp[j]+1);
        }
    }
    cout<<dp[n]<<endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  rep(i,n) a[i]--;
  set<int> s;
  vector<int> idx(n);
  rep(i,n) idx[a[i]] = i;
  ll ans = 0;
  rep(x,n){
    int i =idx[x];
    int l=-1;
    int r=n;
    ll c=0;
    s.insert(i);
    { // calc l
      auto it = s.find(i);
      if(it!=s.begin()){
        --it;
        l = *it;
      }
    }
    { // calc l
      auto it = s.find(i);
      ++it;
      if(it!=s.end()){
        r = *it;
      }
    }
    c += (ll)(i-l)*(ll)(r-i);
    ans += c*(x+1);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 11136
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            int C = sc.nextInt();

            if (A >= B + C) {
                System.out.println(0);
            } else {
                System.out.println(B + C - A);
            }
        }
    }

}


Measured memory_bytes: 25172
#include <cstdio>
#define maxn 60
using namespace std;
int ans[maxn],n,m;
int main() {
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		ans[a]++;
		ans[b]++;
	}
	for (int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
	int i,j,k,m,n,f;
	double a,d[100][100],an[2][100];
	while(cin >> n >> m) {
		if (n==0 && m==0) break;
		for (i=0;i<n;i++) { an[0][i]=1; for (j=0;j<n;j++) cin >> d[i][j];}
		f=0;
		for (k=0;k<m-1;k++) {
			for (i=0;i<n;i++) { a=0; 
			  for (j=0;j<n;j++) a=a < an[f][j]*d[j][i] ? an[f][j]*d[j][i] : a;
			   an[1-f][i]=a; 
		  }
		  f=1-f;
		}
	  for (i=0,a=0;i<n;i++) a= a < an[f][i] ? an[f][i] : a;
	  printf("%.2f\n",a);
  }  			  
  return 0;
}

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

int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	if(n%2 == 1){
		cout << "No" << endl;
		return 0;
	}
	else{
		rep(i,n/2){
			if(s[i] != s[i+n/2]){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 3632
#include <iostream>

int main() {
    int N, T;
    std::cin >> N >> T;
    
    int c, t;
    int res_cost = 1001;
    for (int i=0; i<N; ++i) {
        std::cin >> c >> t;
        if (c < res_cost && t <= T) {
            res_cost = c;
        }
    }
    if (res_cost == 1001)
        std::cout << "TLE" << std::endl;
    else
        std::cout << res_cost << std::endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main() {
	int a, b;
	int re;
	char calc;
	while(cin >> a >> calc >> b && calc != '?') {
	    if (calc == '+') {
			re = a + b;
	    } else if (calc == '-') {
			re = a - b;
	    } else if (calc == '*') {
			re = a * b;
	    } else if (calc == '/') {
			re = a / b;
	    }
	    //cout << re << endl;
	        printf("%d\n", re);
        }
}

Measured memory_bytes: 1144
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace AtCoder_Core
{
    class Program
    {
        static void Main(string[] args)
        {
            var line1 = Console.ReadLine().Trim().Split(' ').Select(N => int.Parse(N)).ToArray();
            int X = line1[0];
            int Y = line1[1];
            int Z = line1[2];
            Console.WriteLine(Z + " " + X + " " + Y);
        }
    }
}


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

main(){
  int x;
  cin >> x;
  
  int point = 0;
  point += (x/500)*1000;
  x=x%500;
  point += (x/5)*5;
  x=x%5;
  
  cout << point <<endl;
  return 0;
  
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    int W = sc.nextInt();
    int H = sc.nextInt();
    int N = sc.nextInt();
    int[] x = new int[N];
    int[] y = new int[N];
    int[] a = new int[N];

    for (int i = 0; i < N; i++) {
      x[i] = sc.nextInt();
      y[i] = sc.nextInt();
      a[i] = sc.nextInt();
    }

    sc.close();

    int ans = 0;

    int startX = 0;
    int startY = 0;
    int endX = W;
    int endY = H;

    for (int i = 0; i < N; i++) {
      if (a[i] == 1) {
        startX = Math.max(startX, x[i]);
      } else if (a[i] == 2) {
        endX = Math.min(endX, x[i]);
      } else if (a[i] == 3) {
        startY = Math.max(startY, y[i]);
      } else {
        endY = Math.min(endY, y[i]);
      }
    }

    if (0 < (endX - startX) && 0 < (endY - startY)) {
      ans = (endX - startX) * (endY - startY);
    }

    System.out.println(ans);

  }

}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    ll N; cin >> N;
    vector<ll> A(3*N);
    ll sumA = 0, sumB = 0;
    vector<ll> a(N+1, 0);
    priority_queue<ll, vector<ll>, greater<ll>> AA;
    priority_queue<ll> AB;
    rep(i,3*N) {
        cin >> A.at(i);
        if (i >= 0 && i < N) {
            sumA += A[i];
            AA.emplace(A[i]);
        } else if (i >= 2*N) {
            sumB += A[i];
            AB.emplace(A[i]);
        }
    }
    a[0] = sumA;
    a[N] = -sumB;
    for (int i = 0; i < N; i++) {
        AA.push(A[N+i]);
        sumA += A[N+i];
        ll mi = AA.top(); AA.pop();
        sumA -= mi;
        a[i+1] += sumA;
        AB.push(A[2*N-1 - i]);
        sumB += A[2*N-1 - i];
        ll ma = AB.top(); AB.pop();
        sumB -= ma;
        a[N-1 - i] -= sumB;
    }
    ll ma = INT64_MIN;
    rep(i,N+1) {
        ma = max(ma, a[i]);
    }
    cout << ma << endl;
}


Measured memory_bytes: 5748
void main(){
	int n = _scan();
	(n^^3).writeln();
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


Measured memory_bytes: 2652
//AOJ 0558: Cheese
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_HW = 1000;
int n, h, w, rat, s[2], g[2], flag[MAX_HW + 1][MAX_HW][2];
int town[MAX_HW][MAX_HW];
char town2[MAX_HW][MAX_HW];
queue <P> que;
P p;
void bfs(int sy, int sx){
	que.push(P(sy, sx));
	flag[sy][sx][0] = rat;
	while (que.size()){
	RE:
		p = que.front();
		que.pop();
		for (int i = -1; i <= 1; i++){
			for (int j = -1; j <= 1; j++){
				if (i == 0 || j == 0){
					if (town2[p.first + i][p.second + j] != 'X'&&flag[p.first + i][p.second + j][0] != rat&&p.first + i < h&&p.first + i >= 0 && p.second + j < w&&p.second + j >= 0) {
						flag[p.first + i][p.second + j][0] = rat;
						flag[p.first + i][p.second + j][1] = flag[p.first][p.second][1] + 1;
						if (town[p.first + i][p.second + j] == rat){
							if (rat == n) return;
							rat++;
							flag[p.first + i][p.second + j][0] = rat;
							while (que.size()){
								que.pop();
							}
							que.push(P(p.first + i, p.second + j));
							goto RE;
						}
						else{
							que.push(P(p.first + i, p.second + j));
						}
					}
				}
			}
		}
	}
}
int main(){
	cin >> h >> w >> n;
	rat = 1;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			cin >> town2[i][j];
			town[i][j] = town2[i][j] - 48;
			if (town2[i][j] == 'S'){
				s[0] = i;
				s[1] = j;
			}
			if (town[i][j] == n){
				g[0] = i;
				g[1] = j;
			}
		}
	}
	bfs(s[0], s[1]);
	cout << flag[g[0]][g[1]][1] << endl;
	return 0;
}

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

int main() {
	int n;
	cin>>n;
	int odd=0,f=0,a[n];
	bool t=false;
	for(int i=0;i<n;i++){
		cin>>a[i];

		if(a[i]%4==0) {f++;} 
		else if(a[i]%2==0) {t=true;}
		else if(a[i]%2!=0){odd++;}
	}
	
	
	if(odd-1+t<=f)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (int i = 0; i < n; i++)
#define IREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(a, b) for (int i = a; i < b + 1; i++)
#define all(v) v.begin(), v.end()
#define SENTINEL 2000000000
#define NIL -1
using namespace std;
typedef long long ll;

const ll INF = 1LL << 60;
const ll MOD = 1000000007;
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()
{
    vector<vector<int>> a(3,vector<int>(3));
    REP(i,3){
        REP(j,3){
            cin >> a[i][j];
        }
    }
    map<int,int> m;
    int n;
    cin >> n;
    REP(i,n){
        int in;
        cin >> in;
        m[in]=100;
    }
    REP(i,3){
        int tmp1=0;
        int tmp2=0;
        REP(j,3){
            tmp1+=m[a[i][j]];
            tmp2+=m[a[j][i]];
        }
        if(tmp1==300||tmp2==300){
            cout << "Yes" << endl;
            return 0;
        }
    }
    if (m[a[0][0]] + m[a[1][1]] + m[a[2][2]] == 300){
        cout << "Yes" << endl;
        return 0;
    }
    if (m[a[2][0]] + m[a[1][1]] + m[a[0][2]] == 300){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    // input
    string S;
    cin >> S;
    lint red = 0, blue = 0;
    for (int i = 0; i < S.length(); ++i) {
        (S[i] == '0') ? ++red : ++blue;
    }
    cout << 2 * min(red, blue) << endl;
    return 0;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a.at(i);

	vector<int> ans(n);
	rep(i, n){
		ans.at(a.at(i)-1) = i+1;
	}

	rep(i, n){
		cout << ans.at(i);
		if(i != n-1)
			cout << " ";
	}
	cout << endl;
	
	return 0;
}


Measured memory_bytes: 1664
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
c = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] > a[j]:
            c += 1
d = 0
for i in range(len(b)):
    for j in range(i + 1, len(b)):
        if b[i] > b[j]:
            d += 1
d -= c * 2
def modpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def modinv(n, mod):
    return modpow(n, mod - 2, mod)
MOD = 10 ** 9 + 7
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
print(ans)

Measured memory_bytes: 41692
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;
const long LINF = 1e13;
const long LLINF = 1e18;

template <class T>
void Swap(T& r, T& l) {
    T tmp = r;
    r = l;
    l = tmp;
}




int main() {

  long x,y;
  cin >> x >> y;

  long ans =0;

  cout << x + y/2;


}


























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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> ds(n);
    for (auto& d : ds) {
        cin >> d;
    }
    int sum_a = 0, sum_b = 0;
    for (auto d : ds) {
        sum_a += d;
        sum_b += d*d;
    }
    cout << (sum_a*sum_a - sum_b)/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int N[31] = { 0 };
	int i, j;
	for (i = 0; i < 29; i++) {
		scanf("%d", &j);
		N[j] = 1;
	}
	for (i = 1; i < 31; i++) {
		if (N[i] == 0)
			printf("%d\n", i);
	}
	return 0;
}

Measured memory_bytes: 1744
// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<P> VP;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

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

#define LFOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RLFOR(i,b,a) for(ll i=(b)-1;i>=(a);--i)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define PB push_back
#define EACH(i,c) REP(i,(int)(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define dump(x) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";
#define dump2(x,y) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x)\
			<< " , " << #y << " = " << (y) << "\n";

const ll INF = 1e18;
const double EPS = 1e-10;

int n,m;
ll k;
string s;

int ans = 0;

ll dp[5001];
P a[5000];

bool comp(const P &a, const P &b) {
	return a.first + a.second < b.first + b.second;
}

int main() {
	omajinai;
	cin >> n;
	REP(i, n){
		int h,p;
		cin >> h >> p;
		a[i] = MP(p,h);
	}
	sort(a, a+n, comp);

	REP(i, n+1) dp[i] = INF;
	dp[0] = 0;
	dp[1] = a[0].first;
	FOR(i, 1, n){
		RFOR(j, 1, i+2){
			if(dp[j-1]!=INF && dp[j-1] <= a[i].second){
				dp[j] = min(dp[j], dp[j-1] + a[i].first);
			}
		}
	}
	int ans = 0;
	RREP(i, n+1){
		if(dp[i]!=INF){
			cout << i << endl;
			return 0;
		}
	}
}


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

signed main() {
    while (true) {
        int n;
        cin >> n;
        
        if (n==0) {
            break;
        }
        
        int p[n];
        int L = 0;
        
        for (int i=0; i<n; i++) {
            cin >> p[i];
            L += p[i];
        }
        
        int j[n-1];
        
        for (int i=0; i<n-1; i++) {
            cin >> j[i];
        }
        
        sort(j, j+n-1, greater<int>());
        
        int ans = n*L;
        
        for (int i=0; i<n-1; i++) {
            n--;
            L += j[i];
            ans = max(ans, n*L);
        }
        
        cout << ans << endl;
    }
}


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

using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mp make_pair
#define ld long double
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > small_heap;
typedef priority_queue<int> big_heap;
const int N = 5e3 + 100;
const ll mod = 1e9 + 7;
int T;
ll ans;
vector<int> v;
ll dp[N];
int f[N], s[N], si[N], a[N], n, k;

int getfa(int x) { return f[x] == x ? x : f[x] = getfa(f[x]); }

ll ksm(ll a, ll b) {
    ll c = 1;
    for (; b; b >>= 1) {
        if (b & 1) c = (ll) c * a % mod;
        a = (ll) a * a % mod;
    }
    return c % mod;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]), f[i] = i;
    for (int i = 1; i <= n; i++)if (a[i] != -1)f[getfa(i)] = getfa(a[i]);//将所有已知的边进行处理
    for (int i = 1; i <= n; i++)if (a[i] == -1)s[getfa(i)]++;
    for (int i = 1; i <= n; i++)si[getfa(i)]++;//统计每一个并查集的容量大小
    for (int i = 1; i <= n; i++)
        if (f[i] == i) { //如果是并查集的根节点
            if (s[i] == 0)ans++;//该并查集所形成的是环。
            else v.push_back(si[i]);
        }
    k = v.size();
    dp[0] = 1;
    for (int i = 0; i < k; i++)
        for (int j = i + 1; j >= 1; j--) {
            dp[j] = (dp[j] + dp[j - 1] * v[i] % mod * max(j - 1, 1) % mod) % mod;
        }
    ans = ans * ksm(n - 1, k) % mod;//起始有的环乘以贡献。
    for (int i = 2; i <= k; i++)ans = (ans + ksm(n - 1, k - i) * dp[i]) % mod;//该树与其他树一起形成一个环
    for (int i = 0; i < k; i++)ans = (ans + ksm(n - 1, k - 1) * (v[i] - 1) % mod) % mod;//每棵树与自己成环
    ans = (n * ksm(n - 1, k) % mod - ans + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 3960
N=readline.to_i
s1= readline.strip.split('')
s2= readline.strip.split('')

domino = s1.zip(s2).map {|u, d| u==d ? 1 : 2 }

frame = []
until domino.empty?
  frame << domino.shift
  domino.shift if frame.last==2
end

pre = frame.shift
result = 3
result = 6 if pre==2

MOD = 10**9+7
frame.each do |c|
  tmp=2
  tmp=1 if pre==2 && c==1
  tmp=3 if pre==2 && c==2
  result = (result * tmp)%MOD
  pre = c
end

p result





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

#define ll long long

const int maxV = 1e5 + 1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, W, V = 0;
	cin >> N >> W;
	vector<pair<int, int>> arr(N);
	vector<ll> dp(maxV); // Min weight in which value i can be reached
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		arr[i] = make_pair(a, b);
		V += b;
	}

	for (int i = V; i > 0; --i) {
		dp[i] = INT_MAX;
	}

	for (int item = 0; item < N; ++item) {
		int w = arr[item].first, v = arr[item].second;
		for (int i = V; i >= v; --i) {
			dp[i] = min(dp[i], dp[i - v] + w);
		}
	}

	for (int i = V; i >= 0; --i) {
		if (dp[i] <= W) {
			cout << i << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 4000
#include<iostream>
using namespace std;
long long n,k;
int main()
{
	cin>>n>>k;
	long long sum=1;
	for(int i=1;i<=n;i++)
	{
		if(sum*2>sum+k)   sum+=k;
		else              sum*=2;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256