akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

#define dump(x)  cout << #x << " = " << (x) << endl;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(0);
    cout << std::fixed;

    ll n,t;
    cin >> n >> t;
    ll a[n];
    rp(i,n) cin >> a[i];
    ll f[n];
    ll mn = INF;
    rp(i,n) {
        mn = min(mn,a[i]);
        f[i] = mn;
    }
    ll mxDif = 0;
    ll numb = 0;
    rp(i,n){
        if(a[i] - f[i] > mxDif) {
            mxDif = a[i] - f[i];
            numb = 1;
        } else if(a[i] - f[i] == mxDif)
            ++numb;
    }
    cout << numb << "\n";
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

struct UnionFind{
  vector<int> par;

  UnionFind(int n) : par(n,-1) { }

  int root(int x){
    if(par[x] < 0) return x;
    return par[x] = root(par[x]);
  }

  bool merge(int x,int y){
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(par[x] > par[y]) swap(x,y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }
};

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> G(H);
  rep(i,H){
    cin >> G[i];
  }
  vector<ll> b(H*W,0),w(H*W,0);
  UnionFind uf(H*W);
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      if(G[i][j] == '#'){
        b[i*W+j] = 1;
      }else{
        w[i*W+j] = 1;
      }
    }
  }
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      for(int dir=0; dir<4; dir++){
        int ny = i+dy[dir];
        int nx = j+dx[dir];
        if(ny<0 or ny>=H or nx<0 or nx>=W) continue;
        if(G[i][j] == G[ny][nx]) continue;
        int now = i*W + j;
        int next = ny*W + nx;
        if(uf.root(now) != uf.root(next)){
          int temp_b = b[uf.root(now)] + b[uf.root(next)];
          int temp_w = w[uf.root(now)] + w[uf.root(next)];
          uf.merge(now,next);
          b[uf.root(now)] = temp_b;
          w[uf.root(now)] = temp_w;
        }
      }
    }
  }
  ll sum = 0;
  set<int> se;
  for(int i=0; i<H*W; i++){
    if(se.count(uf.root(i))) continue;
    sum += b[uf.root(i)] * w[uf.root(i)];
    se.insert(uf.root(i));

  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 9728
n = gets.chomp.to_i
map = {}

(n).times do |index|
  line = gets.chomp.split
  if (line[0][0] == 'i') then
    map[line[1]] = true
  elsif (line[0][0] == 'f') then
    puts (map.has_key?(line[1]) ? 'yes' : 'no')
  end
end

Measured memory_bytes: 168584
#include <stdio.h>

int main(){
  int x, y, total = 0;

  scanf("%d %d", &x, &y);

  if(x == 1){
    total += 300000;
  }
  else if(x == 2){
    total += 200000;
  }
  else if(x == 3){
    total += 100000;
  }

  if(y == 1){
    total += 300000;
  }
  else if(y == 2){
    total += 200000;
  }
  else if(y == 3){
    total += 100000;
  }

  if(x == 1 && y == 1)
    total+= 400000;

  printf("%d\n", total);
  return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python3
import sys


def solve(N: int, S: str, T: str):
    ans = ""
    for i in range(N):
        ans += S[i]
        ans += T[i]
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, S, T)

if __name__ == '__main__':
    main()


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

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
	int counts = 0;
	rep(i,n){
		if(a[a[i]-1] == i+1)counts++;
 	}
	cout << counts/2 << endl;
}

// cout << fixed << setprecision(15) <<  << endl;

Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
int n,i,j;
string s,s1;
bool tc,tf;
int main(){
	cin >> s;
	for(i=0;i<s.size();i++)
	  if(s[i]=='C'||s[i]=='F') s1+=s[i];
	if(s1.find("CF")!=string::npos) cout <<"Yes";
	else cout <<"No";	
	return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;
int h,w;
const int dx[]={1,0,-1,0};
const int dy[]={0,-1,0,1};
bool judge(int i,int j)
{
  if(i<0||i>=h||j<0||j>=w) return false;
  else return true;
}

int main()
{
  cin>>h>>w;
  vector<string> s(h);
  for(auto&& e: s) 
  {
    cin>>e;
  }
  int ans=0;
  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      if(s[i][j]=='#') continue;
      vector<vector<int>> num_field(h,vector<int>(w,-1));
      num_field[i][j]=0;
      queue<pair<int,int>> next_point;
      next_point.push(make_pair(i,j));
      while(!next_point.empty())
      {
        int x=next_point.front().first;
        int y=next_point.front().second;
        next_point.pop();
        for (int k = 0; k < 4; ++k)
        {
          int nx=x+dx[k],ny=y+dy[k];
          if(judge(nx,ny)&&num_field[nx][ny]==-1&&s[nx][ny]=='.')
          {
            next_point.push(make_pair(nx,ny));
            num_field[nx][ny]=1+num_field[x][y];
          }
        }
      }
      for (int x = 0; x < h; ++x)
      {
        for (int y = 0; y < w; ++y)
        {
          ans=(num_field[x][y]>ans)?num_field[x][y]:ans;
        }
      }
    }
  }
  cout<<ans;
}

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


//TEMPLATE
#define pb              push_back
#define mp              make_pair
#define ll              long long
#define ld              long double
//#define pi              3.1415926536
#define pi              acos(-1)
#define newline         printf("\n")
#define printminusone   printf("-1\n")
#define scl1(n)         scanf("%lld", &n)
#define scl2(a, b)      scanf("%lld %lld", &a, &b)
#define scl3(a, b, c)   scanf("%lld %lld %lld", &a, &b, &c)
#define printl(n)       printf("%lld\n", n)
#define ssl1(str)       scanf(" %[^\n]", str)
#define scd1(n)         scanf("%lf", &n)
#define scd2(a, b)      scanf("%lf %lf", &a, &b)
#define printd(n)       printf("%lf\n", n)
#define printld(n)      printf("%Lf\n", n)
#define printcase       printf("Case %lld: ", i)
#define reversed(s)     reverse(s.begin(), s.end())
#define asort(s)        sort(s.begin(), s.end())
#define dsort(s)        sort(s.rbegin(), s.rend())
#define for0(i, n)      for (i = 0; i < n; i++)
#define for1(i, n)      for (i = 1; i <= n; i++)
#define fori(itt, stt)  for(auto itt = stt.begin(); itt != stt.end(); itt++)
#define pii             pair <ll, ll>
#define piii            pair <ll, pii>
#define F               first
#define S               second
#define FR              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ms(arr, x)      memset(arr, x, sizeof arr)
#define bitcount(n)     __builtin_popcountll(n)
#define all(s)          s.begin(), s.end()

const ll INF = LLONG_MAX;
const ll SZ = 4e5+5;
const ll mod = 1e9+7;


unordered_map <ll, ll> dp;
ll a, b, c, d, n;

ll solve(ll v) {
    if(v == 0) return 0;
    if(v == 1) return d;
    if(dp[v]) return dp[v];

    ll i, r, t, res(INF);
    if(v < (res/d)) res = v*d;

    r = v%2;
    t = a + (r*d) + solve(v/2);
    res = min(res, t);
    if(v%2 != 0) {
        r = 2 - r;
        t = a + (r*d) + solve((v+r)/2);
        res = min(res, t);
    }

    r = v%3;
    t = b + (r*d) + solve(v/3);
    res = min(res, t);
    if(v%3 != 0) {
        r = 3 - r;
        t = b + (r*d) + solve((v+r)/3);
        res = min(res, t);
    }

    r = v%5;
    t = c + (r*d) + solve(v/5);
    res = min(res, t);
    if(v%5 != 0) {
        r = 5 - r;
        t = c + (r*d) + solve((v+r)/5);
        res = min(res, t);
    }

//    res = min(res, (v*d));

    return dp[v] = res;
}

int main() {
    FR;
    ll t = 0, x, y, z, i, j, k, g, p, q, ans = 0, sum = 0;
    string s, s1, s2;

    cin >> t;

    while(t--) {
        cin >> n >> a >> b >> c >> d;
        dp.clear();
        cout << solve(n) << "\n";
    }

    return 0;
}



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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define REP(i, N) for (int i = 0; i < N; i++)
constexpr ll M = 1e9 + 7;

int main()
{
    int n, k;
    cin >> n >> k;
    //vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
    ll dp[n+1][n+1];
    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < n + 1; j++) {
            if (j == 0) {
                dp[i][j] = 1;
            } else if (j == 1) {
                dp[i][j] = i;
            } else {
                dp[i][j] = 0;
            }
        }
    }
    for (int i = 2; i < n + 1; i++) {
        for (int j = 2; j < n + 1; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % M;
        }
    }
    for (int i = 1; i < k + 1; i++) {
        cout << (dp[n - k + 1][i] * dp[k - 1][i - 1]) % M << endl;
    }
    return 0;
}


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

int main() {
  int N, K, x2, xk;
  cin >> N >> K;
  x2 = xk = 1;
  
  for (int i = 0; i < N; i++) {
    x2 *= 2;
    xk += K;
    
    if (x2 < xk) {
      xk = x2;
    }
    
    else {
      x2 = xk;
    }
    
  }
  
  cout << x2 << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld double
#define F first
#define S second
#define sz size

using namespace std;

const int MAXN = 1e6 + 5;
const int inf = 1e9 + 7;
const int INF = 1e18;

string s;

int get_len(int l, int r) {
    int ct = 0;
    for (int i = l; i <= r; i++) {
        if (s[i] != 'A' && s[i] != 'C' && s[i] != 'T' && s[i] != 'G') break;
        else ct++;
    }
    return ct;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> s;
    int res = 0;
    for (int i = 0; i < s.sz(); i++) {
        res = max(res, get_len(i, int(s.sz()) - 1)) ;
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int lld;
typedef unsigned long long int llu;
#define INF (lld)(9223372036854775807)
#define IINF (int)(2147483647)

using namespace std;

int main(void) {
  string s, t;
  cin >> s >> t;
  lld c = 0;
  for (lld i = 0; i < s.length(); i++) {
    c += s[i] != t[i];
  }
  cout << c << "\n";
}

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

int main(){
    int n,x;
    int l[105];
    cin>>n>>x;
    for(int i=0;i<n;i++)  cin>>l[i];
    int ans=1,sum;
    int p=0;
    while(sum<=x && ans<n+1){
        sum+=l[p];
        p++;
        if(sum<=x) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

int N, W;
int w[210], acc[210];
int dp[201][10001];

signed main() {
    cin >> N >> W;
    rep(i,0,N) cin >> w[i];
    sort(w, w+N, greater<int>());

    rep(i,0,N) acc[i+1] = acc[i] + w[N-i-1];
    
    dp[0][0] = 1;
    rep(i,0,N) repq(j,0,W) {
        dp[i+1][j] = dp[i][j];
        if(j-w[i] >= 0) (dp[i+1][j] += dp[i][j-w[i]]) %= MOD;
    }
    repq(i,0,N) repq(j,1,W) (dp[i][j] += dp[i][j-1]) %= MOD;

    int ans = (W-acc[N] < 0 ? 0 : dp[N][W-acc[N]]);
    rep(i,0,N) {
        int sum = acc[i];
        if(W-sum < 0) continue;
        int vr = dp[N-i-1][W-sum];
        int vl = (W-sum-w[N-i-1] < 0 ? 0 : dp[N-i-1][W-sum-w[N-i-1]]);
        (ans += (vr - vl + MOD)) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 18808
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll> ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<endl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<a.size();zz++) cerr<<a[zz]<<" ";cerr<<endl
#define trii(x) cerr<<#x<<": ("<<x.F<<","<<x.S<<")\n";
#define trset(s) cerr<<#s<<": ";for(auto &i:s) cerr<<i<<" ";cerr<<"\n"
#define mod 1000000007ll
#define inf 9999999999999999ll
#define nl endl
#define sz(x) (ll)(x).size()
#define all(x) x.begin(), x.end()
#define modulo 998244353ll

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    string s;
    cin>>n>>s;
    vi r,g,b;
    for(ll i=0;i<n;i++)
    {
        if(s[i]=='R')
            r.pb(i);
        else if(s[i]=='G')
            g.pb(i);
        else
            b.pb(i);
    }
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        for(ll j=i+1;j<n;j++)
        {
            if(s[i]!=s[j])
            {
                char c;
                if(s[i]!='R' && s[j]!='R')
                    c='R';
                if(s[i]!='G' && s[j]!='G')
                    c='G';
                if(s[i]!='B' && s[j]!='B')
                    c='B';
                ll ind=2*j-i;
                ll count=0;
                if(c=='R')
                {
                    ll ind1=lower_bound(all(r),j+1)-r.begin();
                    count+=sz(r)-ind1;
                    if(binary_search(all(r),ind))
                    {
                        count--;
                    }
                }
                else if(c=='G')
                {
                    ll ind1=lower_bound(all(g),j+1)-g.begin();
                    count+=sz(g)-ind1;
                    if(binary_search(all(g),ind))
                    {
                        count--;
                    }

                }
                else
                {
                    ll ind1=lower_bound(all(b),j+1)-b.begin();
                    count+=sz(b)-ind1;
                    if(binary_search(all(b),ind))
                    {
                        count--;
                    }
                }
                ans+=count;
            }
        }
    }
    cout<<ans<<nl;
}


Measured memory_bytes: 3684
#include<stdio.h>
#define it register int
#define ct const int
#define il inline
typedef long long ll;
const int N=1000005;
int p[N][2];
int main(){
	int n;scanf("%d",&n);it i,j;
	for(i=1;i<=n;++i) scanf("%d%d",&p[i][0],&p[i][1]);
	ll ans=-2e18;
	for(it s=0;s<4;++s){
		ll mx=-1e18,mn=1e18,tmp;
		for(i=1;i<=n;mx=(tmp>mx?tmp:mx),mn=(tmp<mn?tmp:mn),++i)
			for(j=tmp=0;j<2;++j)
				tmp+=(s&(1<<j))?p[i][j]:-p[i][j];
		mx-=mn,ans=(ans>mx?ans:mx);
	}
	printf("%lld",ans);
  	return 0;
}


Measured memory_bytes: 3292
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int s[26],n;
char c[110001];
int main()
{
	cin>>n>>c;
	for(int i=0;i<n;i++)s[c[i]-'a']++;
	long long ans=1;
	for(int i=0;i<26;i++)ans=ans*(s[i]+1)%mod;
	cout<<(ans+mod-1)%mod<<'\n';
}


Measured memory_bytes: 384
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)


Measured memory_bytes: 472756
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int main() {
  int N; cin >>N;
  ll min,max,sum;
  min = INF; max = -INF; sum = 0;
  rep(i, N){
    ll buf; cin >>buf;
    chmin(min, buf); chmax(max, buf); sum += buf;
  }
  cout <<min <<" " <<max <<" " <<sum <<endl;
}



Measured memory_bytes: 3132
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int AplusB = Math.abs(A+B);

        if (AplusB % 2 == 0) {
            System.out.println(AplusB / 2);
        } else {
            System.out.println("IMPOSSIBLE");
        }
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b;cin>>a>>b;
  for (int i=1;i<=10000;i++){
    if (i*8/100==a&&i*10/100==b){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
  
}

Measured memory_bytes: 256
// D - Powerful Discount Tickets
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,n) for(int i=0;i<(n);i++)
#define allr(x) (x).rbegin(),(x).rend()

int main(){
	int N,M;cin>>N>>M;

	vector<int> A(N);
	vector<pair<int,int>> B;
	rp(i,N){
		int a; cin>>a;
		A[i] = a;
		while(a>0){
			B.push_back(make_pair(a - (a>>1), i));
			a>>=1;
		}
	}

	sort(allr(B));

	vector<int> counting(N);
	int e = min(M, (int)B.size());
	rp(i, e) counting[B[i].second]++;

	ll ans = 0;
	rp(i,N) ans += (ll)A[i]/(1<<counting[i]);
	cout<< ans <<endl;
}

Measured memory_bytes: 35044
import java.util.Scanner;

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

		StringBuffer sb1 = new StringBuffer();
		StringBuffer sb2 = new StringBuffer();

		boolean reverse = false;
		int n = scan.nextInt();
		for (int i = 0; i < n; i++) {
			int q = scan.nextInt();
			if (q == 1) {
				reverse = !reverse;
			} else {
				int f = scan.nextInt();
				String c = scan.next();
				if (f == 1 ^ reverse) {
					sb1.append(c);
				} else {
					sb2.append(c);
				}
			}
		}

		StringBuffer sb = new StringBuffer();
		sb1.reverse();
		sb.append(sb1);
		sb.append(s);
		sb.append(sb2);
		if (reverse) {
			sb.reverse();
		}

		System.out.println(sb.toString());
		scan.close();
	}
}


Measured memory_bytes: 118860
#include <functional>
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include <numeric>
#include<string>
using ll = long long;
using namespace std;
# define maxn 50
# define maxm 50

int main() {
  vector <int>a(3);
  cin>>a.at(0)>>a.at(1)>>a.at(2);
  sort(a.begin(),a.end());
  cout << a[0]+a[1];
}


Measured memory_bytes: 888
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

MOD = 10**9 + 7

def main():
    n,m = getlist()
    anums = getlist()

    accsum = [0]
    tmp = 0

    for anum in anums:
        tmp += anum
        tmp %= m
        accsum.append(tmp)

    cnt = defaultdict(int)

    for acc in accsum:
        cnt[acc] += 1

    res = 0

    for cn in cnt.values():
        res += (cn * (cn-1) ) // 2

    print(res)
    # print(cont)

if __name__ == '__main__':
    main()



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

int m, g;
int dp[8][1001];
int a[7], b[7];

int main () {
	while (cin >> m, m) {
		for (int i = 0; i < m; i++) {
			cin >> a[i] >> b[i];
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 0; i < m; ++i) { // カードの種類
			for (int j = 0; j <= 1000; ++j) { // 点数
				for (int k = 0; k <= b[i]; ++k) { // 枚数
					if (j + a[i] * k > 1000) continue;
					dp[i + 1][j + a[i] * k] += dp[i][j];
				}
			}
		}
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			cout << dp[m][x] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl;
typedef long long ll;
int n,p[20];
ll m,a[20],inf=1e18,f[1<<20],g[1<<20];
ll gcd(ll x,ll y){
	if(x>y) swap(x,y);
	while(x>0){
		y%=x;
		swap(x,y);
	}
	return y;
}
int main(){
	cin>>n>>m;
	rep(i,n) cin>>a[i];
	rep(i,n) cin>>p[i];
	rep(i,1<<n){
		ll now=1,cnt=0;
		rep(j,n){
			if((i>>j)&1){
				cnt++;
				if(m/a[j]<now/gcd(now,a[j])){
					f[i]=-1;
					break;
				}
				now=now/gcd(now,a[j])*a[j];
			}
		}
		if(f[i]==-1) f[i]=0;
		else f[i]=(m/now)*(cnt%2 ? -1 : 1);
	}
	f[0]=0;
	rep(i,n) for(int j=(1<<n)-1;j>=0;j--) if(((j>>i)&1)==1) f[j]+=f[j-(1<<i)];
	double ans=0;
	rep(i,1<<n){
		double pr=1;
		rep(j,n){
			if((i>>j)&1) pr*=(double)p[j]/100.0;
			else pr*=(double)(100.0-p[j])/100.0;
		}
//		cout<<i<<" "<<pr<<" "<<f[i]<<endl;
		ans-=pr*f[i];
	}
	printf("%.12f\n",ans);
}

Measured memory_bytes: 9384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long answer=0;
    for(int i=1;i<=n;i++)
    {
        if(!(i%3==0 or i%5==0))
            answer+=i;
    }
    cout<<answer<<endl;
    return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    int n;
    cin>>n;
    int t=0;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>a[i];
    }

     for(int i=1; i<n; i++)
    {
        if(i==a[i])
        {swap(a[i],a[i+1]);t++;}
    }
     for(int i=n; i>1; i--)
    {
        if(i==a[i])
        {swap(a[i],a[i-1]);t++;}
    }
    cout<<t<<endl;
    return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i,b,e) for (common_type_t<decltype(b),decltype(e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define rep(i,n)   FOR (i, size_t{}, n)
#define ALL(x)     begin (x), end (x)
using namespace std;
using ll = int64_t;
constexpr ll inf = 2e18;

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);

  size_t n, q;
  ll k;
  cin >> n >> k >> q;
  vector <ll> point (n);
  vector <bool> ans (n, true);
  string table [] = {"No", "Yes"};
  rep (i, q)
  {
    size_t a;
    cin >> a;
    -- a;

    ++ point [a];
  }

  for (auto && elem : point)
  {
    ll p = k - static_cast <ll> (q) + elem;
    if (p <= 0)
    {
      cout << "No" << endl;
    }
    else cout << "Yes" << endl;
  }

}


Measured memory_bytes: 1408
#ABC170 C 通せず
x, n = map(int, input().split())
seisulist = list(map(int, input().split()))
numlist = [i for i in range(0,102) if i not in seisulist]
xretu = [x]*len(numlist)
hikizan = [abs(s-t) for (s, t) in zip(numlist, xretu)]
sa = min(hikizan)
if x-sa not in seisulist:
    print(x-sa)
else:
    print(x+sa)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<int>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  int n,m;
  cin >> n >> m;
  Graph k(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    k[a].push_back(b);
    k[b].push_back(a);
  }
  int u[n];
  rep(i,n)u[i]=0;
  u[0]=1;
  u[k[0][0]]=1;
  vector<int> a;
  vector<int> b;
  int o=0;
  while(true){
    a.push_back(o);
    int nxt=-1;
    for(int v: k[o]){
      if(u[v]==0){
        nxt=v;
      }
    }
    if(nxt==-1)break;
    o=nxt;
    u[o]++;
  }
  o=k[0][0];
  while(true){
    b.push_back(o);
    int nxt=-1;
    for(int v: k[o]){
      //if(o==1&&v==3)cout << u[v] << endl;
      if(u[v]==0){
        nxt=v;
      }
    }
    if(nxt==-1)break;
    o=nxt;
    u[o]++;
  }
  cout << a.size()+b.size() << endl;
  rep(i,a.size())cout << a[a.size()-1-i]+1 << " ";
  //cout << endl;
  rep(i,b.size()-1)cout << b[i]+1 << " ";
  cout << b[b.size()-1]+1 << endl;
  //cout << k[0][0] << endl;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

ll n;

ll solve() {
    ll ans = 1e18;
    FOR (i, 1, 1e6+10) {
        if (n%i == 0) {
            ans = min(ans, i+n/i);
        }
    }
    return ans-2;
}

int main() {
    cin >> n;
    cout << solve() << endl;
}

Measured memory_bytes: 256
import sys

input_data = []
input_pointer = 0

output_data = []

def input_scan():
    global input_data
    input_data = sys.stdin.readlines()
    input_data = [x[:-1] for x in input_data]

def next_line():
    global input_pointer
    global input_data
    if input_pointer < len(input_data):
        input_pointer += 1
        return input_data[input_pointer - 1]
    else:
        return ""

def append_output(string):
    global output_data
    output_data.append(string)

def print_output():
    global output_data
    output_data.append("")
    sys.stdout.write("\n".join(output_data))

# Problem A
# alpha = input()
# if alpha.isupper():
#     print("A")
# else:
#     print("a")

# Problem B
# input_scan()
# [n, k] = [int(x) for x in next_line().split(" ")]
# fruits = sorted([int(x) for x in next_line().split(" ")])
# print(sum(fruits[:k]))

# Problem C
# num = int(input())

# dictionary = "abcdefghijklmnopqrstuvwxyz"

# def convert_to_alpha(num):
#     if num == 0:
#         return ""
#     quot = num // 26
#     rem = num % 26
#     if rem == 0:
#         return "z" + convert_to_alpha(quot - 1)
#     else:
#         return dictionary[rem - 1] + convert_to_alpha(quot)

# name = ""
# print("".join(reversed(convert_to_alpha(num))))

# Problem D
input_scan()

next_line()
from collections import Counter
nums = [int(x) for x in next_line().split(" ")]
total_sum = sum(nums)
nums = Counter(nums)


q = int(next_line())
for i in range(q):
    [b, c] = [int(x) for x in next_line().split(" ")]
    # print("Dict before replacing {} with {} = {}".format(b, c, str(nums)))
    diff = c - b
    total_sum += nums[b] * diff
    occ = nums[b]
    if c in nums:
        nums[c] += occ
    else:
        nums[c] = occ
    nums[b] = 0

    # print("Dict before replacing {} with {} = {}".format(b, c, str(nums)))
    append_output(str(total_sum))

print_output()


Measured memory_bytes: 35184
#include <bits/stdc++.h>
using namespace std;
int main(){
    int h,n;
    cin >> h >> n;
    vector <int> a(n);
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum+=a[i];
    }
    if(sum<h){
        cout << "No" <<endl;
    }else{
        cout << "Yes" <<endl;
    }
    return 0;
}

Measured memory_bytes: 640
if __name__ == '__main__':
    n = int(input())
    ls = []
    for i in range(n):
        ls.append(int(input()))
    ls.sort()

    ans = [int(str(i) + str(j)) for i in ls[:3 + 1] for j in ls[:3 + 1] if i != j] if n > 3 else [int(str(i) + str(j)) for i in ls for j in ls if i != j]
    print(sorted(ans)[2])


Measured memory_bytes: 5932
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#define ll long long
using namespace std;



int main(){
  ll X,A;
  cin>>X>>A;
  if(X<A) cout<<"0"<<endl;
  else cout<<"10"<<endl;

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x))%modulo)
#define Inf 100000000000000000



int main(){
	int N;
	cin>>N;
	int cnt = 0;
	for(int i=1;i<=N;i++){
		int k = i;
		int ans = 0;
		while(k!=0){
			ans ++;
			k/=10;
		}
		if(ans%2==1)cnt++;
	}
	cout<<cnt<<endl;
	
	
	
	
	return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
#include <cmath>

using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))


const vector<i64> RHMOD = {999999937LL, 1000000007LL};


struct Rolling_Hash{
	int n;
	i64 base;
	vector<vector<i64>> hs,pw;
	Rolling_Hash(){}
	Rolling_Hash(const string & s , i64 base_ = 9973) : n(s.size()), base(base_) ,  hs(RHMOD.size(),vector<i64>()) , pw(RHMOD.size(),vector<i64>()){
		for(int i = 0;i < RHMOD.size();i++){
			hs[i].assign(n + 1, 0);
			pw[i].assign(n + 1, 0);
			hs[i][0] = 0;
			pw[i][0] = 1;
			for(int j = 0;j < n;j++){
				pw[i][j + 1] = pw[i][j] * base % RHMOD[i];
				hs[i][j + 1] = (hs[i][j] * base + s[j]) % RHMOD[i];
			}
		}
	}

	i64 hash(int l,int r,int i){
		return ((hs[i][r] - hs[i][l] * pw[i][r - l]) % RHMOD[i] + RHMOD[i]) % RHMOD[i];
	}

	i64 match(int l1,int r1,int l2,int r2){
		bool res = true;
		for(int i = 0;i < RHMOD.size();i++) res &= (hash(l1,r1,i) == hash(l2,r2,i));
		return res;
	}
};

string s;
int n;
int m;

int main(){
	cin >> n >> m;
	cin >> s;
	Rolling_Hash rh(s);
	set<pair<i64,i64>> st;
	int l = 0;
	int r = 1;
	for(int i = 0;i < m;i++){
		string q;
		cin >> q;
		if(q == "L++"){
			l++;
		}
		else if(q == "L--"){
			l--;
		}
		else if(q == "R++"){
			r++;
		}
		else if(q == "R--"){
			r--;
		}

		st.emplace(rh.hash(l, r, 0) , rh.hash(l, r,1));
	}

	cout << st.size() << endl;
}



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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

long double n,m,d,ans;

signed main() {
    cin >> n >> m >> d;
    rep(i,m-1) {
        if (d) ans += 2*(n-d)/(n*n);
        else ans += 1.0/n;
    }
    cout << setprecision(20) << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL) ; cout.tie(NULL);
#define MOD 1000000007

ll dp[3005][3005];
ll a[3005];

int main() 
{  
	int n,i,j;
    cin>>n;

    for(i=0;i<n;i++)
    	cin>>a[i];
    
    for(i=n-1;i>=0;i--)
    {
    	for(j=i;j<n;j++)
    	{
    		if(i==j)
    			dp[i][j]=a[i];
    		else
    		    dp[i][j]=max(a[i]-dp[i+1][j],a[j]-dp[i][j-1]);
    	}
    }
   /* 
    for(i=0;i<=n;i++)
    {
    	for(j=0;j<=k;j++)
    		cout<<dp[i][j]<<" ";
    	    cout<<"\n";
    	}
    */		
    cout<<dp[0][n-1]<<"\n";
 	return 0;
}

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

class Program
{
    static void Main()
    {
        var N = int.Parse(ReadLine());
        var S = new string[N];
        for (int i = 0; i < N; i++)
        {
            S[i] = ReadLine();
        }

        long M = S.Count(x => x.First() == 'M');
        long A = S.Count(x => x.First() == 'A');
        long R = S.Count(x => x.First() == 'R');
        long C = S.Count(x => x.First() == 'C');
        long H = S.Count(x => x.First() == 'H');

        var L = M * A * R + M * A * C + M * A * H + M * R * C + M * R * H + M * C * H + A * R * C + A * R * H + R * C * H + A * C * H;
        WriteLine(L);
    }
}

Measured memory_bytes: 23648
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        System.out.println(solve(in));
        
      }
      
      public static String solve(Scanner in) {

        String S = in.next();
        String T = in.next();
        int count = 0;

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == T.charAt(i)) count++;
        }

        return String.valueOf(count);
      }
      
    
}

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

int main() {
  char N[4];
  scanf("%s" ,&N) ;

  if ( N[0] == N[1] && N[1] == N[2]|| N[1] == N[2] && N[2] == N[3] ) {
    puts("Yes" );
  }
  
  else puts("No") ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}

int main()
{
	int a=read(),b=read();
	cout<<max({a+b,a-b,a*b})<<endl;
	return 0;
}



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

def output_ary():

    s = ''

    for x in A:

        s = s + str(x) + ' '
    
    print(s.rstrip())

output_ary()

i = 1

while i < N:

    V = A[i]

    j = i - 1

    while j >= 0 and A[j] > V:

        A[j + 1] = A[j]
        
        j -= 1
    
    A[j + 1] = V

    i += 1

    output_ary()



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

using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define FOR(i, a, b) for (ll i = (a), i < (N): i++)
#define all(A) (A).begin(), (A).end()

int main(){
    int N;
    cin >> N;
    int A[N + 2];
    A[0] = 0;
    A[N + 1] = 0;
    rep(i, N) cin >> A[i + 1];

    int total = 0;
    rep(i, N + 1) total += abs(A[i] - A[i + 1]);
    rep(i, N) {
        cout << total - abs(A[i] - A[i + 1]) - abs(A[i + 1] - A[i + 2]) + abs(A[i] - A[i + 2]) << endl;
    }

    return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

struct cnt{
	ll zero, one, inv;
	bool operator == (const cnt &other) const {
		return zero * other.one == one * other.zero;
	}
	bool operator < (const cnt &other) const {
		return zero * other.one < one * other.zero;
	}
};

vector<vector<int>> graph(200010, vector<int>());
vector<int> a(200010), sz(200010, 1);

void dfs1(int n, int p) {
	for (int i : graph[n]) {
		if (i == p) continue;
		dfs1(i, n);
		sz[n] += sz[i];
	}
}

vector<priority_queue<cnt>> que(200010);
vector<int> look(200010);

void dfs2(int n, int p) {
	int s = 0; int idx = -1;
	for (int i : graph[n]) {
		if (i == p) continue;
		dfs2(i, n);
		if (chmax(s, sz[i])) {
			look[n] = look[i];
			idx = i;
		}
	}
	for (int i : graph[n]) {
		if (i == p) continue;
		if (look[i] != look[n]) {
			while (!que[look[i]].empty()) {
				cnt q = que[look[i]].top(); que[look[i]].pop();
				que[look[n]].push(q);
			}
		}
	}
	if (a[n] == 0) {
		que[look[n]].push({ 1,0,0 });
	}
	else {
		cnt nq = { 0,1,0 };
		while (!que[look[n]].empty() && nq < que[look[n]].top()) {
			cnt q = que[look[n]].top(); que[look[n]].pop();
			nq.inv += q.inv + nq.one * q.zero;
			nq.zero += q.zero;
			nq.one += q.one;
		}
		que[look[n]].push(nq);
	}
}

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

	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int v;
		cin >> v;
		v--;
		graph[i].pb(v);
		graph[v].pb(i);
	}
	rep(i, n) cin >> a[i];
	rep(i, n) look[i] = i;
	dfs1(0, -1); dfs2(0, -1);
	int v = look[0];
	vector<cnt> vec;
	while (!que[v].empty()) {
		cnt q = que[v].top(); que[v].pop();
		vec.pb(q);
	}
	ll ans = 0, onesum = 0;
	for (cnt c : vec) {
		ans += c.inv + onesum * c.zero;
		onesum += c.one;
	}
	cout << ans << '\n';
}

Measured memory_bytes: 60588
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a) (a).begin(), (a).end()
using namespace std;

const int mod = 1e9+7;

vector<string> split(string s){
  vector<string> res;
  string tmp;
  rep(i,s.size()){
    if(isalpha(s[i]))tmp += s[i];
    else if(s[i] == ' '){
      res.push_back(tmp);
      tmp = "";
    }
  }
  res.push_back(tmp);
  return res;
}

int n;
int a,t,g,c,m;
map<string,int> id;
vector<string> rule[55];

void parse(int cur, vector<int> &seq){
  for(string s : rule[cur]){
    if((int)seq.size()>n)return;
    if(isupper(s[0])){
      int k = 0;
      rep(i,s.size()){
	if(s[i] == 'A')k |= 1<<0;
	if(s[i] == 'T')k |= 1<<1;
	if(s[i] == 'G')k |= 1<<2;
	if(s[i] == 'C')k |= 1<<3;
      }
      seq.push_back(k);
    }else parse(id[s],seq);
  }
}

int dp[2][55][55][55];

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  cin >> a >> t >> g >> c >> m; cin.ignore();
  n = a+t+g+c;

  rep(i,m){
    string s;
    getline(cin,s);

    vector<string> vs = split(s);
    id[vs[0]] = i;
    rep(j,vs.size()-1)rule[i].push_back(vs[j+1]);
  }

  vector<int> seq;
  parse(0,seq);
  if((int)seq.size()!=n){
    cout << 0 << endl;
    return 0;
  }

  dp[0][0][0][0] = 1;
  rep(i,n){
    int cur = i&1, nxt = 1-cur;
    rep(A,a+1)rep(T,t+1)rep(G,g+1)dp[nxt][A][T][G] = 0;

    rep(A,a+1)rep(T,t+1)rep(G,g+1){
      if(seq[i]&1 && A+1<=a){
	(dp[nxt][A+1][T][G] += dp[cur][A][T][G]) %= mod;
      }
      if((seq[i]>>1)&1 && T+1<=t){
	(dp[nxt][A][T+1][G] += dp[cur][A][T][G]) %= mod;
      }
      if((seq[i]>>2)&1 && G+1<=g){
	(dp[nxt][A][T][G+1] += dp[cur][A][T][G]) %= mod;
      }
      if((seq[i]>>3)&1 && i-A-T-G<=c){
	(dp[nxt][A][T][G] += dp[cur][A][T][G]) %= mod;
      }
    }
  }
  cout << dp[n&1][a][t][g] << endl; 
}

Measured memory_bytes: 2476
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

d = abs(A - B)
dV = V - W

if dV == 0:
  print("NO")
elif  dV < 0:
  print("NO")

elif d / dV  <=  T:
  print('YES')
else:
  print("NO")

Measured memory_bytes: 9132
#include <cmath>
#include <cstdio>
#include <algorithm>
#define Pi acos(-1.0)

using namespace std;

const int N=8e5+10,Mod=924844033;

struct Edge{ int to,next;} way[N<<1];

int n,num[N],tot,A[N],B[N],P[N],F[N<<4],fact[N],fact_inv[N];

void Build(int a,int b) { way[++tot]=(Edge){b,num[a]}; num[a]=tot; }

void Init()
{
	scanf("%d",&n);
	int a,b;
	for (int i=2;i<=n;++i)
	{
		scanf("%d%d",&a,&b);
		Build(a,b); Build(b,a);
	}
}

int son[N];
void Dfs(int x,int fa)
{
	son[x]=1;
	for (int i=num[x];i;i=way[i].next)
	{
		int v=way[i].to;
		if (v==fa) continue;
		Dfs(v,x);
		son[x]+=son[v];
		A[son[v]]--;
	}
	if (n-son[x]) A[n-son[x]]--;
}

int R[N<<2],L;
int inv(int x)
{
	int t=Mod-2,ret=1;
	while (t)
	{
		if (t&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		t>>=1;
	}
	return ret;
}

int qpow(int x,int k)
{
	int ret=1;
	while (k)
	{
		if (k&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		k>>=1;
	}
	return ret;
}

void ntt(int *a,int f){
    for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
    for(int i=1;i<n;i<<=1){
        int gn=qpow(5,(Mod-1)/(i<<1));
        for(int j=0;j<n;j+=i<<1){
            int g=1;
            for(int k=0;k<i;k++,g=1ll*g*gn%Mod){
                int x=a[j+k],y=1ll*g*a[j+k+i]%Mod;
                a[j+k]=(x+y)%Mod;
                a[j+k+i]=(x-y+Mod)%Mod;
            }
        }
    }
    if(f==-1){
        reverse(a+1,a+n);
        int ny=qpow(n,Mod-2);
        for(int i=0;i<n;i++)a[i]=1ll*a[i]*ny%Mod;
    }
}

void Solve()
{
	Dfs(1,0);A[n]=n; 
	fact[0]=1; for (int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%Mod;
	int ny=inv(fact[n]);fact_inv[n]=ny;
	for (int i=n-1;i;--i) fact_inv[i]=1ll*fact_inv[i+1]*(i+1)%Mod;
	fact_inv[0]=1;
	for (int i=0;i<=n;++i) B[i]=fact_inv[i];
	for (int i=0;i<=n;++i) A[i]=1ll*(A[i]+Mod)*fact[i]%Mod;
	for (int i=0;i<=n;++i) P[i]=A[n-i];
	
    int m=n,_n=n;
    for(n=1;n<=m<<1;n<<=1) L++;
    for(int i=0;i<n;i++)R[i]=R[i>>1]>>1|((i&1)<<(L-1));
	ntt(P,1); ntt(B,1); 
    for(int i=0;i<n;i++)F[i]=1ll*P[i]*B[i]%Mod;
    ntt(F,-1);
	for (int i=_n-1;i>=0;--i) 
		printf("%lld\n",1ll*F[i]*fact_inv[_n-i]%Mod);
}

int main()
{
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 42752
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

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

using namespace std;

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

const int MOD = 1000000007;

signed main()
{
    int n, m;
    cin >> n >> m;
    
    vvi dp(n+1, vi(n+1));
    dp[1][0] = 1;
    
    rep(i, m){
        vvi next(n+1, vi(n+1));
        
        rep(a, n+1) rep(b, n+1){
            if(a+b > n) continue;
            next[a+b][0] = (next[a+b][0] + dp[a][b] * ll(a)) % MOD;
            next[a][b] = (next[a][b] + dp[a][b] * ll(b)) % MOD;
            if(b+1 <= n) next[a][b+1] = (next[a][b+1] + dp[a][b] * ll(n-a-b)) % MOD;
        }
        
        swap(dp, next);
    }
    
    cout << dp[n][0] << endl;
}


Measured memory_bytes: 1028