akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
    out << '(' << p.first << ',' << p.second << ')';
    return out;
}

template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
    in >> p.first >> p.second;
    return in;
}

template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}

template <class T>
ostream& operator << (ostream& out, const vector<vector<T>> &v)
{
    for (const vector<T> &x : v)
        out << x << '\n';
    return out;
}

template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
    for (const T &x : v)
        out << x << ' ';
    return out;
}

long long gcd (long long a, long long b)
{
    if (b > a)
        swap(a, b);
    return (b ? gcd(b, a % b) : a);
}

using ll   = long long;
using pii  = pair<int, int>;
using pll  = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi   = vector<int>;
using vl   = vector<long long>;
using vvi  = vector<vector<int>>;
using vvl  = vector<vector<long long>>;

#define F          first
#define S          second
#define First      first.first
#define Second     first.second
#define Third      second
#define mp         make_pair
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define per(i,b,a) for (int i = (b); i > (a); i--)
#define all(x)     x.begin(), x.end()
#define ret(x)     return cout << x, 0;
#define throwex    throw runtime_error ("Found the error.");

const int h = 1000000007;

signed main()
{
    ios::sync_with_stdio(false);
    #ifdef ONLINE_JUDGE
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.setstate(ios::failbit);
    #endif

    int n;
    cin >> n;
    vi v(n), a(n);
    cin >> v;
    for(int x : v)
        a[x-1]++;
    sort(all(a), greater<int>());
    vi f(n);
    int s = n;
    per(i,n,0)
    {
        rep(j,0,n)
        {
            if(a[j] <= i)
                break;
            a[j]--;
            s--;
        }
        f[i-1] = s / i;
    }
    int x = n - 1;
    rep(i,1,n+1)
    {
        while(x != -1 and f[x] < i)
            x--;
        cout << x + 1 << '\n';
    }
}


Measured memory_bytes: 6624
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 5;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, p[MAXN], s[MAXN], f[MAXN];
int find(int x) {
	if (f[x] == x) return x;
	else return f[x] = find(f[x]);
}
int fac[MAXN], powk[MAXN], dp[MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int main() {
	int k = 0; read(n);
	for (int i = 1; i <= n; i++)
		f[i] = i, s[i] = 1;
	for (int i = 1; i <= n; i++) {
		read(p[i]);
		k += p[i] == -1;
		if (p[i] != -1) {
			int x = find(i), y = find(p[i]);
			if (x != y) {
				f[x] = y;
				s[y] += s[x];
			}
		}
	}
	dp[0] = powk[0] = fac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = 1ll * fac[i - 1] * i % P;
		powk[i] = 1ll * powk[i - 1] * (n - 1) % P;
	}
	int ans = 1ll * n * powk[k] % P;
	for (int i = 1; i <= n; i++)
		if (f[i] == i) {
			if (p[i] == -1) {
				for (int j = n; j >= 1; j--)
					update(dp[j], 1ll * dp[j - 1] * s[i] % P);
			} else update(ans, P - powk[k]);
		}
	for (int i = 1; i <= n; i++)
		if (p[i] == -1) update(ans, P - 1ll * (s[i] - 1) * powk[k - 1] % P);
	for (int i = 2; i <= k; i++)
		update(ans, P - 1ll * dp[i] * fac[i - 1] % P * powk[k - i] % P);
	cout << ans << endl;
	return 0;
}


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


/// File input & output /////
#define fRead(x)        freopen("x.txt","r",stdin)
#define fWrite(x)       freopen ("x.txt","w",stdout)

#define mt              make_tuple
#define ld              long double
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define INF             2e16
#define PI              acos(-1.0)
#define mp              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>


#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define SQR(a)          ((a)*(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define MEM(a,x)        memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))

#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())


#define FASTIO        ios_base::sync_with_stdio(0);cin.tie(nullptr);




///..................Sort by second element in a pair in decending order............. ///
bool SortbySecDesc(const pair<long long,long long > &a, const pair<long long,long long > &b)
{
    return a.second>b.second;
}

///.........................first element of pair in descending order..........................//////
bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}



///.............................................................TEMPLATE................................................./////

int main()
{
    FASTIO;

    string st , v1 , v2 , v3 , st3;

    cin >> st;

    ll len = st.length();

    string st1 = st;


    reverse(st1.begin(),st1.end());

    if(st1==st)
    {
        for(int i=0; i<(len-1)/2; i++)
        {
            v1.pb(st[i]);
        }

       // cout << v1 << endl;


        string st2 = v1;

        reverse(st2.begin(),st2.end());

        if(st2==v1)
        {
            for(int i=((len+3)/2)-1 ; i<len; i++)
            {
                v2.pb(st[i]);
            }

            //cout << v2 << endl;

            string st3 = v2;

            reverse(st3.begin(),st3.end());

            if(st3==v2)
            {
                cout << "Yes" << endl;
                return 0;

            }
            else
            {
                cout << "No" << endl;

                return 0;
            }
        }
        else
        {
            cout << "No" << endl;
            return 0;
        }
    }
    else
    {
        cout << "No" << endl;
    }







    return 0;
}



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

int main(void) {
    int N;
    cin >> N;
    ll ans;
    ll A,B;
    ll last=0;
    for (int i=0; i<N; i++) {
        cin >> A >> B;
        if (A > last) {
            last = A;
            ans = A+B;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include                        <bits/stdc++.h>
#define   lli                   unsigned long long int
#define   ll                    long long int
#define   PI                    acos(-1.0)
#define   UNIQUE(V)             (V).erase(unique(ALL(V), (V).end()) //vector/string etc must need to be sorted
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define   ALL(V)                (V).begin(), (V).end()
#define   MEMSET(a, val)        memset(a, val, sizeof(a))
using     namespace             std;


template  <class T> T GCD(T a, T b) { return (b != 0 ? GCD <T> (b, a%b) : a); }
template  <class T> T LCM(T a, T b) { return ((a*b)  / GCD <T> (a, b)); }


int main()
{
//  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    timesave;

    //while(1){

    int a, b;

    cin >> a >> b;

    if(a <= 5) cout << 0 << endl;
    else if(a >= 6 && a <= 12) cout << b/2 << endl;
    else cout << b << endl;

    //}

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
    in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
    in int read()
    {
        int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;
        x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;
    }
    in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
    in int gs(char *s) {char c,*t=s;while(c=gc(),c<=32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
    in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
    in void flush() {if(C>1<<22) ot();}
    template <typename T>
    in void write(T x,char t)
    {
        int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
        if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
    }
    in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
#define pb push_back
const int N=55;
int n,x,d,mx,L;ll f[N*N*N],ans;
vector<int>e[N];
struct did{ll v;int w,id;in bool operator<(did a)const{return w*a.v>a.w*v;}}a[N];
void dfs(int u)
{
	a[u].id=u,a[u].w=1;
	for(int v:e[u]) dfs(v),a[u].v+=a[v].v,a[u].w+=a[v].w;
}
int main()
{
	n=read(),x=read(),d=read();a[1].v=read();mx=n*n*n;L=min(n,d);
	for(int i=2;i<=n;i++) a[i].v=read(),e[read()].pb(i);
	memset(f,63,sizeof(f));f[0]=0;dfs(1);
	for(int i=1;i<=n;i++)
	{
		int x=L;
		for(int j=0;1<<j<=x;j++)
		{
			int w=a[i].w*(1<<j);ll v=a[i].v*(1<<j);
			for(int k=mx;k>=w;k--) f[k]=min(f[k],f[k-w]+v);
			x-=1<<j;
		}
		if(x)
		{
			int w=a[i].w*x;ll v=a[i].v*x;
			for(int j=mx;j>=w;j--) f[j]=min(f[j],f[j-w]+v);
		}
	}
	sort(a+1,a+n+1); while(a[n].id^1) n--;
	for(int i=0;i<=mx;i++) if(f[i]<=x)
	{
		ll w=i,v=f[i];
		for(int j=1;j<=n;j++)
		{
			ll c=min(j<n?(ll)d-L:(ll)1e18,(x-v)/a[j].v);
			w+=c*a[j].w,v+=c*a[j].v;
		}
		ans=max(ans,w);
	}
	write(ans,'\n');
	return ot(),0;
}
//Author: disangan233


Measured memory_bytes: 4868
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main(void)
{
	int n,i,a,sum=0,sin=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		cin>>a;
		if(a==1){
			sum++;
		}
		else{
			sin=max(sum,sin);
			sum=0;
		}
	}
	sin=max(sum,sin);
	cout<<sin+1<<endl;
	return 0;
}


Measured memory_bytes: 3256
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# データ構造：ヒープ
import heapq
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)

# エントリーポイント
def main():
    N, M = input([int, 2])
    A = input([int, N])

    que = heapque()
    for a in A:
        que.push(-a)
    
    for _ in range(M):
        que.push(-(-que.pop() // 2))

    print(-sum(que.que))
    
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 18764
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
Int StoH(const string &s){
  const Int B = 1777771;
  Int res = 0;
  for(char ch:s) res = (res * B + ch)%mod;
  return res;
}

Int BittoH(string &s,Int l,Int r,Int bit){
  const Int B = 1000000009;
  string a, b;
  for(Int i=l;i<r;i++)
    if(bit>>i&1) a += s[i];
    else b += s[i];
  Int ah = StoH(a);
  Int bh = StoH(b);
  return (ah * B + bh);
}

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

  Int n;
  cin>>n;
  string s;
  cin>>s;

  map<Int,Int> cnt;
  for(Int i=0;i<(1<<n);i++) cnt[BittoH(s, 0, n,i)]++;

  Int ans = 0;
  string rs = s;reverse(rs.begin(),rs.end());
  for(Int i=0;i<(1<<n);i++){
    Int hash = BittoH(rs, 0, n, i);
    ans += cnt[hash];
  }
  cout<<ans<<endl;
  
  
  return 0;
}


Measured memory_bytes: 33024
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int ans[maxn];

void solve() {
    rep(x, 1, 100) {
        rep(y, 1, 100) {
            rep(z, 1, 100) {
                ++ans[x * x + y * y + z * z + x * y + y * z + z * x];
            }
        }
    }
    int n;
    cin >> n;
    rep(i, 1, n)cout << ans[i] << '\n';
}

signed main() {
    start;
    while (T--)
        solve();
    return 0;
}

Measured memory_bytes: 4056
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    if (args.length > 0 && args(0) == "TEST") {
      println(test())
    } else {
      val input = io.Source.stdin.getLines().mkString("\n")
      println(solve(input).trim())
    }
  }

  def solve(input: String): String = {
    val s: Scanner = new Scanner(input)
    List.fill(3)(s.nextInt()).sorted.take(2).sum.toString
  }

  val tests = List(
    """1 3 4""".stripMargin -> """4""",
    """3 2 3""".stripMargin -> """5"""
  )

  def test(): String = tests.map { case (i, o) => (i.trim(), o.trim()) }
    .zipWithIndex.map {
    case ((input, outputExpect), i) =>
      val output = solve(input).trim()
      val tnum = i + 1
      s"test$tnum:" + (
        if (output == outputExpect) "Passed"
        else s"Failed\nexpect:\n$outputExpect\noutput:\n$output")
  }
    .mkString("\n")
}

Measured memory_bytes: 25932
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ld long double
#define ull unsigned long long int
#define ll long long int
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007ll
#define rep(i,L,R) for(i=L;i<R;i++)
#define DEBUG
#ifdef DEBUG
#define deb2(args...) {dbg,args; cerr<<endl;}
#else
#define deb2(args...)
#endif
struct debb{template<typename T> debb& operator,(const T &v){cerr<<v<<" ";return *this;}}dbg;
#define deb1(args...) do {cerr << #args << " : "; dbg,args; cerr << "\n";} while(0)
#define printa(a,L,R) rep(i,L,R) cout << a[i] <<' ';cout<<"\n";
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
template<typename T>T gcd(T a,T b){if(b==0)return a;else return gcd(b,a%b);}
template<typename T>T lcm(T a,T b){return a/gcd(a,b)*b;}
ll power(ll x,ll y,ll p){ll res=1;x=x%p;while(y>0){if(y&1)res=((res%p)*(x%p))%p;y=y>>1;x=(x*x)%p;}return res;}
ll pow1(ll x,ll y){ll res=1;while(y>0){if(y&1)res=(res*x);y=y>>1;x=x*x;}return res;}
const ll INF = 1e18l+10,N = 1e5+10,MAX = 5000000;
#define sq(X) ((X)*(X))

int main()
{
    ll n,i,s=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if(i%3==0||i%5==0)
        continue;
        else s+= i;
    }
    cout<<s<<"\n";
}

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

int main(){
  int a[56]={271,281,311,331,11,401,421,431,461,491,521,541,41,571,601,631,641,61,661,71,691,701,751,761,101,811,821,881,911,941,971,991,1021,1031,151,1051,1061,1091,1151,1171,181,191,1181,1201,1231,211,1291,1301,1321,1361,1381,241,251,1451,1471};
  int n;
  scanf("%d",&n);
  int ans[56]={0};
  for(int i=0;i<n;i++){
    ans[i]=a[i];
  }
  for(int i=0;i<n-1;i++){
    printf("%d ",ans[i]);
  }
  printf("%d\n",ans[n-1]);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
    int j=0, i = 0, n, v[100000], aux, qtd = 0;
    cin >> n;
    for(i; i<n; i++){
        cin >> v[i];
    }
    while (j < n){
        if(j+1 == v[j]){
            aux = v[j];
            v[j+1] = aux;
            v[j] = v[j+1];
            qtd++;
        }
        j++;
    }
    cout << qtd;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		long ans = solve();
		System.out.println(ans);
	}

	public static long solve() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		int[][] dist = new int[n][n];
		boolean[][] path = new boolean[n][n];

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

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				path[i][j] = true;
			}
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j || k == i || k == j) continue;
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						return -1;
					}
					if (dist[i][j] == dist[i][k] + dist[k][j]) {
						path[i][j] = path[j][i] = false;
					}
				}
			}
		}

		long total = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i + 1; j++) {
				if (path[i][j] == true) total += dist[i][j];
			}
		}
		return total;
	}
}

Measured memory_bytes: 52196
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define int long long
using P = pair<int,int>;

signed main(){
  int n;
  cin >> n;
  vector<P> res;
  int dame = n;
  if(n % 2 == 1) dame--;

  for(int i = 1;i<= n;i++){
    for(int j = 1;j <= n;j++){
      if(i >= j || j == dame) continue;
      res.push_back(P(i,j));
    }
    dame--;
  }
  cout << res.size() << endl;
  for(auto p:res){
    cout << p.first << " " << p.second << endl;
  }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a)
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;

inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=205;
//i_am_noob
int t,n,a[maxn],pos[63];
string str;
vector<int> vec;
set<int> st;
bool flag;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n;
        rep(n) cin >> a[i];
        cin >> str;
        reverse(a,a+n);
        reverse(all(str));
        if(str[0]=='1'){
            print1(1);
            continue;
        }
        vec.clear();
        flag=false;
        rep(n){
            vec.pb(a[i]);
            st.clear();
            rep3(j,62,0){
                rep1(k,sz(vec)){
                    if((vec[k]&pow2(j))&&st.count(k)==0){
                        rep1(l,sz(vec)) if((vec[l]&pow2(j))&&l!=k) vec[l]^=vec[k];
                        st.insert(k);
                        break;
                    }
                }
            }
            if(str[i]=='0') if(!vec.back()) vec.pop_back();
            if(str[i]=='1') if(vec.back()){
                print1(1);
                flag=true;
                break;
            }
        }
        if(!flag) print1(0);
    }
	return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

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

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, k;
map<ll, ll> mp;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> k;
  ll sum = 0;
  mp[0] = 1;
  REP(i, n) {
    ll tmp;
    cin >> tmp;
    sum = (sum + (tmp % k)) % k;
    mp[sum]++;
  }

  ll ans = 0;
  for(auto x : mp) {
    if(x.second > 1) ans += x.second * (x.second - 1) / 2;
  }

  cout << ans << endl;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define MAX_V 100000
#define rep(i,n) for(int i=0;i<n;i++)
vector<int> ans;
vector<int>  g[MAX_V];

void dfs(vector<bool>& used,int s){
	used[s] = false;
	rep(i,g[s].size() ){
	if(used[g[s][i]])	{
		dfs(used,g[s][i]);
	//	cout<<i<<endl;
	}
	}
	ans.push_back(s);
	return;
}
void	tsort(int v){
	vector<bool> used(v,true);
	rep(i,v){
	if(used[i]){
	dfs(used,i);
	}
	}
	//rep(i,v)if(used[i])cout<<i<<endl;
	return ;
}
int main(){
	int v,e;
	cin>>v>>e;
	//vector<vector<int> > g(v);	
	int s,t;
	rep(i,e){
	cin>>s>>t;
	s--,t--;
	g[s].push_back(t);
	}
	tsort(v);
	for(int i=ans.size()-1;i>=0;i--)cout<<ans[i]+1<<endl;	

return 0;
}





Measured memory_bytes: 5508
import java.util.Scanner;

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

        int N = scanner.nextInt();
        int num = N / 1000 + (N % 1000 == 0 ? 0 : 1);

        System.out.println(1000*num - N);
    }
}


Measured memory_bytes: 27060
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,a,b) for (int i = (a); i < (b); i++ )
typedef pair<int,int> P;
typedef long long ll;
const int INF = 100000000;

int main() {
  int K;
  cin >> K;
  int A,B;
  cin >> A >> B;
  
  bool ans = false;
  rep(i,A,B+1) {
    if (i%K==0) {
      ans = true;
      break;
    }  
  }
  if (ans) {
    cout << "OK" << endl;
  }
  else {
    cout << "NG" << endl;
  }
    
}

Measured memory_bytes: 3644
n=int(input())
h=list(map(int,input().split()))
ans = [1234567890123]*n
ans[0]=0
ans[1]=ans[0]+abs(h[1]-h[0])
for i in range(2,n):
    ans[i] = min(ans[i-1]+abs(h[i]-h[i-1]),ans[i-2]+abs(h[i]-h[i-2]))
print(ans[n-1])

Measured memory_bytes: 13904
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N + 2);
	int res = 0;
	A[0] = 0;
	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i + 1];
	}
	A[N + 1] = 0;
	for (int i = 0; i < N + 1; i++) {
		sum += abs(A[i + 1] - A[i]);
	}
	for (int i = 1; i <= N; i++) {
		cout << sum - abs(A[i + 1] - A[i]) - abs(A[i] - A[i - 1]) + abs(A[i + 1] - A[i - 1]) << endl;
	}
}

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

int c, n, m;
bool p[1010][1010];

bool is_same(int y, int x) {
  if (y >= m) y = n - y - 1;
  if (x >= m) x = n - x - 1;
  int xx = n - x - 1;
  int yy = n - y - 1;
  return p[y][x] == p[yy][x] &&
         p[y][x] == p[y][xx] &&
         p[y][x] == p[yy][xx];
}

int main() {
  int ans = 0;

  cin >> c >> n;
  m = n / 2;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      scanf("%1d", &p[i][j]);
    }
  }

  int cnt = 0;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < m; ++j) {
      if (!is_same(i, j)) cnt++;
    }
  }

  if (cnt == 0) ans++;

  while (--c) {
    int d;
    cin >> d;

    for (int i = 0; i < d; ++i) {
      int y, x;

      cin >> y >> x;
      y--; x--;

      bool pre = is_same(y, x);
      p[y][x] ^= 1;
      if (pre != is_same(y, x)) {
        if (pre) {
          cnt++;
        } else {
          cnt--;
        }
      }
    }

    if (cnt == 0) ans++;
  }

  cout << ans << endl;
}

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

bool is_prime(int x){
    switch (x){
        case 0:
        case 1:return false;
    }
    for (int i = 2;i < x;i++){
        if(x%i==0) return false;
    }
    return true;
}


int main() {
    int x;
    cin >> x;
    bool can=true,can2;
    while(can){
        can2=is_prime(x);
        if(can2) break;
        x++;

    }
    cout << x << endl;
    }
   



Measured memory_bytes: 256
s = input()
answer = 0
s =s.split(" ")
R = int(s[0])
G = int(s[1])
B = int(s[2])
N = int(s[3])

def turukame(g,b,n):
    ans = 0
    for j in range(n//g+1):
        if (n-g*j) % b == 0:
            ans = ans + 1
    return ans


for i in range(N // R+1):
    answer = answer + turukame(G,B,N-R*i)

print(answer)


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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
constexpr int INF = 1001001001;
//constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;



struct edge {
    int to, cost;
    edge(int a, int b) {to = a; cost = b;}
};
const int MAXV = 10000;
int V;
vector<edge> G[MAXV];
int d[MAXV]; //sからの最短距離を保存する

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    fill(d, d + V, INF);
    d[s] = 0;
    q.push(pii(0, s));

    while (!q.empty()) {
        pii p = q.top(); q.pop();
        int v = p.second;
        if (d[v] > p.first) {
            //cout << "aa" << endl;
            continue;
        }

        for (auto e : G[v]) {
            if (d[e.to] > d[v] + e.cost) {
                //cout << "bb " << endl;
                d[e.to] = d[v] + e.cost;
                q.push(pii(d[e.to], e.to));
            }
        }
    }
}


int main() {
    int N, M; cin >> N >> M;
    vi a(1005,0), b(1005,0), c(1005, 0);

    rep(i, M) {
        cin >> a[i] >> b[i];
        rep(j, b[i]) {
            int x; cin >> x;
            x--;
            c[i] += (1 << x);
        }
        //cout << c[i] << endl;
    }

    rep(i, 1 << N) {
        rep(j, M) {
            if (i < (i | c[j])) {
                //cout << i << " " << (i | c[j]) <<  " " << a[j] << endl;
                G[i].pb(edge((i | c[j]), a[j]));
            }
        }
        /*for(auto e : G[i]){
            cout << i  << " " <<  e.to << " " << e.cost << endl;
        }*/
    }

    V = (1 << 12);
    dijkstra(0);

    /*rep(i,4){
        cout << d[i] << endl;
    }*/
    cout << (d[(1 << N) - 1] != INF ? d[(1 << N) - 1] : -1) << endl;

}

Measured memory_bytes: 33408
K=int(input())-1
A=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(A[K])

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

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;

  int ans = n;
  rep(i,n){
  	if(s[i] == s[i+1]) --ans;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
from collections import Counter


def main():
    N = int(input())
    A = map(int, input().split())
    c = Counter(A)

    x = [
        (num, count, count - num)
        for num, count in c.items()
        if count != num
    ]

    ans = 0
    for num, count, diff in x:
        if diff > 0:
            ans += diff
        else:
            ans += count
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 24688
#include <stdio.h>
int fibonacci(int);

int F[44];

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

  for(i=0;i<n;i++){
    F[i] = 0;
  }
  
  m = fibonacci(n);

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

  return 0;
}

int fibonacci(int n)
{
  if(n==0 || n==1) return F[n] = 1;
  if(F[n]!=0) return F[n];
  return F[n] = fibonacci(n-2) + fibonacci(n-1);
}



  

  



Measured memory_bytes: 2108
package main

import (
	"fmt"
	"strconv"
)

func main() {
	a, b := ScanInt(), ScanInt()

	c := 0
	for i := a; i <= b; i++ {
		s := strconv.Itoa(i)
		if s[0:1]+s[1:2] == s[4:5]+s[3:4] {
			c++
		}
	}

	fmt.Println(c)
}

func ScanInt() (i int) {
	fmt.Scan(&i)
	return
}


Measured memory_bytes: 1024
using System;
class Program
{
	static void Main(string[] args)
	{
      string s = Console.ReadLine();
      char[] cs = s.ToCharArray();
      char a1 = cs[2];
      char a2 = cs[3];
      char b1 = cs[4];
      char b2 = cs[5];
      if(a1==a2 && b1==b2){
        Console.WriteLine("Yes");
      }else{
        Console.WriteLine("No");
      }
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define ld long double
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=22,M=1<<21|5;
int n,k,dp[N][M],ycl[M],Ans[M];
char ch[M];
inline int lowbit(int x){
	return x&(-x);
}
int rev(int x,int len){
	for(int i=0;i<len/2;i++){
		int a=x>>i&1,b=x>>(len-i-1)&1;
		x^=(a^b)<<i; x^=(a^b)<<(len-i-1);
	}
	return x;
}
signed main(){
	n=read(); k=read();
	for(int i=0;i<=n;i++){
		scanf("%s",ch);
		for(int j=0;j<(1<<i);j++)dp[0][(1<<i)+j]+=ch[j]-'0';
	}
	for(int i=2;i<(1<<(n+1));i++)ycl[i]=ycl[i>>1]+1;
	for(int i=0;i<n;i++){
		for(int j=1<<(i+1);j<(1<<(n+1));j++)if(dp[i][j]){
			//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
			int len=ycl[j],t=j-(1<<len),k=t>>i;
			if(j>>i&1){
				dp[i+1][j]+=dp[i][j];
				//if(i==0&&j==13)cout<<k<<" "<<(k>>ycl[lowbit(k^((1<<len)-1))]|(t&((1<<i)-1)))<<endl;
				if(k^((1<<(len-i))-1))dp[i+1][(1<<(len-ycl[lowbit(k^((1<<(len-i))-1))]))+((k>>ycl[lowbit(k^((1<<(len-i))-1))])<<i|(t&((1<<i)-1)))]+=dp[i][j];
			}else{
				dp[i+1][j]+=dp[i][j];
				//if(i==1&&j==12)cout<<k<<" "<<(1<<(len-ycl[lowbit(k)]))+(k>>ycl[lowbit(k)]|(t&((1<<i)-1)))<<endl;
				if(k)dp[i+1][(1<<(len-ycl[lowbit(k)]))+((k>>ycl[lowbit(k)])<<i|(t&((1<<i)-1)))]+=dp[i][j];
			}
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=1<<i;j<(1<<(n+1));j++){
			int t=j-(1<<ycl[j]);
			Ans[(1<<i)+(t&((1<<i)-1))]+=dp[i][j];
		}
	}
	//cout<<dp[1][6]<<" "<<dp[2][6]<<" "<<dp[2][10]<<" "<<dp[2][14]<<" "<<Ans[6]<<endl;
	//cout<<rev(1,3)<<" "<<Ans[6]<<" "<<Ans[7]<<endl;
	for(int i=(1<<(n+1))-1;i;i--)if(Ans[i]>=k){
		for(int j=1<<ycl[i];j<(1<<(ycl[i]+1));j++){
			int jj=j-(1<<ycl[j]),t=rev(jj,ycl[j]); //if(j==9)cout<<t<<endl;
			if(Ans[j]>=k){
				for(int o=ycl[j]-1;o>=0;o--)write(jj>>o&1); return 0;
			}
		}
	}
}
/*
3 1
1
01
1011
01001110


*/

Measured memory_bytes: 189696
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

const int DEBUG = 0;

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

string compact_pos(string s) {
  int n = s.length();
  string ma = "TAPRIS";
  int delta = 0;
  string cur;
  REP(i, 0, n + 1) {
    ma = max(ma, cur + s.substr(i, n));
    if (i == n) break;
    if (cur.size() > 0){
      if (cur[cur.size() - 1] == 'a' && s[i] == 'b') {
	assert (delta > 0);
	cur = string(delta, 'b');
      }
    }
    cur += s[i];
    delta += s[i] == 'b' ? 1 : -1;
  }
  return ma;
}

string compact_neg(string s) {
  int n = s.length();
  string ma = "TAPRIS";
  string cur;
  vector<bool> used(n);
  VI ukk(n, -1);
  VI a,b;
  REP(i, 0, n) {
    if (s[i]=='a') a.push_back(i);
    else b.push_back(i);
  }
  REP(i, 0, a.size()) ukk[a[i]] = b[i];
  int pos = 0;
  REP(i, 1, n) {
    if (used[i]) continue;
    if (s[i] == 'b') {
      cur += "ab";
      REP(j, pos, i) {
	if (not used[j]) {
	  assert (s[j] == 'a');
	  used[j] = 1;
	  used[ukk[j]] = 1;
	}
      }
      pos = i + 1;
    }
  }
  return cur;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  vector<string> cand;
  string ma = "";
  int delta = 0;
  VI zeros(1, 0);
  REP(i, 0, 2 * n) {
    delta += s[i] == 'b' ? 1 : -1;
    if (delta == 0) zeros.push_back(i + 1);
  }
  REP(i, 0, zeros.size() - 1) {
    int ta = zeros[i];
    int tb = zeros[i + 1];
    string u = s.substr(ta, tb - ta);
    cand.push_back(u[0] == 'a' ? compact_neg(u) : compact_pos(u));
  }
  if (DEBUG) {
    REP(i, 0, cand.size()) {
      DEBUGP(cand[i]);
    }
  }
  ma = "";
  for (int i = (int)cand.size() - 1; i >= 0; --i) {
    ma = max(ma, cand[i] + ma);
  }
  cout << ma << endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
#define int long long 

int N;
int res;
void dfs(int v,int mask){
    if(N<v)return ;
    if(mask==7)res++;
    dfs(v*10+3,mask|1);
    dfs(v*10+5,mask|2);
    dfs(v*10+7,mask|4);
}

signed main(){
    cin>>N;
    dfs(0,0);
    cout<<res<<endl;
    return 0;
}

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

class Program
{
    static void Main()
    {
        var n = int.Parse(ReadLine());
        var s = new string[n];
        var p = new int[n];
        var a = new int[n];
        for (int i = 0; i < n; i++)
        {
            var line = ReadLine().Split();
            s[i] = line[0];
            p[i] = int.Parse(line[1]);
            a[i] = i + 1;
        }
        var d = s.Select((x, i) => new { x, t = p[i], k = a[i] }).OrderBy(y => y.x).ThenByDescending(z => z.t);
        foreach (var item in d)
        {
            WriteLine(item.k);
        }
    }
}

Measured memory_bytes: 11616
import Control.Monad

main :: IO ()
main = do
  n <- readLn :: IO Int
  ns <- replicateM n readLn :: IO [Int]
  print $ solve ns

solve :: [Int] -> Int
solve = length . filter isPrime
  where
    isPrime :: Int -> Bool
    isPrime n = all ((/= 0) . (n `mod` ))
                $ takeWhile ((<= n) . (^2)) [2..]

Measured memory_bytes: 8152
use std::cmp::*;
use std::io::*;

fn dfs(v: usize, p: usize, memo: &mut Vec<usize>, graph: &Vec<Vec<usize>>) -> usize {
    if memo[v] != 0 {
        return memo[v];
    }
    let mut res = 0;
    for &nv in graph[v].iter() {
        if nv != p {
            res = max(res, dfs(nv, v, memo, &graph) + 1);
        }
    }

    memo[v] = res;
    res
}

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();
    let xy: Vec<(usize, usize)> = (0..m)
        .map(|_| {
            (
                itr.next().unwrap().parse::<usize>().unwrap() - 1,
                itr.next().unwrap().parse::<usize>().unwrap() - 1,
            )
        })
        .collect();

    let mut starts = Vec::new();
    let mut degree: Vec<usize> = vec![0; n];
    let mut graph: Vec<Vec<usize>> = vec![Vec::new(); n];
    for i in 0..m {
        graph[xy[i].0].push(xy[i].1);
        degree[xy[i].1] += 1;
    }

    for i in 0..n {
        if degree[i] == 0 {
            starts.push(i);
        }
    }

    let mut ans = 0;
    let mut memo: Vec<usize> = vec![0; n];
    for start in starts {
        ans = max(ans, dfs(start, 0, &mut memo, &graph));
    }
    println!("{}", ans);
}


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (2e18)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = -INF;
    ans = max({ans, a*c, a*d, b*c, b*d});
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>
#define MOD         (1000000000+7)
typedef long long ll;

int main(){
    ll n, a[200000]={0}, sum=0, tmp=0;
    scanf("%lld", &n);
    for(int i=0; i<n; i++){
        scanf("%lld", &a[i]);
        tmp += a[i];
        tmp %= MOD;
    }
    for(int i=0; i<n; i++){
        tmp -= a[i];
        if( tmp < 0 ){ tmp += MOD; }
        sum += (a[i] * tmp);
        sum %= MOD;
    }
    printf("%lld\n", sum);
    return 0;
}

Measured memory_bytes: 3296
S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)


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

ll dp[1000005][3];

int main() {
    int n;
    cin >> n;
    int a[n][3];
    rep(i, n) rep(j, 3) cin >> a[i][j];

    rep(i, n) rep(j, 3) rep(k, 3) {
        if (j == k) continue;
        dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k]);
    }

    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
    return 0;
}


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

using namespace std;

int main() {
	string s; cin >> s; string s1 = s;
	int k; cin >> k;
	char prev = s[0];
	int ans = 0;
	int cnt = 1;
	for(int i = 1; i < s.size(); ) {

		while( i < s.size() and s[i] == prev) {
			cnt++;
			i++;
		}
		if(s[i] != prev or i >=  s.size()) {
			ans += cnt/2;
			prev = s[i];
			cnt = 1;
			i+=1;
		}
	}
//	cout << ans  << endl;
	int ans2 = 0;
	s += s1;
	cnt = 1;
	prev = s[0];
	for(int i = 1; i < s.size(); ) {

        while( i < s.size() and s[i] == prev) {
            cnt++;
            i++;
        }
        if( i >=  s.size() or s[i] != prev) {
            ans2 += cnt/2;
			if ( i < s.size())
            prev = s[i];
            cnt = 1;
			i+=1;
        }
    }
	long long extra = ans2 - ans;

	int ans3 = 0;
    s += s1;
    cnt = 1;
    prev = s[0];
    for(int i = 1; i < s.size(); ) {

        while( i < s.size() and s[i] == prev) {
            cnt++;
            i++;
        }
        if( i >=  s.size() or s[i] != prev) {
            ans3 += cnt/2;
            if ( i < s.size())
            prev = s[i];
            cnt = 1;
            i+=1;
        }
    }
//	cout << ans3 << endl;
    long long extra2 = ans3 - ans;
//	cout << extra2 << endl;
	int rem1 = (k-1)/2;
	if((k-1) % 2 == 1) ans += extra;
	cout << ((long long)ans + (extra2*(rem1))) << endl;
	return 0;
}


Measured memory_bytes: 256
a = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]
mark = [[False, False, False] for _ in range(3)]

for i in range(3):
    for j in range(3):
        if a[i][j] in b:mark[i][j] = True
ans = 'No'
for i in range(3):
    if mark[i][0] and mark[i][1] and mark[i][2]:
        ans = 'Yes'
        break

for j in range(3):
    if mark[0][j] and mark[1][j] and mark[2][j]:
        ans = 'Yes'
        break


if (mark[0][0] and mark[1][1] and mark[2][2]) or (mark[0][2] and mark[1][1] and mark[2][0]): ans = 'Yes'
print(ans)


Measured memory_bytes: 3064
#include<algorithm>
#include<iostream>
#include<vector>

struct Point{
  int x;
  int y;
  int h;
};

bool operator< (const Point &p0, const Point &p1){
  return p0.h < p1.h;
}

Point explore(std::vector<Point> points){
  int n = (int)points.size();
  sort(points.begin(), points.end());
  
  Point center;
  
  int o_x = points.at(n - 1).x;
  int o_y = points.at(n - 1).y;
  int o_h = points.at(n - 1).h;
  
  bool yet = true;
  for(int x = 0; x <= 100 && yet; x++){
    for(int y = 0; y <= 100; y++){
      int h = o_h + abs(x - o_x) + abs(y - o_y);
      bool is_center = true;
      
      for(int i = 0; i < n - 1; i++){
        if(points.at(i).h != std::max(h - abs(x - points.at(i).x) - abs(y - points.at(i).y), 0)){
          is_center = false;
          break;
        }
      }
      
      if(is_center){
        center = {x, y, h};
        yet = false;
        break;
      }
    }
  }
  
  return center;
}

int main(){
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  
  int n;
  std::cin >> n;
  
  std::vector<Point> observation_points(n);
  
  for(int i = 0; i < n; i++){
    int x, y, h;
    std::cin >> x >> y >> h;
    
    observation_points.at(i).x = x;
    observation_points.at(i).y = y;
    observation_points.at(i).h = h;
  }
  
  Point center = explore(observation_points);
  std::cout << center.x << ' ' << center.y << ' ' << center.h << std::endl;
  
  return 0;
}

Measured memory_bytes: 256
// n = 100のとき、それはそうなので…
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

int main() {
  int d, n;
  cin >> d >> n;
  int power = 1;
  for (int i = 0; i < d; i++) power *= 100;
  if (n == 100) cout << power * 101 << endl;
  else cout << power * n << endl;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class DModSum {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        lint N;
        in>>N;
        out<<N*(N-1)/2<<'\n';
    }
};


int main() {
	DModSum solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256