akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>//for queue and priority_queue
#include <fstream>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#define endl "\n"
typedef long long ll;
using namespace std;
void Lancer() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
bool isPrime(ll n){
	if (n == 2 || n == 3 || n == 5)
		return true;
	else if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n == 1)
		return false;
	else {
		for (int i = 5; i <= sqrt(n); i += 2){
			if (n%i == 0)
				return false;
		}
		return true;
	}
}

int frq[123];
int main(){
	Lancer();
	ll n, mn = 10000000000, mx = -10000000000,a;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a;
		mn = min(mn, a);
		mx = max(mx, a);
	}
	mx -= mn;
	cout << mx;
	cout << endl;
	return 0;
}


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

int main(){
    int a, b, c, K;
    cin >> a >> b >> c >> K;
    if (a >= K){
          cout << K << endl;
    } else if (a+b >= K){
        cout << a << endl;
    } else {
        cout << a-(K-(a+b)) << endl;
    }
    return 0;
}

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

using ll = long long;
using Pii = std::pair<int, int>;
using Pll = std::pair<ll, ll>;

const ll INF = (ll)1e16;

using namespace std;

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

    int N, M;
    cin >> N >> M;

    bool lamp[10+1][10+1] = {};
    for (int i = 1, k; i <= M; ++i) {
        cin >> k;
        for (int j = 1, s; j <= k; ++j) {
            cin >> s;
            lamp[i][s] = 1;
        }
    }

    int cond[10+1] = {};
    for (int i = 1; i <= M; ++i) {
        cin >> cond[i];
    }

    int ans = 0;
    for (unsigned s = 0; s < (1 << N); ++s) {
        int on = 0;
        for (int i = 1; i <= M; ++i) {
            int p = 0;
            for (int j = 1; j <= N; ++j) {
                if (((s >> (j-1)) & 1) && lamp[i][j]) {
                    ++p;
                }
            }
            if (p % 2 == cond[i]) {
                ++on;
            }
        }
        if (on == M) {
            ++ans;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int i, maxv, minv, n;
	int R[200000];
	scanf("%d", &n);
	
	for(i = 0; i < n; i++){
		scanf("%d", &R[i]);
	}
	
	minv = R[0];
	maxv = -2000000000;
	
	for(i = 1; i < n; i++){
		if(maxv < R[i] - minv){
			maxv = R[i] - minv;
		}
		if(R[i] < minv){
			minv = R[i];
		}
	}
	
	printf("%d\n", maxv);
	
	return 0;
}

Measured memory_bytes: 1380
#include <stdio.h>
int main( void )
{
  int a, b, c;
  scanf("%d %d %d",&a, &b, &c);
  if( a<b && b<c ){printf("%d %d %d\n", a, b, c);}
if( a<c && c<b ){printf("%d %d %d\n", a, c, b);}
 if( b<a && a<c ){printf("%d %d %d\n", b, a, c);}
if( b<c && c<a ){printf("%d %d %d\n", b, c, a);}
if( c<a && a<b ){printf("%d %d %d\n", c, a, b);}
if( c<b && b<a ){printf("%d %d %d\n", c, b, a);}
 if( a==b && b<c  ){printf("%d %d %d\n", a, b, c);}
 if( a==c && c<b ){printf("%d %d %d\n", a, c, b);}
 if( a==b && b>c){printf("%d %d %d\n", c, a, b);}
 if( a==c&& b<a ){printf("%d %d %d\n",b, a, c );}
 if( c==b&& b<a ){printf("%d %d %d\n",b, c, a );}
 if( c==b&& b>a ){printf("%d %d %d\n", a, b, c);}
 if( a==b&&b==c ){printf("%d %d %d\n", a, b, c);}
 return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int main(void) {
	ll n, a, b; cin >> n >> a >> b;
	printf("%lld\n", min(a * n, b));
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define M 1000000007
//#define M 998244353
using namespace std;
const int inf=4e18;
const double pi=3.14159265358979;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	string s;cin>>s;
	int i,o=0,n=s.length();
	for(i=0;i<n/2;i++)
	{
		if(s[i]!=s[n-i-1])
			o++;
	}
	cout<<o<<endl;
}

Measured memory_bytes: 256
var s,t:String;a,ai,b,bi,i:Longint;
begin
	a:=200;
	readln(s);
	for i:=1 to length(s) do begin
		if a>ord(s[i]) then begin
			a:=ord(s[i]);
			ai:=1;
		end
		else if a=ord(s[i]) then
			inc(ai);
	end;
	readln(t);
	for i:=1 to length(t) do begin
		if b<ord(t[i]) then begin
			b:=ord(t[i]);
			bi:=1;
		end
		else if b=ord(t[i]) then
			inc(bi);
	end;
	if (a<b)or((a=b)and(ai<bi)and(ai=length(s)))then
		writeln('Yes')
	else
		writeln('No')
end.


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){int n,r;
cin>>n;
r=n%10;
if(r==3){cout<<"bon";return 0;}
if(r==0||r==1||r==6||r==8){cout<<"pon";return 0;}
cout<<"hon";
    return 0;}

Measured memory_bytes: 3600
n = int(input())
a = list(map(int, input().split()))
count = [0 for i in range(n+1)]
tmp = 0
for i in a:
  if i > n:
    tmp+=1
  else:
    count[i] += 1
  
ans = 0
for i in range(n+1):
  if count[i] >= i:
    ans += count[i] - i
  else:
    ans+=count[i]
print(ans+tmp)

Measured memory_bytes: 14212
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}

/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,z,w;
	cin>>n>>z>>w;
	vl a(n);
	rep(i,n)cin>>a[i];
	
	if(n==1)cout<<abs(a[0]-w)<<endl;
	else cout<<max(abs(a[n-1]-w),abs(a[n-1]-a[n-2]))<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> ac(n);
    vector<int> wa(n);
    rep(i, m) {
        int a;
        string s;
        cin >> a >> s;
        --a;
        if(s == "AC") ac[a] = 1;
        else if(ac[a] == 0) wa[a]++;
    }
    int a = 0, b = 0;
    rep(i, n) {
        a += ac[i];
        if(ac[i]) b+= wa[i];
    }
    cout << a << " " << b << '\n';
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  ll a, b, k;
  cin >> a >> b >> k;
  if (k - a >= 0)
    cout << 0 << " " << max(0LL, b - (k - a)) << endl;
  else
    cout << a - k << " " << b << endl;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chkmax(T& a,T b){return a<b?a=b,1:0;}
template<class T> inline bool chkmin(T& a,T b){return a>b?a=b,1:0;}
template<typename T> inline T& read(T& x){
	static char c; bool flag=0;
	while(!isdigit(c=getchar())) if(c=='-') flag=1;
	for(x=c-'0';isdigit(c=getchar());(x*=10)+=c-'0');
	if(flag) x=-x;
	return x;
}
const int maxn=500010;
int n,k,t[maxn],p[maxn],ind[maxn];
int head[maxn],nxt[maxn],to[maxn],e;
void ae(int x,int y){
	to[++e]=y; nxt[e]=head[x]; head[x]=e;
}
namespace SGT{
#define ls h<<1
#define rs h<<1|1
#define mid ((l+r)>>1)
#define lc l,mid
#define rc mid+1,r
	int T[maxn*3];
	void pushup(int h){
		T[h]=max(T[ls],T[rs]);
	}
	void update(int h,int l,int r,int p,int x){
		if(l==r){T[h]=x; return;}
		if(p<=mid) update(ls,lc,p,x);
		else update(rs,rc,p,x);
		pushup(h);
	}
	int query(int h,int l,int r,int L,int R){
		if(L<=l&&r<=R) return T[h];
		int ret=0;
		if(L<=mid) chkmax(ret,query(ls,lc,L,R));
		if(R>mid) chkmax(ret,query(rs,rc,L,R));
		return ret;
	}
}
using namespace SGT;
priority_queue<int,vector<int>,greater<int> > q;
int main(){
	read(n); read(k);
	for(int i=1;i<=n;i++) t[read(p[i])]=i;
	for(int i=1;i<=n;i++){
		int pre=query(1,1,n,t[i]+1,t[i]+k-1);
		update(1,1,n,t[i],i);
		if(pre) ae(t[pre],t[i]),++ind[t[i]];
	}
	for(int i=1;i<=n;i++) if(!ind[i]) q.push(i);
	for(int i=1;i<=n;i++){
		int u=q.top(); q.pop();
		t[i]=u;
		for(int j=head[u];j;j=nxt[j]){
			int v=to[j];
			if(!--ind[v]) q.push(v);
		}
	}
	for(int i=1;i<=n;i++) p[t[i]]=i;
	for(int i=1;i<=n;i++) printf("%d\n",p[i]);
	return 0;
}


Measured memory_bytes: 22260
n = int(input())

d = []
for i in range(n):
    d.append(int(input()))

d_2 = sorted(d, reverse=True)
ans = 1
for i in range(1, n):
    if d_2[i] < d_2[i-1]:
        ans += 1
    else:
        continue

print(ans)

Measured memory_bytes: 3060
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;
vector<pi>adj[M];
int dis[M];
bool vis[M];
void bfs(int src)
{
    queue<int>q;
    q.push(src);
    dis[src]=0;
    vis[src]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto x:adj[u])
        {
            int v=x.fi;
            int w=x.si;
            if(vis[v]==0)
            {

                dis[v]=dis[u]+w;
                vis[v]=1;
                q.push(v);
            }
        }
    }

}
 main()

{

    int n;
    scanf("%lld",&n);
    f(i,1,n-1)
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        adj[u].pb(mp(v,w));
        adj[v].pb(mp(u,w));
    }
    //done("chk")
    bfs(1);
   // done("chk")
    f(i,1,n)
    {
        //done(dis[i])
        if(dis[i]%2==0)
         {
             printf("0\n");
         }
         else printf("1\n");
    }
    return 0;

}





































Measured memory_bytes: 11952
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define swap(p,q) r=(p);(p)=(q);(q)=r
#define INF 1000000000000//10^12
#define INFINT 2000000001//2*10^9+1
#define ALL(a) (a).begin(),(a).end()

using namespace std;




int main(void)
{
	//変数の宣言
	int n;
	ll int t[110];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	ll int ans=0;
	int count=0;
	ll int temp,temp1,temp2;
	int max,min;
	int len;
	int sum=0;



	//データの読み込み


	scanf("%d",&n);
//	scanf_s("%d",&n);


	for(i=0;i<n;i++){
		scanf("%lld",&t[i]);
//		scanf_s("%lld",&t[i]);
	}
	
	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

	ans=t[0];
	for(i=1;i<n;i++){
		temp1=ans;
		temp2=t[i];
		while(temp1!=0&&temp2!=0){
			if(temp1>temp2){
				temp1=temp1%temp2;
			}else{
				temp2=temp2%temp1;
			}
		}
		ans=ans/(temp1+temp2)*t[i];
	}



	//	printf("計算部分終了\n");

	//出力

	printf("%lld",ans);

	//	printf("結果の出力終了\n");


	return 0;
}



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

template<typename T> class FenwickTree {
  int N, M;
  vector<T> B;
public:
  FenwickTree(int n) : N(n + 1), M(1), B(N, 0) {
    while (M * 2 <= N) M *= 2;
  }
  FenwickTree(const vector<T> &v) : N((int) v.size() + 1), M(1), B(N, 0) {
    for (int i = 0; i < N - 1; i++) add(i, v.at(i));
    while (M * 2 <= N) M *= 2;
  }
  void add(int i, T x) {
    i++;
    while (i < N) B.at(i) += x, i += i & -i;
  }
  void add(int l, int r, T x) {
    add(l, x);
    add(r + 1 , -x);
  }
  T sum(int i) {
    i++;
    T ret = 0;
    while (i > 0) ret += B.at(i), i -= i & -i;
    return ret;
  }
  T sum(int l, int r) {
    return sum(r) - sum(l - 1);
  }
  T at(int i) {
    return sum(i) - sum(i - 1);
  }
  int lower_bound(T w) {
    if (w <= 0) return 0;
    int x = 0;
    for (int k = M; k > 0; k /= 2) {
      if (x + k <= N - 1 && B.at(x + k) < w) {
        w -= B.at(x + k);
        x += k;
      }
    }
    return x;
  }
  int upper_bound(T w) {
    if (w < 0) return 0;
    int x = 0;
    for (int k = M; k > 0; k /= 2) {
      if (x + k <= N - 1 && B.at(x + k) <= w) {
        w -= B.at(x + k);
        x += k;
      }
    }
    return x;
  }
};

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  vector<long> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  FenwickTree<long> FT(A);
  while (Q--) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a) cout << FT.sum(b, c - 1) << "\n";
    else FT.add(b, c);
  }
}

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

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

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

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

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



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
#include <queue>
#include <climits>
#include<cmath>
#include <sstream>
#include <iomanip>

bool sort_pair( std::pair< int64_t, int64_t > origin, std::pair< int64_t, int64_t > another )
{
    return origin.second > another.second;
}


int main()
{

    int64_t a,b;
    
    std::cin>> a;
    std::cin>> b;

    std::priority_queue< int64_t, std::vector< int64_t >, std::greater< int64_t > > q;

    for( int i = 0; i < a; i++ )
    {
        int64_t c;
        std::cin>> c;
        q.push( c );
    }

    std::vector< std::pair< int64_t, int64_t > > list( b );

    for( int i = 0; i < b; i++ )
    {
        std::cin>> list[i].first;
        std::cin>> list[i].second;
    }

    std::sort( list.begin(), list.end(), sort_pair );

    for( int i = 0; i < b; i++ )
    {
        if( list[i].second <= q.top() )
        {
            break;
        }

        for( int r = 0; r < list[i].first; r++ )
        {
            if( q.top() < list[i].second )
            {
                q.pop();
                q.push( list[i].second );
            }
            else
            {
                break;
            }
        }
    }

    int64_t all = 0;

    while( !q.empty() )
    {
        all += q.top();
        q.pop();
    }

    std::cout<< all;
}


Measured memory_bytes: 2676
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    ll n, a;
    cin >> n >> a;
    n %= 500;
    if (n <= a)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

Measured memory_bytes: 3508
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
typedef long long ll;
using namespace std;

int main() {
	ll n,m,ans=0;
	cin>>n;
	m=n;
	while(m>0){
		ans+=m%10;
		m/=10;
	}
	if(n%ans==0){
		cout << "Yes"<<endl;
	}
	else{
		cout <<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let mut s: Vec<String> = (0..n)
        .map(|_| input::<String>().chars().collect())
        .collect();
    for i in 0..n {
        let mut t: Vec<char> = s[i].chars().collect();
        t.sort();
        s[i] = t.iter().cloned().collect();
    }

    let mut m = std::collections::HashMap::new();
    for i in 0..n {
        let e = m.entry(&s[i]).or_insert(0);
        *e += 1;
    }

    let mut ans = 0i64;
    for &v in m.values() {
        ans += v * (v - 1) / 2;
    }
    println!("{}", ans);
}


Measured memory_bytes: 16636
#include <map>
#include <algorithm>
#include <array>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <random>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
constexpr ll MOD = 1000000007;

uint N;
vector<int> sum, zero;
vector<int> get_zero(const vector<int>& l)
{
	vector<int> z(l.size() - 1);
	for (uint i = 0; i + 1 < l.size(); i++) z[i] = zero[l[i + 1]] - zero[l[i]];
	return z;
}
map<int, vector<int>> indexes(const vector<int>& x)
{
	map<int, vector<int>> dic;
	for (uint i = 0; i < x.size(); i++) dic[x[i]].emplace_back(i);
	return dic;
}
vector<ll> calc(const vector<int>& zs)
{
	auto L = zs.size();
	vector<ll> dp(L + 1, 1);
	ll sum = 1;
	for (uint j = 0; j < L; j++)
	{
		dp[j + 1] = (dp[j] + zs[j] * sum % MOD) % MOD;
		sum = (sum + dp[j + 1]) % MOD;
	}
	return dp;
}
ll pow(ll a, ll b, ll mod)
{
	ll p = 1, x = a;
	while (b > 0)
	{
		if ((b & 1L) == 1L) p = p * x % mod;
		b >>= 1;
		x = x * x % mod;
	}
	return p;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N;
	vector<int> A(N);
	for (uint i = 0; i < N; i++) cin >> A[i];
	sum = vector<int>(N + 1, 0);
	for (uint i = 0; i < N; i++) sum[i + 1] = sum[i] ^ A[i];
	zero = vector<int>(N + 2, 0);
	for (uint i = 0; i <= N; i++) zero[i + 1] = zero[i] + (sum[i] == 0 ? 1 : 0);
	auto dic = indexes(sum);
	if (sum[N]) cout << calc(get_zero(dic[sum[N]])).back() << endl;
	else
	{
		ll ans = pow(2, zero[N + 1] - 2, MOD);
		for (auto&& x: dic) if (x.first) for (auto v : calc(get_zero(x.second))) ans += v;
		cout << ans % MOD << endl;
	}
	cout << flush;
	return 0;
}


Measured memory_bytes: 38132
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	int ans=1,p=a[0];
	for(int i=1;i<n;i++)
	{
		if(a[i]<=p)
		{
			ans++;
			p=a[i];
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4416
st = input()
ab = input()
u = input()

s = st.split(' ')[0]
t = st.split(' ')[1]

a = int(ab.split(' ')[0])
b = int(ab.split(' ')[1])


if(u in s):
  a -=1
elif(u in t):
  b -= 1

print(a,b)


Measured memory_bytes: 3060
# input
l = [int(x) for x in list(input())]

N = len(l)
ans = 0

for i in range(N):
    for k in range(N - i - 1):
        ans += (2 ** i) * (2 ** (N - i - k - 2)) * (10 ** k) * l[i]
    ans += (2 ** i) * (10 ** (N - i - 1)) * l[i]

print(ans)


    

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

void PrintVector(vector<int> A, int N)
{
    for (int i = 0; i < N; i++)
    {
        if (i != N - 1)
        {
            cout << A[i] << ' ';
        }
        else
        {
            cout << A[i] << endl;
        }
    }
}

int main()
{
    int N;
    cin >> N;
    vector<int> A(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    PrintVector(A, N);
    for (int i = 1; i < N; i++)
    {
        int pivot = A[i];
        int j = i - 1;
        while ((j >= 0) && (A[j] > pivot))
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = pivot;
        PrintVector(A, N);
    }

    return 0;
}


Measured memory_bytes: 3156
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<cfloat>
using namespace std;
int mod = 1e9+7;
long long int inf = 1e18;

int main() {
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  map<string, bool> mp;
  vector<string> a;
  for(int i=0; i<n; i++){
    string t = "";
    for(int j=i; j<=i+k; j++){
      if( j == n ) break;
      t += s[j];
      if( mp.find(t) == mp.end() ){
        a.push_back(t);
        mp[t] = true;
      }
    }
  }
  sort(a.begin(), a.end());

  cout << a[k-1] << endl;

  return 0;
}

//


Measured memory_bytes: 2556
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define rep(i, n)for(int i=0; i<n; i++)

int main(){
  string S;
  cin >> S;

  if(S[2] == S[3] && S[4]==S[5])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;


  return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
A = list(map(int, input().split()))


def judge(length):
    cnt = 0
    for a in A:
        cnt += a // length
        if a % length == 0:  # ちょうど割り切れるときは切る回数が一回少なくて済む
            cnt -= 1
    return cnt <= k


ng, ok = 0, max(A)
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(mid):
        ok = mid
    else:
        ng = mid

print(ok)

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

int		main(void)
{
	int ans = 0;
	int mn = 10;

	for (int i = 0; i < 5; i++)
	{
		int tmp;

		cin >> tmp;
		if (tmp % 10 == 0)
			ans += tmp;
		else
		{
			ans += tmp + (10 - tmp % 10);
			mn = min(mn, tmp % 10);
		}
	}
	if (mn != 10)
		ans -= 10 - mn;
	cout << ans << endl;
}


Measured memory_bytes: 256
/*
power code taken from geeks for geeks
*/

#include <bits/stdc++.h>
#define MODD 1000000007LL
#define MAX_SIZE 100000000
#define MAX_N 100001
using namespace std;
typedef long long ll;

ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
double max(double a,double b){return a>b?a:b;}
double min(double a,double b){return a<b?a:b;}

ll modd(ll a){if(a<0LL) return a*-1LL;return a;}
double modd(double a){if(a<0.0) return a*-1.0;return a;}

ll modulo(ll a){return a % MODD; }

ll power(ll k, ll p){
    if (p == 0)
        return 1LL;
 
    ll P = power(k, p/2LL);
    P = (P * P) % MODD;
 
    if (p % 2 == 1)
        P = (P * k) % MODD;
 
    return P;
}


bool comp(char a, char b){
    return a>b;
}

void swap(ll& s1, ll &s2){
    ll temp=s1;
    s1=s2;
    s2=temp;
}

ll gcd(ll a, ll b){
    if(b==0){
        return a;
    }
    return gcd(b, a%b);
}

void solve(){
    ll k;
    cin>>k;
    ll ans=0;
    for(ll i=1;i<=k;i++){
        for(ll j=1;j<=k;j++){
            for(ll m=1;m<=k;m++){
                ans+=gcd(i, gcd(j,m));
            }
        }
    }
    cout<<ans<<endl;
}


int main(){




    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;

    // cin>>t;
    while(t--){
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 3664
#include<iostream>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define N 500
int width[N][N];
char m[N][N+1];

int solve(int r,int c){
  rep(i,r){
    if (m[i][0] == '.')width[i][0]=1;
    else width[i][0]=0;

    REP(j,1,c){
      if ( m[i][j]=='*')width[i][j]=0;
      else width[i][j]=width[i][j-1]+1;
    }
  }
  
  /*
  rep(i,r){
    rep(j,c)cout << width[i][j] <<" " ;
    cout << endl;
  }
  */
  int ret=0;
  rep(j,c){
    rep(i,r){
      int minwidth=width[i][j];
      if ( minwidth==0)continue;
      ret=max(ret,minwidth);
      REP(k,i+1,r){
	minwidth=min(minwidth,width[k][j]);
	if ( minwidth == 0)break;
	ret=max(ret,(k-i+1)*minwidth);
      }
    }
  }
  return ret;
}

main(){
  int r,c;
  while(cin>>r>>c && r){
    rep(i,r)cin>>m[i];
    cout << solve(r,c)<<endl;
  }
}

Measured memory_bytes: 2092
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl

int main(){
	int n;
	cin>>n;
	vector<int> x(n);
	double p=0.0;
	int a=0;
	REP(i,n){
		cin>>x[i];
		p+=x[i];
	}
	p/=n;
	a=(int)p;
	if((p-a)>=0.5) a++;
	int ans=0;
	REP(i,n){
		ans+=pow((x[i]-a),2);
	}
	OUT(ans);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int n, h;
	cin >> n >> h;
	VI a(n);
	VI b(n);
	REP(i, n) { cin >> a[i] >> b[i]; }
	int a_max = 0;
	REP(i, n) { chmax(a_max, a[i]); }
	priority_queue<int> pq;
	REP(i, n) { pq.push(b[i]); }
	int result = 0;
	while(h > 0) {
		if(pq.empty() || a_max >= pq.top()) {
			result += (h + a_max - 1) / a_max;
			break;
		}
		h -= pq.top();
		pq.pop();
		result++;
	}
	cout << result << endl;
	return 0;
}


Measured memory_bytes: 4704
#include<stdio.h>

int main(){
  int N, K;
  int A[100000];
  scanf("%d %d", &N, &K);
  for(int i=0; i<N; i++){
    scanf("%d", &A[i]);
  }

  if((N-1)%(K-1)==0){
    printf("%d\n", (N-1)/(K-1));
  }else{
    printf("%d\n", (N-1)/(K-1)+1);
  }

  return 0;
}

Measured memory_bytes: 512
//666yuchen
#include<bits/stdc++.h>
using namespace std;
int n,a[105],m,s,x,y;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i],s+=a[i];
  cin>>m;
  for(int i=1;i<=m;i++)cin>>x>>y,cout<<s+y-a[x]<<endl;
  return 0;
}

Measured memory_bytes: 256
H = int(input())

if H == 1:
  print(1)
else:
  cnt = 1

  if H > 2:
    while H >= 2:
      cnt += 1
      H = H/2

    H = 2 ** (cnt-1)

  cnt = H
  two = H

  while two/2 > 1:
    cnt += two//2
    two = two//2

  print(int(cnt+1))

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

int main(){
  vector <int> a(3);
  for (int i = 0; i < 3; i++){
    cin >> a.at(i);
  }
  
  int odd[3];
  for (int i = 0; i < 3; i++){
    odd[i] = a.at(i) % 2;
  }
  
  int odd_count = 0;
  for (int i = 0; i < 3; i++){
    odd_count += odd[i];
  }
  
  int ans = 0;
  if (odd_count == 1 || odd_count == 2){
    ans++;
    for (int i = 0; i < 3; i++){
      if (odd[i] == odd_count - 1) a.at(i)++;
    }
  }
  sort(a.begin(), a.end());
  ans += (a.at(2) - a.at(0)) / 2 + (a.at(2) - a.at(1)) / 2;
  cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

H, W = map(int, input().split())
a = ""
for i in range(H):
    a += input()

# count = {}
count_all = len(a)
count_4 = 0
count_2 = 0
count_1 = 0

for s in "abcdefghijklmnopqrstuvwxyz":
    # count[s] = a.count(s)
    c = a.count(s)
    count_4 += c//4
    c = c%4
    count_2 += c//2
    c = c%2
    count_1 += c

if W%2 == 1 and H%2 == 0:
    W, H = H, W

if W%2 == 0 and H%2 == 0:
    if count_4 < W*H//4:
        print("No")
    else:
        print("Yes")
elif W%2 == 0 and H%2 == 1:
    if count_4 < W*(H-1)//4:
        # print(count_4, W*(H-1)//4)
        print("No")
    elif 2*(count_4 - W*(H-1)//4) + count_2 < W//2:
        print("No")
    else:
        print("Yes")
else:
    if count_4 < (W-1)*(H-1)//4:
        print("No")
    elif 2*(count_4 - (W-1)*(H-1)//4) + count_2 < (W+H-2)//2:
        print("No")
    else:
        print("Yes")


Measured memory_bytes: 38404
N = int(input())
alldict = {}
nsame = 0
for i in range(N):
  tmp = list(input())
  tmp.sort()
  if ''.join(tmp) in alldict:
    alldict[''.join(tmp)] = alldict[''.join(tmp)] + 1
  else:
    alldict[''.join(tmp)] = 1

from operator import mul
from functools import reduce
def cmb(n,r):
    if n == 1:
        return 0
    r = min(n-r,r)
    if r == 0:
        return 1
    ov = reduce(mul, range(n, n-r, -1))
    un = reduce(mul, range(1, r+1))
    return ov // un

print(sum([cmb(i, 2) for i in alldict.values()]))


Measured memory_bytes: 17936
import sys

n=int(input())
a=list(map(int,input().split()))
x=1
if 0 in a:
    print(0)
    sys.exit()

for i in range(len(a)):
    x=a[i]*x
    if x>10**18:
        print(-1)
        sys.exit()
print(x if x<=10**18 else -1)


Measured memory_bytes: 21788
import java.util.*;

public class Main {

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

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] kinds = new int[m];

        for (int i = 0; i < n; i++) {
            int count = sc.nextInt();
            for (int j = 0; j < count; j++) {
                int value = sc.nextInt();
                kinds[value - 1]++;
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            if (kinds[i] == n) {
                ret++;
            }
        }
        System.out.println(ret);
    }

}

Measured memory_bytes: 22228
//部分点が狙えるかも、また、枝刈りで通ればいいなあ

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Rep(i, N) for(int i = 0; i < N; i++)
#define pb push_back

typedef pair<int, int> Pi;
#define fi first
#define se second

vector < int > G[100005];

int color[100005] = {0};
int power[100005] = {0};

int flag[100005];

int N, M;

void bfs(int sv, int sd, int c, int f) {
  
  queue < Pi > que;
  if(!color[sv]) {
    color[sv] = c;
    power[sv] = sd;
  }
  que.push(Pi(sv, sd));
  if(sd == 0) return;
  flag[sv] = f;
  
  while(!que.empty()) {
    int v = que.front().fi, d = que.front().se; que.pop();
    
    Rep(i, G[v].size()) {
      int u = G[v][i];
      
      if(!color[u]) color[u] = c;
      else if(d - 1 <= power[u]) continue;
      power[u] = d - 1;
      
      if(d > 1 && flag[u] != f) {
	flag[u] = f;
	que.push(Pi(u, d - 1));
      }
    }
  }

  return;
}

signed main()
{
  int A, B;
  int Q;
  int v[100005], d[100005], c[100005];
  
  cin >> N >> M;

  while(M--) {
    cin >> A >> B; --A, --B;
    G[A].pb(B); G[B].pb(A);
  }

  cin >> Q;
  
  //reverseしながら読み込む
  Rep(i, Q) cin >> v[Q - i - 1] >> d[Q - i - 1] >> c[Q - i - 1];

  fill_n(flag, 100005, -1);
  Rep(i, Q) {
    v[i]--;
    bfs(v[i], d[i], c[i], i);
  }

  Rep(i, N) {
    cout << color[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 12848
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())

    K = 0
    for i in range(1,10**3):
        if i * (i-1) // 2 == N:
            K = i
            break

    if K == 0:
        print("No")
        exit()
    
    S = [[] for _ in range(K)]

    i = 1
    k = 0
    cnt = 0
    while i <= N:
        S[k].append(i)
        i += 1
        cnt += 1
        if cnt == K - (k+1):
            k += 1
            cnt = 0

    j = 1
    k = 1
    cnt = 0
    col = 0
    while j <= N:
        S[k].append(j)
        j += 1
        k += 1
        cnt += 1
        if cnt == K - (col+1):
            col += 1
            k = col + 1
            cnt = 0

    print("Yes")
    print(K)

    for s in S:
        print(K - 1, *s)

    
if __name__ == "__main__":
    main()


Measured memory_bytes: 12588
//bismillahir rahmanir rahim            //Author:Fayed Anik
 
#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;
 
/*
template <typename T>  using ordered_set =
    tree<T, null_type, less<T>,   /// greater<T> for sorting decreasingly
    rb_tree_tag, tree_order_statistics_node_update>;
*/

#define         ll                          long  long
#define         lf                          double
#define         pb(x)                       push_back(x)
#define         ull                         unsigned long long
#define         sfl(a)                      scanf("%lld",&a)
#define         sf(a)                       scanf("%d",&a)
#define         pf(a)                       printf("%d\n",a)
#define         pfl(a)                      printf("%lld\n",a)
#define         FOR(x,n)                    for(ll x=1;x<=n;++x)
#define         pii                         pair< ll , ll >
#define         mp(a,b)                     make_pair(a,b)
#define         mod                         1000000007
#define         INF                         2e18
#define         f1                          first
#define         f2                          second
#define         all(v)                      v.begin(),v.end()
#define         PI                          acos(-1)
#define         printminusone               printf("-1\n")
#define         bug                         printf("bug")
#define         FILEIN                      freopen("in.txt","r",stdin)
#define         FILEOUT                     freopen("out.txt","w",stdout)
 
//ll SET(ll mask,ll pos){ return mask = (mask | (1ll<<pos)); }
//ll RESET(ll mask,ll pos){ return mask = mask & ~(1ll<<pos); }
bool CHECK(ll mask,ll pos) { return (bool) (mask & (1ll<<pos)); }
//priority_queue <ll, vector<ll>, greater<ll> > pq;

#define lim 300005

ll a[lim][62],b[lim];
ll fastexpo(ll b,ll p){
    ll res=1;
    while(p){
        if(p&1) res = (res * b)%mod;
        p=p>>1ll;
        b=(b*b)%mod;
    }
    return res;
}
int main(){
   ll n,x;
   sfl(n);
   FOR(i,n){
       sfl(x);
       b[i]=x;
       for(ll j=60;j>=0;j--){
           if(CHECK(x,j)){
               a[i][j]=a[i-1][j]+1;
           }
           else{
               a[i][j]=a[i-1][j];
           }
       }
   }
   ll ans=0,tmp;
   for(ll i=n;i>=1;i--){
       for(ll j=60;j>=0;j--){
           if(!CHECK(b[i],j)){
               tmp = (a[i][j]*fastexpo(2,j))%mod;
               ans = (tmp+ans)%mod;
           }
           else{
               tmp = ((i-a[i][j])*fastexpo(2,j))%mod;
               ans = (ans + tmp ) % mod;
           }
       }
   }
   pfl(ans);
   return 0;
}

Measured memory_bytes: 147840
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    if a[i] == 1:
        m = i
        break
l = [m - k + 1, m]
ans = 114514
for i in range(k):
    x = l[0] + i
    y = l[1] + i
    if not x < 0 and not y >= n:
        c = 1
        while True:
            if x <= 0:
                break
            x -= k - 1
            c += 1
        while True:
            if y >= n - 1:
                break
            y += k - 1
            c += 1
        if c < ans:
            ans = c
print(ans)

Measured memory_bytes: 14008
import java.io.*;
import java.util.Arrays;
class Main{
	public static void main(String[] args) throws IOException {
		int i;
		int n;
		String str;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		for(i=1; ;i++){
			str = in.readLine();
			n = Integer.parseInt(str);
			if(n==0) break;
			System.out.println("Case "+(i)+": "+n);
		}
	}
}

Measured memory_bytes: 31444
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
int const M=2e5+10,M2=1e6+10,M3=5e3+10,inf=1e9+10,mod=1e9+7;
int a[M];
main()
{
	int n;
	cin>>n;
	a[0]=2,a[1]=1;
	for(int i=2;i<=n;i++)
		a[i]=a[i-1]+a[i-2];
	cout<<a[n];
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
typedef long long ll;
typedef pair<int, int> P;
#define INF 1000000000

int maze[22][22] = {0};
int maze_cnt[22][22] = {0};
int h, w;
int bfs(int x, int y, int step){
    int maxstep = 0;
    int nextstep[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    queue<pair<int, int>> point;
    
    if (maze[x][y] == 1) return 0;
    rep(i, 22)rep(j, 22){
        maze_cnt[i][j] = INF;
    }
    maze_cnt[x][y] = 0;
    point.push(P(x, y));

    int ans = 0;
    while(!point.empty()){
        P p = point.front();point.pop();
        for (int i = 0; i < 4; i++)
        {
            P newp = P(p.first + nextstep[i][0], p.second + nextstep[i][1]);
            if (newp.first != 0 && newp.first != w+1 && newp.second != 0 && newp.second != h+1){
                if (maze_cnt[newp.first][newp.second] == INF && maze[newp.first][newp.second] == 0){
                    maze_cnt[newp.first][newp.second] =  maze_cnt[p.first][p.second] + 1;
                    point.push(newp);
                    ans = max(ans,maze_cnt[newp.first][newp.second]);
                }                    
            }
        }
    }

    //cout << x << y << ":"<< ans << endl;
    return ans; 
}

int main()
{
    cin >> h >> w;
    rep(y, h)rep(x, w){
        char wall;
        cin >> wall;
        if (wall == '#'){
            maze[x+1][y+1] = 1;
        }
    }

    int ans = 0;
    rep(y, h)rep(x, w){
        int maxstep = bfs(x+1, y+1, 0);
        ans = max(ans, maxstep);
    }
    cout << ans << endl;
}



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

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

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define xx first
#define yy second
#define sci(n) scanf("%d",&n)
#define scii(n,m) scanf("%d%d",&n,&m)
#define sciii(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scl(n) scanf("%lld",&n)
#define scll(n,m) scanf("%lld%lld",&n,&m)
#define sclll(n,m,w) scanf("%lld%lld%lld",&n,&m,&w)
#define pf(a)   printf("%d\n",a)
#define CASE(a) printf("Case %d:\n",a)
#define dbg(i) printf("yo %lld\n", i)
#define endl '\n'
#define READ  freopen("input.txt","r",stdin)
#define WRITE freopen("output.txt","w",stdout);
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define SQR(a) (a)*(a)
#define all(v) v.begin(),v.end()
#define pb push_back
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define inf INT_MAX
#define eps 1e-9

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

using namespace __gnu_pbds;
using namespace std;

#define mxn 100005


//bool vis[1LL << 19];
const ll nax=100105;
ll ar[nax],br[nax];
void solve()
{
    ll a,b,n,k=0,c,i,q=0,j,l,m,mx;
    cin>>n>>k;
    FOR(i,1,n+1)cin>>ar[i];
    for(i=n-1,ar[n+1]=mod;i>=1;i--){
        mx=mod;
        for(j=i+1,a=1;a<=k&&j<=n;j++,a++){
            mx=min(mx,abs(ar[i]-ar[j])+br[j]);
        }
        br[i]=mx;
    }cout<<br[1]<<'\n';
}
int main()
{
    //IOS;
    double start_time = clock();
    ll t=1,mex=1;
   //cin>>t;
    while(t--){
        solve();
    }
    double end_time = clock();
    //fprintf(stderr, "Time = %lf\n", (end_time - start_time) / CLOCKS_PER_SEC);
    return 0;
}


Measured memory_bytes: 1792
using System;

namespace atcoder_BegginerContest95_Question2
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int donutTypes = Int32.Parse(input[0]);
            int amountMoto = Int32.Parse(input[1]);
            int[] donut = new int[donutTypes];
            int minDonut = amountMoto;
            int sumMoto = 0;
            int numDonut = donutTypes;

            for (var i = 0; i < donutTypes; i++)
            {
                donut[i] = Int32.Parse(Console.ReadLine());
                if (minDonut > donut[i]) minDonut = donut[i];
                sumMoto += donut[i];
            }

            amountMoto -= sumMoto;
            while (true)
            {
                if (amountMoto >= minDonut)
                {
                    amountMoto -= minDonut;
                    numDonut++;
                }
                else
                {
                    break;
                }
            }
            Console.WriteLine(numDonut);
        }
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    map<string,int>mp;
    string st2;
    int n,ck=0;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
    cin >> st2;
        mp[st2]++;
        if(mp[st2]>1)
            ck=1;
    }
    if(ck==1)cout << "NO" << endl;
    else
        cout << "YES" << endl;
}



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

using namespace std;

typedef long long ll;

const int MAX = 1e5+7;

int a[MAX],dp[MAX];

int main()
{
	int n;scanf("%d", &n);
	for(int i = 0; i<n; ++i)scanf("%d", a+i), dp[i] = 1e9;
	dp[0] = 0, dp[1] = abs(a[0]-a[1]);
	for(int i = 2; i<n; ++i)
	{
		dp[i] = min(dp[i],dp[i-1]+abs(a[i-1]-a[i]));
		dp[i] = min(dp[i],dp[i-2]+abs(a[i-2]-a[i]));
	}	
	printf("%d\n", dp[n-1]);
	
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	int n;cin>>n;
	string s1,s2;cin>>s1>>s2;
	for(int i = 1; i < s1.size(); i++) {
		if (s1[i - 1] == s1[i]){
			s1.erase(s1.begin() + i - 1);
		}
		if (s2[i - 1] == s2[i]){
			s2.erase(s2.begin() + i - 1);
		}
	}

	vector<ll> dp(n + 1,0LL);
	if (s1[0] == s2[0]){
		dp[0] = 3;
	}
	else{
		dp[0] = 6;
	}
	for(int i = 1; i < s1.size(); i++) {
		if (s1[i] == s2[i]){
			if(s1[i - 1] == s2[i - 1]){
				dp[i] = 2LL * dp[i - 1];
			}
			else{
				dp[i] = dp[i - 1];
			}
		}
		else{
			if (s1[i - 1] == s2[i - 1]){
				dp[i] = 2LL * dp[i - 1];
			}
			else{
				dp[i] = 3LL * dp[i - 1];
			}
		}
		dp[i] %= mod;
	}
	cout << dp[s1.size() - 1] << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma warning (disable:4996)
#include<cstdio>
#include<cmath>
using namespace std;
int sum(int n) {
	int i = 0, s = 0, a[10] = { 0 };
	while (n>0) {
		a[i++] = n % 10;
		n /= 10;
	}
	for (; i >= 0; i--)s += a[i];
	return s;
}
int main() {
	int n;
	bool flag=0;
	scanf("%d", &n);
	for (int i = 1; i <= 5; i++)
	{
		if (n == pow(10, i)) flag = 1;
	}
	if (flag == 1) printf("10");
	else printf("%d", sum(n));
	return 0;
}


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

int main(){
  string s;cin >> s;
  if (s.at(0) == s.at(1) && s.at(0)!=s.at(2) && s.at(2) == s.at(3)) cout << "Yes";
  else if (s.at(0) != s.at(1) && s.at(0)==s.at(2) && s.at(1) == s.at(3)) cout << "Yes";
  else if (s.at(0) == s.at(3) && s.at(0)!=s.at(2) && s.at(2) == s.at(1)) cout << "Yes";
  else cout << "No";
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
    set<int> s;
    int a;
    cin>>a;
    s.insert(a);
    cin>>a;
    s.insert(a);
    cin>>a;
    s.insert(a);
    if((int)s.size()==2){
        cout<<"Yes"<<'\n';
    }
    else{
        cout<<"No"<<'\n';
    }
    return 0;
}

Measured memory_bytes: 256