akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
const int INF=INT_MAX; 
using namespace std;
void merge_sort(vector<int>& A, int l, int r);
void merge(vector<int>& A, int l, int m, int r);

int c = 0;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i=0;i<n;i++) cin >> A[i];
    merge_sort(A, 0, n);
    for(int i=0;i<n;i++) cout << A[i] << " \n"[i==n-1];
    cout << c << endl;
    
    return 0;
}


void merge(vector<int>& A, int l, int m, int r){
    
    int n1 = m - l;
    int n2 = r - m;
    int L[n1], R[n2];
    for(int i=0;i<n1;i++) L[i] = A[l+i];
    for(int i=0;i<n2;i++) R[i] = A[m+i];
    int i=0,j=0;
    for(int k=l;k<r;k++){
    	c++;
        if( i<n1 and (j>=n2 or L[i]<=R[j])){
            A[k] = L[i];
            i++;
        }else if(j<n2){
            A[k] = R[j];
            j++;
        }
    }
    
}
void merge_sort(vector<int>& A, int l, int r){
    if(l+1<r){
        int m = ((l+r)/2);
        merge_sort(A, l, m);
        merge_sort(A, m, r);
        merge(A, l, m, r);
    }
}


Measured memory_bytes: 6576
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <list>
#include <math.h>
#include <string.h>
#include <bitset>
#include <queue>
using namespace std;

typedef pair<int, int> P;
#define INF (1LL<<60)
#define int long long
#define ll long long
#define mod 1000000007


int N;
int a[123456];

// idxが残れるか
bool func(int idx){
	cerr << idx << endl;
	int size = 0;
	for (int i = 0; i <= idx; i++)
		size += a[i];

	for (int i = idx + 1; i < N; i++){
		if (a[i] <= size * 2) size += a[i];
		else return false;
	}
	return true;

}


signed main(){

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> a[i];

	sort(a, a + N);

	int ok = N - 1;
	int ng = -1;

	while ( abs(ok-ng)>1){
		int mid = (ok + ng) / 2;
		if (func(mid))
			ok = mid;
		else
			ng = mid;
	}

	cout << N - ok << endl;

	return 0;
}


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

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define EACH(begin, end) for(auto itr = (begin); itr != (end); itr++)

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;



ll N = 0;
vector<ll> a;
vector<ll> b;
ll ret = 0;

void input() {
  IN(N);
  ll tmp;
  REP(i, N) {
    IN(tmp);
    a.pb(tmp);
  }
}

void solve() {
  ll x = 0;
  REP(i, N) {
    x += a[i]*((i%2==0)?1:-1);
  }
  b.pb(x/2);
  REP(i, N-1) {
    b.pb(a[i]-b[i]);
  }
  REP(i, N) {
    cout << 2*b[i] << " ";
  }
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 3060
-- https://atcoder.jp/contests/abc173/tasks/abc173_d
-- 最初に挿入された値は、2番目の値だけで左右を独占するため1度だけ得点になる
-- 2番目以降に挿入された数値は左右にそれぞれ挿入可能なため2度得点にできる
-- 大きい順に挿入することで、常に2回ずつポイントにできる

import Data.List
import Data.Ord

calcPoint :: [Int] -> Int
calcPoint [] = 0
calcPoint vs = (sum . take (length vs) $ concatMap (replicate 2) vs) - head vs

main :: IO ()
main = do
  _ <- getLine
  fs <- sortOn Down . map read . words <$> getLine :: IO [Int]
  print $ calcPoint fs


Measured memory_bytes: 104956
#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=150;
int B[maxn],N,ans,now;
int main(){
	scanf("%d",&N);
	for(int i=1;i<N;i++) scanf("%d",&B[i]);
	ans=B[1]; now=B[1];
	for(int i=2;i<N;i++){
		ans+=min(now,B[i]);
		now=B[i];
	}
	ans+=now;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	int i;

	cin.tie(0);
	ios_base::sync_with_stdio(false);

	ll a,b;
	cin >> a >> b;
	if(a*b<=0){
		cout << "Zero" << endl;
		return 0;
	}
	if(a>0 || a==b){
		cout << "Positive" << endl;
		return 0;
	}
	if(b<0 && a!=b){
		if((b-a)%2==0) cout << "Negative" << endl;
		else cout << "Positive" << endl;
		return 0;
	}



	return 0;
}


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}


void solve() {
    int H, W;
    cin >> H >> W;
    const int inf = 1e9;

    map<int, int> mp; // mp[今] = 最初の位置
    multiset<int> diff; // mpで管理してる区間における 今 - 最初 の集合

    for (int i = 0; i < W; i++) {
        mp[i] = i;
        diff.insert(0);     
    }
    
    for (int i = 0; i < H; i++) {
        // cerr << "mp: ";
        // for(auto e : mp) {
        //     cerr << e << " ";
        // }
        // cerr << endl;

        // cerr << "diff: ";
        // for(auto e : diff) {
        //     cerr << e << " ";
        // }
        // cerr << endl;

        int a, b;
        cin >> a >> b;
        a--; // 半開区間 [a, b)
        auto it = mp.lower_bound(a);
        while(it->first < b && it != mp.end()) {
            if (mp.find(b) == mp.end() || it->second > mp.at(b)) {
                if (b == W) {
                    if (diff.find(inf) == diff.end()) {
                        diff.insert(inf);
                    }
                } else {
                    if (mp.find(b) != mp.end() && diff.find(b - mp.at(b)) != diff.end()) {
                        diff.erase(diff.lower_bound(b - mp.at(b)));
                    }
                    diff.insert(b - it->second);
                }
                mp[b] = it->second;
            }
            diff.erase(diff.lower_bound(it->first - it->second));
            it = mp.erase(it);
        }

        if (*diff.begin() >= inf) {
            cout << -1 << endl;
        } else {
            cout << *diff.begin() + i + 1 << endl;
        }
    }
    // cerr << "mp: ";
    // for(auto e : mp) {
    //     cerr << e << " ";
    // }
    // cerr << endl;
    // cerr << "diff: ";
    // for(auto e : diff) {
    //     cerr << e << " ";
    // }
    // cerr << endl;

}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}


Measured memory_bytes: 22372
N, M = map(int,input().split())
H = list(map(int,input().split()))
AB = [list(map(int,input().split())) for o in range(M)]
flag = [1]*N

for x in range(M):
    if H[AB[x][0] -1] > H[AB[x][1] -1]:
        flag[AB[x][1] -1] = 0
    elif H[AB[x][0] -1] < H[AB[x][1] -1]:
        flag[AB[x][0] -1] = 0
    elif H[AB[x][0] -1] == H[AB[x][1] -1]:
        flag[AB[x][0] -1] = 0
        flag[AB[x][1] -1] = 0

print(flag.count(1))



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

int main() {
    int w, h, n;
    cin >> w >> h >> n;
    int x[n], y[n], a[n];

    //入力
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> a[i];
    }

    //面積
    int mx1 = 0, mx2 = 0, mx3 = 0, mx4 = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 1 && x[i] > mx1) mx1 = x[i]; 
        if (a[i] == 2 && w - x[i] > mx2) mx2 = w - x[i]; 
        if (a[i] == 3 && y[i] > mx3) mx3 = y[i];
        if (a[i] == 4 && h - y[i] > mx4) mx4 = h - y[i]; 
    }

    w = w - mx1 - mx2;
    h = h - mx3 - mx4;
    if (h < 0) h = 0;
    if (w < 0) w = 0;

    cout << w * h << endl;

    return 0;

}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N; cin >> N;

    i64 X = -1;
    REP(x, 50000) {
        string xs = to_string(x * 108);
        i64 m = stol(xs.substr(0, xs.length() - 2));
        if (N == m) {
            X = x;
            break;
        }
    }

    if (X == -1) cout << ":(" << endl;
    else cout << X << endl;

    return 0;
}


Measured memory_bytes: 3708
#include <iostream>
#include <algorithm>

int n;
long long a[100005];
int main(){
  std::cin>>n;
  for(int i=0;i<n;++i)
    std::cin>>a[i];
  std::sort(a,a+n);
  
  long long ans1=0;
  {
//    std::cout<<"ans1"<<std::endl;
    int twoplus=(n-2+2-1)/2;
    int twominus=(n-2)/2;
    int pos=0;
    for(int end=pos+twominus;pos<end;++pos){
//      std::cout<<"2*-"<<a[pos]<<std::endl;
      ans1-=2*a[pos];
    }
//    std::cout<<"-"<<a[pos]<<std::endl;
    ans1-=a[pos++];
    if(n%2!=0){
//      std::cout<<"-"<<a[pos]<<std::endl;  
      ans1-=a[pos++];
    }
    if(n%2==0){
//      std::cout<<"+"<<a[pos]<<std::endl;
      ans1+=a[pos++];
    }
    for(int end=pos+twoplus;pos<end;++pos){
//      std::cout<<"2*"<<a[pos]<<std::endl;
      ans1+=2*a[pos];
    }
  }
  
  long long ans2=0;
  {
//    std::cout<<"ans2"<<std::endl;
    int twominus=(n-2+2-1)/2;
    int twoplus=(n-2)/2;
    int pos=0;
    for(int end=pos+twominus;pos<end;++pos){
//      std::cout<<"2*-"<<a[pos]<<std::endl;
      ans2-=2*a[pos];
    }
    if(n%2==0){
//      std::cout<<"-"<<a[pos]<<std::endl;
      ans2-=a[pos++];
    }
//    std::cout<<"+"<<a[pos]<<std::endl;
    ans2+=a[pos++];
    if(n%2!=0){
//      std::cout<<"+"<<a[pos]<<std::endl;
      ans2+=a[pos++];
    }
    for(int end=pos+twoplus;pos<end;++pos){
//      std::cout<<"2*"<<a[pos]<<std::endl;
      ans2+=2*a[pos];
    }
  }
  std::cout<<std::max(ans1,ans2)<<std::endl;
  return 0;
}


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

#define REP(i, n) for (int i = 0; i < (n); ++i)

#define RATE 380000.0

int main(void) {
    int n;
    double x, ans = 0.0;
    string u;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    REP(i, n) {
        cin >> x >> u;
        ans += (u == "BTC")? x * RATE : x;
    }

    cout << fixed << setprecision(10) << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>
       
using namespace std;
       
#define endl '\n'
#define MOD 1000000007
#define INF 1ll<<30
 
// #define MAX 100010
 
#define eps 1e-11
#define bit_max 1ll<<32
#define _USE_MATH_DEFINES
 
long long int fact[3000];
 
void pre()
{
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<2005;i++)
    {
        fact[i]= (fact[i-1]*i)%MOD;
    }
}
 
long long int poww(long long int a,long long int b)
{
    if(b==0)
        return 1;
    long long int x = poww(a,b/2)%MOD;
    if(b%2==0)
    {
        return (x*x)%MOD;
    }
    else
    {
        return (((x*x)%MOD)*a)%MOD;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
    #endif
    string a;
    cin>>a;
    int pos_a=-1,pos_z=-1;
    for(int i=0;i<a.length();i++)
    {
        if(a[i]=='A'&&pos_a==-1)
        {
            pos_a = i;
        }
        if(a[i]=='Z')
            pos_z=i;
    }
    if(pos_z!=-1&&pos_a!=-1)
        cout<<pos_z - pos_a+1<<endl;
 
    return 0;
}

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

namespace ABC110C
{
    static class MainClass
    {

        public static void Main(string[] args)
        {


            char[] S = Console.ReadLine().ToCharArray();
            char[] T = Console.ReadLine().ToCharArray();

            int[] start = (new int[26]).Select(a => -1).ToArray();
            int[] goal = (new int[26]).Select(a => -1).ToArray();


            for(int i = 0; i < S.Length; i++)
            {
                int st = (int)S[i] - (int)'a';
                int gl = (int)T[i] - (int)'a';
           

                if (start[st] >= 0 || goal[gl] >= 0)
                { 
                     if (start[st] != gl || goal[gl] != st)
                     {
                          Console.WriteLine("No");
                         return;
                    
                      }
               }
                else
                {
                    start[st] = gl;
                    goal[gl] = st;
                }
            }

            Console.WriteLine("Yes");



        }
    }
}







Measured memory_bytes: 15456
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <set>
using namespace std;
using ll = long long;

int main()
{
  // 整数の入力
  ll N, X, M;
  cin >> N >> X >> M;
  vector<ll> periods;
  set<ll> used;
  periods.push_back(X);
  while (used.find((X * X) % M) == used.end())
  {
    X = X * X % M;
    used.insert(X);
    periods.push_back(X);
  }
  ll period_start_number = X * X % M;
  bool period_started = false;
  vector<ll> period_sums;
  vector<ll> head_sums;
  period_sums.push_back(0);
  head_sums.push_back(0);
  for (int i = 0; i < periods.size(); i++)
  {
    if (periods[i] == period_start_number)
    {
      period_started = true;
    }
    if (period_started)
    {
      period_sums.push_back(period_sums.back() + periods[i]);
    }
    else
    {
      head_sums.push_back(head_sums.back() + periods[i]);
    }
  }

  ll remain = N;
  ll head = min((ll)head_sums.size() - 1, remain);
  remain = remain - head;
  ll period_times = remain / (period_sums.size() - 1);
  ll period_remain = remain % (period_sums.size() - 1);
  // cout << head << " " << period_times << " " << period_remain << endl;
  cout << head_sums[head] + period_sums.back() * period_times + period_sums[period_remain] << endl;
  return 0;
}


Measured memory_bytes: 6780
module Main where

import Data.List
import Control.Monad
import Debug.Trace
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)


readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as = let
    (fo, la) = span f as
    las = case la of
        [] -> []
        xs -> split f $ tail xs
    in
        case fo of
            [] -> las
            xs -> xs : las


main = do
    num <- readInt
    print $ if even num then num `div` 2 else num `div` 2 + 1


Measured memory_bytes: 380
#include <iostream>
#include <vector>
#include <string>

#define rep(i, n) for (int i = 0; i < n; ++i)
typedef unsigned long long ll;

using namespace std;

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    ll cnt = n / (a + b);
    ll amari = n % (a + b);
    ll blue = min(amari, a);
    cout <<(blue + cnt * a) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  vector<int> cnt(N);
  rep(i, M) {
    cin >> A[i] >> B[i];
    A[i]--; B[i]--;
    cnt[A[i]]++; cnt[B[i]]++;
  }
  rep(i, N) if(cnt[i]%2) {
    cout << "NO" << "\n";
    return 0;
  }
  cout << "YES" << "\n";
  return 0;
}


Measured memory_bytes: 4508
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int lli;
const lli N=1e6+5;
lli b[N], can[N], ans;
vector<lli> v;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    lli n;
    cin>>n;
    lli i,j,num,a[n];
    
    for(i=0;i<n;i++) 
    {
        cin>>a[i];
        if(b[a[i]]==0) v.push_back(a[i]);
        b[a[i]]++;
    }
    sort(v.begin(), v.end());
    
    for(i=0;i<v.size();i++)
    {
        num=v[i];
        if(can[num]==0)
        {
            for(j=2*num; j<N;j+=num) can[j]++;
        }
    }
    for(i=0;i<n;i++)
    {
        if(b[a[i]]==1 && can[a[i]]==0) ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 21784
array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, \
2, 5, 4, 1, 4, 1, 51]

inp = input()

inp = int(inp)

print('{}'.format(array[inp-1]))



Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

int k;
int ans;

signed main() {
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	cin >> k;
	int p = k;
	while (p) {
		bool bl = false;
		for (int j = 0; j < 10; j++)if ((p + k * j) % 10 == 7) {
			bl = true;
			p = p + k * j;
			break;
		}
		if (!bl) {
			cout << -1 << endl;
			return 0;
		}
		while (p % 10 == 7)ans++, p /= 10;
	}
	cout << ans << endl;
}


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

const int MAX_N = 110000;

int dp[MAX_N]; // dp[i] が i についての答え

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

    // 初期化
    for (int i = 0; i < MAX_N; ++i) dp[i] = N; // INF の気持ち
    dp[0] = 0;

    // 貰う DP --- dp[n] に遷移を集める
    for (int n = 1; n <= N; ++n) {
        for (int pow6 = 1; pow6 <= n; pow6 *= 6) {
            dp[n] = min(dp[n], dp[n - pow6] + 1);
        }
        for (int pow9 = 9; pow9 <= n; pow9 *= 9) {
            dp[n] = min(dp[n], dp[n - pow9] + 1);
        }
    }

    cout << dp[N] << endl;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    int K = N - M;

    cout << (1900 * M + 100 * K) * pow(2, M) << endl;
}

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

int main(void){
    
    unsigned int n = 0;
    
    cin >> n;
    
    int min = 1000000;
    int max = -1000000;
    long sum = 0;
    for(int i = 0 ; i < n ; i++){
        int a = 0;
        cin >> a;

        sum += a;
        if(a < min){
            min = a;
        }    
        if(a > max){
            max = a;
        }
    }

    cout << min << ' ' << max << ' ' << sum << endl; 

    return 0;
    
}

Measured memory_bytes: 1168
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	if(a+b==c||b+c==a||c+a==b){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

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

int main(){
  int n,k;
  cin >> n >> k;
  int a[n];
  for(int i=0;i<n;i++){
  cin >> a[i];
  }
  long long b;
  for(int q=0;q<k;q++){b+=a[q];}
  long long km=b;
  for(int i=1;i<n-k+1;i++){
    b= b-a[i-1]+a[i+k-1];
    km=max(km,b);
  }
  double ans=(double)(km+k)/2;
printf("%.12lf\n",ans);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
int main()
{
    int N, M;
    cin >> N >> M;

    vector<vector<int>> ab(N, vector<int>(N, 0));

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        ab[a - 1][b - 1]++;
        ab[b - 1][a - 1]++;
    }

    rep(i, N) {
        int ans = 0;
        rep(j, N) {
            ans += ab[i][j];
        }
        cout << ans << endl;
    }
    return 0;
}

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



#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace __gnu_pbds;

typedef tree<pair<int,int>,null_type,less <pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>ind_set;
typedef gp_hash_table<long long, long long, hash<long long> > ht1;   /// if clear is required
typedef cc_hash_table<long long, long long, hash<long long> > ht2;

///*X.find_by_order("index")
///X.order_of_key("key")

///#define int long long
#pragma GCC optimize ("O3")
#define ll long long
#define vec vector <int>
#define vecl vector <long long>
#define rep(i,a,b) for (ll i=a;i<b;i++)
#define repD(i,a,b) for (ll i=a;i>b;i--)
#define pb push_back
#define pii pair <int,int>
#define pll pair <long long,long long>
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define maa 1000000007
#define Eps 1e-9

int n,arr[100005];
int F1[100005],F2[100005];

void solve()
{
    cin>>n;
    rep(i,0,n)
    {
        cin>>arr[i];
        if (i&1)
        {
            F1[arr[i]]++;
        }
        else F2[arr[i]]++;
    }
    auto p1=max_element(F1,F1+100005),p2=max_element(F2,F2+100005);

    if (p1-F1==p2-F2)
    {
        int t1=0,t2=0;
        rep(i,0,100005)
        {
            if (i!=p1-F1)t1=max(t1,F1[i]);
            if (i!=p2-F2)t2=max(t2,F2[i]);
        }
        if (t1>t2)
        {
            cout<<n-t1-*p2<<"\n";
        }
        else cout<<n-*p1-t2<<"\n";
    }
    else cout<<n-*p1-*p2<<"\n";
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

///freopen("input.txt","r",stdin);
///freopen("output.txt","w",stdout);

    int t=1;
    ///cin>>t;

    rep(a,0,t)
    {
        ///cout<<"Test "<<a+1<<"\n";
        solve();
    }

}


Measured memory_bytes: 1408
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <typeinfo>
#include <map>
#define INF 100000000
#define rep(i,a) for(int i=0;i<(a);i++)

using namespace std;
typedef long long ll;





int main(){
    ll a,b;
    while(cin>>a>>b){
        ll sum=a*b;
        printf("%15.10lf\n",sum/3.305785);
    }
    return 0;
}

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

static int minElement(const int* array, size_t size)
{
    size_t i;
    int min;

    assert(array != NULL);
    assert(size >= 1);

    min = array[0];
    for (i = 1; i < size; ++i) {
        if (min > array[i]) {
            min = array[i];
        }
    }

    return min;
}

int main(){
    int n,w[100],c[100],ans;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    for (int i = 1; i <= n; i++){
        int s1 = 0;
        int s2 = 0;
        for (int j = 0; j < n; j++) {
            if ( j <= i) {
                s1 += w[j];
            } else {
                s2 += w[j];
            }
        }
        c[i-1] = abs(s1-s2);
    }

    cout << minElement(c, n) << endl;
}

Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607???"Invest Master"
//???????§£?????????????????£????????????????????????????????£????¨???¶?????????
//DP????§????????????????
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef pair<int,int> P;
 
int dp[11][100001];
int n, d, x;
int p[10][10];
 
int main(){
    cin >> n >> d >> x;
    rep(i,d) rep(j,n) cin >> p[i][j];
    rep(i,d) rep(j,100001) dp[i][j] = j;
    for(int i = d-2; i >= 0; i--){
        for(int j = 1; j <= 100000; j++){
            rep(k,n){
                if(p[i][k] > j || p[i][k] >= p[i+1][k]) continue;
                dp[i][j] = max(dp[i][j],p[i+1][k]+dp[i][j-p[i][k]]);
            }
        }
    }
    int ans = x;
    for(int i = 0; i <= d-2; i++) ans = dp[i][ans];
    cout << ans << endl;
}

Measured memory_bytes: 5252
import sys
from collections import deque
import time
input = sys.stdin.readline

n, m = map(int, input().split())

path = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

ans = [0] * (n+1)
alr = [0] * (n+1)
que = deque([1])
while len(que) > 0:
    idx = que.popleft()
    for i in path[idx]:
        if alr[i] == 0:
            que.append(i)
            ans[i] = idx
            alr[i] = 1
        else:
            pass

print('Yes')
for i in range(2, n+1):
    print(ans[i])


Measured memory_bytes: 34736
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


int main(){
	char ss[500];
	int i,c;
	c=0;
	while(0<=scanf("%s",ss)){
		for(i=0;i<=strlen(ss)-1;i++){
			if(ss[i]!=ss[strlen(ss)-i-1])break;
		}
		
		if(i==strlen(ss))++c;
	}
	printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

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

const int MAXP = 5010;

struct pall
{
    int x,y;
    pall(int x,int y):x(x),y(y){};
};

char p[MAXP][MAXP];
vector<pall> palls;

int main()
{
    int n;
    while(cin >> n && n)
    {
        palls.clear();
        int ans=0;
        memset(p,0,sizeof(p));
        int x,y;
        REP(n)
        {
            cin >> x >> y;
            p[x][y] = true;
            pall temp = pall(x,y);
            palls.push_back(temp);
        
        }
        if(n<4) break;
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)
        {
            int xa,xb,ya,yb,dx,dy;
            xa = palls[i].x;
            ya = palls[i].y;
            xb = palls[j].x;
            yb = palls[j].y;
            dx = xa - xb;
            dy = ya - yb;
            if((xa-dy>=0)&&xa-dy<=5000&&  (ya+dx>=0) && ya+dx<=5000&& (xb-dy>=0) &&xb-dy<=5000&& (yb+dx>=0)&& yb+dx<=5000  )
                if( p[xa-dy][ya+dx]  && p[xb-dy][yb+dx])ans = max(ans,dx*dx + dy * dy);
            
            if((xa+dy>=0)&&xa+dy<=5000 && (ya-dx>=0) && ya-dx<=5000 && (xb+dy>=0)&& xb+dy<=5000 && (yb-dx >=0)&&yb-dx<=5000 )
                if( p[xa+dy][ya-dx] && p[xb+dy][yb-dx])ans = max(ans,dx*dx + dy * dy);
        }
        cout << ans << endl;
    }
    
    return 0;
}

Measured memory_bytes: 24000
#include <iostream>
#include <cmath>

using namespace std;

long long panduan(long long n){
    int s = 0;
    while(n > 0){
        s += n%10;
        n /= 10;
    }
    return s;
}

void Core(){
    long long n,tmp,x = 1;
    cin>>n;
    long long s = panduan(n);
    tmp = n;
    while(tmp >= 10){
        tmp /= 10;
        x *= 10;
    }
    s = max(s,panduan(n/x*x - 1));
    cout<<s<<endl;
}

int main(){
    Core();
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define MOD 1000000007

//define
ll X;
int n, m;
struct Data{
	int x, y, v;
	bool operator<(const Data a)const{
		return v < a.v;
	}
}d[2333];

void input(){
	scanf("%d %d", &n, &m);
	scanf("%lld", &X);
	for(int i = 1; i <= m; i++)
		scanf("%d %d %d", &d[i].x, &d[i].y, &d[i].v);
	std::sort(d + 1, d + m + 1);
}

//work
ll ans;
int fa[1111];
int ls, mr, eq;

int find(int a){
	if(fa[a] == a) return a;
	return fa[a] = find(fa[a]);
}

void Kruskal(int a){
	ans = 0;
	for(int i = 1; i <= n; i++) fa[i] = i;
	ans = d[a].v;
	fa[d[a].x] = d[a].y;
	for(int i = 1; i <= m; i++){
		if(i == a) continue;
		int u = find(d[i].x), v = find(d[i].y);
		if(u == v) continue;
		fa[u] = v;
		ans = ans + d[i].v;
	}
	if(ans < X) ls++;
	if(ans == X) eq++;
	if(ans > X) mr++;
}

int Ans;

ll quickpow(ll p,ll k)
{
	ll tmp=1;
	while(k)
	{
		if(k&1)
			tmp=(tmp*p)%MOD;
		p=(p*p)%MOD;
		k>>=1;
	}
	return tmp;
}

void work(){
	/*p[0] = 1;
	for(int i = 1; i <= n; i++)
		p[i] = p[i - 1] * 2 % MOD;*/
	for(int i = 1; i <= m; i++) Kruskal(i);
	if(eq == 0) puts("0");
	else if(ls == 0)
		printf("%lld\n", 1ll * ((quickpow(2, eq) - 2 + MOD) % MOD) * quickpow(2, mr) % MOD);
	else
		printf("%lld\n", 2ll * ((quickpow(2, eq) - 1 + MOD) % MOD) % MOD * quickpow(2, mr) % MOD);
}

int main(){
	input();
	work();
	return 0;
}

Measured memory_bytes: 128
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortresult:
        div.sort()
    return div
# endregion
N, K = ri_()
h = ri_()
dp = [INF] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])

Measured memory_bytes: 81168
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 11451419194545;

int main(){
    ll N; cin >> N;
    if(N == 1){
        cout << "Hello World" << endl;
    }else{
        ll A, B;
        cin >> A >> B;
        cout << A + B << endl;
    }
}

Measured memory_bytes: 256
a,b,c = gets.chomp.split(' ').map(&:to_i)
ans = "No"
if a == b
  if a != c
    ans = "Yes"
  end
elsif b == c
  if a != c
    ans = "Yes"
  end
elsif a == c
  if a != b
    ans = "Yes"
  end
end

puts ans

Measured memory_bytes: 1788
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define MAX_V  21;

struct edge{ int to, cost; };
typedef pair<int , int> P;


int V;

int INF = 10000000;
vector<edge> G[22];
int d[22];
int m;
int a1,b1,c1,d1;

bool operator < (P a,P b){
	return a.first == b.first;
}
bool comp(P a,P b){
	return a.first < b.first;
}


void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > que;
	fill(d,d+V+1, INF);
	d[s] = 0;
	que.push(P(0,s));
	
	while (!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		//cout<<" que top "<<v<<endl;
		if (d[v] < p.first) continue;
		for(int i=0;i<G[v].size();i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				//cout<<e.to<< " "<<d[e.to]<<endl;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main(){
	char t;
	int go,come;
	cin>>V>>m;
	rep(i,m){
		edge tmp;
		cin>>a1>>t>>b1>>t>>c1>>t>>d1;
		//cout<<a1<<endl;
		tmp.to = b1; tmp.cost = c1;
		G[a1].push_back(tmp);
		tmp.to = a1; tmp.cost = d1;
		G[b1].push_back(tmp);
	}
	/*
	rep(i,V+1){
		rep(j,G[i].size()){
			cout<<i<< " "<<G[i][j].to<< " "<<G[i][j].cost<<endl;
		}
	}
	*/
	cin>>a1>>t>>b1>>t>>c1>>t>>d1;
	dijkstra(a1);
	go = d[b1];
	
	//cout<<"go  d[i]\n";
	rep(i,V+1){
		//cout<<i<<" "<<d[i]<<endl;
	}
	
	//cout<<"go = "<< go<< endl;
	dijkstra(b1);
	come = d[a1];
	//cout << "come = " << come<< endl;
	cout<<c1-d1-go-come<<endl;
	return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int a,b;
  	cin >> a >> b;
  	//cout << a << b;
  	if((a+b)%2 == 0){
      	cout << (a+b)/2 << endl;
	}
    else{
      	cout << (a+b)/2+1 << endl;
    }
}

Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TestApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = Console.ReadLine()
                .Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
                .Select(x => int.Parse(x))
                .ToArray();
            int max = str[0];
            var a = 0;
            for (int i = 1; i <= max; i++)
            {
                var ls = i.ToString()
                    .Select(x => int.Parse(x.ToString()))
                    .ToArray();
                var sum = 0;

                foreach (var item in ls)
                {
                    sum += item;
                }
                if (sum >= str[1] && sum <= str[2])
                    a += i;
            }
            Console.WriteLine(a);
            Console.ReadLine();
        }
    }

}

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

int main()
{
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i,n) cin >> x[i];
    int p = accumulate(x.begin(), x.end(),0)/n;
    auto square = [&](vector<int> x, int p){
        int ans =0;
        rep(i,n){
            ans += pow(x[i]-p,2);
        }
        return ans;
    };
    int ans = min(square(x,p), square(x,p+1));
    cout << ans << endl;
}

Measured memory_bytes: 3636
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[] A = new int[N];
    int[] B = new int[N-1];

    for (int i=0; i < N-1; i++) {
        B[i] = Integer.parseInt(sc.next()); 
    }
    int sum = 0;

    if(B.length == 1){
        System.out.println(B[0]*2);
        return;
    }else{
        sum = B[0];
        for(int i = 1; i < N-1  ;i++){
            sum += Math.min(B[i], B[i-1]);
            }
        
        }
        sum += B[N-2]; 
        System.out.println(sum);
  }
}



Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N, K, sum;
  cin >> N >> K;
  sum = 0;
  for (int i=0;i<N;i++){
    int x ;
    cin >> x;
    if (2*x <= K){
      sum += 2*x;
    }
    else{
      sum += 2*(K-x);
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

int main() {
    fastio();

    int a, b, c, d;

    cin >> a >> b >> c >> d;

    cout << max(0, min(d, b) - max(c, a)) << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
lis = str(input())
r = []
g = []
b = []
for i in range(n):
  if lis[i] == "R":
    r.append(i)
  elif lis[i] == "G":
    g.append(i)
  else:
    b.append(i)
ans = len(r) * len(g) * len(b)
for i in range(1,n-1):
  for j in range(i+1,n):
    if i != j and 2 * j -i <= n:
      k = j + (j-i)
      if (lis[i-1] != lis[j-1]) and (lis[j-1] != lis[k-1]) and (lis[k-1] != lis[i-1]):
        ans -= 1
print(ans)


Measured memory_bytes: 68156
/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/

const int MAXN=200000+20;
int n,p[MAXN],v[MAXN];
mp inf[MAXN];
LL rest[MAXN];
set<pair<double,int> > s;
double val(int A,int B){
	if(A==0) return (double)(INF);
	return (double)(B)/(double)(A);
}
int fa[MAXN];
int root(int x){
	return fa[x]=(fa[x]==x? x:root(fa[x]));
}
void merge(int u,int v){
	//u->v    pick u right after picking v
	u=root(u);
	v=root(v);
	if(u!=v){
		fa[u]=v;
		s.erase(II(val(inf[v].FIR,inf[v].SEC),v));
		rest[v]+=rest[u]+1ll*inf[v].SEC*inf[u].FIR;
		inf[v].FIR+=inf[u].FIR;
		inf[v].SEC+=inf[u].SEC;
		s.insert(II(val(inf[v].FIR,inf[v].SEC),v));
	}
}
int main(){
	fastio;
	R(n);
	rb(i,2,n){
		R(p[i]);	
	}
	rb(i,1,n) fa[i]=i;
	rb(i,1,n) R(v[i]);
	rb(i,1,n){
		inf[i]=II(0,0);
		if(v[i]==1){
			inf[i].SEC=1;
		}
		else{
			inf[i].FIR=1;
		}
		s.insert(II(val(inf[i].FIR,inf[i].SEC),i));
	}
	while(!s.empty()){
		int now=(*s.begin()).SEC;
		s.erase(s.begin());
		if(now!=1){
			int v=root(p[root(now)]);
			merge(root(now),v);
		}
	}
	cout<<rest[1]<<endl;
	return 0;
}
/** 程序框架：
  *
  *
  *
  *
  **/


Measured memory_bytes: 21600
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t A, B, C, K;
    std::cin >> A >> B >> C >> K;

    if ((K & 1) == 1) {
        std::cout << B - A << std::endl;
    }
    else {
        std::cout << A - B << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main (void){
    int n, k, x, y;
    scanf("%d", &n);
    scanf("%d", &k);
    scanf("%d", &x);
    scanf("%d", &y);
if(k < n)
    printf("%d\n", (x*k) + (y*(n-k)));

    else printf("%d\n", x*n);
    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;

int main(){
  ll N,ans;
  cin>>N;

  for(ll i=1;i<=100000;i++){
    if(i*i>N) {
      ans=(i-1)*(i-1);
      break;
    }
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void) {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int cnt = 0;
  for(int i = 0; i < n - 2; i++) {
    if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int l,m,n;
int a,b;
double rate;
int main(){
  int Tc;
  cin>>Tc;
  for(int tc=0;tc<Tc;tc++){
    cin>>l>>m>>n;
    int Ans=0;
    for(int i=0;i<n;i++){
      cin>>a>>rate>>b;
      int ans=l;
      if(!a){
	int sum=0;
	for(int j=0;j<m;j++){
	  int d=ans*rate;
	  sum+=d;
	  ans-=b;
	}
	ans+=sum;
	Ans=max(Ans,ans);
      }else{
	for(int j=0;j<m;j++){
	  int d=ans*rate;
	  ans+=d;
	  ans-=b;
	}
	Ans=max(Ans,ans);
      }
    }
    cout<<Ans<<endl;
  }
  return 0;
}

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

using namespace std;

const int maxn = 1e5+100;

int n, k, h[maxn], dp[maxn];

int solve(int x){
    if(dp[x]!=0x3f3f3f3f)return dp[x];
    if(x>n)return 0x3f3f3f3f;
    if(x==n)return 0;
    for(int i=1; i<=k; i++){
        dp[x]=min(dp[x], abs(h[x]-h[x+i]) + solve(x+i));
    }
    return dp[x];
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> k;

    for(int i=1; i<=n; i++)cin >> h[i];

    memset(dp, 0x3f3f3f3f, sizeof dp);

    cout << solve(1) << endl;
}


Measured memory_bytes: 5760
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;
typedef unsigned char byte;

int main() {
    speed;
    ll h, ans = 0, n = 1;
    cin >> h;
    while (h) {
        ans += n;
        h /= 2;
        n *= 2;
    }
    cout << ans;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 1000000007;
LL H, W;
std::vector<std::string>a;
std::vector<std::vector<LL>>memo;

LL dp(LL i, LL j)
{
	if (i == H - 1 && j == W - 1) return 1;
	if (memo[i][j] != -1) return memo[i][j];
	LL res1 = 0, res2 = 0;
	if (i < H - 1) if (a[i + 1][j] == '.') res1 = dp(i + 1, j);
	if (j < W - 1) if (a[i][j + 1] == '.') res2 = dp(i, j + 1);
	return memo[i][j] = (res1 + res2) % mod;
}

int main()
{
	in >> H >> W;
	a.resize(H);
	rep(i, H) in >> a[i];

	memo.resize(H);
	rep(i, memo.size()) memo[i].resize(W, -1);
	out << dp(0, 0) << std::endl;
}


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

typedef long long ll;
typedef vector<int> vi;

int main(){
	int N;
    cin >> N;
    vi a(N);
    rep(i, N){
        cin >> a[i];
    }

    sort(a.begin(), a.end());
    int sum = 0;
    rep(i, N){
        sum += a[i];
    }

    int ans;
    rep(i, N){
        if(sum % 10 != 0){
            ans = sum;
            break;
        }
        ans = sum - a[i];
        if(ans % 10 != 0)
            break;
    }

    if(ans % 10 != 0)
        cout << ans << endl;
    else{
        cout << 0 << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

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

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

int main(int argc,char* argv[]){
    int n,m;
    cin >> n >> m;

    vector<int> k(n);
    vector<int> ans(m+1);
    for(int i=0;i<n;i++){
        cin >> k[i];
        for(int j=0;j<k[i];j++){
            int aval;
            cin >> aval;
            ans[aval]++;
        }
    }

    int count=0;
    for(int i=1;i<m+1;i++){
        if(ans[i]==n)count++;
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#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 repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define all(x) (x).begin(), (x).end()
#define show(x) #x " = " << x
template <class T> bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; }

int main() {
    int n; cin >> n;
    vector<int> h(n);
    rep (i,n) cin >> h[i];

    int c = 0;
    for (int i = 0; i < n; i++) {
        int c1 = 0;
        while (i+1<n && h[i] >= h[i+1]) i++,c1++;
        chmax(c,c1);
    }
    cout << c << endl;
}


Measured memory_bytes: 640