akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    ll dp[n+1][n+1][2];
    dp[0][0][0]=0;
    dp[0][0][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j][0]=0;
            dp[i][j][1]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][i][0]=arr[i-1];
        dp[i][i][1]=0;
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            if(arr[i-1]+dp[i+1][j][1]>arr[j-1]+dp[i][j-1][1])
            {
                dp[i][j][0]=arr[i-1]+dp[i+1][j][1];
                dp[i][j][1]=dp[i+1][j][0];
            }
            else
            {
                dp[i][j][0]=arr[j-1]+dp[i][j-1][1];
                dp[i][j][1]=dp[i][j-1][0];
            }
        }
    }
    cout<<dp[1][n][0]-dp[1][n][1]<<"\n";
    return 0;
}

Measured memory_bytes: 140928
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
	    int n = Integer.parseInt(sc.next());
	    int[] array = new int[n];
	    for (int i = 0; i < n; i++) {
	        array[i] = Integer.parseInt(sc.next());
	    }
	    int cnt = 0;
	    for (int i = 0; i < n; i++) {
	        if (array[i] != i + 1) {
	            cnt++;
	        }
	    }
	    if (cnt == 0 || cnt == 2) {
	        System.out.println("YES");
	    } else {
	        System.out.println("NO");
	    }
    }
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;

#define sync std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define loopi(n) for(int i=0;i<n;i++)
#define loopj(n) for(int j=0;j<n;j++)
#define loop(a,b,c) for(int i=a;i<=b;i=i+c)

#define     deb(x)      cout<<#x<<"="<<x<<endl
#define     all(x)      (x).begin(),(x).end()
#define     reset(a)    memset(a,0,sizeof(a))
#define     sz(x)       ((int)(x.size()))
#define     pb          push_back
#define     pf          push_front
#define     pob	        pop_back
#define     pof         pop_front
#define     ins         insert
#define     F           first
#define     S           second
#define     mkp         make_pair
#define     mkt         make_tuple
#define     bitcount(x) __builtin_popcountll(x)
#define     gcd(a,b)    (__gcd(a,b))
#define     lcm(a,b)    ((a*b)/gcd(a,b))
#define PI 3.1415926535897932384626
 
const int mod = 1e9+7;

//============================================//

void solve()
{
	ll a[4];
	loopi(4)	cin>>a[i];
	ll ans=a[0]*a[2];
	
	loop(2,3,1)
	{
		loopj(2)
		{
			ll x=a[i]*a[j];
			ans=max(ans,x);
		}
	}
	cout<<ans;
}

int main() 
{
	sync;

	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
		cout<<endl;
	}
}


Measured memory_bytes: 3648
#include <stdio.h>

int main(void) {
	int N;
	int asumikana = 0;
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		char S[4];
		if (scanf("%3s", S) != 1) return 1;
		switch (S[0]) {
			case 'P': asumikana |= 1; break;
			case 'W': asumikana |= 2; break;
			case 'G': asumikana |= 4; break;
			case 'Y': asumikana |= 8; break;
		}
	}
	switch (asumikana) {
		case 1 | 2 | 4:
		case 1 | 2 | 8:
		case 1 | 4 | 8:
		case 2 | 4 | 8:
			puts("Three");
			break;
		case 1 | 2 | 4 | 8:
		
			puts("Four");
			break;
	}
	return 0;
}


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

using bellman_cost = int;
template<class V, class E>
struct Graph
{
	int sz;
	vector<V> v;
	vector<vector<E>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = V(args...);
	}
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Vertex_Cost
{
	T cost;
	bool valid = false;
	Vertex_Cost(T v1) : cost(v1) {}
	Vertex_Cost() {}
};
using vertex = Vertex_Cost<bellman_cost>;

template<class T>
struct Edge_Cost
{
	int to;
	T cost;
	Edge_Cost(int t, T c) : to(t), cost(c) {}
	Edge_Cost() {}
};
using edge = Edge_Cost<bellman_cost>;
using graph = Graph<vertex, edge>;

template<class T, class V, class E>
void Bellmanford(Graph<V, E>& G, int s, T INF_COST)
{
	auto &v = G.v;
	auto &e = G.e;
	for (auto& vv : v) vv.cost = INF_COST;
	v[s].cost = 0;
	v[s].valid = true;
	for (int i = 0; i + 1 < (int) v.size(); i++) {
		for (int j = 0; j < (int) v.size(); j++) {
			for (auto& x: e[j]) {
				if (v[j].cost == INF_COST) continue;
				v[x.to].cost = min(v[x.to].cost, v[j].cost + x.cost);
				v[x.to].valid = true;
			}
		}
	}
	stack<int> not_valid;
	for (int i = 0; i < (int) v.size(); i++) {
		for (auto& x: e[i]) {
			if (v[i].cost == INF_COST) continue;
			if (v[x.to].cost > v[i].cost + x.cost) {
				not_valid.push(x.to);
			}
		}
	}
	while (!not_valid.empty()) {
		int pos = not_valid.top();
		not_valid.pop();
		if (!v[pos].valid) continue;
		v[pos].valid = false;
		for (auto& x: e[pos]) {
			not_valid.push(x.to);
		}
	}
}


void solve(long long N, long long M, long long P, std::vector<long long> A, std::vector<long long> B, std::vector<long long> C) {
	graph g(N);
	for (int i = 0; i < M; i++) {
		g.add_edge(A[i]-1, B[i]-1, -(C[i] - P));
	}
	Bellmanford(g, 0, INT_MAX);
	if (!g.v[N-1].valid) cout << -1 << endl;
	else cout << max(-g.v[N-1].cost , 0) << endl;
}

signed main() {
	long long N;
	scanf("%lld",&N);
	long long M;
	scanf("%lld",&M);
	long long P;
	scanf("%lld",&P);
	std::vector<long long> A(M);
	std::vector<long long> B(M);
	std::vector<long long> C(M);
	for(int i = 0 ; i < M ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
		scanf("%lld",&C[i]);
	}
	solve(N, M, P, std::move(A), std::move(B), std::move(C));
	return 0;
}


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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

struct UnionFind {
    int n;
    vector<int> dat;
    UnionFind(int size): n(size), dat(size, -1) { }
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (dat[y] < dat[x]) swap(x, y);
            dat[x] += dat[y];
            dat[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    int root(int x){
        return dat[x] < 0 ? x : dat[x] = root(dat[x]);
    }
    int size(int x){
        return -dat[root(x)];
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");
    int n,q; cin >> n >> q;
    auto uf = UnionFind(n);
    rep(i,q){
        int c,x,y; cin >> c >> x >> y;
        if(c == 0) uf.unite(x, y);
        else{
            cout << uf.same(x, y) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3252
import collections

n = int(input())
a = list(map(int,input().split()))
q=int(input())

num_dict = dict(collections.Counter(a))
tmp_sum=sum(a)
#print(num_dict,tmp_sum)

for i in range(q):
    b, c=map(int,input().split())
    if b in num_dict:
        if c in num_dict:
            tmp_sum+=(c-b)*num_dict[b]
            num_dict[c]+=num_dict[b]
            num_dict[b]=0
        else:
            tmp_sum+=(c-b)*num_dict[b]
            num_dict[c]=num_dict[b]
            num_dict[b]=0
    print(tmp_sum)

Measured memory_bytes: 21292
#include<bits/stdc++.h>
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int d,w;
    cin >> d >> w;
    while(d != 0){
        vector<vector<int>> G(d,vector<int> (w));
        for(int i=0; i<d; i++){
            for(int j=0; j<w; j++){
                cin >> G[i][j];
            }
        }
        int ans = 0;
        for(int i=0; i<d; i++){
            for(int j=i+2; j<d; j++){
                for(int k=0; k<w; k++){
                    for(int l=k+2; l<w; l++){
                        int mn_r = inf;
                        int mx_i = 0;
                        int sum = 0;
                        for(int H=i; H<=j; H++){
                            for(int W=k; W<=l; W++){
                                if(H==i or H==j or W==k or W==l){
                                    chmin(mn_r,G[H][W]);
                                }else{
                                    chmax(mx_i,G[H][W]);
                                    sum += G[H][W];
                                }
                            }
                        }
                        if(mn_r > mx_i){
                            chmax(ans,(j-i-1)*(l-k-1)*mn_r - sum);
                        }
                    }
                }
            }
        }
        cout << ans << enld;
        cin >> d >> w;
    }
    return 0;
}



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

int main() {
    int n, k;
    cin >> n >> k;
    int a[n];
    rep(i, n) cin >> a[i];

    int g = a[0];
    rep(i, n) { g = __gcd(g, a[i]); }

    if (k <= *max_element(a, a + n) && k % g == 0)
        cout << "POSSIBLE" << endl;
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}


Measured memory_bytes: 640
S = input()

l = list(S)

c = 0

b = 0

for i in range(2, len(l) - 1):
    if l[i] == 'C':
        c += 1
        
for i in range(len(l)):
    if l[i].isupper() == True:
        b += 1

if l[0] == 'A' and c == 1 and b == 2:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

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

		int[] A = new int[N];

		for (int i = 0; i < A.length; i++) {
			A[i] = sc.nextInt();
		}

		int res = 0;

		while (true) {
			
			boolean existOdd = false;

			// check
			for (int i = 0; i < A.length; i++) {

				if (A[i] % 2 != 0) {
					existOdd = true;
					break;
				}
			}
			
			if (existOdd) {
				break;
			}

			// update
			for (int i = 0; i < A.length; i++) {
				A[i] = A[i] / 2;
			}
			
			res++;
		}
		
		System.out.println(res);
	}

}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
     
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 999999999999999999
#define endl "\n"
#define MOD 1000000007
 
 
 
void func(){
 
ll n;
cin>>n;
 
cout<<setprecision(10)<<2*22*1.0*n/7<<endl;
}
 
 
 
 
    
int main(){
            ios_base::sync_with_stdio(false);
            cin.tie(0);
            cout.tie(0);
     
        /*  #ifndef ONLINE_JUDGE
          freopen("input.txt", "r" , stdin);
          freopen("output1.txt", "w" , stdout);
          #endif*/
     
       ll t=1;
       //cin>>t;
       while(t--)
       func();
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main(){
  int n, ma, mb;
  cin >> n >> ma >> mb;
  vector<int> a(n), b(n), c(n);
  for(int i=0; i<n; ++i){
    cin >> a[i] >> b[i] >> c[i];
  }
  vector<vector<int>> dp(401,vector<int>(401,INF));
  dp[0][0] = 0;
  for(int i=0; i<n; ++i) for(int j=400; j>=a[i]; --j) for(int k=400; k>=b[i]; --k){
    dp[j][k] =min(dp[j][k], dp[j-a[i]][k-b[i]] + c[i]);
  }
  int ans = INF;
  for(int i=1; i<401; ++i){
    if(i*ma > 400 || i*mb > 400) break;
    ans = min(ans, dp[ma*i][mb*i]);
  }
  if(ans == INF) cout << -1 << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 4284
N = int(input())

MOD = 10 ** 9 + 7

pfac = [1] * (N + 1)

for i in range(1, N + 1) :
    j = i
    while j % 2 == 0 :
        j //= 2
        pfac[2] += 1
    
    k = 3
    while j > 1 :
        while j % k == 0 :
            j //= k
            pfac[k] += 1
        k += 2
    
ret = 1
for i in range(2, N + 1) :
    ret *= pfac[i]
    ret %= MOD
    
print(ret)

Measured memory_bytes: 39664
module Main where

import           Control.Monad
import           Control.Monad.State
import           Data.Array.IO
import           Data.Char
import           Data.Fixed
import           Data.List
import           Data.List.Split
import           Data.Ord
import qualified Data.Vector.Unboxed as V
import           Text.Printf

main :: IO ()
main = do
  [n, k] <- map read . words <$> getLine :: IO [Int]
  putStrLn $ showFixed True
    $ (/ tp n)
    $ (`execState` 0)
    $ forM_ [1 .. n]
    $ \i -> do
      let p = ceiling $ fromIntegral k / fromIntegral i
          q = f p 1
      v <- get
      put ((v + (tp 1 / tp q)) :: Pico)
  where
    f :: Int -> Int -> Int
    f p i
      | i >= p = i
      | otherwise = f p (i * 2)

    tp x = realToFrac x :: Pico


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

int main() {
	string s;
	cin >> s;
	if (s == "MON") cout << 6;
	else if (s == "TUE") cout << 5;
	else if (s == "WED") cout << 4;
	else if (s == "THU") cout << 3;
	else if (s == "FRI") cout << 2;
	else if (s == "SAT") cout << 1;
	else cout << 7;
	cout << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




//UnionFind Template
struct UnionFind{ //構造体の定義
    vector<int> d; 
    UnionFind(int n=0): d(n,-1) {} //コンストラクタ
    int find(int x){
        if(d[x]<0) return x;
        return d[x]=find(d[x]);
    }
    bool unite(int x, int y){
        x=find(x); y=find(y);
        if(x==y) return false;
        if(d[x]<d[y]) swap(x,y);//d[x] is smaller. Then, connect d[x] to d[y].
        d[y]+=d[x];
        d[x]=y;
        return true;
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
    int size(int x){
        return -(d[find(x)]);   
    }
    int rootsize(){
        int cnt=0;
        for(auto& v: d){
            if(v<0) cnt++;
        }
        return cnt;
    }
};
//How to use
//UnionFind uf(n); などと書けば使えるようになる.ufというobjectが生成される
//uf.unite(a,b);などで中の関数を使える




int main(){
    int h,w; cin>>h>>w;
    const vector<int> df={-1,1,w,-w};
    vector<string> p(h);
    rep(i,h) cin>>p[i];
    UnionFind uf(h*w);
    rep(i,h*w){
        if(p[i/w][i%w]=='.') continue;
        rep(j,4){
            int a=i+df[j];
            if(a<0 || a>=h*w || (a&w==0 && j==1) || (i%w==0 && j==0)) continue;
            if(p[a/w][a%w]=='#') uf.unite(i,a);
        }
    }
    bool ok=true;
    rep(i,h*w){
        if(uf.size(i)==1 && p[i/w][i%w]=='#') ok=false;
    }
    cout<<(ok? "Yes": "No")<<endl;
    return 0;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define deb(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>h(n);
    
    for(int i=0;i<n;i++)
        cin>>h[i];
    
    vector<int>dp(n,INT_MAX);
    //dp[i] is the minimum cost of reaching the ith step
    dp[0]=0;
    for(int i=1;i<n;i++)
        for(int j=i-1 ; j>=max(i-k,0) ; j--)
            dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
    
    
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 3984
a, b, c = input()  # 3文字の文字列
d, e, f = input()  # 3文字の文字列

if a==d:
  o = 1
else:
  o = 0
  
if b==e:
  p = 1
else:
  p = 0

if c==f:
  q = 1
else:
  q = 0

print(o+p+q)

Measured memory_bytes: 3060
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
#include <map> // pair
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;

using namespace std;
//using ll = long long;
using ll = unsigned long long;
typedef pair <ll, ll > pll;

int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll n, m, K;
	ll memo[1003][1003] = { {} };
	ll memox[1003] = {};
	ll memoy[1003] = {};
	ll x[1000006] = {};
	ll y[100005] = {};
	ll z[100005] = {};
	string s;

	//IntStack yStack;
	//charStack Stack;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x[i];
	}
	sort(x, x + n);
	a = x[0];
	ll X;
	ll tmp;
	ll r;

	for (int i = 1; i < n; i++)
	{
		//if (a < 1000000000000000000 / x[i])
		{

			//最小公倍数
			//X = a * x[i];
			c = a;
			d = x[i];
			/* 自然数 a > b を確認・入替 */
			if (a < x[i]) {
				tmp = a;
				a = x[i];
				x[i] = tmp;
			}
			/* ユークリッドの互除法 */
			r = a % x[i];
			while (r != 0) {
				a = x[i];
				x[i] = r;
				r = a % x[i];
			}
			a = (c / x[i])*d;//答え
		}
		/*
		else
		{
			//a = max(x[i], a);
			X = max(a, x[i]);
			tmp = min(a, x[i]);
			while (X%tmp==0)
			{

			}
		}
		*/
	}
	cout << a << endl;


	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}

//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え

Measured memory_bytes: 8064
N = int(input())
A,B = map(int, input().split())
P = sorted(list(map(int,input().split())))

a,b,c = 0,0,0
for p in P:
    if p <= A:
        a += 1
    elif p <= B:
        b += 1
    else:
        c += 1

ans = min(a,b,c)
print(ans)


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

ll a[300000];
ll sum[300000];

int main(){
	long long N,X;cin>>N>>X;
	ll n=N,x=X;
	rep(i,n){
		long long A;scanf("%lld",&A);
		sum[i]=a[i]=A;
	}
	for(int i=1;i<n;i++)sum[i]+=sum[i-1];
	ll ans=LLONG_MAX;
	for(ll k=1;k<=n;k++){//何回往復するか?
		ll cnt=(n+k)*x;
		for(ll c=0;c<(n+k-1)/k;c++){
			ll l=max((ll)0,n-1-(c+1)*k+1),r=n-1-c*k;
			if(c==0)cnt+=(sum[r]-(l==0?0:sum[l-1]))*5;
			else cnt+=(2*c+3)*(sum[r]-(l==0?0:sum[l-1]));
		}
		ans=min(ans,cnt);
	}
	cout<<(long long)ans<<endl;
}

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

const string ok = "yes", ng = "no";

string solve()
{
    string t,p;
    cin >>t >>p;
    int T = t.size(), P = p.size();

    vector<int> head,tail;

    // head
    int idx = 0;
    rep(i,T)
    {
        if(idx<P && p[idx]==t[i])
        {
            head.pb(i);
            ++idx;
        }
    }

    // tail
    idx = P-1;
    for(int i=T-1; i>=0; --i)
    {
        if(idx>=0 && p[idx]==t[i])
        {
            tail.pb(i);
            --idx;
        }
    }
    reverse(tail.begin(),tail.end());

    if(P != head.size() || head.size() != tail.size()) return ng;

    rep(i,P)if(head[i]!=tail[i]) return ng;

    return ok;
}

int main()
{
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 8964
#include<stdio.h>
#include<string.h>

#define M 1000000
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1+(key % (M-1)); }

int find(char str[]){
    long long key,i,h;
    key = getKey(str);
    for(i=0;;i++){
      h=(h1(key)+i*h2(key))%M;
      if((strcmp(H[h],str)==0))return 1;
      else if (strlen(H[h])==0)return 0;
    }
    return 0;
  }

int insert(char str[]){
   long long key,i,h;
    key = getKey(str);
    for(i=0;;i++){
      h=(h1(key)+i*h2(key))%M;
      if((strcmp(H[h],str)==0))return 1;
      else if (strlen(H[h])==0){
	strcpy(H[h],str);
	return 0;
      }
    }
    return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}



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

int main() {
  long long int X, Y; cin >> X >> Y;
  long long int A = X, ans = 1;
  while (A < Y) {
    A *= 2;
    if (A > Y) ans--;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main(){

  int n,color[9]={},a;
  cin>>n;
  while(n--){
    cin>>a;
    color[min(8,a/400)]++;
  }
  a=0;
  for(int i=0;i<8;++i){
    if(color[i]>0)a++;
  }
  cout << max(a,1) << " " << a+color[8] << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define Mod 1000000007

int main()
{
	int i, n, m;
	long long x[100001], y[100001];
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) scanf("%lld", &(x[i]));
	for (i = 1; i <= m; i++) scanf("%lld", &(y[i]));
	
	long long ans = 0, tmp = 0;
	for (i = 1; i < n; i++) tmp = (tmp + (x[i+1] - x[i]) * ((long long)i * (n - i) % Mod)) % Mod;
	for (i = 1; i < m; i++) ans = (ans + (tmp * (y[i+1] - y[i]) % Mod) * ((long long)i * (m - i) % Mod)) % Mod; 
	
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_b() {
	ll n, m;
	ll x, y;
	//ll a, b, c;
	ll k;
	string s, t;
	ll l_ans = 0;
	float f_ans = 0;
	string s_ans;

	cin >> n;

	V a(n);
	rep(i, n) cin >> a[i];
	
	rep(i, n) {
		if (((i + 1) % 2) == 1 && a[i] % 2 == 1) {
			l_ans++;
		}
	}


	cout << l_ans << "\n";
}

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

	solve_abc_b();

	return 0;
}


Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,ans=1e18;
	cin>>n>>m;
	n%=m;
	for(int i=1;i<=10;i++)
	{
		ans=min(ans,n);
		n=abs(n-m);
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define sortall(obj) sort(ALL(obj))
#define revall(obj) reverse(ALL(obj))
#define SortRevAll(obj) revall(sortall(obj))
typedef string str;
typedef long long ll;
const int mod=1e9+7;
const int INF=1e9;
const ll LINF=1e18;
#define VI vector<int>
#define P pair
#define M map
#define F first()
#define S second()
#define PB(a) push_back(a)
#define IN(a) insert(a)
#define ins(a) int a;cin >> a
#define lls(a) ll a;cin >> a
#define in(a) cin >> a
#define sts(a) string (a);cin >> a
#define For(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) For(i,0,n)
#define Forr(i,m,n) for(int i=n-1;i>=m;i--)
#define repr(i,n) Forr(i,0,n)
#define print(a) cout << a << endl
#define Endl cout << endl
#define YES(n) cout << ((n)? "YES" : "NO") << endl
#define Yes(n) cout << ((n)? "Yes" : "No") << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE" ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define br(c,y,n) cout << ((c)? y : n) << endl

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

int main()
{
    ll N,P,ans=1,T;
    in(N);in(T);
    P=T;
    For(i,2,sqrt(T)){
        ll cnt=0;
        while(P%i==0){
            P/=i;
            if(P>=1){
                cnt++;
            }
        }
        if(cnt>=N){
            ans*=pow(i,cnt/N);
        }
    }
    if(N==1)ans*=P;
    print(ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] A = new int[N];
        for(int i=0;i<N;i++){
            A[i]=scanner.nextInt();
        }
        bubbleSort(A,N);
    }
     
    static void bubbleSort(int[] A,int N){
    	int count = 0;
        for(int i=N-1;i>0;i--){
        	//[N-1-i] is better than 0
        	for(int j=N-1;j>N-1-i;j--){
        		if(A[j-1] > A[j]){
        			int v = A[j];
        			A[j] = A[j-1];
        			A[j-1] = v;
        			count++;
        		}
        	}
        }
    	printList(A,N);
        System.out.println(count);
    }
    static void printList(int[] A,int N){
        StringBuilder builder = new StringBuilder();
        for(int i=0;i<N;i++){
            if(i>0){
                builder.append(" ");
            }
            builder.append(A[i]);
        }
        System.out.println(builder);
    }
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  LL N, M;
  cin >> N >> M;

  LL ans = 0;
  VL idx = {0ll};
  for(LL i=1,j=1;i<=N;++i){
	ans += i*i*i;
	idx.PB(j);
	j += i;
  }

  VVL qs(3);
  REP(i,M){
	LL Q, K;
	cin >> Q >> K;
	qs[Q].PB(K);
  }
  REP(q,3) SORT(qs[q]);

  VL blk_x;
  REP(i,N+1) blk_x.PB(i);

  for(LL x: qs[0]){
	if(x > N*(N+1)/2) continue;
	LL ix = (--upper_bound(ALL(idx), x)) - begin(idx);
	blk_x[ix]--;
	ans -= ix*ix;
  }

  VL blk_y(N+1);
  for(LL i=1;i<=N;++i)
	blk_y[i] = blk_y[i-1] + i * blk_x[i];

  VL del_y(N+1);
  for(LL y:qs[1]){
	if(y > N) continue;
	ans -= blk_y[N] - blk_y[y-1];
	++del_y[y];
  }

  LL acc = 0;
  VL blk_z(N+1);
  for(LL i=1;i<=N;++i){
	acc += del_y[i];
	blk_z[i] = blk_z[i-1] + (i - acc) * blk_x[i];
  }
  for(LL z: qs[2]){
	if(z > N) continue;
	ans -= blk_z[N] - blk_z[z-1];
  }
  cout << ans << endl;

  return 0;
}



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

res = 'Yes'

for i in range(a-1, c-1):
    if s[i] == s[i+1] == '#':
        res = 'No'
        break

if res != 'No':
    if c < d:
        for i in range(b-1, d-1):
            if s[i] == s[i+1] == '#':
                res = 'No'
                break
    else:
        for i in range(b-2, d-1):
            if s[i] == s[i+1] == s[i+2] == '.':
                break
        else:
            res = 'No'

print(res)


Measured memory_bytes: 3572
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define SUP INT_MAX
#define INF INT_MIN
#define SSUP LLONG_MAX
#define IINF LLONG_MIN
#define W while
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vvll vector<vll>
#define it(r,v) for(auto r=v.begin();r!=v.end();r++)
#define all(v) v.begin(),v.end()
#define in insert
//#define For(i,n) for(ll i=0;i<n;i++)
//#define FOR(i,a,b) for(ll i=a;i<b;i++)
//#define Rev(i,n) for(ll i=n-1;i>=0;i--)
using namespace std;
const ll M = 1e9+7;
int main()
{
	/*#ifndef ONLINE_JUDGE
    	freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	#endif*/
	FIO
	string s;
	cin>>s;
	if(s[2]==s[3] && s[4]==s[5]){
	    cout<<"Yes\n";
	    
	}
	else cout<<"No\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main(int qtd, char* nome[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	cout << (n+1)/2 << endl;
	
	return 0;
}

Measured memory_bytes: 256
S = input()
DP = [0, 0, 0, 1]
p = 10 ** 9 + 7
for s in S[::-1]:
  dp = [0, 0, 0, 0]
  dp[3] = DP[3] * (3 if s == '?' else 1) % p
  for i in range(2, -1, -1):
    dp[i] += DP[i] * (3 if s == '?' else 1)
    dp[i] += DP[i + 1] if s == chr(65 + i) or s == '?' else 0
    dp[i] %= p
  DP = dp
print(DP[0] % p)

Measured memory_bytes: 3188
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <ctype.h>
using namespace std;

int main(){
  string S;
  cin >> S;

  int OKFlag = 0;
  if(S[0] == 'A'){
    int cFlag = 0;
    for(int i=2;i<S.size()-1;i++){
      if(S[i] == 'C'){
        cFlag++;
      }
    }

    if(cFlag == 1){
      int small = 0;
      for(int i=0;i<S.size();i++){
        if(islower(S[i]) != 0){
          small++;
        }
      }

      if(small == S.size()-2){
        OKFlag = 1;
      }

    }
  }

  if(OKFlag == 1){
    cout << "AC" << endl;
  }else{
    cout << "WA" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

int main()
{
    std::vector<int> A(5);
    int K;

    for (int i = 0; i < 5; i++) {
        std::cin >> A[i];
    }

    std::cin >> K;

    bool year = true;
    for (int i = 0; i < 4; i++) {
        for (int j = i; j < 5; j++) {
            if (std::abs(A[i] - A[j]) > K) {
                year = false;
                break;
            }
        }
        if (!year) break;
    }

    std::cout << ((year) ? "Yay!" : ":(") << std::endl;

    return 0;
}


 

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
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;}
//constexpr int INF = 1e18;



signed main(){
	int N;
	cin >> N;
	vector<string>v(N);
	REP(i, N) {
		cin >> v[i];
	}
	vector<vector<vector<int>>>vs;
	REP(i, N) {
		vector<vector<int>>tmp(v[i].size() + 1, vector<int>(26));
		REP(j, v[i].size()) {
			REP(k, 26) {
				tmp[j + 1][k] += tmp[j][k] + (v[i][j] - 'a' == k);
			}
		}
		vs.emplace_back(tmp);
	}
	vector<int>id(N);
	iota(ALL(id), 0);
	auto dfs = [&](auto&&f, vector<int>&a, int tail) -> long long {
		vector<int>cnt(26);
		REP(i, a.size()) {
			if(v[a[i]].size() - tail == 1) {
				++cnt[v[a[i]][0] - 'a'];
			}
		}
		long long ret = 0;
		REP(i, a.size()) {
			REP(j, 26) {
				int t = vs[a[i]][vs[a[i]].size() - tail - 1][j] - vs[a[i]][0][j];
				if(t) ret += cnt[j];
			}
		}
		ret -= accumulate(ALL(cnt), 0ll);
		vector<vector<int>>next(26);
		REP(i, a.size()) {
			if(v[a[i]].size() - tail == 1) continue;
			next[v[a[i]][v[a[i]].size() - tail - 1] - 'a'].emplace_back(a[i]);
		}
		REP(i, 26) {
			if(next[i].size() == 0) continue;
			ret += f(f, next[i], tail + 1);
		}
		return ret;
	};
	out(dfs(dfs, id, 0));
}

Measured memory_bytes: 1002916
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector <int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  bool good = false;
  auto iter = [&] () {
    vector <int> bal(n);
    for (int i = 0; i < n; i++) {
      int l = max(0, i - a[i]);
      int r = min(n - 1, i + a[i]);
      bal[l]++;
      if (r + 1 < n) bal[r + 1]--;
    }
    for (int i= 1; i < n; i++) bal[i] += bal[i - 1];
    if (a == bal) {
      good = true;
    }
    a = bal;
  };
  for (int i = 0; i < k; i++) {
    iter();
    if (good) break;
  }
  for (int x : a) cout << x << ' ';
  cout << endl;
}


Measured memory_bytes: 4952
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

using ll = long long;
using ld = long double;

#ifdef EBUG
#define debug(x) cout << "\033[31m" << #x << ": " << x << "\033[0m\n";
#else
#define debug(x)
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

ll x;

int main() {
  cin >> x;
  rep(i, 10000) {
    ll a = i;
    rep(j, 20000) {
      ll b = -10000 + j;
      if (a < b) {
        break;
      }
      if (a * a * a * a * a - b * b * b * b * b == x) {
        cout << a << " " << b << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3596
def solve():
    a, b, x = read()
    result = think(a, b, x)
    write(result)


def read():
    return read_int(3)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a, b, x):
    result = b // x - a // x
    if a % x == 0:
        result += 1
    return result


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
// std::cout << std::setprecision(2) << 3.141; // "3.1"
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
// #include <bits/stdc++.h> all

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;

static const int giga = pow(10,9);
// double pi = 3.141592653589793238463;

int main(void){
  int n; cin >> n;
  vector<int> d(n);
  for(int i = 0; i < n; i++){
    int temp; cin >> temp;
    d[i] = temp;
  }

  sort(d.begin(), d.end(), greater<int>());

  if(d[n/2-1] - d[n/2] >= 0){
    cout << d[n/2-1] - d[n/2]  << endl;
  } else {
    cout << 0 << endl;
  }


  return 0;
}

Measured memory_bytes: 640
from collections import defaultdict
p_y = defaultdict(set)

N,M = map(int,input().split())
PY = [[int(x) for x in input().split()] for _ in range(M)]
for p,y in PY:
        p_y[p].add(y)

def set_rank(retu):
        return {x:i for i,x in enumerate(sorted(retu), 1)}

p_y = {p:set_rank(retu) for p,retu in p_y.items()}
for p,y in PY:
        print('{:06g}{:06g}'.format(p,p_y[p][y]))

Measured memory_bytes: 85760
w = []
v = []
n, W = map(int, input().split())
#dp = [[0 for i in range(n)] for j in range(W)]
dp = [[None for i in range(W+1)] for j in range(n+1)]

for i in range(n):
#    v1, v2 = map(int, input().split())
    v2, v1 = map(int, input().split())
    w.append(v1)
    v.append(v2)

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))




Measured memory_bytes: 24080
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b){
    return a*b/gcd(a, b);
}
int main(){
	long long a, b, c, d;
	cin >> a >> b >> c >> d;
    cout << (b-a+1)-(b/c-(a-1)/c)-(b/d-(a-1)/d)+(b/lcm(c,d)-(a-1)/lcm(c,d)) << endl;
}

Measured memory_bytes: 256
/*
 * ID: 3039
 * Problem: Special Chat
 */

#include <stdio.h>

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

    int given_point = 0;
    int unit[4] = {10000, 5000, 1000, 500};
    int i;
    for (i = 0; i < 4; i++) {
        given_point += (point / unit[i]) * unit[i];
        point %= unit[i];
    }
    printf("%d\n", given_point);

    return 0;
}



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

int main(void)
{
	unsigned long long n,m,p;
	cin >> n >> m;
	
	if(2*n > m){//n>m/2
		cout << m/2 << endl;
	}else if(2*n == m){
		cout << n << endl;
	}else if(2*n < m){//n<m/2.0
		m -= 2*n;
		cout << n+m/4 << endl;
	}
	return 0;
}


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

int main(){
  string s,t;
  cin >> s >> t;
  bool ans = 1;
  for(int i = 0;i < s.size();i++){
    if(s.at(i) != t.at(i)){
      ans = 0;
      break;
    }
  }
  
  if(ans){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
  return 0;
}

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

typedef long long ll;
typedef pair<int,int> P;
ll const mod = 1e9+7;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    int n,k;
    cin >> n >> k;
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(n+1,vector<ll>(n*n+1,0)));
    dp[0][0][0] = 1;
    for (int i = 0;i < n;++i) for (int j = 0;j < n;++j) for (int l = 0;l+2*j < n*n;++l) {
        if (j) (dp[i+1][j-1][l+2*j] += j*j*dp[i][j][l]) %= mod;
        (dp[i+1][j][l+2*j] += (2*j+1)*dp[i][j][l]) %= mod;
        (dp[i+1][j+1][l+2*j] += dp[i][j][l]) %= mod;
    }
    cout << dp[n][0][k] << endl;
    return 0;
}

Measured memory_bytes: 52224
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


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

	int n, q;
	cin >> n;
	vector<int>S(n);
	for (int i = 0; i < n; ++i)cin >> S[i];
	sort(S.begin(), S.end());
	cin >> q;
	vector<int>T(q);
	for (int i = 0; i < q; ++i)cin >> T[i];
	sort(T.begin(), T.end());
	int ans = 0;
	for (int i = 0; i < q; ++i) {
		if(binary_search(S.begin(), S.end(), T[i]))++ans;
	}cout << ans << endl;
}

Measured memory_bytes: 1252
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
const int maxt=1e9+5;
struct thing{
	int last,ed;
}a[maxn];

bool cmp(thing a,thing b){
	if(a.ed==b.ed)return a.last>b.last;
	return a.ed<b.ed;
}

bool vis[maxt];

int main(){
	int n,x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a[i].last,&a[i].ed);
	}
	sort(a+1,a+n+1,cmp);
	int total=0;
	for(int i=1;i<=n;i++){
		total+=a[i].last;
		if(total>a[i].ed){
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 3584
# input
A, B, C, D = map(int, input().split())

ans = 0

if A <= D:
    if A >= C:
        if B >= D:
            ans = D - A
        else:
            ans = B - A
if C <= B:
    if A < C:
        if B >= D:
            ans = D - C
        else:
            ans = B - C

print(ans)


Measured memory_bytes: 2940
a, b, k = gets.chomp.split(' ').map(&:to_i)
num_arr = []

(1..a).each do |n|
  break if n > b
  
  if (a % n == 0) && (b % n == 0)
    num_arr << n
  end
end


print num_arr[num_arr.length-k]

Measured memory_bytes: 1916
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;

int main(){

    int n;
    cin >> n;

    int div4 = 0;
    int div2 = 0;
    long long val;
    for(int i = 0; i < n; i++){
        cin >> val;
        if(val % 4 == 0){
            div4 ++;
        }
        else if(val % 2 == 0){
            div2 ++;
        }  
    }

    if(div2 == 0){
        if(2 * div4 + 1 >= n){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
    else{
        if(div2 + 2 * div4 >= n){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }

    }

}

Measured memory_bytes: 384
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cstdio>
#include <iomanip>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define queint queue<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>//大きい順
#define pqg priority_queue<int,vec,greater<int>>//小さい順
#define pb push_back
#define vec vector<int>
#define vecvec vector<vector<int>>
#define vecll vector<ll>
#define vecvecll vector<vector<ll>>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
#define mp make_pair
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int main(){
    int n=in(),k=in();
    int ans=0;
    if(k==1)ans=0;
    else ans=n-k;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
<?php
for ($i = 0; $i < 10; $i++) {
    $w[] = trim(fgets(STDIN));
}
for ($i = 0; $i < 10; $i++) {
    $k[] = trim(fgets(STDIN));
}
rsort($w);
rsort($k);
$sum_top_3_of = function($array) {
    return array_sum(array_slice($array, 0, 3));
};
echo $sum_top_3_of($w) ." ". $sum_top_3_of($k) . PHP_EOL;


Measured memory_bytes: 9256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <utility>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long int ll;

int main() {
  int N,M;
  cin>>N>>M;
  
  vector<int> a(M);
  vector<int> b(M);
  vector<int> bkt(N+1);
  
  for(int i=0;i<M;++i){
    cin>>a[i]>>b[i];
    ++bkt[a[i]];
    ++bkt[b[i]];
  }
  
  for(int i=1;i<=N;++i){
    cout<<bkt[i]<<endl;
  }
  
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define int long long
#define pii pair <int, int>
#define XX first
#define YY second

// constants:
const int mn = 200005;
const int mod = 1000000007;
const long long inf = 4444444444444444444;
const int sminf = 1111111111;
const bool is_multitest = 0;
const bool is_interactive = 0;

// i/o methods:
const bool input_from_file = 0;
const bool output_to_file = 0;
#define filename ""
#define in_extension "inp"
#define out_extension "out"

// data preprocessing: (e.g.: divisor generating, prime sieve)
void preprocess()
{
    
}

// global variables:
int n;
vector <int> p;
vector <int> alp;
// main solution goes here:
void execute(int test_number)
{
    cin>>n;
    for (int i=2; i*i<=n; i++) if (n%i==0) {
        p.push_back(i);
        int ans = 0;
        while (n%i==0) {
            n/=i;
            ans ++;
        }
        alp.push_back(ans);
    }
    if (n>1) {
        alp.push_back(1);
        p.push_back(n);
    }
    int ans = 0;
    for (int x:alp) {
        // cerr<<x<<" ";
        int l = 0, r = 1000000;
        while (r>l) {
            int mid = (l+r)/2;
            if (mid*(mid+1)/2 <= x) l=mid+1;
            else r=mid;
        }
        ans+=l-1;
    }
    cout<<ans;
}
// REMEMBER TO CHOOSE TEST METHODS
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Solution by low_



















signed main()
{
#ifdef lowie
    if (!is_interactive)
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
#else
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);
#endif
    if (!is_interactive)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    preprocess();
    int ntest;
    if (is_multitest) cin >> ntest;
    else ntest = 1;

    for (int testno = 1; testno <= ntest; testno++)
    // use for instead of while to serve facebook hacker cup test format
    {
        execute(testno); // only start coding in this function, not in main
    }
}
// Template by low_
// Contact me via mail: ttuandung1803@gmail.com
// ...or codeforces: www.codeforces.com/profiles/low_
// ...or if you're interested in food: www.instagram.com/lowie.exe/

Measured memory_bytes: 3660