akhauriyash/Code-Regression huggingface dataset:
n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

count = 0
index = []
for i in range(n):
    for j in range(q):
        if s[i]==t[j]:
            for k in range(len(index)):
                if t[j]==index[k]:
                    break
            else:
                count += 1
                index.append(t[j])
            
print(count)


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

using namespace std;

int main()
{
  int n;
  cin >> n;
  while (n--)
  {
    int x;
    cin >> x;
    if (x % 2 == 0 && x % 3 != 0 && x % 5 != 0)
    {
      cout << "DENIED";
      return 0;
    }
  }
  cout << "APPROVED";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;

const int MOD=1000000007;
int INF=100100100100100;

int x[100],y[100]; 
map<P,int> iti;
vector<P> edge;
signed main(){
  int n;cin>>n;
  int ans=n;
  rep(i,n){
    cin>>x[i]>>y[i];
    iti[P(x[i],y[i])]++;
  }
  rep(i,n){
    rep(j,n){
      if(i==j)continue;
      edge.pb(P(x[i]-x[j],y[i]-y[j]));
    }
  }
  
  for(auto e:edge){
    int res=0;
    rep(i,n){
      res++;
      if(iti[P(x[i]+e.F,y[i]+e.S)]>=1)res--;
    }
    ans=min(ans,res);
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4096
#include<stdio.h>
int main(void){
char s[1001];
int i,sum;
scanf("%s",s);
while(s[0]!='0'){
i=0;
sum=0;
while(s[i]){
sum+=s[i]-'0';
i++;
}
printf("%d\n",sum);
scanf("%s",s);
}
return 0;
}

Measured memory_bytes: 536
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin>>k;
    if(k==7 || k==1){
        cout<<1<<endl;
        return 0;
    }
    if(k%2==0 || k%5==0 ){
        cout<<-1<<endl;
        return 0;
    }
    else{
        int x=7;
        int cnt=0;
        for (int i = 1; i <=k; i++)
        {
            if(x==0){
                cnt=i;
                break;
            }
            x*=10;
            x+=7;
            x%=k;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 3636
n = int(input())
a = list(map(int, input().split()))
s = [0] * n
s[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
    s[i] = s[i + 1] + a[i]
    
ans = 0
mod = 10 ** 9 + 7
for i in range(n - 1):
    ans += a[i] * s[i + 1]
print(ans % mod)

Measured memory_bytes: 31620
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
#define ll long long
int n,m,T[N],q[N];
ll Y[N],sum[N],fl[N],fr[N],f[N],tmp[N];
inline double slope(int x,int y){
	return 1.0*(Y[y]-Y[x])/(y-x);
}
inline void dp(ll *f){
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+T[i];
	int top=0;f[0]=0;q[++top]=0;
	for(int i=1;i<=n;++i){
		while(top>1 && slope(q[top-1],q[top])<=i) --top;
		f[i]=max(f[i-1],f[q[top]]+1ll*(i-q[top])*(i-q[top]+1)/2-(sum[i]-sum[q[top]]));
		Y[i]=f[i]+sum[i]+1ll*i*(i-1)/2;
		while(top>1 && slope(q[top-1],q[top])<=slope(q[top],i)) --top;
		q[++top]=i;
	}
}
void solve(ll *f1,ll *f2,int l,int r){
	if(l==r){
		f[l]=max(f[l],f1[l-1]+f2[l+1]-T[l]+1);
		return;
	}
	int mid=l+r>>1,top=0;
	for(int i=l-1;i<mid;++i){
		Y[i]=f1[i]+sum[i]+1ll*i*(i-1)/2;
		while(top>1 && slope(q[top-1],q[top])<=slope(q[top],i)) --top;
		q[++top]=i;
	}
	for(int i=mid;i<=r;++i){
		while(top>1 && slope(q[top-1],q[top])<=i) --top;
		tmp[i]=f1[q[top]]+f2[i+1]+1ll*(i-q[top])*(i-q[top]+1)/2-(sum[i]-sum[q[top]]);
	}
	for(int i=r-1;i>=mid;--i) tmp[i]=max(tmp[i],tmp[i+1]);
	for(int i=mid;i<=r;++i) f[i]=max(f[i],tmp[i]);
	solve(f1,f2,l,mid);solve(f1,f2,mid+1,r);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&T[i]);
	dp(fl);reverse(T+1,T+n+1);dp(fr);
	reverse(T+1,T+n+1);reverse(fr+1,fr+n+1);
//	for(int i=1;i<=n;++i) printf("%d ",fl[i]);puts("");
//	for(int i=1;i<=n;++i) printf("%d ",fr[i]);puts("");
	for(int i=1;i<=n;++i) f[i]=-T[i],sum[i]=sum[i-1]+T[i];
	solve(fl,fr,1,n);
// for(int i=1;i<=n;++i) printf("%d ",f[i]);puts("");
	reverse(T+1,T+n+1);reverse(f+1,f+n+1);reverse(fl+1,fl+n+1);reverse(fr+1,fr+n+1);
	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+T[i];
	solve(fr,fl,1,n);
	reverse(T+1,T+n+1);reverse(f+1,f+n+1);reverse(fl+1,fl+n+1);reverse(fr+1,fr+n+1);
// for(int i=1;i<=n;++i) printf("%d ",f[i]);puts("");
//	for(int i=1;i<=)
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		int x,y;scanf("%d%d",&x,&y);
		printf("%lld\n",max(fl[x-1]+fr[x+1],f[x]+T[x]-y));
	}
	return 0;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    int n; cin >> n;
    vector<lint> a(n+1); rep(i, n+1) cin >> a[i];

    if(n==0){
        if(a[0]==1) out(1); else out(-1);
        return 0;
    }
    if(a[0]!=0){
        out(-1); return 0;
    }

    vector<lint> p(n+1), q(n+1);
    repr(i, n+1){
        if(i == n){
            p[i] = q[i] = 0; continue;
        }
        p[i] = (a[i+1]+p[i+1]+1)/2;
        q[i] = a[i+1]+q[i+1];
    }
    if(p[0]>1 || 1>q[0]){
        out(-1); return 0;
    }

    vector<lint> b(n+1);
    rep(i, n+1){
        if(i==0){
            b[i] = 1; continue;
        }
        lint m = 2*b[i-1]-a[i];
        b[i] = min(m, q[i]);
    }

    lint sum = 0;
    rep(i, n+1) sum += (a[i]+b[i]);
    out(sum);
}


Measured memory_bytes: 6324
N=int(input())
maxi=0
maxinum=0
submaxi=0
for n in range(N):
    tmp=int(input())
    if tmp>maxi:
        submaxi=maxi
        maxi=tmp
        maxinum=n
    elif tmp>submaxi:
        submaxi=tmp
for n in range(N):
    if n==maxinum:
        print(submaxi)
    else:
        print(maxi)

Measured memory_bytes: 4668
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string s,qwq;
int main()
{
	cin>>s;
	qwq=s;
	reverse(qwq.begin(),qwq.end());
	for(int i=0;i<s.size();i++)
	{
		if(qwq[i]=='p') qwq[i]='q';
		else if(qwq[i]=='q') qwq[i]='p';
		else if(qwq[i]=='d') qwq[i]='b';
		else if(qwq[i]=='b') qwq[i]='d';
	}
	if(qwq==s) printf("Yes");
	else printf("No");
	return 0;
}

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

int main() {
  int n,m;
  cin >> n >> m;
  vector<bool> ac(n,false);
  vector<int> wa(n,0);
  for(int i=0;i<m;i++) {
    string s;
    int p;
    cin >> p >> s;
    p--;
    if(s=="AC") {
      ac.at(p)=true;
    }
    else if(!ac.at(p)) {
      wa.at(p)++;
    }
  }
  int nac=0,nwa=0;
  for(int i=0;i<n;i++) {
    if(ac.at(i)) {
      nac++;
      nwa+=wa.at(i);
    }
  }
  cout << nac << " " << nwa << endl;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define REP(i, start, end) for (ll i = start, i##Len = (end); i < i##Len; ++i)
#define REPR(i, start, end) for (ll i = start, i##Len = (end); i > i##Len; --i)
using ll = long long;
using namespace std;

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

    ll H, W, M;
    cin >> H >> W >> M;
    map<int, int> v_cnt, h_cnt;
    vector<pair<int, int>> a;
    int h, w;
    REP(_, 0, M)
    {
        cin >> h >> w;
        a.emplace_back(h, w);
        h_cnt[h]++;
        v_cnt[w]++;
    }

    int h_max = 0, v_max = 0;
    for (auto &[_, cnt] : h_cnt)
        h_max = max(h_max, cnt);
    for (auto &[_, cnt] : v_cnt)
        v_max = max(v_max, cnt);

    int ans = h_max + v_max - 1;

    int h_max_cnt = 0;
    for (auto &[_, c] : h_cnt)
        if (c == h_max)
            h_max_cnt++;
    map<int, int> mm;
    for (auto &[y, x] : a)
        if (h_cnt[y] == h_max)
            mm[x]++;

    for (auto &[x, cnt] : v_cnt)
        if (cnt == v_max && mm[x] < h_max_cnt)
        {
            cout << ans + 1 << endl;
            return 0;
        }
    cout << ans << endl;
}

Measured memory_bytes: 47640
a, b, c, x, y = map(int,input().split())
total = []

for i in range(0, max(x, y) + 1):
    c_price = i * 2 * c
    if x - i <= 0:
        a_price = 0
    else:
        a_price = (x - i) * a
    if y - i <= 0:
        b_price = 0
    else:
        b_price = (y - i) * b
    total.append(a_price + b_price + c_price)
print(min(total))


Measured memory_bytes: 12648
n,m = map(int, input().split())
a = list(map(int, input().split()))
num = 0
s = 0
#while num != (m):
#    s += int(a[num])
#    num += 1
for i in a:
    s += i
ans = n - s
if ans < 0:
    ans = -1
print(ans)

Measured memory_bytes: 9880
#include<stdio.h>
#include<ctype.h>

int main(){
  char b[100000];
  int i,c;
  
  i=0;
  while(1){
    c=getchar();
    if(c=='\n'){
      break;
    }
    if(islower(c)){
      b[i]=toupper(c);
    }
    else{
      b[i]=c;
    }
    i++;
  }
  b[i]=0;
  printf("%s\n",b);
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cmath>
using namespace std;
int main(){
double w,h,d,r;
double pi=3.141592653,s;
int n;
while(1){
cin >> w >> h >> d;
if(w+h+d==0) break;
cin >> n;
while(n--){
cin >> r;
r*=2;
double dw,dh,dd;
dw=sqrt(w*w+h*h);
dh=sqrt(h*h+d*d);
dd=sqrt(d*d+w*w);
if(dw<r||dh<r||dd<r) cout<<"OK" << endl;
else cout << "NA" << endl;
}
}
return 0;
}

Measured memory_bytes: 1224
program panasonic2020B
    implicit none
    integer(8)::H,W
    read*,H,W
    if(H==1.or.W==1)then
        print'(i0)',1
    else
        print'(i0)',(H*W)/2+mod(H*W,2)
    end if
end program panasonic2020B

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

int main() {
  string s, init, tail;
  cin >> s;
  int q;
  cin >> q;
  bool reversed = false;
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      reversed = !reversed;
    } else {
      int f;
      char c;
      cin >> f >> c;
      if (reversed == (f == 1)) {
        tail += c;
      } else {
        init += c;
      }
    }
  }
  reverse(init.begin(), init.end());
  s = init + s + tail;
  if (reversed) reverse(s.begin(), s.end());
  cout << s << endl;
}


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



int main() {
  string S;
  cin>>S;
  rep(i,S.size()){
      cout<<'x';
  }
  cout<<endl;
}

Measured memory_bytes: 256
#include <iostream>

 

using namespace std;

 

int main() 
{
    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if(x-r >= 0 && y-r >= 0 && x+r <= w && y+r <= h)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
   
        
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
struct Data
{
	int a,b;
}p[maxn],q[maxn];
int n,m,ans,tot1,tot2;
long long f[40],sum[maxn];
bool cmp1(const Data &x,const Data &y)
{
	return x.b<y.b;
}
bool cmp2(const Data &x,const Data &y)
{
	return (1ll*x.b*y.a+y.a)<(1ll*y.b*x.a+x.a);
}
int check(int x)
{
	int l=0,r=tot2;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(sum[mid]<=x)
			l=mid+1;
		else
			r=mid-1;
	}
	return r;
}
int main()
{
	read(n,m);
	for(int i=1;i<=n;i++)
	{
		Data t;
		read(t.a,t.b);
		if(t.a)p[++tot1]=t;
		else q[++tot2]=t;
	}
	for(int i=0;i<=32;i++)
		f[i]=m+1;
	sort(p+1,p+1+tot1,cmp2);
	sort(q+1,q+1+tot2,cmp1);
	f[0]=0;
	for(int i=1;i<=tot1;i++)
		for(int j=32;j;j--)
		{
			if(f[j-1]>m||1ll*p[i].a*f[j-1]>m)
				continue;
			f[j]=min(f[j],1ll*(f[j-1]+1)*(p[i].a+1)+p[i].b);
		}
	for(int i=1;i<=tot2;i++)
		sum[i]=sum[i-1]+q[i].b+1;
	for(int i=0;i<32;i++)
		if(f[i]<=m)
			ans=max(ans,i+check(m-f[i]));
	printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

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

    string s;
    cin >> s;
    int n = 12;

    rep(i, n){
        cout << s[i];
        if(i==3) cout << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
from sys import stdin,stdout
from collections import defaultdict
import math
from bisect import bisect
#input=stdin.readline
#def print(x):stdout.write(str(x)+'\n')
n=int(input())
arr=list(map(int,input().split()))
result = 0
su=sum(arr)
s=[]
s1=0
for i in range(n):
    s1+=arr[i]
    s.append(su-s1)

for i in range(0, n): 
    result+=(arr[i]*s[i])
print((result)%(10**9+7))

Measured memory_bytes: 32084
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> P;
map <int,int> mp;
vector<int> V;
#define debug(x) cerr << #x << ": " << x << "\n";
#define INF (1<<29) //53687091
#define INFLL (1ll<<58)
#define EPS (1e-10)
static const int MAX=(int) 1e6;
static const int MOD=(int) 1e9+7;
static const int NMAX=50;
static const int MMAX=50;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };

int D,G;
int p[11],c[11];
int num;//解く問題数
int score; //得点
int max_rest;//完答しない問題のなかで最大の問題

void solve(){
    int ans = INF;
    for(int mask = 0;mask < (1<<D);mask++){ //完答する問題の2進数表記
        num =0; score=0;
        for(int i=0;i<D;i++){
            if((mask >> i) & 1 ){ //i番目を完答する
                num += p[i];
                score += 100 * (i+1) * p[i] + c[i];
            }else{
                max_rest = i;
            }
        }
        if(score<G){
            int s1 =(max_rest+1)*100;
            int need = (G - score + s1 -1) / s1;
            if(p[max_rest] <= need) continue;
            num += need;
        }
        ans = min(num,ans);
    }
    cout << ans << "\n";
}

int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    cin >> D >> G;
    for(int i=0;i<D;i++) cin >> p[i] >> c[i];
    
    solve();
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<algorithm>
#include <string>
#include <set>
#include <limits.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

#define rip(i,n,s) for (int i=(s);i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;

long long pow(long long n, long long p,long long k) {//n^k(mod p)
	if (k != 0) {
		if (p % 2==0) {
			long long x = pow(n, p, k / 2);
			return (long long)x*x%p;
		}
		else {
			long long x = pow(n, p, k - 1);
			return (long long)x*n%p;
		}
	}
	return 1;
}
long long rev(long long n, long long p) {//nの逆元
	return pow(n, p ,p - 2);
}
long long bino(long long n, long long m, long long p) {//nCm(mod p)
	long long me = 1;
	long long ans = 1;
	for (int i = 0;i < n + m;i++) {
		me = (long long)(i + 1) * ans % p;
		if (i == m - 1) {
			ans =(long long) rev(me,p) * ans%p;
		}
		if (i == m - n - 1) {
			ans = (long long)(rev(me, p))*ans%p;
		}
	}
	ans = (long long)(ans*me%p);
	return ans;
}
struct modint{
    long long num;
    long long p;
    modint () {
        num=0;
        p=1000000007;
    }
    modint(int x){
        p=1000000007;
        num=(long long) x%p;
    }
    modint (long long x){
        p = 1000000007;
        num = x%p;
    }
    modint operator+(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num+other.num)%p;
        return ret;
    }
	modint operator+(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num+(other%p))%p;
        return ret;
    }
    modint operator-(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num-other.num+p)%p;
        return ret;
    }
    modint operator-(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num-(other%p)+p)%p;
        return ret;
    }
    modint operator*(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num*other.num)%p;
        return ret; 
    }
    modint operator*(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num*(other%p))%p;
        return ret; 
    }
    modint operator/(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num*rev(other.num,p))%p;
		return ret;
    }
    modint operator/(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num*rev(other%p,p))%p;
		return ret;
    }
    void operator+=(const modint &other){
        num=(num+other.num)%p;
    }
    void operator+=(const long long &other){
        num=(num+other)%p;
    }
    void operator-=(const modint &other){
        num=(num-other.num+p)%p;
    }
    void operator-=(const long long &other){
        num=(num-other+p)%p;
    }
};

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    rip(i,n,0){
        cin >> a[i];
    }
    vector<vector<modint>> dp(n+1,vector<modint>(k+1));
    dp[0][0]+=1;
    rip(i,n+1,1){
        modint no;
        rip(j,k+1,0){
            no+=dp[i-1][j];
            if(j-a[i-1]-1>-1){
                no-=dp[i-1][j-a[i-1]-1];
            }
            dp[i][j]=no;
        }
    }
    printf("%lld\n",dp[n][k].num);
}

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

int main()
{
	int n, a[1000], sum = 0, y, b[2] = {0};

	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		sum += a[i];
	}
	y = sum / n;
	for (int i = 0; i < n; i++){
		b[0] += (a[i] - y) * (a[i] - y);
	}

	y++;
	for (int i = 0; i < n; i++){
		b[1] += (a[i]- y) * (a[i] - y);
	}
	cout << min(b[0], b[1]) << endl;
	return (0);
}


	


Measured memory_bytes: 256
/*-----------------------------------------------,
|  __                                       __   |
| |  |--.-----.---.-.----.----.-----.-----.|  |_ |
| |  _  |  -__|  _  |  __|  __|  -__|  _  ||   _||
| |_____|_____|___._|____|____|_____|   __||____||
|                                   |__|         |
`-----------------------------------------------*/
#include<algorithm>
#include<array>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
typedef long long lint; typedef long double ldouble ;using namespace std;
#define INF 1000000000000
#define MOD 10000007
#define rep(counter, limit) for (long long counter = 0; counter < limit; counter++)
int gcd(int a, int b) { if (a % b == 0) { return(b); } else { return(gcd(b, a % b)); } }
int lcm(int a, int b) { return a * b / gcd(a, b); }
bool primenum(int a) { if (a == 1) { return false; }if (a == 2) { return true; }if (a % 2 == 0) { return false; }for (int i = 3; i < sqrt(a) + 1; i += 2) { if (a != i) { if (a % i == 0) { return false; } } }return true; }
struct setupios{setupios(){cin.tie(0);ios::sync_with_stdio(0); /*cout<<fixed<<setprecision(20);*/};}setupios;
int main() {

  int n;
  cin>>n;
  vector<int> u(n);
  rep(i,n)cin>>u[i];
  sort(u.begin(),u.end());
  double ans=0;
  rep(i,n){
    if(ans==0){
      ans=u[i];
    }else{
      ans+=u[i];
      ans/=2;
    }
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;

long long n, k;

int main () {
    cin >> n >> k;
    if ( n >= 10 ) {
        cout << k;
    }
    else {
        cout << 100 * (10 - n) + k;
    }
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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; }

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p) pom(a,p-2,p)

////////////////////////////////////////////////////////////////////////////////////////
int main(){
    int K, S; cin >> K >> S;
    K++;
    int res = 0;
    rep(X,0,K){
        rep(Y,0,K){
            if(S - (X + Y) >= 0 && S - (X + Y) <= K-1){
            	res++;
            }
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n;
    while(cin >> n, n){
        vector<int> v(n);
        for (auto &&i : v) scanf("%d", &i);
        sort(v.begin(), v.end());
        int ans = INF<int>;
        for (int i = 0; i < n-1; ++i) {
            ans = min(ans, v[i+1]-v[i]);
        }
        cout << ans << "\n";
    }
    return 0;
}



Measured memory_bytes: 3180
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define UTIL_ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

#define UTIL_SWAP(x, y)                                                                                                                    \
  do {                                                                                                                                     \
    typeof(x) _a = x;                                                                                                                      \
    x = y;                                                                                                                                 \
    y = _a;                                                                                                                                \
  } while (0)

#define UTIL_PRINT_ARRAY(arr, size)                                                                                                        \
  do {                                                                                                                                     \
    uint16_t i;                                                                                                                            \
    for (i = 0; i < size; i++) {                                                                                                           \
      if (i != 0) printf(" ");                                                                                                             \
      printf("%d", arr[i]);                                                                                                                \
    }                                                                                                                                      \
    printf("\n");                                                                                                                          \
  } while (0)

#define BUF_SIZE 100

uint32_t bubble(int32_t buf[], size_t size)
{
  uint32_t num = 0;
  uint16_t i = size;
  while (i--) {
    uint16_t j;
    for (j = 0; j < i; j++) {
      if (buf[j] > buf[j + 1]) {
        UTIL_SWAP(buf[j], buf[j + 1]);
        num++;
      }
    }
  }

  return num;
}

#if !defined(TEST)
int32_t main(void)
{
  int32_t num;
  scanf("%d", &num);
  int32_t buf[BUF_SIZE];
  uint16_t i;
  for (i = 0; i < num; i++) {
    scanf("%d", &buf[i]);
  }

  uint32_t cnt = bubble(buf, num);

  UTIL_PRINT_ARRAY(buf, num);
  printf("%d\n", cnt);

  return 0;
}
#endif

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

int main() {
  int a ,b;
  cin>>a>>b;
  if (a%2==0)
    cout<<"Even"<<endl;
  else if (b%2==0)
    cout <<"Even"<<endl;
  else
    cout<<"Odd"<<endl;
  
}


Measured memory_bytes: 256
def dfs(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + a[n - 1]:
        return dfs(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + dfs(n - 1, x - 2 - a[n - 1])

n, x = map(int, input().split())

a, p = [1], [1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

print(dfs(n, x))

Measured memory_bytes: 38256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 1073741824
#define ll long long
#define PI (2*acos(0.0))
using namespace std;
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> 
void dbg_out(Head H, Tail... T) { 
    cerr << ' ' << H;
     dbg_out(T...); 
}
#define dbg(...) cerr << '(' << #__VA_ARGS__ << ')'<<':', dbg_out(__VA_ARGS__)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define x first
#define y second
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define on(val,pos) (val|(1<<pos))
#define off(val,pos) (val&(~(1<<pos)))
#define check(val,pos) (val&(1<<pos))
#define all(n) n.begin(),n.end()
//first four adjacent,second four corner
//int row[8]={0,-1,0,1,1,-1,-1,1};
//int col[8]={-1,0,1,0,-1,-1,1,1};
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int main(){
    int i,j,k,n,m,val,t=0,test;
    //freopen("000input.txt","r",stdin);
    cin>>n>>m>>k;
    cout<<((n+m-1)/m)*k<<endl;
    //free();   //if pointer array
    return 0;
}


Measured memory_bytes: 3568
//
//  main.cpp
//  ABC164
//

//  Copyright © 2020 エロやん. All rights reserved.
//

#include <iostream>
using namespace std;
int main(){
    int K,A,B;
    bool frag = false;
    cin>>K;
    cin>>A>>B;
    for(int i=A;i<=B;i++)
    {
        if(i%K==0)
        {
            frag= true;
            
        }
        
        
        
    }
        
    if(frag)cout<<"OK";
        else cout<<"NG";
    
    
    
    
    return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a,b,c,cnt=0;
	cin>>a>>b>>c;
	for(int i=a;i<=b;i++){
		if(c%i==0)cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace std;
#define int long long int
//#define double long double
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> new_data_set;
bool isprime(int n)
	{
    	if(n==1) return true;
    	for(int i = 2;i*i<=n;i++){
    		if(n%i==0) return false;
		}
		return true;
	}
int lcm(int a,int b){
	return (a*b)/__gcd(a,b);
}
int gcd(int a, int b) 
{ 
    if (b == 0){
    	return a;
	} 
    return gcd(b, a % b);  
      
} 
unsigned int factorial(unsigned int n) 
{ 
    if (n == 0) 
    return 1; 
    return n * factorial(n - 1); 
} 
const int inf=1e17+7;
int dsu[1000001],s[100005];
pair<int,int>pz[100001],po[100001];
void init(int n,int m){
	for(int i=1;i<=n;i++){
		dsu[i]=i;
		s[i]=1;
	}
}
int root(int x){
	while(dsu[x]!=x){
		x = dsu[x];
	}
	return x;
}
void uni(int x,int y){
	int p = root(x);
	int q = root(y);
	if(p==q){
		return;
	}
	else{
		if(s[p]<s[q]){
			s[q]+=s[p];
			dsu[p] = q;
		}
		else{
			s[p]+=s[q];
			dsu[q] = p;
		}
	}
}
int power(int x, unsigned int y)  
{  
    int res = 1;
    x = x ; 
    if (x == 0) return 0;  
    while (y > 0)  
    {  
        if (y & 1)  
            res = (res*x);   
        y = y>>1;  
        x = (x*x);  
    }  
    return res;  
}
bool visited[100001]={false};

//void dfs(int x){
//	visited[x]=true;
//	//ans.push_back(x);
//	//c[x]=1;
//	for(auto &child:graph[x]){
//		if(!visited[child]){
//			dfs(child);	
//			//c[x]+=c[child];
//		}
//	}
//}
signed main(){
	FAST
	int n,w;
	cin>>n>>w;
	int arr[n][2];
	for(int i=0;i<n;i++){
		cin>>arr[i][0]>>arr[i][1];
	}
	int dp[n][n*1000 +1];
	int ans=0;
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=n*1000;j++){
			if(i==0){
				if(j==arr[i][1] && arr[i][0]<=w)dp[i][j]=arr[i][0];
				else if(j!=0)dp[i][j]=-1;
			}
			else{
				if(j<arr[i][1])dp[i][j]=dp[i-1][j];
				else{
					if(dp[i-1][j-arr[i][1]]+arr[i][0]<=w && dp[i-1][j-arr[i][1]]!=-1){
						dp[i][j]=dp[i-1][j-arr[i][1]]+arr[i][0];
						if(dp[i-1][j]!=-1){
							dp[i][j]=min(dp[i-1][j],dp[i][j]);
						}
					}
					else{
						dp[i][j]=dp[i-1][j];
					}
				}
			}
			if(dp[i][j]!=-1)ans=max(ans,j);
			//cout<<dp[i][j]<<"  ";
		}
		//cout<<endl;
	}
	cout<<ans;
}

Measured memory_bytes: 78336
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		List<Integer> list = new ArrayList<Integer>();
		for(;;){
			int n = scan.nextInt();
			int x = scan.nextInt();
			if(n == 0 && x == 0){
				break;
			}
			int cnt = 0;
			for(int i = 1; i <= n; i++){
				for(int j = i + 1; j <= n; j++){
					for(int k = j + 1; k <= n; k++){
						if(i + j + k == x){
							cnt++;
						}
					}
				}
			}
			list.add(cnt);
		}

		for(int c : list){
			System.out.println(c);
		}
	}
}

Measured memory_bytes: 26820
a,b,n = map(int, input().split())

def ma(k):
    s = a * k / b
    t = k / b
    ss = s // 1
    tt = (t // 1) * a
    return ss - tt

if(n < b):
    print(str(int(ma(n))))
else:
    print(str(int(ma(b-1))))

Measured memory_bytes: 9100
import java.util.*;

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

Measured memory_bytes: 19796
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 300
#define X 1000000007
using namespace std;
int n,p[2*N+5],s[2*N+5],C[2*N+5][2*N+5],IC[2*N+5][2*N+5],f[2*N+5][N+5][N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
	RI i,j;for(C[0][0]=IC[0][0]=i=1;i<=2*N;++i)
		for(C[i][0]=IC[i][0]=j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%X,IC[i][j]=QP(C[i][j],X-2);
	RI k,x,y,t=0,g=0;for(scanf("%d",&n),i=1;i<=n;++i)
	{
		if(scanf("%d%d",&x,&y),~x&&(p[x]=1),~y&&(p[y]=1),~x&&~y) continue;
		~x&&(s[x]=1,++g),~y&&(s[y]=1,++g),!~x&&!~y&&++t;
	}
	RI tmp,cnt=0,h=g;for(f[0][0][0]=i=1;i<=2*n;++i)
	{
		if(s[i])
		{
			for(j=0;j<=t;++j) for(k=0;k^h;++k) f[i][j][k]=
				(1LL*C[h-1][k]*IC[h][k]%X*f[i-1][j][k]+1LL*C[h-1][k]*IC[h][k+1]%X*f[i-1][j][k+1])%X;
			--h;continue;
		}
		if(p[i]) {for(j=0;j<=t;++j) for(k=0;k<=h;++k) f[i][j][k]=f[i-1][j][k];continue;}
		for(j=0;j<=t;++j) for(k=0;k<=h;++k)
		{
			(tmp=(j+g-h)-(cnt-j-k))>0&&(f[i][j][k]=f[i-1][j][k]);
			j&&(f[i][j][k]=(1LL*(t-j+1)*f[i-1][j-1][k]+f[i][j][k])%X);
			k&&(f[i][j][k]=(1LL*(h-k+1)*f[i-1][j][k-1]+f[i][j][k])%X);
		}++cnt;
	}
	RI ans=0;for(j=0;j<=t;++j) ans=(ans+f[2*n][j][0])%X;return printf("%d\n",ans),0;
}

Measured memory_bytes: 222708
#include<iostream>
#include<iomanip>
#include<limits>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9)+7)

int main()
{
  ll x;
  cin >> x;
  ll ans = 0;
  while(x!=0)
  {
    // cout << x << endl;
    if(x-500 >= 0)
    {
      ans += 1000;
      x -= 500;
    }
    else if(x-5 >= 0)
    {
      ans += 5;
      x -= 5;
    }
    else
    {
      break; 
    }
  }
  cout << ans << endl;
}


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

const int MaxN = 10 + 5;

int N;
int P[MaxN];

int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> P[i];
    sort(P + 1, P + 1 + N);

    int ans = P[N] / 2;
    for (int i = 1; i < N; ++i) ans += P[i];
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s, t;
	cin >> s >> t;
	int sz = s.size(), l = t.size();
	int mn = INT_MAX;
	for(int i=0; i<=sz-l; i++){
		int cur = 0;
		for(int j=0; j<l; j++){
			if(s[i+j] != t[j]){
				cur++;
			}
		}
		mn = min(cur,mn);
	}
	cout << mn << endl;
	return 0;
}

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

int main()
{
	int N;
	int count = 0;
	cin >> N;
	for (int i = 2; i <= 9; i++) {
		if (N <= 9) {
			count++;
			cout << "Yes" << endl;
			break;
		}
		if (N%i == 0 && N / i <= 9) {
			count++;
			cout << "Yes" << endl;
			break;
		}

	}
	if (count == 0) {
		cout << "No" << endl;
	}

	return 0;
}


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

int arr[52];
ll dp[maxi][maxi][maxi*maxi];
int N ,a ;
ll mydp(int index , int cnt , int sum ){
    if(index==N){
        if(cnt>0 &&  sum/cnt==a && sum%cnt==0){
            return 1;
        }
        else
            return 0;

    }
    if(dp[index][cnt][sum]!=-1){
        return dp[index][cnt][sum];
    }
    else{
        return dp[index][cnt][sum]=mydp(index+1,cnt,sum)+mydp(index+1,cnt+1,sum+arr[index]);

    }



}

int main(){
  cin >> N >> a;
  for(int i=0;i<N;i++)
    cin >> arr[i];
  memset(dp,-1,sizeof(dp));
  cout << mydp(0,0 , 0) <<endl;
  return 0;
}


Measured memory_bytes: 57344
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
      
        if((a*b) % 2 == 0)
          System.out.println("Even");
        else
          System.out.println("Odd");
    }
}


Measured memory_bytes: 23252
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    string b; cin>>b;
    if(b=="A") cout<<"T";
    else if(b=="T") cout<<"A";
    else if(b=="C") cout<<"G";
    else cout<<"C";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using P = pair <int, int>;
 
 
int main(){
    int a,b;
    cin >> a>>b;
    int c=a,d=b,ans;
    int e=1;
    while(d/10>0){
      d/=10;
      e++;
    }
    for(int i=1;i<=e;i++){
        a *=10;
    }
    ans = a+b;
    int cnt = 0;
    for(int i =1; i<=ans;++i){
      if (i*i==ans) cnt++;
    }
    if (cnt == 0) cout << "No" <<endl;
    else cout <<"Yes" << endl;
   }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  	string s;
  	cin>>s;
  	ll n=s.length(),k=0;
  	for(int i=0;i<n/2;i++){
    	if(s[i]!=s[n-1-i]) k++;
 	}
  	cout<<k;
  	return 0;
}


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

using namespace std;
typedef long long ll;

int main()
{
	//freopen("t.txt","r",stdin);
	int a, x; cin>>x>>a; if (x<a) {
		cout<<0; return 0;
	}
	else cout<<10;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int A, B;

int main() {
    cin >> A >> B;

    if (A == 1) A = 14;
    if (B == 1) B = 14;

    if (A > B)
        cout << "Alice" << endl;
    else if (A < B)
        cout << "Bob" << endl;
    else
        cout << "Draw" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
main(){int N[32769]={0},M=32769,i=0,j,k,l;for(;i*i++<M;)for(N[i*i]++,j=i;i*i+j*j<M;j++)for(N[i*i+j*j]++,k=j;i*i+j*j+k*k<M;k++)for(N[i*i+j*j+k*k]++,l=k;i*i+j*j+k*k+l*l<M;)N[i*i+j*j+k*k+l*l++]++;for(;std::cin>>l,l;)printf("%d\n",N[l]);}

Measured memory_bytes: 880
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<cmath>
#include<sstream>
#include<iomanip>
#include <map>
#include <stack>
 
const int64_t cc = pow( 10, 9 );
//std::cout<< std::fixed << std::setprecision(10) << ( double )( max ) / 2;
bool sort_pair( std::pair< std::string, int64_t > origin, std::pair< std::string, int64_t > another )
{
    return origin.second  > another.second;
}
 
int main()
{
    std::string word = "aa";
    int64_t a,b,c,d,e;
    std::cin>> a;
    std::cin>> b;

    std::vector< std::string > list;

    c = 0;
    d = a;

    while( d <= b )
    {
        d *= 2;
        c += 1;
    }

    std::cout<< c;
}


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

int main(){
  int N, A, B;
  cin >> N >> A >> B;
  int count = 0;
  for(int i = 0; i < N; i++){
    int x = (i + 1)/10000;
    int y = (i + 1)/1000 - 10*x;
    int z = (i + 1)/100 - 100*x - 10*y;
    int w = (i + 1)/10 - 1000*x -100*y -10*z;
    int v = (i + 1) - 10000*x - 1000*y - 100*z - 10*w;
    if( (A <= (x + y + z + w + v)) && ((x + y + z + w + v) <= B) ) count += i + 1;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#agc25a

n = int(input())

lst = []

for i in range(1,int(n/2)+1):
    a = n-i

    s1 = str(a)
    s2 = str(i)
    
    #print(s1,s2)
    ans = 0
    for j in range(len(s1)):
        ans += int(s1[j])
    #print(s1,ans)
    for j in range(len(s2)):
        ans += int(s2[j])
    #print(s2,ans) 
    lst.append(ans)
lst.sort()
print(lst[0])

Measured memory_bytes: 3480
/* it was worth becoming a chemist */
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned int uni;
typedef unsigned long long unll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<int> vi;
typedef vector<long long> vll;

#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define NAME "puts"
#define F first
#define S second

const ll INF = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
const db EPS = (db) 1e-9;
const db pi = acos(-1.0);
const int MAXN = 1e6 + 5;

ll q, h, s, d, n;

int main() {	
    #ifndef ONLINE_JUDGE
	//~ freopen(NAME".in", "r", stdin);
	//~ freopen(NAME".out", "w", stdout);
    #endif
	
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << setprecision(9) << fixed;

	cin >> q >> h >> s >> d >> n;
	
	ll L1 = min(q * 4, min(h * 2, s));
	ll L2 = min(d, L1 * 2);
	
	ll res = n / 2 * L2;
	n = n - n / 2 * 2;
	
	res += (n * L1);
	
	cout << res;
	
	return 0;
}


Measured memory_bytes: 256
var
 i,n,s,max:longint;
 ch:char;
begin
 readln(n);
 s:=0;
 for i:=1 to n do
  begin
   read(ch);
   case ch of
    'I':inc(s);
    'D':dec(s);
   end;
   if s>max then max:=s;
  end;
 writeln(max);
end.

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

#define MAX_N 500

int main() {
	int N;
	cin >> N;
	long home[MAX_N][3] = {0};
	for (int i = 0; i < N-1; i++) {
		for (int j = 0; j < 3; j++)
			cin >> home[i][j];
	}
	for (int i = 0; i < N-1; i++) {
		long sum = home[i][1];
		for (int j = i; j < N-1; j++) {
			if (sum < home[j][1]) 
				sum = home[j][1];
			if (sum % home[j][2] != 0)
				sum += home[j][2] - sum % home[j][2];
			sum += home[j][0];
		}
		cout << sum << endl;
	}
	cout << 0 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long 
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define REP(i,n) for (int i=0; i<(n); i++)
#define RREP(i,n) for (int i=(n-1); i>=0; i--)
#define ALL(x) x.begin(),x.end()
#define SZ(x) x.size()
#define MNTO(a,b) a = min(a,(__typeof__(a))(b))
#define MXTO(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define debug(x) cerr<<#x<<" is "<<x<<endl
using namespace std;

const int maxn = 2e5+5;
const int intinf = 1<<29;
const ll inf = 1ll<<60;


void GG(){cout<<"No\n"; exit(0);}



int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    string s; cin>>s;
    map<char, bool> mp;
    for (char c: s){
    	mp[c]=1;
    }
    if (mp['N']!=mp['S'] or mp['E']!=mp['W']) {
    	cout<<"No\n";
    }else cout<<"Yes\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
#define int ll
using namespace std;
 
const ll N =(2e5+5);
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX;
const ll LOG = 29;
#define PI 3.141592653589793238 
 
 
long long binpow(long long a, long long b) {
    a%=MOD;    
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%MOD;
        a = (a * a)%MOD;
 
        
        b >>= 1;
    }
    res%=MOD;
    return res;
}
vll adj[N];
bool vis[N];
ll cnt = 0;

void dfs(ll u){
    vis[u]=true;
    for(auto v:adj[u]){
        if(!vis[v])
            dfs(v);
    }
    cnt++;
}
map<ll,ll> co;
void solve(){

    ll n,m;
    cin>> n >> m;
    ll src = -1;
    for(int i =1;i<=m;i++){
        ll u,v;
        cin>> u >> v;
        if(src==-1)src=  u;
        adj[u].pb(v);
    
        adj[v].pb(u);
        if(u > v)swap(u,v); 
        co[u]++;
        co[v]++;
    }
    for(auto x:co){
        if(x.s %2 !=0){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";  


    
}
 
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     
    ll t=1;
    while(t--){
        solve();
    }    
}

Measured memory_bytes: 13824
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; 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 sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

class rMq {
  public:
  int N;
  vl segtree;
  rMq(int n) {
    N = 1;
    int len = 1;
    while(N < n) {
      N *= 2;
      len += N;
    }
    segtree = vl(len,-LINF);
  }
  void build(int idx,ll val) {
    int s = sz(segtree) - (N-idx);
    segtree[s] = val;
    while(1) {
      if(s == 0) break;
      s = (s-1)/2;
      segtree[s] = max(segtree[s*2+1],segtree[s*2+2]);
    }
  }
  ll _query(int a,int b,int idx,int l,int r) {
    if(a <= l && r <= b) return segtree[idx];
    if(r <= a || b <= l) return -LINF;
    ll vl = _query(a,b,idx*2+1,l,(l+r)/2);
    ll rl = _query(a,b,idx*2+2,(l+r)/2,r);
    return max(vl,rl);
  }
  // max(A[i] | l <= i < r)
  ll query(int l,int r) {
    return _query(l,r,0,0,N);
  }
};
  
int main() {
  int N;
  cin >> N;
  vl h(N),a(N);
  rep(i,N) {
    cin >> h[i];
  }
  rep(i,N) {
    cin >> a[i];
  }
  rMq seg(N+3);
  seg.build(0,0);
  rep(i,N) {
    ll r = seg.query(0,h[i]+1)+a[i];
    ll now = seg.query(h[i],h[i]+1);
    if(now<r) {
      seg.build(h[i],r);
    }
  }
  ll ans = seg.query(0,N+3);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 7424