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


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m,currentSPosition=0;
	ll fullLoops=0;
	string s,t,alpha="abcdefghijklmnopqrstuvwxyz";
	cin>>s;
	cin>>t;
	n=s.length();
	m=t.length();
	map<int,map<char,int>> future;
	map<char,int> nextOccurence;
	for (int i=0;i<26;++i)
	{
		nextOccurence[alpha[i]]=-1;
	}
	future[n]=nextOccurence;
	for (int i=n;i>0;--i)
	{
		nextOccurence[s[i-1]]=i;
		future[i-1]=nextOccurence;
	}
	for (int i=0;i<m;++i)
	{
		if (future[currentSPosition][t[i]]==-1)
		{
			//cout<<"NEWLOOP at i="<<i<<"\n";
			++fullLoops;
			if (future[0][t[i]]==-1)
			{
				cout<<-1;
				return 0;
			}
			currentSPosition=future[0][t[i]];
		}
		else
		{
			currentSPosition=future[currentSPosition][t[i]];
		}
		//cout<<"currentSPosition = "<<currentSPosition<<"\n";
	}
	//cout<<fullLoops<<" "<<currentSPosition<<"\n";
	fullLoops*=n;
	fullLoops+=currentSPosition;
	cout<<fullLoops;
	return 0;
}

Measured memory_bytes: 133712
/*
    Author: zxy_hhhh
    date: 2020/03/13
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<iostream>
#define ll long long
inline ll rd() {
    ll _x=0;int _ch=getchar(),_f=1;
    for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
    if (_ch=='-'){_f=0;_ch=getchar();}
    for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
    return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 100005
int n,Q,top;
ll a[maxn],sta[maxn],f[maxn],d[maxn];
int main() {
    n=rd(),Q=rd();
    sta[top=1]=n;
    for(int i=1;i<=Q;i++) {
        a[i]=rd();
        while(top&&a[i]<=sta[top])
            top--;
        sta[++top]=a[i];
    }
    f[top]=1;
    for(int i=top;i>=2;i--) {
        ll x=sta[i]%sta[i-1];
        f[i-1]+=f[i]*(sta[i]/sta[i-1]);
        while(1) {
            int R=std::upper_bound(sta+1,sta+i,x)-sta;
            R--;
            if (R>0) {
                f[R]+=f[i]*(x/sta[R]);x%=sta[R];
            }
            else {
                d[1]+=f[i],d[x+1]-=f[i];
                break;
            }
        }
    }
    for(int i=1;i<=n;i++) {
        d[i]+=d[i-1];
    }
    for(int i=1;i<=n;i++) {
        wrt(d[i]+f[1]*(i<=sta[1]),'\n');
    }
}

Measured memory_bytes: 4864
#include<cstdio>

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

using namespace std;

typedef long long ll;

const ll INF=1LL<<61;

const int N_MAX=4000;

template<class T>
T optimal_BST(int n,const T *w){
	T w_sum[N_MAX+1];
	w_sum[0]=0;
	rep(i,n) w_sum[i+1]=w_sum[i]+w[i];

	static T dp[N_MAX][N_MAX];
	static int argmin[N_MAX][N_MAX];
	rep(i,n){
		argmin[i][i]=i;
		rep(j,n) dp[i][j]=(i==j?0:INF);
	}

	for(int t=1;t<n;t++){
		for(int i=0,j=t;j<n;i++,j++){
			for(int k=argmin[i][j-1];k<=argmin[i+1][j];k++){
				if(k+1>=n) break;
				T cost=dp[i][k]+dp[k+1][j]+w_sum[j+1]-w_sum[i];
				if(dp[i][j]>=cost){
					dp[i][j]=cost;
					argmin[i][j]=k;
				}
			}
		}
	}
	return dp[0][n-1];
}

int main(){
	int n; scanf("%d\n",&n);
	ll w[4000];
	rep(i,n) scanf("%lld",w+i);

	printf("%lld\n",optimal_BST(n,w));

	return 0;
}

Measured memory_bytes: 188584
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

bool isPal(string s){
  F0R(i,s.length()/2){
    if(s[i] != s[s.length()-i-1])
      return false;
  }
  return true;
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;
    ll n,m;
    cin >> n >> m;
    if(n == 1 && m == 1) cout << 1;
    else if(n == 1 || m == 1) cout << n+m-3;
    else cout << (n-2)*(m-2);
    cout << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=100010;

vector<ll> ar;
ll k;
ll dp[N];
ll func(ll idx)
{
    if(idx<0){return INT_MAX;}
    if(idx==0){return 0;}
    if(dp[idx]==-1)
    {
        ll ans=INT_MAX;
        for(ll i=1;i<=k;++i)
        {
            if(idx-i>=0)
            {ans=min(ans,func(idx-i)+abs(ar[idx]-ar[idx-i]));}
        }
        dp[idx]=ans;
    }
    return dp[idx];
}

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

    ll n;
    cin>>n>>k;
    for(ll i=0;i<n;++i)
    {
        ll x;
        cin>>x;
        ar.pb(x);
        dp[i]=-1;
    }

    ll ans=func(n-1);

    cout<<ans<<endl;

    return (0);
}


Measured memory_bytes: 8180
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int n; cin >> n;
    for (ll a = 1; a <= 3500; a++) {
        for (ll b = 1; b <= 3500; b++) {
            ll x = 4 * a * b - n * (a + b);
            ll y = n * a * b;
            if (x == 0) continue;
            if (y % x == 0) {
                ll c = y / x;
                if (1 <= c && c <= 3500) {
                    printf("%lld %lld %lld\n", a, b, c);
                    return 0;
                }
            }
        }
    }
}


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

using ll = long long;
const int mod = 1e9+7;
const int N = 2e6+23;

int f[N];

int binpow(long long b, long long e) {
  if (!e) return 1;
  if (e&1) return b*binpow(b, e-1)%mod;
  return binpow(b*b%mod, e/2);
}
int C(int n, int k) {
  if(n - k < 0){
    cout << 0;
    exit(0);
  }
  return 1LL * f[n] * binpow(f[k], mod-2) % mod * binpow(f[n-k], mod-2) % mod;
}

int main() {

  ll x, y;
  cin >> x >> y;
  f[0] = 1;
  for (int i = 1; i <= 1000001; ++i) {
    f[i] = 1LL * f[i-1] * i % mod;
  }
  if(2 * x - y < 0) cout << "0";
  else if((x + y) % 3 != 0)cout << "0";
  else cout << C((x + y) / 3, (2 * x - y ) / 3);

  return 0;
}


Measured memory_bytes: 7496
#include <iostream>
//#include <numeric>
#include <vector>
	#include<math.h>
	//#include <algorithm>
	//#include <functional>
	#include <numeric>
	//#include<cmath>
//#include <stdio.h> 
#include <cstdint>
	#include <string>
	//#include <cstdlib>
	//#define pi 3.14159265359
#include <iomanip>
using namespace std;


int main() {

	double num = 0;
	double max_num = 0;
	double k, n;
	cin >> n >> k;
	vector<double> b(n);
	//vector<float> c(k);
	double m;
	for (uint64_t i = 0; i < n; i++) {
		cin >> m;
		if (m != 1) {
			m = (m + 1) / 2;
			//cout << m << endl;
		}

		b[i] = m;
		num += m;
		if (num > max_num) {
			max_num = num;
		}

		if (i>= k - 1) {
			num -= b[i - k + 1];
		}
	}

	cout << fixed << setprecision(2) << max_num;

	return 0;

}


Measured memory_bytes: 1920
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
    int n, m;
    int pena = 0;
    int corr = 0;
    int al[100010] = {};
    int wa[100010] = {};

    cin >> n >> m;

    vector<pair<int, string>> ans;

    for (int i = 0; i < m; i++) {
        int num;
        string s;
        cin >> num >> s;
        ans.push_back(make_pair(num, s));
    }

    for (int i = 0; i < m; i++) {
       if (ans[i].second == "WA") {
           if (al[ans[i].first] == 0) {
               wa[ans[i].first]++;
           }
       }
       else {
           if (al[ans[i].first] == 0) {
               corr++;
               pena += wa[ans[i].first];
               al[ans[i].first] = 1;
           }
       }
    }

    cout << corr << " " << pena << endl;

}


Measured memory_bytes: 7280
S = input()
q = int(input())

for i in range(q):
	L = input().split()
	a = int(L[1])
	b = int(L[2])
	slice1 = S[:a]
	slice2 = S[a:b+1]
	slice3 = S[b+1:]
	if L[0] == 'print':
		print(slice2)
	elif L[0] == 'reverse':
		S = slice1 + slice2[::-1] + slice3
	elif L[0] == 'replace':
		S = slice1 + L[3] + slice3

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

int main() {
  int a, b;
  cin >> a >> b;
  if(a + b == 15) cout << "+" << endl;
  else if(a * b == 15) cout << "*" << endl;
  else cout << "x" << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N;
	cin >> N;
	string S;
	cin >> S;
	int x = 0, ans = 0;
	for (int i = 0; i < N; i++) {
		if (S.at(i) == 'I') x++;
		else x--;
		if (ans < x) ans = x;
	}
	cout << ans << endl;
}

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

const int limit = 100010;
using edge = struct {int to; ll cost; };
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d) {
    depth[v] = d;
    for(auto &e : tree[v]) {
        if(e.to == p) continue;
        dfs(e.to, v, d + e.cost);
    }
}

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

    for(int i = 0; i < N-1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }

    int Q, K;
    cin >> Q >> K;
    K--;

    dfs(K, -1, 0);
    for(int i = 0; i < Q; ++i){
        int x, y;
        cin >> x >> y;
        x--, y--;
        cout << depth[x] + depth[y] << endl;
    }

    return 0;
}

Measured memory_bytes: 14336
import java.util.*;


public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a + w <= b)System.out.println(b - (a + w));
        else if(b + w <= a) System.out.println(a - (b + w));
        else System.out.println(0);
    }
}


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

int main(){

  /*******************************
    writer Torisuto 2020/6/1
    A×Bの小数点切り捨てを出力せよ
    0 <= A <= 10^15
    0 <= B < 10（Bは小数第二位まで）
  ********************************/

  /*******************************
    long doubleを使うことに注意
    切り捨て方はlongに再代入すると良い
    (long)A*Bだとうまく行かない
  ********************************/

  long a;
  long double b;
  cin >> a >> b;
  a = a*b;  // 再代入
  cout << a << endl;
  return 0;
}


Measured memory_bytes: 3732
#include <iostream>
using namespace std;
typedef long long ll;
ll a[100003],r[100003];
ll ans=0,mx=0;
const ll md=998244353;
ll pw(ll x,ll n)
{
	if (x==0) return 0;
	if (n==0) return 1;
	ll q=pw(x,n/2);
	if (n%2==0) return q*q%md;
	else return q*q%md*x%md;
}
int main()
{
	int x;
	cin>>x;
	for (int i=1;i<=x;i++){
		cin>>a[i];
		r[a[i]]++;
		mx=max(mx,a[i]);
	}
	if (a[1]!=0||r[0]>1) ans=0;
	else
	{
		ans=1;
		for (int i=2;i<=mx;i++)
		{
			ans=ans*pw(r[i-1],r[i])%md;
		}
	}
	cout<<ans<<endl;
} 

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<string>
#include<climits>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<queue>
#include<math.h>

int main(){
	long long n;
	std::cin>>n;

	long long sqN= sqrtl(n);

	long long x1;
	long long y2;

	long long delta;

	if(sqN*sqN==n){
		x1= sqN;
		y2= sqN;

		delta= 0;
	}
	else if(sqN*(sqN+1)>=n){
		x1= sqN;
		y2= sqN+1;

		delta= sqN*(sqN+1)-n;
	}else{
		x1= sqN+1;
		y2= sqN+1;

		delta= (sqN+1)*(sqN+1)-n;
	}

	std::cout<<"0 0 ";
	std::cout<<x1<<" "<<delta<<" ";
	std::cout<<"1"<<" "<<y2<<std::endl;

	return 0;
	
}

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

using namespace std;

const int inf = (int)1e17;


void solve(){
    int n, c;
    cin >> n >> c;
    vector < int > x(n);
    vector < int > v(n);
    for(int i = 0; i < n; ++i){
        cin >> x[i] >> v[i];
    }
    int ans = 0;
    if(n == 1){
        ans = max(ans, v[0] - x[0]);
        ans = max(ans, v[0] - (c - x[0]));
        cout << ans << "\n";
        return;
    }
    vector < int > a(n);
    vector < int > ra(n);
    a[0] = -x[0] + v[0];
    for(int i = 1; i < n; ++i){
        a[i] = a[i - 1] - (x[i] - x[i - 1]) + v[i];
    }
    ra[0] = -(c - x[ra.size() - 1]) + v[ra.size() - 1];
    for(int i = 1; i < n; ++i){
        ra[i] = ra[i - 1] - (x[ra.size() - i] - x[ra.size() - 1 - i]) + v[ra.size() - 1 - i];
    }
    vector < int > pa(n);
    vector < int > pra(n);
    pa[0] = a[0];
    for(int i = 1; i < n; ++i){
        pa[i] = max(pa[i - 1], a[i]);
    }
    pra[0] = ra[0];
    for(int i = 1; i < n; ++i){
        pra[i] = max(pra[i - 1], ra[i]);
    }
//    cerr << "HERE\n";
//    for(int i = 0; i < a.size(); ++i){
//        cerr << a[i] << " ";
//    }
//    cerr << "\n";
//    for(int i = 0; i < ra.size(); ++i){
//        cerr << ra[i] << " ";
//    }
//    cerr << "\n";
//    for(int i = 0; i < n; ++i){
//        cerr << pa[i] << " ";
//    }
//    cerr << "\n";
//    for(int i = 0; i < pra.size(); ++i){
//        cerr << pra[i] << " ";
//    }
//    cerr << "\n";
//    cerr << "HERE\n";
    for(int i = 0; i < n; ++i){
        ans = max(ans, max(a[i], ra[i]));
        ans = max(ans, a[i] - x[i] + ((n - i - 2 >= 0) ? pra[n - i - 2] : -inf));
        //cerr << i << " " << a[i] << " " << x[i] << " " << ((n - i - 2 >= 0) ? pra[n - i - 2] : -inf) << "\n";
        ans = max(ans, ra[i] - (c - x[ra.size() - i - 1]) + ((n - i - 2 >= 0) ? pa[n - i - 2] : -inf));
    }
    cout << ans << "\n";

}



signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        cin >> t;
    #endif
    for(int i = 0; i < t; ++i){
        solve();
    }
}


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

int main() {
    int n, a[3][3], check[3][3] = {0};
    rep(i, 3) rep(j, 3) cin >> a[i][j];
    cin >> n;
    int b[n];
    rep(i, n) cin >> b[i];
    rep(i, n) {
        rep(j, 3) {
            rep(k, 3) {
                if(a[j][k] == b[i]) {
                    check[j][k] = 1;
                }
            }
        }
    }

    bool flag = false;
    rep(i, 3) {
        if(check[i][0] == 1 and check[i][1] == 1 and check[i][2] == 1) {
            flag = true;
        } else if(check[0][i] == 1 and check[1][i] == 1 and check[2][i] == 1) {
            flag = true;
        }
    }
    if(check[0][0] == 1 and check[1][1] == 1 and check[2][2] == 1) {
        flag = true;
    } else if(check[2][0] == 1 and check[1][1] == 1 and check[0][2] == 1) {
        flag = true;
    }
    if(flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstdio>
#include<cstring>
#define _A_ true
#define _3_ true
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

int main(){
  int a,b,rem;
  int persons[60];
  while(_A_){
    scanf("%d %d",&a,&b);
    if(!(a|b))break;
    rep(i,60)persons[i] = 0;
    int Index=0;
    rem = b;
    while(_3_){
      if(Index%a == 0)Index = 0; 
 
      if(rem == 1 && persons[Index]+1 == b){
	cout << Index << endl;
	break;
      }
      else if(rem != 0){
	persons[Index]++;
	rem--;
	Index++;
      }
      else if(rem == 0){
	rem=persons[Index];
	persons[Index] = 0;
	Index++;
      }    
    }
  }
  return 0;
}

Measured memory_bytes: 888
<?php
$fl=array();
for($i=0;$i<4;$i++){
  $fl[$i]=array();
  for($j=0;$j<3;$j++){
    $fl[$i][$j]=array();
    for($k=0;$k<10;$k++)$fl[$i][$j][$k]=0;
  }
}

$n=trim(fgets(STDIN));

for($i=0;$i<$n;$i++){
  list($b,$f,$r,$v)=explode(' ',trim(fgets(STDIN)));
  $fl[$b-1][$f-1][$r-1]+=$v;
}

$o='';
$sp='';for($i=0;$i<20;$i++){$sp.='#';}
for($i=0;$i<4;$i++){
  for($j=0;$j<3;$j++){
    for($k=0;$k<10;$k++)$o.=' '.$fl[$i][$j][$k];
    $o.=PHP_EOL;
  }
  if($i<3){$o.=$sp.PHP_EOL;}
}
print $o;

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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7



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

	K--;
	switch (S[K]) {
	case 'A':S[K] = 'a'; break;
	case 'B':S[K] = 'b'; break;
	case 'C':S[K] = 'c'; break;
	}
	cout << S << endl;
	return 0;
}


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

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

  if (h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }

  if (h > w) swap(h, w);

  ll ans = 1001001001;

  for (int i = 1; i <= w - 1; i++) {
    ll sq1 = (ll) i * h;
    ll sq2, sq3;
    if (h % 2 == 0 || (w - i) % 2 == 0) {
      sq2 = (ll) h * (w - i) / 2;
      sq3 = (ll) h * (w - i) / 2;
      ans = min(ans, abs(sq1 - sq2));
    }
    else {
      ll nowH = h;
      ll nowW = w - i;
      if (nowH > nowW) swap(nowW, nowH);
      sq2 = (ll) nowH * (nowW / 2);
      sq3 = (ll) nowH * (nowW / 2 + 1);
      ans = min(ans, max({sq1, sq2, sq3}) - min({sq1, sq2, sq3}));
    }
  }

  for (int i = 1; i <= h - 1; i++) {
    ll sq1 = (ll) i * w;
    ll sq2, sq3;
    if ((h - i) % 2 == 0 || w % 2 == 0) {
      sq2 = (ll) w * (h - i) / 2;
      ans = min(ans, abs(sq1 - sq2));
    }
    else {
      ll nowH = h - i;
      ll nowW = w;
      if (nowH > nowW) swap(nowW, nowH);
      sq2 = (ll) nowH * (nowW / 2);
      sq3 = (ll) nowH * (nowW / 2 + 1);
      ans = min(ans, max({sq1, sq2, sq3}) - min({sq1, sq2, sq3}));
    }
  }

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


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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
using intmap = map<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
inline bool bit (ll b, ll i) { return b & (1 << i); }
inline ll ceiv (ll a, ll b) { return (a + b - 1) / b; }
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define debug(x) cerr << #x << ": " << x << '\n'
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()

signed main(){
    int l, r, d;
    cin >> l >> r >> d;
    int a = 0;
    reps(i,l,r){
        if(i % d == 0) a++;
    }
    
    cout << a << endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<pint> vpint;
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for (int i=(n)-1;i>=0;i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define REPS(i,f,n) for (int i=(f)-1;i>=(n);i--)
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
 
void slove(int n, int r){//n ?????° r?????????????????°?°
    stack<int> s;
    reps(i, 1, n + 1) s.push(i);//?????????
 
    rep(i, r){//r????????????
        int p, c;
        cin >> p >> c;
        stack<int> tmp1;
        stack<int> tmp2;

        rep(i, p - 1){
            tmp1.push(s.top());
            s.pop();
        }
        rep(i, c){
            tmp2.push(s.top());
            s.pop();
        }

        rep(i, p - 1){
            s.push(tmp1.top());
            tmp1.pop();
        }
        rep(i, c){
            s.push(tmp2.top());
            tmp2.pop();
        }
    }
 
    printf("%d\n", s.top());
    return;
}
 
int main(void){
    int n, r;
    cin >> n >> r;
    while(n != 0 || r != 0){
        slove(n, r);
        cin >> n >> r;
    }
    return 0;
}

Measured memory_bytes: 3044
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void){
  int a[31];
  REP(i,31){
    a[i]=0;
  }
  int n,m;
  cin>>n>>m;
  REP(i, n){
    int k;
    cin>>k;
    REP(j, k){
      int v;
      cin>>v;
      a[v]++;
    }
  }
  int ans=0;
  REP(i,m+1){
    if(a[i]==n)ans++;
  }
  cout<<ans<<endl;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, K;
	cin >> n >>K;
	
	if(K %2 ==1){puts("0"); return 0;}
	K/=2;
	const int BMX=K+5;
	vector<VL> dp(n+2, VL(BMX+3));
	dp[0][0] = 1;
	rep(i, n){
		vector<VL> np(n+2, VL(BMX+3));
		rep(j, i+1) rep(k, BMX){
			if(k+j < BMX){
				np[j][k+j] += dp[j][k]  *j;
				np[j][k+j] += dp[j][k];
				np[j][k+j] += dp[j][k] *j;
				np[j][k+j] %=MD;
				(np[j+1][k+j] += dp[j][k]) %=MD;
				if(j) (np[j-1][k+j] += dp[j][k] *j *j) %=MD;
			}
		}
		swap(dp, np);
	}
	//for(auto x :dp[0]) printf("%lld ",x); puts("");
	cout << dp[0][K] << endl; 
	return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;

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

	int x = scan.nextInt();
	int t = scan.nextInt();

	if(x - t >= 0){
	    System.out.println(x-t);
	}else{
	    System.out.println(0);
	}
    }
}


Measured memory_bytes: 20948
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
#define ll long long
#define vel vector<ll>
#define vvel vector<vel>
#define vvvel vector<vvel>
#define veb vector<bool>
#define pin pair<ll,ll>
#define mkp make_pair
#define mot pair<D,D>//time,dist
#define path pair<ll,int>//cost,to
#define int long long
using namespace std;
vvel ta_min(0);
vvel ta_max(0);
int leth = 1024 * 512;
int p = 1000000007;
vel par;
vel dis;
int n;
void mmax(ll &a, ll b) { a = max(a, b); }
void mmin(ll &a, ll b) { a = min(a, b); }
pin root(int ser) {
	if (par[ser] == -1) {return mkp(ser,0);}
	pin x=root(par[ser]);
	x.second += dis[ser];
	par[ser] = x.first;
	dis[ser] = x.second;
	return x;
}
void uni(int a, int b,int d) {
	pin p1 = root(a);
	pin p2 = root(b);
	int a1 = p1.first;
	int b1 = p2.first;
	if (a1 != b1) {
		par[b1] = a1;
		dis[b1] = d + dis[a] - dis[b];
	}
}
bool issame(int x, int y) {
	return root(x).first == root(y).first;
}
void ref(int &x) { x = x % p; x = (x + p) % p; }
signed main() {
	cin >> n; int m; cin >> m;
	par = vel(n, -1);
	dis = vel(n,0);
	for (int i = 0; i < m; i++) {
		int l, r; cin >> l >> r; l--; r--;
		int d; cin >> d;
		pin l1=root(l);
		pin r1= root(r);
		if (l1.first != r1.first ) { uni(r, l, d); }
		else {
			if (dis[r] + d == dis[l]) { uni(r, l, d); }
			else { cout << "No" << endl; return 0; }
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

int main(){

  int k;
  cin>>k;
  ll a,b=0;
  cin>>a>>b;
	

  for(int i=a;i<b+1;i++){

    if(i%k==0){cout<<"OK"<<endl;return 0;}

  }
  
  cout<<"NG"<<endl;

}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

const LL INF = 0x3f3f3f3f3f3f3f3f;
template<const int maxN, const int maxM>
struct MCMF {
	int n, m, s, t;
	struct Edge {
		int from, to, last;
		LL flow, cap, cost;
		Edge() {}
		Edge(int f, int t, int l, LL fl, LL cp, LL cst) :
			from(f), to(t), last(l), flow(fl), cap(cp), cost(cst) {}
	} edges[maxM << 1]; int h[maxN];
	void init(int n) {
		this->n = n;
		m = 1;
	}
	void link(int x, int y, int f, int c) {
		edges[++m] = Edge(x, y, h[x], 0, f, c); h[x] = m;
		edges[++m] = Edge(y, x, h[y], 0, 0, -c); h[y] = m;
	}
	bool inq[maxN];
	LL d[maxN], a[maxN];
	int p[maxN];
	LL augument(int s, int t) {
		memset(inq, 0, sizeof(inq));
		memset(a, 0, sizeof(a));
		memset(d, ~INF, sizeof(d));
		d[s] = 0; a[s] = INF;
		queue<int> Q; Q.push(s); inq[s] = true;
		while(Q.size()) {
			int u = Q.front(); Q.pop(); inq[u] = false;
			for(int i = h[u]; i; i = edges[i].last) {
				const Edge &e = edges[i];
				if(e.cap > e.flow && chmax(d[e.to], d[u] + e.cost)) {
					a[e.to] = min(a[u], e.cap - e.flow);
					p[e.to] = i;
					if(!inq[e.to]) Q.push(e.to), inq[e.to] = true;
				}
			}
		}
		if(a[t] == 0) return 0;
		int u = t;
		while(u != s) {
			edges[p[u]].flow += a[t];
			edges[p[u] ^ 1].flow -= a[t];
			u = edges[p[u]].from;
		}
		return a[t] * d[t];
	}
	LL solve(int s, int t) {
		this->s = s; this->t = t;
		LL ans = 0, dans;
		while((dans = augument(s, t))) ans += dans;
		return ans;
	}
};
const int maxN = 1000 + 5;
int n;
MCMF<maxN * 2, maxN * 10> sol;

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	sol.init(2 * n + 6);
	int S = 2 * n + 5, T = 2 * n + 6;
	for(int i = 1; i <= n; ++i) {
		int x, y, c; cin >> x >> y >> c;
		sol.link(S, i, c, 0);
		sol.link(i, 2 * n + 1, c,   x + y);
		sol.link(i, 2 * n + 2, c,   x - y);
		sol.link(i, 2 * n + 3, c, - x + y);
		sol.link(i, 2 * n + 4, c, - x - y);
	}
	for(int i = 1; i <= n; ++i) {
		int x, y, c; cin >> x >> y >> c;
		sol.link(n + i, T, c, 0);
		sol.link(2 * n + 1, n + i, c, - x - y);
		sol.link(2 * n + 2, n + i, c, - x + y);
		sol.link(2 * n + 3, n + i, c,   x - y);
		sol.link(2 * n + 4, n + i, c,   x + y);
	}
	cout << sol.solve(S, T) << endl;
	return 0;
}


Measured memory_bytes: 1280
#include <iostream>

using namespace std;
using ll = long long;

int count_digits(ll n) {
    int digits = 0;
    while (n > 0) {
        n /= 10;
        digits++;
    }

    return digits;
}

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

    int min = count_digits(n);
    for (ll a = 1; a * a <= n; a++) {
        if (n % a != 0)
            continue;
        ll b = n / a;
        int cur = max(count_digits(a), count_digits(b));
        
        if (min > cur)
            min = cur;
    }

    cout << min << endl;

    return 0;
}

Measured memory_bytes: 256
k=int(input())
l=[1,2,3,4,5,6,7,8,9]
for i in range(10**5+1):
  if len(l)>=k:
    break
  di=l[i]%10
  for j in range(max(0,di-1),min(9,di+1)+1):
    l.append(l[i]*10+j)
print(l[k-1])


Measured memory_bytes: 46708
#include<bits/stdc++.h>
using namespace std;
int n, m, a[101], sum, temp, i, c;
int main()
{
    cin >> n >> m;
    for(i=0;i<n;i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a+n);
    temp = sum /(4*m) + (sum%(4*m)>0);
    for(i=0;i<n;i++)
    {
        if(a[i]>=temp)
            c++;
    }
    if(c>=m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


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

using namespace std;

int main  ()
{

int N;
int A;
int B;

cin >> N;
cin >> A;
cin >> B;


if(N*A > B)
{
cout<< B <<endl;
}

else
{
 cout<< N*A <<endl;
}

return 0;

}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int i,j,k,a,b,q;
	int right,pips[6],ans[24];

	for(i = 0;i < 6;i++){
		scanf("%d",&pips[i]);
	}
        scanf("%d",&q);
	for(j = 0;j < q;j++){
		scanf("%d %d",&a,&b);
		if(a == pips[0]){
			if(b == pips[1])right = pips[2];
			if(b == pips[2])right = pips[4];
			if(b == pips[3])right = pips[1];
			if(b == pips[4])right = pips[3];
		}
		if(a == pips[1]){
			if(b == pips[0])right = pips[3];
			if(b == pips[2])right = pips[0];
			if(b == pips[3])right = pips[5];
			if(b == pips[5])right = pips[2];
		}
		if(a == pips[2]){
			if(b == pips[0])right = pips[1];
			if(b == pips[1])right = pips[5];
			if(b == pips[4])right = pips[0]; 
			if(b == pips[5])right = pips[4];		
		}
		if(a == pips[3]){
			if(b == pips[0])right = pips[4];
			if(b == pips[1])right = pips[0];	      
			if(b == pips[4])right = pips[5];
			if(b == pips[5])right = pips[1];       		
		}
		if(a == pips[4]){
			if(b == pips[0])right = pips[2];
			if(b == pips[2])right = pips[5];
		       	if(b == pips[3])right = pips[0];
			if(b == pips[5])right = pips[3];       	
		}
		if(a == pips[5]){
			if(b == pips[1])right = pips[3];
			if(b == pips[2])right = pips[1];       
			if(b == pips[3])right = pips[4];       
			if(b == pips[4])right = pips[2];      		
		}
		ans[j] = right;
	}
	for(j = 0;j < q;j++){
		printf("%d\n",ans[j]);
	}
	return 0;
}

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

    int main()
    {
        int a, b;
        scanf("%d%d",&a,&b);
        string aa[a];
        for(int i=0;i<a;i++)
        {
            cin >> aa[i];
        }
        for(int i=0;i<a;i++)
        {
            cout << aa[i] << "\n" << aa[i] << endl;
        }
        return 0;
    }


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, p = map(int, input().split())
    s = list(input())
    if 10 % p == 0:
        ans = 0
        for i in range(n):
            if (ord(s[i])-ord('0')) % p == 0:
                ans += i+1
        print(ans)
        return

    d = [0] * (n+1)
    ten = 1
    for i in reversed(range(n)):
        a = (ord(s[i])-ord('0')) * ten % p
        d[i] = (d[i+1]+a) % p
        ten *= 10
        ten %= p

    cnt = [0] * p
    ans = 0
    for i in reversed(range(n+1)):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
    print(ans)


main()


Measured memory_bytes: 62832
#include <stdio.h>

int main(){

  int k,s,i,j,l,count=0;

  scanf("%d %d",&k,&s);

  for(i=0;i<=k;i++){
    for(j=0;j<=k;j++){
      if(i+j>s) break;
      l=s-i-j;
      if(l<=k) count++;
    }
  }
  printf("%d\n",count);
  return 0;
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

int main() {
  ll n;
  cin >> n;
  cout << (n - 1) * n / 2 << endl;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {
            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }


        public static long gcd(long x, long y)
        {
            if (y < x) gcd(y, x);
            while (y != 0)
            {
                var z = x % y;
                x = y;
                y = z;
            }
            return x;
        }
        public static long keta(long x)
        {
            var z = 1;
            while (x > 0)
            {
                x /= 10;
                z++;
            }
            return z;
        }
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var  n = Read();
            long t = 0, x = 0, y = 0;
            long bt = 0, bx = 0, by = 0;
            bool ans = true;
            for (int i = 0; i < n; i++)
            {
                var txy = Reads();
                t = txy[0];
                x = txy[1];
                y = txy[2];
                bool f = Math.Abs(x - bx) + Math.Abs(y - by) <= t - bt && (Math.Abs(x - bx) + Math.Abs(y - by)) % 2 == (t - bt) % 2;
                if (!f) ans = false;
                bt = t;
                bx = x;
                by = y;
            }
            WriteLine(ans ? "Yes" : "No");
            

            Console.Out.Flush();
        }
    }
}



Measured memory_bytes: 23084
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

"""
まず、前処理として、「Bの祭壇から大きさb以下のパーツを使うとき、Aの祭壇のパーツとの組み合わせはいくつあるか」というのを調べてメモしておく。
次に、Cの祭壇の大きさがcのとき、という風に場合わけして、選べるBの祭壇の大きさを絞って、A,B,Cの組み合わせの数を加算していく。
"""


tmpSum = 0
dicB = {}
for i in range(N):
    b = B[i]
    if b not in dicB:
        dicB[b] = tmpSum
    idx = bisect_left(A,b)
    dicB[b] += idx
    tmpSum += idx

ans = 0
for i in range(N):
    c = C[i]
    idx = bisect_left(B,c)
    if idx != 0:
        b = B[idx-1]
        ans += dicB[b]

print(ans)


Measured memory_bytes: 111084
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#include<vector>
#include<algorithm>
#include<string>
typedef long long ll;
using namespace std;

int main(void) {
	string n;
	cin >> n;
	cout << "ABC" + n << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

#define MAX 2000

int combi(int,int);
int n,A[MAX],q,M[MAX];

int main(void){
  int i;

  scanf("%d", &n);
  for(i=0;i<n;i++) scanf("%d", &A[i]);

  scanf("%d", &q);
  for(i=0;i<q;i++) scanf("%d", &M[i]);

  for(i=0;i<q;i++){
    if(combi(0,M[i])) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}

int combi(int m,int i){
  int x;
  if(i==0) return 1;
  if(n<=m) return 0;
  x= combi(m+1,i) || combi(m+1,i-A[m]);
  return x;
}

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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

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

int main(){
	
	ll n,q,p;cin >> n >> p >> q;
	vector<ll> v;
	ll sum = 0;
	REP(i,n){
		ll c;cin >> c;
		sum += c;
		v.PB(- c + (q - i) * p);
	}
	
	sort(ALL(v),greater<ll>());
	
	ll ans = sum;
		
	REP(i,n){
		sum += v[i];
		ans = max(ans,sum + i * (i + 1) * p);
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 7060
#include <stdio.h>

int main(void)
{
    int n;
    int t[100001] = {0};
    int x[100001] = {0};
    int y[100001] = {0};

    int flag = 1;
    int i, sx, sy, s, e;

    scanf("%d", &n);
    for (i=1; i<=n; i++) {
        scanf("%d%d%d", &t[i], &x[i], &y[i]);
    }


    for (i=1; i<=n; i++) {
        sx = x[i] - x[i-1];
        if (sx<0) sx=-sx;
        sy = y[i] - y[i-1];
        if (sy<0) sy=-sy;
        s = sx + sy;
        e = t[i] - t[i-1];

        if (!(s<=e && (e-s)%2==0)) {
            flag = 0;
            break;
        }
    }

    if (flag)   printf("Yes\n");
    else        printf("No\n");

    return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int N_MAX=300;
int main()
{
  int h,w,k,i,j,ii,kk=0;
  int r[N_MAX][N_MAX];
  string s,t;
  bool empi=true,empj;
  cin >> h >> w >> k;
  for(i=0;i<h;i++){
    cin >> s;
    empj=true;
    for(j=0;j<w;j++){
      t=s.substr(j,1);
      if(t=="."&&!empj){
        r[i][j]=kk;
      }else if(t=="#"){
        kk++;
        r[i][j]=kk;
        if(empj){
          fill(r[i],r[i]+j,kk);
          empj=false;
        }
      }
    }
    if(!empi&&empj)
      copy(r[i-1],r[i-1]+w,r[i]);
    if(empi&&!empj){
      for(ii=0;ii<i;ii++)
        copy(r[i],r[i]+w,r[ii]);
      empi=false;
    }
  }
  for(i=0;i<h;i++){
    for(j=0;j<w;j++)
      cout << r[i][j] << " ";
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
N=int(input())
A=list(map(int,input().split()))
A.sort()

def binary(l,i):
  r=N-1
  while l<=r:
    m=(l+r)//2
    if A[m]==i:
      return A[m]
    elif A[m]>i:
      r=m-1
    else:
      l=m+1
  x=abs(A[m]-i)
  for j in range(max(0,m-2),min(m+3,N-1)):
    if x >= abs(A[j]-i):
      res = A[j]     
      x=abs(A[j]-i)
  return res


print(A[-1],binary(1,A[-1]/2))

Measured memory_bytes: 62704
n = int(input())
ais = list(map(int, input().split()))
bis = list(map(int, input().split()))
m = 0
for i in range(n):
  if bis[i] >= ais[i]:
    m += ais[i]
    bis[i] -= ais[i]
    if bis[i] >= ais[i+1]:
      m += ais[i+1]
      ais[i+1] = 0
    elif bis[i] < ais[i+1]:
      ais[i+1] -= bis[i]
      m += bis[i]
  else:
    m += bis[i]
    ais[i] -= bis[i]
print(m)
  

Measured memory_bytes: 19284
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)
typedef pair<int,int> pii;
int n,m;
pii a[222];
int dp[222];

inline bool le(pii const& t, pii const& u){
    return t.first<u.first && t.second<u.second;
}

int solve(){
    sort(a,a+n+m);
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1;i<n+m;i++){
        for(int j=0;j<i;j++){
            if(le(a[j],a[i])){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int ans=1;
    for(int i=0;i<n+m;i++){
        ans=max(ans,dp[i]);
    }
    return ans;
}

int main(){
    while(cin>>n && n){
        rep(i,n)cin>>a[i].first>>a[i].second;
        cin>>m;
        rep(i,m)cin>>a[i+n].first>>a[i+n].second;
        cout << solve() << endl;
    }
}

Measured memory_bytes: 1164
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int w, p;
		int[] ans = new int[51];
		Arrays.fill(ans, Integer.MAX_VALUE);
		for(int a=0;a<=4;a++){
			for(int b=0;b<=3;b++){
				for(int c=0;c<=2;c++){
					for(int d=0;d<=5;d++){
						for(int e=0;e<=4;e++){
							for(int f=0;f<=3;f++){
								w = a*2 + b*3 + c*5 + d*10 + e*12 + f*15;
								if(w<=50){
									p = a*380 + b*550 + c*850 + d*1520 + e*1870 + f*2244;
									ans[w] = Math.min(ans[w], p);
								}
							}
						}
					}
				}
			}
		}
	
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			System.out.println(ans[n/100]);
		}	
	}	
}

Measured memory_bytes: 17408
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn rep<T, F: FnMut() -> T>(n: usize, mut f: F) -> Vec<T> {
    (0..n).map(|_| f()).collect()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let a: Vec<usize> = rep(n, || scan(tokens));
    let mut ans = 0;
    for i in 0..60 {
        let bit = 1 << i;
        let count = a.iter().filter(|&&ai| ai & bit == 0).count();
        ans += bit % MODULO * count % MODULO * (n - count) % MODULO;
        ans %= MODULO;
    }
    println!("{}", ans);
}

const MODULO: usize = 1_000_000_007;


Measured memory_bytes: 13560
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 500;
int N, A[Nmax];
ll K;

vector<int> get_divisors(int x){
	vector<int> div(1, 1);
	for(int i=2; i*i<=x; i++){
		if(x%i==0) div.push_back(i);
	}
	vector<int> ret;
	for(int d: div){
		ret.push_back(d);
		if(d!=x/d) ret.push_back(x/d);
	}
	sort(ret.begin(), ret.end());
	return ret;
}

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

	ll sum = 0;
	for(int i=0; i<N; i++) sum += A[i];

	auto divisors = get_divisors(sum);
	int ans = 1;
	//cout << ub << endl;
	for(int div: divisors){
		vector<int> costs;
		int cost_sum = 0;
		//cout << div <<":"<< endl;
		for(int i=0; i<N; i++){
			int p = A[i]/div;
			//cout << A[i]-p*div << endl;
			costs.push_back(A[i]-p*div);
			cost_sum += A[i]-p*div;
		}
		if(cost_sum==0) {
			ans = div;
		}
		sort(costs.begin(), costs.end());
		int cum = 0;
		for(int i=0; i<N; i++){
			cum += costs[i];
			if(cost_sum==(N-i-1)*div){
				break;
			}
		}
		if(cum <= K) ans = div;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] data = new int[100000];
    int m = 0;

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


    for(int i = 0;i < n;i++){
      if(data[i] >= k){
        m++;
      }
    }

    System.out.println(m);

  }
}

Measured memory_bytes: 47700
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//--<for debugging>
#define whatis(x) cout << #x << " is " << x<<" ";
#define whatisl(x) cout << #x << " is " << x<<"\n";
#define parr(array,end)for(ll loop=0;loop<end;loop++)cout<<array[loop]<<" ";cout<<"\n";
#define lline cout<<"\n";
#define errorl(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"\n";}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"___";}
    
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a <<" , ";
    err(++it, args...);
}
//--</for debugging> 
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define testcase ll tt; cin >> tt; while(tt--)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define vars ll h,i,j,k,d,l,p,q,r,x,y,a,b,c,v,var,n,m,z,s,ans,ind1,ind2,flag,limit1,limit2,limit3,mod;
#define vll vector<ll>
#define pll pair<ll,ll>
#define sll set<ll>
#define pint pair<int,int>
const ll INF=1e9+7;
const ll MOD=1e9+7;
bool vis[10];
bool check(ll num)
{
    ll var,m;
    var=num;
    while(var)
    {
        m=var%10;
        var/=10;
        if(vis[m])return false;
    }
    return true;
}
int main()
{
    boost vars
    cin>>n>>k;
    ll arr[k];
    for(i=0;i<k;i++)
    {
        cin>>v;
        vis[v]=true;
    }
    v=n;
    while(!check(v))v++;
    cout<<v;
}

Measured memory_bytes: 3616