akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define rev(v) (v).rbegin(), (v).rend()
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> P;
typedef long long ll;

int dp[600000] = {};

int main(){
	for(int i = 1; i < 1001; i++){
		int sum = 0;
		for(int j = i; j < 1001; j++){
			sum += j;
			dp[sum]++;
		}
	}
	rep(i, 1001){
		dp[i]--;
	}

	int n;
	while(cin >> n, n){
		cout << dp[n] << endl;
	}

	return 0;
}

Measured memory_bytes: 3116
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long int ll;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

int main() {
  long n;
  cin >> n;
  vector<long> v(n);
  rep (i, n) {
    cin >> v[i];
  }

  map<long, long> count;
  rep (i, n) {
    auto itr = count.find(v[i]);
    if (itr != count.end()) {
      count[v[i]]++;
    } else {
      count[v[i]] = 1;
    }
  }

  long total = 0;
  for (auto itr = count.begin(); itr != count.end(); itr++) {
    if (itr->second > 1) {
      total += (itr->second) * (itr->second - 1) / 2;
    }
  }
  // P(total);

  rep (i, n) {
    if (count[v[i]] == 1) P(total);
    else {
      long minus = count[v[i]] * (count[v[i]] - 1) / 2;
      long plus  = (count[v[i]] - 1) * (count[v[i]] - 2) / 2;
      P(total - minus + plus);
    }
  }



  return 0;
}

Measured memory_bytes: 11008
#include <iostream>
using namespace std;
const int limn=1e5+5;
int tab[limn];
int dp[limn];
int bzw(int a)
{
    if(a<0)
        return a*-1;
    else
        return a;
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        dp[i]=1e9;
    for(int i=0;i<n;i++)
    {
        cin>>tab[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=max(0,i-k);j<i;j++)
            dp[i]=min(dp[i],bzw(tab[i]-tab[j])+dp[j]);
        if(dp[i]==1e9)
            dp[i]=0;
    }
//    for(int i=0;i<n;i++)
//    {
//        cout<<dp[i]<<" ";
//    }
    cout<<dp[n-1];
    return 0;
}


Measured memory_bytes: 1024
N,M = (int(x) for x in input().split())
H   = [int(x) for x in input().split()]
Way = [[] for I in range(N)]
for T in range(0,M):
    A,B = (int(x) for x in input().split())
    Way[A-1].append(B)
    Way[B-1].append(A)
    
Count = 0
for TT in range(0,N): 
    if all(H[TT]>Ele for Ele in [H[I-1] for I in Way[TT]]):
        Count = Count+1
print(Count)

Measured memory_bytes: 29932
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>

#include <algorithm>

using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;
const ll INF = 1ll << 60;

ll MOD = 1e9 + 7;

int main()
{
    int n;
    double a;
    cin >> n;
    double ans = 0.0;

    REP(i, n)
    {
        cin >> a;
        ans += 1.0 / a;
    }

    cout << 1.0 / ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>


typedef long double ld;
typedef long long ll;
using namespace std;
const ll MX=5e5+9;
const int MAXN = 10100;
const ld pi = acos(-1);
const ll mod = 1e9+7;

//bool cmp ( int a,int b ) { return a>b; }
ll vl;
ll po ( ll a , ll b )
{
    if ( b==0 ) { return 1; }
    ll x = po ( a , b/2 );
    x *= x;
    if ( b%2 ) { x*=a; }
    return x;
}
int power(int p)
{
    if(p==0)return 1;
    if(p==1)return vl;
    if(p%2)return (vl*power(p-1))%mod;
    long long x=power(p/2);
    return (x*x)%mod;
}
int mod_inv(ll a,ll b)
{
    vl=b;
    return (a*power(mod-2))%mod;
}
ll gcd (  ll a , ll b )
{
    if ( b==0 ) return a;
    else { return gcd( b , a%b ); }
}

bool cmp ( int a ,int b ) { return (a>b); }
int dx[]={ 0 , 0 , -1 , 1 };
int dy[]={ 1 , -1 , 0 , 0 };


struct state
{
    int cost;
    int a;
    int b;
};

int dp[41][401][401];
state arr[101];
int n,a,b;

int solve ( int x , int ma , int mb )
{
    //cout<<ma<<" "<<mb<<endl;
    int &ans = dp[x][ma][mb];
    if ( ans!=-1 ) { return ans; }
    if ( ma%a==0 && mb%b==0 && ma/a==mb/b && ma!=0 && mb!=0 ) { return 0; }
    if ( x>=n ) { return 1e9; }
    ans = 1e9;
    ans = min ( ans , solve( x+1 , ma , mb ) );
    ans = min ( ans , arr[x].cost+solve( x+1 , ma+arr[x].a , mb+arr[x].b ) );
    return ans;
}

int main()
{
    memset ( dp , -1 , sizeof(dp) );

    cin>>n>>a>>b;
    for ( int i=0 ; i<n ; i++ )
    {
        int aq,bq,cq;
        cin>>aq>>bq>>cq;
        arr[i].cost=cq;
        arr[i].a=aq;
        arr[i].b=bq;
    }

    int ans = solve ( 0 , 0 , 0 );
    if ( ans==1e9 ) { ans=-1; }
    cout<<ans;


    return 0;
}


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


long long N, A[300][300];
bool useless[300][300];

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

    bool error = false;
    long long ans = 0;
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(A[i][j] > A[i][k] + A[k][j]){
                    error = true;
                }
                if(k != i && k != j && A[i][j] == A[i][k] + A[k][j]){
                    useless[i][j] = true;
                }
            }
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            if(!useless[i][j]){
                ans += A[i][j];
            }
        }
    }
    if(error){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
}
                

Measured memory_bytes: 1024
def solve():
    from sys import stdin
    f_i = stdin
    
    inf = 5000001
    
    N = int(f_i.readline())
    P = map(int, f_i.readline().split())
    X = tuple(map(int, f_i.readline().split()))
    
    # Create lists of children
    C = [[] for i in range(N)]
    for c, p in enumerate(P, start=1):
        C[p-1].append(c) # Set vertex numbers to 0-based
    
    Y = [inf] * N
    
    # Perform a depth-first search in postorder
    # Execute dp in each sub-tree
    def dfs(v):
        for c in C[v]:
            dfs(c)
        
        X_v = X[v]
        dp1 = [0] * (X_v + 1)
        dp2 = [inf] * (X_v + 1)
        for c in C[v]:
            X_c = X[c]
            Y_c = Y[c]
            for i, b in zip(range(X_c, X_v + 1), dp1):
                if b != inf:
                    dp2[i] = b + Y_c
            for i, w, dp2_i in zip(range(Y_c, X_v + 1), dp1, dp2[Y_c:]):
                tmp = w + X_c
                if tmp < dp2_i:
                    dp2[i] = tmp
            
            dp1 = dp2
            dp2 = [inf] * (X_v + 1)
        
        Y_v = min(dp1)
        Y[v] = Y_v
        return Y_v
    
    ans = dfs(0)
    if ans == inf:
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
    
solve()

Measured memory_bytes: 3956
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

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

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
  int n; cin>>n;
  ll cnt[5];
  rep(i,5) cnt[i]=0;
  rep(i,n){
    string s; cin>>s;
    if(s[0]=='M') cnt[0]++;
    if(s[0]=='A') cnt[1]++;
    if(s[0]=='R') cnt[2]++;
    if(s[0]=='C') cnt[3]++;
    if(s[0]=='H') cnt[4]++;
  }

  ll ans = 0;
  for(int i=0; i<3; i++){
    for(int j=i+1; j<4; j++){
      for(int k=j+1; k<5; k++){
        ans += cnt[i]*cnt[j]*cnt[k];
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
long n,a[200000],dp[5][200001],ans;
int main(){
    scanf("%ld",&n);
    for(int i=0;i<n;i++){
        scanf("%ld",&a[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<5;j++){
            dp[j][i+1]=dp[0][i];
            for(int k=1;k<=j;k++){
                dp[j][i+1]=min(dp[j][i+1],dp[k][i]);
            }
        }
        dp[0][i+1]+=a[i];
        dp[4][i+1]+=a[i];
        dp[2][i+1]+=(a[i]+1)%2;
        if(a[i]==0){
            dp[1][i+1]+=2;
            dp[3][i+1]+=2;
        }
        else{
            dp[1][i+1]+=a[i]%2;
            dp[3][i+1]+=a[i]%2;
        }
    }
    ans=dp[0][n];
    for(int i=1;i<5;i++){
        ans=min(ans,dp[i][n]);
    }
    printf("%ld\n",ans);
}

Measured memory_bytes: 9472
/* AtCoder My Practice
 * author: Leonardone @ NEETSDKASU
 */
#include <stdio.h>

#define N_MAX (200001)

typedef struct _range {
    int upper, lower;
    struct _range *ubound, *lbound;
} Range;

Range *newRange(int lower, int upper) {
    Range *range = (Range*)malloc(sizeof(Range));
    range->lower = lower;
    range->upper = upper;
    return range;
}

int idx[N_MAX];
long long sum;
Range range;

void calc(int value, int index) {
    Range *tmp = &range;
    long long len;
    for (;;) {
        if (tmp->lower <= index && index <= tmp->upper) {
            len = (long long)(tmp->upper - tmp->lower + 1);
            sum += (len * (len + 1LL) / 2LL) * (long long)value;
            len = (long long)(tmp->upper - index);
            sum -= (len * (len + 1LL) / 2LL) * (long long)value;
            len = (long long)(index - tmp->lower);
            sum -= (len * (len + 1LL) / 2LL) * (long long)value;
            if (tmp->lower == index) {
                tmp->lower++;
            } else if (tmp->upper == index) {
                tmp->upper--;
            } else {
                tmp->lbound = newRange(tmp->lower, index - 1);
                tmp->ubound = newRange(index + 1, tmp->upper);
                tmp->lower = tmp->upper = index;
            }
            break;
        } else if (index < tmp->lower) {
            tmp = tmp->lbound;
        } else {
            tmp = tmp->ubound;
        }
    }
}


int main(void){
    int i, n;
    
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        idx[a] = i;
    }
    
    range.upper = n - 1;
    
    for (i = 1; i <= n; i++) {
        calc(i, idx[i]);
    }
    
    printf("%lld\n", sum);

    return 0;
}


Measured memory_bytes: 5120
#include<stdio.h>
#include<string.h>
#define LEN 210005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P x){
	Q[tail] = x;
	tail++;
}
P dequeue(){
	P tmp = Q[head];
	head++;
	return tmp;
}


int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  head = 0;
  
  scanf("%d %d", &n, &q);

  for ( i = 0; i < n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }

    tail = n;

	while(head != tail) {
		u = dequeue();
		if (u.t > q) {
			u.t -= q;
			elaps += q;
			enqueue(u);
		} else {
			elaps += u.t;
			printf("%s %d\n", u.name, elaps);
		}
	}
		
  
  return 0;
}

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

int main() {
  int64_t N;
  cin >> N;
  
  int count = 0;
  int64_t ans =1;
  
  while(N/2>0){
    N/=2;
    count ++;
  }
  count ++;
  while(count > 0){
    ans*=2;
    count --;
  }
  
  cout << ans-1 << endl;
  
}

Measured memory_bytes: 3520
#include<iostream>
#include<string>
using namespace std;
 
int main(){
	int i;
	int N,L,Max=0,count=0;
	cin>>N;

	for(i=0;i<N;i++){
		cin>>L;
		count += L;
		if(Max<L){
			count += Max;
			Max = L;
			count -= Max;
		}
	}

	if(Max >= count) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;

}

Measured memory_bytes: 256
n=io.read("*n")
t,x,y={},{},{}
t[0],x[0],y[0]=0,0,0
for i=1,n do
    t[i],x[i],y[i]=io.read("*n","*n","*n")
end

feasible=true
for i=0,n-1 do
    manhattan=math.abs(x[i+1]-x[i])+math.abs(y[i+1]-y[i])
    time=t[i+1]-t[i]
    if time<manhattan then
        feasible=false
    end
    if time%2~=manhattan%2 then
        feasible=false
    end
end
if feasible then
    print("Yes")
else
    print("No")
end

Measured memory_bytes: 6516
#include<stdio.h>

int A[1000000],n;

int serch(int key){
  int left = 0,right,mid=0;
  right = n;
  
  while(left<right){
    mid = (left + right) / 2;
    
    if(key == A[mid])
      return 1;
    
    if(key > A[mid])left = mid + 1;
    
    else if(key < A[mid])right = mid;
  }
  return 0;
}


int main(){
  int i,q,k,sum = 0;
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&k);
    if(serch(k)) sum++;
  }
  
  printf("%d\n",sum);
  
  return 0;
}

Measured memory_bytes: 988
#include <bits/stdc++.h>
using namespace std;
const int maxn=5005,mod=1e9+7;
struct Edge{
	int to,nxt;
}e[2*maxn];
int cnt;
int head[maxn];
int son[maxn];
long long dp1[maxn][maxn][2],dp2[maxn][maxn][2],g[maxn];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<48||ch>57){if(ch==45)y=-1;ch=getchar();}
    while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
void add(int u,int v){
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
void dfs(int x,int fa){
	son[x]=1;
	dp1[x][1][0]=1;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int tmp=e[i].to;
		if(tmp==fa)continue;
		dfs(tmp,x);
		for(int j=1;j<=son[x];j++){
			for(int k=1;k<=son[tmp];k++){
				(dp2[x][j+k][0]+=dp1[x][j][0]*dp1[tmp][k][0]%mod+dp1[x][j][1]*dp1[tmp][k][1]%mod)%=mod;
				(dp2[x][j+k][1]+=dp1[x][j][1]*dp1[tmp][k][0]%mod+dp1[x][j][0]*dp1[tmp][k][1]%mod)%=mod;
				(dp2[x][j][0]+=dp1[x][j][0]*dp1[tmp][k][1]%mod*g[k]%mod+dp1[x][j][1]*dp1[tmp][k][0]%mod*g[k])%=mod;
				(dp2[x][j][1]+=dp1[x][j][0]*dp1[tmp][k][0]%mod*g[k]%mod+dp1[x][j][1]*dp1[tmp][k][1]%mod*g[k])%=mod;
			}
		}
		son[x]+=son[tmp];
		for(int j=1;j<=son[x];j++)dp1[x][j][0]=dp2[x][j][0],dp1[x][j][1]=dp2[x][j][1];
		for(int j=1;j<=son[x];j++)dp2[x][j][0]=dp2[x][j][1]=0;
	}
	return ;
}
int main(){
//    freopen("AT4352.in","r",stdin);
//    freopen("AT4352.out","w",stdout);
	int n;
	n=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<n;i++){
		int u,v;
		u=read();v=read();
		add(u,v);
		add(v,u);
	}
	g[0]=1;
    for(int i=2;i<=n;i+=2)g[i]=g[i-2]*(i-1)%mod;
	dfs(1,0);
	long long ans=0;
	for(int i=1;i<=n;i++)(ans+=(dp1[1][i][0]-dp1[1][i][1]+mod)%mod*g[i]%mod)%=mod;
	printf("%lld\n",ans);
    return 0;
}


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

if N == K:
    print(0)
elif N < K:
    if K - N > N:
        print(N)
    else:
        print(K-N)
else:
    if N % K == 0:
        print(0)
    else:
        p = N % K
        print(min(p, K-p))

Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long int ll;

int main(){
	string s,t; cin >> s >> t;
	bool ok=true;
	map<char,char> ma,ma2;
	for(int i=0;i<s.size();i++){
		if(ma.count(s[i])){
			if(ma[s[i]]!=t[i])ok=false;
		}
		if(ma2.count(t[i])){
			if(ma2[t[i]]!=s[i])ok=false;
		}
		ma[s[i]]=t[i],ma2[t[i]]=s[i];
	}
	if(ok){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int n; cin >> n;
	using P = pair<Int, Int>;
	vector<P> v(n);
	for(Int i=0; i<n; ++i){
		Int x, l; cin >> x >> l;
		v[i] = P(x+l, l);
	}
	sort(v.begin(), v.end());
	Int r = -1e18;
	Int cnt = 0;
	for(Int i=0; i<n; ++i){
		if(v[i].first - 2*v[i].second < r){
			++cnt;
		}else{
			r = v[i].first;
		}
	}
	cout << n - cnt << "\n";
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(void){
    int n,m,x,a=0,b=0,A,i;
    scanf("%d%d%d",&n,&m,&x);
    for(i=0;i<m;i++){
        scanf("%d",&A);
        if(A<x){
            a++;
        }else{
            b++;
        }
    }
    if(a<b){
        printf("%d\n",a);
    }else{
        printf("%d\n",b);
    }
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(void)
{
	char a,b;
	scanf("%c %c",&a,&b);

	if(a=='H')
	{
		if(b=='H') printf("H");
		else printf("D");
	}
	else 
	{
		if(b=='H') printf("D");
		else printf("H");
	}
   	return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>  // include all standard C++ libraries

using namespace std;

// Loops
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define _rrep(i,n) rrepi(i,n,0)
#define rrepi(i,a,b) for(int i=int(a)-1;i>=int(b);--i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(xi, x) for (auto&& xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)


// typedef
using ll = long long;
template <class T> using vec = vector<T>;
using vi   = vector<int>;
using vvi  = vector<vi>;
using vvvi = vector<vvi>;
using pii  = pair<int, int>;


// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second


// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase( unique(all(v)), v.end() )
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<class T> pair<T, size_t> max(vector<T> &x){ auto it = max_element(all(x)); return mp(*it, it-x.begin()); }
template<class T> pair<T, size_t> min(vector<T> &x){ auto it = min_element(all(x)); return mp(*it, it-x.begin()); }

template<class T> inline bool chmax(T &maxval, const T &newval) { if (maxval<newval) { maxval=newval; return 1; } return 0; }
template<class T> inline bool chmin(T &minval, const T &newval) { if (minval>newval) { minval=newval; return 1; } return 0; }

// Utilities
// Grid world utilities
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
#define inside(H,W,y,x) 0<=(x) && (x)<(W) && 0<=(y) && (y)<(H)

inline int in() {int x; cin >> x; return x;} // read int from cin
inline  ll IN() {ll x; cin >> x; return x;}  // read ll from cin



// Debug
#ifdef LOCAL
  #include "dump.hpp"
  #define debug(x) cerr << #x << ": " << x << '\n'
#else
  #define dump(...)
  #define debug(x)
#endif

// Paste snippets here!!

// 

int main(){
  cin.tie(0); ios::sync_with_stdio(false);    // Magic for faster cin
  int r, D, x;
  cin >> r >> D >> x;
  rep(i,10){
    x = r * x - D;
    cout << x << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
	    int a = sc.nextInt();
		int b = sc.nextInt();

		if (b % a == 0) {
			System.out.println(a + b);
		} else {
			System.out.println(b - a);
		}
	}
}

Measured memory_bytes: 21844
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
s = int(input())
a = s//3
if a == 0:
    print(0)
else:
    m = 10**9+7
    cnt = 1
    for i in range(2, a+1):
        cnt += comb(s-2*i-1, i-1)
    print(cnt%m)

Measured memory_bytes: 9124
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define inf 1000000000
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define yoi cout<<"yo"<<endl;
#define debug(x) cerr << #x << " is " << x << endl;
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int main(){
IOS;
lli a,b;
cin>>a>>b;
if(a>b)
    swap(a,b);
if(a==b){
    cout<<1<<endl;
    return 0;
}
else{
    lli x=(a+b)/2;
    if((a+b)%2){
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
    if(a-x<0)
        cout<<x<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
}
}


Measured memory_bytes: 256
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<iomanip>

#define mod 998244353
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	if (b == 0)
		return(1);
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return(sol);
}
ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
	{
		return gcd(b, a % b);
	}
}
int fun(int x)
{
	int ans = 0;
	int d = 0;
	while (x)
	{
		x = x / 10;
		d++;
	}
	if (d % 2 == 1)
		ans = 1;
	return ans;
}
void solve()
{
	int n,sol=0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		sol = sol + fun(i);
	}
	cout << sol;
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl

const int MAX = 2e5+10;
const int MAX_F = 1e6+10;

int N;
int A[MAX];

vector<pair<ll, ll>> factorize(ll N) {
    vector<pair<ll, ll>> res;
    ll n = N;
    for (ll p = 2; p*p <= n; p++) {
        if (N%p != 0) continue;
        int count = 0;
        while (N%p == 0) {
        count++;
        N /= p;
        }
        res.push_back(make_pair(p, count));
    }
    if (N != 1) res.push_back(make_pair(N, 1));
    return res;
}

vi getFactors(ll N) {
    vector<pair<ll, ll>> f = factorize(N);
    vi res;
    res.push_back(1);
    for (int i = 0; i < f.size(); i++) {
        int s = res.size();
        for (int j = 0; j < s; j++) for (int k = 0; k < f[i].second; k++) {
        res.push_back(res[j]*pow(f[i].first, k+1));
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int solve() {
    vi cnt(MAX_F);
    REP (i, N) cnt[A[i]]++;
    int ret = 0;
    FOR (a, 1, MAX_F) {
        if (cnt[a] != 1) continue;
        bool check = true;
        FORE (b, getFactors(a)) check &= (b == a || cnt[b] == 0);
        if (check) ret++;
    }
    return ret;
}

int main() {
    cout << fixed << setprecision(15);
    cin >> N;
    REP (i, N) cin >> A[i];
    cout << solve() << endl;
}

Measured memory_bytes: 12036
#include <iostream>
#include <string>
#include <functional>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;
using ll = long long;

int main()
{
	int n, t;
	cin >> n >> t;
	int cnt = 0;
	int min = 1e10;
	int urine = 0;

	for (int i = 0; i < n; ++i)
	{
		int a;
		cin >> a;

		if (min > a)
		{
			min = a;
		}

		if (a - min == urine)
			cnt++;
		if (a - min > urine)
		{
			urine = a - min;
			cnt = 1;
		}
	}

	cout << cnt << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n); i >= 0; i--)
#define revrepr(i, a, b) for (int i = (a); i >= b; i--)
#define debug(x) cerr << #x << ": " << x << "\n"

using ll = long long;
using P = pair<int, int>;

const long long MOD = 1e9+7;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

int main() {
    int n;
    cin >> n;
    vector<int> x(n);
    cin >> x;
    int min_sum = 1e9;
    rep(p, 101) {
        int sum = 0;
        rep(i, n) sum += (x.at(i) - p) * (x.at(i) - p);
        chmin(min_sum, sum);
    }
    cout << min_sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

int main(void)
{
  LL n;
  cin >> n;
  vector<tuple<string,LL,LL>> spi;
  REP(i,n) {
    string s;
    LL p;
    cin >> s >> p;
    spi.emplace_back(s,-p,i+1);
  }
  sort(spi.begin(),spi.end());
  REP(i,n) {
    LL id;
    tie(ignore,ignore,id) = spi[i];
    cout << id << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
#define dame { printf("No\n"); return 0;}
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)


struct UnionFind{
    int par[MAX];
    int kosuu[MAX];
    UnionFind(int n){
        REP(i,n) par[i]=i;
        REP(i,n) kosuu[i] = 1;
    }

    int root(int x){
        int tmp;
        if(par[x]==x) return x;
        else{
            tmp=root(par[x]);
            par[x]=tmp;
            return tmp;
        }
    }

    bool same(int x,int y){
        return root(x) == root(y);
    }

    void unite(int x,int y){
        if(not same(x,y)){ 
        kosuu[root(y)] += kosuu[root(x)];
        par[root(x)] = root(y);
        }
    }

    int renketu_kosuu(int x){
        return kosuu[root(x)];
    }
};


signed main(){
    int n,m;
    cin >> n >> m;
    vector<int> lang[m+1];
    int q;
    int tmp;
    REP(i,n){
        scanf("%lld",&q);
        REP(j,q){
            scanf("%lld",&tmp);
            lang[tmp].push_back(i);
        }

    }

    UnionFind U(n);
    FOR(i,1,m+1){
        itrfor(itr,lang[i]){
            if( itr != lang[i].end() -1){
                U.unite( *itr, *(next(itr)));
            }
        }
    }

    if(U.renketu_kosuu(1) == n){
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;



}


Measured memory_bytes: 6900
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))

    a = [0] * n
    b = [0] * n
    for i in range(n):
        if i == 0:
            a[i] = v[i]
            continue
        a[i] = a[i-1] + v[i]
    for i in reversed(range(n)):
        if i == n-1:
            b[i] = v[i]
            continue
        b[i] = b[i+1] + v[i]
    ans = INF
    for i in range(n-1):
        ans = min(ans, abs(a[i] - b[i+1]))
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 84516
s = input()
n = len(s)
sr = s[::-1]
if n % 2 == 0:
    f = s[0:(n-1)//2 + 1]
    b = s[(n+3)//2 - 1:n]
else:
    f = s[0:(n-1)//2]
    b = s[(n+3)//2 - 1:n]

fr = f[::-1]
br = b[::-1]
flag = True
if s == sr:
    pass
else:
    flag = False
if f == fr:
    pass
else:
    flag = False
if b == br:
    pass
else:
    flag = False
    
if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char a[100],b[100];
	int i,lena,lenb;
	scanf("%s %s",&a,&b);
	lena=strlen(a);
	lenb=strlen(b);
	for(i=0; i<lenb; i++)
		printf("%c%c",a[i],b[i]);
	if(lena>lenb)printf("%c",a[lena-1]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	cout << fixed << setprecision(10);
	int n;
	cin >> n;
	vector<int> x(n);
	for (int i = 0; i < n; i++) cin >> x.at(i);
	vector<int> y(n);
	for (int i = 0; i < n; i++) cin >> y.at(i);
	double sum = 0;
	for (int i = 0; i < n; i++) {
		sum += abs(x.at(i) - y.at(i));
	}
	cout << sum << endl;
	sum = 0;
	for (int i = 0; i < n; i++) {
		sum += abs(x.at(i) - y.at(i))* abs(x.at(i) - y.at(i));
	}
	sum = sqrt(sum);
	cout << sum << endl;
	sum = 0;
	for (int i = 0; i < n; i++) {
		sum += abs(x.at(i) - y.at(i)) * abs(x.at(i) - y.at(i)) * abs(x.at(i) - y.at(i));
	}
	sum = pow(sum, 0.33333333333333);
	cout << sum << endl;
	sum = 0;
	for (int i = 0; i < n; i++) {
		(sum < abs(x.at(i) - y.at(i))) ? sum = abs(x.at(i) - y.at(i)) : sum = sum;
	}
	cout << sum << endl;
}


Measured memory_bytes: 3404
k = int(input())
vals = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(", ")
print(vals[k-1])

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define N  1000


typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

using namespace std;

int main() {
	fast;
	ll n;
	cin>>n;
	ll k= floor(sqrt(n));
	cout<<k*k;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#define pb push_back
#define mpr make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ll long long
#define ld long double
#define fi first
#define se second
#define all(arr) arr.begin(), arr.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define INF 1000000001
#define inf1 1000000000000000001
#define MOD 1000000007
#define mod 1000000007
#define pie 3.14159265358979323846264338327950L
#define N 200009
#define M 1e6 + 9
#define mid(l, r) l + (r - l) / 2
#define vec vector<int>
#define vecl vector<ll>
#define umap unordered_map<ll, ll>
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define endl "\n"
#define int long long
using namespace std;
 
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};  
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
ll lcm(ll a, ll b) { return (a*b)/ gcd(a,b);}
 

 
void test_case()
{
    
    
    
    int n,k;
    cin >> n >> k;
    vector<int> a(3);
    rep(i,3) cin >> a[i];
    string s;
    cin >> s;
    vector<int> ctoi(256);
    ctoi['r']=2;
    ctoi['c']=0;
    ctoi['p']=1;
    int ans=0;
    rep(i,k){
        vector<int> x;
        for(int j=i;j<n;j+=k){
            x.push_back(ctoi[s[j]]);
        }
        vector<int> dp(2);
        int pre=-1;
        for(int nx :x){
            vector<int> p(2);
            swap(dp,p);
            dp[0]=max(p[0],p[1]);
            if(pre==nx){
                dp[1]=p[0]+a[nx];
            }else{
                dp[1]=max(p[0],p[1])+a[nx];
            }
            pre=nx;
        }
        ans+=max(dp[0],dp[1]);
    }
    cout << ans << endl;



      



 
    
}
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(20);
 
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
 
    int t = 1;
    // cin >> t;
    while (t--)
    {
        test_case();
    }
}

Measured memory_bytes: 4472
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#include <set>
using namespace std;
int a[200100];
int n,k;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
        cin>>n>>k;
        int x;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            cin>>x;
            a[x]++;
        }
        sort(a,a+200100,cmp);
        int ans=0;
        for(int i=k;a[i]!=0;i++) ans+=a[i];
        cout<<ans;

    return 0;
}

Measured memory_bytes: 1024
import java.util.*;
 
public class Main {
 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);				
		int a = sc.nextInt();		
		int robot[][] = new int[a][2];		
		for(int i=0;i<a;i++) {
			int b = sc.nextInt(), c = sc.nextInt();
			robot[i][0] = b-c;
			robot[i][1] = b+c;
		}		
		Arrays.sort(robot, Comparator.comparingInt(arr -> arr[1]));
		
		int d = 0;
		int e = Integer.MIN_VALUE;
		for(int i=0;i<a;i++) {
			if(robot[i][0] >= e) {
				d++;
				e = robot[i][1];
			}
		}		
		System.out.println(d);				
	} 
}


Measured memory_bytes: 92772
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        long[] inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
        string ans = "dangerous";

        if(inpt[2]<=inpt[1]) {
            ans = "delicious";
        } else if(inpt[2]-inpt[1]<=inpt[0]) {
            ans = "safe";
        }
        Console.WriteLine(ans);

    }





    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"



4 3 6



";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}


Measured memory_bytes: 11348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
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 gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll n;
  cin >> n;
  vi a(n);
  rep(i,n){
      cin >> a[i];
  }
  sort(all(a));
  while (a[1] != INF){
      for (ll i = 1; i < n;i++){
          if(a[i]==INF)continue;
          a[i] -= a[0] * (a[i] / a[0]);
          if(a[i]==0)a[i] = INF;
      }
      sort(all(a));
  }
  print(a[0]);
}

Measured memory_bytes: 1024
s    = gets.chomp.chars
cnt0 = 0
cnt1 = 0
ans  = 0

s.each do |c|
  if c == '0'
    if cnt1 > 0
      cnt1 -= 1
      ans += 2
    else
      cnt0 += 1
    end
  else #c == '1'
    if cnt0 > 0
      cnt0 -= 1
      ans += 2
    else
      cnt1 += 1
    end
  end
end
puts ans


Measured memory_bytes: 9596
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <numeric>


using namespace std;

using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)


using namespace std;

// R
//   B

int main() {
	int n;
	cin >> n;
	int ans = (n / 500) * 1000;
	n = n % 500;
	ans += n / 5 * 5;
	cout << ans << endl;
	return 0;

}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  ll n,m;
  cin>>n>>m;
  ll i,t,ans=0;
  priority_queue<ll> pq;
  for(i=0;i<n;i++)
  {
    cin>>t;
    pq.push(t);
  }
  while(m)
  {
    ll tmp = pq.top();
    pq.pop();
    tmp/=2;
    m--;
    pq.push(tmp);
  }
  while(!pq.empty())
  {
    ans+=pq.top();
    pq.pop();
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = __int128_t;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE

Int pow(Int a){return a * a * a * a * a;}

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  _int X;
  cin>>X;


  for(Int i=-1000;i<1000;i++)
    for(Int j=-1000;j<1000;j++){
      if(pow(i) - pow(j) == X){
        _int a = i;
        _int b = j;
        cout<<a<<" "<<b<<endl;
        return 0;

      }
    }

  return 0;
}


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

int main() {
	int S;

	cin >> S;

	int h;
	int m;
	int s;

	h = S / 3600;
	m = S % 3600 / 60;
	s = S % 3600 % 60;

	cout << h <<":" << m << ":" << s << endl;

	return 0;
}



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

using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++)cin >> a[i];
  a.erase(unique(a.begin(), a.end()), a.end());
  for(int i = 0; i < a.size(); i++)cout << (i?" ":"") << a[i];
  cout << endl;
  return 0;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


int euler_phi(int n) {
  int ret = n;
  for(int i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ret -= ret / i;
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ret -= ret / n;
  return ret;
}

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

  int n;
  cin>>n;
  cout<<euler_phi(n)<<endl;


}


Measured memory_bytes: 3200
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long llt;

const int MaxN = 3000 + 5;

int N;
llt A[MaxN];
llt dp[MaxN][MaxN];

void init() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
}

llt dfs(int l, int r) {
  if (l == r) return dp[l][r] = A[l];
  if (l > r) return dp[l][r] = 0;
  if (dp[l][r] != 0) return dp[l][r];

  dp[l][r] = A[l] + min(dfs(l + 2, r), dfs(l + 1, r - 1));
  dp[l][r] = max(dp[l][r], A[r] + min(dfs(l + 1, r - 1), dfs(l, r - 2)));
  return dp[l][r];
}

void solve() {
  llt sum = 0;
  for (int i = 1; i <= N; ++i) sum += A[i];
  cout << dfs(1, N) * 2 - sum << endl;
}

int main() {
  init();
  solve();
  return 0;
}

Measured memory_bytes: 70144
// 問題の URL を書いておく
// 

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

using ll = int64_t;

template<int Mod>
struct MintBase {
  int64_t x; // typedef long long int64_t;
  MintBase(int64_t x=0):x((x%Mod+Mod)%Mod){}
  MintBase operator-() const { return MintBase(-x);}
  MintBase& operator+=(const MintBase a) {
    if ((x += a.x) >= Mod) x -= Mod;
    return *this;
  }
  MintBase& operator-=(const MintBase a) {
    if ((x += Mod-a.x) >= Mod) x -= Mod;
    return *this;
  }
  MintBase& operator*=(const MintBase a) { (x *= a.x) %= Mod; return *this;}
  MintBase operator+(const MintBase a) const { return MintBase(*this) += a;}
  MintBase operator-(const MintBase a) const { return MintBase(*this) -= a;}
  MintBase operator*(const MintBase a) const { return MintBase(*this) *= a;}
  MintBase pow(int64_t t) const {
    if (!t) return 1;
    MintBase a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime Mod
  MintBase inv() const { return pow(Mod-2);}
  MintBase& operator/=(const MintBase a) { return *this *= a.inv();}
  MintBase operator/(const MintBase a) const { return MintBase(*this) /= a;}
};

//const int Mod = 1000000007;
//const int Mod = 998244353;

using mint = MintBase<1000000007>;

istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(int, const char**)
{
    int n;
    cin >> n;
    mint ans = 0;
    mint sums = 0;
    ll a0;
    cin >> a0;
    sums.x = a0; 
    rep(i, n - 1)
    {
        mint a;
        ll aa;
        cin >> aa;
        a.x = aa;
        ans += sums * a;
        sums += a;
    }
    cout << ans.x << endl;
    return 0;
}


Measured memory_bytes: 3616
N, K = map(int, input().split())
sunuke = [0] * N
Ans = 0
for i in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for j in A:
    sunuke[j - 1] += 1
    
for i in sunuke:
  if i == 0:
    Ans += 1
    
print(Ans)

Measured memory_bytes: 9188
#include<stdio.h>
#include<math.h>

int arr_x[1500] = {0};
int  arr_y[1500] = {0};
double dis[4];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&arr_x[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d",&arr_y[i]);
	}
	
	for(int i=0;i<3;i++){
		long long  sum = 0;
		int expon = i+1;
	for(int j=0;j<n;j++){
		long long abs_val = pow(abs(arr_x[j] - arr_y[j]),expon);
		sum += abs_val;

	}
	
	
	dis[i] = pow(sum,1.0/expon*1.0);
}

long long max = abs(arr_x[0] - arr_y[0]);
for(int i=1;i<n;i++){
	long long abs_val = abs(arr_x[i] - arr_y[i]);
	if(abs_val>max){
		max = abs_val;
	}

}
dis[3] = max * 1.0;

for(int i=0;i<4;i++){
	printf("%.8lf\n",dis[i] );
}






}


Measured memory_bytes: 2092
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<28)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
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, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int a, b, c, d;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    string s;
    cin >> s;
    rep(i, 0, s.size()) {
        if (s[i] == 'N') a++;
        else if (s[i] == 'S') b++;
        else if (s[i] == 'W') c++;
        else d++;
    }
    if ((a != 0 && b != 0 || a == 0 && b == 0) && (c == 0 && d == 0 || c != 0 && d != 0)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
def primes(n):
    i = 1
    p = [2]
    while i+2 <= n:
        flag = True
        i += 2
        for j in range(3, int(i**(1/2))+1, 2):
            if i % j == 0:
                flag = False
                break
        if flag:
            p.append(i)
    return p
n = int(input())
l = primes(55555)
l = [i for i in l if i % 5 == 1]
print(*l[:n])

Measured memory_bytes: 40560