akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int main()
{
	int n;
	while (scanf("%d", &n), n)
	{
		const int Inf = 1000000;
		int cost[11][11];
		for (int i = 0; i < 11; ++i)
			for (int j = 0; j < 11; ++j)
				cost[i][j] = Inf;
		for (int i = 0; i < 11; ++i)
			cost[i][i] = 0;

		int m = 0;
		for (int i = 0; i < n; ++i)
		{
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			cost[a][b] = cost[b][a] = c;
			m = max(m, max(a, b));
		}
		++m;
		for (int k = 0; k < m; ++k)
			for (int i = 0; i < m; ++i)
				for (int j = 0; j < m; ++j)
					cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);

		int no, minCost = Inf;
		for (int i = 0; i < m; ++i)
		{
			int sum = 0;
			for (int j = 0; j < m; ++j)
				sum += cost[i][j];
			if (sum < minCost)
			{
				minCost = sum;
				no = i;
			}
		}
		printf("%d %d\n", no, minCost);
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define N 200011
#define INF 0x7f7f7f7f
using namespace std;
struct apple{
	int v,nxt,flw;
}edge[N*11];
int que[N],indexx[N],dist[N],cur[N],Mac[N][2],tot,S,T,vist[N],n;
vector<int> V[N];
void addedge(int x,int y,int flw){
	edge[++tot].v=y;
	edge[tot].flw=flw;
	edge[tot].nxt=indexx[x];
	indexx[x]=tot;
}
void add(int x,int y,int flw){
	addedge(x,y,flw);
	addedge(y,x,0);
}
int bfs(){
	memset(dist,0,sizeof(dist));
	memcpy(cur,indexx,sizeof(indexx));
	dist[S]=1;
	int head=0,tail=0;
	que[++tail]=S;
	while(head<tail){
		int x=que[++head];
		int t=indexx[x],vv;
		while(t){
			vv=edge[t].v;
			if(edge[t].flw && !dist[vv]){
				dist[vv]=dist[x]+1;
				que[++tail]=vv;
			}
			t=edge[t].nxt;
		}
	}
	return dist[T];
}
int dfs(int u,int flw){
	if(u==T) return flw;
	int t=cur[u],vv,All=0;
	while(t){
		vv=edge[t].v;
		cur[u]=t;
		if(edge[t].flw && dist[vv]==dist[u]+1){
			int temp=dfs(vv,min(flw,edge[t].flw));
			if(temp){
				All+=temp;
				edge[t].flw-=temp;
				edge[((t-1)^1)+1].flw+=temp;
				flw-=temp;
				if(!flw) return All;
			}
		}
		t=edge[t].nxt;
	}
	return All;
}
int Dinic(){
	int ret=0;
	while(bfs()){
		ret+=dfs(S,INF);
	}
	return ret;
}
int solve(){
	int head=0,tail=0;
	que[++tail]=n;
	while(head<tail){
		int x=que[++head];
		int len=V[x].size();
		for(int i=0;i<len;i++){
			int y=V[x][i];
			if(vist[y]) continue;
			vist[y]=1;
			Mac[y][0]=x;
			int t=indexx[y+n],vv;
			while(t){
				vv=edge[t].v;
				if(!edge[t].flw){
					Mac[y][1]=vv;
					que[++tail]=vv;
					break;
				}
				t=edge[t].nxt;
			}
		}
	}
	for(int i=1;i<n;i++){
		if(!vist[i]) return -1;
	}
	return 1;
}
int main(){
	int m,x;
	scanf("%d",&n);S=n*2,T=n*2+1;
	for(int i=1;i<n;i++){
		add(S,i+n,1);
		scanf("%d",&m);
		for(int j=1;j<=m;j++){
			scanf("%d",&x);
			V[x].push_back(i);
			add(i+n,x,1);
		}
	}
	for(int i=1;i<n;i++) add(i,T,1);
	int t=Dinic();
	if(t!=n-1){
		printf("-1");
		return 0;
	}
	t=solve();
	if(t==-1){
		printf("-1");
		return 0;
	}
	for(int i=1;i<n;i++){
		if(Mac[i][0]>Mac[i][1]) swap(Mac[i][0],Mac[i][1]);
		printf("%d %d\n",Mac[i][0],Mac[i][1]);
	}
	return 0;
}

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

bool dp[100005];
int data[105];

int main()
{
  int n,k;

  scanf("%d%d",&n,&k);
  for(int c=0;c<n;c++)
  scanf("%d",&data[c]);
  for(int c=0;c<=k;c++)
  {
    for(int c2=0;c2<n;c2++)
    {
      if (c-data[c2]>=0&&dp[c-data[c2]]==0)
      dp[c]=1;
    }
  }
  printf("%s\n",dp[k]==1?"First":"Second");
}


Measured memory_bytes: 384
n,a,b=map(int,input().split())
p=10**9+7

def cmb(n, r):
  # 分子(n*(n-1)*...*(n-r+1))
  nume = 1
  for i in range(n-r+1, n+1):
    nume = nume * i % p
  # 分母（1*2*...*r）
  deno = 1
  for j in range(1, r+1):
    deno = deno * j % p
    d = pow(deno, p-2, p)
  return nume * d

nca = cmb(n, a)
ncb = cmb(n, b)
res = pow(2, n, p) - nca - ncb - 1
print(res%p)

Measured memory_bytes: 9180
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  ll X, yen;
  cin >> X;
  ll year = 0;
  yen = 100;
  while (yen / X < 1) {
    yen += yen / 100;
    year++;
  }
  cout << year << endl;
  return 0;
}

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

int main()
{
    int n;
    cin>>n;
    long long ans = 0;
    for(int i = 1; i<=n; i++)
        if(i%3!=0 and i%5!=0)
          ans+=i;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3596
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

int[10^^5] AS;

void main()
{
    auto N = readln.chomp.to!int;
    long r;
    foreach (i; 0..N) {
        auto A = readln.chomp.to!long;
        if (i != 0 && A > 0 && AS[i-1] > 0) {
            --A;
            ++r;
        }
        r += A/2;
        if (A%2 == 1) AS[i] = 1;
    }
    writeln(r);
}

Measured memory_bytes: 1660
import sys
input = sys.stdin.readline
n,m,c=map(int,input().split())
ans=0
b=list(map(int,input().split()))

for i in range(n):
        a=list(map(int,input().split()))
        s=c
        for j in range(m):
                s+=a[j]*b[j]
        if s>0:
                ans+=1
        else:
                continue
print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	set<tuple<string,int,int>>R;
	int N;
	cin>>N;
	for(int i=0;i<N;i++)
	{
		string s;
		int p;
		cin>>s>>p;
		R.insert(make_tuple(s,-p,i));
	}
	for(auto i=R.begin();i!=R.end();i++)
	{
		cout<<get<2>(*i)+1<<endl;
	}
}


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

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<std::vector<char> > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<std::vector<double> > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<std::vector<std::string> > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<std::vector<bool> > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std; 

int main(void)
{
    int n; cin >> n;
    string s; cin >> s;
    
    int ans = 0, x = 0;
    irep(i, n) {
        if(s[i] == 'I') {
            x++;
        } else {
            x--;
        }
        ans = max(x, ans); 
    }
    cout << ans << endl;
    return 0;
}
/** atcoder **/


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

#define             ll                      long long
#define             si(a)                   scanf("%d",&a)
#define             sii(a,b)                scanf("%d%d",&a,&b)
#define             siii(a,b,c)             scanf("%d%d%d",&a,&b,&c)
#define             s(a)                    scanf("%s",a)
#define             ss(a,b)                 scanf("%s%s",a,b)
#define             pii                     pair<int,int>
#define             pb(a)                   push_back(a)
#define             fr(i,n)                 for(int i=0;i<n;i++)
#define             pri(a)                  printf("%d ",a)
#define             bl                      printf("\n")
#define             PI                      2*acos(0.0)
#define             inf                     1000000
#define             sz                      120
#define             MOD                     1000000007
#define             base                    2147483647
#define             vsort(a)                (a.begin(),a.end())
#define             EPS                     10E-10
#define             gcd(a, b)               __gcd(a, b)
#define             lcm(a, b)               ((a)*((b)/gcd(a,b))
#define             finput                  freopen("input.txt","r",stdin)
#define             foutput                 freopen("output.txt","w",stdout)
#define             debug(a,b)              printf("%s %d ",a,b)


//const int fx[]={1,-1,0,0};
//const int fy[]={0,0,1,-1};
//const int fx[]={0,0,1,-1,-1,1,-1,1};   // Kings Move
//const int fy[]={-1,1,0,0,1,1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move


using namespace std;

int grid[sz][sz];

int main()
{

    int n,m,c;

    scanf("%d%d%d",&n,&m,&c);

    fr(i,m){
        si(grid[0][i]);
    }

   for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            si(grid[i][j]);
        }
    }

    int sum = 0;
    int cnt = 0;

    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            sum = sum+(grid[0][j]*grid[i][j]);
        }
        if((sum+c)>0) cnt++;
        sum = 0;
    }

    printf("%d\n",cnt);

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long 
#define ull unsigned long long
#define db double
#define vi vector<ll>
#define vvi vector<vector<int> >
#define vvii vector<vector<pii> >
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl "\n"
#define pii pair<ll,ll>
#define piii pair<ll,pair<ll,ll> >
#define mem(a,b) memset(a , b , sizeof a ) ; 
#define pb push_back
#define pf push_front
#define F first 
#define S second 
#define mp make_pair
#define all(v) v.begin(),v.end()

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}



#define deb1(a) cout<<#a<<"=*"<<a<<endl;
#define deb2(a) cout<<#a<<"=@"<<a<<endl;
#define deb3(a) cout<<#a<<"=#"<<a<<endl;
#define deb4(a,b) cout<<#a<<"="<<a<<" and "<<#b<<"="<<b<<endl;
#define deb5(a,b) cout<<#a<<"="<<a<<" and "<<#b<<"="<<b<<endl;


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


ll mod=1000000007;
ll vis[212345]={0};
vvi v(212345);
ll d[212345]={0};


ll pow(ll a, ll b, ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}


//extended euclidean algorithm( x is inverse of a wrt b onlt if gcd!=1)
ll gcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll x1,y1;
	ll d=gcd(b,a%b,x1,y1);
	x=y1;
	y=x1-y1*(a/b);
	return d;

}


int main()
{
speed

ll n;
cin>>n;
ll a[n];
ll s=0;
rep(i,0,n)
{
	cin>>a[i];
	s+=a[i];
	s%=mod;
}
ll z=0;
ll ss=0;
rep(i,0,n)
{	ss+=a[i];
ss%=mod;
	z+=(a[i]*((s-ss+mod)%mod))%mod;
	z%=mod;
}
cout<<z<<endl;
}



Measured memory_bytes: 9796
#include <iostream>
#include <set>
#include <unordered_map>

std::set<int> coins;
std::unordered_map<int, int> memo;

int get_minimum_count(int n) {
    if (coins.find(n) != coins.end()) {
        return 1;
    } else if (memo.find(n) != memo.end()) {
        return memo[n];
    } else {
        int min_count = n;
        for (int next : coins) {
            if (next < n) {
                min_count = std::min(get_minimum_count(n - next), min_count);
            }
        }
        min_count += 1;
        memo[n] = min_count;
        return min_count;
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    for (int i = 0; i < m; i ++) {
        int c;
        std::cin >> c;
        coins.insert(c);
    }
    std::cout << get_minimum_count(n) << std::endl;
}



Measured memory_bytes: 7252
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
	public static void main(String[] args) { 
		/**/
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int N = I.nextInt();
		int ans = 0;
		while (N>0) {
			ans+=N%10==2?1:0;
			N/=10;
		}
		O.pln(ans);
	}
	public static double max(double a, double b) {return Math.max(a, b);}
	public static double min(double a, double b) {return Math.min(a, b);}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x) {return Math.abs(x);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return max(a,b);
		return GCD(min(a,b),max(a,b)%min(a,b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}


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

int main(void){
    int n;
    cin >> n;
    while(n--){
        int a[3];
        cin >> a[0] >> a[1] >> a[2];
        bool tf=false;
        for(int b=0; b<3; b++){
            for(int c=0; c<3; c++){
                if(b==c) continue;
                for(int d=0; d<3; d++){
                    if(b==d || c==d) continue;
                    if((a[b]*a[b]+a[c]*a[c])==a[d]*a[d]) tf=true;
                }
            }
        }
        cout << (tf? "YES":"NO") << "\n";
    }
}



Measured memory_bytes: 2988
#include<bits/stdc++.h>
using namespace std;
long long dp[100];
long long lucas_num(long long n)
{
	if(n==0)
		return 2;
	if(n==1)
		return 1;
	if(dp[n]==-1)
	{
		dp[n] = lucas_num(n-1)+ lucas_num(n-2);
	}
	return dp[n];
}
int main()
{
	long long n;
	cin>>n;
	for (long long i = 0; i < 100; ++i)
	{
		dp[i] = -1;
	}
	cout<<lucas_num(n)<<endl;
	return 0;
}

Measured memory_bytes: 3580
#include <stdio.h>
int main(){
	int N;
	scanf ("%d", &N);

	char S[N + 1];
	scanf ("%s", &S);
	
	if (N % 2 == 1){
		puts ("No");
	}
	else {
		int flag = 1;
		for (int i = 0; i < N/2; i++){
			if (S[i] != S[i + N/2]){
			flag = 0;	
			}
			}
	if (flag){
		puts ("Yes");
	}
	else {
		puts ("No");
	}
}
	return 0;
}

Measured memory_bytes: 1664
#include <stdio.h> 
 
int main(void)
{
    int A[100][100] = {0}, b[100] = {0}, c[100] = {0};
    int m, n, i, j;
 
    scanf("%d %d", &n, &m);
 
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            scanf("%d",&A[i][j]);
        }
    }
 
    for(i = 0; i < m; i++)
    {
        scanf("%d", &b[i]);
    }
 
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            c[i] = c[i] + A[i][j] * b[j];
        }
    }
 
    for(i = 0; i < n; i++)
    {
        printf("%d\n",c[i]);
    }
 
    return 0;
}

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

ans = 0
from bisect import bisect, bisect_left
for b in B:
    i = bisect_left(A, b)
    j = bisect(C, b)
    ans += i * (N-j)
print(ans)

Measured memory_bytes: 23328
#include<stdio.h>
int main()
{
	int N,M,P,i;
	while(scanf("%d%d%d",&N,&M,&P),N)
	{
		int a[101]={0},s=0;
		for(i=1;i<=N;++i)scanf("%d",&a[i]),s+=a[i];
		if(a[M])printf("%d\n",s*(100-P)/a[M]);
		else puts("0");
	}
	return 0;
}

Measured memory_bytes: 0
ans = []

def paint(h, w):
    a = []
    for i in range(h):
        a.append("")
        for j in range(w):
            a[-1] += ["#", "."][(i + j) % 2]
    ans.append("\n".join(a))

while True:
    H, W = map(int, input().split())
    if H == W == 0: break

    paint(H, W)

print(("\n" * 2).join(ans), "\n", sep = "")


Measured memory_bytes: 5732
#!/usr/bin/env python3
import numpy as np

def main():
    N, K = map(int, input().split())
    A = np.array(input().split(),dtype=int)
    I = np.arange(N)# 電球番号を保持
    for i in range(K):
        B = np.zeros(N+1, int)
        # ユニバーサル関数(ufunc)を利用して一度に処理
        np.add.at(B, np.maximum(0,I-A),1)
        np.add.at(B, np.minimum(N,I+A+1),-1)
        A = B.cumsum()[:-1]
        if np.all(A == N):
            break
    print(*A)

if __name__ == "__main__":
    main()


Measured memory_bytes: 50212
#include<iostream>
#include<string>
#include<cmath>
#include <iomanip>
using namespace std;

int main()
{
  int A,B,H,M,minute;
  double A_x,A_y,B_x,B_y;
  cin>>A>>B>>H>>M;
  minute=60*H+M;
  A_x=(double)A*cos((double)minute/720.0*2.0*M_PI);
  A_y=(double)A*sin((double)minute/720.0*2.0*M_PI);
  B_x=(double)B*cos((double)minute/60.0*2.0*M_PI);
  B_y=(double)B*sin((double)minute/60.0*2.0*M_PI);
  cout << std::fixed << std::setprecision(15)<<(double)sqrt(pow(A_x-B_x,2)+pow(A_y-B_y,2)); 
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> setw(n) >> s;
  s[k - 1] = (s[k - 1] + 0x20);
  cout << s << endl;
}

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

int main(){
  string S;
  cin >> S;
  if(S.at(0)==S.at(1) || S.at(1)==S.at(2) || S.at(2)==S.at(3)){
    cout << "Bad" << endl;
  }
  else{
    cout << "Good" << endl;
  }
}

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

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

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
// clang-format on

int N;
int a[MAX_N];

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  REP(i, N) cin >> a[i];
  map<string, bool> mp;
  int freeC = 0;

  for (int i = 0; i < N; i++) {
    if (1 <= a[i] && a[i] <= 399)
      mp["gray"] = true;
    else if (400 <= a[i] && a[i] <= 799)
      mp["brown"] = true;
    else if (800 <= a[i] && a[i] <= 1199)
      mp["green"] = true;
    else if (1200 <= a[i] && a[i] <= 1599)
      mp["aqua"] = true;
    else if (1600 <= a[i] && a[i] <= 1999)
      mp["blue"] = true;
    else if (2000 <= a[i] && a[i] <= 2399)
      mp["yellow"] = true;
    else if (2400 <= a[i] && a[i] <= 2799)
      mp["orange"] = true;
    else if (2800 <= a[i] && a[i] <= 3199)
      mp["red"] = true;
    else
      freeC++;
  }

  int ans = 0;
  for (auto m : mp) {
    if (m.second > 0) ans++;
  }

  int offset = 0;
  if (ans == 0 && freeC > 0) {
    offset++;
  }

  printf("%d %d\n", ans + offset, ans + freeC);

  return 0;
}


Measured memory_bytes: 380
module Main where

import Control.Applicative
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

f bs [m, a, r, c, h] = case B.head bs of
    'M' -> [m + 1, a, r, c, h]
    'A' -> [m, a + 1, r, c, h]
    'R' -> [m, a, r + 1, c, h]
    'C' -> [m, a, r, c + 1, h]
    'H' -> [m, a, r, c, h + 1]
    _   -> [m, a, r, c,     h]

main :: IO ()
main = do
    n <- readLn
    ss <- replicateM n B.getLine
    let as = filter (>= 1) $ foldr f [0, 0, 0, 0, 0] ss
    let c3 = filter ((== 3) . length) (subsequences as)
    let ans = sum $ fmap product c3
    print ans

Measured memory_bytes: 23932
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int H,W;
    int i,j;
    while(1){
        scanf("%d %d",&H,&W);
        if(H==0&&W==0){
            break;
        }
        for(i=1;i<=H;i++){
            if(i!=1){
                printf("\n");
            }for(j=1;j<=W;j++){
                if(i==1||j==1||i==H||j==W){
                    printf("#");
                }
                else{
                    printf(".");
                }
            }
        }printf("\n");
        printf("\n");
    }
    
    return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


using namespace std;

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(int i=0;i<(int)(n);i++)
#define foi(i,k,n) for(int i=(k); i<(int)(n); i+=1)
#define fod(i,n,k) for(int i=k; i>=(int)n; i-=1)
#define fast_io ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define endl "\n"

#define int long long
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007

#define fir first
#define sec second
#define pb push_back
#define mp make_pair

typedef long long llint;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<llint> VL;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MII;
typedef set<int> SI;
string tostr(int n) {stringstream rr;rr<<n;return rr.str();}
llint toint(string s) {stringstream ss(s); llint x; ss >> x; return x;}
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//gp_hash_table<string, llint> table;


//int mpow(llint base, llint exp) {
  //base %= MOD;
  //llint result = 1;
  //while (exp > 0) {
    //if (exp & 1) result = ((llint)result * base) % MOD;
    //base = ((llint)base * base) % MOD;
    //exp >>= 1;
  //}
  //return result;
//}


//void makegraph(int n, int m){
	//int i, u, v;
	//while(m--){
		//cin>>u>>v;
		//u--, v--;
		//g[u].pb(v);
		//g[v].pb(u);
	//}
//}

//void dfs(int u, int par){
	//for(int v:g[u]){
		//if (v == par) continue;
		//dfs(v, u);
	//}
//}


// ------------------------------------------------------------------ILB----------------------------------------------------------------  //





void solve(){
	int n;
	cin>>n;
	vector<vector<int>>d(4,vector<int>(n));
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
		d[0][i]=x+y;
		d[1][i]=x-y;
		d[2][i]=-x+y;
		d[3][i]=-x-y;
	}
	for(int i=0;i<4;i++){
		sort(d[i].begin(),d[i].end());
	}
	int ans=-1e18;
	for(int i=0;i<4;i++){
		ans=max(ans,d[i][n-1]-d[i][0]);
	}
	cout<<ans;
}




int32_t main() {
	fast_io;
    int t = 1;
    //cin >> t;
    //int xx = 0
    while(t--) {
		//xx++;
		//cout << "Case ";
      solve();
    }
    return 0;
}



Measured memory_bytes: 11080
#include<iostream>
using namespace std;
int main(void){
  int n,m,i=1,j;
  for(cin>>m;i<=m;i++){
    cout<<"Case "<<i<<":"<<endl;
    for(cin>>n,j=0;j<10;j++){
      n=((n*n)%1000000)/100;
      cout<<n<<endl;
    }
  }
}

Measured memory_bytes: 2968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename T> vector<vector<T>> make_vector_2d(int n, int m, T initialValue) {
    auto r = vector<vector<T>>(n);
    for (int i = 0; i < n; i++) r[i] = vector<T>(m,initialValue);
    return r;
}
template <typename T> vector<vector<vector<T>>> make_vector_3d(int n, int m, int l, T initialValue) {
    auto r = vector<vector<vector<T>>>(n);
    for (int i = 0; i < n; i++) {
        r[i] = vector<vector<T>>(m);
        for (int j = 0; j < m; j++) r[i][j] = vector<T>(l, initialValue);
    }
    return r;
}

int main() {

    int n;
    cin >> n;
    int c500 = n / 500;
    int c5 = (n % 500) / 5;
    cout << (c500 * 1000 + c5 * 5) << endl;

    return 0;

}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, start, end) for (int i = (start); i <= (int)(end); i++)

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> okasi(n);

  rep(i,k){
    int d;
    cin >> d;
    rep(j,d){
      int a;
      cin >> a;
      okasi.at(a - 1) = 1;
    }
  }

  int counter = 0;
  rep(i,n){
    if(okasi.at(i) == 0) counter++;
  }
  cout << counter << endl;

}


Measured memory_bytes: 3636
matrix = []
for i in range(3):
    matrix.append([])
    something = input()
    for j in range(len(something)):
        matrix[i].append(something[j])
output = ""
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        if i == j:
            output += matrix[i][j]
print(output)

Measured memory_bytes: 3060
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

set <int> Sx;
int main() {
	int N, i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		int t;
		scanf("%d", &t);
		if (Sx.count(t)) Sx.erase(t);
		else Sx.insert(t);
	}
	return !printf("%d\n", (int)Sx.size());
}

Measured memory_bytes: 4864
#include <tuple>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int H[8];
typedef pair<int,double> P;
typedef tuple<double,int,int> T;
vector<P> G[30];
priority_queue<T,vector<T>,greater<T>> que;
double memo[30][1<<8];

int main(){
    int n,m,p,a,b;
    while(cin>>n>>m>>p>>a>>b,n){
        a--;b--;
        for(int i=0;i<n;i++) cin>>H[i];
        for(int i=0;i<30;i++) G[i].clear();
        for(int i=0;i<p;i++){
            int x,y,z;
            cin>>x>>y>>z;
            x--; y--;
            G[x].emplace_back(y,z);
            G[y].emplace_back(x,z);
        }
        fill(memo[0],memo[30],1e9);
        memo[a][(1<<n)-1]=0;
        que.emplace(0,a,(1<<n)-1);
        while(!que.empty()){
            auto t=que.top(); que.pop();
            double cost=get<0>(t);
            int city=get<1>(t);
            int tickets=get<2>(t);
            if(city==b){
                cout.precision(3);
                cout<<fixed<<cost<<endl;
                break;
            }
            if(cost>memo[city][tickets]) continue;
            for(int i=0;i<n;i++){
                if((1<<i)&tickets){
                    for(auto r:G[city]){
                        int to=r.first;
                        double length=cost+r.second/H[i];
                        if(memo[to][tickets^(1<<i)]>length){
                            memo[to][tickets^(1<<i)]=length;
                            que.emplace(length,to,tickets^(1<<i));
                        }
                    }
                }
            }
        }
        if(que.empty()){
            cout<<"Impossible"<<endl;
        }else{
            while(!que.empty()) que.pop();
        }
    }
    return 0;
}

Measured memory_bytes: 4044
//https://atcoder.jp/contests/dp/tasks/dp_g
#include<bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[]) {
	int n, m;
	cin >> n >> m;
	vector<int> in_d (n);
	vector<int> vis (n);
	vector<vector<int>> g (n);
	vector<int> dp (n);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		g[x-1].push_back(y-1);
		++in_d[y-1];
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (in_d[i] == 0 && !vis[i]) {
			queue<int> q;
			q.push(i);
			while (q.size()) {
				int s = q.front();
				++vis[s];
				q.pop();
				for (auto x:g[s]) {
					if (--in_d[x] == 0 && !vis[x]) {
						q.push(x);
					}
					dp[x] = max(dp[x], dp[s]+1);
					ans = max(ans, dp[x]);
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<map>
using namespace std;

int main() {
	int N;
	cin >> N;
	if (N % 2 == 0) cout << N;
	else cout << N * 2;

	return 0;
}

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

using namespace std;

#define ll long long
#define ld long double
#define mod 1000000007

vector<ll> adj[100005];
bool visited[100005];

void dfs(ll x)
{

	visited[x] = true;

	for(ll i = 0 ; i < adj[x].size() ; i++)
	{
		ll adjver = adj[x][i];

		if(!visited[adjver])
		{
			dfs(adjver);
		}

	}
}

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

	for(ll i = 0 ; i < m; i++)
	{
		ll u,v,w;
		cin>>u>>v>>w;

		u--;
		v--;

		adj[u].push_back(v);
		adj[v].push_back(u);

	}

	memset(visited,false,sizeof visited);

	ll cnt = 0;

	for(ll i = 0 ; i < n ; i++)
	{
		if(!visited[i])
		{
			cnt++;
			dfs(i);
		}
	}

	cout<<cnt<<endl;

}	

Measured memory_bytes: 8960
W,a,b = map(int,input().split())
if a<=b<=a+W or b<=a<=b+W:
  print("0")
else:
  mina=a
  maxa=a+W
  minb=b
  maxb=b+W
  print(abs(min(abs(mina-minb),abs(mina-maxb),abs(maxa-minb),abs(maxa-maxb))))

Measured memory_bytes: 3060
/*
AuThOr Gwj
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
#define biggest(A,B) A=max(A,B)
#define smallest(A,B) A=min(A,B)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
mp a[200000+2];
int cnt=0;
int main(){
	fastio;
	LL res=0;
	int t;
	cin>>t;
	while(t--){
		set<int> s;
		res=cnt=0;
		int n;
		cin>>n;
		rb(i,1,n)
		{
			s.insert(i);
			int k,l,r;
			cin>>k>>l>>r;
//			cerr<<" "<<l<<" "<<r<<endl; 
			res+=r;
			a[i]=II(l-r,k);
		}
		sort(a+1,a+1+n);
		reverse(a+1,a+1+n);
		vector<int> v;
		rb(i,1,n){
			if(a[i].FIR<0){
				break;
			}
			if(*s.begin()<=a[i].SEC){
				res+=a[i].FIR;
				a[i].FIR=-INF;
				set<int> :: IT ite=s.upper_bound(a[i].SEC);
				ite--;
				v.PB(*(ite));
				s.erase(ite);
			}
		}
		sort(ALL(v));
		rb(i,1,v.size()){
			if(*s.begin()<=v[i-1]){
				s.insert(v[i-1]);
				s.erase(s.begin());	
			}
		}
		sort(a+1,a+1+n);
		rb(i,1,n){
			if(a[i].FIR==-INF) continue;
			if(s.upper_bound(a[i].SEC)==s.end()){
				res+=a[i].FIR;
			} 
			else{
				s.erase(s.upper_bound(a[i].SEC));
			}
		}
		cout<<res<<endl;
	}
	return 0;
}
/*
1
3
2 93 78
1 71 59
3 57 96



2 1 3
*/

Measured memory_bytes: 14872
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,popcnt,avx,avx2,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef uint64_t ull;

const ll LINF = 9187201950435737471;
const ll nLINF = -9187201950435737472;
const ll INF = 2139062143;
const int nINF = -2139062144;
const ull ULINF = numeric_limits<ull>::max();
const ll MAXN = 1e8 + 15;
const ll MAXE = 5761456 + 5;
const double PI = acos(-1);
const ll MOD = 998244353;
const double EPS = 1e-8;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);

bool isEqual(double a, double b) {
    return abs(a - b) <= EPS;
}

#define all(_v) _v.begin(), _v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)(v.size())
#define sqr(_v) ((_v) * (_v))
#define vpi vector<pair<int, int>>
#define eb emplace_back
#define pb push_back
#define mod(x, m) ((x) % m + ((x) < 0  && ((x % m) != 0) ? m : 0))
#define vi vector<int>
#define pi pair<int, int>
#define minq(x, y) (x) = min(x, y)
#define maxq(x, y) (x) = max(x, y)


inline void IO() {
#if(DEBUG_LEVEL > 0)
    freopen("../input.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
}

template <typename T>
istream& operator >> (istream& in, vector<T>& a) {
    for (auto& i : a)
        in >> i;
    return in;
}

template <typename T>
ostream& operator << (ostream& out, const vector<T>& a) {
    for (auto& i : a) {
        out << i << " ";
    }
    return out;
}

template <typename T, typename D>
istream& operator >> (istream& in, pair<T, D>& a) {
    in >> a.first >> a.second;
    return in;
}

template <typename T, typename D>
ostream& operator << (ostream& out, const pair<T, D>& a) {
    out << a.first << " " << a.second;
    return out;
}

#define int ll

inline void solve() {
    int n, ans = 0;
    cin >> n;
    vi a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    reverse(all(a));
    reverse(all(b));
    for (int i = 0; i < n; ++i) {
        int x = a[i] + ans, y = b[i];
        int k = ((x + y - 1) / y) * y;
        ans += (k - x);
    }
    cout << ans;
}

signed main() {
    IO();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}






Measured memory_bytes: 4808
#include <bits/stdc++.h>
using namespace std;
typedef pair<string, string> pss;

map<pss, int> mp;

string s;
long long ans, n;

int main() {
	cin >>n >> s;
	int mid = (int)s.size() / 2, mid2 = (int)s.size() - mid;
	for (int i = 0; i < (1<<mid); i++) {
		string s1, t1;
		for (int j = 0; j < mid; j++) {
			if ((i>>j) & 1) 
				s1 += s[j];
			else 
				t1 += s[j];
		}
		reverse(t1.begin(), t1.end());
		mp[pss(s1, t1)]++;
	}
	for (int i = 0; i < (1<<mid2); i++) {
		string s1, t1;
		for (int j = 0; j < mid2; j++) {
			if ((i>>j) & 1) 
				s1 += s[j+mid];
			else 
				t1 += s[j+mid];
		}
		reverse(s1.begin(), s1.end());
		ans += mp[pss(s1, t1)];
		
	}
	cout << ans;
		
	
	
}

Measured memory_bytes: 87040
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cctype>
#include <string>
using namespace std;
int main(){
  string str,com,temp,s;
  int q,a,b,p;
  cin>>str>>q;
  for(int i=0;i<=q-1;i++){
    cin>>com>>a>>b;
    if(com=="print") {
      cout<<str.substr(a,b-a+1)<<endl;
    }
    else if(com=="reverse"){
      temp=str.substr(a,b-a+1);
      int n=temp.size();
      for(int i=0;i<=n-1;i++) {
        str[a+i]=temp[n-1-i];
      }
    }
    else if(com=="replace"){
      cin>>s;
      str=str.replace(a,b-a+1,s);
    }
  }
  return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[3];
string str;
int main(void){
    // Your code here!
    cin >> str;
    for (ll i = 0; i < str.length(); i++) {
        a[str[i] - 'a']++;
    }
    sort(a, a + 3);
    if (a[2] - a[0] <= 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    string s; cin>>s;
    int n=s.size();
    rep(i,n-1){
        if(s[i]=='A' && s[i+1]=='C'){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}


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

using namespace std;

template<typename T> class Polynomial {
private:
  vector<T> val;
	
public:
	Polynomial() {}

	Polynomial(const vector<T>& val) : val(val) {}

	Polynomial(const int n) : val(vector<T>(n, 0)) {}

	Polynomial(const int n, const T val) : val(vector<T>(n, val)) {}

	Polynomial operator+=(const Polynomial& p) {
    for (int i = 0; i < p.size(); ++i) {
      if (int(val.size()) == i) val.emplace_back(p[i]);
      else val[i] += p[i];
    }
		return *this;
	}
  
	Polynomial operator-=(const Polynomial& p) {
    for (int i = 0; i < p.size(); ++i) {
      if (int(val.size()) == i) val.emplace_back(-p[i]);
      else val[i] -= p[i];
    }
		return *this;
	}
  
	Polynomial operator*=(Polynomial p) {
		return *this = *this * p;
	}
  
	Polynomial operator+(const Polynomial& p) const {
		Polynomial res = *this;
		res += p;
		return res;
	}
	
	Polynomial operator-(const Polynomial& p) const {
		Polynomial res = *this;
		res -= p;
		return res;
	}

  // TODO FFT
	Polynomial operator*(Polynomial& p) {
		Polynomial res(size() + p.size());
    for (int i = 0; i < size(); ++i) {
      for (int j = 0; j < p.size(); ++j) {
        res[i + j] += val[i] * p[j];
      }
    }
		return res;
	}
	
  T& operator[](int i) {
    if (i >= int(val.size())) val.resize(i + 1, 0);
    return val[i];
  }

  int size() const {
    return val.size();
  }

  Polynomial identity() const {
    return Polynomial(1, 1);
  }
};

int main() {
  Polynomial<int> poly;
  poly = poly.identity();
  for (int i = 0; i < 4; ++i) poly *= Polynomial<int>(10, 1);

  int n;
  while (cin >> n) cout << poly[n] << endl;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 3*(int)1e3 + 10;

int n, t;
vector<P> a;
int dp[N][N];

int solve(int idx, int time){
   if(idx >= n or time >= t){
      return 0;
   }

   int &ans = dp[idx][time];
   if(ans != -1)
      return ans;
   
   ans = solve(idx+1, time);
   int curr = a[idx].F, deli = a[idx].S;
   if((time < t and time + curr < t) or (time < t and time + curr >= t)){
      smax(ans, solve(idx+1, time + curr) + deli);
   }
   return ans;
}

int32_t main(){_

   cin>>n>>t;
   a.resize(n);

   for (int i = 0; i < n; ++i)
   {
      cin>>a[i].F>>a[i].S;
   }

   sort(a.begin(), a.end());
   // cout<<a<<endl;
   
   memset(dp, -1, sizeof dp);
   
   cout<<solve(0, 0);

   return 0;
}

Measured memory_bytes: 71296
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1) // 2
        y = (x + n // x) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x
    elif n == 0:
        return 0
    else:
        raise ValueError("isqrt() argument must be nonnegative")


def main():
    N = int(readline())
    c = Counter(prime_factorize(N))

    ans = 0
    for power in c.values():
        ans += (isqrt(1 + 8 * power) - 1) // 2

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9484
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1010;

int a[N];

int main(){
	int a, b, c, k;
	scanf("%d%d%d%d",&a,&b,&c,&k);
	if (k <= a){
		printf("%d\n",k);
	}
	else if (k <= a + b){
		printf("%d\n",a);
	}
	else{
		printf("%d\n",a - (k - a - b));
	}
	return 0;
}

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

using namespace std;

int main()
{
    string s, t;

    cin >> s >> t;

    map<char, int> s_map;
    map<char, int> t_map;

    for (auto& c : s) {
        s_map[c] += 1;
    }
    for (auto& c : t) {
        t_map[c] += 1;
    }

    // cout << "s_map.size=" << s_map.size() << endl;
    // for (auto& e : s_map) {
    //     cout << e.first << "," << e.second << endl;
    // }
    // cout << "t_map.size=" << t_map.size() << endl;
    // for (auto& e : t_map) {
    //     cout << e.first << "," << e.second << endl;
    // }

    if (s.size() != t.size()) {
        cout << "No" << endl;
        return 0;
    }

    vector<int> s_value;
    vector<int> t_value;
    auto s_iter = s_map.begin();
    auto t_iter = t_map.begin();
    int i=0;
    for (; s_iter != s_map.end(); s_iter++, t_iter++) {
        s_value.push_back((*s_iter).second);
        t_value.push_back((*t_iter).second);
        i++;
        // cout << s_value[i] << "," << t_value[i] << endl;
        // s_iter++;
        // t_iter++;
    }

    // cout << "s_value.size=" << s_value.size() << endl;
    // for (auto& e : s_value) {
    //     cout << e << ",";
    // }
    // cout << endl;
    // cout << "t_value.size=" << t_value.size() << endl;
    // for (auto& e : t_value) {
    //     cout << e << ",";
    // }
    // cout << endl;

    sort(s_value.begin(), s_value.end());
    sort(t_value.begin(), t_value.end());

    for (int i=0; i<s_value.size(); i++) {
        if (s_value[i] != t_value[i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 776
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
	int R[MAX], n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> R[i];
	}
	int maxv = -2000000000;
	int minv = R[0];
	for (int i = 1; i < n; i++) {
		maxv = max(maxv, R[i] - minv);
		minv = min(minv, R[i]);
	}
	
	cout << maxv << endl;
	return 0;
}


Measured memory_bytes: 3868
#include <stdio.h>
int main(void){
    int row,col , i, j;
    
    //タテとヨコのマスの数を入力
    scanf("%d %d", &row, &col);
    int count_row[row],count_col[col];
    char box[row][col];
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
        //文字列の入力　空白文字を飛ばす
            scanf(" %c",&box[i][j]);
            //値の初期化
            count_row[i]=0;
            count_col[j]=0;
        }
    }
  for(i=0;i<row;i++){
    for(j=0;j<col;j++){
      if(box[i][j]=='#'){
        //i行j列目の文字が#ならrow[i]とcolumn[j]を１にする
        count_row[i]=1;
        count_col[j]=1;
      }
    }
  }
  for(i=0;i<row;i++){
    if(count_row[i]==1){
      for(j=0;j<col;j++){
        if(count_col[j]==1){
          //rowとcolumnが１のものをプリントしていく
          printf("%c",box[i][j]);
        }
      }
      //改行の場所を間違えると正しい答えにならなくなる
      printf("\n");
    }
  }
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <utility>
#include <set>
//#include <map>
#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1ll<<61 ;

void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
void fix_cout(){cout << fixed << setprecision(20) ;}
void chmax(ll &a,ll b){	if(a<b) a = b ;}
void chmin(ll &a,ll b){ if(a>b) a = b ;}

int main(){
	string s ; cin >> s ;
	ll sum = 0 ;
	for(int i=0;i<s.size();i++) sum += s.at(i)-'0' ;
	yorn(sum%9==0) ;
}


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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(10);

    string cmd;
    priority_queue<int> que;
    while (cin >> cmd) {
        if (cmd[2] == 'd') return 0;
        if (cmd[2] == 's') {
            int k;
            cin >> k;
            que.push(k);
            continue;
        }
        cout << que.top() << endl;
        que.pop();
    }
}


Measured memory_bytes: 6976
#include<stdio.h>
#include<string.h>
 
#define MAX 1001
 
int c[MAX][MAX];
int m,n;
 
void LCRLength(char *,char *);
 
int main(){
  int i,q;
  char a[MAX],b[MAX];
 
  scanf("%d",&q);
 
  for(i=1;i<=q;i++){
    scanf("%s",a);
    scanf("%s",b);
    LCRLength(a,b);
    printf("%d\n",c[m][n]);
  }
  return 0;
}

void LCRLength(char *a,char *b){
  int i,j;
 
  m=strlen(a);
  n=strlen(b);
 
  for(i=1;i<=m;i++) c[i][0]=0;
  for(j=0;j<=n;j++) c[0][j]=0;
 
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
      if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1;
      else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];
      else c[i][j]=c[i][j-1];
    }
  }
}

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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;


int main() {

    ll A, B, X;
    cin >> A >> B >> X;

    if(A > X){
        cout << "NO" << endl;
    }else if(A == X){
        cout << "YES" << endl;
    }else{
        if(B >= X - A){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }

}

Measured memory_bytes: 256