akhauriyash/Code-Regression huggingface dataset:
// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=5e5+10,inf=1e9;

int n,pos[maxn];
vector<int>v[maxn];

int val[2*maxn];

void add(int pos,int x){
    pos+=n;
    val[pos]=x;
    for(pos>>=1; pos>0 ; pos>>=1)
	val[pos]= min(val[2*pos], val[2*pos+1]);
}
int ask(int f,int s){
    int ans=inf;
    for(f+=n,s+=n; f<s; f>>=1, s>>=1){
	if(f&1) ans=min(ans,val[f++]);
	if(s&1) ans=min(ans,val[--s]);
    }
    return ans;
}

priority_queue<int,vector<int>,greater<int> >pq;
int SZ[maxn];

void adde(int a,int b){
    v[a].PB(b);
    SZ[b]++;
}

int ANS[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    
    int k;cin>>n>>k;
    for(int i=0;i<n;i++){
	int x;cin>>x;
	pos[--x]=i;
    }

    fill(val,val+2*maxn,inf);
    
    for(int i=n-1;i>=0;i--){
	int num=ask(pos[i],min(pos[i]+k,n));
	if(num!=inf) adde(pos[i],pos[num]);
	num=ask( max(int(0),pos[i]-k+1), pos[i] );
	if(num!=inf) adde(pos[i],pos[num]);
	add(pos[i],i);
    }
    
    for(int i=0;i<n;i++){
	if(SZ[i]==0) pq.push(i);
    }

    int C=0;
    
    while(sz(pq)){
	int u=pq.top();
	pq.pop();
	ANS[u]=C++;
	for(int y:v[u]){
	    if(--SZ[y]==0)
		pq.push(y);
	}
    }
    for(int i=0;i<n;i++){
	cout<<ANS[i]+1<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ppb pop_back
#define INF 1e18
typedef long long ll;

using namespace std;

ll cnt[100001];

int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    ll k;
    cin >> n >> k;
    rep(i, n)
    {
        int a, b;
        cin >> a >> b;
        cnt[a] += b;
    }
    //k--;
    rep(i, 100001)
    {
        if (k <= cnt[i])
        {
            cout << i << endl;
            break;
        }
        k -= cnt[i];
    }

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> h;
    rep(i, n){
        ll x;
        cin >> x;
        h.push_back(x);
    }
    sort(h.begin(), h.end());
    ll sum=0;
    if(k<n){
        rep(i, n-k){
            sum += h[i];
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 5368
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,e,t,a[100005],k;
ll o,f[100005];
int main(){
    o=orz*4ll;
    scanf("%d%d%d",&n,&e,&t);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1;i<=n;++i){
        while((a[i]-a[k+1])*2>t)o=min(o,f[k]-a[k]-a[k+1]*2ll),++k;
        f[i]=min(f[k]+a[i]-a[k]+t,o+a[i]*3ll);
    }
    printf("%lld\n",f[n]+e-a[n]);
    //system("pause");
    return 0;
}


Measured memory_bytes: 1408
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	int n,i,j,a[4],l[4],s[4],cnt,kake,x,y,z;
	while(1){
		cnt=0;
		cin>>n;
		if(n==0000) break;
		for(i=3;i>=0;i--){
			a[i]=n%10;
			n=n/10;
		}
		for(i=0;i<4;i++){
			if(a[0]==a[i]) cnt=cnt+1;
		}
		if(cnt==4) cout<<"NA"<<endl;
		if(cnt!=4){
			cnt=0;
			while(1){
				if(a[0]==6&&a[1]==1&&a[2]==7&&a[3]==4) break;
				cnt=cnt+1;
				for(i=0;i<4;i++){
					l[i]=a[i];
					s[i]=a[i];
				}
				for(i=0;i<4;i++){
					for(j=0;j<4;j++){
						if(l[i]>l[j]){
							swap(l[i],l[j]);
						}
						if(s[i]<s[j]){
							swap(s[i],s[j]);
						}
					}
				}
/*				cout<<'l'<<endl;
				for(i=0;i<4;i++) cout<<l[i];
				cout<<endl;
				cout<<'s'<<endl;
				for(i=0;i<4;i++) cout<<s[i];
				cout<<endl;*/
				kake=1000;
				x=0;
				y=0;
				for(i=0;i<4;i++){
					x=x+l[i]*kake;
					y=y+s[i]*kake;
					kake=kake/10;
				}
				z=x-y;
//				cout<<x<<'|'<<y<<'|'<<z<<endl;
				for(i=3;i>=0;i--){
				a[i]=z%10;
				z=z/10;
				}
/*				cout<<'a'<<endl;
				for(i=0;i<4;i++) cout<<a[i];
				cout<<endl;
				if(cnt==2) break;*/
			}
			cout<<cnt<<endl;
		}
	}
/*	cout<<'a'<<endl;
	for(i=0;i<4;i++) cout<<a[i];
	cout<<endl;
	cout<<'l'<<endl;
	for(i=0;i<4;i++) cout<<l[i];
	cout<<endl;
	cout<<'s'<<endl;
	for(i=0;i<4;i++) cout<<s[i];
	cout<<endl;
	*/
	return 0;
}



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

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vi a(n+1),b(n+1);
    
    for(int i=0; i<=n; i++)
        cin >> a[i];
    for(int i=0; i<n; i++)
        cin >> b[i];
    
    ll sol=0;
    for(int i=0; i<=n; i++){
        if(a[i]>b[i])
            sol+=b[i];
        else{
            sol+=a[i];
            b[i] -= a[i];
            if(i+1<=n){
                sol+=min(b[i], a[i+1]);
                a[i+1]=max(a[i+1]-b[i], 0);
            }
        }
    }
    cout << sol;
}

Measured memory_bytes: 1024
#include<algorithm>
#include <bits/stdc++.h>
using namespace std;
int main(void){
	char a,b;
	cin>>a>>b;
	if(a=='H') cout<<b<<endl;
  	else{
      if(b=='H') cout<<"D"<<endl;
      else cout<<"H"<<endl;
    }
  	return 0;
}


Measured memory_bytes: 256
from collections import deque
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
G[0]=["#"]*(w+2)
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
G[h+1]=["#"]*(w+2)
a=0
for i in range(h+2):
  for j in range(w+2):
    if G[i][j]==".":
      a=a+1
B=[[0]*(w+2) for i in range(h+2)]
for i in range(h+2):
  for j in range(w+2):
    if G[i][j]=="#":
      B[i][j]=1
INF=10**4
A=[[INF]*(w+2) for i in range(h+2)]
C=[-1,1,0,0]
D=[0,0,-1,1]
sx=1
sy=1
gx=h
gy=w
A[sx][sy]=0
E=deque([sx,sy])
while len(E)>0:
  x=E[0]
  E.popleft()
  y=E[0]
  E.popleft()
  for i in range(4):
    if B[x+C[i]][y+D[i]]==0:
      A[x+C[i]][y+D[i]]=A[x][y]+1
      B[x+C[i]][y+D[i]]=1
      E.append(x+C[i])
      E.append(y+D[i])
if A[gx][gy]==INF:
  print(-1)
else:
  print(a-A[gx][gy]-1)

Measured memory_bytes: 3436
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  a=read(),b=read()
#define in3(a,b,c)  a=read(),b=read(),c=read()
#define in4(a,b,c,d)  a=read(),b=read(),c=read(),d=read()
#define inl(a)  a=readl()
#define inl2(a,b)  a=readl(),b=readl()
#define inl3(a,b,c)  a=readl(),b=readl(),c=readl()
#define inl4(a,b,c,d)  a=readl(),b=readl(),c=readl(),d=readl()
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x,y) memset(x,y,sizeof(x))
inline int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
inline ll readl(){
    char c;ll s=0;int t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
	return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 100010
/*------------------------------------------------------------*/
	
int main(){
	int a[10]={0};
	FOR(i,1,3)in(a[i]);
	sort(a+1,a+4);
	a[1]!=a[2]?out(a[1]):out(a[3]); 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll
#define flagcount __builtin_popcount
#define flag(x) (1 << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1 << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define idx_lower(v, x) (distance(v.begin(), low2way(v, x)))  //配列vでx未満の要素数を返す
#define idx_upper(v, x) (distance(v.begin(), high2way(v, x))) //配列vでx以下の要素数を返す
#define idx_lower2(v, x) (v.size() - idx_lower(v, x))         //配列vでx以上の要素数を返す
#define idx_upper2(v, x) (v.size() - idx_upper(v, x))         //配列vでxより大きい要素の数を返す
#define putout(a) cout << a << endl
#define Gput(a, b) G[a].push_back(b)
#define Sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
template <typename T>
T lcm(T x, T y)
{
    T z = gcd(x, y);
    return x * y / z;
}
template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
//場合によって使い分ける
//const ll dx[4]={1,0,-1,0};
//const ll dy[4]={0,1,0,-1};
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//2次元配列の宣言
//vector<vector<ll>> field(h, vector<ll>(w));

int main()
{
    cout << fixed << setprecision(30);
    ll D;
    cin >> D; //=365
    vec c(26);
    loop(i, 26) cin >> c[i];
    vector<vector<ll>> s(D, vector<ll>(26));
    loop(i, D)
    {
        loop(j, 26) cin >> s[i][j];
    }
    vec t(D);
    loop(i, D) cin >> t[i];
    /*
    //score計算
    ll score = 0;
    vector<ll> before(26); //直近で何日前に開催したか？
    loop(i, D)
    {
        score += s[i][t[i] - 1];
        before[t[i] - 1] = i + 1; //リセット
        //スコア減点
        loop(j, 26)
        {
            score -= c[j] * ((i + 1) - before[j]);
        }
    }
    */
    ll M;
    cin >> M;
    loop(k, M)
    {
        ll d, q;
        cin >> d >> q;
        d--;
        t[d] = q;
        ll score = 0;
        vector<ll> before(26); //直近で何日前に開催したか？
        loop(i, D)
        {
            score += s[i][t[i] - 1];
            before[t[i] - 1] = i + 1; //リセット
            //スコア減点
            loop(j, 26)
            {
                score -= c[j] * ((i + 1) - before[j]);
            }
        }
        putout(score);
    }
    return 0;
}


Measured memory_bytes: 3664
#include <stdio.h>
int max(int a, int b);
int min(int a, int b);
int main()
{
    int n;
    scanf("%d", &n);
    int b[100]={0};
    for(int i=0; i<n-1; i++)
        scanf("%d", &b[i]);
    int sum = b[0] + b[n-2];
    for(int i=1; i<=n-2; i++)
    {
        sum+=min(b[i],b[i-1]);
    }
    printf("%d\n", sum);
    return 0;
}
int max(int a, int b)
{
    if(a>=b)
        return a;
    else
        return b;
}
int min(int a, int b)
{
    if(a<=b)
        return a;
    else
        return b;
}

Measured memory_bytes: 128
c11,c12,c13 = map(int,input().split())
c21,c22,c23 = map(int,input().split())
c31,c32,c33 = map(int,input().split())
count = 0
if c11-c12 == c21-c22 == c31-c32:
  count += 1
  if c12-c13 == c22-c23 == c32-c33:
    count += 1
    if c21-c11 == c22-c12 == c23-c13:
      count += 1
      if c21-c31 == c22-c32 == c23-c33:
        count += 1
if count == 4:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
int dp[105][100010];
int V[105];
signed main(void){
    int n,k;cin>>n>>k;
    rep(i,n)cin>>V[i];
    rep(i,105)rep(j,100010)dp[i][j]=0;
    dp[0][0]=1;dp[0][V[0]+1]=-1;
    rep(i,n-1)rep(j,k+1){
        dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
        dp[i+1][j]=(dp[i][j]+dp[i+1][j])%mod;
        dp[i+1][min((int)100009,V[i+1]+j+1)]=(dp[i+1][min((int)100009,V[i+1]+j+1)]-dp[i][j])%mod;
    }
    rep(i,k+1)dp[n-1][i+1]=(dp[n-1][i+1]+dp[n-1][i])%mod;
    cout<<(dp[n-1][k]+mod)%mod<<endl;
}

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

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define endl '\n'
#define fcin ios::sync_with_stdio(false); cin.tie(nullptr);
#define INF 0x3f3f3f3f
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

template <typename A, typename B>
string to_string(pair<A, B> p){
    return "(" + to_string(p.fi) + ", " + to_string(p.se) + ")";
}

template <typename T>
string to_string(T v){
    string s = "{";
    bool first = true;
    for(const auto & x : v){
        if(!first) s += ", ";
        first = false;
        s += to_string(x);
    }
    return s + "}";
}

void debug_out(){ cerr << endl;}
template <typename First, typename... Next>
void debug_out(First F, Next... N){
    cerr << " " << to_string(F);
    debug_out(N...);
}

#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 1
#endif

int main(){
    fcin;
    int w, h, x, y;
    cin >> w >> h >> x >> y;

    ll a = ll(w) * h;
    cout << fixed << setprecision(10) << a / 2.0 << " ";


    if(x == w/2.0 and y == h/2.0) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll maxNum=100010;
vector<bool> isPrime(maxNum,true);
bool sieve(ll n){
    isPrime[0]=false;
    isPrime[1]=false;

    for(ll i=2;i<n;i++){
        if(!isPrime[i]) continue;
        for(int j=i*2;j<=n;j+=i)    isPrime[j]=false;
    }
}

int main(){
    int n;cin>>n;
    vector<ll> ans;
    sieve(100001);
    int ln[100001]={};
    rep(i,100001){
        if(i%2==0)  continue;
        if(isPrime[i]&&isPrime[(i+1)/2])    ln[i]=1;
    }
    ll sum[100001]={};
    rep(i,100001){
        sum[i+1]=sum[i]+ln[i];
    }
    rep(i,n){
        int r,l;cin>>r>>l;
        ans.push_back(sum[l+1]-sum[r]);
    }
    rep(i,n)    cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
double eps=1e-8;
ll mod=1e9+7;
ll inf=1e9+7;
priority_queue<P,vector<P>,greater<P> > pq;

/*max_flowを使わない二部マッチング O(F|E|)*/
/*定数倍高速*/
#define MAX_V 10000
int V;                //頂点数
vector<int> G[MAX_V]; //グラフの隣接リスト表現
int match[MAX_V];     //マッチングのペア
bool used[MAX_V];     //DFSですでに調べたかのフラグ

//uとvを結ぶ辺をグラフに追加する
void add_edge(int u,int v){
  G[u].push_back(v);
  G[v].push_back(u);
}

//増加パスをDFSで探す
bool dfs(int v){
  used[v] = true;
  for(int i=0; i<G[v].size(); i++){
    int u = G[v][i], w = match[u];
    if(w<0 || !used[w] && dfs(w)){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

//二部グラフの最大マッチングを求める
int Bipartite_Matching(){
  int res=0;
  memset(match, -1, sizeof(match));
  for(int v=0; v<V; v++){
    if(match[v] < 0){
      memset(used,0,sizeof(used));
      if(dfs(v)) res++;
    }
  }
  return res;
}

int main(){
  int n,a[200],b[200],c[200],d[200];
  cin>>n;
  V=1000;
  for(int i=0;i<n;i++)cin>>a[i]>>b[i];//,add_edge(0,i+1);
  for(int i=0;i<n;i++){
    cin>>c[i]>>d[i];
    for(int j=0;j<n;j++){
      if(a[j]<c[i]&&b[j]<d[i])add_edge(i+1+n,j+1);
    }
    // add_edge(i+1+n,V-1);
  }
  cout<<Bipartite_Matching()<<endl;
  return 0;
}


Measured memory_bytes: 512
li=[]
for i in range(1,int(1000**0.5)+1):
  for j in range(2,11):
    tmp=i**j
    if tmp>1000:
      break
    else:
      li.append(tmp)
l=(sorted(set(li)))
x=int(input())
#l=[4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000]
ans=0
for i in l[::-1]:
  if i<=x:
    print(i)
    exit()
  

Measured memory_bytes: 3060
//Heaplax
//别让自己后悔
#include<bits/stdc++.h>
#define N 3001
#define LL long long
#define LOG(x) cerr<<#x<<" = "<<x<<endl
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;
}
using namespace std;
bool f[N],vis[N];
int n,a[N];
int cnt,head[N],nxt[N+N],to[N+N];
void dfs(int u)
{
	vis[u]=1;
	for(int i=head[u],v;i;i=nxt[i])
		if(a[u] > a[v=to[i]])
		{
			if(!vis[v])dfs(v);
			f[u]|=!f[v];
		}
}
int main()
{
	re(n);
	for(int i=1;i<=n;++i)re(a[i]);
	for(int i=1,u,v;i<n;++i)
	{
		re(u),re(v);
		add_edge(u,v);
		add_edge(v,u);
	}
	for(int i=1;i<=n;++i)
	{
		if(!vis[i])dfs(i);
		if(f[i])printf("%d ",i);
	}
	puts("");
}


Measured memory_bytes: 384
import numpy as np
import math





n= int(input())



xandy=np.ones((n,n))

xandy=xandy*(-1)

flag=0
for i in range(0,n):
    a=int(input())
    for j in range(0,a):
        x,y= map(int, input().split())
        xandy[i][x-1]=y

max=0


for l in range(0,2**n):
    i=2**n-1-l
    flag=1
    if max<bin(i).count("1"):
        for j in range(0,n):
       
        #iを2進数表示した時kの位置ででの0-1が対応してあるか立っているか？
            if  bin( i& 2**j).count("1")>0:
                 for k in range(0,n):
                      if  xandy[j][k]!=-1 and xandy[j][k]!=(i >> k)%2:
                          flag=0 
                          break
                       
            if flag==0:
                break
        if flag==1 and max<bin(i).count("1"):
             max=bin(i).count("1")
         

print(max)

                     
             

Measured memory_bytes: 12396
N = int(input())
*A, = map(int, input().split())
MOD = 10**9+7

ac = [0]*(N+1)
for i in range(N):
    ac[i+1] = ac[i]+A[i]
ans = 0

for i in range(1, N):
    ans += (ac[N]-ac[i])*A[i-1]
    ans %= MOD

print(ans)


Measured memory_bytes: 31752
#include<bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define N 300005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
main()
{
    string s;
    cin>>s;
    s+='#';
    int now=0,mx=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!='R')
        {
            mx=max(mx,now);
            now=0;
        }
        else
            now++;
    }
    cout<<mx;
}



Measured memory_bytes: 3624
H,W = map(int,input().split())

ans = H*W
for h in range(1,H):
    A = W*h

    h_res = H - h

    B1 = W*(h_res//2)
    C1 = W*(h_res - h_res//2)

    diff1 = max(abs(A - B1), abs(A - C1), abs(B1 - C1))

    B2 = h_res * (W//2)
    C2 = h_res * (W - W//2)
    diff2 = max(abs(A - B2), abs(A - C2), abs(B2 - C2))

    ans = min(ans, diff1, diff2)

for w in range(1,W):
    A = w*H

    w_res = W - w

    B1 = w_res*(H//2)
    C1 = w_res*(H - H//2)

    diff1 = max(abs(A - B1), abs(A - C1), abs(B1 - C1))

    B2 = H* (w_res//2)
    C2 = H * (w_res - w_res//2)
    diff2 = max(abs(A - B2), abs(A - C2), abs(B2 - C2))

    ans = min(ans, diff1, diff2)


print(ans)


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

int main() {
  int N;
  cin >> N;
  vector<int>X(N);
  vector<int>P(101);
  for(int i=0;i<N;i++){
    cin >> X.at(i);
  }
  for(int i=0;i<101;i++){
    for(int j=0;j<N;j++){
      P.at(i)+=pow(X.at(j)-i,2);
    }
  }
  sort(P.begin(),P.end());
  cout << P.at(0) << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0;--i)
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
const int INF = 1000000007;
int K;
string S;
typedef pair<ll, ll> P;

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

  cin >> S;
  cin >> K;

  ll cnt = 0ll;
  bool init_same=false;
  ll start_idx = -2ll;
  vector<P> vec;
  rep(i, S.size()-1){
    if (S[i]!=S[i+1]){
      vec.push_back(P(start_idx, cnt));
      if (start_idx==0) init_same = true;
      cnt = 0;
    } else {
      if (cnt==0) start_idx = i;
      cnt++;
    }
  }

  ll total = 0ll;
  // 最初と最後が違う場合
  if (S[0] != S[S.size()-1]){ // ex) s-------t
    vec.push_back(P(start_idx, cnt)); // cnt==0でもどうせ0が足されるので問題ない
    rep(i, vec.size()){
      total+=(vec[i].second+1)/2;
    }
    cout << total*K<< "\n";
    return 0;
  }

  // 全部同じ場合
  if (vec.size()==0){
    ll ans = (S.size()*K)/2;
    cout << ans << "\n";
    return 0;
  }

  // 最初と最後が同じだが、0番目と1番目が同じ
  if (init_same){
    ll real_init = vec[0].second;
    vec[0] = P(0, real_init+cnt+1);
    rep(i, vec.size()){
      if (i==0) total+=((vec[i].second+1)/2)*(K-1);
      else total+=((vec[i].second+1)/2)*K;
    }
    total+=(real_init+1)/2;
    total+=(cnt+1)/2;
    cout << total<< "\n";
    return 0;
  }

  // 最初と最後が同じだが、0番目と1番目が違う    
  // vec.push_back(P(S.size()-1, cnt+1));
  rep(i, vec.size()){
    total+=((vec[i].second+1)/2)*K;
  }
  total+=(cnt/2+1)*(K-1);
  total+=(cnt+1)/2;
  cout << total<< "\n";
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int go[100005],ans=0;
int main(){
    int n,i,j,k,l;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&go[i]);
    for(i=1;i<=n;i++){
        if(go[go[i]]==i)ans++;
    }
    printf("%d\n",ans/2);
    return 0;
}




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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int32 di[8] = {-1,-1,-1,0,1,1,1,0};
int32 dj[8] = {1,0,-1,-1,-1,0,1,1};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 h,w;
  cin >> h >> w;
  vector<string> s(h);
  REP(i,h)cin >> s[i];
  REP(i,h)REP(j,w){
    if(s[i][j] == '#')continue;
    int32 cnt = 0;
    REP(k,8){
      int32 ni = i + di[k];
      int32 nj = j + dj[k];
      if(ni < 0 || h <= ni)continue;
      if(nj < 0 || w <= nj)continue;
      if(s[ni][nj] == '#')cnt++;
    }
    s[i][j] = '0' + cnt;
  }
  REP(i,h)ANS(s[i]);
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 200005

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



Measured memory_bytes: 2512
#include <stdio.h>

int main()
{
 int a, b, c, d, e, f, x1, y1;
 // x = (bf-ce) / (bd-ae)
 // y = (cd-af) / (bd-ae)
 double x, y, nn;

 while(scanf("%d%d%d%d%d%d", &a,&b,&c,&d,&e,&f) != EOF){
  x1 = b*f-c*e;
  y1 = c*d-a*f;
  nn = b*d-a*e;
  x = (double)x1 / nn;
   if(x==0) x=+0;
  y = (double)y1 / nn;
  if(y==0) y=+0;
   printf("%.3lf %.3lf\n", x, y);
 }
 return 0;
}

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

# from numba import njit

# input = stdin.readline

INF = 10**9

# @njit
def solve(n,a):
  ans = INF
  k = min(a)
  while k <= max(a):
    ans = min(ans,sum((x-k)**2 for x in a))
    k += 1
  return ans



def main():
  N = int(input())
  # N,M = map(int,input().split())
  a = list(map(int,input().split()))
  print(solve(N,a))
  return

if __name__ == '__main__':
  main()


Measured memory_bytes: 9196
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <limits>
using namespace std;
// 素因数分解
typedef pair<long long, long long> P;
vector<P> prime_factorize(long long n)
{
vector<P> res;
for (long long p = 2; p * p <= n; ++p)
{
if (n % p != 0)
continue;
int num = 0;
while (n % p == 0)
{
++num;
n /= p;
}
res.push_back(make_pair(p, num));
}
if (n != 1)
res.push_back(make_pair(n, 1));
return res;
}
// 因数分解
long long gcd(long long x, long long y)
{
  if (y == 0)
  {
    return x;
  }
  else
  {
    return gcd(y, x % y);
  }
}
const int MOD = 1000000007;
typedef long long int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)

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

Measured memory_bytes: 3512
//84104971101048411497 - Can you guess what does this mean?
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define maxN 55
#define oo 2000000007
#define sz(a) (int)a.size()

const double PI = acos(-1.0);

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int n, P, cntOdd, cntEven;
ll c[maxN][maxN];

int main () {
    scanf("%d%d", &n, &P);
    fto(i, 1, n) {
        int x; scanf("%d", &x);
        if (x&1) ++cntOdd;
        else ++cntEven;
    }

    fto(i, 0, n) {
        c[i][0] = 1;
        fto(j, 1, i) c[i][j] = c[i-1][j]+c[i-1][j-1];
    }

    ll ans = 0;
    for(int i = P; i <= cntOdd; i += 2) {
        ans += (1LL<<cntEven)*c[cntOdd][i];
    }

    cout << ans;

    return 0;
}


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

typedef long long ll;
typedef pair<ll, ll> pll;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define vuni(v) v.erase(unique(v.begin(), v.end()), v.end());
#define mins(m, s) m.insert(make_pair(s, 1));
#define mfin(m, s) m.find(s) != m.end()

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl

const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9 + 7;

using Graph = vector<ll>; // グラフ型
Graph G[200005];          // グラフ

bool seen[200005];

ll dfs(int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    ll cnt = 1;
    for(auto next_v : G[v]) {
        if(seen[next_v])
            continue;       // next_v が探索済だったらスルー
        cnt += dfs(next_v); // 再帰的に探索
    }
    return cnt;
}

int main() {
    ll n, m, a, b;
    m0(seen);
    
    cin >> n >> m;
    for(ll i = 0; i < m; i++) {
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    ll ma = 0;
    for(ll i = 0; i < n; i++) {
        if(seen[i])
            continue;
        ma = max(ma, dfs(i));
    }

    cout << ma << endl;

    return 0;
}

Measured memory_bytes: 24100
#include <iostream>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cmath>

#define FAST                     \
    ios::sync_with_stdio(false); \
    cin.tie(NULL);               \
    cout.tie(NULL);
#pragma GCC optimize("O3")

using namespace std;
typedef long long ll;

int freq[100005];

int main()
{
    FAST;
    int n, m;
    cin >> n >> m;
    unordered_set<int> us;
    us.insert(1);
    int a1, a2;
    memset(freq,  0, sizeof(freq));
    for (int i = 0; i < m; i++)
    {
        cin >> a1 >> a2;
        freq[a1]--;
        freq[a2]++;
        // cout << freq[a1] << " " << freq[a2] << "\n";
        if (us.count(a1))
        {
            us.insert(a2);
            if(freq[a1] == -1)
                us.erase(a1);
        }
    }
    cout << us.size();
}

Measured memory_bytes: 7000
#include <iostream>
using namespace std;
 
int main() {
  int A, B, N;
  A = 100;
  B = 100;
  cin >> N;
  int res = 0;
  for (int a = 0; a <= A; ++a) {
    for (int b = 0; b <= B; ++b) {
        int total = 4*a + 7*b;
        if (total == N) ++res;
    }
  }
	if(res != 0) cout << "Yes" << endl;
	else	cout << "No" << endl;
}

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

int main(){
    int num;
    cin >> num;
    string a;
    cin >> a;

    int ans=0;
    for(int i=1;i<=num;i++){
        if(a[i-1]!=a[i]){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3728
hw = []
buff = []

while True:
    buff = list(map(int, input().split()))
    if [0, 0] == buff:
        break
    else:
        hw.append(buff)

for i in hw:
    for j in range(i[0]):
        for k in range(i[1]):
            if (j % 2 == 0 and k % 2 == 0) or (j % 2 != 0 and k % 2 != 0):
                print("#", end="")
            else:
                print(".", end="")
        print()
    print()


Measured memory_bytes: 7012
#include<iostream>

struct PokerCard{
    char suit;
    int value;
};

void PrintArray(const struct PokerCard *cards, int N);
void BubbleSort(struct PokerCard *cards, int N);
void SelectionSort(struct PokerCard *cards, int N);
bool IsStable(const struct PokerCard *cards_1, const struct PokerCard *cards_2, int N);

int main() {
    int n;
    struct PokerCard *cards_1, *cards_2;

    std::cin >> n;

    /* allocate and initialize cards_1 and cards_2 */
    cards_1 = (struct PokerCard*)calloc(n + 1, sizeof(struct PokerCard));
    if (!cards_1) {
        std::cout << "ERROR! Could not allocate cards_1 structure." << std::endl;
        exit(-1);
    }
    for (int i = 0; i < n; i++) {
        std::cin >> cards_1[i].suit >> cards_1[i].value;
    }
    cards_2 = (struct PokerCard*)calloc(n + 1, sizeof(struct PokerCard));
    if (!cards_2) {
        std::cout << "ERROR! Could not allocate cards_2 structure." << std::endl;
        exit(-1);
    }
    for (int i = 0; i < n; i++) {
        cards_2[i] = cards_1[i];
    }

    /* bubble sort for cards_1 */
    BubbleSort(cards_1, n);

    /* selection sort for cards_2 */
    SelectionSort(cards_2, n);

    /* print the results */
    PrintArray(cards_1, n);
    std::cout << "Stable" << std::endl;
    PrintArray(cards_2, n);
    if (IsStable(cards_1, cards_2, n)) {
        std::cout << "Stable" << std::endl;
    } else {
        std::cout << "Not stable" << std::endl;
    }

    free(cards_1);
    free(cards_2);

    return 0;
}

void PrintArray(const struct PokerCard *cards, int N) {
    for (int i = 0; i < N; i++) {
        if (i > 0) {
            std::cout << " ";
        }
        std::cout << cards[i].suit << cards[i].value;
    }
    std::cout << std::endl;
}

void BubbleSort(struct PokerCard *cards, int N) {
    bool flag;
    int i;
    
    flag = 1;
    i = 0;

    while (flag) {
        flag = 0;
        for (int j = N - 1; j > i; j--) {
            if (cards[j].value < cards[j - 1].value) {
                struct PokerCard tmp;
                tmp = cards[j];
                cards[j] = cards[j - 1];
                cards[j - 1] = tmp;
                flag = 1;
            }
        }
        i++;
    }
    
}

void SelectionSort(struct PokerCard *cards, int N) {
    int minIndex;

    for (int i = 0; i < N - 1; i++) {
        minIndex = i;
        for (int j = i; j < N; j++) {
            if (cards[j].value < cards[minIndex].value) {
                minIndex = j;
            }
        }
        
        if (minIndex != i) {
            struct PokerCard tmp;
            tmp = cards[i];
            cards[i] = cards[minIndex];
            cards[minIndex] = tmp;
        }
    }
    
}

bool IsStable(const struct PokerCard *cards_1, const struct PokerCard *cards_2, int N) {
    for (int i = 0; i < N; i++) {
        if (cards_1[i].suit != cards_2[i].suit) {
            return false;
        }
    }
    
    return true;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n) ; ++i)
#define orep(i,a) for(int i = 1;i<=(a);++i)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define emb emplace_back
#define fcout cout << fixed << setprecision(15)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using vi = vector<int>;

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[105][100005];
int main() {
  int n,k;
  cin >> n >> k;
  vi a(n,0);
  rep(i,n) cin >> a.at(i);
  rep(i,k+1) dp[0][i] = mint(1);

  orep(i,n) {
    mint t = 0;
    rep(j,k+1) {
      if(j-a.at(i-1)-1>=0) dp[i][j] = t+ dp[i-1][j] - dp[i-1][j-a.at(i-1)-1];
      else dp[i][j] = t+ dp[i-1][j];
      t=dp[i][j];
    }
  }
  cout << dp[n][k] - dp[n][k-1] << endl;

  return 0;
}


Measured memory_bytes: 82304
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int P=200003;
const int g=2;

typedef complex<double> C;
typedef vector<double> vd;
#define vi vector<int> 

void fft(vector<C>& a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vector<complex<long double>> R(2, 1);
	static vector<C> rt(2, 1);  // (^ 10% faster if double)
	for (static int k = 2; k < n; k *= 2) {
		R.resize(n); rt.resize(n);
		auto x = polar(1.0L, acos(-1.0L) / k);
		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
	}
	vi rev(n);
	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
		}
}
vd conv(const vd& a, const vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n);
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in);
	for (C& x : in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
	return res;
}

int n;
ll arr[200005];

ll val[200005];
ll pos[200005];

ll ans=0;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	ll curr=1;
	rep(x,0,P-1){
		val[x]=curr;
		pos[curr]=x;
		
		curr=curr*g%P;
	}
	
	vector<double> v(P);
	
	cin>>n;
	rep(x,0,n){
		cin>>arr[x];
		if (arr[x]) v[pos[arr[x]]]+=1;
	}
	
	v=conv(v,v);
	
	rep(x,0,2*(P-1)) {
		ans+=(ll)floor(v[x]+0.3)*val[x%(P-1)];
		
		//if (v[x]>0.3) cout<<x<<" "<<v[x]<<" "<<val[x%(P-1)]<<endl;
	}
	
	rep(x,0,n){
		ans-=(arr[x]*arr[x])%P;
		//cout<<(arr[x]*arr[x])%P<<endl;
	}
	
	cout<<ans/2<<endl;
}


Measured memory_bytes: 56188
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include <stdio.h>
#include <bitset>
#include<math.h>
using namespace std;
typedef long long ll;

int main(){
	ll n,ans;
	cin >> n;
	ans = ((n-1) * n )/ 2;
	cout << ans << endl;

}

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

const int MAX = 20000; // N
int main() {
	int N, p;
	static pair<int, int> c[MAX];
	cin >> N;
	for (int i = 0;i < N;++ i) {
		cin >> p;
		c[i] = make_pair(p, i);
	}
	sort(c, c+N);
	cout << N;
	for (int i = 2;i <= N;++ i) cout << " " << N * i;
	cout << endl << N * N + c[0].second;
	for (int i = 1;i < N;++ i) cout << " " << N * (N - i) + c[i].second;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

まず、a_i=Ni, b_i=N(N-i+1)とすると任意のiに対しa_{p_i}+b_{p_i}は一定になる
後は、b_{p_i} += i - 1とすれば全ての条件を満たすように構築できる
*/

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(a);i<=(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(b);i>=(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
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;}
template<class T>
ll sum(const T& a){return accumulate(all(a),0LL);}

void solve(){
    while(1){
        ll m,f,r;cin>>m>>f>>r;
        if(m==-1&&f==-1&&r==-1)return;
        if(m==-1||f==-1)cout<<"F"<<endl;
        else if(m+f>=80)cout<<"A"<<endl;
        else if(m+f>=65)cout<<"B"<<endl;
        else if(m+f>=50||m+f>=30&&r>=50)cout<<"C"<<endl;
        else if(m+f>=30)cout<<"D"<<endl;
        else cout<<"F"<<endl;
    }
}

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



Measured memory_bytes: 3204
{-#LANGUAGE FlexibleContexts#-}
import Control.Monad
import Control.Monad.State
import Control.Monad.Reader
import Control.Arrow
-- import Control.Comonad
import Data.Maybe
import Data.List
import Data.Bool
import Data.Fixed
import Data.Tuple
import Data.Ratio
import qualified Data.Map.Strict as M
import qualified Data.Array.IO as IA
import qualified Data.Vector as V

getI = read <$> getLine :: IO Int
getIs = map read . words <$> getLine :: IO [Int]
getD = read <$> getLine :: IO Double
getDs = map read . words <$> getLine :: IO [Double]
getInt = read <$> getLine :: IO Integer
getInts = map read . words <$> getLine :: IO [Integer]

type Row = Integer
type Col = Integer
type PointI = (Integer, Integer)
type Point = (Int, Int)

mmm = 1000000007
fact n
    | n < 1 = 1
    | True = foldr1 (*) [1..n]
ti = toInteger
fi = fromInteger
fig = fromIntegral
rf = realToFrac

(.<.) :: Integer -> Integer -> Integer
(.<.) f g -- combination
    | g < 1 || f < 1 || f < g = 1
    | True = foldr1 (*) (take (fi g) [f,f-1..]) `div` fact g
(.>.) f g --combination with repetition
    | g < 1 || f < 1 = 1
    | True = fact (f + g - 1) `div` (fact (f - 1) * fact g)
comb = (.<.)
combWp = (.>.)

unique a = unique_ (reverse . sort $ a) [] Nothing
    where
        unique_ [] arr _ = arr
        unique_ (x:xs) arr n
            | n == Just x = unique_ xs arr n
            | otherwise = unique_ xs (x:arr) $ Just x
 
zeroume keta num
    | (length . show $ num) > keta = show num
    | otherwise = do 
        let zeros = take keta $ repeat '0'
        reverse . take keta $ (reverse . show $ num) ++ zeros
 
i2b num
    | num < 2 = show num
    | otherwise = i2b_ num []
        where
            i2b_ num str
                | num == 0 = str
                | num == 1 = '1':str
                | otherwise = do
                    let next = num `div` 2
                    let this = if odd num then '1' else '0'
                    i2b_ next (this:str)

mapIncr = mapPlus 1
mapPlus n Nothing = Just n
mapPlus n a = (+) n <$> a

countIf f = length . filter f

enumDivisor :: Int -> [Int]
enumDivisor n = do
    let sqrted = floor $ sqrt (fromIntegral n)
        smaller = filter (\x -> mod n x == 0) [1..sqrted]
        bigger = reverse $ map (div n) smaller
    if head bigger == sqrted then smaller ++ (init bigger)
    else smaller ++ bigger

-- 
--
--

main = do
    [b, p] <- getIs
    putStrLn . show $ p * ((p - 1) ^ (b - 1))


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n;
vector<ll> vs;

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

  cin>>n;
  vs.resize(n);
  rep(i,n)cin>>vs[i];
  sort(all(vs));

  double crt=(double)(vs[0]+vs[1])/2.0;
  repl(i,2,n){
    double nxt=(crt+(double)vs[i])/2.0;
    crt=nxt;
  }
  printf("%.10f\n", crt);

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
	char a,b,c;
	scanf("%c%c%c\n",&a,&b,&c);
	printf("%c",a);
	scanf("%c%c%c\n",&a,&b,&c);
	printf("%c",b);
	scanf("%c%c%c\n",&a,&b,&c);
	printf("%c",c);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <sstream>
#include <istream>
#include <cmath>
#include <cstdio>

using namespace std;

#define vci vector<int>
#define vcs vector<string>
#define pb push_back
#define sz size()
#define mapii map<int, int>
#define mapci map<char, int>
#define mapsi map<string, int>
#define all(x) x.begin(), x.end()
#define minit(a, i) memset(a, i, sizeof(a));

#define for_(i, a, b) for (int i=(int)a; i<(int)b; i++)
#define for_d(i, a, b) for (int i=(int)a-1; i>=b; i--)
#define for_r(i, a, b, c) for (int i=(int)a; i<(int)b; i += c)
#define for_dr(i, a, b, c) for (int i=(int)a-1; i>=b; i -= c)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

typedef long long ll;

const int iINF = 2147483647;
const ll lINF = 9223372036854775807;

template <class T> inline void dbg(T t) { cout << t << endl; }


ll sti(string s) {
	ll len = s.length();
	if (len < 1) return 0;
	return (s[len - 1] - '0') + 10 * (sti(s.substr(0, len - 1)));
}


int main() {
	vci v(8);
	int N; cin >> N;
	
	for_(p, 0, N) {
		string line; cin >> line;
		int ln = sti(line);
		
		for_(i, 0, 8) {
			v[i] = ln % 10;
			ln /= 10;
		}
		
		sort(all(v));
		int maxi = 0, mini = iINF;
		do {
			int val = 0;
			for_(i, 0, 8) val += v[i] * pow(10, i);
			maxi = max(maxi, val);
			mini = min(mini, val);
		} while(next_permutation(all(v)));
		
		cout << maxi-mini << endl;
	}	
	
	return 0;
}

Measured memory_bytes: 1272