akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int MAX_A = 100000;
int x, y, a, b, c;
long long int p[MAX_A], q[MAX_A], r[MAX_A];

void solve() {
    sort(p, p + a);
    sort(q, q + b);
    long long int ans = 0;
    long long int all[x + y + c];
    for (int i = 0; i < x; i++) {
        all[i] = p[a - 1 - i];
    }
    for (int i = 0; i < y; i++) {
        all[x + i] = q[b - 1 - i];
    }
    for (int i = 0; i < c; i++) {
        all[x + y + i] = r[c - 1 - i];
    }
    sort(all, all + x + y + c);
    for (int i = x + y + c - 1; i > c - 1; i--) {
        ans += all[i];
    }

    cout << ans << endl;
}

int main() {
    cin >> x >> y >> a >> b >> c;
    for (int i = 0; i < a; i++) {
        cin >> p[i];
    }
    for (int i = 0; i < b; i++) {
        cin >> q[i];
    }
    for (int i = 0; i < c; i++) {
        cin >> r[i];
    }
    solve();
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6,OO=0x3f3f3f3f;
int d()
{
    int ret;
    scanf("%d", &ret);
    return ret;
}
long long lld()
{
    long long ret;
    scanf("%lld", &ret);
    return ret;
}
char arr[N];
char arr1[N];
int W[N];
int E[N];
int main(){
    int n=d();
    scanf("%s",arr1);
    for(int i=1;i<=n;i++){
        arr[i]=arr1[i-1];
    }


    for(int i=1;i<=n;i++){
        if(arr[i]=='W')
            W[i]=W[i-1]+1;
        else
            W[i]=W[i-1];

        //////////////

        if(arr[i]=='E')
            E[i]=E[i-1]+1;
        else
            E[i]=E[i-1];
    }

    int mn=E[n]-E[1];

    for(int i=2;i<=n;i++){
        mn=min(mn,(E[n]-E[i])+(W[i-1]-W[0]));
    }
    printf("%d\n",mn);
}


Measured memory_bytes: 7808
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
using namespace std;
using v = vector<int>;
using ll = long long int;
template <class T = int> T in(){ T x; cin >> x; return (x);}

ll gdb(ll i, ll x){
    ll c = 0;
    if(i == 0) return 0;
    rfor(j, 0, i+1){
        if(j % x == 0) c++;
    }
    return c;
}
int main(int argc, char *argv[]){
    ll a, b, x; cin >> a >> b >> x;
    ll res;
    if(a == 0){
        res = b/x + 1;
    }else{
        res = b/x - (a - 1)/x;
    }
    // if(a == 0 && b == 0) res = 1;
    // else if(a == 0 && b != 0) res++;
    cout << res << endl;
    return 0;
}

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

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ar array
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
const ll inf = 2e9 + 5;
double PI = 3.14159265358979323846;


void solve() {

	int n, k;
	cin >> n >> k;
	vi a(n+1);

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	vvi dp(n + 1, vi(k + 1, 0));

	dp[0][0] = 1;

	for (int i = 1; i <= n; i++) {

		vi pre(k+1,0);
		pre[0] = dp[i-1][0];
		for(int j = 1;j <=k;j++){
			pre[j] = (pre[j-1] + dp[i-1][j])%mod;
		}

		for (int j = 0; j <= k; j++) {
			// if I have j candies I can give ith child any candies from 0...j
			// say I give x to ith child then remaining can be divided
			// among i-1 children something like:
			// dp[i-1][j-x]+dp[i-1][j-x-1]+++dp[i-1][0] i,e prefix_sum(dp[i-1][0...j-x])
			int temp;
			if(j-a[i] > 0){
				temp = ((pre[j] - pre[j-a[i]-1])%mod+mod)%mod;
			} else{
				temp = pre[j];
			}
			dp[i][j] = temp;
		}
	}
	cout << dp[n][k];

}

int32_t main()
{
	IOS
	// int T; cin >> T; while (T--)
	solve();
	return 0;
}


Measured memory_bytes: 43268
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
vector<int>vec;

int main(){
  int n;
  int ans=0;
  cin>>n;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(mp[a]==0){
      vec.push_back(a);
    }
    mp[a]++;
  }
  for(int i=0;i<vec.size();i++){
    if(mp[vec[i]]>=vec[i]){
      ans+=mp[vec[i]]-vec[i];
    }
    else ans+=mp[vec[i]];
  }
  cout<<ans<<endl;
  return(0);
}


Measured memory_bytes: 5112
n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n + 1 - i):
        if 1000 * i + 5000 * j + 10000 * (n - i - j) == y:
            print(n - i - j, j, i)
            exit()
print('-1 -1 -1')


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
struct Graph
{
    Graph(const std::size_t v) : V{v}, edge(v), rev_edge(v) {}
    void addEdge(const std::size_t from, const std::size_t to) { edge[from].push_back(to), rev_edge[to].push_back(from); }
    const std::size_t V;
    std::vector<std::vector<std::size_t>> edge, rev_edge;
};
std::pair<bool, std::vector<std::size_t>> TopSort(const Graph& g)
{
    std::vector<std::size_t> srt, used(g.V, 0);
    auto dfs = [&](auto&& self, const std::size_t s) -> bool {
        if (used[s] == 1) {
            return false;
        } else if (used[s] == 0) {
            used[s] = 1;
            for (const std::size_t to : g.edge[s]) {
                if (not self(self, to)) { return false; }
            }
            used[s] = 2, srt.push_back(s);
        }
        return true;
    };
    for (std::size_t i = 0; i < g.V; i++) {
        if (not dfs(dfs, i)) { return {false, srt}; }
    }
    std::reverse(srt.begin(), srt.end());
    return {true, srt};
}
int main()
{
    int N, M;
    std::cin >> N >> M;
    Graph g(N);
    for (int i = 0; i < M; i++) {
        int x, y;
        std::cin >> x >> y, x--, y--;
        g.addEdge(x, y);
    }
    std::vector<int> dp(N, 0);
    const auto ord = TopSort(g).second;
    for (const int s : ord) {
        for (const int to : g.edge[s]) { dp[to] = std::max(dp[to], dp[s] + 1); }
    }
    std::cout << *std::max_element(dp.begin(), dp.end()) << std::endl;
    return 0;
}


Measured memory_bytes: 15224
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

int main(){
  const int n = getInt();
  const int m = getInt();
  if(m + m - 1 <= n) puts("YES");
  else puts("NO");
  return 0;
}

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

#define mod 1000000007

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

using namespace std;
typedef long long ll; 
 
int main(void){
	
	int a[100000];
	
	cin >> a[0];
	
	rep(i, 100000){
		if(a[i-1] % 2 == 0)
			a[i] = a[i-1] / 2;
		else
			a[i] = 3 * a[i-1] + 1;
		for(int j=0; j<i; j++){
			if(a[j] == a[i]){
				cout << i+1;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

ll dp[310][8];
int main() {
    ll N, Y; cin >> N >> Y;
    ll target = 0;
    vector<ll> A(2*N), S(2*N + 1);
    for(int i=0; i<N; i++) {
        cin >> A[i];
        A[N+i] = A[i];
        S[i+1] = S[N+i+1] = A[i];
        target += A[i];
    }
    for(int i=1; i<=2*N; i++) S[i] += S[i-1];
    target /= 5;
    
    ll ans = 0;
    for(int ofs=0; ofs<N; ofs++) {
        fill(dp[0], dp[N+1], 0);
        dp[0][0] = 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<5; j++) {
                for(int k=i+1; k<=N; k++) {
                    ll sum = S[ofs+k] - S[ofs+i];
                    if(sum + Y >= target) {
                        dp[k][j+1] += dp[i][j];
                    }
                }
            }
        }
        ans += dp[N][5];
    }
    cout << ans / 5 << endl;
    return 0;
}



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

int main(){
  int h, w;  cin >> h >> w;
  vector<vector<int>> field(h+2, vector<int>(w+2, 0));
  queue<pair<int, int>> que;
  for(int i=0; i<h; i++){
    string s;  cin >> s;
    for(int j=0; j<w; j++)
      if(s[j] == '.')  field[i+1][j+1] = -1;
      else  que.push({i+1, j+1});
  } 

  while(!que.empty()){
    auto now = que.front();  que.pop();
    for(int i=-1; i<=1; i++)
      for(int j=-1; j<=1; j++){
        if(abs(i)+abs(j) == 2 || (i == 0 && j == 0))  continue;
        if(field[now.first+i][now.second+j] < 0){
          field[now.first+i][now.second+j] = field[now.first][now.second] + 1;
          que.push({now.first+i, now.second+j});
        }
      }
  }

  int ans = 0;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++)
      ans = max(ans, field[i][j]);
  }
 
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 15100
/*==============================================*\
Codeforces ID:    mdshihab
                                                  |
Name:     Md. Shihabul Minhaz                     |
Study:      CSE, JKKNIU                           |
Address:  Trishal, Mymensingh, Bangladesh         |
                                                  |
 mail:   mdshihabul20171@gmail.com                |
 FB  :   fb.com/mdshihabul.minhaz.7               |
 github: Shihabulminhaz                           |
stopstalk :  mdshihab                             |
                                                  |
@uthor   Md. Shihabul Minhaz (shihab)             |
\*===============================================*/


#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int shihab;
void FI()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\SHIHAB\\Desktop\\input.in","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
    fast
  //  FI(); /// skip this line for compile
    unsigned ll a,b,x;
    cin >> a >> b;
    if(a==1 || b==1){
        cout << 1 << endl;
        return 0;
    }
    x = (a*b+1)/2;
    cout << x << endl;
    return 0;
    //code end
}
//okbye


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

int cnt[1000001];

int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        for(int j=i;j<=n;j+=i) {
            cnt[j]++;
        }
    }
    long long ret=0;
    for(int i=1;i<n;i++) {
        ret+=cnt[i];
    }
    printf("%lld",ret);
}

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

Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n,m,q=map(int,input().split())
lr=[list(map(int,input().split())) for i in range(m)]
pq=[list(map(int,input().split())) for i in range(q)]
x=[[0]*n for i in range(n)]
for i in range(m):
    x[lr[i][0]-1][lr[i][1]-1]+=1
# print(x)
rui=[[0]*(n+1) for i in range(n+1)]
for i in range(n):
    for j in range(n):
        rui[i+1][j+1]=rui[i][j+1]+rui[i+1][j]-rui[i][j]+x[i][j]
# print(rui)
for i in range(q):
    print(rui[pq[i][1]][pq[i][1]] - rui[pq[i][0]-1][pq[i][1]] - rui[pq[i][1]][pq[i][0]-1] + rui[pq[i][0]-1][pq[i][0]-1])


Measured memory_bytes: 99932
#include <iostream>
#include <string>
#define LONG_INF 10000000000000000
#define INT_INF 2147483647
#define REP(i,N) for(int (i) = 0; (i) < (N); i++)

using namespace std;

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

    return gcd(b,r);
}

int main(void){
	int n;
	int i,ans,a,mi=INT_INF,ma=0;
	cin >> n;

    for(int i=0;i<n;i++){
        cin >> a;
        if(a<mi) mi = a;
        if(a>ma) ma = a;
    }
	cout << ma-mi << endl;

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
/*
ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=2000005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

ll nPk(ll n,ll k){
	return nCk(n,k)*F[k]%mod;
}*/

int n,k;
vi a;

int main(){
	cin>>n>>k;
	a=vi(n);
	for(auto &i:a) cin>>i;
	for(int i=k;i<n;i++) cout<<(a[i]>a[i-k]?"Yes":"No")<<endl;
}

Measured memory_bytes: 3972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1e18;

int main(){
    int n;
    string s,t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++){
        cout<<s[i]<<t[i];
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PI 3.1415926535
const long long int MOD = 1000000007;
#define pb push_back
#define mp make_pair
#define fill(a)  memset(a, 0, sizeof (a))
#define SORT(v)  sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define MAX(v) *max_element(v.begin(), v.end())
#define MIN(v) *min_element(v.begin(), v.end())
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define watch(x) cout << (#x) << " is " << (x) << endl;
const long long int MAXX = 200000 + 5;
const long long int MINN = 2e5 + 5;
const long long int inf = 1e6;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector< iii > viii;

ll lcm(ll a, ll b) {
   return a / __gcd(a, b) * b;
}
int XOR(int x, int y){
  return (x | y) & (~x | ~y);
}
bool cmp(const pair<int,int> &a,const pair<int,int> &b) {
    return (a.second < b.second);
}
// bool isl = binary_search(x.begin(), x.end(), 5);
// __builtin_popcount(x)  - Returns the number of set bits in x
const long long int N = 10050;
const int MAXN = 105;
int binsearch(int lo, int hi){
	while(lo<hi){
		int mid=(lo+hi)/2;
		if((mid))   // check(mid)
			hi=mid;
		else
			lo=mid+1;
	}
	return lo;
}
ll power(ll x,ll y){
    ll res=1;
    while(y>0){
      if(y&1) res=((res*x)%MOD);

      y/=2;
      x=((x*x)%MOD);
    }
    return res%MOD;
}


int main(){
    FAST
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(1){
        c-=b;
        if(c<=0){
            cout<<"Yes"; return 0;
        }
        a-=d;
        if(a<=0){
            cout<<"No"; return 0;
        }
    }

    return 0;
}


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

int main(){
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  float res = 0;
  int max_s = 0;
  int max_w = 0;
  for(int i = 0; i * a * 100 < f; ++i){
    for(int j = 0; j * b * 100 < f; ++j){
      float w = i * a * 100 + j * b * 100;      
      if(w > f) break;
      for(int l = 0; l * c < f; ++l){
        for(int m = 0; m * d < f; ++m){      
          float s = l * c + m * d;
          if(w + s > f) break;
          if((100 * s) / w <= e){          
            if(res <= (100 * s) / (s + w)){            
              res = (100 * s) / (s + w);
              max_s = s;            
              max_w = w;
            }
          }
        }
      }    
    }
  }
  cout << (max_s + max_w) << " " << max_s << endl;
}
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main(void) {

    ll A,B; cin>>A>>B;
    ll Gcd = __gcd(A,B);
    int cnt=1;

    for (ll i = 2; i*i <= Gcd; ++i) {
        if(Gcd % i ==0){
            cnt++;
            while(Gcd % i == 0){
                Gcd /= i;
            }
        }
    }

    if(Gcd>1) cnt++;
    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
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 (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int n; cin >> n;
  vector<int> a(n+1),b(n+1);
  REP(i,n) cin >> a[i+1];

  vector<int> ans;
  for (int i=n; i>0; i--) {
    int sum = 0;
    for(int j=i*2; j<=n; j+=i) sum+=b[j];
    if (sum%2 != a[i]) { b[i]++; ans.push_back(i); }
  }
  COUT(ans.size());
  REP(i,ans.size()) {
    cout << ans[ans.size()-i-1] << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 5360
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod = 1000000007;
const ll mod009 = 1000000009;
const ll mod998 = 998244353;
const ll intmax = 2147483647;
const ll llmax = 9223372036854775807;
const char sp = ' ';

int N, K, a[100000];
pair<int, int>tree[1 << 18];
set<int>st;
vector<int>res;


void update(int x, int t) {
	x += (1 << 17);
	tree[x].first = t;
	while (x) {
		x /= 2;
		tree[x] = max(tree[x + x], tree[x + x + 1]);
	}
}

bool func(int x) {
	if (x == N - 1) {
		if (a[res.back()] == *st.begin())return false;
		res.push_back(*st.begin());
		return true;
	}
	else {
		if (tree[1].first == N - x - 1) {
			auto p = tree[1];
			if (!res.empty() && a[res.back()] == p.second)return false;
			st.erase(p.second);
			res.push_back(p.second);
			update(p.second, 0);
			update(a[p.second], tree[(1 << 17) + a[p.second]].first - 1);
			if (func(x + 1))return true;
			res.pop_back();
			st.insert(p.second);
			update(a[p.second], tree[(1 << 17) + a[p.second]].first + 1);
			update(p.second, p.first);
		}
		else {
			auto it = st.begin();
			while (it != st.end()) {
				auto it2 = it;
				it2++;
				int t = *it;
				if (!(!res.empty() && a[res.back()] == t)) {
					st.erase(it);
					res.push_back(t);
					int k = tree[t + (1 << 17)].first;
					update(t, 0);
					update(a[t], tree[(1 << 17) + a[t]].first - 1);
					if (func(x + 1))return true;
					res.pop_back();
					st.insert(t);
					update(a[t], tree[(1 << 17) + a[t]].first + 1);
					update(t, k);
				}
				it = it2;
			}
		}
	}
	return false;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		a[i]--;
		tree[i + (1 << 17)].second = i;
		tree[a[i] + (1 << 17)].first++;
		st.insert(i);
	}
	for (int i = (1 << 17) - 1; i; i--) {
		tree[i] = max(tree[i + i], tree[i + i + 1]);
	}
	if (func(0)) {
		for (int i = 0; i < N - 1; i++) {
			cout << res[i] + 1 << sp;
		}
		cout << res[N - 1] + 1 << endl;
	}
	else {
		cout << -1 << endl;
	}
}

Measured memory_bytes: 13952
#include <iostream>

using namespace std;

int digitsSum(int n) {
    int ret = 0;
    while (n) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;

    int ret = 0;
    for (int m = 1; m <= n; m++) {
        int ds = digitsSum(m);
        if (a <= ds && ds <= b)
            ret += m;
    }
    cout << ret << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>

int main() {
	int x;
	cin >> x;
	for (int i = -1000; i < 1000; ++i) {
		for (int j = -1000; j < 1000; ++j) {
			if (pow(i, 5) - pow(j, 5) == x) {
				cout << i << " " << j;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 4100
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n = ri()
    s = input()
    if n % 2 == 1 or s[:n//2] != s[n//2:]:
        print("No")
        return
    print("Yes")


if __name__ == '__main__':
    main()


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

#define N 2000000

int main(void)
{
    unsigned long int i = 0, sum = 0, black = 0;
    char buf[N+2];

    if(scanf("%s", buf) != 1) {
        return 0;
    }

    while(buf[i]) {
        if (buf[i] == 'W') {
            sum += black;
        } else if (buf[i] == 'B') {
            black++;
        }
        i++;
    }

    printf("%lu\n", sum);
    return 0;
}


Measured memory_bytes: 384
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

int n,k,ans;

int32_t main(){_
    //freopen("input","r",stdin);
	cin >> n >> k;
	if(k == 0) rc(n * n);
	for(int i = k+1;i <= n;i++)
	{
		if(n % i == 0) ans += (n / i) * (i - 1 - k + 1) + (k == 0);
		else ans += (((n) / i)) * (i - 1 - k + 1) + (max(0LL,(n%i) - k + 1));
	}
	rc(ans);
}

Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
z_list = factorization(N)
Z = []
for z in z_list:
        for e in range(1, z[1]+1):
            Z.append(z[0]**e)
sorted(Z)
counter = 0 
if N==1:
    print(0)
    quit()
for z in Z:
    if(N%z==0):
        N = N//z
        counter += 1
print(counter)



Measured memory_bytes: 63400
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    int a,b,c;
    while(true){
        
        cin>>a>>b>>c;
        int ans=0;
        if(a+b+c==0)break;
        for(int i=1;i<c;i++){
            for(int j=1;j<c;j++){
                int x1=i*(100+a)/100;
                int x2=j*(100+a)/100;
                if(x1+x2==c){
                    int y1=i*(100+b)/100;
                    int y2=j*(100+b)/100;
                if(y1+y2>ans)ans=y1+y2;
                }
            }
        }
        cout<<ans<<endl;
        
        
        
    }

    return 0;
}



Measured memory_bytes: 3068
#include<cstdio>
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 100000
#define MM 200000
struct edge{int nx,t;}e[MM*2+5];
int h[MN+5],en,d[MN+5],o;
inline void ins(int x,int y)
{
	e[++en]=(edge){h[x],y};h[x]=en;
	e[++en]=(edge){h[y],x};h[y]=en;
}
void dfs(int x)
{
	for(int i=h[x];i;i=e[i].nx)
		if(d[e[i].t])o|=d[x]==d[e[i].t];
		else d[e[i].t]=3-d[x],dfs(e[i].t);
}
int main()
{
	int n=read(),m=read(),i,s1=0,s2=0,s3=0;
	while(m--)ins(read(),read());
	for(i=1;i<=n;++i)if(!d[i])
	{
		if(!h[i]){++s1;continue;}
		o=0;d[i]=1;dfs(i);
		if(o)++s3;else ++s2;
	}
	printf("%lld",2LL*n*s1-1LL*s1*s1+2LL*s2*s2+1LL*s3*(s2+s3)+1LL*s2*s3);
}

Measured memory_bytes: 5888
#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){
    	int a , b, c,moves = 0;
      	cin >> a >> b;
      	for(int i = 0; i < b; i++){
        	cin >> c;
          	moves +=c;  
        }
      
      	if(moves >= a){
        	cout << "Yes\n";
        }else{
        	cout << "No\n";
        }
      
    	return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    int h,w;
    cin >> h >>w;
    vector<string> s(h);
    for(int i=0;i<h;i++){
        cin >> s[i];
    }
    for(int j=0;j<w+2;j++){
        if(j==w+1) cout << "#" <<endl;
        else cout << "#";
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<3;j++){
            if(j==0) cout<< "#";
            else if(j==2) cout << "#"<<endl;
            else cout << s[i];
        }
    }
    for(int j=0;j<w+2;j++){
        if(j==w+1) cout << "#" <<endl;
        else cout << "#";
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <map>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<30;

typedef pair<int,int> pii;
typedef vector<vector<int> > mat;

mat ans(10,vector<int>(10));
int memo[15], memo2[15], memo3[15];
pii basyo[15];
int X, Y, n;
int ansnum;

void solve(mat ba, int d) {
  if (d == n) {
    ans = ba;
    ansnum++;
    return ;
  }
  for (int XX=1; XX<=memo[d]; ++XX) {
    if (memo[d] % XX) continue;
    int YY = memo[d] / XX;
    REP(yy, YY) {
      REP(xx, XX) {
        bool f = 0;
        REP(yyy, YY) {
          REP(xxx, XX) {
            int x = basyo[d].first - xx + xxx;
            int y = basyo[d].second - yy + yyy;

            if (x < 0 || X <= x || y < 0 || Y <= y) {
              f = 1;
            } else if (ba[x][y] != d && ba[x][y] != -1)
              f = 1;
          }
        }
        // ツつ「ツつッツづゥ
        if (!f) {
          mat tmp = ba;
          REP(yyy, YY) {
            REP(xxx, XX) {
              int x = basyo[d].first - xx + xxx;
              int y = basyo[d].second - yy + yyy;
              tmp[x][y] = d;
            }
          }
          solve(tmp, d+1);
        }
      }
    }
  }
}
  
  
int main() {
  mat ba(10, vector<int>(10));
  while(cin >> X >> Y >> n, X+Y+n) {
    vector<pii> P(n);
    REP(i,n) {
      int b, k;
      cin >> b >> k;
      P[i] = make_pair(k,b);
    }
    sort(ALL(P), greater<pii>());
    REP(i,n) {
      memo[i] = P[i].first;
      memo2[P[i].second] = i;
      memo3[i] = P[i].second;
    }
    REP(y, Y) {
      REP(x, X) {
        cin >> ba[x][y];
        if (ba[x][y] > 0) {
          ba[x][y] = memo2[ba[x][y]];
          basyo[ba[x][y]] = pii(x,y);
        } else
          ba[x][y] = -1;
      }
    }
    ansnum = 0;
    solve(ba, 0);
    if (ansnum == 1) {
      REP(y,Y) {
        REP(x,X) {
          if (x) cout << " ";
          cout << memo3[ans[x][y]];
        }
        cout << endl;
      }
    } else
      cout << "NA" << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> i_i;
ll INF = 1e12+10;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
vector<pair<ll, ll> > pairs;
#define print1(x) cerr << "x = " << x << endl;
#define print2(x, y) cerr<< "x,y = "  << x << "," << y << endl;
#define print3(x, y, z) cerr << "x,y,z = " << x << "," << y << "," << z << endl;

int opinion[16], fopinion[16], A[16];

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

int main()
{
    ll A, B;
    cin >> A >> B;
    ll g = gcd(A, B);
    cout << A * B/g;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  int a[209];
  int ans=0;
  cin>>n;
  n*=2;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  for(int i=0;i<n;i+=2){
    ans+=a[i];
  }
  cout<<ans<<endl;
  return(0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define DEBUG
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define deb(x) std::cout << #x << " " << x << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}
template<typename... T>
void write(T... a){
    ((cout << a << "\n"),...);
}

template<typename... T>
void write_space(T... a){
    ((cout << a << " "),...);
}

void solve(){
    int x;
    read(x);
    cout << 1 - x << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    solve();
    return 0;
}



Measured memory_bytes: 3652
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define pb push_back
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
int main(){
	ios::sync_with_stdio(false);
	int t,d=0,a;
	for(cin>>t;t;t--){
		cin>>a;
		d=gcd(a,d);
	}
	cout<<d<<endl;
	return 0;
}





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

using pii = pair<int, int>;

int main() {
    int n, r, l; cin >> n >> r >> l;
    vector<int> d(r), t(r), x(r);
    for(int i = 0; i < r; ++i) {
        cin >> d[i] >> t[i] >> x[i];
        d[i]--;
    }
    vector<int> score(n), ans(n);
    priority_queue<pii> que;
    for(int i = 0; i < n; ++i) que.emplace(0, -i);

    int pre_t = 0;
    for(int i = 0; i < r; ++i) {
        while(score[-que.top().second] != que.top().first) que.pop();
        ans[-que.top().second] += t[i] - pre_t;
        score[d[i]] += x[i];
        que.emplace(score[d[i]], -d[i]);
        pre_t = t[i];
    }
    while(score[-que.top().second] != que.top().first) que.pop();
    ans[-que.top().second] += l - pre_t;

    cout << (max_element(begin(ans), end(ans)) - begin(ans) + 1) << endl;
}



Measured memory_bytes: 19528
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(v) (v).size()
#define debug(x) cerr << #x << "_=_" << x << "\n";
#define sum(n) ((n)*((n)+1)>>1)
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<pair<int, int>, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;

const int MAXN = 1e5+5;
int dp[MAXN][5], cost[MAXN][5];
int n;

int f(int i, int lst){
    if(i<0) return 0;
    if(~dp[i][lst]) return dp[i][lst];
    int ans=INT_MIN;
    for (int k=0; k<3; k++){
        if(k==lst) continue;
        ans = max(ans, f(i-1, k) + cost[i][k]);
    }
    return dp[i][lst] = ans;
}


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


    cin >> n;
    for (int i=0; i<n; i++)
        for (int j=0; j<3; j++)
            cin >> cost[i][j];

    memset(dp, -1, sizeof dp);
    cout << f(n-1, 3) << "\n";

    return 0;
}

/*
1
9 3
111100000
 */

Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi atan(1.0)*4
#define pb(x) push_back(x)
#define in(x) insert(x)
#define fl(x,y) for(ll i=x;i<y;i++)
#define vi vector<long long>
#define vs  vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define fi first
#define se second
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
/*bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
LL bpow(LL a,LL b){if(b==0)return 1;LL r=bpow(a,b/2);if(b%2)return r*r*a;else return r*r;}
LL binpow(LL a,LL b){LL r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
LL binpow(LL a,LL b,LL m){a%=m;LL r=1;while(b>0){if(b&1) r=r*a%m;a=a*a%m; b>>=1;}return r;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
*/
//bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int main()
{
    ll a,b,c,t,n,k,p,q,r,y,yy,sum,ct=0,flag=0;
    string s,s1,s2,s3;
    set<ll>st;
    char ch;
    map<ll,ll>mp;
    vector<string>v,vv,vz;

      cin>>a>>b;
      fl(0,a)
      {
          cin>>s;
          v.pb(s);
      }
      fl(0,a)
      {
          cout<<v[i]<<endl;
          cout<<v[i]<<endl;
      }
}





Measured memory_bytes: 3624
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [1] * n

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]


n, m = [int(i) for i in input().split()]
uf = UnionFind(n)
ab = [[int(i) - 1 for i in input().split()] for _ in range(m)]
c = n * (n - 1) // 2
ans = []
for a, b in reversed(ab):
    ans.append(c)
    if uf.is_same_tree(a, b):
        continue
    e = uf.get_root(a)
    f = uf.get_root(b)
    c -= uf.count[e] * uf.count[f]
    uf.merge(a, b)
print("\n".join(map(str, reversed(ans))))


Measured memory_bytes: 35788
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int n; cin>>n;
    int r = 0, l = inf;
    rep(i,n){
        int p; cin>>p;
        r = max(r,p);
        l = min(l,p);
    }
    cout<<r-l<<endl; return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    int n,s=0;
    scanf("%d",&n);
    while(n/10!=0){
        if(n%10==7){
            s=1;
            break;
        }
        n=n/10;
    }
    if((n==7)||(s==1))
        printf("Yes\n");
    else 
        printf("No\n");
    return 0;
}

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

typedef long long int llint;

int main()
{
  int n, a;
  cin>> n >> a;
  
  if(n % 500 <= a)
    cout<< "Yes" <<endl;
  else
    cout<< "No"  <<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using P = pair<int,int>;
using ll = long long;
static const int INF = 1000000000;
static const ll MOD = 1000000007;
ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

vector<ll> fac(1000001); //n!(mod M)
vector<ll> ifac(1000001); //k!^{M-2} (mod M)
//a,bの範囲的にこれだけ配列を用意していけば十分

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b] * ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}

int main(){
  int x, y;
  cin >> x >> y;
  if((x + y) % 3 != 0){
    cout << 0 << endl;
    return 0;
  }

  int m = (2 * y - x) / 3;
  int n = (2 * x - y) / 3;
  if(m < 0 || n < 0){
    cout << 0 << endl;
    return 0;
  }

  fac[0] = 1;
  ifac[0] = 1;
  for(ll i = 0; i<1000000; i++){
      fac[i+1] = fac[i]*(i+1) % MOD; // n!(mod M)
      ifac[i+1] = ifac[i]*mpow(i+1, MOD-2) % MOD; // k!^{M-2} (mod M) ←累乗にmpowを採用
  }

  cout << comb(m + n, n) << endl;

  return 0;
}

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

using namespace std;

long bit[222222];
int siz;
void add(int a, int n) {
	for (a++; a <= siz; a += a & -a)
		bit[a] += n;
}
long sum(int a) {
	long r = 0;
	for (; a; a &= a - 1)
		r += bit[a];
	return r;
}

int a[111111];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	int l = 1, r = 1e9 + 1;
	siz = n * 2;
	while (l + 1 < r) {
		int x = (l + r) / 2;
		int s = n;
		fill(bit, bit + n * 2 + 1, 0);
		add(s, 1);
		long c = 0;
		for (int i = 0; i < n; i++) {
			s += a[i] < x ? 1 : -1;
			c += sum(s);
			add(s, 1);
		}
		if (c > n*(n + 1l) / 4)
			r = x;
		else l = x;
	}
	cout << l << endl;
	return 0;
}


Measured memory_bytes: 2176
import java.util.Scanner;

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

            int array[][] = new int[3][3];

            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    array[i][j] = sc.nextInt();
                }
            }

            int n = sc.nextInt();

            int target[] = new int[n];
            for (int i = 0; i < n; i++) {
                target[i] = sc.nextInt();
            }

            String result = "No";

            int check[][] = new int[3][3];
            a: for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    for (int k : target) {
                        if (array[i][j] == k) {
                            check[i][j] = 1;

                            if (bingo(check)) {
                                result = "Yes";
                                break a;
                            }
                        }
                    }
                }
            }

            System.out.println(result);

        }
    }

    private static boolean bingo(int[][] data) {

        boolean result = false;

        for (int[] a : data) {
            // 横
            boolean test = true;
            for (int b : a) {
                if (b == 0) {
                    test = false;
                    break;
                }
            }
            if (test) {
                return true;
            }

        }

        // 縦
        for (int i = 0; i < 3; i++) {
            boolean test = true;
            for (int j = 0; j < 3; j++) {
                if (data[j][i] == 0) {
                    test = false;
                    break;
                }
            }
            if (test) {
                return true;
            }
        }

        // 斜め
        boolean test = true;
        for (int i = 0; i < 3; i++) {
            if (data[i][i] == 0) {
                test = false;
                break;
            }
        }
        if (test) {
            return true;
        }

        int cnt = 0;
        test = true;
        for (int i = 2; i >= 0; i--) {
            if (data[i][cnt] == 0) {
                test = false;
                break;
            }
            cnt++;
        }
        if (test) {
            return true;
        }

        return result;
    }
}


Measured memory_bytes: 23764
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)















int main() {
	ll n, m, v, p;
	cin >> n >> m >> v >> p;
	vector<ll> a(n);
	REP(i, n) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<ll>());
	ll l = 0, r = n;
	auto f = [&](ll x) {
		if (x < p) return true;
		if (a[x] + m < a[p - 1]) return false;
		ll sum = 0;
		REP(i, n) {
			if (i < p - 1) sum += m;
			else if (i < x) sum += a[x] - a[i] + m;
			else sum += m;
		}
		return m * v <= sum;
	};
	while (r - l > 1) {
		ll x = (l + r) / 2;
		if (f(x)) l = x;
		else r = x;
	}
	cout << l + 1 << endl;
}

Measured memory_bytes: 1024
H, W = map(int, input().split())
a = [list(map(int, input().split())) for i in range(H)]
flag = False
prev = [-1, -1]
ans = []
for i in range(0, H, 2):
    for j in range(W):
        if flag:
            ans.append(" ".join(map(str, [prev[0], prev[1], i+1, j+1])))
            a[i][j] += 1
            flag = False
        if a[i][j] % 2 == 1:
            flag = True
            prev = [i+1, j+1]
    if i < H-1:
        for j in reversed(range(W)):
            if flag:
                ans.append(" ".join(map(str, [prev[0], prev[1], i+2, j+1])))
                a[i+1][j] += 1
                flag = False
            if a[i+1][j] % 2 == 1:
                flag = True
                a[i+1][j] -= 1
                prev = [i+2, j+1]

print(len(ans))
for x in ans:
    print(x)


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

int main() {
  // 入力
  int N;
  cin >> N;
  int d[N];
  for (int i = 0; i < N; i++) scanf("%d", d + i);
  int M;
  cin >> M;
  int t[M];
  for (int i = 0; i < M; i++) scanf("%d", t + i);

  sort(d, d + N);
  sort(t, t + M);
  int pos = 0;
  for (int i = 0; i < N; i++) {
    if (d[i] == t[pos]) pos++;

    if (pos == M) break;
  }

  // 解答
  cout << (pos == M ? "YES" : "NO") << endl;

  return 0;
}


Measured memory_bytes: 1792
import java.util.*;


public class Main{
  public static void main(String[] arg){
    Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    int S = sc.nextInt();
    int total = 0;
    List<Integer> list = new ArrayList<>();
    for(int i = 0; i < K+1; i++){
      list.add(i);
    }
    for(int x = 0; x < K+1; x++){
      for(int y = 0; y < K+1; y++){
          if(S-(list.get(x) + list.get(y))<=K &&
             (S-(list.get(x) + list.get(y))>=0)){
            total += 1;
          }
      }
    }
    System.out.println(total);
  }
}


Measured memory_bytes: 22100
taro, hanako = (0, 0)
for i in range(int(input())):
    t, h = input().strip().split()
    if t > h:
        taro += 3
    elif t < h:
        hanako += 3
    else:
        taro += 1
        hanako +=  1

print(taro, hanako)

Measured memory_bytes: 7680
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int a,b;
    char op;
    cin >> a >> op >> b;
    if(op=='+')cout << a+b;
    else cout << a-b;
    cout << endl;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> x(n),y(n),h(n);
	int nonzero;
	for(int i=0; i<n; i++){
		cin >> x[i] >> y[i] >> h[i];
		if(h[i] != 0) nonzero = i;
	}
	for(int i=0; i<=100; i++){
		for(int j=0; j<=100; j++){
			int top = h[nonzero] +abs(i-x[nonzero]) +abs(j-y[nonzero]);
			bool ok = true;
			for(int k=0; k<n; k++){
				if(max(top -abs(i-x[k]) -abs(j-y[k]), 0) != h[k]){
					ok = false;
					break;
				}
			}
			if(ok){
				cout << i << " " << j << " " << top << endl;
				i = 100;
				break;
			}
		}
	}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (int)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

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

    ll N;
    cin >> N;
    double s = 0;
    rep(_, N){
        double a;
        cin >> a;
        s += 1 / a;
    }

    print(1 / s);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while(cin >> N, N){
        vector<int> w(N);
        REP(i,N) cin >> w[i];
        // REP(i,N) cout << w[i] << " ";
        // cout << endl;
        vector<vector<int>> dp(N+1, vector<int>(N+1, -1));
        auto solve = [&](auto && self, int l, int r) -> int{
            if(l >= r) return 0;
            int &res = dp[l][r];
            if(res != -1) return res;
            for(int i=l;i<r;i++){
                res = max(res, self(self, l, i) + self(self, i+1, r));
            }
            if(abs(w[l] - w[r]) <= 1){
                if(self(self, l + 1, r - 1) == max(0, r - l - 1)) res = r - l + 1;
            }
            return res;
        };

        cout << solve(solve, 0, N-1) << endl;;
    }
}


Measured memory_bytes: 3344