akhauriyash/Code-Regression huggingface dataset:
from heapq import heapify, heappop


def sort(xs):
    heapify(xs)
    return [heappop(xs) for _ in range(len(xs))]


def run():
    n = int(input())
    elements = []
    for _ in range(n):
        v, w, t, d, s = input().split()
        elements.append((int(v), int(w), t, int(d), s))

    for e in sort(elements):
        print("{} {} {} {} {}".format(*e))


if __name__ == '__main__':
    run()



Measured memory_bytes: 31408
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int a = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();
        if (a >= 3200) { Console.WriteLine(s); }
        else { Console.WriteLine("red"); }
    }
}


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

using namespace std;

#define int long long
#define endl '\n'
#define MOD 1000000007
#define maxn 100010

int lcm(int a, int b) {
    return (a * b) / __gcd(a, b);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    int ans = 0, lc = 1;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];

        ans += v[i] - 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i = s; i < n; i++)
const ll maxn = 2e5+10;
ll N,X;
ll in[maxn];
ll cumsum[maxn];
double ans = 1e100;

int main(){
	cin>>N>>X;
	rep(i,0,N){
		scanf("%lld", &in[i+1]);
	}
	cumsum[1] = in[1];
	rep(i,2,N+1){
		cumsum[i] = cumsum[i-1]+in[i];
	}
	rep(k,1,N+1){
		double tmp=0.0;
		for(int i = N; i >=0; i-=k){
			if(i==N) tmp+=5*cumsum[i];
			else if(N-k==i)continue;
			else tmp+=2*cumsum[i];
		}
		tmp+=X*N+k*X;
		// cout<<tmp<<endl;
		ans = min(ans,tmp);
	}
	cout<<(ll)ans<<endl;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e6;
const long long int mod = 1e9+7;
typedef pair<ll,ll> pairs;
vector<pairs> p;


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

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// ------------------------------------

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

    map<char, ll> t;
    for(ll i=0;i<n;++i){
        t[s[i]]++;
    }
    ll ans=1;
    for(auto val : t){
        ans *= val.second + 1;
        ans %= mod;
    }
    ans--;
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 512
from collections import deque
import random
isdebug=0
if isdebug==0:
    N=int(input())
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
else:
    N=20*10**4
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=random.randrange(i+1),i+1
        G[a].append(b)
        G[b].append(a)
dist=[-1 for i in range(N)]
X=[]
Y=[]
q=deque([0])
dist[0]=0
while(len(q)>0):
    r=q.popleft()
    if dist[r]%2==0:
        X.append(r)
    else:
        Y.append(r)
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=dist[r]+1
            q.append(p)
P=[0 for i in range(N)]
que=deque([])
if min(len(X),len(Y))<=N//3:
    for i in range(1,N+1):
        if i%3==0:
            que.appendleft(i)
        else:
            que.append(i)
    if len(X)<len(Y):
        for i in X:
            t=que.popleft()
            P[i]=t
        for i in Y:
            t=que.pop()
            P[i]=t
    else:
        for i in Y:
            t=que.popleft()
            P[i]=t
        for i in X:
            t=que.pop()
            P[i]=t
else:
    for i in range(1,N+1):
        if i%3==0:
            que.appendleft(i)
    for i in range(1,N+1):
        if i%3==1:
            que.appendleft(i)
        elif i%3==2:
            que.append(i)
    for i in X:
        t=que.popleft()
        P[i]=t
    for i in Y:
        t=que.pop()
        P[i]=t
print(*P)


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

int main() {

  int N;
  map<int, int> mochi;

  cin >> N;
  int m;

  for(int i=0; i<N; i++) { 
    cin >> m;
    mochi[m]++;
    
  }

  cout << mochi.size() << endl;
  return 0;
}
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
const long long MOD=1e9+7;
const double PI=3.14159265359;



int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    long long q,h,s,d,n;
    cin>>q>>h>>s>>d>>n;
    
    s=min(s,min(2*h,4*q));
    cout<<(min(s*n, d*(n/2)+s*(n%2)));
    
    
    //getPos();
    return 0;
    
}

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

using namespace std;

int main()
{
  int n, m;
  string s;
  while(cin >> n, n) {
    cin >> m >> s;
    int len = s.size();
    s += "#####";
    int dp[2][1000010];
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < len; i++) {
      if(s[i] == 'I') {
	if(dp[0][i] == -1) dp[0][i] = 0;
	if(s[i+2] == 'I') dp[0][i+2] = dp[0][i]+1;
      } else if(s[i] == 'O') {
	if(dp[1][i] == -1) dp[1][i] = 0;
	if(s[i+2] == 'O') dp[1][i+2] = dp[1][i]+1;
      }
    }
    int cnt = 0;
    for(int i = 2; i < len; i++) {
      if(dp[0][i] >= n && dp[1][i-1] >= n-1) cnt++;
    }
    cout << cnt << endl;
  }
  return 0;
}

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

int main() {
	unsigned int a, b;
	cin >> a >> b;

	cout << bitset<32>(a&b) << endl;
	cout << bitset<32>(a|b) << endl;
	cout << bitset<32>(a^b) << endl;

	return 0;
}



Measured memory_bytes: 3148
// 基本テンプレート

#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 <fstream>
#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, A, B, C, D;

signed main() {
    cin >> N >> A >> B >> C >> D;
    bool ok = false;
    repq(x,0,N) {
        int up = x, down = (N - 1 - x);
        int base = C * (2 * x - N + 1);
        int d = D - C;
        int ub = base + up * d + A;
        int lb = base - down * d + A;

        if(lb <= B && B <= ub) ok = true;
    }
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>

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

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fr first
#define sc second



int main() {
	int k, s, ans = 0;
	cin >> k >> s;
	for (int i = 0;i <= k;i++) {
		for (int j = 0;j <= k;j++) {
			if (i + j >= s - k&&i + j <= s)ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
S = list(input())
e = [0]*(N+1)
w = [0]*(N+1)
if S[0] == 'E':
    e[0] += 1
else:
    w[0] += 1
for i in range(1, N):
    if S[i] == 'E':
        e[i] += e[i-1] + 1
        w[i] += w[i-1]
    else:
        e[i] += e[i-1]
        w[i] += w[i-1] + 1
        
ans = float('inf')
for i in range(N):
    tmp = w[i-1] + e[N-1] - e[i]
    ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 67824
// AtCoder Beginner Contest 111 - Problem C: /\/\/\/ (https://beta.atcoder.jp/contests/abc111/tasks/arc103_a)
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ii = pair<ll, ll>;

#define REP(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define REPN(i, N) for (int (i) = 0; (i) < N; (i)++)
#define DEC(i, b, a) for (int (i) = (b); (i) >= (a); (i)--)
#define DECN(i, N) for (int (i) = N - 1; (i) >= 0; (i)--)

#define LOG(var, sep) (cerr << #var << " = " << (var) << (sep))
#define LOGM(msg) (cerr << (msg))
#define LOGV(vec, sep) { cerr << #vec << " ="; for (const auto& v : (vec)) cerr << " " << v; cerr << (sep); }
#define LOGA(arr, N, sep) { cerr << #arr << " ="; for (int i = 0; i < N; ++i) cerr << " " << (arr)[i]; cerr << (sep); }
#define LOGA2(arr, N, M, sep) { cerr << #arr << " =\n"; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) cerr << (arr)[i][j] << " "; cerr << endl; } cerr << (sep); }

ostream& operator<<(ostream& os, const ii& p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

const int MAX { 2000010 };
const int oo { 2000000010 };
const int MOD { 1000000007 };

int vs[MAX];

void solve(int N)
{
    map<int, int> hist[2];
    vector<ii> cost[2];

    REPN(k, 2)
    {
        for (int i = k; i < N; i += 2)
            ++hist[k][vs[i]];

        hist[k][100001] = 0;

        for (const auto& p : hist[k])
        {
            int v, n;
            tie(v, n) = p;

            cost[k].push_back(ii(N/2 - n, v));
        }

        sort(cost[k].begin(), cost[k].end());
    }

    auto ans = cost[0][0].second == cost[1][0].second ? min(cost[0][0].first + cost[1][1].first,
        cost[0][1].first + cost[1][0].first) : cost[0][0].first + cost[1][0].first;

    cout << ans << endl;
}

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

    int N;
    cin >> N;

    REPN(i, N)
        cin >> vs[i];

    solve(N);

    return 0;
}


Measured memory_bytes: 7668
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stdlib.h>
#define ll long long
#define MOD_P 1000000007
using namespace std;

bool isACGT(char c)
{
	if (c == 'A' || c == 'C' || c == 'G' || c == 'T') {
		return true;
	}
	return false;
}

int main()
{
	string test;
	int n, q, countAC = 0;
	int l, r;

	cin >> n >> q;
	cin >> test;
	vector<int> numberAC(n);

	numberAC[0] = 0;
	for (int i = 1; i < n; i++) {
		if (test[i - 1] == 'A' && test[i] == 'C') {
			countAC++;
		}
		numberAC[i] = countAC;
	}

	for (int i = 0; i < q; i++) {
		cin >> l >> r;
	/*	printf("f(%d) = %d\n", r, numberAC[r - 1]);
		printf("f(%d) = %d\n", l, numberAC[l - 1]);*/
		printf("%d\n", numberAC[r - 1] - numberAC[l - 1]);
	}

	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define all(a) (a).begin(),(a)end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)

int main() {

  int heap[250];

  int H;
  scanf("%d",&H);

  rep(i,H){
    scanf("%d",&heap[i]);
  }

  rep(i,H){
    printf("node %d: key = %d, ",i+1,heap[i]);
    if((i-1)/2>=0&&i!=0) printf("parent key = %d, ",heap[(i-1)/2]);
    if(2*i+1<H) printf("left key = %d, ",heap[2*i+1]);
    if(2*i+2<H) printf("right key = %d, ",heap[2*i+2]);
    putchar('\n');
  }
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
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-1;i>=0;i--)
#define Pool(i, m, n) for(ll i=n-1;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#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 count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(x) cout<<x<<endl
#define Gput(a,b) G[a].push_back(b)
int main() {
  ll n,m;
  cin>>n>>m;
  vec a(n);
  vec b(n);
  loop(i,n){
    cin>>a[i]>>b[i];
  }
  vector<tuple<ll,ll>> ab(n);
  loop(i,n){
    ab.push_back(make_tuple(a[i],b[i]));
  }
  sort(all(ab));
  ll ans=0;
for( tuple<ll,ll> t : ab ){
    ll x,y;
    tie(x,y)=t;
    if(m>y){
      ans+=x*y;
      m-=y;
      continue;
    }
    if(m<=y){
      ans+=x*m;
      break;
    }
  }
  
 
 
 putout(ans);
 
 
 
 
 
 
 
 
}

Measured memory_bytes: 6400
-- Kaisetsu

main = do
    n <- read <$> getLine
    let fullList = [x | x<-primes 55555, x`mod`5==1]
    let answer = printList $ take n fullList
    putStrLn answer

printList :: [Int] -> String
printList []     = []
printList (x:xs) = show x++" "++(printList xs)

primes :: Int -> [Int]
primes 1 = []
primes n = 2:[x| x<-[3,5..n], and [mod x k /=0 | k<-primes (sqrtI x) ]]

sqrtI :: Integral a => a -> Int
sqrtI = floor.sqrt.fromIntegral

Measured memory_bytes: 892
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    a,b = LI()
    if not (a*b)%2:
        print("Even")
    else:
        print("Odd")
    return

#B
def B():
    s = S()
    print(s.count("1"))
    return

#C
def C():
    n = I()
    a = LI()
    f = 0
    for j in range(100000):
        for i in range(n):
            if a[i]%2:
                f = 1
                break
            a[i] //= 2
        if f:break
    print(j)
    return

#D
def D():
    a,b,c,x = IR(4)
    su = 0
    for i in range(a+1):
        for j in range(b+1):
            for k in range(c+1):
                if 500*i+100*j+50*k == x:su += 1
    print(su)
    return

#E
def E():
    n,y = LI()
    for i in range(n+1):
        for j in range(n+1-i):
            k = n-i-j
            if 10000*i+5000*j+1000*k == y:
                print(i,j,k)
                quit()
    print(-1,-1,-1)
    return

#F
def F():
    s = input()
    while s:
        if s[:11] == "dreameraser":
            s = s[11:]
        elif s[:10] == "dreamerase":
            s = s[10:]
        elif s[:7] == "dreamer":
            s = s[7:]
        elif s[:6] == "eraser":
            s = s[6:]
        elif s[:5] == "dream":
            s = s[5:]
        elif s[:5] == "erase":
            s = s[5:]
        else:
            print("NO")
            quit()
    print("YES")
    return

#G
def G():
    n,a,b = LI()
    h = IR(n)
    return

#H
def H():
    n = I()
    a = LI()
    a.sort()
    m = a[-1]
    i = bisect.bisect_left(a,m//2)
    b = float("inf")
    c = float("inf")
    if i > 0:
        k = a[i-1]
        l = m-a[i-1]
        b = max(k,l)-min(k,l)
    if i < n-1:
        d = a[i]
        l = m-a[i]
        c = max(d,l)-min(d,l)
    if b < c:
        print(m,k)
    else:
        print(m,d)
    return

#Solve
if __name__ == "__main__":
    H()


Measured memory_bytes: 60656
#include <bits/stdc++.h>
using namespace std;
 
#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    string s;
    cin >> s;

    int menor = INFINITO;
    for ( size_t i = 0; i < s.size() - 2; i++ ) {
        // cout << s.substr(i, i + 2) << endl;
        menor = min(menor, abs(753 - stoi(s.substr(i, 3))));
    }

    cout << menor << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int f(int n) {
    if (n % 2 == 0)
        return n/2;
    else
        return 3*n + 1;    
}

int main(){
    int s;
    cin >> s;
    int i = 2;
    vector<int> v = {s};
    while (true){
        int next = f(v.back());
        if (v.end() != find(v.begin(), v.end(), next)) {
            cout << i << endl;
            break;
        }
        else {
            v.push_back(next);
            ++i;
        }
    }
    return 0;
}

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

using data_map = std::vector<std::vector<char>>;

int main() {
    int h, w;
    std::cin >> h >> w;

    data_map map;
    for (auto y = 0; y < h; ++y) {
        std::vector<char> line(w);
        for (auto& p : line) {
            std::cin >> p;
        }
        if (!std::all_of(std::begin(line), std::end(line),
            [](char c) { return c == '.'; })) {
            map.push_back(line);
        }
    }

    for (auto i = w - 1; 0 <= i ; --i) {
        bool ret = true;
        for (auto& line : map) {
            if (line[i] != '.') {
                ret = false;
                break;
            }
        }
        if (ret) {
            for (auto& line : map) {
                line.erase(std::begin(line) + i);
            }
        }
    }
    for (auto& line : map) {
        for (auto& v : line) {
            std::cout << v;
        }
        std::cout << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);
	  int N = Integer.parseInt(sc.next());
	  int[] h = new int[N];
	  for(int i = 0; i < N; i++)
		  h[i] = Integer.parseInt(sc.next());
	  
	  int[] temp = new int[N];
	  temp[0] = 0;
	  temp[1] = temp[0] + Math.abs(h[1] - h[0]);
	  for(int i = 2; i < N; i++) {
		  int a = Math.abs(h[i] - h[i-1]);
		  int b = Math.abs(h[i] - h[i-2]);
		  temp[i] = Math.min(a + temp[i-1], b + temp[i-2]);
	  }
	  System.out.println(temp[N-1]);
	  
	  sc.close();
	  
  }
}

Measured memory_bytes: 48792
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define ms(s,x) memset(s,x,sizeof(s))
#define pb push_back
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;

const double PI = acos(-1.0);
const double eps = 1e-8;
const ll MOD = 1e9+7;
const int MAXN = 1e5+5;

int main()
{
    int n, ans = inf, mini = 100, maxi = 1;
    int x[105];
    cin >> n;
    rep(i, 1, n){
        cin >> x[i];
        mini = min(mini, x[i]);
        maxi = max(maxi, x[i]);
    }
    rep(p, mini, maxi){
        int sum = 0;
        rep(i, 1, n){
            sum += (x[i] - p) * (x[i] - p);
            if (sum >= ans) break;
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	int h, w;
	cin >> h >> w;
	char c;
	vvi vv(h + 2, vi(w + 2, 0));
	rep(i, h) {
		rep(j, w) {
			cin >> c;
			vv[i + 1][j + 1] = ((c=='#') ? 1 : 0);
		}
	}
	bool ans = true;
	int x[] = { 1,0,-1,0 }, y[] = { 0,-1,0,1 };
	rep(i, h) {
		rep(j, w) {
			if (vv[i + 1][j + 1]) {
				bool check = false;
				rep(k, 4) {
					if (vv[i + 1 + x[k]][j + 1 + y[k]]==1) {
						check = true;
					}
				}
				if (!check)ans = false;
			}
		}
	}
	cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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



int main()
{
  ll N; cin>>N;
  vector<ll> a(N); rep(i,N) cin>>a[i];
  
  ll count=1;
  rep(i,N){
    if(a[i]==count) count++;
  }
  if(count==1) {cout<<-1<<endl; return 0;}
  else cout<<N-(count-1)<<endl;
  return 0;
}


Measured memory_bytes: 4844
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define x real()
#define y imag()
#define fi first
#define se second
#define pii pair<int, int>

const int N = 1e5 + 1000;
int a[N], b[N], c[N], dp[N][3];
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i][0] = max({dp[i - 1][1] + a[i], dp[i - 1][2] + a[i]});
		dp[i][1] = max({dp[i - 1][0] + b[i], dp[i - 1][2] + b[i]});
		dp[i][2] = max({dp[i - 1][1] + c[i], dp[i - 1][0] + c[i]});
	}
	cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}



Measured memory_bytes: 4992
N,K = map(int,input().split())
*A, = map(int,input().split())

M = len(bin(K))-2

B = [[0]*N for _ in [0]*M]
B[0] = [a-1 for a in A]
for i in range(1,M):
    for j in range(N):
        B[i][j] = B[i-1][B[i-1][j]]

k = K
a = 0
while k>0:
    if k%2==1:
        a = B[0][a]
        k -= 1
        continue
    j = 1
    while k%(2**(j+1))==0:
        j += 1
    a = B[j][a]
    k -= 2**j
print(a+1)

Measured memory_bytes: 203768
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define print(A,n) for(ll i=0;i<n;++i)cout<<A[i]<<' ';cout<<endl;
#define take(A,n) for(ll i=0;i<n;++i)cin>>A[i];
//    for(auto& it : m)
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
//  priority_queue<ll int> pq;
//  priority_queue <ll int, vector<ll int>, greater<ll int> > pq;
//  vector<ll int> v;
//  vector< pair<ll int,ll int> > v;
//  set<ll int>::iterator it=s.begin();
//  unordered_map<  pair<ll int,ll int>, ll int> mp;
 
 
const int ALPHABET_SIZE = 26; 
  
// trie node 


int main() 
{ 
ll int T;T=1;
while(T--)
{ll int N,i,ans=0;cin>>N;
  for(i=0;i<=N;i++)
  {
    if(i%3==0||i%5==0)
    {
      continue;
    }
    else ans+=i;
  }

cout<<ans<<endl;
}


       
    return 0; 
} 


Measured memory_bytes: 3580
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 c = sc.nextInt();
		if(a + b >= c) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
	
}

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

int main() {
	int X, Y;
	cin >> X >> Y;

	for (int i = 0; i <= X; i++) {
		if (i * 2 + (X - i) * 4 == Y) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0;i<n;i++)
 
using namespace std;
 
 
int main()
{
	int a,b,c,x,y,ans;
	cin>>a>>b>>c>>x>>y;
	if(a+b>=c*2){
		int cost=min(x,y);
		x-=cost,y-=cost;
		ans+=c*2*cost;
		if(a*x+b*y>c*2*max(x,y)){
			ans+=c*2*max(x,y);
		}
		else{
			ans+=a*x+b*y;
		}
	}
	else{
		ans+=a*x+b*y;
	}
	cout<<ans<<endl;
	}
	

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;

    int main()
    {
        int n,r,d,i,p1=0,p2=0;
        int s=0;
        cin>>n;
        int arr[n];
        for(i=0;i<n;i++)
        {
            cin>>arr[i];
            s=s+arr[i];
        }
        s=s/n;
        
        for(i=0;i<n;i++)
        p1=p1+(arr[i]-s)*(arr[i]-s);
        s=s+1;
        for(i=0;i<n;i++)
        p2=p2+(arr[i]-s)*(arr[i]-s);
        if(p1<p2)
        cout<<p1;
        else
        cout<<p2;
        return 0;
    }
        
        
        
        
        
    
        
    


Measured memory_bytes: 256
N = int(input())
ball_array = list(map(int, input().split()))
count_array = [0] * (N+1)
for i in ball_array:
    count_array[i] += 1
ans_max = 0

for i in count_array:
    ans_max += (i * (i-1) // 2)

for i in ball_array:
    count = count_array[i]
    print(ans_max - (count-1))



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

using namespace std;


void solve() {
    string s;
    cin >> s;
    bool t = false;
    for (int i = 0; i < 3; i++) {
        t |= s[i] == s[i+1];
    }
    cout << (t?"Bad":"Good");
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


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

int main() {
    string str, c;
    int q;
    cin >> str >> q;

    for (int i = 0; i < q; i++) {
        cin >> c;
        if (c == "print") {
            int a, b;
            cin >> a >> b;
            cout << str.substr(a, b - a + 1) << endl;
        } else if (c == "reverse") {
            int a, b;
            cin >> a >> b;
            string sub = str.substr(a, b - a + 1);

            for (int i = 0; i < b - a + 1; i++) {
                str[b - i] = sub[i];
            }
        } else {
            int a, b;
            string p;
            cin >> a >> b >> p;
            str.replace(a, b - a + 1, p);
        }
    }
}

Measured memory_bytes: 1220
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<limits>
#include<stdio.h>
using namespace std;
typedef long long ll;

void solve() {
	string str;
	cin >> str;
	if (str == "Sunny") {
		cout << "Cloudy" << endl;
	}
	else if (str == "Cloudy") {
		cout << "Rainy" << endl;
	}
	else if (str == "Rainy") {
		cout << "Sunny" << endl;
	}
	
}


int main() {
	solve();

}

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

int main() {
    int cnt;
    cin >> cnt;
    int* num= new int[cnt];
    if (num == NULL) { return -1; }
    for (int i = 0; i < cnt; i++) {
        cin >> num[i];
    }
    int Scnt = 0;
    bool flag = true;
    while (flag) {
        flag = false;
        for (int i = cnt - 1; i >= 1; i--) {
            if (num[i] < num[i - 1]) {
                swap(num[i], num[i - 1]);
                Scnt++;
                flag = true;
            }
        }
    }
    for (int i = 0; i < cnt; i++) {
        if (i)cout << ' ';
        cout << num[i];
    }
    cout << endl<<Scnt<<endl
        ;
    delete num;
    return 0;
}


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


int main()
{
    long long int n,k,a[200005],i,stp,val,idx;
    bool vis[200005];
    long long int steps[200005];
    cin>>n>>k;
    for(i=1;i<=n;i++)
        cin>>a[i];
    memset(vis,false,sizeof(vis));
    long long int looplen,cnt,inipos,reppos,rem;

    vis[1]=true;
    idx=1;
    steps[1]=0;
    stp=0;
    while(true)
    {
        stp+=1;
        val=a[idx];
        if (vis[val])
        {
        // cout<<"loop detected at"<<steps[val]<<" after that at step "<<stp<<endl;
        inipos=steps[val];
        reppos=stp;
        looplen=stp-steps[val];
            break;
        }
        else{
            vis[val]=1;
            steps[val]=stp;
            idx=val;
        }
    }
    if (k<=inipos)
    {
        // while loop
        idx=1;
        stp=0;
        while(stp<k)
        {
            stp+=1;
            val=a[idx];
            idx=val;
            
        }
        cout<<val<<endl;

    }
    else{
        stp=0;
        idx=1;
        while(stp<inipos)
        {
            stp+=1;
            val=a[idx];
            idx=val;
            
        }
        idx=val;
        // cout<<val<<endl;

        rem=k-inipos;
        cnt=rem%looplen;
        // while loop
        stp=0;
        while(stp<cnt)
        {
            stp+=1;
            val=a[idx];
            idx=val;
            
        }
        cout<<val<<endl;

    }
    
    
}

Measured memory_bytes: 6960
let s = Array.to_list @@ Array.init 4 @@ fun _ -> Scanf.scanf " %c" @@ fun c -> c
let s' = List.sort_uniq compare s |> Array.of_list
let c = Array.length s'
let list_count f ls =
  let rec list_count_kernel count = function
  | [] -> count
  | x :: xs -> list_count_kernel (if f x then count + 1 else count) xs
  in
    list_count_kernel 0 ls
let _ = print_endline @@
  if c <> 2 then "No"
  else
    if list_count ((=) s'.(0)) s = 2 && list_count ((=) s'.(1)) s = 2 then "Yes" else "No"

Measured memory_bytes: 384
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int main(){
  long long N,M;
  cin >> N >> M;
  vector < pair<long long, long long> > vec(N);
  for (long i = 0; i < N; i++){
    cin >> vec[i].first >> vec[i].second;
  }
  sort(vec.begin(), vec.end());
  long long res = 0;
  for(long i = 0; i < N && M > 0; i++){
    res += min(M, vec[i].second) * vec[i].first;
    M -= min(M, vec[i].second);
  }
  cout << res << endl;
}




Measured memory_bytes: 1792
s=list(input())

ksum=0
# itertools 使用 bit全探索
import itertools
for i in itertools.product([0,1], repeat=len(s)-1):
    isum=0
    nstr=s[0]
    for ii in range(len(s)-1):
        if i[ii]==0:
            nstr=nstr+s[ii+1]
        elif i[ii]==1:
            isum=isum+int(nstr)
            nstr=s[ii+1]
    isum=isum+int(nstr)
    ksum=ksum+isum
#    print(isum,i)
print(ksum)



Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	for (;;) {
		int N; cin >> N;
		if (N == 0) break;
		vector< vector<bool> > a(21, vector<bool>(21));
		int cnt = N;
		while (N--) {
			int x, y; cin >> x >> y;
			a[y][x] = true;
		}
		int x = 10, y = 10;
		int M; cin >> M;
		while (M--) {
			string d; int l; cin >> d >> l;
			int dx = 0, dy = 0;
			if (d == "N") dy = 1;
			if (d == "E") dx = 1;
			if (d == "S") dy = -1;
			if (d == "W") dx = -1;
			while (l--) {
				x += dx; y += dy;
				if (a[y][x]) {
					a[y][x] = false;
					cnt--;
				}
			}
		}
		cout << (cnt == 0 ? "Yes" : "No") << endl;
	}
}

Measured memory_bytes: 1196
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
string S[1010];
typedef pair<int, int> P;
typedef pair<int, P> PP;
int d[1010][1010];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int H, W;
int bfs() {
    priority_queue<PP, vector<PP>, greater<PP>> que;
    rep(i, 1010) rep(j, 1010) d[i][j] = INF;
    rep(i, 1010) {
        rep(j, 1010) {
            if (S[i][j] == '#') {
                d[i][j] = 0;
                que.push({0, {i, j}});
            }
        }
    }
    while(!que.empty()) {
        PP p = que.top(); que.pop();
        int x = p.second.first;
        int y = p.second.second;
        rep(i, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 0 || xx >= H || yy < 0 || yy >= W) continue;
            if (d[xx][yy] != INF) continue;
            if (d[x][y] + 1 < d[xx][yy]) {
                d[xx][yy] = d[x][y] + 1;
                que.push({d[xx][yy], {xx, yy}});
            }
        }
    }
    int ans = 0;
    rep(i, H) {
        rep(j, W) {
            ans = max(ans, d[i][j]);
        }
    } 
    return ans;
}

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

    cin >> H >> W;
    
    rep(i, H) cin >> S[i];
    cout << bfs() << endl;


    return 0;
}


Measured memory_bytes: 18668
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,m=map(int,input().split())
a=list(map(int,input().split()))
lst=[0]+list(accumulate(a))
# print(lst)
dic=defaultdict(int)
for i in range(n+1):
    dic[lst[i]%m]+=1
# print(dic)
lis2=list(dic.items())
# print(lis2)
ans=0
for i in lis2:
    ans+=i[1]*(i[1]-1)//2
print(ans)

Measured memory_bytes: 88172
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:   
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1 

    return res

n = int(input())
a = [int(x) for x in input().split()]

from collections import Counter

c = Counter(a)
flag = 1
for i in a:
    if c[i] > 1 and i != 1:
        flag = 0
if flag:
    if max_gcd_pair(a) <= 1:
        print('pairwise coprime')
        sys.exit()

import math
from functools import reduce

def gcd(*numbers):
    return abs(reduce(math.gcd, numbers))

if gcd(*a) == 1:
    print('setwise coprime')
    sys.exit()

else:
    print('not coprime')


Measured memory_bytes: 257136
#include "bits/stdc++.h"
 
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<VVLL> VVVLL;

#define SORT_ASC(c) sort((c).begin(), (c).end())
#define SORT_DESC(c) sort((c).begin(), (c).end(), greater<typeof((c).begin())>())
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FORL(i,a,b) for(LL i=(a);i<(b);++i)
#define REPL(i,n)  FORL(i,0,n)
#define SIZE(a) int((a).size())
#define ALL(a) (a).begin(),(a).end()
 
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         rotate(k,itr2,last);
         return true;
      }
   }
   rotate(first,k,last);
   return false;
}

inline double get_time_sec(void){
    return static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count())/1000000000;
}

template<typename T>
T gcd(T a, T b) {
    if(a > b) swap(a, b);
    if(a == 0) return b;
    else return gcd(b%a, a);
}

template<typename T>
map<T, T> prime_list(T n) {
    map<T, T> ret;
    for(T i = 2; i*i <= n; i++) {
        if(n % i == 0) {
            ret[i] = 0;
            while(n % i == 0) {
                n /= i;
                ret[i]++;
            }
        }
    }
    if(n != 1) ret[n]++;
    return ret;
}

#define MOD 1000000007

LL mypow(LL a, LL n) {
    if(n == 1) return a % MOD;
    if(n % 2 == 1) return (a * mypow(a, n-1)) % MOD;
    LL t = mypow(a, n/2);
    return (t * t) % MOD; 
}

int main(void) {
    int n, m;
    cin >> n >> m;
    n -= m;
    cout << (m * 1900 + n * 100) * pow(2, m) << endl;
}

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

using ll = long long;

#define mod 1000000007
#define REP(i, n) for (int i = 0; i < n; i++)
#define INF (1 << 29)

using namespace std;

//long C(long n, long r);
//long long gcd(long long a, long long b);
//long long lcm(long long a, long long b);
 

void solve() {
    int N;
    cin >> N;
    int m[N+1][N+1];
    bool flag[N+1][N+1];
    ll ans = 0ll;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> m[i][j];
            flag[i][j] = false;
            ans += (ll)m[i][j];
        }
    }

    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if(m[i][j] > m[i][k] + m[k][j]){
                    cout << -1 << endl;
                    return;
                }
                else if(m[i][j] == m[i][k] + m[k][j] && i != k && j != k){
                    flag[i][j] = true;
                }
            }
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(flag[i][j]) ans -= (ll)m[i][j];
        }
    }
    cout << ans/2 << endl;
}
 
int main() {
    solve();
    return 0;
}


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int k, t; cin >> k >> t;
    int maxi = 0;
    for (int i = 0; i < t; i++) {
        int c; cin >> c;
        maxi = max(maxi, c);
    }
    cout << max(0, maxi * 2 - k - 1) << "\n";
    return 0;
}

Measured memory_bytes: 256
N = int(input())
query = []
for i in range(N):
  query.append(list(map(int, input().split())))
  
query.sort(key=lambda x: x[2],reverse=True)

marker = [0]*101
for Cx in range(101):
  marker[Cx] = [True]*101
  for Cy in range(101):
    h = -1
    for i in range(N):
      X,Y,H = query[i]
      if H==0:
        if h > abs(Cx-X)+abs(Cy-Y):
          marker[Cx][Cy] = False
          break
      else:
        a = H+abs(Cx-X)+abs(Cy-Y)
        if h == -1:
          h = a
        elif h != a:
          marker[Cx][Cy] = False
          break
    if marker[Cx][Cy] == True:
      ans = [Cx,Cy,h]
      print(*ans)
      exit()

Measured memory_bytes: 3064
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
p=[0]*n
for i in range(q):
  pp,x=map(int,input().split())
  p[pp-1]+=x
from collections import deque
d=deque()
d.append(0)
visited=[False]*n
visited[0]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    p[i]+=p[g]
print(*p)

Measured memory_bytes: 105364
N=int(input())
A=[int(i) for i in input().split()]
A_=sorted(A)
if A==A_:
  print("YES")
  exit()
for i in range(N):
  for j in range(i):
    B=A[::]
    B[i],B[j]=B[j],B[i]
    if B==A_:
      print("YES")
      exit()
print("NO")

Measured memory_bytes: 38768
#include<bits/stdc++.h>
#define LL long long
#define db long double

using namespace std;
const int N=(1<<20)+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
LL ans;
struct node
{
    int a,b,i;
    bool operator < (const node &bb) const {return 1ll*b*bb.a>1ll*a*bb.b;}
}a[N];
priority_queue<node> hp;
int n,fa[N],ff[N];
int findf(int x){return ff[x]==x?x:ff[x]=findf(ff[x]);}

int main()
{
    /////
    n=rd();
    for(int i=2;i<=n;++i) fa[i]=rd();
    for(int i=1;i<=n;++i)
	ff[i]=i,hp.push(a[i]=((rd()&1)?(node){0,1,i}:(node){1,0,i}));
    for(int h=1;h<=n;++h)
    {
	int x=hp.top().i,na=hp.top().a,nb=hp.top().b;
	hp.pop();
	if(na<a[x].a||nb<a[x].b){--h;continue;}
	int fz=findf(fa[x]);
	ans+=1ll*a[fz].b*a[x].a,a[fz].a+=a[x].a,a[fz].b+=a[x].b,ff[findf(x)]=fz;
	if(fz) hp.push(a[fz]);
    }
    printf("%lld\n",ans);
    return 0;
}
 


Measured memory_bytes: 10352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e6+5;

int lol[100][100];

signed main(){
    IOS();

    int n; cin>>n;

    ll re = 0;
    for( int i = 0; i<n; ++i) {
        int n2 = 0, n5 = 0;
        string x; cin>>x;
        ll y = 0; bool dec = 0;
        for (char c : x) {
            if (dec) --n2, --n5;
            if (c == '.') {
                dec = 1; continue;
            }
            y = y*10ll + (c-'0');
        }
        assert(y!=0);
        bug(y);
        while (y % 2 == 0) {
            ++n2; y/=2;
        }
        while (y%5 == 0) {
            ++n5; y/=5;
        }
        bug(n2, n5);
        for (int I = -n2 + 50; I<100; ++I) {
            for (int j = -n5 + 50; j<100; ++j) {
                re += lol[I][j];
            }
        }

        lol[n2+50][n5+50]++;
//        sort(ALL(v));
    }
    cout<<re<<endl;
}


Measured memory_bytes: 3656
#include <iostream>
#include <string>
 
class Baseball
{
    u_int runner, out, point;
     
public:
    Baseball();
    ~Baseball(){}
    
    u_int get_runner() const {return runner;}
    u_int get_out() const {return out;}
    u_int get_point() const {return point;}
    
    void game();
    void event_hit();
    void event_homerun();
    void event_out();
     
private:
    void set_runner(const u_int r) {runner = r;}
    void inc_runner() {++runner;}
    void inc_out() {++out;}
    void add_point(const u_int p) {point += p;}
};
 
Baseball::Baseball()
{
    runner = 0;
    out = 0;
    point = 0;
}

void Baseball::game()
{
    std::string event;
    while(get_out() != 3){
        std::cin >> event;
        if(event == "HIT"){
            event_hit();
        }
        else if(event == "HOMERUN"){
            event_homerun();
        }
        else{
            event_out();
        }
    }
} 

void Baseball::event_hit()
{
    if(get_runner() == 3){
        add_point(1);
    }
    else{
        inc_runner();
    }   
}
 
void Baseball::event_homerun()
{
    add_point(1 + get_runner());
    set_runner(0);
}
 
void Baseball::event_out()
{
    inc_out();
}
 
int main()
{
    u_int inning;
    std::cin >> inning;
     
    for(u_int i = 0; i < inning; ++i){
        Baseball b_ball;
        b_ball.game();
        std::cout << b_ball.get_point() << std::endl;
    }
 
    return 0;
}

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

ll arr[100010],dp[100010];

ll solve(ll cur,ll n)
{
	if(dp[cur]!=1e18)return dp[cur];
	if(cur+2<=n)
		return dp[cur]=min(dp[cur],min(abs(arr[cur+1]-arr[cur])+solve(cur+1,n),abs(arr[cur+2]-arr[cur])+solve(cur+2,n)));
	else if(cur+1<=n)
		return dp[cur]=min(dp[cur],abs(arr[cur+1]-arr[cur])+solve(cur+1,n));
	else return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)cin>>arr[i],dp[i]=1e18;
	cout<<solve(1,n)<<"\n";
	return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF=1001001001;

long long int answ(long long int x){
  if(x==1) return 1;
  if(x>1) return 2*answ(x/2)+1;
}
int main() {
    long long int n;
    cin>>n;
    map<string,int> dict;
    for(string x;n--;dict[x]++){
        cin>>x;
    }
    cout<<dict.size()<<endl;
    
}


Measured memory_bytes: 19188
import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            // in
            String N = sc.next();

            // calc
            int sum = 0;
            for (char c : N.toCharArray()) {
                sum += Integer.parseInt(String.valueOf(c));
            }
            System.out.println(sum % 9 == 0 ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 50340
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mod = 2019;

signed main(void){ 
  
  string S; cin >> S;
  
  reverse(S.begin(),S.end());
  
  map<int,int> mp;
  
  mp[0]++;
  
  int res = 0;
  
  int digit = 1LL;
  
  int ans = 0;
  
  for(int i = 0; i < (int)S.size(); i++){ 
    
    res = (res + digit*(int)(S[i]-'0'))%mod;
    
    ans += mp[res];
    
    mp[res]++;
    
    digit = (digit*10)%mod;
    
  }
  
  cout << ans << endl;
  
  return 0;
}
   

Measured memory_bytes: 3732