akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

template<class T, class F>
struct slidingWindowAggregation {
    // using F = function<T(T,T)>;
    F f;
    T d;
    stack<pair<T,T>> st1, st2;
    slidingWindowAggregation(F f, T d) : f(f), d(d) {}
    T fold_all() { 
        if(st1.size() && st2.size()) return f(st1.top().second, st2.top().second); 
        if(st2.size()) return st2.top().second;
        if(st1.size()) return st1.top().second;
        return d;
    }
    void push(T x) { 
        const T rui = st2.size() ? f(st2.top().second, x) : x;
        st2.push({x, rui}); 
    }
    void pop() {
        if(st1.empty()) {
            T rui = d;
            while(st2.size()) {
                T t; tie(t, ignore) = st2.top(); st2.pop();
                rui = f(rui, t);
                st1.push({t, rui});
            }
        }
        st1.pop();
    }
};

int main(void) {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];

    // dp[i回投げた][最後に当てたのがj]
    // dp[i][j] = max(dp[i-1][k]) + (i+1)*j j-m<=k<=j-1
    vector<vector<ll>> dp(k, vector<ll>(n, -INF));
    REP(i, n) dp[0][i] = a[i]; 
    FOR(i, 1, k) {
        auto f = [&](ll l, ll r) { return max(l, r); };
        slidingWindowAggregation<ll, decltype(f)> swag(f, -INF);
        REP(j, n) {
            dp[i][j] = swag.fold_all() + (i+1)*a[j];
            swag.push(dp[i-1][j]);
            if(j >= m) swag.pop();
        }
        dump(i, dp[i]);
    }

    ll ret = 0;
    REP(i, n) chmax(ret, dp[k-1][i]);
    cout << ret << endl;

    return 0;
}

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


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

  int n;
  cin >> n;
  ll sum = 0;
  vector<int> a(n);
  rep(i,n){
    cin >> a[i];
  }
  sort(a.rbegin(),a.rend());

  rep(i,n){
    if(i==0) continue;
    else{
      sum += a[i/2];
    }
  }
  cout << sum << endl;
  
  return 0;
    

}


Measured memory_bytes: 3988
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define eps 1e-9
#define maxp 220000
#define mod 1000000007
#define pi 3.141592653589793238
#define sin(s) scanf("%lld",&s);
#define sout(s) printf("%lld\n",s);
#define in(s) cin>>s
#define in2(a,b) cin>>a>>b
#define in3(a,b,c) cin>>a>>b>>c
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl '\n'
#define sp ' '
#define gear_change ios_base::sync_with_stdio(false),cin.tie(0)
#define nfl(i,n) for(i=0;i<n;i++)
#define sfl(i,s,e) for(i=s;i<e;i++)
#define ufl(i,n) for(i=n-1;i>=0;i--)
ll power(ll x,ll y){
    ll ret=1;
    while(y>0){
        if(y&1)
            ret=(ret*x);
        y/=2;
        x=(x*x);
    }
    return ret;
}
vector<ll> divs(ll n){
	vector<ll>ret;
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			if(i*i==n){
				ret.push_back(i);
			}
			else{
				ret.push_back(i);
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}
void solve(){
	ll n,i;
	char a;
	cin>>a;
	if(a>='A' && a<='Z'){
		cout<<'A'<<endl;
	}else{
		cout<<"a"<<endl;
	}
}	
int main(){
	gear_change;
	ll test=1;
	// in(test);
	while(test--){
		solve();
	}
}	


Measured memory_bytes: 3612
while True:
    n, m, a = [int(i) for i in input().split()]
    
    if n == 0 and m == 0 and a == 0:
        break
    else:
        horizons = [[int(i) for i in input().split()] for j in range(m)]
        horizons.sort(reverse=True, key=lambda x: x[0])
        
        res = [int(i) for i in range(1, n+1)]
        
        for i in horizons:
            i[1] -= 1
            i[2] -= 1
            res[i[1]], res[i[2]] = res[i[2]], res[i[1]]
        
        print(res.index(a) + 1)


Measured memory_bytes: 5644
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;
long long int MOD = 1000000007;


int main(){
	
	while(true){
		int n;
		cin >> n;
		if(n == 0){
			break;
		}
		
		vector<int> v;
		
		string str1, str2;
		cin >> str1 >> str2;
		
		int num = (str1[0] - str2[0] + 10) % 10;
		if(num != 0){
			v.push_back(num);
		}
		
		for(int i = 1; i < n; i++){
			int d1 = str1[i] - str1[i - 1];
			int d2 = str2[i] - str2[i - 1];
			num = (d1 - d2 + 100) % 10;
			if(num != 0){
				v.push_back(num);
			}
		}
		
		num = (str2[n - 1] - str1[n - 1] + 10) % 10;
		if(num != 0){
			v.push_back(num);
		}
		
		sort(v.begin(), v.end());
		
		int ans = 10000;
		
		do{
			int cnt = 0;
			int pre = 0;
			int S = 0;
			for(int i = 0; i < v.size(); i++){
				S += v[i];
				if(S % 10 == 0){
					cnt += i - pre;
					pre = i + 1;
				}
				//cout << v[i] << " ";
			}
			//cout << endl;
			ans = min(ans, cnt);
		}while(next_permutation(v.begin(), v.end()));
		
		cout << ans << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
//const ull all=(1ull<<64)-1;
int n;
int S[505],T[505];
ull U[505],V[505];
ull A[505][505];
bool ok=1;
int has[505]; 
vector<int> tmp;
void solve(int bt)
{
	for(int i=0;i<n;i++)has[i]=0;
	
	for(int i=0;i<n;i++)
	{
		if(S[i]==0)
		{
			if((U[i]>>bt&1))
			{
				for(int j=0;j<n;j++)
				{
					A[i][j]|=(1ull<<bt);
					has[j]++;
					if((T[j]==1)&&(!(V[j]>>bt&1)))
					{
						ok=0;
						return;
					}
				}
			}
			else
			{
				int cnt=0;tmp.clear();
				for(int j=0;j<n;j++)
				{
					if((T[j]==0)&&(V[j]>>bt&1))
					{
						A[i][j]|=(1ull<<bt);
						has[j]++;
						cnt++;
					}
					else if((T[j]==1)&&(V[j]>>bt&1)&&(!has[j]))
					{
						tmp.push_back(j);
					}
				}
				if(cnt==n)
				{
					ok=0;
					return;
				}
				if(!tmp.empty())
				{
					while((cnt+(int)tmp.size())>=n)tmp.pop_back();
					for(int j=0;j<tmp.size();j++)
					{
						A[i][tmp[j]]|=(1ull<<bt);
						has[tmp[j]]++;
					}
				}
			}
		}
		else
		{
			if((U[i]>>bt&1))
			{
				bool can=0;
				int may=-1;
				for(int j=0;j<n;j++)
				{
					if((V[j]>>bt&1))
					{
						has[j]++;
						A[i][j]|=(1ull<<bt);
						can=1;
					}
					else if(T[j]==0)
					{
						if(may==-1||(has[j]<has[may]))may=j;
					}
				}
				if(!can)
				{
					if(may==-1)
					{
						ok=0;
						return;
					}
					has[may]++;
					A[i][may]|=(1ull<<bt);
				}
			}
			else
			{
				for(int j=0;j<n;j++)
				{
					if((T[j]==0)&&(V[j]>>bt&1))
					{
						ok=0;
						return;
					}
				}
			}
		}
	}
	for(int j=0;j<n;j++)
	{
		if(T[j]==0)
		{
			if((V[j]>>bt&1))
			{
				if(has[j]!=n)
				{
					ok=0;
					return;
				}
			}
			else
			{
				if(has[j]==n)
				{
					ok=0;
					return;
				}
			}
		}
		else
		{
			if(V[j]>>bt&1)
			{
				if(has[j]==0)
				{
					ok=0;
					return;
				}
			}
			else
			{
				if(has[j]!=0)
				{
					ok=0;
					return;
				}
			}
		}
	}
}
int main()
{
//	cout<<all<<endl;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&S[i]);
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&T[i]);
	}
	for(int i=0;i<n;i++)
	{
		scanf("%llu",&U[i]);
	}
	for(int i=0;i<n;i++)
	{
		scanf("%llu",&V[i]);
	}
	for(int t=0;t<64;t++)
	{
		solve(t);
		if(!ok)
		{
			printf("-1\n");
			return 0;
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			printf("%llu ",A[i][j]);
		}
		printf("\n");
	}
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<tuple<string,int,int>> rest(N);
  for(int i=0;i<N;i++){
    string s;
    cin >> s;
    int a;
    cin >>a;
    get<0>(rest.at(i)) = s;
    get<1>(rest.at(i)) = -a;
    get<2>(rest.at(i)) = i+1;
  }
  sort(rest.begin(),rest.end());

  for(int i=0;i<N;i++){
    cout << get<2>(rest.at(i)) << endl;
  }
}


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

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

    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            string temp;
            cin >> temp;
            if (temp == "snuke")
            {
                cout << (char)('A' + j) << i + 1 << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;


int h, w;
ll dist[55][55];
bool seen[55][55];
string field[55];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
    cin >> h >> w;
    rep(i, h) cin >> field[i];
    ll cnt = 0;
    rep(i, h) rep(j, w) if (field[i][j] == '#') cnt++;
    queue<pair<int,int>> que;
    que.push(make_pair(0, 0));
    dist[0][0] = 1;
    seen[0][0] = true;

    while(!que.empty()){
        pair<int, int> p = que.front();
        que.pop();
        int x = p.first;
        int y = p.second;
        rep(i, 4){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || w <= nx || ny < 0 || h <= ny || seen[ny][nx] || field[ny][nx] == '#') continue;
            seen[ny][nx] = true;
            dist[ny][nx] = dist[y][x] + 1;
            que.push(make_pair(nx, ny));
        }
    }

    if (!dist[h-1][w-1]) cout << -1 << endl;
    else cout << h * w - dist[h-1][w-1] - cnt << endl;

    return 0;
}

Measured memory_bytes: 256
n,m=[int(i) for i in input().split()]
id=[[int(i) for i in input().split()]+[j] for j in range(m)]

pre_num=[0]*(n+1)
ans=[""]*m

id.sort(key=lambda x:x[1])

for p, y, i in id:
    pre_num[p] += 1
    ans[i] = str(p).zfill(6) + str(pre_num[p]).zfill(6)

print("\n".join(ans))

Measured memory_bytes: 34696
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll a, b;
  cin >> a >> b;
  cout << (a-1) * (b-1) << endl;

  return 0;
}


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

int pow2(int l){
    if(l>0){
        return 2*pow2(l-1);
    }
    return 1;
}

vector<bool> inttobool(int n,int l){
    vector<bool> rep;
    for(int i=0;i<l;i++){
        rep.push_back(n%2);
        n/=2;
    }
    return rep;
}

int main(){
    string S;
    cin>>S;
    int l=S.size();
    long sum=0;

    vector<bool> positionofplus(11);
    string T;
    for(int i=0;i<(pow2(l-1));i++){
        positionofplus=inttobool(i,l-1);
        positionofplus.push_back(1);
        T+=S.at(0);
        for(int j=0;j<=l-1;j++){
            if(positionofplus.at(j)){
                sum+=stol(T);
                T="";
                if(j!=l-1){
                    T+=S.at(j+1);
                }
            }
            else{
                T+=S.at(j+1);
            }
        }
    }
    cout<<sum<<endl;
}

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

using namespace std;

bool match(string s, int id, string p){ 
        if(id+p.length()-1 < s.length()){
                bool flag = true;
                for(int i = 0; i < p.length(); i++){
                        flag &= p.at(i) == s.at(i+id);
                }   
                return flag;
        }   
        return false;
}
void change(string &s, int id, string p){ 
        for(int i = 0; i < p.length(); i++){
                s[id+i] = p[i];
        }   
}
int main(){
        string s;
        char c[1000];
        cin.getline(c, 1000);
        s = c;
        for(int i = 0; i < s.length(); i++){
                if(match(s, i, "apple")){
                        change(s, i, "peach");
                }else if(match(s, i, "peach")){
                        change(s, i, "apple");
                }   
        }   
        cout << s << endl;
}

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

int main() {
	int A, B;
  	cin >> A >> B;
  
  	if (A < 6) {
    	cout << 0 << endl;
    } else if (A < 13) {
    	cout << B / 2 << endl;
    } else {
    	cout << B << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool check[10]={0};
vector<int> s;
int coun=0;
bool flag=0;
 void perm(int n,int A[]){ //will genrate the permutatoins
  if(s.size()==n){
        coun++;
        flag=1;
        for(int i=0;i<n;i++){
            if(A[i]!=s[i])
                flag=0;
        }
    return;
  }
 for(int i=1;i<=n;i++){
    if(check[i]==0){
            check[i]=1;
        s.push_back(i);
        perm(n,A);
        if(flag==1)
        return;

        s.pop_back();
    check[i]=0;
    }
 }




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

perm(n,A);
//cout<<coun;
int c1=coun;
coun=0;
flag=0;
for(int i=1;i<=n;i++){
    s.pop_back();
    check[i]=0;
}
perm(n,B);
//cout<<c1<<" "<<coun;
cout<<abs(coun-c1);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
 
#define INF 1000000
#define NIL NULL
#define WHITE 5000
#define BLACK 5001
 
void initializeSingleSource(void);
void dijkstra(void);
 
int v[101][101],c[101][101];
int *d,*pi,*color,*k;
int n;
 
int main(){
  int i,j;
  int *u;
 
  scanf("%d",&n);
 
  u = malloc(sizeof(int)*n);
  d = malloc(sizeof(int)*n);
  pi = malloc(sizeof(int)*n);
  color = malloc(sizeof(int)*n);
  k = malloc(sizeof(int)*n);
 
  for(i = 0;i < n;i++){
    scanf("%d %d",&u[i],&k[i]);
    for(j = 0;j < k[i];j++){
      scanf("%d",&v[i][j]);
      scanf("%d",&c[i][j]);
    }
  }
 
  dijkstra();
 
  for(i = 0;i < n;i++){
    printf("%d %d\n",u[i],d[i]);
  }
 
  return 0;
}
 
void initializeSingleSource(){
  int i;
  for(i = 0;i < n;i++){
    d[i] = INF;
    pi[i] = NIL;
    color[i] = WHITE;
  }
  d[0] = 0;
}
 
void dijkstra(){
  int i,j,mincost,u1,v1;
 
  initializeSingleSource();
 
  while(1){
    mincost = INF;
    for(i = 0;i < n;i++){
      if(color[i] != BLACK && d[i] < mincost){
    mincost = d[i];
    u1 = i;
      }
    }
 
    if(mincost == INF)break;
 
    color[u1] = BLACK;
 
    for(v1 = 0;v1 < k[u1];v1++){
      if(color[v[u1][v1]] != BLACK && (d[u1] + c[u1][v1]) < d[v[u1][v1]]){
    pi[v[u1][v1]] = u1;
    d[v[u1][v1]] = d[u1] + c[u1][v1];
      }
    }
  }
}

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

int main(){
  vector<int> v(3);
  for(int i=0;i<3;i++){
    cin >> v.at(i);
  }
  sort(v.begin(),v.end(),greater<int>());
  cout << v.at(0)*10+v.at(1)+v.at(2) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main (){
  int n,a,b,c,d,e;
  scanf("%d",&n);
  a=n/1000;
  b=(n-(a*1000))/100;
  c=(n-(a*1000)-(b*100))/10;
  d=(n-(a*1000)-(b*100)-(c*10));
  e=0;
  if(a==2){
     e++;
  }
  if(b==2){
     e++;
  }
  if(c==2){
     e++;
  }
  if(d==2){
     e++;
  }
  printf("%d\n",e);
}

Measured memory_bytes: 128
/*
 * atcoder/dp_3rd/e.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const int MAX_N = 110;
const int MAX_V = 110000;
const ll INF = 100000000000000000;
ll N, CAP;
ll W[MAX_N], V[MAX_N];
ll dp[MAX_N][MAX_V];

void input() {
  cin >> N >> CAP;
  loop(n,0,N) {
    cin >> W[n] >> V[n];
  }
}

void solve() {
  loop(n,0,N) loop(v,0,MAX_V) dp[n][v] = INF;
  for (int n=0; n<N; n++) {
    ll w = W[n], v = V[n];
    for (ll maxv=0; maxv<=1000*N; maxv++) {
      if (maxv == 0) { dp[n][0] = 0; continue; }
      if (v>=maxv) chmin(dp[n][maxv], w); // 今回のアイテムだけで価値をまかなえるところまでwを設定
      if (n==0) continue;
      chmin(dp[n][maxv], dp[n-1][maxv]); // 前回までの方が軽く済んだか確認
      if (maxv-v>=0) chmin(dp[n][maxv], dp[n-1][maxv-v] + w); // 今回のアイテムを使うことでさらに軽く出来るか確認
    }
  }

  ll maxv = 0;
  while (dp[N-1][maxv] <= CAP) maxv++;
  if (maxv>0) maxv--;
  cout << maxv << endl;
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 86272
import bisect
def resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    cnt = 0
    for i, edge in enumerate(AB):
        edges = AB[:i]+AB[i+1:]
        if not is_reachable(edges, edge[0], edge[1]):
            cnt += 1
    print(cnt)


def is_reachable(edges, src, dst):
    import collections
    stack = collections.deque()
    stack.append(src)

    while stack:
        pos = stack.pop()
        if pos == dst:
            return True
        _edges = []
        while edges:
            edge = edges.pop()
            if edge[0] == pos:
                stack.append(edge[1])
            elif edge[1] == pos:
                stack.append(edge[0])
            else:
                _edges.append(edge)
        edges = _edges
    return False


if '__main__' == __name__:
    resolve()

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const double PI=acos(-1.0);
const int INF=1e9;
const double EPS=1e-10;
const ll MOD=1e9+7;


int main(){
int n,h;
int cnt=0;
cin>>n;
vector<int> v(n);
REP(i,n){
cin>>v[i];
}
h=v[0];
REP(i,n){
if(v[i]>=h){
h=v[i];
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}

Measured memory_bytes: 256
//C
//#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>


#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Hang in there!

using namespace std;


int main() {
	int A, B;
	cin >> A >> B;
	cout << (A - 1) * (B - 1) << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_set>
#include <bitset>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
static const int INF = 1000010000;
static const int NIL = -1;
static const int MOD = 1000000007;
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue
 
int gcd(int a, int b) { int c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
int lcm(int a, int b) { int c = gcd(a, b); a /= c; return a*b; }
int nCr(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
int pow(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llpow(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llgcd(long long a, long long b) { long long c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
long long lllcm(long long a, long long b) { long long c = llgcd(a, b); a /= c; return a*b; }
long long llnCr(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
 
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};

int main(){
    int a, b, h;
    cin >> a >> b >> h;
    cout << h / 2 * (a + b) << endl;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n := nextInt(sc)

	var min, max, sum int64
	min = math.MaxInt64
	max = math.MinInt64
	for i := int64(0); i < n; i++ {
		a := nextInt(sc)
		sum += a
		if min > a {
			min = a
		}
		if max < a {
			max = a
		}
	}

	fmt.Printf("%d %d %d\n", min, max, sum)
}

func nextString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) int64 {
	i, err := strconv.ParseInt(nextString(sc), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}



Measured memory_bytes: 1128
a,b,c,d = map(int, input().split())

for i in range(100): # 繰り返し処理したい、とりあえず100回以上の繰り返しはないから100回繰り返す
    c -= b # 青木くんの体力cから高橋くんの攻撃力bぶん引く
#    print('c', c) # 残り体力確認用
    if c <= 0: # 青木くん体力が0以下になったら
        print('Yes') # 高橋くんの勝ちなのでYes
        break # 体力が0になったら繰り返しも終了

    a -= d # 次に高橋くんの体力aから青木くんの攻撃力dを引く
 #   print('a',a) # 残り体力確認用
    if a <= 0: # 高橋くん体力が0以下になったら
        print('No') # 青木くん勝利でNo
        break # 体力が0になったら繰り返しも終了
# どちらの体力も残ってたら次の繰り返し

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

using namespace std;
using P = pair<char, int>;

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

const int INF = 1e18;
const int MOD = 1e9 + 7;

signed main(){
    int N, K, Q; cin >> N >> K >> Q;
    vector<int> ap( N );
    REP( i, Q ){
        int a; cin >> a;
        a--;
        ap[a]++;
    }

    REP( i, N ){
        if( K - ( Q - ap[i] ) > 0 ){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

}


Measured memory_bytes: 1408
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;






int main(){
    ll a,b;
    cin>>a>>b;
    a*=b;
    if(a%2==0){cout<<"No"<<endl;}
    else{cout<<"Yes"<<endl;}
    
    return 0;
}


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

int main(){
    int n,p;
    cin >> n >> p;
    bool hasodd = false;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        if(a%2!=0) hasodd=true;
    }

    if(hasodd){
        cout << (1LL<<(n-1)) << endl;
    }else{
        if(p==0){
            cout << (1LL<<n) << endl;
        }else{
            cout << 0 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<bitset>
#include<stack>
#include<set>
#include<vector>
#include <time.h>
#include<string.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

const int maxn = 1e5+5;
const int Mod=1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e=exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;

#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
int a[maxn];
char str[maxn];
int main()
{
    ios::sync_with_stdio(false);
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);
    int n;
    int a,b;
    cin>>a>>b;
    if(a%2==1&&b%2==1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}


Measured memory_bytes: 256
using System;

class Program {
    static void Main(string[] args) {
        int N = int.Parse(Console.ReadLine());
        string D = Console.ReadLine();

        int now = 0;
        int max = 0;

        for (int i = 0; i < N; i++) {
            if (D[i] == 'I') {
                now++;
                max = Math.Max(max, now);
            } else {
                now--;
            }
        }
        Console.WriteLine(max);
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
string a="snuke";
int main()
{
    string s;
    int h,w;
    cin>>h>>w;
    int ans=0;
    for(int i=0;i<h*w;i++)
    {
        cin>>s;
        if(s==a)
            ans=i;
    }
    int hh=ans/w+1;
    char ww=(ans)%(w)+'A';
    cout<<ww<<hh<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define repd(i, n) for (ll i = (n)-1; i >= 0; --i)
#define INF 10e12
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n, d;
    cin >> n >> d;
    cout << (n + 2 * d) / (2 * d + 1) << endl;
}

Measured memory_bytes: 3604
package main

import (
	"fmt"
	//"math"
	"strconv"
	"strings"
)

func main() {
	var k, x int
	fmt.Scan(&k, &x)
	var a []string
	for i := -k+1; i < k; i++ {
		a = append(a, strconv.Itoa(x+i))
	}
	fmt.Print(strings.Join(a, " "))
}

Measured memory_bytes: 640
#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 ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

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;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll w, a, b; cin >> w >> a >> b;
    if (a + w < b) {
        cout << abs(a + w - b) << endl;
    } else { 
        if (a < b + w) {
            cout << 0 << endl;
        } else {
            cout << abs(a - (b + w)) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#pragma warning(disable:4996) 

typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
//const long long MOD = 1000000007;
const long long MOD = 998244353;

using namespace std;



void solve()
{
    int n;
    scanf("%d", &n);
    ll s = 0;
    int i;
    map<int, int> z;
    for (i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        z[tmp]++;
        s += tmp;
    }
    int Q;
    scanf("%d", &Q);
    for (i = 0; i < Q; i++) {
        int b, c;
        scanf("%d%d", &b, &c);
        auto it=z.find(b);
        if (it != z.end()) {
            s += (ll)(it->second)*(c - b);
            auto it2 = z.find(c);
            if (it2 == z.end()) {
                z[c] = it->second;
            }
            else {
                it2->second += it->second;
            }
            z.erase(it);
        }
        printf("%lld\n", s);
    }


    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}


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

using ll=long long;

const int MAX = 2200000;
const long long MOD = 1000000007;
long long INF = 90000000001000;

long long fac[MAX], finv[MAX], inv[MAX];

unsigned GetDigit(unsigned num){
    return to_string(num).length();
}

vector<ll> enumDivisor(ll n){
    vector<ll> res;
    for(ll i=1; i*i<=n; ++i){//nの二乗根まで調べれば良い。
        if(n%i != 0) continue;//割り切れない場合
        res.push_back(i);//割り切れたらresにいれる
        if(i*i != n) res.push_back(n/i);//二乗根じゃない場合もう片方の約数もいれる。
    }
    return res;
}


int main() {
int a,b,c,x,y,mx;
ll ans=INF;
cin >> a >> b >> c >> x >> y;
mx = max(x,y);
for (int i = 0; i <= mx; ++i)
{
    int an,bn;
    ll sum = 0;
    an = max(0,x-i);bn = max(0,y-i);
    sum = an*a+bn*b+i*2*c;
    ans = min(ans,sum);
}

cout << ans;
return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <queue>
#include <map>
#include <stack>
using namespace std;
 
int dx[8]={1,-1,0,0,1,1,-1,-1};
int dy[8]={0,0,1,-1,-1,1,-1,1};
 
 
int main() {
int n;
while(cin>>n && n){
int mi=1000000;
for(int z=0;z<101;z++){
if(z*z*z>n) break;
int q=n-z*z*z;
int y=0;
while(y*y<=q) y++;
y--;
int x=q-y*y;
mi=min(mi,x+y+z);
}
cout<<mi<<endl;
}
	return 0;
 
   }

Measured memory_bytes: 2980
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

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


	int N, M;
	cin >> N >> M;
	vector<int> IE[100001];
	int num = 1;
	int topo[100001], jisuu[100001] = {};
	rep(i, N + M - 1) {
		int a, b;
		cin >> a >> b;
		IE[b].pb(a);
		jisuu[a]++;
	}

	stack<int> ST;
	rep1(i, N) {
		if(!jisuu[i])ST.push(i);
	}
	while (ST.size()) {
		int k = ST.top();
		ST.pop();
		topo[k] = num++;
		for (int u : IE[k]) {
			jisuu[u]--;
			if (!jisuu[u]) ST.push(u);
		}
	}

	rep1(i, N) {
		int kotae = 0;
		int saishou = 1e9;
		if (topo[i] == N) kotae = 0;
		else {
			for (int u : IE[i]) {
				if (saishou > topo[u]) {
					saishou = topo[u];
					kotae = u;
				}
			}
		}
		co(kotae);
	}

	Would you please return 0;
}

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

int main(){
	string s;cin>>s;
	string a="abc";
	do{
		string t;
		rep(i,s.size()){
			t+=a[i%3];
		}
		string x=s;
		sort(x.begin(),x.end());
		sort(t.begin(),t.end());
		if(x==t){
			puts("YES");
			return 0;
		}
	}while(next_permutation(a.begin(),a.end()));
	puts("NO");
}

Measured memory_bytes: 696
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <utility>
using namespace std;

using P = pair<int, int>;

struct UnionFind {
    vector<int> parent;
    int set_num;

    UnionFind(int n) {
        parent.resize(n, -1);
        set_num = n;
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            if (size(x) < size(y)) swap(x, y);
            parent[x] += parent[y];
            parent[y] = x;
            set_num--;
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    int find(int x) {
        if (parent[x] < 0) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    int size(int x) {
        return -parent[find(x)];
    }

    int size() {
        return set_num;
    }
};

array<int, 300000> group1, group2;

int main() {
    int N, K, L;
    cin >> N >> K >> L;

    UnionFind uf1(N), uf2(N);
    for (int i = 0; i < K; i++) {
        int p, q;
        cin >> p >> q;
        p--; q--;
        uf1.unite(p, q);
    }

    for (int v = 0; v < N; v++) {
        group1[v] = uf1.find(v);
    }

    for (int i = 0; i < L; i++) {
        int r, s;
        cin >> r >> s;
        r--; s--;
        uf2.unite(r, s);
    }

    for (int v = 0; v < N; v++) {
        group2[v] = uf2.find(v);
    }

    map<P, int> counter;
    for (int v = 0; v < N; v++) {
        counter[make_pair(group1[v], group2[v])]++;
    }
    for (int v = 0; v < N; v++) {
        cout << counter[make_pair(group1[v], group2[v])] << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 15104
"""    Arnab Chanda    """

from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7


x, n = multi_int_input()

arr = list_input()

arr = set(arr)

a = 0

while(True):
    l = x - a
    r = x + a

    if (l not in arr):
        print(l)
        break
    elif (r not in arr):
        print(r)
        break

    a+=1

Measured memory_bytes: 9596
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int d[200005];
const int inf = 200005;
vector<int> v[200005];

void bfs(void)
{
    d[1] = 0;

    queue<int> q;

    q.push(1);

    while (!q.empty())
    {
        int t = q.front();q.pop();

        for (int i = 0;i < v[t].size();i++)
        {
            int tt = v[t][i];

            if (d[t] + 1 < d[tt])
            {
                d[tt] = d[t] + 1;

                q.push(tt);
            }
        }
    }
}

int main()
{
    memset(d,inf,sizeof(d));

    int n,m;

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

    for (int i = 1;i <= m;i++)
    {
        int a,b;

        scanf("%d%d",&a,&b);

        v[a].push_back(b);
    }

    bfs();

    if (d[n] == 2) printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");

    return 0;
}


Measured memory_bytes: 9592
#include <cstdio>
using namespace std;

int main()
{

	int  a, b;
	char query;

	while( scanf( "%d %c %d", &a, &query, &b ), query != '?' ) {

		switch( query ) {

			case '+':
				printf( "%d\n", a + b ); break;
			case '-':
				printf( "%d\n", a - b ); break;
			case '*':
				printf( "%d\n", a * b ); break;
			case '/':
				printf( "%d\n", a / b ); break;

		}

	}

	return 0;

}

Measured memory_bytes: 1028
// beet hieteruka~~~
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

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

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
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...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  int N;
  cin >> N;
  vector< int > R(N), A(N), W(N), T(N);
  vector< int > ord(N);
  for(int i = 0; i < N; i++) {
    cin >> R[i] >> A[i] >> W[i] >> T[i];
    ord[i] = i;
  }
  sort(begin(ord), end(ord), [&](int a, int b) {
    return R[a] + T[a] > R[b] + T[b];
  });

  vector< int64 > dp(5000);
  for(int i : ord) {
    vector< int64 > dp2(5000);
    fill_v(dp2, -infll);
    for(int j = 0; j < 5000; j++) {
      if(j + R[i] < 5000 && j + R[i] + T[i] >= 5000) chmax(dp2[j + R[i]], dp[j] + A[i]);
    }
    for(int j = 0; j < 5000; j++) {
      if(j + R[i] < 5000 && j + R[i] + T[i] >= 5000) chmax(dp2[j + R[i]], dp2[j] + W[i]);
    }
    for(int j = 0; j < 5000; j++) {
      chmax(dp[j], dp2[j]);
    }
  }
  cout << dp[4999] << endl;
}








Measured memory_bytes: 3340
import sys
sys.setrecursionlimit(10**6)

n = int(input())
h = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

ma = 0
ans = 0

for i in range(n):
    if h[i] >= ma:
        ans += 1
    ma = max(ma, h[i])
    
print(ans)

Measured memory_bytes: 9120
#include <iostream>
using namespace std;
int main()
{

	int n, m, a[100], b[100][100], p[100], count;

	for (int i = 0; i < 100; i++) p[i] = 0;

	cin >> n >> m;

	for (int i = 0; i < m; i++) cin >> a[i];

	for (int i = 0; i < m; i++){
		count = 0;
		for (int j = 0; j < n; j++){
			cin >> b[i][j];
			if (b[i][j] == a[i]) p[j] += 1;
			else count++;
		}
		p[a[i]-1] += count;
	}

	for (int i = 0; i < n; i++)
		cout << p[i] << endl;

}

Measured memory_bytes: 1196
#include <iostream>
using namespace std;
int main(){
    string s;cin>>s;
    string ans;
    for(int i=1;i<s.size();++i){
        if(s[i-1]==s[i]){
            ans="Bad";
            break;
        }else{
            ans="Good";
        }
    }    
    cout<<ans<<endl;
}

Measured memory_bytes: 256
// Lets go to the next level
// AIM EXP at CF *__* asap
// Hit A,B,C faster and reach Expert
// Remember you were also a novice when you started,
// hence never be rude to anyone who wants to learn something!Be calm and help everyone.
// Never open the rank list until and unless you are done with solving problems!
/*HACK ME IF YOU CAN!
░░███▒▒░░░░░░░░░░░░░░░░████
░░████▒░░░░░░░░░░░░░░░███▒█
░░██████░░░░░░░░░░░░░███▒▒▒█
░░██▒▒▒▒█▒▒▒▒▒▒▒▒▒▒▒█████▒██
░▒▒▒▒▓▓▓▓▓▓▒▒▒▒▒▓▓▓▓▓▓▒▒▒░██
▒▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒█
▒▒▓▓███████▓░▓▓███████▓▒▒▒▒▒▒
▒▒▓▓▓█▓▄▓█▓░░░▓▓█▓▄▓█▓▓▒▒▒▒▒▒
▒▒▓▓▓▓███▓░░░░░▓▓███▓▓▓▒▒▒▒▒▒
▒▒▒▓▓▓▓▓▓████▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒
▒▒▒▒▓▓▓▓▓▒██▒▒▒▓▓▓▓▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
░▒▒▒▒▒▒▒▒█████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
░░▒▒▒▒▒▒█▒▒▒▒▒█▒▒▒▒▒▒▒▒▒▒▒▒▒
░░░░░▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
*/

//Author: kaiyu
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) ((long long)(x).size())
#define all(x)  x.begin(),x.end()
#define endl "\n"
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define leastsigbit(x)     __builtin_ffs(x)
#define mod             1000000007
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define pii pair<int,int>
#define vpii vector<pii>
#define tt ll tt;cin >> tt;while(tt--)
#define  fio ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define D1(x) { cerr << " [" << #x << ": " << x << "]\n"; }
#define D2(x) { cerr << " [" << #x << ": "; for(auto it:x) cerr << it << " "; cerr << "]\n";}
const double PI = acos(-1);
ll power(ll a,ll b,ll m=mod){ ll ans=1; a=a%m;  while(b>0) {  if(b&1)  ans=(1ll*a*ans)%m; b>>=1;a=(1ll*a*a)%m;}return ans;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm( ll x, ll y) { return (x*y)/gcd(x,y);}
bool isprime(ll n){if(n < 2) return 0; ll i = 2; while(i*i <= n){if(n%i == 0) return 0; i++;} return 1;}
struct cmp {
    bool operator() (const pair<int,int>& lhs, const pair<int,int>& rhs) const {
        return lhs.ff * rhs.ss < lhs.ss * rhs.ff;
    }
//for map<pii,int>
};

bool cmps(pair<int,int>p1,pair<int,int>p2) {
    return p1.ss > p2.ss;
}

const int MAXN = 2e5+ 10;

#define int long long
int32_t main() {
//#ifndef ONLINE_JUDGE
    //freopen("inp1.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
//#endif
    fio
    int n;
    cin >> n;
    int a[n];
    map<int,int>pk;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pk[a[i]]++;
        sum += a[i];
    }
    tt{
        int x,y;
        cin >> x >> y;
        sum-=pk[x] * x;
        sum += pk[x]*y;
        int tmp = pk[x];
        pk.erase(x);
        pk[y] += tmp;
        cout << sum << endl;
    };


    cerr << "[ Time : " << (float)clock() / CLOCKS_PER_SEC << " secs ]" << endl;


}






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

using namespace std;

#define endl '\n'

int a, b;

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

    cin >> a >> b;

    if(a < b)
        cout << "a < b" << endl;
    else if(a > b)
        cout << "a > b" << endl;
    else
        cout << "a == b" << endl;
}



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

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

const int MOD = 1e9 + 7;
const int INFi = 2e9 + 1;
const lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(i, vec) for(auto &(i) : (vec))


template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


int main(void){
  int n, m, c, res = 0;
  cin >> n >> m >> c;
  Vint B(m);
  vREP(ele, B) cin >> ele;
  int SUM;
  REP(i, n){
    SUM = 0;
    int tmp;
    REP(j, m){
      cin >> tmp;
      SUM += B.at(j) * tmp;
    }
    if(SUM + c > 0) res++;
  }
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 256