akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

const int mx=1000006;
int hurui[mx];
const int INF = 100100101;
int main() {
  int n;
  cin >> n;
  vi a(n,0);
  rep(i,n) {
    cin >> a.at(i);
  }
  int ans = 0;
  sort(rng(a));
  rep(i,n) {
    int ai=a.at(i);
    int cai=a.at(i);
    if(hurui[ai]==INF) {
      ans--;
      hurui[ai]++;
      continue;
    }
    if(hurui[ai]>INF) continue;
    if(hurui[ai]>0 and hurui[ai] < 1000000) {
      continue;
    }
    hurui[ai] = INF;
    ans++;
    ai+=cai;
    while(ai<mx) {
      hurui[ai]++;
      ai+=cai;
    }
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 7980
//                                               KEEP GRINDING
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define int long long
#define ld long double
#define MOD 1000000007
#define mod 998244353
#define precise(i) fixed << setprecision(10) << i
#define f(i,a,b) for(int i=a;i<b;++i)

#define endl '\n'
#define debug cout<<"\n========================================\n"<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define all(a) a.begin(),a.end()
#define show(a) for(auto xyz:a)cout<<xyz<<" ";cout<<endl;
#define mx(a) *max_element(a)
#define mn(a) *min_element(a) 
#define LB lower_bound  //THIS GIVES THE ITR TO THE ELEMENT IN RANGE [SI,EI) THAT IS >= OUR VALUE 
#define UB upper_bound  //THIS GIVES THE ITR TO THE ELEMENT IN RANGE [SI,EI) THAT IS > OUR VALUE 

#define fr first
#define sc second

#define MAXN 500000
#define INF 9223372036854775807
signed main(){
    fastio
    int A,B,V,W,T;
    cin >> A >> V >> B >> W >> T;
    if( W >= V ){
    	cout<<"NO"<<endl;
    	return 0;
	}if( abs(B-A) <= T * abs(V-W) ){
		cout<<"YES"<<endl;
		return 0;
	}else{
		cout<<"NO"<<endl;
    	return 0;
	}

}

Measured memory_bytes: 3660
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[500005];
vector<int> G[500005];
string s;
int last0=0;
int main()
{
    int N;
    cin>>N>>s;
    s=" "+s;
    for(int i=1;i<=N;i++)
    {
        if(s[i]=='0')
        {
            if(s[i-1]=='1')
            {
                for(int j=i+1;j<=N&&s[j]=='1';j++)
                    G[j].push_back(i-2);
            }
            if(s[i+1]=='1')
            {
                for(int j=i-1;j>0&&s[j]=='1';j--)
                    G[i+1].push_back(j-1);
            }
        }
    }
    for(int i=1;i<=N;i++)
    {
        dp[i]=dp[i-1];
        for(auto it:G[i])
            dp[i]=max(dp[i],dp[it]+(i-it-2));
    }
    cout<<dp[N];
    return 0;
}


Measured memory_bytes: 32664
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n;
  cin >> n;
  vp w(n);
  rep(i,n){
    cin >> w[i].se >> w[i].fi;
  }
  sort(rng(w));
  int c = 0;
  rep(i,n){
    c+=w[i].se;
    if(c>w[i].fi){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 1792
n = int(input())
a = list(map(int, input().split()))
A = max(a)
t = -1
tt = 0
for i in range(n):
    if t < a[i]:
        t = a[i]
        tt = i
a.pop(tt)
# print(a)
z = A / 2
d = float('INF')
da = 0
for i in range(n - 1):
    # print(d, abs(a[i] - z))
    if d > abs(a[i] - z):
        da = a[i]
        d = abs(da - z)
print(A, da)


Measured memory_bytes: 14428
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	ll n;
	cin >> n;

	vector<ll> a(n);
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	ll m;
	cin >> m;

	vector<ll> b(m);
	for (ll i = 0; i < m; i++)
	{
		cin >> b[i];
	}

	vector<ll> res;
	set_union(all(a), all(b), inserter(res, end(res)));

	for (ll it : res)
	{
		println(it);
	}
}


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

int main(){
  long long int w, h, v, t, x, y, p, q;
  cin >> w >> h >> v >> t >> x >> y >> p >> q;
  long long int r = v*t;
  long long int ans = 0LL;
  for(int i = 0; i < 2; ++i){
    for(int j = 0; j < 2; ++j){
      long long int m = (-r+x)/2/w - 1;
      long long int k = 2*w*m - (1-2*i)*p;
      int d = (1-2*j);
      while(k < r + x && (k-x)*(k-x) + (d*q-y)*(d*q-y) > r*r && (k-x)*(k-x) + (2*h+d*q-y)*(2*h+d*q-y) > r*r) k += 2*w;
      while((k-x)*(k-x) + (d*q-y)*(d*q-y) <= r*r || (k-x)*(k-x) + (2*h+d*q-y)*(2*h+d*q-y) <= r*r){
	long long int l = sqrt(r*r - (k-x)*(k-x));
	ans += (l+y-d*q)/2/h - (-l+y-d*q)/2/h + 1;
	if((k-x)*(k-x) + (d*q-y)*(d*q-y) > r*r && (k-x)*(k-x) + (2*h+d*q-y)*(2*h+d*q-y) <= r*r) --ans;
	k += 2*w;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3116
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

int main(void)
{
    long long A, B, C, K;
    cin >> A >> B >> C >> K;

    long long ans = 0;
    ans += min(A, K);
    ans -= min(C, max(0LL, K - A - B));

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll n, dp[3005][3005];
const ll inf = 1e18+5;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	vector<ll> a(n);
	for (ll i= 0; i< n; i++)cin >> a[i];
	for (ll i = n-1; i >= 0; i--){
		for (ll j = i; j < n; j++){
			ll L = i, R= j;
			dp[i][j] = max(a[L] - dp[L+1][R], (R == 0 ? -inf:a[R] - dp[L][R-1]));
		} //this works because 1. whenever i calculate ij and look back at the dp states, i am trying to maximise y-x for the 
		//opponent, this means i am maximizing -(x-y) which is equivalent to minimizing x-y
	}
	cout << dp[0][n-1];
}


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

using namespace std;



int main() {
	double A,B,H,M;
	double pi = 3.141592653589793238;
	string S;
	cin >> A >> B >> H >> M;
	double nAns;
	double x = 30 * H + 0.5 * M - 6 * M;
	if (x < 0) {
		x = -x;
	}
	nAns = A * A + B * B - 2 * A * B * cos(x / 180.0 * pi);
	printf("%.10f\n", sqrt(nAns));
	return 0;
}

Measured memory_bytes: 4200
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

ll N,M,K,A,B,C;
string S;
vector<ll> vec;

void solve() {
	cin >> N >> K;

	cout << (K==1 ? 0 : N - K);
}

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

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

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

using namespace std;

template <class T>
void printv(vector<T> v)
{
  cout << '[';
  for (auto vec: v)
  {
    cout << vec << ' ';
  }
  cout << ']' << endl;
}

int main()
{
  map<long long, long long> m;
  map<long long, long long> mm;
  set<long long> s;
  long long n, mmax = 0, mmmax = 0;
  cin >> n;
  vector<long long> v;
  vector<long long> w;
  vector<pair<long long, long long>> vv;
  vector<pair<long long, long long>> ww;

  for (long long i = 0; i < n; i++)
  {
    long long tmp;
    cin >> tmp;
    s.insert(tmp);

    if (i % 2 == 0)
    {
      m[tmp]++;
      if (mmax < m[tmp])
        mmax = m[tmp];
      v.push_back(tmp);
    }
    else
    {
      mm[tmp]++;
      if (mmmax < mm[tmp])
        mmmax = mm[tmp];
      w.push_back(tmp);
    }
  }

  for (auto itr : m)
  {
    vv.push_back({itr.first, itr.second});
  }

  for (auto itr : mm)
  {
    ww.push_back({itr.first, itr.second});
  }

  sort(vv.begin(), vv.end(), [](auto left, auto right){return left.second > right.second;});
  sort(ww.begin(), ww.end(), [](auto left, auto right){return left.second > right.second;});

  if (vv[0].first == ww[0].first)
  {
    if (vv.size() == 1)
      vv.push_back({0, 0});
    if (ww.size() == 1)
      ww.push_back({0, 0});

    if ((w.size() - ww[1].second) + (v.size() - mmax) > (w.size() - mmmax) + (v.size() - vv[1].second))
      mmax = vv[1].second;
    else
      mmmax = ww[1].second;
  }

  if (s.size() == 1)
  {
    long long aaaaa = (w.size() + v.size()) / 2;
    cout << aaaaa << endl;
  }
  else if (v.size() == mmax && w.size() == mmmax)
    cout << 0 << endl;
  else
    cout << (w.size() - mmax) + (v.size() - mmmax) << endl;
}


Measured memory_bytes: 14316
def main():
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())

    m = H*W // 2 + (H*W) % 2

    if H == 1 or W == 1:
        print(1)
    else:
        print(m)


if __name__ == '__main__':
    main()


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

int main()
{
	string s;
	cin>>s;
	
	char ans[100000];
	for(int i=0;i<s.length();i+=2){
		ans[i/2]=s[i];
	}
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    string s, ans = "NA";
    cin >> s;
    bool yymm = false, mmyy = false;
    int a = stoi(s);
    if (a % 100 < 13 and a % 100 > 0) {
        yymm = true;
    }
    if (a / 100 < 13 and a / 100 > 0) {
        mmyy = true;
    }
    if (yymm and mmyy) {
        ans = "AMBIGUOUS";
    } else if (yymm and !mmyy) {
        ans = "YYMM";
    } else if (!yymm and mmyy) {
        ans = "MMYY";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>

using namespace std;

int main(){
  int n;
  bool valueExe = false;
  cin>>n;
  long long int res = 1, maxVal = 1000000000000000000;
  for(int i = 0; i < n; i++){
   	 long long int num;
     cin>>num;
     if(num == 0){
       cout<<0;
       return 0;
     }
     if(res > maxVal/num){
      	valueExe = true;
     }
    if(valueExe == false){
      res *= num;
    }
  }
  if(valueExe == true){
   cout<<-1; 
  }
  else{
  	cout<<res;
  }
  return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    long long N,X,i,pan[51],sum[51];
    cin>>N>>X;
    long long x=X;
    pan[0]=0;sum[0]=1;
    for(i=0;i<51;i++){
        pan[i+1]=pan[i]*2+2;
        sum[i+1]=sum[i]*2+3;
    }
    long long pansum=0;
    for(i=N;i>0;i--){
        if(X==sum[i]){
            pansum+=pan[i];
            break;
        }
        if(X>sum[i-1]+1){
            pansum+=pan[i-1]+1;
            X-=sum[i-1]+2;
        }else{
            if(X>0){
                pansum++;
                X--;
            }
        }
    }
    cout<<x-pansum<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
    return powmod(a, MOD-2);
}
int main()
{
	int n, k; cin>>n>>k;
	vector<P> v(n);
	for(int i=0; i<n; i++){
		ll a; cin>>a;
		if(a>=0) v[i]=P(a, 1);
		else v[i]=P(-a, 0);
	}
	sort(v.begin(), v.end(), greater<P>());
	int cnt=0;
	ll ans=1;
	for(int i=0; i<k; i++){
		if(v[i].second) (ans*=v[i].first)%=MOD;
		else (ans*=(MOD-v[i].first))%=MOD;
		cnt+=1-v[i].second;
	}
	if(ans==0){
		cout<<0<<endl;
		return 0;
	}
	if(cnt%2==0){
		cout<<ans<<endl;
		return 0;
	}
	ll mn1=MOD, mn2=MOD, mx1=-1, mx2=-1;
	for(int i=0; i<k; i++){
		if(v[i].second) mn1=min(mn1, v[i].first);
		else mn2=min(mn2, v[i].first);
	}
	for(int i=k; i<n; i++){
		if(v[i].second) mx1=max(mx1, v[i].first);
		else mx2=max(mx2, v[i].first);
	}
	P mx=P(-1, 1);
	if(mn1<MOD && mx2>=0){
		if(mx.first*mn1<mx.second*mx2){
			mx=P(mx2, mn1);
		}
	}
	if(mn2<MOD && mx1>=0){
		if(mx.first*mn2<mx.second*mx1){
			mx=P(mx1, mn2);
		}
	}
	if(mx==P(-1, 1)){
		ans=1;
		for(int i=n-1; i>=n-k; i--){
			if(v[i].second) (ans*=v[i].first)%=MOD;
			else (ans*=(MOD-v[i].first))%=MOD;
		}
		cout<<ans<<endl;
	}else{
		ans=ans*mx.first%MOD*inv(mx.second)%MOD;
		ans=(MOD-ans)%MOD;
		cout<<ans<<endl;
	}
	return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;

  vector<int> vec(N);
  for (int i = 0; i < N; i++) cin >> vec.at(i);

  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());

  int ans = 0;

  for (int i = 0; i < K; i++) {
    ans += vec.at(i);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;cin>>n;
  ll i,j,k,a[n],ans=0;
  for(i=0;i<n;i++) cin>>a[i];
  k=1;
  for(i=0;i<n;i++){
    j=(a[i]-1)/k;
    if(j<=0){
      k=max(k,a[i]+1);
      continue;
    }
    ans+=j;
    a[i]-=j*k;
    if(a[i]==k&&k==1) k++;
    //cout << i << ":" << k << ":" << ans << endl;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

void insertionSort (int A[],int n,int g) {
  for (int i = g; i <= n-1; i++) {
    int v = A[i];
    int j = i - g;
    while (j >= 0 && A[j] > v) {
      A[j+g] = A[j];
      j -= g;
      cnt++;
      }
    A[j+g] = v;
    }
  }

  void shellSort (int A[],int n) {
    for(int h = 1; ; ) {
      if(h>n) break;
      G.push_back(h);
      h = 3*h + 1;
    }

    for(int i = G.size() - 1; i >= 0; i--) {
      insertionSort (A,n,G[i]);
    }

  }

int main() {
  cin >> n;
  for(int i = 0; i < n; i++) {
    scanf("%d", &A[i]);
  }
  cnt = 0;

  shellSort(A,n);

  int m = G.size();
  std::cout << m << endl;
  for(int i = m-1; i >= 0; i--) {
    printf("%d", G[i]);
    if(i) printf(" ");
  }
  printf("\n");
  printf("%d\n",cnt);
  for(int i = 0; i < n; i++) {
    printf("%d\n",A[i]);
  }
}


Measured memory_bytes: 7220
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
constexpr int MOD = 100000000 + 7;
// constexpr int MOD = 998244353;
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;
}
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int modpow(int a, int n)
{
    int res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

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

    int n;
    string s;
    cin >> n >> s;

    bool can = true;
    if (n % 2)
        can = false;
    else
    {
        for (int i = 0; i < n / 2; i++)
        {
            int j = i + n / 2;
            if (s[i] != s[j])
            {
                can = false;
                break;
            }
        }
    }
    cout << (can ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <queue>
#include <stack>
#include <cstring>
#include <ctime>
#include <cassert>


#define pb emplace_back
#define re return
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const double pi = 3.14159265359;


int main()
{
    //freopen("distance.in", "r", stdin);
    //freopen("distance.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    int ans = n / m;
    if (n % m)
        ans++;
    cout << ans;
}
/// ACTUAL CODE STARTS HERE:
//  I'm red in soul
/*
     ▄▀▀▀▄
▄███▀░◐░░░▌
    ▌░░░░░▐
    ▐░░░░░▐
    ▌░░░░░▐▄▄
    ▌░░░░▄▀▒▒▀▀▀▀▄
   ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
   ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
    ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
      ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
           ▌▌░▌▌
           ▌▌░▌▌
         ▄▄▌▌▄▌▌        */


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a[10001][7];
  for(int i=0;i<7;i++)a[0][i]=i;
  int n;
  while(cin>>n){
    if(n==0)return 0;
  string in;
  for(int i=1;i<=n;i++){
    cin>>in;
    for(int j=1;j<7;j++){
      a[i][j]=a[i-1][j];
    }
    if(in=="North"){
      a[i][1]=a[i-1][2];
      a[i][2]=a[i-1][6];
      a[i][5]=a[i-1][1];
      a[i][6]=a[i-1][5];
    }
    if(in=="East"){
      a[i][1]=a[i-1][4];
      a[i][3]=a[i-1][1];
      a[i][4]=a[i-1][6];
      a[i][6]=a[i-1][3];
    }
 if(in=="West"){
      a[i][1]=a[i-1][3];
      a[i][3]=a[i-1][6];
      a[i][4]=a[i-1][1];
      a[i][6]=a[i-1][4];
    }
 if(in=="South"){
      a[i][1]=a[i-1][5];
      a[i][2]=a[i-1][1];
      a[i][5]=a[i-1][6];
      a[i][6]=a[i-1][2];
    }
 if(in=="Right"){
      a[i][2]=a[i-1][3];
      a[i][3]=a[i-1][5];
      a[i][4]=a[i-1][2];
      a[i][5]=a[i-1][4];
    }
 if(in=="Left"){
      a[i][2]=a[i-1][4];
      a[i][3]=a[i-1][2];
      a[i][4]=a[i-1][5];
      a[i][5]=a[i-1][3];
    }
  }int sum=0;
  for(int i=0;i<=n;i++){
    sum+=a[i][1];
  }
  cout<<sum<<endl;

  }
}

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

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

    int ans = 0;
    while(1){
        for(i = 0; i < N; i++){
            if(A[i] % 2 != 0) break;
            A[i] /= 2;
        }
        if(i != N) break;
        ans++;
    }

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

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] line = scanner.nextLine().split(" ");
        int a1 = Integer.parseInt(line[0]);
        int a2 = Integer.parseInt(line[1]);
        int a3 = Integer.parseInt(line[2]);
        int a4 = Integer.parseInt(line[3]);
        int a5 = Integer.parseInt(line[4]);
        int a6 = Integer.parseInt(line[5]);
 
        int b = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < b; i++) {
            int c = scanner.nextInt();
            int d = scanner.nextInt();
            int result = 0;
            if (c == a1 || c == a6)
                if (d == a2)
                    result = 3;
                else if (d == a3)
                    result = 5;
                else if (d == a4)
                    result = 2;
                else
                    result = 4;
            else if (c == a2 || c == a5)
                if (d == a1)
                    result = 4;
                else if (d == a3)
                    result = 1;
                else if (d == a4)
                    result = 6;
                else
                    result = 3;
            else {
                if (d == a1)
                    result = 2;
                else if (d == a2)
                    result = 6;
                else if (d == a5)
                    result = 1;
                else
                    result = 5;
            }
            if (c == a4 || c == a5 || c == a6)
                result = 7 - result;
            System.out.println(line[result - 1]);
        }
    }
}


Measured memory_bytes: 26240
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    r, D, x = MI()
    for _ in range(10):
        x = (x * r) - D
        print(x)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;

const long long INF = 1LL<<10;

void solve(long long n, vector< vector<long long> > A) {
    bool is_need_edge = true;
    long long ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            is_need_edge = true;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) {
                    continue;
                }
                if (A[i][j] > A[i][k] + A[j][k]) {
                    std::cout << -1 << std::endl;
                    return;
                }
                if (A[i][j] == A[i][k] + A[j][k]) {
                    is_need_edge = false;
                }
            }
            if (is_need_edge) {
                ret += A[i][j];
            }
        }
    }
    std::cout << ret << std::endl;
}

int main() {
    struct timeval start,end;
    long long span;
    long long n;

    gettimeofday(&start,NULL);

    std::cin >> n;
    vector< vector<long long> > A(n, vector<long long>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> A[i][j];
        }
    }
    solve(n, A);

    gettimeofday(&end,NULL);
    span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
    std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
    return 0;
}


Measured memory_bytes: 1664
a[1000],m,n,c;main(d){
for(scanf("%d%d",&n,&m);m--;)for(scanf("%d%d",&c,&d);c<d;c++)a[c]=1;
for(c=d=0;c<n;c++)d+=a[c]*2;
m=!printf("%d\n",d+n+1);
}

Measured memory_bytes: 604
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int k = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        boolean flag = false;
        for(int i = a; i<=b; i++){
            if(i % k ==0){
                flag = true;
            }
        }

        System.out.println(flag?"OK":"NG");
    }
}

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

int main()
{
    string S;
    cin >> S;
    list<bool> s;
    list<bool>::iterator itr;
    for (int i = 0; i < S.size(); i++)
    {
        if (s.empty())
        {
            s.push_back(S[i] == '0');
        }
        else
        {
            if (s.back() != (S[i] == '0'))
            {
                itr = s.end();
                itr--;
                s.erase(itr);
            }
            else
            {
                s.push_back(S[i] == '0');
            }
        }
    }
    cout << S.size() - s.size() << endl;
}


Measured memory_bytes: 3456
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        int i,j,area,per;
        
        Scanner scan = new Scanner(System.in);
        i = scan.nextInt();
        j = scan.nextInt();
        
        area = i*j;
        per = (i*2)+(j*2);
        System.out.println(area + " " + per);
        
        
    }
}


Measured memory_bytes: 26188
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int A, B, m;
    cin >> A >> B >> m;
    int a[A], b[B];
    int amin = 1e+7, bmin = 1e+7;
    rep(i, A) cin >> a[i], amin = min(amin, a[i]);
    rep(i, B) cin >> b[i], bmin = min(bmin, b[i]);
    ll ans = amin + bmin;
    rep(i, m){
        int x, y, c;
        cin >> x >> y >> c;
        ll tmp;
        tmp = a[x - 1] + b[y - 1] - c;
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
n, k = map(int, input().split())
m = (n - 1) * (n - 2) // 2
if k > m:
    print(-1)
    exit(0)
print(n + m - k - 1)
for i in range(1, n):
    print(i, n)
for i in range(1, n):
    for j in range(i + 1, n):
        if m == k:
            exit(0)
        print(i, j)
        k += 1

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

int main()
{
    // input
    int a, b, c;
    cin >> a >> b >> c;

    // output
    if (a < b && b < c)
    {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}



Measured memory_bytes: 3084
#include<bits/stdc++.h>
#define ll long long 
#define inf 1000000007
using namespace std;
void make_fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int main(){
    make_fast();
    ll n,m,k;

	    scanf("%lld %lld %lld",&n,&m,&k);
	    vector<ll>a(n),b(m);
	    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	    for(int i=0;i<m;i++)scanf("%lld",&b[i]);
	    ll tk1=0,tk2=0;
	    int res1=0,res2=0;
	    int res=0;
	    if(a[0]<=k)res=1;
	    if(b[0]<=k)res=1;
	    for(int i=1;i<n;i++){
	        a[i]+=a[i-1];
	        if(a[i]<=k)res=max(res,i+1);
	    }
	    for(int i=1;i<m;i++){
	        b[i]+=b[i-1];
	        if(b[i]<=k)res=max(res,i+1);
	    }
	    for(int i=0;i<n;i++){
	        if(a[i]<k){
	            int j=lower_bound(b.begin(),b.end(),k-a[i])-b.begin();
	            if(j==m||b[j]!=(k-a[i]))j--;
	            if(a[i]+b[j]<=k){
	                res=max(res,i+1+j+1);
	            }
	        }
	        else break;
	    }
	    for(int i=0;i<m;i++){
	        if(b[i]<k){
	            int j=lower_bound(a.begin(),a.end(),k-b[i])-a.begin();
	            if(j==n||a[j]!=(k-b[i]))j--;
	            if(b[i]+a[j]<=k){
	                res=max(res,i+1+j+1);
	            }
	        }
	        else break;
	    }
	    printf("%d\n",res);
	    //cout<<co<<endl;
}
	   


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

ll MAX_SCORE = 26000;
ll SCORE = 13000;
bool dp[85][85][26000];

ll ind(ll i) {
    return (i >= 0) ? i : MAX_SCORE + i;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("text.txt", "r", stdin);
    ll H, W; cin >> H >> W;
    vector<vector<ll>> SC (H, vector<ll>(W));
    for (ll i = 0; i < H; ++i) {
        for (ll j = 0; j < W; ++j) {
            cin >> SC[i][j];
        }
    }
    for (ll i = 0; i < H; ++i) {
        for (ll j = 0; j < W; ++j) {
            ll x; cin >> x;
            SC[i][j] -= x;
        }
    }
    for (ll i = 0; i <= 80; ++i) {
        for (ll j = 0; j <= 80; ++j) {
            for (ll x = -SCORE; x <= SCORE; ++x) {
                dp[i][j][ind(x)] = false;
            }
        }
    }

    dp[0][0][0] = true;
    for (ll i = 0; i < H; ++i) {
        for (ll j = 0; j < W; ++j) {
            for (ll s = -SCORE; s <= SCORE; ++s) {
                if (!dp[i][j][ind(s)]) continue;

               
                if (i + 1 < H) {
                    dp[i+1][j][ind(s + SC[i][j])] = true;
                    dp[i+1][j][ind(s - SC[i][j])] = true;
                }

                if (j + 1 < W) {
                    dp[i][j+1][ind(s + SC[i][j])] = true;
                    dp[i][j+1][ind(s - SC[i][j])] = true;
                }
            }
        }
    }
    ll best = 2*SCORE;
    for (ll s = 0; s <= SCORE; ++s) {
        if (!dp[H-1][W-1][s]) continue;
        best = min(best, abs(s + SC[H-1][W-1]));
        best = min(best, abs(s - SC[H-1][W-1]));
    }
    cout << best << endl;
}

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

#define ll long long int
#define loop(i,s,e) for(ll i=s; i<e; i++)
#define endl '\n'
#define vll vector<ll>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define N 100001
#define pb push_back
#define INF LLONG_MAX
#define inf INT_MAX
#define minusinf INT_MIN

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

vector<ll> adj[100001];
ll n, m;

ll dp[100001];

ll util(ll i){
	if(adj[i].size()==0) return 0;

	if(dp[i]!=-1) return dp[i];

	ll ans = minusinf;

	loop(j,0,adj[i].size()){
		ans = max(ans, 1+util(adj[i][j]));
	}

	return dp[i] = ans;
}

void alpha(){

	cin>>n>>m;

	memset(dp, -1, sizeof(dp));

	ll u, v;
	loop(i,0,m){
		cin>>u>>v;
		adj[u].pb(v);
	}

	ll ans = minusinf;
	for(ll i=1; i<=n; i++){
		ans = max(ans, util(i));
	}

	cout<<ans<<endl;
	
	return;

}

int main(){

	ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);



    ll t=1;
	//cin>>t;

  	while(t--) alpha();

	return 0;

}

Measured memory_bytes: 8576
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

void display(vector<int> ary) {
  for (int i = 0; i < ary.size(); i++) {
    if (i > 0) cout << " ";
    cout << ary[i];
  }

  cout << endl;
}

void bubble_sort_and_display(vector<int> ary) {
  int count = 0;
  bool flag = true;

  while (flag) {
    flag = false;
    for (int i = ary.size() - 1; i > 0; i--) {
      if (ary[i] < ary[i - 1]) {
        swap(ary[i], ary[i - 1]);
        flag = true;
        count++;
      }
    }
  }

  display(ary);
  cout << count << endl;
}

int main(void) {
  int len;
  vector<int> ary;
  char s[200];

  cin >> len;

  for (int i = 0; i < len; i++) {
    cin >> s;
    ary.push_back(atoi(s));
  }

  bubble_sort_and_display(ary);

  return 0;
}

Measured memory_bytes: 3160
#include <iostream>
#include <vector>
#include <numeric>
#include <cstring>

using namespace std;

vector<int> LINE;

uint64_t count(uint index) noexcept
{
  if (LINE.size() <= ++index)
    return 1;
  else
    return 2 * count(index);
}


uint64_t calc(uint index) noexcept
{
  uint64_t ret = 0;

  for (uint i=index+1; i<=LINE.size(); ++i) {
    ret += count(i) * accumulate(LINE.cbegin() + index, LINE.cbegin() + i, static_cast<uint64_t>(0), [](uint64_t a, uint64_t b) { return 10 * a + b; })\
;
    ret += calc(i);
  }

  return ret;
}


int main()
{
  char line[11];
  cin.getline(line, 11);

  for (uint i=0; i<strlen(line); ++i)
    LINE.push_back(line[i] - '0');

  cout << calc(0) << endl;

  return 0;
}

Measured memory_bytes: 256
def main():
	n = int(input())
	s = int(input())
	ans = solve(n, s)
	print(ans)

def solve(n: int, s: int) -> int:
	if n == s:
		return n+1

	def f(b:int, n:int) -> int:
		if b < 2:
			return -1
		if b > n:
			return n
		cur = n
		ans = 0
		while cur > 0:
			ans += cur%b
			cur //= b
		return ans

	sqrtn = int(n**0.5)
	for i in range(2, sqrtn):
		this_ans = f(i, n)
		if this_ans == s:
			return i

	for p in range(sqrtn+1, 0, -1):
		if (n-s)%p != 0:
			continue
		b = (n-s)//p + 1
		if f(b, n) == s:
			return b
	return -1


if __name__ == '__main__':
	main()

Measured memory_bytes: 3064
import java.util.*;
import java.math.BigDecimal;

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

        final int L = sc.nextInt();
        sc.close();
        double syo = L / 3.0;
        double amari = L - syo * 3.0;
        double V;
        if(amari > 0)
            V = syo * syo * (syo + amari);
        else
            V = syo * syo * syo;

        System.out.println(BigDecimal.valueOf(V).toPlainString());
    }
}

Measured memory_bytes: 20052
N = int(input())
a = map(int, input().split())

four_count = 0
two_count = 0
for i in a:
    if i % 4 == 0:
        four_count += 1
    elif i % 2 == 0:
        two_count += 1

if (N // 2) > four_count:
    tmp = (N // 2) - four_count
    if two_count >= tmp * 2:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
else:
    print("Yes")

Measured memory_bytes: 11096
mod=10**9+7

def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod

n,a,b=map(int,input().split())
all_patterns=modpow(2,n)
a=a if n/2>a else n-a
b=b if n/2>b else n-b
print((all_patterns-conb(n,a)-conb(n,b)-1)%mod)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
set<string>s;
int main(){
	int n;
	cin>>n;
	string a;
	int ans=0;
	for(int i=1;i<=n;i++){
	    cin>>a;
	    if(!s.count(a)){
	       s.insert(a); 
	       ans++;
	    }
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 19128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n % 2 == 0) {
            System.out.println(n);
        } else {
            System.out.println(n * 2);

        }

    }

}


Measured memory_bytes: 22612
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int a = in.nextInt();
        int b = in.nextInt();
        double x = (double) (a+b)/2;
        System.out.println(Math.round( Math.round(x)));
    }
}

Measured memory_bytes: 21844
var h,n : int64;
    a,b : array[1..1010] of int64;
    dp : array[0..10010] of int64;
    i,hi : int64;
    
function max(a,b:int64):int64;
begin
  if a >= b then max := a
  else max := b
end;

function min(a,b:int64):int64;
begin
  if a <= b then min := a
  else min := b
end;

begin
  read(h,n);
  for i := 1 to n do read(a[i],b[i]);
  dp[0] := 0;
  for i := 1 to h do dp[i] := 1000000000000000000;
  for hi := 1 to h do begin
    for i := 1 to n do dp[hi] := min(dp[hi],dp[max(hi-a[i],0)] + b[i])
  end;
  writeln(dp[h])
end.

Measured memory_bytes: 256
#include <iostream>
#include <unordered_set>

using namespace std;

int main(){
    ios::sync_with_stdio(0);

    unordered_set<string> hs;
    int n;
    string last, cur;
    bool ans = 1;

    cin >> n >> last;
    hs.insert(last);

    while( (--n) && ans){
        cin >> cur;
        if( cur.front() != last.back() || hs.find(cur) != hs.end() ) ans = 0;
        hs.insert(cur);
        last = cur;
    }

    if(ans) cout << "Yes";
    else cout << "No";
    cout << '\n';


}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,p;
    cin>>a>>p;
    p+=a*3;
    cout<<p/2<<endl;
}

Measured memory_bytes: 256
s=str(input())
n=len(s)
s=int(s)
if n==1:
  print(s)
elif n==2:
  print(9)
elif n==3:
  print(10+s-100)
elif n==4:
  print(909)
elif n==5:
  print(910+s-10000)
else:
  print(90909)

Measured memory_bytes: 9168
S = input()


def main():
    r = S.count("R")
    if r == 3:
        ans = 3
    elif r == 2 and S[1] == "R":
        ans = 2
    elif r == 0:
        ans = 0
    else:
        ans = 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 8964
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
//#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言

int main()
{
	int n;
	cin >> n;
	int a = 1000;
	while (a < n)
	{
		a += 1000;
	}
	cout << a-n << endl;
}

Measured memory_bytes: 3620
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#define re(c, b) for(ll c=0;c<b;c++)
using namespace std;

int main() {
  int h, w;scanf("%d %d", &h, &w);
  vector<string> s(h);
  for(int i=0;i<h;i++) std::cin >> s[i];
  vector<set<int>> spl(w);
  for(int i=w-1;i>=1;i--){
    int mode = (s[0][i]==s[0][i-1]);
    for(int j=1;j<h;j++){
      if(mode==(s[j][i]==s[j][i-1])) continue;
      mode = (s[j][i]==s[j][i-1]);
      spl[i].insert(j-1);
    }
  }

  vector<int> las(h, -1);
  int ans = 0;
  for(int j=w-1;j>=0;j--){
    int tmp = h;
    map<int, int> L;
    map<int, int> rev; // 長さ、個数
    L.emplace(0, h);
    rev.emplace(h, 1);

    for(int i=1;i+j<w;i++){
      for(auto t:spl[i+j]){
        auto itr = --L.upper_bound(t);
        int x_len = t - (*itr).first + 1;
        int y_len = (*itr).first + (*itr).second - 1 - t;

        auto x = rev.find((*itr).second);
        if((*x).second==1) rev.erase(x);
        else (*x).second--;

        (*itr).second = x_len;
        L.emplace(t+1, y_len);

        x = rev.find(x_len);
        if(x==rev.end()) rev.emplace(x_len, 1);
        else (*x).second++;

        x = rev.find(y_len);
        if(x==rev.end()) rev.emplace(y_len, 1);
        else (*x).second++;
        //rev.insert(x_len);
        //rev.insert(y_len);
      }
      auto itr = (--rev.end());
      tmp = max((*itr).first*(i+1), tmp);
    }
    ans = max(ans, tmp);
    for(auto i:spl[j]){
      if(las[i]!=-1) spl[las[i]].erase(i);
      las[i] = j;
    }
  }
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 133376
package main

import (
	"fmt"
	"sort"
	"strconv"
)

func main() {
	var s string
	var buffer []int

	for {
		if _, err := fmt.Scan(&s); err != nil {
			break
		}

		i, err := strconv.Atoi(s)
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, i)
	}

	sort.Ints(buffer)

	var c int
	i := len(buffer) - 1
	for j := len(buffer) - 2; j != -1; j-- {
		c += (buffer[i] - buffer[j])
		i = j
	}

	fmt.Println(c)
}


Measured memory_bytes: 512
import sys
from io import StringIO
import unittest


def factorization(n):
    if n == 1:
        return {}
    d = {}
    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
            d[i] = cnt

    if temp != 1:
        d[temp] = 1

    if d == {}:
        d[n] = 1

    return d


def resolve():
    A, B = map(int, input().split())
    A_f = factorization(A)
    B_f = factorization(B)

    d = {}
    for key_A, value_A in A_f.items():
        if key_A not in B_f:
            continue
        d[key_A] = max(value_A, B_f[key_A])

    print(len(d.keys()) + 1)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 50028
N,M = map(int,input().split())

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

MOD = 10**9+7

MAX = 2*10**5

fac = [1,1] + [0]*MAX
finv = [1,1] + [0]*MAX
inv = [0,1] + [0]*MAX
for i in range(2,MAX+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD
def nhr(n,r):
    return ncr(n+r-1, r)


factors = factorize(M)
ans = 1
for v in factors.values():
    ans *= nhr(N,v)
    ans %= MOD
print(ans)


Measured memory_bytes: 28624
#include<bits/stdc++.h>
#define fastio 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
typedef long long int ll;

int n, k;
int dp[2][100005];
bool find(bool curr, int arr[], int rem) {
	if (rem < 0)
		return curr;
	if (dp[curr][rem] != -1)
		return dp[curr][rem];
	bool ok = false;
	for (int j = 0; j < n; j++) {
		bool flag = find(!curr, arr, rem - arr[j]);
		if (flag == curr)
			ok = true;
	}
	if (ok)
		return dp[curr][rem] = curr;
	return dp[curr][rem] = !curr;
}


int main() {
	fastio;

	cin >> n >> k;
	memset(dp, -1, sizeof dp);
	int arr[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	if (find(true, arr, k))
		cout << "First";
	else
		cout << "Second";
	return 0;
}

Measured memory_bytes: 13648
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N-1):
        for j in range(i+1, N):
            if S[i] == S[j]:
                dp[i+1][j+1] = min(dp[i][j] + 1, j-i)
    print( max( [ max(dp[i]) for i in range(N+1)]))
if __name__ == '__main__':
    main()


Measured memory_bytes: 230024
function Main(input){
	input = input.split(" ").map((a)=>~~a);
  return input[0]/input[1];
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
8 3
`);

Measured memory_bytes: 21064
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
	string s;
	cin>>s;
	string ans;
	if(s[0]==s[1] || s[1]==s[2] || s[2]==s[3])
		ans="Bad";
	else
		ans="Good";
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
N,M,K = map(int, input().split())

mod = 10**9+7
a = 1
b = 1
for i in range(min(K-2, N*M-K)):
    a *= (N*M-2-i)
    a %= mod
    b *= i+1
    b %= mod
comb = a * pow(b, mod - 2, mod) % mod

ans = (((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)*comb)%mod
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int r,c,k;
ll dp[3005][3005][4];
ll fie[3005][3005];

int main(void){
	scanf("%d%d%d",&r,&c,&k);
	for(int i=0;i<k;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		a--;
		b--;
		fie[a][b]=c;
	}
	dp[0][0][0]=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			for(int k=0;k<=3;k++){
				dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k]);
				dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
				if(k<3){
					dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k]+fie[i][j]);
					dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+fie[i][j]);
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=3;i++){
		ans=max(ans,dp[r-1][c-1][i]);
		if(i<3){
			ans=max(ans,dp[r-1][c-1][i]+fie[r-1][c-1]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 355996