akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

int main() {
  int n;
  cin >> n;
  int arr[n];
  bool ok = 1;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    if (arr[i] % 2 == 0) {
      ok &= (arr[i] % 3 == 0 || arr[i] % 5 == 0);
    }
  }
  if (ok) {
    cout << "APPROVED" << endl;
  } else {
    cout << "DENIED" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e8;
using namespace std;

int main(void)
{
    
    string a, b;
    cin >> a >> b;
    int n = a.length() + 1;
    int m = b.length() + 1;
    vector<vector<int> >v(n, vector<int>(m));
    for(int i=0; i< n; i++){
        for(int j=0; j< m; j++){
            if(j == 0){
                v[i][j] = i;
            }
            else if(i == 0) {
                v[i][j] = j;
            }

        }
    }

    for(int i=1; i < n; i++){
        for(int j=1; j < m; j++){
            int tmp_a = v[i-1][j] + 1;
            int tmp_b = v[i][j-1] + 1;
            int tmp_c;
            if(a[i-1] == b[j-1]){
                tmp_c = v[i-1][j-1];
            }else{
                tmp_c = v[i-1][j-1] + 1;
            }
            v[i][j] = min(tmp_a, min(tmp_b, tmp_c));
        }
    }

    cout << v[n-1][m-1] << endl;

    // for(int i=0; i<n; i++){
    //     for(int j =0; j<m; j++){
    //         cout << v[i][j];
    //     }
    //     cout << endl;
    // }
}



Measured memory_bytes: 6712
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <map>
#include <set> 
#include <bitset>
#include <cmath>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)

int main () {
    
    int n; cin >> n;
    string s; cin >> s;

    vector<int> ec(n+1);
    vector<int> wc(n+1);

    int ecount = 0, wcount = 0;
    for (int i = 0; i < n; i++) {
        if(s[i] == 'E') {
            ecount += 1;
        } else {
            wcount += 1;
        } 
        ec[i+1] = ecount;
        wc[i+1] = wcount;
    }
    
    int res = 1000000000;
    for (int i = 0; i < n; i++) {
        int this_ans = 0;
        this_ans += wc[i] - wc[0];
        this_ans += ec[n] - ec[i+1];
        res = min(res, this_ans);
    }

    cout << res << endl;

    return 0;
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
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; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }

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

    int n, m, k;
    cin >> n >> m >> k;
    if (k == 0) {
        cout << "Yes" << endl;
        return 0;
    }
    reps(i, n) reps(j, m) {
        if (k == i * (m - j) + j * (n - i)) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main()
{
    int N, K;
    double ans = 0;
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
    {
        int cnt;
        if (i >= K)
        {
            cnt = 0;
        }
        else
        {
            cnt = ceil(log2((1.0 * K) / i));
        }
        ans += (1.0 / N) * (1.0 / pow(2, cnt));
    }
    cout << setprecision(15) << ans << endl;
    return 0;
}

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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

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

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

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

    vi ct(N);
    vector<array<int, 2>> req;
    int tot = 0;

    for (int i = 0; i < N; i++) {
        cin >> ct[i];
        req.push_back({ max(0, K + 1 - ct[i]), i });
        tot += req.back()[0];
    }

    sort(all(req));
    while (tot < K) {
        req[0][0]++;
        tot++;
        sort(all(req));
    }

    reverse(all(req));
    if (req.front()[0] > (K + 1) / 2 || tot > K) {
        cout << -1 << endl;
        return 0;
    }

    vi seq(N * (K + 1) - K, -1);

    vi grp1, grp2;
    bool par = false;
    for (int inx = N - 1; inx < seq.size() - (N - 1); inx += N - 1) {
        (par ? grp2 : grp1).push_back(inx);
        par = !par;
    }
    vi put;
    copy(all(grp1), back_inserter(put));
    copy(all(grp2), back_inserter(put));

    int use = 0;
    for (auto p : req) {
        for (int q = 0; q < p[0]; q++)
            seq[put[use++]] = p[1];
    }

    sort(all(put));
    use = 0;

    for (int i = 0, v = 0; i < seq.size(); i++) {
        if (i == put[use]) {
            use++;
            v = 0;
        }
        else {
            while (use < put.size() && v == seq[put[use]] ||
                    use > 0 && v == seq[put[use-1]])
                v++;
            seq[i] = v++;
        }
    }

    cout << seq.size() << "\n";
    for (int v : seq)
        cout << v + 1 << " ";
    cout << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

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

int main(){
    const int value = 2019;
    ll L, R;
    cin >> L >> R;
    ll num = R - L + 1; //LからRまでの間にある整数の個数
    ll ans;
    if(num >= value){
        ans = 0;
    }else{
        ans = 2019;
        for(ll j = L; j <= R; j++){
            for(ll k = j + 1; k <= R; k++){
            ll a = j * k;
            ans = min(ans, a % value);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int graph[105][105];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			graph[i][j]=0;
	}
	for(int i=1;i<=n;i++)
	{
		int v;
		cin>>v;
		int num;
		cin>>num;
		while(num--)
		{
			int aa;
			cin>>aa;
			graph[v-1][aa-1]=1;
			//cout<<v-1<<" "<<aa<<endl;
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(j>0)
			cout<<" ";
			cout<<graph[i][j];
		}
		cout<<endl;
	}
	return 0;
} 


Measured memory_bytes: 3152
a=input()
a=list(a)
a1=[]
b1=[]
c1=[]
for i in range(len(a)-1,-1,-1):
    a1.append(a[i])
b=a[0:(len(a)-1)//2]
for i in range(len(b)-1,-1,-1):
    b1.append(a[i])
c=a[(len(a)+3)//2-1:len(a)]
for i in range(len(c)-1,-1,-1):
    c1.append(a[i])



if(a==a1):
    if(b==b1 and c==c1):
        print("Yes")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define inf 0x3fffffff

int n,m,a[10][10];

bool check()
{
    if (a[1][1]==0&&a[1][2]==0&&a[1][3]==0) return true;
    if (a[2][1]==0&&a[2][2]==0&&a[2][3]==0) return true;
    if (a[3][1]==0&&a[3][2]==0&&a[3][3]==0) return true;
    if (a[1][1]==0&&a[2][1]==0&&a[3][1]==0) return true;
    if (a[1][2]==0&&a[2][2]==0&&a[3][2]==0) return true;
    if (a[1][3]==0&&a[2][3]==0&&a[3][3]==0) return true;
    if (a[1][1]==0&&a[2][2]==0&&a[3][3]==0) return true;
    if (a[1][3]==0&&a[2][2]==0&&a[3][1]==0) return true;
    return false;
}

int main()
{
    n=3;
    int x;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin>>a[i][j];
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>x;
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
                if (a[j][k]==x) a[j][k]=0;
    }if (check()) puts("Yes");
    else puts("No");
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair 
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;

struct UnionFind{
    vector<ll> par,siz;

    UnionFind(ll N):par(N+1),siz(N+1,1){
        rep1(i,N) par[i]=i; //親を自分自身として初期化
    }

    ll root(ll x){
        if(par[x]==x){
            return x;
        }
        else{
            return  par[x]=root(par[x]);
        }
    }
    void unite(ll x,ll y){
        x=root(x);
        y=root(y);
        if(x==y) return;

        if(siz[x]<siz[y]) swap(x,y);
        
		siz[x]+=siz[y];
		siz[y]=siz[x];
		par[y]=x;
    }
    bool same(ll x,ll y){
        return root(x)==root(y);
    }
};

int main(){
	//input
	ll N,M; cin>>N>>M;
	vector<ll> A(M+1);
	vector<ll> B(M+1);
	rep1(i,M) cin>>A[i]>>B[i];

	vector<ll> ans(M+1);
	ans[M]=N*(N-1)/2;

	UnionFind tree(N);
	rrep1(i,M){
		if(tree.same(A[i],B[i])) ans[i-1]=ans[i];
		else ans[i-1]=ans[i]-tree.siz[tree.root(A[i])]*tree.siz[tree.root(B[i])];
		tree.unite(A[i],B[i]);
	}
	
	rep1(i,M) cout<<ans[i]<<endl;
}

Measured memory_bytes: 5248
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn main() {
    let mut S: String = read();

    if S == "AAA" || S == "BBB" {
        println!("No");
    } else {
        println!("Yes");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

unsigned int
ones32(register unsigned int x)
{
        /* 32-bit recursive reduction using SWAR...
	   but first step is mapping 2-bit values
	   into sum of 2 1-bit values in sneaky way
	*/
        x -= ((x >> 1) & 0x55555555);
        x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
        x = (((x >> 4) + x) & 0x0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        return(x & 0x0000003f);
}

int main() {
    int N;
    cin >> N;
    vector<int> F(N);
    rep(i,N) {
        int b = 0;
        rep(j,10) {
            int bit;
            cin >> bit;
            b = b * 2 + bit;
        }
        F.at(i) = b;
    } 
    int P[N][11];
    int mi = 0;
    rep(i,N) {
        rep(j,11) {
            cin >> P[i][j];
            if (mi > P[i][j]) mi = P[i][j];
        }
    }
    ll ma = -(1LL << 60);
    for (int i = 1; i < 1024; i++) {
        ll p = 0;
        rep(j, N) {
            int CB = F[j] & i;
            uint C = ones32(CB);
            p += P[j][C];
        }
        if (ma < p) ma = p;
    }
    cout << ma << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
    cin >> n;
    string ans;
    while(n){
        n--;
        ans += char('a' + n % 26);
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    char a, b;
    cin >> a >> b;
    if (a == 'H')
        cout << b;
    else 
        if (b == 'H')
            cout << 'D';
        else 
            cout << 'H';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fr first
#define se second
#define r_0 return 0;
#define ll long long
#define pb push_back
#define TIME ios_base::sync_with_stdio(0)
using namespace std;
vector<char>V,L;
vector<pair<char,ll>>B;
vector<string>Ans;
map<int,int>M;
set<ll>S;
set<char>:: iterator it;
ll n,m,a,b,c,d,e,f,x,y,z,t,l,r,ans,cnt,score;
string   s,winner,temp,p;
ll arr[100001];
bool xy=0;
char bd;
float ans1;
int main()
{
    TIME;
    cin>>n;
    for (int i =0; i <n; i ++ )
    {
        cin>>a;
        cnt+=a;
        arr[a]++;
    }
    cin>>m;
    for (int i =0; i <m; i ++)
    {
        cin>>x>>y;
        z=arr[x];
        arr[y]+=arr[x];
        arr[x]=0;
        b=z*x;
        c=z*y;
        cnt-=b;
        cnt+=c;
        cout<<cnt<<endl;
    }
}


Measured memory_bytes: 4404
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
  const int N = 1000000;
  int dp[2][N+1],n;

  for(int i=0;i<=N;i++)dp[0][i] = dp[1][i] = N;
  dp[0][0] = dp[1][0] = 0;

  int val = 1;
  for(int i=1;val<=N;i++){
    for(int j=0;j+val<=N;j++){
      int nxt = j+val;
      dp[0][nxt] = min(dp[0][nxt],dp[0][j] + 1);
      if(val&1)dp[1][nxt] = min(dp[1][nxt],dp[1][j] + 1);
    }
    val = i*(i+1)*(i+2)/6;
  }

  while(scanf("%d",&n),n)printf("%d %d\n",dp[0][n],dp[1][n]);
}

Measured memory_bytes: 8836
#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 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;}

int main() {
    int h,w,n;
    cin >> h >> w >> n;
    VI a(n);
    REP(i,0,n) cin >> a[i];
    VVI b(h, VI(w));
    int pos = 0;
    REP(i,0,h) REP(j,0,w) {
        b[i][j] = pos+1;
        if (--a[pos] == 0) ++pos;
    }
    REP(i,0,h) {
        if (i % 2) reverse(all(b[i]));
    }
    REP(i,0,h) {
        REP(j,0,w) {
            if (j) cout << " ";
            cout << b[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

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

long long C(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

int main()
{
    int n,m,flag=0,humty=0,sum=0;
    cin>>n>>m;
    if(n>1 && m>1)
     {
         humty=C(n,2);
         //cout<<humty<<endl;

         sum=C(m,2);
         //cout<<sum<<endl;
         cout<<humty+sum<<endl;
     }
    else if(n<=1 && m<=1)
        cout<< "0"<<endl;

        else{
            flag=max(n,m);
            cout<<C(flag,2)<<endl;
        }

}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _094
{
    class Program
    {
        static void Main(string[] args)
        {
            int N, M, X;

            string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            N = int.Parse(str[0]);  //数値で受け取りたい場合は変換する
            M = int.Parse(str[1]);
            X = int.Parse(str[2]);

            string[] A = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得

            int Left = 0;
            int Right = 0;
            for (int i = 0; i < M; i++)
            {
                if (X < int.Parse(A[i])) { ++Left; }
                else if (X > int.Parse(A[i])) { ++Right; }
            }
            if (Left <= Right) { Console.WriteLine(Left); }
            else { Console.WriteLine(Right); }

        }
    }
}


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

int main(){
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  vector<int>cmm(1000001);
  for(int x:a){
    if(cmm[x]!=0){
      cmm[x]=2;
      continue;
    }
    for(int j=x;j<1000001;j+=x){
      cmm[j]++;
    }
  }
  int num=0;
  for(int x:a){
    if(cmm[x]==1){
      num++;
    }
  }
  cout<<num<<endl;
}
      

Measured memory_bytes: 8012
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

const int nmax = 1e9 + 7;
typedef long long ll;

int main(){
  ll X, A, B; cin >> X >> A >> B;

  if (B - A <= 0){
    cout << "delicious" << endl;
  }else if(B - A <= X){
    cout << "safe" << endl;
  }else{
    cout << "dangerous" << endl;
  }
  
  
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String s1 = sc.next();
		String s2 = sc.next();

		int[][] dp = new int[s1.length()+1][s2.length()+1];

		for(int i=1;i<=s1.length();i++)
		{
			for(int j=1;j<=s2.length();j++)
			{
				dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

					if(s1.charAt(i-1)==s2.charAt(j-1))
					{
						dp[i][j] = 1 + dp[i-1][j-1];
					}
					
			}
		}
       
  

       String ans = "";
       int i =dp.length-1;
       int j =dp[0].length-1;

       while(i>=1||j>=1)
       {
       	  if(i>=1&&j>=1&&s1.charAt(i-1)==s2.charAt(j-1)&&dp[i][j]==dp[i-1][j-1]+1)
       	  {
       	  	  ans = ans + s1.charAt(i-1);
       	  	  i--;
       	  	  j--;
       	  }
       	  else if(i>=0&&j>=1&&dp[i][j]==dp[i][j-1])
       	  {
              j=j-1;
       	  }
       	  else
       	  {
             i=i-1;
       	  }
       	 
       }
       StringBuilder str = new StringBuilder();
       str.append(ans);

       System.out.println(str.reverse());
 	}
}

Measured memory_bytes: 88736
using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');

            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);

            string ret = null;

            if(a%2 == 0 || b%2 == 0)
            {
                ret = "Even";
            }else
            {
                ret = "Odd";
            }

            Console.WriteLine(ret);
        }
    }
}

Measured memory_bytes: 11092
// #define int long long
// #define repeat(i, n) for (int i = 0; i < n; ++i)

#include <cmath> // cmath includes sqrt, abs
#include <iostream> // iostream includes cout, endl
#include <string> // string
#include <algorithm> // algorithm includes sort

#include <set>

using namespace std;

int main() {
  bool can = false;
  int num = 0;
  int sum = 0;
  string S;
  int N;
  
  int K;
  int M = 0;

  int A[200000];
  int B[200000];

  cin >> N >> K;

  for (int i = 0; i < N; ++i) cin >> A[i];

  for (int i = 0; i <= N; ++i) B[i] = 0;
  
  for (int i = 0; i < N; ++i) B[A[i] - 1] += 1;

  for (int i = 0; i < N; ++i) if (B[i] > 0) M += 1;
  sort(B, B + N, greater<int>());
  
  while (M > K) {
    B[0] += B[M - 1];
    sum += B[M - 1];
    B[M - 1] = 0;

    M -= 1;
  }
  
  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 1792
def comb(x, y):
    temp1 = 1
    temp2 = 1
    for i in range(x, x-y, -1):
        temp1 = temp1 * i % mod
    for i in range(1, y+1):
        temp2 = temp2 * i % mod
    temp = pow(temp2, mod-2, mod)
    return temp1 * temp % mod
n,a,b = map(int, input().split())
mod = 10 ** 9 + 7
total = pow(2, n, mod) - 1
a = comb(n, a)
b = comb(n, b)
print((total - a - b) % mod)

Measured memory_bytes: 3064
N = int(input())
S = input()

R = [0]
W = [0]
r = 0
w = 0

for i in range(N):
    if S[i]=="W":
        w+=1
    else:
        r+=1
    R.append(r)
    W.append(w)
ans = N
for i in range(N+1):
    ans = min(ans,max(W[i],R[N]-R[i]))
print(ans)

Measured memory_bytes: 108616
import java.util.Scanner;

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

        if(a >= 13){
            ans = b;
        }else if(a <= 5){
            ans = 0;
        }else{
            ans = b / 2;
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rrep(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
typedef long long ll;
using namespace std;

char s[15][1050];

int main(){
    int h,w,k; cin >> h >> w >> k;

    rep(i,h)rep(j,w) cin >> s[i][j];
  
    int h1 = 0, h2; vector<int> a;
    int ans = h * w, white;
    for(int bit = 0; bit < (1 << h-1); bit++){
        a.resize(0); a.emplace_back(-1);
        rep(i,h-1) if(bit & (1<<i)) a.emplace_back(i);
        a.emplace_back(h-1);
        int dp[a.size()-1] = {};
        int w1 = 0, w2 = 0, tmp = __builtin_popcount(bit);
        bool can = true;
        while(1){
            bool ok = true;
            rep(i, a.size()-1){
                int h1 = a[i]+1, h2 = a[i+1];
                rep2(j,h1,h2+1) if(s[j][w2] == '1') dp[i]++;
                if(dp[i] > k) ok = false;
            }
            if(!ok && w2 == w1){ can = false; break; }
            if(ok){
                if(w2+1 < w) w2++;
                else break;
            }
            if(!ok){ w1 = w2; tmp++; rep(j,a.size()-1) dp[j] = 0;}
        }
        if(can) ans = min(ans,tmp);
    }

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

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  int n;cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];

  vector<pair<ll,int>> p(n);
  rep(i,n) p[i] = {-a[i], i};
  sort(p.begin(), p.end());
  vector<vector<ll>> dp(n+1, vector<ll>(n+1,0));
  rep(i,n) {
    rep(j,n) {
      if(i + j >= n) continue;
      chmax(dp[i+1][j], dp[i][j] - p[i+j].first * (ll)abs(p[i+j].second - i));
      chmax(dp[i][j+1], dp[i][j] - p[i+j].first * (ll)abs(n - 1 - j - p[i+j].second) );
    }
  }

  ll res = 0;
  rep(i,n) {
    rep(j,n) {
      if(i + j > n) continue;
      if(i + j == n) {
	chmax(res, dp[i][j]);
      }
    }
  }
  cout << res << "\n";
  
  return 0;
}


Measured memory_bytes: 34424
using System;

class ITP1_8_D
{
  /// <summary>
  ///   文字列sの任意の位置からスタートして一周する間に文字列pが作れるかどうか判定する。
  /// </summary>
  [STAThread]
  public static void Main(string[] args)
  {
    string s = Console.ReadLine();
    string p = Console.ReadLine();
    string ss = s + s;///文字列sを重ねれば、仮に文字列sの最後と最初で文字列pが形成されるとしても対応できる。
    if (ss.Contains(p)) Console.WriteLine("Yes");
    else Console.WriteLine("No");
  }
}



Measured memory_bytes: 17832
import java.util.*;
public class Main {
    
    public static void main(String[] args) throws InterruptedException{
        Scanner sc = new Scanner(System.in);
        
        int n_participants = sc.nextInt();
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        String participants = sc.next();
        
        int pass_counter = 0;
        int b_rank = 1;
        
        for(int i = 0;i<n_participants;i++){
            if(participants.charAt(i) == 'c')
                System.out.println("No");
            else if(participants.charAt(i) == 'a'){
                if(pass_counter < a+b){
                    pass_counter++;
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }else{
                if(pass_counter < a+b && b_rank <= b){
                    pass_counter++;
                    b_rank++;
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }
}

Measured memory_bytes: 23244
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <functional>
typedef long long ll;
typedef long double ld;
using namespace std;

int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
 
int main() {
    int N;
    vector<long long> ans(1001,0);;
    cin >> N;
    int sum = 0;
    for (int i = 1; i<=N; i++){
        for (int j = 1; j<=N; j++){
            for (int k = 1; k<=N; k++){
                int tmp = gcd(i,j);
                sum += gcd(tmp,k);
            }
        }
    }
    cout <<  sum  << endl;
    return 0;
}


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

int main() {
    string s,t; cin >> s >> t;
    vector<string> ans;
    int l = s.size()-t.size()+1;
    for(int i = 0; i < max(0, l); i ++) {
        string tmp = s;
        for(int j = 0; j < t.length(); j ++) {
            if(i+j>s.size()-1) break;
            if(tmp[i+j]=='?' || tmp[i+j]==t[j]) tmp[i+j] = t[j];
            else break;
            if(j==t.length()-1) {
                for(int k = 0; k < tmp.length(); k ++) {
                    if(tmp[k]=='?') tmp[k] = 'a';
                }
                ans.push_back(tmp);
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << (ans.size() > 0 ? ans[0] : "UNRESTORABLE") << endl;
    return 0;
}

Measured memory_bytes: 256
/*
 ID: swagchicken1
 PROG:
 LANG: C++11
 */

#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;

#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)

//#define endl '\n';

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1000000007;

long double PI = 4*atan(1);
long double eps = 1e-12;


ll dp[2010][2010] = {};
int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    int a,b,c,d; cin >> a >> b >> c >> d;
    if((c+b-1)/b <= (a+d-1)/d) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}


Measured memory_bytes: 3652
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N, K;
    cin >> N >> K;

    vi A(N);
    REP(i, N) cin >> A[i];

    REP(i, K) {

        vi r(N + 1, 0);

        REP(j, N) {
            int a = A[j];

            int s = max(j - a, 0);
            int t = min(j + a + 1, N);
            r[s] += 1;
            r[t] -= 1;

        }

        bool f = true;
        int s = 0;
        REP(j, N) {
            s += r[j];
            f &= (s == N);
            A[j] = s;
        }

        if (f) break;
    }

    REP(i, N) {
        if (i > 0) cout << " ";
        cout << A[i];
    }

    cout << endl;
    
}


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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) {
        ll d = euclid(b, a % b, y, x);
        return y -= a / b * x, d;
    }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1)
            ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1);
        return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e)
            return Mod(1);
        Mod r = *this ^ (e / 2);
        r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);

    while (true) {
        int n; cin >> n;
        if (!n) break;

        vector<bitset<101>> v(n + 1);
        rep(i, 1, n + 1) {
            int m; cin >> m;
            rep(j, 0, m) {
                int t; cin >> t;
                v[i][t] = 1;
            }
        }

        int m; cin >> m;
        bitset<101> leak;
        rep(i, 0, m) {
            int t; cin >> t;
            leak[t] = true;
        }

        vi pos;
        rep(i, 1, n + 1) {
            // cout << i << ": " << ((v[i] & leak) == leak) << endl;
            if ((v[i] & leak) == leak) {
                pos.push_back(i);
            }
        }
        if (pos.size() == 1) cout << pos.front() << endl;
        else cout << -1 << endl;
    }
}


Measured memory_bytes: 3192
import sys
input=sys.stdin.readline
from collections import deque
mod=1000000007
n,k=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(lambda x: int(x)-1,input().split())
    Edges[u].append(v)
    Edges[v].append(u)
Ans=[1]*n
Ans[0]=k
depth=[0]*n
Used=[False]*n
Used[0]=True
q=deque()
q.append(0)
while q:
    v=q.popleft()
    if v==0:
        cnt=k
    else:
        cnt=k-1
    for c in Edges[v]:
        if Used[c]:
            continue
        depth[c]=depth[v]+1
        d=depth[c]
        cnt-=1
        if cnt==0:
            print(0)
            exit()
        Ans[d]*=cnt
        Ans[d]%=mod
        q.append(c)
        Used[c]=True
max_depth=max(depth)
ans=1
for i in range(max_depth+1):
    ans*=Ans[i]
    ans%=mod
print(ans)

Measured memory_bytes: 63280
import numpy as np
N = int(input())
A = [int(s)-1 for s in input()]
#print(A)
if 1 in A:
  factor = 1
else:
  factor = 2
  A = [a//2 for a in A]

n = len(A) - 1
s = 0
for i, a in enumerate(A):
  s += a * (n == ( i | (n - i) )) 
  s = s%2
print((s%2)*factor)


Measured memory_bytes: 29320
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  ll k,a,b;
  //bool chk = false;
  cin>>k;
  a=100,b=0;
  while(a<k)
  {
      a+=floor(a*.01);
      //cout<<a<<endl;
      b++;
  }
  cout<<b<<endl;
  return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 200005
using namespace std;
struct edge{
	int k,next;
}e[N<<1];
int n,home[N],cnt=-1,h[N],a[N],tot;
void add(int x,int y){
	cnt++;
	e[cnt].k=y;
	e[cnt].next=home[x];
	home[x]=cnt;
}
int s[N],top,nxt[N],vis[N],D;
void dfs(int k){
	vis[k]=D;s[++top]=k;
	for(int i=home[k];~i;i=e[i].next){
		if(!vis[e[i].k]) dfs(e[i].k);
		else if(vis[e[i].k]==D){
			tot=top;
			for(int p=1;p<=top;p++) h[s[p]]=s[p==1?top:p-1],nxt[s[p]]=s[p==top?1:p+1],a[p]=s[p];
		}
	}
	top--;
}
int f[N],sum[25];
void dfs(int k,int F){
	for(int i=home[k];~i;i=e[i].next) if(e[i].k!=F){
		dfs(e[i].k,k);
	}
	for(int i=home[k];~i;i=e[i].next) if(e[i].k!=F){
		sum[f[e[i].k]]=k;
	}
	for(int i=0;i<=20;i++) if(sum[i]!=k){
		f[k]=i;break;
	}
}
bool pan(){
	for(int i=f[a[1]];i<=20;i++){
		memset(sum,0,sizeof(sum));
		bool t=1;
		f[a[1]]=i;
		for(int p=home[a[1]];~p;p=e[p].next) if(e[p].k!=nxt[a[1]]) if(f[e[p].k]==i){
			t=0;break;
		}
		if(!t) continue;
		for(int p=tot;p;p--){
			for(int j=home[a[p]];~j;j=e[j].next) sum[f[e[j].k]]=p;
			for(int j=0;j<=20;j++) if(sum[j]!=p){
				f[a[p]]=j;break;
			}
		}
		if(f[a[1]]!=i) t=0;
		if(t) return 1;
	}
	return 0;
}
int main(){
	memset(home,-1,sizeof(home));
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		add(x,i);
	}
	for(int i=1;i<=n;i++) if(!vis[i]) D=i,dfs(i);
	for(int i=1;i<=n;i++) if(nxt[i]) dfs(i,nxt[i]);
	if(pan()) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define AB_BHI_NI_DEGI                \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
#define int long long
#define pb push_back
#define N 100009
#define inf 1e18
const double PI = 3.141592653589793238462643383279;
//int mod = 1e9 + 7;
int mod = 998244353;
#define P pair<int, int>
#define F first
#define S second
#define ll long long
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define ld long double

#define ordered_set tree<P, null_type, less<P>, rb_tree_tag, tree_order_statistics_node_update>

int32_t main()
{
	AB_BHI_NI_DEGI
	string s, t;
	cin >> s >> t;
	int op = 0;
	for (int i = 0; i < s.size(); i++)
		op += (s[i] != t[i]);
	cout << op << "\n";
	return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ABC128C - Switches
  // onとoffの状態を持つN個のスイッチとM個の電球、スイッチには1からNまで、電球には1からMまでの番号
  // 電球iはki個のスイッチに繋がっており、onになっているスイッチの個数を2で割った余りがpiに等しいとき点灯
  // 全ての電球が点灯するようなスイッチのon/off状態の組合せ
  // on/offの二択で、Nが10　→　bit全探索で全てのスイッチの状態を確かめる
  int N, M;
  cin >> N >> M;
  vector<int> k(M);
  vector<vector<int> > s(M, vector<int>());
  vector<int> p(M);
  int tmp;
  REP(i, M){
    cin >> k.at(i);
    REP(j, k.at(i)){
      cin >> tmp;
      s.at(i).push_back(tmp-1);
    }
  }
  REP(i, M){
    cin >> p.at(i);
  }

  ll ans = 0;
  REP(bits, 1 << N){
    bool flag = true;
    REP(i, M){  // i番目の電球について探索
      int cnt = 0;
      REP(j, k[i]){  // i番目の電球のj番目のスイッチ（番号s[i][j]）について探索
        if(bits & (1 << s[i][j])) cnt++;
      }
      if(cnt%2 != p[i]) flag = false;
    }
    if(flag) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        if (y%2==1) {
            System.out.println("No");
            return;
        }
        int min = x*2;
        int max = x*4;
        if (y>=min && y<=max) {
            System.out.println("Yes");
            return;
        }
        System.out.println("No");
    }
}


Measured memory_bytes: 35768
#include<cstdio>
#include<queue>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std; 
int main(){
	long long n,k;
	long long s;
	scanf("%lld%lld%lld",&n,&k,&s);
	long long i;
	for(i=1;i<=n;i++){
		if(i<=k)
		printf("%lld\n",s);
		else{
			if((s-1)>n-k) 
			printf("%lld\n",(s-1)/(n-k));
			else
			printf("%lld\n",s*2);
		}
	}
}

Measured memory_bytes: 1280
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

int n;
int mn;
int a[21];

void dfs(int battle , int depth){
	if(depth==n){
		mn=min( mn , abs(battle));
	} else {
		//cout << "left >battle:" << abs(battle+a[depth]) << " depth:" << depth << endl;
		dfs(battle+a[depth] , depth+1);
		//cout << "right>battle:" << abs(battle-a[depth]) << " depth:" << depth << endl;
		dfs(battle-a[depth] , depth+1);
	}
}


int main(){
	while(cin>>n , n!=0){
		for(int i=0;i<n;++i){
			cin >> a[i];
		}
		mn=1000001;
		dfs(0 , 0);
		cout << mn << endl;
	}
	return 0; 
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    ll ans = 0;
    reps(i, 1, n + 1) {
        string s = to_string(i);
        ll sl = len(s);
        if (sl % 2 == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
long long a, b, h[101010], l, r, s[101010],t;
bool ans, q;

bool chk(long long x){
ll u = b*x;
ll ht = a-b;
ll c=0;
for(int i =1; i<=n; i++){
    if(h[i]-u<=0)continue;
    ht = h[i]-u;
    c+=ht/(a-b);
    if(ht%(a-b)!=0)c++;
}
if(c>x)return false;
else return true;
}


int main(){
cin >> n >> a >> b;
for(int i =1 ; i<=n; i++){
    cin >> h[i];
    r = max(h[i], r);
}
l=1;
while(l<=r){
    t=(l+r)/2;
    ans = chk(t);
    q = chk(t-1);
    if(ans==true && q==false)break;
    if(ans)r=t;
    else l=t;
}

cout << t << endl;

return 0;}


Measured memory_bytes: 1024
import copy
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    walled_maze = copy.copy(maze)
    walled_maze[H:H] = [''.join(['#' for _ in range(W+2)])]
    walled_maze[0:0] = [''.join(['#' for _ in range(W+2)])]
    for row_num in range(1, H+1):
        walled_maze[row_num] = '#{}#'.format(walled_maze[row_num])
    # for i in range(H+2):
    #     print(walled_maze[i])

    stack = deque()
    sx, sy = 1, 1
    gx, gy = H, W
    distances = [[-1]*(W+2) for _ in range(H+2)]
    vectors = ((1, 0), (-1, 0), (0, 1), (0, -1))

    distances[sx][sy] = 0
    for vec_x, vec_y in vectors:
        x = sx + vec_x
        y = sy + vec_y
        stack.append((x, y))
        distances[x][y] = float('inf')

    min_path_dist = -1
    while len(stack):
        x, y = stack.popleft()
        if x < 0 or x >= H+1 or y < 0 or y >= W+1 or walled_maze[x][y] == '#':
            continue
        for vec_x, vec_y in vectors:
            try:
                next_x = x + vec_x
                next_y = y + vec_y
                if distances[next_x][next_y] < 0:
                    stack.append((next_x, next_y))
                    distances[next_x][next_y] = float('inf')
                else:
                    if distances[x][y] > distances[next_x][next_y] + 1:
                        distances[x][y] = distances[next_x][next_y] + 1
            except IndexError:
                pass

        # print('{} {}'.format(x, y))
        # print(stack)
        # for i in range(H+2):
        #     print(distances[i])

        if x == gx and y == gy:
            min_path_dist = distances[x][y]
            break

    if min_path_dist < 0:
        print('-1')
    else:
        black_square_num = sum([row.count('#') for row in maze])
        print(H*W-(min_path_dist+1)-black_square_num)

if __name__ == '__main__':
    main()


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

typedef long long ll;

int n,x[15],y[15],p[15],D[15],d[15];
ll ans[16];

int main(){

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

    cin>>n;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>p[i];
    memset(ans,0x3f,sizeof(ans));
    ans[0]=0;
    for(int i=0;i<n;i++){
        D[i]=min(abs(x[i]),abs(y[i]));
        ans[0]+=(ll)p[i]*D[i];
    }
    for(int s=0;s<1<<n;s++){
        for(int t=s;t;t=(t-1)&s){
            memcpy(d,D,sizeof(d));
            for(int i=0;i<n;i++){
                if(s>>i&1){
                    if(t>>i&1){
                        for(int j=0;j<n;j++){
                            d[j]=min(d[j],abs(x[i]-x[j]));
                        }
                    }else{
                        for(int j=0;j<n;j++){
                            d[j]=min(d[j],abs(y[i]-y[j]));
                        }
                    }
                }
            }
            ll cur=0;
            for(int i=0;i<n;i++){
                cur+=(ll)d[i]*p[i];
            }
            ans[__builtin_popcount(s)]=min(ans[__builtin_popcount(s)],cur);
        }
        {
            int t=0;
            memcpy(d,D,sizeof(d));
            for(int i=0;i<n;i++){
                if(s>>i&1){
                    if(t>>i&1){
                        for(int j=0;j<n;j++){
                            d[j]=min(d[j],abs(x[i]-x[j]));
                        }
                    }else{
                        for(int j=0;j<n;j++){
                            d[j]=min(d[j],abs(y[i]-y[j]));
                        }
                    }
                }
            }
            ll cur=0;
            for(int i=0;i<n;i++){
                cur+=(ll)d[i]*p[i];
            }
            ans[__builtin_popcount(s)]=min(ans[__builtin_popcount(s)],cur);
        }
    }
    for(int i=0;i<=n;i++)cout<<ans[i]<<'\n';

    return 0;
}


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

map<int,int>data;

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n*(n-1)/2;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(c>d)data[a]+=3;
		else if(c<d)data[b]+=3;
		else {
			data[a]+=1;
			data[b]+=1;
		}
	}
	map<int,int>ans;
	int c=1;
	int cc=0;
	while(cc!=data.size()){
		int ma=0;
		int count=0;
		for(map<int,int>::iterator itr=data.begin();itr!=data.end();itr++){
			if(itr->second>ma)ma=itr->second;
		}
		for(map<int,int>::iterator itr=data.begin();itr!=data.end();itr++){
			
			if(itr->second==ma){
				ans[itr->first]=c;
				cc++;
				itr->second=-5;
				count++;
			}
		}
		c+=count;
	}
	for(map<int,int>::iterator itr=ans.begin();itr!=ans.end();itr++){
		cout<<(itr->second)<<endl;
	}
}

Measured memory_bytes: 1204
#include <iostream>
#define mod 998244353
using namespace std;
int a[305];
long long dp[2][200005],dp2[200005];
const int qwq=100000;
int main(int argc, char** argv) {
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	dp[0][qwq]=1;
	dp2[0]=1;
	long long s=1,sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		for(int j=10000;j<=190000;j++)
			dp[i&1][j]=(dp[i&1^1][j-a[i]]*2+dp[i&1^1][j+a[i]])%mod;
		for(int j=qwq;j>=0;j--) dp2[j+a[i]]+=dp2[j],dp2[j+a[i]]%=mod;
		s*=3,s%=mod;
	}
	long long ans=0;
	for(int i=qwq;i>=0;i--)
		ans+=dp[n&1][i],ans%=mod;
	if(sum%2==0)
		ans-=dp2[sum/2];
	cout << ((s-ans-ans-ans)%mod+mod)%mod;
	return 0;
}

Measured memory_bytes: 3968
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    long long solve(int n) {
        long long res = 0;
        int x = n / 500 * 500;
        n -= x;
        res += 1000 * 1LL * (x / 500);
        x = n / 5 * 5;
        n -= x;
        res += x;
        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    Solution sol;
    cout << sol.solve(n) << "\n";

    return 0;
}

Measured memory_bytes: 256
#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; }

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

int sum[100005];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	for(int i = 3; i <= 100001; ++i){
		sum[i] = sum[i-1];
		if(isPrime(i) && isPrime((i+1)/2)) ++sum[i];
	}
	int q;
	cin >> q;
	rep(qi,q){
		int l, r;
		cin >> l >> r;
		cout << sum[r] - sum[l-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 4000