akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<cmath>
#define SZ(x) ((int)x.size())
#include<vector>
#include<set>
#include<map>
#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#include<string>
#include<cctype>
#include<queue>
#define ii pair<int,int>
#include <sstream>
#define lli long long int
#define pairs pair<int,int>
#define mod 1000000007
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;
ll pows(ll a,ll n,ll m)
{
	ll res=1;
	while(n)
	{
	if(n%2!=0)
	{
		res=(res*a)%m;
		n--;
		}
		else
		{
			a=(a*a)%m;
			n=n/2;
			}	
	}
	return res%m;
}
ll  gcd(ll a,ll b)
{
	if(b==0)
	return a;
	else 
	return gcd(b,a%b);
}
bool isprime(ll n)
{
	if(n==1)
	{
		return false;
	}
	for(ll i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}
bool istrue(string s)
{
	int i=0;
	int j=s.size()-1;
	while(i<j)
	{
	if(s[i]==s[j])
	{
		i++;
		j--;
		}
		else
		{
			return false;
			}	
	}
	return true;
}
int main()
{
   ios::sync_with_stdio(false);
	 cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    if(isprime(n)==true)
    {
    	cout<<1<<endl;
    	return 0;
	}
	if(n==1)
	{
		cout<<0<<endl;
		return 0;
	}
vector<ll>vi;
for(ll i=2;i*i<=n;i++)
{
	if(n%i==0)
	{
		int cnt=0;
		while(n%i==0)
		{
			cnt++;
			n=n/i;
		}
		vi.pb(cnt);
	}
}
if(n>1)
{
	vi.pb(1);
}
int ans=0;
for(ll i=0;i<vi.size();i++)
{
	int p=vi[i];
	for(ll j=1;j<=50;j++)
	{
		if(p<j)
		{
			break;
		}
		else
		{
			ans++;
			p=p-j;
		}
	}
}
cout<<ans<<endl;
}
 


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i = s; i < n; i++)
const int maxn = 100005;
const int INF = INT_MAX;
int N, K;
int h[maxn];
int d[maxn];

int dp(int a){
	if(d[a]!=-1) return d[a];
	int ans = INF;
	rep(i,1,K+1){
		if(a-i<1)break;
		ans = min(ans, dp(a-i)+abs(h[a-i]-h[a]));
	}
	return d[a] = ans;
}

int main(){
	cin>>N>>K;
	rep(i,0,N) {
		cin>>h[i+1];
	}
	memset(d,-1,sizeof d);
	d[1] = 0;
	cout<<dp(N)<<endl;
}

Measured memory_bytes: 5760
#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 n;
  	cin>>n;
  	
  	ll sum=0;
  	rep(i,n){
    	if(i%3!=0 && i%5!=0){
        	sum+=i;
        }
    }
  	cout<<sum<<endl;
  
}

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

// clang-format off
#define forn(i, x, y) for(int i = x; i < y; i++)
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL)

using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVILL = vector<VLL>;
// clang-format on

const long long MOD = 1000000007;

int main()
{
  IOS;

  int H, W;
  cin >> H >> W;
  VVI grid(H, VI(W, 1));
  string line;
  forn(i, 0, H)
  {
    cin >> line;
    forn(j, 0, W) if (line[j] == '#') grid[i][j] = 0;
  }

  VVI dp(H, VI(W));
  dp[0][0] = 1;
  forn(i, 0, H)
  {
    forn(j, 0, W)
    {
      if (grid[i][j] == 0)
        continue;
      if (i > 0)
        dp[i][j] += dp[i - 1][j];
      if (j > 0)
        dp[i][j] += dp[i][j - 1];
      dp[i][j] %= MOD;
    }
  }
  cout << dp[H - 1][W - 1] << endl;

  return 0;
}


Measured memory_bytes: 11084
object Main extends App {
	val n = scala.io.StdIn.readLong
	val a = new Array[Long](5)

	for(i<-0 until 5){
		a(i) = scala.io.StdIn.readLong
	}

	val b = new Array[Long](5)

	for(i<-0 until 5){
		b(i) = (n + a(i) - 1L)/a(i)
	}

	println(4 + b.max)

}

Measured memory_bytes: 25536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

ll par[100005];
ll find(ll x){
    if(par[x]<0)return x;
    return par[x]=find(par[x]);
}
void unite(ll x,ll y){
    x=find(x),y=find(y);
    if(x==y)return;
    par[y]=x;
}
void solve(){
    ll n,q;cin>>n>>q;
    memset(par,-1,sizeof(par));
    rep(i,q){
        ll com,x,y;cin>>com>>x>>y;
        if(com==0){
            unite(x,y);
        }else{
            if(find(x)==find(y)){
                cout<<1<<endl;
            }else{
                cout<<0<<endl;
            }
        }
    }
}

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



Measured memory_bytes: 3996
/+ dub.sdl:
    name "C"
    dependency "dcomp" version=">=0.3.2"
    lflags "-stack_size" "100000000"
+/

import std.algorithm, std.conv, std.range, std.stdio;

// import dcomp.scanner;

int[128][1001] dp;
int calc(int n, int d) {
    if (n == 1) return d;
    if (dp[n][d] != -1) return dp[n][d];
    int ans = 0;
    foreach (i; 0..128) {
        ans = max(ans, calc(n-1, d^i) + i);
    }
    return dp[n][d] = ans;
}

int main(string[] argv) {
    auto sc = new Scanner();
    int t;
    sc.read(t);
    foreach (i; 0..1001) {
        dp[i][] = -1;
    }
    foreach (unused; 0..t) {
        int n, d;
        sc.read(n, d);
        writeln(calc(n, d));
    }
    return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

class Scanner {
    import std.stdio : File, stdin;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f = stdin) {
        this.f = f;
    }
    string[] buf;
    private bool succ() {
        while (!buf.length) {
            if (f.eof) return false;
            buf = f.readln.split;
        }
        return true;
    }
    private bool readSingle(T)(ref T x) {
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                //string or char[10] etc
                x = buf.front;
                buf.popFront;
            } else {
                static if (isStaticArray!T) {
                    //static
                    assert(buf.length == T.length);
                }
                x = buf.map!(to!E).array;
                buf.length = 0;                
            }
        } else {
            x = buf.front.to!T;
            buf.popFront;            
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}

unittest {
    import std.path : buildPath;
    import std.file : tempDir;
    import std.algorithm : equal;
    import std.stdio : File;
    string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
    auto fout = File(fileName, "w");
    fout.writeln("1 2 3");
    fout.writeln("ab cde");
    fout.writeln("1.0 1.0 2.0");
    fout.close;
    Scanner sc = new Scanner(File(fileName, "r"));
    int a;
    int[2] b;
    char[2] c;
    string d;
    double e;
    double[] f;
    sc.read(a, b, c, d, e, f);
    assert(a == 1);
    assert(equal(b[], [2, 3]));
    assert(equal(c[], "ab"));
    assert(equal(d, "cde"));
    assert(e == 1.0);
    assert(equal(f, [1.0, 2.0]));
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
#define fine cout<<"fine"<<endl;
#define ll long long int
#define pb push_back
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
const ll inf=(ll)2e18;
const int mod=1e9+7;
bool overflow(ll a,ll b){
    if (a <= (inf+b-1)/b) return false;
    return true;
}
int main(){
FASTIO;
string s;
cin>>s;
int i,n=s.length();
for(i=0;i<n/2;i++){
    if(s[i]!=s[n-i-1])
        break;
}
if(i!=n/2){
    cout<<"No"<<endl;
    return 0;
}
for(i=0;i<n/4;i++){
    if(s[i]!=s[n/2-i-1])
        break;
}
if(i!=n/4){
    cout<<"No"<<endl;
    return 0;
}
for(i=0;i<n/4;i++){
    if(s[i+n/2+1]!=s[n-i-1])
        break;
}
if(i!=n/4){
    cout<<"No"<<endl;
    return 0;
}
cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
int n,k,a[107];
int dp[100007];

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	dp[k]=0;
	for(int i=0;i<=k;i++){
		int ok=0;
		for(int j=1;j<=n;j++){
			if(i>=a[j]){
				if(dp[i-a[j]]==0){
					ok=1;
				}
			}
		}
		dp[i]=ok;
	}
	if(dp[k]==1){
		printf("First\n");
	}
	else{
		printf("Second\n");
	}
}

Measured memory_bytes: 4116
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
    ll n;
    cin>>n;
    char c[n];
    rep(i,n){
        cin>>c[i];
    }
    ll co=1;
    rep(i,n-1){
        if(c[i]!=c[i+1]){
            co++;
        }
    }
    cout<<co<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n) for(int i=(int)k; i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
using namespace std;
using namespace boost;
using namespace boost::adaptors;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

using Weight = ll;
Weight INF = 1000000000000000l;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
}

// Dijkstra (Verified: AOJ2005)
void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  using P = pair<Weight,int>;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int main() {
  ll n,m,s;
  cin>>n>>m>>s;
  ll mxs = 2500;
  Graph g(n*mxs);
  REP(i,m) {
    ll u,v,a,b;
    cin>>u>>v>>a>>b;
    --u;--v;
    FOR(j,a,mxs) {
      add_edge(g, u*mxs + j, v*mxs + j-a, b);
      add_edge(g, v*mxs + j, u*mxs + j-a, b);
    }
  }
  REP(i,n) {
    ll c,d;
    cin>>c>>d;
    c = min(c, mxs-1);
    REP(j,mxs) {
      add_edge(g, i*mxs + j, i*mxs + min(j+c, mxs-1), d);
    }
  }
  s = min(s, mxs-1);
  Array res;
  dijkstra(g, res, s);
  FOR(i,1,n) {
    ll mn = INF;
    REP(j,mxs) mn = min(mn, res[i*mxs + j]);
    cout<<mn<<endl;
  }
  return 0;
}


Measured memory_bytes: 23732
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int ch(vector<ll> v,int t){
    if(v[t]==9) return 0;
    v[t]++;
    rep(i,v.size()-1) if(abs(v[i]-v[i+1])>1) return 0;
    return 1;
}

int main() {
   ll k,ans=0; cin>>k;
   vector<ll> num(1,0);
   rep(i,k){
       rep(j,num.size()){
           if(ch(num,j)){
               num[j]++;
               rep(r,j) num[j-r-1]=max(0LL,num[j-r]-1);
               break;
           }
           if(j==num.size()-1){
               num.push_back(1);
               rep(r,num.size()-1) num[r]=0;
               break;
           }
       }
   }
   ll cnt=1;
  rep(i,num.size()){
      ans+=cnt*num[i];
      cnt*=10;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define LL long long
#define pii pair<int,int>
#define mp make_pair

int n,ci;
LL ans;
int a[N],b[N];
priority_queue<pii> q;

int main()
{
	ios_base::sync_with_stdio(0);
	
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	for(int i=0;i<n;i++)
		q.push(mp(b[i],i));
	while(!q.empty())
	{
		ci++;
		if(ci>=2e7) return cout<<"-1\n",0;
		int x=q.top().second;
		q.pop();
		if(b[x]==a[x]) continue;
		int pa,pb;
		if(x) pa=b[x-1];
		else pa=b[n-1];
		if(x!=n-1) pb=b[x+1];
		else pb=b[0];
		if(max(max(pa,pb),a[x])+pa+pb<b[x])
		{
			ans+=(b[x]-max(max(pa,pb),a[x]))/(pa+pb);
			b[x]-=(b[x]-max(max(pa,pb),a[x]))/(pa+pb)*(pa+pb);
		}
		else b[x]-=pa+pb,ans++;
		if(b[x]<a[x]) return cout<<"-1\n",0;
		q.push(mp(b[x],x));
	}
	cout<<ans<<'\n';
	
	return 0;
}

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

int main(){

 	#ifndef ONLINE_JUDGE
 	freopen("input.txt", "r", stdin);
 	freopen("output.txt", "w", stdout);
 	#endif

 	int ans=0,n,k,f[1000];
 	cin>>n>>k;
 	for (int i = 0; i < n; ++i)
 	{
 		cin>>f[i];
 	}
 	sort(f,f+n);
 	for (int i = 0; i < k; ++i)
 	{
 		ans+=f[i];
 	}
 	cout<<ans;
 	return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
long long a,b;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>a>>b;
    if (a<b){
        for (int i=0;i<b;i++){
            cout<<a;
        }
    }
    else {
        for (int i=0;i<a;i++){
            cout<<b;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define per(i,n) for(long long i = (long long)(n-1);i >= 0;--i)
#define REP(i,s,t) for(long long i=s;i<t;i++)
#define PER(i,s,t) for(long long i=s;i>t;--i)
#define all(x) x.begin(),x.end()
#define sp(n) setprecision(n)
typedef long long ll;
using namespace std;
int main(){
  int a,b,h;
  cin>>a>>b>>h;
  cout<<(a+b)*h/2<<endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
 
AB.sort()
cost = 0
for i in range(N):
    M -= AB[i][1]
    cost += AB[i][1]*AB[i][0]
    if M<=0:
        store_num = i
        break
if M<0:
    m = abs(M)
    cost -= m*AB[store_num][0]
print(cost)

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

using namespace std;

namespace {

#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define DYDY(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define RARA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int ll;
typedef double dd;

ll Sum(ll x) {
  ll res = 0;
  while (x > 0) {
    res += x % 10;
    x /= 10;
  }
  return res;
}

void Solve(ll) {
  ll n, res = 1e9;
  cin >> n;
  VEVE(a, 1, n) res = min(res, Sum(a) + Sum(n - a));
  cout << res << endl;
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}

int32_t main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}


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

int x[15],lside[15],rside[15];
int n,kase;

void dfs(int i,int l,int r){
	if(i > 10){
		kase = 1;
		return ;	
	}
	if(kase)	return ;
	if(x[i]>lside[l]){
		lside[l+1] = x[i];
		dfs(i+1,l+1,r);
	}
	if(x[i]>rside[r]){
		rside[r+1] = x[i];
		dfs(i+1,l,r+1);
	}
}
int main(void){
	cin>>n;
	while(n--){
		for(int i=1;i<=10;i++)
			cin>>x[i];
		kase = 0;
		dfs(1,0,0);
		if(kase)	printf("YES\n");
		else	printf("NO\n");
	}
	return 0;
} 


Measured memory_bytes: 3052
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define brep(i,n) for(int i=n-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<n;i++)
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
#define ll long long
ll pow2(ll p,ll n){
    long long num = 1;
    while(n){
        if(n%2 == 1){
            num *= p;
        }
        n/=2;
        p *= p;
    }
    return num;
}

int main(void){
    ll n,p;
    cin >> p >> n;
    map<ll,ll> mp;
    ll a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            mp[a]++;
            n /= a;
        } 
        else a++;
    }
    mp[n]++;
    ll ans = 1;
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
        ll num = (ll)itr ->second;
        while(num >= p){
            ans *= itr->first;
            num -= p;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
def gcd(a, b):
    if a < b: a, b = b, a
    while b:
        t = a / b
        a -= b * t
        a, b = b, a
    return a
def lcm(a, b):
    return a * b / gcd(a, b)
n = input()
print reduce(lambda a, b:lcm(a, b), map(int, raw_input().split()))

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

int P, Q, R;

int eval(string &S, int &cur) {
    if (S[cur] == '(') {
        int a = eval(S, ++cur);
        char op = S[cur];
        int b = eval(S, ++cur);
        int res = 0;
        if (op == '*') {
            res = min(a, b);
        } else {  // S[cur] == '+'
            if (a == 2 || b == 2) {
                res = 2;
            } else if (a == 1 || b == 1) {
                res = 1;
            } else {
                res = 0;
            }
        }

        // curは閉じ括弧に位置する
        ++cur;
        return res;
    } else if (S[cur] == '-') {  // S[cur] == '-'
        int a = eval(S, ++cur);
        return 2 - a;
    } else if (S[cur] == 'P') {
        ++cur;
        return P;
    } else if (S[cur] == 'Q') {
        ++cur;
        return Q;
    } else if (S[cur] == 'R') {
        ++cur;
        return R;
    } else {
        int res = (int)(S[cur] - '0');
        ++cur;
        return res;
    }
}

int main() {
    string S;
    while (cin >> S, S != ".") {
        int res = 0;
        for (P = 0; P <= 2; ++P) {
            for (Q = 0; Q <= 2; ++Q) {
                for (R = 0; R <= 2; ++R) {
                    int cur = 0;
                    if (eval(S, cur) == 2) ++res;
                    //cout << "cur: " << cur << endl;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 3144
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 100005;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w,n,s1,s2;
    string s,t;
    cin >> h >> w >> n >> s1 >> s2 >> s >> t;
    --s1;
    --s2;
    reverse(all(s));
    reverse(all(t));
    ll l = 0,r = w;
    rep(i,n){
        if (t[i] == 'L') r = min(w,r+1);
        if (t[i] == 'R') l = max(0ll,l-1);
        if (s[i] == 'L') l++;
        if (s[i] == 'R') r--;
        if (l >= r){
            PRINT("NO");
            return 0;
        }
    }
    if (s2 < l || r <= s2){
        PRINT("NO");
        return 0;
    }
    l = 0;
    r = h;
    rep(i,n){
        if (t[i] == 'U') r = min(h,r+1);
        if (t[i] == 'D') l = max(0ll,l-1);
        if (s[i] == 'U') l++;
        if (s[i] == 'D') r--;
        if (l >= r){
            PRINT("NO");
            return 0;
        }
    }
    if (s1 < l || r <= s1){
        PRINT("NO");
        return 0;
    }
    PRINT("YES");
}





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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    for(int& i: A) cin >> i;
    pair<int, int> mx;
    mx.first = max(A[0], A[1]);
    mx.second = min(A[0], A[1]);
    for(int i = 2; i < n; i++){
        if(A[i] >= mx.first){
            mx.second = mx.first;
            mx.first = A[i];
        }
        else if(A[i] >= mx.second) mx.second = A[i];
    }
    for(int i: A) if(i == mx.first) cout << mx.second << endl; else cout << mx.first << endl;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
typedef long long ll;
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;

//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------


int main() {
    int ac=0,wa=0,tle=0,re=0;
    int n;
    cin>>n;
    rep(i,n){
        string s;
        cin>>s;
        if(s=="AC")ac++;
        else if(s=="WA")wa++;
        else if(s=="TLE")tle++;
        else re++;
    }
    cout<<"AC x "<<ac<<endl;
    cout<<"WA x "<<wa<<endl;
    cout<<"TLE x "<<tle<<endl;
    cout<<"RE x "<<re<<endl;

}




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

int remainders[200005];

string num = "";

int frequency[2030];

void fillRemainders()
{
	int x = num[num.length() - 1] - '0';
	remainders[num.length() - 1] = x;
	
	int k = 1, rem = x;
	for(int i = num.length() - 2; i >= 0; i--)
	{
		k *= 10;
		k %= 2019;
		
		rem = (num[i] - '0') * k + rem;
		rem %= 2019;
		
		remainders[i] = rem; 
	}
	
	for(int i = 0; i < (int)(num.length()) ; i++)
		frequency[remainders[i]]++;
}

int main()
{
	char s[200005];
	scanf("%s", s);

	for(int i = 0; s[i]; i++)
		num += s[i];
		
	fillRemainders();
	
	long long int ans = 0;
	for(int i = 0; i < 2030; i++)
	{
		ans += (long long)(frequency[i]) * (frequency[i] - 1) / 2;
	}
		
	printf("%lld", ans + frequency[0]); 
}

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

int main() {
  string s;
  int ans=0;
  cin>>s;
  for(int i=0;i<s.size();i++){
   for(int j=1;j<=s.size()-i;j++){
     string s1=s.substr(i,j);
     int c=0;
     for(int k=0;k<j;k++){
       if(s1[k]!='A'&&s1[k]!='C'&&s1[k]!='T'&&s1[k]!='G'){
         c=1;
       }
     }
     if(c==0){
       ans=max(ans,j);
     }
   }
  }
  cout<<ans;
      
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace CompetitiveProgramming
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] H_W = Console.ReadLine().Split(' ');
            int H = int.Parse(H_W[0]);
            int W = int.Parse(H_W[1]);

            string[] h_w = Console.ReadLine().Split(' ');
            int h = int.Parse(h_w[0]);
            int w = int.Parse(h_w[1]);

            Console.WriteLine(H * W - h * W - w * H + h * w);
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int main() {
    string S; cin>>S;
    long long counter=0;
    long long counter1=0;
    long long counter2=0;
    long long answer=0;
    if(S.at(0)=='<'){
    counter++;}
    else
    counter1++;
    for(long long i=1; i<S.size(); i++){
    if(counter>0&&counter2==0){
    if(S.at(i)=='<'){
    counter++;
    continue;}
    else{
    answer+=counter*(counter+1)/2;
    counter1++;
    counter2=counter;
    counter=0;
    continue;}}
    else {
    if(S.at(i)=='>'){
    counter1++;
    continue;}
    else{
    answer+=counter1*(counter1-1)/2+max((counter1-counter2),0LL);
    counter++;
    counter2=0;
    counter1=0;
    continue;}}}
    answer+=counter*(counter+1)/2;
    answer+=counter1*(counter1-1)/2+max((counter1-counter2),0LL);
    cout<<answer<<endl;}
    
      
    
    


Measured memory_bytes: 900
# 4桁の数字で3つ以上連続するか判定

N = list(input())
# print(N)

if N[0] == N[1] and N[0] == N[2]:
    print('Yes')
elif N[1] == N[2] and N[1] == N[3]:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9004
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = 1e9 + 7;

int n, x[200009], y[200009];
vector<long long> vec[4];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		vec[0].pb(x[i] + y[i]);
		vec[1].pb(-x[i] + y[i]);
		//vec[2].pb(-x[i] - y[i]);
		//vec[3].pb(x[i] - y[i]);
	}
	for (int i = 0; i < 2; i++) {
		sort(vec[i].begin(), vec[i].end());
		vec[i].resize(unique(vec[i].begin(), vec[i].end()) - vec[i].begin());
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int u = x[i], v = y[i];
		long long l = 0, r = 2e9;
		while (l + 1 < r) {
			bool ok = false;
			long long mid = (l + r) / 2;
			long long tmp = u + v + mid;
			if (lower_bound(vec[0].begin(), vec[0].end(), tmp) < vec[0].end()) ok = true;
			tmp = -u + v + mid;
			if (lower_bound(vec[1].begin(), vec[1].end(), tmp) < vec[1].end()) ok = true;
			tmp = u + v - mid;
			if (lower_bound(vec[0].begin(), vec[0].end(), tmp) > vec[0].begin()) ok = true;
			tmp = -u + v - mid;
			if (lower_bound(vec[1].begin(), vec[1].end(), tmp) > vec[1].begin()) ok = true;
			if (ok) l = mid;
			else r = mid;
		}
		ans = max(ans, l);
	}
	cout << ans << E;
	//system("pause");
	return 0;
}

Measured memory_bytes: 8236
#include<cstdio>
#include<bits/stdc++.h>
#define fi first
#define sc second
#define pb push_back


using namespace std;

const int MAXN = (int) 1e5;
int row[MAXN], col[MAXN];
long long cost[MAXN]; 

int R, C, D, Q;

int calc(int a, int b) {
	return abs(row[a] - row[b]) + abs(col[a] - col[b]);
}
int main() {
	cin >> R >> C >> D;
	
	for (int i = 1, x; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> x;
			row[x] = i; col[x] = j;
		}
	}
	for (int i = 1; i <= R * C; i++) {
		if (i - D > 0) {
			cost[i] += cost[i - D];
			cost[i] += calc(i, i -D);
		}
	}
	cin >> Q;
	for (int q = 0, le, ri; q < Q; q++)	 {
		cin >> le >> ri;
		cout << cost[ri] - cost[le] << endl; 
	}
	
	return 0;
}

Measured memory_bytes: 2560
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    string s; cin >> s;
    puts(s.substr(0, 4) == "YAKI" ? "Yes" : "No");
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	for(int i=0; i<m; ++i) cin >> a[i];

	vector<int> dp(n+1,1);
	for(int i=0; i<m; ++i) dp[a[i]]=0;
	for(int i=2; i<=n; ++i) dp[i] = dp[i]*(dp[i-1]+dp[i-2])%mod;

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

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

using namespace std;

using ll = long long int;

#define REP(i, N) for (int i = 0; i < (N); ++i)
#define scanInt(x) int x; scanf("%d", &(x)); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &(x)); getchar();
#define scanVecInt(A, N) vector<int> A(N); REP(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); REP(i, N){scanf("%lld", &(A[i])); getchar();}

ll getSum(ll N)
{
    ll sum = 0;
    while (0 < N){
        sum += (N % 10);
        N /= 10;
    }
    return sum;
}

int main()
{
    scanLLInt(N);
    ll sum_max = getSum(N);
    for (ll temp1 = 10; ; temp1 *= 10){
        ll temp2 = temp1 - 1;
        if (N < temp2) break;
        const ll temp3 = ((N - temp2) / temp1) * temp1 + temp2;
        // cout << temp3 << endl;
        sum_max = max(sum_max, getSum(temp3));
    }
    cout << sum_max << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int N=2e5+9;
int n,c[N],ans[N],sz[N];
int cnt[N];
vector <int> g[N];
void dfs(int v,int p){
    int mx=0,hold=cnt[c[v]];
    cnt[c[v]]=0;
    for(auto u:g[v]){
        if(u==p)continue;
        int prev=cnt[c[v]];
        dfs(u,v);
        sz[v]+=sz[u];
        int del=cnt[c[v]]-prev;
        int x=sz[u]-del;
        ans[c[v]]+=x*(x-1)/2+x;
    }
    sz[v]++;
    cnt[c[v]]=sz[v]+hold;
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> c[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        int x=n-cnt[i];
        ans[i]+=x*(x-1)/2+x;
    }
    int k=n*(n-1)/2+n;
    for(int i=1;i<=n;i++)
        cout << k-ans[i] << '\n';
}


Measured memory_bytes: 39592
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
/*#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <assert.h>*/

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;

int n, cnt;
int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n;
    forn(i, 1, n) {
        int x;
        cin >> x;
        if (x & 1) ++cnt;
    }

    cout << (cnt & 1 ? "NO" : "YES") << "\n";

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lln long long int
#define llu unsigned lln
#define sc(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define scd(n) scanf("%lf",&n);
#define pf(res) printf("%d\n",res);
#define pfl(res) printf("%lld\n",res);
#define pfd(res) printf("%lf\n",res);
#define maxii 100005
using namespace std;
typedef pair<int,int> pii;
typedef pair<lln,lln> pll;
typedef vector<int> vi;
typedef vector<lln> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


int arr[maxii];
int arr2[maxii];
int gcd(int a,int b)
{
    if(b==0){
      return a;
     }
    return gcd(b,a%b);
}
int lcm(int a,int b)
{
    int res=(a*b)/gcd(a,b);
    return res;
}
int po(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b%2!=0)
        {
            res*=a;
            b--;
        }
        else
        {
            a*=a;
            b/=2;
        }
    }
    return res;
}

lln modMul(lln  a, lln b,lln mod){
    lln ans = 0;
    a = a % mod;
    while (b > 0){
        if ( b % 2 )ans = (ans%mod+ a%mod) % mod;
        a = (a%mod * 2%mod) % mod;
        b /= 2;
    }
    return ans % mod;
}
lln powerMod(lln a,lln b,lln mod){
	if(b==0)return 1LL%mod;
	lln x=powerMod( a,b/2,mod );
	x = ( x%mod * x%mod ) % mod;
	if( b%2==1 )x = ( x%mod * a%mod ) % mod;
	return x%mod;
}

int main()
{
    string a,b;
    cin>>a>>b;
    int len=a.size();
    int c=0;
    for(int i=0;i<len;i++)
    {
        if(a[i]!=b[i])c++;
    }
    cout<<c;
}






Measured memory_bytes: 3916
#include<stdio.h>
#define min(a,b) (((a)<(b))?(a):(b))
int main(){
  int a,b,c,d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  printf("%d",min(a,b)+min(c,d));
  return 0;
}

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

int bubbleSort(int A[],int N){
	int iii=0;
	int flag=1;
	int ans1=0;
	while(flag){
		flag=0;
		for(int j=N-1;j>0;j--){
			if(A[j]<A[j-1]){
				swap(A[j-1],A[j]);
				flag=1;
				//cout<<"test"<<endl;
				ans1++;
			}
		}
		//iii++;
		}
	return ans1;
}
int main(){
	ios::sync_with_stdio(false);
	int N,A[100],ans=0;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>A[i];
	}
	ans=bubbleSort(A,N);
	for(int ji=0;ji<N;ji++){
		if(ji==N-1){cout<<A[ji]<<endl;}
		else{cout<<A[ji]<<" ";
		}
	}
	cout<<ans<<endl;
	int aa;cin>>aa;
	return 0;
}

Measured memory_bytes: 3200
def resolve():
  n, m = map(int, input().split())
  h = list(map(int, input().split()))
  ans = {i for i in range(n)}

  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if h[a] <= h[b]:
      ans.discard(a)
    if h[b] <= h[a]:
      ans.discard(b)

  print(len(ans))
  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 22380
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [na, nb] <- getIntList
  let (a:_) = show na
      (b:_) = show nb
      sa = replicate nb a
      sb = replicate na b
      ans = if sa < sb then sa else sb
  putStrLn ans

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

using namespace std;
long int v[101],w[101],dp[101][100001];
long int knapsack(long int wt,long int i){
    if(i<0)return 0;
    if(dp[i][wt]!=0)return dp[i][wt];
    if(wt>=w[i]) return dp[i][wt]=max(v[i]+knapsack(wt-w[i],i-1),knapsack(wt,i-1));
    else return dp[i][wt]=knapsack(wt,i-1);
}

int main()
{
   long int n,wt;
   cin >> n>>wt;
   
   for(int i=0;i<n;i++){
       cin>>w[i]>>v[i];
   }
   
   cout<< knapsack(wt,n-1)<<endl;
//   for(int i=0;i<=wt;i++){
//       cout<<dp[i]<<endl;
//   }
   
   return 0;
}

Measured memory_bytes: 78080
$n=<>;
@a=glob<>;
for(;$r<$n;$r++){
  $x^=$a[$r];
  $s+=$a[$r];
  while($x<$s){
    $x^=$a[$l];
    $s-=$a[$l++]
  }
  $\+=$r-$l+1
}
print

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

int main() {
	int N;
	cin >> N;
	vector<int> a(3*N,0);
	long long max=0;
	for (int i = 0; i < 3 * N; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	for (int i = N; i < 3 * N; i += 2) {
		max += a[i];
	}
	cout << max;

}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int p[10];
int n,m;
int ans=0;
vector<vector<bool>> a(10,vector<bool>(10,false));

void dfs(int pos,int mask){
	if(pos==n){
		if(p[0]==0){
			bool flg=true;
			rep(i,n-1){
				if(!(a[p[i]][p[i+1]] || a[p[i+1]][p[i]])) flg=false;
			}
			if(flg) ans++;
		}
		return;
	}
	rep(i,n){
		if(mask&(1<<i)){
			p[pos]=i;
			dfs(pos+1,(mask^(1<<i)));
		}
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	rep(i,m){
		int x,y;
		cin >> x >> y;
		x--;
		y--;
		a[x][y]=true;
		a[y][x]=true;
	}
	dfs(0,(1<<n)-1);
	cout << ans << endl;
}

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

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, A[10][10];
  while(cin >> N, N) {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        cin >> A[i][j];
      }
    }
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        A[i][j] = max(A[i][j], A[j][i]);
      }
    }

    int ret = INF;
    vector< int > s(N), p(N, 0);
    iota(begin(s), end(s), 0);
    int loop = 0;
    do {
      if(loop++ >= 3000000) break;
      int i = 1;
      while(i < s.size()) {
        p[i] = 0;
        for(int j = i - 1; j >= 0; j--) {
          p[i] = max(p[i], A[s[j]][s[i]] + p[j]);
        }
        if(p[i++] >= ret) break;
      }
      ret = min(ret, p.back());
    } while(next_permutation(begin(s), end(s)));

    cout << ret << endl;
  }
}

Measured memory_bytes: 3056
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());

    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

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

using namespace std;

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

const int maxn=4e3+5;

const ll mod=998244353;

int a[maxn],b[maxn];

int dp[maxn][maxn];

int dp2[maxn][maxn];

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",a+i,b+i);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i][j]=dp[i-1][j];
		}
		for(int j=a[i];j<=m;j++){
			dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+b[i]);
		}
	}
	
	for(int i=n;i>=1;i--){
		for(int j=0;j<=m;j++){
			dp2[i][j]=dp2[i+1][j];
		}
		for(int j=a[i];j<=m;j++){
			dp2[i][j]=max(dp2[i][j],dp2[i+1][j-a[i]]+b[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m-1;j++){
			ans=max(ans,b[i]+dp[i-1][j]+dp2[i+1][m-j-1]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 96512
#include "bits/stdc++.h"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;

using namespace std;
using ll = long long;

ll cnt(ll a, ll mod)
{
  return (mod*(a/(mod << 1)) + std::max(0LL, a%(mod << 1)-mod));
}


void Main()
{
  ll A, B;
  cin >> A >> B;

  bitset<40> bit(0);
  int i=0;
  for(ll mod=1LL;mod<=B;mod<<=1)
  {
    if((cnt(B+1,mod) - cnt(A,mod))%2)
    {
      bit.flip(i);
    }
    i++;
  }
  cout << bit.to_ulong() << endl;
}

int main()
{
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
class Program
{
    static void Main()
    {
        //int[] input = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
        //int input=int.Parse(Console.ReadLine());
        string a = Console.ReadLine();
        Console.WriteLine(a.Contains("a")&& a.Contains("b") && a.Contains("c") ?"Yes":"No");
        Console.ReadLine();
    }
}


Measured memory_bytes: 11092
N, L = list(map(int, input().split()))

A = [0]*N
sm = 0
m = -100
for i in range(N):
    A[i] = L+i
    sm+= L+i
    if L+i == 0:
        m = i 

if m >=0:
    print(sm)
elif L > 0:
    print(sm-A[0])
elif L+N-1 <0:
    print(sm-A[-1])

Measured memory_bytes: 3064
#include<cstdio>
using namespace std;
int main(void)
{
	int a[5],gou,hei,i;
	gou=0;
	for(i=0;i<5;i++){
		scanf("%d",&a[i]);
		if(a[i]<40){
			a[i]=40;
		}
		gou+=a[i];
	}
	hei=gou/5;
	printf("%d\n",hei);
	return 0;
}

Measured memory_bytes: 1028
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
int ar[200005]={0},lmax[200005]={0},rmax[200005]={0};
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    int a;
    cin>>a;
    ar[i]=a;
    lmax[i]=max(lmax[i-1],a);
  }
  for(int i=n;i>0;i--) rmax[i]=max(rmax[i+1],ar[i]);
  for(int i=1;i<=n;i++) cout<<max(lmax[i-1],rmax[i+1])<<endl;
}


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

int main(){
        int time;
        int h,m,s;

        cin >> time;

        h = time / 3600;
        m = (time - (h * 3600)) / 60;
        s = time - (h * 3600) - (m * 60);

        cout << h << ":" << m << ":" << s << endl;

        return 0;
}

Measured memory_bytes: 1164
from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

l,r,d = NextInts()

ans = 0
for i in range(l,r+1):
    if i%d == 0:
        ans += 1
print(ans)

Measured memory_bytes: 9280
#include <iostream>
#include <string>

using namespace std;

bool kind_a(string str){
	
	if(str[0] != '>' || str[1] != '\'' || str[str.size()-1] != '~'){
		return false;
	}
	
	string su = str.substr(2, str.size()-3);
	
	if(su.size()<3)
		return false;
	
	for(int i=0; i<su.size(); ++i){
		
		int j = su.size()-1-i;
		
		if(i>=j)
			break;
			
		if(su[i]!='=' || su[i]!=su[j]){
			return false;
		}	
	}
	
	return su[(su.size()-1)/2]=='#';
}

bool kind_b(string str){
		
	if(str[0] != '>'  || str[1] != '^' || 
		str[str.size()-2] != '~' || str[str.size()-1] != '~'){
		return false;
	}
	
	string su = str.substr(2, str.size()-4);
	
	if(su.size()<2)
		return false;
	
	for(int i=0; i<su.size(); ++i){
		
		int j = su.size()-1-i;
		
		if(i>=j)
			break;
			
		if( !(su[i]=='Q' && su[j]=='=' || su[j]=='Q' && su[i]=='=') ){
			return false;
		}
	}
	
	return true;
}

string solve(string str){
	
	if(kind_a(str)){
		return "A";
	}
	else if(kind_b(str)){
		return "B";
	}
	else{
		return "NA";
	}
}


int main(){

	int n;
	cin>>n;
	
	while(n--){
		
		string str;
		cin>>str;
		cout << solve(str) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1212
module.exports=function(r){var e={};function t(n){if(e[n])return e[n].exports;var o=e[n]={i:n,l:!1,exports:{}};return r[n].call(o.exports,o,o.exports,t),o.l=!0,o.exports}return t.m=r,t.c=e,t.d=function(r,e,n){t.o(r,e)||Object.defineProperty(r,e,{enumerable:!0,get:n})},t.r=function(r){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(r,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(r,"__esModule",{value:!0})},t.t=function(r,e){if(1&e&&(r=t(r)),8&e)return r;if(4&e&&"object"==typeof r&&r&&r.__esModule)return r;var n=Object.create(null);if(t.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:r}),2&e&&"string"!=typeof r)for(var o in r)t.d(n,o,function(e){return r[e]}.bind(null,o));return n},t.n=function(r){var e=r&&r.__esModule?function(){return r.default}:function(){return r};return t.d(e,"a",e),e},t.o=function(r,e){return Object.prototype.hasOwnProperty.call(r,e)},t.p="",t(t.s=0)}([function(r,e,t){t(1)(t(2).readFileSync("/dev/stdin","UTF-8"))},function(r,e){function t(r,e){return function(r){if(Array.isArray(r))return r}(r)||function(r,e){var t=[],n=!0,o=!1,u=void 0;try{for(var i,l=r[Symbol.iterator]();!(n=(i=l.next()).done)&&(t.push(i.value),!e||t.length!==e);n=!0);}catch(r){o=!0,u=r}finally{try{n||null==l.return||l.return()}finally{if(o)throw u}}return t}(r,e)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance")}()}r.exports=function(r){for(var e=r.split("\n"),n=t(e[0].split(" ").map(function(r){return Number(r)}),2),o=n[0],u=n[1],i=new Array(o),l=0;l<o-1;l++){var a=t(e[l+1].split(" ").map(function(r){return Number(r)-1}),2),f=a[0],c=a[1];i[f]||(i[f]=[]),i[c]||(i[c]=[]),i[f].push(c),i[c].push(f)}for(var p=new Array(o).fill(0),y=0;y<u;y++){var s=t(e[y+o].split(" ").map(function(r){return Number(r)}),2),d=s[0],v=s[1];p[d-1]+=v}for(var b=[0],m=new Array(o).fill(0),h=0;h<b.length;){var x=b[h];h+=1,m[x]=1;var g=!0,j=!1,w=void 0;try{for(var S,O=i[x][Symbol.iterator]();!(g=(S=O.next()).done);g=!0){var _=S.value;1!=m[_]&&(p[_]+=p[x],b.push(_))}}catch(r){j=!0,w=r}finally{try{g||null==O.return||O.return()}finally{if(j)throw w}}}console.log(p.join(" "))}},function(r,e){r.exports=require("fs")}]);

Measured memory_bytes: 129400
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int t = 0;

        if(a > b) {
            t = a;
            a = b;
            b = t;
        } if(b > c){
            t = b;
            b = c;
            c = t;
        } if(a > b){
            t = a;
            a = b;
            b = t;
        }
            System.out.println(a + " " + b + " " + c);

    }
}


Measured memory_bytes: 26100
using System;

class Program
{
    static void Main(string[] args)
    {
        //標準入力の値を取得
        int inval = int.Parse(Console.ReadLine());

        int checkval = (inval % 100) % 10;
        string outval = "";
        switch (checkval)
        {
            case 2:
            case 4:
            case 5:
            case 7:
            case 9:
                outval = "hon";
                break;

            case 0:
            case 1:
            case 6:
            case 8:
                outval = "pon";
                break;
            
            case 3:
                outval = "bon";
                break;
        }

        //出力
        Console.WriteLine(outval);
    }
}



Measured memory_bytes: 27540
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
static const long long INF = 1000000;
using p = pair<int64_t,int64_t>;
int main(){
    int n;
    cin >> n;
    map<string,int> mp;
    rep(i,n){
        string s;
        cin >> s;
        mp[s] ++;
    }
    int mx = 0;
    for (auto v : mp){
        if (v.second > mx){
            mx = v.second;
        }
    }
    for (auto v : mp){
        if (v.second == mx){
            cout << v.first << endl;
        }
    }
}

Measured memory_bytes: 19204
#include <bits/stdc++.h>
using namespace std;
bool prime[10000001];
int main() {
    for(long long int i=3;i<3162;i++)if(!prime[i])for(long long int j=i*2;j<10000001;j+=i)prime[j]=1;
    int n;
    while(cin>>n,n){
        if(n%2==0)n--;
        for(;;n-=2){
            if(!prime[n]&&!prime[n-2]&&!prime[n-6]&&!prime[n-8]){
                cout<<n<<endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 10924
//I am so vegetable
//#define _LOCAL_
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PB push_back
#define IN insert
#define CT count
#define EP empty
#define _for(i,a,b) for(ll i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll N = 2e5 + 5;
const int MOD = 998244353;
const double eps = 1e-6;
const double pi = acos(-1);
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
ll qpow(int x, int y) { ll ans = 1; for (; y; y >= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
int main(){
	FIO;
	double l;
    cin>>l;
    l/=3;
    l=l*l*l;
    cout<<fixed<<setprecision(12)<<l;
	return 0;
}

Measured memory_bytes: 256