akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
int N;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    if(N==3){
        cout <<2<<" "<<5<<" "<<63<<"\n";
        return 0;
    }
    else{
        if(N%2==0){
            vector<int> v;
            v.pb(3);
            v.pb(9);
            v.pb(2);
            v.pb(4);
            rep(i,0,min((N-4)/2,4999)){
                v.pb(6*(i+1)+2);
                v.pb(6*(i+1)+4);
            }
            rep(i,0,max(0,min((N-4)/2-4999,2499))){
                v.pb(12*(i+1)+3);
                v.pb(12*(i+1)+9);
            }
            rep(i,0,max(0,(N-4)-14996)){
                v.pb(6*(i+1));
            }
            rep(i,0,N){
                if(i==N-1) cout <<v[i]<<"\n";
                else cout <<v[i]<<" ";
            }
        }
        else{
            vector<int> v;
            v.pb(3);
            v.pb(9);
            v.pb(2);
            v.pb(4);
            rep(i,0,min((N-4)/2,4999)){
                v.pb(6*(i+1)+2);
                v.pb(6*(i+1)+4);
            }
            rep(i,0,max(0,min(2499,(N-4)/2-4999))){
                v.pb(12*(i+1)+3);
                v.pb(12*(i+1)+9);
            }
            rep(i,0,max(1,(N-4)-14996)){
                v.pb(6*(i+1));
            }
            rep(i,0,N){
                if(i==N-1) cout <<v[i]<<"\n";
                else cout <<v[i]<<" ";
            }
        }
    }
}

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

#define CFOR(i, str) for(int i = 0; (str)[i]!='\0'; (i)++)
#define FOR(i, s, r) for(int i = (s); i < (r); i++)
#define INF 1e9
#define NINF -1e9
#define SUM(a) accumulate(a.begin(), a.end(), 0)
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v) sort(v.rbegin(), v.rend())
#define vmax(v) *max_element(v.begin(), v.end())
#define vmin(v) *min_element(v.begin(), v.end())
#define cnt(v, n) count(v.begin(), v.end(), (n))
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vpic vector<pair<int, char>>
#define mp make_pair

typedef long long ll;
typedef unsigned long long ulld;

using namespace std;

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


void solve(){
    int n, k;
    cin>>n>>k;
    int arr[n];
    FOR(i, 0, n){
        cin>>arr[i];
    }
    vi dp(n, INF);
    // FOR(i, 0, n) cout<<dp[i]<<" ";

    dp[0] = 0;
    dp[1] = abs(arr[1] - arr[0]);
    FOR(i, 2, n){
        FOR(j, 1, k+1){
            if((i-j) >= 0){
                dp[i] = min(dp[i], dp[i-j] + abs(arr[i] - arr[i - j]));
                // cout<<dp[i];
            }
            else break;
        }

    }
    // FOR(i, 0, n) cout<<dp[i]<<" ";
    cout<<dp[n-1];
}

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

    // // COMMENT BEFORE SUBMISSION /////////////////////////////////////////////////
    // clock_t start = clock();
    // //

    // int t;
    // cin>>t;

    // while(t--){
        solve();
    // }

    // //COMMENT BEFORE SUBMISSION /////////////////////////////////////////////////
    // clock_t stop = clock();
    // double elapsed = (double) (stop - start) / CLOCKS_PER_SEC;
    // cout<<setprecision(5)<<fixed;
    // cout<<"\nProcess finished in: "<<elapsed<<"s\n";
    
    return 0;

}



Measured memory_bytes: 3988
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<par<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

int n;
vector<vi> g;
vi c;
vi d;
int cnt;

void dfs(int pos){
    d[pos]=c[cnt++];
    for(int v:g[pos]){
        if(d[v]!=-1)continue;
        dfs(v);
    }
}

void run(){
    cin>>n;
    g.resize(n);
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        a--,b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    c.resize(n);
    int s=0;
    rep(i,n){
        cin>>c[i];
        s+=c[i];
    }
    RSORT(c);
    s-=c[0];
    d.resize(n);
    fill(all(d),-1);
    dfs(0);
    cout<<s<<endl;
    rep(i,n)cout<<d[i]<<sp;
    cout<<endl;
}

Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[500],b[500];
int calc(int n, int t){
  int u=0,l=0,i;
  for(i=0;i<n;i++){
    b[i]=a[i]%t;
    l+=b[i];
  }
  sort(b,b+n,greater<int>());
  if(b[0]==0)
    return 0;
  for(i=0;i<n;i++){
    l-=b[i];
    u+=t-b[i];
    if(l==u)
      break;
  }
  return u;
}
int main()
{
  int n,k,s=0,m,t,u,i;
  cin >> n >> k;
  for(i=0;i<n;i++){
    cin >> a[i];
    s+=a[i];
  }
  m=(int)sqrt(s)+1;
  for(i=1;i<=m;i++){
    if(s%i>0)
      continue;
    t=s/i;
    if(t<i)
      break;
    u=calc(n,t);
    if(u<=k){
      cout << t << endl;
      return 0;
    }
  }
  for(i=m;i>0;i--){
    if(s%i>0||s/i<i)
      continue;
    u=calc(n,i);
    if(u<=k){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 3580
/* ****GT_18**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define W  100005
#define N  105

ll n;
ll w;
ll wts[N];
ll vals[N];
ll dp[W][N];

ll solve(ll rem, ll item){
	if(dp[rem][item]!=-1)return dp[rem][item];
	ll choose = -1;
	if(item==n){
		return 0;
	}
	if(rem-wts[item]>=0){
		choose=solve(rem-wts[item],item+1)+vals[item];
	}
	ll notchoose = solve(rem,item+1);
	return dp[rem][item]=max(choose,notchoose);
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	rep(i,0,W)rep(j,0,N)dp[i][j]=-1;
	while(TESTS--)
	{
			cin>>n>>w;
			rep(i,0,n){
				cin>>wts[i]>>vals[i];
			}
			cout<<solve(w,0)<<endl;
	}
	return 0;
}

Measured memory_bytes: 85648
#include <stdlib.h>
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>



int main()
{
    
   char str ;
   scanf("%c",&str);
   
   int d = str;
   
   if (d>=65 && d<=92) printf("A");
   else printf("a");


   return 0;
}

Measured memory_bytes: 1592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    int n, k; cin >> n >> k;
    vector<char> d(k);
    rep(i,k) cin >> d[i];
    for(int i = n; ; i++){
        bool isOK = true;
        string s = to_string(i);
        for(int j = 0; j < s.size(); j++){
            for(int l = 0; l < k; l++){
                if(s[j] == d[l]) isOK = false;
            }
        }
        if(!isOK) continue;
        else {
            cout << i << endl;
            return 0;
        }
    }
}

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

using CP = complex<long double>;
#define X real()
#define Y imag()
const long double PI = acos(-1);
const long double EPS = 1e-10;
// conj(x) : complex conjugate,(0,1)->(0,-1)
// abs(x) : dist between(0,0) and x
// norm(x) : abs(x) * abs(x)
// arg(x) : argment
long double dot(CP a, CP b) { return (a * conj(b)).X; }
long double cross(CP a, CP b) { return (a * conj(b)).Y; }
long double corner(CP a, CP b) {
  //[0,pi]
  return acos(dot(a, b) / (abs(a) * abs(b)));
}

CP intersection(CP a, CP b, CP c, CP d) {
  return a + (b - a) * (cross(d - c, c - a) /
                        cross(d - c, b - a));
}

bool on_seg(CP a, CP b, CP p) {
  // if not use end point, dot(a - p, b - p) < 0
  return abs(cross(a - p, b - p)) <= 1e-10 &&
         dot(a - p, b - p) <= 0;
}

// crossing lines? (a,b) and (c,d)
bool iscross(CP a, CP b, CP c, CP d) {
  // parallel
  if(abs(cross(a - b, c - d)) <= 1e-10) {
    return on_seg(a, b, c) || on_seg(a, b, d) ||
           on_seg(c, d, a) || on_seg(c, d, b);
  }
  CP isp = intersection(a, b, c, d);
  return on_seg(a, b, isp) && on_seg(c, d, isp);
}

struct line {
  CP s, t;
  bool l;
};

line newline;

bool operator<(const line &l, const line &r) {
  CP pl = intersection(newline.s, newline.t, l.s, l.t),
     pr = intersection(newline.s, newline.t, r.s, r.t);
  return abs(pl - newline.s) < abs(pr - newline.s);
}

int n, t;
vector<line> v;

int solve();

int main() {
  cin >> t;
  while(t--) {
    long double a, b, c, d;
    cin >> a >> b >> c >> d >> n;
    newline.s = CP(a, b);
    newline.t = CP(c, d);
    v.clear();
    for(int i = 0; i < n; ++i) {
      bool o, l;
      cin >> a >> b >> c >> d >> o >> l;
      if(iscross(newline.s, newline.t, CP(a, b), CP(c, d)))
        v.push_back({CP(a, b), CP(c, d), o ^ l});
    }
    cout << solve() << endl;
  }
  return 0;
}

int solve() {
  int ans = 0;
  sort(v.begin(), v.end());
  for(int i = 1; i < v.size(); ++i)
    if(v[i].l ^ v[i - 1].l) ++ans;
  return ans;
}


Measured memory_bytes: 3244
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()
#define tpl(...) make_tuple(__VA_ARGS__)

typedef long long LL;
typedef pair<int, int> P; typedef pair<int, P> IP; typedef pair<P, P> PP;
typedef vector<int> Array; typedef vector<vector<int> > Array2;
typedef vector<LL> LArray; typedef vector<P> PArray; typedef vector<string> SArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

inline int getInt() { int itiv; return (cin >> itiv, itiv); }
template <typename T> void readAll(vector<T>& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i]; }
template <typename T, typename U> void readAll(vector<pair<T, U> >& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i].first >> vec[i].second; }
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };
inline bool between(int min, int max, int n) { return min <= n && n <= max; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int dr[] = { 0, -1, 0, 1 }, dc[] = { -1, 0, 1, 0 };

int m, n;

int main(void)
{
	ios::sync_with_stdio(false);
	while(cin >> n && n)
	{
		int a = 0, b = 0;
		for (int i = 0; i < n; i++)
		{
			int ta, tb;
			cin >> ta >> tb;
			if(ta == tb) {}
			else if(ta > tb)
			{
				ta += tb;
				tb = 0;
			}
			else
			{
				tb += ta;
				ta = 0;
			}
			a += ta;
			b += tb;
		}

		cout << a << ' ' << b << endl;
	}
	return 0;
}

Measured memory_bytes: 1192
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;

#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)
const int N = (int) 1e6 + 6, mod = 0;

int h[N], res, k, n, d[N];
vector<int> adj[N];

void dfs(int v) {
    for (int u : adj[v]) {
        d[u] = d[v] + 1;
        dfs(u);
//        cout << " hi " << v << " - > " << u << endl;
        h[v] = max(h[u] + 1, h[v]);
    }
//    cout << v << ' ' << d[v] << ' ' << h[v] << ' ' << k << endl;

    if (v != 0 && d[v] > 1 && (h[v] % k) == k - 1) {
        res++;
        h[v] = -1;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x; --x;
        if (i > 0) {
            adj[x].push_back(i);
            if (k == 1) res += (x != 0);
        } else {
            res += (x != 0);
        }
    }
    if (k == 1) {
        cout << res << '\n';
        return 0;
    }
    dfs(0);
    cout << res << '\n';
}





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

int main() {
    int N;
    cin >> N;
    vector<ll> a(N);
    for (int i=0; i<N; i++) {
        cin >> a.at(i);
    }

    ll count = 0;
    for (int i=0; i<N; i++) {
        while (a.at(i)%2 == 0) {
            a.at(i) /= 2;
            count++;
        }
    }
    
    
    
    cout << count << endl;
}

Measured memory_bytes: 3712
#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--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    cout << n*n*n << endl;
}


Measured memory_bytes: 256
r,c=gets.split.map(&:to_i)
seet=[]
r.times do
    seet.push(gets.split.map(&:to_i))
end
2.times do 
    seet.each do |s|
        s.push(s.inject{|a,b|a+b})
    end
    seet=seet.transpose
end
seet.each do |nums|
    puts nums.join(" ")
end



Measured memory_bytes: 7256
#include <bits/stdc++.h>
#define  ll      long long 
#define  int     ll 
#define  mod     1000000007
#define  pb      push_back
#define  pob     pop_back
#define  f1      first
#define  s2      second
#define  N       102
#define  K       100005
#define  bol     (int)ceil((say-1)/2.0)
#define  PII     pair<int,int>
#define  PIII    pair<int,PII>
#define  PIIII   pair<PII,PII>
#define  PIIIII  pair<PIII,PII>
#define  PIIIIII pair<PIII,PIII>

using namespace std;

int n,k,dp[N][K],dizi[N],pre[N][K];
int32_t main(){
	// freopen("a.gir","r",stdin);		
    // freopen("a.cik","w",stdout);
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&dizi[i]);
	}
	for(int i=0;i<=n;i++){
		dp[i][0]=1;
		pre[i][0]=1;
	}
	for(int j=1;j<=k;j++){
		dp[1][j]=((j<=dizi[1])?1:0);
		pre[1][j]=pre[1][j-1]+dp[1][j];
		for(int i=2;i<=n;i++){
			dp[i][j]=pre[i-1][j];
			if(j>dizi[i]){
				dp[i][j]-=pre[i-1][(j-dizi[i])-1];
				dp[i][j]+=mod;
				dp[i][j]%=mod;

			}
			pre[i][j]=((pre[i][j-1]+dp[i][j])%mod);
			pre[i][j]%=mod;
		}
	}
	/*for(int i=0;i<=n;i++){
		printf("%lld ",dp[i][1] );
	}
	printf("\n");*/
	printf("%lld\n", dp[n][k]);
}

Measured memory_bytes: 158080
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
using namespace std;typedef long long ll;typedef double ld;int INF=0x3f3f3f3f;int INF2=0x7fffffff;ll LNF=0x3f3f3f3f3f3f3f3f;ll LNF2=0x7fffffffffffffff;
typedef pair<ll,int> pli;

#define Mod 1000000007
int n,m;
int S,T;
ll Ans;
int U[200001],V[200001],D[200001];
int h[100001],nxt[400001],to[400001],w[400001],tot;
void ins(int x,int y,int z){nxt[++tot]=h[x];to[tot]=y;w[tot]=z;h[x]=tot;}

ll d1[100001],d2[100001],g1[100001],g2[100001];bool v1[100001],v2[100001];
priority_queue<pli,vector<pli>,greater<pli> > pq;

void Dij(ll*d,ll*g,bool*v,int s){
	d[s]=0ll;
	pq.push(pli(0ll,s));
	g[s]=1;
	while(!pq.empty()){
		pli P=pq.top(); pq.pop();
		int u=P.second; ll du=P.first;
		if(v[u]||d[u]<du) continue;
		v[u]=1;
		eF(i,u){
			if(d[to[i]]==du+w[i])
				g[to[i]]=(g[to[i]]+g[u])%Mod;
			if(d[to[i]]>du+w[i])
				g[to[i]]=g[u],
				d[to[i]]=du+w[i], pq.push(pli(d[to[i]],to[i]));
		}
	}
}

int main(){
	int x,y,z;
	scanf("%d%d",&n,&m);
	scanf("%d%d",&S,&T);
	F(i,1,m) scanf("%d%d%d",&x,&y,&z), ins(x,y,z), ins(y,x,z), U[i]=x, V[i]=y, D[i]=z;
	memset(d1,0x3f,sizeof d1);
	Dij(d1,g1,v1,S);
	memset(d2,0x3f,sizeof d2);
	Dij(d2,g2,v2,T);
	ll Dist=d1[T];
	Ans=g1[T]*g1[T]%Mod;
	F(i,1,n){
		if(d1[i]+d2[i]==Dist&&d1[i]==d2[i])
			Ans=(Ans-g1[i]*g1[i]%Mod*g2[i]%Mod*g2[i]%Mod)%Mod;
	}
	int u,v,d;
	F(i,1,m){
		u=U[i], v=V[i], d=D[i];
		if(d1[u]+d+d2[v]==Dist && d1[u]+d>d2[v] && d2[v]+d>d1[u]){
			Ans=(Ans-g1[u]*g2[v]%Mod*g1[u]%Mod*g2[v]%Mod)%Mod;
		}
		u=V[i], v=U[i], d=D[i];
		if(d1[u]+d+d2[v]==Dist && d1[u]+d>d2[v] && d2[v]+d>d1[u]){
			Ans=(Ans-g1[u]*g2[v]%Mod*g1[u]%Mod*g2[v]%Mod)%Mod;
		}
	}
	printf("%lld",(Ans%Mod+Mod)%Mod);
	return 0;
}

Measured memory_bytes: 12656
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
//#define int   long long
#define ll   long long
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int>
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double

int main()
{
	FAST;
	ll n,i;
	cin >> n;
	ll h[n];
	fr(i,0,n)
		cin >> h[i];
	ll dp[n];
	dp[0] = 0;
	dp[1] = abs(h[1] - h[0]);
	fr(i,2,n)	
		dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i] - h[i-2])); 
	cout << dp[n-1];
}


Measured memory_bytes: 1792
import itertools

def find_eq(abcd):
    a,b,c,d = abcd
    ops = ['+', '-']
    for op1, op2, op3 in itertools.product(ops, repeat=3):
        eq = a + op1 + b + op2 + c + op3 + d
        if eval(eq) == 7:
            return eq + '=7'

print(find_eq(input()))

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

int main() {
  int A, B; cin >> A >> B;
  int cnt = 1;
  int ans = 0;
  rep(i, 100) {
    if (cnt < B) {
      cnt--;
      cnt += A;
      ans++;
    }
    if (cnt >= B) {
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main ()
{
  int x,y;
  vector<int> tx,ty;
  vector<int> v(16010,0);
  vector<vector<int> > vv(4010,v);
  vector<vector<int> > vv2(vv);
  int count = 0 , w = 0;
  bool memo;
  char c;
  bool q = false;
  scanf("%c",&c);
  if (c == 'T'){
    w+=1;
  }
  else{
    q = true;
    count += 1;
  }
  while(true){
    scanf("%c",&c);
    if (c == 'F'){
      count += 1;
    }
    else if (c == 'T'){
      if(count != 0){
        if(w%2 == 0){
          tx.push_back(count);
        }
        else{
          ty.push_back(count);
        }
        count = 0;
        }
      w+=1;
    }
    else if (c == '\n'){
      if(count != 0){
        if(w%2 == 0){
          tx.push_back(count);
        }
        else{
          ty.push_back(count);
        }
      }
      break;
    }
  }
  pair<vector<int>,vector<int> > pv = make_pair(tx,ty);
  cin >> x >> y;
  pair<int,int> p = make_pair(x,y);
  vv[0][8000] = 1;
  for(int j=0;j<pv.first.size();j++){
    if (j == 1 && q){
      vv[j][8000-pv.first[j-1]] = 0;
    }
    for(int k=0;k<16000;k++){
      if (vv[j][k]==1){
        vv[j+1][k+pv.first[j]] = vv[j+1][k-pv.first[j]] = 1;
        }
      }
    }
  if (q){
    vv[1][8000 -pv.first[0]] = 0;
  }
  if (vv[pv.first.size()][x+8000] == 1){
    memo = true;
  }
  else{
    memo = false;
  }
  vv = vv2;
  vv[0][8000] = 1;
  for(int j=0;j<pv.second.size();j++){
    for(int k=0;k<16000;k++){
      if (vv[j][k]==1){
        vv[j+1][k+pv.second[j]] = vv[j+1][k-pv.second[j]] = 1;
      }
    }
  }
  if(vv[pv.second.size()][y+8000] == 1 && memo){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 502152
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//breadth first search

int main() {
	int n, u, k, v;
	vector< vector< int > > list;
	vector< int > dist;
	queue< int > que;
	
	cin >> n;
	list.resize(n);
	dist.resize(n);
	
	for(int i=0;i<n;++i){
		cin >> u >> k;
		dist[i] = -1;
		
		for(int j=0;j<k;++j){
			cin >> v;
			list[u-1].push_back(v-1);
		}
	}
	
	que.push(0);
	dist[0] = 0;
	
	while(!que.empty()){
		int cur = que.front();
		vector< int > branch = list[cur];
		que.pop();
		
		for(vector< int >::iterator it=branch.begin();it<branch.end();++it){
			if(dist[*it] == -1){
				que.push(*it);
				dist[*it] = dist[cur] + 1;
			}
		}
	}
	
	for(int i=0;i<n;++i){
		cout << i+1 << " " << dist[i] << endl;
	}
	
	return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i=0; i<N; ++i) cin >> a[i];

    int M = 0, m = INF;
    vector<int> cnt(N);
    for (int x : a) {
        chmax(M, x);
        chmin(m, x);
        ++cnt[x];
    }
    if (m != (M+1) / 2) {
        cout << "Impossible" << '\n';
        return;
    }
    if ((M%2 == 0 && cnt[m] != 1) || (M%2 == 1 && cnt[m] != 2)) {
        cout << "Impossible" << '\n';
        return;
    }
    for (int i=M; i>m; --i) {
        if (cnt[i] < 2) {
            cout << "Impossible" << '\n';
            return;
        }
    }
    cout << "Possible" << '\n';
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3620
import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
    auto s = readln().split();
    assert(s.length == t.length);
    foreach(ref ti; t) {
        ti = s[0].to!(typeof(ti));
        s = s[1..$];
    }
}

const real eps = 1e-10;

const long p = 1_000_000_000 + 7;

bool ask(long n) {
    writeln("? ", n);
    stdout.flush();
    return readln.chomp() == "Y";
}

void main(){
    if(ask(10000000000)) {
        long n = 9;
        while(!ask(n)) {
            n *= 10;
            n += 9;
        }
        writeln("! ", (n+1) / 10);
        return;
    } else {
        long u = 10;
        long l = 0;
        while(u > l+1) {
            auto m = (u+l)/2;
            if(ask(pow(10, m))) {
                l = m;
            } else {
                u = m;
            }
        }
        long x = 0;
        foreach_reverse(i; iota(u)) {
            long y = pow(10L, i+1);
            if(i+1 != u && ask(x + y-1)) {
                continue;
            }
            auto uu = 9;
            auto ll = 0;
            while(uu > ll+1) {
                auto m = (uu+ll)/2;
                if(ask(x + y * m + y-1)) {
                    uu = m;
                } else {
                    ll = m;
                }
            }
            x += y * uu;
        }
        writeln("! ", x / 10);
    }
}



Measured memory_bytes: 596
// Author by Md. Jashim Uddin_RMSTU

#include<bits/stdc++.h>
using namespace std;
#define     sf(a)           scanf("%d",&a)
#define     sff(a,b)        scanf("%d %d",&a,&b)
#define     sfff(a,b,c)     scanf("%d %d %d",&a,&b, &c)
#define     pb              push_back
#define     ll              long  long
#define     fast            ios_base :: sync_with_stdio(false);cin.tie(0)
#define     pi              2*acos(0)
#define     sp              fixed<<setprecision
#define     lcm(a,b)        (a*b)/gcd(a,b)
#define     gcd(a,b)        _gcd(a,b)
#define     forn(i,n)       for(int i=1;i<=n;i++)
#define     min3(a,b,c)     min(a,min(b,c))
#define     M             32000
int main()
{


 int r;
   cin>>r;
   cout<<sp(20)<<abs(2*pi*r)<<endl;

}


Measured memory_bytes: 3780
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define lin puts("");
long double n,x,y,a[300000],b[300000],c=0,t=0,sum=0,z=0,i=0,j,f=0;
char ch[101],cr,ss[101];
string s;
int gcd(int,int);
int main()
{
    cin>>n;
    printf("%.24llf",2*acos(0)*2*n);
    return 0;
}


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

using namespace std;

#define M_DEBUG if (0)

struct PlayList {
    PlayList (string pTitle, int pTime) :
    title(pTitle), time(pTime)
    {}

    string title;
    int time;
};

/******************************************************************************
	Main
******************************************************************************/
int main()
{
    int n;
    cin >> n ;
    assert(n >= 1 && n <= 50);

    vector<PlayList> playlist;
    for (int i = 0; i < n; i++){
        string s;
        int t;
        cin >> s >> t ;
        assert(s.length() >= 1 && s.length() <= 100);
        assert(t >= 1 && s.length() <= 1000);

        playlist.push_back(PlayList(s, t));
    }

    string x;
    cin >> x;
    assert(x.length() >= 1 && x.length() <= 100);
    
    int ans = 0;
    bool sleeping = false;
    for (auto item : playlist) {
        M_DEBUG{ cout << item.title << ", " << item.time << endl; }
        if (item.title == x) {
            sleeping = true;
            continue;
        }
        if (!sleeping) continue;

        ans += item.time;
    }

    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<pair<ld,int>, null_type, less<pair<ld,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[100011];
ll b[100011];
ll c[100011];
const ld eps = 1e-11;
int timer=0;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
	ld lo = -ld(3e8); ld hi = ld(3e8);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	ll half = ((ll(n)*ll(n-1))/2 - 1)/2;
	ld X = 0;
	while(hi-lo>=eps)
	{
		ld mid = (lo+hi)*ld(0.5);
		//vector<ld> P,N;
		vector<pair<ld,ld> > neg;
		for(int i=0;i<n;i++)
		{
			ld M = (ld(-a[i])/ld(b[i]));
			ld C = ld(c[i])/ld(b[i]);
			neg.pb(mp(M, M*mid+C));
			/*
			if((a[i]*b[i])>0)
			{
				
				N.pb(M*mid+C);
			}
			else
			{
				//pos.pb(mp(M, M*mid+C));
				//P.pb(M*mid+C);
			}
			*/
		}
		sort(neg.begin(),neg.end());
		//sort(pos.begin(),pos.end());
		//sort(P.begin(),P.end());
		//sort(N.begin(),N.end());
		ll cnt = 0;
		pbds tmp;
		/*
		for(int i=0;i<pos.size();i++)
		{
			int val = tmp.order_of_key(mp(pos[i].se,-1));
			cnt += val;
			tmp.insert(mp(pos[i].se, ++timer));
		}
		tmp.clear();
		*/
		for(int i=0;i<neg.size();i++)
		{
			int val = tmp.order_of_key(mp(neg[i].se,-1));
			cnt += val;
			tmp.insert(mp(neg[i].se, ++timer));
		}
		if(cnt<=half)
		{
			lo = mid;
		}
		else
		{
			hi = mid;
		}
	}
	X = lo;
	ld Y = 0;
	lo = -ld(3e8); hi = ld(3e8);
	while(hi-lo>=eps)
	{
		ld mid = (lo+hi)*ld(0.5);
		//vector<ld> P,N;
		vector<pair<ld,ld> > neg;
		for(int i=0;i<n;i++)
		{
			ld M = (ld(-b[i])/ld(a[i]));
			ld C = ld(c[i])/ld(a[i]);
			neg.pb(mp(M, M*mid+C));
			/*
			if((a[i]*b[i])>0)
			{
				
				N.pb(M*mid+C);
			}
			else
			{
				//pos.pb(mp(M, M*mid+C));
				//P.pb(M*mid+C);
			}
			*/
		}
		sort(neg.begin(),neg.end());
		//sort(pos.begin(),pos.end());
		//sort(P.begin(),P.end());
		//sort(N.begin(),N.end());
		ll cnt = 0;
		pbds tmp;
		/*
		for(int i=0;i<pos.size();i++)
		{
			int val = tmp.order_of_key(mp(pos[i].se,-1));
			cnt += val;
			tmp.insert(mp(pos[i].se, ++timer));
		}
		tmp.clear();
		*/
		for(int i=0;i<neg.size();i++)
		{
			int val = tmp.order_of_key(mp(neg[i].se,-1));
			cnt += val;
			tmp.insert(mp(neg[i].se, ++timer));
		}
		if(cnt<=half)
		{
			lo = mid;
		}
		else
		{
			hi = mid;
		}
	}
	Y = lo;
	cout<<fixed<<setprecision(20)<<X<<' '<<Y<<'\n';
}


Measured memory_bytes: 9784
#include<stdio.h>
 
#define N 2000000
 
int arr[N];
int n;
 
void count(int A[], int k){
  int ca[k],i,j;
  for(i=0; i<k ; i++) ca[i] = 0;
  for(j=1; j<=n; j++) ca[A[j]]++;
  for(i=1; i<k; i++) ca[i] += ca[i-1];
  for(j=n; j>=1; j--){
    arr[ca[A[j]]] = A[j];
    ca[A[j]]--;
  }
}
 
int main(int argc,char *argv[]){
  int k=0,i;
  int A[N];
  scanf("%d",&n);
  for(i=1; i<=n; i++){
    scanf("%d",&A[i]);
  }
  k=A[1];
  for(i=2; i<=n; i++){
      if(k < A[i]) k = A[i];
  }
  count(A, k+1);
  for(i=1; i<n; i++) {
    printf("%d ",arr[i]);
  }
  printf("%d\n",arr[i]);
  return 0;
}

Measured memory_bytes: 16260
/**   Created by: Marcos Portales
          Codeforces User: marcosportales
          Country: Cuba
          Copyright                    */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
#define vi vector<int>
#define sz(a) int((a).size())
#define rep(i,x,y) for(int i=x;i<y;i++)
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 400010;
const int mod = 1000000007;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 2000000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return (pwur * pwur) % mod;
}
int modinv(int x){
    return qpow(x,mod-2);
}
/// My Code -------------------------------------------------

int a[101][101];

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));

    //freopen("a.in","r",stdin);
    //freopen("a.in","w",stdout);
    int a,b,x;
    cin>>a>>b>>x;
    if(b==0)cout<<1;
    else if(a==0)cout<<b/x+1;
    else {
        cout<<b/x-(a-1)/x;
    }
    return 0;
}


Measured memory_bytes: 3636
package main

import (
	"fmt"
)

func main() {
	var n, a, b int
	fmt.Scan(&n, &a, &b)

	cal := (b-a)*(n-2) + 1
	if cal < 0 {
		fmt.Print(0)
	} else {
		fmt.Print(cal)
	}
}


Measured memory_bytes: 512
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys
from collections import deque

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    s = input()
    l = len(s)
    odd = 0
    even =0

    for i in range(l):
        if (i + 1) % 2 == 0:
            even += int(s[i])
        else:
            odd += int(s[i])

    #even = 1
    a = (l // 2) - even + odd

    #odd = 1
    b = ((l+1) // 2) - odd + even

    print(min(a,b))


if __name__ == '__main__':
    main()


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

using namespace std;

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

    int x;
    cin >> x;

    if(x >= 30) {
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }

    return 0;
}


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

int main() {
    long long N, K;  cin >> N >> K;
    vector<int> f(N), f_cp(N);
    for (int i = 0; i < N; ++i) {
        cin >> f[i];
        --f[i];
        f_cp[i] = f[i];
    }

    int now = 0;
    while (K) {
        if (K & 1) now = f[now];
        for (int i = 0; i < N; ++i) f_cp[i] = f[f[i]];
        f = f_cp;
        K >>= 1;
    }

    cout << now + 1 << endl;
}


Measured memory_bytes: 4804
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
m = [[10**10]*N for i in range(N)]

for i in range(M):
  a, b, c = map(int, input().split())
  m[a-1][b-1] = c
  m[b-1][a-1] = c

for i in range(N):
  m[i][i] = 0

for i in range(N):
  for j in range(N):
    for k in range(N):
      m[j][k] = min(m[j][k], m[j][i] + m[i][k])

ans = 10**10
for l in itertools.permutations(r):
  cost = 0
  for i in range(1, R):
    cost += m[l[i-1]-1][l[i]-1]
  ans = min(ans, cost)

print(ans)

Measured memory_bytes: 46168
import java.util.Scanner;

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

		if (a < b && b < c)
			answer = "Yes";
		else
			answer = "No";

		System.out.println(answer);
	}
}

Measured memory_bytes: 26268
#include "iostream"
#include "random"
#include "string"
#include "bitset"
#include "algorithm"
#include "map"
#include "queue"
#include "list"
#include "climits"

using namespace std;


int main() {
	
	int dir_y[] = { 1,1,0,-1,-1,0 };
	int dir_x[] = { 0,1,1,0,-1,-1 };
	int N, K;
	list<int>ret;
	cin >> N >> K;
	while (N) {
		vector<vector<int>>v(1000, vector<int>(1000, INT_MAX));
		for (int i = 0; i < K; i++) {
			int y, x;
			cin >> y >> x;
			y += 500;
			x += 500;
			v[y][x] = -1;
		}
		int sy, sx;
		cin >> sy >> sx;
		sy += 500;
		sx += 500;
		queue<pair<int,int>>Q;
		Q.push({ sy,sx });
		v[sy][sx] = 0;
		int cnt = 0;
		while (cnt<=N&&!Q.empty()) {
			int cy = Q.front().first;
			int cx = Q.front().second;
			cnt = max(cnt, v[cy][cx] + 1);
			Q.pop();
			for (int i = 0; i < 6; i++) {
				int ny = cy + dir_y[i];
				int nx = cx + dir_x[i];
				if (v[ny][nx]>cnt) {
					v[ny][nx] = cnt;
					Q.push({ ny,nx });
				}
			}
		}
		int ans = 0;
		for (auto i : v) {
			for (auto j : i) {
				if (j >= 0 && j <= N) {
					ans++;
				}
			}
		}
		ret.push_back(ans);
		cin >> N >> K;
	}
	for (auto i : ret) {
		cout << i << endl;
	}
	return 0;
}


Measured memory_bytes: 6808
#include<iostream>

int main(){
    int n;
    std::cin >> n;
    int tmp = n;
    int sum = 0;
    while(tmp > 0){
        sum += tmp % 10;
        tmp /= 10;
    }
    if(n % sum == 0) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
    return 0;
}


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

#define INF (1<<60)

long long weight[100], value[100];

long long dp[110][100010]={0};	// [item][weight]


int main(){
	int n,w;	cin>>n>>w;
	for(int i=0;i<n;i++)	cin>>weight[i]>>value[i];

	for(int i=0;i<n;i++){
		for(int sum_w=0; sum_w<=w; sum_w++){
			
			// i番目を選ぶ場合
			if(sum_w - weight[i]>=0){
				dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-weight[i]] + value[i]);
			}

			// 選ばない場合
			dp[i+1][sum_w]=max(dp[i+1][sum_w], dp[i][sum_w]);

		}
	}

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


	return 0;
}


Measured memory_bytes: 79360
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S, W = MAP()
print("unsafe" if W >= S else "safe")

Measured memory_bytes: 10044
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
	int n,k,p,q,ans=0;
	cin>>n>>k;
	vector<int>t(n,1);
	rep(i,k){
	    cin>>p;
	    rep(j,p){
	        cin>>q;
	        t[q-1]=0;
	    }
	}
	rep(i,n)ans+=t[i];
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3624
using System;

class Program
{
    static void Main(string[] args)
    {
        var nw = Console.ReadLine().Split();
        var n = int.Parse(nw[0]);
        var W = int.Parse(nw[1]);

        var w = new int[n];
        var v = new int[n];
        for (int i = 0; i < n; i++)
        {
            var wv = Console.ReadLine().Split();
            w[i] = int.Parse(wv[0]);
            v[i] = int.Parse(wv[1]);
        }

        var dp = new long[n + 1, W + 1];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= W; j++)
            {
                if (w[i] <= j)
                {
                    dp[i + 1, j] = Math.Max(
                        dp[i, j],
                        dp[i, j - w[i]] + v[i]);
                }
                else
                {
                    dp[i + 1, j] = dp[i, j];
                }
            }
        }

        Console.WriteLine(dp[n, W]);
    }
}


Measured memory_bytes: 88800
#include <bits/stdc++.h>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(7)<<(x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define loop(i,a,b) for (int i=a; i<b; ++i)
using ll = long long;
const int mod = 998244353;
typedef pair<int , int> pairs;
typedef complex<ll> G;

const int N = 2e5 + 5;

int power(int a,int b){
    if(!b)
        return 1;
    int c=power(a,b/2);
    c=(1LL*c*c)%mod;
    if(b%2)
        c=(1LL*c*a)%mod;
    return c;
}


vector<int>adj[N];
vector<int>ans(N+1, 0);
void dfs(int s, int e) {
    ans[s] = 1;
    for(auto u : adj[s]) {
        if(u == e)continue;
        dfs(u, s );
        ans[s] += ans[u];
    }
}
void done() {

    int n;
    cin >> n;
    for(int i = 0;i < n-1;++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    dfs(1, 0);
    for(int i = 1;i < n+1;++i) {
        cout << ans[i] << " ";
    }


}

/*string solve_palindrome(const string& s)
{
    string a = s;
    reverse(a.begin(), a.end());
    //a = s + "#" + a;
    int c = 0;
    for (int i = 1; i < (int)a.size(); i++)
    {
        while (c != 0 && a[c] != a[i])
            c = pref[c - 1];
        if (a[c] == a[i])
            c++;
        pref[i] = c;
    }
    return s.substr(0, c);
}
*/


void solve()
{
    int n;
    cin >> n;
    vector<int>a(n);
    int d = 1e9 +1;
    for(int &c : a) {
        cin >> c;
        d = min(d, c);
    }
    bool ok = 1;
    for(int i = 1;i < n;++i)
        if(a[i - 1] > a[i])ok = 0;
    if(ok) {
        cout << "YES\n" << '\n';
        return;
    }


}

void another() {
    int h, w;
    cin >> h >> w;
    int cx, cy;
    int q, p;
    cin >> cx >> cy >> q >> p;
    --cx;
    --q;
    --p;
    --cy;
    vector<string>s(h);
    for(string &c : s) {
        cin >> c;
    }
    vector<vector<pair<int , int>>> adj(h * w * 2);
    vector<vector<int>>dis(h, vector<int>(w, -1));
    auto add = [&](int x, int y, int d) {
            if(x < 0 || x >= h || y <0 || y >= w)return;
            if(s[x][y] == '#')return;
            if(dis[x][y] >= 0 && d >= dis[x][y])return;
            dis[x][y] = d;
            adj[d].push_back({x, y});
    };
    add(cx, cy, 0);
    for(int d = 0;d +1 < adj.size();++d) {
        for(int close = 0;close < adj[d].size();++close) {
            int x = adj[d][close].first;
            int y = adj[d][close].second;
            for(int lx = -2;lx <= 2;++lx) {
                for(int ly = -2;ly <= 2;++ly) {
                    int ux = x + lx;
                    int uy = y + ly;
                    add(ux, uy, d + (abs(lx) + abs(ly) > 1 ? 1 : 0));
                }
            }
        }
    }
    cout << dis[q][p];



}
void test_case() {
    int t;
    cin >> t;
    while(t--)another();
}
int main() {

   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    another();
}


Measured memory_bytes: 67508
import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int w = sc.nextInt();
		int h = sc.nextInt();
		int n = sc.nextInt();

		boolean[][] wh = new boolean[h + 1][w + 1];

		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int a = sc.nextInt();

			for (int xx = 0; xx <= w; xx++) {
				for (int yy = 0; yy <= h; yy++) {
					if (a == 1 && xx < x) {
						wh[yy][xx] = true;
					} else if (a == 2 && xx >= x) {
						wh[yy][xx] = true;
					} else if (a == 3 && yy < y) {
						wh[yy][xx] = true;
					} else if (a == 4 && yy >= y) {
						wh[yy][xx] = true;
					}
				}
			}
		}

		int ret = 0;
		for (int xx = 0; xx < w; xx++) {
			for (int yy = 0; yy < h; yy++) {
				if (!wh[yy][xx]) {
					ret++;
				}
			}
		}

		pr.println(ret);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
vector<vector<pair<int,double>>> graph(1000010);
vector<double> d(1000010);
void dijkstra(int s){
    //(暫定コスト,頂点番号)のpairたち
    priority_queue<pair<double,int> ,vector<pair<double,int>>, greater<pair<double,int>>> que;
    rep(i,0,1000010) d[i]=1e18;
    d[s]=0;
    que.push(make_pair((double)0,s));
    
    while(!que.empty()){
        pair<double,int> p=que.top();
        que.pop();
        int  v=p.second; //
        if(d[v]<p.first) continue;
        
        rep(i,0,graph[v].size()){
            pair<int,double> e=graph[v][i];
            if(d[e.first]>d[v]+e.second){
                d[e.first]=d[v]+e.second;
                que.push(make_pair(d[e.first],e.first));
            }
        }
        
    }
}

int main(){
    double sx,sy,gx,gy;
    cin>>sx>>sy>>gx>>gy;
    int n;
    cin>>n;
    
    vector<tuple<double,double,double>> vertex(n+2);
    vertex[0]=make_tuple(sx,sy,(double)0);
    vertex[n+1]=make_tuple(gx,gy,(double)0);
    
    rep(i,0,n){
        double x,y,r;
        cin>>x>>y>>r;
        vertex[i+1]=make_tuple(x,y,r);
    }
    
    graph.resize(n+2);
    d.resize(n+2);
    
    rep(i,0,n+2){
        rep(j,0,n+2){
            if(i==j) continue;
            
            double x1,y1,r1,x2,y2,r2;
            tie(x1,y1,r1)=vertex[i];
            tie(x2,y2,r2)=vertex[j];
            
            double dist=max((double)0,sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2);
            graph[i].emplace_back(j,dist);
        }
    }
    
    dijkstra(0);
    cout<<fixed<<setprecision(10)<<d[n+1]<<endl;
    
}


Measured memory_bytes: 53488
PROGRAM ATCODER

implicit none
integer :: a,b,c,count

read(*,*) a,b,c    !ここが入力欄

count = 3
if(a==b .and. b==c)then
  count = 1
else if(a==b)then
  count = 2
else if(b==c)then
  count = 2
else if(a==c)then
  count = 2
end if

! ここに出力結果
write(*,'(i0)') count

contains
!!!!!! サブルーチンは↓

!!!!!!

END PROGRAM ATCODER


Measured memory_bytes: 384
n = int(input())
aaa = list(map(int, input().split(' ')))

ans = 0
mmm = int(1e9 + 7)
#for i in range(n):  # 1e5 ^ 2 なので...
#    for j in range(i+1, n):
#        ans = (ans + (aaa[i] ^ aaa[j])) % mmm

# 日本語的には自分より後ろのもの全部と xor を取った和

# 1 1 2 3 4 => 34
# 0 0 1
# 0 0 1
# 0 1 0 
# 0 1 1
# 1 0 0
#=======
# 4 2 1
#
# 4 * (4*1) + 2 * (3*2) * 1 * (2*3) = 34 (sum(ケタ * (0の数*1の数)) で合ってるっぽい?)
def get_bit_array(num):
    res = []
    while num > 0:
        res.append(num%2)
        num //= 2
    return res

bits = {}  # n がいくつあるか (n=1,2,4,8,...)
for i in range(n):
    t = aaa[i]
    bit_array = get_bit_array(t)
    r = 1
    for i in range(len(bit_array)):  # TLEかも
        bits[r] = bits.get(r, 0) + bit_array[i]
        r *= 2

# print(bits, n)
ans = 0
for k, v in bits.items():
    ans = (ans + k * (v * (n-v))) % mmm

print(ans)


Measured memory_bytes: 122652