akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

// find_by_order(k) returns the iterator to the kth largest element (start from 0)
// order_of_key(k) returns the number of elements in the set which are strictly less than the value k

using namespace std;
using namespace __gnu_pbds;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define rightmostbit(x) __builtin_ffsll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         cout << fixed; cout << setprecision(x); cout << y;
#define pi              3.141592653589793238
#define mk(a,n)         int n;cin>>n;vi a(n);for(int i=0;i<n;i++) cin>>a[i]
#define w(x)            int x; cin>>x; while(x--)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int dx2[] = { -1 , -1 , -1, 0 , 0 , 1 , 1 , 1};
int dy2[] = { -1 , 0 , 1 , -1, 1 , -1, 0, 1};

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void g_b()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
#endif
}
// 1, 1, 2, 5, 14, 42, 132, 429, 1430, CATALAN NUMBER
int32_t main()
{
	g_b();
	int a, b, c, d; cin >> a >> b >> c >> d;
	int ans = a * c;
	if (a <= 0 and c <= 0) ans = max(ans , a * c);
	if (b >= 0 && d >= 0) ans = max(ans, b * d);
	ans = max(ans, b * c), ans = max(ans, a * d);
	cout << ans;

	return 0;
}


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

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 2e3 + 5;

typedef long long ll;

int n, k, dist[N][N], ans;
vector <int> g[N];

void dfs(int v, int par = 0){
      for(int to : g[v]){
            if(to == par) continue;
            int res = 0;
            for(int i = 1; i <= n; i ++){
                  int d = min(dist[v][i] - 1, dist[to][i] - 1);
                  if(d <= k / 2 - 1) res ++;
            }
            ans = max(ans, res);
            dfs(to, v);
      }
}

int main(){
      scanf("%d %d", &n, &k);
      k ++;
      for(int i = 1; i < n; i ++){
            int x, y;
            scanf("%d %d", &x, &y);
            g[x].pb(y);
            g[y].pb(x);
      }

      for(int i = 1; i <= n; i ++){
            queue <int> q;
            q.push(i);
            dist[i][i] = 1;
            while(!q.empty()){
                  int v = q.front();
                  q.pop();
                  for(int to : g[v]){
                        if(dist[i][to]) continue;
                        dist[i][to] = dist[i][v] + 1;
                        q.push(to);
                  }
            }
      }

      if(k % 2){
            for(int i = 1; i <= n; i ++){
                  int res = 0;
                  for(int j = 1; j <= n; j ++){
                        if((dist[i][j] - 1) <= k / 2) res ++;
                  }
                  ans = max(ans, res);
            }
      } else {
            dfs(1);
      }

      printf("%d", n - ans);
}


Measured memory_bytes: 16256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=4e5+10;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
const int mod=1e9+7;
int fac[N],inv[N],e[N];
int head[N],nxt[N],to[N],w[N];
int siz[N],ans,f[N],V,E,C;
bool vis[N];
inline int binom(int n,int m) { return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod; }
inline void dfs(int k,int fa) {
	vis[k]=true;V++;
	for (int i=head[k];i;i=nxt[i],E++)
		if (!vis[to[i]])
			e[to[i]]=i^1,dfs(to[i],k);
		else if (to[i]!=fa) C=i;
}
inline void dp(int k,int e) {
	f[k]=1;siz[k]=0;
	for (int i=head[k];i;i=nxt[i])
		if (i/2!=C/2&&(i^1^e)) {
			dp(to[i],i);
			if (w[i]>w[e])
				ans=1LL*ans*inv[siz[to[i]]]%mod*f[to[i]]%mod;
			else
				f[k]=1LL*f[k]*f[to[i]]%mod*binom(siz[k]+=siz[to[i]],siz[to[i]])%mod;
		}
	siz[k]++;
}
int main()
{
	int n=gi()*2,i,tot=1,a,b,sum,k;
	
	for (i=fac[0]=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
	for (i=2,inv[0]=inv[1]=1;i<=n;i++) inv[i]=mod-1LL*(mod/i)*inv[mod%i]%mod;
	for (i=3;i<=n;i++) inv[i]=1LL*inv[i]*inv[i-1]%mod;
	
	for (i=1;i<=n;i++) {
		a=gi(),b=gi()+n/2;
		to[++tot]=b,nxt[tot]=head[a],head[a]=tot;
		to[++tot]=a,nxt[tot]=head[b],head[b]=tot;
		w[tot]=w[tot^1]=a+b;
	}

	int res=fac[n];
	for (k=1;k<=n;k++)
		if (!vis[k]) {
			V=E=C=0;
			dfs(k,0);
			if (V*2!=E) return puts("0"),0;
			for (a=to[C],b=to[C^1];a!=b;a=to[e[a]]) if (w[e[a]]>w[C]) C=e[a];
			ans=1;
			dp(to[C],C);
			sum=1LL*ans*inv[siz[to[C]]]%mod*f[to[C]]%mod;
			ans=1;
			dp(to[C^1],C);
			sum=(sum+1LL*ans*inv[siz[to[C^1]]]%mod*f[to[C^1]])%mod;
			res=1LL*res*sum%mod;
		}
	printf("%d\n",res);
	return 0;
}


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

#define ll long long int
#define vi vector<int>
#define vl vector<ll>

int main() {

    int N, K;
    cin >> N >> K;

    vi v;
    int tmp;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        v.push_back(tmp);
    }

    vi score;
    for (int k = 0; k <= min(K, N); k++) {
        for (int l = 0; l <= k; l++) {
            int sum = 0;
            vi getV;
            for (int i = 0; i < l; i++) {
                getV.push_back(v[i]);
            }
            for (int i = N - (k - l); i < N; i++) {
                getV.push_back(v[i]);
            }
            sort(getV.begin(), getV.end());

            for (int i = 0; i < min(K - k, (int) getV.size()); i++) {
                getV[i] = max(0, getV[i]);
            }
            for (int i = 0; i < getV.size(); i++) {
                sum += getV[i];
            }
            score.push_back(sum);
        }
    }

    cout << *max_element(score.begin(), score.end()) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

int N; LL M;
std::vector<LL> A;

LL Count(LL v) {
	LL count = 0;
  for (const LL Ax : A) {
		LL Ay = v - Ax;
		int idx = std::lower_bound(A.begin(), A.end(), Ay) - A.begin();
		count += N - idx;
	}
	return count;
}

LL Sum(int v) {
  std::vector<LL> As = A;
	for (int i = N-2; i >= 0; --i) As[i] += As[i + 1];

	LL sum = 0;
  for (const LL Ax : A) {
		LL Ay = v - Ax;
		int idx = std::lower_bound(A.begin(), A.end(), Ay) - A.begin();
		LL cnt = N - idx;
    if (cnt == 0) continue;

		sum += Ax * cnt;
		sum += As[idx];
	}
	return sum;
}

int main() {
  std::cin >> N >> M;
  A.resize(N);
	for(int i = 0; i < N; ++i) std::cin >> A[i];
  std::sort(A.begin(), A.end());

	LL l = 0, r = 2 * A[N-1] + 1;
	while (l + 1 != r) {
		LL mid = (l + r) / 2;
		if (M <= Count(mid)) l = mid;
		else r = mid;
	}

	LL ans = (M - Count(l + 1)) * l + Sum(l + 1);
  std::cout << ans << std::endl;
}


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

int main()
{

    cin >> N;
    vector<ll> a(N);
    int o = 0,
        e = 0;

    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        if (a[i] % 2 == 0)
        {
            e++;
        }
        else
        {
            o++;
        }
    }
    while (o > 1)
    {
        o -= 2;
        e++;
    }
    if (e > 0 && o > 0)
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
    }

    return 0;
}


Measured memory_bytes: 3944
def main():
    """
    N,M:10^6より N^2->NG
    矛盾する情報を見つける
    距離情報の保持

    1-2:1, 2-3:1, 1-3:2 <-OK
    1-2:1, 2-3:1, 1-3:5 <-NG(over)
    1-2:1, 2-3:1, 1-3:1 <-NG(less)
    1-2:1, 2-4:3, 1-3:3 <-OK(2-3:2, 3-4:1)
    1-2:1, 2-4:3, 1-3:5 <-NG

    (Li,Ri,Di)
    人Ri は人Li よりも距離 Di だけ右にいる
    すなわち、xRi − xLi = Di
    Ri > Li のとき(人7の右に人8がいる)処理上問題なし
    Ri < Li のとき(人8の右に人7がいる)場合、
    xLi - xRi = -Di
    """
    N, M = map(int, input().split())
    lrd = [
        tuple(map(int, input().split()))
        for _ in range(M)
    ]

    editorial(N, M, lrd)


def editorial(N, M, lrd):
    import sys
    sys.setrecursionlimit(10 ** 7)

    xs = [None] * N
    graph = [[] for _ in range(N)]
    for l, r, d in lrd:
        graph[l - 1].append((r - 1, d))
        graph[r - 1].append((l - 1, -d))

    def dfs(i):
        # 辺情報がなければ独立
        for j, d in graph[i]:
            if xs[j] is None:
                xs[j] = xs[i] + d
                f = dfs(j)
                if not f:
                    return False
            elif xs[j] - xs[i] != d:
                # 距離が誤情報
                return False

        return True

    for i, x in enumerate(xs):
        if x is None:
            # root以外は、dfsで木を探索するときに座標確定
            # １回で確定しないときは、独立した木が存在する
            # 他の木とは別で考えて良いので、初期座標は0固定で問題ない
            xs[i] = 0
            f = dfs(i)
            if not f:
                print("No")
                return

    print("Yes")

if __name__ == '__main__':
    main()


Measured memory_bytes: 161264
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long ul;
typedef unsigned int ui;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
#define All(v) (v).begin(),(v).end()
#define Rep(i,n) for(int i = 0; i < (int)n; i++)
#define Reps(i,n) for(int i = 1; i <= (int)n; i++)
#define For(i,m,n) for(int i = m; i < n; i++)
#define Fors(i,m,n) for(int i = m; i <= n; i++)
#define inf 2e9
#define f first
#define s second
#define pb push_back
#define mp make_pair
struct speed{speed(){cin.tie(); ios::sync_with_stdio(false); cout << fixed << setprecision(18);}}speed;

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

ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

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


int main (){
    int r,d,x;
    cin >> r >> d >> x;
    int count = 1;
    while(count <= 10){
        x = r*x-d;
        cout << x << endl;
        count++;
    }
}

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

using  namespace std;

#define FOR(x,z,y) for(int x = z; x <= y; x++)
typedef long long ll;
typedef pair<int,int> iPair;




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

    int n;
    ll sum = 0;
    cin >> n;
    FOR(i,1,n){
        if(i%3 && i%5 ){
            sum += i;
        }
    }
    cout << sum;
}

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

int main() {
  int n; cin>>n;
  vector<int> x(n),y(n);
  rep(i, n) {
    int p; cin>>p;
    x[i]=p+i;
    y[i]=p-i;
  }
  ll res=0;
  sort(y.begin(), y.end());
  rep(i, n) {
    ll cnt=upper_bound(y.begin(), y.end(), -x[i])-lower_bound(y.begin(), y.end(), -x[i]);
    res+=cnt;
  }
  cout<<res<<endl;
}


Measured memory_bytes: 4832
// package agc.agc021;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        char[] s = in.nextToken().toCharArray();

        int max = digitSum(s);
        s[0]--;
        for (int i = 1 ; i < s.length; i++) {
            s[i] = '9';
        }
        max = Math.max(max, digitSum(s));

        out.println(max);
        out.flush();
    }

    static int digitSum(char[] s) {
        int x = 0;
        for (char c : s) {
            x += (c - '0');
        }
        return x;
    }

    public static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }

    public static class InputReader {
        private static final int BUFFER_LENGTH = 1 << 12;
        private InputStream stream;
        private byte[] buf = new byte[BUFFER_LENGTH];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int next() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            return (char) skipWhileSpace();
        }

        public String nextToken() {
            int c = skipWhileSpace();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = skipWhileSpace();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        int skipWhileSpace() {
            int c = next();
            while (isSpaceChar(c)) {
                c = next();
            }
            return c;
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) FOR(i,0,n)
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

int a,b,c;

int main(){
  cin>>a>>b>>c;

  if(a<=c&&a+b>=c)
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;

  return 0;
}


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

int main(){
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S.at(i);
  }
  sort(S.begin(), S.end());
  for(int i = 0; i < N; i++){
    cout << S.at(i);
  }
  cout << endl;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 1005
#define M 128
#define seed 23333

using namespace std;
const int inf=(int)1e9;
int i,j,m,n,p,k,f[N][M],T,d,ans;
int main()
{
		scanf("%d",&T);
		for (;T--;)
		{
				scanf("%d%d",&n,&d);
				ans=0;
				for (i=6;i>=0;--i)
					if (((d&(1<<i))>0)^(n%2==0))
						ans+=n*(1<<i);
						else ans+=(n-1)*(1<<i);
				printf("%d\n",ans);
		}
}


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

using namespace std;

int n, a[100000+5], b[100000+5], c[100000+5];

int memo[100000+5][5];

int solve(int currentDay, int currentActivity){

    if(currentDay == n){
        return 0;
    }
    if(memo[currentDay][currentActivity] != -1)return memo[currentDay][currentActivity];
    if(currentActivity==0){
        return memo[currentDay][currentActivity] =  a[currentDay] + max( solve(currentDay+1,1),solve(currentDay+1, 2) );
    }
    if(currentActivity==1){
        return memo[currentDay][currentActivity] = b[currentDay] + max( solve(currentDay+1,0),solve(currentDay+1, 2) );
    }
    if(currentActivity==2){
        return memo[currentDay][currentActivity] = c[currentDay] + max( solve(currentDay+1,0),solve(currentDay+1, 1) );
    }

}

int main()
{
    scanf("%d", &n);

    for(int i=0; i<=100000; i++){
        memo[i][0]=-1;
        memo[i][1]=-1;
        memo[i][2]=-1;
    }
    for(int i = 0; i<n; i++){
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
    }
    cout << max(solve(0,0), max(solve(0,1), solve(0,2)));
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) sort((c).rbegin(),(c).rend())
#define UNIQUE(c) SORT(c); (c).erase(unique((c).begin(), (c).end()), (c).end());
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


void solve(string S){
	int flag_yes = 1;
	while (SZ(S) > 0) {
		flag_yes = 0;
		if (SZ(S) >= 5) {
			string s = S.substr(SZ(S) - 5, 5);
			if (s == "dream" || s == "erase") {
				flag_yes = 1;
                S = S.substr(0, SZ(S) - 5);
            }
		}
		if (flag_yes == 0 && SZ(S) >= 6) {
			string s = S.substr(SZ(S) - 6, 6);
			if (s == "eraser") {
				flag_yes = 1;
				S = S.substr(0, SZ(S) - 6);
			}
		}
		if (flag_yes == 0 && SZ(S) >= 7) {
			string s = S.substr(SZ(S) - 7, 7);
            if (s == "dreamer") {
				flag_yes = 1;
                S = S.substr(0, SZ(S) - 7);
            }
		}
		if (flag_yes == 0) {
			break;
		}
	}
	if (flag_yes == 1) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
}


int main(){	
	string S;
	cin >> S;
	solve(S);
	return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
vector<int>a ;
int n,k ;
bool ok(int c){
  int ans =0 ;
  for(int &x:a)
    ans+=(x-1)/c ;
  return ans<=k ;
}
int main() {
  cin >> n >> k ;
  a=vector<int>(n);
  for(int &x:a)
    cin >> x ;
  int lb=1,rb=1e9 ;
  while(lb<rb){
    int mb=(lb+rb)/2 ;
    if(!ok(mb))
      lb=mb+1 ;
    else
      rb=mb ;
  }
  cout << lb << "\n";
}

Measured memory_bytes: 4020
n=int(input())
s=input()
a=['SS','WS','SW','WW']
def f(a,b,w):
    if w=='o':
        if a=='S' and b=='S':return 'S'
        elif a=='W' and b=='S':return 'W'
        elif a=='S' and b=='W':return 'W'
        else:return 'S'
    else:
        if a=='S' and b=='S':return 'W'
        elif a=='W' and b=='S':return 'S'
        elif a=='S' and b=='W':return 'S'
        else:return 'W'

for i in range(n):
    for j in range(4):a[j]+=f(a[j][i],a[j][i+1],s[i])
for i in range(4):
    if a[i][1]==a[i][n+1] and a[i][0] == a[i][n]:print(a[i][1:n+1]);exit()
print(-1)

Measured memory_bytes: 3860
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define Ans(f, y, n) if(f) cout << y << endl; else cout << n << endl;
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i, v.size()){ cout << v[i] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl;}
#define pb push_back
#define int long long
#define INF 1000000000000000000

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

template<typename T> void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }

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

int mod = 1000000007;
//int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod
#define AddMult(x, y, z) x = (x + (y) * (z)) % mod

int f(int x){
    if(x % 4 == 0) return x;
    if(x % 4 == 1) return 1;
    if(x % 4 == 2) return x + 1;
    if(x % 4 == 3) return 0;
}

signed main(){

    int A, B; cin >> A >> B;
    cout << (f(A - 1) ^ f(B)) << endl;

    return 0;
}


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

typedef long long i64;

const int NMAX = 200005;

vector<int> G[NMAX];
int values[NMAX];
int subtree[NMAX];

int h[NMAX], low[NMAX];

int total = 0;

int64_t ans = 1;

void dfs1(int node, int prev) {
    subtree[node] = values[node];
    for (int to: G[node]) {
        if (to != prev) {
            dfs1(to, node);
            h[node] = max(h[node], h[to]);
            subtree[node] += subtree[to];
        }
    }
    ++h[node];
}

void dfs2(int node, int prev, int hup) {
    int hmax1 = hup, hmax2 = 0;
    int hnode = prev;
    int hmin = NMAX;
    for (int to: G[node]) {
        if (to != prev) {
            if (h[to] > hmax1) {
                hmax2 = hmax1;
                hmax1 = h[to];
                hnode = to;
            } else if (h[to] > hmax2) {
                hmax2 = h[to];
            }
            if (subtree[to] > 0) {
                hmin = min(hmin, h[to]);
            }
        }
    }
    hmax1++; hmax2++;
    
    // cerr << node << ' ' << hmax1 << ' ' << hmax2 << endl;
    int ch;
    if (hmax1 == hmax2) {
        ch = hmax2 - 1;
    } else {
        ch = hmax2;
        if (hmax1 > hmax2 + 1) {
            ch++;
        }
    }

    if (total - subtree[node] > 0) {
        hmin = min(hmin, hup);
    }
    hmin++;

    int vis = -1;
    if (values[node] != 1) {
        if (hmin == hmax1) {
            low[node] = hmax2 + 2;
            if (hnode == prev) {
                low[node] = max(low[node], low[hnode] + 2);
            } else {
                vis = hnode;
                dfs2(hnode, node, hmax2);
                low[node] = max(low[node], low[hnode] + 2);
            }
        } else {
            low[node] = hmin;
        }
    } else {
        low[node] = 1;
    }

    ans += max(ch - low[node] + 1, 0);
    // cerr << node + 1 << ' ' << hmin << ' ' << low[node] << ' ' << ch << endl;
    
    for (int to: G[node]) {
        if (to != prev && to != vis) {
            if (h[to] == hmax1 - 1) {
                dfs2(to, node, hmax2);
            } else {
                dfs2(to, node, hmax1);
            }
        }
    }
}

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    string s;
    cin >> s;

    for (int i = 0; i < n; ++i) {
        values[i] = s[i] - '0';
        total += values[i];
    }

    dfs1(0, -1);
    dfs2(0, -1, 0);

    cout << ans << '\n';
}


Measured memory_bytes: 28944
import random
def main():
    N = int(input())
    switches = [int(input()) for _ in range(N)]

    count = 0
    cur   = 0
    nxt   = 0

    find = False

    for i in range(2*N):
        count += 1

        if switches[cur] == 2:
            find = True
            print(count)
            break

        nxt = switches[cur] - 1

        if switches[nxt] - 1 == cur:
            find = True
            print(-1)
            break

        cur = nxt
    if find == False:
        print(-1)

main()

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
template<class T>
inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}
template<class T>
inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

double a,b,h,m;
int main(){
    cin >> a >> b >> h >> m;
    double ans = 0;
    double mk = M_PI/1800.0;
    double hk = M_PI/21600.0;
    double mr = ((mk*(h*3600+m*60)-h*2*M_PI)>=0?mk*(h*3600+m*60)-h*2*M_PI:mk*(h*3600+m*60));
    double hr = hk*(h*3600+m*60);
    double dr;
    if((mr-hr)>=0){
        dr = mr-hr;
        if(dr>M_PI){
            dr = (2*M_PI-mr)+hr;
        }
    }
    else
    {
        dr = hr-mr;
        if(dr>M_PI){
            dr = (2*M_PI-hr)+mr;
        }
    }
    ans = sqrt(a*a+b*b-2*a*b*cos(dr));
    cout << fixed << setprecision(11) << ans << endl;
    return 0;
}

Measured memory_bytes: 4212
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(double  ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;


     cin>>n;

     double ara[n+2];

     input(ara,n);

     sort(ara,ara+n);

       double sum=(ara[0]+ara[1])/2.0;

       for(i=2; i<n; i++)
       {
           sum=(sum+ara[i])/2.0;
       }

       cout<<sum<<endl;





}



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


#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, z, w;
	cin >>n >>z >>w;
	VI a(n);
	rep(i, n) cin >>a[i];
	
	int ans=0;
	if(n > 1) ans = max(abs(a[n-1] - w) , abs(a[n-2] - a[n-1]));
	else ans = abs(a[n-1] - w);
	cout << ans <<"\n";
	
	return 0;
}


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

int main(){
  int i,j,cnt=0;
  int n;
  cin>>n;
  ll a[n];
  for(i=0;i<n;i++)cin>>a[i];
  int minus=0;
  for(i=0;i<n;i++){
    if(a[i]<0)minus++;
  }
  for(i=0;i<n;i++)a[i]=max(a[i],-a[i]);
  sort(a,a+n);
  ll sum=0;
  for(i=0;i<n;i++)sum+=a[i];
  if(minus%2==1){
    sum-=2*a[0];
  }
  cout<<sum;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i<=(b);i++)
#define ROF(i,a,b) for(int i = (a);i>=(b);i--)
#define MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 105
#define M 51
#define INF 1000000007
#define MOD 1000000007
#define MOD2 1000000009
#define eps 1e-7
using namespace std;
inline int Max(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^b;
}
inline int Min(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^a;
}

string a,b;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n)
    {
        cin>>a>>b;
        int pos = n;
        FOR(i,0,n-1)
        {
            int f = 1;
            FOR(j,i,n-1)
            {
                if(a[j]!=b[j-i])
                {
                    f = 0;
                    break;
                }
            }
            if(f)
            {
                pos = i;
                break;
            }
        }
        cout<<n+pos<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
N,Y=map(int,input().split())
d=Y//1000-N

sw=0
for a in range(N+1):
  for b in range(N+1):
    if 9*a+4*b==d:
      c=N-a-b
      if c>=0:
        sw=1
        break
  else:
    continue
  break
  
if sw==1:
  print(a,b,c)
else:
  print(-1,-1,-1)

Measured memory_bytes: 3064
from collections import Counter


def solve(string):
    n, *aqbc = map(int, string.split())
    a, _, bc = aqbc[:n], aqbc[n], aqbc[n + 1:]
    s = sum(a)
    t = Counter(a)
    ans = []
    for b, c in zip(*[iter(bc)] * 2):
        if b not in t.keys():
            ans.append(s)
            continue
        s += (c - b) * t[b]
        t[c] += t[b]
        t[b] = 0
        ans.append(s)
    return "\n".join(map(str, ans))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 44260
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int MOD = 1000000007;

int main()
{
	int n, k  = 0;
	string s = "";
	cin >> n >> s >> k;
	char c = s[k - 1];

	for (int i = 0; i < s.length(); i++)
	{
		if (c != s[i])
		{
			s[i] = '*';
		}
	}

	cout << s << "\n";
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
#define deb(x) cout << #x": " << (x) << endl;

int main(){ _
  string n;
  cin >> n;
  lli c = 0;
  fore (i,0,sz(n)){
    c+=n[i] - '0';
  }
  if (c % 9 == 0){
    cout << "Yes" << ENDL;
  }
  else{
    cout << "No" << ENDL;
  }
  return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
#define VALS(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pf push_front
#define INF 1234567890ll
#define PI (acos((ld)-1.0))
#define ll long long int 
#define ld long double
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
typedef pair <int, int> pi;
typedef pair <ll, ll> pl;
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;


int main()
{
	IAMSPEED
	int n, k; cin >> n >> k;
	int ans = 0;
	FOR(i, 1, n) {
		int x; cin >> x;
		if (x >= k) ++ans;
	}
	cout << ans;
	
}

Measured memory_bytes: 384
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		sc.close();
		ArrayList<Integer> c = new ArrayList<>();
		c.add(0);
		int j=0;
		for(int i=0;i<3;++i){
			if(str.charAt(i)=='R'){
				c.set(j, c.get(j)+1);
			}
			if(str.charAt(i)=='S'){
				j++;
				c.add(0);
			}
		}
		System.out.println(Collections.max(c));
	}
}



Measured memory_bytes: 35608
import java.util.Scanner;
import java.util.Arrays;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] l = new int[n];

    for(int i = 0; i < n; i++){
      l[i] = sc.nextInt();
    }
    Arrays.sort(l);

    int count = 0;
    for(int a = 0; a < n; a++){
      for(int b = a + 1; b < n; b++){
        int ab = l[a] + l[b];

        for(int c = b + 1; c < n; c++){
          if( l[a] < l[b] + l[c] &&
              l[b] < l[a] + l[c] &&
              l[c] < ab
          ){
            count++;
          }
        }
      }
    }

    System.out.println(count);

  }
}


Measured memory_bytes: 26548
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define db(x) cerr << #x << ": " << x << '\n';
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define rz(v, n) v.resize((n) + 1);
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int x = 100, y, i = 0;
	cin >> y;
	while (true)
	{
	    x += (double)(x)/(double)(100);
	    i++;
	    if (x >= y) {cout << i; break;}
	}
	
}










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

int main(){
  int N, M;
  vector<pair<int,int>> AB(100010, make_pair(1e8, 1e8));

  cin >> N >> M;
  for(int i=0; i<N; i++) cin >> AB[i].first >> AB[i].second;
  sort(AB.begin(), AB.begin()+N);

  priority_queue<int> Q;

  int ans = 0, id = 0;
  for(int i=1; i<=M; i++){
    if(AB[id].first > i) {
      if(!Q.empty()){
        ans += Q.top(); Q.pop();
      }
      continue;
    }

    while(AB[id].first <= i){
      Q.push(AB[id].second); id++;
    }

    ans += Q.top(); Q.pop();
  }

  cout << ans << endl;
}

Measured memory_bytes: 1660
using System.Linq;
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        var amin = a.Min();
        for (int i = 0; i < n; i++) a[i] -= amin;
        var ans = 0;
        for (int i = 0; i < n -1; i++)
        {
            if (a[i + 1] < a[i]) ans += a[i] - a[i + 1];
        }
        ans += a[n - 1];
        ans += amin;
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13268
def manhattan(inlist1,inlist2):
	return abs(inlist1[0]-inlist2[0]) + abs(inlist1[1]-inlist2[1])

n, m = [ int(v) for v in input().split() ]


student_list = [ [ int(v) for v in input().split() ] for i in range(n) ]
point_list = [ [ int(v) for v in input().split() ] for i in range(m) ]
for i in range(n):
	ans = [10**9,0]
	for j in range(m):
		d = manhattan(student_list[i],point_list[j])
		if d < ans[0]:
			ans = [d, j+1]
	print(ans[1])

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

int main()
{
	int n;
	int b, f, r, v;
	int room[4][30]={0};
	int i, j;
	
	cin >> n;
	
	for(i=0;i<n;i++){
		cin >> b >> f >> r >> v;
		room[b-1][(f-1)*10+r-1]+=v;
	}
	
	for(i=0;i<4;i++){
		for(j=0;j<30;j++){
			cout << ' ' << room[i][j];
			if(j==9||j==19)
				cout << endl;
		}
		cout << endl;
		if(i!=3)
			cout << "####################" << endl;
	}
	
	return 0;
	
}

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


#define fast_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define pb push_back
#define F first
#define S second
#define int long long int
#define ll long long
#define ld long double

bool isPrime(ll n){if(n<2)return false;for(ll i=2;i*i<=n;++i){if(n%i==0){return false;}}return true;}

ll lcm(ll x,ll y){
    return (x*y)/(__gcd(x,y));
}


signed main(){
    fast_IO;
    int t=1;
    //cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int sum=0;
        int maxx=a[0];
        for(int i=1;i<n;i++){
            if(a[i]>maxx){
                maxx=a[i];
            }
            else{
                sum+=maxx-a[i];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 4684
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 200005;
ll A[MAX_N];

int main()
{
	int N;
	cin >> N;
	ll sum = 0;
	rep(i,N)
	{
		cin >> A[i];
		sum += A[i];
	}

	ll nowsum = 0;
	int cnt;
	rep(i,N)
	{
		nowsum += A[i];
		if (nowsum * 2 > sum)
		{
			cnt = i;
			break;
		}
	}
	//cout << cnt << endl;

	ll ans = min(sum - (nowsum - A[cnt]) * 2, nowsum * 2 - sum);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
//#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
//#include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T> using G = greater<T>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), G<type>())
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく、n=10が限界(500 ms)
#define ENDL cout << endl;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, G<T> >;

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 = 2e9;
const LL MOD = 1e9 + 7;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, W;
  cin >> N >> W;
  VLL v(N), w(N);
  REP(int, i, N) cin >> w[i] >> v[i];
  VLL dp(100001, INF);
  dp[0] = 0;
  REP(int, i, N) REPR2(int, j, v[i], 100001) chmin(dp[j], dp[j-v[i]]+w[i]);
  REPR(int, j, 100001)
  {
    if (dp[j] <= W)
    {
      cout << j << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 1024
# coding: utf-8
# Your code here!
import sys
import math
from collections import Counter
input = sys.stdin.readline

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

N = int(input())
arr = [input() for i in range(N)]
ini_arr = [j[0] for j in arr if j[0] == "M" or j[0] == "A" or j[0] == "R" or j[0] == "C" or j[0] == "H"]
dic = Counter(ini_arr)
key_num = len(dic)
val_num = sum(k for k in dic.values())
if key_num < 3:
    print(0)
else:
    total = C(len(ini_arr), 3)
    for i in dic.values():
        if i == 2:
            total -= C(val_num - i, 1)
        elif i >= 3:
            total -= C(i, 2) * C(val_num - i, 1)  + C(i, 3)
    print(total)

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

using namespace std;

typedef long long ll;
typedef double long dl;
typedef pair < int , int > pii;
typedef pair < pii, pii > p2i;
const int maxn = (int) 3e5 + 1;
const int mod = (int) 1e9 + 7;
const ll inf = (ll)1e18;

#define fi first
#define se second
#define acel ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define next continue
#define getsz(x) (int) log10(x)

int n;
ll a, b;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a >> b;
        ll s = a * b;
        if(abs(a - b) <= 1){
            cout << (2 * min(a, b)) - 2 << "\n";
            next;
        }
        ll x = sqrt(s);
        if(x * x == s){
            x--;
        }
        if(x * (x + 1) >= s){
            cout << (x * 2) - 2 << "\n";
        }
        else {
            cout << (x * 2) - 1 << "\n";
        }
    }
}


Measured memory_bytes: 256
a,b,c,x,y=map(int,input().split())
ans1=a*x+b*y
if x>=y:
    ans2=a*(x-y)+c*y*2
    ans3=c*x*2
else:
    ans2=b*(y-x)+c*x*2
    ans3=c*y*2
print(min(ans1,ans2,ans3))

Measured memory_bytes: 3060
N,*uvws=$<.read.split.map(&:to_i)

h = {}
uvws.each_slice(3) do |u,v,w|
    h[u] ||= []
    h[u] << [u,v,w%2]
    h[v] ||= []
    h[v] << [v,u,w%2]
end

arr = Array.new(N+1,-1)
arr[1] = 0

q = h[1]
until q.empty?
    u,v,w = q.shift
    next if arr[v] != -1
    if w == 0
        arr[v] = arr[u]
    else
        arr[v] = 1-arr[u]
    end
    q.push(*h[v])
    # h[v].each do |x|
    #     q << x
    # end
end

puts arr[1..-1]

Measured memory_bytes: 55028
#include <stdio.h>
#include <ctype.h>
/*#define dbg*/
int main(void){
    char keyword[11]={0};
    char target[1001]={0};
    int index=0, counter=0;
    
    scanf("%s", keyword);/*gets(keyword);*/
    #ifdef dbg
    printf("debug-keyword:%s\n", keyword);
    sleep(5);
    #endif
    
    for(index=0; strlen(keyword) > index; index++){
        keyword[index] = tolower(keyword[index]);
        #ifdef dbg
        printf("debug-lowerprocess:%c\n", keyword[index]);
        #endif
    }
    #ifdef dbg
    printf("debug-keyword_lower:%s\n", keyword);
    sleep(5);
    #endif
    
    while(scanf("%s", target) && strcmp(target, "END_OF_TEXT")){
        #ifdef dbg
        printf("debug-linescan:%s\n", target);
        sleep(5);
        #endif
        
        for(index=0; strlen(target) > index; index++){
            target[index] = tolower(target[index]);
            #ifdef dbg
            printf("debug-lowerprocess:%c\n", target[index]);
            #endif
        }
        #ifdef dbg
            printf("debug-target_lower:%s\n", target);
            sleep(5);
        #endif
        
        if(!strcmp(target, keyword)){
            counter++;
            #ifdef dbg
            printf("debug-counting:%d (tar)%s=(key)%s\n", counter, target, keyword);
            sleep(5);
            #endif
        }
    }
    
    printf("%d\n", counter);
    
    return 0;
}

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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pipipii = pair<ll, pair<int, pii>>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n, m;
    cin >> n >> m;
    vector<char>a(n+1, 1);
    for(int i = 0; i < m; ++i){
        int tmp;
        cin >> tmp;
        a[tmp] = 0;
    }
    vector<int> dp(n+2);
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        if(!a[i]) continue;
        dp[i+1] = ((ll)dp[i] + dp[i+1]) % MOD;
        dp[i+2] = ((ll)dp[i] + dp[i+2]) % MOD;
    }
    cout << dp[n] << "\n";
    return 0;
}

Measured memory_bytes: 768