akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int H, W;
	cin >> H >> W;
	vector<vector<char>> a(H, vector<char>(W));
	for(int i=0; i<H; ++i) for(int j=0; j<W; ++j) cin >> a[i][j];
	queue<int> hight;
	queue<int> width;
	bool flag = true;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			if(a[i][j]=='#'){
				flag = false;
				break;
			}
		}
		if(flag) hight.push(i);
		flag = true;
	}
	for(int i=0; i<W; ++i){
		for(int j=0; j<H; ++j){
			if(a[j][i]=='#'){
				flag = false;
				break;
			}
		}
		if(flag) width.push(i);
		flag = true;
	}
	int h, w;
	int count = 0;
	for(int i=0; i<H; ++i){
		if(i==0){
			if(hight.empty()){
				h = H+100;
			}else{
				h = hight.front();
				hight.pop();
				hight.push(h);
			}
		}
	if(i==h){
			h = hight.front();
			hight.pop();
			hight.push(h);
			continue;
		}
		++count;
		for(int j=0; j<W; ++j){
			if(j==0 && count == 1){
				if(width.empty()){
					w = W+100;
				}else{
					w = width.front();
					width.pop();
					width.push(w);
				}
			}
			if(j==w){
				w = width.front();
				width.pop();
				width.push(w);
				continue;
			}
			cout << a[i][j];
		}
	cout << endl;
	}
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>

using namespace std;
using ull=unsigned long long;

long dp[101][100001];

long knap(int N, int W, const vector<int>& w, const vector<int>& c)
{
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            if (i == 0 or j == 0)
                dp[i][j] = 0;
            else if (j >= w[i])
                dp[i][j] = max(dp[i-1][j], c[i] + dp[i-1][j - w[i]]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    
    return dp[N][W];
}

int main() {
    int N, W; cin >> N >> W;
    
    vector<int> w(N+1), c(N+1);
    
    for (int i = 1; i <= N; i++)
    {
        cin >> w[i] >> c[i];
    }
    
    long ans = knap(N, W, w, c);
    
    cout << ans << "\n";
}

Measured memory_bytes: 79104
N=int(input())
s=[]
for i in range(N):
  s.append(str(input()))
M=int(input())
t=[]
for i in range(M):
  t.append(str(input()))
li=list(set(s))
ans=[]
for i in range(len(li)):
  ans.append(s.count(li[i])-t.count(li[i]))
print(max(max(ans),0))

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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define odd(x) ((x)&1)
#define even(x) (!odd(x))
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(auto i=0;i<n;++i)
#define LOOP_IT(it,s) for(auto it=(s).begin();it!=(s).end();++it)
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TEST_CASE int tc;cin>>tc;while(tc--)


#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}


template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif



int main(int argv, char* argc[])
{
    FASTIO

    int x,y;bool f=0;
    cin>>x>>y;
    int c = x*2;
    c = y-c;
    if(even(c)&&(c<=2*x))
        f=1;
    if(c<0)
        f=0;
    cout<<(f?"Yes":"No");


    return 0;
}


Measured memory_bytes: 3640
use std::collections::HashSet;

fn main() {
    let num = read().trim().parse().unwrap();
    let mut a: HashSet<u32> = vec!().into_iter().collect();
     
    for i in 0..num {
        a.insert(read().trim().parse().unwrap());
    }

    println!("{}", a.len());
}

fn read() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s);
    s
}


Measured memory_bytes: 4352
# ABC081C - Not so Diverse (ARC086C)
from collections import Counter


def main():
    N, K, *A = open(0).read().split()
    C, K = list(Counter(A).values()), int(K)
    C.sort(reverse=1)
    ans = sum(C[K:])
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 35988
#include <iostream>
#include <map>
#include <vector>
#include <limits>

using ll = long long;

const ll INF = std::numeric_limits<ll>::max();

int main() {
    int N, K;
    ll L, R;
    std::cin >> N >> K >> L >> R;

    int M = N / 2;
    std::vector<ll> a(M);
    for (auto& e : a) std::cin >> e;

    std::vector<std::map<ll, ll>> cnt(M + 1);
    for (int k = 0; k <= M; ++k) {
        cnt[k][-INF] = cnt[k][INF] = 0;
    }

    for (int b = 0; b < (1 << M); ++b) {
        int k = __builtin_popcount(b);
        ll sum = 0;
        for (int i = 0; i < M; ++i) {
            if ((b >> i) & 1) sum += a[i];
        }
        if (!cnt[k].count(sum)) cnt[k][sum] = 0;
        ++cnt[k][sum];
    }

    // 累積和に変換
    for (int k = 0; k <= M; ++k) {
        ll psum = 0;
        for (auto& p : cnt[k]) {
            psum += p.second;
            p.second = psum;
        }
    }

    M = N - N / 2;
    a.resize(M);
    for (auto& e : a) std::cin >> e;

    ll ans = 0;
    for (int b = 0; b < (1 << M); ++b) {
        int k = __builtin_popcount(b);
        if (K - k < 0 || N / 2 < K - k) continue;

        ll sum = 0;
        for (int i = 0; i < M; ++i) {
            if ((b >> i) & 1) sum += a[i];
        }
        auto l = --cnt[K - k].lower_bound(L - sum);
        auto r = --cnt[K - k].upper_bound(R - sum);
        ans += r->second - l->second;
    }

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



Measured memory_bytes: 68612
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int a,b;
    cin >> a >> b;
    if (a > 8 || b > 8) cout << ":(" << endl;
    else cout << "Yay!" << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 256
from collections import deque
n, *A = map(int, open(0).read().split())
B = deque()

rev = False
for i in range(n):
  if rev:
    B.appendleft(A[i])
  else:
    B.append(A[i])
  rev = not rev
if rev:
  B.reverse()
print(*B)
  

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

#define ll long long int
#define str string
#define ALL(a)  (a).begin(),(a).end()
#define P pair<ll,ll>

using Graph = vector<vector<int>>;

const int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
ll INFL = 1ll << 60, INF = 1 << 30, mod = 1e9 + 7, Min = INFL, Max = -1;
ll a, b, c, n, sum, A[500010], B[500000], rui[500000], dp[5000];
str S; bool check = true;	vector<ll> v;



int main() {
	//Code Line
	cin >> n >> S;
	for (int i = 0; i < S.size(); i++) {

		a = S[i] + n;
		if (a <= 90)cout << (char)a;
		else cout << (char)(a - 26);
	}


	return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> pa;

#define fst first
#define snd second
#define pb push_back

const int maxn=1000005,maxm=306;
const double pi=acos(-1.0);
const ll mod=1000000007;
const double eps=1e-8;

int n;
int a[maxn],b[maxn];


int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d %d",a+i,b+i);
	sort(a,a+n);sort(b,b+n);
	if(n%2)
    {
        printf("%d\n",b[n/2]-a[n/2]+1);
    }
    else
    {
        printf("%d\n",(b[n/2]+b[n/2-1])-(a[n/2]+a[n/2-1])+1);
    }
    return 0;
}


Measured memory_bytes: 5332
def readinput():
    l,r=map(int,input().split())
    return l,r

def main(l,r):
    ans=2018
    for i in range(l,min(l+2019,r+1)):
        for j in range(i+1,min(l+2019,r+1)):
            ans=min( ((i%2019) * (j%2019))%2019, ans )
    return ans

if __name__=='__main__':
    l,r=readinput()
    ans=main(l,r)
    print(ans)


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

#define ll  long long
#define endl "\n" 
#define FOR(n) for(int i=0 ; i<n ; i++)
#define FORa(a, n) for(ll i=a ; i<=n ; i++)
ll mod=1000000007;
ll inf=1e9;

int gcd(int a , int b){
  if(a==0) return b;
  return gcd(b%a , a);
}
void solve()
{
  string s;
  ll ans=0, n;
  cin >> n;
  ans=n-1;
  for(int i=2 ; i<=n/2 ; i++){
    ans+=((n+i-1)/(i));
  }
  if(n&1) ans++;
  cout << ans << endl;


}

  


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t=1;
  //cin >> t;
  while(t--)
    solve();
    return 0 ;
}


Measured memory_bytes: 3644
#include <iostream>
#include <cmath>
#define MAX 100000

using namespace std;

int v[MAX + 5], dp[MAX + 5];
int main()
{
    int n;

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

    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> v[i];

    dp[0] = 0;
    dp[1] = abs(v[1] - v[0]);

    for(int i = 2; i < n; i++)
        dp[i] = min(dp[i - 1] + abs(v[i] - v[i - 1]), dp[i - 2] + abs(v[i] - v[i - 2]));

    cout << dp[n - 1];

    return 0;
}


Measured memory_bytes: 1024
n,k = map(int,input().split())

ok,ng = 0,k+1
while ng-ok>1:
    mid = (ng+ok)//2

    s = 0
    m = mid
    for i in range(n):
        s += m
        m //= 2
        if m == 0:
            break

    if s <= k:
        ok = mid
    else:
        ng = mid

print(ok)



Measured memory_bytes: 5600
#include <bits/stdc++.h>
#define loop(n) for(ll i=0;i<n;i++)
#define loopj(n) for(ll j=0;j<n;j++)
#define loopR(i,a,b,c) for(ll i=a;i>=b;i-=c)
#define rng(i,a,b,c) for(ll i = a; i<b;i+=c)
#define loop2(i,a,b) for(long long i = a; i>=b;i--)
#define loop3(j,a,b) for(int j = a; j<b;j++)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll long long   
#define ld long double
#define SET set<ll>
#define pb push_back
#define mp make_pair
#define gc getchar_unlocked

using namespace std; 

//cout<<setprecision(4) << fixed;
/*int compare(string str1, string str2){
   if(str1.length() < str2.length())
   return 1;
   return 0;
}*/
/* int to string-
int c=0;
stringstream ss;
ss<<c;
string str=ss.str();*/
/* STRING TO INT
string s;
	cin>>s;
	reverse(s.begin(),s.end());
	stringstream ss(s);
	ll a=0;
	ss>>a;*/
//about maps
/*unordered_map <int,int> g;
 
    i1 = std::min_element(v + 2, v + 5); 
    cout<<*i1;
 
//getline

cin.ignore();
getline(cin,s);    

*/
// no getchar_unlocked on Windows so call _getchar_nolock
/*

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

inline int getchar_unlocked() { return _getchar_nolock(); }
inline ll read() {  
 ll n=0;  
 char p=getchar_unlocked();  
 while((p<'0'||p>'9')&&p!=EOF)  
 p=getchar_unlocked();  
 while(p>='0'&&p<='9')  
 {  
 n = (n<< 3) + (n<< 1) + (p - '0');  
 p=getchar_unlocked();}  
 return n;
}

void dfs(vector<ll> adj[],ll vis[],ll u)
{

	if(vis[u]==0)
	{
		cout<<u<<' ';
		vis[u]=1;
		for(auto x:adj[u])
		{
			if(vis[x]==0 )
			{
			dfs(adj,vis,x);
		    }
		}
	}
}
*/



void go()
{
ll a,b,c,d;

cin>>a>>b>>c>>d;

ll x,y;

ll ans1=b*d;
ll ans2=b*c;
ll ans3=a*c;
ll ans4=a*d;

x=max(ans1,ans2);
y=max(ans3,ans4);

cout<<max(x,y);


}





int main() 
{ 
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/	
	
int t;

fast;

//cin>>t; 

//loop(t)
go();
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }



int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	n -= 2;
	int H = n, W = n;
	vector<int> height(n, n);
	vector<int> width(n, n);
	long long answer = 0;
	while(q--) {
		int type, x;
		scanf("%d%d", &type, &x);
		x -= 2;
		assert(0 <= x && x <= n - 1);
		if(type == 1) {
			if(x < W) {
				answer += min(H, height[x]);
				height[x] = -1; // will not use this again
				// debug() << imie(x) imie(height[x]);
				for(int i = x + 1; i < W; ++i) {
					height[i] = H;
				}
				W = x;
			}
			else {
				answer += height[x];
				height[x] = -1;
			}
		}
		else {
			swap(H, W);
			swap(height, width);
			if(x < W) {
				answer += min(H, height[x]);
				height[x] = -1; // will not use this again
				for(int i = x + 1; i < W; ++i) {
					height[i] = H;
				}
				W = x;
			}
			else {
				answer += height[x];
				height[x] = -1;
			}
			swap(H, W);
			swap(height, width);
		}
		debug() << imie(answer) imie(H) imie(W) imie(height) imie(width);
	}
	printf("%lld\n", (long long) n * n - answer);
}


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

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

typedef long long ll;

const int MAX = 1000000;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    COMinit();
    ll X, Y;
    cin >> X >> Y;
    if ((X + Y) % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    int i = (X + Y) / 3;
    if (X < i or X > 2 * i) {
        cout << 0 << endl;
        return 0;
    }

    // i_C_(X-i)が答え
    cout << COM(i, X - i) << endl;
}


Measured memory_bytes: 23680
#include <iostream>
#include<stdio.h>
#include <math.h>
using namespace std;


int main(){
  string S;
  /*                                                                                         
AC x C0                                                                                      
WA x C1                                                                                      
TLE x C2                                                                                     
RE x C3                                                                                      
  */
  int N;
  int C0,C1,C2,C3=0;
  C0=C1=C2=C3=0;
  cin >> N;

  for (int i=0; i<N; i++){
    cin >>S;
    if (S=="AC"){C0=C0+1;}
    if (S=="WA"){C1=C1+1;}
    if (S=="TLE"){C2=C2+1;}
    if (S=="RE"){C3=C3+1;}

  }
  cout<<"AC x "<<C0<<endl;
  cout<<"WA x "<<C1<<endl;
  cout<<"TLE x "<<C2<<endl;
  cout<<"RE x "<<C3<<endl;


  return 0;




}




Measured memory_bytes: 3536
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			br.readLine();
			String[] str_array = br.readLine().split(" ");
			for(int i = str_array.length -1 ; i >= 0 ; i--) {
				System.out.printf("%s", str_array[i]);
				if (i != 0) System.out.printf(" ");
			}
			System.out.println();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}



Measured memory_bytes: 24776
n, k = gets.to_s.split.map{|t| t.to_i }
a    = gets.to_s.split.map{|t| t.to_i }.sort
f    = gets.to_s.split.map{|t| t.to_i }.sort.reverse

m = []
n.times do |i|
   m << [a[i] * f[i], a[i], f[i]]
end

m.sort_by!{|(af,_, _)| -af }

ans = (0 .. (10**12)).bsearch do |x|
  
  k_x = 0
  m.each do |(m_i, a_i, f_i)|
    break if m_i <= x
    k_x += ( m_i - x + f_i - 1 ) / f_i
  end
  
  k_x <= k
end

puts ans

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



int main() {
    int N, K;
    cin >> N >> K;
    vector<double > P(N);
    for (int i = 0; i < N; i++) cin >> P[i];

    for (int i = 0; i < N; i++) {
        P[i] = (P[i] + 1) / 2;
    }

    double res = 0;
    int left = 0, right = 0;
    double sum = 0;
    for (int i = 0; i < N; i++) {
        int next_left = i;
        int next_right = min(i + K, N);

        while (next_left > left) {
            sum -= P[left++];
        }
        while (next_right > right) {
            sum += P[right++];
        }
        res = max(res, sum);
    }

    printf("%.9f\n", res);
    return 0;
}

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

using namespace std;

#ifdef WIN32
	#define I64 "%I64d"
#else
	#define I64 "%lld"
#endif

typedef long long ll;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"


int main()
{
	#ifdef LOCAL
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	#endif

	ll n, m;

	scanf(I64 "" I64, &n, &m);

	ll ans = min(n, m / 2);
	n -= ans;
	m -= ans * 2;
	ans += m / 4;
	printf(I64"\n", ans);

	return 0;
}


Measured memory_bytes: 256
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/25 09:33:21 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1e9+7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

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

// TOP
void	Main()
{
	int	h, w;
	cin >> h >> w;

	vector<string> V(h + 2);
	rep(i, h)
	{
		V.at(i + 1) = ".";
		string	s;
		cin >> s;
		V.at(i + 1) += s;
		V.at(i + 1) += ".";
	}
	rep(i, w + 2)
		V.at(0) += ".";
	V.at(h + 1) = V.at(0);
	int	y, x;
	y = h;
	x = w;
	while (!(x == 1 && y == 1))
	{
		if (V.at(y + 1).at(x - 1) == '#' || V.at(y - 1).at(x + 1) == '#' || (V.at(y - 1).at(x) == '#' && V.at(y).at(x - 1) == '#'))
		{
			cout << "Impossible" << endl;
			return ;
		}
		if (V.at(y - 1).at(x) == '#')
			y--;
		else if (V.at(y).at(x - 1) == '#')
			x--;
	}
	cout << "Possible" << endl;
}
// END

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int shift=2999;
int n;
double p[3000];
double dp[3000][6000];
double ans; 
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>p[i];
	}
	for(int i=0;i<=6000;++i){
		dp[0][i]=1.0;
	}
	for(int i=1;i<=n;++i){
		for(int j=-(i-1);j<=(i-1);++j){
			dp[i][j+1+shift]+=dp[i-1][j+shift]*p[i];
			dp[i][j-1+shift]+=dp[i-1][j+shift]*(1-p[i]);
		}
	}
	for(int i=1;i<=n;++i){
		ans+=dp[n][i+shift];
	}
	cout<<fixed<<setprecision(10)<<ans<<'\n';
	return 0;
}

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

int main(){
	int N;
	string S;
	cin >> N >> S;
	
	int ans=0;
	
	for(int p=0;p<1000;p++){
		int a,b,c;
		c=p%10;
		b=((p-c)/10)%10;
		a=p/100;
		
		bool fa=false,fb=false,fc=false;
		for(int i=0;i<N;i++){
			if(!fa)if((S[i]-'0')==a){
				fa=true;
				continue;
			}
			if(fa && (!fb))if((S[i]-'0')==b){
				fb=true;
				continue;
			}
			if(fa && fb && (!fc))if((S[i]-'0')==c){
				fc=true;
				continue;
			}
		}
		if(fa && fb && fc){
			//cout << p << endl;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define ll long long



int main()
{
    ll n;

    cin>>n;


    ll ans=1,s=0;
    while(n!=1){

        n=(n/2);


        ans=ans*2;


        s+=ans;

    }





   cout<<s+1<<endl;








    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
q = int(input())
s = sum(a)

cnt = [0]*(10**5+1)
for i in a:
  cnt[i] += 1
  
for i in range(q):
  b, c = map(int, input().split())
  s = s - cnt[b]*b + cnt[b]*c
  cnt[c] += cnt[b]
  cnt[b] = 0
  print(s)


Measured memory_bytes: 20824
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(v)    begin(v), end(v)
#define in        []{lint n; cin>>n; return n;}()

int main(){
    int N = in;
    lint K = in;
    vector<lint> A(N);
    rep( i, N ) A[i] = in;

    lint X = 0;
    for( lint i = lint(1)<<50; i!=0; i>>=1 ) {
        if( X + i > K ) continue;
        int count = 0;
        rep( j, N ) if( i & A[j] ) count ++;
        if( count <= N/2 ) X ^= i;
    }

    lint f = 0;
    rep( i, N ) f += X ^ A[i];

    cout << f << "\n";
}


Measured memory_bytes: 1024
N, A, B = map(int, input().split())
MOD = 10**9 + 7

def pow_mod(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return pow_mod(x * x % MOD, n // 2) % MOD
    else:
        return x * pow_mod(x * x % MOD, n // 2) % MOD

def cmb_k(k):
    X = 1
    for i in range(N-k+1, N+1):
        X = X * i % MOD

    Y = 1
    for i in range(1,k+1):
        Y = Y * i % MOD

    Y_inv = pow_mod(Y, MOD-2)
    return X * Y_inv % MOD

ans = pow_mod(2, N) - 1 - cmb_k(A) - cmb_k(B)
ans %= MOD
print(ans)


Measured memory_bytes: 38640
#include <iostream>
#include <vector>

using namespace std;

int main(void) {
  int N;
  cin >> N;
  vector<vector<int>> A;
  A.resize(2);
  for (auto& r : A) r.resize(N);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int s = 0;
    int j;
    for (j = 0; j <= i; j++) s += A[0][j];
    --j;
    for (; j < N; j++) s += A[1][j];
    ans = max(ans, s);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vc=vector<char>;
using vvc=vector<vc>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N,M;
  cin >> N >> M;
  vi A(N),B(N);
  vvi rew(M+1);
  rep(i,N) {
    cin >> A[i] >> B[i];
    if(A[i]<=M) rew[A[i]].push_back(B[i]);
  }
  
  int ans=0;
  priority_queue<int> que;
  rep2(i,1,M+1) {
    for(int x:rew[i]) que.push(x);
    if(!que.empty()) {
      ans+=que.top();que.pop();
    }
  }
  
  cout << ans << endl;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(W,n)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {REP(aaa,i){REP(bbb,j)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

ll ans[] = {4,4,9,4,7,10,18,5,21,8,16,11,11,19,19,6,14,22,22,9,9,17,17,12,25,12,113,20,20,20,108,7,28,15,15,23,23,23,36,10,111,10,31,18,18,18,106,13,26,26,26,13,13,114,114,21,34,21,34,21,21,109,109,8,29,29,29,16,16,16,104,24,117,24,16,24,24,37,37,11,24,112,112,11,11,32,32,19,32,19,94,19,19,107,107,14,120,27,27,27};
set<ll> s;

int main(){

	int s;cin >> s;cout << ans[s-1] << endl;

	return 0;
}


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

typedef struct {
    double x,y;
} sP;
sP makeS(sP p1,sP p2){
    sP s;
    s.x=(2*p1.x+p2.x)/3;
    s.y=(2*p1.y+p2.y)/3;
    return s;
}
sP makeT(sP p1,sP p2){
    sP t;
    t.x=(p1.x+2*p2.x)/3;
    t.y=(p1.y+2*p2.y)/3;
    return t;
}
sP makeU(sP s,sP t){
    sP u;
    u.x=(t.x-s.x)*cos(M_PI/3)-(t.y-s.y)*sin(M_PI/3)+s.x;
    u.y=(t.x-s.x)*sin(M_PI/3)+(t.y-s.y)*cos(M_PI/3)+s.y;
    return u;
}
void kock(int n,sP p1,sP p2){
    if (n == 0){
        return;
    }
    sP s;
    sP t;
    sP u;
    s=makeS(p1,p2);
    t=makeT(p1,p2);
    u=makeU(s,t);
    // p1, p2 から s, t, u を計算

    kock(n-1, p1, s);
    cout<<s.x<<" "<<s.y<<endl;
    kock(n-1, s, u);
    cout<<u.x<<" "<<u.y<<endl;
    kock(n-1, u, t);
    cout<<t.x<<" "<<t.y<<endl;
    kock(n-1, t, p2);
}
int main(){
    int n;
    cin>>n;
    sP p1={0,0};
    sP p2={100,0};
    cout<<fixed<<p1.x<<" "<<p1.y<<endl;
    kock(n,p1,p2);
    cout<<fixed<<p2.x<<" "<<p2.y<<endl;
}


Measured memory_bytes: 3216
import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int,input().split()))

'''
import random
N = 100000
P = list(range(1,N+1))
#random.shuffle(P)
'''

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

P2 = [[[p,i],[0,0]] for i,p in enumerate(P)]

max2 = lambda x,y : sorted(x+y,reverse=True)[:2]

seg = SegmentTree(P2,max2,[[0,0],[0,0]])

cand = [[0,N]]

ans = 0
visited = set([])
while cand:
    #print(cand)
    temp = []
    for l,r in cand:
        if r-l < 2:
            continue
        if (l,r) in visited:
            continue
        visited.add((l,r))
        (m1,i1), (m2,i2) = seg.get(l,r)
        #print(P[l:r],m1,m2)
        i1,i2 = (i1,i2) if i1 < i2 else (i2,i1)
        ans += m2 * (i1-l+1) * (r-i2)
        temp.append([l,i2])
        temp.append([i1+1,r])
    cand = temp

print(ans)





Measured memory_bytes: 189924
#include<bits/stdc++.h>
using namespace std;
long long a[3];
int main(){
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    cout<<((a[0]&1&a[1]&1&a[2]&1)?a[0]*a[1]:0)<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
int arr[200005];
int main()
{
	// freopen("AGC032-E.in", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n << 1; i++)
		scanf("%d", arr + i);
	std::sort(arr, arr + (n << 1));
	int l = 0, r = n, res = -1;
	while (l <= r)
	{
		int x = l + r >> 1;
		bool flg = true;
		for (int i = 0; i < x; i++)
			flg &= arr[n * 2 - x + i] + arr[n * 2 - x - i - 1] >= m;
		if (flg)
		{
			res = x;
			l = x + 1;
		}
		else
			r = x - 1;
	}
	int ans = 0;
	for (int i = 0; i < n - res; i++)
		ans = std::max(ans, arr[i] + arr[n * 2 - res * 2 - i - 1]);
	for (int i = 0; i < res; i++)
		ans = std::max(ans, arr[n * 2 - res + i] + arr[n * 2 - res - i - 1] - m);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 896
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> cnt(9, 0);
    int n;
    cin >> n;
    int a;
    rep(i,n){
        cin >> a;
        cnt[min(a/400,8)]++;
    }
    int mi = 0;
    rep(i,8) if(cnt[i] > 0) mi++;
    cout << max(1, mi) << " " << mi + cnt[8] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef unsigned long long ll;
const int maxn = 55;

int n;
struct P{
  int x,y;
  bool operator<(const P&a)const {
    return (x!=a.x?x<a.x:y<a.y);
  }
}p[maxn];

int solve(int dx, int dy){
  set<pair<int,int>>st;
  for(int i=0;i<n;i++){
    st.insert(make_pair(p[i].x,p[i].y));
  }
  int ret = 0;
  for(int i=0;i<n;i++){
    if(st.find(make_pair(p[i].x,p[i].y))==st.end())continue;
    ret++;
    int x = p[i].x,y=p[i].y;
    while(true){
      if(st.find(make_pair(x,y))==st.end())break;
      st.erase(make_pair(x,y));
      x+=dx,y+=dy;
    }
  }
  return ret;
}

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>p[i].x>>p[i].y;
  }
  sort(p,p+n);
  int ret = n;
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      ret=min(ret,solve(p[j].x-p[i].x,p[j].y-p[i].y));
    cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int ss=s.size();
    if (ss==1){
        if (s[0]=='P') cout<<'P';
        else cout<<'D';
        return 0;
    }
    for (int i=0; i<ss; i++){
        if (s[i]=='?'){
            if (i==0){
                if (s[1]!='P') s[0]='P';
                else s[0]='D';
            } else {
                if (s[i-1]=='P'||i==ss-1) s[i]='D';
                else {
                    if (s[i+1]!='P') s[i]='P';
                    else s[i]='D';
                }
            }
        }
        cout<<s[i];
    }
}

Measured memory_bytes: 3748
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int main(){

	int q,left,right;
	long long int table[2] = {0,0};
	char buf[2];

	scanf("%d",&q);

	for(int i = 0; i < q; i++){
		scanf("%d %s %d",&left,buf,&right);
		if(buf[0] == '('){
			table[0] += right;
		}else{
			table[1] += right;
		}

		if(table[0] == table[1]){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}

    return 0;
}

Measured memory_bytes: 2704
def main(n, a, b, p):
    _a, _ab, _b = 0, 0, 0

    for p in p:
        if p <= a:
            _a += 1
        elif a < p <= b:
            _ab += 1
        elif p > b:
            _b += 1

    print(min(_a, _ab, _b))


if __name__ == "__main__":
    n = int(input())
    a, b = map(int, input().split())
    p = list(map(int, input().split()))

    main(n, a, b, p)


Measured memory_bytes: 3064
#include <stdio.h>

struct Card{
  char mark;
  int num;
};


int Partition(struct Card A[], int left, int pivot, int right){
  int i, j;
  struct Card x, temp;
  x = A[right];
  i = pivot-1;
  for(j=pivot; j<right; j++){
    if(A[j].num<=x.num){
      i++;
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
	}
  }
  temp = A[i+1];
  A[i+1] = A[right];
  A[right] = temp;
  return i+1;
}


void quickSort(struct Card A[], int n, int p, int r){
  int q;
  if(p<r){
    q=Partition(A, n, p, r);
    quickSort(A, n, p, q-1);
    quickSort(A, n, q+1, r);
  }
}

void Merge(struct Card A[], int n, int left, int mid, int right){
  int i, j, k, n1, n2;
  struct Card L[100001/2+2], R[100001/2+2];
  n1 = mid - left;
  n2 = right - mid;
  for(i=0;i<n1;i++)
    L[i] = A[left+i];
  for(i=0;i<n2;i++)
    R[i] = A[mid+i];
  L[n1].num=2000000000;
  R[n2].num=2000000000;
  i=0;
  j=0;
  for(k=left;k<right;k++){
    if(L[i].num<=R[j].num){
      A[k]=L[i];
      i++;;
    }
    else{
      A[k]=R[j];
      j++;
    }
  }
}

void MergeSort(struct Card A[], int n, int left, int right){
  int mid;
  if (left+1<right){
    mid = (left + right)/2;
    MergeSort(A, n, left, mid);
    MergeSort(A, n, mid, right);
    Merge(A, n, left, mid, right);
  }
}
   


int main(){
  int n, i, j, v, stable=0;
  char s[10];
  struct Card A[100001], B[100001]; 
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%s %d", s, &v);
    A[i].mark=s[0];
    B[i].mark=A[i].mark;
    A[i].num=v;
    B[i].num=A[i].num;
  }

  quickSort(A, n, 0, n-1);
  MergeSort(B, n, 0, n);
  
  for(i=0; i<n; i++){
    if(A[i].mark==B[i].mark)stable++;
  }

  if(stable==n)printf("Stable\n");
  else printf("Not stable\n");
  for(i=0;i<n;i++){
    printf("%c %d\n",A[i].mark, A[i].num);
  }  
  return 0;
}

Measured memory_bytes: 2956
#include <bits/stdc++.h>
#define int long long

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a, i##_len=(b); i<i##_len; i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define all(box) box.begin(), box.end()

using namespace std;

using P = pair<int,int>;
using ll = long long;

const long long INF = LLONG_MAX/3;

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; }
inline void Yes (bool condition) { if(condition) { cout << "Yes" << endl; } else { cout << "No" << endl;} }

struct UnionFind{
	std::vector<int> par,siz;
	void init(int n){
		par.resize(n);
		for(int i=0;i<n;i++)par[i]=i;
		siz.resize(n,1);
	}
	UnionFind(int n){
		init(n);
	}
	int root(int n){
		if(par[n]==n)return n;
		else return par[n]=root(par[n]);
	}
	bool issame(int x,int y){
		return (root(x)==root(y));
	}
	bool marge(int a,int b){
		if(issame(a,b))return false;
		else{
			a=root(a),b=root(b);
			if(siz[a]<siz[b])swap(a,b);
			siz[b]+=siz[a];
			par[a]=par[b];
			return true;
		}
	}
	int size(int n){
		return siz[root(n)];
	}
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}
long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

const int MOD=998244353;
long long fac[510000], finv[510000], inv[510000];
long long MAX=510000;
bool COMinited=false;
long long COM(int n, int k){
	if(COMinited==false){
		fac[0] = fac[1] = 1;
    	finv[0] = finv[1] = 1;
    	inv[1] = 1;
    	for (int i = 2; i < MAX; i++){
        	fac[i] = fac[i - 1] * i % MOD;
        	inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        	finv[i] = finv[i - 1] * inv[i] % MOD;
    	}
		COMinited=true;
	}
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}
template< typename T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
signed main(){
	int n,m;
	cin>>n>>m;
	int a[110];
	int s=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		s+=a[i];
		a[i]*=4*m;
	}
	sort(a,a+n,greater<>());
	int cnt=0;
	for(int i=0;i<n;i++){
		if(a[i]>=s)cnt++;
	}
	if(cnt>=m)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <string.h>

using namespace std;

const int MAXV = 110;
const long long INF = (1LL<<32);

ifstream in("apsp.in");

int v, e;
long long int cost[MAXV][MAXV];

int min(int a,int b){
  if(a > b) return b;
  else return a;
}

void Floyd_Warshall(){
	for(int k = 0; k < v; ++k){
		for(int i = 0; i < v; ++i){
			if(cost[i][k]==INF) continue;
			for(int j = 0; j < v; ++j){	
				if(cost[k][j]==INF) continue;
				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}	
	}	
}

int main(){	
	int x, y, c;
	cin >> v >> e;
	for(int i = 0; i < v; ++i){
		for(int j = 0; j < v; ++j){
			 	if(i==j) 
			 		cost[i][j]=0;
      	else 
      		cost[i][j]=INF;
		}
  }	
	for(int i = 0; i < e; ++i){
		cin >> x >> y >> c;
		cost[x][y] = c;
	}		

	Floyd_Warshall();

	for(int i = 0; i < v; ++i){
		if(cost[i][i] < 0){
			cout << "NEGATIVE CYCLE" << '\n';
			return 0;
		}
	}
	for(int i = 0; i < v; ++i){
		for(int j = 0; j < v; ++j){
			if(cost[i][j] == INF)
				cout << "INF";
			else 
				cout << cost[i][j];
			if(j == v-1) 
				cout << '\n';
			else 
				cout << " ";
			}
	}
	return 0;
}



Measured memory_bytes: 3204
#include<iostream>
#include<vector>
#include<algorithm>
int n,x;
std::vector<int> vec;
long long int num(){
	long long int lli=0;
	for(auto v:vec){
		lli+=static_cast<long long int>(v);
	}
	return lli;
}
int main(){
	std::cin>>n;
	for(int i=0;i<n;++i){
		std::cin>>x;
		vec.push_back(x);
	}
	sort(vec.begin(),vec.end());
	std::cout<<*vec.begin()<<" "<<*(vec.end()-1)<<" "<<num()<<std::endl;
	return 0;
}

Measured memory_bytes: 1328
import java.util.*;

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

        if(a>=13){
            System.out.println(b);
        }else if (a>=6 && a<=12){
            System.out.println(b/2);
        }else{
            System.out.println(0);
        }
    }
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<10) cout<<n<<endl;
    else if(n>=10&&n<100) cout<<"9"<<endl;
    else if(n>=100&&n<1000) cout<<n-100+10<<endl;
    else if(n>=1000&&n<10000) cout<<"909"<<endl;
    else if(n>=10000&&n<100000) cout<<n-10000+1000-100+10<<endl;
    else cout<<"90909"<<endl;
}


Measured memory_bytes: 3588
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;

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

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, h, w;
	cin >> n >> h >> w;
	cout << (n - h + 1)*(n - w + 1) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
#define REP(i,st,ed) for(int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(int i=st,i##end=ed;i>=i##end;--i)
template<typename T>bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
int read(){
	int x=0,f=1;
	char c=getchar();
	while((c<'0')||(c>'9')){if(c=='-')f=-1;c=getchar();}
	while((c>='0')&&(c<='9'))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int maxn=500005;
int n;
char a[maxn];
int c[maxn],dp[maxn][4];
int main(){
	scanf("%d%s",&n,a+1);
	if(n<=2){puts("0");return 0;}
	int cur=1,ans=0;
	while(a[cur]=='0')++cur;
	for(int i=cur;i<=n;i=cur+1){
		while((a[cur+1]=='1')||(a[cur+2]=='1'))++cur;
		int cnt=1;
		REP(j,i,cur){
			if(a[j]=='0')++cnt;
			else ++c[cnt];
		}
		while(a[cur+1]=='0')++cur;
		REP(j,1,cnt+1)
			REP(k,0,3)
				dp[j][k]=-1e9;
		dp[1][0]=0;
//		REP(j,1,cnt)
//			printf("%d%c",c[j],j==jend?'\n':' ');
		REP(j,2,cnt+1){
			chkmax(dp[j][0],max(max(dp[j-1][0],dp[j-1][1]),max(dp[j-1][2],dp[j-1][3])));
			if(c[j]>1){
				chkmax(dp[j][1],max(max(dp[j-1][0]+c[j-1],dp[j-1][1]+c[j-1]-1),max(dp[j-1][2]+1,dp[j-1][3])));
				chkmax(dp[j][2],max(max(dp[j-1][0]+max(c[j]-1,c[j-1]),dp[j-1][1]+max(c[j-1]-1,c[j]-1)),max(dp[j-1][2]+c[j]-1,dp[j-1][3])));
			}
			chkmax(dp[j][3],max(max(dp[j-1][0]+max(c[j-1],c[j]),dp[j-1][1]+max(c[j-1]-1,c[j])),max(dp[j-1][2]+c[j],dp[j-1][3])));
//			cout<<dp[j-1][0]+max(c[j-1],c[j])<<' '<<dp[j-1][1]+max(c[j-1]-1,c[j])<<' '<<dp[j-1][2]+c[j]<<' '<<dp[j-1][3]<<endl;
//			printf("%d %d %d %d\n",dp[j][0],dp[j][1],dp[j][2],dp[j][3]);
		}
//		printf("---%d %d %d\n",dp[cnt][0],dp[cnt][1],dp[cnt][2]+(c[cnt]!=1));
		ans+=dp[cnt+1][0];
		REP(j,1,cnt)c[j]=0;
		i=cur;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll sum;
int gcd(int a,int b){
	int r=a%b;
	while(r)
	  {
	  	  a=b,b=r; r=a%b;
	  }
	  return b;
}
int main()
{
 cin>>n;
 for(int a=1;a<=n;a++)
    for(int b=1;b<=n;b++)
     for(int c=1;c<=n;c++)
 {

	  //sum+=y;
	sum+=gcd(a,gcd(b,c));
 }
 cout<<sum;
return 0;
}


Measured memory_bytes: 3576
// #include <iostream>
// #include <set>
// #include <vector>
// #include <map>
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define rep(i, a) for (int i = 0; i < (a); i++)
#define repd(i, a) for (int i = (a)-1; i >= 0; i--)
#define reps(i, a, j) for (int i = (j); i < (a); i++)
#define deb(x) cout << #x << " " << x << endl;
#define debs(x) cout << #x << " " << x << " ";
#define deba(x) for (auto _i:x) cout << _i << " "; cout << endl;
#define ms(a) memset(a,0,sizeof(a));
#define mp make_pair
#define eb emplace_back
#define FastOpen freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define pii pair < int , int >
//int power(int x,int p){if(p==0)return 1;if(p==1)return x;if(p%2)return x*power(x,p-1);int y=power(x,p/2);return y*y;}
/*
*/

const int inf = 1e9 +7;
void solve() {
    int n,w; cin >> n >> w;
    int dp[n][100010],res = 0;
    rep(i,n) rep(j,100010) {
        dp[i][j] = inf;
    }
    rep(i,n) {
        int curw,v; cin >> curw >> v;
        if (i == 0) {
            dp[i][v] = curw;
            continue;
        }
        dp[i][v] = min(dp[i][v],curw);
        rep(j,100010) {// cant start with v because we have to copy for j<v to this array.
            dp[i][j] = min(dp[i-1][j],dp[i][j]);
            if (j-v > 0) dp[i][j] = min(dp[i][j],dp[i-1][j-v] + curw);
        }
        
    }
    rep(i,100010) if (dp[n-1][i] <= w) res = i;
    cout << res << endl; 
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    FastOpen
    int t; t=1;
    while (t--) solve();
}





Measured memory_bytes: 81732
N, Y = map(int, input().split())

for x in range(N+1):
    for y in range(N+1):
        if 10000*x + 5000*y + 1000*(N-(x+y)) == Y and N-(x+y) >= 0:
            print(x, y, N-(x+y))
            exit()

print(-1,-1,-1)

Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>

int main(void) {
	
	/*
	int a,b;
	scanf("%d",&a);
	scanf("%d",&b);
	*/
	
	/*
	printf("%d ",a/b);
	printf("%d ",a%b);
	printf("%lf\n",(double)a/b);
	*/
	
	double r;
	scanf("%lf",&r);
	
	
	
	printf("%lf ",r*r* M_PI);
	printf("%lf\n",r*2*M_PI);
	
	
	return 0;
}



Measured memory_bytes: 2088